reweb3_num/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 reweb3_num::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 reweb3_num::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>(
123 buf, radix, false
124 ))
125 }
126
127 /// 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`.
128 ///
129 /// # Panics
130 ///
131 /// This function panics if `radix` is not in the range from 2 to 256 inclusive.
132 ///
133 /// # Examples
134 ///
135 /// ```
136 /// use reweb3_num::types::U512;
137 ///
138 /// let n = U512::from(109837459878951038945798u128);
139 /// let digits = n.to_radix_le(15);
140 /// assert_eq!(Some(n), U512::from_radix_le(&digits, 15));
141 /// ```
142 #[inline]
143 pub const fn from_radix_le(buf: &[u8], radix: u32) -> Option<Self> {
144 assert_range!(radix, 256);
145 if buf.is_empty() {
146 return Some(Self::ZERO);
147 }
148 if radix == 256 {
149 return Self::from_le_slice(buf);
150 }
151
152 crate::nightly::ok!(Self::from_buf_radix_internal::<false, false>(
153 buf, radix, false
154 ))
155 }
156
157 #[inline]
158 const fn byte_to_digit<const FROM_STR: bool>(byte: u8) -> u8 {
159 if FROM_STR {
160 match byte {
161 b'0'..=b'9' => byte - b'0',
162 b'a'..=b'z' => byte - b'a' + 10,
163 b'A'..=b'Z' => byte - b'A' + 10,
164 _ => u8::MAX,
165 }
166 } else {
167 byte
168 }
169 }
170
171 /// Converts a string slice in a given base to an integer.
172 ///
173 /// 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`:
174 ///
175 /// - `0-9`
176 /// - `a-z`
177 /// - `A-Z`
178 ///
179 /// # Panics
180 ///
181 /// This function panics if `radix` is not in the range from 2 to 36 inclusive.
182 ///
183 /// # Examples
184 ///
185 /// ```
186 /// use reweb3_num::types::U512;
187 ///
188 /// assert_eq!(U512::from_str_radix("A", 16), Ok(U512::from(10u128)));
189 /// ```
190 #[inline]
191 pub const fn from_str_radix(src: &str, radix: u32) -> Result<Self, ParseIntError> {
192 assert_range!(radix, 36);
193 if src.is_empty() {
194 return Err(ParseIntError {
195 kind: IntErrorKind::Empty,
196 });
197 }
198 let buf = src.as_bytes();
199 let leading_plus = buf[0] == b'+';
200 Self::from_buf_radix_internal::<true, true>(buf, radix, leading_plus)
201 }
202
203 #[doc = doc::radix::parse_str_radix!($BUint)]
204 #[inline]
205 pub const fn parse_str_radix(src: &str, radix: u32) -> Self {
206 match Self::from_str_radix(src, radix) {
207 Ok(n) => n,
208 Err(e) => panic!("{}", e.description()),
209 }
210 }
211
212 pub(crate) const fn from_buf_radix_internal<const FROM_STR: bool, const BE: bool>(
213 buf: &[u8],
214 radix: u32,
215 leading_sign: bool,
216 ) -> Result<Self, ParseIntError> {
217 if leading_sign && buf.len() == 1 {
218 return Err(ParseIntError {
219 kind: IntErrorKind::InvalidDigit,
220 });
221 }
222 let input_digits_len = if leading_sign {
223 buf.len() - 1
224 } else {
225 buf.len()
226 };
227
228 match radix {
229 2 | 4 | 16 | 256 => {
230 let mut out = Self::ZERO;
231 let base_digits_per_digit =
232 (digit::$Digit::BITS_U8 / ilog2(radix)) as usize;
233 let full_digits = input_digits_len / base_digits_per_digit as usize;
234 let remaining_digits = input_digits_len % base_digits_per_digit as usize;
235 if full_digits > N || full_digits == N && remaining_digits != 0 {
236 return Err(ParseIntError {
237 kind: IntErrorKind::PosOverflow,
238 });
239 }
240
241 let radix_u8 = radix as u8;
242 let log2r = ilog2(radix);
243
244 let mut i = 0;
245 while i < full_digits {
246 let mut j = 0;
247 while j < base_digits_per_digit {
248 let idx = if BE {
249 buf.len() - 1 - (i * base_digits_per_digit + j)
250 } else {
251 i * base_digits_per_digit + j
252 };
253 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
254 if d >= radix_u8 {
255 return Err(ParseIntError {
256 kind: IntErrorKind::InvalidDigit,
257 });
258 }
259 out.digits[i] |= (d as $Digit) << (j * log2r as usize);
260 j += 1;
261 }
262 i += 1;
263 }
264 let mut j = 0;
265 while j < remaining_digits {
266 let idx = if BE {
267 buf.len() - 1 - (i * base_digits_per_digit + j)
268 } else {
269 i * base_digits_per_digit + j
270 };
271 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
272 if d >= radix_u8 {
273 return Err(ParseIntError {
274 kind: IntErrorKind::InvalidDigit,
275 });
276 }
277 out.digits[i] |= (d as $Digit) << (j * log2r as usize);
278 j += 1;
279 }
280 Ok(out)
281 }
282 8 | 32 | 64 | 128 => {
283 let mut out = Self::ZERO;
284 let radix_u8 = radix as u8;
285 let log2r = ilog2(radix);
286
287 let mut index = 0;
288 let mut shift = 0;
289
290 let mut i = buf.len();
291 let stop_index = if leading_sign { 1 } else { 0 };
292 while i > stop_index {
293 i -= 1;
294 let idx = if BE { i } else { buf.len() - 1 - i };
295 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
296 if d >= radix_u8 {
297 return Err(ParseIntError {
298 kind: IntErrorKind::InvalidDigit,
299 });
300 }
301 out.digits[index] |= (d as $Digit) << shift;
302 shift += log2r;
303 if shift >= digit::$Digit::BITS_U8 {
304 shift -= digit::$Digit::BITS_U8;
305 let carry = (d as $Digit) >> (log2r - shift);
306 index += 1;
307 if index == N {
308 if carry != 0 {
309 return Err(ParseIntError {
310 kind: IntErrorKind::PosOverflow,
311 });
312 }
313 while i > stop_index {
314 i -= 1;
315 let idx = if BE { i } else { buf.len() - 1 - i };
316 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
317 if d != 0 {
318 return Err(ParseIntError {
319 kind: IntErrorKind::PosOverflow,
320 });
321 }
322 }
323 return Ok(out);
324 } else {
325 out.digits[index] = carry;
326 }
327 }
328 }
329 Ok(out)
330 }
331 _ => {
332 let (base, power) = Self::radix_base(radix);
333 let r = input_digits_len % power;
334 let split = if r == 0 { power } else { r };
335 let radix_u8 = radix as u8;
336 let mut out = Self::ZERO;
337 let mut first: $Digit = 0;
338 let mut i = if leading_sign { 1 } else { 0 };
339 while i < if leading_sign { split + 1 } else { split } {
340 let idx = if BE { i } else { buf.len() - 1 - i };
341 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
342 if d >= radix_u8 {
343 return Err(ParseIntError {
344 kind: IntErrorKind::InvalidDigit,
345 });
346 }
347 first = first * (radix as $Digit) + d as $Digit;
348 i += 1;
349 }
350 out.digits[0] = first;
351 let mut start = i;
352 while start < buf.len() {
353 let end = start + power;
354
355 let mut carry = 0;
356 let mut j = 0;
357 while j < N {
358 let (low, high) =
359 digit::$Digit::carrying_mul(out.digits[j], base, carry, 0);
360 carry = high;
361 out.digits[j] = low;
362 j += 1;
363 }
364 if carry != 0 {
365 return Err(ParseIntError {
366 kind: IntErrorKind::PosOverflow,
367 });
368 }
369
370 let mut n = 0;
371 j = start;
372 while j < end && j < buf.len() {
373 let idx = if BE { j } else { buf.len() - 1 - j };
374 let d = Self::byte_to_digit::<FROM_STR>(buf[idx]);
375 if d >= radix_u8 {
376 return Err(ParseIntError {
377 kind: IntErrorKind::InvalidDigit,
378 });
379 }
380 n = n * (radix as $Digit) + d as $Digit;
381 j += 1;
382 }
383
384 out = match out.checked_add(Self::from_digit(n)) {
385 Some(out) => out,
386 None => {
387 return Err(ParseIntError {
388 kind: IntErrorKind::PosOverflow,
389 })
390 }
391 };
392 start = end;
393 }
394 Ok(out)
395 }
396 }
397 }
398
399 /// Returns the integer as a string in the given radix.
400 ///
401 /// # Panics
402 ///
403 /// This function panics if `radix` is not in the range from 2 to 36 inclusive.
404 ///
405 /// # Examples
406 ///
407 /// ```
408 /// use reweb3_num::types::U512;
409 ///
410 /// let src = "934857djkfghhkdfgbf9345hdfkh";
411 /// let n = U512::from_str_radix(src, 36).unwrap();
412 /// assert_eq!(n.to_str_radix(36), src);
413 /// ```
414 #[inline]
415 pub fn to_str_radix(&self, radix: u32) -> String {
416 let mut out = Self::to_radix_be(self, radix);
417
418 for byte in out.iter_mut() {
419 if *byte < 10 {
420 *byte += b'0';
421 } else {
422 *byte += b'a' - 10;
423 }
424 }
425 unsafe { String::from_utf8_unchecked(out) }
426 }
427
428 /// Returns the integer in the given base in big-endian digit order.
429 ///
430 /// # Panics
431 ///
432 /// This function panics if `radix` is not in the range from 2 to 256 inclusive.
433 ///
434 /// ```
435 /// use reweb3_num::types::U512;
436 ///
437 /// let digits = &[3, 55, 60, 100, 5, 0, 5, 88];
438 /// let n = U512::from_radix_be(digits, 120).unwrap();
439 /// assert_eq!(n.to_radix_be(120), digits);
440 /// ```
441 #[inline]
442 pub fn to_radix_be(&self, radix: u32) -> Vec<u8> {
443 let mut v = self.to_radix_le(radix);
444 v.reverse();
445 v
446 }
447
448 /// Returns the integer in the given base in little-endian digit order.
449 ///
450 /// # Panics
451 ///
452 /// This function panics if `radix` is not in the range from 2 to 256 inclusive.
453 ///
454 /// ```
455 /// use reweb3_num::types::U512;
456 ///
457 /// let digits = &[1, 67, 88, 200, 55, 68, 87, 120, 178];
458 /// let n = U512::from_radix_le(digits, 250).unwrap();
459 /// assert_eq!(n.to_radix_le(250), digits);
460 /// ```
461 pub fn to_radix_le(&self, radix: u32) -> Vec<u8> {
462 if self.is_zero() {
463 vec![0]
464 } else if radix.is_power_of_two() {
465 if $Digit::BITS == 8 && radix == 256 {
466 return (&self.digits[0..=self.last_digit_index()])
467 .into_iter()
468 .map(|d| *d as u8)
469 .collect(); // we can cast to `u8` here as the underlying digit must be a `u8` anyway
470 }
471
472 let bits = ilog2(radix);
473 if digit::$Digit::BITS_U8 % bits == 0 {
474 self.to_bitwise_digits_le(bits)
475 } else {
476 self.to_inexact_bitwise_digits_le(bits)
477 }
478 } else if radix == 10 {
479 self.to_radix_digits_le(10)
480 } else {
481 self.to_radix_digits_le(radix)
482 }
483 }
484
485 fn to_bitwise_digits_le(self, bits: u8) -> Vec<u8> {
486 let last_digit_index = self.last_digit_index();
487 let mask: $Digit = (1 << bits) - 1;
488 let digits_per_big_digit = digit::$Digit::BITS_U8 / bits;
489 let digits = div_ceil(self.bits(), bits as ExpType);
490 let mut out = Vec::with_capacity(digits as usize);
491
492 let mut r = self.digits[last_digit_index];
493
494 for mut d in IntoIterator::into_iter(self.digits).take(last_digit_index) {
495 for _ in 0..digits_per_big_digit {
496 out.push((d & mask) as u8);
497 d >>= bits;
498 }
499 }
500 while r != 0 {
501 out.push((r & mask) as u8);
502 r >>= bits;
503 }
504 out
505 }
506
507 fn to_inexact_bitwise_digits_le(self, bits: u8) -> Vec<u8> {
508 let mask: $Digit = (1 << bits) - 1;
509 let digits = div_ceil(self.bits(), bits as ExpType);
510 let mut out = Vec::with_capacity(digits as usize);
511 let mut r = 0;
512 let mut rbits = 0;
513 for c in self.digits {
514 r |= c << rbits;
515 rbits += digit::$Digit::BITS_U8;
516
517 while rbits >= bits {
518 out.push((r & mask) as u8);
519 r >>= bits;
520
521 if rbits > digit::$Digit::BITS_U8 {
522 r = c >> (digit::$Digit::BITS_U8 - (rbits - bits));
523 }
524 rbits -= bits;
525 }
526 }
527 if rbits != 0 {
528 out.push(r as u8);
529 }
530 while let Some(&0) = out.last() {
531 out.pop();
532 }
533 out
534 }
535
536 fn to_radix_digits_le(self, radix: u32) -> Vec<u8> {
537 let radix_digits = div_ceil(self.bits(), ilog2(radix) as ExpType);
538 let mut out = Vec::with_capacity(radix_digits as usize);
539 let (base, power) = Self::radix_base_half(radix);
540 let radix = radix as $Digit;
541 let mut copy = self;
542 while copy.last_digit_index() > 0 {
543 let (q, mut r) = copy.div_rem_digit(base);
544 for _ in 0..power {
545 out.push((r % radix) as u8);
546 r /= radix;
547 }
548 copy = q;
549 }
550 let mut r = copy.digits[0];
551 while r != 0 {
552 out.push((r % radix) as u8);
553 r /= radix;
554 }
555 out
556 }
557 }
558
559 impl<const N: usize> FromStr for $BUint<N> {
560 type Err = ParseIntError;
561
562 fn from_str(src: &str) -> Result<Self, Self::Err> {
563 Self::from_str_radix(src, 10)
564 }
565 }
566 };
567}
568
569crate::macro_impl!(radix);