Skip to main content

qubit_codec_binary/codec/
zig_zag_codec.rs

1// =============================================================================
2//    Copyright (c) 2026 Haixing Hu.
3//
4//    SPDX-License-Identifier: Apache-2.0
5//
6//    Licensed under the Apache License, Version 2.0.
7// =============================================================================
8
9use core::convert::Infallible;
10use core::marker::PhantomData;
11
12use qubit_codec::Codec;
13use qubit_codec::DecodeFailure;
14
15use crate::Leb128Codec;
16use crate::Leb128DecodeError;
17use crate::Leb128DecodePolicy;
18use crate::NonStrict;
19use crate::codec::leb128_codec::map_leb128_decode_failure;
20use crate::codec::leb128_codec::uleb_encoded_len;
21
22/// Type-level unchecked ZigZag + unsigned LEB128 codec.
23///
24/// Encoding is always canonical; `P` only affects decoding. Encoding-only
25/// callers should conventionally use [`NonStrict`] because no decoding policy
26/// is applied on that path.
27///
28/// # Type Parameters
29///
30/// - `T`: Signed integer value type to decode from ZigZag-encoded LEB128 bytes
31///   and encode into ZigZag-encoded LEB128 bytes.
32/// - `P`: Required type-level decoding policy implementing
33///   [`Leb128DecodePolicy`] for the underlying unsigned LEB128 payload. Use
34///   [`crate::Strict`] to reject non-canonical inputs, or [`NonStrict`] to
35///   accept non-canonical inputs. This parameter does not affect canonical
36///   encoding.
37///
38/// The decoding policy is intentionally required so wire-format callers make
39/// the canonicality contract explicit.
40/// The underlying unsigned LEB128 payload remains subject to its target
41/// integer's maximum decode width and terminal payload bits, including under
42/// [`NonStrict`]. See that policy's documentation for the width limits.
43///
44/// ```compile_fail
45/// use qubit_codec_binary::ZigZagCodec;
46///
47/// let _ = ZigZagCodec::<i64>::default();
48/// ```
49///
50/// # Examples
51///
52/// ```
53/// use qubit_codec_binary::{
54///     NonStrict,
55///     ZigZagCodec,
56/// };
57///
58/// let mut output = [0_u8; ZigZagCodec::<i64, NonStrict>::MAX_ENCODE_UNITS_PER_VALUE];
59/// let written = unsafe {
60///     ZigZagCodec::<i64, NonStrict>::encode(-42, &mut output, 0)
61/// };
62/// assert_eq!(1, written);
63///
64/// let (decoded, consumed) = unsafe {
65///     ZigZagCodec::<i64, NonStrict>::decode(&output[..written], 0)
66/// }.expect("canonical ZigZag LEB128 value should decode");
67/// assert_eq!(-42, decoded);
68/// assert_eq!(1, consumed.get());
69/// ```
70#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
71pub struct ZigZagCodec<T, P> {
72    /// Associates the value and decode-policy types without storing either.
73    marker: PhantomData<fn() -> (T, P)>,
74}
75
76/// Implements the ZigZag codec for one signed and unsigned integer pair.
77///
78/// The expansion defines the unchecked helpers and the [`Codec`] implementation
79/// while keeping their arithmetic tied to the integer type's bit width.
80macro_rules! impl_zig_zag_codec {
81    ($signed:ty, $unsigned:ty, $shift:expr) => {
82        impl<P> ZigZagCodec<$signed, P>
83        where
84            P: Leb128DecodePolicy,
85        {
86            /// Minimum number of bytes that can represent a complete value.
87            pub const MIN_UNITS_PER_VALUE: usize = <Self as Codec>::MIN_UNITS_PER_VALUE;
88
89            /// Maximum number of bytes emitted when encoding this type.
90            pub const MAX_ENCODE_UNITS_PER_VALUE: usize = <Self as Codec>::MAX_ENCODE_UNITS_PER_VALUE;
91
92            /// Maximum number of bytes consumed when decoding this type.
93            pub const MAX_DECODE_UNITS_PER_VALUE: usize = <Self as Codec>::MAX_DECODE_UNITS_PER_VALUE;
94
95            /// Decodes a value from `input` starting at `input_index` without
96            /// bounds checks.
97            ///
98            /// # Parameters
99            ///
100            /// - `input`: Source byte buffer.
101            /// - `input_index`: Start index in `input`.
102            ///
103            /// # Returns
104            ///
105            /// Returns the decoded value and the non-zero number of consumed
106            /// bytes.
107            ///
108            /// # Errors
109            ///
110            /// Returns [`Leb128DecodeError`] if the underlying LEB128 bytes are
111            /// incomplete, malformed, or non-canonical under strict policy.
112            ///
113            /// # Safety
114            ///
115            /// The caller must guarantee that `input_index` is a valid boundary
116            /// and at least [`Self::MIN_UNITS_PER_VALUE`] byte is readable
117            /// from `input_index`.
118            #[inline]
119            pub unsafe fn decode(
120                input: &[u8],
121                input_index: usize,
122            ) -> Result<($signed, core::num::NonZeroUsize), Leb128DecodeError> {
123                debug_assert!(input.len().saturating_sub(input_index) >= Self::MIN_UNITS_PER_VALUE);
124
125                // SAFETY: The caller guarantees enough readable bytes for this
126                // type.
127                let (encoded, consumed) = unsafe { Leb128Codec::<$unsigned, P>::decode(input, input_index)? };
128                let value = ((encoded >> 1) as $signed) ^ (-((encoded & 1) as $signed));
129                Ok((value, consumed))
130            }
131
132            /// Encodes `value` into `output` starting at `output_index` without
133            /// bounds checks.
134            ///
135            /// # Parameters
136            ///
137            /// - `value`: Value to encode.
138            /// - `output`: Destination byte buffer.
139            /// - `output_index`: Start index in `output`.
140            ///
141            /// # Returns
142            ///
143            /// Returns the number of written bytes.
144            ///
145            /// # Safety
146            ///
147            /// The caller must guarantee that the canonical ZigZag LEB128 byte
148            /// width of `value` is writable starting at `output_index`.
149            /// Reserving [`Self::MAX_ENCODE_UNITS_PER_VALUE`] bytes always satisfies
150            /// this requirement; for a known value, the exact
151            /// [`Codec::encode_len`] is sufficient.
152            #[must_use = "the returned byte count determines the encoded payload range"]
153            #[inline]
154            pub unsafe fn encode(value: $signed, output: &mut [u8], output_index: usize) -> usize {
155                let encoded = ((value as $unsigned) << 1) ^ ((value >> $shift) as $unsigned);
156                // SAFETY: The caller guarantees enough writable bytes for the
157                // canonical representation of this value.
158                unsafe { Leb128Codec::<$unsigned, NonStrict>::encode(encoded, output, output_index) }
159            }
160        }
161
162        impl<P> Codec for ZigZagCodec<$signed, P>
163        where
164            P: Leb128DecodePolicy,
165        {
166            /// The signed integer represented by this codec.
167            type Value = $signed;
168            /// One byte of the ZigZag LEB128 representation.
169            type Unit = u8;
170            /// Detailed errors for incomplete, malformed, or policy-rejected input.
171            type DecodeError = Leb128DecodeError;
172            /// Encoding is infallible for every value of this signed integer type.
173            type EncodeError = Infallible;
174
175            /// Minimum bytes readable before decoding can be attempted.
176            const MIN_UNITS_PER_VALUE: usize = 1;
177            /// Maximum bytes emitted by canonical ZigZag plus unsigned LEB128 encoding.
178            const MAX_ENCODE_UNITS_PER_VALUE: usize = Leb128Codec::<$unsigned, NonStrict>::MAX_ENCODE_UNITS_PER_VALUE;
179            /// Maximum bytes consumed by decoding this signed integer type.
180            const MAX_DECODE_UNITS_PER_VALUE: usize = Leb128Codec::<$unsigned, NonStrict>::MAX_DECODE_UNITS_PER_VALUE;
181
182            /// Returns the exact width of the canonical unsigned LEB128 encoding
183            /// of `value` after ZigZag mapping.
184            ///
185            /// # Parameters
186            ///
187            /// - `value`: Signed integer value whose encoded width is queried.
188            ///
189            /// # Returns
190            ///
191            /// Returns a width of at least one byte and no more than
192            /// [`Self::MAX_ENCODE_UNITS_PER_VALUE`]. The decoding policy does not
193            /// affect this length.
194            #[inline]
195            fn encode_len(&self, value: &$signed) -> usize {
196                let encoded = ((*value as $unsigned) << 1) ^ ((*value >> $shift) as $unsigned);
197                uleb_encoded_len(encoded as u128)
198            }
199
200            /// Decodes one ZigZag-mapped unsigned LEB128 value and reports its
201            /// byte consumption.
202            ///
203            /// # Parameters
204            ///
205            /// - `input`: Source bytes.
206            /// - `input_index`: Start index of the encoded value.
207            ///
208            /// # Returns
209            ///
210            /// Returns the signed value and the non-zero number of bytes consumed.
211            ///
212            /// # Errors
213            ///
214            /// Returns [`DecodeFailure::Incomplete`] with the detailed error
215            /// retained as its source and a minimum total byte requirement when
216            /// a valid prefix needs more input. Returns [`DecodeFailure::Invalid`]
217            /// with the detailed error and consumed-byte count for malformed
218            /// input or, under [`crate::Strict`], a non-canonical underlying
219            /// unsigned LEB128 representation. The required count is a lower
220            /// bound, not a guarantee that decoding will succeed at that length.
221            /// The consumed count is not a guaranteed protocol-field recovery
222            /// boundary. Non-strict decoding still enforces the target integer's
223            /// maximum width and terminal payload-bit limits.
224            ///
225            /// # Safety
226            ///
227            /// `input_index` must be a valid boundary and at least
228            /// [`Self::MIN_UNITS_PER_VALUE`] bytes must be readable there.
229            #[inline]
230            unsafe fn decode(
231                &mut self,
232                input: &[u8],
233                input_index: usize,
234            ) -> Result<($signed, core::num::NonZeroUsize), DecodeFailure<Self::DecodeError>> {
235                debug_assert!(input.len().saturating_sub(input_index) >= Self::MIN_UNITS_PER_VALUE);
236
237                // SAFETY: The caller upholds the `Codec::decode`
238                // contract.
239                unsafe { Self::decode(input, input_index) }.map_err(map_leb128_decode_failure)
240            }
241
242            /// Encodes one value using canonical ZigZag mapping followed by
243            /// unsigned LEB128 encoding.
244            ///
245            /// # Parameters
246            ///
247            /// - `value`: Signed integer value to encode.
248            /// - `output`: Destination byte buffer.
249            /// - `output_index`: Start index in `output`.
250            ///
251            /// # Returns
252            ///
253            /// Returns the number of bytes written, equal to
254            /// [`Self::encode_len`] for `value`.
255            ///
256            /// # Errors
257            ///
258            /// This implementation uses [`Infallible`]; every value of the
259            /// signed integer type can be encoded.
260            ///
261            /// # Safety
262            ///
263            /// The caller must ensure [`Codec::can_encode_value`] returned
264            /// `true` for `value`. Starting at `output_index`, provide either
265            /// the exact [`Self::encode_len`] capacity for `value` or at least
266            /// [`Self::MAX_ENCODE_UNITS_PER_VALUE`] writable bytes.
267            #[inline]
268            unsafe fn encode(
269                &mut self,
270                value: &$signed,
271                output: &mut [u8],
272                output_index: usize,
273            ) -> Result<usize, Self::EncodeError> {
274                let required = self.encode_len(value);
275                debug_assert!(output.len().saturating_sub(output_index) >= required);
276
277                // SAFETY: The `Codec::encode` contract provides either the
278                // exact canonical width or this type's maximum width.
279                let written = unsafe { Self::encode(*value, output, output_index) };
280                Ok(written)
281            }
282        }
283    };
284}
285
286impl_zig_zag_codec!(i8, u8, 7);
287impl_zig_zag_codec!(i16, u16, 15);
288impl_zig_zag_codec!(i32, u32, 31);
289impl_zig_zag_codec!(i64, u64, 63);
290impl_zig_zag_codec!(i128, u128, 127);
291impl_zig_zag_codec!(isize, usize, isize::BITS - 1);