tables.bend

bend-osdev-gf@0.1.1.0 · 120 lines · 19 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.1.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)