malachite_nz/natural/conversion/string/from_string.rs
1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::natural::InnerNatural::Small;
10use crate::natural::Natural;
11use crate::platform::{Limb, MAX_DIGITS_PER_LIMB};
12use core::str::FromStr;
13use malachite_base::num::arithmetic::traits::{ModPowerOf2, ShrRound};
14use malachite_base::num::basic::integers::PrimitiveInt;
15use malachite_base::num::conversion::string::from_string::digit_from_display_byte;
16use malachite_base::num::conversion::traits::{Digits, ExactFrom, FromStringBase, WrappingFrom};
17use malachite_base::rounding_modes::RoundingMode::*;
18
19impl FromStr for Natural {
20 type Err = ();
21
22 /// Converts an string to a [`Natural`].
23 ///
24 /// If the string does not represent a valid [`Natural`], an `Err` is returned. To be valid, the
25 /// string must be nonempty and only contain the [`char`]s `'0'` through `'9'`. Leading zeros
26 /// are allowed.
27 ///
28 /// # Worst-case complexity
29 /// $T(n) = O(n (\log n)^2 \log\log n)$
30 ///
31 /// $M(n) = O(n \log n)$
32 ///
33 /// where $T$ is time, $M$ is additional memory, and $n$ is `s.len()`.
34 ///
35 /// # Examples
36 /// ```
37 /// use core::str::FromStr;
38 /// use malachite_nz::natural::Natural;
39 ///
40 /// assert_eq!(Natural::from_str("123456").unwrap(), 123456);
41 /// assert_eq!(Natural::from_str("00123456").unwrap(), 123456);
42 /// assert_eq!(Natural::from_str("0").unwrap(), 0);
43 ///
44 /// assert!(Natural::from_str("").is_err());
45 /// assert!(Natural::from_str("a").is_err());
46 /// assert!(Natural::from_str("-5").is_err());
47 /// ```
48 #[inline]
49 fn from_str(s: &str) -> Result<Self, ()> {
50 Self::from_string_base(10, s).ok_or(())
51 }
52}
53
54fn from_binary_str(s: &str) -> Option<Natural> {
55 let len = s.len();
56 if len <= usize::wrapping_from(Limb::WIDTH) {
57 Limb::from_str_radix(s, 2).ok().map(Natural::from)
58 } else {
59 let mut xs = vec![0; len.shr_round(Limb::LOG_WIDTH, Ceiling).0];
60 let mut remaining = u64::wrapping_from(len & usize::wrapping_from(Limb::WIDTH_MASK));
61 let mut i = xs.len();
62 let mut x = xs.last_mut().unwrap();
63 if remaining != 0 {
64 i -= 1;
65 }
66 for b in s.bytes() {
67 if remaining == 0 {
68 i -= 1;
69 x = &mut xs[i];
70 remaining = Limb::WIDTH;
71 }
72 *x <<= 1;
73 match b {
74 b'1' => *x |= 1,
75 b'0' => {}
76 _ => return None,
77 }
78 remaining -= 1;
79 }
80 Some(Natural::from_owned_limbs_asc(xs))
81 }
82}
83
84fn from_oct_str(s: &str) -> Option<Natural> {
85 let len = s.len();
86 if len <= usize::wrapping_from(Limb::WIDTH / 3) {
87 Limb::from_str_radix(s, 8).ok().map(Natural::from)
88 } else {
89 let bit_len = len.checked_mul(3).unwrap();
90 let mut xs = vec![0; bit_len.shr_round(Limb::LOG_WIDTH, Ceiling).0];
91 let mut remaining = u64::exact_from(bit_len) & Limb::WIDTH_MASK;
92 let mut i = xs.len();
93 let mut x = xs.last_mut().unwrap();
94 if remaining != 0 {
95 i -= 1;
96 }
97 for b in s.bytes() {
98 let digit = digit_from_display_byte(b)?;
99 if digit >= 8 {
100 return None;
101 }
102 let digit = Limb::wrapping_from(digit);
103 match remaining {
104 0 => {
105 i -= 1;
106 x = &mut xs[i];
107 *x = digit;
108 remaining = Limb::WIDTH - 3;
109 }
110 1 => {
111 *x <<= 1;
112 *x |= digit >> 2;
113 i -= 1;
114 x = &mut xs[i];
115 *x = digit & 3;
116 remaining = Limb::WIDTH - 2;
117 }
118 2 => {
119 *x <<= 2;
120 *x |= digit >> 1;
121 i -= 1;
122 x = &mut xs[i];
123 *x = digit & 1;
124 remaining = Limb::WIDTH - 1;
125 }
126 _ => {
127 *x <<= 3;
128 *x |= digit;
129 remaining -= 3;
130 }
131 }
132 }
133 Some(Natural::from_owned_limbs_asc(xs))
134 }
135}
136
137fn from_hex_str(s: &str) -> Option<Natural> {
138 let len = s.len();
139 if len <= usize::wrapping_from(Limb::WIDTH >> 2) {
140 Limb::from_str_radix(s, 16).ok().map(Natural::from)
141 } else {
142 let mut xs = vec![0; len.shr_round(Limb::LOG_WIDTH - 2, Ceiling).0];
143 let mut remaining = u64::wrapping_from(len.mod_power_of_2(Limb::LOG_WIDTH - 2)) << 2;
144 let mut i = xs.len();
145 let mut x = xs.last_mut().unwrap();
146 if remaining != 0 {
147 i -= 1;
148 }
149 for b in s.bytes() {
150 if remaining == 0 {
151 i -= 1;
152 x = &mut xs[i];
153 remaining = Limb::WIDTH;
154 }
155 *x <<= 4;
156 let digit = digit_from_display_byte(b)?;
157 if digit >= 16 {
158 return None;
159 }
160 *x |= Limb::wrapping_from(digit);
161 remaining -= 4;
162 }
163 Some(Natural::from_owned_limbs_asc(xs))
164 }
165}
166
167impl FromStringBase for Natural {
168 /// Converts an string, in a specified base, to a [`Natural`].
169 ///
170 /// If the string does not represent a valid [`Natural`], an `Err` is returned. To be valid, the
171 /// string must be nonempty and only contain the [`char`]s `'0'` through `'9'`, `'a'` through
172 /// `'z'`, and `'A'` through `'Z'`, with an optional single leading `'+'`; and only characters
173 /// that represent digits smaller than the base are allowed. Leading zeros are always allowed.
174 ///
175 /// # Worst-case complexity
176 /// $T(n) = O(n (\log n)^2 \log\log n)$
177 ///
178 /// $M(n) = O(n \log n)$
179 ///
180 /// where $T$ is time, $M$ is additional memory, and $n$ is `s.len()`.
181 ///
182 /// # Panics
183 /// Panics if `base` is less than 2 or greater than 36.
184 ///
185 /// # Examples
186 /// ```
187 /// use malachite_base::num::conversion::traits::FromStringBase;
188 /// use malachite_nz::natural::Natural;
189 ///
190 /// assert_eq!(Natural::from_string_base(10, "123456").unwrap(), 123456);
191 /// assert_eq!(Natural::from_string_base(10, "00123456").unwrap(), 123456);
192 /// assert_eq!(Natural::from_string_base(16, "0").unwrap(), 0);
193 /// assert_eq!(
194 /// Natural::from_string_base(16, "deadbeef").unwrap(),
195 /// 3735928559u32
196 /// );
197 /// assert_eq!(
198 /// Natural::from_string_base(16, "deAdBeEf").unwrap(),
199 /// 3735928559u32
200 /// );
201 ///
202 /// assert!(Natural::from_string_base(10, "").is_none());
203 /// assert!(Natural::from_string_base(10, "a").is_none());
204 /// assert!(Natural::from_string_base(10, "-5").is_none());
205 /// assert!(Natural::from_string_base(2, "2").is_none());
206 /// ```
207 #[inline]
208 fn from_string_base(base: u8, mut s: &str) -> Option<Self> {
209 assert!((2..=36).contains(&base), "base out of range");
210 if s.is_empty() {
211 None
212 } else {
213 match base {
214 2 => from_binary_str(s),
215 8 => from_oct_str(s),
216 16 => from_hex_str(s),
217 10 => {
218 if s.len() < MAX_DIGITS_PER_LIMB {
219 Limb::from_str(s).ok().map(|x| Self(Small(x)))
220 } else {
221 if let Some(prefix_s) = s.strip_prefix('+') {
222 s = prefix_s;
223 }
224 Self::from_digits_desc(
225 &10,
226 s.bytes()
227 .map(|b| if b >= b'0' { b - b'0' } else { u8::MAX }),
228 )
229 }
230 }
231 _ => {
232 for b in s.bytes() {
233 let digit = digit_from_display_byte(b)?;
234 if digit >= base {
235 return None;
236 }
237 }
238 Self::from_digits_desc(
239 &u8::wrapping_from(base),
240 s.bytes().map(|b| digit_from_display_byte(b).unwrap()),
241 )
242 }
243 }
244 }
245 }
246}