def mask_lt

bend-collections-laws-math@1.0.0.0 · proofs/lib/word.bend:310

import Base
import bend-collections-laws-math@1.0.0.0/proofs/lib/nat.bend as N
import bend-collections-laws-math@1.0.0.0/proofs/lib/logic.bend as L

310# x & mask k is below 2^k
311def mask_lt(+n: Nat, +k: Nat, +one: Nat, +h1: {one == 1n : Nat}, +x: Word(n)) -> {Nat.is_lt(uw(n, Word.and(n, x, mask(n, k))), sc(k, one)) == True{} : Bool}:
312  match n k x:
313    case 0n _ WNil{}:
314      lt1r(k, one, h1, 0n, sc_pos(k))
315    case 1n+p 0n WCon{b, t}:
316      +z = uw(1n+p, Word.and(1n+p, WCon{b, t}, mask(1n+p, 0n)))
317      L.subst(Nat, o => {Nat.is_lt(z, o) == True{} : Bool}, 1n, one, Equal.sym(Nat, one, 1n, h1), L.subst(Nat, w => {Nat.is_lt(w, 1n) == True{} : Bool}, 0n, z, Equal.sym(Nat, z, 0n, low0(p, b, t)), {==}))
318    case 1n+p 1n+j WCon{b, t}:
319      N.double_lt_bit(Bool.and(b, True{}), uw(p, Word.and(p, t, mask(p, j))), sc(j, one), mask_lt(p, j, one, h1, t))