Debian Codegraph @

third_party/rust/rust_decimal/src/ops/array.rs

raw
1 use crate::constants::{MAX_PRECISION_U32, POWERS_10, U32_MASK};
2
3 /// Rescales the given decimal to new scale.
4 /// e.g. with 1.23 and new scale 3 rescale the value to 1.230
5 #[inline(always)]
6 pub(crate) fn rescale_internal(value: &mut [u32; 3], value_scale: &mut u32, new_scale: u32) {
7 if *value_scale == new_scale {
8 // Nothing to do
9 return;
10 }
11
12 if is_all_zero(value) {
13 *value_scale = new_scale.min(MAX_PRECISION_U32);
14 return;
15 }
16
17 if *value_scale > new_scale {
18 let mut diff = value_scale.wrapping_sub(new_scale);
19 // Scaling further isn't possible since we got an overflow
20 // In this case we need to reduce the accuracy of the "side to keep"
21
22 // Now do the necessary rounding
23 let mut remainder = 0;
24 while let Some(diff_minus_one) = diff.checked_sub(1) {
25 if is_all_zero(value) {
26 *value_scale = new_scale;
27 return;
28 }
29
30 diff = diff_minus_one;
31
32 // Any remainder is discarded if diff > 0 still (i.e. lost precision)
33 remainder = div_by_u32(value, 10);
34 }
35 if remainder >= 5 {
36 for part in value.iter_mut() {
37 let digit = u64::from(*part) + 1u64;
38 remainder = if digit > U32_MASK { 1 } else { 0 };
39 *part = (digit & U32_MASK) as u32;
40 if remainder == 0 {
41 break;
42 }
43 }
44 }
45 *value_scale = new_scale;
46 } else {
47 let mut diff = new_scale.wrapping_sub(*value_scale);
48 let mut working = [value[0], value[1], value[2]];
49 while let Some(diff_minus_one) = diff.checked_sub(1) {
50 if mul_by_10(&mut working) == 0 {
51 value.copy_from_slice(&working);
52 diff = diff_minus_one;
53 } else {
54 break;
55 }
56 }
57 *value_scale = new_scale.wrapping_sub(diff);
58 }
59 }
60
61 #[cfg(feature = "legacy-ops")]
62 pub(crate) fn add_by_internal(value: &mut [u32], by: &[u32]) -> u32 {
63 let mut carry: u64 = 0;
64 let vl = value.len();
65 let bl = by.len();
66 if vl >= bl {
67 let mut sum: u64;
68 for i in 0..bl {
69 sum = u64::from(value[i]) + u64::from(by[i]) + carry;
70 value[i] = (sum & U32_MASK) as u32;
71 carry = sum >> 32;
72 }
73 if vl > bl && carry > 0 {
74 for i in value.iter_mut().skip(bl) {
75 sum = u64::from(*i) + carry;
76 *i = (sum & U32_MASK) as u32;
77 carry = sum >> 32;
78 if carry == 0 {
79 break;
80 }
81 }
82 }
83 } else if vl + 1 == bl {
84 // Overflow, by default, is anything in the high portion of by
85 let mut sum: u64;
86 for i in 0..vl {
87 sum = u64::from(value[i]) + u64::from(by[i]) + carry;
88 value[i] = (sum & U32_MASK) as u32;
89 carry = sum >> 32;
90 }
91 if by[vl] > 0 {
92 carry += u64::from(by[vl]);
93 }
94 } else {
95 panic!("Internal error: add using incompatible length arrays. {} <- {}", vl, bl);
96 }
97 carry as u32
98 }
99
100 pub(crate) fn add_by_internal_flattened(value: &mut [u32; 3], by: u32) -> u32 {
101 manage_add_by_internal(by, value)
102 }
103
104 #[inline]
105 pub(crate) fn add_one_internal(value: &mut [u32; 3]) -> u32 {
106 manage_add_by_internal(1, value)
107 }
108
109 // `u64 as u32` are safe because of widening and 32bits shifts
110 #[inline]
111 pub(crate) fn manage_add_by_internal<const N: usize>(initial_carry: u32, value: &mut [u32; N]) -> u32 {
112 let mut carry = u64::from(initial_carry);
113 let mut iter = 0..value.len();
114 let mut sum = 0;
115
116 let mut sum_fn = |local_carry: &mut u64, idx| {
117 sum = u64::from(value[idx]).wrapping_add(*local_carry);
118 value[idx] = (sum & U32_MASK) as u32;
119 *local_carry = sum.wrapping_shr(32);
120 };
121
122 if let Some(idx) = iter.next() {
123 sum_fn(&mut carry, idx);
124 }
125
126 for idx in iter {
127 if carry > 0 {
128 sum_fn(&mut carry, idx);
129 }
130 }
131
132 carry as u32
133 }
134
135 pub(crate) fn sub_by_internal(value: &mut [u32], by: &[u32]) -> u32 {
136 // The way this works is similar to long subtraction
137 // Let's assume we're working with bytes for simplicity in an example:
138 // 257 - 8 = 249
139 // 0000_0001 0000_0001 - 0000_0000 0000_1000 = 0000_0000 1111_1001
140 // We start by doing the first byte...
141 // Overflow = 0
142 // Left = 0000_0001 (1)
143 // Right = 0000_1000 (8)
144 // Firstly, we make sure the left and right are scaled up to twice the size
145 // Left = 0000_0000 0000_0001
146 // Right = 0000_0000 0000_1000
147 // We then subtract right from left
148 // Result = Left - Right = 1111_1111 1111_1001
149 // We subtract the overflow, which in this case is 0.
150 // Because left < right (1 < 8) we invert the high part.
151 // Lo = 1111_1001
152 // Hi = 1111_1111 -> 0000_0001
153 // Lo is the field, hi is the overflow.
154 // We do the same for the second byte...
155 // Overflow = 1
156 // Left = 0000_0001
157 // Right = 0000_0000
158 // Result = Left - Right = 0000_0000 0000_0001
159 // We subtract the overflow...
160 // Result = 0000_0000 0000_0001 - 1 = 0
161 // And we invert the high, just because (invert 0 = 0).
162 // So our result is:
163 // 0000_0000 1111_1001
164 let mut overflow = 0;
165 let vl = value.len();
166 let bl = by.len();
167 for i in 0..vl {
168 if i >= bl {
169 break;
170 }
171 let (lo, hi) = sub_part(value[i], by[i], overflow);
172 value[i] = lo;
173 overflow = hi;
174 }
175 overflow
176 }
177
178 fn sub_part(left: u32, right: u32, overflow: u32) -> (u32, u32) {
179 let part = 0x1_0000_0000u64 + u64::from(left) - (u64::from(right) + u64::from(overflow));
180 let lo = part as u32;
181 let hi = 1 - ((part >> 32) as u32);
182 (lo, hi)
183 }
184
185 // Returns overflow
186 #[inline]
187 pub(crate) fn mul_by_10(bits: &mut [u32; 3]) -> u32 {
188 let mut overflow = 0u64;
189 for b in bits.iter_mut() {
190 let result = u64::from(*b) * 10u64 + overflow;
191 let hi = (result >> 32) & U32_MASK;
192 let lo = (result & U32_MASK) as u32;
193 *b = lo;
194 overflow = hi;
195 }
196
197 overflow as u32
198 }
199
200 // Returns overflow
201 pub(crate) fn mul_by_u32(bits: &mut [u32], m: u32) -> u32 {
202 let mut overflow = 0;
203 for b in bits.iter_mut() {
204 let (lo, hi) = mul_part(*b, m, overflow);
205 *b = lo;
206 overflow = hi;
207 }
208 overflow
209 }
210
211 pub(crate) fn mul_part(left: u32, right: u32, high: u32) -> (u32, u32) {
212 let result = u64::from(left) * u64::from(right) + u64::from(high);
213 let hi = ((result >> 32) & U32_MASK) as u32;
214 let lo = (result & U32_MASK) as u32;
215 (lo, hi)
216 }
217
218 // Returns remainder
219 pub(crate) fn div_by_u32<const N: usize>(bits: &mut [u32; N], divisor: u32) -> u32 {
220 if divisor == 0 {
221 // Divide by zero
222 panic!("Internal error: divide by zero");
223 } else if divisor == 1 {
224 // dividend remains unchanged
225 0
226 } else {
227 let mut remainder = 0u32;
228 let divisor = u64::from(divisor);
229 for part in bits.iter_mut().rev() {
230 let temp = (u64::from(remainder) << 32) + u64::from(*part);
231 remainder = (temp % divisor) as u32;
232 *part = (temp / divisor) as u32;
233 }
234
235 remainder
236 }
237 }
238
239 pub(crate) fn div_by_1x(bits: &mut [u32; 3], power: usize) -> u32 {
240 let mut remainder = 0u32;
241 let divisor = POWERS_10[power] as u64;
242 let temp = ((remainder as u64) << 32) + (bits[2] as u64);
243 remainder = (temp % divisor) as u32;
244 bits[2] = (temp / divisor) as u32;
245 let temp = ((remainder as u64) << 32) + (bits[1] as u64);
246 remainder = (temp % divisor) as u32;
247 bits[1] = (temp / divisor) as u32;
248 let temp = ((remainder as u64) << 32) + (bits[0] as u64);
249 remainder = (temp % divisor) as u32;
250 bits[0] = (temp / divisor) as u32;
251 remainder
252 }
253
254 #[inline]
255 pub(crate) fn shl1_internal(bits: &mut [u32], carry: u32) -> u32 {
256 let mut carry = carry;
257 for part in bits.iter_mut() {
258 let b = *part >> 31;
259 *part = (*part << 1) | carry;
260 carry = b;
261 }
262 carry
263 }
264
265 #[inline]
266 pub(crate) fn cmp_internal(left: &[u32; 3], right: &[u32; 3]) -> core::cmp::Ordering {
267 let left_hi: u32 = left[2];
268 let right_hi: u32 = right[2];
269 let left_lo: u64 = u64::from(left[1]) << 32 | u64::from(left[0]);
270 let right_lo: u64 = u64::from(right[1]) << 32 | u64::from(right[0]);
271 if left_hi < right_hi || (left_hi <= right_hi && left_lo < right_lo) {
272 core::cmp::Ordering::Less
273 } else if left_hi == right_hi && left_lo == right_lo {
274 core::cmp::Ordering::Equal
275 } else {
276 core::cmp::Ordering::Greater
277 }
278 }
279
280 #[inline]
281 pub(crate) fn is_all_zero<const N: usize>(bits: &[u32; N]) -> bool {
282 bits.iter().all(|b| *b == 0)
283 }
284
285 #[cfg(test)]
286 mod test {
287 // Tests on private methods.
288 //
289 // All public tests should go under `tests/`.
290
291 use super::*;
292 use crate::prelude::*;
293
294 #[test]
295 fn it_can_rescale_internal() {
296 fn extract(value: &str) -> ([u32; 3], u32) {
297 let v = Decimal::from_str(value).unwrap();
298 (v.mantissa_array3(), v.scale())
299 }
300
301 let tests = &[
302 ("1", 0, "1", 0),
303 ("1", 1, "1.0", 1),
304 ("1", 5, "1.00000", 5),
305 ("1", 10, "1.0000000000", 10),
306 ("1", 20, "1.00000000000000000000", 20),
307 (
308 "0.6386554621848739495798319328",
309 27,
310 "0.638655462184873949579831933",
311 27,
312 ),
313 (
314 "843.65000000", // Scale 8
315 25,
316 "843.6500000000000000000000000",
317 25,
318 ),
319 (
320 "843.65000000", // Scale 8
321 30,
322 "843.6500000000000000000000000",
323 25, // Only fits 25
324 ),
325 ("0", 130, "0.000000000000000000000000000000", 28),
326 ];
327
328 for &(value_raw, new_scale, expected_value, expected_scale) in tests {
329 let (expected_value, _) = extract(expected_value);
330 let (mut value, mut value_scale) = extract(value_raw);
331 rescale_internal(&mut value, &mut value_scale, new_scale);
332 assert_eq!(value, expected_value);
333 assert_eq!(
334 value_scale, expected_scale,
335 "value: {}, requested scale: {}",
336 value_raw, new_scale
337 );
338 }
339 }
340
341 #[test]
342 fn test_shl1_internal() {
343 struct TestCase {
344 // One thing to be cautious of is that the structure of a number here for shifting left is
345 // the reverse of how you may conceive this mentally. i.e. a[2] contains the higher order
346 // bits: a[2] a[1] a[0]
347 given: [u32; 3],
348 given_carry: u32,
349 expected: [u32; 3],
350 expected_carry: u32,
351 }
352 let tests = [
353 TestCase {
354 given: [1, 0, 0],
355 given_carry: 0,
356 expected: [2, 0, 0],
357 expected_carry: 0,
358 },
359 TestCase {
360 given: [1, 0, 2147483648],
361 given_carry: 1,
362 expected: [3, 0, 0],
363 expected_carry: 1,
364 },
365 ];
366 for case in &tests {
367 let mut test = [case.given[0], case.given[1], case.given[2]];
368 let carry = shl1_internal(&mut test, case.given_carry);
369 assert_eq!(
370 test, case.expected,
371 "Bits: {:?} << 1 | {}",
372 case.given, case.given_carry
373 );
374 assert_eq!(
375 carry, case.expected_carry,
376 "Carry: {:?} << 1 | {}",
377 case.given, case.given_carry
378 )
379 }
380 }
381 }