src/math/instances.bend

bend-collections-laws-crypto@1.0.0.0 · 197 lines · 11 definitions

1import Base
2import bend-collections-laws-crypto@1.0.0.0/src/math/num.bend as N
3import bend-collections-laws-crypto@1.0.0.0/src/math/u64.bend as W
4import bend-collections-laws-crypto@1.0.0.0/src/math/w64.bend as X
5import bend-collections-laws-crypto@1.0.0.0/src/math/generic.bend as G
6import bend-collections-laws-crypto@1.0.0.0/src/math/natural.bend as M
7
8# Numeric instances for generic.bend (num.bend's Op and Test per type):
9# U32 (Base), U64 (the two-limb U64 of u64.bend, fast arithmetic in
10# w64.bend) and F32 (Base's float); F64 lives in f64.bend.
11#
12#   G.gcd(~U32, ~I.u32_op, ~I.u32_is, a, b)
13#   G.gcd(~W.U64, ~I.u64_op, ~I.u64_is, a, b)
14#   G.pow(~F32, ~I.f32_op, ~I.f32_is, x, k)
15#
16# Fixed widths are checked: generic.bend forms Add and Mul only next to their
17# over-test and uses the result only if the test says it fits.
18
19# ---- U32 ----
20
21# a * b >= 2^32: the full product has a nonzero high word
22def u32_mul_over(+a: U32, +b: U32) -> Bool:
23  Bool.not(U32.is_zero(X.hi(X.mul32(a, b))))
24
25def u32_mulmod(+a: U32, +b: U32, +m: U32) -> U32:
26  X.mod32(X.mul32(a, b), m)
27
28def u32_op(o: N.Op<U32>) -> U32:
29  match o:
30    case N.ZeroOp{}:
31      0
32    case N.One{}:
33      1
34    case N.Add{a, b}:
35      U32.add(a, b)
36    case N.Sub{a, b}:
37      U32.sub(a, b)
38    case N.Mul{a, b}:
39      U32.mul(a, b)
40    case N.Neg{a}:
41      U32.sub(0, a)
42    case N.Abs{a}:
43      a
44    case N.Quot{a, b}:
45      U32.div(a, b)
46    case N.Rem{a, b}:
47      U32.mod(a, b)
48    case N.Half{a}:
49      U32.shr(a)
50    case N.MulMod{a, b, m}:
51      u32_mulmod(a, b, m)
52    case N.Pow2{k}:
53      X.pow2(k)
54    case N.Sqrt{a}:
55      X.isqrt32(a)
56    case N.PowMod{a, e, m}:
57      X.mpow32(a, e, m)
58
59    case N.GcdSmall{a, b}:
60      0
61def u32_add_over(+a: U32, +b: U32) -> Bool:
62  U32.is_lt(U32.add(a, b), a)
63
64def u32_odd(+a: U32) -> Bool:
65  U32.is_eq(U32.and(a, 1), 1)
66
67def u32_is(t: N.Test<U32>) -> Bool:
68  match t:
69    case N.Lt{a, b}:
70      U32.is_lt(a, b)
71    case N.AddOver{a, b}:
72      u32_add_over(a, b)
73    case N.MulOver{a, b}:
74      u32_mul_over(a, b)
75    case N.Odd{a}:
76      u32_odd(a)
77    case N.IsZero{a}:
78      U32.is_zero(a)
79    case N.FastDiv{}:
80      True{}
81    case N.Mont{m}:
82      X.mont32_ok(m)
83
84# ---- U64 ----
85    case N.Small{a, b}:
86      False{}
87
88# 2^k for k < 64
89def u64_pow2(+k: Nat) -> W.U64:
90  X.w_pow2(k, Nat.is_lt(k, 32n))
91
92def u64_op(o: N.Op<W.U64>) -> W.U64:
93  match o:
94    case N.ZeroOp{}:
95      W.U64{0, 0}
96    case N.One{}:
97      W.U64{1, 0}
98    case N.Add{a, b}:
99      X.add(a, b)
100    case N.Sub{a, b}:
101      X.sub(a, b)
102    case N.Mul{a, b}:
103      X.mul(a, b)
104    case N.Neg{a}:
105      X.sub(W.U64{0, 0}, a)
106    case N.Abs{a}:
107      a
108    case N.Quot{a, b}:
109      X.quot(a, b)
110    case N.Rem{a, b}:
111      X.rem(a, b)
112    case N.Half{a}:
113      X.half(a)
114    case N.MulMod{a, b, m}:
115      X.mulmod(a, b, m)
116    case N.Pow2{k}:
117      u64_pow2(k)
118    case N.Sqrt{a}:
119      X.isqrt(a)
120    case N.PowMod{a, e, m}:
121      X.mpow(a, e, m)
122
123    case N.GcdSmall{a, b}:
124      X.of48(M.gcd(X.n48(a), X.n48(b)))
125def u64_is(t: N.Test<W.U64>) -> Bool:
126  match t:
127    case N.Lt{a, b}:
128      X.lt(a, b)
129    case N.AddOver{a, b}:
130      X.add_over(a, b)
131    case N.MulOver{a, b}:
132      X.mul_over(a, b)
133    case N.Odd{a}:
134      X.odd(a)
135    case N.IsZero{a}:
136      X.is_zero(a)
137    case N.FastDiv{}:
138      False{}
139    case N.Mont{m}:
140      X.mont_ok(m)
141    case N.Small{a, b}:
142      X.small2(a, b)
143
144# ---- F32 ----
145
146def f32_op(o: N.Op<F32>) -> F32:
147  match o:
148    case N.ZeroOp{}:
149      0.0
150    case N.One{}:
151      1.0
152    case N.Add{a, b}:
153      F32.add(a, b)
154    case N.Sub{a, b}:
155      F32.sub(a, b)
156    case N.Mul{a, b}:
157      F32.mul(a, b)
158    case N.Neg{a}:
159      F32.neg(a)
160    case N.Abs{a}:
161      F32.abs(a)
162    case N.Quot{a, b}:
163      F32.div(a, b)
164    case N.Rem{a, b}:
165      F32.mod(a, b)
166    case N.Half{a}:
167      F32.mul(a, 0.5)
168    case N.MulMod{a, b, m}:
169      F32.mod(F32.mul(a, b), m)
170    case N.Pow2{k}:
171      F32.pow(2.0, F32.from_nat(k))
172    case N.Sqrt{a}:
173      F32.sqrt(a)
174    case N.PowMod{a, e, m}:
175      0.0
176
177    case N.GcdSmall{a, b}:
178      0.0
179def f32_is(t: N.Test<F32>) -> Bool:
180  match t:
181    case N.Lt{a, b}:
182      F32.is_lt(a, b)
183    case N.AddOver{a, b}:
184      False{}
185    case N.MulOver{a, b}:
186      False{}
187    case N.Odd{a}:
188      False{}
189    case N.IsZero{a}:
190      F32.is_eq(a, 0.0)
191    case N.FastDiv{}:
192      True{}
193    case N.Mont{m}:
194      False{}
195
196    case N.Small{a, b}:
197      False{}