word64.bend
bend-osdev-word64@0.1.0.0 · 358 lines · 0 definitions
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.
10import Base
11
12type W64 is Data:
13 W64{hi: U32, lo: U32}
14
15def W64.zero() -> W64:
16 W64{0, 0}
17
18def W64.one() -> W64:
19 W64{0, 1}
20
21def W64.max() -> W64:
22 W64{4294967295, 4294967295}
23
24# Conversions
25
26def 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.
32def 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
41def 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
50def 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
60def W64.lo(a: W64) -> U32:
61 match a:
62 case W64{h, l}:
63 l
64
65# the high 32 bits
66def 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
72def 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)
76def W64.two32() -> Nat:
77 Nat.add(4294967295n, 1n)
78
79def 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
84def 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
89def 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
94def W64.bit(b: Bool) -> U32:
95 match b:
96 case True{}:
97 1
98 case False{}:
99 0
100
101def 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
110def 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
113def 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
118def 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)
125def 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
129def 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
136def 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
143def 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
148def 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
153def 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
158def 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
164def 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
179def 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
182def 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
197def 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
202def 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
211def 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
216def W64.is_eq(a: W64, b: W64) -> Bool:
217 Cmp.is_eq(W64.cmp(a, b))
218
219def W64.is_lt(a: W64, b: W64) -> Bool:
220 Cmp.is_lt(W64.cmp(a, b))
221
222def W64.is_le(a: W64, b: W64) -> Bool:
223 Cmp.is_le(W64.cmp(a, b))
224
225def W64.is_gt(a: W64, b: W64) -> Bool:
226 Cmp.is_gt(W64.cmp(a, b))
227
228def W64.is_ge(a: W64, b: W64) -> Bool:
229 Cmp.is_ge(W64.cmp(a, b))
230
231def 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
238def 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
247def 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)
256def W64.divmod(+a: W64, +b: W64) -> W64 & W64:
257 W64.divmod.pick(W64.is_zero(b), a, b)
258
259def W64.fst(p: W64 & W64) -> W64:
260 (x, y) = p
261 x
262
263def W64.snd(p: W64 & W64) -> W64:
264 (x, y) = p
265 y
266
267def W64.div(+a: W64, +b: W64) -> W64:
268 W64.fst(W64.divmod(a, b))
269
270def 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
277def 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
283type W64Small is Data:
284 W64Small{q: W64, r: U32}
285
286def W64.small.join(qhi: U32, ql: U32 & U32) -> W64Small:
287 (qlo, r) = ql
288 W64Small{W64{qhi, qlo}, r}
289
290def 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
294def 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
299def W64.digit(+d: U32) -> Char:
300 Chr{U32.add(48, d)}
301
302def 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
309def W64.small.q(p: W64Small) -> W64:
310 match p:
311 case W64Small{q, r}:
312 q
313
314def 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)
321def 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
329def 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
336def 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
340def 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
347def W64.hex.digit(+d: U32) -> Char:
348 W64.hex.pick(U32.is_lt(d, 10), d)
349
350def 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
357def W64.show_hex(a: W64) -> String:
358 W64.hex.go(16n, a, "")