1 use core::iter::FusedIterator;
2
3 #[cfg(not(u64_digit))]
4 use super::u32_chunk_to_u64;
5
6 /// An iterator of `u32` digits representation of a `BigUint` or `BigInt`,
7 /// ordered least significant digit first.
8 pub struct U32Digits<'a> {
9 #[cfg(u64_digit)]
10 data: &'a [u64],
11 #[cfg(u64_digit)]
12 next_is_lo: bool,
13 #[cfg(u64_digit)]
14 last_hi_is_zero: bool,
15
16 #[cfg(not(u64_digit))]
17 it: core::slice::Iter<'a, u32>,
18 }
19
20 #[cfg(u64_digit)]
21 impl<'a> U32Digits<'a> {
22 #[inline]
new(data: &'a [u64]) -> Self23 pub(super) fn new(data: &'a [u64]) -> Self {
24 let last_hi_is_zero = data
25 .last()
26 .map(|&last| {
27 let last_hi = (last >> 32) as u32;
28 last_hi == 0
29 })
30 .unwrap_or(false);
31 U32Digits {
32 data,
33 next_is_lo: true,
34 last_hi_is_zero,
35 }
36 }
37 }
38
39 #[cfg(u64_digit)]
40 impl Iterator for U32Digits<'_> {
41 type Item = u32;
42 #[inline]
next(&mut self) -> Option<u32>43 fn next(&mut self) -> Option<u32> {
44 match self.data.split_first() {
45 Some((&first, data)) => {
46 let next_is_lo = self.next_is_lo;
47 self.next_is_lo = !next_is_lo;
48 if next_is_lo {
49 Some(first as u32)
50 } else {
51 self.data = data;
52 if data.is_empty() && self.last_hi_is_zero {
53 self.last_hi_is_zero = false;
54 None
55 } else {
56 Some((first >> 32) as u32)
57 }
58 }
59 }
60 None => None,
61 }
62 }
63
64 #[inline]
size_hint(&self) -> (usize, Option<usize>)65 fn size_hint(&self) -> (usize, Option<usize>) {
66 let len = self.len();
67 (len, Some(len))
68 }
69
70 #[inline]
last(self) -> Option<u32>71 fn last(self) -> Option<u32> {
72 self.data.last().map(|&last| {
73 if self.last_hi_is_zero {
74 last as u32
75 } else {
76 (last >> 32) as u32
77 }
78 })
79 }
80
81 #[inline]
count(self) -> usize82 fn count(self) -> usize {
83 self.len()
84 }
85 }
86
87 #[cfg(u64_digit)]
88 impl DoubleEndedIterator for U32Digits<'_> {
next_back(&mut self) -> Option<Self::Item>89 fn next_back(&mut self) -> Option<Self::Item> {
90 match self.data.split_last() {
91 Some((&last, data)) => {
92 let last_is_lo = self.last_hi_is_zero;
93 self.last_hi_is_zero = !last_is_lo;
94 if last_is_lo {
95 self.data = data;
96 if data.is_empty() && !self.next_is_lo {
97 self.next_is_lo = true;
98 None
99 } else {
100 Some(last as u32)
101 }
102 } else {
103 Some((last >> 32) as u32)
104 }
105 }
106 None => None,
107 }
108 }
109 }
110
111 #[cfg(u64_digit)]
112 impl ExactSizeIterator for U32Digits<'_> {
113 #[inline]
len(&self) -> usize114 fn len(&self) -> usize {
115 self.data.len() * 2 - usize::from(self.last_hi_is_zero) - usize::from(!self.next_is_lo)
116 }
117 }
118
119 #[cfg(not(u64_digit))]
120 impl<'a> U32Digits<'a> {
121 #[inline]
new(data: &'a [u32]) -> Self122 pub(super) fn new(data: &'a [u32]) -> Self {
123 Self { it: data.iter() }
124 }
125 }
126
127 #[cfg(not(u64_digit))]
128 impl Iterator for U32Digits<'_> {
129 type Item = u32;
130 #[inline]
next(&mut self) -> Option<u32>131 fn next(&mut self) -> Option<u32> {
132 self.it.next().cloned()
133 }
134
135 #[inline]
size_hint(&self) -> (usize, Option<usize>)136 fn size_hint(&self) -> (usize, Option<usize>) {
137 self.it.size_hint()
138 }
139
140 #[inline]
nth(&mut self, n: usize) -> Option<u32>141 fn nth(&mut self, n: usize) -> Option<u32> {
142 self.it.nth(n).cloned()
143 }
144
145 #[inline]
last(self) -> Option<u32>146 fn last(self) -> Option<u32> {
147 self.it.last().cloned()
148 }
149
150 #[inline]
count(self) -> usize151 fn count(self) -> usize {
152 self.it.count()
153 }
154 }
155
156 #[cfg(not(u64_digit))]
157 impl DoubleEndedIterator for U32Digits<'_> {
next_back(&mut self) -> Option<Self::Item>158 fn next_back(&mut self) -> Option<Self::Item> {
159 self.it.next_back().copied()
160 }
161 }
162
163 #[cfg(not(u64_digit))]
164 impl ExactSizeIterator for U32Digits<'_> {
165 #[inline]
len(&self) -> usize166 fn len(&self) -> usize {
167 self.it.len()
168 }
169 }
170
171 impl FusedIterator for U32Digits<'_> {}
172
173 /// An iterator of `u64` digits representation of a `BigUint` or `BigInt`,
174 /// ordered least significant digit first.
175 pub struct U64Digits<'a> {
176 #[cfg(not(u64_digit))]
177 it: core::slice::Chunks<'a, u32>,
178
179 #[cfg(u64_digit)]
180 it: core::slice::Iter<'a, u64>,
181 }
182
183 #[cfg(not(u64_digit))]
184 impl<'a> U64Digits<'a> {
185 #[inline]
new(data: &'a [u32]) -> Self186 pub(super) fn new(data: &'a [u32]) -> Self {
187 U64Digits { it: data.chunks(2) }
188 }
189 }
190
191 #[cfg(not(u64_digit))]
192 impl Iterator for U64Digits<'_> {
193 type Item = u64;
194 #[inline]
next(&mut self) -> Option<u64>195 fn next(&mut self) -> Option<u64> {
196 self.it.next().map(u32_chunk_to_u64)
197 }
198
199 #[inline]
size_hint(&self) -> (usize, Option<usize>)200 fn size_hint(&self) -> (usize, Option<usize>) {
201 let len = self.len();
202 (len, Some(len))
203 }
204
205 #[inline]
last(self) -> Option<u64>206 fn last(self) -> Option<u64> {
207 self.it.last().map(u32_chunk_to_u64)
208 }
209
210 #[inline]
count(self) -> usize211 fn count(self) -> usize {
212 self.len()
213 }
214 }
215
216 #[cfg(not(u64_digit))]
217 impl DoubleEndedIterator for U64Digits<'_> {
next_back(&mut self) -> Option<Self::Item>218 fn next_back(&mut self) -> Option<Self::Item> {
219 self.it.next_back().map(u32_chunk_to_u64)
220 }
221 }
222
223 #[cfg(u64_digit)]
224 impl<'a> U64Digits<'a> {
225 #[inline]
new(data: &'a [u64]) -> Self226 pub(super) fn new(data: &'a [u64]) -> Self {
227 Self { it: data.iter() }
228 }
229 }
230
231 #[cfg(u64_digit)]
232 impl Iterator for U64Digits<'_> {
233 type Item = u64;
234 #[inline]
next(&mut self) -> Option<u64>235 fn next(&mut self) -> Option<u64> {
236 self.it.next().cloned()
237 }
238
239 #[inline]
size_hint(&self) -> (usize, Option<usize>)240 fn size_hint(&self) -> (usize, Option<usize>) {
241 self.it.size_hint()
242 }
243
244 #[inline]
nth(&mut self, n: usize) -> Option<u64>245 fn nth(&mut self, n: usize) -> Option<u64> {
246 self.it.nth(n).cloned()
247 }
248
249 #[inline]
last(self) -> Option<u64>250 fn last(self) -> Option<u64> {
251 self.it.last().cloned()
252 }
253
254 #[inline]
count(self) -> usize255 fn count(self) -> usize {
256 self.it.count()
257 }
258 }
259
260 #[cfg(u64_digit)]
261 impl DoubleEndedIterator for U64Digits<'_> {
next_back(&mut self) -> Option<Self::Item>262 fn next_back(&mut self) -> Option<Self::Item> {
263 self.it.next_back().cloned()
264 }
265 }
266
267 impl ExactSizeIterator for U64Digits<'_> {
268 #[inline]
len(&self) -> usize269 fn len(&self) -> usize {
270 self.it.len()
271 }
272 }
273
274 impl FusedIterator for U64Digits<'_> {}
275
276 #[test]
test_iter_u32_digits()277 fn test_iter_u32_digits() {
278 let n = super::BigUint::from(5u8);
279 let mut it = n.iter_u32_digits();
280 assert_eq!(it.len(), 1);
281 assert_eq!(it.next(), Some(5));
282 assert_eq!(it.len(), 0);
283 assert_eq!(it.next(), None);
284 assert_eq!(it.len(), 0);
285 assert_eq!(it.next(), None);
286
287 let n = super::BigUint::from(112500000000u64);
288 let mut it = n.iter_u32_digits();
289 assert_eq!(it.len(), 2);
290 assert_eq!(it.next(), Some(830850304));
291 assert_eq!(it.len(), 1);
292 assert_eq!(it.next(), Some(26));
293 assert_eq!(it.len(), 0);
294 assert_eq!(it.next(), None);
295 }
296
297 #[test]
test_iter_u64_digits()298 fn test_iter_u64_digits() {
299 let n = super::BigUint::from(5u8);
300 let mut it = n.iter_u64_digits();
301 assert_eq!(it.len(), 1);
302 assert_eq!(it.next(), Some(5));
303 assert_eq!(it.len(), 0);
304 assert_eq!(it.next(), None);
305 assert_eq!(it.len(), 0);
306 assert_eq!(it.next(), None);
307
308 let n = super::BigUint::from(18_446_744_073_709_551_616u128);
309 let mut it = n.iter_u64_digits();
310 assert_eq!(it.len(), 2);
311 assert_eq!(it.next(), Some(0));
312 assert_eq!(it.len(), 1);
313 assert_eq!(it.next(), Some(1));
314 assert_eq!(it.len(), 0);
315 assert_eq!(it.next(), None);
316 }
317
318 #[test]
test_iter_u32_digits_be()319 fn test_iter_u32_digits_be() {
320 let n = super::BigUint::from(5u8);
321 let mut it = n.iter_u32_digits();
322 assert_eq!(it.len(), 1);
323 assert_eq!(it.next(), Some(5));
324 assert_eq!(it.len(), 0);
325 assert_eq!(it.next(), None);
326 assert_eq!(it.len(), 0);
327 assert_eq!(it.next(), None);
328
329 let n = super::BigUint::from(112500000000u64);
330 let mut it = n.iter_u32_digits();
331 assert_eq!(it.len(), 2);
332 assert_eq!(it.next(), Some(830850304));
333 assert_eq!(it.len(), 1);
334 assert_eq!(it.next(), Some(26));
335 assert_eq!(it.len(), 0);
336 assert_eq!(it.next(), None);
337 }
338
339 #[test]
test_iter_u64_digits_be()340 fn test_iter_u64_digits_be() {
341 let n = super::BigUint::from(5u8);
342 let mut it = n.iter_u64_digits();
343 assert_eq!(it.len(), 1);
344 assert_eq!(it.next_back(), Some(5));
345 assert_eq!(it.len(), 0);
346 assert_eq!(it.next(), None);
347 assert_eq!(it.len(), 0);
348 assert_eq!(it.next(), None);
349
350 let n = super::BigUint::from(18_446_744_073_709_551_616u128);
351 let mut it = n.iter_u64_digits();
352 assert_eq!(it.len(), 2);
353 assert_eq!(it.next_back(), Some(1));
354 assert_eq!(it.len(), 1);
355 assert_eq!(it.next_back(), Some(0));
356 assert_eq!(it.len(), 0);
357 assert_eq!(it.next(), None);
358 }
359