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 zerocopy::{FromBytes, Immutable, IntoBytes};
6use zr::static_assert;
7
8#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub enum Exact {
10    No,
11    Yes,
12}
13
14/// Rounding Behaviors used when scaling.
15///
16/// | val  | N   | D   | Down | Up  | TowardsZero | AwayFromZero |
17/// | :--- | :-- | :-- | :--- | :-- | :---------- | :----------- |
18/// | 7    | 1   | 2   | 3    | 4   | 3           | 4            |
19/// | -7   | 1   | 2   | -4   | -3  | -3          | -4           |
20pub struct Round;
21impl Round {
22    pub const DOWN: u8 = 0;
23    pub const UP: u8 = 1;
24    pub const TOWARDS_ZERO: u8 = 2;
25    pub const AWAY_FROM_ZERO: u8 = 3;
26}
27
28#[repr(C)]
29#[derive(Debug, Clone, Copy, PartialEq, Eq, FromBytes, IntoBytes, Immutable)]
30pub struct Ratio {
31    numerator: u32,
32    denominator: u32,
33}
34
35static_assert!(core::mem::size_of::<Ratio>() == 8);
36static_assert!(core::mem::align_of::<Ratio>() == 4);
37
38impl Default for Ratio {
39    fn default() -> Self {
40        Ratio { numerator: 1, denominator: 1 }
41    }
42}
43
44impl Ratio {
45    pub const OVERFLOW: i64 = i64::MAX;
46    pub const UNDERFLOW: i64 = i64::MIN;
47
48    pub fn new(numerator: u32, denominator: u32) -> Self {
49        debug_assert!(denominator != 0);
50        Ratio { numerator, denominator }
51    }
52
53    pub fn numerator(&self) -> u32 {
54        self.numerator
55    }
56
57    pub fn denominator(&self) -> u32 {
58        self.denominator
59    }
60
61    pub fn invertible(&self) -> bool {
62        self.numerator != 0
63    }
64
65    pub fn inverse(&self) -> Self {
66        debug_assert!(self.invertible());
67        Ratio { numerator: self.denominator, denominator: self.numerator }
68    }
69
70    /// Reduces the ratio of numerator/denominator in-place (32-bit).
71    pub fn reduce_u32(numerator: &mut u32, denominator: &mut u32) {
72        assert!(*denominator != 0);
73        if *numerator == 0 {
74            *denominator = 1;
75            return;
76        }
77        let gcd = binary_gcd(*numerator as u64, *denominator as u64) as u32;
78        *numerator /= gcd;
79        *denominator /= gcd;
80    }
81
82    /// Reduces the ratio of numerator/denominator in-place (64-bit).
83    pub fn reduce_u64(numerator: &mut u64, denominator: &mut u64) {
84        assert!(*denominator != 0);
85        if *numerator == 0 {
86            *denominator = 1;
87            return;
88        }
89        let gcd = binary_gcd(*numerator, *denominator);
90        *numerator /= gcd;
91        *denominator /= gcd;
92    }
93
94    /// Reduces the ratio instance in-place.
95    pub fn reduce(&mut self) {
96        Self::reduce_u32(&mut self.numerator, &mut self.denominator);
97    }
98
99    /// Produces the product of two ratios.
100    ///
101    /// If `exact` is `Exact::Yes`, this panics on loss of precision.
102    /// If `exact` is `Exact::No`, it attempts to find the best 32-bit approximation.
103    pub fn product_raw(
104        a_numerator: u32,
105        a_denominator: u32,
106        b_numerator: u32,
107        b_denominator: u32,
108        exact: Exact,
109    ) -> (u32, u32) {
110        let mut numerator = a_numerator as u64 * b_numerator as u64;
111        let mut denominator = a_denominator as u64 * b_denominator as u64;
112
113        Self::reduce_u64(&mut numerator, &mut denominator);
114
115        if numerator > u32::MAX as u64 || denominator > u32::MAX as u64 {
116            assert!(exact == Exact::No, "Precision loss in exact Ratio::product");
117
118            // Try to find the best approximation of the ratio that we can. Our
119            // approach is as follows. Figure out the number of bits to the right
120            // we need to shift the numerator and denominator, rounding up or down
121            // in the process, such that the result can be reduced to fit into 32
122            // bits.
123            //
124            // This approach tends to beat out a just-shift-until-it-fits approach,
125            // as well as an always-shift-then-reduce approach, but _none_ of these
126            // approaches always finds the best solution.
127            //
128            // TODO(johngro): figure out if it is reasonable to actually compute
129            // the best solution. Alternatively, consider implementing a "just
130            // shift until it fits" solution if the approximate results are good
131            // enough.
132            for i in 1..=32 {
133                // Produce a version of the numerator and denominator which have
134                // each been divided by 2^i, rounding up/down as appropriate
135                // (instead of truncating).
136                let rounded_numerator = (numerator + (1u64 << (i - 1))) >> i;
137                let rounded_denominator = (denominator + (1u64 << (i - 1))) >> i;
138
139                if rounded_denominator == 0 {
140                    // Product is larger than we can represent. Return the largest value we
141                    // can represent.
142                    return (u32::MAX, 1);
143                }
144
145                if rounded_numerator == 0 {
146                    // Product is smaller than we can represent. Return 0.
147                    return (0, 1);
148                }
149
150                let mut rn = rounded_numerator;
151                let mut rd = rounded_denominator;
152                Self::reduce_u64(&mut rn, &mut rd);
153                if rn <= u32::MAX as u64 && rd <= u32::MAX as u64 {
154                    return (rn as u32, rd as u32);
155                }
156            }
157            // Fallback (should be unreachable)
158            return (numerator as u32, denominator as u32);
159        }
160
161        (numerator as u32, denominator as u32)
162    }
163
164    pub fn product(a: Ratio, b: Ratio, exact: Exact) -> Ratio {
165        let (n, d) =
166            Self::product_raw(a.numerator, a.denominator, b.numerator, b.denominator, exact);
167        Ratio { numerator: n, denominator: d }
168    }
169
170    /// Scales an `i64` value by the ratio of numerator/denominator.
171    ///
172    /// Returns a saturated value (`OVERFLOW` or `UNDERFLOW`) on overflow/underflow.
173    /// The rounding behavior is determined by the `ROUND` const generic.
174    pub fn scale_with_round<const ROUND: u8>(value: i64, numerator: u32, denominator: u32) -> i64 {
175        assert!(denominator != 0);
176
177        if value >= 0 {
178            const LIMIT: u64 = i64::MAX as u64; // 0x7FFFFFFFFFFFFFFF
179            let value = value as u64;
180            let scaled = match ROUND {
181                Round::UP | Round::AWAY_FROM_ZERO => {
182                    scale_unsigned::<true, LIMIT>(value, numerator, denominator)
183                }
184                _ => scale_unsigned::<false, LIMIT>(value, numerator, denominator),
185            };
186            scaled as i64
187        } else {
188            // LIMIT == 0x8000000000000000
189            //
190            // Note:  We are attempting to pass the unsigned distance from zero into
191            // our ScaleUInt64 function.  In the case of negative numbers, we pass
192            // the twos compliment into the scale function, and then flip the sign
193            // again on the way out.
194            //
195            // We are taking the advantage of the fact that the twos compliment of
196            // MIN is itself for any signed integer type, and that casting this
197            // value to an unsigned integer of the same size properly produces the
198            // original value's distance from zero.  Clamping the limit to the
199            // distance of MIN from zero means that saturated results will likewise
200            // get properly flipped back to MIN during the return.
201            //
202            const LIMIT: u64 = 0x8000000000000000; // i64::MIN.unsigned_abs()
203            let value = value.unsigned_abs();
204            let scaled = match ROUND {
205                Round::DOWN | Round::AWAY_FROM_ZERO => {
206                    scale_unsigned::<true, LIMIT>(value, numerator, denominator)
207                }
208                _ => scale_unsigned::<false, LIMIT>(value, numerator, denominator),
209            };
210            if scaled == LIMIT { i64::MIN } else { -(scaled as i64) }
211        }
212    }
213
214    /// Scales an `i64` value by this ratio.
215    ///
216    /// Returns a saturated value (`OVERFLOW` or `UNDERFLOW`) on overflow/underflow.
217    /// The rounding behavior is determined by the `ROUND` const generic.
218    pub fn scale<const ROUND: u8>(&self, value: i64) -> i64 {
219        Self::scale_with_round::<ROUND>(value, self.numerator, self.denominator)
220    }
221}
222
223// Calculates the greatest common denominator (factor) of two values.
224fn binary_gcd(mut a: u64, mut b: u64) -> u64 {
225    debug_assert!(a != 0 && b != 0);
226
227    // Remove and count the common factors of 2.
228    let mut twos = 0;
229    while ((a | b) & 1) == 0 {
230        a >>= 1;
231        b >>= 1;
232        twos += 1;
233    }
234
235    // Get rid of the non-common factors of 2 in a. a is non-zero, so this
236    // terminates.
237    while (a & 1) == 0 {
238        a >>= 1;
239    }
240
241    loop {
242        // Get rid of the non-common factors of 2 in b. b is non-zero, so this
243        // terminates.
244        while (b & 1) == 0 {
245            b >>= 1;
246        }
247
248        // Apply the Euclid subtraction method.
249        if a > b {
250            core::mem::swap(&mut a, &mut b);
251        }
252
253        b -= a;
254        if b == 0 {
255            break;
256        }
257    }
258
259    // Multiply in the common factors of two.
260    a << twos
261}
262
263// Scales a u64 value by the ratio of two u32 values. If ROUND_UP is true, the
264// result is rounded up rather than down. Saturates at LIMIT on overflow.
265fn scale_unsigned<const ROUND_UP: bool, const LIMIT: u64>(
266    value: u64,
267    numerator: u32,
268    denominator: u32,
269) -> u64 {
270    let numerator = numerator as u64;
271    let denominator = denominator as u64;
272    const LOW_32_BITS: u64 = u32::MAX as u64;
273
274    // high and low are the product of the numerator and the high and low halves
275    // (respectively) of value, with the high end of low moved into the low end
276    // of high.
277    let low_product = numerator * (value & LOW_32_BITS);
278    let high = numerator * (value >> 32) + (low_product >> 32);
279    let mut low = low_product & LOW_32_BITS;
280
281    // Ignoring overflow and remainder, the result we want is:
282    // ((high << 32) + low) / denominator.
283
284    // Compute the divmod of high/D
285    let high_q = high / denominator;
286    let high_r = high % denominator;
287
288    // If high_q is larger than the overflow limit, then we can just get out now.
289    // The overflow limit will be different depending on whether we are scaling
290    // a non-negative number (0x7FFFFFFF) or a negative number (0x80000000)
291    if high_q > LIMIT >> 32 {
292        return LIMIT;
293    }
294
295    // The remainder of high/D are the high bits of low. Or them in, and do the
296    // divmod for the low portion
297    low |= high_r << 32;
298
299    let low_q = low / denominator;
300    let low_r = low % denominator;
301    let result = (high_q << 32) | low_q;
302    if result >= LIMIT {
303        return LIMIT;
304    }
305
306    // `result` is strictly less than LIMIT, so `result + 1` neither overflows
307    // nor exceeds LIMIT; if it is exactly LIMIT, that is the saturated value we
308    // would have returned anyway.
309    if ROUND_UP && low_r != 0 {
310        return result + 1;
311    }
312
313    result
314}
315
316// Operators
317
318impl core::ops::Mul for Ratio {
319    type Output = Self;
320    fn mul(self, rhs: Self) -> Self::Output {
321        Ratio::product(self, rhs, Exact::Yes)
322    }
323}
324
325impl core::ops::Div for Ratio {
326    type Output = Self;
327    fn div(self, rhs: Self) -> Self::Output {
328        self * rhs.inverse()
329    }
330}
331
332impl core::ops::Mul<i64> for Ratio {
333    type Output = i64;
334    fn mul(self, rhs: i64) -> Self::Output {
335        self.scale::<{ Round::DOWN }>(rhs)
336    }
337}
338
339impl core::ops::Mul<Ratio> for i64 {
340    type Output = i64;
341    fn mul(self, rhs: Ratio) -> Self::Output {
342        rhs.scale::<{ Round::DOWN }>(self)
343    }
344}
345
346impl core::ops::Div<Ratio> for i64 {
347    type Output = i64;
348    fn div(self, rhs: Ratio) -> Self::Output {
349        rhs.inverse().scale::<{ Round::DOWN }>(self)
350    }
351}
352
353#[cfg(test)]
354mod tests {
355    use super::*;
356
357    #[test]
358    fn test_construction() {
359        let valid_vectors = [(0, 1), (1, 1), (23, 41)];
360        for &(n, d) in &valid_vectors {
361            let r = Ratio::new(n, d);
362            assert_eq!(r.numerator(), n);
363            assert_eq!(r.denominator(), d);
364        }
365
366        // Ratio::default() produces 1/1
367        let r = Ratio::default();
368        assert_eq!(r.numerator(), 1);
369        assert_eq!(r.denominator(), 1);
370
371        // Reduction is NOT automatically performed
372        let r = Ratio::new(9, 21);
373        assert_eq!(r.numerator(), 9);
374        assert_eq!(r.denominator(), 21);
375    }
376
377    #[test]
378    fn test_reduction_32() {
379        let mut vectors = [
380            (1, 1, 1, 1),
381            (10, 10, 1, 1),
382            (10, 2, 5, 1),
383            (0, 1, 0, 1),
384            (0, 500, 0, 1),
385            (48000, 44100, 160, 147),
386            (44100, 48000, 147, 160),
387            (1000007, 1000000, 1000007, 1000000),
388        ];
389
390        for v in &mut vectors {
391            let mut n = v.0;
392            let mut d = v.1;
393            Ratio::reduce_u32(&mut n, &mut d);
394            assert_eq!((n, d), (v.2, v.3));
395
396            let mut r = Ratio::new(v.0, v.1);
397            r.reduce();
398            assert_eq!((r.numerator(), r.denominator()), (v.2, v.3));
399        }
400    }
401
402    #[test]
403    fn test_reduction_64() {
404        let mut vectors = [
405            (1, 1, 1, 1),
406            (10, 10, 1, 1),
407            (10, 2, 5, 1),
408            (0, 1, 0, 1),
409            (0, 500, 0, 1),
410            (48000, 44100, 160, 147),
411            (44100, 48000, 147, 160),
412            (1000007, 1000000, 1000007, 1000000),
413            (48000336000, 44100000000, 1000007, 918750),
414        ];
415
416        for v in &mut vectors {
417            let mut n = v.0;
418            let mut d = v.1;
419            Ratio::reduce_u64(&mut n, &mut d);
420            assert_eq!((n, d), (v.2, v.3));
421        }
422    }
423
424    #[test]
425    fn test_product() {
426        struct TestVector {
427            a_n: u32,
428            a_d: u32,
429            b_n: u32,
430            b_d: u32,
431            expected_n: u32,
432            expected_d: u32,
433            exact: Exact,
434        }
435
436        let test_vectors = [
437            TestVector {
438                a_n: 1,
439                a_d: 1,
440                b_n: 1,
441                b_d: 1,
442                expected_n: 1,
443                expected_d: 1,
444                exact: Exact::Yes,
445            },
446            TestVector {
447                a_n: 0,
448                a_d: 1,
449                b_n: 1,
450                b_d: 1,
451                expected_n: 0,
452                expected_d: 1,
453                exact: Exact::Yes,
454            },
455            TestVector {
456                a_n: 0,
457                a_d: 500,
458                b_n: 1,
459                b_d: 1,
460                expected_n: 0,
461                expected_d: 1,
462                exact: Exact::Yes,
463            },
464            TestVector {
465                a_n: 3,
466                a_d: 4,
467                b_n: 5,
468                b_d: 9,
469                expected_n: 5,
470                expected_d: 12,
471                exact: Exact::Yes,
472            },
473            TestVector {
474                a_n: 48000,
475                a_d: 44100,
476                b_n: 1000007,
477                b_d: 1000000,
478                expected_n: 1000007,
479                expected_d: 918750,
480                exact: Exact::Yes,
481            },
482            TestVector {
483                a_n: 3465653567,
484                a_d: 2327655023,
485                b_n: 1291540343,
486                b_d: 3698423317,
487                expected_n: 317609835,
488                expected_d: 610852072,
489                exact: Exact::No,
490            },
491            TestVector {
492                a_n: 0xFFFFFFFF,
493                a_d: 1,
494                b_n: 0xFFFFFFFF,
495                b_d: 1,
496                expected_n: 0xFFFFFFFF,
497                expected_d: 1,
498                exact: Exact::No,
499            },
500            TestVector {
501                a_n: 1,
502                a_d: 0xFFFFFFFF,
503                b_n: 1,
504                b_d: 0xFFFFFFFF,
505                expected_n: 0,
506                expected_d: 1,
507                exact: Exact::No,
508            },
509        ];
510
511        for v in &test_vectors {
512            let a = Ratio::new(v.a_n, v.a_d);
513            let b = Ratio::new(v.b_n, v.b_d);
514
515            let res = Ratio::product(a, b, v.exact);
516            assert_eq!(
517                (res.numerator(), res.denominator()),
518                (v.expected_n, v.expected_d),
519                "Expected {}/{} * {}/{} to produce {}/{}; got {}/{} instead (static)",
520                v.a_n,
521                v.a_d,
522                v.b_n,
523                v.b_d,
524                v.expected_n,
525                v.expected_d,
526                res.numerator(),
527                res.denominator()
528            );
529
530            let res = Ratio::product(b, a, v.exact);
531            assert_eq!(
532                (res.numerator(), res.denominator()),
533                (v.expected_n, v.expected_d),
534                "Expected {}/{} * {}/{} to produce {}/{}; got {}/{} instead (commutative static)",
535                v.b_n,
536                v.b_d,
537                v.a_n,
538                v.a_d,
539                v.expected_n,
540                v.expected_d,
541                res.numerator(),
542                res.denominator()
543            );
544
545            if v.exact == Exact::Yes {
546                let res = a * b;
547                assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
548
549                let res = b * a;
550                assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
551
552                if b.invertible() {
553                    let res = a / b.inverse();
554                    assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
555                }
556
557                if a.invertible() {
558                    let res = b / a.inverse();
559                    assert_eq!((res.numerator(), res.denominator()), (v.expected_n, v.expected_d));
560                }
561            }
562        }
563    }
564
565    #[test]
566    fn test_product_raw() {
567        struct TestVector {
568            a_n: u32,
569            a_d: u32,
570            b_n: u32,
571            b_d: u32,
572            expected_n: u32,
573            expected_d: u32,
574            exact: Exact,
575        }
576
577        let test_vectors = [
578            TestVector {
579                a_n: 1,
580                a_d: 1,
581                b_n: 1,
582                b_d: 1,
583                expected_n: 1,
584                expected_d: 1,
585                exact: Exact::Yes,
586            },
587            TestVector {
588                a_n: 0,
589                a_d: 1,
590                b_n: 1,
591                b_d: 1,
592                expected_n: 0,
593                expected_d: 1,
594                exact: Exact::Yes,
595            },
596            TestVector {
597                a_n: 0,
598                a_d: 500,
599                b_n: 1,
600                b_d: 1,
601                expected_n: 0,
602                expected_d: 1,
603                exact: Exact::Yes,
604            },
605            TestVector {
606                a_n: 3,
607                a_d: 4,
608                b_n: 5,
609                b_d: 9,
610                expected_n: 5,
611                expected_d: 12,
612                exact: Exact::Yes,
613            },
614            TestVector {
615                a_n: 48000,
616                a_d: 44100,
617                b_n: 1000007,
618                b_d: 1000000,
619                expected_n: 1000007,
620                expected_d: 918750,
621                exact: Exact::Yes,
622            },
623            TestVector {
624                a_n: 3465653567,
625                a_d: 2327655023,
626                b_n: 1291540343,
627                b_d: 3698423317,
628                expected_n: 317609835,
629                expected_d: 610852072,
630                exact: Exact::No,
631            },
632            TestVector {
633                a_n: 0xFFFFFFFF,
634                a_d: 1,
635                b_n: 0xFFFFFFFF,
636                b_d: 1,
637                expected_n: 0xFFFFFFFF,
638                expected_d: 1,
639                exact: Exact::No,
640            },
641            TestVector {
642                a_n: 1,
643                a_d: 0xFFFFFFFF,
644                b_n: 1,
645                b_d: 0xFFFFFFFF,
646                expected_n: 0,
647                expected_d: 1,
648                exact: Exact::No,
649            },
650        ];
651
652        for v in &test_vectors {
653            let res = Ratio::product_raw(v.a_n, v.a_d, v.b_n, v.b_d, v.exact);
654            assert_eq!(
655                res,
656                (v.expected_n, v.expected_d),
657                "Expected {}/{} * {}/{} to produce {}/{}; got {}/{} instead",
658                v.a_n,
659                v.a_d,
660                v.b_n,
661                v.b_d,
662                v.expected_n,
663                v.expected_d,
664                res.0,
665                res.1
666            );
667        }
668    }
669
670    fn test_scale_helper<const ROUND: u8>() {
671        struct TestVector {
672            val: i64,
673            n: u32,
674            d: u32,
675            expected: i64,
676            fractional_result: bool,
677        }
678
679        let test_vectors = [
680            TestVector { val: 0, n: 0, d: 1, expected: 0, fractional_result: false },
681            TestVector { val: 1234567890, n: 0, d: 1, expected: 0, fractional_result: false },
682            TestVector { val: 0, n: 1, d: 1, expected: 0, fractional_result: false },
683            TestVector {
684                val: 1234567890,
685                n: 1,
686                d: 1,
687                expected: 1234567890,
688                fractional_result: false,
689            },
690            TestVector { val: 198, n: 48000, d: 44100, expected: 215, fractional_result: true },
691            TestVector { val: -198, n: 48000, d: 44100, expected: -216, fractional_result: true },
692            TestVector {
693                val: 49 * 198,
694                n: 48000,
695                d: 44100,
696                expected: 10560,
697                fractional_result: false,
698            },
699            TestVector {
700                val: -(49 * 198),
701                n: 48000,
702                d: 44100,
703                expected: -10560,
704                fractional_result: false,
705            },
706            TestVector {
707                val: (49 * 198) + 1,
708                n: 48000,
709                d: 44100,
710                expected: 10561,
711                fractional_result: true,
712            },
713            TestVector {
714                val: -((49 * 198) + 1),
715                n: 48000,
716                d: 44100,
717                expected: -10562,
718                fractional_result: true,
719            },
720            TestVector {
721                val: 0x1517ffffeae80,
722                n: 0xbebc200,
723                d: 0x33333333,
724                expected: 0x4e94914f0000,
725                fractional_result: false,
726            },
727            TestVector {
728                val: -0x1517ffffeae80,
729                n: 0xbebc200,
730                d: 0x33333333,
731                expected: -0x4e94914f0000,
732                fractional_result: false,
733            },
734            TestVector {
735                val: i64::MAX,
736                n: 1000001,
737                d: 1000000,
738                expected: Ratio::OVERFLOW,
739                fractional_result: false,
740            },
741            TestVector {
742                val: i64::MIN,
743                n: 1000001,
744                d: 1000000,
745                expected: Ratio::UNDERFLOW,
746                fractional_result: false,
747            },
748            TestVector {
749                val: -0x2000000000000001,
750                n: 4,
751                d: 1,
752                expected: Ratio::UNDERFLOW,
753                fractional_result: false,
754            },
755        ];
756
757        for v in &test_vectors {
758            let res_static = Ratio::scale_with_round::<ROUND>(v.val, v.n, v.d);
759            let r = Ratio::new(v.n, v.d);
760            let res_inst = r.scale::<ROUND>(v.val);
761
762            let adjusted_expected = if !v.fractional_result || ROUND == Round::DOWN {
763                v.expected
764            } else if v.val >= 0 {
765                if ROUND == Round::TOWARDS_ZERO { v.expected } else { v.expected + 1 }
766            } else {
767                if ROUND == Round::AWAY_FROM_ZERO { v.expected } else { v.expected + 1 }
768            };
769
770            assert_eq!(
771                res_static, adjusted_expected,
772                "Static: Expected {} * {}/{} to produce {}; got {}",
773                v.val, v.n, v.d, adjusted_expected, res_static
774            );
775            assert_eq!(
776                res_inst, adjusted_expected,
777                "Instanced: Expected {} * {}/{} to produce {}; got {}",
778                v.val, v.n, v.d, adjusted_expected, res_inst
779            );
780
781            if ROUND == Round::DOWN {
782                let res_op1 = r * v.val;
783                let res_op2 = v.val * r;
784                assert_eq!(res_op1, adjusted_expected);
785                assert_eq!(res_op2, adjusted_expected);
786
787                if r.invertible() {
788                    let res_op3 = v.val / r.inverse();
789                    assert_eq!(res_op3, adjusted_expected);
790                }
791            }
792        }
793    }
794
795    #[test]
796    fn test_scale_round_down() {
797        test_scale_helper::<{ Round::DOWN }>();
798    }
799    #[test]
800    fn test_scale_round_up() {
801        test_scale_helper::<{ Round::UP }>();
802    }
803    #[test]
804    fn test_scale_round_towards_zero() {
805        test_scale_helper::<{ Round::TOWARDS_ZERO }>();
806    }
807    #[test]
808    fn test_scale_round_away_from_zero() {
809        test_scale_helper::<{ Round::AWAY_FROM_ZERO }>();
810    }
811
812    #[test]
813    fn test_inverse() {
814        let test_vectors = [(1, 1), (123456, 987654)];
815        for &(n, d) in &test_vectors {
816            let r = Ratio::new(n, d);
817            let inv = r.inverse();
818            assert_eq!(inv.numerator(), d);
819            assert_eq!(inv.denominator(), n);
820        }
821
822        let r = Ratio::new(0, 1);
823        assert!(!r.invertible());
824    }
825
826    // The two limits used by `Ratio::scale_with_round`; the limit for
827    // non-negative values, and the limit for the distance from zero of
828    // negative values.
829    const POSITIVE_LIMIT: u64 = i64::MAX as u64; // 0x7fffffffffffffff
830    const NEGATIVE_LIMIT: u64 = 0x8000000000000000; // i64::MIN.unsigned_abs()
831
832    // Invokes `scale_unsigned` and checks its result.  The rounding direction
833    // and the limit are const generic parameters, so they are spelled as
834    // literals here rather than being gathered into a table of test vectors.
835    macro_rules! check_scale_unsigned {
836        ($value:expr, $numerator:expr, $denominator:expr, $round_up:expr, $limit:expr,
837         $expected:expr $(,)?) => {{
838            let value: u64 = $value;
839            let numerator: u32 = $numerator;
840            let denominator: u32 = $denominator;
841            let expected: u64 = $expected;
842            let res = scale_unsigned::<{ $round_up }, { $limit }>(value, numerator, denominator);
843            assert_eq!(
844                res, expected,
845                "Expected scale_unsigned::<{}, {:#x}>({:#x}, {}, {}) to produce {:#x}; got {:#x}",
846                $round_up, $limit, value, numerator, denominator, expected, res
847            );
848        }};
849    }
850
851    // Exercises the `high_q > (LIMIT >> 32)` early-out, which both saturates
852    // and keeps the subsequent `high_q << 32` from overflowing.
853    #[test]
854    fn test_scale_unsigned_early_out() {
855        // high_q == 0x80000000, which is one more than POSITIVE_LIMIT >> 32;
856        // take the early out.
857        check_scale_unsigned!(0x8000000000000000, 1, 1, false, POSITIVE_LIMIT, POSITIVE_LIMIT);
858
859        // The same value against the negative limit; high_q is now exactly
860        // NEGATIVE_LIMIT >> 32, so there is no early out and the value is
861        // scaled exactly.
862        check_scale_unsigned!(0x8000000000000000, 1, 1, false, NEGATIVE_LIMIT, 0x8000000000000000);
863
864        // high_q == POSITIVE_LIMIT >> 32 exactly; no early out, and the result
865        // is well under the limit.
866        check_scale_unsigned!(0x7fffffff00000000, 1, 1, false, POSITIVE_LIMIT, 0x7fffffff00000000);
867
868        // The largest possible intermediates: high and low are each just shy of
869        // 2^64.  The first takes the early out; the second has
870        // high_q == (u64::MAX >> 32) and so does not.
871        check_scale_unsigned!(u64::MAX, u32::MAX, 1, true, POSITIVE_LIMIT, POSITIVE_LIMIT);
872        check_scale_unsigned!(u64::MAX, u32::MAX, u32::MAX, false, u64::MAX, u64::MAX);
873    }
874
875    // Exercises the `result >= LIMIT` saturation, which is only reachable when
876    // high_q is exactly `LIMIT >> 32` and the low half pushes the result past
877    // the limit.
878    #[test]
879    fn test_scale_unsigned_result_saturation() {
880        // result == NEGATIVE_LIMIT + 1, reached without the early out.
881        check_scale_unsigned!(0x8000000000000001, 1, 1, false, NEGATIVE_LIMIT, NEGATIVE_LIMIT);
882
883        // result == NEGATIVE_LIMIT exactly, which also saturates (to the same
884        // value it would have produced).
885        check_scale_unsigned!(0x4000000000000000, 2, 1, false, NEGATIVE_LIMIT, NEGATIVE_LIMIT);
886
887        // result == POSITIVE_LIMIT exactly.
888        check_scale_unsigned!(POSITIVE_LIMIT, 1, 1, true, POSITIVE_LIMIT, POSITIVE_LIMIT);
889
890        // Saturation of a small limit, where high_q is 0 and low_q alone
891        // exceeds the limit.
892        check_scale_unsigned!(1000, 3, 1, false, 100, 100);
893    }
894
895    // Exercises the rounding-up path, in particular the case where rounding up
896    // would produce exactly the limit.
897    #[test]
898    fn test_scale_unsigned_round_up_at_limit() {
899        // result == NEGATIVE_LIMIT - 1 with a non-zero remainder; rounding up
900        // produces exactly the limit.
901        check_scale_unsigned!(u64::MAX, 1, 2, true, NEGATIVE_LIMIT, NEGATIVE_LIMIT);
902
903        // The same inputs without rounding up produce the truncated value.
904        check_scale_unsigned!(u64::MAX, 1, 2, false, NEGATIVE_LIMIT, NEGATIVE_LIMIT - 1);
905
906        // result == POSITIVE_LIMIT - 1 with a non-zero remainder; rounding up
907        // produces exactly the limit.
908        check_scale_unsigned!(0xfffffffffffffffd, 1, 2, true, POSITIVE_LIMIT, POSITIVE_LIMIT);
909
910        // result == POSITIVE_LIMIT - 2 with a non-zero remainder; rounding up
911        // stays below the limit.
912        check_scale_unsigned!(0xfffffffffffffffb, 1, 2, true, POSITIVE_LIMIT, POSITIVE_LIMIT - 1);
913
914        // An exact result is never rounded up.
915        check_scale_unsigned!(0xfffffffffffffffc, 1, 2, true, POSITIVE_LIMIT, POSITIVE_LIMIT - 1);
916
917        // Rounding up a small result.
918        check_scale_unsigned!(198, 48000, 44100, true, POSITIVE_LIMIT, 216);
919        check_scale_unsigned!(198, 48000, 44100, false, POSITIVE_LIMIT, 215);
920    }
921
922    // A straightforward 128-bit reference implementation of the scaling
923    // operation, used to validate the 64-bit implementation.
924    fn scale_unsigned_reference(
925        value: u64,
926        numerator: u32,
927        denominator: u32,
928        round_up: bool,
929        limit: u64,
930    ) -> u64 {
931        let prod = (value as u128) * (numerator as u128);
932        let q = prod / (denominator as u128);
933        let r = prod % (denominator as u128);
934
935        if q >= (limit as u128) {
936            return limit;
937        }
938
939        let mut result = q as u64;
940        if round_up && r != 0 {
941            result += 1;
942            if result >= limit {
943                return limit;
944            }
945        }
946
947        result
948    }
949
950    // Compares `scale_unsigned` against the reference implementation across a
951    // range of values, numerators, and denominators, for one particular
952    // rounding direction and limit.
953    fn check_against_reference<const ROUND_UP: bool, const LIMIT: u64>() {
954        let values = [
955            0,
956            1,
957            2,
958            0xffff_ffff,
959            0x1_0000_0000,
960            0x1_0000_0001,
961            0x7fff_ffff_ffff_fffe,
962            POSITIVE_LIMIT,
963            NEGATIVE_LIMIT,
964            0x8000_0000_0000_0001,
965            0xffff_ffff_ffff_fffd,
966            u64::MAX,
967            0x1517ffffeae80,
968            1234567890,
969        ];
970        let numerators = [0, 1, 2, 3, 48000, 44100, 1000001, 0x7fff_ffff, u32::MAX];
971        let denominators = [1, 2, 3, 7, 44100, 1000000, 0x7fff_ffff, u32::MAX];
972
973        for &value in &values {
974            for &numerator in &numerators {
975                for &denominator in &denominators {
976                    let res = scale_unsigned::<ROUND_UP, LIMIT>(value, numerator, denominator);
977                    let expected =
978                        scale_unsigned_reference(value, numerator, denominator, ROUND_UP, LIMIT);
979                    assert_eq!(
980                        res, expected,
981                        "Expected scale_unsigned::<{}, {:#x}>({:#x}, {}, {}) to produce \
982                         {:#x}; got {:#x}",
983                        ROUND_UP, LIMIT, value, numerator, denominator, expected, res
984                    );
985                }
986            }
987        }
988    }
989
990    #[test]
991    fn test_scale_unsigned_matches_reference() {
992        macro_rules! check_against_reference_for_limits {
993            ($($limit:expr),* $(,)?) => {
994                $(
995                    check_against_reference::<false, { $limit }>();
996                    check_against_reference::<true, { $limit }>();
997                )*
998            };
999        }
1000
1001        check_against_reference_for_limits!(0, 1, 2, 100, POSITIVE_LIMIT, NEGATIVE_LIMIT, u64::MAX,);
1002    }
1003}
affine/ratio.rs

affine/
ratio.rs
