Common — library colibrilib.fbin — module BitsIv

The encodings of an interval of floats, and back

For 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).

2909
module BitsIv
2910
use int.Int
2911
use int.Power
2912
use int.EuclideanDivision
2913
use option.Option
2914
use Pow2r
2915
use Format
2916
use Float
2917
use Round
2918
use Impl
2919
2920
predicate
in_r
(b: int) (r: option (int, int)) =
2921
match r with None -> false | Some (x, y) -> x <= b <= y end
2922
2923
predicate
in_f
(v: t) (r: option (t, t)) =
2924
match r with None -> false | Some (x, y) -> le_dz x v /\ le_dz v y end
2925
Valid (1.1s) (colibri2 7) (cvc4) (split_vc) (depth 1)
2926
let ghost
bits_index
(fm: format) (c: int) : unit
2927
requires { 0 <= c < 2 * half_bits fm }
2928
ensures { let h = half_bits fm in let n1 = nb_sign fm - 1 in
2929
n1 < h /\ (of_bits fm c).fmt = fm /\
2930
(c < h -> (c <= n1 <-> not is_nan (of_bits fm c))) /\
2931
(c < h -> c <= n1 -> index (of_bits fm c) = c) /\
2932
(h <= c -> (c - h <= n1 <-> not is_nan (of_bits fm c))) /\
2933
(h <= c -> c - h <= n1 -> index (of_bits fm c) = h - 1 - c) }
2934
= {proof…}
2935
half_bits_nb_sign fm; binade_ge_2 fm;
2936
let h = half_bits fm in
2937
let n1 = nb_sign fm - 1 in
2938
assert { mod c (2 * h) = c };
2939
if c < h then begin
2940
if c < n1 then assert { of_bits fm c = mk fm (Finite false c) }
2941
else if c = n1 then assert { of_bits fm c = mk fm PlusInf }
2942
else assert { of_bits fm c = mk fm NaN }
2943
end else begin
2944
if c - h < n1 then assert { of_bits fm c = mk fm (Finite true (c - h)) }
2945
else if c - h = n1 then assert { of_bits fm c = mk fm MinusInf }
2946
else assert { of_bits fm c = mk fm NaN }
2947
end
2948
{qed}

The bits of a float that is not NaN, by its index

  Valid (402ms) (colibri2)
2951
let ghost
index_bits
(v: t) : unit
2952
requires { not is_nan v }
2953
ensures { let h = half_bits v.fmt in
2954
0 <= to_bits v < 2 * h /\ of_bits v.fmt (to_bits v) = v /\
2955
(0 <= index v -> to_bits v = index v) /\
2956
(index v < 0 -> to_bits v = h - 1 - index v) }
2957
= {proof…}
2958
half_bits_nb_sign v.fmt; to_bits_range v; of_to_bits v
2959
{qed}

The bits whose float is in [l, hi]

  Valid (1.5s) (cvc4)
2962
let
bits_of_iv
(l hi: t) : (option (int, int), option (int, int))
2963
ensures { let (p, n) = result in forall b. 0 <= b < 2 * half_bits l.fmt ->
2964
(le_dz l (of_bits l.fmt b) /\ le_dz (of_bits l.fmt b) hi <-> in_r b p \/ in_r b n) }
2965
= if is_nan l || is_nan hi || not (eq_format l.fmt hi.fmt) then (None, None)
2966
else begin
2967
let fm = l.fmt in
2968
let h = pow2_int (fm.eb + fm.sb - 1) in
2969
let il = index_p l in
2970
let ih = index_p hi in
2971
let p = if ih >= 0 then Some ((if il >= 0 then il else 0), ih) else None in
2972
let n =
2973
if il <= -1 then Some (h - 1 - (if ih <= -1 then ih else -1), h - 1 - il)
2974
else None in
2975
{proof…}
2976
index_range l; index_range hi;
2977
let lemma pt (b: int) : unit
2978
requires { 0 <= b < 2 * half_bits fm }
2979
ensures { le_dz l (of_bits fm b) /\ le_dz (of_bits fm b) hi <-> in_r b p \/ in_r b n }
2980
= bits_index fm b in
2981
{qed}
2982
(p, n)
2983
end

The bits of the NaNs

  Valid (390ms) (colibri2)
