def pow2_value

bend-collections-laws-crypto@1.0.0.0 · proofs/math/random/uint64n.bend:101

import Base
import bend-collections-laws-crypto@1.0.0.0/spec/math/w64.bend as SW
import bend-collections-laws-crypto@1.0.0.0/spec/math/random/rand.bend as SR
import bend-collections-laws-crypto@1.0.0.0/src/math/u64.bend as WU
import bend-collections-laws-crypto@1.0.0.0/src/math/w64.bend as X
import bend-collections-laws-crypto@1.0.0.0/src/math/random/rand.bend as R
import bend-collections-laws-crypto@1.0.0.0/proofs/math/typed/w64add.bend as WA
import bend-collections-laws-crypto@1.0.0.0/proofs/math/random/bits.bend as BI

101# the power-of-two test is n & (n - 1) == 0
102def pow2_value(+n: WU.U64, +m: Nat, +hv: {SW.value(n) == 1n+m : Nat}) -> {R.is_pow2(n) == Nat.is_eq(SR.and_bits(64n, 1n+m, m), 0n) : Bool}:
103  Equal.trans(Bool, R.is_pow2(n), Nat.is_eq(SW.value(R.and64(n, X.sub(n, one64()))), 0n), Nat.is_eq(SR.and_bits(64n, 1n+m, m), 0n),
104    WA.is_zero_value(R.and64(n, X.sub(n, one64()))),
105    %Equal.sym(Nat, SW.value(R.and64(n, X.sub(n, one64()))), SR.and_bits(64n, SW.value(n), SW.value(X.sub(n, one64()))), BI.and64_value(n, X.sub(n, one64()))) : {Nat.is_eq(_, 0n) == Nat.is_eq(SR.and_bits(64n, 1n+m, m), 0n) : Bool}
106    %Equal.sym(Nat, SW.value(n), 1n+m, hv) : {Nat.is_eq(SR.and_bits(64n, _, SW.value(X.sub(n, one64()))), 0n) == Nat.is_eq(SR.and_bits(64n, 1n+m, m), 0n) : Bool}
107    %Equal.sym(Nat, SW.value(X.sub(n, one64())), m, pred_value(n, m, hv)) : {Nat.is_eq(SR.and_bits(64n, 1n+m, _), 0n) == Nat.is_eq(SR.and_bits(64n, 1n+m, m), 0n) : Bool}
108    {==})