bnum/buint/radix.rs
1/*
2Most of the code in this file is adapted from the Rust `num_bigint` library, https://docs.rs/num-bigint/latest/num_bigint/, modified under the MIT license. The changes are released under either the MIT license or the Apache License 2.0, as described in the README. See LICENSE-MIT or LICENSE-APACHE at the project root.
3
4The appropriate copyright notice for the `num_bigint` code is given below:
5Copyright (c) 2014 The Rust Project Developers
6
7The original license file and copyright notice for `num_bigint` can be found in this project's root at licenses/LICENSE-num-bigint.
8*/
9
10use crate::digit;
11use crate::doc;
12use crate::errors::ParseIntError;
13use crate::int::radix::assert_range;
14use crate::ExpType;
15use alloc::string::String;
16use alloc::vec::Vec;
17use core::iter::Iterator;
18use core::num::IntErrorKind;
19use core::str::FromStr;
20
21#[inline]
22const fn ilog2(a: u32) -> u8 {
23 31 - a.leading_zeros() as u8
24}
25
26#[inline]
27const fn div_ceil(a: ExpType, b: ExpType) -> ExpType {
28 if a % b == 0 {
29 a / b
30 } else {
31 (a / b) + 1
32 }
33}
34
35macro_rules! radix {
36 ($BUint: ident, $BInt: ident, $Digit: ident) => {
37 #[doc = doc::radix::impl_desc!($BUint)]
38 impl<const N: usize> $BUint<N> {
39 #[inline]
40 const fn radix_base(radix: u32) -> ($Digit, usize) {
41 let mut power: usize = 1;
42 let radix = radix as $Digit;
43 let mut base = radix;
44 loop {
45 match base.checked_mul(radix) {
46 Some(n) => {
47 base = n;
48 power += 1;
49 }
50 None => return (base, power),
51 }
52 }
53 }
54
55 #[inline]
56 const fn radix_base_half(radix: u32) -> ($Digit, usize) {
57 const HALF_BITS_MAX: $Digit = $Digit::MAX >> ($Digit::BITS / 2);
58
59 let mut power: usize = 1;
60 let radix = radix as $Digit;
61 let mut base = radix;
62 loop {
63 match base.checked_mul(radix) {
64 Some(n) if n <= HALF_BITS_MAX => {
65 base = n;
66 power += 1;
67 }
68 _ => return (base, power),
69 }
70 }
71 }
72
73 /// Converts a byte slice in a given base to an integer. The input slice must contain ascii/utf8 characters in [0-9a-zA-Z].
74 ///
75 /// This function is equivalent to the [`from_str_radix`](#method.from_str_radix) function for a string slice equivalent to the byte slice and the same radix.
76 ///
77 /// Returns `None` if the conversion of the byte slice to string slice fails or if a digit is larger than or equal to the given radix, otherwise the integer is wrapped in `Some`.
78 ///
79 /// # Panics
80 ///
81 /// This function panics if `radix` is not in the range from 2 to 36 inclusive.
82 ///
83 /// # Examples
84 ///
85 /// ```
86 /// use bnum::types::U512;
87 ///
88 /// let src = "394857hdgfjhsnkg947dgfjkeita";
89 /// assert_eq!(U512::from_str_radix(src, 32).ok(), U512::parse_bytes(src.as_bytes(), 32));
90 /// ```
91 #[inline]
92 pub const fn parse_bytes(buf: &[u8], radix: u32) -> Option<Self> {
93 let s = crate::nightly::option_try!(crate::nightly::ok!(core::str::from_utf8(buf)));
94 crate::nightly::ok!(Self::from_str_radix(s, radix))
95 }
96
97 /// Converts a slice of big-endian digits in the given radix to an integer. Each `u8` of the slice is interpreted as one digit of base `radix` of the number, so this function will return `None` if any digit is greater than or equal to `radix`, otherwise the integer is wrapped in `Some`.
98 ///
99 /// # Panics
100 ///
101 /// This function panics if `radix` is not in the range from 2 to 256 inclusive.
102 ///
103 /// # Examples
104 ///
105 /// ```
106 /// use bnum::types::U512;
107 ///
108 /// let n = U512::from(34598748526857897975u128);
109 /// let digits = n.to_radix_be(12);
110 /// assert_eq!(Some(n), U512::from_radix_be(&digits, 12));
111 /// ```
112 #[inline]
113 pub const fn from_radix_be(buf: &[u8], radix: u32) -> Option<Self> {
114 assert_range!(radix, 256);
115 if buf.is_empty() {
116 return Some(Self::ZERO);
117 }
118 if radix == 256 {
119 return Self::from_be_slice(buf);
120 }
121
122 crate::nightly::ok!(Self::from_buf_radix_internal::<false, true>(buf, radix, false))
123 }
124
125 /// Converts a slice of little-endian digits in the given radix to an integer. Each `u8` of the slice is interpreted as one digit of base `radix` of the number, so this function will return `None` if any digit is greater than or equal to `radix`, otherwise the integer is wrapped in `Some`.
126 ///
127 /// # Panics
128 ///
129 /// This function panics if `radix` is not in the range from 2 to 256 inclusive.
130 ///
131 /// # Examples
132 ///
133 /// ```
134 /// use bnum::types::U512;
135 ///
136 /// let n = U512::from(109837459878951038945798u128);
137 /// let digits = n.to_radix_le(15);
138 /// assert_eq!(Some(n), U512::from_radix_le(&digits, 15));
139 /// ```
140 #[inline]
141 pub const fn from_radix_le(buf: &[u8], radix: u32) -> Option<Self> {
142 assert_range!(radix, 256);
143 if buf.is_empty() {
144 return Some(Self::ZERO);
145 }
146 if radix == 256 {
147 return Self::from_le_slice(buf);
148 }
149
150 crate::nightly::ok!(Self::from_buf_radix_internal::<false, false>(buf, radix, false))
151 }
152
153 #[inline]
154 const fn byte_to_digit<const FROM_STR: bool>(byte: u8) -> u8 {
155 if FROM_STR {
156 match byte {
157 b'0'..=b'9' => byte - b'0',
158 b'a'..=b'z' => byte - b'a' + 10,
159 b'A'..=b'Z' => byte - b'A' + 10,
160 _ => u8::MAX,
161 }
162 } else {
163 byte
164 }
165 }
166
167 /// Converts a string slice in a given base to an integer.
168 ///
169 /// The string is expected to be an optional `+` sign followed by digits. Leading and trailing whitespace represent an error. Digits are a subset of these characters, depending on `radix`:
170 ///
171 /// - `0-9`
172 /// - `a-z`
173 /// - `A-Z`
174 ///
175 /// # Panics
176 ///
177 /// This function panics if `radix` is not in the range from 2 to 36 inclusive.
178 ///
179 /// # Examples
180 ///
181 /// ```
182 /// use bnum::types::U512;
183 ///
184 /// assert_eq!(U512::from_str_radix("A", 16), Ok(U512::from(10u128)));
185 /// ```
186 #[inline]
187 pub const fn from_str_radix(src: &str, radix: u32) -> Result<Self, ParseIntError> {
188 assert_range!(radix, 36);
189 if src.is_empty() {
190 return Err(ParseIntError {
191 kind: IntErrorKind::Empty,
192 });
193 }
194 let buf = src.as_bytes();
195 let leading_plus = buf[0] == b'+';
196 Self::from_buf_radix_internal::<true, true>(buf, radix, leading_plus)
197 }
198
199 #[doc = doc::radix::parse_str_radix!($BUint)]
200 #[inline]
201 pub const fn parse_str_radix(src: &str, radix: u32) -> Self {
202 match Self::from_str_radix(src, radix) {
203 Ok(n) => n,
204 Err(e) => panic!("{}", e.description()),
205 }
206 }
207
208 pub(crate) const fn from_buf_radix_internal<const FROM_STR: bool, const BE: bool>(buf: &[u8], radix: u32, leading_sign: bool) -> Result<Self, ParseIntError> {
209 if leading_sign && buf.len() == 1 {
210 return Err(ParseIntError {
211 kind: IntErrorKind::InvalidDigit,
212 });
213 }
214 let input_digits_len = if leading_sign {
215 buf.len() - 1
216 } else {
217 buf.len()
218 };
219
220 match radix {
221 2 | 4 | 16 | 256 => {
222 let mut out = Self::ZERO;
223 let base_digits_per_digit = (digit::$Digit::BITS_U8 / ilog2(radix)) as usize;
224 let full_digits = input_digits_len / base_digits_per_digit as usize;
225 let remaining_digits = input_digits_len % base_digits_per_digit as usize;
226 let radix_u8 = radix as u8;
227
228 if full_digits > N || full_digits == N && remaining_digits != 0 {
229 let mut i = if leading_sign { 1 } else { 0 };
230 while i < N * base_digits_per_digit + if leading_sign { 1 } else { 0 } {
231 if Self::byte_to_digit::<FROM_STR>(buf[i]) >= radix_u8 {
232 return Err(ParseIntError {
233 kind: IntErrorKind::InvalidDigit,
234 });
235 }
236 i += 1;
237 }
238 return Err(ParseIntError {
239 kind: IntErrorKind::PosOverflow,
240 });
241 }
242
243 let log2r = ilog2(radix);
244
245 let mut i = 0;
246 while i < full_digits {
247 let mut j = 0;
248 while j < base_digits_per_digit {
249 let idx = if BE {
250 buf.len() - 1 - (i * base_digits_per_digit + j)
251 } else {
252 i * base_digits_per_digit + j
253 };
254 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
255 if d >= radix_u8 {
256 return Err(ParseIntError {
257 kind: IntErrorKind::InvalidDigit,
258 });
259 }
260 out.digits[i] |= (d as $Digit) << (j * log2r as usize);
261 j += 1;
262 }
263 i += 1;
264 }
265 let mut j = 0;
266 while j < remaining_digits {
267 let idx = if BE {
268 buf.len() - 1 - (i * base_digits_per_digit + j)
269 } else {
270 i * base_digits_per_digit + j
271 };
272 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
273 if d >= radix_u8 {
274 return Err(ParseIntError {
275 kind: IntErrorKind::InvalidDigit,
276 });
277 }
278 out.digits[i] |= (d as $Digit) << (j * log2r as usize);
279 j += 1;
280 }
281 Ok(out)
282 },
283 /*8 | 32 | 64 | 128*/ 0 => { // TODO: for now, we don't use this, as hard to get the errors right
284 let mut out = Self::ZERO;
285 let radix_u8 = radix as u8;
286 let log2r = ilog2(radix);
287
288 let mut index = 0;
289 let mut shift = 0;
290
291 let mut i = buf.len();
292 let stop_index = if leading_sign { 1 } else { 0 };
293 while i > stop_index {
294 i -= 1;
295 let idx = if BE {
296 i
297 } else {
298 buf.len() - 1 - i
299 };
300 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
301 if d >= radix_u8 {
302 // panic!("noooooo");
303 return Err(ParseIntError {
304 kind: IntErrorKind::InvalidDigit,
305 });
306 }
307 out.digits[index] |= (d as $Digit) << shift;
308 shift += log2r;
309 if shift >= digit::$Digit::BITS_U8 {
310 shift -= digit::$Digit::BITS_U8;
311 let carry = (d as $Digit) >> (log2r - shift);
312 index += 1;
313 if index == N {
314 if carry != 0 {
315 return Err(ParseIntError {
316 kind: IntErrorKind::PosOverflow,
317 });
318 }
319 while i > stop_index {
320 i -= 1;
321 let idx = if BE {
322 i
323 } else {
324 buf.len() - 1 - i
325 };
326 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
327 if d != 0 {
328 return Err(ParseIntError {
329 kind: IntErrorKind::PosOverflow,
330 });
331 }
332 }
333 return Ok(out);
334 } else {
335 out.digits[index] = carry;
336 }
337 }
338 }
339 Ok(out)
340 },
341 _ => {
342 let (base, power) = Self::radix_base(radix);
343 let r = input_digits_len % power;
344 let split = if r == 0 { power } else { r };
345 let radix_u8 = radix as u8;
346 let mut out = Self::ZERO;
347 let mut first: $Digit = 0;
348 let mut i = if leading_sign {
349 1
350 } else {
351 0
352 };
353 while i < if leading_sign { split + 1 } else { split } {
354 let idx = if BE {
355 i
356 } else {
357 buf.len() - 1 - i
358 };
359 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
360 if d >= radix_u8 {
361 return Err(ParseIntError {
362 kind: IntErrorKind::InvalidDigit,
363 });
364 }
365 first = first * (radix as $Digit) + d as $Digit;
366 i += 1;
367 }
368 out.digits[0] = first;
369 let mut start = i;
370 while start < buf.len() {
371 let end = start + power;
372
373 let mut carry = 0;
374 let mut j = 0;
375 while j < N {
376 let (low, high) = digit::$Digit::carrying_mul(out.digits[j], base, carry, 0);
377 carry = high;
378 out.digits[j] = low;
379 j += 1;
380 }
381 if carry != 0 {
382 while start < buf.len() && start < end { // TODO: this isn't quite correct behaviour
383 let idx = if BE {
384 start
385 } else {
386 buf.len() - 1 - start
387 };
388 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
389 if d >= radix_u8 {
390 return Err(ParseIntError {
391 kind: IntErrorKind::InvalidDigit,
392 });
393 }
394 start += 1;
395 }
396 return Err(ParseIntError {
397 kind: IntErrorKind::PosOverflow,
398 });
399 }
400
401 let mut n = 0;
402 j = start;
403 while j < end && j < buf.len() {
404 let idx = if BE {
405 j
406 } else {
407 buf.len() - 1 - j
408 };
409 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
410 if d >= radix_u8 {
411 return Err(ParseIntError {
412 kind: IntErrorKind::InvalidDigit,
413 });
414 }
415 n = n * (radix as $Digit) + d as $Digit;
416 j += 1;
417 }
418
419 out = match out.checked_add(Self::from_digit(n)) {
420 Some(out) => out,
421 None => {
422 return Err(ParseIntError {
423 kind: IntErrorKind::PosOverflow,
424 })
425 }
426 };
427 start = end;
428 }
429 Ok(out)
430 }
431 }
432 }
433
434 /// Returns the integer as a string in the given radix.
435 ///
436 /// # Panics
437 ///
438 /// This function panics if `radix` is not in the range from 2 to 36 inclusive.
439 ///
440 /// # Examples
441 ///
442 /// ```
443 /// use bnum::types::U512;
444 ///
445 /// let src = "934857djkfghhkdfgbf9345hdfkh";
446 /// let n = U512::from_str_radix(src, 36).unwrap();
447 /// assert_eq!(n.to_str_radix(36), src);
448 /// ```
449 #[inline]
450 pub fn to_str_radix(&self, radix: u32) -> String {
451 let mut out = Self::to_radix_be(self, radix);
452
453 for byte in out.iter_mut() {
454 if *byte < 10 {
455 *byte += b'0';
456 } else {
457 *byte += b'a' - 10;
458 }
459 }
460 unsafe { String::from_utf8_unchecked(out) }
461 }
462
463 /// Returns the integer in the given base in big-endian digit order.
464 ///
465 /// # Panics
466 ///
467 /// This function panics if `radix` is not in the range from 2 to 256 inclusive.
468 ///
469 /// ```
470 /// use bnum::types::U512;
471 ///
472 /// let digits = &[3, 55, 60, 100, 5, 0, 5, 88];
473 /// let n = U512::from_radix_be(digits, 120).unwrap();
474 /// assert_eq!(n.to_radix_be(120), digits);
475 /// ```
476 #[inline]
477 pub fn to_radix_be(&self, radix: u32) -> Vec<u8> {
478 let mut v = self.to_radix_le(radix);
479 v.reverse();
480 v
481 }
482
483 /// Returns the integer in the given base in little-endian digit order.
484 ///
485 /// # Panics
486 ///
487 /// This function panics if `radix` is not in the range from 2 to 256 inclusive.
488 ///
489 /// ```
490 /// use bnum::types::U512;
491 ///
492 /// let digits = &[1, 67, 88, 200, 55, 68, 87, 120, 178];
493 /// let n = U512::from_radix_le(digits, 250).unwrap();
494 /// assert_eq!(n.to_radix_le(250), digits);
495 /// ```
496 pub fn to_radix_le(&self, radix: u32) -> Vec<u8> {
497 if self.is_zero() {
498 vec![0]
499 } else if radix.is_power_of_two() {
500 if $Digit::BITS == 8 && radix == 256 {
501 return (&self.digits[0..=self.last_digit_index()])
502 .into_iter()
503 .map(|d| *d as u8)
504 .collect(); // we can cast to `u8` here as the underlying digit must be a `u8` anyway
505 }
506
507 let bits = ilog2(radix);
508 if digit::$Digit::BITS_U8 % bits == 0 {
509 self.to_bitwise_digits_le(bits)
510 } else {
511 self.to_inexact_bitwise_digits_le(bits)
512 }
513 } else if radix == 10 {
514 self.to_radix_digits_le(10)
515 } else {
516 self.to_radix_digits_le(radix)
517 }
518 }
519
520 fn to_bitwise_digits_le(self, bits: u8) -> Vec<u8> {
521 let last_digit_index = self.last_digit_index();
522 let mask: $Digit = (1 << bits) - 1;
523 let digits_per_big_digit = digit::$Digit::BITS_U8 / bits;
524 let digits = div_ceil(self.bits(), bits as ExpType);
525 let mut out = Vec::with_capacity(digits as usize);
526
527 let mut r = self.digits[last_digit_index];
528
529 for mut d in IntoIterator::into_iter(self.digits).take(last_digit_index) {
530 for _ in 0..digits_per_big_digit {
531 out.push((d & mask) as u8);
532 d >>= bits;
533 }
534 }
535 while r != 0 {
536 out.push((r & mask) as u8);
537 r >>= bits;
538 }
539 out
540 }
541
542 fn to_inexact_bitwise_digits_le(self, bits: u8) -> Vec<u8> {
543 let mask: $Digit = (1 << bits) - 1;
544 let digits = div_ceil(self.bits(), bits as ExpType);
545 let mut out = Vec::with_capacity(digits as usize);
546 let mut r = 0;
547 let mut rbits = 0;
548 for c in self.digits {
549 r |= c << rbits;
550 rbits += digit::$Digit::BITS_U8;
551
552 while rbits >= bits {
553 out.push((r & mask) as u8);
554 r >>= bits;
555
556 if rbits > digit::$Digit::BITS_U8 {
557 r = c >> (digit::$Digit::BITS_U8 - (rbits - bits));
558 }
559 rbits -= bits;
560 }
561 }
562 if rbits != 0 {
563 out.push(r as u8);
564 }
565 while let Some(&0) = out.last() {
566 out.pop();
567 }
568 out
569 }
570
571 fn to_radix_digits_le(self, radix: u32) -> Vec<u8> {
572 let radix_digits = div_ceil(self.bits(), ilog2(radix) as ExpType);
573 let mut out = Vec::with_capacity(radix_digits as usize);
574 let (base, power) = Self::radix_base_half(radix);
575 let radix = radix as $Digit;
576 let mut copy = self;
577 while copy.last_digit_index() > 0 {
578 let (q, mut r) = copy.div_rem_digit(base);
579 for _ in 0..power {
580 out.push((r % radix) as u8);
581 r /= radix;
582 }
583 copy = q;
584 }
585 let mut r = copy.digits[0];
586 while r != 0 {
587 out.push((r % radix) as u8);
588 r /= radix;
589 }
590 out
591 }
592 }
593
594 impl<const N: usize> FromStr for $BUint<N> {
595 type Err = ParseIntError;
596
597 fn from_str(src: &str) -> Result<Self, Self::Err> {
598 Self::from_str_radix(src, 10)
599 }
600 }
601 };
602}
603
604#[cfg(test)]
605crate::test::all_digit_tests! {
606 use crate::test::{quickcheck_from_to_radix, test_bignum, self};
607 use crate::BUint;
608 use core::str::FromStr;
609 use crate::test::types::utest;
610
611
612 test_bignum! {
613 function: <utest>::from_str,
614 cases: [
615 ("398475394875230495745"),
616 ("3984753948752304957423490785029749572977970985"),
617 ("12345💩👍"),
618 ("1234567890a"),
619 ("")
620 ]
621 }
622
623 #[cfg(not(test_int_bits = "16"))]
624 test_bignum! {
625 function: <utest>::from_str_radix,
626 cases: [
627 ("+af7345asdofiuweor", 35u32),
628 ("+945hhdgi73945hjdfj", 32u32),
629 ("+3436847561345343455", 9u32),
630 ("+affe758457bc345540ac399", 16u32),
631 ("+affe758457bc345540ac39929334534ee34579234795", 17u32),
632 ("+3777777777777777777777777777777777777777777", 8u32),
633 ("+37777777777777777777777777777777777777777761", 8u32),
634 ("+1777777777777777777777", 8u32),
635 ("+17777777777777777777773", 8u32),
636 ("+2000000000000000000000", 8u32),
637 ("-234598734", 10u32),
638 ("g234ab", 16u32),
639 ("234£$2234", 15u32),
640 ("123456💯", 30u32),
641 ("3434💯34593487", 12u32),
642 ("💯34593487", 11u32),
643 ("12345678", 8u32),
644 ("abcdefw", 32u32),
645 ("1234ab", 11u32),
646 ("1234", 4u32),
647 ("010120101", 2u32),
648 ("10000000000000000", 16u32),
649 ("p8hrbe0mo0084i6vckj1tk7uvacnn4cm", 32u32),
650 ("", 10u32)
651 ]
652 }
653
654 quickcheck_from_to_radix!(utest, radix_be, 256);
655 quickcheck_from_to_radix!(utest, radix_le, 256);
656 quickcheck_from_to_radix!(utest, str_radix, 36);
657
658 #[test]
659 #[should_panic(expected = "attempt to parse integer from empty string")]
660 fn parse_str_radix_empty() {
661 let _ = UTEST::parse_str_radix("", 10);
662 }
663
664 #[test]
665 #[should_panic(expected = "attempt to parse integer from string containing invalid digit")]
666 fn parse_str_radix_invalid_char() {
667 let _ = UTEST::parse_str_radix("a", 10);
668 }
669
670 #[test]
671 fn parse_empty() {
672 assert_eq!(UTEST::from_radix_be(&[], 10), Some(UTEST::ZERO));
673 assert_eq!(UTEST::from_radix_le(&[], 10), Some(UTEST::ZERO));
674 }
675
676 test::quickcheck_from_str_radix!(utest, "+" | "");
677 test::quickcheck_from_str!(utest);
678
679 #[test]
680 fn parse_bytes() {
681 let src = "134957dkbhadoinegrhi983475hdgkhgdhiu3894hfd";
682 let u = BUint::<100>::parse_bytes(src.as_bytes(), 35).unwrap();
683 let v = BUint::<100>::from_str_radix(src, 35).unwrap();
684 assert_eq!(u, v);
685 assert_eq!(v.to_str_radix(35), src);
686
687 let bytes = b"345977fsuudf0350845";
688 let option = BUint::<100>::parse_bytes(bytes, 20);
689 assert!(option.is_none());
690 }
691}
692
693crate::macro_impl!(radix);