1	import 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	
13	type U64 is Data:
14	  U64{lo: U32, hi: U32}
15	
16	def zero() -> U64:
17	  U64{0, 0}
18	
19	def of_u32(+x: U32) -> U64:
20	  U64{x, 0}
21	
22	def is_zero(a: U64) -> Bool:
23	  U64{lo, hi} = a
24	  Bool.and(U32.is_zero(lo), U32.is_zero(hi))
25	
26	def carry(b: Bool) -> U32:
27	  match b:
28	    case True{}:
29	      1
30	    case False{}:
31	      0
32	
33	def 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.
37	def 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	
42	def 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.
46	def neg(a: U64) -> U64:
47	  U64{+lo, +hi} = a
48	  neg_fin(U32.inc(U32.not(lo)), hi)
49	
50	def 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	
59	def 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.
69	def 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.
76	def 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	
79	def 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	
82	def 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.
86	def 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	
90	def 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.
98	def 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))