crypto_bigint/uint/
encoding.rs

1//! Const-friendly decoding/encoding operations for [`Uint`].
2
3#[cfg(feature = "der")]
4mod der;
5#[cfg(feature = "rlp")]
6mod rlp;
7
8use super::Uint;
9use crate::{
10    ByteOrder, DecodeError, EncodedSize, Encoding, Limb, Word, bitlen,
11    encoding::{truncate_be, truncate_le},
12};
13use core::{fmt, ops::Deref};
14
15#[cfg(feature = "alloc")]
16use crate::{NonZero, Reciprocal, UintRef, WideWord};
17#[cfg(feature = "alloc")]
18use alloc::{string::String, vec::Vec};
19
20#[cfg(feature = "alloc")]
21const RADIX_ENCODING_LIMBS_LARGE: usize = 16;
22#[cfg(feature = "alloc")]
23const RADIX_ENCODING_THRESHOLD_LARGE: usize = 24;
24
25const RADIX_ENCODING_MIN: u32 = 2;
26const RADIX_ENCODING_MAX: u32 = 36;
27
28impl<const LIMBS: usize> Uint<LIMBS> {
29    /// Decode [`Uint`] from the provided big endian bytes.
30    ///
31    /// # Panics
32    /// If the supplied byte slice is not equal to the byte length of this [`Uint`], i.e.
33    /// [`Limb::BYTES`] * `LIMBS`.
34    #[must_use]
35    #[track_caller]
36    pub const fn from_be_slice(bytes: &[u8]) -> Self {
37        assert!(
38            bytes.len() == Limb::BYTES * LIMBS,
39            "bytes are not the expected size"
40        );
41
42        let mut res = [Limb::ZERO; LIMBS];
43        let mut buf = [0u8; Limb::BYTES];
44        let mut i = 0;
45
46        while i < LIMBS {
47            let mut j = 0;
48            while j < Limb::BYTES {
49                buf[j] = bytes[i * Limb::BYTES + j];
50                j += 1;
51            }
52            res[LIMBS - i - 1] = Limb(Word::from_be_bytes(buf));
53            i += 1;
54        }
55
56        Uint::new(res)
57    }
58
59    /// Decode [`Uint`] from the provided little endian bytes.
60    ///
61    /// # Panics
62    /// If the supplied byte slice is not equal to the byte length of this [`Uint`], i.e.
63    /// [`Limb::BYTES`] * `LIMBS`.
64    #[must_use]
65    #[track_caller]
66    pub const fn from_le_slice(bytes: &[u8]) -> Self {
67        assert!(
68            bytes.len() == Limb::BYTES * LIMBS,
69            "bytes are not the expected size"
70        );
71
72        let mut res = [Limb::ZERO; LIMBS];
73        let mut buf = [0u8; Limb::BYTES];
74        let mut i = 0;
75
76        while i < LIMBS {
77            let mut j = 0;
78            while j < Limb::BYTES {
79                buf[j] = bytes[i * Limb::BYTES + j];
80                j += 1;
81            }
82            res[i] = Limb(Word::from_le_bytes(buf));
83            i += 1;
84        }
85
86        Uint::new(res)
87    }
88
89    /// Decode [`Uint`] from the provided big endian bytes, zero padding if necessary, and
90    /// truncating to the least significant bytes in the event the given amount of data exceeds
91    /// `bits_precision`.
92    ///
93    /// # Panics
94    /// If `bits_precision > Self::BITS`.
95    #[must_use]
96    #[track_caller]
97    pub fn from_be_slice_truncated(bytes: &[u8], bits_precision: u32) -> Self {
98        let mut ret = Self::ZERO;
99        assert!(
100            fill_limbs_from_be_slice_truncated(bytes, &mut ret.limbs, bits_precision).is_ok(),
101            "U{} is too small to store requested {} bits",
102            Self::BITS,
103            bits_precision
104        );
105        ret
106    }
107
108    /// Decode [`Uint`] from the provided little endian bytes, zero padding if necessary, and
109    /// truncating to the least significant bytes in the event the given amount of data exceeds
110    /// `bits_precision`.
111    ///
112    /// # Panics
113    /// If `bits_precision > Self::BITS`.
114    #[must_use]
115    #[track_caller]
116    pub fn from_le_slice_truncated(bytes: &[u8], bits_precision: u32) -> Self {
117        let mut ret = Self::ZERO;
118        assert!(
119            fill_limbs_from_le_slice_truncated(bytes, &mut ret.limbs, bits_precision).is_ok(),
120            "U{} is too small to store requested {} bits",
121            Self::BITS,
122            bits_precision
123        );
124        ret
125    }
126
127    /// Decode [`Uint`] from the provided slice, using the supplied [`ByteOrder`] to determine the
128    /// endianness.
129    ///
130    /// # Panics
131    /// If the supplied byte slice is not equal to the byte length of this [`Uint`], i.e.
132    /// [`Limb::BYTES`] * `LIMBS`.
133    #[must_use]
134    #[track_caller]
135    pub const fn from_slice(bytes: &[u8], byte_order: ByteOrder) -> Self {
136        match byte_order {
137            ByteOrder::BigEndian => Self::from_be_slice(bytes),
138            ByteOrder::LittleEndian => Self::from_le_slice(bytes),
139        }
140    }
141
142    /// Decode [`Uint`] from the provided bytes, using the supplied [`ByteOrder`] to determine the
143    /// endianness.
144    ///
145    /// Zero pads if necessary, and truncates to the least significant bytes in the event the given
146    /// amount of data exceeds `bits_precision`.
147    ///
148    /// # Panics
149    /// If `bits_precision > Self::BITS`.
150    #[must_use]
151    #[track_caller]
152    pub fn from_slice_truncated(bytes: &[u8], bits_precision: u32, byte_order: ByteOrder) -> Self {
153        match byte_order {
154            ByteOrder::BigEndian => Self::from_be_slice_truncated(bytes, bits_precision),
155            ByteOrder::LittleEndian => Self::from_le_slice_truncated(bytes, bits_precision),
156        }
157    }
158
159    /// Create a new [`Uint`] from the provided big endian hex string.
160    ///
161    /// # Panics
162    /// If the hex is malformed or not zero-padded accordingly for the size.
163    #[must_use]
164    #[track_caller]
165    pub const fn from_be_hex(hex: &str) -> Self {
166        let bytes = hex.as_bytes();
167
168        assert!(
169            bytes.len() == Limb::BYTES * LIMBS * 2,
170            "hex string is not the expected size"
171        );
172
173        let mut res = [Limb::ZERO; LIMBS];
174        let mut buf = [0u8; Limb::BYTES];
175        let mut i = 0;
176        let mut err = 0;
177
178        while i < LIMBS {
179            let mut j = 0;
180            while j < Limb::BYTES {
181                let offset = (i * Limb::BYTES + j) * 2;
182                let (result, byte_err) = decode_hex_byte([bytes[offset], bytes[offset + 1]]);
183                err |= byte_err;
184                buf[j] = result;
185                j += 1;
186            }
187            res[LIMBS - i - 1] = Limb(Word::from_be_bytes(buf));
188            i += 1;
189        }
190
191        assert!(err == 0, "invalid hex byte");
192
193        Uint::new(res)
194    }
195
196    /// Create a new [`Uint`] from the provided little endian hex string.
197    ///
198    /// # Panics
199    /// If the hex is malformed or not zero-padded accordingly for the size.
200    #[must_use]
201    #[track_caller]
202    pub const fn from_le_hex(hex: &str) -> Self {
203        let bytes = hex.as_bytes();
204
205        assert!(
206            bytes.len() == Limb::BYTES * LIMBS * 2,
207            "bytes are not the expected size"
208        );
209
210        let mut res = [Limb::ZERO; LIMBS];
211        let mut buf = [0u8; Limb::BYTES];
212        let mut i = 0;
213        let mut err = 0;
214
215        while i < LIMBS {
216            let mut j = 0;
217            while j < Limb::BYTES {
218                let offset = (i * Limb::BYTES + j) * 2;
219                let (result, byte_err) = decode_hex_byte([bytes[offset], bytes[offset + 1]]);
220                err |= byte_err;
221                buf[j] = result;
222                j += 1;
223            }
224            res[i] = Limb(Word::from_le_bytes(buf));
225            i += 1;
226        }
227
228        assert!(err == 0, "invalid hex byte");
229
230        Uint::new(res)
231    }
232
233    /// Create a new [`Uint`] from the provided hex string, using the supplied [`ByteOrder`] to
234    /// determine the endianness.
235    ///
236    /// # Panics
237    /// - if the hex is malformed or not zero-padded accordingly for the size.
238    #[must_use]
239    #[track_caller]
240    pub const fn from_hex(hex: &str, byte_order: ByteOrder) -> Self {
241        match byte_order {
242            ByteOrder::BigEndian => Self::from_be_hex(hex),
243            ByteOrder::LittleEndian => Self::from_le_hex(hex),
244        }
245    }
246
247    /// Serialize this [`Uint`] as big-endian, writing it into the provided
248    /// byte slice.
249    #[cfg(feature = "hybrid-array")]
250    #[inline]
251    pub(crate) fn write_be_bytes(&self, out: &mut [u8]) {
252        debug_assert_eq!(out.len(), Limb::BYTES * LIMBS);
253
254        for (src, dst) in self
255            .limbs
256            .iter()
257            .rev()
258            .cloned()
259            .zip(out.chunks_exact_mut(Limb::BYTES))
260        {
261            dst.copy_from_slice(&src.to_be_bytes());
262        }
263    }
264
265    /// Serialize this [`Uint`] as little-endian, writing it into the provided
266    /// byte slice.
267    #[cfg(feature = "hybrid-array")]
268    #[inline]
269    pub(crate) fn write_le_bytes(&self, out: &mut [u8]) {
270        debug_assert_eq!(out.len(), Limb::BYTES * LIMBS);
271
272        for (src, dst) in self
273            .limbs
274            .iter()
275            .cloned()
276            .zip(out.chunks_exact_mut(Limb::BYTES))
277        {
278            dst.copy_from_slice(&src.to_le_bytes());
279        }
280    }
281
282    /// Create a new [`Uint`] from a string slice in a given base.
283    ///
284    /// The string may begin with a `+` character, and may use
285    /// underscore characters to separate digits.
286    ///
287    /// # Errors
288    /// - Returns [`DecodeError::InputSize`] if the size of the decoded integer is larger than this
289    ///   type can represent
290    /// - Returns [`DecodeError::InvalidDigit`] if the input value contains non-digit characters or
291    ///   digits outside of the range `0..radix`.
292    ///
293    /// # Panics
294    /// - if `radix` is not in the range from 2 to 36.
295    pub fn from_str_radix_vartime(src: &str, radix: u32) -> Result<Self, DecodeError> {
296        let mut slf = Self::ZERO;
297        radix_decode_str(src, radix, &mut SliceDecodeByLimb::new(&mut slf.limbs))?;
298        Ok(slf)
299    }
300
301    /// Format a [`Uint`] as a string in a given base.
302    ///
303    /// # Panics
304    /// - if `radix` is not in the range from 2 to 36.
305    #[cfg(feature = "alloc")]
306    #[must_use]
307    pub fn to_string_radix_vartime(&self, radix: u32) -> String {
308        let mut buf = *self;
309        radix_encode_limbs_mut_to_string(radix, buf.as_mut_uint_ref())
310    }
311
312    /// Serialize as big endian bytes.
313    #[must_use]
314    pub const fn to_be_bytes(&self) -> EncodedUint<LIMBS> {
315        EncodedUint::new_be(self)
316    }
317
318    /// Serialize as little endian bytes.
319    #[must_use]
320    pub const fn to_le_bytes(&self) -> EncodedUint<LIMBS> {
321        EncodedUint::new_le(self)
322    }
323}
324
325/// Common implementation of a truncating big endian decoder which supports partial inputs and
326/// truncates inputs larger than the provided `bits_precision`.
327///
328/// Fills the supplied `limbs` with the decoded `bytes` after truncating to `bits_precision`.
329pub(crate) fn fill_limbs_from_be_slice_truncated(
330    bytes: &[u8],
331    limbs: &mut [Limb],
332    bits_precision: u32,
333) -> Result<(), DecodeError> {
334    if bitlen::from_limbs(limbs.len()) < bits_precision {
335        return Err(DecodeError::Precision);
336    }
337
338    let bytes = truncate_be(bytes, bits_precision);
339    for (chunk, limb) in bytes.rchunks(Limb::BYTES).zip(limbs.iter_mut()) {
340        *limb = Limb::from_be_slice(chunk);
341    }
342
343    mask_high_limb(limbs, bits_precision);
344    Ok(())
345}
346
347/// Common implementation of a truncating little endian decoder which supports partial inputs and
348/// truncates inputs larger than the provided `bits_precision`.
349///
350/// Fills the supplied `limbs` with the decoded `bytes` after truncating to `bits_precision`.
351pub(crate) fn fill_limbs_from_le_slice_truncated(
352    bytes: &[u8],
353    limbs: &mut [Limb],
354    bits_precision: u32,
355) -> Result<(), DecodeError> {
356    if bitlen::from_limbs(limbs.len()) < bits_precision {
357        return Err(DecodeError::Precision);
358    }
359
360    let bytes = truncate_le(bytes, bits_precision);
361    for (chunk, limb) in bytes.chunks(Limb::BYTES).zip(limbs.iter_mut()) {
362        *limb = Limb::from_le_slice(chunk);
363    }
364
365    mask_high_limb(limbs, bits_precision);
366    Ok(())
367}
368
369/// Handle masking for the case that `bits_precision` is not aligned to `Limb::BITS`.
370#[inline(always)]
371fn mask_high_limb(limbs: &mut [Limb], bits_precision: u32) {
372    debug_assert!(bitlen::from_limbs(limbs.len()) >= bits_precision);
373    let unaligned_bits = bits_precision & (Limb::BITS - 1);
374    if unaligned_bits != 0 {
375        limbs[bitlen::to_limbs(bits_precision) - 1].mask_to_precision(unaligned_bits);
376    }
377}
378
379/// [`Uint`] encoded as bytes.
380// Until const generic expressions are stable, we cannot statically declare a `u8` array
381// of the size `LIMBS * Limb::BYTES`.
382// So instead we use the array of words, and treat it as an array of bytes.
383// It's a little hacky, but it works, because the array is guaranteed to be contiguous.
384#[derive(Copy, Clone, Debug, PartialEq, Eq)]
385pub struct EncodedUint<const LIMBS: usize>([Word; LIMBS]);
386
387#[allow(unsafe_code)]
388const fn cast_slice(limbs: &[Word]) -> &[u8] {
389    let new_len = size_of_val(limbs);
390
391    // SAFETY:
392    // - `size_of_val` returns the size of `limbs` in bytes
393    // - We are creating a new slice of the same size, but casting word to bytes, so we don't need
394    //   to worry about alignment because bytes are always aligned
395    unsafe { core::slice::from_raw_parts(limbs.as_ptr() as *mut u8, new_len) }
396}
397
398#[allow(unsafe_code)]
399const fn cast_slice_mut(limbs: &mut [Word]) -> &mut [u8] {
400    let new_len = size_of_val(limbs);
401
402    // SAFETY:
403    // - `size_of_val` returns the size of `limbs` in bytes
404    // - We are creating a new slice of the same size, but casting word to bytes, so we don't need
405    //   to worry about alignment because bytes are always aligned
406    unsafe { core::slice::from_raw_parts_mut(limbs.as_mut_ptr().cast::<u8>(), new_len) }
407}
408
409impl<const LIMBS: usize> EncodedUint<LIMBS> {
410    /// Extracts a byte slice containing the entire contents.
411    #[must_use]
412    pub const fn as_slice(&self) -> &[u8] {
413        cast_slice(&self.0)
414    }
415
416    /// Extracts a mutable byte slice containing the entire contents.
417    pub const fn as_mut_slice(&mut self) -> &mut [u8] {
418        cast_slice_mut(&mut self.0)
419    }
420
421    const fn new_le(value: &Uint<LIMBS>) -> Self {
422        let mut buffer = [0; LIMBS];
423        let mut i = 0;
424
425        while i < LIMBS {
426            let src_bytes = &value.limbs[i].0.to_le_bytes();
427
428            // We could cast the whole `buffer` to bytes at once,
429            // but IndexMut does not work in const context.
430            let dst_bytes: &mut [u8] = cast_slice_mut(core::slice::from_mut(&mut buffer[i]));
431
432            // `copy_from_slice` can be used here when MSRV moves past 1.87
433            let mut j = 0;
434            while j < Limb::BYTES {
435                dst_bytes[j] = src_bytes[j];
436                j += 1;
437            }
438
439            i += 1;
440        }
441        Self(buffer)
442    }
443
444    const fn new_be(value: &Uint<LIMBS>) -> Self {
445        let mut buffer = [0; LIMBS];
446        let mut i = 0;
447        while i < LIMBS {
448            let src_bytes = &value.limbs[i].0.to_be_bytes();
449
450            // We could cast the whole `buffer` to bytes at once,
451            // but IndexMut does not work in const context.
452            let dst_bytes: &mut [u8] =
453                cast_slice_mut(core::slice::from_mut(&mut buffer[LIMBS - 1 - i]));
454
455            // `copy_from_slice` can be used here when MSRV moves past 1.87
456            let mut j = 0;
457            while j < Limb::BYTES {
458                dst_bytes[j] = src_bytes[j];
459                j += 1;
460            }
461
462            i += 1;
463        }
464        Self(buffer)
465    }
466}
467
468impl<const LIMBS: usize> Default for EncodedUint<LIMBS> {
469    fn default() -> Self {
470        Self([0; LIMBS])
471    }
472}
473
474impl<const LIMBS: usize> AsRef<[u8]> for EncodedUint<LIMBS> {
475    fn as_ref(&self) -> &[u8] {
476        self.as_slice()
477    }
478}
479
480impl<const LIMBS: usize> AsMut<[u8]> for EncodedUint<LIMBS> {
481    fn as_mut(&mut self) -> &mut [u8] {
482        self.as_mut_slice()
483    }
484}
485
486impl<const LIMBS: usize> Deref for EncodedUint<LIMBS> {
487    type Target = [u8];
488    fn deref(&self) -> &Self::Target {
489        self.as_ref()
490    }
491}
492
493impl<const BYTES: usize, const LIMBS: usize> From<EncodedUint<LIMBS>> for [u8; BYTES]
494where
495    EncodedUint<LIMBS>: EncodedSize<Target = [u8; BYTES]>,
496{
497    #[inline]
498    fn from(input: EncodedUint<LIMBS>) -> Self {
499        Self::from(&input)
500    }
501}
502
503impl<const BYTES: usize, const LIMBS: usize> From<&EncodedUint<LIMBS>> for [u8; BYTES]
504where
505    EncodedUint<LIMBS>: EncodedSize<Target = [u8; BYTES]>,
506{
507    #[inline]
508    fn from(input: &EncodedUint<LIMBS>) -> Self {
509        let mut output = [0u8; BYTES];
510        output.as_mut_slice().copy_from_slice(input.as_ref());
511        output
512    }
513}
514
515impl<const BYTES: usize, const LIMBS: usize> From<[u8; BYTES]> for EncodedUint<LIMBS>
516where
517    [u8; BYTES]: EncodedSize<Target = EncodedUint<LIMBS>>,
518{
519    #[inline]
520    fn from(input: [u8; BYTES]) -> Self {
521        Self::from(&input)
522    }
523}
524
525impl<const BYTES: usize, const LIMBS: usize> From<&[u8; BYTES]> for EncodedUint<LIMBS>
526where
527    [u8; BYTES]: EncodedSize<Target = EncodedUint<LIMBS>>,
528{
529    #[inline]
530    fn from(input: &[u8; BYTES]) -> Self {
531        let mut output = Self::default();
532        output.as_mut().copy_from_slice(input.as_ref());
533        output
534    }
535}
536
537/// Returned if an object cannot be instantiated from the given byte slice.
538#[derive(Clone, Copy, Debug, PartialEq, Eq)]
539pub struct TryFromSliceError;
540
541impl fmt::Display for TryFromSliceError {
542    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
543        write!(f, "TryFromSliceError")
544    }
545}
546
547impl core::error::Error for TryFromSliceError {}
548
549impl<'a, const LIMBS: usize> TryFrom<&'a [u8]> for EncodedUint<LIMBS> {
550    type Error = TryFromSliceError;
551
552    fn try_from(bytes: &'a [u8]) -> Result<Self, Self::Error> {
553        if bytes.len() != Uint::<LIMBS>::BYTES {
554            return Err(TryFromSliceError);
555        }
556        let mut result = Self::default();
557        result.as_mut().copy_from_slice(bytes);
558        Ok(result)
559    }
560}
561
562impl<const LIMBS: usize> Encoding for Uint<LIMBS> {
563    type Repr = EncodedUint<LIMBS>;
564
565    #[inline]
566    fn from_be_bytes(bytes: Self::Repr) -> Self {
567        Self::from_be_slice(bytes.as_ref())
568    }
569
570    #[inline]
571    fn from_le_bytes(bytes: Self::Repr) -> Self {
572        Self::from_le_slice(bytes.as_ref())
573    }
574
575    #[inline]
576    fn from_be_slice_truncated(bytes: &[u8], bits_precision: u32) -> Self {
577        Self::from_be_slice_truncated(bytes, bits_precision)
578    }
579
580    #[inline]
581    fn from_le_slice_truncated(bytes: &[u8], bits_precision: u32) -> Self {
582        Self::from_le_slice_truncated(bytes, bits_precision)
583    }
584
585    #[inline]
586    fn to_be_bytes(&self) -> Self::Repr {
587        self.to_be_bytes()
588    }
589
590    #[inline]
591    fn to_le_bytes(&self) -> Self::Repr {
592        self.to_le_bytes()
593    }
594}
595
596/// Decode a single nibble of upper or lower hex
597#[inline(always)]
598#[allow(clippy::cast_sign_loss)]
599const fn decode_nibble(src: u8) -> u16 {
600    let byte = src as i16;
601    let mut ret: i16 = -1;
602
603    // 0-9  0x30-0x39
604    // if (byte > 0x2f && byte < 0x3a) ret += byte - 0x30 + 1; // -47
605    ret += (((0x2fi16 - byte) & (byte - 0x3a)) >> 8) & (byte - 47);
606    // A-F  0x41-0x46
607    // if (byte > 0x40 && byte < 0x47) ret += byte - 0x41 + 10 + 1; // -54
608    ret += (((0x40i16 - byte) & (byte - 0x47)) >> 8) & (byte - 54);
609    // a-f  0x61-0x66
610    // if (byte > 0x60 && byte < 0x67) ret += byte - 0x61 + 10 + 1; // -86
611    ret += (((0x60i16 - byte) & (byte - 0x67)) >> 8) & (byte - 86);
612
613    ret as u16
614}
615
616/// Decode a single byte encoded as two hexadecimal characters.
617/// Second element of the tuple is non-zero if the `bytes` values are not in the valid range
618/// (0-9, a-z, A-Z).
619#[inline(always)]
620#[allow(clippy::cast_possible_truncation)]
621pub(crate) const fn decode_hex_byte(bytes: [u8; 2]) -> (u8, u16) {
622    let hi = decode_nibble(bytes[0]);
623    let lo = decode_nibble(bytes[1]);
624    let byte = (hi << 4) | lo;
625    let err = byte >> 8;
626    let result = byte as u8;
627    (result, err)
628}
629
630/// Allow decoding of integers into fixed and variable-length types
631pub(crate) trait DecodeByLimb {
632    /// Access the limbs as a mutable slice
633    fn limbs_mut(&mut self) -> &mut [Limb];
634
635    /// Append a new most-significant limb
636    fn push_limb(&mut self, limb: Limb) -> bool;
637}
638
639/// Wrap a `Limb` slice as a target for decoding
640pub(crate) struct SliceDecodeByLimb<'de> {
641    limbs: &'de mut [Limb],
642    len: usize,
643}
644
645impl<'de> SliceDecodeByLimb<'de> {
646    #[inline]
647    pub fn new(limbs: &'de mut [Limb]) -> Self {
648        Self { limbs, len: 0 }
649    }
650}
651
652impl DecodeByLimb for SliceDecodeByLimb<'_> {
653    #[inline]
654    fn push_limb(&mut self, limb: Limb) -> bool {
655        if self.len < self.limbs.len() {
656            self.limbs[self.len] = limb;
657            self.len += 1;
658            true
659        } else {
660            false
661        }
662    }
663
664    #[inline]
665    fn limbs_mut(&mut self) -> &mut [Limb] {
666        &mut self.limbs[..self.len]
667    }
668}
669
670/// Decode an ascii string in base `radix`, writing the result to the `DecodeByLimb` instance `out`.
671///
672/// The input must be a non-empty ascii string, may begin with a `+` character, and may use `_` as a
673/// separator between digits.
674///
675/// # Panics
676/// - if `radix` is not within `RADIX_ENCODING_MIN..=RADIX_ENCODING_MAX`.
677#[allow(clippy::cast_possible_truncation, clippy::panic_in_result_fn)]
678pub(crate) fn radix_decode_str<D: DecodeByLimb>(
679    src: &str,
680    radix: u32,
681    out: &mut D,
682) -> Result<(), DecodeError> {
683    assert!(
684        (RADIX_ENCODING_MIN..=RADIX_ENCODING_MAX).contains(&radix),
685        "unsupported radix"
686    );
687    if radix == 2 || radix == 4 || radix == 16 {
688        radix_decode_str_aligned_digits(src, radix as u8, out)
689    } else {
690        radix_decode_str_digits(src, radix as u8, out)
691    }
692}
693
694#[inline(always)]
695/// Perform basic validation and pre-processing on a digit string
696fn radix_preprocess_str(src: &str) -> Result<&[u8], DecodeError> {
697    // Treat the input as ascii bytes
698    let src_b = src.as_bytes();
699    let mut digits = src_b.strip_prefix(b"+").unwrap_or(src_b);
700
701    if digits.is_empty() {
702        // Blank string or plain "+" not allowed
703        Err(DecodeError::Empty)
704    } else if digits.starts_with(b"_") || digits.ends_with(b"_") {
705        // Leading or trailing underscore not allowed
706        Err(DecodeError::InvalidDigit)
707    } else {
708        // Strip leading zeroes to simplify parsing
709        while digits[0] == b'0' || digits[0] == b'_' {
710            digits = &digits[1..];
711            if digits.is_empty() {
712                break;
713            }
714        }
715        Ok(digits)
716    }
717}
718
719/// Decode a string of digits in base `radix`
720#[allow(clippy::cast_possible_truncation)]
721fn radix_decode_str_digits<D: DecodeByLimb>(
722    src: &str,
723    radix: u8,
724    out: &mut D,
725) -> Result<(), DecodeError> {
726    let digits = radix_preprocess_str(src)?;
727    let mut buf = [0u8; Limb::BITS as _];
728    let mut limb_digits = Word::MAX.ilog(radix.into()) as usize;
729    let mut limb_max = Limb(Word::pow(radix.into(), limb_digits as _));
730    let mut digits_pos = 0;
731    let mut buf_pos = 0;
732
733    while digits_pos < digits.len() {
734        // Parse digits from most significant, to fill buffer limb
735        loop {
736            let digit = match digits[digits_pos] {
737                b @ b'0'..=b'9' => b - b'0',
738                b @ b'a'..=b'z' => b + 10 - b'a',
739                b @ b'A'..=b'Z' => b + 10 - b'A',
740                b'_' => {
741                    digits_pos += 1;
742                    continue;
743                }
744                _ => radix,
745            };
746            if digit >= radix {
747                return Err(DecodeError::InvalidDigit);
748            }
749            buf[buf_pos] = digit;
750            buf_pos += 1;
751            digits_pos += 1;
752
753            if digits_pos == digits.len() || buf_pos == limb_digits {
754                break;
755            }
756        }
757
758        // On the final loop, there may be fewer digits to process
759        if buf_pos < limb_digits {
760            limb_digits = buf_pos;
761            limb_max = Limb(Word::pow(radix.into(), limb_digits as _));
762        }
763
764        // Combine the digit bytes into a limb
765        let mut carry = Limb::ZERO;
766        for c in buf[..limb_digits].iter().copied() {
767            carry = Limb(carry.0 * Word::from(radix) + Word::from(c));
768        }
769        // Multiply the existing limbs by `radix` ^ `limb_digits`,
770        // and add the new least-significant limb
771        for limb in out.limbs_mut().iter_mut() {
772            (*limb, carry) = limb.carrying_mul_add(limb_max, carry, Limb::ZERO);
773        }
774        // Append the new carried limb, if any
775        if carry.0 != 0 && !out.push_limb(carry) {
776            return Err(DecodeError::InputSize);
777        }
778
779        buf_pos = 0;
780        buf[..limb_digits].fill(0);
781    }
782
783    Ok(())
784}
785
786/// Decode digits for bases where an integer number of characters
787/// can represent a saturated Limb (specifically 2, 4, and 16).
788#[allow(clippy::integer_division_remainder_used, reason = "needs triage")]
789fn radix_decode_str_aligned_digits<D: DecodeByLimb>(
790    src: &str,
791    radix: u8,
792    out: &mut D,
793) -> Result<(), DecodeError> {
794    debug_assert!(radix == 2 || radix == 4 || radix == 16);
795
796    let digits = radix_preprocess_str(src)?;
797    let shift = radix.trailing_zeros();
798    let limb_digits = (Limb::BITS / shift) as usize;
799    let mut buf = [0u8; Limb::BITS as _];
800    let mut buf_pos = 0;
801    let mut digits_pos = digits.len();
802
803    while digits_pos > 0 {
804        // Parse digits from the least significant, to fill the buffer limb
805        loop {
806            digits_pos -= 1;
807
808            let digit = match digits[digits_pos] {
809                b @ b'0'..=b'9' => b - b'0',
810                b @ b'a'..=b'z' => b + 10 - b'a',
811                b @ b'A'..=b'Z' => b + 10 - b'A',
812                b'_' => {
813                    // cannot occur when c == 0
814                    continue;
815                }
816                _ => radix,
817            };
818            if digit >= radix {
819                return Err(DecodeError::InvalidDigit);
820            }
821            buf[buf_pos] = digit;
822            buf_pos += 1;
823
824            if digits_pos == 0 || buf_pos == limb_digits {
825                break;
826            }
827        }
828
829        if buf_pos > 0 {
830            // Combine the digit bytes into a limb
831            let mut w: Word = 0;
832            for c in buf[..buf_pos].iter().rev().copied() {
833                w = (w << shift) | Word::from(c);
834            }
835            // Append the new most-significant limb
836            if !out.push_limb(Limb(w)) {
837                return Err(DecodeError::InputSize);
838            }
839
840            buf_pos = 0;
841            buf[..limb_digits].fill(0);
842        }
843    }
844
845    Ok(())
846}
847
848/// Encode a slice of limbs to a string in base `radix`. The result will have no leading
849/// zeros unless the value itself is zero.
850///
851/// # Panics
852/// - if `radix` is not in the range from 2 to 36.
853#[cfg(feature = "alloc")]
854pub(crate) fn radix_encode_limbs_to_string(radix: u32, limbs: &[Limb]) -> String {
855    let mut array_buf = [Limb::ZERO; 128];
856    let mut vec_buf = Vec::new();
857    let limb_count = limbs.len();
858    let buf = if limb_count <= array_buf.len() {
859        array_buf[..limb_count].copy_from_slice(limbs);
860        &mut array_buf[..limb_count]
861    } else {
862        vec_buf.extend_from_slice(limbs);
863        &mut vec_buf[..limb_count]
864    };
865    radix_encode_limbs_mut_to_string(radix, UintRef::new_mut(buf))
866}
867
868/// Encode a slice of limbs to a string in base `radix`. The contents of the slice
869/// will be used as a working buffer. The result will have no leading zeros unless
870/// the value itself is zero.
871///
872/// # Panics
873/// - if `radix` is not in the range from 2 to 36.
874#[cfg(feature = "alloc")]
875pub(crate) fn radix_encode_limbs_mut_to_string(radix: u32, limbs: &mut UintRef) -> String {
876    assert!(
877        (RADIX_ENCODING_MIN..=RADIX_ENCODING_MAX).contains(&radix),
878        "unsupported radix"
879    );
880
881    let mut out;
882    if radix.is_power_of_two() {
883        let size = bitlen::from_limbs(limbs.nlimbs()).div_ceil(radix.trailing_zeros()) as usize;
884        out = vec![0u8; size];
885        radix_encode_limbs_by_shifting(radix, limbs, &mut out[..]);
886    } else {
887        let params = RadixDivisionParams::for_radix(radix);
888        let size = params.encoded_size(limbs.nlimbs());
889        out = vec![0u8; size];
890        params.encode_limbs(limbs, &mut out[..]);
891    }
892    let size = out.len();
893    let mut skip = 0;
894    while skip + 1 < size && out[skip] == b'0' {
895        skip += 1;
896    }
897    if skip > 0 {
898        out.copy_within(skip..size, 0);
899        out.truncate(size - skip);
900    }
901    String::from_utf8(out).expect("utf-8 decoding error")
902}
903
904/// For `radix` values which are a power of two, encode the mutable limb slice to
905/// the output buffer as ASCII characters in base `radix`. Leading zeros are added to
906/// fill `out`. The slice `limbs` is used as a working buffer. Output will be truncated
907/// if the provided buffer is too small.
908#[cfg(feature = "alloc")]
909#[allow(clippy::cast_possible_truncation, reason = "needs triage")]
910#[allow(clippy::integer_division_remainder_used, reason = "needs triage")]
911fn radix_encode_limbs_by_shifting(radix: u32, limbs: &UintRef, out: &mut [u8]) {
912    debug_assert!(radix.is_power_of_two());
913    debug_assert!(!out.is_empty());
914
915    let radix_bits = radix.trailing_zeros();
916    let mask = (radix - 1) as u8;
917    let mut out_idx = out.len();
918    let mut digits: WideWord = 0;
919    let mut digits_bits = 0;
920    let mut digit;
921
922    for limb in limbs.iter().chain([&Limb::ZERO]) {
923        digits_bits += Limb::BITS;
924        digits |= WideWord::from(limb.0) << (digits_bits % Limb::BITS);
925        for _ in 0..((digits_bits / radix_bits) as usize).min(out_idx) {
926            out_idx -= 1;
927            (digit, digits) = ((digits as u8) & mask, digits >> radix_bits);
928            out[out_idx] = if digit < 10 {
929                b'0' + digit
930            } else {
931                b'a' + (digit - 10)
932            };
933            digits_bits -= radix_bits;
934        }
935    }
936
937    out[0..out_idx].fill(b'0');
938}
939
940/// Parameter set used to perform radix encoding by division.
941#[cfg(feature = "alloc")]
942#[derive(Debug, Clone, Copy)]
943pub(crate) struct RadixDivisionParams {
944    radix: u32,
945    digits_per_limb: usize,
946    bits_per_limb: u32,
947    recip_limb: Reciprocal,
948    digits_large: usize,
949    div_large: [Limb; RADIX_ENCODING_LIMBS_LARGE],
950    recip_large: Reciprocal,
951    shift_large: u32,
952}
953
954#[cfg(feature = "alloc")]
955impl RadixDivisionParams {
956    // Generate all valid parameters ahead of time
957    #[allow(trivial_numeric_casts)]
958    const ALL: [Self; 31] = {
959        let mut res = [Self {
960            radix: 0,
961            digits_per_limb: 0,
962            bits_per_limb: 0,
963            recip_limb: Reciprocal::default(),
964            digits_large: 0,
965            div_large: [Limb::ZERO; RADIX_ENCODING_LIMBS_LARGE],
966            shift_large: 0,
967            recip_large: Reciprocal::default(),
968        }; 31];
969        let mut radix: u32 = 3;
970        let mut i: usize = 0;
971        while radix <= RADIX_ENCODING_MAX {
972            if radix.is_power_of_two() {
973                radix += 1;
974                continue;
975            }
976            let digits_limb = Word::MAX.ilog(radix as Word);
977            let div_limb = NonZero::new_unchecked(Limb((radix as Word).pow(digits_limb)));
978            let bits_limb = Limb::BITS - div_limb.as_ref().leading_zeros() - 1;
979            let (div_large, digits_large, shift_large) =
980                radix_large_divisor(radix, div_limb, digits_limb as usize);
981            let recip_large = Reciprocal::new(
982                div_large[RADIX_ENCODING_LIMBS_LARGE - 1]
983                    .to_nz()
984                    .expect_copied("zero divisor"),
985            );
986            res[i] = Self {
987                radix,
988                digits_per_limb: digits_limb as usize,
989                bits_per_limb: bits_limb,
990                recip_limb: Reciprocal::new(div_limb),
991                digits_large,
992                div_large,
993                shift_large,
994                recip_large,
995            };
996            radix += 1;
997            i += 1;
998        }
999        res
1000    };
1001
1002    #[allow(trivial_numeric_casts)]
1003    pub const fn for_radix(radix: u32) -> Self {
1004        assert!(
1005            !(radix < RADIX_ENCODING_MIN || radix > RADIX_ENCODING_MAX),
1006            "invalid radix for division"
1007        );
1008        let ret = Self::ALL[(radix + radix.leading_zeros() - 33) as usize];
1009        assert!(ret.radix == radix, "radix lookup failure");
1010        ret
1011    }
1012
1013    /// Get the minimum size of the required output buffer for encoding a set of limbs.
1014    pub const fn encoded_size(&self, limb_count: usize) -> usize {
1015        // a slightly pessimistic estimate
1016        limb_count * (self.digits_per_limb + 1)
1017    }
1018
1019    /// Encode the mutable limb slice to the output buffer as ASCII characters in base
1020    /// `radix`. Leading zeros are added to fill `out`. The slice `limbs` is used as a
1021    /// working buffer. Output will be truncated if the provided buffer is too small.
1022    #[allow(clippy::cast_possible_truncation)]
1023    pub fn encode_limbs(&self, mut limbs: &mut UintRef, out: &mut [u8]) {
1024        let mut out_idx = out.len();
1025        let mut remain = Uint::<RADIX_ENCODING_LIMBS_LARGE>::ZERO;
1026
1027        while out_idx > 0 {
1028            let (digits, next_idx) = if limbs.nlimbs() >= RADIX_ENCODING_THRESHOLD_LARGE {
1029                let div_large = UintRef::new(&self.div_large);
1030                let remain_mut = remain.as_mut_uint_ref();
1031
1032                // Divide by the large divisor
1033                let limbs_hi = limbs.shl_assign_limb_vartime(self.shift_large);
1034                let rem_high = limbs.div_rem_large_shifted::<true>(
1035                    limbs_hi,
1036                    div_large,
1037                    RADIX_ENCODING_LIMBS_LARGE as u32,
1038                    self.recip_large,
1039                );
1040                let limbs_rem;
1041                // At this point, the limbs at and above RADIX_ENCODING_LIMBS_LARGE represent
1042                // the quotient, and the limbs below (plus rem_high) represent the remainder
1043                (limbs_rem, limbs) = limbs.split_at_mut(RADIX_ENCODING_LIMBS_LARGE - 1);
1044
1045                // Copy out the remainder
1046                remain_mut
1047                    .leading_mut(RADIX_ENCODING_LIMBS_LARGE - 1)
1048                    .copy_from(limbs_rem);
1049                remain_mut.limbs[RADIX_ENCODING_LIMBS_LARGE - 1] = rem_high;
1050                remain_mut.shr_assign_limb_vartime(self.shift_large);
1051
1052                (remain_mut, out_idx.saturating_sub(self.digits_large))
1053            } else {
1054                (core::mem::replace(&mut limbs, UintRef::new_mut(&mut [])), 0)
1055            };
1056
1057            // Encode the next batch of digits
1058            self.encode_limbs_small(digits, &mut out[next_idx..out_idx]);
1059            out_idx = next_idx;
1060        }
1061    }
1062
1063    #[allow(trivial_numeric_casts, reason = "needs triage")]
1064    #[allow(clippy::cast_possible_truncation, reason = "needs triage")]
1065    #[allow(clippy::integer_division_remainder_used, reason = "needs triage")]
1066    fn encode_limbs_small(&self, mut limbs: &mut UintRef, out: &mut [u8]) {
1067        const DIGITS: &[u8; 36] = b"0123456789abcdefghijklmnopqrstuvwxyz";
1068
1069        let radix = Word::from(self.radix);
1070        let mut out_idx = out.len();
1071        let mut bits_acc = 0;
1072        let (mut digit, mut digits_word);
1073
1074        while out_idx > 0 {
1075            if limbs.is_empty() {
1076                out[0..out_idx].fill(b'0');
1077                break;
1078            }
1079
1080            // The remainder represents a digit in base `radix ** digits_per_limb`
1081            let limbs_hi = limbs.shl_assign_limb_vartime(self.recip_limb.shift());
1082            digits_word = limbs
1083                .div_rem_limb_with_reciprocal_shifted(limbs_hi, &self.recip_limb)
1084                .0;
1085
1086            // Reduce the length of the input as we consume a limb's worth of bits (conservatively)
1087            bits_acc += self.bits_per_limb;
1088            if bits_acc >= Limb::BITS {
1089                bits_acc -= Limb::BITS;
1090                limbs = limbs.leading_mut(limbs.nlimbs().saturating_sub(1));
1091            }
1092
1093            // Output the individual digits
1094            for _ in 0..self.digits_per_limb.min(out_idx) {
1095                out_idx -= 1;
1096                (digits_word, digit) = (digits_word / radix, (digits_word % radix) as usize);
1097                out[out_idx] = DIGITS[digit];
1098            }
1099        }
1100    }
1101}
1102
1103/// Compute the maximum radix divisor for a number of limbs.
1104/// Returns a pair of the large divisor value and the number of digits,
1105/// such that `divisor = radix ** digits`. The value `div_limb` is the
1106/// largest power of `radix` that can fit within a limb.
1107#[cfg(feature = "alloc")]
1108#[allow(trivial_numeric_casts)]
1109const fn radix_large_divisor<const LIMBS: usize>(
1110    radix: u32,
1111    div_limb: NonZero<Limb>,
1112    digits_limb: usize,
1113) -> ([Limb; LIMBS], usize, u32) {
1114    let mut out = [Limb::ZERO; LIMBS];
1115    let mut digits_large = digits_limb;
1116    let mut top = 1;
1117    out[0] = div_limb.get_copy();
1118    // Calculate largest power of div_limb (itself a power of radix)
1119    while top < LIMBS {
1120        let mut carry = Limb::ZERO;
1121        let mut j = 0;
1122        while j < top {
1123            (out[j], carry) = out[j].carrying_mul_add(div_limb.get_copy(), carry, Limb::ZERO);
1124            j += 1;
1125        }
1126        if carry.0 != 0 {
1127            out[top] = carry;
1128            top += 1;
1129        }
1130        digits_large += digits_limb;
1131    }
1132    // Multiply by radix while we can do so without overflowing
1133    let mut out_test = out;
1134    loop {
1135        let mut carry = Limb::ZERO;
1136        let mut j = 0;
1137        while j < LIMBS {
1138            (out_test[j], carry) = out[j].carrying_mul_add(Limb(radix as Word), carry, Limb::ZERO);
1139            j += 1;
1140        }
1141        if carry.0 == 0 {
1142            out = out_test;
1143            digits_large += 1;
1144        } else {
1145            break;
1146        }
1147    }
1148
1149    let out_mut = UintRef::new_mut(&mut out);
1150    let shift = out_mut.leading_zeros();
1151    out_mut.shl_assign_limb_vartime(shift);
1152    (out, digits_large, shift)
1153}
1154
1155#[cfg(test)]
1156mod tests {
1157    use crate::{DecodeError, EncodedUint, Limb, U64, U128};
1158    use hex_literal::hex;
1159
1160    #[cfg(feature = "alloc")]
1161    use {
1162        super::{radix_encode_limbs_to_string, radix_large_divisor},
1163        crate::{NonZero, Uint, Word},
1164        alloc::format,
1165    };
1166
1167    cpubits::cpubits! {
1168        32 => {
1169            use crate::U64 as UintEx;
1170
1171            #[test]
1172            fn from_be_slice() {
1173                let bytes = hex!("0011223344556677");
1174                let n = UintEx::from_be_slice(&bytes);
1175                assert_eq!(n.as_limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
1176            }
1177
1178            #[test]
1179            fn from_le_slice() {
1180                let bytes = hex!("7766554433221100");
1181                let n = UintEx::from_le_slice(&bytes);
1182                assert_eq!(n.as_limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
1183            }
1184
1185            #[test]
1186            fn from_be_slice_truncated() {
1187                let bytes = hex!("0011223344556677");
1188                let n = UintEx::from_be_slice_truncated(&bytes, 64);
1189                assert_eq!(n.as_limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
1190            }
1191
1192            #[test]
1193            fn from_le_slice_truncated() {
1194                let bytes = hex!("7766554433221100");
1195                let n = UintEx::from_le_slice_truncated(&bytes, 64);
1196                assert_eq!(n.as_limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
1197            }
1198
1199            #[test]
1200            fn from_be_hex() {
1201                let n = UintEx::from_be_hex("0011223344556677");
1202                assert_eq!(n.as_limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
1203            }
1204
1205            #[test]
1206            fn from_le_hex() {
1207                let n = UintEx::from_le_hex("7766554433221100");
1208                assert_eq!(n.as_limbs(), &[Limb(0x44556677), Limb(0x00112233)]);
1209            }
1210        }
1211        64 => {
1212            use crate::U128 as UintEx;
1213
1214            #[test]
1215            fn from_be_slice() {
1216                let bytes = hex!("00112233445566778899aabbccddeeff");
1217                let n = UintEx::from_be_slice(&bytes);
1218                assert_eq!(
1219                    n.as_limbs(),
1220                    &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
1221                );
1222            }
1223
1224            #[test]
1225            fn from_le_slice() {
1226                let bytes = hex!("ffeeddccbbaa99887766554433221100");
1227                let n = UintEx::from_le_slice(&bytes);
1228                assert_eq!(
1229                    n.as_limbs(),
1230                    &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
1231                );
1232            }
1233
1234            #[test]
1235            fn from_be_slice_truncated() {
1236                let bytes = hex!("112233445566778899aabbccddeeff");
1237                let n = UintEx::from_be_slice_truncated(&bytes, 128);
1238                assert_eq!(
1239                    n.as_limbs(),
1240                    &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
1241                );
1242            }
1243
1244            #[test]
1245            fn from_le_slice_truncated() {
1246                let bytes = hex!("ffeeddccbbaa998877665544332211");
1247                let n = UintEx::from_le_slice_truncated(&bytes, 128);
1248                assert_eq!(
1249                    n.as_limbs(),
1250                    &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
1251                );
1252            }
1253
1254            #[test]
1255            fn from_be_hex() {
1256                let n = UintEx::from_be_hex("00112233445566778899aabbccddeeff");
1257                assert_eq!(
1258                    n.as_limbs(),
1259                    &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
1260                );
1261            }
1262
1263            #[test]
1264            fn from_le_hex() {
1265                let n = UintEx::from_le_hex("ffeeddccbbaa99887766554433221100");
1266                assert_eq!(
1267                    n.as_limbs(),
1268                    &[Limb(0x8899aabbccddeeff), Limb(0x0011223344556677)]
1269                );
1270            }
1271        }
1272    }
1273
1274    #[test]
1275    fn fill_limbs_from_be_slice_truncated_empty() {
1276        let mut limbs = [];
1277        assert!(super::fill_limbs_from_be_slice_truncated(b"", &mut limbs, 0).is_ok());
1278        assert_eq!(
1279            super::fill_limbs_from_be_slice_truncated(b"", &mut limbs, 1),
1280            Err(DecodeError::Precision)
1281        );
1282    }
1283
1284    #[test]
1285    fn fill_limbs_from_le_slice_truncated_empty() {
1286        let mut limbs = [];
1287        assert!(super::fill_limbs_from_le_slice_truncated(b"", &mut limbs, 0).is_ok());
1288        assert_eq!(
1289            super::fill_limbs_from_le_slice_truncated(b"", &mut limbs, 1),
1290            Err(DecodeError::Precision)
1291        );
1292    }
1293
1294    #[cfg(feature = "alloc")]
1295    #[test]
1296    fn hex_upper() {
1297        let hex = "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD";
1298        let n = U128::from_be_hex(hex);
1299        assert_eq!(hex, format!("{n:X}"));
1300    }
1301
1302    #[cfg(feature = "alloc")]
1303    #[test]
1304    fn hex_lower() {
1305        let hex = "aaaaaaaabbbbbbbbccccccccdddddddd";
1306        let n = U128::from_be_hex(hex);
1307        assert_eq!(hex, format!("{n:x}"));
1308    }
1309
1310    #[cfg(feature = "alloc")]
1311    #[test]
1312    fn fmt_binary() {
1313        let hex = "AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD";
1314        let n = U128::from_be_hex(hex);
1315        let expect = "\
1316            1010101010101010101010101010101010111011101110111011101110111011\
1317            1100110011001100110011001100110011011101110111011101110111011101";
1318        assert_eq!(expect, format!("{n:b}"));
1319    }
1320
1321    #[test]
1322    fn from_str_radix_disallowed() {
1323        let tests = [
1324            ("", 10, DecodeError::Empty),
1325            ("+", 10, DecodeError::Empty),
1326            ("_", 10, DecodeError::InvalidDigit),
1327            ("0_", 10, DecodeError::InvalidDigit),
1328            ("0_", 10, DecodeError::InvalidDigit),
1329            ("a", 10, DecodeError::InvalidDigit),
1330            (".", 10, DecodeError::InvalidDigit),
1331            (
1332                "99999999999999999999999999999999",
1333                10,
1334                DecodeError::InputSize,
1335            ),
1336        ];
1337        for (input, radix, expect) in tests {
1338            assert_eq!(U64::from_str_radix_vartime(input, radix), Err(expect));
1339        }
1340    }
1341
1342    #[test]
1343    fn from_str_radix_2() {
1344        let buf = &[b'1'; 128];
1345        let radix = U128::from_u64(2);
1346        let radix_max = U128::from_u64(1);
1347        let mut last: Option<U128> = None;
1348        for idx in (1..buf.len()).rev() {
1349            let res = U128::from_str_radix_vartime(
1350                core::str::from_utf8(&buf[..idx]).expect("utf-8 error"),
1351                2,
1352            )
1353            .expect("error decoding");
1354            assert!(!bool::from(res.is_zero()));
1355            if let Some(prev) = last {
1356                assert_eq!(res.saturating_mul(&radix).saturating_add(&radix_max), prev);
1357            }
1358            last = Some(res);
1359        }
1360        assert_eq!(last, Some(radix_max));
1361    }
1362
1363    #[test]
1364    fn from_str_radix_5() {
1365        let buf = &[b'4'; 55];
1366        let radix = U128::from_u64(5);
1367        let radix_max = U128::from_u64(4);
1368        let mut last: Option<U128> = None;
1369        for idx in (1..buf.len()).rev() {
1370            let res = U128::from_str_radix_vartime(
1371                core::str::from_utf8(&buf[..idx]).expect("utf-8 error"),
1372                5,
1373            )
1374            .expect("error decoding");
1375            assert!(!bool::from(res.is_zero()));
1376            if let Some(prev) = last {
1377                assert_eq!(res.saturating_mul(&radix).saturating_add(&radix_max), prev);
1378            }
1379            last = Some(res);
1380        }
1381        assert_eq!(last, Some(radix_max));
1382    }
1383
1384    #[test]
1385    fn from_str_radix_10() {
1386        let dec = "+340_282_366_920_938_463_463_374_607_431_768_211_455";
1387        let res = U128::from_str_radix_vartime(dec, 10).expect("error decoding");
1388        assert_eq!(res, U128::MAX);
1389    }
1390
1391    #[cfg(feature = "alloc")]
1392    #[test]
1393    fn from_str_radix_16() {
1394        let hex = "fedcba9876543210fedcba9876543210";
1395        let res = U128::from_str_radix_vartime(hex, 16).expect("error decoding");
1396        assert_eq!(hex, format!("{res:x}"));
1397    }
1398
1399    #[cfg(feature = "alloc")]
1400    #[test]
1401    fn encode_radix_8() {
1402        assert_eq!(
1403            &radix_encode_limbs_to_string(8, U128::MAX.as_limbs()),
1404            "3777777777777777777777777777777777777777777"
1405        );
1406        assert_eq!(&radix_encode_limbs_to_string(8, U128::ZERO.as_limbs()), "0");
1407        assert_eq!(&radix_encode_limbs_to_string(8, U128::ONE.as_limbs()), "1");
1408
1409        let hex = "1234567123456765432107654321";
1410        let res = U128::from_str_radix_vartime(hex, 8).expect("error decoding");
1411        let out = radix_encode_limbs_to_string(8, res.as_limbs());
1412        assert_eq!(&out, hex);
1413    }
1414
1415    #[cfg(feature = "alloc")]
1416    #[test]
1417    fn encode_radix_10() {
1418        assert_eq!(
1419            &radix_encode_limbs_to_string(10, U128::MAX.as_limbs()),
1420            "340282366920938463463374607431768211455"
1421        );
1422        assert_eq!(
1423            &radix_encode_limbs_to_string(10, U128::ZERO.as_limbs()),
1424            "0"
1425        );
1426        assert_eq!(&radix_encode_limbs_to_string(10, U128::ONE.as_limbs()), "1");
1427    }
1428
1429    #[cfg(feature = "alloc")]
1430    #[test]
1431    fn encode_radix_16() {
1432        let hex = "fedcba9876543210fedcba9876543210";
1433        let res = U128::from_str_radix_vartime(hex, 16).expect("error decoding");
1434        let out = radix_encode_limbs_to_string(16, res.as_limbs());
1435        assert_eq!(&out, hex);
1436    }
1437
1438    #[cfg(all(feature = "rand_core", feature = "alloc"))]
1439    #[test]
1440    fn encode_radix_round_trip() {
1441        use crate::{Random, U256};
1442        use rand_core::SeedableRng;
1443        let mut rng = chacha20::ChaCha8Rng::seed_from_u64(1);
1444
1445        let rounds = if cfg!(miri) { 10 } else { 100 };
1446        for _ in 0..rounds {
1447            let uint = U256::random_from_rng(&mut rng);
1448            for radix in 2..=36 {
1449                let enc = uint.to_string_radix_vartime(radix);
1450                let res = U256::from_str_radix_vartime(&enc, radix).expect("decoding error");
1451                assert_eq!(
1452                    res, uint,
1453                    "round trip failure: radix {radix} encoded {uint} as {enc}"
1454                );
1455            }
1456        }
1457    }
1458
1459    cpubits::cpubits! {
1460        32 => {
1461            #[test]
1462            fn encode_be_hex() {
1463                let n = UintEx::from_be_hex("0011223344556677");
1464
1465                let bytes = n.to_be_bytes();
1466                assert_eq!(bytes.as_ref(), hex!("0011223344556677"));
1467
1468                #[cfg(feature = "der")]
1469                assert_eq!(super::der::count_der_be_bytes(&n.limbs), 7);
1470            }
1471        }
1472        64 => {
1473            #[test]
1474            fn encode_be_hex() {
1475                let n = UintEx::from_be_hex("00112233445566778899aabbccddeeff");
1476
1477                let bytes = n.to_be_bytes();
1478                assert_eq!(bytes.as_ref(), hex!("00112233445566778899aabbccddeeff"));
1479
1480                #[cfg(feature = "der")]
1481                assert_eq!(super::der::count_der_be_bytes(&n.limbs), 15);
1482            }
1483        }
1484    }
1485
1486    #[test]
1487    fn infer_sizes() {
1488        let bytes = b"0011223344556677";
1489
1490        let n = EncodedUint::from(bytes);
1491        assert_eq!(n.as_slice(), bytes);
1492
1493        let n = EncodedUint::from(*bytes);
1494        assert_eq!(n.as_slice(), bytes);
1495
1496        let n: [u8; 16] = EncodedUint::from(bytes).into();
1497        assert_eq!(n.as_slice(), bytes);
1498
1499        let n: [u8; 16] = (&EncodedUint::from(bytes)).into();
1500        assert_eq!(n.as_slice(), bytes);
1501    }
1502
1503    #[allow(clippy::cast_lossless)]
1504    #[allow(trivial_numeric_casts)]
1505    #[cfg(feature = "alloc")]
1506    #[test]
1507    fn test_radix_large_divisor() {
1508        let radix = 5u32;
1509        let digits_limb = Word::MAX.ilog(radix as Word);
1510        let div_limb = NonZero::new_unchecked(Limb((radix as Word).pow(digits_limb)));
1511        let (div_large, _digits_large, _shift_large) =
1512            radix_large_divisor::<4>(radix, div_limb, digits_limb as usize);
1513        assert!(
1514            Uint::new(div_large)
1515                .checked_mul(&Uint::<1>::from_u32(radix))
1516                .is_none()
1517                .to_bool()
1518        );
1519    }
1520}
crypto_bigint/uint/encoding.rs

crypto_bigint/uint/
encoding.rs
