API 模型:各族详解
本页接着 API 模型往下讲。这里的全部内容都是功能性材料:它不是安全结论所必需的,也没有安全目标使用这些模型,只是 compressBound 和 compressBound_z 的目标提到了模型的上界公式。本页逐族说明这些不涉及堆的关系说了什么,以及它们在哪些地方没有覆盖到 C 的实际行为。本页中带“必须”的句子,说的是一个功能目标的细化证明要证明什么;它不表示这个证明已经存在。关于模型关系的定理是关于模型的命题,不是关于翻译后的 C 的命题。哪些功能目标已完成,见进度。
状态、调用与历史
InflState 记录重置以来已消费的输入和已交付的输出(seen、out)。DeflState 记录已接受的输入和已产生的输出(input、produced)。一步是 InflStep st call result st' 这样的关系,不是实现函数。公开接口允许每次调用有不同的进展量,也允许压缩器对数据块作不同的划分和选型。关系约束这些选择,但不选定算法。
轨迹中的每一步都可以把未消费的输入再交给下一次调用,并改变可用的输出空间和刷新值。因此,在 InflTrace 和 DeflTrace 所表示的操作族之内,它们支持跨任意分块边界的结论。模型的总数是自然数;LP64 上具体的 uLong 总数必须按模 2^64 与之联系。
调用记录用 badBuf 表示为 NULL 的输出缓冲区,或者输入长度非零时为 NULL 的输入缓冲区。它没有实际的 NULL 指针,也没有重叠的内存。这些形状和别名属于具体边界。
数据方面的结论依赖状态的精确性标志。位预置、恢复和关闭校验和验证,都可能使普通的字节格式解释不再适用。InflState.Exact 同时要求精确性和验证。较弱的数据解释绝不取消具体的安全、终止或逐次调用精确效果的要求。
核心历史模型省略 msg 和 data_type。它把 adler 建模为已交付的 inflate 输出或已接受的 deflate 输入所适用的校验和。deflateUsed、inflateCodesUsed、zlibCompileFlags 等数值查询以及校验和组合入口在这里没有完整的契约;它们的具体目标另行给出。
Inflate:输出需要因果证据
Layer.Decodes wrap wbits dict stream output 选择独立的裸、zlib、gzip 或自动识别的封装关系。对裸数据,它使用字典的有效后缀。对 zlib,它还对照配置的窗口检查头部窗口;零表示采用头部的窗口。
| 关系 | 含义 |
|---|---|
Layer.Viable |
字节前缀有完整且有效的后续,另允许头部较短的情形 |
Layer.Consistent |
已消费字节的某个补全具有所提议的输出前缀 |
Layer.Determined |
与已消费的字节历史兼容的每个完整流都扩展该输出 |
Layer.OutputEvidence |
某个支持位前缀有有效的补全,并且在每个允许的字典之下,每个兼容的补全都扩展该输出 |
Layer.Detectable |
按配置的检测滞后,某个更早的字节前缀已不可延续 |
只有存在性的一致,就允许凭一个有利但尚未读取的后续去猜输出。全称的确定性排除这种情况。在已拉入的预读内容含有尚未检查的错误时,支持位证据还防止命题空真。InflState.Consistent 使用 Layer.OutputEvidence;InflState.Determined 另外对每个允许的字典量化。两者都出现在普通关系和后期内存错误关系中。
未知的预置字典不是空字典。在带封装的流请求字典之前,合法的后续仍可以提供它。对于精确的、完整窗口的流,数据错误必须对状态仍允许的每个字典都有依据。字典一旦提供,就固定下来。
FullWindow 标记这样的配置:每个格式上有效的距离都得到支持。普通的往返目标使用 15 位的 inflate 窗口。较小的配置窗口可能拒绝一个本来有效的流,这取决于调用怎样分块:一个距离可以够到本次调用输出中的字节,而这些字节在较小的保存窗口中已经不可用。完整窗口条件限定的是抽象的拒绝和完成结论;它不是公开的安全限制。
常数 detectLag = 8 不描述实际的 inflate。一个动态表前缀可能在第 230 字节就已不可能成立,而一次调用消费了 281 字节并返回 Z_OK。所以 Goal.inflate_rejects_invalid 陈述的是模型的一个性质,不是这个实现何时报错。
InflRunOk 描述游标的进展、总数、返回码、停止、格式子句、校验和,以及所请求的头字段。InflRunMem 描述调用退出时历史窗口分配失败。这种失败可以发生在读取输入和写出非空输出之后,而 total_in、total_out 和 adler 保留旧值。之后进入内存错误阶段。模型的活性结论允许用这种结果代替正常完成。这与尚未写出输出的早期分配失败是两回事。
负的 inflatePrime 值贡献它的低位:模型取模 2^bits 的非负余数。InflMark 只描述新建状态的情形。InflSyncPoint 和输入之后的位预置只有部分的抽象描述。InflGetDict 描述窗口固定的、运行中的流。InflBack 把它的两个回调表示为调用编号的纯函数;这个关系不表示回调对堆的任意效果。
Deflate:字节有效性与调用历史
DeflState.Valid 把完成的输出与全部已接受的输入以及选定的封装联系起来。DeflState.FlushedAt 描述一次完成的 Z_SYNC_FLUSH 或 Z_FULL_FLUSH 处的输出。DeflRun 还记录待输出字节、缓冲的位、校验和更新和返回码条件。
历史标志 started 在重置之前是单调的,被拒绝的调用也算在内。如果在拒绝时把它清掉,就会允许在封装头已经写出之后更换字典。模型的 done 标志变为真,恰好是在它已经为真,或者某次调用返回 Z_STREAM_END 的时候。缓冲区错误不结束流。当调用返回 Z_OK 且还有剩余空间时,模型记录一次完成的 Z_FULL_FLUSH,并保留对应的输入/输出切分,供裸流重新同步性质使用。
DeflState.bound 给出数值的 deflateBound 公式。输出是否够用是另一个子句,由模型的 clean 标志及其精确的转换规则把守。参数变更、位预置、调优、字典变更和刷新都要把各自的效果计算在内;单有一个数值公式证明不了任何输出上界。compressBound 是饱和的默认公式,而抽象的 deflateBound 公式没有溢出钳制。
字典模型不描述每一种操作上的用法。裸流的 InflSetDict 限于输入之前的情形,尽管 C 允许之后修改窗口。DeflSetDict 描述文档规定的压缩前顺序,并拒绝 C 在流结束后接受的一些调用。这些限制记录在偏离记录中。一个字节格式阶段只有一个初始字典,它无法表示之后任意的字典替换。
单次调用的工具函数:字节与标量单元不同
Compress2 是只讲数据的关系。CompressCall 和 CompressResult 加上指针形状、容量和单独存放的长度;Compress2Z 保持 _z 入口的检查顺序:
- 拒绝长度非零而源为 NULL、长度单元为 NULL,或容量为正而目的缓冲区为 NULL 的调用。长度单元不为 NULL 时保持原值。
- 在初始化之前把存放的长度清零。无效的级别在分配器可能失败之前被拒绝。
- 容量为零且目的缓冲区为 NULL 的调用通过这些检查。初始化可能返回内存错误;否则内层的压缩器拒绝这个为 NULL 的目的缓冲区。
- 对可接受的形状,数据关系给出写出的字节和存放的长度。
兼容用的包装函数在这些检查之前读取长度单元。长度单元为 NULL 时发生故障;这不是 _z 入口那种不产生故障的参数拒绝。这些适配器中没有标量单元与输入/输出之间的别名。带计数的解压适配器也让它们的标量单元保持分离。Uncompress2 同时记录写出的输出和消费的输入,并区分输入被截断与输出空间不足。早期和后期的分配失败必须保留各自不同的标量效果。
Concrete.execute 在 C.Heap 上运行实际的翻译后计算,保留每个返回的堆,并暴露故障。它不是一个可以替换的关系。Concrete.Correct 要求对每个允许的初始堆都有一次实际的成功运行,之后满足写明的后置条件。前置条件仍然必须是可达的;函数级的不变量由初始化函数建立,顶层结论需要一个具体的、被允许的见证。
有两个具体目标明确写出了有用的区分:
| 目标 | 范围 |
|---|---|
Goal.compress_bound_value |
对每个 UInt64 输入,两个翻译后的上界函数的数值都等于模型的上界公式;不涉及输出是否够用 |
Goal.compress2_z_first_alloc_failure |
第一次默认分配失败:内存错误、存放的长度为零、字节块不变、没有多出的存活块 |
后者把局部流当作自动存储,所以它不消耗分配器失败的序号。它不描述成功的压缩,也不描述之后的分配失败。
Gzip 文件:抽象文件不是操作系统
GzHandle 保存文件内容、已解码的数据、位置、退回的字节、写入方的历史和错误标志。GzDecoded 描述已解码的内容和终止状态。模型允许外部 I/O 失败;failed 被设置之后,它对数据的承诺就不再成立。具体目标仍然必须描述所有权、错误的效果和安全的清理。
模型中表示的源码行为包括四字节的 gzip 检测、透明读取、拼接的成员、尾部垃圾、延迟的错误交付,以及文件被截断时的缓冲区错误。G 模式关闭透明读取。gzprintf 接受已格式化的字节;它不验证任意的 C 可变参数格式化函数。
位置关系保留了一个重要的区分。压缩读取方到达 EOF 之后,一次向前的定位(gzseek)可以返回一个将来的位置,而在挂起的跳过真正执行之前,gztell 一直停在旧的末尾。透明模式下的定位移动描述符的位置,可以丢弃退回的字节,也可以移到文件末尾之后。GzHandle.CopyMode 区分这种情形。GzOffset 只约束结果为非负或 -1;它不是精确的描述符位置契约。这些例子说明抽象的 gz 关系为什么不能代替具体的逐函数目标。此外,GzDecoded 的错误后缀子句使用存在性的 Layer.Consistent,而不是 InflState 使用的因果输出证据关系。它不是 gzip 读取的完整操作规格。
抽象接口必须表达什么
HeapApi 固定了细化目标 *_refines 的类型。它的字段不是运行时堆的实现。选一个空的运行关系,或者一个不可能成立的匹配关系,什么也验证不了。
| 字段族 | 在具体实例中必须有的解释 |
|---|---|
Heap, Strm, GzFile |
实际的运行时堆,以及所表示的流和句柄引用 |
inflMatches, deflMatches, gzMatches |
存活的具体表示加上模型历史;无关的字段不受约束 |
*Args |
该操作的实际缓冲区、标量值、大小、可写性和所需的分离 |
*Run,以及初始化、结束、复制、回调解码和工具函数的操作 |
每一种实际的执行结果,包括故障以及外部失败和分配失败 |
*NoState, *Disjoint |
初始化或复制所要求的具体的无状态条件和分离条件 |
对 inflate,匹配关系必须把模式、位缓冲、环形历史、校验和,以及会回绕的总数,都与模型状态联系起来。对 deflate,它还必须联系待输出内容、缓冲的位和最近一次刷新。复制之后的匹配必须说明:两份状态各自拥有独立的存储,而逻辑历史相同。回调解码需要明确的回调效果和终止假设。
抽象的细化目标要求每个允许的操作之后没有故障并且保持匹配。只有在实际的初始化函数建立了匹配、实际的操作保持匹配之后,序列的组合才成立。无泄漏还需要具体的所有权命题和帧命题;抽象接口不提供它们。生成的运行时结构定义描述的是表示的字段,不是匹配关系成立的证明。