def ws.g1w

bend-osdev-word64@0.1.1.0 · proof_shift.bend:369

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 UL

369# The bits a shift left by k carries out are the shift right by n - k:
370# 2^k * w = shl(w, k) + 2^n * shr(w, n - k), and shl(w, k) is 2^k times
371# the remainder of w by 2^(n - k)
372def ws.g1w(+n: Nat, +k: Nat, +w: Word(n), hk: {Nat.is_le(k, n) == True{} : Bool}) -> {U.U32Nat.dbl(k, Word.to_nat(n, w)) == Nat.add(U.U32Nat.dbl(k, Nat.sub(Word.to_nat(n, w), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w))))), U.U32Nat.dbl(n, Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))) : Nat}:
373  +er = UL.nat_le_witness(U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w))), Word.to_nat(n, w), ws.shr_le(n, Nat.sub(n, k), w))
374  Equal.trans(Nat, U.U32Nat.dbl(k, Word.to_nat(n, w)), U.U32Nat.dbl(k, Nat.add(Nat.sub(Word.to_nat(n, w), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w))))), Nat.add(U.U32Nat.dbl(k, Nat.sub(Word.to_nat(n, w), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w))))), U.U32Nat.dbl(n, Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))), Equal.cong(Nat, Nat, v => U.U32Nat.dbl(k, v), Word.to_nat(n, w), Nat.add(Nat.sub(Word.to_nat(n, w), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))), Equal.sym(Nat, Nat.add(Nat.sub(Word.to_nat(n, w), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))), Word.to_nat(n, w), er)), Equal.trans(Nat, U.U32Nat.dbl(k, Nat.add(Nat.sub(Word.to_nat(n, w), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w))))), Nat.add(U.U32Nat.dbl(k, Nat.sub(Word.to_nat(n, w), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w))))), U.U32Nat.dbl(k, U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w))))), Nat.add(U.U32Nat.dbl(k, Nat.sub(Word.to_nat(n, w), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w))))), U.U32Nat.dbl(n, Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))), UL.dbl_add(k, Nat.sub(Word.to_nat(n, w), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))), Equal.cong(Nat, Nat, v => Nat.add(U.U32Nat.dbl(k, Nat.sub(Word.to_nat(n, w), U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w))))), v), U.U32Nat.dbl(k, U.U32Nat.dbl(Nat.sub(n, k), Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)))), U.U32Nat.dbl(n, Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w))), ns.dkm(n, k, Word.to_nat(n, ws.shr(n, Nat.sub(n, k), w)), hk))))