Fil-C on Nix

Filnix wiki

the formal campaign

rocq/theories/Ops.v

Integer arithmetic and the evaluation of ops, transcribed from interp.pl's Operations section: alu/4, additive_res/4 and kind_res/8 for the core subset.

Integers of class K are 0..2^bits(K)-1; signed readings, shift counts and divisions follow the interpreter clause by clause. Fil-C defines division by zero as 0 and MIN / −1 as MIN (docs/ub.md), so integer arithmetic never has undefined behaviour here.

op_res gives an op's partial result, or asks for an allocation: alloc is the only op whose result depends on a choice, the fresh base of its object (Memory.v's fresh).

From Stdlib Require Import String ZArith List Bool
From Nanofil Require Import Term Ieee Syntax Values Memory
Import ListNotations
Open Scope Z_scope

Option binding: let* x ≔ e in b is b with x the value of e, or none if e has none.

21Notation 'let*' x ':=' e 'in' b ≔ match e with Somex ⇒ b | None ⇒ None end (at level 200 , x name , e at level 100 , b at level 200)

Integers

As sign_extension(M, H, U, S): the two's-complement reading of the low bits of u, for a field of modulus m with sign threshold h, from which values read as negative.

30Definition sign_extensionm h u : Z : Z ≔
let l ≔ u mod m in
h ≤? l
→
l − m
else
l

As signed(K, U, S): the integer u of class k read as signed; none for a class that is not an integer class.

35Definition signedk : class u : Z : optionZ ≔
let* m ≔ modulusk in
let* h ≔ half_modulusk in

As extension(T, X, S): the low bytes of x that the narrow type t names, sign- or zero-extended.

42Definition extensiont : narrow x : Z : Z ≔
match t with
⇒
⇒
x mod 256
⇒
sign_extension65536 32768 x
⇒
x mod 65536
⇒
sign_extension2 ^ 32 2 ^ 31 x
⇒
x mod 2 ^ 32

As cond_bit(Cond, K, X, Y, B): 1 when x c y holds at the integer class k, else 0; a float condition has none here (float_compare).

55Definition cond_bitc : cond k : class x y : Z : optionZ ≔
let bit b : bool ≔
Some
→
1
else
0
in
match c with
⇒
bitx =? y
⇒
bitnegbx =? y
⇒
bitx <? y
⇒
bitx ≤? y
⇒
bity <? x
⇒
bity ≤? x
⇒
let* sx ≔ signedk x in
let* sy ≔ signedk y in
bitsx <? sy
⇒
let* sx ≔ signedk x in
let* sy ≔ signedk y in
bitsx ≤? sy
⇒
let* sx ≔ signedk x in
let* sy ≔ signedk y in
bitsy <? sx
⇒
let* sx ≔ signedk x in
let* sy ≔ signedk y in
bitsy ≤? sx
Le | Lt | Ge | Gt | Ord | Unord
⇒
None

As shift_factor(K, Y, P): the power of two a shift by y at class k multiplies or divides by; the count is taken modulo the class width.

74Definition shift_factork : class y : Z : optionZ ≔
let* bits ≔ class_bitsk in
Some2 ^ y mod bits

As unsigned_division/4: the division or remainder f of x by y, where a zero divisor gives 0.

80Definition unsigned_divisionf : Z → Z → Z x y : Z : Z ≔
y =? 0
→
0
else
fx y

