bones_core/clock/
text.rs

1use crate::clock::itc::Stamp;
2
3pub const ITC_TEXT_PREFIX: &str = "itc:v3:";
4const LEGACY_ITC_TEXT_PREFIX: &str = "itc:v1:";
5const COMPACT_ITC_VERSION: u8 = 1;
6const SPARSE_ITC_WIRE_VERSION: u8 = 1;
7const BASE64_URL: &[u8; 64] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";
8
9#[must_use]
10pub fn stamp_to_text(stamp: &Stamp) -> String {
11    let compact = stamp.serialize_compact();
12    compact_to_sparse_payload(&compact).map_or_else(
13        || format!("{LEGACY_ITC_TEXT_PREFIX}{}", encode_hex(&compact)),
14        |sparse_payload| {
15            format!(
16                "{ITC_TEXT_PREFIX}{}",
17                encode_base64_url_no_pad(&sparse_payload)
18            )
19        },
20    )
21}
22
23#[must_use]
24pub fn stamp_from_text(raw: &str) -> Option<Stamp> {
25    if let Some(encoded) = raw.strip_prefix(ITC_TEXT_PREFIX) {
26        let sparse_payload = decode_base64_url_no_pad(encoded)?;
27        let compact = sparse_payload_to_compact(&sparse_payload)?;
28        return Stamp::deserialize_compact(&compact).ok();
29    }
30
31    let encoded = raw.strip_prefix(LEGACY_ITC_TEXT_PREFIX)?;
32    let compact = decode_hex(encoded)?;
33    Stamp::deserialize_compact(&compact).ok()
34}
35
36#[derive(Debug, Clone, Copy)]
37struct CompactSections<'a> {
38    id_bit_len: usize,
39    id_bits: &'a [u8],
40    event_bit_len: usize,
41    event_bits: &'a [u8],
42    event_values: &'a [u8],
43}
44
45fn compact_to_sparse_payload(compact: &[u8]) -> Option<Vec<u8>> {
46    let sections = parse_compact_sections(compact)?;
47    let values = decode_u32_varint_list(sections.event_values, sections.event_bit_len)?;
48
49    let mut sparse = Vec::new();
50    sparse.push(SPARSE_ITC_WIRE_VERSION);
51    encode_varint_usize(sections.id_bit_len, &mut sparse);
52    sparse.extend_from_slice(sections.id_bits);
53    encode_varint_usize(sections.event_bit_len, &mut sparse);
54    sparse.extend_from_slice(sections.event_bits);
55
56    let non_zero_count = values.iter().filter(|&&value| value != 0).count();
57    encode_varint_usize(non_zero_count, &mut sparse);
58
59    let mut previous_index = 0usize;
60    let mut wrote_any = false;
61    for (index, value) in values.into_iter().enumerate() {
62        if value == 0 {
63            continue;
64        }
65        let delta = if wrote_any {
66            index.checked_sub(previous_index)?
67        } else {
68            index
69        };
70        encode_varint_usize(delta, &mut sparse);
71        encode_varint_u32(value, &mut sparse);
72        previous_index = index;
73        wrote_any = true;
74    }
75
76    Some(sparse)
77}
78
79fn sparse_payload_to_compact(sparse: &[u8]) -> Option<Vec<u8>> {
80    let mut cursor = 0usize;
81    let version = *sparse.get(cursor)?;
82    cursor += 1;
83    if version != SPARSE_ITC_WIRE_VERSION {
84        return None;
85    }
86
87    let id_bit_len = decode_varint_usize(sparse, &mut cursor)?;
88    let id_byte_len = bytes_for_bits(id_bit_len)?;
89    let id_bits = take_slice(sparse, &mut cursor, id_byte_len)?;
90
91    let event_bit_len = decode_varint_usize(sparse, &mut cursor)?;
92    let event_byte_len = bytes_for_bits(event_bit_len)?;
93    let event_bits = take_slice(sparse, &mut cursor, event_byte_len)?;
94
95    let non_zero_count = decode_varint_usize(sparse, &mut cursor)?;
96
97    let mut values = vec![0_u32; event_bit_len];
98    let mut previous_index = 0usize;
99    let mut has_previous = false;
100
101    for _ in 0..non_zero_count {
102        let delta = decode_varint_usize(sparse, &mut cursor)?;
103        let index = if has_previous {
104            previous_index.checked_add(delta)?
105        } else {
106            delta
107        };
108        if index >= values.len() {
109            return None;
110        }
111        if values[index] != 0 {
112            return None;
113        }
114
115        let value = decode_varint_u32(sparse, &mut cursor)?;
116        if value == 0 {
117            return None;
118        }
119        values[index] = value;
120        previous_index = index;
121        has_previous = true;
122    }
123
124    if cursor != sparse.len() {
125        return None;
126    }
127
128    let mut event_values = Vec::new();
129    for value in values {
130        encode_varint_u32(value, &mut event_values);
131    }
132
133    let mut compact = Vec::new();
134    compact.push(COMPACT_ITC_VERSION);
135    encode_varint_usize(id_bit_len, &mut compact);
136    compact.extend_from_slice(id_bits);
137    encode_varint_usize(event_bit_len, &mut compact);
138    compact.extend_from_slice(event_bits);
139    encode_varint_usize(event_values.len(), &mut compact);
140    compact.extend_from_slice(&event_values);
141    Some(compact)
142}
143
144fn parse_compact_sections(raw: &[u8]) -> Option<CompactSections<'_>> {
145    let mut cursor = 0usize;
146    let version = *raw.get(cursor)?;
147    cursor += 1;
148    if version != COMPACT_ITC_VERSION {
149        return None;
150    }
151
152    let id_bit_len = decode_varint_usize(raw, &mut cursor)?;
153    let id_byte_len = bytes_for_bits(id_bit_len)?;
154    let id_bits = take_slice(raw, &mut cursor, id_byte_len)?;
155
156    let event_bit_len = decode_varint_usize(raw, &mut cursor)?;
157    let event_byte_len = bytes_for_bits(event_bit_len)?;
158    let event_bits = take_slice(raw, &mut cursor, event_byte_len)?;
159
160    let event_values_len = decode_varint_usize(raw, &mut cursor)?;
161    let event_values = take_slice(raw, &mut cursor, event_values_len)?;
162
163    if cursor != raw.len() {
164        return None;
165    }
166
167    Some(CompactSections {
168        id_bit_len,
169        id_bits,
170        event_bit_len,
171        event_bits,
172        event_values,
173    })
174}
175
176fn decode_u32_varint_list(raw: &[u8], expected_len: usize) -> Option<Vec<u32>> {
177    let mut cursor = 0usize;
178    let mut out = Vec::with_capacity(expected_len);
179    while out.len() < expected_len {
180        out.push(decode_varint_u32(raw, &mut cursor)?);
181    }
182    if cursor != raw.len() {
183        return None;
184    }
185    Some(out)
186}
187
188fn take_slice<'a>(raw: &'a [u8], cursor: &mut usize, len: usize) -> Option<&'a [u8]> {
189    let end = cursor.checked_add(len)?;
190    let slice = raw.get(*cursor..end)?;
191    *cursor = end;
192    Some(slice)
193}
194
195fn bytes_for_bits(bit_len: usize) -> Option<usize> {
196    bit_len.checked_add(7).map(|value| value / 8)
197}
198
199fn encode_varint_usize(value: usize, out: &mut Vec<u8>) {
200    encode_varint_u64(u64::try_from(value).unwrap_or(u64::MAX), out);
201}
202
203fn encode_varint_u32(value: u32, out: &mut Vec<u8>) {
204    encode_varint_u64(u64::from(value), out);
205}
206
207fn encode_varint_u64(mut value: u64, out: &mut Vec<u8>) {
208    while value >= 0x80 {
209        let lower = u8::try_from(value & 0x7f).unwrap_or(0);
210        out.push(lower | 0x80);
211        value >>= 7;
212    }
213    let final_byte = u8::try_from(value & 0x7f).unwrap_or(0);
214    out.push(final_byte);
215}
216
217fn decode_varint_usize(raw: &[u8], cursor: &mut usize) -> Option<usize> {
218    let value = decode_varint_u64(raw, cursor)?;
219    usize::try_from(value).ok()
220}
221
222fn decode_varint_u32(raw: &[u8], cursor: &mut usize) -> Option<u32> {
223    let value = decode_varint_u64(raw, cursor)?;
224    u32::try_from(value).ok()
225}
226
227fn decode_varint_u64(raw: &[u8], cursor: &mut usize) -> Option<u64> {
228    let mut shift = 0_u32;
229    let mut value = 0_u64;
230
231    loop {
232        let byte = *raw.get(*cursor)?;
233        *cursor += 1;
234        let payload = u64::from(byte & 0x7f);
235        let shifted = payload.checked_shl(shift)?;
236        value = value.checked_add(shifted)?;
237        if (byte & 0x80) == 0 {
238            return Some(value);
239        }
240        if shift >= 63 {
241            return None;
242        }
243        shift += 7;
244    }
245}
246
247fn encode_base64_url_no_pad(bytes: &[u8]) -> String {
248    let mut out = String::with_capacity((bytes.len() * 4).div_ceil(3));
249    let mut idx = 0usize;
250
251    while idx + 3 <= bytes.len() {
252        let b0 = bytes[idx];
253        let b1 = bytes[idx + 1];
254        let b2 = bytes[idx + 2];
255        out.push(char::from(BASE64_URL[usize::from(b0 >> 2)]));
256        out.push(char::from(
257            BASE64_URL[usize::from(((b0 & 0b0000_0011) << 4) | (b1 >> 4))],
258        ));
259        out.push(char::from(
260            BASE64_URL[usize::from(((b1 & 0b0000_1111) << 2) | (b2 >> 6))],
261        ));
262        out.push(char::from(BASE64_URL[usize::from(b2 & 0b0011_1111)]));
263        idx += 3;
264    }
265
266    let remainder = bytes.len() - idx;
267    if remainder == 1 {
268        let b0 = bytes[idx];
269        out.push(char::from(BASE64_URL[usize::from(b0 >> 2)]));
270        out.push(char::from(BASE64_URL[usize::from((b0 & 0b0000_0011) << 4)]));
271    } else if remainder == 2 {
272        let b0 = bytes[idx];
273        let b1 = bytes[idx + 1];
274        out.push(char::from(BASE64_URL[usize::from(b0 >> 2)]));
275        out.push(char::from(
276            BASE64_URL[usize::from(((b0 & 0b0000_0011) << 4) | (b1 >> 4))],
277        ));
278        out.push(char::from(BASE64_URL[usize::from((b1 & 0b0000_1111) << 2)]));
279    }
280
281    out
282}
283
284fn decode_base64_url_no_pad(raw: &str) -> Option<Vec<u8>> {
285    let input = raw.as_bytes();
286    if input.len() % 4 == 1 {
287        return None;
288    }
289
290    let mut out = Vec::with_capacity(input.len() * 3 / 4 + 2);
291    let mut cursor = 0usize;
292
293    while cursor + 4 <= input.len() {
294        let a = decode_base64_url_digit(*input.get(cursor)?)?;
295        let b = decode_base64_url_digit(*input.get(cursor + 1)?)?;
296        let c = decode_base64_url_digit(*input.get(cursor + 2)?)?;
297        let d = decode_base64_url_digit(*input.get(cursor + 3)?)?;
298        out.push((a << 2) | (b >> 4));
299        out.push(((b & 0b0000_1111) << 4) | (c >> 2));
300        out.push(((c & 0b0000_0011) << 6) | d);
301        cursor += 4;
302    }
303
304    let remainder = input.len() - cursor;
305    if remainder == 2 {
306        let a = decode_base64_url_digit(*input.get(cursor)?)?;
307        let b = decode_base64_url_digit(*input.get(cursor + 1)?)?;
308        out.push((a << 2) | (b >> 4));
309    } else if remainder == 3 {
310        let a = decode_base64_url_digit(*input.get(cursor)?)?;
311        let b = decode_base64_url_digit(*input.get(cursor + 1)?)?;
312        let c = decode_base64_url_digit(*input.get(cursor + 2)?)?;
313        out.push((a << 2) | (b >> 4));
314        out.push(((b & 0b0000_1111) << 4) | (c >> 2));
315    } else if remainder != 0 {
316        return None;
317    }
318
319    Some(out)
320}
321
322const fn decode_base64_url_digit(raw: u8) -> Option<u8> {
323    match raw {
324        b'A'..=b'Z' => Some(raw - b'A'),
325        b'a'..=b'z' => Some(raw - b'a' + 26),
326        b'0'..=b'9' => Some(raw - b'0' + 52),
327        b'-' => Some(62),
328        b'_' => Some(63),
329        _ => None,
330    }
331}
332
333fn encode_hex(bytes: &[u8]) -> String {
334    const HEX: &[u8; 16] = b"0123456789abcdef";
335    let mut out = String::with_capacity(bytes.len() * 2);
336    for byte in bytes {
337        out.push(HEX[(byte >> 4) as usize] as char);
338        out.push(HEX[(byte & 0x0f) as usize] as char);
339    }
340    out
341}
342
343fn decode_hex(raw: &str) -> Option<Vec<u8>> {
344    if !raw.len().is_multiple_of(2) {
345        return None;
346    }
347
348    let mut out = Vec::with_capacity(raw.len() / 2);
349    let chars: Vec<char> = raw.chars().collect();
350    let mut idx = 0;
351    while idx < chars.len() {
352        let hi = decode_hex_nibble(chars[idx])?;
353        let lo = decode_hex_nibble(chars[idx + 1])?;
354        out.push((hi << 4) | lo);
355        idx += 2;
356    }
357
358    Some(out)
359}
360
361const fn decode_hex_nibble(c: char) -> Option<u8> {
362    match c {
363        '0'..='9' => Some((c as u8) - b'0'),
364        'a'..='f' => Some((c as u8) - b'a' + 10),
365        'A'..='F' => Some((c as u8) - b'A' + 10),
366        _ => None,
367    }
368}
369
370#[cfg(test)]
371mod tests {
372    use super::*;
373
374    #[test]
375    fn stamp_text_roundtrip_v3() {
376        let mut stamp = Stamp::seed();
377        stamp.event();
378        stamp.event();
379
380        let encoded = stamp_to_text(&stamp);
381        assert!(encoded.starts_with(ITC_TEXT_PREFIX));
382        let decoded = stamp_from_text(&encoded).expect("parse encoded stamp");
383        assert_eq!(decoded, stamp);
384    }
385
386    #[test]
387    fn stamp_text_roundtrip_v1_legacy_decode() {
388        let mut stamp = Stamp::seed();
389        for _ in 0..8 {
390            stamp.event();
391        }
392
393        let legacy = format!(
394            "{LEGACY_ITC_TEXT_PREFIX}{}",
395            encode_hex(&stamp.serialize_compact())
396        );
397        let decoded = stamp_from_text(&legacy).expect("parse legacy stamp");
398        assert_eq!(decoded, stamp);
399    }
400
401    #[test]
402    fn sparse_payload_smaller_than_legacy_hex() {
403        let mut stamp = Stamp::seed();
404        for _ in 0..1024 {
405            stamp.event();
406        }
407
408        let compact = stamp.serialize_compact();
409        let sparse = compact_to_sparse_payload(&compact).expect("sparse payload");
410        let legacy_text = encode_hex(&compact);
411        let sparse_text = encode_base64_url_no_pad(&sparse);
412
413        assert!(sparse_text.len() < legacy_text.len());
414    }
415
416    #[test]
417    fn decode_rejects_malformed_v3_payloads() {
418        assert!(stamp_from_text("itc:v3:^").is_none());
419
420        // valid base64url but invalid sparse payload version
421        let encoded = encode_base64_url_no_pad(&[99, 0]);
422        assert!(stamp_from_text(&format!("itc:v3:{encoded}")).is_none());
423    }
424
425    #[test]
426    fn sparse_compact_roundtrip_preserves_bytes() {
427        let mut stamp = Stamp::seed();
428        for _ in 0..64 {
429            stamp.event();
430        }
431
432        let compact = stamp.serialize_compact();
433        let sparse = compact_to_sparse_payload(&compact).expect("to sparse");
434        let reconstructed = sparse_payload_to_compact(&sparse).expect("to compact");
435        assert_eq!(reconstructed, compact);
436    }
437
438    #[test]
439    fn sparse_decode_rejects_duplicate_indices() {
440        let mut sparse = Vec::new();
441        sparse.push(SPARSE_ITC_WIRE_VERSION);
442        encode_varint_usize(2, &mut sparse); // id bits len
443        sparse.push(0b0100_0000); // Id::One leaf
444        encode_varint_usize(1, &mut sparse); // event bits len
445        sparse.push(0); // Event::Leaf kind bit
446        encode_varint_usize(2, &mut sparse); // two non-zero values
447        encode_varint_usize(0, &mut sparse); // first index delta
448        encode_varint_u32(1, &mut sparse);
449        encode_varint_usize(0, &mut sparse); // duplicate index delta
450        encode_varint_u32(2, &mut sparse);
451
452        assert!(sparse_payload_to_compact(&sparse).is_none());
453    }
454
455    #[test]
456    fn sparse_decode_rejects_out_of_range_index() {
457        let mut sparse = Vec::new();
458        sparse.push(SPARSE_ITC_WIRE_VERSION);
459        encode_varint_usize(2, &mut sparse); // id bits len
460        sparse.push(0b0100_0000); // Id::One leaf
461        encode_varint_usize(1, &mut sparse); // event bits len
462        sparse.push(0); // Event::Leaf kind bit
463        encode_varint_usize(1, &mut sparse); // one non-zero value
464        encode_varint_usize(1, &mut sparse); // out-of-range index
465        encode_varint_u32(3, &mut sparse);
466
467        assert!(sparse_payload_to_compact(&sparse).is_none());
468    }
469
470    #[test]
471    fn decode_rejects_bad_input() {
472        assert!(stamp_from_text("itc:v1:not-hex").is_none());
473        assert!(stamp_from_text("itc:v1:abc").is_none());
474        assert!(stamp_from_text("itc:v3:abcde").is_none());
475        assert!(stamp_from_text("itc:AQ").is_none());
476    }
477}
bones_core/clock/text.rs

bones_core/clock/
text.rs
