malachite_base/num/conversion/slice.rs
1// Copyright © 2025 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::num::arithmetic::traits::ShrRound;
10use crate::num::basic::integers::{PrimitiveInt, USIZE_IS_U32};
11use crate::num::basic::unsigneds::PrimitiveUnsigned;
12use crate::num::conversion::traits::{
13 FromOtherTypeSlice, SplitInHalf, VecFromOtherType, VecFromOtherTypeSlice, WrappingFrom,
14};
15use crate::rounding_modes::RoundingMode::*;
16use alloc::vec;
17use alloc::vec::Vec;
18
19const fn from_other_type_slice_ident<T: PrimitiveUnsigned>(xs: &[T]) -> T {
20 if xs.is_empty() { T::ZERO } else { xs[0] }
21}
22
23macro_rules! impl_slice_traits_ident {
24 ($a:ty) => {
25 impl FromOtherTypeSlice<$a> for $a {
26 /// Converts a slice of one type of value to a single value of the same type.
27 ///
28 /// $$
29 /// f((x_k)_{k=0}^{n-1}) = \\begin{cases}
30 /// 0 & \text{if} \\quad n = 0, \\\\
31 /// x_0 & \\text{otherwise},
32 /// \\end{cases}
33 /// $$
34 /// where $W$ is the width of the type.
35 ///
36 /// The slice is interpreted as the base-$2^W$ digits of the value, in ascending order,
37 /// where $W$ is the width of the type. If there's more than one element in the input
38 /// slice, the value wraps and all elements past the first are ignored. This means that
39 /// if the slice is empty, the output value is 0; otherwise, it's the first element of
40 /// the slice.
41 ///
42 /// # Worst-case complexity
43 /// Constant time and additional memory.
44 ///
45 /// # Examples
46 /// See [here](super::slice#from_other_type_slice).
47 #[inline]
48 fn from_other_type_slice(xs: &[$a]) -> Self {
49 from_other_type_slice_ident(xs)
50 }
51 }
52
53 impl VecFromOtherTypeSlice<$a> for $a {
54 /// Converts a slice of one type of value to a [`Vec`] of the same type.
55 ///
56 /// In this case, it just converts the slice to a [`Vec`] the usual way.
57 ///
58 /// # Worst-case complexity
59 /// $T(n) = O(n)$
60 ///
61 /// $M(n) = O(n)$
62 ///
63 /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
64 ///
65 /// # Examples
66 /// See [here](super::slice#vec_from_other_type_slice).
67 #[inline]
68 fn vec_from_other_type_slice(xs: &[$a]) -> Vec<Self> {
69 xs.to_vec()
70 }
71 }
72
73 impl VecFromOtherType<$a> for $a {
74 /// Converts a value of one type to a [`Vec`] of the same type.
75 ///
76 /// In this case, it just creates a one-element [`Vec`].
77 ///
78 /// # Worst-case complexity
79 /// Constant time and additional memory.
80 ///
81 /// # Examples
82 /// See [here](super::slice#vec_from_other_type).
83 #[inline]
84 fn vec_from_other_type(x: $a) -> Vec<Self> {
85 ::alloc::vec![x]
86 }
87 }
88 };
89}
90
91fn from_other_type_slice_large_to_small<
92 A: PrimitiveUnsigned,
93 B: PrimitiveUnsigned + WrappingFrom<A>,
94>(
95 xs: &[A],
96) -> B {
97 if xs.is_empty() {
98 B::ZERO
99 } else {
100 B::wrapping_from(xs[0])
101 }
102}
103
104fn vec_from_other_type_slice_large_to_small<
105 A: PrimitiveUnsigned,
106 B: PrimitiveUnsigned + WrappingFrom<A>,
107>(
108 xs: &[A],
109) -> Vec<B> {
110 let log_size_ratio = A::LOG_WIDTH - B::LOG_WIDTH;
111 let mut out = ::alloc::vec![B::ZERO; xs.len() << log_size_ratio];
112 for (chunk, &u) in out.chunks_exact_mut(1 << log_size_ratio).zip(xs.iter()) {
113 let mut u = u;
114 for x in chunk {
115 *x = B::wrapping_from(u);
116 u >>= B::WIDTH;
117 }
118 }
119 out
120}
121
122fn vec_from_other_type_large_to_small<
123 A: PrimitiveUnsigned,
124 B: PrimitiveUnsigned + WrappingFrom<A>,
125>(
126 mut x: A,
127) -> Vec<B> {
128 let mut xs = ::alloc::vec![B::ZERO; 1 << (A::LOG_WIDTH - B::LOG_WIDTH)];
129 for out in &mut xs {
130 *out = B::wrapping_from(x);
131 x >>= B::WIDTH;
132 }
133 xs
134}
135
136macro_rules! impl_slice_traits_large_to_small {
137 ($a:ident, $b:ident) => {
138 impl FromOtherTypeSlice<$a> for $b {
139 /// Converts a slice of one type of unsigned integer to a single value of a smaller
140 /// unsigned type.
141 ///
142 /// $$
143 /// f((x_k)_{k=0}^{n-1}) = \\begin{cases}
144 /// 0 & \text{if} \\quad n = 0, \\\\
145 /// y & \\text{otherwise},
146 /// \\end{cases}
147 /// $$
148 /// where $0 \leq y < 2^W$, $x = y + k2^W$ for some integer $k$, and $W$ is the width of
149 /// the output type.
150 ///
151 /// The slice is interpreted as the base-$2^W$ digits of the value, in ascending order,
152 /// where $W$ is the width of the type. If the slice is empty, the output value is 0;
153 /// otherwise, it consists of the least-significant bits of the first element of the
154 /// slice.
155 ///
156 /// # Worst-case complexity
157 /// Constant time and additional memory.
158 ///
159 /// # Examples
160 /// See [here](super::slice#from_other_type_slice).
161 #[inline]
162 fn from_other_type_slice(xs: &[$a]) -> Self {
163 from_other_type_slice_large_to_small(xs)
164 }
165 }
166
167 impl VecFromOtherTypeSlice<$a> for $b {
168 /// Converts a slice of one type of unsigned integer to a [`Vec`] of a smaller unsigned
169 /// type.
170 ///
171 /// Each value of the input slice will be broken up into several values in the output
172 /// [`Vec`].
173 ///
174 /// Let $V$ be the the width of the input type and $W$ the width of the output type.
175 ///
176 /// $f((x_k)_ {k=0}^{n-1}) = (y_k)_ {k=0}^{m-1}$, where
177 ///
178 /// $$
179 /// \sum_{j=0}^{n-1}2^{jV}x_j = \sum_{j=0}^{m-1}2^{jW}y_j,
180 /// $$
181 ///
182 /// $y_j < 2^W$ for all $j$, and $m = 2^{V-W}n$.
183 ///
184 /// # Worst-case complexity
185 /// $T(n) = O(n)$
186 ///
187 /// $M(n) = O(n)$
188 ///
189 /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
190 ///
191 /// # Examples
192 /// See [here](super::slice#vec_from_other_type_slice).
193 #[inline]
194 fn vec_from_other_type_slice(xs: &[$a]) -> Vec<Self> {
195 vec_from_other_type_slice_large_to_small(xs)
196 }
197 }
198
199 impl VecFromOtherType<$a> for $b {
200 /// Converts a value of one type of unsigned integer to a [`Vec`] of a smaller unsigned
201 /// type.
202 ///
203 /// The input value will be broken up into several values in the output [`Vec`].
204 ///
205 /// $f(x) = (y_k)_{k=0}^{m-1}$, where $x = \sum_{j=0}^{m-1}2^{jW}y_j$ and $m =
206 /// 2^{V-W}n$.
207 ///
208 /// # Worst-case complexity
209 /// Constant time and additional memory.
210 ///
211 /// # Examples
212 /// See [here](super::slice#vec_from_other_type).
213 #[inline]
214 fn vec_from_other_type(x: $a) -> Vec<Self> {
215 vec_from_other_type_large_to_small(x)
216 }
217 }
218 };
219}
220
221fn from_other_type_slice_small_to_large<
222 A: PrimitiveUnsigned,
223 B: PrimitiveUnsigned + WrappingFrom<A>,
224>(
225 xs: &[A],
226) -> B {
227 let mut result = B::ZERO;
228 let mut offset = 0;
229 for &u in xs.iter().take(1 << (B::LOG_WIDTH - A::LOG_WIDTH)) {
230 result |= B::wrapping_from(u) << offset;
231 offset += A::WIDTH;
232 }
233 result
234}
235
236fn vec_from_other_type_slice_small_to_large<
237 A: PrimitiveUnsigned,
238 B: PrimitiveUnsigned + WrappingFrom<A>,
239>(
240 xs: &[A],
241) -> Vec<B> {
242 let log_size_ratio = B::LOG_WIDTH - A::LOG_WIDTH;
243 let mut out = ::alloc::vec![B::ZERO; xs.len().shr_round(log_size_ratio, Ceiling).0];
244 for (x, chunk) in out.iter_mut().zip(xs.chunks(1 << log_size_ratio)) {
245 *x = from_other_type_slice_small_to_large(chunk);
246 }
247 out
248}
249
250fn vec_from_other_type_small_to_large<A, B: WrappingFrom<A>>(x: A) -> Vec<B> {
251 ::alloc::vec![B::wrapping_from(x)]
252}
253
254macro_rules! impl_slice_traits_small_to_large {
255 ($a:ident, $b:ident) => {
256 impl FromOtherTypeSlice<$a> for $b {
257 /// Converts a slice of one type of unsigned integer to a single value of a larger
258 /// unsigned type.
259 ///
260 /// Let $V$ be the the width of the input type and $W$ the width of the output type.
261 ///
262 /// $f((x_k)_{k=0}^{n-1}) = y$, where $y < 2^W$ and
263 ///
264 /// $$
265 /// y = k2^W + \sum_{j=0}^{n-1}2^{jV}x_j
266 /// $$
267 ///
268 /// for some integer $k$.
269 ///
270 /// If the input slice contains more values than necessary to build an output value, the
271 /// trailing values are ignored. If the input slice contains too few values to build an
272 /// output value, the most-significant bits of the output value are set to 0.
273 ///
274 /// # Worst-case complexity
275 /// Constant time and additional memory.
276 ///
277 /// # Examples
278 /// See [here](super::slice#from_other_type_slice).
279 #[inline]
280 fn from_other_type_slice(xs: &[$a]) -> Self {
281 from_other_type_slice_small_to_large(xs)
282 }
283 }
284
285 impl VecFromOtherTypeSlice<$a> for $b {
286 /// Converts a slice of one type of unsigned integer to a [`Vec`] of a larger unsigned
287 /// type.
288 ///
289 /// Adjacent chunks of values in the input slice will be joined into values of the
290 /// output [`Vec`]. If the last few elements of the input slice don't make up a full
291 /// chunk, the most-significant bits of the last output value are set to 0.
292 ///
293 /// Let $V$ be the the width of the input type and $W$ the width of the output type.
294 ///
295 /// $f((x_k)_ {k=0}^{n-1}) = (y_k)_ {k=0}^{m-1}$, where
296 ///
297 /// $$
298 /// \sum_{j=0}^{n-1}2^{jV}x_j = \sum_{j=0}^{m-1}2^{jW}y_j,
299 /// $$
300 ///
301 /// $y_j < 2^W$ for all $j$, and $m = \lceil n / 2^{W-V} \rceil$.
302 ///
303 /// # Worst-case complexity
304 /// $T(n) = O(n)$
305 ///
306 /// $M(n) = O(n)$
307 ///
308 /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
309 ///
310 /// # Examples
311 /// See [here](super::slice#vec_from_other_type_slice).
312 #[inline]
313 fn vec_from_other_type_slice(xs: &[$a]) -> Vec<Self> {
314 vec_from_other_type_slice_small_to_large(xs)
315 }
316 }
317
318 impl VecFromOtherType<$a> for $b {
319 /// Converts a value of one type of unsigned integer to a [`Vec`] of a larger unsigned
320 /// type.
321 ///
322 /// The output [`Vec`] only contains one value. The least-significant bits of the output
323 /// value contain the input value, and the most-significant bits are set to 0.
324 ///
325 /// # Worst-case complexity
326 /// Constant time and additional memory.
327 ///
328 /// # Examples
329 /// See [here](super::slice#vec_from_other_type).
330 #[inline]
331 fn vec_from_other_type(x: $a) -> Vec<Self> {
332 vec_from_other_type_small_to_large(x)
333 }
334 }
335 };
336}
337apply_to_unsigneds!(impl_slice_traits_ident);
338
339impl_slice_traits_large_to_small!(u16, u8);
340impl_slice_traits_large_to_small!(u32, u8);
341impl_slice_traits_large_to_small!(u32, u16);
342impl_slice_traits_large_to_small!(u64, u8);
343impl_slice_traits_large_to_small!(u64, u16);
344impl_slice_traits_large_to_small!(u64, u32);
345impl_slice_traits_large_to_small!(u128, u8);
346impl_slice_traits_large_to_small!(u128, u16);
347impl_slice_traits_large_to_small!(u128, u32);
348impl_slice_traits_large_to_small!(u128, u64);
349impl_slice_traits_large_to_small!(u128, usize);
350impl_slice_traits_large_to_small!(usize, u8);
351impl_slice_traits_large_to_small!(usize, u16);
352
353impl_slice_traits_small_to_large!(u8, u16);
354impl_slice_traits_small_to_large!(u8, u32);
355impl_slice_traits_small_to_large!(u8, u64);
356impl_slice_traits_small_to_large!(u8, u128);
357impl_slice_traits_small_to_large!(u8, usize);
358impl_slice_traits_small_to_large!(u16, u32);
359impl_slice_traits_small_to_large!(u16, u64);
360impl_slice_traits_small_to_large!(u16, u128);
361impl_slice_traits_small_to_large!(u16, usize);
362impl_slice_traits_small_to_large!(u32, u64);
363impl_slice_traits_small_to_large!(u32, u128);
364impl_slice_traits_small_to_large!(u64, u128);
365impl_slice_traits_small_to_large!(usize, u128);
366
367impl FromOtherTypeSlice<u32> for usize {
368 /// Converts a slice of `u32`s to a single `usize`.
369 ///
370 /// # Worst-case complexity
371 /// Constant time and additional memory.
372 ///
373 /// See [here](super::slice#from_other_type_slice).
374 fn from_other_type_slice(xs: &[u32]) -> Self {
375 if USIZE_IS_U32 {
376 if xs.is_empty() {
377 0
378 } else {
379 usize::wrapping_from(xs[0])
380 }
381 } else {
382 assert_eq!(usize::WIDTH, u64::WIDTH);
383 let mut result = 0;
384 let mut offset = 0;
385 for &u in xs.iter().take(2) {
386 result |= usize::wrapping_from(u) << offset;
387 offset += u32::WIDTH;
388 }
389 result
390 }
391 }
392}
393
394impl VecFromOtherTypeSlice<u32> for usize {
395 /// Converts a slice of [`u32`]s to a [`Vec`] of [`usize`]s.
396 ///
397 /// # Worst-case complexity
398 /// $T(n) = O(n)$
399 ///
400 /// $M(n) = O(n)$
401 ///
402 /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
403 ///
404 /// See [here](super::slice#vec_from_other_type_slice).
405 fn vec_from_other_type_slice(xs: &[u32]) -> Vec<Self> {
406 let mut out;
407 if USIZE_IS_U32 {
408 out = vec![0; xs.len()];
409 for (x, &u) in out.iter_mut().zip(xs.iter()) {
410 *x = usize::wrapping_from(u);
411 }
412 } else {
413 assert_eq!(usize::WIDTH, u64::WIDTH);
414 out = vec![0; xs.len().shr_round(1, Ceiling).0];
415 for (x, chunk) in out.iter_mut().zip(xs.chunks(2)) {
416 *x = usize::from_other_type_slice(chunk);
417 }
418 }
419 out
420 }
421}
422
423impl VecFromOtherType<u32> for usize {
424 /// Converts a [`u32`] to a [`Vec`] of [`usize`]s.
425 ///
426 /// # Worst-case complexity
427 /// Constant time and additional memory.
428 ///
429 /// See [here](super::slice#vec_from_other_type).
430 #[inline]
431 fn vec_from_other_type(x: u32) -> Vec<Self> {
432 vec![usize::wrapping_from(x)]
433 }
434}
435
436impl FromOtherTypeSlice<u64> for usize {
437 /// Converts a slice of [`u64`]s to a single [`usize`].
438 ///
439 /// # Worst-case complexity
440 /// Constant time and additional memory.
441 ///
442 /// See [here](super::slice#from_other_type_slice).
443 #[inline]
444 fn from_other_type_slice(xs: &[u64]) -> Self {
445 if xs.is_empty() {
446 0
447 } else {
448 usize::wrapping_from(xs[0])
449 }
450 }
451}
452
453impl VecFromOtherTypeSlice<u64> for usize {
454 /// Converts a slice of [`u64`]s to a [`Vec`] of [`usize`]s.
455 ///
456 /// # Worst-case complexity
457 /// $T(n) = O(n)$
458 ///
459 /// $M(n) = O(n)$
460 ///
461 /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
462 ///
463 /// See [here](super::slice#vec_from_other_type_slice).
464 #[allow(arithmetic_overflow)]
465 fn vec_from_other_type_slice(xs: &[u64]) -> Vec<Self> {
466 let mut out;
467 if USIZE_IS_U32 {
468 out = ::alloc::vec![0; xs.len() << 1];
469 for (chunk, &u) in out.chunks_exact_mut(2).zip(xs.iter()) {
470 let mut u = u;
471 for x in chunk {
472 *x = usize::wrapping_from(u);
473 u >>= usize::WIDTH;
474 }
475 }
476 } else {
477 assert_eq!(usize::WIDTH, u64::WIDTH);
478 out = ::alloc::vec![0; xs.len()];
479 for (x, &u) in out.iter_mut().zip(xs.iter()) {
480 *x = usize::wrapping_from(u);
481 }
482 }
483 out
484 }
485}
486
487impl VecFromOtherType<u64> for usize {
488 /// Converts a [`u64`] to a [`Vec`] of [`usize`]s.
489 ///
490 /// # Worst-case complexity
491 /// Constant time and additional memory.
492 ///
493 /// See [here](super::slice#vec_from_other_type).
494 fn vec_from_other_type(x: u64) -> Vec<Self> {
495 if USIZE_IS_U32 {
496 let (upper, lower) = x.split_in_half();
497 ::alloc::vec![usize::wrapping_from(lower), usize::wrapping_from(upper)]
498 } else {
499 assert_eq!(usize::WIDTH, u64::WIDTH);
500 ::alloc::vec![usize::wrapping_from(x)]
501 }
502 }
503}
504
505impl FromOtherTypeSlice<usize> for u32 {
506 /// Converts a slice of [`usize`]s to a single [`u32`].
507 ///
508 /// # Worst-case complexity
509 /// Constant time and additional memory.
510 ///
511 /// See [here](super::slice#from_other_type_slice).
512 #[inline]
513 fn from_other_type_slice(xs: &[usize]) -> Self {
514 if xs.is_empty() {
515 0
516 } else {
517 u32::wrapping_from(xs[0])
518 }
519 }
520}
521
522impl VecFromOtherTypeSlice<usize> for u32 {
523 /// Converts a slice of [`usize`]s to a [`Vec`] of [`u32`]s.
524 ///
525 /// # Worst-case complexity
526 /// $T(n) = O(n)$
527 ///
528 /// $M(n) = O(n)$
529 ///
530 /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
531 ///
532 /// See [here](super::slice#vec_from_other_type_slice).
533 #[allow(arithmetic_overflow)]
534 fn vec_from_other_type_slice(xs: &[usize]) -> Vec<Self> {
535 let mut out;
536 if USIZE_IS_U32 {
537 out = ::alloc::vec![0; xs.len()];
538 for (x, &u) in out.iter_mut().zip(xs.iter()) {
539 *x = u32::wrapping_from(u);
540 }
541 } else {
542 assert_eq!(usize::WIDTH, u64::WIDTH);
543 out = ::alloc::vec![0; xs.len() << 1];
544 for (chunk, &u) in out.chunks_exact_mut(2).zip(xs.iter()) {
545 let mut u = u;
546 for x in chunk {
547 *x = u32::wrapping_from(u);
548 u >>= u32::WIDTH;
549 }
550 }
551 }
552 out
553 }
554}
555
556impl VecFromOtherType<usize> for u32 {
557 /// Converts a [`usize`] to a [`Vec`] of [`u32`]s.
558 ///
559 /// # Worst-case complexity
560 /// Constant time and additional memory.
561 ///
562 /// See [here](super::slice#vec_from_other_type).
563 #[allow(arithmetic_overflow)]
564 fn vec_from_other_type(x: usize) -> Vec<Self> {
565 if USIZE_IS_U32 {
566 ::alloc::vec![u32::wrapping_from(x)]
567 } else {
568 assert_eq!(usize::WIDTH, u64::WIDTH);
569 let (upper, lower) = u64::wrapping_from(x).split_in_half();
570 ::alloc::vec![lower, upper]
571 }
572 }
573}
574
575impl FromOtherTypeSlice<usize> for u64 {
576 /// Converts a slice of [`usize`]s to a single [`u64`].
577 ///
578 /// # Worst-case complexity
579 /// Constant time and additional memory.
580 ///
581 /// See [here](super::slice#from_other_type_slice).
582 fn from_other_type_slice(xs: &[usize]) -> Self {
583 if USIZE_IS_U32 {
584 let mut result = 0;
585 let mut offset = 0;
586 for &u in xs.iter().take(2) {
587 result |= u64::wrapping_from(u) << offset;
588 offset += usize::WIDTH;
589 }
590 result
591 } else {
592 assert_eq!(usize::WIDTH, u64::WIDTH);
593 if xs.is_empty() {
594 0
595 } else {
596 u64::wrapping_from(xs[0])
597 }
598 }
599 }
600}
601
602impl VecFromOtherTypeSlice<usize> for u64 {
603 /// Converts a slice of [`usize`]s to a [`Vec`] of [`u64`]s.
604 ///
605 /// # Worst-case complexity
606 /// $T(n) = O(n)$
607 ///
608 /// $M(n) = O(n)$
609 ///
610 /// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
611 ///
612 /// See [here](super::slice#vec_from_other_type_slice).
613 fn vec_from_other_type_slice(xs: &[usize]) -> Vec<Self> {
614 let mut out;
615 if USIZE_IS_U32 {
616 out = ::alloc::vec![0; xs.len().shr_round(1, Ceiling).0];
617 for (x, chunk) in out.iter_mut().zip(xs.chunks(2)) {
618 *x = u64::from_other_type_slice(chunk);
619 }
620 } else {
621 assert_eq!(usize::WIDTH, u64::WIDTH);
622 out = ::alloc::vec![0; xs.len()];
623 for (x, &u) in out.iter_mut().zip(xs.iter()) {
624 *x = u64::wrapping_from(u);
625 }
626 }
627 out
628 }
629}
630
631impl VecFromOtherType<usize> for u64 {
632 /// Converts a [`usize`] to a [`Vec`] of [`u64`]s.
633 ///
634 /// # Worst-case complexity
635 /// Constant time and additional memory.
636 ///
637 /// See [here](super::slice#vec_from_other_type).
638 #[inline]
639 fn vec_from_other_type(x: usize) -> Vec<Self> {
640 ::alloc::vec![u64::wrapping_from(x)]
641 }
642}