As signed_division/5: the division or remainder f of x by y read as signed at class k. A zero divisor gives 0, and the quotient truncates toward zero (Prolog's // and rem), then wraps, so the most negative value divided by -1 is itself.

87Definition signed_divisionf : Z → Z → Z k : class x y : Z : optionZ ≔
let* sx ≔ signedk x in
let* sy ≔ signedk y in
let* m ≔ modulusk in
Some
sy =? 0
→
0
else
fsx sy mod m

As alu(Op, K, Xs, Res): the integer op o of class k on the words xs, wrapping to the class's modulus; add and sub are integer here (additive_res adds to pointers). No word for arguments of the wrong form.

97Definition aluo : op k : class xs : listword : optionword ≔
match o, xs with
⇒
let* m ≔ modulusk in
SomeWIntx + y mod m
⇒
let* m ≔ modulusk in
SomeWIntx − y mod m
⇒
let* m ≔ modulusk in
SomeWIntx × y mod m
⇒
let* m ≔ modulusk in
SomeWInt−x mod m
Copy, x
⇒
Somex
⇒
SomeWIntZ.landx y
⇒
SomeWIntZ.lorx y
⇒
SomeWIntZ.lxorx y
⇒
⇒
SomeWIntunsigned_divisionZ.modulo x y
⇒
let* r ≔ signed_divisionZ.quot k x y in
SomeWIntr
⇒
let* r ≔ signed_divisionZ.rem k x y in
SomeWIntr
⇒
let* p ≔ shift_factork y in
let* m ≔ modulusk in
SomeWIntx × p mod m
⇒
let* p ≔ shift_factork y in
SomeWIntx / p
⇒
let* p ≔ shift_factork y in
let* sx ≔ signedk x in
let* m ≔ modulusk in
SomeWIntsx / p mod m
⇒
let* m ≔ modulusk in
SomeWIntextensiont x mod m
Cmpc ck, WIntx; WInty
⇒
let* b ≔ cond_bitc ck x y in
SomeWIntb
_, _
⇒
None

As additive_res(K, Op, Xs, Res): add or sub at class k. A pointer plus or minus an l offset keeps its capability, its address wrapping modulo 2^64; integer add and sub are alu's.

128Definition additive_resk : class o : op xs : listword : optionword ≔
match k, o, xs with
P, Add, WPtrp; WIntx
⇒
SomeWPtrmkPtrptr_addrp + x mod 2 ^ 64 ptr_capp
P, Sub, WPtrp; WIntx
⇒
SomeWPtrmkPtrptr_addrp − x mod 2 ^ 64 ptr_capp
W | L, _, _
⇒
aluo k xs
_, _, _
⇒
None

Checks

As checked_res(Res0, P, Res): a check's result from its access check r: the pointer p, now proven, or r's trap.

142Definition checked_resr : resunit p : word : resword ≔
match r with

As raw_res(Res0, Res): a raw access is the access its check covers, made again without trapping; what would have trapped is unchecked.

152Definition raw_resX : Type r : resX : resX ≔
match r with
_
⇒
r

As renew_res(Res0, P, Mem, Res): a renew's result from the access check r of the check it replaced, of the pointer p. It traps as that check would on a freed object or a write to a read-only one; any other failure means the earlier check's bounds did not cover this access: unchecked Span.

163Definition renew_resr : resunit p : ptr m : mem : optionresword ≔
match r with
⇒
⇒
match ptr_capp with
Objbase | Robase
⇒
let* reg ≔ object_regionbase m_regionsm in

As half_bound(Bound, B, Size, Base, End, Life): the one bound a half check tests natively, for size bytes at the address b of the object from base up to end_ of life l. The upper bound holds if the bytes end at or below end_; the lower if base is at or below b read as signed, and never for a freed object.

185Definition half_boundbd : bound b size base end_ : Z l : life : bool ≔
match bd with
⇒
b + size ≤? end_
⇒
match l with
⇒
false
⇒
base
≤?
2 ^ 63 ≤? b
→
b − 2 ^ 64
else
b

As half_passes(Bound, Mem, B, Size, Cap, Rights, Align, Passes): a half check's whole native test at the address b: the bound bd, the read-only flag for a write, and the alignment. Its inner none is for a capability that is not an object's, whose header no half check may read.

200Definition half_passesbd : bound m : mem b size : Z c : cap r : rights align : Z : optionoptionbool ≔
let test base ro ≔
let* reg ≔ object_regionbase m_regionsm in
SomeSomehalf_boundbd b size base r_endreg r_lifereg && negbrights_eqbr Write && ro && b mod align =? 0
in
match c with
Objbase
⇒
testbase false
Robase
⇒
testbase true
_
⇒
SomeNone

As half_res(Res0, Passes, P, Res): a half check's result from the full check's r and the native test. Where they agree it is theirs; where they disagree, the bound the validator took as known was false: unchecked Half.

217Definition half_resr : resunit passes : bool p : word : resword ≔
match r, passes with
RVal_, true
⇒
RTrapwhy, false
⇒

Loads

As extended_res(Res0, T, K, Res) of a loaded u: u extended from the narrow type t, as a word of class k.

228Definition extendedt : narrow k : class u : Z : optionword ≔
let* m ≔ modulusk in
SomeWIntextensiont u mod m

As load_op_res(T, K, filc, [ptr(A, Cap)], ...) for a non-pointer load type t: the access check of the address a through the capability c (read, alignment 1), then the bytes, extended for a narrow t.

235Definition int_load_rest : load_type k : class m : mem a : Z c : cap : optionresword ≔
let size ≔
match t with
⇒
8
⇒
4
⇒
10
in
let* chk ≔ access_resm a c size Read 1 in
match chk with
⇒
let u ≔ load_bytesm a size in
match t with
⇒
let* x ≔ extendedn k u in
SomeRValx
_
⇒
⇒
SomeRTrapwhy

One step e of a pointer load's protocol at the address a. The state st is the aux capability read so far and the pointer being assembled (interp.pl's loaded(C, P, Mem)); a store's step has none here.

