nx_fx.nx source

1// fx.nx -- deterministic Q16.16 fixed-point math. 2// 3// Why fixed-point and not IEEE-754 float: 4// Rollback netcode (GGPO 2006, Skullgirls, Killer Instinct) requires 5// bit-identical simulation across machines. IEEE-754 + Math.sin 6// cannot deliver this -- different JS engines (V8, SpiderMonkey, 7// JavaScriptCore) ship different sin/cos implementations, and even 8// addition order can diverge under JIT inlining. Fixed-point 9// integer math is the only way to guarantee "same input → same bits 10// on every machine." 11// 12// Representation: Q16.16 13// - 64-bit signed integer: high 16 bits integer part, low 16 bits 14// fractional part. Negative values use two's complement. 15// - Range: ±32767.99998... blocks. Precision: 1/65536 ≈ 15 μm at 16// 1 m = 1 block. Adequate for voxel games, physics, gameplay 17// sim up to ~32 km arenas. 18// 19// Invariants (enforced, not hoped): 20// FX1 No IEEE-754 anywhere. NishiLang has no float type today, so 21// this is trivial -- but if floats ever land, fx.nx does not 22// use them. 23// FX2 fx_mul and fx_div round toward zero (arithmetic shift, not 24// round-to-nearest). Deterministic and simple; callers needing 25// round-to-nearest do `(a + (b >> 1)) / b` explicitly. 26// FX3 sin/cos via CORDIC algorithm -- 16 iterations, ~Q16.16 27// precision, no Math.sin dependency. Converges through a 28// precomputed atan table. Every implementation (NishiVM, 29// native C VM, future Nishi silicon) produces bit-identical 30// results by construction. 31// FX4 Overflow in fx_mul is possible if both operands exceed 16-bit 32// integer range. Callers are responsible for clamping; we do 33// NOT implement saturation arithmetic by default (silent 34// saturation masks bugs; explicit clamp is better). 35// 36// References: 37// - Volder 1959, "The CORDIC Trigonometric Computing Technique" 38// - Kota-Kuroda-Shimamura 1989, "A High-Speed Fixed-Point Multiplier 39// Using Carry-Propagation-Free Adders" 40// - GGPO 2006 whitepaper (rollback determinism rationale) 41 42// nx_safety_envelope: 43// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 44// sil_target: SIL1 45// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail] 46// verdict: NOT_YET_EVALUATED 47 48import "nx_syscalls.nx" 49const FX_MAGIC_51472: i64 = 51472 50const FX_MAGIC_30386: i64 = 30386 51const FX_MAGIC_16055: i64 = 16055 52const FX_MAGIC_8150: i64 = 8150 53const FX_MAGIC_4091: i64 = 4091 54const FX_MAGIC_2047: i64 = 2047 55const FX_MAGIC_1024: i64 = 1024 56 57// ---- scale knobs --------------------------------------------------- 58 59const FX_SHIFT: i64 = 16 60const FX_ONE: i64 = 65536 // 2^16 61const FX_HALF: i64 = 32768 // 0.5 in Q16.16 62const FX_FRAC_MASK: i64 = 0xFFFF // low 16 bits 63const FX_TWO_PI: i64 = 411775 // round(2π * 65536); 1 rev in Q16.16 64const FX_PI: i64 = 205887 // round(π * 65536) 65const FX_HALF_PI: i64 = 102944 // round(π/2 * 65536) 66 67// CORDIC scaling factor K_n for n=16 iterations: ≈ 0.6072529350088814 68// Stored in Q16.16 = round(0.6072529 * 65536) = 39797. 69const FX_CORDIC_K: i64 = 39797 70 71// ---- basic arithmetic --------------------------------------------- 72 73// Addition / subtraction are plain integer ops -- the same-format 74// operands, same-format result invariant means no scaling needed. 75func fx_add(a: i64, b: i64) -> i64 { return a + b } 76func fx_sub(a: i64, b: i64) -> i64 { return a - b } 77func fx_neg(a: i64) -> i64 { return 0 - a } 78 79// Q16.16 * Q16.16 = Q32.32; we shift right by 16 to get Q16.16 back. 80// Careful: intermediate product can overflow i64 if a and b both 81// exceed ~ Q16.0 range. FX4 responsibility. 82func fx_mul(a: i64, b: i64) -> i64 { 83 return (a * b) >> FX_SHIFT 84} 85 86// Q16.16 / Q16.16 = Q16.16. Shift LHS up by 16 before dividing so 87// the result carries the correct fractional bits. Does integer 88// truncation toward zero (FX2). 89func fx_div(a: i64, b: i64) -> i64 { 90 return (a << FX_SHIFT) / b 91} 92 93// ---- conversions --------------------------------------------------- 94 95func fx_from_int(n: i64) -> i64 { return n << FX_SHIFT } 96 97// Truncate Q16.16 to integer (toward zero). 98func fx_to_int(a: i64) -> i64 { return a >> FX_SHIFT } 99 100// Construct Q16.16 from (integer, numerator, denominator): useful for 101// exact rationals like "1/3 of a block". 102func fx_from_frac(num: i64, den: i64) -> i64 { 103 return (num << FX_SHIFT) / den 104} 105 106// ---- CORDIC sin/cos ----------------------------------------------- 107// 108// Rotation-mode CORDIC. Input: angle in Q16.16 radians (call 109// fx_normalize_angle first if you can't guarantee |angle| <= π/2). 110// Output: writes sin to *sin_out, cos to *cos_out, both Q16.16. 111// 112// Precomputed atan(2^-i) in Q16.16 for i = 0..15. Each entry is 113// round(atan(2^-i) * 65536). These are constant across all targets 114// by spec (not by local IEEE-754 evaluation). 115func fx_cordic_atan(i: i64) -> i64 { 116 if i == 0 { return FX_MAGIC_51472 } // atan(1) * 2^16 117 if i == 1 { return FX_MAGIC_30386 } // atan(1/2) 118 if i == 2 { return FX_MAGIC_16055 } // atan(1/4) 119 if i == 3 { return FX_MAGIC_8150 } // atan(1/8) 120 if i == 4 { return FX_MAGIC_4091 } // atan(1/16) 121 if i == 5 { return FX_MAGIC_2047 } // atan(1/32) 122 if i == 6 { return FX_MAGIC_1024 } // atan(1/64) 123 if i == 7 { return 512 } // atan(1/128) 124 if i == 8 { return 256 } // atan(1/256) 125 if i == 9 { return 128 } 126 if i == 10 { return 64 } 127 if i == 11 { return 32 } 128 if i == 12 { return 16 } 129 if i == 13 { return 8 } 130 if i == 14 { return 4 } 131 return 2 // atan(2^-15) 132} 133 134// Normalise angle into [-π, π] (Q16.16). Strips off full-rotation 135// multiples of 2π so CORDIC convergence stays stable. 136func fx_normalize_angle(a: i64) -> i64 { 137 var r: i64 = a 138 while r > FX_PI { r = r - FX_TWO_PI } 139 while r < (0 - FX_PI) { r = r + FX_TWO_PI } 140 return r 141} 142 143// Compute sin(theta) and cos(theta) for theta in Q16.16. Writes both 144// outputs to caller-supplied slots so callers can take both without 145// a second pass. 146// 147// CORDIC range is [-π/2, π/2] in the basic form. To cover the full 148// [-π, π] we reduce via quadrant rules: 149// θ ∈ [π/2, π] -> θ' = π - θ; sin = sin(θ'); cos = -cos(θ') 150// θ ∈ [-π, -π/2] -> θ' = -π - θ; sin = -sin(θ'); cos = -cos(θ') 151func fx_sin_cos(theta_raw: i64, sin_out: *i64, cos_out: *i64) -> i64 { 152 let theta: i64 = fx_normalize_angle(theta_raw) 153 var t: i64 = theta 154 var flip_cos: i64 = 0 155 var flip_sin: i64 = 0 156 157 if t > FX_HALF_PI { 158 t = FX_PI - t 159 flip_cos = 1 160 } 161 if t < (0 - FX_HALF_PI) { 162 t = (0 - FX_PI) - t 163 flip_sin = 1 164 flip_cos = 1 165 } 166 167 // Core CORDIC loop: start at (K, 0), iteratively converge on 168 // angle t. 169 var x: i64 = FX_CORDIC_K 170 var y: i64 = 0 171 var z: i64 = t 172 var i: i64 = 0 173 while i < 16 { 174 let atan_i: i64 = fx_cordic_atan(i) 175 let dx: i64 = y >> i 176 let dy: i64 = x >> i 177 if z >= 0 { 178 x = x - dx 179 y = y + dy 180 z = z - atan_i 181 } else { 182 x = x + dx 183 y = y - dy 184 z = z + atan_i 185 } 186 i = i + 1 187 } 188 189 if flip_sin == 1 { y = 0 - y } 190 if flip_cos == 1 { x = 0 - x } 191 192 *sin_out = y 193 *cos_out = x 194 return 0 195} 196 197// Convenience wrappers for callers that only want one component. 198func fx_sin(theta: i64) -> i64 { 199 let s_raw: *u8 = sys_mmap(16) 200 let c_raw: *u8 = sys_mmap(16) 201 let s: *i64 = s_raw as *i64 202 let c: *i64 = c_raw as *i64 203 fx_sin_cos(theta, s, c) 204 return *s 205} 206 207func fx_cos(theta: i64) -> i64 { 208 let s_raw: *u8 = sys_mmap(16) 209 let c_raw: *u8 = sys_mmap(16) 210 let s: *i64 = s_raw as *i64 211 let c: *i64 = c_raw as *i64 212 fx_sin_cos(theta, s, c) 213 return *c 214} 215 216// ---- game-sim convenience: u8 yaw angle -------------------------- 217// 218// Many game protocols (including ours) transmit yaw as a single byte: 219// 256 discrete angles equally spaced around the circle. This helper 220// converts a yaw byte to Q16.16 radians using the exact formula 221// angle = yaw * 2π / 256 (Q16.16) 222// implemented as (yaw * FX_TWO_PI) / 256, where FX_TWO_PI is the 223// same integer on every target -- no target-dependent rounding. 224func fx_yaw_u8_to_angle(yaw: i64) -> i64 { 225 let y: i64 = yaw & 0xFF 226 return (y * FX_TWO_PI) / 256 227} 228 229// ---- compile-only smoke ------------------------------------------ 230// 231// Exercises each primitive. Real validation (bit-exact comparison 232// with reference values computed offline) comes in fx_test.nx once 233// an execution harness is available on this host. 234func main() -> i64 { 235 // Trig smoke: sin(0) should be 0, cos(0) should be FX_ONE. 236 let zero: i64 = 0 237 let s0: i64 = fx_sin(zero) 238 let c0: i64 = fx_cos(zero) 239 240 // sin(π/2) ≈ 1.0 → close to FX_ONE. 241 let s1: i64 = fx_sin(FX_HALF_PI) 242 243 // Multiply: 2.5 * 4.0 = 10.0 in Q16.16. 244 let a: i64 = FX_ONE * 2 + FX_HALF // 2.5 245 let b: i64 = FX_ONE * 4 // 4.0 246 let prod: i64 = fx_mul(a, b) // expect 10 << 16 247 248 // Divide: 1.0 / 3.0 ≈ 21845 in Q16.16. 249 let third: i64 = fx_div(FX_ONE, FX_ONE * 3) 250 251 // Yaw conversion: yaw=64 (quarter-turn) → angle ≈ π/2. 252 let q: i64 = fx_yaw_u8_to_angle(64) 253 254 return s0 + c0 + s1 + prod + third + q 255}