Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_austenite/src/eval/lib/decimal.rs

20.6 KiB, 1 run

created by r1870400018:63230, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1// U3 owns this file. Typst's `decimal`: a 96-bit integer mantissa, a scale of 0 to 28 decimal places and
2// a sign, with the arithmetic of the `rust_decimal` crate Typst 0.15 uses (itself a port of .NET's
3// `System.Decimal`), so a result carries the digits, the scale and even the sign of zero that Typst's
4// does. The algorithms follow rust_decimal 1.39: an exact result reduced to 96 bits by round half to
5// even over every discarded digit, division extended a chunk of digits at a time and then stripped of
6// trailing zeros, and a float read through rust_decimal's base-2 walk.
7
8use oxedyne_fe2o3_core::prelude::*;
9
10use std::cmp::Ordering;
11
12const MAX_SCALE: u32 = 28;
13const MAX_M: u128 = (1u128 << 96) - 1;
14const LIMBS: usize = 8; // a 256-bit working integer, room for any product or aligned sum
15
16// Wide unsigned arithmetic, little-endian 32-bit limbs.
17type W = [u32; LIMBS];
18
19fn w_from(x: u128) -> W {
20 let mut w = [0u32; LIMBS];
21 for (i, l) in w.iter_mut().enumerate().take(4) {
22 *l = (x >> (32 * i)) as u32;
23 }
24 w
25}
26
27fn w_fits96(w: &W) -> bool { w.iter().skip(3).all(|l| *l == 0) }
28
29fn w_to_u128(w: &W) -> u128 {
30 w.iter().take(4).enumerate().fold(0u128, |a, (i, l)| a | ((*l as u128) << (32 * i)))
31}
32
33// Multiplies in place by a small factor; true when it overflowed 256 bits.
34fn w_mul_small(w: &mut W, f: u32) -> bool {
35 let mut carry = 0u64;
36 for l in w.iter_mut() {
37 let t = (*l as u64) * (f as u64) + carry;
38 *l = t as u32;
39 carry = t >> 32;
40 }
41 carry != 0
42}
43
44// Divides in place by a small divisor, returning the remainder.
45fn w_div_small(w: &mut W, d: u32) -> u32 {
46 let mut rem = 0u64;
47 for l in w.iter_mut().rev() {
48 let t = (rem << 32) | (*l as u64);
49 *l = (t / d as u64) as u32;
50 rem = t % d as u64;
51 }
52 rem as u32
53}
54
55fn w_mul(a: u128, b: u128) -> W {
56 let (x, y) = (w_from(a), w_from(b));
57 let mut out = [0u32; LIMBS];
58 for i in 0..4 {
59 let mut carry = 0u64;
60 for j in 0..4 {
61 let k = i + j;
62 let t = (x[i] as u64) * (y[j] as u64) + (out[k] as u64) + carry;
63 out[k] = t as u32;
64 carry = t >> 32;
65 }
66 let mut k = i + 4;
67 while carry != 0 && k < LIMBS {
68 let t = (out[k] as u64) + carry;
69 out[k] = t as u32;
70 carry = t >> 32;
71 k += 1;
72 }
73 }
74 out
75}
76
77fn w_add(a: &W, b: &W) -> W {
78 let mut out = [0u32; LIMBS];
79 let mut carry = 0u64;
80 for i in 0..LIMBS {
81 let t = (a[i] as u64) + (b[i] as u64) + carry;
82 out[i] = t as u32;
83 carry = t >> 32;
84 }
85 out
86}
87
88// `a - b` for `a >= b`.
89fn w_sub(a: &W, b: &W) -> W {
90 let mut out = [0u32; LIMBS];
91 let mut borrow = 0i64;
92 for i in 0..LIMBS {
93 let mut t = (a[i] as i64) - (b[i] as i64) - borrow;
94 borrow = 0;
95 if t < 0 {
96 t += 1i64 << 32;
97 borrow = 1;
98 }
99 out[i] = t as u32;
100 }
101 out
102}
103
104fn w_cmp(a: &W, b: &W) -> Ordering {
105 for i in (0..LIMBS).rev() {
106 match a[i].cmp(&b[i]) {
107 Ordering::Equal => continue,
108 o => return o,
109 }
110 }
111 Ordering::Equal
112}
113
114// Multiplies by ten `k` times; true on overflow.
115fn w_scale_up(w: &mut W, k: u32) -> bool {
116 for _ in 0..k {
117 if w_mul_small(w, 10) {
118 return true;
119 }
120 }
121 false
122}
123
124/// A Typst decimal. Equality and ordering are by value (`1.0 == 1.00`); the scale survives for display.
125#[derive(Clone, Copy, Debug, Default)]
126pub struct Decimal {
127 m: u128, // below 2^96
128 scale: u32, // 0 to 28 digits after the point
129 neg: bool,
130}
131
132impl PartialEq for Decimal {
133 fn eq(&self, other: &Self) -> bool { self.cmp(other) == Ordering::Equal }
134}
135
136impl Eq for Decimal {}
137
138impl PartialOrd for Decimal {
139 fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) }
140}
141
142impl Ord for Decimal {
143 fn cmp(&self, other: &Self) -> Ordering {
144 let (za, zb) = (self.is_zero(), other.is_zero());
145 if za && zb {
146 return Ordering::Equal;
147 }
148 let (na, nb) = (self.neg && !za, other.neg && !zb);
149 if na != nb {
150 return if na { Ordering::Less } else { Ordering::Greater };
151 }
152 let (a, b) = aligned(self, other);
153 let mag = match (a, b) {
154 (Some(a), Some(b)) => w_cmp(&a, &b),
155 _ => Ordering::Equal,
156 };
157 if na { mag.reverse() } else { mag }
158 }
159}
160
161// Both mantissas at the larger scale.
162fn aligned(a: &Decimal, b: &Decimal) -> (Option<W>, Option<W>) {
163 let s = a.scale.max(b.scale);
164 let mut x = w_from(a.m);
165 let mut y = w_from(b.m);
166 let ox = w_scale_up(&mut x, s - a.scale);
167 let oy = w_scale_up(&mut y, s - b.scale);
168 (if ox { None } else { Some(x) }, if oy { None } else { Some(y) })
169}
170
171impl From<i64> for Decimal {
172 fn from(i: i64) -> Self { Decimal { m: i.unsigned_abs() as u128, scale: 0, neg: i < 0 } }
173}
174
175impl Decimal {
176 pub const ZERO: Decimal = Decimal { m: 0, scale: 0, neg: false };
177 pub const ONE: Decimal = Decimal { m: 1, scale: 0, neg: false };
178
179 pub fn is_zero(&self) -> bool { self.m == 0 }
180
181 /// Is the sign bit set? A negative zero is, as in rust_decimal.
182 pub fn is_negative(&self) -> bool { self.neg }
183
184 pub fn scale(&self) -> u32 { self.scale }
185
186 pub fn neg(self) -> Self { Decimal { neg: !self.neg, ..self } }
187
188 pub fn abs(self) -> Self { Decimal { neg: false, ..self } }
189
190 /// Does the value have no fractional part?
191 pub fn is_integer(&self) -> bool {
192 let mut m = self.m;
193 for _ in 0..self.scale {
194 if m % 10 != 0 {
195 return false;
196 }
197 m /= 10;
198 }
199 true
200 }
201
202 /// rust_decimal's `from_str_exact`: an optional sign, digits with `_` separators after the first
203 /// digit, one optional point, no exponent; more than 28 decimal places or 96 bits is an error.
204 pub fn parse(s: &str) -> Option<Self> {
205 let b = s.as_bytes();
206 // rust_decimal takes its 96-bit path from 18 bytes on, where 28 decimal places is the limit.
207 let big = b.len() >= 18;
208 let mut i = 0;
209 let mut neg = false;
210 match b.first() {
211 Some(b'-') => { neg = true; i = 1; }
212 Some(b'+') => i = 1,
213 _ => (),
214 }
215 let (mut m, mut scale, mut point, mut has) = (0u128, 0u32, false, false);
216 while i < b.len() {
217 let c = b[i];
218 match c {
219 b'0'..=b'9' => {
220 let next = m * 10 + (c - b'0') as u128;
221 if next > MAX_M {
222 return None;
223 }
224 m = next;
225 has = true;
226 if point {
227 scale += 1;
228 if big && scale >= MAX_SCALE && i + 1 < b.len() {
229 return None;
230 }
231 }
232 }
233 b'.' if !point => point = true,
234 b'_' if has => (),
235 _ => return None,
236 }
237 i += 1;
238 }
239 if !has || scale > MAX_SCALE {
240 return None;
241 }
242 Some(Decimal { m, scale, neg })
243 }
244
245 /// rust_decimal's `from_f64_retain`: the float's binary value walked into base ten, keeping every
246 /// digit that fits. `None` for NaN, an infinity or a magnitude past 96 bits.
247 pub fn from_f64(x: f64) -> Option<Self> {
248 if !x.is_finite() {
249 return None;
250 }
251 let raw = x.to_bits();
252 let positive = (raw >> 63) == 0;
253 let biased = ((raw >> 52) & 0x7ff) as i32;
254 let frac = (raw & 0x000f_ffff_ffff_ffff) as u128;
255 if biased == 0 && frac == 0 {
256 return Some(Decimal { m: 0, scale: 0, neg: !positive });
257 }
258 let mut exp2 = biased - 1023;
259 let mut bits = frac;
260 if biased == 0 {
261 exp2 += 1;
262 } else {
263 bits |= 1u128 << 52;
264 }
265 exp2 -= 52;
266 let mut exp5 = -exp2;
267 let mut exp10 = exp2;
268 while exp5 > 0 {
269 if bits & 1 == 0 {
270 exp10 += 1;
271 exp5 -= 1;
272 bits >>= 1;
273 } else {
274 exp5 -= 1;
275 let t = bits * 5;
276 if t <= MAX_M {
277 bits = t;
278 } else {
279 exp10 += 1;
280 bits >>= 1;
281 }
282 }
283 }
284 while exp5 < 0 {
285 if bits & (1u128 << 95) == 0 {
286 exp10 -= 1;
287 exp5 += 1;
288 bits <<= 1;
289 } else if exp10 * 2 > -exp5 {
290 return None;
291 } else {
292 exp5 += 1;
293 bits /= 5;
294 }
295 }
296 while exp10 > 0 {
297 let t = bits * 10;
298 if t > MAX_M {
299 return None;
300 }
301 bits = t;
302 exp10 -= 1;
303 }
304 while exp10 < -(MAX_SCALE as i32) {
305 let rem = bits % 10;
306 bits /= 10;
307 exp10 += 1;
308 if bits == 0 {
309 exp10 = 0;
310 } else if rem >= 5 {
311 bits += 1;
312 }
313 }
314 Some(Decimal { m: bits, scale: (-exp10) as u32, neg: !positive })
315 }
316
317 /// rust_decimal's conversion to `f64`: the integral and fractional parts summed, then rounded to
318 /// the scale's decimal places.
319 pub fn to_f64(&self) -> f64 {
320 let v = if self.scale == 0 {
321 self.m as f64
322 } else {
323 let p = 10u128.pow(self.scale);
324 let int = (self.m / p) as f64;
325 let frac = ((self.m % p) as f64) / (p as f64);
326 if frac == 0.0 {
327 int
328 } else {
329 let r = 10f64.powi(self.scale as i32);
330 ((int + frac) * r).round() / r
331 }
332 };
333 if self.neg { -v } else { v }
334 }
335
336 /// The integer part, when it fits in an `i64`.
337 pub fn to_i64(&self) -> Option<i64> {
338 let t = self.trunc();
339 if t.neg {
340 if t.m <= (i64::MAX as u128) + 1 { Some((t.m as i128).wrapping_neg() as i64) } else { None }
341 } else if t.m <= i64::MAX as u128 {
342 Some(t.m as i64)
343 } else {
344 None
345 }
346 }
347
348 pub fn trunc(&self) -> Self {
349 let mut m = self.m;
350 for _ in 0..self.scale {
351 m /= 10;
352 }
353 Decimal { m, scale: 0, neg: self.neg }
354 }
355
356 pub fn fract(&self) -> Self {
357 match self.checked_sub(self.trunc()) {
358 Some(f) => f,
359 None => Decimal::ZERO,
360 }
361 }
362
363 pub fn floor(&self) -> Self {
364 if self.scale == 0 {
365 return *self;
366 }
367 let t = self.trunc();
368 if self.neg && !self.fract().is_zero() {
369 t.checked_sub(Decimal::ONE).unwrap_or(t)
370 } else {
371 t
372 }
373 }
374
375 pub fn ceil(&self) -> Self {
376 if self.scale == 0 {
377 return *self;
378 }
379 let t = self.trunc();
380 if !self.neg && !self.fract().is_zero() {
381 t.checked_add(Decimal::ONE).unwrap_or(t)
382 } else {
383 t
384 }
385 }
386
387 /// Rounds half away from zero to `dp` decimal places; a value with fewer places is unchanged.
388 pub fn round_dp(&self, dp: u32) -> Self {
389 if self.scale <= dp {
390 return *self;
391 }
392 if self.is_zero() {
393 return Decimal { m: 0, scale: dp, neg: self.neg };
394 }
395 let cut = 10u128.pow(self.scale - dp);
396 let mut q = self.m / cut;
397 if (self.m % cut) * 2 >= cut {
398 q += 1;
399 }
400 Decimal { m: q, scale: dp, neg: self.neg }
401 }
402
403 /// Typst's `round(digits)`: half away from zero, negative digits rounding to tens, hundreds and so
404 /// on. `None` when multiplying back overflows.
405 pub fn round(&self, digits: i64) -> Option<Self> {
406 if digits >= 0 {
407 let dp = if digits > u32::MAX as i64 { u32::MAX } else { digits as u32 };
408 return Some(self.round_dp(dp));
409 }
410 let d = digits.unsigned_abs();
411 let new_scale = (self.scale as u64) + d;
412 if new_scale > MAX_SCALE as u64 || d > 28 {
413 return Some(Decimal { m: 0, scale: 0, neg: self.neg });
414 }
415 let shifted = Decimal { m: self.m, scale: new_scale as u32, neg: self.neg }.round_dp(0);
416 let ten = Decimal { m: 10u128.pow(d as u32), scale: 0, neg: false };
417 shifted.checked_mul(ten)
418 }
419
420 pub fn checked_add(self, other: Self) -> Option<Self> { add_sub(self, other, false) }
421
422 pub fn checked_sub(self, other: Self) -> Option<Self> { add_sub(self, other, true) }
423
424 pub fn checked_mul(self, other: Self) -> Option<Self> {
425 if self.is_zero() || other.is_zero() {
426 return Some(Decimal::ZERO);
427 }
428 let scale = self.scale + other.scale;
429 let neg = self.neg ^ other.neg;
430 // Two 32-bit mantissas: past 47 places the product rounds to a plain zero.
431 if self.m >> 32 == 0 && other.m >> 32 == 0 && scale > MAX_SCALE + 19 {
432 return Some(Decimal::ZERO);
433 }
434 reduce(w_mul(self.m, other.m), scale, neg)
435 }
436
437 pub fn checked_div(self, other: Self) -> Option<Self> {
438 if other.is_zero() {
439 return None;
440 }
441 if self.is_zero() {
442 return Some(Decimal::ZERO);
443 }
444 div(self, other)
445 }
446
447 /// The remainder with the dividend's sign, at the larger of the two scales.
448 pub fn checked_rem(self, other: Self) -> Option<Self> {
449 if other.is_zero() {
450 return None;
451 }
452 if self.is_zero() {
453 return Some(Decimal::ZERO);
454 }
455 let (a, b) = match aligned(&self, &other) {
456 (Some(a), Some(b)) => (a, b),
457 _ => return None,
458 };
459 match w_cmp(&a, &b) {
460 Ordering::Equal => return Some(Decimal::ZERO),
461 Ordering::Less => return Some(self),
462 Ordering::Greater => (),
463 }
464 let b = w_to_u128(&b);
465 // `a` may exceed 96 bits after alignment; the remainder does not.
466 let mut rem = 0u128;
467 for l in a.iter().rev() {
468 rem = ((rem << 32) | (*l as u128)) % b;
469 }
470 Some(Decimal { m: rem, scale: self.scale.max(other.scale), neg: self.neg })
471 }
472
473 pub fn checked_div_euclid(self, other: Self) -> Option<Self> {
474 let q = match self.checked_div(other) {
475 Some(q) => q.trunc(),
476 None => return None,
477 };
478 match self.checked_rem(other) {
479 Some(r) if r.neg && !r.is_zero() => if !other.neg {
480 q.checked_sub(Decimal::ONE)
481 } else {
482 q.checked_add(Decimal::ONE)
483 },
484 _ => Some(q),
485 }
486 }
487
488 pub fn checked_rem_euclid(self, other: Self) -> Option<Self> {
489 let r = match self.checked_rem(other) {
490 Some(r) => r,
491 None => return None,
492 };
493 if r.neg && !r.is_zero() { r.checked_add(other.abs()) } else { Some(r) }
494 }
495
496 /// rust_decimal's `checked_powi`: squaring and multiplying, then `1 / x^n` for a negative power.
497 pub fn checked_powi(self, exp: i64) -> Option<Self> {
498 if exp >= 0 {
499 return self.checked_powu(exp as u64);
500 }
501 match self.checked_powu(exp.unsigned_abs()) {
502 Some(p) => Decimal::ONE.checked_div(p),
503 None => None,
504 }
505 }
506
507 fn checked_powu(self, exp: u64) -> Option<Self> {
508 if exp == 0 {
509 return Some(Decimal::ONE);
510 }
511 if self.is_zero() {
512 return Some(Decimal::ZERO);
513 }
514 if self == Decimal::ONE {
515 return Some(Decimal::ONE);
516 }
517 match exp {
518 1 => Some(self),
519 2 => self.checked_mul(self),
520 _ => {
521 let mut product = Decimal::ONE;
522 let mut mask = exp;
523 let mut power = self;
524 for n in 0..(64 - exp.leading_zeros()) {
525 if n > 0 {
526 power = match power.checked_mul(power) {
527 Some(p) => p,
528 None => return None,
529 };
530 mask >>= 1;
531 }
532 if mask & 1 > 0 {
533 product = match product.checked_mul(power) {
534 Some(p) => p,
535 None => return None,
536 };
537 }
538 }
539 Some(product.normalize())
540 }
541 }
542 }
543
544 /// Trailing zeros removed; zero becomes a plain positive zero.
545 pub fn normalize(self) -> Self {
546 if self.is_zero() {
547 return Decimal::ZERO;
548 }
549 let (mut m, mut scale) = (self.m, self.scale);
550 while scale > 0 && m % 10 == 0 {
551 m /= 10;
552 scale -= 1;
553 }
554 Decimal { m, scale, neg: self.neg }
555 }
556
557 /// The digits with the scale's places, unsigned: `rust_decimal`'s `Display` without its sign.
558 pub fn digits(&self) -> String {
559 let raw = self.m.to_string();
560 let s = self.scale as usize;
561 if s == 0 {
562 return raw;
563 }
564 let padded = if raw.len() <= s { fmt!("{}{}", "0".repeat(s + 1 - raw.len()), raw) } else { raw };
565 let (int, frac) = padded.split_at(padded.len() - s);
566 fmt!("{}.{}", int, frac)
567 }
568
569 /// As `repr` quotes it: an ASCII minus, and none on a zero, which rust_decimal prints unsigned.
570 pub fn text(&self) -> String {
571 if self.neg && !self.is_zero() { fmt!("-{}", self.digits()) } else { self.digits() }
572 }
573
574 /// As a document shows it: a typographic minus.
575 pub fn display(&self) -> String {
576 if self.neg && !self.is_zero() { fmt!("\u{2212}{}", self.digits()) } else { self.digits() }
577 }
578}
579
580// Reduces an exact mantissa at `scale` to 96 bits and at most 28 places, rounding half to even over
581// every discarded digit, as rust_decimal's `rescale`. If rounding carries past 96 bits, one more digit
582// goes, rounded afresh.
583fn reduce(w: W, scale: u32, neg: bool) -> Option<Decimal> {
584 let mut w = w;
585 let mut scale = scale as i64;
586 let (mut last, mut sticky) = (0u32, false);
587 let mut cut = 0u32;
588 while !w_fits96(&w) || scale > MAX_SCALE as i64 {
589 if scale == 0 {
590 return None;
591 }
592 if cut > 0 {
593 sticky |= last != 0;
594 }
595 last = w_div_small(&mut w, 10);
596 cut += 1;
597 scale -= 1;
598 }
599 let mut m = w_to_u128(&w);
600 if cut > 0 && (last > 5 || (last == 5 && (sticky || m & 1 == 1))) {
601 m += 1;
602 if m > MAX_M {
603 if scale == 0 {
604 return None;
605 }
606 let d = (m % 10) as u32;
607 m /= 10;
608 scale -= 1;
609 if d > 5 || (d == 5 && m & 1 == 1) {
610 m += 1;
611 }
612 }
613 }
614 Some(Decimal { m, scale: scale as u32, neg })
615}
616
617// Addition and subtraction exactly as rust_decimal signs them, including the sign of a zero result.
618fn add_sub(a: Decimal, b: Decimal, subtract: bool) -> Option<Decimal> {
619 if a.is_zero() {
620 let mut r = b;
621 if subtract && !b.is_zero() {
622 r.neg = !b.neg;
623 }
624 return Some(r);
625 }
626 if b.is_zero() {
627 return Some(a);
628 }
629 let sub = subtract ^ (a.neg != b.neg);
630 let (x, y) = match aligned(&a, &b) {
631 (Some(x), Some(y)) => (x, y),
632 _ => return None,
633 };
634 let scale = a.scale.max(b.scale);
635 if !sub {
636 return reduce(w_add(&x, &y), scale, a.neg);
637 }
638 // The magnitude is |x - y|; the sign follows the larger operand. An exact zero keeps the sign
639 // rust_decimal's paths give it: the first operand's, except where the first had the larger scale
640 // and did not fit its 32-bit fast path, when the aligned operands were swapped.
641 match w_cmp(&x, &y) {
642 Ordering::Greater => reduce(w_sub(&x, &y), scale, a.neg),
643 Ordering::Less => reduce(w_sub(&y, &x), scale, !a.neg),
644 Ordering::Equal => {
645 let small = a.m >> 32 == 0 && b.m >> 32 == 0 && fast_rescale(&a, &b);
646 let neg = if !small && a.scale > b.scale { sub ^ a.neg } else { a.neg };
647 Some(Decimal { m: 0, scale, neg })
648 }
649 }
650}
651
652// Whether rust_decimal's 32-bit fast path handles the pair: the rescaled operand must stay in 32 bits.
653fn fast_rescale(a: &Decimal, b: &Decimal) -> bool {
654 let (small, by) = if a.scale > b.scale { (b.m, a.scale - b.scale) } else { (a.m, b.scale - a.scale) };
655 if by > 9 {
656 return false;
657 }
658 small * 10u128.pow(by) <= u32::MAX as u128
659}
660
661// The largest power of ten, up to nine, the quotient can take without passing 96 bits, per
662// rust_decimal's `find_scale`, which judges from the top 32 bits and so is conservative.
663fn find_scale(q: u128, scale: i32) -> Option<u32> {
664 const POV: [u128; 8] = [
665 MAX_M / 10, MAX_M / 100, MAX_M / 1_000, MAX_M / 10_000, MAX_M / 100_000, MAX_M / 1_000_000,
666 MAX_M / 10_000_000, MAX_M / 100_000_000,
667 ];
668 let hi = (q >> 64) as u32;
669 let low64 = q as u64;
670 if hi > 429_496_729 {
671 return if scale < 0 { None } else { Some(0) };
672 }
673 let hi_of = |i: usize| (POV[i] >> 64) as u32;
674 let low_of = |i: usize| POV[i] as u64;
675 if scale > MAX_SCALE as i32 - 9 {
676 let x = (MAX_SCALE as i32 - scale) as usize;
677 if x >= 1 && hi < hi_of(x - 1) {
678 return if x as i32 + scale < 0 { None } else { Some(x as u32) };
679 }
680 } else if hi < 4 || (hi == 4 && low64 <= 5_441_186_219_426_131_129) {
681 return Some(9);
682 }
683 let mut x: usize = if hi > 42_949 {
684 if hi > 4_294_967 {
685 if hi > 42_949_672 { 1 } else { 2 }
686 } else if hi > 429_496 {
687 3
688 } else {
689 4
690 }
691 } else if hi > 429 {
692 if hi > 4_294 { 5 } else { 6 }
693 } else if hi > 42 {
694 7
695 } else {
696 8
697 };
698 if hi == hi_of(x - 1) && low64 > low_of(x - 1) {
699 x -= 1;
700 }
701 if x as i32 + scale < 0 { None } else { Some(x as u32) }
702}
703
704// A carry past 96 bits after adding a quotient digit: back one place, rounding half to even with the
705// remainder as a sticky digit.
706fn unscale_from_overflow(q: u128, scale: i32, sticky: bool) -> Option<(u128, i32)> {
707 let scale = scale - 1;
708 if scale < 0 {
709 return None;
710 }
711 let d = (q % 10) as u32;
712 let mut m = q / 10;
713 if d > 5 || (d == 5 && (sticky || m & 1 == 1)) {
714 m += 1;
715 }
716 Some((m, scale))
717}
718
719// rust_decimal's division: the integer quotient, extended by up to nine digits at a time while the
720// remainder is not zero and there is room, rounded half to even at the end, and, when any remainder
721// was met, stripped of trailing zeros.
722fn div(a: Decimal, b: Decimal) -> Option<Decimal> {
723 let neg = a.neg ^ b.neg;
724 let mut scale = a.scale as i32 - b.scale as i32;
725 let d = b.m;
726 let mut q = a.m / d;
727 let mut r = a.m % d;
728 let mut unscale = false;
729 loop {
730 let mut power = 0u32;
731 if r == 0 {
732 if scale >= 0 {
733 break;
734 }
735 power = 9.min((-scale) as u32);
736 } else {
737 unscale = true;
738 let full = if scale == MAX_SCALE as i32 {
739 true
740 } else {
741 match find_scale(q, scale) {
742 Some(s) => {
743 power = s;
744 s == 0
745 }
746 None => return None,
747 }
748 };
749 if full {
750 let twice = r * 2;
751 if twice > d || (twice == d && q & 1 == 1) {
752 q += 1;
753 if q > MAX_M {
754 match unscale_from_overflow(q, scale, true) {
755 Some((m, s)) => { q = m; scale = s; }
756 None => return None,
757 }
758 }
759 }
760 break;
761 }
762 let p = 10u128.pow(power);
763 scale += power as i32;
764 q = match q.checked_mul(p) {
765 Some(x) if x <= MAX_M => x,
766 _ => return None,
767 };
768 let rs = r * p;
769 q += rs / d;
770 r = rs % d;
771 if q > MAX_M {
772 match unscale_from_overflow(q, scale, r != 0) {
773 Some((m, s)) => { q = m; scale = s; }
774 None => return None,
775 }
776 break;
777 }
778 continue;
779 }
780 let p = 10u128.pow(power);
781 scale += power as i32;
782 q = match q.checked_mul(p) {
783 Some(x) if x <= MAX_M => x,
784 _ => return None,
785 };
786 }
787 // rust_decimal's `unscale`: eight zeros at a time only while the low word is clear, then at most
788 // one strip each of four, two and one, so a long run of zeros can survive.
789 if unscale {
790 while (q as u32) == 0 && scale >= 8 && q % 100_000_000 == 0 {
791 q /= 100_000_000;
792 scale -= 8;
793 }
794 for (mask, k, p) in [(0xfu128, 4, 10_000u128), (0x3, 2, 100), (0x1, 1, 10)] {
795 if q & mask == 0 && scale >= k && q % p == 0 {
796 q /= p;
797 scale -= k;
798 }
799 }
800 }
801 if scale < 0 {
802 return None;
803 }
804 Some(Decimal { m: q, scale: scale as u32, neg })
805}