257Definition pointer_load_effectm : mem a : Z st : cap × ptr e : effect : optioncap × ptr ≔
let c, p ≔ st in
match e with
⇒
let c′ ≔ aux_atm a in
Somec′, mkPtrptr_addrp c′
⇒
let c′ ≔ aux_atm a in
Somec′, mkPtrload_bytesm a 8 c′
_
⇒
None

As pointer_load_effects_res(ok, Effects, A, Mem0, val(P), Mem): the pointer the protocol es loads from the address a, run from loaded(none, ptr(0, none)).

272Definition pointer_load_effectsm : mem a : Z es : listeffect : optionptr ≔
let* st ≔
fold_left
λ st e  ⇒
let* s ≔ st in
es
in
Somesndst

As pointer_store_effect(A, P, Effect, Mem0, Mem): one step e of storing the pointer x at the address a. Ensure, barrier and reload are identities here (no garbage collector, no aux allocation); the writes happen in list order, the lower before the primary address.

282Definition pointer_store_effecta : Z x : ptr m : mem e : effect : optionmem ≔

The memory after a pointer store's protocol es, each step by pointer_store_effect in turn.

293Definition pointer_store_effectsa : Z x : ptr m : mem es : listeffect : optionmem ≔
fold_left
λ m e  ⇒
let* m′ ≔ m in
es
Somem

Stores

As store_res(filc, Width, Mem0, ptr(A, Cap), X, Res, Mem): a store of the word x at width w to the address a through the capability c. The access check (alignment 8 for a pointer and for x, else 1, width_word/5), then its bytes, and for a pointer its capability in aux; a failed check leaves memory as it was.

304Definition store_resw : width m : mem a : Z c : cap x : word : optionresunit × mem ≔
let size ≔ width_bytesw in
match w, x with
⇒
let* chk ≔ access_resm a c size Write 8 in
Some
chk
match chk with
Wb | Wh | Ww | Wl | Ws | Wd | Wx, WIntv
⇒
let align ≔
match w with
⇒
8
_
⇒
1
in
let* chk ≔ access_resm a c size Write align in
Some
chk
match chk with
⇒
store_bytesm a size v
_
⇒
m
_, _
⇒
None

Variadic arguments

The width a store of a value of class k writes, as width_bytes(K, Size) reads a class as a width; none for a proof class.

326Definition class_widthk : class : optionwidth ≔
match k with
⇒
SomeWw
⇒
SomeWl
⇒
SomeWp
⇒
SomeWs
⇒
SomeWd
⇒
SomeWx
_
⇒
None

As va_cell(K, Step, Align): a va_arg of class k takes Step bytes at an Align-aligned cursor, as Fil-C's runtime does: a long double's cell is 16 bytes at 16, of which it reads its 10.

336Definition va_cellk : class : optionZ × Z ≔
match k with
⇒
Some16, 16
_
⇒
let* w ≔ class_widthk in
Somewidth_bytesw, 8

As kind_res(va_arg, _, K, filc, [P], S0, Res, S): the next variadic argument, of class k, through the va_list p. The cursor is the pointer stored at p (pointer_load_res/5); its cell is checked for reading, the cursor moves past it with an l store at p, and the value is the cell's bytes, a pointer with its stored capability for p (va_cursor_res/6 and va_checked_res/8).

348Definition va_arg_resk : class p : ptr m : mem : optionresword × mem ≔
let* chk ≔ access_resm ptr_addrp ptr_capp 8 Read 8 in
match chk with
⇒
SomeRTrapwhy, m
⇒
None
⇒
let cursor ≔ mkPtrload_bytesm ptr_addrp 8 aux_atm ptr_addrp in
let* cell ≔ va_cellk in
let step, align ≔ cell in
let* w ≔ class_widthk in
let a ≔ ptr_addrcursor + align − 1 / align × align in
let* chk′ ≔ access_resm a ptr_capcursor step Read 8 in
match chk′ with
⇒
SomeRTrapwhy, m
⇒
None
⇒
let* stored ≔ store_resWl m ptr_addrp ptr_capp WInta + step in
let r, m1 ≔ stored in
match r, k with
RTrapwhy, _
⇒
SomeRTrapwhy, m1
⇒
None
⇒

