library colibrilib.fbin — module BitsIvFor of_ieee_bits (Fp_interval): the bits 0 <= b < 2^(eb+sb) whose float is in [l, h] (two intervals of bits, the positive and the negative floats), the bits of the NaNs, and the floats of an interval of bits (two intervals of floats and NaN). With H = half_bits fm and n1 the index of +inf, the bits c < H are the floats of index c (NaN above n1), and the bits c >= H the floats of index H - 1 - c (NaN above H + n1).
module BitsIv2909use int.Int2910use int.Power2911use int.EuclideanDivision2912use option.Option2913use Pow2r2914use Format2915use Float2916use Round2917use Impl29182919predicate in_r (b: int) (r: option (int, int)) =2920match r with None -> false | Some (x, y) -> x <= b <= y end29212922predicate in_f (v: t) (r: option (t, t)) =2923match r with None -> false | Some (x, y) -> le_dz x v /\ le_dz v y end2924Valid (1.1s) (colibri2 7) (cvc4) (split_vc) (depth 1)2925let ghost bits_index (fm: format) (c: int) : unit2926requires { 0 <= c < 2 * half_bits fm }2927ensures { let h = half_bits fm in let n1 = nb_sign fm - 1 in2928n1 < h /\ (of_bits fm c).fmt = fm /\2929(c < h -> (c <= n1 <-> not is_nan (of_bits fm c))) /\2930(c < h -> c <= n1 -> index (of_bits fm c) = c) /\2931(h <= c -> (c - h <= n1 <-> not is_nan (of_bits fm c))) /\2932(h <= c -> c - h <= n1 -> index (of_bits fm c) = h - 1 - c) }2933= {proof…}2934half_bits_nb_sign fm; binade_ge_2 fm;2935let h = half_bits fm in2936let n1 = nb_sign fm - 1 in2937assert { mod c (2 * h) = c };2938if c < h then begin2939if c < n1 then assert { of_bits fm c = mk fm (Finite false c) }2940else if c = n1 then assert { of_bits fm c = mk fm PlusInf }2941else assert { of_bits fm c = mk fm NaN }2942end else begin2943if c - h < n1 then assert { of_bits fm c = mk fm (Finite true (c - h)) }2944else if c - h = n1 then assert { of_bits fm c = mk fm MinusInf }2945else assert { of_bits fm c = mk fm NaN }2946end2947{qed}2948
The bits of a float that is not NaN, by its index
Valid (402ms) (colibri2)let ghost index_bits (v: t) : unit2951requires { not is_nan v }2952ensures { let h = half_bits v.fmt in29530 <= to_bits v < 2 * h /\ of_bits v.fmt (to_bits v) = v /\2954(0 <= index v -> to_bits v = index v) /\2955(index v < 0 -> to_bits v = h - 1 - index v) }2956= {proof…}2957half_bits_nb_sign v.fmt; to_bits_range v; of_to_bits v2958{qed}2959
The bits whose float is in [l, hi]
Valid (1.5s) (cvc4)let bits_of_iv (l hi: t) : (option (int, int), option (int, int))2962ensures { let (p, n) = result in forall b. 0 <= b < 2 * half_bits l.fmt ->2963(le_dz l (of_bits l.fmt b) /\ le_dz (of_bits l.fmt b) hi <-> in_r b p \/ in_r b n) }2964= if is_nan l || is_nan hi || not (eq_format l.fmt hi.fmt) then (None, None)2965else begin2966let fm = l.fmt in2967let h = pow2_int (fm.eb + fm.sb - 1) in2968let il = index_p l in2969let ih = index_p hi in2970let p = if ih >= 0 then Some ((if il >= 0 then il else 0), ih) else None in2971let n =2972if il <= -1 then Some (h - 1 - (if ih <= -1 then ih else -1), h - 1 - il)2973else None in2974{proof…}2975index_range l; index_range hi;2976let lemma pt (b: int) : unit2977requires { 0 <= b < 2 * half_bits fm }2978ensures { le_dz l (of_bits fm b) /\ le_dz (of_bits fm b) hi <-> in_r b p \/ in_r b n }2979= bits_index fm b in2980{qed}2981(p, n)2982end2983
The bits of the NaNs
Valid (390ms) (colibri2)let nan_bits (fm: format) : ((int, int), (int, int))2986ensures { let ((a1, b1), (a2, b2)) = result in forall b. 0 <= b < 2 * half_bits fm ->2987(is_nan (of_bits fm b) <-> a1 <= b <= b1 \/ a2 <= b <= b2) }2988= let h = pow2_int (fm.eb + fm.sb - 1) in2989let n1 = nb_sign_p fm - 1 in2990{proof…}2991let lemma pt (b: int) : unit2992requires { 0 <= b < 2 * half_bits fm }2993ensures { is_nan (of_bits fm b) <-> n1 + 1 <= b <= h - 1 \/ h + n1 + 1 <= b <= 2 * h - 1 }2994= bits_index fm b in2995{qed}2996((n1 + 1, h - 1), (h + n1 + 1, 2 * h - 1))2997
The floats of the bits of [a, b]: the negative ones, the positive ones and NaN
type fiv = { fneg: option (t, t); fpos: option (t, t); fnan: bool }3001Valid (1.7s) (colibri2 22) (cvc4 9) (cvc5 19) (split_vc 22) (depth 5)3002let iv_of_bits (fm: format) (a b: int) : fiv3003ensures { forall v. v.fmt = fm -> not is_nan v ->3004(in_f v result.fneg \/ in_f v result.fpos <->3005exists c. a <= c <= b /\ 0 <= c < 2 * half_bits fm /\ of_bits fm c = v) }3006ensures { result.fnan <->3007exists c. a <= c <= b /\ 0 <= c < 2 * half_bits fm /\ is_nan (of_bits fm c) }3008ensures { match result.fneg with3009| None -> true | Some (x, y) -> fmt x = fm /\ le_dz x y /\ index y < 0 end }3010ensures { match result.fpos with3011| None -> true | Some (x, y) -> fmt x = fm /\ le_dz x y /\ 0 <= index x end }3012= let h = pow2_int (fm.eb + fm.sb - 1) in3013let n1 = nb_sign_p fm - 1 in3014let a = if a < 0 then 0 else a in3015let b = if b > 2 * h - 1 then 2 * h - 1 else b in3016{proof…}3017half_bits_nb_sign fm; binade_ge_2 fm;3018{qed}3019let pb = if b < n1 then b else n1 in3020let fpos =3021if a <= pb then begin3022{proof…} of_index_range fm a; of_index_range fm pb; {qed}3023Some (of_index_p fm a, of_index_p fm pb)3024end else None in3025let na = if a > h then a else h in3026let nb = if b < h + n1 then b else h + n1 in3027let fneg =3028if na <= nb then begin3029{proof…} of_index_range fm (h - 1 - nb); of_index_range fm (h - 1 - na); {qed}3030Some (of_index_p fm (h - 1 - nb), of_index_p fm (h - 1 - na))3031end else None in3032let la = if a > n1 + 1 then a else n1 + 1 in3033let lb = if b < h - 1 then b else h - 1 in3034let ma = if a > h + n1 + 1 then a else h + n1 + 1 in3035let fnan = la <= lb || ma <= b in3036{proof…}3037let lemma pt (v: t) : unit3038requires { v.fmt = fm /\ not is_nan v }3039ensures { in_f v fneg \/ in_f v fpos <->3040exists c. a <= c <= b /\ 0 <= c < 2 * half_bits fm /\ of_bits fm c = v }3041= index_bits v; index_range v;3042let lemma ex (c: int) : unit3043requires { a <= c <= b /\ 0 <= c < 2 * half_bits fm /\ of_bits fm c = v }3044ensures { in_f v fneg \/ in_f v fpos }3045= bits_index fm c;3046if c < h then begin3047assert { a <= c <= pb /\ index v = c };3048assert { in_f v fpos }3049end else begin3050assert { na <= c <= nb /\ index v = h - 1 - c };3051assert { in_f v fneg }3052end in3053if pure { in_f v fneg \/ in_f v fpos } then3054assert { a <= to_bits v <= b } in3055if la <= lb then begin3056bits_index fm la;3057assert { a <= la <= b /\ 0 <= la < 2 * half_bits fm /\ is_nan (of_bits fm la) }3058end;3059if ma <= b then begin3060bits_index fm ma;3061assert { a <= ma <= b /\ 0 <= ma < 2 * half_bits fm /\ is_nan (of_bits fm ma) }3062end;3063let lemma nan (c: int) : unit3064requires { a <= c <= b /\ 0 <= c < 2 * half_bits fm /\ is_nan (of_bits fm c) }3065ensures { fnan }3066= bits_index fm c in3067{qed}3068{ fneg = fneg; fpos = fpos; fnan = fnan }3069end3070