1	# bend-osdev-word64's laws of multiplication, for every input: the high
2	# half of a 32-bit product (W64.mulhi), and W64.mul as the low 64 bits of the
3	# product of the values. Proved in PROOF_mul.bend.
4	import Base
5	import bend-osdev-u32@0.1.0.0/u32.bend as U
6	import ./word64.bend as W
7	
8	# Multiplication. W64.mulhi(a, b) is the high 32 bits of the product of two
9	# 32-bit words: with the low 32 bits (U32.mul), the whole product. W64.mul
10	# is the product modulo 2^64: its value is the low 64 bits of the product of
11	# the values (U32Nat.low, from bend-osdev-u32), what wraps is 2^64 times the
12	# rest, and with the product no more than a word's value nothing wraps.
13	law mulhi_value:
14	  for +a: U32
15	  for +b: U32
16	  {Nat.add(U32.to_nat(U32.mul(a, b)), U.U32Nat.dbl(32n, U32.to_nat(W.W64.mulhi(a, b)))) == Nat.mul(U32.to_nat(a), U32.to_nat(b)) : Nat}
17	
18	law mul_wrap:
19	  for +a: W.W64
20	  for +b: W.W64
21	  {Nat.add(W.W64.to_nat(W.W64.mul(a, b)), U.U32Nat.dbl(64n, U.U32Nat.high(64n, Nat.mul(W.W64.to_nat(a), W.W64.to_nat(b))))) == Nat.mul(W.W64.to_nat(a), W.W64.to_nat(b)) : Nat}
22	
23	law mul_low:
24	  for +a: W.W64
25	  for +b: W.W64
26	  {W.W64.to_nat(W.W64.mul(a, b)) == U.U32Nat.low(64n, Nat.mul(W.W64.to_nat(a), W.W64.to_nat(b))) : Nat}
27	
28	law mul_value:
29	  for +a: W.W64
30	  for +b: W.W64
31	  for +c: W.W64
32	  for h: {Nat.is_le(Nat.mul(W.W64.to_nat(a), W.W64.to_nat(b)), W.W64.to_nat(c)) == True{} : Bool}
33	  {W.W64.to_nat(W.W64.mul(a, b)) == Nat.mul(W.W64.to_nat(a), W.W64.to_nat(b)) : Nat}