affine/
ratio.rs

1// Copyright 2026 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use zr::static_assert;
6
7#[derive(Debug, Clone, Copy, PartialEq, Eq)]
8pub enum Exact {
9    No,
10    Yes,
11}
12
13/// Rounding Behaviors used when scaling.
14///
15/// | val  | N   | D   | Down | Up  | TowardsZero | AwayFromZero |
16/// | :--- | :-- | :-- | :--- | :-- | :---------- | :----------- |
17/// | 7    | 1   | 2   | 3    | 4   | 3           | 4            |
18/// | -7   | 1   | 2   | -4   | -3  | -3          | -4           |
19pub struct Round;
20impl Round {
21    pub const DOWN: u8 = 0;
22    pub const UP: u8 = 1;
23    pub const TOWARDS_ZERO: u8 = 2;
24    pub const AWAY_FROM_ZERO: u8 = 3;
25}
26
27#[repr(C)]
28#[derive(Debug, Clone, Copy, PartialEq, Eq)]
29pub struct Ratio {
30    numerator: u32,
31    denominator: u32,
32}
33
34static_assert!(core::mem::size_of::<Ratio>() == 8);
35static_assert!(core::mem::align_of::<Ratio>() == 4);
36
37impl Default for Ratio {
38    fn default() -> Self {
39        Ratio { numerator: 1, denominator: 1 }
40    }
41}
42
43impl Ratio {
44    pub const OVERFLOW: i64 = i64::MAX;
45    pub const UNDERFLOW: i64 = i64::MIN;
46
47    pub fn new(numerator: u32, denominator: u32) -> Self {
48        debug_assert!(denominator != 0);
49        Ratio { numerator, denominator }
50    }
51
52    pub fn numerator(&self) -> u32 {
53        self.numerator
54    }
55
56    pub fn denominator(&self) -> u32 {
57        self.denominator
58    }
59
60    pub fn invertible(&self) -> bool {
61        self.numerator != 0
62    }
63
64    pub fn inverse(&self) -> Self {
65        debug_assert!(self.invertible());
66        Ratio { numerator: self.denominator, denominator: self.numerator }
67    }
68
69    /// Reduces the ratio of numerator/denominator in-place (32-bit).
70    pub fn reduce_u32(numerator: &mut u32, denominator: &mut u32) {
71        assert!(*denominator != 0);
72        if *numerator == 0 {
73            *denominator = 1;
74            return;
75        }
76        let gcd = binary_gcd(*numerator as u64, *denominator as u64) as u32;
77        *numerator /= gcd;
78        *denominator /= gcd;
79    }
80
81    /// Reduces the ratio of numerator/denominator in-place (64-bit).
82    pub fn reduce_u64(numerator: &mut u64, denominator: &mut u64) {
83        assert!(*denominator != 0);
84        if *numerator == 0 {
85            *denominator = 1;
86            return;
87        }
88        let gcd = binary_gcd(*numerator, *denominator);
89        *numerator /= gcd;
90        *denominator /= gcd;
91    }
92
93    /// Reduces the ratio instance in-place.
94    pub fn reduce(&mut self) {
95        Self::reduce_u32(&mut self.numerator, &mut self.denominator);
96    }
97
98    /// Produces the product of two ratios.
99    ///
100    /// If `exact` is `Exact::Yes`, this panics on loss of precision.
101    /// If `exact` is `Exact::No`, it attempts to find the best 32-bit approximation.
102    pub fn product_raw(
103        a_numerator: u32,
104        a_denominator: u32,
105        b_numerator: u32,
106        b_denominator: u32,
107        exact: Exact,
108    ) -> (u32, u32) {
109        let mut numerator = a_numerator as u64 * b_numerator as u64;
110        let mut denominator = a_denominator as u64 * b_denominator as u64;
111
112        Self::reduce_u64(&mut numerator, &mut denominator);
113
114        if numerator > u32::MAX as u64 || denominator > u32::MAX as u64 {
115            assert!(exact == Exact::No, "Precision loss in exact Ratio::product");
116
117            // Try to find the best approximation of the ratio that we can. Our
118            // approach is as follows. Figure out the number of bits to the right
119            // we need to shift the numerator and denominator, rounding up or down
120            // in the process, such that the result can be reduced to fit into 32
121            // bits.
122            //
123            // This approach tends to beat out a just-shift-until-it-fits approach,
124            // as well as an always-shift-then-reduce approach, but _none_ of these
125            // approaches always finds the best solution.
126            //
127            // TODO(johngro): figure out if it is reasonable to actually compute
128            // the best solution. Alternatively, consider implementing a "just
129            // shift until it fits" solution if the approximate results are good
130            // enough.
131            for i in 1..=32 {
132                // Produce a version of the numerator and denominator which have
133                // each been divided by 2^i, rounding up/down as appropriate
134                // (instead of truncating).
135                let rounded_numerator = (numerator + (1u64 << (i - 1))) >> i;
136                let rounded_denominator = (denominator + (1u64 << (i - 1))) >> i;
137
138                if rounded_denominator == 0 {
139                    // Product is larger than we can represent. Return the largest value we
140                    // can represent.
141                    return (u32::MAX, 1);
142                }
143
144                if rounded_numerator == 0 {
145                    // Product is smaller than we can represent. Return 0.
146                    return (0, 1);
147                }
148
149                let mut rn = rounded_numerator;
150                let mut rd = rounded_denominator;
151                Self::reduce_u64(&mut rn, &mut rd);
152                if rn <= u32::MAX as u64 && rd <= u32::MAX as u64 {
153                    return (rn as u32, rd as u32);
154                }
155            }
156            // Fallback (should be unreachable)
157            return (numerator as u32, denominator as u32);
158        }
159
160        (numerator as u32, denominator as u32)
161    }
162
163    pub fn product(a: Ratio, b: Ratio, exact: Exact) -> Ratio {
164        let (n, d) =
165            Self::product_raw(a.numerator, a.denominator, b.numerator, b.denominator, exact);
166        Ratio { numerator: n, denominator: d }
167    }
168
169    /// Scales an `i64` value by the ratio of numerator/denominator.
170    ///
171    /// Returns a saturated value (`OVERFLOW` or `UNDERFLOW`) on overflow/underflow.
172    /// The rounding behavior is determined by the `ROUND` const generic.
173    pub fn scale_with_round<const ROUND: u8>(value: i64, numerator: u32, denominator: u32) -> i64 {
174        assert!(denominator != 0);
175
176        if value >= 0 {
177            // LIMIT == 0x7FFFFFFFFFFFFFFF
178            let limit = i64::MAX as u64;
179            let round_up = match ROUND {
180                Round::UP | Round::AWAY_FROM_ZERO => true,
181                _ => false,
182            };
183            let scaled = scale_unsigned(value as u64, numerator, denominator, round_up, limit);
184            scaled as i64
185        } else {
186            // LIMIT == 0x8000000000000000
187            //
188            // Note:  We are attempting to pass the unsigned distance from zero into
189            // our ScaleUInt64 function.  In the case of negative numbers, we pass
190            // the twos compliment into the scale function, and then flip the sign
191            // again on the way out.
192            //
193            // We are taking the advantage of the fact that the twos compliment of
194            // MIN is itself for any signed integer type, and that casting this
195            // value to an unsigned integer of the same size properly produces the
196            // original value's distance from zero.  Clamping the limit to the
197            // distance of MIN from zero means that saturated results will likewise
198            // get properly flipped back to MIN during the return.
199            //
200            let limit = 0x8000000000000000u64; // i64::MIN.unsigned_abs()
201            let round_up = match ROUND {
202                Round::DOWN | Round::AWAY_FROM_ZERO => true,
203                _ => false,
204            };
205            let scaled =
206                scale_unsigned(value.unsigned_abs(), numerator, denominator, round_up, limit);
207            if scaled == 0x8000000000000000 { i64::MIN } else { -(scaled as i64) }
208        }
209    }
210
211    /// Scales an `i64` value by this ratio.
212    ///
213    /// Returns a saturated value (`OVERFLOW` or `UNDERFLOW`) on overflow/underflow.
214    /// The rounding behavior is determined by the `ROUND` const generic.
215    pub fn scale<const ROUND: u8>(&self, value: i64) -> i64 {
216        Self::scale_with_round::<ROUND>(value, self.numerator, self.denominator)
217    }
218}
219
220// Calculates the greatest common denominator (factor) of two values.
221fn binary_gcd(mut a: u64, mut b: u64) -> u64 {
222    debug_assert!(a != 0 && b != 0);
223
224    // Remove and count the common factors of 2.
225    let mut twos = 0;
226    while ((a | b) & 1) == 0 {
227        a >>= 1;
228        b >>= 1;
229        twos += 1;
230    }
231
232    // Get rid of the non-common factors of 2 in a. a is non-zero, so this
233    // terminates.
234    while (a & 1) == 0 {
235        a >>= 1;
236    }
237
238    loop {
239        // Get rid of the non-common factors of 2 in b. b is non-zero, so this
240        // terminates.
241        while (b & 1) == 0 {
242            b >>= 1;
243        }
244
245        // Apply the Euclid subtraction method.
246        if a > b {
247            core::mem::swap(&mut a, &mut b);
248        }
249
250        b -= a;
251        if b == 0 {
252            break;
253        }
254    }
255
256    // Multiply in the common factors of two.
257    a << twos
258}
259
260// Scales a uint64_t value by the ratio of two uint32_t values. If round_up is
261// true, the result is rounded up rather than down. Saturates at `limit` on overflow.
262fn scale_unsigned(value: u64, numerator: u32, denominator: u32, round_up: bool, limit: u64) -> u64 {
263    let prod = (value as u128) * (numerator as u128);
264    let q = prod / (denominator as u128);
265    let r = prod % (denominator as u128);
266
267    if q >= (limit as u128) {
268        return limit;
269    }
270
271    let mut result = q as u64;
272    if round_up && r != 0 {
273        result += 1;
274        if result >= limit {
275            return limit;
276        }
277    }
278    result
279}
280
281// Operators
282
283impl core::ops::Mul for Ratio {
284    type Output = Self;
285    fn mul(self, rhs: Self) -> Self::Output {
286        Ratio::product(self, rhs, Exact::Yes)
287    }
288}
289
290impl core::ops::Div for Ratio {
291    type Output = Self;
292    fn div(self, rhs: Self) -> Self::Output {
293        self * rhs.inverse()
294    }
295}
296
297impl core::ops::Mul<i64> for Ratio {
298    type Output = i64;
299    fn mul(self, rhs: i64) -> Self::Output {
300        self.scale::<{ Round::DOWN }>(rhs)
301    }
302}
303
304impl core::ops::Mul<Ratio> for i64 {
305    type Output = i64;
306    fn mul(self, rhs: Ratio) -> Self::Output {
307        rhs.scale::<{ Round::DOWN }>(self)
308    }
309}
310
311impl core::ops::Div<Ratio> for i64 {
312    type Output = i64;
313    fn div(self, rhs: Ratio) -> Self::Output {
314        rhs.inverse().scale::<{ Round::DOWN }>(self)
315    }
316}
317
318#[cfg(test)]
319mod tests {
320    use super::*;
321
322    #[test]
323    fn test_construction() {
324        let valid_vectors = [(0, 1), (1, 1), (23, 41)];
325        for &(n, d) in &valid_vectors {
326            let r = Ratio::new(n, d);
327            assert_eq!(r.numerator(), n);
328            assert_eq!(r.denominator(), d);
329        }
330
331        // Ratio::default() produces 1/1
332        let r = Ratio::default();
333        assert_eq!(r.numerator(), 1);
334        assert_eq!(r.denominator(), 1);
335
336        // Reduction is NOT automatically performed
337        let r = Ratio::new(9, 21);
338        assert_eq!(r.numerator(), 9);
339        assert_eq!(r.denominator(), 21);
340    }
341
342    #[test]
343    fn test_reduction_32() {
344        let mut vectors = [
345            (1, 1, 1, 1),
346            (10, 10, 1, 1),
347            (10, 2, 5, 1),
348            (0, 1, 0, 1),
349            (0, 500, 0, 1),
350            (48000, 44100, 160, 147),
351            (44100, 48000, 147, 160),
352            (1000007, 1000000, 1000007, 1000000),
353        ];
354
355        for v in &mut vectors {
356            let mut n = v.0;
357            let mut d = v.1;
358            Ratio::reduce_u32(&mut n, &mut d);
359            assert_eq!((n, d), (v.2, v.3));
360
361            let mut r = Ratio::new(v.0, v.1);
362            r.reduce();
363            assert_eq!((r.numerator(), r.denominator()), (v.2, v.3));
364        }
365    }
366
367    #[test]
368    fn test_reduction_64() {
369        let mut vectors = [
370            (1, 1, 1, 1),
371            (10, 10, 1, 1),
372            (10, 2, 5, 1),
373            (0, 1, 0, 1),
374            (0, 500, 0, 1),
375            (48000, 44100, 160, 147),
376            (44100, 48000, 147, 160),
377            (1000007, 1000000, 1000007, 1000000),
378            (48000336000, 44100000000, 1000007, 918750),
379        ];
380
381        for v in &mut vectors {
382            let mut n = v.0;
383            let mut d = v.1;
384            Ratio::reduce_u64(&mut n, &mut d);
385            assert_eq!((n, d), (v.2, v.3));
386        }
387    }
388
389    #[test]
390    fn test_product() {
391        struct TestVector {
392            a_n: u32,
393            a_d: u32,
394            b_n: u32,
395            b_d: u32,
396            expected_n: u32,
397            expected_d: u32,
398            exact: Exact,
399        }
400
401        let test_vectors = [
402            TestVector {
403                a_n: 1,
404                a_d: 1,
405                b_n: 1,
406                b_d: 1,
407                expected_n: 1,
408                expected_d: 1,
409                exact: Exact::Yes,
410            },
411            TestVector {
412                a_n: 0,
413                a_d: 1,
414                b_n: 1,
415                b_d: 1,
416                expected_n: 0,
417                expected_d: 1,
418                exact: Exact::Yes,
419            },
420            TestVector {
421                a_n: 0,
422                a_d: 500,
423                b_n: 1,
424                b_d: 1,
425                expected_n: 0,
426                expected_d: 1,
427                exact: Exact::Yes,
428            },
429            TestVector {
430                a_n: 3,
431                a_d: 4,
432                b_n: 5,
433                b_d: 9,
434                expected_n: 5,
435                expected_d: 12,
436                exact: Exact::Yes,
437            },
438            TestVector {
439                a_n: 48000,
440                a_d: 44100,
441                b_n: 1000007,
442                b_d: 1000000,
443                expected_n: 1000007,
444                expected_d: 918750,
445                exact: Exact::Yes,
446            },
447            TestVector {
448                a_n: 3465653567,
449                a_d: 2327655023,
450                b_n: 1291540343,
451                b_d: 3698423317,
452                expected_n: 317609835,
453                expected_d: 610852072,
454                exact: Exact::No,
455            },
456            TestVector {
457                a_n: 0xFFFFFFFF,
458                a_d: 1,
459                b_n: 0xFFFFFFFF,
460                b_d: 1,
461                expected_n: 0xFFFFFFFF,
462                expected_d: 1,
463                exact: Exact::No,
464            },
465            TestVector {
466                a_n: 1,
467                a_d: 0xFFFFFFFF,
468                b_n: 1,
469                b_d: 0xFFFFFFFF,
470                expected_n: 0,
471                expected_d: 1,
472                exact: Exact::No,
473            },
474        ];
475
476        for v in &test_vectors {
477            let a = Ratio::new(v.a_n, v.a_d);
478            let b = Ratio::new(v.b_n, v.b_d);
479
480            let res = Ratio::product(a, b, v.exact);
481            assert_eq!(
482                (res.numerator(), res.denominator()),
483                (v.expected_n, v.expected_d),
484                "Expected {}/{} * {}/{} to produce {}/{}; got {}/{} instead (static)",
485                v.a_n,
486                v.a_d,
487                v.b_n,
488                v.b_d,
489                v.expected_n,
490                v.expected_d,
491                res.numerator(),
492                res.denominator()
493            );
494
495            let res = Ratio::product(b, a, v.exact);
496            assert_eq!(
497                (res.numerator(), res.denominator()),
498                (v.expected_n, v.expected_d),
499                "Expected {}/{} * {}/{} to produce {}/{}; got {}/{} instead (commutative static)",
500                v.b_n,
501                v.b_d,
502                v.a_n,
503                v.a_d,
504                v.expected_n,
505                v.expected_d,
506                res.numerator(),
507                res.denominator()
508            );
509
510            if v.exact == Exact::Yes {
511                let res = a * b;
512                assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
513
514                let res = b * a;
515                assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
516
517                if b.invertible() {
518                    let res = a / b.inverse();
519                    assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
520                }
521
522                if a.invertible() {
523                    let res = b / a.inverse();
524                    assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
525                }
526            }
527        }
528    }
529
530    #[test]
531    fn test_product_raw() {
532        struct TestVector {
533            a_n: u32,
534            a_d: u32,
535            b_n: u32,
536            b_d: u32,
537            expected_n: u32,
538            expected_d: u32,
539            exact: Exact,
540        }
541
542        let test_vectors = [
543            TestVector {
544                a_n: 1,
545                a_d: 1,
546                b_n: 1,
547                b_d: 1,
548                expected_n: 1,
549                expected_d: 1,
550                exact: Exact::Yes,
551            },
552            TestVector {
553                a_n: 0,
554                a_d: 1,
555                b_n: 1,
556                b_d: 1,
557                expected_n: 0,
558                expected_d: 1,
559                exact: Exact::Yes,
560            },
561            TestVector {
562                a_n: 0,
563                a_d: 500,
564                b_n: 1,
565                b_d: 1,
566                expected_n: 0,
567                expected_d: 1,
568                exact: Exact::Yes,
569            },
570            TestVector {
571                a_n: 3,
572                a_d: 4,
573                b_n: 5,
574                b_d: 9,
575                expected_n: 5,
576                expected_d: 12,
577                exact: Exact::Yes,
578            },
579            TestVector {
580                a_n: 48000,
581                a_d: 44100,
582                b_n: 1000007,
583                b_d: 1000000,
584                expected_n: 1000007,
585                expected_d: 918750,
586                exact: Exact::Yes,
587            },
588            TestVector {
589                a_n: 3465653567,
590                a_d: 2327655023,
591                b_n: 1291540343,
592                b_d: 3698423317,
593                expected_n: 317609835,
594                expected_d: 610852072,
595                exact: Exact::No,
596            },
597            TestVector {
598                a_n: 0xFFFFFFFF,
599                a_d: 1,
600                b_n: 0xFFFFFFFF,
601                b_d: 1,
602                expected_n: 0xFFFFFFFF,
603                expected_d: 1,
604                exact: Exact::No,
605            },
606            TestVector {
607                a_n: 1,
608                a_d: 0xFFFFFFFF,
609                b_n: 1,
610                b_d: 0xFFFFFFFF,
611                expected_n: 0,
612                expected_d: 1,
613                exact: Exact::No,
614            },
615        ];
616
617        for v in &test_vectors {
618            let res = Ratio::product_raw(v.a_n, v.a_d, v.b_n, v.b_d, v.exact);
619            assert_eq!(
620                res,
621                (v.expected_n, v.expected_d),
622                "Expected {}/{} * {}/{} to produce {}/{}; got {}/{} instead",
623                v.a_n,
624                v.a_d,
625                v.b_n,
626                v.b_d,
627                v.expected_n,
628                v.expected_d,
629                res.0,
630                res.1
631            );
632        }
633    }
634
635    fn test_scale_helper<const ROUND: u8>() {
636        struct TestVector {
637            val: i64,
638            n: u32,
639            d: u32,
640            expected: i64,
641            fractional_result: bool,
642        }
643
644        let test_vectors = [
645            TestVector { val: 0, n: 0, d: 1, expected: 0, fractional_result: false },
646            TestVector { val: 1234567890, n: 0, d: 1, expected: 0, fractional_result: false },
647            TestVector { val: 0, n: 1, d: 1, expected: 0, fractional_result: false },
648            TestVector {
649                val: 1234567890,
650                n: 1,
651                d: 1,
652                expected: 1234567890,
653                fractional_result: false,
654            },
655            TestVector { val: 198, n: 48000, d: 44100, expected: 215, fractional_result: true },
656            TestVector { val: -198, n: 48000, d: 44100, expected: -216, fractional_result: true },
657            TestVector {
658                val: 49 * 198,
659                n: 48000,
660                d: 44100,
661                expected: 10560,
662                fractional_result: false,
663            },
664            TestVector {
665                val: -(49 * 198),
666                n: 48000,
667                d: 44100,
668                expected: -10560,
669                fractional_result: false,
670            },
671            TestVector {
672                val: (49 * 198) + 1,
673                n: 48000,
674                d: 44100,
675                expected: 10561,
676                fractional_result: true,
677            },
678            TestVector {
679                val: -((49 * 198) + 1),
680                n: 48000,
681                d: 44100,
682                expected: -10562,
683                fractional_result: true,
684            },
685            TestVector {
686                val: 0x1517ffffeae80,
687                n: 0xbebc200,
688                d: 0x33333333,
689                expected: 0x4e94914f0000,
690                fractional_result: false,
691            },
692            TestVector {
693                val: -0x1517ffffeae80,
694                n: 0xbebc200,
695                d: 0x33333333,
696                expected: -0x4e94914f0000,
697                fractional_result: false,
698            },
699            TestVector {
700                val: i64::MAX,
701                n: 1000001,
702                d: 1000000,
703                expected: Ratio::OVERFLOW,
704                fractional_result: false,
705            },
706            TestVector {
707                val: i64::MIN,
708                n: 1000001,
709                d: 1000000,
710                expected: Ratio::UNDERFLOW,
711                fractional_result: false,
712            },
713            TestVector {
714                val: -0x2000000000000001,
715                n: 4,
716                d: 1,
717                expected: Ratio::UNDERFLOW,
718                fractional_result: false,
719            },
720        ];
721
722        for v in &test_vectors {
723            let res_static = Ratio::scale_with_round::<ROUND>(v.val, v.n, v.d);
724            let r = Ratio::new(v.n, v.d);
725            let res_inst = r.scale::<ROUND>(v.val);
726
727            let adjusted_expected = if !v.fractional_result || ROUND == Round::DOWN {
728                v.expected
729            } else if v.val >= 0 {
730                if ROUND == Round::TOWARDS_ZERO { v.expected } else { v.expected + 1 }
731            } else {
732                if ROUND == Round::AWAY_FROM_ZERO { v.expected } else { v.expected + 1 }
733            };
734
735            assert_eq!(
736                res_static, adjusted_expected,
737                "Static: Expected {} * {}/{} to produce {}; got {}",
738                v.val, v.n, v.d, adjusted_expected, res_static
739            );
740            assert_eq!(
741                res_inst, adjusted_expected,
742                "Instanced: Expected {} * {}/{} to produce {}; got {}",
743                v.val, v.n, v.d, adjusted_expected, res_inst
744            );
745
746            if ROUND == Round::DOWN {
747                let res_op1 = r * v.val;
748                let res_op2 = v.val * r;
749                assert_eq!(res_op1, adjusted_expected);
750                assert_eq!(res_op2, adjusted_expected);
751
752                if r.invertible() {
753                    let res_op3 = v.val / r.inverse();
754                    assert_eq!(res_op3, adjusted_expected);
755                }
756            }
757        }
758    }
759
760    #[test]
761    fn test_scale_round_down() {
762        test_scale_helper::<{ Round::DOWN }>();
763    }
764    #[test]
765    fn test_scale_round_up() {
766        test_scale_helper::<{ Round::UP }>();
767    }
768    #[test]
769    fn test_scale_round_towards_zero() {
770        test_scale_helper::<{ Round::TOWARDS_ZERO }>();
771    }
772    #[test]
773    fn test_scale_round_away_from_zero() {
774        test_scale_helper::<{ Round::AWAY_FROM_ZERO }>();
775    }
776
777    #[test]
778    fn test_inverse() {
779        let test_vectors = [(1, 1), (123456, 987654)];
780        for &(n, d) in &test_vectors {
781            let r = Ratio::new(n, d);
782            let inv = r.inverse();
783            assert_eq!(inv.numerator(), d);
784            assert_eq!(inv.denominator(), n);
785        }
786
787        let r = Ratio::new(0, 1);
788        assert!(!r.invertible());
789    }
790}
affine/ratio.rs

affine/
ratio.rs
