src/math/u64.bend

bend-collections-laws-math@1.0.0.0 · 100 lines · 18 definitions

1import Base
2
3# 64-bit integers as two native U32 limbs (Bend 2 has no native 64-bit word).
4# The same bits read as unsigned or as two's-complement signed, as in C.
5#
6#   zero(), of_u32(x)          construction
7#   is_zero(a)                 a == 0
8#   add(a, b), neg(a)          wrapping addition and negation
9#   le_signed(a, b)            a <= b as signed 64-bit integers
10#   div_small(a, d)            unsigned a / d, for 0 < d <= 2^20
11#   div_small_signed(a, d)     signed a / d truncated toward zero, 0 < d <= 2^20
12
13type U64 is Data:
14  U64{lo: U32, hi: U32}
15
16def zero() -> U64:
17  U64{0, 0}
18
19def of_u32(+x: U32) -> U64:
20  U64{x, 0}
21
22def is_zero(a: U64) -> Bool:
23  U64{lo, hi} = a
24  Bool.and(U32.is_zero(lo), U32.is_zero(hi))
25
26def carry(b: Bool) -> U32:
27  match b:
28    case True{}:
29      1
30    case False{}:
31      0
32
33def add_fin(+lo: U32, +alo: U32, +ahi: U32, +bhi: U32) -> U64:
34  U64{lo, U32.add(U32.add(ahi, bhi), carry(U32.is_lt(lo, alo)))}
35
36# Wrapping 64-bit addition.
37def add(a: U64, b: U64) -> U64:
38  U64{+alo, +ahi} = a
39  U64{+blo, +bhi} = b
40  add_fin(U32.add(alo, blo), alo, ahi, bhi)
41
42def neg_fin(+lo2: U32, +hi: U32) -> U64:
43  U64{lo2, U32.add(U32.not(hi), carry(U32.is_zero(lo2)))}
44
45# Two's-complement negation.
46def neg(a: U64) -> U64:
47  U64{+lo, +hi} = a
48  neg_fin(U32.inc(U32.not(lo)), hi)
49
50def order(high: Cmp, low: Cmp) -> Cmp:
51  match high:
52    case EQ{}:
53      low
54    case LT{}:
55      LT{}
56    case GT{}:
57      GT{}
58
59def le_sign(+alo: U32, +ahi: U32, +blo: U32, +bhi: U32, negative_a: Bool, negative_b: Bool) -> Bool:
60  match negative_a negative_b:
61    case True{} False{}:
62      True{}
63    case False{} True{}:
64      False{}
65    case _ _:
66      Cmp.is_le(order(U32.cmp(ahi, bhi), U32.cmp(alo, blo)))
67
68# a <= b as signed 64-bit integers.
69def le_signed(a: U64, b: U64) -> Bool:
70  U64{alo, +ahi} = a
71  U64{blo, +bhi} = b
72  le_sign(alo, ahi, blo, bhi, U32.is_ge(ahi, 2147483648), U32.is_ge(bhi, 2147483648))
73
74# Long division in 32/12/12/8-bit digits: every partial remainder is below
75# d <= 2^20, so each candidate r * 2^12 + digit stays below 2^32.
76def div_fin(+lo: U32, +hi: U32, +d: U32, +t1: U32, +t2: U32, +t3: U32) -> U64:
77  U64{U32.add(U32.add(U32.mul(U32.div(t1, d), 1048576), U32.mul(U32.div(t2, d), 256)), U32.div(t3, d)), U32.div(hi, d)}
78
79def div_t3(+lo: U32, +hi: U32, +d: U32, +t1: U32, +t2: U32) -> U64:
80  div_fin(lo, hi, d, t1, t2, U32.add(U32.mul(U32.mod(t2, d), 256), U32.and(lo, 255)))
81
82def div_t2(+lo: U32, +hi: U32, +d: U32, +t1: U32) -> U64:
83  div_t3(lo, hi, d, t1, U32.add(U32.mul(U32.mod(t1, d), 4096), U32.and(U32.div(lo, 256), 4095)))
84
85# Unsigned a / d, for 0 < d <= 2^20.
86def div_small(a: U64, +d: U32) -> U64:
87  U64{+lo, +hi} = a
88  div_t2(lo, hi, d, U32.add(U32.mul(U32.mod(hi, d), 4096), U32.div(lo, 1048576)))
89
90def div_sign(a: U64, +d: U32, negative: Bool) -> U64:
91  match negative:
92    case False{}:
93      div_small(a, d)
94    case True{}:
95      neg(div_small(neg(a), d))
96
97# Signed a / d truncated toward zero (C semantics), for 0 < d <= 2^20.
98def div_small_signed(a: U64, +d: U32) -> U64:
99  U64{lo, +hi} = a
100  div_sign(U64{lo, hi}, d, U32.is_ge(hi, 2147483648))