proofs/lib/lemmas/proofs/division_remainder.bend

bend-collections-laws-crypto@1.0.0.0 · 26 lines · 4 definitions

1import Base
2import bend-collections-laws-crypto@1.0.0.0/proofs/lib/lemmas/proofs/map_difference_order.bend as Order
3import bend-collections-laws-crypto@1.0.0.0/proofs/lib/lemmas/src/wide.bend as W
4import bend-collections-laws-crypto@1.0.0.0/proofs/lib/lemmas/proofs/division_no_overflow.bend as Overflow
5import bend-collections-laws-crypto@1.0.0.0/proofs/lib/lemmas/proofs/word_comparison.bend as Compare
6import bend-collections-laws-crypto@1.0.0.0/proofs/lib/lemmas/proofs/subtraction_bounds.bend as Sub
7import bend-collections-laws-crypto@1.0.0.0/proofs/lib/lemmas/proofs/division_bounds.bend as Bounds
8import bend-collections-laws-crypto@1.0.0.0/proofs/lib/lemmas/proofs/natural_products.bend as Product
9
10# General U32 subtraction branch; comparison and decoded subtraction are both
11# justified by the actual Base definitions, and the input range is explicit.
12def subtract(+r: U32, +d: U32, above: {U32.is_ge(r, d) == True{} : Bool}, below: {Nat.is_lt(U32.to_nat(r), Nat.double(U32.to_nat(d))) == True{} : Bool}) -> {U32.is_lt(U32.sub(r, d), d) == True{} : Bool}:
13  +enough = Equal.trans(Bool, Nat.is_le(U32.to_nat(d), U32.to_nat(r)), Nat.is_ge(U32.to_nat(r), U32.to_nat(d)), True{}, Equal.sym(Bool, Nat.is_ge(U32.to_nat(r), U32.to_nat(d)), Nat.is_le(U32.to_nat(d), U32.to_nat(r)), Bounds.ge_reverse(U32.to_nat(r), U32.to_nat(d))), Equal.trans(Bool, Nat.is_ge(U32.to_nat(r), U32.to_nat(d)), U32.is_ge(r, d), True{}, Equal.sym(Bool, U32.is_ge(r, d), Nat.is_ge(U32.to_nat(r), U32.to_nat(d)), Compare.u32_ge(r, d)), above))
14  inside = Equal.trans(Bool, Nat.is_lt(U32.to_nat(r), Nat.add(U32.to_nat(d), U32.to_nat(d))), Nat.is_lt(U32.to_nat(r), Nat.double(U32.to_nat(d))), True{}, Equal.cong(Nat, Bool, x => Nat.is_lt(U32.to_nat(r), x), Nat.add(U32.to_nat(d), U32.to_nat(d)), Nat.double(U32.to_nat(d)), Equal.sym(Nat, Nat.double(U32.to_nat(d)), Nat.add(U32.to_nat(d), U32.to_nat(d)), Product.double_sum(U32.to_nat(d)))), below)
15  Equal.trans(Bool, U32.is_lt(U32.sub(r, d), d), Nat.is_lt(U32.to_nat(U32.sub(r, d)), U32.to_nat(d)), True{}, Compare.u32_lt(U32.sub(r, d), d), Equal.trans(Bool, Nat.is_lt(U32.to_nat(U32.sub(r, d)), U32.to_nat(d)), Nat.is_lt(Nat.sub(U32.to_nat(r), U32.to_nat(d)), U32.to_nat(d)), True{}, Equal.cong(Nat, Bool, x => Nat.is_lt(x, U32.to_nat(d)), U32.to_nat(U32.sub(r, d)), Nat.sub(U32.to_nat(r), U32.to_nat(d)), Sub.u32_exact(r, d, enough)), Bounds.subtract_bound(U32.to_nat(r), U32.to_nat(d), inside, enough)))
16
17def subtract_native(+r: U32, +d: U32, high: {W.last(32n, Overflow.bits(d)) == False{} : Bool}, above: {U32.is_ge(r, d) == True{} : Bool}, below: {U32.is_lt(r, U32.shl(d)) == True{} : Bool}) -> {U32.is_lt(U32.sub(r, d), d) == True{} : Bool}:
18  subtract(r, d, above, Equal.trans(Bool, Nat.is_lt(U32.to_nat(r), Nat.double(U32.to_nat(d))), Nat.is_lt(U32.to_nat(r), U32.to_nat(U32.shl(d))), True{}, Equal.cong(Nat, Bool, x => Nat.is_lt(U32.to_nat(r), x), Nat.double(U32.to_nat(d)), U32.to_nat(U32.shl(d)), Equal.sym(Nat, U32.to_nat(U32.shl(d)), Nat.double(U32.to_nat(d)), Overflow.double_value(d, high))), Equal.trans(Bool, Nat.is_lt(U32.to_nat(r), U32.to_nat(U32.shl(d))), U32.is_lt(r, U32.shl(d)), True{}, Equal.sym(Bool, U32.is_lt(r, U32.shl(d)), Nat.is_lt(U32.to_nat(r), U32.to_nat(U32.shl(d))), Compare.u32_lt(r, U32.shl(d))), below)))
19
20# Concrete executed subtraction restores the native remainder bound.
21def million(+r: U32, above: {U32.is_ge(r, 1000000) == True{} : Bool}, below: {U32.is_lt(r, 2000000) == True{} : Bool}) -> {U32.is_lt(U32.sub(r, 1000000), 1000000) == True{} : Bool}:
22  subtract_native(r, 1000000, {==}, above, below)
23
24def subtraction_conservation(+r: U32, +d: U32, above: {U32.is_ge(r, d) == True{} : Bool}) -> {U32.to_nat(r) == Nat.add(U32.to_nat(d), U32.to_nat(U32.sub(r, d))) : Nat}:
25  +enough = Equal.trans(Bool, Nat.is_le(U32.to_nat(d), U32.to_nat(r)), Nat.is_ge(U32.to_nat(r), U32.to_nat(d)), True{}, Equal.sym(Bool, Nat.is_ge(U32.to_nat(r), U32.to_nat(d)), Nat.is_le(U32.to_nat(d), U32.to_nat(r)), Bounds.ge_reverse(U32.to_nat(r), U32.to_nat(d))), Equal.trans(Bool, Nat.is_ge(U32.to_nat(r), U32.to_nat(d)), U32.is_ge(r, d), True{}, Equal.sym(Bool, U32.is_ge(r, d), Nat.is_ge(U32.to_nat(r), U32.to_nat(d)), Compare.u32_ge(r, d)), above))
26  Equal.trans(Nat, U32.to_nat(r), Nat.add(U32.to_nat(d), Nat.sub(U32.to_nat(r), U32.to_nat(d))), Nat.add(U32.to_nat(d), U32.to_nat(U32.sub(r, d))), Equal.sym(Nat, Nat.add(U32.to_nat(d), Nat.sub(U32.to_nat(r), U32.to_nat(d))), U32.to_nat(r), Order.add_complement(U32.to_nat(r), U32.to_nat(d), enough)), Equal.cong(Nat, Nat, x => Nat.add(U32.to_nat(d), x), Nat.sub(U32.to_nat(r), U32.to_nat(d)), U32.to_nat(U32.sub(r, d)), Equal.sym(Nat, U32.to_nat(U32.sub(r, d)), Nat.sub(U32.to_nat(r), U32.to_nat(d)), Sub.u32_exact(r, d, enough))))