1// This uses stdlib features higher than the MSRV
2#![allow(clippy::manual_range_contains)] // 1.35
3
4use super::{biguint_from_vec, BigUint, ToBigUint};
5
6use super::addition::add2;
7use super::division::{div_rem_digit, FAST_DIV_WIDE};
8use super::multiplication::mac_with_carry;
9
10use crate::big_digit::{self, BigDigit};
11use crate::ParseBigIntError;
12use crate::TryFromBigIntError;
13
14use alloc::vec::Vec;
15use core::cmp::Ordering::{Equal, Greater, Less};
16use core::convert::TryFrom;
17use core::mem;
18use core::str::FromStr;
19use num_integer::{Integer, Roots};
20use num_traits::float::FloatCore;
21use num_traits::{FromPrimitive, Num, One, PrimInt, ToPrimitive, Zero};
22
23/// Find last set bit
24/// fls(0) == 0, fls(u32::MAX) == 32
25fn fls<T: PrimInt>(v: T) -> u8 {
26 mem::size_of::<T>() as u8 * 8 - v.leading_zeros() as u8
27}
28
29fn ilog2<T: PrimInt>(v: T) -> u8 {
30 fls(v) - 1
31}
32
33impl FromStr for BigUint {
34 type Err = ParseBigIntError;
35
36 #[inline]
37 fn from_str(s: &str) -> Result<BigUint, ParseBigIntError> {
38 BigUint::from_str_radix(str:s, radix:10)
39 }
40}
41
42// Convert from a power of two radix (bits == ilog2(radix)) where bits evenly divides
43// BigDigit::BITS
44pub(super) fn from_bitwise_digits_le(v: &[u8], bits: u8) -> BigUint {
45 debug_assert!(!v.is_empty() && bits <= 8 && big_digit::BITS % bits == 0);
46 debug_assert!(v.iter().all(|&c| BigDigit::from(c) < (1 << bits)));
47
48 let digits_per_big_digit: u8 = big_digit::BITS / bits;
49
50 let data: Vec = vimpl Iterator
51 .chunks(chunk_size:digits_per_big_digit.into())
52 .map(|chunk: &[u8]| {
53 chunk
54 .iter()
55 .rev()
56 .fold(init:0, |acc: u64, &c: u8| (acc << bits) | BigDigit::from(c))
57 })
58 .collect();
59
60 biguint_from_vec(digits:data)
61}
62
63// Convert from a power of two radix (bits == ilog2(radix)) where bits doesn't evenly divide
64// BigDigit::BITS
65fn from_inexact_bitwise_digits_le(v: &[u8], bits: u8) -> BigUint {
66 debug_assert!(!v.is_empty() && bits <= 8 && big_digit::BITS % bits != 0);
67 debug_assert!(v.iter().all(|&c| BigDigit::from(c) < (1 << bits)));
68
69 let total_bits = (v.len() as u64).saturating_mul(bits.into());
70 let big_digits = Integer::div_ceil(&total_bits, &big_digit::BITS.into())
71 .to_usize()
72 .unwrap_or(usize::MAX);
73 let mut data = Vec::with_capacity(big_digits);
74
75 let mut d = 0;
76 let mut dbits = 0; // number of bits we currently have in d
77
78 // walk v accumululating bits in d; whenever we accumulate big_digit::BITS in d, spit out a
79 // big_digit:
80 for &c in v {
81 d |= BigDigit::from(c) << dbits;
82 dbits += bits;
83
84 if dbits >= big_digit::BITS {
85 data.push(d);
86 dbits -= big_digit::BITS;
87 // if dbits was > big_digit::BITS, we dropped some of the bits in c (they couldn't fit
88 // in d) - grab the bits we lost here:
89 d = BigDigit::from(c) >> (bits - dbits);
90 }
91 }
92
93 if dbits > 0 {
94 debug_assert!(dbits < big_digit::BITS);
95 data.push(d as BigDigit);
96 }
97
98 biguint_from_vec(data)
99}
100
101// Read little-endian radix digits
102fn from_radix_digits_be(v: &[u8], radix: u32) -> BigUint {
103 debug_assert!(!v.is_empty() && !radix.is_power_of_two());
104 debug_assert!(v.iter().all(|&c| u32::from(c) < radix));
105
106 // Estimate how big the result will be, so we can pre-allocate it.
107 #[cfg(feature = "std")]
108 let big_digits = {
109 let radix_log2 = f64::from(radix).log2();
110 let bits = radix_log2 * v.len() as f64;
111 (bits / big_digit::BITS as f64).ceil()
112 };
113 #[cfg(not(feature = "std"))]
114 let big_digits = {
115 let radix_log2 = ilog2(radix.next_power_of_two()) as usize;
116 let bits = radix_log2 * v.len();
117 (bits / big_digit::BITS as usize) + 1
118 };
119
120 let mut data = Vec::with_capacity(big_digits.to_usize().unwrap_or(0));
121
122 let (base, power) = get_radix_base(radix);
123 let radix = radix as BigDigit;
124
125 let r = v.len() % power;
126 let i = if r == 0 { power } else { r };
127 let (head, tail) = v.split_at(i);
128
129 let first = head
130 .iter()
131 .fold(0, |acc, &d| acc * radix + BigDigit::from(d));
132 data.push(first);
133
134 debug_assert!(tail.len() % power == 0);
135 for chunk in tail.chunks(power) {
136 if data.last() != Some(&0) {
137 data.push(0);
138 }
139
140 let mut carry = 0;
141 for d in data.iter_mut() {
142 *d = mac_with_carry(0, *d, base, &mut carry);
143 }
144 debug_assert!(carry == 0);
145
146 let n = chunk
147 .iter()
148 .fold(0, |acc, &d| acc * radix + BigDigit::from(d));
149 add2(&mut data, &[n]);
150 }
151
152 biguint_from_vec(data)
153}
154
155pub(super) fn from_radix_be(buf: &[u8], radix: u32) -> Option<BigUint> {
156 assert!(
157 2 <= radix && radix <= 256,
158 "The radix must be within 2...256"
159 );
160
161 if buf.is_empty() {
162 return Some(BigUint::ZERO);
163 }
164
165 if radix != 256 && buf.iter().any(|&b| b >= radix as u8) {
166 return None;
167 }
168
169 let res = if radix.is_power_of_two() {
170 // Powers of two can use bitwise masks and shifting instead of multiplication
171 let bits = ilog2(radix);
172 let mut v = Vec::from(buf);
173 v.reverse();
174 if big_digit::BITS % bits == 0 {
175 from_bitwise_digits_le(&v, bits)
176 } else {
177 from_inexact_bitwise_digits_le(&v, bits)
178 }
179 } else {
180 from_radix_digits_be(buf, radix)
181 };
182
183 Some(res)
184}
185
186pub(super) fn from_radix_le(buf: &[u8], radix: u32) -> Option<BigUint> {
187 assert!(
188 2 <= radix && radix <= 256,
189 "The radix must be within 2...256"
190 );
191
192 if buf.is_empty() {
193 return Some(BigUint::ZERO);
194 }
195
196 if radix != 256 && buf.iter().any(|&b| b >= radix as u8) {
197 return None;
198 }
199
200 let res = if radix.is_power_of_two() {
201 // Powers of two can use bitwise masks and shifting instead of multiplication
202 let bits = ilog2(radix);
203 if big_digit::BITS % bits == 0 {
204 from_bitwise_digits_le(buf, bits)
205 } else {
206 from_inexact_bitwise_digits_le(buf, bits)
207 }
208 } else {
209 let mut v = Vec::from(buf);
210 v.reverse();
211 from_radix_digits_be(&v, radix)
212 };
213
214 Some(res)
215}
216
217impl Num for BigUint {
218 type FromStrRadixErr = ParseBigIntError;
219
220 /// Creates and initializes a `BigUint`.
221 fn from_str_radix(s: &str, radix: u32) -> Result<BigUint, ParseBigIntError> {
222 assert!(2 <= radix && radix <= 36, "The radix must be within 2...36");
223 let mut s = s;
224 if let Some(tail) = s.strip_prefix('+') {
225 if !tail.starts_with('+') {
226 s = tail
227 }
228 }
229
230 if s.is_empty() {
231 return Err(ParseBigIntError::empty());
232 }
233
234 if s.starts_with('_') {
235 // Must lead with a real digit!
236 return Err(ParseBigIntError::invalid());
237 }
238
239 // First normalize all characters to plain digit values
240 let mut v = Vec::with_capacity(s.len());
241 for b in s.bytes() {
242 let d = match b {
243 b'0'..=b'9' => b - b'0',
244 b'a'..=b'z' => b - b'a' + 10,
245 b'A'..=b'Z' => b - b'A' + 10,
246 b'_' => continue,
247 _ => u8::MAX,
248 };
249 if d < radix as u8 {
250 v.push(d);
251 } else {
252 return Err(ParseBigIntError::invalid());
253 }
254 }
255
256 let res = if radix.is_power_of_two() {
257 // Powers of two can use bitwise masks and shifting instead of multiplication
258 let bits = ilog2(radix);
259 v.reverse();
260 if big_digit::BITS % bits == 0 {
261 from_bitwise_digits_le(&v, bits)
262 } else {
263 from_inexact_bitwise_digits_le(&v, bits)
264 }
265 } else {
266 from_radix_digits_be(&v, radix)
267 };
268 Ok(res)
269 }
270}
271
272fn high_bits_to_u64(v: &BigUint) -> u64 {
273 match v.data.len() {
274 0 => 0,
275 1 => {
276 // XXX Conversion is useless if already 64-bit.
277 #[allow(clippy::useless_conversion)]
278 let v0 = u64::from(v.data[0]);
279 v0
280 }
281 _ => {
282 let mut bits = v.bits();
283 let mut ret = 0u64;
284 let mut ret_bits = 0;
285
286 for d in v.data.iter().rev() {
287 let digit_bits = (bits - 1) % u64::from(big_digit::BITS) + 1;
288 let bits_want = Ord::min(64 - ret_bits, digit_bits);
289
290 if bits_want != 0 {
291 if bits_want != 64 {
292 ret <<= bits_want;
293 }
294 // XXX Conversion is useless if already 64-bit.
295 #[allow(clippy::useless_conversion)]
296 let d0 = u64::from(*d) >> (digit_bits - bits_want);
297 ret |= d0;
298 }
299
300 // Implement round-to-odd: If any lower bits are 1, set LSB to 1
301 // so that rounding again to floating point value using
302 // nearest-ties-to-even is correct.
303 //
304 // See: https://en.wikipedia.org/wiki/Rounding#Rounding_to_prepare_for_shorter_precision
305
306 if digit_bits - bits_want != 0 {
307 // XXX Conversion is useless if already 64-bit.
308 #[allow(clippy::useless_conversion)]
309 let masked = u64::from(*d) << (64 - (digit_bits - bits_want) as u32);
310 ret |= (masked != 0) as u64;
311 }
312
313 ret_bits += bits_want;
314 bits -= bits_want;
315 }
316
317 ret
318 }
319 }
320}
321
322impl ToPrimitive for BigUint {
323 #[inline]
324 fn to_i64(&self) -> Option<i64> {
325 self.to_u64().as_ref().and_then(u64::to_i64)
326 }
327
328 #[inline]
329 fn to_i128(&self) -> Option<i128> {
330 self.to_u128().as_ref().and_then(u128::to_i128)
331 }
332
333 #[allow(clippy::useless_conversion)]
334 #[inline]
335 fn to_u64(&self) -> Option<u64> {
336 let mut ret: u64 = 0;
337 let mut bits = 0;
338
339 for i in self.data.iter() {
340 if bits >= 64 {
341 return None;
342 }
343
344 // XXX Conversion is useless if already 64-bit.
345 ret += u64::from(*i) << bits;
346 bits += big_digit::BITS;
347 }
348
349 Some(ret)
350 }
351
352 #[inline]
353 fn to_u128(&self) -> Option<u128> {
354 let mut ret: u128 = 0;
355 let mut bits = 0;
356
357 for i in self.data.iter() {
358 if bits >= 128 {
359 return None;
360 }
361
362 ret |= u128::from(*i) << bits;
363 bits += big_digit::BITS;
364 }
365
366 Some(ret)
367 }
368
369 #[inline]
370 fn to_f32(&self) -> Option<f32> {
371 let mantissa = high_bits_to_u64(self);
372 let exponent = self.bits() - u64::from(fls(mantissa));
373
374 if exponent > f32::MAX_EXP as u64 {
375 Some(f32::INFINITY)
376 } else {
377 Some((mantissa as f32) * 2.0f32.powi(exponent as i32))
378 }
379 }
380
381 #[inline]
382 fn to_f64(&self) -> Option<f64> {
383 let mantissa = high_bits_to_u64(self);
384 let exponent = self.bits() - u64::from(fls(mantissa));
385
386 if exponent > f64::MAX_EXP as u64 {
387 Some(f64::INFINITY)
388 } else {
389 Some((mantissa as f64) * 2.0f64.powi(exponent as i32))
390 }
391 }
392}
393
394macro_rules! impl_try_from_biguint {
395 ($T:ty, $to_ty:path) => {
396 impl TryFrom<&BigUint> for $T {
397 type Error = TryFromBigIntError<()>;
398
399 #[inline]
400 fn try_from(value: &BigUint) -> Result<$T, TryFromBigIntError<()>> {
401 $to_ty(value).ok_or(TryFromBigIntError::new(()))
402 }
403 }
404
405 impl TryFrom<BigUint> for $T {
406 type Error = TryFromBigIntError<BigUint>;
407
408 #[inline]
409 fn try_from(value: BigUint) -> Result<$T, TryFromBigIntError<BigUint>> {
410 <$T>::try_from(&value).map_err(|_| TryFromBigIntError::new(value))
411 }
412 }
413 };
414}
415
416impl_try_from_biguint!(u8, ToPrimitive::to_u8);
417impl_try_from_biguint!(u16, ToPrimitive::to_u16);
418impl_try_from_biguint!(u32, ToPrimitive::to_u32);
419impl_try_from_biguint!(u64, ToPrimitive::to_u64);
420impl_try_from_biguint!(usize, ToPrimitive::to_usize);
421impl_try_from_biguint!(u128, ToPrimitive::to_u128);
422
423impl_try_from_biguint!(i8, ToPrimitive::to_i8);
424impl_try_from_biguint!(i16, ToPrimitive::to_i16);
425impl_try_from_biguint!(i32, ToPrimitive::to_i32);
426impl_try_from_biguint!(i64, ToPrimitive::to_i64);
427impl_try_from_biguint!(isize, ToPrimitive::to_isize);
428impl_try_from_biguint!(i128, ToPrimitive::to_i128);
429
430impl FromPrimitive for BigUint {
431 #[inline]
432 fn from_i64(n: i64) -> Option<BigUint> {
433 if n >= 0 {
434 Some(BigUint::from(n as u64))
435 } else {
436 None
437 }
438 }
439
440 #[inline]
441 fn from_i128(n: i128) -> Option<BigUint> {
442 if n >= 0 {
443 Some(BigUint::from(n as u128))
444 } else {
445 None
446 }
447 }
448
449 #[inline]
450 fn from_u64(n: u64) -> Option<BigUint> {
451 Some(BigUint::from(n))
452 }
453
454 #[inline]
455 fn from_u128(n: u128) -> Option<BigUint> {
456 Some(BigUint::from(n))
457 }
458
459 #[inline]
460 fn from_f64(mut n: f64) -> Option<BigUint> {
461 // handle NAN, INFINITY, NEG_INFINITY
462 if !n.is_finite() {
463 return None;
464 }
465
466 // match the rounding of casting from float to int
467 n = n.trunc();
468
469 // handle 0.x, -0.x
470 if n.is_zero() {
471 return Some(Self::ZERO);
472 }
473
474 let (mantissa, exponent, sign) = FloatCore::integer_decode(n);
475
476 if sign == -1 {
477 return None;
478 }
479
480 let mut ret = BigUint::from(mantissa);
481 match exponent.cmp(&0) {
482 Greater => ret <<= exponent as usize,
483 Equal => {}
484 Less => ret >>= (-exponent) as usize,
485 }
486 Some(ret)
487 }
488}
489
490impl From<u64> for BigUint {
491 #[inline]
492 fn from(mut n: u64) -> Self {
493 let mut ret: BigUint = Self::ZERO;
494
495 while n != 0 {
496 ret.data.push(n as BigDigit);
497 // don't overflow if BITS is 64:
498 n = (n >> 1) >> (big_digit::BITS - 1);
499 }
500
501 ret
502 }
503}
504
505impl From<u128> for BigUint {
506 #[inline]
507 fn from(mut n: u128) -> Self {
508 let mut ret: BigUint = Self::ZERO;
509
510 while n != 0 {
511 ret.data.push(n as BigDigit);
512 n >>= big_digit::BITS;
513 }
514
515 ret
516 }
517}
518
519macro_rules! impl_biguint_from_uint {
520 ($T:ty) => {
521 impl From<$T> for BigUint {
522 #[inline]
523 fn from(n: $T) -> Self {
524 BigUint::from(n as u64)
525 }
526 }
527 };
528}
529
530impl_biguint_from_uint!(u8);
531impl_biguint_from_uint!(u16);
532impl_biguint_from_uint!(u32);
533impl_biguint_from_uint!(usize);
534
535macro_rules! impl_biguint_try_from_int {
536 ($T:ty, $from_ty:path) => {
537 impl TryFrom<$T> for BigUint {
538 type Error = TryFromBigIntError<()>;
539
540 #[inline]
541 fn try_from(value: $T) -> Result<BigUint, TryFromBigIntError<()>> {
542 $from_ty(value).ok_or(TryFromBigIntError::new(()))
543 }
544 }
545 };
546}
547
548impl_biguint_try_from_int!(i8, FromPrimitive::from_i8);
549impl_biguint_try_from_int!(i16, FromPrimitive::from_i16);
550impl_biguint_try_from_int!(i32, FromPrimitive::from_i32);
551impl_biguint_try_from_int!(i64, FromPrimitive::from_i64);
552impl_biguint_try_from_int!(isize, FromPrimitive::from_isize);
553impl_biguint_try_from_int!(i128, FromPrimitive::from_i128);
554
555impl ToBigUint for BigUint {
556 #[inline]
557 fn to_biguint(&self) -> Option<BigUint> {
558 Some(self.clone())
559 }
560}
561
562macro_rules! impl_to_biguint {
563 ($T:ty, $from_ty:path) => {
564 impl ToBigUint for $T {
565 #[inline]
566 fn to_biguint(&self) -> Option<BigUint> {
567 $from_ty(*self)
568 }
569 }
570 };
571}
572
573impl_to_biguint!(isize, FromPrimitive::from_isize);
574impl_to_biguint!(i8, FromPrimitive::from_i8);
575impl_to_biguint!(i16, FromPrimitive::from_i16);
576impl_to_biguint!(i32, FromPrimitive::from_i32);
577impl_to_biguint!(i64, FromPrimitive::from_i64);
578impl_to_biguint!(i128, FromPrimitive::from_i128);
579
580impl_to_biguint!(usize, FromPrimitive::from_usize);
581impl_to_biguint!(u8, FromPrimitive::from_u8);
582impl_to_biguint!(u16, FromPrimitive::from_u16);
583impl_to_biguint!(u32, FromPrimitive::from_u32);
584impl_to_biguint!(u64, FromPrimitive::from_u64);
585impl_to_biguint!(u128, FromPrimitive::from_u128);
586
587impl_to_biguint!(f32, FromPrimitive::from_f32);
588impl_to_biguint!(f64, FromPrimitive::from_f64);
589
590impl From<bool> for BigUint {
591 fn from(x: bool) -> Self {
592 if x {
593 One::one()
594 } else {
595 Self::ZERO
596 }
597 }
598}
599
600// Extract bitwise digits that evenly divide BigDigit
601pub(super) fn to_bitwise_digits_le(u: &BigUint, bits: u8) -> Vec<u8> {
602 debug_assert!(!u.is_zero() && bits <= 8 && big_digit::BITS % bits == 0);
603
604 let last_i = u.data.len() - 1;
605 let mask: BigDigit = (1 << bits) - 1;
606 let digits_per_big_digit = big_digit::BITS / bits;
607 let digits = Integer::div_ceil(&u.bits(), &u64::from(bits))
608 .to_usize()
609 .unwrap_or(usize::MAX);
610 let mut res = Vec::with_capacity(digits);
611
612 for mut r in u.data[..last_i].iter().cloned() {
613 for _ in 0..digits_per_big_digit {
614 res.push((r & mask) as u8);
615 r >>= bits;
616 }
617 }
618
619 let mut r = u.data[last_i];
620 while r != 0 {
621 res.push((r & mask) as u8);
622 r >>= bits;
623 }
624
625 res
626}
627
628// Extract bitwise digits that don't evenly divide BigDigit
629fn to_inexact_bitwise_digits_le(u: &BigUint, bits: u8) -> Vec<u8> {
630 debug_assert!(!u.is_zero() && bits <= 8 && big_digit::BITS % bits != 0);
631
632 let mask: BigDigit = (1 << bits) - 1;
633 let digits = Integer::div_ceil(&u.bits(), &u64::from(bits))
634 .to_usize()
635 .unwrap_or(usize::MAX);
636 let mut res = Vec::with_capacity(digits);
637
638 let mut r = 0;
639 let mut rbits = 0;
640
641 for c in &u.data {
642 r |= *c << rbits;
643 rbits += big_digit::BITS;
644
645 while rbits >= bits {
646 res.push((r & mask) as u8);
647 r >>= bits;
648
649 // r had more bits than it could fit - grab the bits we lost
650 if rbits > big_digit::BITS {
651 r = *c >> (big_digit::BITS - (rbits - bits));
652 }
653
654 rbits -= bits;
655 }
656 }
657
658 if rbits != 0 {
659 res.push(r as u8);
660 }
661
662 while let Some(&0) = res.last() {
663 res.pop();
664 }
665
666 res
667}
668
669// Extract little-endian radix digits
670#[inline(always)] // forced inline to get const-prop for radix=10
671pub(super) fn to_radix_digits_le(u: &BigUint, radix: u32) -> Vec<u8> {
672 debug_assert!(!u.is_zero() && !radix.is_power_of_two());
673
674 #[cfg(feature = "std")]
675 let radix_digits = {
676 let radix_log2 = f64::from(radix).log2();
677 ((u.bits() as f64) / radix_log2).ceil()
678 };
679 #[cfg(not(feature = "std"))]
680 let radix_digits = {
681 let radix_log2 = ilog2(radix) as usize;
682 ((u.bits() as usize) / radix_log2) + 1
683 };
684
685 // Estimate how big the result will be, so we can pre-allocate it.
686 let mut res = Vec::with_capacity(radix_digits.to_usize().unwrap_or(0));
687
688 let mut digits = u.clone();
689
690 // X86 DIV can quickly divide by a full digit, otherwise we choose a divisor
691 // that's suitable for `div_half` to avoid slow `DoubleBigDigit` division.
692 let (base, power) = if FAST_DIV_WIDE {
693 get_radix_base(radix)
694 } else {
695 get_half_radix_base(radix)
696 };
697 let radix = radix as BigDigit;
698
699 // For very large numbers, the O(n²) loop of repeated `div_rem_digit` dominates the
700 // performance. We can mitigate this by dividing into chunks of a larger base first.
701 // The threshold for this was chosen by anecdotal performance measurements to
702 // approximate where this starts to make a noticeable difference.
703 if digits.data.len() >= 64 {
704 let mut big_base = BigUint::from(base);
705 let mut big_power = 1usize;
706
707 // Choose a target base length near √n.
708 let target_len = digits.data.len().sqrt();
709 while big_base.data.len() < target_len {
710 big_base = &big_base * &big_base;
711 big_power *= 2;
712 }
713
714 // This outer loop will run approximately √n times.
715 while digits > big_base {
716 // This is still the dominating factor, with n digits divided by √n digits.
717 let (q, mut big_r) = digits.div_rem(&big_base);
718 digits = q;
719
720 // This inner loop now has O(√n²)=O(n) behavior altogether.
721 for _ in 0..big_power {
722 let (q, mut r) = div_rem_digit(big_r, base);
723 big_r = q;
724 for _ in 0..power {
725 res.push((r % radix) as u8);
726 r /= radix;
727 }
728 }
729 }
730 }
731
732 while digits.data.len() > 1 {
733 let (q, mut r) = div_rem_digit(digits, base);
734 for _ in 0..power {
735 res.push((r % radix) as u8);
736 r /= radix;
737 }
738 digits = q;
739 }
740
741 let mut r = digits.data[0];
742 while r != 0 {
743 res.push((r % radix) as u8);
744 r /= radix;
745 }
746
747 res
748}
749
750pub(super) fn to_radix_le(u: &BigUint, radix: u32) -> Vec<u8> {
751 if u.is_zero() {
752 vec![0]
753 } else if radix.is_power_of_two() {
754 // Powers of two can use bitwise masks and shifting instead of division
755 let bits: u8 = ilog2(radix);
756 if big_digit::BITS % bits == 0 {
757 to_bitwise_digits_le(u, bits)
758 } else {
759 to_inexact_bitwise_digits_le(u, bits)
760 }
761 } else if radix == 10 {
762 // 10 is so common that it's worth separating out for const-propagation.
763 // Optimizers can often turn constant division into a faster multiplication.
764 to_radix_digits_le(u, radix:10)
765 } else {
766 to_radix_digits_le(u, radix)
767 }
768}
769
770pub(crate) fn to_str_radix_reversed(u: &BigUint, radix: u32) -> Vec<u8> {
771 assert!(2 <= radix && radix <= 36, "The radix must be within 2...36");
772
773 if u.is_zero() {
774 return vec![b'0'];
775 }
776
777 let mut res: Vec = to_radix_le(u, radix);
778
779 // Now convert everything to ASCII digits.
780 for r: &mut u8 in &mut res {
781 debug_assert!(u32::from(*r) < radix);
782 if *r < 10 {
783 *r += b'0';
784 } else {
785 *r += b'a' - 10;
786 }
787 }
788 res
789}
790
791/// Returns the greatest power of the radix for the `BigDigit` bit size
792#[inline]
793fn get_radix_base(radix: u32) -> (BigDigit, usize) {
794 static BASES: [(BigDigit, usize); 257] = generate_radix_bases(big_digit::MAX);
795 debug_assert!(!radix.is_power_of_two());
796 debug_assert!((3..256).contains(&radix));
797 BASES[radix as usize]
798}
799
800/// Returns the greatest power of the radix for half the `BigDigit` bit size
801#[inline]
802fn get_half_radix_base(radix: u32) -> (BigDigit, usize) {
803 static BASES: [(BigDigit, usize); 257] = generate_radix_bases(max:big_digit::HALF);
804 debug_assert!(!radix.is_power_of_two());
805 debug_assert!((3..256).contains(&radix));
806 BASES[radix as usize]
807}
808
809/// Generate tables of the greatest power of each radix that is less that the given maximum. These
810/// are returned from `get_radix_base` to batch the multiplication/division of radix conversions on
811/// full `BigUint` values, operating on primitive integers as much as possible.
812///
813/// e.g. BASES_16[3] = (59049, 10) // 3¹⁰ fits in u16, but 3¹¹ is too big
814/// BASES_32[3] = (3486784401, 20)
815/// BASES_64[3] = (12157665459056928801, 40)
816///
817/// Powers of two are not included, just zeroed, as they're implemented with shifts.
818const fn generate_radix_bases(max: BigDigit) -> [(BigDigit, usize); 257] {
819 let mut bases: [(u64, usize); 257] = [(0, 0); 257];
820
821 let mut radix: BigDigit = 3;
822 while radix < 256 {
823 if !radix.is_power_of_two() {
824 let mut power: usize = 1;
825 let mut base: u64 = radix;
826
827 while let Some(b: u64) = base.checked_mul(radix) {
828 if b > max {
829 break;
830 }
831 base = b;
832 power += 1;
833 }
834 bases[radix as usize] = (base, power)
835 }
836 radix += 1;
837 }
838
839 bases
840}
841
842#[test]
843fn test_radix_bases() {
844 for radix in 3u32..256 {
845 if !radix.is_power_of_two() {
846 let (base, power) = get_radix_base(radix);
847 let radix = BigDigit::from(radix);
848 let power = u32::try_from(power).unwrap();
849 assert_eq!(base, radix.pow(power));
850 assert!(radix.checked_pow(power + 1).is_none());
851 }
852 }
853}
854
855#[test]
856fn test_half_radix_bases() {
857 for radix in 3u32..256 {
858 if !radix.is_power_of_two() {
859 let (base, power) = get_half_radix_base(radix);
860 let radix = BigDigit::from(radix);
861 let power = u32::try_from(power).unwrap();
862 assert_eq!(base, radix.pow(power));
863 assert!(radix.pow(power + 1) > big_digit::HALF);
864 }
865 }
866}
867