yog_data/
binary.rs

1//! The binary form — what the build compiles content to and the runtime and
2//! the Java hosts read, like NBT:
3//!
4//! ```text
5//! "YOGD" version:u8
6//! strings: varint count, then each as varint length + UTF-8
7//! root value
8//! ```
9//!
10//! A value is a tag byte and its payload; every string (map keys too) is an
11//! index into the table, so repeated keys and ids cost one varint each.
12//!
13//! | Tag | Value | Payload |
14//! |---:|---|---|
15//! | 0 | null | — |
16//! | 1, 2 | false, true | — |
17//! | 3 | int | zigzag varint |
18//! | 4 | float | f64, little-endian |
19//! | 5 | string | string |
20//! | 6 | list | varint count, values |
21//! | 7 | map | varint count, (key string, value) pairs |
22//! | 8 | ref | kind string, id string |
23//! | 9 | tag | kind string, id string |
24//! | 10 | resource | set string, key string |
25//! | 11 | text | string |
26//! | 12 | image | string |
27//! | 13 | color | u32, little-endian (`0xAARRGGBB`) |
28//! | 14 | translation key | string |
29//!
30//! Varints are LEB128. Decoding checks every length against the input, so
31//! malformed bytes are an error, never a panic or a huge allocation.
32
33use std::collections::HashMap;
34use std::fmt;
35use std::hash::{BuildHasherDefault, Hasher};
36
37use crate::value::{Map, Ref, Res, Value};
38
39pub const MAGIC: &[u8; 4] = b"YOGD";
40pub const VERSION: u8 = 1;
41
42/// Nested deeper than this is malformed.
43pub const MAX_DEPTH: usize = 256;
44
45mod tag {
46    pub const NULL: u8 = 0;
47    pub const FALSE: u8 = 1;
48    pub const TRUE: u8 = 2;
49    pub const INT: u8 = 3;
50    pub const FLOAT: u8 = 4;
51    pub const STR: u8 = 5;
52    pub const LIST: u8 = 6;
53    pub const MAP: u8 = 7;
54    pub const REF: u8 = 8;
55    pub const TAG: u8 = 9;
56    pub const RES: u8 = 10;
57    pub const TEXT: u8 = 11;
58    pub const IMAGE: u8 = 12;
59    pub const COLOR: u8 = 13;
60    pub const LANG: u8 = 14;
61}
62
63/// `value` in the binary form.
64pub fn encode(value: &Value) -> Vec<u8> {
65    let mut enc = Encoder {
66        body: Vec::new(),
67        strings: HashMap::default(),
68        table: Vec::new(),
69    };
70    enc.value(value);
71    let table_len: usize = enc.table.iter().map(|s| s.len() + 2).sum();
72    let mut out = Vec::with_capacity(5 + table_len + enc.body.len() + 4);
73    out.extend_from_slice(MAGIC);
74    out.push(VERSION);
75    varint(&mut out, enc.table.len() as u64);
76    for s in &enc.table {
77        varint(&mut out, s.len() as u64);
78        out.extend_from_slice(s.as_bytes());
79    }
80    out.extend_from_slice(&enc.body);
81    out
82}
83
84struct Encoder<'v> {
85    body: Vec<u8>,
86    strings: HashMap<&'v str, u32, BuildHasherDefault<Fx>>,
87    table: Vec<&'v str>,
88}
89
90impl<'v> Encoder<'v> {
91    fn string(&mut self, s: &'v str) {
92        let next = self.table.len() as u32;
93        let i = *self.strings.entry(s).or_insert_with(|| {
94            self.table.push(s);
95            next
96        });
97        varint(&mut self.body, i as u64);
98    }
99
100    fn value(&mut self, v: &'v Value) {
101        match v {
102            Value::Null => self.body.push(tag::NULL),
103            Value::Bool(false) => self.body.push(tag::FALSE),
104            Value::Bool(true) => self.body.push(tag::TRUE),
105            Value::Int(n) => {
106                self.body.push(tag::INT);
107                varint(&mut self.body, ((n << 1) ^ (n >> 63)) as u64);
108            }
109            Value::Float(f) => {
110                self.body.push(tag::FLOAT);
111                self.body.extend_from_slice(&f.to_le_bytes());
112            }
113            Value::Str(s) => {
114                self.body.push(tag::STR);
115                self.string(s);
116            }
117            Value::List(items) => {
118                self.body.push(tag::LIST);
119                varint(&mut self.body, items.len() as u64);
120                for item in items {
121                    self.value(item);
122                }
123            }
124            Value::Map(map) => {
125                self.body.push(tag::MAP);
126                varint(&mut self.body, map.len() as u64);
127                for (k, v) in map.iter() {
128                    self.string(k);
129                    self.value(v);
130                }
131            }
132            Value::Ref(r) | Value::Tag(r) => {
133                self.body.push(if matches!(v, Value::Ref(_)) {
134                    tag::REF
135                } else {
136                    tag::TAG
137                });
138                self.string(&r.kind);
139                self.string(&r.id);
140            }
141            Value::Res(r) => {
142                self.body.push(tag::RES);
143                self.string(&r.set);
144                self.string(&r.key);
145            }
146            Value::Text(s) => {
147                self.body.push(tag::TEXT);
148                self.string(s);
149            }
150            Value::Image(s) => {
151                self.body.push(tag::IMAGE);
152                self.string(s);
153            }
154            Value::Lang(s) => {
155                self.body.push(tag::LANG);
156                self.string(s);
157            }
158            Value::Color(c) => {
159                self.body.push(tag::COLOR);
160                self.body.extend_from_slice(&c.to_le_bytes());
161            }
162        }
163    }
164}
165
166/// rustc's Fx hash — the string table's keys are short and not adversarial.
167#[derive(Default)]
168struct Fx(u64);
169
170impl Fx {
171    fn add(&mut self, word: u64) {
172        self.0 = (self.0.rotate_left(5) ^ word).wrapping_mul(0x51_7c_c1_b7_27_22_0a_95);
173    }
174}
175
176impl Hasher for Fx {
177    fn write(&mut self, bytes: &[u8]) {
178        let (words, rest) = bytes.as_chunks::<8>();
179        for w in words {
180            self.add(u64::from_le_bytes(*w));
181        }
182        if !rest.is_empty() {
183            let mut b = [0u8; 8];
184            b[..rest.len()].copy_from_slice(rest);
185            self.add(u64::from_le_bytes(b));
186        }
187    }
188
189    fn write_u8(&mut self, b: u8) {
190        self.add(b as u64);
191    }
192
193    fn finish(&self) -> u64 {
194        self.0
195    }
196}
197
198fn varint(out: &mut Vec<u8>, mut n: u64) {
199    while n >= 0x80 {
200        out.push((n as u8) | 0x80);
201        n >>= 7;
202    }
203    out.push(n as u8);
204}
205
206/// Malformed binary data.
207#[derive(Debug, Clone, PartialEq, Eq)]
208pub struct DecodeError {
209    pub message: String,
210    pub offset: usize,
211}
212
213impl fmt::Display for DecodeError {
214    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
215        write!(f, "byte {}: {}", self.offset, self.message)
216    }
217}
218
219impl std::error::Error for DecodeError {}
220
221/// Reads the binary form.
222pub fn decode(bytes: &[u8]) -> Result<Value, DecodeError> {
223    let mut d = Decoder {
224        b: bytes,
225        i: 0,
226        strings: Vec::new(),
227    };
228    if !bytes.starts_with(MAGIC) {
229        return Err(d.error("not Yog Data (no `YOGD` header)"));
230    }
231    d.i = 4;
232    let version = d.byte()?;
233    if version != VERSION {
234        return Err(d.error(format!(
235            "Yog Data version {version}, this reads version {VERSION}"
236        )));
237    }
238    let count = d.count(1)?;
239    d.strings.reserve(count);
240    for _ in 0..count {
241        let len = d.count(1)?;
242        let start = d.i;
243        let s = std::str::from_utf8(&bytes[start..start + len]).map_err(|_| DecodeError {
244            message: "a string isn't UTF-8".into(),
245            offset: start,
246        })?;
247        d.strings.push(s);
248        d.i += len;
249    }
250    let v = d.value(0)?;
251    if d.i != bytes.len() {
252        return Err(d.error("bytes after the value"));
253    }
254    Ok(v)
255}
256
257struct Decoder<'b> {
258    b: &'b [u8],
259    i: usize,
260    strings: Vec<&'b str>,
261}
262
263impl<'b> Decoder<'b> {
264    fn error(&self, message: impl Into<String>) -> DecodeError {
265        DecodeError {
266            message: message.into(),
267            offset: self.i,
268        }
269    }
270
271    fn byte(&mut self) -> Result<u8, DecodeError> {
272        let b = *self
273            .b
274            .get(self.i)
275            .ok_or_else(|| self.error("unexpected end"))?;
276        self.i += 1;
277        Ok(b)
278    }
279
280    fn varint(&mut self) -> Result<u64, DecodeError> {
281        let mut n = 0u64;
282        for shift in (0..64).step_by(7) {
283            let b = self.byte()?;
284            n |= ((b & 0x7F) as u64) << shift;
285            if b & 0x80 == 0 {
286                return Ok(n);
287            }
288        }
289        Err(self.error("varint longer than 64 bits"))
290    }
291
292    /// A length, checked against what's left: each of the `count` things takes at least `min` bytes.
293    fn count(&mut self, min: usize) -> Result<usize, DecodeError> {
294        let n = self.varint()?;
295        let left = self.b.len() - self.i;
296        if n > (left / min.max(1)) as u64 {
297            return Err(self.error(format!("length {n} past the end ({left} bytes left)")));
298        }
299        Ok(n as usize)
300    }
301
302    fn fixed<const N: usize>(&mut self) -> Result<[u8; N], DecodeError> {
303        let bytes = self
304            .b
305            .get(self.i..self.i + N)
306            .ok_or_else(|| self.error("unexpected end"))?;
307        self.i += N;
308        Ok(bytes.try_into().unwrap())
309    }
310
311    fn string(&mut self) -> Result<&'b str, DecodeError> {
312        let i = self.varint()?;
313        self.strings
314            .get(i as usize)
315            .copied()
316            .ok_or_else(|| self.error(format!("string {i} isn't in the table")))
317    }
318
319    fn value(&mut self, depth: usize) -> Result<Value, DecodeError> {
320        if depth > MAX_DEPTH {
321            return Err(self.error(format!("nested deeper than {MAX_DEPTH} levels")));
322        }
323        Ok(match self.byte()? {
324            tag::NULL => Value::Null,
325            tag::FALSE => Value::Bool(false),
326            tag::TRUE => Value::Bool(true),
327            tag::INT => {
328                let z = self.varint()?;
329                Value::Int(((z >> 1) as i64) ^ -((z & 1) as i64))
330            }
331            tag::FLOAT => Value::Float(f64::from_le_bytes(self.fixed()?)),
332            tag::STR => Value::Str(self.string()?.to_string()),
333            tag::LIST => {
334                let n = self.count(1)?;
335                let mut items = Vec::with_capacity(n);
336                for _ in 0..n {
337                    items.push(self.value(depth + 1)?);
338                }
339                Value::List(items)
340            }
341            tag::MAP => {
342                let n = self.count(2)?;
343                let mut map = Map::with_capacity(n);
344                for _ in 0..n {
345                    let k = self.string()?.to_string();
346                    map.push_unchecked(k, self.value(depth + 1)?);
347                }
348                Value::Map(map)
349            }
350            t @ (tag::REF | tag::TAG) => {
351                let r = Ref {
352                    kind: self.string()?.to_string(),
353                    id: self.string()?.to_string(),
354                };
355                if t == tag::REF {
356                    Value::Ref(r)
357                } else {
358                    Value::Tag(r)
359                }
360            }
361            tag::RES => Value::Res(Res {
362                set: self.string()?.to_string(),
363                key: self.string()?.to_string(),
364            }),
365            tag::TEXT => Value::Text(self.string()?.to_string()),
366            tag::IMAGE => Value::Image(self.string()?.to_string()),
367            tag::COLOR => Value::Color(u32::from_le_bytes(self.fixed()?)),
368            tag::LANG => Value::Lang(self.string()?.to_string()),
369            t => {
370                self.i -= 1;
371                return Err(self.error(format!("unknown tag {t}")));
372            }
373        })
374    }
375}
376
377#[cfg(test)]
378mod tests {
379    use super::*;
380
381    fn sample() -> Value {
382        let mut m = Map::new();
383        m.insert("name", Value::Str("Ruby".into()));
384        m.insert(
385            "n",
386            Value::List(vec![
387                Value::Int(0),
388                Value::Int(-1),
389                Value::Int(i64::MAX),
390                Value::Int(i64::MIN),
391                Value::Float(0.5),
392                Value::Null,
393                Value::Bool(true),
394                Value::Bool(false),
395            ]),
396        );
397        m.insert("item", Value::Ref(Ref::new("item", "minecraft:stick")));
398        m.insert("tag", Value::Tag(Ref::new("item", "minecraft:planks")));
399        m.insert(
400            "title",
401            Value::Res(Res {
402                set: "Strings".into(),
403                key: "title".into(),
404            }),
405        );
406        m.insert("text", Value::Text("{b|hi}".into()));
407        m.insert("icon", Value::Image("sprite:x".into()));
408        m.insert("color", Value::Color(0x80FF0000));
409        m.insert("lang", Value::Lang("gui.done".into()));
410        m.insert("again", Value::Str("Ruby".into()));
411        Value::Map(m)
412    }
413
414    #[test]
415    fn round_trips_every_type() {
416        let v = sample();
417        let bytes = encode(&v);
418        assert_eq!(decode(&bytes).unwrap(), v);
419        // "Ruby" is stored once.
420        assert_eq!(bytes.windows(4).filter(|w| w == b"Ruby").count(), 1);
421    }
422
423    #[test]
424    fn malformed_bytes_are_errors() {
425        let bytes = encode(&sample());
426        // Every truncation fails cleanly.
427        for len in 0..bytes.len() {
428            assert!(decode(&bytes[..len]).is_err(), "truncated at {len}");
429        }
430        let mut extra = bytes.clone();
431        extra.push(0);
432        assert!(
433            decode(&extra)
434                .unwrap_err()
435                .message
436                .contains("after the value")
437        );
438        assert!(
439            decode(b"YOGD\x02\x00\x00")
440                .unwrap_err()
441                .message
442                .contains("version 2")
443        );
444        assert!(
445            decode(b"YOGD\x01\x00\x63")
446                .unwrap_err()
447                .message
448                .contains("unknown tag")
449        );
450        assert!(
451            decode(b"YOGD\x01\x00\x05\x00")
452                .unwrap_err()
453                .message
454                .contains("isn't in the table")
455        );
456        // A huge count with nothing behind it doesn't allocate.
457        assert!(
458            decode(b"YOGD\x01\x00\x06\xff\xff\xff\xff\x0f")
459                .unwrap_err()
460                .message
461                .contains("past the end")
462        );
463        let deep: Vec<u8> = b"YOGD\x01\x00"
464            .iter()
465            .copied()
466            .chain(std::iter::repeat_n([6u8, 1], 300).flatten())
467            .chain([0])
468            .collect();
469        assert!(decode(&deep).unwrap_err().message.contains("nested deeper"));
470    }
471}
yog_data/binary.rs

yog_data/
binary.rs
