def first_false

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

import Base
import bend-collections-laws-crypto@1.0.0.0/spec/lib/common.bend as C
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/lib/nat.bend as N
import bend-collections-laws-crypto@1.0.0.0/spec/math/random.bend as SRM

227# lo >= n: the first draw is accepted by the specification too
228def first_false(~S: Data, ~next: S -> WU.U64 & S, +n: WU.U64, +m: Nat, +x: WU.U64, +s1: S, +hv: {SW.value(n) == 1n+m : Nat}, +hp: {Nat.is_eq(SR.and_bits(64n, 1n+m, m), 0n) == False{} : Bool}, +htn: {Nat.is_lt(SR.pow2mod(64n, 1n+m), 1n+m) == True{} : Bool}, +hc: {X.lt(X.pfst(X.mul128(x, n)), n) == False{} : Bool}) -> {SRM.val_pair(S, R.lemire_small(~S, ~next, n, X.psnd(X.mul128(x, n)), X.pfst(X.mul128(x, n)), s1, False{})) == cont(~S, ~next, 127n, 1n+m, SW.value(x), s1) : Nat & S}:
229  +L = C.low(64n, Nat.mul(SW.value(x), 1n+m))
230  +H = C.high(64n, Nat.mul(SW.value(x), 1n+m))
231  +pm = SR.pow2mod(64n, 1n+m)
232  +hn = Equal.trans(Bool, Nat.is_lt(L, 1n+m), X.lt(X.pfst(X.mul128(x, n)), n), False{},
233    Equal.sym(Bool, X.lt(X.pfst(X.mul128(x, n)), n), Nat.is_lt(L, 1n+m), lt_low_n(x, n, m, hv)),
234    hc)
235  +hl = N.le_not_lt(L, pm, N.le_trans(pm, 1n+m, L, N.lt_le(pm, 1n+m, htn), N.not_lt_le(L, 1n+m, hn)))
236  %Equal.sym(Maybe<&2, Nat>, SR.draw(64n, SW.value(x), 1n+m), SR.accept(H, True{}), dec(SW.value(x), m, hp, htn, False{}, hl)) : {(SW.value(X.psnd(X.mul128(x, n))), s1) == SR.below_go(~S, ~next, 127n, 1n+m, _, SW.value(x), s1) : Nat & S}
237  Equal.cong(Nat, Nat & S, z => (z, s1), SW.value(X.psnd(X.mul128(x, n))), H, hi_value(x, n, m, hv))