deser_core/ext/
bigint.rs

1use alloc::string::ToString;
2use alloc::vec::Vec;
3use core::cmp::Ordering;
4use core::fmt;
5use core::str::FromStr;
6
7use crate::error::Error;
8use crate::event::Atom;
9use crate::ext::Extension;
10use crate::ext::known::{WellKnown, impl_well_known, invalid};
11
12/// An integer of arbitrary size.
13///
14/// This is a well-known extension type (see [`ext`](crate::ext)) for
15/// integers that do not fit into 128 bits.  It holds the sign and the
16/// magnitude as big-endian bytes.  Leading zero bytes are permitted, zero is
17/// never negative.
18///
19/// The fallback is the decimal representation as string.  Integers that
20/// fit into 64 or 128 bits are not represented as [`BigInt`]: they are
21/// passed through deser as `U64`, `I64`, `u128` or `i128` instead.  That is
22/// what the `num-bigint` support does.  When deserializing, all of these as
23/// well as strings are accepted.
24///
25/// ```
26/// use deser::ext::BigInt;
27///
28/// let value: BigInt =
29///     "-340282366920938463463374607431768211456".parse().unwrap();
30/// assert!(value.negative);
31/// assert_eq!(
32///     value.magnitude,
33///     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
34/// );
35/// assert_eq!(value.to_string(), "-340282366920938463463374607431768211456");
36/// ```
37///
38/// Values are compared and hashed by their numeric value.
39#[derive(Clone, Default)]
40pub struct BigInt {
41    /// `true` if the integer is negative.
42    pub negative: bool,
43    /// The magnitude as big-endian bytes.
44    pub magnitude: Vec<u8>,
45}
46
47impl BigInt {
48    /// Returns the magnitude without leading zero bytes.
49    pub fn significant_magnitude(&self) -> &[u8] {
50        let skip = self.magnitude.iter().take_while(|&&x| x == 0).count();
51        &self.magnitude[skip..]
52    }
53
54    /// Returns `true` if the value is zero.
55    pub fn is_zero(&self) -> bool {
56        self.significant_magnitude().is_empty()
57    }
58
59    /// Returns `true` if the value is negative (and not zero).
60    pub fn is_negative(&self) -> bool {
61        self.negative && !self.is_zero()
62    }
63
64    /// Returns the magnitude as `u128` if it fits.
65    fn magnitude_u128(&self) -> Option<u128> {
66        let significant = self.significant_magnitude();
67        if significant.len() > 16 {
68            return None;
69        }
70        let mut buf = [0u8; 16];
71        buf[16 - significant.len()..].copy_from_slice(significant);
72        Some(u128::from_be_bytes(buf))
73    }
74
75    /// Returns the value as `u128` if it fits.
76    pub fn to_u128(&self) -> Option<u128> {
77        if self.is_negative() {
78            None
79        } else {
80            self.magnitude_u128()
81        }
82    }
83
84    /// Returns the value as `i128` if it fits.
85    pub fn to_i128(&self) -> Option<i128> {
86        let magnitude = self.magnitude_u128()?;
87        if self.is_negative() {
88            0i128.checked_sub_unsigned(magnitude)
89        } else {
90            i128::try_from(magnitude).ok()
91        }
92    }
93
94    /// Converts the value into the smallest atom that can hold it.
95    ///
96    /// This is `U64` or `I64` if the value fits into 64 bits, an `u128` or
97    /// `i128` extension value if it fits into 128 bits and a [`BigInt`]
98    /// extension value otherwise.
99    pub fn into_atom(self) -> Atom<'static> {
100        use crate::ext::ExtValue;
101        if let Some(value) = self.to_u128() {
102            match u64::try_from(value) {
103                Ok(value) => Atom::U64(value),
104                Err(_) => Atom::Ext(ExtValue::owned(value)),
105            }
106        } else if let Some(value) = self.to_i128() {
107            match i64::try_from(value) {
108                Ok(value) => Atom::I64(value),
109                Err(_) => Atom::Ext(ExtValue::owned(value)),
110            }
111        } else {
112            Atom::Ext(ExtValue::owned(self))
113        }
114    }
115}
116
117impl PartialEq for BigInt {
118    fn eq(&self, other: &BigInt) -> bool {
119        self.is_negative() == other.is_negative()
120            && self.significant_magnitude() == other.significant_magnitude()
121    }
122}
123
124impl Eq for BigInt {}
125
126impl core::hash::Hash for BigInt {
127    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
128        self.is_negative().hash(state);
129        self.significant_magnitude().hash(state);
130    }
131}
132
133impl PartialOrd for BigInt {
134    fn partial_cmp(&self, other: &BigInt) -> Option<Ordering> {
135        Some(self.cmp(other))
136    }
137}
138
139impl Ord for BigInt {
140    fn cmp(&self, other: &BigInt) -> Ordering {
141        let (a, b) = (self.significant_magnitude(), other.significant_magnitude());
142        let magnitude = a.len().cmp(&b.len()).then_with(|| a.cmp(b));
143        match (self.is_negative(), other.is_negative()) {
144            (false, false) => magnitude,
145            (true, true) => magnitude.reverse(),
146            (false, true) => Ordering::Greater,
147            (true, false) => Ordering::Less,
148        }
149    }
150}
151
152impl From<i128> for BigInt {
153    fn from(value: i128) -> BigInt {
154        let mut rv = BigInt::from(value.unsigned_abs());
155        rv.negative = value < 0;
156        rv
157    }
158}
159
160impl From<u128> for BigInt {
161    fn from(value: u128) -> BigInt {
162        let bytes = value.to_be_bytes();
163        let skip = (value.leading_zeros() / 8) as usize;
164        BigInt {
165            negative: false,
166            magnitude: bytes[skip..].to_vec(),
167        }
168    }
169}
170
171impl From<i64> for BigInt {
172    fn from(value: i64) -> BigInt {
173        BigInt::from(i128::from(value))
174    }
175}
176
177impl From<u64> for BigInt {
178    fn from(value: u64) -> BigInt {
179        BigInt::from(u128::from(value))
180    }
181}
182
183impl fmt::Display for BigInt {
184    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
185        // repeatedly divide by 10^9 and collect the remainders
186        let mut value = self.significant_magnitude().to_vec();
187        let mut chunks = Vec::new();
188        while !value.is_empty() {
189            let mut remainder = 0u64;
190            for byte in value.iter_mut() {
191                let current = remainder << 8 | u64::from(*byte);
192                *byte = (current / 1_000_000_000) as u8;
193                remainder = current % 1_000_000_000;
194            }
195            chunks.push(remainder as u32);
196            let skip = value.iter().take_while(|&&x| x == 0).count();
197            value.drain(..skip);
198        }
199        if self.is_negative() {
200            f.write_str("-")?;
201        }
202        match chunks.pop() {
203            None => f.write_str("0"),
204            Some(first) => {
205                write!(f, "{}", first)?;
206                for chunk in chunks.iter().rev() {
207                    write!(f, "{:09}", chunk)?;
208                }
209                Ok(())
210            }
211        }
212    }
213}
214
215impl fmt::Debug for BigInt {
216    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
217        write!(f, "BigInt({})", self)
218    }
219}
220
221impl FromStr for BigInt {
222    type Err = Error;
223
224    /// Parses a decimal integer with an optional sign.
225    fn from_str(s: &str) -> Result<BigInt, Error> {
226        let (negative, digits) = match s.as_bytes().first() {
227            Some(b'-') => (true, &s[1..]),
228            Some(b'+') => (false, &s[1..]),
229            _ => (false, s),
230        };
231        if digits.is_empty() || !digits.bytes().all(|x| x.is_ascii_digit()) {
232            return Err(invalid("invalid integer"));
233        }
234        // multiply by 10^9 and add, working on chunks of nine digits
235        let mut magnitude: Vec<u8> = Vec::new();
236        let first = digits.len() % 9;
237        let chunks = (first != 0).then(|| &digits[..first]).into_iter().chain(
238            digits.as_bytes()[first..].chunks(9).map(|x| {
239                // the digits are ASCII
240                core::str::from_utf8(x).unwrap()
241            }),
242        );
243        for chunk in chunks {
244            let factor = 10u64.pow(chunk.len() as u32);
245            let mut carry: u64 = chunk.parse().unwrap();
246            for byte in magnitude.iter_mut().rev() {
247                let current = u64::from(*byte) * factor + carry;
248                *byte = current as u8;
249                carry = current >> 8;
250            }
251            while carry != 0 {
252                magnitude.insert(0, carry as u8);
253                carry >>= 8;
254            }
255        }
256        let rv = BigInt {
257            negative,
258            magnitude,
259        };
260        Ok(BigInt {
261            negative: rv.is_negative(),
262            ..rv
263        })
264    }
265}
266
267impl Extension for BigInt {
268    fn name(&self) -> &str {
269        "big integer"
270    }
271
272    fn fallback(&self) -> Atom<'_> {
273        Atom::Str(self.to_string().into())
274    }
275}
276
277impl WellKnown for BigInt {
278    const EXPECTING: &'static str = "integer";
279
280    /// Accepts integers of all sizes and strings.
281    fn from_atom(atom: &Atom) -> Result<Option<BigInt>, Error> {
282        Ok(Some(match *atom {
283            Atom::Ext(ref ext) => {
284                if let Some(value) = ext.downcast_ref::<BigInt>() {
285                    value.clone()
286                } else if let Some(&value) = ext.downcast_ref::<u128>() {
287                    BigInt::from(value)
288                } else if let Some(&value) = ext.downcast_ref::<i128>() {
289                    BigInt::from(value)
290                } else if let Some(value) = ext
291                    .downcast_value_ref::<crate::ext::Number>()
292                    .filter(|x| x.is_integer())
293                {
294                    // integer literals that do not fit into 128 bits
295                    value.as_str().parse()?
296                } else {
297                    return Ok(None);
298                }
299            }
300            Atom::U64(value) => BigInt::from(value),
301            Atom::I64(value) => BigInt::from(value),
302            Atom::Str(ref value) => value.parse()?,
303            _ => return Ok(None),
304        }))
305    }
306}
307
308impl_well_known!(BigInt);
309
310#[test]
311fn test_bigint() {
312    for s in [
313        "0",
314        "1",
315        "-1",
316        "255",
317        "256",
318        "999999999",
319        "1000000000",
320        "-18446744073709551616",
321        "340282366920938463463374607431768211456",
322        "-123456789012345678901234567890123456789012345678901234567890",
323    ] {
324        let value: BigInt = s.parse().unwrap();
325        assert_eq!(value.to_string(), s);
326    }
327    assert_eq!("-0".parse::<BigInt>().unwrap().to_string(), "0");
328    assert_eq!("+007".parse::<BigInt>().unwrap().to_string(), "7");
329    assert_eq!(BigInt::from(i128::MIN).to_i128(), Some(i128::MIN));
330    assert_eq!(BigInt::from(u128::MAX).to_u128(), Some(u128::MAX));
331    assert_eq!(BigInt::from(u128::MAX).to_i128(), None);
332    assert_eq!(BigInt::from(-1i64).to_u128(), None);
333    assert_eq!(BigInt::from(-1i64).into_atom(), Atom::I64(-1));
334    for invalid in ["", "-", "1.0", "1e5", " 1", "0x10"] {
335        assert!(invalid.parse::<BigInt>().is_err());
336    }
337    let n = |s: &str| s.parse::<BigInt>().unwrap();
338    assert_eq!(
339        BigInt {
340            negative: true,
341            magnitude: vec![0, 0]
342        },
343        n("0")
344    );
345    assert_eq!(
346        BigInt {
347            negative: false,
348            magnitude: vec![0, 1]
349        },
350        n("1")
351    );
352    let mut values = vec![n("256"), n("-1"), n("0"), n("-256"), n("255"), n("1")];
353    values.sort();
354    assert_eq!(
355        values,
356        [n("-256"), n("-1"), n("0"), n("1"), n("255"), n("256")]
357    );
358}
deser_core/ext/bigint.rs

deser_core/ext/
bigint.rs
