def un.carry

bend-osdev-u32@0.1.0.0 · PROOF.bend:611

import Base
import bend-osdev-u32@0.1.0.0/u32.bend as U
import bend-osdev-u32@0.1.0.0/LAWS.bend as Laws

611# s + 2^n * C = A + B with B < 2^n: C is whether s < A
612def un.carry(c: Bool, +n: Nat, +s: Nat, +a: Nat, +b: Nat, e: {Nat.add(s, U.U32Nat.dbl(n, U.U32Nat.bit(c))) == Nat.add(a, b) : Nat}, hb: {Nat.is_lt(b, U.U32Nat.dbl(n, 1n)) == True{} : Bool}) -> {Nat.is_lt(s, a) == c : Bool}:
613  match c:
614    case True{}:
615      +k = U.U32Nat.dbl(n, 1n)
616      +h1 = Equal.trans(Bool, Nat.is_lt(Nat.add(a, b), Nat.add(a, k)), Nat.is_lt(b, k), True{}, un.lt_add_l(a, b, k), hb)
617      +h2 = un.lt_rw(Nat.add(a, b), Nat.add(s, k), Nat.add(a, k), Equal.sym(Nat, Nat.add(s, k), Nat.add(a, b), e), h1)
618      Equal.trans(Bool, Nat.is_lt(s, a), Nat.is_lt(Nat.add(s, k), Nat.add(a, k)), True{}, Equal.sym(Bool, Nat.is_lt(Nat.add(s, k), Nat.add(a, k)), Nat.is_lt(s, a), un.lt_add_r(s, a, k)), h2)
619    case False{}:
620      +es = Equal.trans(Nat, s, Nat.add(s, 0n), Nat.add(a, b), Equal.sym(Nat, Nat.add(s, 0n), s, un.add_zero(s)), Equal.trans(Nat, Nat.add(s, 0n), Nat.add(s, U.U32Nat.dbl(n, 0n)), Nat.add(a, b), Equal.cong(Nat, Nat, v => Nat.add(s, v), 0n, U.U32Nat.dbl(n, 0n), Equal.sym(Nat, U.U32Nat.dbl(n, 0n), 0n, Laws.dbl_zero(n))), e))
621      %Equal.sym(Nat, s, Nat.add(a, b), es) : {Nat.is_lt(_, a) == False{} : Bool}
622      un.not_lt_add(a, b)