malachite_base/num/conversion/digits/power_of_2_digits.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::basic::unsigneds::PrimitiveUnsigned;
10use crate::num::conversion::traits::{PowerOf2Digits, WrappingFrom};
11use alloc::vec::Vec;
12
13fn to_power_of_2_digits_asc<T: PrimitiveUnsigned, U: PrimitiveUnsigned + WrappingFrom<T>>(
14 x: &T,
15 log_base: u64,
16) -> Vec<U> {
17 assert_ne!(log_base, 0);
18 assert!(
19 log_base <= U::WIDTH,
20 "type {:?} is too small for a digit of width {}",
21 U::NAME,
22 log_base
23 );
24 let mut digits = Vec::new();
25 if *x == T::ZERO {
26 } else if x.significant_bits() <= log_base {
27 digits.push(U::wrapping_from(*x));
28 } else {
29 let mut x = *x;
30 let mask = U::low_mask(log_base);
31 while x != T::ZERO {
32 digits.push(U::wrapping_from(x) & mask);
33 x >>= log_base;
34 }
35 }
36 digits
37}
38
39fn to_power_of_2_digits_desc<T: PrimitiveUnsigned, U: PrimitiveUnsigned + WrappingFrom<T>>(
40 x: &T,
41 log_base: u64,
42) -> Vec<U> {
43 let mut digits = to_power_of_2_digits_asc(x, log_base);
44 digits.reverse();
45 digits
46}
47
48fn from_power_of_2_digits_asc<
49 T: TryFrom<U> + PrimitiveUnsigned + WrappingFrom<U>,
50 U: PrimitiveUnsigned,
51 I: Iterator<Item = U>,
52>(
53 log_base: u64,
54 digits: I,
55) -> Option<T> {
56 assert_ne!(log_base, 0);
57 assert!(
58 log_base <= U::WIDTH,
59 "type {:?} is too small for a digit of width {}",
60 U::NAME,
61 log_base
62 );
63 let mut n = T::ZERO;
64 let mut shift = 0;
65 for digit in digits {
66 if digit.significant_bits() > log_base {
67 return None;
68 }
69 n |= T::try_from(digit)
70 .ok()
71 .and_then(|d| d.arithmetic_checked_shl(shift))?;
72 shift += log_base;
73 }
74 Some(n)
75}
76
77fn from_power_of_2_digits_desc<
78 T: PrimitiveUnsigned + WrappingFrom<U>,
79 U: PrimitiveUnsigned,
80 I: Iterator<Item = U>,
81>(
82 log_base: u64,
83 digits: I,
84) -> Option<T> {
85 assert_ne!(log_base, 0);
86 assert!(
87 log_base <= U::WIDTH,
88 "type {:?} is too small for a digit of width {}",
89 U::NAME,
90 log_base
91 );
92 let mut n = T::ZERO;
93 for digit in digits {
94 if digit.significant_bits() > log_base {
95 return None;
96 }
97 let shifted = n.arithmetic_checked_shl(log_base)?;
98 n = shifted | T::wrapping_from(digit);
99 }
100 Some(n)
101}
102
103macro_rules! impl_power_of_2_digits {
104 ($t:ident) => {
105 macro_rules! impl_power_of_2_digits_inner {
106 ($u:ident) => {
107 impl PowerOf2Digits<$u> for $t {
108 /// Returns a [`Vec`] containing the base-$2^k$ digits of a number in ascending
109 /// order (least- to most-significant).
110 ///
111 /// The base-2 logarithm of the base is specified. `log_base` must be no larger
112 /// than the width of the digit type. If `self` is 0, the [`Vec`] is empty;
113 /// otherwise, it ends with a nonzero digit.
114 ///
115 /// $f(x, k) = (d_i)_ {i=0}^{n-1}$, where $0 \leq d_i < 2^k$ for all $i$, $n=0$
116 /// or $d_{n-1} \neq 0$, and
117 ///
118 /// $$
119 /// \sum_{i=0}^{n-1}2^{ki}d_i = x.
120 /// $$
121 ///
122 /// # Worst-case complexity
123 /// $T(n) = O(n)$
124 ///
125 /// $M(n) = O(n)$
126 ///
127 /// where $T$ is time, $M$ is additional memory, and $n$ is
128 /// `self.significant_bits()`.
129 ///
130 /// # Panics
131 /// Panics if `log_base` is greater than the width of the output type, or if
132 /// `log_base` is zero.
133 ///
134 /// # Examples
135 /// See [here](super::power_of_2_digits#to_power_of_2_digits_asc).
136 #[inline]
137 fn to_power_of_2_digits_asc(&self, log_base: u64) -> Vec<$u> {
138 to_power_of_2_digits_asc(self, log_base)
139 }
140
141 /// Returns a [`Vec`] containing the base-$2^k$ digits of a number in descending
142 /// order (most- to least-significant).
143 ///
144 /// The base-2 logarithm of the base is specified. `log_base` must be no larger
145 /// than the width of the digit type. If `self` is 0, the [`Vec`] is empty;
146 /// otherwise, it begins with a nonzero digit.
147 ///
148 /// $f(x, k) = (d_i)_ {i=0}^{n-1}$, where $0 \leq d_i < 2^k$ for all $i$, $n=0$
149 /// or $d_0 \neq 0$, and
150 ///
151 /// $$
152 /// \sum_{i=0}^{n-1}2^{k (n-i-1)}d_i = x.
153 /// $$
154 ///
155 /// # Worst-case complexity
156 /// $T(n) = O(n)$
157 ///
158 /// $M(n) = O(n)$
159 ///
160 /// where $T$ is time, $M$ is additional memory, and $n$ is
161 /// `self.significant_bits()`.
162 ///
163 /// # Panics
164 /// Panics if `log_base` is greater than the width of the output type, or if
165 /// `log_base` is zero.
166 ///
167 /// # Examples
168 /// See [here](super::power_of_2_digits#to_power_of_2_digits_desc).
169 #[inline]
170 fn to_power_of_2_digits_desc(&self, log_base: u64) -> Vec<$u> {
171 to_power_of_2_digits_desc(self, log_base)
172 }
173
174 /// Converts an iterator of base-$2^k$ digits into a value.
175 ///
176 /// The base-2 logarithm of the base is specified. The input digits are in
177 /// ascending order (least- to most-significant). `log_base` must be no larger
178 /// than the width of the digit type. The function returns `None` if the input
179 /// represents a number that can't fit in the output type.
180 ///
181 /// $$
182 /// f((d_i)_ {i=0}^{n-1}, k) = \sum_{i=0}^{n-1}2^{ki}d_i.
183 /// $$
184 ///
185 /// # Worst-case complexity
186 /// $T(n) = O(n)$
187 ///
188 /// $M(n) = O(1)$
189 ///
190 /// where $T$ is time, $M$ is additional memory, and $n$ is `digits.count()`.
191 ///
192 /// # Panics
193 /// Panics if `log_base` is greater than the width of the digit type, or if
194 /// `log_base` is zero.
195 ///
196 /// # Examples
197 /// See [here](super::power_of_2_digits#from_power_of_2_digits_asc).
198 #[inline]
199 fn from_power_of_2_digits_asc<I: Iterator<Item = $u>>(
200 log_base: u64,
201 digits: I,
202 ) -> Option<$t> {
203 from_power_of_2_digits_asc(log_base, digits)
204 }
205
206 /// Converts an iterator of base-$2^k$ digits into a value.
207 ///
208 /// The base-2 logarithm of the base is specified. The input digits are in
209 /// descending order (most- to least-significant). `log_base` must be no larger
210 /// than the width of the digit type. The function returns `None` if the input
211 /// represents a number that can't fit in the output type.
212 ///
213 /// $$
214 /// f((d_i)_ {i=0}^{n-1}, k) = \sum_{i=0}^{n-1}2^{k (n-i-1)}d_i.
215 /// $$
216 ///
217 /// # Worst-case complexity
218 /// $T(n) = O(n)$
219 ///
220 /// $M(n) = O(1)$
221 ///
222 /// where $T$ is time, $M$ is additional memory, and $n$ is `digits.count()`.
223 ///
224 /// # Panics
225 /// Panics if `log_base` is greater than the width of the digit type, or if
226 /// `log_base` is zero.
227 ///
228 /// # Examples
229 /// See [here](super::power_of_2_digits#from_power_of_2_digits_desc).
230 fn from_power_of_2_digits_desc<I: Iterator<Item = $u>>(
231 log_base: u64,
232 digits: I,
233 ) -> Option<$t> {
234 from_power_of_2_digits_desc(log_base, digits)
235 }
236 }
237 };
238 }
239 apply_to_unsigneds!(impl_power_of_2_digits_inner);
240 };
241}
242apply_to_unsigneds!(impl_power_of_2_digits);