1	# bend-osdev-word64: unsigned 64-bit words for bend-osdev, wrapping on overflow.
2	#
3	# Every bend-osdev package that needs 64 bits uses W64, and only through these
4	# defs. A W64 is its two 32-bit halves, each a native U32, so a W64 costs two
5	# machine words (a Word(64n) of bits, used before, cost sixty-four, and records
6	# of several of them were more than Bend's C backend can compile:
7	# bendlang/bend#1069). When Base gains a native U64 (bendlang/bend#1027), only
8	# this file changes. The type is not named U64, so that it cannot clash with
9	# Base's when it arrives.
10	import Base
11	
12	type W64 is Data:
13	  W64{hi: U32, lo: U32}
14	
15	def W64.zero() -> W64:
16	  W64{0, 0}
17	
18	def W64.one() -> W64:
19	  W64{0, 1}
20	
21	def W64.max() -> W64:
22	  W64{4294967295, 4294967295}
23	
24	# Conversions
25	
26	def W64.from_u32(a: U32) -> W64:
27	  W64{0, a}
28	
29	# Splitting a Word(m + n) into its low m and high n bits (bits are stored
30	# least significant first), and joining them back. Named under W64, not Word,
31	# so that they cannot clash with Base if it gains Word.lo, Word.hi or Word.cat.
32	def W64.bits.lo(m: Nat, n: Nat, w: Word(Nat.add(m, n))) -> Word(m):
33	  match m:
34	    case 0n:
35	      WNil{}
36	    case 1n+p:
37	      match w:
38	        case WCon{h, t}:
39	          WCon{h, W64.bits.lo(p, n, t)}
40	
41	def W64.bits.hi(m: Nat, n: Nat, w: Word(Nat.add(m, n))) -> Word(n):
42	  match m:
43	    case 0n:
44	      w
45	    case 1n+p:
46	      match w:
47	        case WCon{h, t}:
48	          W64.bits.hi(p, n, t)
49	
50	def W64.bits.cat(m: Nat, n: Nat, a: Word(m), b: Word(n)) -> Word(Nat.add(m, n)):
51	  match m:
52	    case 0n:
53	      b
54	    case 1n+p:
55	      match a:
56	        case WCon{h, t}:
57	          WCon{h, W64.bits.cat(p, n, t, b)}
58	
59	# the low 32 bits
60	def W64.lo(a: W64) -> U32:
61	  match a:
62	    case W64{h, l}:
63	      l
64	
65	# the high 32 bits
66	def W64.hi(a: W64) -> U32:
67	  match a:
68	    case W64{h, l}:
69	      h
70	
71	# the word whose high and low 32 bits are hi and lo
72	def W64.from_parts(hi: U32, lo: U32) -> W64:
73	  W64{hi, lo}
74	
75	# 2^32, built from literals Bend reads (a literal is at most 2^32 - 1)
76	def W64.two32() -> Nat:
77	  Nat.add(4294967295n, 1n)
78	
79	def W64.to_nat(a: W64) -> Nat:
80	  match a:
81	    case W64{h, l}:
82	      Nat.add(Nat.mul(U32.to_nat(h), W64.two32()), U32.to_nat(l))
83	
84	def W64.from_nat.pair(qr: Nat & Nat) -> W64:
85	  (q, r) = qr
86	  W64{U32.from_nat(q), U32.from_nat(r)}
87	
88	# k mod 2^64
89	def W64.from_nat(k: Nat) -> W64:
90	  W64.from_nat.pair(Nat.divmod(k, W64.two32()))
91	
92	# Selecting without branching on a computed value in a recursive def
93	
94	def W64.bit(b: Bool) -> U32:
95	  match b:
96	    case True{}:
97	      1
98	    case False{}:
99	      0
100	
101	def W64.sel(b: Bool, x: W64, y: W64) -> W64:
102	  match b:
103	    case True{}:
104	      x
105	    case False{}:
106	      y
107	
108	# Arithmetic, modulo 2^64
109	
110	def W64.add.go(+al: U32, ah: U32, bh: U32, +l: U32) -> W64:
111	  W64{U32.add(U32.add(ah, bh), W64.bit(U32.is_lt(l, al))), l}
112	
113	def W64.add(a: W64, b: W64) -> W64:
114	  match a b:
115	    case W64{ah, +al} W64{bh, bl}:
116	      W64.add.go(al, ah, bh, U32.add(al, bl))
117	
118	def W64.sub(a: W64, b: W64) -> W64:
119	  match a b:
120	    case W64{ah, +al} W64{bh, +bl}:
121	      W64{U32.sub(U32.sub(ah, bh), W64.bit(U32.is_lt(al, bl))), U32.sub(al, bl)}
122	
123	# the high 32 bits of the 64-bit product of two 32-bit words, from their
124	# 16-bit halves (every partial product fits in 32 bits)
125	def W64.mulhi.go(+p00: U32, +p01: U32, +p10: U32, p11: U32) -> U32:
126	  +mid = U32.add(U32.add(U32.shrn(p00, 16n), U32.and(p01, 65535)), U32.and(p10, 65535))
127	  U32.add(U32.add(U32.add(p11, U32.shrn(p01, 16n)), U32.shrn(p10, 16n)), U32.shrn(mid, 16n))
128	
129	def W64.mulhi(+a: U32, +b: U32) -> U32:
130	  +a0 = U32.and(a, 65535)
131	  +a1 = U32.shrn(a, 16n)
132	  +b0 = U32.and(b, 65535)
133	  +b1 = U32.shrn(b, 16n)
134	  W64.mulhi.go(U32.mul(a0, b0), U32.mul(a0, b1), U32.mul(a1, b0), U32.mul(a1, b1))
135	
136	def W64.mul(a: W64, b: W64) -> W64:
137	  match a b:
138	    case W64{ah, +al} W64{bh, +bl}:
139	      W64{U32.add(U32.add(W64.mulhi(al, bl), U32.mul(al, bh)), U32.mul(ah, bl)), U32.mul(al, bl)}
140	
141	# Bits
142	
143	def W64.and(a: W64, b: W64) -> W64:
144	  match a b:
145	    case W64{ah, al} W64{bh, bl}:
146	      W64{U32.and(ah, bh), U32.and(al, bl)}
147	
148	def W64.or(a: W64, b: W64) -> W64:
149	  match a b:
150	    case W64{ah, al} W64{bh, bl}:
151	      W64{U32.or(ah, bh), U32.or(al, bl)}
152	
153	def W64.xor(a: W64, b: W64) -> W64:
154	  match a b:
155	    case W64{ah, al} W64{bh, bl}:
156	      W64{U32.xor(ah, bh), U32.xor(al, bl)}
157	
158	def W64.not(a: W64) -> W64:
159	  match a:
160	    case W64{h, l}:
161	      W64{U32.not(h), U32.not(l)}
162	
163	# shifts by k bits: 0 leaves the word, 64 or more gives 0
164	def W64.shl.pick(z: Bool, lt32: Bool, lt64: Bool, +k: Nat, a: W64) -> W64:
165	  match z lt32 lt64:
166	    case True{} _ _:
167	      a
168	    case False{} True{} _:
169	      match a:
170	        case W64{h, +l}:
171	          W64{U32.or(U32.shln(h, k), U32.shrn(l, Nat.sub(32n, k))), U32.shln(l, k)}
172	    case False{} False{} True{}:
173	      match a:
174	        case W64{h, l}:
175	          W64{U32.shln(l, Nat.sub(k, 32n)), 0}
176	    case False{} False{} False{}:
177	      W64.zero()
178	
179	def W64.shl(a: W64, +k: Nat) -> W64:
180	  W64.shl.pick(Nat.is_eq(k, 0n), Nat.is_lt(k, 32n), Nat.is_lt(k, 64n), k, a)
181	
182	def W64.shr.pick(z: Bool, lt32: Bool, lt64: Bool, +k: Nat, a: W64) -> W64:
183	  match z lt32 lt64:
184	    case True{} _ _:
185	      a
186	    case False{} True{} _:
187	      match a:
188	        case W64{+h, l}:
189	          W64{U32.shrn(h, k), U32.or(U32.shrn(l, k), U32.shln(h, Nat.sub(32n, k)))}
190	    case False{} False{} True{}:
191	      match a:
192	        case W64{h, l}:
193	          W64{0, U32.shrn(h, Nat.sub(k, 32n))}
194	    case False{} False{} False{}:
195	      W64.zero()
196	
197	def W64.shr(a: W64, +k: Nat) -> W64:
198	  W64.shr.pick(Nat.is_eq(k, 0n), Nat.is_lt(k, 32n), Nat.is_lt(k, 64n), k, a)
199	
200	# Comparisons
201	
202	def W64.cmp.pick(c: Cmp, al: U32, bl: U32) -> Cmp:
203	  match c:
204	    case EQ{}:
205	      U32.cmp(al, bl)
206	    case LT{}:
207	      LT{}
208	    case GT{}:
209	      GT{}
210	
211	def W64.cmp(a: W64, b: W64) -> Cmp:
212	  match a b:
213	    case W64{ah, al} W64{bh, bl}:
214	      W64.cmp.pick(U32.cmp(ah, bh), al, bl)
215	
216	def W64.is_eq(a: W64, b: W64) -> Bool:
217	  Cmp.is_eq(W64.cmp(a, b))
218	
219	def W64.is_lt(a: W64, b: W64) -> Bool:
220	  Cmp.is_lt(W64.cmp(a, b))
221	
222	def W64.is_le(a: W64, b: W64) -> Bool:
223	  Cmp.is_le(W64.cmp(a, b))
224	
225	def W64.is_gt(a: W64, b: W64) -> Bool:
226	  Cmp.is_gt(W64.cmp(a, b))
227	
228	def W64.is_ge(a: W64, b: W64) -> Bool:
229	  Cmp.is_ge(W64.cmp(a, b))
230	
231	def W64.is_zero(a: W64) -> Bool:
232	  W64.is_eq(a, W64.zero())
233	
234	# Division: shift-and-subtract over the 64 bits of a, most significant first.
235	# r stays below b; when doubling r overflows 64 bits (its top bit was set),
236	# the true value is past b, and the wrapping subtraction is still exact.
237	
238	def W64.div.go(n: Nat, +a: W64, +b: W64, +q: W64, +r: W64) -> W64 & W64:
239	  match n:
240	    case 0n:
241	      (q, r)
242	    case 1n+p:
243	      +r2 = W64.or(W64.shl(r, 1n), W64.from_u32(U32.shrn(W64.hi(a), 31n)))
244	      +ge = Bool.or(U32.is_eq(U32.shrn(W64.hi(r), 31n), 1), W64.is_ge(r2, b))
245	      W64.div.go(p, W64.shl(a, 1n), b, W64.or(W64.shl(q, 1n), W64.from_u32(W64.bit(ge))), W64.sel(ge, W64.sub(r2, b), r2))
246	
247	def W64.divmod.pick(z: Bool, +a: W64, +b: W64) -> W64 & W64:
248	  match z:
249	    case True{}:
250	      (W64.zero(), a)
251	    case False{}:
252	      W64.div.go(64n, a, b, W64.zero(), W64.zero())
253	
254	# the quotient and the remainder; by zero, the quotient is 0 and the
255	# remainder is a (as bend-kit-int's U64, used before, answered)
256	def W64.divmod(+a: W64, +b: W64) -> W64 & W64:
257	  W64.divmod.pick(W64.is_zero(b), a, b)
258	
259	def W64.fst(p: W64 & W64) -> W64:
260	  (x, y) = p
261	  x
262	
263	def W64.snd(p: W64 & W64) -> W64:
264	  (x, y) = p
265	  y
266	
267	def W64.div(+a: W64, +b: W64) -> W64:
268	  W64.fst(W64.divmod(a, b))
269	
270	def W64.mod(+a: W64, +b: W64) -> W64:
271	  W64.snd(W64.divmod(a, b))
272	
273	# Text
274	
275	# a divided by a small d (1 to 65536) and the remainder, through the four
276	# 16-bit pieces of a, most significant first: every step fits in 32 bits
277	def W64.small.step(+d: U32, qr: U32 & U32, +c: U32) -> U32 & U32:
278	  (q, r) = qr
279	  +v = U32.add(U32.mul(r, 65536), c)
280	  (U32.or(U32.shln(q, 16n), U32.div(v, d)), U32.mod(v, d))
281	
282	# a quotient and a small remainder
283	type W64Small is Data:
284	  W64Small{q: W64, r: U32}
285	
286	def W64.small.join(qhi: U32, ql: U32 & U32) -> W64Small:
287	  (qlo, r) = ql
288	  W64Small{W64{qhi, qlo}, r}
289	
290	def W64.small.fin(qh: U32 & U32, +d: U32, +l: U32) -> W64Small:
291	  (qhi, r) = qh
292	  W64.small.join(qhi, W64.small.step(d, W64.small.step(d, (0, r), U32.shrn(l, 16n)), U32.and(l, 65535)))
293	
294	def W64.small.divmod(a: W64, +d: U32) -> W64Small:
295	  match a:
296	    case W64{+h, l}:
297	      W64.small.fin(W64.small.step(d, W64.small.step(d, (0, 0), U32.shrn(h, 16n)), U32.and(h, 65535)), d, l)
298	
299	def W64.digit(+d: U32) -> Char:
300	  Chr{U32.add(48, d)}
301	
302	def W64.show.push(z: Bool, acc: String, +d: U32) -> String:
303	  match z:
304	    case True{}:
305	      acc
306	    case False{}:
307	      SCon{W64.digit(d), acc}
308	
309	def W64.small.q(p: W64Small) -> W64:
310	  match p:
311	    case W64Small{q, r}:
312	      q
313	
314	def W64.small.r(p: W64Small) -> U32:
315	  match p:
316	    case W64Small{q, r}:
317	      r
318	
319	# the decimal digits of a, consuming one of 20 steps per digit (after a
320	# reaches 0 the steps add nothing)
321	def W64.show.go(n: Nat, +a: W64, acc: String) -> String:
322	  match n:
323	    case 0n:
324	      acc
325	    case 1n+p:
326	      +dm = W64.small.divmod(a, 10)
327	      W64.show.go(p, W64.small.q(dm), W64.show.push(W64.is_zero(a), acc, W64.small.r(dm)))
328	
329	def W64.show.pick(z: Bool, +a: W64) -> String:
330	  match z:
331	    case True{}:
332	      "0"
333	    case False{}:
334	      W64.show.go(20n, a, "")
335	
336	def W64.show(+a: W64) -> String:
337	  W64.show.pick(W64.is_zero(a), a)
338	
339	# the 16 hex digits, lower case, most significant first
340	def W64.hex.pick(lt: Bool, d: U32) -> Char:
341	  match lt:
342	    case True{}:
343	      Chr{U32.add(48, d)}
344	    case False{}:
345	      Chr{U32.add(87, d)}
346	
347	def W64.hex.digit(+d: U32) -> Char:
348	  W64.hex.pick(U32.is_lt(d, 10), d)
349	
350	def W64.hex.go(n: Nat, +a: W64, acc: String) -> String:
351	  match n:
352	    case 0n:
353	      acc
354	    case 1n+p:
355	      W64.hex.go(p, W64.shr(a, 4n), SCon{W64.hex.digit(U32.and(W64.lo(a), 15)), acc})
356	
357	def W64.show_hex(a: W64) -> String:
358	  W64.hex.go(16n, a, "")