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.
13	import Base
14	import ./gf.bend as G
15	
16	type 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
20	def 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
28	def 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	
35	def Gf8Tab.exp_table(+f: G.Gf8Field) -> Array<U32>:
36	  gf8tab.fill.exp(510n, [0 : U32*512n], f, 1, 0)
37	
38	def Gf8Tab.log_table(+f: G.Gf8Field) -> Array<U32>:
39	  gf8tab.fill.log(255n, [0 : U32*256n], f, 1, 0)
40	
41	def 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	
46	def gf8tab.exp.fin(r: Array<U32> & U32, l: Array<U32>) -> Gf8Tab & U32:
47	  (e, v) = r
48	  (Gf8Tab{e, l}, v)
49	
50	def 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
55	def 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)
61	def 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	
66	def 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)
75	def 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	
79	def 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	
83	def 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
93	def 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)
99	def 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	
104	def 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	
108	def 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
118	def 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)