library colibrilib.lowbits — module LowBitsLow bits of integers (two's complement): two integers differ by a multiple of 2^i iff they have the same i lowest bits.
The facts are let ghost functions that a proof calls, not let lemma (see colibrilib/dv.mlw).
module LowBits6use int.Int7use colibrilib.zarith.Zbit8
Shifting by one more bit doubles, for every integer
Valid (138ms) (colibri2)let ghost lsl_dbl (k i:int) : unit11requires { 0 <= i }12ensures { Zbit.lsl k (i + 1) = 2 * Zbit.lsl k i }13= {proof…} let lemma bit (j:int) : unit14requires { 0 <= j }15ensures { Zbit.bittest (Zbit.lsl k (i + 1)) j <-> Zbit.bittest (2 * Zbit.lsl k i) j }16= () in17Zbit.ext_bittest (Zbit.lsl k (i + 1)) (2 * Zbit.lsl k i) {qed}18
lsl k i is the product by lsl 1 i = 2^i
Valid (4.5s) (colibri2 6) (split_vc 2) (depth 2)let rec ghost lsl_mul (k i:int) : unit21requires { 0 <= i }22variant { i }23ensures { Zbit.lsl k i = k * Zbit.lsl 1 i }24= {proof…} if i > 0 then begin25lsl_dbl k (i - 1);26lsl_dbl 1 (i - 1);27lsl_mul k (i - 1)28end {qed}29
No carry reaches i when the i low bits of t are zero
Valid (52ms) (colibri2)let rec ghost no_carry (r t i:int) : unit32requires { 0 <= i }33requires { forall j. 0 <= j < i -> not (Zbit.bittest t j) }34variant { i }35ensures { not (Zbit.carry r t i) }36= if i > 0 then no_carry r t (i - 1)37
Adding a number whose i low bits are zero does not change the i low bits
Valid (41ms) (colibri2)let ghost add_low (r t i:int) : unit41requires { 0 <= i }42requires { forall j. 0 <= j < i -> not (Zbit.bittest t j) }43ensures { forall j. 0 <= j < i -> (Zbit.bittest (r + t) j <-> Zbit.bittest r j) }44= {proof…} let lemma bit (j:int) : unit45requires { 0 <= j < i }46ensures { Zbit.bittest (r + t) j <-> Zbit.bittest r j }47= no_carry r t j in () {qed}48
n - r is a multiple of 2^i: n and r have the same i lowest bits
Valid (52ms) (colibri2)let ghost same_low (n r m i:int) : unit52requires { 0 <= i }53requires { n - r = m * Zbit.lsl 1 i }54ensures { forall j. 0 <= j < i -> (Zbit.bittest n j <-> Zbit.bittest r j) }55= {proof…} lsl_mul m i;56assert { n = r + Zbit.lsl m i };57let lemma zero (j:int) : unit58requires { 0 <= j < i }59ensures { not (Zbit.bittest (Zbit.lsl m i) j) }60= () in61add_low r (Zbit.lsl m i) i {qed}62Valid (402ms) (cvc5)63let rec ghost sub_low_aux (n r t i:int) : unit64requires { 0 <= i }65requires { n = r + t }66requires { forall j. 0 <= j < i -> (Zbit.bittest n j <-> Zbit.bittest r j) }67variant { i }68ensures { forall j. 0 <= j < i -> not (Zbit.bittest t j) }69ensures { not (Zbit.carry r t i) }70= {proof…} if i > 0 then begin71sub_low_aux n r t (i - 1);72assert { not (Zbit.bittest t (i - 1)) }73end {qed}74
Conversely, n - r is a multiple of 2^i when the i low bits of n and r agree
Valid (166ms) (colibri2)let ghost sub_low (n r i:int) : unit78requires { 0 <= i }79requires { forall j. 0 <= j < i -> (Zbit.bittest n j <-> Zbit.bittest r j) }80ensures { exists m:int. n - r = m * Zbit.lsl 1 i }81= {proof…} let t = n - r in82sub_low_aux n r t i;83let m = Zbit.asr t i in84let lemma bit (j:int) : unit85requires { 0 <= j }86ensures { Zbit.bittest t j <-> Zbit.bittest (Zbit.lsl m i) j }87= () in88Zbit.ext_bittest t (Zbit.lsl m i);89lsl_mul m i {qed}90end91