2986
let
nan_bits
(fm: format) : ((int, int), (int, int))
2987
ensures { let ((a1, b1), (a2, b2)) = result in forall b. 0 <= b < 2 * half_bits fm ->
2988
(is_nan (of_bits fm b) <-> a1 <= b <= b1 \/ a2 <= b <= b2) }
2989
= let h = pow2_int (fm.eb + fm.sb - 1) in
2990
let n1 = nb_sign_p fm - 1 in
2991
{proof…}
2992
let lemma pt (b: int) : unit
2993
requires { 0 <= b < 2 * half_bits fm }
2994
ensures { is_nan (of_bits fm b) <-> n1 + 1 <= b <= h - 1 \/ h + n1 + 1 <= b <= 2 * h - 1 }
2995
= bits_index fm b in
2996
{qed}
2997
((n1 + 1, h - 1), (h + n1 + 1, 2 * h - 1))

The floats of the bits of [a, b]: the negative ones, the positive ones and NaN

3001
type
fiv
= {
fneg
: option (t, t);
fpos
: option (t, t);
fnan
: bool }
3002
Valid (1.7s) (colibri2 22) (cvc4 9) (cvc5 19) (split_vc 22) (depth 5)
3003
let
iv_of_bits
(fm: format) (a b: int) : fiv
3004
ensures { forall v. v.fmt = fm -> not is_nan v ->
3005
(in_f v result.fneg \/ in_f v result.fpos <->
3006
exists c. a <= c <= b /\ 0 <= c < 2 * half_bits fm /\ of_bits fm c = v) }
3007
ensures { result.fnan <->
3008
exists c. a <= c <= b /\ 0 <= c < 2 * half_bits fm /\ is_nan (of_bits fm c) }
3009
ensures { match result.fneg with
3010
| None -> true | Some (x, y) -> fmt x = fm /\ le_dz x y /\ index y < 0 end }
3011
ensures { match result.fpos with
3012
| None -> true | Some (x, y) -> fmt x = fm /\ le_dz x y /\ 0 <= index x end }
3013
= let h = pow2_int (fm.eb + fm.sb - 1) in
3014
let n1 = nb_sign_p fm - 1 in
3015
let a = if a < 0 then 0 else a in
3016
let b = if b > 2 * h - 1 then 2 * h - 1 else b in
3017
{proof…}
3018
half_bits_nb_sign fm; binade_ge_2 fm;
3019
{qed}
3020
let pb = if b < n1 then b else n1 in
3021
let fpos =
3022
if a <= pb then begin
3023
{proof…} of_index_range fm a; of_index_range fm pb; {qed}
3024
Some (of_index_p fm a, of_index_p fm pb)
3025
end else None in
3026
let na = if a > h then a else h in
3027
let nb = if b < h + n1 then b else h + n1 in
3028
let fneg =
3029
if na <= nb then begin
3030
{proof…} of_index_range fm (h - 1 - nb); of_index_range fm (h - 1 - na); {qed}
3031
Some (of_index_p fm (h - 1 - nb), of_index_p fm (h - 1 - na))
3032
end else None in
3033
let la = if a > n1 + 1 then a else n1 + 1 in
3034
let lb = if b < h - 1 then b else h - 1 in
3035
let ma = if a > h + n1 + 1 then a else h + n1 + 1 in
3036
let fnan = la <= lb || ma <= b in
3037
{proof…}
3038
let lemma pt (v: t) : unit
3039
requires { v.fmt = fm /\ not is_nan v }
3040
ensures { in_f v fneg \/ in_f v fpos <->
3041
exists c. a <= c <= b /\ 0 <= c < 2 * half_bits fm /\ of_bits fm c = v }
3042
= index_bits v; index_range v;
3043
let lemma ex (c: int) : unit
3044
requires { a <= c <= b /\ 0 <= c < 2 * half_bits fm /\ of_bits fm c = v }
3045
ensures { in_f v fneg \/ in_f v fpos }
3046
= bits_index fm c;
3047
if c < h then begin
3048
assert { a <= c <= pb /\ index v = c };
3049
assert { in_f v fpos }
3050
end else begin
3051
assert { na <= c <= nb /\ index v = h - 1 - c };
3052
assert { in_f v fneg }
3053
end in
3054
if pure { in_f v fneg \/ in_f v fpos } then
3055
assert { a <= to_bits v <= b } in
3056
if la <= lb then begin
3057
bits_index fm la;
3058
assert { a <= la <= b /\ 0 <= la < 2 * half_bits fm /\ is_nan (of_bits fm la) }
3059
end;
3060
if ma <= b then begin
3061
bits_index fm ma;
3062
assert { a <= ma <= b /\ 0 <= ma < 2 * half_bits fm /\ is_nan (of_bits fm ma) }
3063
end;
3064
let lemma nan (c: int) : unit
3065
requires { a <= c <= b /\ 0 <= c < 2 * half_bits fm /\ is_nan (of_bits fm c) }
3066
ensures { fnan }
3067
= bits_index fm c in
3068
{qed}
3069
{ fneg = fneg; fpos = fpos; fnan = fnan }
3070
end