module Rmbt
  use int.Int
  use ref.Ref
  use bv.BV64

  let ghost rightmost_position_set (a : t) : t
    requires { a <> zeros }
    ensures  { ult result (64:t) }
    ensures  { eq_sub_bv a zeros zeros result }
    ensures  { nth_bv a result }
  =
    let i = ref zeros in
    while ult !i (64:t) && not (nth_bv a !i) do
      variant {64 - t'int !i}
      invariant {eq_sub_bv a zeros zeros !i}
      i := add !i BV64.one
    done;
    !i

  let rightmost_bit_trick (x: t) (ghost p : ref int) : t
    requires { x <> zeros }
    writes   { p }
    ensures  { 0 <= !p < 64 }
    ensures  { eq_sub x zeros 0 !p }
    ensures  { nth x !p }
    ensures  { eq_sub result zeros 0 !p }
    ensures  { eq_sub result zeros (!p+1) (63 - !p) }
    ensures  { nth result !p }
  =
    let ghost p_bv = rightmost_position_set x in
    ghost p := t'int p_bv;
    assert { nth_bv (neg x) p_bv };
    let r = bw_and x (neg x) in
    assert  { eq_sub_bv r zeros (add p_bv (1:t)) (sub (63:t) p_bv) };
    r

end