Skip to main content

rustbinary/
adaptive.rs

1use alloc::{borrow::Cow, string::String, vec::Vec};
2
3use crate::{
4    canonical::encode_varint_le, BitReader, BitWriter, Config, Error, Result, TrailingBytes,
5};
6
7const RAW_UTF8: u8 = 0;
8const ASCII7: u8 = 1;
9const RAW_INTEGERS: u8 = 0;
10const DELTA_INTEGERS: u8 = 1;
11const RLE_INTEGERS: u8 = 2;
12
13/// Number of leading elements sampled by [`AdaptiveMode::Heuristic`] before
14/// deciding whether delta / run-length coding is worth a full pass.
15pub const HEURISTIC_SAMPLE: usize = 64;
16
17/// How much analysis the adaptive codec performs before encoding.
18///
19/// The choice is **size-only**: every strategy is lossless, so a cheaper mode
20/// never changes what decodes, only how many bytes the frame occupies and how
21/// many scan passes the encoder performs.
22#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
23pub enum AdaptiveMode {
24    /// Encode directly with the raw representation.
25    ///
26    /// Zero analysis passes — the low-latency default for online paths. Bytes
27    /// are larger than `Heuristic`/`Exact` on compressible data, but the
28    /// encoder never rescans the input to save a few bytes.
29    #[default]
30    Off,
31    /// Sample the first [`HEURISTIC_SAMPLE`] elements to decide whether
32    /// delta / run-length pays off, then take a single sizing pass over the
33    /// chosen strategy.
34    ///
35    /// Integer collections are always safe to sample (the choice is size-only
36    /// and lossless). Strings cannot be sampled safely — `ASCII7` requires
37    /// every scalar to be ASCII, so they use the exact scan in this mode.
38    Heuristic,
39    /// Compare the complete raw / delta / run-length sizes and pick the
40    /// smallest. Optimal size at the cost of extra full scans; best for
41    /// offline compression.
42    Exact,
43}
44
45/// Selected representation for one adaptively encoded string.
46#[derive(Clone, Copy, Debug, Eq, PartialEq)]
47pub enum StringStrategy {
48    /// Original UTF-8 bytes.
49    RawUtf8,
50    /// Seven bits per ASCII scalar.
51    Ascii7,
52}
53
54/// Selected representation for one adaptively encoded `i64` collection.
55#[derive(Clone, Copy, Debug, Eq, PartialEq)]
56pub enum CollectionStrategy {
57    /// Independent ZigZag varints.
58    Raw,
59    /// First value followed by ZigZag deltas.
60    Delta,
61    /// ZigZag value and run-length pairs.
62    RunLength,
63}
64
65/// Data-aware encoding configuration.
66#[derive(Clone, Copy, Debug, Eq, PartialEq)]
67pub struct AdaptiveConfig {
68    base: Config,
69    mode: AdaptiveMode,
70}
71
72impl AdaptiveConfig {
73    pub(crate) const fn new(base: Config) -> Self {
74        Self {
75            base,
76            mode: AdaptiveMode::Off,
77        }
78    }
79
80    /// Returns the variable-integer payload configuration.
81    pub const fn base_config(self) -> Config {
82        self.base
83    }
84
85    /// Selects how much analysis the adaptive encoder performs.
86    ///
87    /// [`AdaptiveMode::Off`] (the default) encodes directly with no extra
88    /// scans; [`AdaptiveMode::Heuristic`] samples a bounded prefix;
89    /// [`AdaptiveMode::Exact`] compares complete encodings.
90    pub const fn with_adaptive_mode(mut self, mode: AdaptiveMode) -> Self {
91        self.mode = mode;
92        self
93    }
94
95    /// Returns the configured analysis mode.
96    pub const fn mode(self) -> AdaptiveMode {
97        self.mode
98    }
99
100    /// Uses value-width adaptive varints for a regular nextjson payload.
101    pub fn serialize<T: nextjson::NsonSerialize + ?Sized>(self, value: &T) -> Result<Vec<u8>> {
102        self.base.serialize(value)
103    }
104
105    /// Decodes a regular value-width adaptive nextjson payload.
106    pub fn deserialize<'de, T: nextjson::NsonDeserialize<'de>>(
107        self,
108        input: &'de [u8],
109    ) -> Result<T> {
110        self.base.deserialize(input)
111    }
112
113    /// Encodes a string using raw UTF-8 or 7-bit ASCII packing, whichever is smaller.
114    pub fn encode_string(self, value: &str) -> Result<Vec<u8>> {
115        if self.mode == AdaptiveMode::Off {
116            // Direct raw UTF-8 with no ASCII scan: the low-latency default.
117            let required = 1usize
118                .checked_add(varint_size(value.len() as u128))
119                .and_then(|size| size.checked_add(value.len()))
120                .ok_or(Error::Adaptive("encoded size overflow"))?;
121            self.enforce_byte_limit(required)?;
122            let mut output = Vec::with_capacity(required);
123            output.push(RAW_UTF8);
124            push_varint(&mut output, value.len() as u128);
125            output.extend_from_slice(value.as_bytes());
126            return Ok(output);
127        }
128        let required = self.encoded_string_size(value)?;
129        let mut output = Vec::new();
130        output
131            .try_reserve_exact(required)
132            .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
133        output.resize(required, 0);
134        self.encode_string_into_slice(&mut output, value)?;
135        Ok(output)
136    }
137
138    /// Returns the exact adaptive string frame size without allocating.
139    pub fn encoded_string_size(self, value: &str) -> Result<usize> {
140        let (_, _, required) = string_layout(value, self.mode)?;
141        self.enforce_byte_limit(required)?;
142        Ok(required)
143    }
144
145    /// Encodes a string into caller-owned memory without allocating.
146    ///
147    /// The output is left untouched when it is too small.
148    pub fn encode_string_into_slice(self, output: &mut [u8], value: &str) -> Result<usize> {
149        let (strategy, payload_size, required) = string_layout(value, self.mode)?;
150        self.enforce_byte_limit(required)?;
151        if output.len() < required {
152            return Err(Error::BufferTooSmall {
153                required,
154                available: output.len(),
155            });
156        }
157        let mut cursor = OutputCursor::new(&mut output[..required]);
158        cursor.byte(match strategy {
159            StringStrategy::RawUtf8 => RAW_UTF8,
160            StringStrategy::Ascii7 => ASCII7,
161        });
162        cursor.varint(value.len() as u128);
163        match strategy {
164            StringStrategy::RawUtf8 => cursor.bytes(value.as_bytes()),
165            StringStrategy::Ascii7 => {
166                let packed = cursor.take_mut(payload_size);
167                let mut writer = BitWriter::new(packed);
168                for byte in value.bytes() {
169                    writer.write(byte as u128, 7)?;
170                }
171            }
172        }
173        Ok(required)
174    }
175
176    /// Returns the strategy tag without decoding the string.
177    pub fn string_strategy(self, input: &[u8]) -> Result<StringStrategy> {
178        match input.first().copied().ok_or(Error::UnexpectedEnd)? {
179            RAW_UTF8 => Ok(StringStrategy::RawUtf8),
180            ASCII7 => Ok(StringStrategy::Ascii7),
181            _ => Err(Error::Adaptive("unknown string strategy")),
182        }
183    }
184
185    /// Decodes and validates an adaptively encoded string.
186    pub fn decode_string(self, input: &[u8]) -> Result<String> {
187        Ok(self.decode_string_borrowed(input)?.into_owned())
188    }
189
190    /// Decodes a string into caller-owned UTF-8 storage without allocating.
191    ///
192    /// The returned string borrows `output`. Raw UTF-8 is copied into the
193    /// destination; use [`Self::decode_string_borrowed`] when borrowing the
194    /// encoded frame directly is preferable. The output is left untouched
195    /// when its capacity is smaller than the declared decoded length.
196    pub fn decode_string_into_slice<'output>(
197        self,
198        output: &'output mut [u8],
199        input: &[u8],
200    ) -> Result<&'output str> {
201        self.enforce_byte_limit(input.len())?;
202        let mut cursor = Cursor::new(input);
203        let strategy = cursor.byte()?;
204        if !matches!(strategy, RAW_UTF8 | ASCII7) {
205            return Err(Error::Adaptive("unknown string strategy"));
206        }
207        let length = cursor.usize_varint()?;
208        if output.len() < length {
209            return Err(Error::BufferTooSmall {
210                required: length,
211                available: output.len(),
212            });
213        }
214
215        match strategy {
216            RAW_UTF8 => {
217                let bytes = cursor.take(length)?;
218                core::str::from_utf8(bytes).map_err(Error::InvalidUtf8)?;
219                output[..length].copy_from_slice(bytes);
220            }
221            ASCII7 => {
222                let meaningful_bits = length
223                    .checked_mul(7)
224                    .ok_or(Error::Adaptive("ASCII7 length overflow"))?;
225                let packed = meaningful_bits
226                    .checked_add(7)
227                    .ok_or(Error::Adaptive("ASCII7 length overflow"))?
228                    / 8;
229                let bytes = cursor.take(packed)?;
230                let mut reader = BitReader::new(bytes);
231                for slot in &mut output[..length] {
232                    *slot = reader.read(7)? as u8;
233                }
234                validate_ascii_padding(bytes, meaningful_bits)?;
235            }
236            _ => return Err(Error::Adaptive("unknown string strategy")),
237        }
238        cursor.finish(self.base.trailing)?;
239        core::str::from_utf8(&output[..length]).map_err(Error::InvalidUtf8)
240    }
241
242    /// Decodes a string while borrowing raw UTF-8 payloads directly from `input`.
243    ///
244    /// ASCII7 payloads require expansion and are therefore returned as owned
245    /// strings. The returned [`Cow`] makes that distinction explicit.
246    pub fn decode_string_borrowed(self, input: &[u8]) -> Result<Cow<'_, str>> {
247        self.enforce_byte_limit(input.len())?;
248        let mut cursor = Cursor::new(input);
249        let strategy = cursor.byte()?;
250        let length = cursor.usize_varint()?;
251        let value = match strategy {
252            RAW_UTF8 => {
253                let bytes = cursor.take(length)?;
254                Cow::Borrowed(core::str::from_utf8(bytes).map_err(Error::InvalidUtf8)?)
255            }
256            ASCII7 => {
257                let meaningful_bits = length
258                    .checked_mul(7)
259                    .ok_or(Error::Adaptive("ASCII7 length overflow"))?;
260                let packed = meaningful_bits
261                    .checked_add(7)
262                    .ok_or(Error::Adaptive("ASCII7 length overflow"))?
263                    / 8;
264                let bytes = cursor.take(packed)?;
265                let mut reader = BitReader::new(bytes);
266                let mut value = String::new();
267                value
268                    .try_reserve_exact(length)
269                    .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
270                for _ in 0..length {
271                    // A 7-bit read is always 0..=127, so every scalar is ASCII
272                    // by construction; truncation is the only failure mode.
273                    value.push(reader.read(7)? as u8 as char);
274                }
275                validate_ascii_padding(bytes, meaningful_bits)?;
276                Cow::Owned(value)
277            }
278            _ => return Err(Error::Adaptive("unknown string strategy")),
279        };
280        cursor.finish(self.base.trailing)?;
281        Ok(value)
282    }
283
284    /// Encodes an `i64` slice using raw, delta, or run-length varints.
285    pub fn encode_i64_slice(self, values: &[i64]) -> Result<Vec<u8>> {
286        if self.mode == AdaptiveMode::Off {
287            // Direct raw encoding with a single growing pass: the low-latency
288            // default never rescans the input to save a few bytes.
289            self.enforce_collection_limit(values.len())?;
290            let mut output = Vec::with_capacity(values.len().saturating_add(1));
291            output.push(RAW_INTEGERS);
292            push_varint(&mut output, values.len() as u128);
293            for value in values {
294                push_varint(&mut output, zigzag_i64(*value));
295            }
296            self.enforce_byte_limit(output.len())?;
297            return Ok(output);
298        }
299        let required = self.encoded_i64_slice_size(values)?;
300        let mut output = Vec::new();
301        output
302            .try_reserve_exact(required)
303            .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
304        output.resize(required, 0);
305        self.encode_i64_slice_into_slice(&mut output, values)?;
306        Ok(output)
307    }
308
309    /// Returns the exact adaptive integer-collection frame size without allocating.
310    pub fn encoded_i64_slice_size(self, values: &[i64]) -> Result<usize> {
311        self.enforce_collection_limit(values.len())?;
312        let (_, _, required) = collection_layout(values, self.mode)?;
313        self.enforce_byte_limit(required)?;
314        Ok(required)
315    }
316
317    /// Encodes an integer collection into caller-owned memory without allocating.
318    ///
319    /// The output is left untouched when it is too small.
320    pub fn encode_i64_slice_into_slice(self, output: &mut [u8], values: &[i64]) -> Result<usize> {
321        self.enforce_collection_limit(values.len())?;
322        let (strategy, _, required) = collection_layout(values, self.mode)?;
323        self.enforce_byte_limit(required)?;
324        if output.len() < required {
325            return Err(Error::BufferTooSmall {
326                required,
327                available: output.len(),
328            });
329        }
330        let mut cursor = OutputCursor::new(&mut output[..required]);
331        cursor.byte(match strategy {
332            CollectionStrategy::Raw => RAW_INTEGERS,
333            CollectionStrategy::Delta => DELTA_INTEGERS,
334            CollectionStrategy::RunLength => RLE_INTEGERS,
335        });
336        cursor.varint(values.len() as u128);
337        match strategy {
338            CollectionStrategy::Raw => {
339                for value in values {
340                    cursor.varint(zigzag_i64(*value));
341                }
342            }
343            CollectionStrategy::Delta => {
344                if let Some(first) = values.first() {
345                    cursor.varint(zigzag_i64(*first));
346                    for pair in values.windows(2) {
347                        cursor.varint(zigzag_i128(pair[1] as i128 - pair[0] as i128));
348                    }
349                }
350            }
351            CollectionStrategy::RunLength => {
352                let mut start = 0;
353                while start < values.len() {
354                    let mut end = start + 1;
355                    while end < values.len() && values[end] == values[start] {
356                        end += 1;
357                    }
358                    cursor.varint(zigzag_i64(values[start]));
359                    cursor.varint((end - start) as u128);
360                    start = end;
361                }
362            }
363        }
364        Ok(required)
365    }
366
367    /// Returns the collection strategy tag without decoding all values.
368    pub fn collection_strategy(self, input: &[u8]) -> Result<CollectionStrategy> {
369        match input.first().copied().ok_or(Error::UnexpectedEnd)? {
370            RAW_INTEGERS => Ok(CollectionStrategy::Raw),
371            DELTA_INTEGERS => Ok(CollectionStrategy::Delta),
372            RLE_INTEGERS => Ok(CollectionStrategy::RunLength),
373            _ => Err(Error::Adaptive("unknown collection strategy")),
374        }
375    }
376
377    /// Decodes an adaptive `i64` collection with checked delta reconstruction.
378    pub fn decode_i64_vec(self, input: &[u8]) -> Result<Vec<i64>> {
379        let length = self.decoded_i64_slice_len(input)?;
380        let mut values = Vec::new();
381        values
382            .try_reserve_exact(length)
383            .map_err(|_| Error::SizeLimit { limit: u64::MAX })?;
384        values.resize(length, 0);
385        self.decode_i64_slice_into(&mut values, input)?;
386        Ok(values)
387    }
388
389    /// Returns the declared decoded element count after validating the frame header.
390    pub fn decoded_i64_slice_len(self, input: &[u8]) -> Result<usize> {
391        self.enforce_byte_limit(input.len())?;
392        let mut cursor = Cursor::new(input);
393        let strategy = cursor.byte()?;
394        if !matches!(strategy, RAW_INTEGERS | DELTA_INTEGERS | RLE_INTEGERS) {
395            return Err(Error::Adaptive("unknown collection strategy"));
396        }
397        let length = cursor.usize_varint()?;
398        self.enforce_collection_limit(length)?;
399        Ok(length)
400    }
401
402    /// Decodes an adaptive integer collection into caller-owned memory.
403    ///
404    /// This path performs no heap allocation. The output is left untouched
405    /// when it is smaller than the decoded collection length.
406    pub fn decode_i64_slice_into(self, output: &mut [i64], input: &[u8]) -> Result<usize> {
407        self.enforce_byte_limit(input.len())?;
408        let mut cursor = Cursor::new(input);
409        let strategy = cursor.byte()?;
410        if !matches!(strategy, RAW_INTEGERS | DELTA_INTEGERS | RLE_INTEGERS) {
411            return Err(Error::Adaptive("unknown collection strategy"));
412        }
413        let length = cursor.usize_varint()?;
414        self.enforce_collection_limit(length)?;
415        if output.len() < length {
416            return Err(Error::BufferTooSmall {
417                required: length,
418                available: output.len(),
419            });
420        }
421        let mut written = 0usize;
422        match strategy {
423            RAW_INTEGERS => {
424                while written < length {
425                    let remaining_values = length - written;
426                    let plain = plain_varint_prefix(cursor.remaining_slice()).min(remaining_values);
427                    for byte in cursor.take(plain)? {
428                        output[written] = decode_i128(*byte as u128) as i64;
429                        written += 1;
430                    }
431                    if written < length {
432                        output[written] = decode_i64(cursor.varint()?)?;
433                        written += 1;
434                    }
435                }
436            }
437            DELTA_INTEGERS => {
438                if length != 0 {
439                    output[0] = decode_i64(cursor.varint()?)?;
440                    written = 1;
441                    while written < length {
442                        let delta = decode_i128(cursor.varint()?);
443                        let next = (output[written - 1] as i128)
444                            .checked_add(delta)
445                            .and_then(|value| i64::try_from(value).ok())
446                            .ok_or(Error::Adaptive("delta reconstruction overflow"))?;
447                        output[written] = next;
448                        written += 1;
449                    }
450                }
451            }
452            RLE_INTEGERS => {
453                while written < length {
454                    let value = decode_i64(cursor.varint()?)?;
455                    let run = cursor.usize_varint()?;
456                    if run == 0 || run > length - written {
457                        return Err(Error::Adaptive("invalid run length"));
458                    }
459                    output[written..written + run].fill(value);
460                    written += run;
461                }
462            }
463            _ => unreachable!("strategy was validated above"),
464        }
465        cursor.finish(self.base.trailing)?;
466        Ok(written)
467    }
468
469    fn enforce_byte_limit(self, length: usize) -> Result<()> {
470        if let Some(limit) = self.base.limit {
471            if length as u64 > limit {
472                return Err(Error::SizeLimit { limit });
473            }
474        }
475        Ok(())
476    }
477
478    fn enforce_collection_limit(self, length: usize) -> Result<()> {
479        if let Some(limit) = self.base.collection_limit {
480            if length as u64 > limit {
481                return Err(Error::CollectionLimit { limit });
482            }
483        }
484        Ok(())
485    }
486}
487
488fn validate_ascii_padding(bytes: &[u8], meaningful_bits: usize) -> Result<()> {
489    if meaningful_bits % 8 != 0
490        && bytes
491            .last()
492            .is_some_and(|last| last >> (meaningful_bits % 8) != 0)
493    {
494        return Err(Error::Adaptive("non-zero ASCII7 padding"));
495    }
496    Ok(())
497}
498
499fn string_layout(value: &str, mode: AdaptiveMode) -> Result<(StringStrategy, usize, usize)> {
500    let raw_size = value.len();
501    // ASCII7 requires every scalar to be ASCII, so the scan cannot be sampled
502    // safely; `Off` skips the scan entirely and writes raw UTF-8.
503    let packed_size = if mode == AdaptiveMode::Off {
504        None
505    } else if is_ascii(value.as_bytes()) {
506        Some(
507            value
508                .len()
509                .checked_mul(7)
510                .and_then(|bits| bits.checked_add(7))
511                .ok_or(Error::Adaptive("encoded size overflow"))?
512                / 8,
513        )
514    } else {
515        None
516    };
517    let (strategy, payload_size) = match packed_size {
518        Some(size) if size < raw_size => (StringStrategy::Ascii7, size),
519        _ => (StringStrategy::RawUtf8, raw_size),
520    };
521    let required = 1usize
522        .checked_add(varint_size(value.len() as u128))
523        .and_then(|size| size.checked_add(payload_size))
524        .ok_or(Error::Adaptive("encoded size overflow"))?;
525    Ok((strategy, payload_size, required))
526}
527
528fn is_ascii(input: &[u8]) -> bool {
529    #[cfg(feature = "simd")]
530    return crate::simd::is_ascii(input);
531    #[cfg(not(feature = "simd"))]
532    input.is_ascii()
533}
534
535fn plain_varint_prefix(input: &[u8]) -> usize {
536    #[cfg(feature = "simd")]
537    return crate::simd::plain_varint_prefix(input);
538    #[cfg(not(feature = "simd"))]
539    input.iter().take_while(|&&byte| byte <= 250).count()
540}
541
542/// Exact byte size of the independent-ZigZag encoding of `values`.
543fn raw_size(values: &[i64]) -> Result<usize> {
544    values.iter().try_fold(0usize, |size, value| {
545        size.checked_add(varint_size(zigzag_i64(*value)))
546            .ok_or(Error::Adaptive("encoded size overflow"))
547    })
548}
549
550/// Exact byte size of the delta encoding of `values`.
551fn delta_size(values: &[i64]) -> Result<usize> {
552    let Some(first) = values.first() else {
553        return Ok(0);
554    };
555    values
556        .windows(2)
557        .try_fold(varint_size(zigzag_i64(*first)), |size, pair| {
558            size.checked_add(varint_size(zigzag_i128(pair[1] as i128 - pair[0] as i128)))
559                .ok_or(Error::Adaptive("encoded size overflow"))
560        })
561}
562
563/// Exact byte size of the run-length encoding of `values`.
564fn rle_size(values: &[i64]) -> Result<usize> {
565    let mut size = 0usize;
566    let mut start = 0;
567    while start < values.len() {
568        let mut end = start + 1;
569        while end < values.len() && values[end] == values[start] {
570            end += 1;
571        }
572        size = size
573            .checked_add(varint_size(zigzag_i64(values[start])))
574            .and_then(|size| size.checked_add(varint_size((end - start) as u128)))
575            .ok_or(Error::Adaptive("encoded size overflow"))?;
576        start = end;
577    }
578    Ok(size)
579}
580
581/// Picks the smallest complete encoding from precomputed sizes.
582fn best_strategy(raw: usize, delta: usize, rle: usize) -> (CollectionStrategy, usize) {
583    if delta < raw && delta <= rle {
584        (CollectionStrategy::Delta, delta)
585    } else if rle < raw {
586        (CollectionStrategy::RunLength, rle)
587    } else {
588        (CollectionStrategy::Raw, raw)
589    }
590}
591
592fn collection_layout(
593    values: &[i64],
594    mode: AdaptiveMode,
595) -> Result<(CollectionStrategy, usize, usize)> {
596    let (strategy, payload_size) = match mode {
597        // Direct raw encoding: no analysis at all.
598        AdaptiveMode::Off => (CollectionStrategy::Raw, raw_size(values)?),
599        // Compare the whole collection exactly.
600        AdaptiveMode::Exact => {
601            let raw = raw_size(values)?;
602            let delta = delta_size(values)?;
603            let rle = rle_size(values)?;
604            best_strategy(raw, delta, rle)
605        }
606        // The sample covers everything: the comparison is exact and cheap.
607        AdaptiveMode::Heuristic if values.len() <= HEURISTIC_SAMPLE => {
608            let raw = raw_size(values)?;
609            let delta = delta_size(values)?;
610            let rle = rle_size(values)?;
611            best_strategy(raw, delta, rle)
612        }
613        // Sample a bounded prefix to pick a strategy, then take one full
614        // sizing pass under the chosen strategy.
615        AdaptiveMode::Heuristic => {
616            let sample = &values[..HEURISTIC_SAMPLE];
617            let raw = raw_size(sample)?;
618            let delta = delta_size(sample)?;
619            let rle = rle_size(sample)?;
620            let (chosen, _) = best_strategy(raw, delta, rle);
621            let payload = match chosen {
622                CollectionStrategy::Raw => raw_size(values)?,
623                CollectionStrategy::Delta => delta_size(values)?,
624                CollectionStrategy::RunLength => rle_size(values)?,
625            };
626            (chosen, payload)
627        }
628    };
629    let required = 1usize
630        .checked_add(varint_size(values.len() as u128))
631        .and_then(|size| size.checked_add(payload_size))
632        .ok_or(Error::Adaptive("encoded size overflow"))?;
633    Ok((strategy, payload_size, required))
634}
635
636const fn zigzag_i64(value: i64) -> u128 {
637    ((value << 1) ^ (value >> 63)) as u64 as u128
638}
639
640const fn zigzag_i128(value: i128) -> u128 {
641    ((value << 1) ^ (value >> 127)) as u128
642}
643
644fn decode_i64(value: u128) -> Result<i64> {
645    i64::try_from(decode_i128(value)).map_err(|_| Error::IntegerOverflow { target: "i64" })
646}
647
648const fn decode_i128(value: u128) -> i128 {
649    ((value >> 1) as i128) ^ -((value & 1) as i128)
650}
651
652const fn varint_size(value: u128) -> usize {
653    match value {
654        0..=250 => 1,
655        251..=0xffff => 3,
656        0x1_0000..=0xffff_ffff => 5,
657        0x1_0000_0000..=0xffff_ffff_ffff_ffff => 9,
658        _ => 17,
659    }
660}
661
662struct OutputCursor<'a> {
663    output: &'a mut [u8],
664    position: usize,
665}
666
667impl<'a> OutputCursor<'a> {
668    fn new(output: &'a mut [u8]) -> Self {
669        Self {
670            output,
671            position: 0,
672        }
673    }
674
675    fn byte(&mut self, value: u8) {
676        self.output[self.position] = value;
677        self.position += 1;
678    }
679
680    fn bytes(&mut self, value: &[u8]) {
681        self.take_mut(value.len()).copy_from_slice(value);
682    }
683
684    fn take_mut(&mut self, length: usize) -> &mut [u8] {
685        let start = self.position;
686        self.position += length;
687        &mut self.output[start..self.position]
688    }
689
690    fn varint(&mut self, value: u128) {
691        // Single source of truth: the canonical little-endian marker-varint
692        // (also used by the compact profile and the Kani proofs).
693        let (bytes, len) = encode_varint_le(value);
694        self.bytes(&bytes[..len]);
695    }
696}
697
698/// Appends a canonical little-endian marker-varint to a growing vector.
699///
700/// Used by the `Off` owned-encode fast paths, which avoid a sizing pass by
701/// letting the output buffer grow.
702fn push_varint(output: &mut Vec<u8>, value: u128) {
703    let (bytes, len) = encode_varint_le(value);
704    output.extend_from_slice(&bytes[..len]);
705}
706
707struct Cursor<'a> {
708    input: &'a [u8],
709    position: usize,
710}
711
712impl<'a> Cursor<'a> {
713    const fn new(input: &'a [u8]) -> Self {
714        Self { input, position: 0 }
715    }
716
717    fn byte(&mut self) -> Result<u8> {
718        Ok(self.take(1)?[0])
719    }
720
721    fn take(&mut self, length: usize) -> Result<&'a [u8]> {
722        let end = self
723            .position
724            .checked_add(length)
725            .ok_or(Error::UnexpectedEnd)?;
726        let bytes = self
727            .input
728            .get(self.position..end)
729            .ok_or(Error::UnexpectedEnd)?;
730        self.position = end;
731        Ok(bytes)
732    }
733
734    fn remaining_slice(&self) -> &'a [u8] {
735        &self.input[self.position..]
736    }
737
738    fn take_array<const N: usize>(&mut self) -> Result<[u8; N]> {
739        self.take(N)?.try_into().map_err(|_| Error::UnexpectedEnd)
740    }
741
742    fn varint(&mut self) -> Result<u128> {
743        let marker = self.byte()?;
744        let (value, minimum) = match marker {
745            0..=250 => return Ok(marker as u128),
746            251 => (u16::from_le_bytes(self.take_array()?) as u128, 251),
747            252 => (u32::from_le_bytes(self.take_array()?) as u128, 0x1_0000),
748            253 => (
749                u64::from_le_bytes(self.take_array()?) as u128,
750                0x1_0000_0000,
751            ),
752            254 => (
753                u128::from_le_bytes(self.take_array()?),
754                0x1_0000_0000_0000_0000,
755            ),
756            marker => return Err(Error::InvalidVarintMarker(marker)),
757        };
758        if value < minimum {
759            Err(Error::NonCanonicalVarint)
760        } else {
761            Ok(value)
762        }
763    }
764
765    fn usize_varint(&mut self) -> Result<usize> {
766        usize::try_from(self.varint()?).map_err(|_| Error::IntegerOverflow { target: "usize" })
767    }
768
769    fn finish(self, trailing: TrailingBytes) -> Result<()> {
770        if trailing == TrailingBytes::Reject && self.position != self.input.len() {
771            return Err(Error::TrailingBytes {
772                remaining: self.input.len() - self.position,
773            });
774        }
775        Ok(())
776    }
777}