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

yog_data/
binary.rs
