tables.bend
bend-osdev-gf@0.1.0.0 · 120 lines · 0 definitions
1# bend-osdev-gf, the table-driven fast path for GF(2^8): exponential
2# (antilog) and logarithm tables to the field's generator, and
3# multiplication, inversion and division through them.
4#
5# exp[i] = gen^i for i from 0 to 509 (two periods of 255), so exp[log a +
6# log b] needs no reduction modulo 255; log[a] is the i < 255 with gen^i =
7# a, for a nonzero (log[0] is 0 and never read). The tables are built from
8# gf.bend's reference multiplication; they are correct only when gen
9# generates the field (it does for the named fields).
10#
11# A Gf8Tab holds two Arrays, so it has one owner: every operation hands it
12# back beside its result. Build it once (Gf8Tab.new) and thread it through.
13import Base
14import bend-osdev-gf@0.1.0.0/gf.bend as G
15
16type Gf8Tab is Type:
17 Gf8Tab{exp: Array<U32>, log: Array<U32>}
18
19# exp[i] for i from i0, n entries, with cur = gen^i0
20def gf8tab.fill.exp(n: Nat, a: Array<U32>, +f: G.Gf8Field, +cur: U32, +i: U32) -> Array<U32>:
21 match n:
22 case 0n:
23 a
24 case 1n+k:
25 gf8tab.fill.exp(k, Array.set(U32, a, i, cur), f, G.Gf8.mul(f, G.Gf8.gen(f), cur), U32.add(i, 1))
26
27# log[gen^i] = i for i from i0, n entries
28def gf8tab.fill.log(n: Nat, a: Array<U32>, +f: G.Gf8Field, +cur: U32, +i: U32) -> Array<U32>:
29 match n:
30 case 0n:
31 a
32 case 1n+k:
33 gf8tab.fill.log(k, Array.set(U32, a, cur, i), f, G.Gf8.mul(f, G.Gf8.gen(f), cur), U32.add(i, 1))
34
35def Gf8Tab.exp_table(+f: G.Gf8Field) -> Array<U32>:
36 gf8tab.fill.exp(510n, [0 : U32*512n], f, 1, 0)
37
38def Gf8Tab.log_table(+f: G.Gf8Field) -> Array<U32>:
39 gf8tab.fill.log(255n, [0 : U32*256n], f, 1, 0)
40
41def Gf8Tab.new(+f: G.Gf8Field) -> Gf8Tab:
42 Gf8Tab{Gf8Tab.exp_table(f), Gf8Tab.log_table(f)}
43
44# Lookups hand the table back: each helper takes an Array.get result
45
46def gf8tab.exp.fin(r: Array<U32> & U32, l: Array<U32>) -> Gf8Tab & U32:
47 (e, v) = r
48 (Gf8Tab{e, l}, v)
49
50def gf8tab.log.fin(e: Array<U32>, r: Array<U32> & U32) -> Gf8Tab & U32:
51 (l, v) = r
52 (Gf8Tab{e, l}, v)
53
54# gen^i, for i below 510
55def Gf8Tab.exp(t: Gf8Tab, i: U32) -> Gf8Tab & U32:
56 match t:
57 case Gf8Tab{e, l}:
58 gf8tab.exp.fin(Array.get(U32, e, i), l)
59
60# the logarithm of a nonzero a (0 for a = 0)
61def Gf8Tab.log(t: Gf8Tab, a: U32) -> Gf8Tab & U32:
62 match t:
63 case Gf8Tab{e, l}:
64 gf8tab.log.fin(e, Array.get(U32, l, G.Gf8.elt(a)))
65
66def gf8tab.two.idx(div: Bool, +lx: U32, +ly: U32) -> U32:
67 match div:
68 case True{}:
69 U32.sub(U32.add(lx, 255), ly)
70 case False{}:
71 U32.add(lx, ly)
72
73# exp[log x + log y + k], where k is 0 (multiplying) or 255 - 2 log y
74# (dividing: log x + 255 - log y)
75def gf8tab.two.fin(e: Array<U32>, ry: Array<U32> & U32, +lx: U32, div: Bool) -> Gf8Tab & U32:
76 (l, ly) = ry
77 gf8tab.exp.fin(Array.get(U32, e, gf8tab.two.idx(div, lx, ly)), l)
78
79def gf8tab.two.mid(e: Array<U32>, rx: Array<U32> & U32, +y: U32, div: Bool) -> Gf8Tab & U32:
80 (l, lx) = rx
81 gf8tab.two.fin(e, Array.get(U32, l, y), lx, div)
82
83def gf8tab.two.pick(z: Bool, t: Gf8Tab, +x: U32, +y: U32, div: Bool) -> Gf8Tab & U32:
84 match z:
85 case True{}:
86 (t, 0)
87 case False{}:
88 match t:
89 case Gf8Tab{e, l}:
90 gf8tab.two.mid(e, Array.get(U32, l, x), y, div)
91
92# a * b = exp[log a + log b], or 0 if either is 0
93def Gf8Tab.mul(t: Gf8Tab, a: U32, b: U32) -> Gf8Tab & U32:
94 +x = G.Gf8.elt(a)
95 +y = G.Gf8.elt(b)
96 gf8tab.two.pick(Bool.or(U32.is_eq(x, 0), U32.is_eq(y, 0)), t, x, y, False{})
97
98# a / b = exp[log a + 255 - log b], or 0 if either is 0 (as Gf8.div)
99def Gf8Tab.div(t: Gf8Tab, a: U32, b: U32) -> Gf8Tab & U32:
100 +x = G.Gf8.elt(a)
101 +y = G.Gf8.elt(b)
102 gf8tab.two.pick(Bool.or(U32.is_eq(x, 0), U32.is_eq(y, 0)), t, x, y, True{})
103
104def gf8tab.inv.fin(e: Array<U32>, rx: Array<U32> & U32) -> Gf8Tab & U32:
105 (l, lx) = rx
106 gf8tab.exp.fin(Array.get(U32, e, U32.sub(255, lx)), l)
107
108def gf8tab.inv.pick(z: Bool, t: Gf8Tab, +x: U32) -> Gf8Tab & U32:
109 match z:
110 case True{}:
111 (t, 0)
112 case False{}:
113 match t:
114 case Gf8Tab{e, l}:
115 gf8tab.inv.fin(e, Array.get(U32, l, x))
116
117# a^-1 = exp[255 - log a], and the inverse of 0 is 0
118def Gf8Tab.inv(t: Gf8Tab, a: U32) -> Gf8Tab & U32:
119 +x = G.Gf8.elt(a)
120 gf8tab.inv.pick(U32.is_eq(x, 0), t, x)