wacore_binary/
token.rs

1pub const DICT_VERSION: u8 = 3;
2
3// --- Public Constants for Special Tags ---
4pub const LIST_EMPTY: u8 = 0;
5pub const DICTIONARY_0: u8 = 236;
6pub const DICTIONARY_1: u8 = 237;
7pub const DICTIONARY_2: u8 = 238;
8pub const DICTIONARY_3: u8 = 239;
9
10pub const JID_PAIR: u8 = 250;
11pub const HEX_8: u8 = 251;
12pub const BINARY_8: u8 = 252;
13pub const BINARY_20: u8 = 253;
14pub const BINARY_32: u8 = 254;
15pub const NIBBLE_8: u8 = 255;
16pub const INTEROP_JID: u8 = 245;
17pub const FB_JID: u8 = 246;
18pub const AD_JID: u8 = 247;
19pub const LIST_8: u8 = 248;
20pub const LIST_16: u8 = 249;
21
22pub const PACKED_MAX: u8 = 127;
23pub const SINGLE_BYTE_MAX: u16 = 256;
24
25#[derive(Debug, Clone, Copy, PartialEq, Eq)]
26pub enum TokenKind {
27    Single(u8),
28    Double(u8, u8),
29}
30
31include!(concat!(env!("OUT_DIR"), "/token_maps.rs"));
32
33/// One open-addressing probe over the build-generated table (layout and
34/// rationale in build.rs). Keys of length <= 4 — the bulk of probe traffic —
35/// are matched exactly by their padded u32; longer keys match a two-load
36/// signature first and byte-verify only on signature hits, so a miss of any
37/// shape costs a handful of instructions and no full compare.
38#[inline]
39pub fn index_of_token(token: &str) -> Option<TokenKind> {
40    lookup_bytes(token.as_bytes())
41}
42
43#[inline(always)]
44fn decode_kind(kind: u16) -> TokenKind {
45    if kind < SINGLE_BYTE_MAX {
46        TokenKind::Single(kind as u8)
47    } else {
48        TokenKind::Double((kind >> 8) as u8 - 1, kind as u8)
49    }
50}
51
52#[inline(always)]
53fn lookup_bytes(key: &[u8]) -> Option<TokenKind> {
54    let len = key.len();
55    if len == 0 || len > MAX_TOKEN_LEN {
56        return None;
57    }
58    // Key derivation must mirror build.rs exactly. For len <= 4 the padded
59    // word IS the key (tokens are NUL-free, so padding can't collide with
60    // real bytes) and the meta tag pins the exact length; longer keys match
61    // a signature and byte-verify against the length-prefixed blob. In both
62    // loops 0 marks an empty slot (build.rs asserts no key is 0), so most
63    // misses stop on the first load, and a false key match — an alias across
64    // the short/long split or a signature collision — just keeps probing:
65    // the real owner may live further down the chain.
66    if len <= 4 {
67        let x = match *key {
68            [a] => a as u32,
69            [a, b] => u32::from_le_bytes([a, b, 0, 0]),
70            [a, b, c] => u32::from_le_bytes([a, b, c, 0]),
71            _ => u32::from_le_bytes([key[0], key[1], key[2], key[3]]),
72        };
73        let mut h = (x.wrapping_mul(TOK_MUL) >> TOK_SHIFT) as usize;
74        loop {
75            let k = TOK_KEYS[h];
76            if k == 0 {
77                return None;
78            }
79            if k == x {
80                let meta = TOK_META[h];
81                if (meta >> 11) as usize == len - 1 {
82                    return Some(decode_kind(meta & 0x7FF));
83                }
84            }
85            h = (h + 1) & TOK_MASK;
86        }
87    }
88    let head = u32::from_le_bytes([key[0], key[1], key[2], key[3]]);
89    let tail = u32::from_le_bytes([key[len - 4], key[len - 3], key[len - 2], key[len - 1]]);
90    let x = head.rotate_left(11) ^ tail ^ (len as u32).wrapping_mul(0x9E37_79B1);
91    let mut h = (x.wrapping_mul(TOK_MUL) >> TOK_SHIFT) as usize;
92    loop {
93        let k = TOK_KEYS[h];
94        if k == 0 {
95            return None;
96        }
97        if k == x {
98            let meta = TOK_META[h];
99            if meta >> 11 == 31 {
100                let off = TOK_OFF[h] as usize;
101                if TOK_BLOB[off] as usize == len
102                    && TOK_BLOB[off + 1..off + 1 + len]
103                        .iter()
104                        .zip(key)
105                        .all(|(a, b)| a == b)
106                {
107                    return Some(decode_kind(meta & 0x7FF));
108                }
109            }
110        }
111        h = (h + 1) & TOK_MASK;
112    }
113}
114
115pub fn get_single_token(index: u8) -> Option<&'static str> {
116    SINGLE_BYTE_TOKENS.get(index as usize).copied()
117}
118
119pub fn get_double_token(dict: u8, index: u8) -> Option<&'static str> {
120    DOUBLE_BYTE_TOKENS
121        .get(dict as usize)
122        .and_then(|d| d.get(index as usize))
123        .copied()
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129
130    #[test]
131    fn test_single_byte_token_roundtrip() {
132        for i in 1u8..=235 {
133            if let Some(token) = get_single_token(i) {
134                let result = index_of_token(token);
135                assert!(
136                    matches!(result, Some(TokenKind::Single(idx)) if idx == i),
137                    "Token '{}' at index {} doesn't round-trip",
138                    token,
139                    i,
140                );
141            }
142        }
143    }
144
145    #[test]
146    fn test_double_byte_token_roundtrip() {
147        for dict in 0..4u8 {
148            for idx in 0..255u8 {
149                if let Some(token) = get_double_token(dict, idx) {
150                    let result = index_of_token(token);
151                    assert!(
152                        matches!(result, Some(TokenKind::Double(d, i)) if d == dict && i == idx),
153                        "Token '{}' at dict {} index {} doesn't round-trip",
154                        token,
155                        dict,
156                        idx,
157                    );
158                }
159            }
160        }
161    }
162
163    #[test]
164    fn test_unknown_string_returns_none() {
165        assert!(index_of_token("xyzzy_not_a_token_12345").is_none());
166    }
167
168    #[test]
169    fn test_empty_string_returns_none() {
170        assert!(index_of_token("").is_none());
171    }
172
173    #[test]
174    fn test_token_boundary_indices() {
175        let token_0 = get_single_token(0);
176        assert_eq!(token_0, Some(""), "Index 0 should be empty string token");
177        assert!(get_single_token(LIST_8).is_none());
178        assert!(get_single_token(LIST_16).is_none());
179        assert!(get_single_token(JID_PAIR).is_none());
180        assert!(get_single_token(HEX_8).is_none());
181        assert!(get_single_token(BINARY_8).is_none());
182        assert!(get_single_token(BINARY_20).is_none());
183        assert!(get_single_token(BINARY_32).is_none());
184        assert!(get_single_token(NIBBLE_8).is_none());
185    }
186
187    #[test]
188    fn test_almost_matching_strings() {
189        let token = get_single_token(1).expect("single token at index 1 must exist");
190        assert!(index_of_token(&format!("{}_modified", token)).is_none());
191        assert!(index_of_token(&format!("prefix_{}", token)).is_none());
192        assert!(index_of_token(&format!("{}!", token)).is_none());
193    }
194
195    #[test]
196    fn test_out_of_bounds_dictionary() {
197        assert!(get_double_token(4, 0).is_none());
198        assert!(get_double_token(5, 100).is_none());
199        assert!(get_double_token(255, 0).is_none());
200    }
201
202    /// Exhaustive equivalence guard: against a reference map built from the token
203    /// tables, every one-byte input and every single-byte mutation (all 256
204    /// values) of every token must resolve to the reference value (the token or
205    /// `None`). Probes the length-bucketed lookup for any discriminator collision
206    /// that would silently map a non-token (a JID/id) onto a token and corrupt the
207    /// wire, and stays durable against future token-set edits.
208    ///
209    /// Ignored under Miri: ~3M lookups (every byte position of every token,
210    /// times 256) is minutes of interpretation for a table probe that holds no
211    /// `unsafe` and no raw pointers, so there is nothing there for the
212    /// interpreter to find.
213    #[test]
214    #[cfg_attr(miri, ignore)]
215    fn lookup_matches_reference_under_byte_mutation() {
216        use std::collections::HashMap;
217
218        let mut reference: HashMap<Vec<u8>, TokenKind> = HashMap::new();
219        for i in 0u8..=235 {
220            if let Some(t) = get_single_token(i) {
221                reference
222                    .entry(t.as_bytes().to_vec())
223                    .or_insert(TokenKind::Single(i));
224            }
225        }
226        for dict in 0..4u8 {
227            for idx in 0..=255u8 {
228                if let Some(t) = get_double_token(dict, idx) {
229                    reference
230                        .entry(t.as_bytes().to_vec())
231                        .or_insert(TokenKind::Double(dict, idx));
232                }
233            }
234        }
235
236        let check = |bytes: &[u8]| {
237            assert_eq!(
238                lookup_bytes(bytes),
239                reference.get(bytes).copied(),
240                "lookup disagrees with reference for {bytes:?}",
241            );
242        };
243
244        for b in 0u8..=255 {
245            check(&[b]);
246        }
247
248        let keys: Vec<Vec<u8>> = reference.keys().cloned().collect();
249        for key in &keys {
250            let mut m = key.clone();
251            for pos in 0..m.len() {
252                let orig = m[pos];
253                for b in 0u8..=255 {
254                    m[pos] = b;
255                    check(&m);
256                }
257                m[pos] = orig;
258            }
259        }
260    }
261}
wacore_binary/token.rs

wacore_binary/
token.rs
