翻译 C 而不改变它的行为
选定源码中的每个 C 函数,都由人工逐语句改写成一个 Lean 函数。本页给出规则、四条采纳的规范化、翻译偏离 C 文本的其他几种形式,以及两个连同 C 一起列出的函数,让读者能够自己把翻译与源码对照。内核不对照 C 检查翻译。做这件事的是审查和差分测试;测试是忠实性的证据,不是证明。
架构定义这里用到的类型(M、Fault、cwhile、指针)。可信基础记录模型的限制。
规则
翻译按原有顺序保留 C 函数的语句。除了下面列出的四条采纳的规范化和另外六种形式,它不重排检查,不丢掉任何一次读或写,也不替换算法。证明难做不是改动翻译的理由。与 C 不一致就是翻译缺陷,要对照 C 改正它。定理的定义域也不会为了掩盖困难而收窄。C 的一个缺陷,只有在下面两种情形下才称为已确认的发现:真实的 C 在一个具体输入上的运行显示了它(sanitizer 的报告,或者一个违背 zlib.h 承诺的结果);或者它按 C 标准的字面是未定义行为,并且有一个补丁修正它。
采纳的规范化有四条。它们连同例子列在采纳的规范化里:
- 内部函数的输出参数按值传入,并作为第二个结果返回。
- 对同一位置的两次读取,中间没有写入,就算一次读取。
- 对同一个记录的字段的连续赋值,算一次记录更新。
- 如果同一函数中前面的检验已保证某个有符号运算不会越界,这个运算就用普通运算符书写。
翻译还使用另外六种形式:例如,刚写入的值不经读取就再次使用;一个操作数在 C 中受短路检验保护,翻译却在这个检验之前对它求值。四条采纳的规范化没有覆盖的形式说明翻译在每种形式下怎样做,连同文件和函数给出实例,并说明与 C 一致这一点依靠什么。
被翻译的源码
只翻译一种构建:默认的 x86_64 Linux、静态库、LP64。运行时参数绝不会选出另一个编译分支。预处理选择是对照固定版本的 zlib 源码加上按文件名顺序应用的本项目补丁来确定的。
| 源码族 | 选定的分支 |
|---|---|
| 压缩 | 启用 gzip;禁用 FASTEST、LIT_MEM、UNALIGNED_OK 和调试检查;默认的 MAX_WBITS 15 和 MAX_MEM_LEVEL 9 |
| 解码表和 inflate | 启用 gzip 和快速解码;禁用 BUILDFIXED、MAKEFIXED、PKZIP_BUG_WORKAROUND、INFLATE_STRICT 和无效距离恢复。固定表来自 inffixed.h |
| CRC | 静态表;braid 参数 N = 5 和 W = 8。运行的是小端分支;大端分支没有被走到 |
| Gzip 文件 | LP64 的大文件入口和 C99 格式化;不选 Windows、宽字符和 Z_SOLO 的路径。一次 I/O 请求至多 2^30 字节 |
每个翻译文件都在文件头注释里列出它的预处理选择。这些选择是针对这种构建对源码的解读。没有证明检查它们:这些解读尚未确认,须由源码审查确认,即对照预处理后的源码。
zlib/X.c 的翻译是文件 X.c.lean,zlib/X.h 的翻译是 X.h.lean。(deflate.c 拆成三个文件。)翻译文件里没有证明。每个函数保留它的 C 名字,文档字符串以 C 签名开头。每一块的 C 文本都引在翻译它的 Lean 行上方的注释里。
一个完整的例子:syncsearch
syncsearch 是 zlib/inflate.c 中 inflateSync 的辅助函数。它在缓冲区里搜索模式 00 00 FF FF。
local unsigned syncsearch(unsigned FAR *have, const unsigned char FAR *buf,
unsigned len) {
unsigned got;
unsigned next;
got = *have;
next = 0;
while (next < len && got < 4) {
if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
got++;
else if (buf[next])
got = 0;
else
got = 4 - got;
next++;
}
*have = got;
return next;
}
它的翻译:
/-- `local unsigned syncsearch(unsigned FAR *have, const unsigned char FAR *buf, unsigned len)`.
`have` is the value of `*have`; the result is (return value, `*have` afterwards). -/
def syncsearch (have_ : UInt32) (buf : BPtr) (len : UInt32) : M (UInt32 × UInt32) := do
-- got = *have; next = 0;
let (next, got) ← cwhile (σ := UInt32 × UInt32)
-- while (next < len && got < 4) {
(fun (next, got) => pure (next < len && got < 4, (next, got)))
(fun (next, got) => do
let b ← index8 buf next.toNat
-- if ((int)(buf[next]) == (got < 2 ? 0 : 0xff)) got++; else if (buf[next]) got = 0; else got = 4 - got;
let got := if b.toNat == (if got < 2 then 0 else 0xff) then got + 1 else if b != 0 then 0 else 4 - got
-- next++;
pure (next + 1, got))
(0, have_)
-- *have = got; return next;
return (next, got)
怎样读它:
| C | Lean | 要核对什么 |
|---|---|---|
函数返回 unsigned,并且可能有未定义行为 |
结果类型 M (UInt32 × UInt32) |
M α 就是 Heap → Except Fault (α × Heap):一个值和新堆,或者 Fault.ub,或者 Fault.outOfFuel。 |
unsigned *have |
参数 have_ : UInt32,以及结果的第二个分量 |
规范化 1。调用者在调用前读出这个单元,在调用后把第二个结果写回去;见下文。 |
局部变量 got、next |
循环状态 (next, got) : UInt32 × UInt32 |
循环会改动的局部变量作为循环状态携带。unsigned 是 UInt32。起始状态 (0, have_) 就是 next = 0; got = *have。 |
while (c) body |
cwhile cond body start |
cwhile 检验条件、运行循环体,如此重复,至多检验 2^64 次;之后是 Fault.outOfFuel。这个循环运行不到 2^32 次,因为 next 一直增加到 len。 |
next < len && got < 4 |
next < len && got < 4 |
两个操作数都只读局部变量,所以短路求值的顺序观察不到。 |
buf[next] |
index8 buf next.toNat |
index8 p i 是指针算术再加一次读取。buf 为 NULL、它的数组已被释放、下标在数组之外时,它都发生故障。C 里的一次越界读取在这里就是 Fault.ub。 |
else if 里再读一次的 buf[next] |
同一个 b |
规范化 2。两次读取之间没有写入。 |
(int)(buf[next]) == (got < 2 ? 0 : 0xff) |
b.toNat == (if got < 2 then 0 else 0xff) |
提升为 int 的字节落在 0..255 内;把两个值当作自然数来比较,结果相同。 |
got++、4 - got、next++ |
UInt32 上的 got + 1、4 - got、next + 1 |
无符号算术在 C 里和在 UInt32 里都回绕。这里不需要检查。 |
*have = got; return next; |
return (next, got) |
见输出参数那一行。 |
inflateSync 中的调用处显示了输出参数的另一半:
len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
let (len, hv) ← syncsearch (← rdS st (·.«have»)) z.next_in z.avail_in
wrS st fun s => { s with «have» := hv }
rdS st f 读状态记录 *st 的一个字段,wrS st f 把这个记录换成 f 作用于它的结果。C 在被调用函数内部写 state->have;Lean 在被调用函数刚返回之后写它。这中间没有任何东西读这个字段。被调用函数内部的故障在两边都结束这次运行。
第二个例子:有符号算术与记录字段
zlib/inflate.c 中 inflateReset2 函数体的开头,位于 int wrap; 和 struct inflate_state FAR *state; 这两个声明之后。这种构建定义了 GUNZIP,所以 #ifdef GUNZIP 和 #endif 之间的几行会被编译:
/* get the state */
if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
state = (struct inflate_state FAR *)strm->state;
/* extract wrap request from windowBits parameter */
if (windowBits < 0) {
if (windowBits < -15)
return Z_STREAM_ERROR;
wrap = 0;
windowBits = -windowBits;
}
else {
wrap = (windowBits >> 4) + 5;
#ifdef GUNZIP
if (windowBits < 48)
windowBits &= 15;
#endif
}
/* set number of window bits, free window if different */
if (windowBits && (windowBits < 8 || windowBits > 15))
return Z_STREAM_ERROR;
if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {
ZFREE(strm, state->window);
state->window = Z_NULL;
}
它的翻译:
-- if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
if (← inflateStateCheck strm) != 0 then return Z_STREAM_ERROR
let z ← ldZStream strm
let state ← castInflateState z.state
let mut windowBits := windowBits
let mut wrap : Int32 := 0
-- if (windowBits < 0) { if (windowBits < -15) return Z_STREAM_ERROR; wrap = 0; windowBits = -windowBits; }
if windowBits < 0 then
if windowBits < -15 then return Z_STREAM_ERROR
wrap := 0
windowBits ← chkI32 (-(windowBits.toInt))
else
-- wrap = (windowBits >> 4) + 5;
wrap ← chkI32 ((windowBits >>> 4).toInt + 5)
-- if (windowBits < 48) windowBits &= 15;
if windowBits < 48 then windowBits := windowBits &&& 15
-- if (windowBits && (windowBits < 8 || windowBits > 15)) return Z_STREAM_ERROR;
if windowBits != 0 && (windowBits < 8 || windowBits > 15) then return Z_STREAM_ERROR
-- if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) { ZFREE; window = Z_NULL; }
let s ← ldInflateState state
if s.window != .null && s.wbits != i2u windowBits then
ZFREEB strm s.window
wrS state fun s => { s with window := .null }
| C | Lean | 要核对什么 |
|---|---|---|
int windowBits、int wrap |
Int32 |
int 是 Int32。let mut 是会被再次赋值的局部变量。 |
strm->state |
ldZStream strm,然后取字段 z.state |
对 z_stream * 而言,ldZStream p 就是 *p。p 为 NULL 或它的记录已被释放时,它发生故障。 |
(struct inflate_state *)strm->state |
castInflateState z.state |
流的状态指针可能指向 inflate 状态,也可能指向 deflate 状态。它指向 deflate 状态时这个转换发生故障:C 会通过错误的类型去读。 |
-windowBits |
chkI32 (-(windowBits.toInt)) |
取负是在无界整数上计算的。结果放得下时 chkI32 返回这个 Int32,放不下时返回 Fault.ub "signed integer overflow"。 |
(windowBits >> 4) + 5 |
chkI32 ((windowBits >>> 4).toInt + 5) |
对加法作同样的检查。在这个分支里 windowBits 不为负,所以移位不涉及符号问题。 |
windowBits &= 15,各处比较 |
Int32 上的 &&&、<、> |
这些运算不会溢出。 |
state->window、state->wbits |
ldInflateState state,然后取 s 的字段 |
对记录的一次读取供两次字段读取使用(规范化 2)。 |
(unsigned)windowBits |
i2u windowBits |
int 到 unsigned 的转换在 C 里有定义:对 2^32 取模。 |
ZFREE(strm, state->window) |
ZFREEB strm s.window |
这个宏调用 strm->zfree。只对默认分配器建模:该字段是 zcfree 时 ZFREEB 释放这个块,是任何其他函数指针时为 Fault.ub。释放一个不存活的块会发生故障。 |
state->window = Z_NULL |
wrS state fun s => { s with window := .null } |
一次字段写入是:读取记录、更新记录、写回记录。 |
C 里提前的 return 就是 Lean 的 do 块里的 return:块中余下的部分不运行。
采纳的规范化
1. 内部函数的输出参数按值传入,并作为第二个结果返回。 模型里没有指向记录的标量字段或指向标量局部变量的指针。例子是上面的 syncsearch:unsigned *have 成了参数 have_ 和第二个结果,由调用者写回。其他用到的地方:inflate_table(table、bits)、gz_load(have),以及 inflateBack 输入回调的 &next。
一些公开函数的标量输出参数也用同样的表示:compress* 的 destLen,inflateGetDictionary 和 deflateGetDictionary 的 dictLength,deflatePending 的 pending 和 bits,以及 deflateUsed 的 bits。规范化 1 只针对内部函数;对这些公开函数,这种表示是模型的一个限制:调用者的单元不是内存,所以一个与某个缓冲区重叠的单元无法表达,这些函数的安全目标对这个单元的内存也什么都没说。偏离记录里有“结果单元”和“整缓冲区压缩”两行。uncompress* 的长度单元和 gzerror 的 errnum 单元是内存:前者是八字节的块,后者是一个四字节的块。
2. 对同一位置的两次读取,中间没有写入,就算一次读取。 在 syncsearch 里:
if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
got++;
else if (buf[next])
let b ← index8 buf next.toNat
let got := if b.toNat == (if got < 2 then 0 else 0xff) then got + 1 else if b != 0 then 0 else 4 - got
C 的两次读取给出同一个字节,并在相同的情形下发生故障,因为两者之间没有任何写入。
3. 对同一个记录的字段的连续赋值,算一次记录更新。 在 inflateSync 里:
state->mode = SYNC;
state->hold >>= state->bits & 7;
state->bits -= state->bits & 7;
let h ← shr64 s.hold (s.bits &&& 7)
wrS st fun s => { s with mode := SYNC, hold := h, bits := s.bits - (s.bits &&& 7) }
三条语句写三个不同的字段,每条的右边只读它之前的语句没有写过的字段。所以各个值与 C 中相同。shr64 是带检查的移位;这里它的计数至多为 7,所以它不发生故障,它排在更新之前这一点也观察不到。
4. 如果同一函数中前面的检验已保证某个有符号运算不会越界,这个运算就用普通运算符书写。 在 zError 里(zutil.c,经由 zutil.h 的宏 ERR_MSG):
#define ERR_MSG(err) z_errmsg[(err) < -6 || (err) > 2 ? 9 : 2 - (err)]
let i : Int32 := if err < -6 || err > 2 then 9 else 2 - err
Lean 的 Int32 减法回绕;C 的减法在溢出时未定义。这个减法只在 -6 ≤ err ≤ 2 时执行,所以结果在 0..8 内,两者一致。另一处是 adler32_combine_ 中 Int64 上的 %,在检验 len2 < 0 之后。
没有这种检验的有符号运算使用带检查的辅助定义(第二个例子里的 chkI32)。这些辅助定义列在架构里。
四条采纳的规范化没有覆盖的形式
翻译使用下面六种形式。按四条采纳的规范化的措辞,没有一条覆盖它们。Lean 在这些地方与 C 一致,这一点是被信任的,不是已证明的:它依靠对每一处的解读,没有定理陈述它(可信基础,第 3 项)。下面各表是例子,不是完整的清单:可能还有别的实例和别的形式。
1. 刚写入的值被直接再用,而不是读回来。
| 文件,函数 | C | Lean |
|---|---|---|
inflate.c.lean,inflateSync |
state->have = 0; syncsearch(&(state->have), buf, len); |
字段被置为 0,调用写成 syncsearch 0 buf len:被调用函数拿到的是字面量,不是读回来的字段。这个函数里的第二次调用确实读了字段。 |
inflate.c.lean,inflate_CODELENS 和 inflate_LENLENS;infback.c.lean,back_TABLE(两处) |
state->next = state->codes; state->lencode = (const code FAR *)(state->next); |
一次更新,其中 next := codesP c.st, lencode := codesP c.st。inflate_LENLENS 对 state->lencode = state->distcode = (const code FAR *)(state->next) 也这样设置 distcode。 |
deflate_strategies.c.lean,deflate_stored |
s->strstart = s->w_size; s->insert = s->strstart; |
一次更新,其中 strstart := d.w_size, insert := d.w_size。 |
deflate_strategies.c.lean,deflate_stored(两处窗口滑动) |
s->strstart -= s->w_size; zmemcpy(s->window, s->window + s->w_size, s->strstart);,以及后面的 if (s->insert > s->strstart) s->insert = s->strstart; |
新值是局部变量 ss。复制的长度和对 insert 的检验用的都是 ss;字段在这之后才写入(形式 6)。 |
inflate.c.lean,updatewindow |
state->wnext += dist; if (state->wnext == state->wsize) state->wnext = 0; if (state->whave < state->wsize) state->whave += dist; |
和是局部变量 wnext,它与 wsize 比较,相等时置为 0。然后用一次更新写入 wnext 和 whave:其间字段没有被写入再读回。 |
deflate_base.c.lean,flush_pending |
s->pending -= len; if (s->pending == 0) |
差是局部变量 pend。它被写入字段,而检验用的是 pend,不是字段。 |
第二行和第三行与规范化 3 不同:有一个右边读的是同组中在前的语句写过的字段。
2. 一个操作数在 C 中受短路检验保护,在 Lean 中却先于这个检验求值。 C 只在左操作数不能决定结果时才对 && 和 || 的右操作数求值。在 Lean 的 do 块里,条件中的内嵌动作 (← e) 在条件求值之前运行;条件上方用 let 读取的记录,则在任何情形下都会被读取。
| 文件,函数 | 什么提前运行 |
|---|---|
inflate.c.lean,inflateSync |
ldInflateState st 在 z.avail_in == 0 && s.bits < 8 之前运行。C 只在 strm->avail_in == 0 时才读 state->bits。 |
inflate.c.lean,inflatePrime |
状态在检验左操作数 bits > 16 之前被读取。C 只在这个操作数为假时才读 state->bits。 |
inflate.c.lean,inflateValidate |
状态在 check != 0 && s.wrap != 0 之前被读取,对 reqwrap 的同样检验也是如此。 |
deflate.c.lean,deflate |
状态在以操作数 strm->next_out == Z_NULL 开头的检验之前被读取。RANK flush 和 RANK old_flush 是带检查的有符号算术,它们在 z.avail_in == 0 && 之前运行。流在 s->status == FINISH_STATE && 之前被读取。 |
deflate.c.lean,deflateParams |
带检查的和 (s->strstart - s->block_start) + s->lookahead 在检验左操作数 strm->avail_in 之前算出。C 只在 strm->avail_in 为 0 时才计算它。 |
deflate_strategies.c.lean,deflate_stored |
状态和 s->strm->avail_in 在 flush != Z_NO_FLUSH && flush != Z_FINISH && 之前被读取。s->strm->avail_in 在检验左操作数 left >= min_block 之前被读取。 |
deflate_strategies.c.lean,deflate_fast_body、deflate_slow_body |
状态在 hash_head != NIL && 之前被读取。 |
trees.c.lean,detect_data_type |
s->dyn_ltree[n].Freq 在 (block_mask & 1) && 之前被读取。 |
gzread.c.lean,gz_look |
gz 状态在检验左操作数 strm->avail_in == 0 之前被读取。流在 state->junk == 0 && 之前被读取。 |
gzread.c.lean,gz_skip、gz_read |
流在 state->eof && 之前被读取。在 gz_read 里,gz 状态在 n == 0 && 之前和 len && 之前被读取。 |
除三行之外,每一行里提前的操作都不写入任何东西,它要么是读取同一函数已经读取过的记录(直接读取,或经由它调用的状态检查读取),要么是读取内嵌在函数已读取过的 gz 状态里的流。另外三行在模型里可能在某个状态上发生故障,而 C 在这个状态上并不对该操作数求值:带检查算术的两行(deflate、deflateParams),以及 detect_data_type 的数组读取。在 deflate 里,只有 RANK old_flush 可能发生故障:flush 已经通过函数开头的范围检验,而 old_flush 是存下来的字段 last_flush。安全定理表明翻译在它们的定义域内不发生故障,所以这个差别落在定义域之外。
右操作数是一次调用,或者是通过左操作数所检验的指针进行的读取时,翻译用嵌套的 if 保持 C 的顺序。例子:inflateBack 中的 strm == Z_NULL || strm->state == Z_NULL,以及 gzvprintf 中的 state->skip && gz_zero(state) == -1。
3. 字段的值取自一次写入之前读取的记录。 规范化 2 覆盖的是中间没有写入的两次读取。这里在读取记录与使用字段之间有一次写入;它写的是另一个字段或另一个记录。
| 文件,函数 | 被再用的是什么 |
|---|---|
deflate.c.lean,deflate |
状态 d 和流 z 在 s->last_flush = flush 之前被读取。d.pending 和 z.avail_in 在这次写入之后使用。 |
deflate_strategies.c.lean,deflate_stored |
s->strm 在开头只读一次(let strm := d.strm),此后每一处 s->strm 都用它,中间隔着对 *s 其他字段的写入。 |
inflate.c.lean,inflate_leave |
流 z 在 RESTORE() 之后被读取。z.avail_in、z.avail_out 和 z.next_out 在调用 updatewindow 之后、在写入 total_in 和 total_out 之后使用。 |
4. 按常数计数的移位用普通运算符书写。 计数是变量的移位经过带检查的辅助定义(shl32、shr32、shl64、shr64、ishl、ushl、shl1、shl1i32、shlUs、shrUs)。计数是小于操作数位宽的字面量的移位,写成 >>> 或 <<<:例如 inflateSync 中对应 state->hold >>= 8 的 s.hold >>> 8,以及 adler32_z 中的 adler >>> 16。对无符号操作数,两种语言在这样的移位上结果一致。含有普通移位的函数,按文件列出:
| 文件 | 函数 |
|---|---|
adler32.c.lean |
adler32_z、adler32_combine_ |
compress.c.lean |
compressBound_z |
crc32.c.lean |
byte_swap、crc_word、crc_word_big、multmodp、x2nmodp、braidTab、braidBigTab、crcByte,以及辅助定义 loadWord |
deflate.c.lean |
deflatePrime、deflate、deflateBound_z |
deflate_base.c.lean |
d_code、tally_dist、putShortMSB |
deflate_strategies.c.lean |
longest_match、deflate_stored |
gzguts.h.lean |
辅助定义 load32、store32、load64、store64 |
gzlib.c.lean |
gzbuffer |
gzread.c.lean |
gz_load、gz_look、gz_fetch、gz_read、gzungetc |
gzwrite.c.lean |
gz_init、gz_comp |
infback.c.lean |
back_STORED |
inffast.c.lean |
inflate_fast |
inflate.c.lean |
inflateReset2、inflatePrime、ZSWAP32、CRC2、CRC4、inflate_STORED、inflate_HCRC、inflate_OS、inflate_FLAGS、inflate_HEAD、inflateSync、inflateMark |
inftrees.c.lean |
buildStep |
trees.c.lean |
put_short、d_code、bi_reverse、bi_flush、gen_codes、_tr_stored_block、_tr_align、compress_block、detect_data_type、_tr_flush_block、_tr_tally |
zutil.c.lean |
zlibCompileFlags |
这些普通移位中,有一些不是“无符号操作数加字面量计数”:
- 操作数有符号,计数是字面量:
inflateReset2中的windowBits >>> 4,deflatePrime中的(s->bi_valid + bits) >> 3,x2nmodp中作用于z_off64_t的n >>= 1,braidTab和braidBigTab中的k <<< 3,inflateMark中的-(1L << 16),inflate_HCRC中的(state->flags >> 9) & 1(flags是int),以及trees.c.lean中的常量STORED_BLOCK << 1、STATIC_TREES << 1和DYN_TREES << 1。对负值右移在 C 里是实现定义的,不是未定义的;这种构建的编译器与 Lean 的Int32、Int64都作算术右移。 - 计数是变量:
deflatePrime中的value >>> put(操作数有符号;put已通过同一轮循环里带检查的ishl 1 put),以及inflatePrime中的(1 : Int64) <<< bits.toInt64(它之前的检验保证1 ≤ bits ≤ 16,所以这一处属于规范化 4)。 - 辅助定义
loadWord、load64和store64的移位计数是 8 乘以一个小于 8 的循环下标。
5. inflate 中 C 没有初始化的局部变量从固定的值开始。 inflate.c.lean 中的 IL.init 给局部变量 copy、len、from、here 和 last 的值是 0、NULL 和一个全零的 code。inflateBack 使用同一个记录。对未初始化整数的规则是:它的值任意,定理必须对每个值都成立。inflate.c.lean 的文件头注释记录了这个选择。inflate 是否可能在给这些局部变量赋值之前读它们,这一解读尚未确认,须由源码审查确认:模型把这些值固定了,所以对当前翻译的证明显示不了这一点。
6. 一次写入在 C 中位于某次调用之前,翻译却把它写在这次调用之后。 C 先写入一个字段,再调用 zmemcpy。Lean 先做复制,再在其后的一次记录更新里写这个字段。
| 文件,函数 | C | Lean |
|---|---|---|
deflate_strategies.c.lean,deflate_stored |
s->matches = 2; zmemcpy(s->window, s->strm->next_in - s->w_size, s->w_size); |
memcpyB 先运行。matches := 2 在其后的那次更新里,与 strstart 和 insert 一起写入。 |
deflate_strategies.c.lean,deflate_stored(两处窗口滑动) |
s->strstart -= s->w_size; zmemcpy(s->window, s->window + s->w_size, s->strstart); 第二处滑动在这之前还有 s->block_start -= s->w_size;。 |
新值是局部变量 ss 和 bs。memcpyB 运行之后,一次更新把 strstart(以及 block_start)连同 matches 和 insert 一起写入。 |
在这几处,复制读写的是窗口和输入中的字节,被移后的写入写的是状态记录的字段。
还有一种相近的重新分组,其中没有调用。在 flush_pending(deflate_base.c.lean)里,C 对两个记录的写入是交错的:strm->next_out += len; s->pending_out += len; strm->total_out += len; strm->avail_out -= len; s->pending -= len;。Lean 先算出两个新指针,用一次更新写流的三个字段,再用另一次更新写状态的两个字段。规范化 3 说的是对同一个记录的连续赋值。
整数类型与算术
宏按源码顺序展开。读、写、分支条件和提前返回都保留。右操作数是一次调用,或者是通过左操作数所检验的指针进行的读取时,短路求值保留;操作数被提前求值的地方,见上面清单的形式 2。整数提升和通常的算术转换都明确写出:在这个目标上,unsigned short + int 按 int 计算。
| C 类型 | LP64 上的 Lean 类型 |
|---|---|
unsigned char |
UInt8 |
unsigned short |
UInt16 |
unsigned、unsigned int |
UInt32 |
unsigned long、size_t、z_size_t |
UInt64 |
int |
Int32 |
long、z_off_t、z_off64_t |
Int64 |
无符号运算按各自的位宽回绕。有符号运算要检查结果是否可表示,规范化 4 的情形除外。计数是变量的移位经过带检查的辅助定义。用于无符号操作数的辅助定义在计数不小于操作数位宽时发生故障。用于 int 操作数的辅助定义在计数为负时也发生故障,其中的左移在操作数为负或结果放不下时同样发生故障。计数是小于操作数位宽的字面量的移位用普通运算符书写;上面清单的形式 4 指出这些地方和例外。Lean 的算术是全函数;单凭这一点绝不能说明某个 C 运算是正当的。
一个枚举常量有两个名字:一个 UInt32 名字用于无符号的状态字段,一个带后缀 _i 的 Int32 名字用于 C 类型为 int 的用法。与枚举常量重名的宏命名为 GZ_<name>:GZ_COPY 是 gzguts.h 的宏,COPY 是 inflate.h 的枚举常量。
每种 C 对象怎样表示
| C 对象或操作 | 表示 |
|---|---|
| 结构体 | 它那一种的堆表中的一个记录,按块编号引用 |
p->f 和 p->f = v |
记录字段的读取和记录更新,没有 ABI 偏移算术 |
| 内嵌数组 | 一个数组字段;复制记录就复制了它 |
| 指向内嵌数组内部的指针 | 一个指明记录、字段和下标的引用 |
| 字节缓冲区 | 一个堆字节块加一个偏移 |
head 和 prev 字数组 |
一个堆字块加一个元素偏移 |
| 静态表 | 一个静态引用或一张带检查的常量表;写入会发生故障 |
| 被取地址的局部变量 | 一个表示出来的对象,在声明处建立,在每个返回之前释放 |
| 字符串字面量 | 指向源码字面量的封闭只读表的 strLitRef;不作分配 |
ZALLOC 和 ZFREE |
带失败预言的默认分配器;自定义分配器是 Fault.ub |
记录类型根据 C 头文件生成(运行时结构定义)。生成的数组字段在类型里不带它声明的长度;这个事实由证明携带。
局部对象不消耗分配失败预言的一次调用:给它 ZALLOC 的语义,会改变哪一次真实的分配失败。被取地址的局部变量在它的 C 生命周期结束之后不再存活。
新分配的内存
新分配的整数内容是任意的。定理对每个值都成立,包括在 prev 的已初始化部分之外、或在匹配预读的已初始化部分之外读到或复制的值。翻译不把这些内容换成零。
新分配的指针字段在这个模型里是 NULL。这比 C 弱,在 C 里它是不确定的。与 NULL 的比较、复制和 free(NULL) 都发现不了没写过的字段,所以指针字段漏写一次,在模型里看不出来。C 对新分配记录的每个指针字段都是先写后读,这一点尚未确认,须由源码审查确认:没有定理陈述它,在这个模型里也不可能有。证明表明的要窄一些:每种状态的不变量(InflateInv、DInv、GzInv)在每个可达的流上、在每个有历史的 gz 句柄上成立,而不变量说明了它提到的那些指针字段里是什么(可信基础)。
证明不假设对未初始化单元的重复读取结果一致,尽管模型给这个单元一个稳定的值。
对结构定义中的记录类型 K,K.zeroed 是 C 中一条真实的整记录清零语句之后的记录,K.garbage 是一个新分配的记录。两者不能互换。见安全性,模型的限制。
库操作
下面的 K 代表一种记录,如 stZStream 和 copyInflateState 中那样。
| C 操作 | 翻译 |
|---|---|
字节的 memcpy、zmemcpy |
memcpyB,带范围检查和不重叠检查 |
整记录的 memcpy |
copyK dst src;它检查重叠,这与先读取再写入不同 |
memmove |
移动操作,它允许重叠 |
字节的 memset |
memsetB |
| 把更宽的数组清零 | Ptr.fill p 0 n,带元素个数 |
用字节 c 填充更宽的数组 |
Ptr.memset p c n,它在每个元素里重复 c |
| 整记录清零 | stK p K.zeroed |
memcpy 既复制已初始化的值,也复制任意值。即使复制长度为零,运行时遇到 NULL 也发生故障。建模的操作按元素计数,所以 C 的字节数要换算。可信基础列出它们与 C 的差别。
控制流
循环用运行时的循环构造来表示,它的局部变量放在显式的状态里传递。do … while 先运行循环体,再检验条件。循环内的 break、continue 和 return 用控制标签表示,标签区分这三者各自的去向。goto 有两种建模方式:用一个异常(inflate 中的 goto inf_leave),或者用一个让某个块再运行一遍的标志(inflate_fast 中的 goto dolen)。switch 的贯穿(fall-through)写成对下一个分支的尾调用。inflate.c.lean 和 inffast.c.lean 的文件头注释描述了各自的方案。
循环的上界不是提前停下的许可。耗尽是 Fault.outOfFuel,终止证明把它排除。C 能到达的每一种未定义操作,在已记录的模型差别之内,都作为 Fault.ub 保持可见:指针边界、存活性、对只读对象的写入、无效的比较、有符号算术和重叠的复制。