ph_surfaces/axis/
mod.rs

1//! Per-axis lookup strategies, chosen in the type of a surface rather than at
2//! runtime.
3//!
4//! Every strategy answers one question — *which segment of this axis contains
5//! this coordinate* — and answers it identically. They differ only in what they
6//! store and how much work the answer costs:
7//!
8//! | Strategy | Stored per axis | Strategy work after endpoint checks | Choose when |
9//! | --- | --- | --- | --- |
10//! | [`LinearAxis`] | `2*N` knot bytes | bounded scan, at most `N - 1` comparisons | tiny axis; minimum auxiliary structure |
11//! | [`BinaryAxis`] | `2*N` knot bytes | exactly `ceil(log2(N))` comparisons | the general default |
12//! | [`UniformAxis`] | none | no comparison at all | even spacing; drop knot arrays; constant location |
13//! | [`BucketedAxis`] | `2*N` knot bytes plus `2*B` index bytes | one bucket read plus a bounded local scan | irregular axis; extra index bytes for a smaller local bound |
14//!
15//! # Why the choice is in the type
16//!
17//! A runtime enum would add a branch to every lookup and would keep all four
18//! implementations in the image even when a firmware uses one. A Cargo feature
19//! would be worse: Cargo unifies features across the whole dependency graph, so
20//! an unrelated downstream crate could change which strategy a firmware
21//! compiles. Selecting in the type leaves the decision where the surface is
22//! declared, and a firmware that names one combination compiles exactly that
23//! one.
24//!
25//! # What a strategy does not decide
26//!
27//! A strategy locates. It does not decide boundary behaviour, error identity,
28//! rounding, or composition order:
29//!
30//! * the private lookup module owns the endpoint tests, the [`Boundary`]
31//!   policy, the clamped-coordinate substitution, and the cell invariants.
32//!   Every strategy reaches the evaluator through that one function.
33//! * the private interpolation module owns rounding, and the evaluator owns
34//!   the X-then-Y composition.
35//!
36//! That split is why swapping a strategy cannot change a value, an error, or a
37//! boundary outcome, and why there is one numerical path rather than four.
38//!
39//! [`Boundary`]: crate::Boundary
40
41mod binary;
42mod bucketed;
43mod linear;
44mod uniform;
45
46pub use binary::BinaryAxis;
47pub use bucketed::{BucketedAxis, bucket_index, max_local_comparisons};
48pub use linear::LinearAxis;
49pub use uniform::UniformAxis;
50
51/// Seals [`AxisLookup`] and [`KnotArray`] against outside implementations.
52///
53/// The two traits carry preconditions the crate relies on for memory safety of
54/// its indexing — a located index is always in range, and a validated axis is
55/// always strictly increasing — but they are checked by construction inside
56/// this module rather than by the type system. A downstream implementation
57/// could satisfy the signatures while violating them, so the trait is closed.
58mod sealed {
59    /// Implemented only by this crate's four axis strategies.
60    pub trait Sealed<const N: usize> {
61        /// Locates a coordinate after the shared caller has established that it
62        /// is inside the inclusive axis domain.
63        fn search_in_domain(&self, coordinate: u16) -> (usize, u32);
64    }
65}
66
67/// One axis of `N` knots, together with the strategy that locates a coordinate
68/// in it.
69///
70/// This trait is sealed: [`LinearAxis`], [`BinaryAxis`], [`UniformAxis`], and
71/// [`BucketedAxis`] are the only implementations, and each validates its own
72/// invariants in a `const fn` constructor. An invalid axis therefore fails to
73/// compile rather than reaching [`search`](AxisLookup::search).
74///
75/// `N` is a parameter of the trait rather than an associated constant so that
76/// an axis and the value grid it addresses cannot drift apart: a
77/// [`BilinearSurface`](crate::BilinearSurface) requires `X: AxisLookup<NX>`, so
78/// pairing a 5-knot axis with a grid of 4 columns is a type error at the
79/// declaration.
80///
81/// # Invariants
82///
83/// Every implementation guarantees that `N >= 2` and that
84/// `knot(0) < knot(1) < .. < knot(N - 1)`, all of them representable in `u16`.
85pub trait AxisLookup<const N: usize>: sealed::Sealed<N> + Copy {
86    /// Bytes of stored knots or descriptor this strategy references.
87    ///
88    /// This is the axis's own static payload. It excludes the value grid, the
89    /// auxiliary index counted by [`INDEX_BYTES`](AxisLookup::INDEX_BYTES), the
90    /// surface handle, alignment, code, and stack. It is exact and
91    /// target-independent, and it is not a total memory figure.
92    const KNOT_BYTES: usize;
93
94    /// Bytes of auxiliary index this strategy references.
95    ///
96    /// Zero for every strategy except [`BucketedAxis`], which is the only one
97    /// that buys a smaller search bound with static data.
98    const INDEX_BYTES: usize;
99
100    /// The most strategy-specific knot comparisons needed to locate an
101    /// in-domain coordinate, after the inclusive endpoint checks.
102    ///
103    /// This counts comparisons against stored knots, not machine instructions,
104    /// and it excludes the two endpoint comparisons performed before the
105    /// strategy-specific search. The public [`search`](AxisLookup::search)
106    /// wrapper routes through the lookup module that owns those checks; surface
107    /// evaluation reuses the endpoint classification it already needs for
108    /// boundary handling. It is a work bound, never a cycle count.
109    const MAX_SEARCH_COMPARISONS: u32;
110
111    /// Returns the first knot: the inclusive lower bound of the axis domain.
112    fn first(&self) -> u16;
113
114    /// Returns the last knot: the inclusive upper bound of the axis domain.
115    fn last(&self) -> u16;
116
117    /// Returns the knot at `index`.
118    ///
119    /// # Panics
120    ///
121    /// Panics if `index >= N`. Every index this crate passes comes from a
122    /// located cell, whose lower knot is at most `N - 2` and whose upper knot is
123    /// therefore at most `N - 1`.
124    fn knot(&self, index: usize) -> u16;
125
126    /// Returns the greatest index whose knot is at or below `coordinate`,
127    /// together with the number of knot comparisons it took.
128    ///
129    /// The returned count covers only the strategy-specific work and is bounded
130    /// by [`MAX_SEARCH_COMPARISONS`](AxisLookup::MAX_SEARCH_COMPARISONS). It is
131    /// the observable half of that declared bound: because the count is public,
132    /// a consumer — and this crate's own black-box conformance suite — can
133    /// verify the bound instead of taking it on faith. Callers that only want
134    /// the index discard it, and an optimising build removes the counting.
135    ///
136    /// # Panics
137    ///
138    /// Panics in every build profile unless
139    /// `first() <= coordinate <= last()`. This makes the answer set non-empty
140    /// and the returned index well defined.
141    ///
142    /// # Cost
143    ///
144    /// A direct public call performs one or two endpoint comparisons before the
145    /// strategy-specific work (two for an in-domain coordinate). The surface
146    /// evaluator does not duplicate those comparisons: its private locator
147    /// performs the same endpoint checks for boundary handling, then enters the
148    /// sealed in-domain search directly.
149    fn search(&self, coordinate: u16) -> (usize, u32) {
150        crate::lookup::search(self, coordinate)
151    }
152}
153
154/// Enters a strategy after the shared locator has checked both domain endpoints.
155#[inline(always)]
156pub(crate) fn search_in_domain<const N: usize, A: AxisLookup<N>>(
157    axis: &A,
158    coordinate: u16,
159) -> (usize, u32) {
160    <A as sealed::Sealed<N>>::search_in_domain(axis, coordinate)
161}
162
163/// An axis whose knots are stored as one static array.
164///
165/// [`LinearAxis`], [`BinaryAxis`], and [`BucketedAxis`] implement it;
166/// [`UniformAxis`] does not, because it stores no knots to hand out. It is what
167/// keeps [`BilinearSurface::x_axis`](crate::BilinearSurface::x_axis) available
168/// for the strategies that have an array, without inventing one for the
169/// strategy that deliberately does not.
170///
171/// This trait is sealed for the same reason [`AxisLookup`] is.
172pub trait KnotArray<const N: usize>: AxisLookup<N> {
173    /// Returns the declared knots, strictly increasing and at least two long.
174    fn knots(&self) -> &'static [u16; N];
175}
176
177/// Returns `ceil(log2(len))`: the number of probes [`BinaryAxis`] performs on an
178/// axis of `len` knots.
179///
180/// This is the bit length of `len - 1`, which is target-independent even though
181/// `usize::BITS` is not.
182///
183/// It is an exact count rather than an upper bound, because the search window
184/// shrinks by `size -> ceil(size / 2)` on both branches.
185///
186/// # Preconditions
187///
188/// `len >= 2`. Every axis this crate can construct satisfies it, so `len - 1`
189/// cannot underflow.
190pub(crate) const fn probe_bound(len: usize) -> u32 {
191    debug_assert!(len >= 2, "an axis declares at least two knots");
192
193    usize::BITS - (len - 1).leading_zeros()
194}
195
196/// Asserts that `knots` is a usable axis: at least two knots, strictly
197/// increasing.
198///
199/// Shared by the three stored-knot strategies so that one rule is stated once.
200/// The message is axis-neutral because a `const fn` panic cannot name the axis
201/// it was called for; [`BilinearSurface::new`](crate::BilinearSurface::new)
202/// keeps its own X- and Y-named assertions for the default construction path.
203const fn assert_valid_knots<const N: usize>(knots: &[u16; N]) {
204    assert!(N >= 2, "an axis must declare at least two knots");
205
206    let mut i = 1;
207    while i < N {
208        assert!(
209            knots[i - 1] < knots[i],
210            "axis knots must be strictly increasing"
211        );
212        i += 1;
213    }
214}
215
216/// Every knot of an axis and its two neighbours, plus a stride across the whole
217/// domain, with anything outside the domain dropped.
218///
219/// Those are the coordinates where a cell boundary can be got wrong, and enough
220/// of the interior to catch a locator that is wrong in bulk. The strategy
221/// modules share it so that they are all held to the same probe set.
222#[cfg(test)]
223pub(crate) fn probes<const N: usize>(
224    knots: &'static [u16; N],
225    stride: usize,
226) -> impl Iterator<Item = u16> {
227    knots
228        .iter()
229        .flat_map(|&knot| [knot.saturating_sub(1), knot, knot.saturating_add(1)])
230        .chain((knots[0]..=knots[N - 1]).step_by(stride))
231        .filter(|&coordinate| coordinate >= knots[0] && coordinate <= knots[N - 1])
232}
233
234#[cfg(test)]
235mod tests {
236    use super::{
237        AxisLookup, BinaryAxis, BucketedAxis, LinearAxis, UniformAxis, bucket_index, probes,
238    };
239    use crate::boundary::{Boundary, BoundaryPolicy};
240    use crate::error::SurfaceError;
241    use crate::surface::BilinearSurface;
242    use core::mem::size_of;
243
244    // A uniformly spaced axis, so all four strategies can describe it and the
245    // equivalence checks below have something all four can be compared on.
246    static UNIFORM_KNOTS: [u16; 9] = [100, 150, 200, 250, 300, 350, 400, 450, 500];
247    static UNIFORM_BUCKETS: [u16; 4] = bucket_index(&UNIFORM_KNOTS);
248
249    // The Y axis is the same shape but shorter, so a mixed pairing is not
250    // accidentally symmetric.
251    static Y_KNOTS: [u16; 3] = [10, 20, 30];
252    static Y_BUCKETS: [u16; 2] = bucket_index(&Y_KNOTS);
253
254    // Strictly convex in both indices, so a wrongly located cell changes the
255    // value instead of hiding behind collinear data.
256    static VALUES: [[i32; 9]; 3] = [
257        [0, 1, 4, 9, 16, 25, 36, 49, 64],
258        [100, 102, 108, 118, 132, 150, 172, 198, 228],
259        [-50, -49, -46, -41, -34, -25, -14, -1, 14],
260    ];
261
262    const LINEAR_X: LinearAxis<9> = LinearAxis::new(&UNIFORM_KNOTS);
263    const BINARY_X: BinaryAxis<9> = BinaryAxis::new(&UNIFORM_KNOTS);
264    const UNIFORM_X: UniformAxis<9, 100, 50> = UniformAxis::new();
265    const BUCKETED_X: BucketedAxis<9, 4> = BucketedAxis::new(&UNIFORM_KNOTS, &UNIFORM_BUCKETS);
266
267    const LINEAR_Y: LinearAxis<3> = LinearAxis::new(&Y_KNOTS);
268    const BINARY_Y: BinaryAxis<3> = BinaryAxis::new(&Y_KNOTS);
269    const UNIFORM_Y: UniformAxis<3, 10, 10> = UniformAxis::new();
270    const BUCKETED_Y: BucketedAxis<3, 2> = BucketedAxis::new(&Y_KNOTS, &Y_BUCKETS);
271
272    // An irregular axis: only the three stored-knot strategies can describe it.
273    static IRREGULAR_KNOTS: [u16; 7] = [3, 4, 5, 1_000, 40_000, 65_000, 65_535];
274    static IRREGULAR_BUCKETS: [u16; 8] = bucket_index(&IRREGULAR_KNOTS);
275    static IRREGULAR_VALUES: [[i32; 7]; 3] = [
276        [0, 1, 4, 9, 16, 25, 36],
277        [100, 102, 108, 118, 132, 150, 172],
278        [-50, -49, -46, -41, -34, -25, -14],
279    ];
280
281    const IRREGULAR_LINEAR: LinearAxis<7> = LinearAxis::new(&IRREGULAR_KNOTS);
282    const IRREGULAR_BINARY: BinaryAxis<7> = BinaryAxis::new(&IRREGULAR_KNOTS);
283    const IRREGULAR_BUCKETED: BucketedAxis<7, 8> =
284        BucketedAxis::new(&IRREGULAR_KNOTS, &IRREGULAR_BUCKETS);
285
286    /// Every coordinate worth probing on the uniform fixture: each knot, one
287    /// unit either side of it, both endpoints, and coordinates outside the
288    /// domain on both sides.
289    fn uniform_probes() -> impl Iterator<Item = u16> {
290        (99u16..=501).chain([0, 50, 502, 1_000, u16::MAX])
291    }
292
293    #[test]
294    fn every_strategy_locates_the_same_cell_on_an_equivalent_axis() {
295        for coordinate in 100u16..=500 {
296            let expected = BINARY_X.search(coordinate).0;
297
298            assert_eq!(LINEAR_X.search(coordinate).0, expected, "at {coordinate}");
299            assert_eq!(UNIFORM_X.search(coordinate).0, expected, "at {coordinate}");
300            assert_eq!(BUCKETED_X.search(coordinate).0, expected, "at {coordinate}");
301        }
302    }
303
304    #[test]
305    fn every_strategy_reports_the_same_domain_and_knots() {
306        for (index, &expected) in UNIFORM_KNOTS.iter().enumerate() {
307            assert_eq!(LINEAR_X.knot(index), expected);
308            assert_eq!(BINARY_X.knot(index), expected);
309            assert_eq!(UNIFORM_X.knot(index), expected);
310            assert_eq!(BUCKETED_X.knot(index), expected);
311        }
312
313        for (first, last) in [
314            (LINEAR_X.first(), LINEAR_X.last()),
315            (BINARY_X.first(), BINARY_X.last()),
316            (UNIFORM_X.first(), UNIFORM_X.last()),
317            (BUCKETED_X.first(), BUCKETED_X.last()),
318        ] {
319            assert_eq!((first, last), (100, 500));
320        }
321    }
322
323    #[test]
324    fn the_three_stored_knot_strategies_agree_on_an_irregular_axis() {
325        // A uniform axis cannot describe this one, so the comparison is over the
326        // three strategies that can.
327        for coordinate in probes(&IRREGULAR_KNOTS, 211) {
328            let expected = IRREGULAR_BINARY.search(coordinate).0;
329
330            assert_eq!(
331                IRREGULAR_LINEAR.search(coordinate).0,
332                expected,
333                "at {coordinate}"
334            );
335            assert_eq!(
336                IRREGULAR_BUCKETED.search(coordinate).0,
337                expected,
338                "at {coordinate}"
339            );
340        }
341    }
342
343    /// The sixteen boundary selections, as bits: X-below, X-above, Y-below,
344    /// Y-above, a set bit meaning [`Boundary::Clamp`].
345    fn policy_from_bits(bits: usize) -> BoundaryPolicy {
346        let side = |shift: u32| {
347            if (bits >> shift) & 1 == 0 {
348                Boundary::Error
349            } else {
350                Boundary::Clamp
351            }
352        };
353
354        BoundaryPolicy::new()
355            .with_x_below(side(0))
356            .with_x_above(side(1))
357            .with_y_below(side(2))
358            .with_y_above(side(3))
359    }
360
361    #[test]
362    fn every_pairing_evaluates_identically_under_every_policy() {
363        // Sixteen pairings over one equivalent axis pair. The default binary
364        // surface is the baseline every other pairing must reproduce, value for
365        // value and error for error.
366        for bits in 0..16 {
367            let policy = policy_from_bits(bits);
368            let baseline =
369                BilinearSurface::from_axes(BINARY_X, BINARY_Y, &VALUES).with_policy(policy);
370
371            macro_rules! agrees {
372                ($x:expr, $y:expr) => {
373                    let surface = BilinearSurface::from_axes($x, $y, &VALUES).with_policy(policy);
374                    for x in uniform_probes() {
375                        for y in [0u16, 9, 10, 11, 20, 25, 30, 31, 100, u16::MAX] {
376                            assert_eq!(
377                                surface.evaluate(x, y),
378                                baseline.evaluate(x, y),
379                                "bits {bits} at ({x}, {y})"
380                            );
381                        }
382                    }
383                };
384            }
385
386            agrees!(LINEAR_X, LINEAR_Y);
387            agrees!(LINEAR_X, BINARY_Y);
388            agrees!(LINEAR_X, UNIFORM_Y);
389            agrees!(LINEAR_X, BUCKETED_Y);
390            agrees!(BINARY_X, LINEAR_Y);
391            agrees!(BINARY_X, BINARY_Y);
392            agrees!(BINARY_X, UNIFORM_Y);
393            agrees!(BINARY_X, BUCKETED_Y);
394            agrees!(UNIFORM_X, LINEAR_Y);
395            agrees!(UNIFORM_X, BINARY_Y);
396            agrees!(UNIFORM_X, UNIFORM_Y);
397            agrees!(UNIFORM_X, BUCKETED_Y);
398            agrees!(BUCKETED_X, LINEAR_Y);
399            agrees!(BUCKETED_X, BINARY_Y);
400            agrees!(BUCKETED_X, UNIFORM_Y);
401            agrees!(BUCKETED_X, BUCKETED_Y);
402        }
403    }
404
405    #[test]
406    fn a_mixed_pairing_reproduces_the_default_surface_on_an_irregular_axis() {
407        let baseline = BilinearSurface::new(&IRREGULAR_KNOTS, &Y_KNOTS, &IRREGULAR_VALUES);
408        let linear_bucketed =
409            BilinearSurface::from_axes(IRREGULAR_LINEAR, BUCKETED_Y, &IRREGULAR_VALUES);
410        let bucketed_uniform =
411            BilinearSurface::from_axes(IRREGULAR_BUCKETED, UNIFORM_Y, &IRREGULAR_VALUES);
412
413        let mut x = 3u16;
414        loop {
415            for y in [10u16, 15, 20, 25, 30] {
416                let expected = baseline.evaluate(x, y);
417                assert_eq!(linear_bucketed.evaluate(x, y), expected, "({x}, {y})");
418                assert_eq!(bucketed_uniform.evaluate(x, y), expected, "({x}, {y})");
419            }
420
421            if x == u16::MAX {
422                break;
423            }
424            x = x.saturating_add(197);
425        }
426    }
427
428    #[test]
429    fn the_four_error_variants_are_invariant_across_pairings() {
430        let cases: [(u16, u16, SurfaceError); 4] = [
431            (
432                99,
433                20,
434                SurfaceError::XBelow {
435                    coordinate: 99,
436                    bound: 100,
437                },
438            ),
439            (
440                501,
441                20,
442                SurfaceError::XAbove {
443                    coordinate: 501,
444                    bound: 500,
445                },
446            ),
447            (
448                200,
449                9,
450                SurfaceError::YBelow {
451                    coordinate: 9,
452                    bound: 10,
453                },
454            ),
455            (
456                200,
457                31,
458                SurfaceError::YAbove {
459                    coordinate: 31,
460                    bound: 30,
461                },
462            ),
463        ];
464
465        for (x, y, expected) in cases {
466            assert_eq!(
467                BilinearSurface::from_axes(UNIFORM_X, BUCKETED_Y, &VALUES).evaluate(x, y),
468                Err(expected)
469            );
470            assert_eq!(
471                BilinearSurface::from_axes(BUCKETED_X, LINEAR_Y, &VALUES).evaluate(x, y),
472                Err(expected)
473            );
474            assert_eq!(
475                BilinearSurface::from_axes(LINEAR_X, UNIFORM_Y, &VALUES).evaluate(x, y),
476                Err(expected)
477            );
478        }
479    }
480
481    #[test]
482    fn x_before_y_precedence_is_invariant_across_pairings() {
483        // Both coordinates out of domain on Error sides: the X-side error wins
484        // whichever strategies located them.
485        let expected = Err(SurfaceError::XBelow {
486            coordinate: 99,
487            bound: 100,
488        });
489
490        assert_eq!(
491            BilinearSurface::from_axes(UNIFORM_X, UNIFORM_Y, &VALUES).evaluate(99, 9),
492            expected
493        );
494        assert_eq!(
495            BilinearSurface::from_axes(BUCKETED_X, LINEAR_Y, &VALUES).evaluate(99, 9),
496            expected
497        );
498
499        // A clamped X still leaves the Y side free to reject.
500        let clamped_x = BoundaryPolicy::new()
501            .with_x_below(Boundary::Clamp)
502            .with_x_above(Boundary::Clamp);
503        assert_eq!(
504            BilinearSurface::from_axes(LINEAR_X, BUCKETED_Y, &VALUES)
505                .with_policy(clamped_x)
506                .evaluate(99, 9),
507            Err(SurfaceError::YBelow {
508                coordinate: 9,
509                bound: 10,
510            })
511        );
512    }
513
514    #[test]
515    fn clamping_never_extrapolates_under_any_strategy() {
516        let all_clamp = policy_from_bits(0b1111);
517        let hull = VALUES
518            .iter()
519            .flat_map(|row| row.iter().copied())
520            .fold((i32::MAX, i32::MIN), |(lo, hi), v| (lo.min(v), hi.max(v)));
521
522        macro_rules! clamps_into_the_hull {
523            ($x:expr, $y:expr) => {
524                let surface = BilinearSurface::from_axes($x, $y, &VALUES).with_policy(all_clamp);
525                for x in [0u16, 1, 99, 501, u16::MAX] {
526                    for y in [0u16, 9, 31, u16::MAX] {
527                        let value = surface.evaluate(x, y).expect("every side clamps");
528                        assert!(
529                            (hull.0..=hull.1).contains(&value),
530                            "({x}, {y}) extrapolated to {value}"
531                        );
532                    }
533                }
534                // A clamped edge evaluates the boundary itself.
535                assert_eq!(surface.evaluate(0, 20), surface.evaluate(100, 20));
536                assert_eq!(surface.evaluate(u16::MAX, 20), surface.evaluate(500, 20));
537                assert_eq!(surface.evaluate(200, 0), surface.evaluate(200, 10));
538                assert_eq!(surface.evaluate(200, u16::MAX), surface.evaluate(200, 30));
539            };
540        }
541
542        clamps_into_the_hull!(LINEAR_X, UNIFORM_Y);
543        clamps_into_the_hull!(BINARY_X, BUCKETED_Y);
544        clamps_into_the_hull!(UNIFORM_X, LINEAR_Y);
545        clamps_into_the_hull!(BUCKETED_X, BINARY_Y);
546    }
547
548    #[test]
549    fn every_declared_knot_returns_its_stored_value_under_every_pairing() {
550        macro_rules! knots_are_exact {
551            ($x:expr, $y:expr) => {
552                let surface = BilinearSurface::from_axes($x, $y, &VALUES);
553                for (row, &y) in Y_KNOTS.iter().enumerate() {
554                    for (column, &x) in UNIFORM_KNOTS.iter().enumerate() {
555                        assert_eq!(surface.evaluate(x, y), Ok(VALUES[row][column]));
556                    }
557                }
558            };
559        }
560
561        knots_are_exact!(LINEAR_X, LINEAR_Y);
562        knots_are_exact!(BINARY_X, UNIFORM_Y);
563        knots_are_exact!(UNIFORM_X, BUCKETED_Y);
564        knots_are_exact!(BUCKETED_X, BINARY_Y);
565    }
566
567    // The locked order fixture from the accepted contract, on a uniform axis so
568    // that all four strategies can describe it.
569    static ORDER_KNOTS: [u16; 2] = [0, 2];
570    static ORDER_VALUES: [[i32; 2]; 2] = [[0, 0], [1, 3]];
571    static ORDER_BUCKETS: [u16; 2] = bucket_index(&ORDER_KNOTS);
572
573    const ORDER_LINEAR: LinearAxis<2> = LinearAxis::new(&ORDER_KNOTS);
574    const ORDER_BINARY: BinaryAxis<2> = BinaryAxis::new(&ORDER_KNOTS);
575    const ORDER_UNIFORM: UniformAxis<2, 0, 2> = UniformAxis::new();
576    const ORDER_BUCKETED: BucketedAxis<2, 2> = BucketedAxis::new(&ORDER_KNOTS, &ORDER_BUCKETS);
577
578    #[test]
579    fn the_locked_order_fixture_still_distinguishes_x_then_y_under_every_pairing() {
580        // X first gives 1; Y first would give 2. Every pairing must give 1, so
581        // no strategy can have smuggled in a second composition order.
582        macro_rules! keeps_the_order {
583            ($x:expr, $y:expr) => {
584                let surface = BilinearSurface::from_axes($x, $y, &ORDER_VALUES);
585                assert_eq!(surface.evaluate(1, 1), Ok(1));
586                assert_ne!(surface.evaluate(1, 1), Ok(2));
587            };
588        }
589
590        keeps_the_order!(ORDER_LINEAR, ORDER_LINEAR);
591        keeps_the_order!(ORDER_LINEAR, ORDER_BINARY);
592        keeps_the_order!(ORDER_LINEAR, ORDER_UNIFORM);
593        keeps_the_order!(ORDER_LINEAR, ORDER_BUCKETED);
594        keeps_the_order!(ORDER_BINARY, ORDER_LINEAR);
595        keeps_the_order!(ORDER_BINARY, ORDER_BINARY);
596        keeps_the_order!(ORDER_BINARY, ORDER_UNIFORM);
597        keeps_the_order!(ORDER_BINARY, ORDER_BUCKETED);
598        keeps_the_order!(ORDER_UNIFORM, ORDER_LINEAR);
599        keeps_the_order!(ORDER_UNIFORM, ORDER_BINARY);
600        keeps_the_order!(ORDER_UNIFORM, ORDER_UNIFORM);
601        keeps_the_order!(ORDER_UNIFORM, ORDER_BUCKETED);
602        keeps_the_order!(ORDER_BUCKETED, ORDER_LINEAR);
603        keeps_the_order!(ORDER_BUCKETED, ORDER_BINARY);
604        keeps_the_order!(ORDER_BUCKETED, ORDER_UNIFORM);
605        keeps_the_order!(ORDER_BUCKETED, ORDER_BUCKETED);
606    }
607
608    #[test]
609    fn no_strategy_exceeds_its_declared_search_bound() {
610        for coordinate in 100u16..=500 {
611            assert!(LINEAR_X.search(coordinate).1 <= <LinearAxis<9>>::MAX_SEARCH_COMPARISONS);
612            assert!(BINARY_X.search(coordinate).1 <= <BinaryAxis<9>>::MAX_SEARCH_COMPARISONS);
613            assert!(
614                BUCKETED_X.search(coordinate).1 <= <BucketedAxis<9, 4>>::MAX_SEARCH_COMPARISONS
615            );
616            // A bound of zero is a claim of its own: the uniform strategy must
617            // reach the same cell without looking at a knot at all.
618            assert_eq!(UNIFORM_X.search(coordinate).1, 0);
619        }
620
621        // The bounds themselves, so the numbers are pinned and not merely
622        // self-consistent.
623        assert_eq!(<LinearAxis<9>>::MAX_SEARCH_COMPARISONS, 8);
624        assert_eq!(<BinaryAxis<9>>::MAX_SEARCH_COMPARISONS, 4);
625        assert_eq!(<UniformAxis<9, 100, 50>>::MAX_SEARCH_COMPARISONS, 0);
626        assert_eq!(<BucketedAxis<9, 4>>::MAX_SEARCH_COMPARISONS, 8);
627    }
628
629    #[test]
630    fn stored_bytes_are_exactly_what_each_strategy_declares() {
631        assert_eq!(<LinearAxis<9>>::KNOT_BYTES, 18);
632        assert_eq!(<LinearAxis<9>>::INDEX_BYTES, 0);
633        assert_eq!(<BinaryAxis<9>>::KNOT_BYTES, 18);
634        assert_eq!(<BinaryAxis<9>>::INDEX_BYTES, 0);
635        assert_eq!(<UniformAxis<9, 100, 50>>::KNOT_BYTES, 0);
636        assert_eq!(<UniformAxis<9, 100, 50>>::INDEX_BYTES, 0);
637        assert_eq!(<BucketedAxis<9, 4>>::KNOT_BYTES, 18);
638        assert_eq!(<BucketedAxis<9, 4>>::INDEX_BYTES, 8);
639
640        // The declared figures match the arrays actually referenced.
641        assert_eq!(<LinearAxis<9>>::KNOT_BYTES, size_of::<[u16; 9]>());
642        assert_eq!(<BucketedAxis<9, 4>>::INDEX_BYTES, size_of::<[u16; 4]>());
643    }
644
645    #[test]
646    fn a_uniform_axis_occupies_no_storage_and_the_others_are_thin_handles() {
647        // The descriptor lives in the type, so the value is zero-sized: a
648        // uniform axis costs no static bytes and nothing in the handle either.
649        assert_eq!(size_of::<UniformAxis<9, 100, 50>>(), 0);
650
651        assert_eq!(size_of::<LinearAxis<9>>(), size_of::<usize>());
652        assert_eq!(size_of::<BinaryAxis<9>>(), size_of::<usize>());
653        assert_eq!(size_of::<BucketedAxis<9, 4>>(), 2 * size_of::<usize>());
654    }
655
656    #[test]
657    fn a_strategy_is_a_type_and_never_a_runtime_discriminant() {
658        // Each axis is exactly its stored references: there is no tag byte to
659        // select an implementation with, on any of the four.
660        assert_eq!(size_of::<LinearAxis<9>>(), size_of::<&'static [u16; 9]>());
661        assert_eq!(size_of::<BinaryAxis<9>>(), size_of::<&'static [u16; 9]>());
662        assert_eq!(
663            size_of::<BucketedAxis<9, 4>>(),
664            size_of::<&'static [u16; 9]>() + size_of::<&'static [u16; 4]>()
665        );
666
667        // And the default surface is unchanged by the existence of the other
668        // three: same handle as a surface that names its strategies explicitly.
669        assert_eq!(
670            size_of::<BilinearSurface<9, 3>>(),
671            size_of::<BilinearSurface<9, 3, BinaryAxis<9>, BinaryAxis<3>>>()
672        );
673    }
674
675    #[test]
676    fn the_default_surface_is_the_binary_pairing() {
677        // Source compatibility, stated as a test: the defaulted type parameters
678        // resolve to the binary strategy on both axes, and the two spellings
679        // are the same type and the same value.
680        let defaulted: BilinearSurface<9, 3> =
681            BilinearSurface::new(&UNIFORM_KNOTS, &Y_KNOTS, &VALUES);
682        let explicit: BilinearSurface<9, 3, BinaryAxis<9>, BinaryAxis<3>> =
683            BilinearSurface::from_axes(BINARY_X, BINARY_Y, &VALUES);
684
685        assert_eq!(defaulted, explicit);
686    }
687}
ph_surfaces/axis/mod.rs

ph_surfaces/axis/
mod.rs
