library colibrilib.zbit — module ZbitIntTotal versions of the bit operations, for an index or an offset that is not known to fit in an int63 (a number of bits, for example). They never overflow: beyond max_int63, x has become 0 or -1 for asr, and lsl can only run out of memory, as any operation of Zarith.
module ZbitInt6
Implemented
use int.Int7use mach.int.Int638use colibrilib.zarith.Zbit9Valid (29ms) (colibri2)10let ghost asr_asr (x a b:int) : unit11requires { 0 <= a /\ 0 <= b }12ensures { asr (asr x a) b = asr x (a + b) }13= let lemma bit (i:int) : unit14requires { i >= 0 }15ensures { bittest (asr (asr x a) b) i = bittest (asr x (a + b)) i }16= def_asr (asr x a) b i; def_asr x a (i + b); def_asr x (a + b) i in17ext_bittest (asr (asr x a) b) (asr x (a + b))18Valid (27ms) (colibri2)19let rec ghost minus_one_bits (j:int) : unit20requires { 0 <= j }21ensures { bittest (-1) j }22variant { j }23= odd_bittest (-1) j; if j > 0 then minus_one_bits (j - 1)24Valid (40ms) (colibri2)25let ghost asr_fix (x k:int) : unit26requires { x = 0 \/ x = -1 }27requires { 0 <= k }28ensures { asr x k = x }29= let lemma bit (i:int) : unit30requires { 0 <= i }31ensures { bittest (asr x k) i = bittest x i }32= def_asr x k i;33if x = -1 then (minus_one_bits i; minus_one_bits (i + k)) in34ext_bittest (asr x k) x35Valid (40ms) (colibri2)36let rec asr_int (x offset:int) : int37requires { 0 <= offset }38ensures { result = asr x offset }39variant { offset }40= if offset <= max_int63 then asr63 x (of_int offset)41else if x = 0 || x = -1 then begin asr_fix x offset; x end42else begin43asr_asr x max_int63 (offset - max_int63);44asr_int (asr63 x max_int) (offset - max_int63)45end46Valid (42ms) (colibri2)47let ghost lsl_lsl (x a b:int) : unit48requires { 0 <= a /\ 0 <= b }49ensures { lsl (lsl x a) b = lsl x (a + b) }50= let lemma bit (i:int) : unit51requires { i >= 0 }52ensures { bittest (lsl (lsl x a) b) i = bittest (lsl x (a + b)) i }53= def_asr (lsl x a) (-b) i; def_asr x (-(a + b)) i;54if i - b >= 0 then def_asr x (-a) (i - b)55else (bittest_neg (lsl x a) (i - b); bittest_neg x (i - b - a)) in56ext_bittest (lsl (lsl x a) b) (lsl x (a + b))57Valid (311ms) (cvc4)58let rec lsl_int (x offset:int) : int59requires { 0 <= offset }60ensures { result = lsl x offset }61variant { offset }62= if offset <= max_int63 then lsl63 x (of_int offset)63else if x = 0 then 064else begin65lsl_lsl x max_int63 (offset - max_int63);66lsl_int (lsl63 x max_int) (offset - max_int63)67end68Valid (20ms) (colibri2)69let mask_int (k:int) : int70requires { 0 <= k }71ensures { result = mask k }72= lsl_int 1 k - 173Valid (33ms) (colibri2)74let test_bit_int (x i:int) : bool75requires { 0 <= i }76ensures { result <-> bittest x i }77= if i <= max_int63 then test_bit x (of_int i)78else begin79def_asr x (i - max_int63) max_int63;80test_bit (asr_int x (i - max_int63)) max_int81end82end83