logicaffeine_base/
exact_codec.rs

1//! Canonical byte encodings of the exact numbers — the one form they cross a task boundary, the
2//! wire and storage in.
3//!
4//! Every exact type writes its canonical name: an integer its sign and magnitude, a rational its
5//! reduced numerator and denominator, a real algebraic number its minimal polynomial and root
6//! index, a hyperreal its reduced numerator and denominator in `dt`, an infinite natural its
7//! residue-indexed polynomials, an ordinal its Cantor normal form, a computable real its exact form
8//! or the expression that builds it. Lengths are LEB128 varints.
9//!
10//! A decoder trusts nothing it reads. [`ExactCodec::from_bytes`] accepts an encoding only when it
11//! is complete, has no trailing bytes, and is the canonical encoding of the value it decodes to —
12//! so a forged non-canonical name (an unreduced fraction, a reducible "minimal polynomial", a
13//! non-real exponential sum) is refused rather than breaking the equality every other part of the
14//! system relies on. Sizes are bounded before any work is done: a minimal polynomial's degree by
15//! [`MAX_WIRE_DEGREE`], collection lengths by [`MAX_WIRE_LEN`], magnitudes by
16//! [`MAX_WIRE_MAGNITUDE`] bytes, and nesting by [`MAX_WIRE_DEPTH`].
17
18use crate::describe::{read_uvarint, write_uvarint};
19use crate::numeric::{BigInt, Rational};
20
21/// The largest minimal-polynomial degree a decoder accepts: an irreducibility check is a
22/// factorization, and this bound keeps a hostile encoding from demanding an expensive one.
23pub const MAX_WIRE_DEGREE: usize = 32;
24/// The most elements a decoded collection may claim.
25pub const MAX_WIRE_LEN: usize = 1 << 16;
26/// The most magnitude bytes a decoded integer may claim.
27pub const MAX_WIRE_MAGNITUDE: usize = 1 << 20;
28/// The deepest nesting a decoded ordinal or expression may have.
29pub const MAX_WIRE_DEPTH: usize = 256;
30
31/// A canonical, self-delimiting byte encoding. See the module documentation.
32pub trait ExactCodec: Sized {
33    fn write(&self, out: &mut Vec<u8>);
34    fn read(buf: &[u8], pos: &mut usize) -> Option<Self>;
35
36    fn to_bytes(&self) -> Vec<u8> {
37        let mut out = Vec::new();
38        self.write(&mut out);
39        out
40    }
41
42    /// The value `buf` canonically encodes, with nothing left over.
43    fn from_bytes(buf: &[u8]) -> Option<Self> {
44        let mut pos = 0;
45        let v = Self::read(buf, &mut pos)?;
46        (pos == buf.len() && v.to_bytes() == buf).then_some(v)
47    }
48}
49
50/// One byte.
51pub fn read_byte(buf: &[u8], pos: &mut usize) -> Option<u8> {
52    let b = *buf.get(*pos)?;
53    *pos += 1;
54    Some(b)
55}
56
57/// A length, at most `bound`.
58pub fn read_len(buf: &[u8], pos: &mut usize, bound: usize) -> Option<usize> {
59    let n = read_uvarint(buf, pos)?;
60    (n as usize <= bound).then_some(n as usize)
61}
62
63pub fn write_len(n: usize, out: &mut Vec<u8>) {
64    write_uvarint(n as u64, out);
65}
66
67/// A length-prefixed list.
68pub fn write_list<T: ExactCodec>(items: &[T], out: &mut Vec<u8>) {
69    write_len(items.len(), out);
70    for item in items {
71        item.write(out);
72    }
73}
74
75pub fn read_list<T: ExactCodec>(buf: &[u8], pos: &mut usize) -> Option<Vec<T>> {
76    let n = read_len(buf, pos, MAX_WIRE_LEN)?;
77    let mut out = Vec::with_capacity(n.min(64));
78    for _ in 0..n {
79        out.push(T::read(buf, pos)?);
80    }
81    Some(out)
82}
83
84impl ExactCodec for u64 {
85    fn write(&self, out: &mut Vec<u8>) {
86        write_uvarint(*self, out);
87    }
88
89    fn read(buf: &[u8], pos: &mut usize) -> Option<Self> {
90        read_uvarint(buf, pos)
91    }
92}
93
94impl ExactCodec for i64 {
95    fn write(&self, out: &mut Vec<u8>) {
96        write_uvarint(crate::describe::zigzag(*self), out);
97    }
98
99    fn read(buf: &[u8], pos: &mut usize) -> Option<Self> {
100        read_uvarint(buf, pos).map(crate::describe::unzigzag)
101    }
102}
103
104impl ExactCodec for BigInt {
105    /// A sign byte (`0` nonnegative, `1` negative), the magnitude's length, its little-endian bytes.
106    fn write(&self, out: &mut Vec<u8>) {
107        let (negative, magnitude) = self.to_le_bytes();
108        out.push(u8::from(negative));
109        write_len(magnitude.len(), out);
110        out.extend_from_slice(&magnitude);
111    }
112
113    fn read(buf: &[u8], pos: &mut usize) -> Option<Self> {
114        let negative = match read_byte(buf, pos)? {
115            0 => false,
116            1 => true,
117            _ => return None,
118        };
119        let n = read_len(buf, pos, MAX_WIRE_MAGNITUDE)?;
120        let bytes = buf.get(*pos..*pos + n)?;
121        *pos += n;
122        Some(BigInt::from_le_bytes(negative, bytes))
123    }
124}
125
126impl ExactCodec for Rational {
127    /// The reduced numerator, then the positive denominator.
128    fn write(&self, out: &mut Vec<u8>) {
129        self.numerator().write(out);
130        self.denominator().write(out);
131    }
132
133    fn read(buf: &[u8], pos: &mut usize) -> Option<Self> {
134        let num = BigInt::read(buf, pos)?;
135        let den = BigInt::read(buf, pos)?;
136        if !den.is_positive() {
137            return None;
138        }
139        Rational::new(num, den)
140    }
141}
142
143#[cfg(test)]
144#[path = "../../logicaffeine_tests/unit/logicaffeine_base/exact_codec/tests.rs"]
145mod tests;
logicaffeine_base/exact_codec.rs

logicaffeine_base/
exact_codec.rs
