library colibrilib.zbit_model — module ZbitModelmodule ZbitModel : colibrilib.zarith.Zbit6
Implemented
use int.Int7use int.MinMax8use int.EuclideanDivision9use int.Power1011function pow2 (n:int) : int = power 2 n1213predicate bittest (x i:int) = 0 <= i /\ (mod x (pow2 (i+1))) >= pow2 i1415predicate subset (a:int) (b:int) = forall i. bittest a i -> bittest b i16Valid (24ms) (colibri2)17lemma pow2_pos: forall i. 0 <= i -> 0 < pow2 i Valid (26ms) (colibri2)18lemma pow2_s: forall i. 0 <= i -> pow2 (i+1) = 2 * pow2 i Valid (16ms) (colibri2)19lemma pow2_ge_2: forall i. 1 <= i -> 2 <= pow2 i Valid (40ms) (colibri2)20let rec lemma pow2_add (a b:int) : unit21requires { 0 <= a }22requires { 0 <= b }23ensures { pow2 (a+b) = pow2 a * pow2 b }24variant { b }25=26if b = 0 then assert { pow2 0 = 1 }27else begin28pow2_s (a+b-1);29pow2_add a (b-1);30pow2_s (b-1)31end Valid (26ms) (colibri2)32let rec lemma pow2_le (a b:int) : unit33requires { 0 <= a <= b }34ensures { pow2 a <= pow2 b }35variant { b - a }36=37if a = b then ()38else begin39pow2_s (b-1);40pow2_le a (b-1)41end Valid (1.1s) (cvc5) (split_vc) (depth 1)42lemma mod_twice: forall x y. 0 < y -> mod (2*x) (2*y) = 2 * mod x y43Valid (59ms) (colibri2)44let lemma even_bittest (x i:int) : unit45requires { 0 <= i }46ensures { bittest (2*x) i = (if i = 0 then False else bittest x (i-1)) }47=48if i = 0 then ()49else begin50pow2_s i;51mod_twice x (pow2 i);52pow2_s (i-1)53end54Valid (249ms) (colibri2)55let lemma odd_bittest (x i:int) : unit56requires { 0 <= i }57ensures { bittest (2*x+1) i = (if i = 0 then True else bittest x (i-1)) }58=59if i = 0 then ()60else begin61pow2_s i;62mod_twice x (pow2 i);63pow2_s (i-1)64end65Valid (24ms) (colibri2)66lemma bittest_neg: forall x i. i < 0 -> not (bittest x i) Valid (32ms) (colibri2)67lemma bittest_0: forall i. not (bittest 0 i) Valid (39ms) (colibri2)68lemma bittest_1: forall i. bittest 1 i = (i = 0)69Valid (56ms) (colibri2)70let lemma bittest_div2 (x i:int) : unit71requires { 0 <= i }72ensures { bittest (div x 2) i = bittest x (i+1) }73=74let r = mod x 2 in75if r = 0 then begin76even_bittest (div x 2) (i+1);77end else begin78odd_bittest (div x 2) (i+1);79end80Valid (64ms) (colibri2)81let rec lemma bits_zero (z:int) : unit82requires { forall i. 0 <= i -> not (bittest z i) }83ensures { z = 0 }84variant { if z >= 0 then z else -z }85=86if z = 0 then ()87else begin88assert { not (bittest z 0) };89bits_zero (div z 2)90end91Valid (32ms) (colibri2)92let lemma bittest_parity (x:int) : unit93ensures { bittest x 0 <-> (mod x 2 = 1) }94=95()96Valid (2.5s) (colibri2 7) (split_vc) (depth 1)97let rec lemma ext_bittest_pos (x y:int) : unit98requires { 0 < x }99requires { forall i. 0 <= i -> bittest x i = bittest y i }100ensures { x = y }101variant { x }102=103let xh = div x 2 in104let yh = div y 2 in105bittest_parity x;106bittest_parity y;107if xh > 0 then begin108ext_bittest_pos xh yh109end else begin110bits_zero yh111end112Valid (395ms) (colibri2)113let rec lemma bits_minus_one (z:int) : unit114requires { forall i. 0 <= i -> bittest z i }115ensures { z = -1 }116variant { if z >= 0 then z else -z }117=118bittest_parity z;119if div z 2 <> z then bits_minus_one (div z 2)120Valid (309ms) (colibri2 7) (split_vc) (depth 1)121let rec lemma ext_bittest_neg (x y:int) : unit122requires { x < 0 }123requires { forall i. 0 <= i -> bittest x i = bittest y i }124ensures { x = y }125variant { -x }126=127let xh = div x 2 in128let yh = div y 2 in129bittest_parity x;130bittest_parity y;131if xh <> x then begin132ext_bittest_neg xh yh133end else begin134bits_minus_one y135end136Valid (46ms) (colibri2)137let lemma ext_bittest (x y:int) : unit138requires { forall i. 0 <= i -> bittest x i = bittest y i }139ensures { x = y }140=141if x > 0 then ext_bittest_pos x y142else if x = 0 then begin143bits_zero y144end145else ext_bittest_neg x y146147function asr (x offset:int) : int =148if 0 <= offset then div x (pow2 offset) else x * pow2 (-offset)149150function lsl (x offset:int) : int = asr x (-offset)151152function mask (k:int) : int = lsl 1 k - 1153Valid (32ms) (colibri2)154let rec function numbits (x:int) : int =155variant { if x < 0 then -x else x }156if x = 0 then 0157else if x < 0 then 1 + numbits (div (-x) 2)158else 1 + numbits (div x 2)159Valid (29ms) (colibri2)160lemma asr_eq: forall x. asr x 0 = x161Valid (19ms) (colibri2)162let ghost asr_div (x n:int) : unit163requires { 0 <= n }164ensures { asr x n = div x (power 2 n) }165= ()166Valid (32ms) (colibri2)167let ghost lsl_mul (x n:int) : unit168requires { 0 <= n }169ensures { lsl x n = x * power 2 n }170= if n = 0 then assert { div x (pow2 0) = x }171Valid (25ms) (colibri2)172let lemma asr_gt (x offset:int) : unit173requires { 0 < x /\ offset < 0 }174ensures { x < asr x offset }175=176pow2_ge_2 (-offset);177assert { x * 2 <= x * pow2 (-offset) }178Valid (753ms) (colibri2)179let lemma div_twice (x y:int) : unit180requires { 0 < y }181ensures { div x (2*y) = div (div x y) 2 }182=183let q = div x y in184let r = mod x y in185assert { x = 2*y*(div q 2) + y*(mod q 2) + r }186Valid (132ms) (colibri2)187let rec lemma bittest_div_pow2 (x k i:int) : unit188requires { 0 <= k }189requires { 0 <= i }190ensures { bittest (div x (pow2 k)) i = bittest x (i+k) }191variant { k }192=193if k = 0 then ()194else begin195pow2_s (k-1);196div_twice x (pow2 (k-1));197bittest_div2 (div x (pow2 (k-1))) i;198bittest_div_pow2 x (k-1) (i+1)199end200Valid (134ms) (colibri2)201let rec lemma bittest_mul_pow2 (x k i:int) : unit202requires { 0 <= k }203ensures { bittest (x * pow2 k) i <-> (i >= k /\ bittest x (i-k)) }204variant { k }205=206if k = 0 then ()207else begin208pow2_s (k-1);209bittest_mul_pow2 (x*2) (k-1) i;210let j = i - (k-1) in211if j >= 0 then even_bittest x j212end213Valid (49ms) (colibri2)214let lemma def_asr (x offset i:int) : unit215requires { i >= 0 }216ensures { bittest (asr x offset) i = bittest x (i+offset) }217=218if 0 <= offset then begin219bittest_div_pow2 x offset i220end else begin221bittest_mul_pow2 x (-offset) i222end223Valid (24ms) (colibri2)224let lemma mask_pow2 (k:int) : unit225requires { 0 <= k }226ensures { mask k = pow2 k - 1 }227=228()229Valid (28ms) (colibri2)230let lemma mask_nonneg (k:int) : ()231requires { 0 <= k }232ensures { 0 <= mask k } =233if k = 0 then asr_eq 1234else asr_gt 1 (-k)235236Valid (229ms) (colibri2)237let lemma bittest_pred_pow2 (k i:int) : unit238requires { 0 <= i < k }239ensures { bittest (pow2 k - 1) i }240=241pow2_add (i+1) (k - i - 1);242assert { pow2 k - 1 = pow2 (i+1) * (pow2 (k - i - 1) - 1) + (pow2 (i+1) - 1) };243pow2_s i244Valid (1.1s) (colibri2)245let lemma bittest_pred_pow2_high (k i:int) : unit246requires { 0 <= k <= i }247ensures { not (bittest (pow2 k - 1) i) }248=249pow2_le k (i+1);250pow2_le k i251Valid (26ms) (colibri2)252let lemma mask_bits (k i:int) : unit253requires { 0 <= k }254requires { 0 <= i < k }255ensures { bittest (mask k) i }256=257mask_pow2 k;258bittest_pred_pow2 k i259Valid (19ms) (colibri2)260let lemma mask_bits_high (k i:int) : unit261requires { 0 <= k }262requires { i >= k }263ensures { not (bittest (mask k) i) }264=265mask_pow2 k;266bittest_pred_pow2_high k i267Valid (37ms) (colibri2)268let lemma numbits_neg (x:int) : unit269requires { x < 0 }270ensures { numbits x = numbits (-x) }271=272()273Valid (36ms) (colibri2)274let rec lemma numbits_nonneg (x:int) : unit275requires { 0 <= x }276ensures { 0 <= numbits x }277variant { x }278=279if x = 0 then assert { numbits 0 = 0 }280else begin281numbits_nonneg (div x 2)282end283Valid (51ms) (colibri2)284let rec lemma numbits_ge_1 (x:int) : unit285requires { 1 <= x }286ensures { 1 <= numbits x }287variant { x }288=289if x = 1 then assert { numbits 1 = 1 }290else begin291numbits_ge_1 (div x 2)292end293Valid (67ms) (colibri2)294let rec lemma numbits_bound (x:int) : unit295requires { 0 <= x }296ensures { x < pow2 (numbits x) }297variant { x }298=299if x = 0 then assert { numbits 0 = 0 }300else begin301numbits_bound (div x 2);302numbits_nonneg (div x 2);303pow2_s (numbits (div x 2))304end305Valid (130ms) (colibri2)306let rec lemma numbits_lower (x:int) : unit307requires { x > 0 }308ensures { pow2 (numbits x - 1) <= x }309variant { x }310=311if x = 1 then assert { numbits 1 = 1 }312else begin313numbits_lower (div x 2);314numbits_ge_1 (div x 2);315pow2_s (numbits (div x 2) - 1)316end317Valid (98ms) (colibri2)318let rec lemma numbits_pow2 (n:int) : unit319requires { 0 <= n }320ensures { numbits (pow2 n) = n + 1 }321variant { n }322=323if n = 0 then assert { numbits 1 = 1 }324else begin325pow2_s (n-1);326numbits_pow2 (n-1)327end328Valid (32ms) (colibri2)329let lemma numbits_top_bit (x:int) : unit330requires { x > 0 }331ensures { bittest x (numbits x - 1) }332=333numbits_ge_1 x;334numbits_lower x;335numbits_bound x336Valid (1.1s) (colibri2)337let lemma numbits_high_clear (x i:int) : unit338requires { x > 0 }339requires { i >= numbits x }340ensures { not (bittest x i) }341=342numbits_bound x;343pow2_le (numbits x) i;344pow2_le (numbits x) (i+1)345Valid (78ms) (colibri2)346let rec lemma numbits_le (x n:int) : unit347requires { 0 <= x }348requires { 0 <= n }349requires { x < pow2 n }350ensures { numbits x <= n }351variant { x }352=353if x = 0 then assert { numbits 0 = 0 }354else begin355pow2_s (n-1);356numbits_le (div x 2) (n-1)357end358Valid (70ms) (colibri2)359let rec lemma numbits_ge (x n:int) : unit360requires { 0 <= x }361requires { 0 <= n }362requires { pow2 n <= x }363ensures { n + 1 <= numbits x }364variant { x }365=366if n = 0 then begin367numbits_ge_1 x368end else begin369pow2_s (n-1);370numbits_ge (div x 2) (n-1)371end372Valid (34ms) (colibri2)373lemma numbits_pos: forall x. x > 0 ->374bittest x (numbits x - 1) /\375(forall i. i >= numbits x -> not (bittest x i))376Valid (42ms) (colibri2)377let lemma numbits_lsl (n:int) : unit378requires { 0 <= n }379ensures { numbits (lsl 1 n) = n + 1 }380=381()382Valid (37ms) (colibri2)383let lemma mask_numbits (k:int) : unit384requires { 0 <= k }385ensures { numbits (mask k) = k }386=387mask_pow2 k;388if k = 0 then assert { mask 0 = 0 }389else begin390pow2_pos k;391numbits_le (pow2 k - 1) k;392pow2_s (k-1);393pow2_pos (k-1);394numbits_ge (pow2 k - 1) (k-1)395end396Valid (33ms) (colibri2)397let lemma numbits_ge_pos (x y:int) : unit398requires { 0 <= x }399requires { 0 <= y }400requires { x <= y }401ensures { numbits x <= numbits y }402=403numbits_bound y;404numbits_nonneg y;405numbits_le x (numbits y)406Valid (29ms) (colibri2)407let lemma numbits_gt_pos (x y:int) : unit408requires { 0 <= x }409requires { 0 <= y }410requires { numbits x < numbits y }411ensures { x < y }412=413if not (x < y) then begin414numbits_ge_pos y x415end416Valid (48ms) (colibri2)417let lemma numbits_lt_lsl (x n:int) : unit418requires { 0 <= x }419requires { x < lsl 1 n }420ensures { numbits x <= n }421=422if n < 0 then begin423pow2_ge_2 (-n)424end;425numbits_le x n426Valid (58ms) (colibri2)427let lemma numbits_mul_pow2 (x k:int) : unit428requires { 0 < x }429requires { 0 <= k }430ensures { numbits (x * pow2 k) = numbits x + k }431=432numbits_lower x;433numbits_bound x;434numbits_nonneg x;435pow2_add (numbits x - 1) k;436assert { pow2 (numbits x - 1) * pow2 k <= x * pow2 k };437pow2_add (numbits x) k;438numbits_ge (x * pow2 k) (numbits x - 1 + k);439numbits_le (x * pow2 k) (numbits x + k)440Valid (15ms) (colibri2)441let lemma div_lt (a b q:int) : unit442requires { 0 < b /\ a < b * q }443ensures { div a b < q }444=445if div a b >= q then assert { b * div a b >= b * q }446Valid (36ms) (colibri2)447let lemma div_ge (a b q:int) : unit448requires { 0 < b /\ b * q <= a }449ensures { q <= div a b }450=451if div a b < q then assert { b * div a b <= b * q - b }452Valid (121ms) (colibri2)453let lemma numbits_asr_pow2 (x k:int) : unit454requires { 0 < x }455requires { 0 <= k }456ensures { numbits (div x (pow2 k)) = max 0 (numbits x - k) }457=458numbits_bound x;459numbits_lower x;460numbits_nonneg x;461if numbits x - k <= 0 then begin462pow2_le (numbits x) k463end else begin464pow2_add k (numbits x - 1 - k);465div_ge x (pow2 k) (pow2 (numbits x - 1 - k));466pow2_add k (numbits x - k);467div_lt x (pow2 k) (pow2 (numbits x - k));468numbits_ge (div x (pow2 k)) (numbits x - 1 - k);469numbits_le (div x (pow2 k)) (numbits x - k)470end471Valid (27ms) (colibri2)472let lemma asr_nonneg (x offset:int) : unit473requires { 0 <= x }474ensures { 0 <= asr x offset }475=476()477Valid (227ms) (colibri2)478let lemma asr_numbits (x offset:int) : unit479requires { 0 < x }480ensures { numbits (asr x offset) = max 0 (numbits x - offset) }481=482()483Valid (380ms) (cvc4)484let rec function land (x y:int) : int485variant { max (if x < 0 then -x else x) (if y < 0 then -y else y) }486= if x = -1 then y487else if y = -1 then x488else if x = 0 || y = 0 then 0489else let xh = div x 2 in490let yh = div y 2 in491let b = if mod x 2 = 1 && mod y 2 = 1 then 1 else 0 in492b + 2 * land xh yh493Valid (2.0s) (colibri2 21) (split_vc 5) (depth 4)494let rec lemma def_land (x y i:int) : unit495requires { 0 <= i }496ensures { bittest (land x y) i <-> (bittest x i /\ bittest y i) }497variant { i }498=499if x = -1 then ()500else if y = -1 then ()501else if x = 0 || y = 0 then ()502else begin503let xh = div x 2 in504let yh = div y 2 in505let b = if mod x 2 = 1 && mod y 2 = 1 then 1 else 0 in506assert { land x y = b + 2 * land xh yh };507if i = 0 then begin508bittest_parity (land x y);509bittest_parity x;510bittest_parity y511end else begin512if b = 1 then odd_bittest (land xh yh) i else even_bittest (land xh yh) i;513if mod x 2 = 1 then odd_bittest xh i else even_bittest xh i;514if mod y 2 = 1 then odd_bittest yh i else even_bittest yh i;515def_land xh yh (i-1)516end517end518Valid (665ms) (cvc5)519let rec lemma land_nonneg (x y:int) : unit520requires { 0 <= x /\ 0 <= y }521ensures { 0 <= land x y }522variant { max x y }523=524if x = 0 || y = 0 then ()525else begin526let xh = div x 2 in527let yh = div y 2 in528land_nonneg xh yh529end530Valid (108ms) (colibri2)531let rec lemma land_nonneg_l (x y:int) : unit532requires { 0 <= x }533ensures { 0 <= land x y }534variant { x }535=536if x = 0 || y = -1 || y = 0 then ()537else begin538let xh = div x 2 in539let yh = div y 2 in540land_nonneg_l xh yh541end542Valid (697ms) (cvc5)543let rec lemma land_le (x y:int) : unit544requires { 0 <= x /\ 0 <= y }545ensures { land x y <= y }546variant { max x y }547=548if x = 0 || y = 0 then ()549else begin550let xh = div x 2 in551let yh = div y 2 in552land_le xh yh553end554Valid (393ms) (colibri2)555let rec function lor (x y:int) : int556variant { max (if x < 0 then -x else x) (if y < 0 then -y else y) }557= if x = -1 || y = -1 then -1558else if x = 0 then y559else if y = 0 then x560else let xh = div x 2 in561let yh = div y 2 in562let b = if mod x 2 = 1 || mod y 2 = 1 then 1 else 0 in563b + 2 * lor xh yh564Valid (502ms) (colibri2)565let rec lemma def_lor (x y i:int) : unit566requires { 0 <= i }567ensures { bittest (lor x y) i <-> (bittest x i \/ bittest y i) }568variant { i }569=570if x = -1 then ()571else if y = -1 then ()572else if x = 0 then ()573else if y = 0 then ()574else begin575let xh = div x 2 in576let yh = div y 2 in577let b = if mod x 2 = 1 || mod y 2 = 1 then 1 else 0 in578if i = 0 then begin579bittest_parity (lor x y);580bittest_parity x;581bittest_parity y582end else begin583if b = 1 then odd_bittest (lor xh yh) i else even_bittest (lor xh yh) i;584if mod x 2 = 1 then odd_bittest xh i else even_bittest xh i;585if mod y 2 = 1 then odd_bittest yh i else even_bittest yh i;586def_lor xh yh (i-1)587end588end589Valid (671ms) (cvc5)590let rec lemma lor_nonneg (x y:int) : unit591requires { 0 <= x /\ 0 <= y }592ensures { 0 <= lor x y }593variant { max x y }594=595if x = 0 || y = 0 then ()596else begin597let xh = div x 2 in598let yh = div y 2 in599lor_nonneg xh yh600end601Valid (169ms) (cvc5)602let rec lemma lor_le (x y:int) : unit603requires { 0 <= x /\ 0 <= y }604ensures { y <= lor x y }605variant { max x y }606=607if x = 0 || y = 0 then ()608else begin609let xh = div x 2 in610let yh = div y 2 in611lor_le xh yh612end613Valid (1.2s) (colibri2 5) (split_vc) (depth 1)614let rec lemma lor_numbits (x y:int) : unit615requires { 0 <= x /\ 0 <= y }616ensures { numbits (lor x y) = max (numbits x) (numbits y) }617variant { max x y }618=619if x = 0 then ()620else if y = 0 then ()621else begin622let xh = div x 2 in623let yh = div y 2 in624lor_numbits xh yh625end626627let function lnot (x:int) : int = -x - 1628Valid (184ms) (colibri2)629let rec lemma def_lnot (x i:int) : unit630requires { 0 <= i }631ensures { bittest (lnot x) i <-> not (bittest x i) }632variant { i }633=634if i = 0 then begin635bittest_parity x;636bittest_parity (lnot x)637end else begin638let q = div x 2 in639if mod x 2 = 0 then begin640odd_bittest (-q-1) i;641even_bittest q i;642def_lnot q (i-1)643end else begin644even_bittest (-q-1) i;645odd_bittest q i;646def_lnot q (i-1)647end648end649650function set (x:int) (offset:int) : int =651lor x (lsl 1 offset)652Valid (263ms) (colibri2)653let lemma def_set (x offset i:int) : unit654requires { 0 <= i }655ensures { bittest (set x offset) i = (i = offset \/ bittest x i) }656=657def_lor x (lsl 1 offset) i;658assert { bittest (lsl 1 offset) i <-> i = offset }659660661function unset (x:int) (offset:int) : int = land x (lnot (lsl 1 offset))662let function lxor (x y:int) : int = lor (land x (lnot y)) (land (lnot x) y)663664function change (x:int) (offset:int) (v:bool) : int =665if v then set x offset else unset x offset666Valid (215ms) (colibri2)667let lemma def_change (x offset i:int) (v:bool) : unit668requires { 0 <= i }669ensures { bittest (change x offset v) i <-> (if i = offset then v else bittest x i) }670=671def_asr 1 (- offset) i;672if v then def_lor x (lsl 1 offset) i673else begin674def_land x (lnot (lsl 1 offset)) i;675def_lnot (lsl 1 offset) i676end677Valid (46ms) (colibri2)678let lemma change_nonneg (x offset:int) (v:bool) : unit679requires { 0 <= x }680ensures { 0 <= change x offset v }681=682if v then begin683lor_nonneg x (lsl 1 offset)684end else begin685land_nonneg_l x (lnot (lsl 1 offset))686end687Valid (176ms) (colibri2)688let rec ghost function of_bits (f: int -> bool) (n:int) : int689variant { n }690ensures { 0 <= result }691ensures { forall i. 0 <= i -> (bittest result i <-> (i < n /\ f i)) }692= if n <= 0 then 0693else begin694let r = of_bits f (n-1) in695change_nonneg r (n-1) (f (n-1));696change r (n-1) (f (n-1))697end698Valid (48ms) (colibri2)699let lemma of_bits_nonneg (f: int -> bool) (n:int) : unit700ensures { 0 <= of_bits f n }701= ()702Valid (62ms) (colibri2)703let lemma def_of_bits (f: int -> bool) (n i:int) : unit704requires { 0 <= i }705ensures { bittest (of_bits f n) i <-> (i < n /\ f i) }706= ()707Valid (39ms) (colibri2)708let lemma unset_nonneg (x offset:int) : unit709requires { 0 <= x }710ensures { 0 <= unset x offset }711=712land_nonneg_l x (lnot (lsl 1 offset))713Valid (800ms) (colibri2 7) (split_vc) (depth 1)714let lemma numbits_unset_le (x offset:int) : unit715requires { 0 <= x }716requires { 0 <= offset }717ensures { numbits (unset x offset) <= numbits x }718=719if x = 0 then ()720else begin721assert { forall j. 0 <= j -> bittest (unset x offset) j -> bittest x j };722if numbits (unset x offset) > numbits x then begin723assert { unset x offset > 0 };724assert { numbits (unset x offset) - 1 >= numbits x };725assert { bittest (unset x offset) (numbits (unset x offset) - 1) };726assert { bittest x (numbits (unset x offset) - 1) };727assert { not bittest x (numbits (unset x offset) - 1) }728end729end730Valid (268ms) (colibri2)731let lemma land_numbits (x y:int) : unit732requires { 0 <= x /\ 0 <= y }733ensures { numbits (land x y) <= min (numbits x) (numbits y) }734=735land_nonneg x y;736land_le x y;737land_le y x;738ext_bittest (land y x) (land x y);739numbits_ge_pos (land x y) y;740numbits_ge_pos (land x y) x741Valid (58ms) (colibri2)742let lemma numbits_set (x offset:int) : unit743requires { 0 <= x /\ 0 <= offset }744ensures { numbits (set x offset) = max (numbits x) (offset+1) }745=746numbits_lsl offset;747lor_numbits x (lsl 1 offset)748Valid (51ms) (colibri2)749let lemma numbits_change_true (x offset:int) : unit750requires { 0 <= x /\ 0 <= offset }751ensures { numbits (change x offset True) = max (numbits x) (offset+1) }752=753numbits_set x offset754Valid (60ms) (colibri2 5) (cvc5) (split_vc) (depth 1)755let lemma bittest_sub_lsl (x s j:int) : unit756requires { 0 <= j < s }757ensures { bittest (x - lsl 1 s) j <-> bittest x j }758=759mask_pow2 s;760pow2_add (j+1) (s-j-1);761pow2_pos (j+1);762assert { x - lsl 1 s = pow2 (j+1) * (- pow2 (s-j-1)) + x }763Valid (76ms) (colibri2)764let lemma bittest_sub_lsl_high (x s j:int) : unit765requires { 0 <= x /\ 0 <= s <= j }766requires { x < lsl 1 s }767ensures { bittest (x - lsl 1 s) j }768=769mask_pow2 s;770pow2_le s j;771pow2_s j;772pow2_pos s;773let y = x - pow2 s in774assert { - pow2 (j+1) <= y < 0 };775assert { pow2 (j+1) * (-1) <= y < pow2 (j+1) * (-1) + pow2 (j+1) };776assert { div y (pow2 (j+1)) = -1 };777assert { mod y (pow2 (j+1)) = y + pow2 (j+1) }778779predicate carry (x y i: int) = mod x (pow2 i) + mod y (pow2 i) >= pow2 i780Valid (58ms) (colibri2)781let lemma carry_0 (x y: int) : unit782ensures { not (carry x y 0) }783= assert { pow2 0 = 1 }784
The bit i is the parity of the quotient by 2^i
Valid (57ms) (colibri2)
787 let lemma bittest_quot (x i: int) : unit
788 requires { 0 <= i }
789 ensures { bittest x i <-> mod (div x (pow2 i)) 2 = 1 }
790 =
791 bittest_div_pow2 x i 0;
792 bittest_parity (div x (pow2 i))
793
Valid (56ms) (colibri2)
794 let lemma mod_split (x p: int) : unit
795 requires { 0 < p }
796 ensures { mod x (2 * p) = mod x p + p * mod (div x p) 2 }
797 =
798 let q = div x p in
799 assert { x = p * q + mod x p };
800 assert { q = 2 * div q 2 + mod q 2 };
801 assert { p * q = 2 * p * div q 2 + p * mod q 2 };
802 assert { x = 2 * p * div q 2 + (mod x p + p * mod q 2) };
803 assert { 0 <= mod x p + p * mod q 2 < 2 * p }
804
Valid (703ms) (cvc5)
805 let lemma div_add (x y p: int) : unit
806 requires { 0 < p }
807 ensures { div (x + y) p = div x p + div y p + (if mod x p + mod y p >= p then 1 else 0) }
808 =
809 let c = if mod x p + mod y p >= p then 1 else 0 in
810 let q = div x p + div y p + c in
811 Div_mod x p;
812 Div_mod y p;
813 assert { x + y = q * p + (mod x p + mod y p - p * c) };
814 assert { 0 <= mod x p + mod y p - p * c < p };
815 Div_unique (x + y) p q
816
Valid (86ms) (colibri2)
817 let lemma carry_succ (x y i: int) : unit
818 requires { 0 <= i }
819 ensures { carry x y (i+1) <-> ((bittest x i /\ bittest y i) \/ ((bittest x i \/ bittest y i) /\ carry x y i)) }
820 =
821 let p = pow2 i in
822 pow2_s i;
823 mod_split x p;
824 mod_split y p;
825 bittest_quot x i;
826 bittest_quot y i
827
Valid (148ms) (colibri2)
828 let lemma bittest_add (x y i: int) : unit
829 requires { 0 <= i }
830 ensures { bittest (x + y) i <-> ((bittest x i <-> bittest y i) <-> carry x y i) }
831 =
832 let p = pow2 i in
833 div_add x y p;
834 bittest_quot x i;
835 bittest_quot y i;
836 bittest_quot (x + y) i;
837 let dx = div x p in
838 let dy = div y p in
839 assert { mod (dx + dy) 2 = mod (mod dx 2 + mod dy 2) 2 };
840 assert { mod (dx + dy + 1) 2 = mod (mod dx 2 + mod dy 2 + 1) 2 }
841
842 use mach.int.Int63
844
845 (* 2^n for the bodies below, which the driver replaces: int.Power.power
has no precondition, so it is not extracted *)
Valid (60ms) (colibri2)
846 let rec pow2_body (n:int) : int
847 requires { 0 <= n }
848 variant { n }
849 ensures { result = pow2 n }
850 = if n = 0 then 1 else 2 * pow2_body (n - 1)
851
Valid (43ms) (colibri2)
852 let test_bit (x:int) (i:int63) : bool
853 requires { 0 <= i }
854 ensures { result <-> bittest x i }
855 = let i = to_int i in mod x (pow2_body (i+1)) >= pow2_body i
856
Valid (35ms) (colibri2)
857 let lsl63 (x:int) (offset:int63) : int
858 requires { 0 <= offset }
859 ensures { result = lsl x offset }
860 = x * pow2_body (to_int offset)
861
Valid (36ms) (colibri2)
862 let asr63 (x:int) (offset:int63) : int
863 requires { 0 <= offset }
864 ensures { result = asr x offset }
865 = div x (pow2_body (to_int offset))
866
Valid (41ms) (colibri2)
867 let mask63 (k:int63) : int
868 requires { 0 <= k }
869 ensures { result = mask k }
870 = pow2_body (to_int k) - 1
871
872
Valid (109ms) (colibri2)
873 let rec trailing_zeros (x:int) : int
874 requires { x <> 0 }
875 ensures { 0 <= result }
876 ensures { bittest x result }
877 ensures { forall j. 0 <= j < result -> not (bittest x j) }
878 variant { if x < 0 then -x else x }
879 = if mod x 2 <> 0 then begin
880 assert { x = 2 * div x 2 + 1 };
881 odd_bittest (div x 2) 0;
882 0
883 end else begin
884 let y = div x 2 in
885 assert { x = 2 * y /\ y <> 0 };
886 let r = trailing_zeros y in
887 even_bittest y (r + 1);
888 let lemma low (j:int) : unit
889 requires { 0 <= j < r + 1 }
890 ensures { not (bittest x j) }
891 = even_bittest y j in
892 r + 1
893 end
894end