Ops

What an op yields: a partial result and the memory after it, undefined behaviour (ub(Why), only an invalid float-to-integer conversion here), or a request for a fresh object and what follows from its base.

381Inductive op_out: Type ≔
|OpRes
r : resword m : mem
|OpUB
why : term
ub(Why)
|OpAlloc
q : alloc_req k : Z → word × mem
allocate q; k gives the result and the memory for its fresh base

Floats

The ieee.pl format of a float class k; none for the others.

389Definition fmt_ofk : class : optionfmt ≔
match k with
⇒
SomeFmtS
⇒
SomeFmtD
_
⇒
None

The ieee.pl condition of a comparison's condition c; none for the integer orders, which condition/2 never holds.

397Definition fcond_ofc : cond : optionfcond ≔
match c with
⇒
SomeFEq
⇒
SomeFNe
⇒
SomeFLe
⇒
SomeFLt
⇒
SomeFGe
⇒
SomeFGt
⇒
SomeFOrd
_
⇒
None

As op_res(cmp(C, CK), ...) at a float CK: 1 if the bit patterns a and b of format ck compare by c, else 0 (ieee_compare/5).

406Definition float_comparec : cond ck : fmt a b : Z : Z ≔
match fcond_ofc with
Somefc
⇒
ieee_compareck fc a b
None
⇒
0

As float_arithmetic(Op, K, Xs, R): add, sub, mul, div, neg and copy in the float format k, on bit patterns. A copy only checks that its word is an integer.

412Definition float_arithmetico : op k : fmt xs : listword : optionZ ≔
match o, xs with
⇒
Somex
⇒
Someieee_negk x
⇒
Someieee_binaryk FAdd x y
⇒
Someieee_binaryk FSub x y
⇒
Someieee_binaryk FMul x y
⇒
Someieee_binaryk FDiv x y
_, _
⇒
None

As kind_res(float_convert, Op, K, ...): the float x converted by the op o to class k, rounded to nearest: ext(s) to any float class, ext(d) to x, truncd to s, truncx to any float class, and sqrt, the square root at k (ieee_sqrt).

427Definition float_converto : op k : class x : Z : optionZ ≔
let* to ≔ fmt_ofk in
match o, k with

As float_integer(Op, K, X, Res): the float x of format from truncated toward zero, if it is finite and fits the class k signed or unsigned, else the undefined behaviour ub(float_conversion).

441Definition float_integerfrom : fmt sg : signedness k : class x : Z m0 : mem : optionop_out ≔
let* m ≔ modulusk in
let 'lo, hi ≔
match sg with
⇒
−m / 2, m / 2 − 1
⇒
0, m − 1
in
match ieee_to_intfrom x with
Somen
⇒
lo ≤? n && n ≤? hi
→
SomeOpResRValWIntn mod m m0
else
SomeOpUBTAtom"float_conversion"
None
⇒
SomeOpUBTAtom"float_conversion"

As integer_source(Op, X, N): the integer an int-to-float op reads from the word x of class ik, signed or unsigned.

456Definition integer_sourceik : class sg : signedness x : Z : optionZ ≔
match sg with
⇒
Somex

As kind_res/8 for the core subset's integer, pointer and checked ops: what the op o of result class k does on the words xs in the memory m, or none where the interpreter fails (arguments of the wrong form, a capability it cannot follow, or a setjmp, which kind_res/8 refuses since it does not return twice). The checks read memory and never change it; Alloc asks for an allocation.

