Skip to main content

unityrs_testkit/
blob.rs

1// Ported from UnityPy 1.25.2 (MIT): UnityPy/helpers/TypeTreeNode.py. See THIRD_PARTY_LICENSES.
2//! Typetree node lists, written in the blob format (format 10 and 12 up) or
3//! the old recursive format (below 10, and 11).
4//!
5//! The layouts are the ones UnityPy 1.25.2 reads: the blob is
6//! `TypeTreeNode.parse_blob` (`helpers/TypeTreeNode.py:111-154`, rows
7//! `hBBIIiii` plus `Q` from format 19, `:331-347`) and the old format is
8//! `TypeTreeNode.parse` (`:78-109`: each node's fields, then its child count,
9//! children following in pre-order). Rows are written in the file's byte
10//! order.
11//!
12//! Owner: package C.
13
14use std::collections::HashMap;
15
16use crate::writer::ByteWriter;
17
18/// One node, as the writer lays it out.
19#[derive(Clone, Debug, PartialEq, Eq)]
20pub struct NodeSpec {
21    /// Depth (`m_Level`); the root is 0.
22    pub level: u8,
23    /// `m_Type`.
24    pub ty: Vec<u8>,
25    /// `m_Name`.
26    pub name: Vec<u8>,
27    /// `m_ByteSize`.
28    pub byte_size: i32,
29    /// `m_Version`.
30    pub version: i32,
31    /// `m_TypeFlags` (`m_IsArray` in the old format).
32    pub type_flags: i32,
33    /// `m_MetaFlag`; `0x4000` is "align after".
34    pub meta_flag: i32,
35    /// `m_RefTypeHash` (blob format 19 and up).
36    pub ref_type_hash: u64,
37    /// `m_Index` as stored; `None` writes the row's pre-order index. The core
38    /// keeps it as stored, never recomputed, which a test pins with a value
39    /// that differs from the position.
40    pub index: Option<i32>,
41}
42
43impl NodeSpec {
44    /// A node with zero sizes and flags.
45    #[must_use]
46    pub fn new(level: u8, ty: &str, name: &str) -> Self {
47        Self {
48            level,
49            ty: ty.as_bytes().to_vec(),
50            name: name.as_bytes().to_vec(),
51            byte_size: 0,
52            version: 1,
53            type_flags: 0,
54            meta_flag: 0,
55            ref_type_hash: 0,
56            index: None,
57        }
58    }
59
60    /// With `m_ByteSize`.
61    #[must_use]
62    pub fn size(mut self, byte_size: i32) -> Self {
63        self.byte_size = byte_size;
64        self
65    }
66
67    /// With the align flag.
68    #[must_use]
69    pub fn aligned(mut self) -> Self {
70        self.meta_flag |= 0x4000;
71        self
72    }
73}
74
75/// How strings are stored in a blob.
76#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
77pub enum Strings {
78    /// Every string in the local buffer.
79    #[default]
80    Local,
81    /// Names found in the common-string table by offset (the caller passes
82    /// the table, so the testkit does not copy core's).
83    Common,
84}
85
86/// A blob-format tree: node count, string-buffer size, nodes, buffer.
87/// `common` is `(offset, string)` pairs used when `strings` is `Common`: a
88/// type or name equal to one of them is written as its offset with the high
89/// bit set, and every other string goes into the local buffer. Each distinct
90/// local string is stored once, in first-use order (type, then name, row by
91/// row).
92#[must_use]
93pub fn blob_tree(
94    nodes: &[NodeSpec],
95    format: u32,
96    big_endian: bool,
97    strings: Strings,
98    common: &[(u32, &[u8])],
99) -> Vec<u8> {
100    let mut buffer: Vec<u8> = Vec::new();
101    let mut local: HashMap<Vec<u8>, u32> = HashMap::new();
102    let mut offset = |s: &[u8]| -> u32 {
103        if strings == Strings::Common
104            && let Some((o, _)) = common.iter().find(|(_, c)| *c == s)
105        {
106            return o | 0x8000_0000;
107        }
108        if let Some(o) = local.get(s) {
109            return *o;
110        }
111        let o = u32::try_from(buffer.len()).unwrap_or(u32::MAX);
112        buffer.extend_from_slice(s);
113        buffer.push(0);
114        local.insert(s.to_vec(), o);
115        o
116    };
117    let offsets: Vec<(u32, u32)> = nodes
118        .iter()
119        .map(|n| {
120            let t = offset(&n.ty);
121            (t, offset(&n.name))
122        })
123        .collect();
124
125    let mut w = writer(big_endian);
126    w.i32(len_i32(nodes.len()));
127    w.i32(len_i32(buffer.len()));
128    for (i, (n, (ty, name))) in nodes.iter().zip(offsets).enumerate() {
129        // `hBBIIiii`: version, level, type flags, the two offsets, byte size,
130        // index, meta flag; then `Q` from format 19.
131        w.i16(truncate_i16(n.version));
132        w.u8(n.level);
133        w.u8(n.type_flags.to_le_bytes()[0]);
134        w.u32(ty);
135        w.u32(name);
136        w.i32(n.byte_size);
137        w.i32(n.index.unwrap_or_else(|| len_i32(i)));
138        w.i32(n.meta_flag);
139        if format >= 19 {
140            w.u64(n.ref_type_hash);
141        }
142    }
143    w.bytes(&buffer);
144    w.into_inner()
145}
146
147/// An old-format tree: each node then its child count, recursively (in
148/// pre-order). The format decides the fields, as `TypeTreeNode.parse` reads
149/// them: `m_VariableCount` (written 0) only at format 2, `m_Index` and
150/// `m_MetaFlag` except at format 3. A node's children are the rows UnityPy's
151/// stack rule nests directly under it (`TypeTreeNode.from_list`), so a level
152/// jump nests under the previous row as the blob reader would nest it.
153#[must_use]
154pub fn old_tree(nodes: &[NodeSpec], format: u32, big_endian: bool) -> Vec<u8> {
155    let parents = parents(nodes);
156    let mut w = writer(big_endian);
157    for (i, n) in nodes.iter().enumerate() {
158        w.cstr(&n.ty);
159        w.cstr(&n.name);
160        w.i32(n.byte_size);
161        if format == 2 {
162            w.i32(0);
163        }
164        if format != 3 {
165            w.i32(n.index.unwrap_or_else(|| len_i32(i)));
166        }
167        w.i32(n.type_flags);
168        w.i32(n.version);
169        if format != 3 {
170            w.i32(n.meta_flag);
171        }
172        let children = parents.iter().filter(|p| **p == Some(i)).count();
173        w.i32(len_i32(children));
174    }
175    w.into_inner()
176}
177
178/// A little-endian blob of format 19 and up whose `rows` rows each name
179/// offset 0 of a string buffer of `buffer` bytes `A` with no NUL for both
180/// their type and their name (round 4's input): every string is the
181/// 32,767-byte window where the buffer is longer, and raises where it is
182/// not. Each row is a level-0 node of byte size -1 and index `i`.
183#[must_use]
184pub fn no_nul_blob(rows: usize, buffer: usize) -> Vec<u8> {
185    let mut w = ByteWriter::le();
186    w.i32(len_i32(rows)).i32(len_i32(buffer));
187    for i in 0..rows {
188        // version, level, type flags, type, name, byte size, index, meta
189        // flag, ref type hash.
190        w.i16(1).u8(0).u8(0).u32(0).u32(0);
191        w.i32(-1).i32(len_i32(i)).i32(0).u64(0);
192    }
193    w.bytes(&vec![b'A'; buffer]);
194    w.into_inner()
195}
196
197/// Each row's parent under UnityPy's stack rule (`TypeTreeNode.from_list`):
198/// a row above the previous row's level nests under the previous row, a row
199/// at its level is its sibling, and a row below it pops to the nearest
200/// ancestor of lower level. `None` for a top-level row.
201fn parents(nodes: &[NodeSpec]) -> Vec<Option<usize>> {
202    let mut out = Vec::with_capacity(nodes.len());
203    // The current parent and the parents above it, the hidden root at -1.
204    let root: (Option<usize>, i32) = (None, -1);
205    let mut stack: Vec<(Option<usize>, i32)> = Vec::new();
206    let mut parent = root;
207    let mut prev = root;
208    for (i, n) in nodes.iter().enumerate() {
209        let level = i32::from(n.level);
210        if level > prev.1 {
211            stack.push(parent);
212            parent = prev;
213        } else if level < prev.1 {
214            while level <= parent.1 {
215                parent = stack.pop().unwrap_or(root);
216                if parent == root {
217                    break;
218                }
219            }
220        }
221        out.push(parent.0);
222        prev = (Some(i), level);
223    }
224    out
225}
226
227fn writer(big_endian: bool) -> ByteWriter {
228    if big_endian {
229        ByteWriter::be()
230    } else {
231        ByteWriter::le()
232    }
233}
234
235fn len_i32(n: usize) -> i32 {
236    i32::try_from(n).unwrap_or(i32::MAX)
237}
238
239fn truncate_i16(v: i32) -> i16 {
240    let b = v.to_le_bytes();
241    i16::from_le_bytes([b[0], b[1]])
242}
243
244#[cfg(test)]
245mod tests {
246    use super::{NodeSpec, Strings, blob_tree, old_tree, parents};
247
248    fn tree() -> Vec<NodeSpec> {
249        vec![
250            NodeSpec::new(0, "Base", "Base"),
251            NodeSpec::new(1, "int", "a").size(4),
252            NodeSpec::new(1, "Sub", "s"),
253            NodeSpec::new(2, "UInt8", "b").size(1).aligned(),
254            NodeSpec::new(1, "int", "c").size(4),
255        ]
256    }
257
258    #[test]
259    fn a_blob_is_counts_rows_and_a_deduplicated_buffer() {
260        let b = blob_tree(&tree(), 17, false, Strings::Local, &[]);
261        assert_eq!(&b[..4], &5i32.to_le_bytes());
262        let buf = b"Base\0int\0a\0Sub\0s\0UInt8\0b\0c\0";
263        assert_eq!(&b[4..8], &i32::try_from(buf.len()).unwrap().to_le_bytes());
264        assert_eq!(b.len(), 8 + 5 * 24 + buf.len());
265        assert_eq!(&b[b.len() - buf.len()..], buf);
266        // Row 3: version 1, level 2, flags 0, type "UInt8" at 17, name "b"
267        // at 23, size 1, index 3, meta 0x4000.
268        let row = &b[8 + 3 * 24..8 + 4 * 24];
269        assert_eq!(&row[..4], &[1, 0, 2, 0]);
270        assert_eq!(&row[4..8], &17u32.to_le_bytes());
271        assert_eq!(&row[8..12], &23u32.to_le_bytes());
272        assert_eq!(&row[16..20], &3i32.to_le_bytes());
273        assert_eq!(&row[20..24], &0x4000i32.to_le_bytes());
274        // Format 19 adds the hash; big-endian swaps every field.
275        let b = blob_tree(&tree(), 19, true, Strings::Local, &[]);
276        assert_eq!(b.len(), 8 + 5 * 32 + buf.len());
277        assert_eq!(&b[..4], &5i32.to_be_bytes());
278    }
279
280    #[test]
281    fn common_strings_are_offsets_with_the_high_bit() {
282        let common: &[(u32, &[u8])] = &[(0, b"AABB"), (5, b"int")];
283        let b = blob_tree(&tree(), 17, false, Strings::Common, common);
284        let row = &b[8 + 24..8 + 48];
285        assert_eq!(&row[4..8], &0x8000_0005u32.to_le_bytes());
286        // Strings not in the table stay local.
287        let buf = b"Base\0a\0Sub\0s\0UInt8\0b\0c\0";
288        assert_eq!(&b[b.len() - buf.len()..], buf);
289    }
290
291    #[test]
292    fn the_old_format_writes_child_counts_in_pre_order() {
293        let t = tree();
294        assert_eq!(parents(&t), [None, Some(0), Some(0), Some(2), Some(0)]);
295        let b = old_tree(&t, 9, false);
296        // Base: "Base\0Base\0", size, index, flags, version, meta, 3 children.
297        assert_eq!(&b[..10], b"Base\0Base\0");
298        assert_eq!(&b[10 + 20..10 + 24], &3i32.to_le_bytes());
299        // Format 3 has no index or meta flag; format 2 a variable count.
300        let v3 = old_tree(&t[..1], 3, false);
301        assert_eq!(v3.len(), 10 + 16);
302        let v2 = old_tree(&t[..1], 2, false);
303        assert_eq!(v2.len(), 10 + 28);
304        // A level jump nests under the previous row; a second top-level row
305        // has no parent.
306        let jump = [
307            NodeSpec::new(0, "A", "a"),
308            NodeSpec::new(2, "B", "b"),
309            NodeSpec::new(1, "C", "c"),
310            NodeSpec::new(0, "D", "d"),
311        ];
312        assert_eq!(parents(&jump), [None, Some(0), Some(0), None]);
313    }
314}