证明细节
先从引擎的完整论证进入,再按查表、复制、编码和内存等组件查阅细节。每条路线都连接到具体函数约定和相关定义。
解压引擎
窗口内容、真实模式、位前缀、查表、退出与跨调用序列。
完整证明细节 →公开契约与精确目标 →压缩引擎
窗口、哈希链、匹配搜索、策略循环、符号账本、块输出与默认封装。
完整证明细节 →公开契约与精确目标 →实际证明的阅读路线
下面按实现步骤排列关键引理。先读每项解决的问题和前提,再点击查看具体推导;完整接口证明需要把这些步骤连接起来。
inflate
- 初始化参数域
这一条先回答“初始化实际创建了怎样的解码器”。它展开 inflateInit2_,在每个被接受的窗口参数下建立初始化契约 InflateInitContract,并覆盖版本/尺寸拒绝、空流拒绝、分配成功和分配失败。
窗口参数必须先满足 Api.inflWbits,因此无效参数不在这条结果内,也就不是不受限的 Goal.inflateInit2_。其余前提包含可读版本值、合法调用者流存储、未来分配标识未被使用(Fresh)、已有对象身份不冲突(Uniq),以及默认或空分配器。inflate_init2_valid_public - 固定表安装
读完固定块头后,解码器需要把格式规定的编码表装到真实状态中。这条结果跟随 TYPEDO 尾部进入读取符号前的 LEN_ 状态,在返回堆上建立表不变量 DataTableInvariant;表指针对应实际静态数组。
运行环境 Env 和库静态数据 LibraryGlobals 必须有效;位寄存器 hold 的低两位选择固定编码块,刷新参数不能是 Z_TREES。它只处理这一安装分支;动态表安装、此后历史中的保持和完整的公开 inflate 调用,都不能单由它得出。typedoTail_fixed_tableInvariant - 动态表内容
动态块先给出码长,构造器必须把这些码长变成实际可读的表。这条结果展开 inflate_table,同时给出安全/返回分类和构造内容关系 TableConstruction:成功时记录规范编码叶子、子表链接和返回范围,也包括空表、单符号表和错误返回。
调用前提 CallPre 要求码长输入可读、目标表容量可写、满足相应分离条件,并包含其他内部调用条件。这条结果不把构造出的内容与解码器使用的表关系和实际调用状态联系起来;它不是整个流的解码正确性。inflate_table_construction - 模式循环与终止
主解码循环会在读位、查表和复制等模式之间切换。这条结果证明实际分派循环退出时没有运行时故障,保留解码状态条件 DefaultStateJ、剩余输入,以及精确的输入/输出游标和计数。用于终止的秩读取实际模式,执行次数落在运行时步数预算内。
需要有效运行环境 Env、状态条件 DefaultStateJ、分派缓冲区条件 DispatchBuffers、局部头部条件 HeaderLocal,且进入时缓冲位不超过 39。结果不包含公开入口完整定义域、公共退出路径或所有权后置条件。inflate_default_view_loop - 固定流字段的保持
处理数据会改变游标,却不应改写流的身份和分配配置。这条结果穿过入口归一化、加载字段的 LOAD 和完整模式循环,保持状态根、分配/释放函数、opaque 上下文参数与 reserved 保留字段。辅助函数的保持结论来自其实际翻译体。
context.strm 必须指向所述流。StreamFrameX 描述“执行已经成功返回时,固定字段保持不变”这一条件性结论。它本身不说明执行是否存在、能否终止、是否无故障,也不说明输出内容。streamFrameX_inflate_run - 状态与窗口释放
结束调用要释放流拥有的状态和窗口,同时保留调用者的其他对象。这条对应 Goal.inflateEnd 的执行返回 Z_OK、清空状态指针,按照所有权关系 InflateOwned 精确移除活块,并保持无关存储和分配计数。
Goal.inflateEnd 要求状态满足 Good,并使用默认释放函数 zcfree。它使用已有的 Good 条件;它本身不说明每一段公开调用历史都满足该条件。inflate_end_public - 缓冲区替换与历史
调用者换一块缓冲区后,解码器仍应继续同一个任务。公开替换关系 Rebuffer 保持解码状态关系 DefaultDecodeJ 中的表、未完成工作和窗口等条款,不要求新旧调用者缓冲区保存相同字节。
需要已有 DefaultDecodeJ、合法的缓冲区替换 Rebuffer,以及新堆满足 ByteObjectsFit 的逐字节对象大小条件。它只说这一种历史操作;初始化、其他状态操作和整个调用序列不在这条结果内。rebuffer_default_J
deflate
- 默认初始化与分配失败
默认初始化先建立可继续使用的压缩器,也必须清理失败到一半的分配。这条结果展开固定配置的 deflateInit_,建立 Goal.deflateInit_,包括任意压缩级别、版本和参数拒绝、五次分配的成功/失败、清理、所有权与初始化不变量。
前提保留未来分配身份未占用 Fresh、现有身份唯一 Uniq、库静态数据、调用者存储、版本及默认或空分配器条件。配置固定为窗口指数 15、内存级别 8、策略 0;通用 Goal.deflateInit2_ 不在这条结果内。deflateInit_proof - 引擎初始不变量
初始化的零值必须足以让第一次引擎调用安全开始。这条结果在实际成功分配的堆上建立起始关系 EngineStart:真实窗口与哈希数组满足初始链条件,计数和游标为规定初值,调用者输入/输出绑定保留。
需要合法默认参数和调用者存储、有效的 Fresh/Uniq/LibraryGlobals 条件、默认或空分配器,且五次分配全部成功。压缩器有效状态 DGood 和链不变量由初始化建立;之后的非空链、非零计数和其他历史不在这条结果内。default_initialization_engine_bindings - 窗口补充与哈希预置
继续压缩时,补充输入必须同时更新窗口字节和查找索引。这条 fill_window 结果给出精确返回堆,保持压缩器有效状态 DGood 与哈希链关系 HeapChains,建立已初始化前缀,并在预读量足够时连接滚动哈希与实际字节。
所选分支不搬移窗口,待插入计数 insert 为零,封装字段 wrap 为 1(zlib),预读量 lookahead 小于 262 字节且输入非空。还需要窗口/输入视图、范围和复制分离条件;搬移及延期插入字符串分支不在这条结果内。fill_window_resume_complete - 匹配搜索与决策
一次搜索和后续决策结束后,下一轮必须仍处在合法策略边界。这条结果恢复 StrategyBoundary,推进当前位置 strstart、减少预读量 lookahead,并保持输入终点、调用者缓冲区和精确输出记账;包括符号缓冲区填满时的原样存储、固定编码和动态编码输出。
需要已有策略边界 StrategyBoundary、终点关系 EndFrontier、缓冲区条件 StreamBuffers、正压缩级别、非空预读和匹配比较空间。符号容量尺度 lit_bufsize 固定为 16384,输出是直接字节数组,且块发布条件 PublishReady 已成立。它从补充输入之后开始,不包括补充输入本身。slow_search_decision_ready_boundary - 部分输出与剩余位
输出空间不足时,已经交付的字节和仍保留的位必须能接回原序列。这条 flush_pending 低缓冲位路径交付 min(pending, avail_out) 个字节,保持有效状态 DGood、精确记账和存储关系;已写字节的位串接上剩余位 PendingBits,等于调用前的写入器位串。
需要树状态 TreesInvAt、少于八个缓冲位、位于基址的待交付游标、合法可写输出,且输出和待交付存储是不同的直接字节对象。输出容量可以为零;它不覆盖一般的位刷新,也不覆盖更广的公开缓冲区定义域。flush_pending_low_raw_bits_storage