465Definition op_res_into : op k : class xs : listword m : mem : optionop_out ≔
let pure x : optionword ≔
let* w ≔ x in
SomeOpResRValw m
in
let with_mem r : optionresword ≔
let* r′ ≔ r in
SomeOpResr′ m
in
match o, k, xs with
Allocalign, _, WIntsize
⇒
else
let q ≔ heap_reqalign size in
SomeOpAllocq λbase ⇒ WPtrmkPtrbase Objbase, allocatedm q base
Checklo hi r al, A, WPtrp
⇒
let* chk ≔ access_resm raw_addressptr_addrp lo ptr_capp hi − lo r al in
CheckAheadlo hi r al ahi, A, WPtrp
⇒
let b ≔ raw_addressptr_addrp lo in
let* need ≔ access_resm b ptr_capp ahi − lo r al in
match need with
⇒
SomeOpResRTrapwhy m
_
⇒
let* whole ≔ access_resm b ptr_capp hi − lo r al in
match whole with
⇒
_
⇒
Renewlo hi r al, A, q1; x
⇒
match q1, x with
⇒
→
let* chk ≔ access_resm raw_addressptr_addrp lo ptr_capp hi − lo r al in
with_memrenew_reschk p m
RenewHulllo hi r al, A, ql; qh; x
⇒
match ql, qh, x with
WPtrpl, WPtrph, WPtrp
⇒
→
let* chk ≔ access_resm raw_addressptr_addrp lo ptr_capp hi − lo r al in
with_memrenew_reschk p m
_, _, _
⇒
HalfCheckbd lo hi r al, A, q1; x
⇒
match q1, x with
⇒
→
let b ≔ raw_addressptr_addrp lo in
let* chk ≔ access_resm b ptr_capp hi − lo r al in
let* passes ≔ half_passesbd m b hi − lo ptr_capp r al in
match passes with
Someok′
⇒
SomeOpReshalf_reschk ok′ WPtrp m
None
⇒
SpanTestlo hi, W, WPtrp
⇒
let span base ≔
let* reg ≔ object_regionbase m_regionsm in
let l ≔ raw_addressptr_addrp lo in
let h ≔ raw_addressptr_addrp hi in
Some
base ≤? l && l <? h && h ≤? r_endreg
→
1
else
0
m
in
match ptr_capp with
Objbase | Robase
⇒
spanbase
_
⇒
RenewIflo hi r al, A, WPtrp; WIntg
⇒
let* chk ≔ access_resm raw_addressptr_addrp lo ptr_capp hi − lo r al in
g =? 0
→
else
match chk with
Limitsize, L, WPtrp
⇒
pureSomeWLimitptr_capp size
CheckLimitlo hi r al, A, WPtrp; u
⇒
match u with
WLimitc size
⇒
cap_eqbc ptr_capp && size =? hi − lo
→
let* chk ≔ access_resm raw_addressptr_addrp lo ptr_capp hi − lo r al in
RawLoadt off, _, WPtrp
⇒
let* r ≔ int_load_rest k m raw_addressptr_addrp off ptr_capp in
⇒
let b ≔ raw_addressptr_addrp off in
let* chk ≔ access_resm b ptr_capp 8 Read 8 in
match chk with
⇒
let* x ≔ pointer_load_effectsm b es in
⇒
Add | Sub, _, _
⇒
pureadditive_resk o xs
Mul | Div | Udiv | Rem | Urem | And | Or | Xor | Sar | Shr | Shl | Neg | Copy | Ptoi | Itop | Cmp_ _ | Ext_, _, _
⇒
purealuo k xs
_, _, _
⇒
None

As op_res(Op, K, filc, Args, S0, Res, S) and kind_res/8 for the core subset: what the op o of result class k does on the words xs in the memory m. A float comparison and float arithmetic come first, as op_res/7 commits to them before the integer dispatch of op_res_int.

570Definition op_reso : op k : class xs : listword m : mem : optionop_out ≔
match o, fmt_ofk, xs with
Cmpc ck, _, WInta; WIntb
⇒
match fmt_ofck with
Somef
⇒
None
⇒
op_res_into k xs m
Cmp_ ck, _, _
⇒
match fmt_ofck with
Some_
⇒
None
None
⇒
op_res_into k xs m
Add | Sub | Mul | Div | Neg | Copy, Somef, _
⇒
let* r ≔ float_arithmetico f xs in
ExtF_ | Truncd | Truncx | Sqrt, _, WIntx
⇒
let* r ≔ float_converto k x in
FloatToIntfk sg, _, WIntx
⇒
let* from ≔ fmt_offk in
float_integerfrom sg k x m
IntToFloatik sg, Somef, WIntx
⇒
let* n ≔ integer_sourceik sg x in
Cast, _, WIntx
⇒
VaArg, _, WPtrp
⇒
let* rm ≔ va_arg_resk p m in
SomeOpResfstrm sndrm
_, _, _
⇒
op_res_into k xs m