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 bumpalo::Bump;
38
39use crate::borrowed::{MapRef, ValueRef};
40use crate::value::{Map, Ref, Res, Value};
41
42pub const MAGIC: &[u8; 4] = b"YOGD";
43pub const VERSION: u8 = 1;
44
45/// Nested deeper than this is malformed.
46pub const MAX_DEPTH: usize = 256;
47
48mod tag {
49    pub const NULL: u8 = 0;
50    pub const FALSE: u8 = 1;
51    pub const TRUE: u8 = 2;
52    pub const INT: u8 = 3;
53    pub const FLOAT: u8 = 4;
54    pub const STR: u8 = 5;
55    pub const LIST: u8 = 6;
56    pub const MAP: u8 = 7;
57    pub const REF: u8 = 8;
58    pub const TAG: u8 = 9;
59    pub const RES: u8 = 10;
60    pub const TEXT: u8 = 11;
61    pub const IMAGE: u8 = 12;
62    pub const COLOR: u8 = 13;
63    pub const LANG: u8 = 14;
64}
65
66/// `value` in the binary form.
67pub fn encode(value: &Value) -> Vec<u8> {
68    let mut w = Writer::new();
69    w.value(value);
70    w.finish()
71}
72
73/// Writes the binary form piece by piece, from data that isn't a [`Value`]
74/// — nothing is built or copied on the way; strings are borrowed until
75/// [`Writer::finish`]. A map or list is given its length, then that many
76/// entries (`key` then a value) or values.
77///
78/// ```
79/// let mut w = yog_data::binary::Writer::new();
80/// w.map(2).key("id").str("mymod:ruby").key("count").int(3);
81/// let v = yog_data::binary::decode(&w.finish()).unwrap();
82/// assert_eq!(v.get("count").and_then(|c| c.as_i64()), Some(3));
83/// ```
84pub struct Writer<'v>(Encoder<'v>);
85
86impl Default for Writer<'_> {
87    fn default() -> Self {
88        Self::new()
89    }
90}
91
92impl<'v> Writer<'v> {
93    pub fn new() -> Self {
94        Writer(Encoder { body: Vec::new(), strings: HashMap::default(), table: Vec::new() })
95    }
96
97    pub fn null(&mut self) -> &mut Self {
98        self.0.body.push(tag::NULL);
99        self
100    }
101
102    pub fn bool(&mut self, b: bool) -> &mut Self {
103        self.0.body.push(if b { tag::TRUE } else { tag::FALSE });
104        self
105    }
106
107    pub fn int(&mut self, n: i64) -> &mut Self {
108        self.0.body.push(tag::INT);
109        varint(&mut self.0.body, ((n << 1) ^ (n >> 63)) as u64);
110        self
111    }
112
113    pub fn float(&mut self, f: f64) -> &mut Self {
114        self.0.body.push(tag::FLOAT);
115        self.0.body.extend_from_slice(&f.to_le_bytes());
116        self
117    }
118
119    pub fn str(&mut self, s: &'v str) -> &mut Self {
120        self.0.body.push(tag::STR);
121        self.0.string(s);
122        self
123    }
124
125    /// A list of `len` values.
126    pub fn list(&mut self, len: usize) -> &mut Self {
127        self.0.body.push(tag::LIST);
128        varint(&mut self.0.body, len as u64);
129        self
130    }
131
132    /// A map of `len` entries, each a [`Writer::key`] and a value.
133    pub fn map(&mut self, len: usize) -> &mut Self {
134        self.0.body.push(tag::MAP);
135        varint(&mut self.0.body, len as u64);
136        self
137    }
138
139    pub fn key(&mut self, k: &'v str) -> &mut Self {
140        self.0.string(k);
141        self
142    }
143
144    pub fn value(&mut self, v: &'v Value) -> &mut Self {
145        self.0.value(v);
146        self
147    }
148
149    /// The bytes.
150    pub fn finish(self) -> Vec<u8> {
151        let enc = self.0;
152        let table_len: usize = enc.table.iter().map(|s| s.len() + 2).sum();
153        let mut out = Vec::with_capacity(5 + table_len + enc.body.len() + 4);
154        out.extend_from_slice(MAGIC);
155        out.push(VERSION);
156        varint(&mut out, enc.table.len() as u64);
157        for s in &enc.table {
158            varint(&mut out, s.len() as u64);
159            out.extend_from_slice(s.as_bytes());
160        }
161        out.extend_from_slice(&enc.body);
162        out
163    }
164}
165
166struct Encoder<'v> {
167    body: Vec<u8>,
168    strings: HashMap<&'v str, u32, BuildHasherDefault<Fx>>,
169    table: Vec<&'v str>,
170}
171
172impl<'v> Encoder<'v> {
173    fn string(&mut self, s: &'v str) {
174        let next = self.table.len() as u32;
175        let i = *self.strings.entry(s).or_insert_with(|| {
176            self.table.push(s);
177            next
178        });
179        varint(&mut self.body, i as u64);
180    }
181
182    fn value(&mut self, v: &'v Value) {
183        match v {
184            Value::Null => self.body.push(tag::NULL),
185            Value::Bool(false) => self.body.push(tag::FALSE),
186            Value::Bool(true) => self.body.push(tag::TRUE),
187            Value::Int(n) => {
188                self.body.push(tag::INT);
189                varint(&mut self.body, ((n << 1) ^ (n >> 63)) as u64);
190            }
191            Value::Float(f) => {
192                self.body.push(tag::FLOAT);
193                self.body.extend_from_slice(&f.to_le_bytes());
194            }
195            Value::Str(s) => {
196                self.body.push(tag::STR);
197                self.string(s);
198            }
199            Value::List(items) => {
200                self.body.push(tag::LIST);
201                varint(&mut self.body, items.len() as u64);
202                for item in items {
203                    self.value(item);
204                }
205            }
206            Value::Map(map) => {
207                self.body.push(tag::MAP);
208                varint(&mut self.body, map.len() as u64);
209                for (k, v) in map.iter() {
210                    self.string(k);
211                    self.value(v);
212                }
213            }
214            Value::Ref(r) | Value::Tag(r) => {
215                self.body.push(if matches!(v, Value::Ref(_)) {
216                    tag::REF
217                } else {
218                    tag::TAG
219                });
220                self.string(&r.kind);
221                self.string(&r.id);
222            }
223            Value::Res(r) => {
224                self.body.push(tag::RES);
225                self.string(&r.set);
226                self.string(&r.key);
227            }
228            Value::Text(s) => {
229                self.body.push(tag::TEXT);
230                self.string(s);
231            }
232            Value::Image(s) => {
233                self.body.push(tag::IMAGE);
234                self.string(s);
235            }
236            Value::Lang(s) => {
237                self.body.push(tag::LANG);
238                self.string(s);
239            }
240            Value::Color(c) => {
241                self.body.push(tag::COLOR);
242                self.body.extend_from_slice(&c.to_le_bytes());
243            }
244        }
245    }
246}
247
248/// rustc's Fx hash — the string table's keys are short and not adversarial.
249#[derive(Default)]
250struct Fx(u64);
251
252impl Fx {
253    fn add(&mut self, word: u64) {
254        self.0 = (self.0.rotate_left(5) ^ word).wrapping_mul(0x51_7c_c1_b7_27_22_0a_95);
255    }
256}
257
258impl Hasher for Fx {
259    fn write(&mut self, bytes: &[u8]) {
260        let (words, rest) = bytes.as_chunks::<8>();
261        for w in words {
262            self.add(u64::from_le_bytes(*w));
263        }
264        if !rest.is_empty() {
265            let mut b = [0u8; 8];
266            b[..rest.len()].copy_from_slice(rest);
267            self.add(u64::from_le_bytes(b));
268        }
269    }
270
271    fn write_u8(&mut self, b: u8) {
272        self.add(b as u64);
273    }
274
275    fn finish(&self) -> u64 {
276        self.0
277    }
278}
279
280fn varint(out: &mut Vec<u8>, mut n: u64) {
281    while n >= 0x80 {
282        out.push((n as u8) | 0x80);
283        n >>= 7;
284    }
285    out.push(n as u8);
286}
287
288/// Malformed binary data.
289#[derive(Debug, Clone, PartialEq, Eq)]
290pub struct DecodeError {
291    pub message: String,
292    pub offset: usize,
293}
294
295impl fmt::Display for DecodeError {
296    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
297        write!(f, "byte {}: {}", self.offset, self.message)
298    }
299}
300
301impl std::error::Error for DecodeError {}
302
303/// Reads the binary form.
304pub fn decode(bytes: &[u8]) -> Result<Value, DecodeError> {
305    let mut d = Decoder::open(bytes)?;
306    let v = d.value(0)?;
307    d.end()?;
308    Ok(v)
309}
310
311/// Reads the binary form borrowed: every string points into `bytes`,
312/// lists and maps go in `arena` — nothing is copied. What a schema reads
313/// fastest ([`crate::read_bytes`]).
314pub fn decode_ref<'a>(bytes: &'a [u8], arena: &'a Bump) -> Result<ValueRef<'a>, DecodeError> {
315    let mut d = Decoder::open(bytes)?;
316    let mut stack = Vec::new();
317    let v = d.value_ref(0, arena, &mut stack)?;
318    d.end()?;
319    Ok(v)
320}
321
322impl<'b> Decoder<'b> {
323    /// The header and the string table read; the root value next.
324    fn open(bytes: &'b [u8]) -> Result<Self, DecodeError> {
325        let mut d = Decoder {
326            b: bytes,
327            i: 0,
328            strings: Vec::new(),
329            keys: Vec::new(),
330        };
331        if !bytes.starts_with(MAGIC) {
332            return Err(d.error("not Yog Data (no `YOGD` header)"));
333        }
334        d.i = 4;
335        let version = d.byte()?;
336        if version != VERSION {
337            return Err(d.error(format!(
338                "Yog Data version {version}, this reads version {VERSION}"
339            )));
340        }
341        let count = d.count(1)?;
342        d.strings.reserve(count);
343        for _ in 0..count {
344            let len = d.count(1)?;
345            let start = d.i;
346            let s = std::str::from_utf8(&bytes[start..start + len]).map_err(|_| DecodeError {
347                message: "a string isn't UTF-8".into(),
348                offset: start,
349            })?;
350            d.strings.push(s);
351            d.i += len;
352        }
353        Ok(d)
354    }
355
356    fn end(&self) -> Result<(), DecodeError> {
357        if self.i != self.b.len() {
358            return Err(self.error("bytes after the value"));
359        }
360        Ok(())
361    }
362}
363
364struct Decoder<'b> {
365    b: &'b [u8],
366    i: usize,
367    strings: Vec<&'b str>,
368    /// Map keys made so far, by table index: each key is allocated once.
369    keys: Vec<Option<std::sync::Arc<str>>>,
370}
371
372impl<'b> Decoder<'b> {
373    fn error(&self, message: impl Into<String>) -> DecodeError {
374        DecodeError {
375            message: message.into(),
376            offset: self.i,
377        }
378    }
379
380    fn byte(&mut self) -> Result<u8, DecodeError> {
381        let b = *self
382            .b
383            .get(self.i)
384            .ok_or_else(|| self.error("unexpected end"))?;
385        self.i += 1;
386        Ok(b)
387    }
388
389    fn varint(&mut self) -> Result<u64, DecodeError> {
390        let mut n = 0u64;
391        for shift in (0..64).step_by(7) {
392            let b = self.byte()?;
393            n |= ((b & 0x7F) as u64) << shift;
394            if b & 0x80 == 0 {
395                return Ok(n);
396            }
397        }
398        Err(self.error("varint longer than 64 bits"))
399    }
400
401    /// A length, checked against what's left: each of the `count` things takes at least `min` bytes.
402    fn count(&mut self, min: usize) -> Result<usize, DecodeError> {
403        let n = self.varint()?;
404        let left = self.b.len() - self.i;
405        if n > (left / min.max(1)) as u64 {
406            return Err(self.error(format!("length {n} past the end ({left} bytes left)")));
407        }
408        Ok(n as usize)
409    }
410
411    fn fixed<const N: usize>(&mut self) -> Result<[u8; N], DecodeError> {
412        let bytes = self
413            .b
414            .get(self.i..self.i + N)
415            .ok_or_else(|| self.error("unexpected end"))?;
416        self.i += N;
417        Ok(bytes.try_into().unwrap())
418    }
419
420    fn string(&mut self) -> Result<&'b str, DecodeError> {
421        let i = self.varint()?;
422        self.strings
423            .get(i as usize)
424            .copied()
425            .ok_or_else(|| self.error(format!("string {i} isn't in the table")))
426    }
427
428    /// A map key: shared with every other map that has it.
429    fn key(&mut self) -> Result<std::sync::Arc<str>, DecodeError> {
430        let i = self.varint()? as usize;
431        if let Some(Some(k)) = self.keys.get(i) {
432            return Ok(k.clone());
433        }
434        let s = *self.strings.get(i).ok_or_else(|| self.error(format!("string {i} isn't in the table")))?;
435        let k: std::sync::Arc<str> = s.into();
436        if self.keys.len() <= i {
437            self.keys.resize(self.strings.len(), None);
438        }
439        self.keys[i] = Some(k.clone());
440        Ok(k)
441    }
442
443    /// [`Decoder::value`], borrowed: children gather on `stack`, then move
444    /// into `arena` as one slice.
445    fn value_ref<'a>(&mut self, depth: usize, arena: &'a Bump, stack: &mut Vec<ValueRef<'a>>) -> Result<ValueRef<'a>, DecodeError>
446    where
447        'b: 'a,
448    {
449        if depth > MAX_DEPTH {
450            return Err(self.error(format!("nested deeper than {MAX_DEPTH} levels")));
451        }
452        Ok(match self.byte()? {
453            tag::NULL => ValueRef::Null,
454            tag::FALSE => ValueRef::Bool(false),
455            tag::TRUE => ValueRef::Bool(true),
456            tag::INT => {
457                let z = self.varint()?;
458                ValueRef::Int(((z >> 1) as i64) ^ -((z & 1) as i64))
459            }
460            tag::FLOAT => ValueRef::Float(f64::from_le_bytes(self.fixed()?)),
461            tag::STR => ValueRef::Str(self.string()?),
462            tag::LIST => {
463                let n = self.count(1)?;
464                let start = stack.len();
465                for _ in 0..n {
466                    let v = self.value_ref(depth + 1, arena, stack)?;
467                    stack.push(v);
468                }
469                let items = arena.alloc_slice_copy(&stack[start..]);
470                stack.truncate(start);
471                ValueRef::List(items)
472            }
473            tag::MAP => {
474                let n = self.count(2)?;
475                let mut entries = bumpalo::collections::Vec::with_capacity_in(n, arena);
476                for _ in 0..n {
477                    let k = self.string()?;
478                    entries.push((k, self.value_ref(depth + 1, arena, stack)?));
479                }
480                ValueRef::Map(MapRef(entries.into_bump_slice()))
481            }
482            t @ (tag::REF | tag::TAG) => {
483                let (kind, id) = (self.string()?, self.string()?);
484                if t == tag::REF { ValueRef::Ref { kind, id } } else { ValueRef::Tag { kind, id } }
485            }
486            tag::RES => ValueRef::Res { set: self.string()?, key: self.string()? },
487            tag::TEXT => ValueRef::Text(self.string()?),
488            tag::IMAGE => ValueRef::Image(self.string()?),
489            tag::COLOR => ValueRef::Color(u32::from_le_bytes(self.fixed()?)),
490            tag::LANG => ValueRef::Lang(self.string()?),
491            t => {
492                self.i -= 1;
493                return Err(self.error(format!("unknown tag {t}")));
494            }
495        })
496    }
497
498    fn value(&mut self, depth: usize) -> Result<Value, DecodeError> {
499        if depth > MAX_DEPTH {
500            return Err(self.error(format!("nested deeper than {MAX_DEPTH} levels")));
501        }
502        Ok(match self.byte()? {
503            tag::NULL => Value::Null,
504            tag::FALSE => Value::Bool(false),
505            tag::TRUE => Value::Bool(true),
506            tag::INT => {
507                let z = self.varint()?;
508                Value::Int(((z >> 1) as i64) ^ -((z & 1) as i64))
509            }
510            tag::FLOAT => Value::Float(f64::from_le_bytes(self.fixed()?)),
511            tag::STR => Value::Str(self.string()?.to_string()),
512            tag::LIST => {
513                let n = self.count(1)?;
514                let mut items = Vec::with_capacity(n);
515                for _ in 0..n {
516                    items.push(self.value(depth + 1)?);
517                }
518                Value::List(items)
519            }
520            tag::MAP => {
521                let n = self.count(2)?;
522                let mut map = Map::with_capacity(n);
523                for _ in 0..n {
524                    let k = self.key()?;
525                    map.push_unchecked(k, self.value(depth + 1)?);
526                }
527                Value::Map(map)
528            }
529            t @ (tag::REF | tag::TAG) => {
530                let r = Ref {
531                    kind: self.string()?.to_string(),
532                    id: self.string()?.to_string(),
533                };
534                if t == tag::REF {
535                    Value::Ref(r)
536                } else {
537                    Value::Tag(r)
538                }
539            }
540            tag::RES => Value::Res(Res {
541                set: self.string()?.to_string(),
542                key: self.string()?.to_string(),
543            }),
544            tag::TEXT => Value::Text(self.string()?.to_string()),
545            tag::IMAGE => Value::Image(self.string()?.to_string()),
546            tag::COLOR => Value::Color(u32::from_le_bytes(self.fixed()?)),
547            tag::LANG => Value::Lang(self.string()?.to_string()),
548            t => {
549                self.i -= 1;
550                return Err(self.error(format!("unknown tag {t}")));
551            }
552        })
553    }
554}
555
556#[cfg(test)]
557mod tests {
558    use super::*;
559
560    fn sample() -> Value {
561        let mut m = Map::new();
562        m.insert("name", Value::Str("Ruby".into()));
563        m.insert(
564            "n",
565            Value::List(vec![
566                Value::Int(0),
567                Value::Int(-1),
568                Value::Int(i64::MAX),
569                Value::Int(i64::MIN),
570                Value::Float(0.5),
571                Value::Null,
572                Value::Bool(true),
573                Value::Bool(false),
574            ]),
575        );
576        m.insert("item", Value::Ref(Ref::new("item", "minecraft:stick")));
577        m.insert("tag", Value::Tag(Ref::new("item", "minecraft:planks")));
578        m.insert(
579            "title",
580            Value::Res(Res {
581                set: "Strings".into(),
582                key: "title".into(),
583            }),
584        );
585        m.insert("text", Value::Text("{b|hi}".into()));
586        m.insert("icon", Value::Image("sprite:x".into()));
587        m.insert("color", Value::Color(0x80FF0000));
588        m.insert("lang", Value::Lang("gui.done".into()));
589        m.insert("again", Value::Str("Ruby".into()));
590        Value::Map(m)
591    }
592
593    #[test]
594    fn round_trips_every_type() {
595        let v = sample();
596        let bytes = encode(&v);
597        assert_eq!(decode(&bytes).unwrap(), v);
598        // "Ruby" is stored once.
599        assert_eq!(bytes.windows(4).filter(|w| w == b"Ruby").count(), 1);
600    }
601
602    #[test]
603    fn the_borrowed_decode_reads_the_same_without_copying() {
604        let v = sample();
605        let bytes = encode(&v);
606        let arena = Bump::new();
607        let r = decode_ref(&bytes, &arena).unwrap();
608        assert_eq!(r.to_value(), v);
609        assert_eq!(r, v.borrow(&arena), "borrowing a Value gives the same");
610        // Its strings point into the bytes.
611        let span = bytes.as_ptr_range();
612        let mut strings = Vec::new();
613        fn walk<'a>(v: &ValueRef<'a>, out: &mut Vec<&'a str>) {
614            match v {
615                ValueRef::Str(s) | ValueRef::Text(s) | ValueRef::Image(s) | ValueRef::Lang(s) => out.push(s),
616                ValueRef::List(l) => l.iter().for_each(|x| walk(x, out)),
617                ValueRef::Map(m) => m.iter().for_each(|(k, x)| {
618                    out.push(k);
619                    walk(x, out)
620                }),
621                _ => {}
622            }
623        }
624        walk(&r, &mut strings);
625        assert!(!strings.is_empty() && strings.iter().all(|s| span.contains(&s.as_ptr())));
626        // Malformed bytes are errors here too.
627        for len in 0..bytes.len() {
628            assert!(decode_ref(&bytes[..len], &arena).is_err(), "truncated at {len}");
629        }
630    }
631
632    #[test]
633    fn malformed_bytes_are_errors() {
634        let bytes = encode(&sample());
635        // Every truncation fails cleanly.
636        for len in 0..bytes.len() {
637            assert!(decode(&bytes[..len]).is_err(), "truncated at {len}");
638        }
639        let mut extra = bytes.clone();
640        extra.push(0);
641        assert!(
642            decode(&extra)
643                .unwrap_err()
644                .message
645                .contains("after the value")
646        );
647        assert!(
648            decode(b"YOGD\x02\x00\x00")
649                .unwrap_err()
650                .message
651                .contains("version 2")
652        );
653        assert!(
654            decode(b"YOGD\x01\x00\x63")
655                .unwrap_err()
656                .message
657                .contains("unknown tag")
658        );
659        assert!(
660            decode(b"YOGD\x01\x00\x05\x00")
661                .unwrap_err()
662                .message
663                .contains("isn't in the table")
664        );
665        // A huge count with nothing behind it doesn't allocate.
666        assert!(
667            decode(b"YOGD\x01\x00\x06\xff\xff\xff\xff\x0f")
668                .unwrap_err()
669                .message
670                .contains("past the end")
671        );
672        let deep: Vec<u8> = b"YOGD\x01\x00"
673            .iter()
674            .copied()
675            .chain(std::iter::repeat_n([6u8, 1], 300).flatten())
676            .chain([0])
677            .collect();
678        assert!(decode(&deep).unwrap_err().message.contains("nested deeper"));
679    }
680}
yog_data/binary.rs

yog_data/
binary.rs
