saturnus_objects/
prolog.rs

1//! Object types by prolog and the size walk over nibbles.
2//!
3//! Prologs, type names and the rules for finding an object's end: wiki:
4//! protocols/hp-object-format (RPLMAN chapter 3; the 49G types from the
5//! Conn4x sources; DOEXT0-4 from the 48 entry list). The names are those
6//! the calculator's `G D` directory listing prints.
7
8use crate::error::{DecodeError, Reason};
9
10type Result<T, E = DecodeError> = std::result::Result<T, E>;
11
12/// SEMI, the end marker of composites (lists, programs, algebraics, units).
13pub const SEMI: u32 = 0x0312B;
14/// Deepest nesting the walks follow.
15pub const MAX_DEPTH: usize = 64;
16/// Prologs live in this ROM range on the 48 and the 49G; an embedded value
17/// in it that is no known prolog is an error, not a ROM pointer.
18const PROLOG_RANGE: std::ops::RangeInclusive<u32> = 0x02600..=0x02FFF;
19
20/// Object types by prolog.
21#[derive(Clone, Copy, Debug, PartialEq, Eq)]
22pub enum ObjectType {
23    /// #02911.
24    SystemBinary,
25    /// #02933.
26    Real,
27    /// #02955.
28    LongReal,
29    /// #02977.
30    Complex,
31    /// #0299D.
32    LongComplex,
33    /// #029BF.
34    Character,
35    /// #029E8.
36    Array,
37    /// #02A0A.
38    LinkedArray,
39    /// #02A2C.
40    String,
41    /// #02A4E.
42    BinaryInteger,
43    /// #02A74.
44    List,
45    /// #02A96.
46    Directory,
47    /// #02AB8.
48    Algebraic,
49    /// #02ADA.
50    Unit,
51    /// #02AFC.
52    Tagged,
53    /// #02B1E.
54    Graphic,
55    /// #02B40.
56    Library,
57    /// #02B62.
58    Backup,
59    /// #02B88.
60    LibraryData,
61    /// #02D9D.
62    Program,
63    /// #02DCC.
64    Code,
65    /// #02E48.
66    GlobalName,
67    /// #02E6D.
68    LocalName,
69    /// #02E92.
70    XlibName,
71    /// #02614, 49G.
72    Integer,
73    /// #02686, 49G symbolic matrix.
74    SymbolicMatrix,
75    /// #0263A, 49G long real.
76    LongReal49,
77    /// #02660, 49G long complex.
78    LongComplex49,
79    /// #026AC, 49G flash pointer.
80    FlashPointer,
81    /// #026D5, 49G aplet.
82    Aplet,
83    /// #026FE, 49G mini font.
84    MiniFont,
85    /// #02BAA, extended (access) pointer.
86    ExtendedPointer,
87    /// #02BCC.
88    Extended2,
89    /// #02BEE.
90    Extended3,
91    /// #02C10.
92    Extended4,
93}
94
95/// How an object's end is found.
96#[derive(Clone, Copy, Debug)]
97enum Extent {
98    /// A fixed size in nibbles, prolog included.
99    Fixed(usize),
100    /// `n` consecutive 5-nibble length fields after the prolog, each
101    /// counting itself and its body (most objects: 1).
102    Lengths(usize),
103    /// Elements up to and including SEMI.
104    Composite,
105    /// 2-nibble character count, characters, one element.
106    Tagged,
107    /// 2-nibble character count, characters.
108    Name,
109    /// Library id, last-variable offset, variable records.
110    Directory,
111}
112
113use Extent::{Composite, Fixed, Lengths, Name};
114
115/// (type, prolog, `G D` name, extent), in [`ObjectType`] order.
116const TYPES: [(ObjectType, u32, &str, Extent); 35] = [
117    (
118        ObjectType::SystemBinary,
119        0x02911,
120        "System Binary",
121        Fixed(10),
122    ),
123    (ObjectType::Real, 0x02933, "Real Number", Fixed(21)),
124    (ObjectType::LongReal, 0x02955, "Long Real", Fixed(26)),
125    (ObjectType::Complex, 0x02977, "Complex Number", Fixed(37)),
126    (ObjectType::LongComplex, 0x0299D, "Long Complex", Fixed(47)),
127    (ObjectType::Character, 0x029BF, "Character", Fixed(7)),
128    (ObjectType::Array, 0x029E8, "Array", Lengths(1)),
129    (ObjectType::LinkedArray, 0x02A0A, "Linked Array", Lengths(1)),
130    (ObjectType::String, 0x02A2C, "String", Lengths(1)),
131    (
132        ObjectType::BinaryInteger,
133        0x02A4E,
134        "Binary Integer",
135        Lengths(1),
136    ),
137    (ObjectType::List, 0x02A74, "List", Composite),
138    (
139        ObjectType::Directory,
140        0x02A96,
141        "Directory",
142        Extent::Directory,
143    ),
144    (ObjectType::Algebraic, 0x02AB8, "Algebraic", Composite),
145    (ObjectType::Unit, 0x02ADA, "Unit", Composite),
146    (ObjectType::Tagged, 0x02AFC, "Tagged", Extent::Tagged),
147    (ObjectType::Graphic, 0x02B1E, "Graphic", Lengths(1)),
148    (ObjectType::Library, 0x02B40, "Library", Lengths(1)),
149    (ObjectType::Backup, 0x02B62, "Backup", Lengths(1)),
150    (ObjectType::LibraryData, 0x02B88, "Library Data", Lengths(1)),
151    (ObjectType::Program, 0x02D9D, "Program", Composite),
152    (ObjectType::Code, 0x02DCC, "Code", Lengths(1)),
153    (ObjectType::GlobalName, 0x02E48, "Global Name", Name),
154    (ObjectType::LocalName, 0x02E6D, "Local Name", Name),
155    (ObjectType::XlibName, 0x02E92, "XLIB Name", Fixed(11)),
156    (ObjectType::Integer, 0x02614, "Integer", Lengths(1)),
157    (
158        ObjectType::SymbolicMatrix,
159        0x02686,
160        "Symbolic Matrix",
161        Composite,
162    ),
163    // Mantissa and exponent, each a length-prefixed integer body.
164    (
165        ObjectType::LongReal49,
166        0x0263A,
167        "Long Real (49G)",
168        Lengths(2),
169    ),
170    // Two long reals without their prologs.
171    (
172        ObjectType::LongComplex49,
173        0x02660,
174        "Long Complex (49G)",
175        Lengths(4),
176    ),
177    // Prolog, 3-nibble bank, 4-nibble address.
178    (
179        ObjectType::FlashPointer,
180        0x026AC,
181        "Flash Pointer",
182        Fixed(12),
183    ),
184    // Length-prefixed per the Conn4x sources; not checked on a real object.
185    (ObjectType::Aplet, 0x026D5, "Aplet", Lengths(1)),
186    (ObjectType::MiniFont, 0x026FE, "Mini Font", Lengths(1)),
187    // Prolog and two 5-nibble fields.
188    (
189        ObjectType::ExtendedPointer,
190        0x02BAA,
191        "Extended Pointer",
192        Fixed(15),
193    ),
194    (ObjectType::Extended2, 0x02BCC, "Extended 2", Lengths(1)),
195    (ObjectType::Extended3, 0x02BEE, "Extended 3", Lengths(1)),
196    (ObjectType::Extended4, 0x02C10, "Extended 4", Lengths(1)),
197];
198
199impl ObjectType {
200    /// The type with this prolog, if known.
201    pub fn from_prolog(prolog: u32) -> Option<Self> {
202        TYPES.iter().find(|t| t.1 == prolog).map(|t| t.0)
203    }
204
205    fn entry(self) -> &'static (ObjectType, u32, &'static str, Extent) {
206        // TYPES lists every variant once, in declaration order.
207        &TYPES[self as usize]
208    }
209
210    /// The prolog address.
211    pub fn prolog(self) -> u32 {
212        self.entry().1
213    }
214
215    /// The type name as `G D` prints it, e.g. `Real Number`.
216    pub fn name(self) -> &'static str {
217        self.entry().2
218    }
219}
220
221/// The `width`-nibble field at `at`, low nibble first; `None` past the end
222/// or for fields wider than 8 nibbles.
223pub fn read_field(n: &[u8], at: usize, width: usize) -> Option<u32> {
224    if width > 8 {
225        return None;
226    }
227    let f = n.get(at..at.checked_add(width)?)?;
228    Some(
229        f.iter()
230            .rev()
231            .fold(0, |acc, &d| (acc << 4) | u32::from(d & 0xF)),
232    )
233}
234
235fn field(n: &[u8], at: usize, width: usize) -> Result<usize> {
236    let v = read_field(n, at, width).ok_or(DecodeError::new(at, Reason::Truncated))?;
237    usize::try_from(v).map_err(|_| DecodeError::new(at, Reason::SizeOverflow))
238}
239
240fn add(a: usize, b: usize) -> Result<usize> {
241    a.checked_add(b)
242        .ok_or(DecodeError::new(a, Reason::SizeOverflow))
243}
244
245/// Size in nibbles of the object at nibble `at`. Fails on an unknown
246/// prolog, a truncated object or nesting deeper than [`MAX_DEPTH`], with
247/// the offset into `n` where the walk stopped.
248pub fn object_size(n: &[u8], at: usize) -> Result<usize> {
249    walk(n, at, 0)
250}
251
252/// Size of an embedded object (composite element, tagged payload,
253/// directory variable): an object with a known prolog, else a 5-nibble ROM
254/// pointer.
255pub fn element_size(n: &[u8], at: usize, depth: usize) -> Result<usize> {
256    let p = field(n, at, 5)? as u32;
257    if ObjectType::from_prolog(p).is_some() {
258        walk(n, at, depth)
259    } else if PROLOG_RANGE.contains(&p) {
260        Err(DecodeError::new(at, Reason::UnknownProlog(p)))
261    } else {
262        Ok(5)
263    }
264}
265
266fn walk(n: &[u8], at: usize, depth: usize) -> Result<usize> {
267    if depth > MAX_DEPTH {
268        return Err(DecodeError::new(at, Reason::TooDeep));
269    }
270    let prolog = field(n, at, 5)? as u32;
271    let ty = ObjectType::from_prolog(prolog)
272        .ok_or(DecodeError::new(at, Reason::UnknownProlog(prolog)))?;
273    let body = add(at, 5)?;
274    let size = match ty.entry().3 {
275        Fixed(size) => size,
276        Lengths(count) => {
277            let mut pos = body;
278            for _ in 0..count {
279                let len = field(n, pos, 5)?;
280                if len < 5 {
281                    return Err(DecodeError::new(pos, Reason::LengthTooShort(len)));
282                }
283                pos = add(pos, len)?;
284            }
285            pos - at
286        }
287        Composite => {
288            let mut pos = body;
289            while field(n, pos, 5)? != SEMI as usize {
290                pos = add(pos, element_size(n, pos, depth + 1)?)?;
291            }
292            add(pos, 5)? - at
293        }
294        Extent::Tagged => {
295            let inner = add(body, 2 + 2 * field(n, body, 2)?)?;
296            add(inner, element_size(n, inner, depth + 1)?)? - at
297        }
298        Name => 7 + 2 * field(n, body, 2)?,
299        Extent::Directory => directory_size(n, at, depth)?,
300    };
301    if add(at, size)? > n.len() {
302        return Err(DecodeError::new(
303            at,
304            Reason::DoesNotFit {
305                kind: ty,
306                size,
307                left: n.len().saturating_sub(at),
308            },
309        ));
310    }
311    Ok(size)
312}
313
314/// One variable record of a directory body (wiki: hardware/hp48-system-ram
315/// "Directories"): a 5-nibble offset from this field back to the previous
316/// record's name length field (0 for the first record), the name's length
317/// n in 2 nibbles, its characters, n again (absent when n = 0), the
318/// object. Records lie oldest first; the directory's offset field points
319/// at the newest.
320#[derive(Clone, Copy, Debug, PartialEq, Eq)]
321pub struct Record {
322    /// Nibble of the back-offset field (the record's start).
323    pub start: usize,
324    /// Nibble of the first name length field.
325    pub name_at: usize,
326    /// Name length in characters.
327    pub name_len: usize,
328    /// Nibble of the object (or the 5-nibble ROM pointer).
329    pub object: usize,
330    /// Size of the object in nibbles.
331    pub object_size: usize,
332}
333
334impl Record {
335    /// The record at `start`.
336    pub fn at(n: &[u8], start: usize, depth: usize) -> Result<Record> {
337        let name_at = add(start, 5)?;
338        let name_len = field(n, name_at, 2)?;
339        let mut object = add(name_at, 2 + 2 * name_len)?;
340        if name_len != 0 {
341            object = add(object, 2)?;
342        }
343        let object_size = element_size(n, object, depth + 1)?;
344        Ok(Record {
345            start,
346            name_at,
347            name_len,
348            object,
349            object_size,
350        })
351    }
352
353    /// The nibble after the record.
354    pub fn end(&self) -> usize {
355        self.object + self.object_size
356    }
357}
358
359/// The records of the directory body whose last-variable offset field is
360/// at `offset_at` (records follow it), in memory order (oldest first).
361pub fn records(n: &[u8], offset_at: usize, depth: usize) -> Result<Vec<Record>> {
362    let offset = field(n, offset_at, 5)?;
363    let mut out = Vec::new();
364    if offset == 0 {
365        return Ok(out);
366    }
367    let last = add(offset_at, offset)?;
368    let mut pos = add(offset_at, 5)?;
369    loop {
370        let r = Record::at(n, pos, depth)?;
371        if r.name_at > last {
372            return Err(DecodeError::new(offset_at, Reason::DirectoryOffset));
373        }
374        pos = r.end();
375        let done = r.name_at == last;
376        out.push(r);
377        if done {
378            return Ok(out);
379        }
380    }
381}
382
383/// An ordinary directory: prolog, 3-nibble attached library (#7FF none),
384/// 5-nibble offset from that field to the last record's name length (0 =
385/// empty), then the records.
386fn directory_size(n: &[u8], at: usize, depth: usize) -> Result<usize> {
387    let offset_at = add(at, 8)?;
388    let end = records(n, offset_at, depth)?
389        .last()
390        .map_or(offset_at + 5, Record::end);
391    Ok(end - at)
392}
393
394#[cfg(test)]
395mod tests {
396    use super::*;
397
398    fn nib(s: &str) -> Vec<u8> {
399        s.chars()
400            .map(|c| c.to_digit(16).unwrap_or(0) as u8)
401            .collect()
402    }
403
404    #[test]
405    fn table_is_in_declaration_order() {
406        for (i, t) in TYPES.iter().enumerate() {
407            assert_eq!(t.0 as usize, i, "{:?}", t.0);
408            assert_eq!(ObjectType::from_prolog(t.1), Some(t.0));
409        }
410    }
411
412    #[test]
413    fn sizes() {
414        assert_eq!(object_size(&nib("339200000000000000050"), 0).ok(), Some(21));
415        // { 1 "A" } with 1 as a ROM pointer.
416        assert_eq!(
417            object_size(&nib("47A209C2A2C2A207000014B2130"), 0).ok(),
418            Some(27)
419        );
420        assert!(object_size(&nib("3392000"), 0).is_err());
421        assert!(object_size(&nib("C2A2030000"), 0).is_err());
422        // A directory holding Z = 5. (48SX RAM, wiki: hardware/hp48-system-ram).
423        let d = nib("69A20FF7A00000000010A510339200000000000000050");
424        assert_eq!(object_size(&d, 0).ok(), Some(45));
425        let rs = records(&d, 8, 0).unwrap_or_default();
426        assert_eq!(rs.len(), 1);
427        assert_eq!(
428            (rs[0].name_len, rs[0].object, rs[0].object_size),
429            (1, 24, 21)
430        );
431        // An empty directory.
432        assert_eq!(object_size(&nib("69A20FF700000"), 0).ok(), Some(13));
433    }
434}
saturnus_objects/prolog.rs

saturnus_objects/
prolog.rs
