nx_p256_solinas_timing.nx source
↩ module page · 122 lines · 3412 B
1// nx_p256_solinas_timing.nx -- honest FAST(Solinas) vs SLOW(bit-serial)
2// timing for the P-256 field multiply used by TLS ECDSA cert verify.
3//
4// The Solinas fast reduction is ALREADY the production path (p256_field_mul);
5// the bit-serial p256_field_mul_slow is the retained oracle == the "naive
6// reduction" baseline. Timing both on the SAME workload quantifies the
7// reduction speedup that Solinas already delivers. Seeds from a runtime
8// clock and chains a=mul(a,b) (data-dependent) so the optimizer cannot
9// const-fold the field arithmetic away. No correctness claim here -- see
10// nx_p256_solinas_difftest.nx for the bit-identical proof.
11//
12// license_tier: ORIGINAL
13
14import "nx_syscalls.nx"
15import "nx_u256.nx"
16import "nx_p256_field.nx"
17import "nx_p256_field_mul.nx"
18const K_MAGIC_2654435761: i64 = 2654435761
19const K_MAGIC_40503: i64 = 40503
20const K_MAGIC_30000: i64 = 30000
21
22func _tm_print_dec(n: i64) -> i64 {
23 let out: *u8 = sys_mmap(32)
24 if n == 0 {
25 out[0] = 48 as u8
26 sys_write(1, out, 1)
27 return 0
28 }
29 let tmp: *u8 = sys_mmap(32)
30 var v: i64 = n
31 var i: i64 = 0
32 while v > 0 {
33 let d: i64 = v - (v / 10) * 10
34 tmp[i] = (48 + d) as u8
35 v = v / 10
36 i = i + 1
37 }
38 var j: i64 = 0
39 while i > 0 {
40 i = i - 1
41 out[j] = tmp[i]
42 j = j + 1
43 }
44 sys_write(1, out, j)
45 return 0
46}
47
48func _tm_seed(a: *i64, b: *i64, seed: i64) -> i64 {
49 var j: i64 = 0
50 while j < NX_U256_LIMBS {
51 a[j] = (seed + j * K_MAGIC_2654435761) & NX_U256_LIMB_MASK
52 b[j] = (seed * 3 + j * K_MAGIC_40503) & NX_U256_LIMB_MASK
53 j = j + 1
54 }
55 return 0
56}
57
58func main() -> i64 {
59 let _s: i64 = nx_scratch_save()
60 let a: *i64 = u256_alloc()
61 let b: *i64 = u256_alloc()
62 let r: *i64 = u256_alloc()
63 let seed: i64 = sys_now_us() // runtime -> defeats const-fold
64 let ITERS: i64 = K_MAGIC_30000
65 var acc: i64 = 0
66
67 // ---- FAST (Solinas) ----
68 _tm_seed(a, b, seed)
69 let f0: i64 = sys_now_us()
70 var i: i64 = 0
71 while i < ITERS {
72 p256_field_mul(r, a, b)
73 var k: i64 = 0
74 while k < NX_U256_LIMBS {
75 a[k] = r[k]
76 k = k + 1
77 }
78 acc = acc + (r[0] & 0xFF)
79 i = i + 1
80 }
81 let f1: i64 = sys_now_us()
82
83 // ---- SLOW (bit-serial, == naive-reduction baseline) ----
84 _tm_seed(a, b, seed)
85 let s0: i64 = sys_now_us()
86 i = 0
87 while i < ITERS {
88 p256_field_mul_slow(r, a, b)
89 var k2: i64 = 0
90 while k2 < NX_U256_LIMBS {
91 a[k2] = r[k2]
92 k2 = k2 + 1
93 }
94 acc = acc + (r[0] & 0xFF)
95 i = i + 1
96 }
97 let s1: i64 = sys_now_us()
98
99 let fast_us: i64 = f1 - f0
100 let slow_us: i64 = s1 - s0
101
102 sys_write(1, "fieldmul x" as *u8, 10)
103 _tm_print_dec(ITERS)
104 sys_write(1, " FAST(Solinas)=" as *u8, 16)
105 _tm_print_dec(fast_us)
106 sys_write(1, "us (" as *u8, 4)
107 _tm_print_dec(fast_us * 1000 / ITERS)
108 sys_write(1, "ns/mul) SLOW(bitserial)=" as *u8, 25)
109 _tm_print_dec(slow_us)
110 sys_write(1, "us (" as *u8, 4)
111 _tm_print_dec(slow_us * 1000 / ITERS)
112 sys_write(1, "ns/mul) speedup=" as *u8, 17)
113 if fast_us > 0 {
114 _tm_print_dec(slow_us / fast_us)
115 } else {
116 _tm_print_dec(0)
117 }
118 sys_write(1, "x\n" as *u8, 2)
119
120 nx_scratch_restore(_s)
121 return (acc + seed) & 255
122}