renew_fixed/
angle.rs

1//! Angles, and the sine table they read.
2//!
3//! # Binary angles
4//!
5//! A full turn is 2³² units, so an angle is a `u32` and wrapping is exact
6//! integer overflow. That is the whole reason for the representation: in
7//! radians the modulus is 2π, which is irrational and therefore not
8//! representable, so every wrap would lose precision and two machines
9//! wrapping at different times would drift apart. Here, adding a full turn
10//! is the identity, exactly, forever.
11//!
12//! # The table
13//!
14//! 513 entries covering a quarter turn, with the other three quadrants
15//! reached by symmetry. Linear interpolation between entries, rounded rather
16//! than truncated.
17//!
18//! **Measured worst error: 1.0322 units in the last place** over a three-million-point sweep
19//! of the whole circle, against a double-precision reference. That is the
20//! floor for a table of any size — the entries themselves are rounded to half
21//! a unit, interpolating between two of them inherits that, and the
22//! interpolation rounds once more. Sixteen times the entries buys 0.03 of a
23//! unit, which is why this table is 2 KB rather than 32.
24
25use crate::Fixed;
26
27/// Entries in the quarter-turn table, excluding the endpoint.
28const QUARTER_ENTRIES: u32 = 512;
29
30/// Binary angle units in a quarter turn.
31const QUARTER_TURN: u32 = 1 << 30;
32
33/// How many low bits of an angle fall between two table entries.
34const STEP_BITS: u32 = 30 - 9;
35
36/// `sin` over a quarter turn, in raw [`Fixed`] units.
37///
38/// Generated, not hand-written, and checked by a test against a
39/// double-precision reference — the generator lives beside the note that
40/// chose the table size. First entry is exactly zero and last is exactly
41/// one, which the same test asserts, because a table whose endpoints drift
42/// makes every symmetry below wrong at the quadrant boundaries.
43static QUARTER_SINE: [i32; 513] = [
44    0, 201, 402, 603, 804, 1005, 1206, 1407, 1608, 1809, 2010, 2211, 2412, 2613, 2814, 3015, 3216,
45    3417, 3617, 3818, 4019, 4219, 4420, 4621, 4821, 5022, 5222, 5422, 5623, 5823, 6023, 6224, 6424,
46    6624, 6824, 7024, 7224, 7423, 7623, 7823, 8022, 8222, 8421, 8621, 8820, 9019, 9218, 9417, 9616,
47    9815, 10014, 10212, 10411, 10609, 10808, 11006, 11204, 11402, 11600, 11798, 11996, 12193,
48    12391, 12588, 12785, 12983, 13180, 13376, 13573, 13770, 13966, 14163, 14359, 14555, 14751,
49    14947, 15143, 15338, 15534, 15729, 15924, 16119, 16314, 16508, 16703, 16897, 17091, 17285,
50    17479, 17673, 17867, 18060, 18253, 18446, 18639, 18832, 19024, 19216, 19409, 19600, 19792,
51    19984, 20175, 20366, 20557, 20748, 20939, 21129, 21320, 21510, 21699, 21889, 22078, 22268,
52    22457, 22645, 22834, 23022, 23210, 23398, 23586, 23774, 23961, 24148, 24335, 24521, 24708,
53    24894, 25080, 25265, 25451, 25636, 25821, 26005, 26190, 26374, 26558, 26742, 26925, 27108,
54    27291, 27474, 27656, 27838, 28020, 28202, 28383, 28564, 28745, 28926, 29106, 29286, 29466,
55    29645, 29824, 30003, 30182, 30360, 30538, 30716, 30893, 31071, 31248, 31424, 31600, 31776,
56    31952, 32127, 32303, 32477, 32652, 32826, 33000, 33173, 33347, 33520, 33692, 33865, 34037,
57    34208, 34380, 34551, 34721, 34892, 35062, 35231, 35401, 35570, 35738, 35907, 36075, 36243,
58    36410, 36577, 36744, 36910, 37076, 37241, 37407, 37572, 37736, 37900, 38064, 38228, 38391,
59    38554, 38716, 38878, 39040, 39201, 39362, 39523, 39683, 39843, 40002, 40161, 40320, 40478,
60    40636, 40794, 40951, 41108, 41264, 41420, 41576, 41731, 41886, 42040, 42194, 42348, 42501,
61    42654, 42806, 42958, 43110, 43261, 43412, 43562, 43713, 43862, 44011, 44160, 44308, 44456,
62    44604, 44751, 44898, 45044, 45190, 45335, 45480, 45625, 45769, 45912, 46056, 46199, 46341,
63    46483, 46624, 46765, 46906, 47046, 47186, 47325, 47464, 47603, 47741, 47878, 48015, 48152,
64    48288, 48424, 48559, 48694, 48828, 48962, 49095, 49228, 49361, 49493, 49624, 49756, 49886,
65    50016, 50146, 50275, 50404, 50532, 50660, 50787, 50914, 51041, 51166, 51292, 51417, 51541,
66    51665, 51789, 51911, 52034, 52156, 52277, 52398, 52519, 52639, 52759, 52878, 52996, 53114,
67    53232, 53349, 53465, 53581, 53697, 53812, 53926, 54040, 54154, 54267, 54379, 54491, 54603,
68    54714, 54824, 54934, 55043, 55152, 55260, 55368, 55476, 55582, 55689, 55794, 55900, 56004,
69    56108, 56212, 56315, 56418, 56520, 56621, 56722, 56823, 56923, 57022, 57121, 57219, 57317,
70    57414, 57511, 57607, 57703, 57798, 57892, 57986, 58079, 58172, 58265, 58356, 58448, 58538,
71    58628, 58718, 58807, 58896, 58983, 59071, 59158, 59244, 59330, 59415, 59499, 59583, 59667,
72    59750, 59832, 59914, 59995, 60075, 60156, 60235, 60314, 60392, 60470, 60547, 60624, 60700,
73    60776, 60851, 60925, 60999, 61072, 61145, 61217, 61288, 61359, 61429, 61499, 61568, 61637,
74    61705, 61772, 61839, 61906, 61971, 62036, 62101, 62165, 62228, 62291, 62353, 62415, 62476,
75    62536, 62596, 62655, 62714, 62772, 62830, 62886, 62943, 62998, 63054, 63108, 63162, 63215,
76    63268, 63320, 63372, 63423, 63473, 63523, 63572, 63621, 63668, 63716, 63763, 63809, 63854,
77    63899, 63944, 63987, 64031, 64073, 64115, 64156, 64197, 64237, 64277, 64316, 64354, 64392,
78    64429, 64465, 64501, 64536, 64571, 64605, 64639, 64672, 64704, 64735, 64766, 64797, 64827,
79    64856, 64884, 64912, 64940, 64967, 64993, 65018, 65043, 65067, 65091, 65114, 65137, 65159,
80    65180, 65200, 65220, 65240, 65259, 65277, 65294, 65311, 65328, 65343, 65358, 65373, 65387,
81    65400, 65413, 65425, 65436, 65447, 65457, 65467, 65476, 65484, 65492, 65499, 65505, 65511,
82    65516, 65521, 65525, 65528, 65531, 65533, 65535, 65536, 65536,
83];
84
85/// An angle, as a fraction of a turn.
86///
87/// # Contract
88///
89/// - **A full turn is 2³² units**, so arithmetic wraps exactly and an angle
90///   is always in range by construction. There is no normalisation step and
91///   no way to hold an out-of-range angle.
92/// - **`Ord` follows the underlying bits**, which orders angles by their
93///   position in a turn starting from zero — not by "smallest rotation",
94///   which is not a total order.
95#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
96pub struct Angle(u32);
97
98impl Angle {
99    /// No rotation.
100    pub const ZERO: Self = Self(0);
101    /// A quarter turn: 90 degrees.
102    pub const QUARTER: Self = Self(QUARTER_TURN);
103    /// A half turn: 180 degrees.
104    pub const HALF: Self = Self(QUARTER_TURN * 2);
105    /// Three quarters of a turn: 270 degrees.
106    pub const THREE_QUARTERS: Self = Self(QUARTER_TURN * 3);
107
108    /// From raw binary-angle units.
109    #[must_use]
110    pub const fn from_bits(bits: u32) -> Self {
111        Self(bits)
112    }
113
114    /// The raw units.
115    #[must_use]
116    pub const fn to_bits(self) -> u32 {
117        self.0
118    }
119
120    /// From degrees, exactly for the ones that divide a turn evenly.
121    ///
122    /// Wrapping, so 370 degrees is 10 and −90 is 270 — which is the whole
123    /// point of the representation rather than a convenience.
124    #[must_use]
125    pub const fn from_degrees(degrees: i32) -> Self {
126        // 2^32 / 360 is not an integer, so the multiply happens first and in
127        // 64 bits: the result is exact for every degree value.
128        let turns = (degrees as i64).rem_euclid(360);
129        // `rem_euclid` puts `turns` in [0, 360), so the quotient is in
130        // [0, 2^32) — non-negative and inside a u32 by construction.
131        #[expect(
132            clippy::cast_possible_truncation,
133            clippy::cast_sign_loss,
134            reason = "rem_euclid bounds the value to [0, 2^32)"
135        )]
136        let bits = ((turns << 32) / 360) as u32;
137        Self(bits)
138    }
139
140    /// From a fraction of a turn: `from_turn_ratio(1, 8)` is 45 degrees.
141    ///
142    /// # Panics
143    ///
144    /// If `denominator` is zero.
145    #[must_use]
146    pub const fn from_turn_ratio(numerator: i32, denominator: i32) -> Self {
147        assert!(
148            denominator != 0,
149            "Angle::from_turn_ratio needs a nonzero denominator"
150        );
151        let scaled = ((numerator as i64) << 32) / denominator as i64;
152        // Deliberately wrapping: a ratio past a whole turn, or a negative
153        // one, is a real angle and lands where the turn wraps. That is the
154        // representation's whole point, so truncation here is the intent
155        // rather than a hazard.
156        #[expect(
157            clippy::cast_possible_truncation,
158            clippy::cast_sign_loss,
159            reason = "wrapping is the defined behaviour for angles past a turn"
160        )]
161        let bits = scaled as u32;
162        Self(bits)
163    }
164
165    /// The sine.
166    #[must_use]
167    pub fn sin(self) -> Fixed {
168        let quadrant = self.0 >> 30;
169        let within = self.0 & (QUARTER_TURN - 1);
170        // Quadrants 1 and 3 read the table backwards; 2 and 3 negate. The
171        // reversal is `QUARTER_TURN - within` rather than a separate table,
172        // and it lands exactly on the endpoint when `within` is zero.
173        let magnitude = if quadrant.is_multiple_of(2) {
174            lookup(within)
175        } else {
176            lookup(QUARTER_TURN - within)
177        };
178        if quadrant < 2 { magnitude } else { -magnitude }
179    }
180
181    /// The cosine, which is the sine a quarter turn ahead.
182    #[must_use]
183    pub fn cos(self) -> Fixed {
184        Self(self.0.wrapping_add(QUARTER_TURN)).sin()
185    }
186
187    /// Both, for callers that need them together — which is every rotation.
188    #[must_use]
189    pub fn sin_cos(self) -> (Fixed, Fixed) {
190        (self.sin(), self.cos())
191    }
192}
193
194/// Sine over `[0, QUARTER_TURN]`, interpolated and rounded.
195fn lookup(within: u32) -> Fixed {
196    let index = (within >> STEP_BITS) as usize;
197    // The endpoint: `within == QUARTER_TURN` indexes one past the last gap.
198    if index >= QUARTER_ENTRIES as usize {
199        return Fixed::from_bits(i64::from(QUARTER_SINE[QUARTER_ENTRIES as usize]));
200    }
201    let low = i64::from(QUARTER_SINE[index]);
202    let high = i64::from(QUARTER_SINE[index + 1]);
203    let fraction = i64::from(within & ((1 << STEP_BITS) - 1));
204    // Rounded, not truncated: truncating costs half a unit in the last place
205    // on every interpolation, which is a third of the total error budget for
206    // nothing.
207    let half = 1i64 << (STEP_BITS - 1);
208    Fixed::from_bits(low + (((high - low) * fraction + half) >> STEP_BITS))
209}
210
211impl core::ops::Add for Angle {
212    type Output = Self;
213    /// Wrapping, which is exact: a full turn is the identity.
214    fn add(self, other: Self) -> Self {
215        Self(self.0.wrapping_add(other.0))
216    }
217}
218
219impl core::ops::Sub for Angle {
220    type Output = Self;
221    /// Wrapping, which is exact.
222    fn sub(self, other: Self) -> Self {
223        Self(self.0.wrapping_sub(other.0))
224    }
225}
226
227impl core::ops::Neg for Angle {
228    type Output = Self;
229    fn neg(self) -> Self {
230        Self(self.0.wrapping_neg())
231    }
232}
renew_fixed/angle.rs

renew_fixed/
angle.rs
