解压输出与工作预算

形式陈述

解码正确性说“合法输入恢复原文”；资源契约还要说“面对不合法或巨大展开的输入，在有限工作和内存中停止”。本页把解压看成受预算限制的状态机，接受压缩输入和调用者给出的上限，返回完整结果或明确失败。文件头里的原长是待检查的声明，不能充当可信授权。

至少分别限制：输入字节或有效位数 $I_{max}$ ，输出字节数 $N_{max}$ ，码表/字母表大小，LZ历史窗口，字典条目数 $D_{max}$ ，以及可定义的解码工作 $K_{max}$ 。工作单位要明确，例如“读一个token算1，输出或复制一个字节算1”；它不是声称精确预测CPU毫秒数。

设已产出 $p$ 字节，一个动作准备追加 $\ell$ 字节。必须先验证

0\le\ell\le N_{max}-p,\qquad \operatorname{cost}(动作)\le K_{max}-used,

再扩容、创建临时对象和执行循环。用减法形式可避免固定宽度下 $p+\ell$ 溢出后绕回小数。调用开始时还要检查所有预算为非负且状态计数在界内。

对LZ77回指，先验证距离 $1\le d\le\min(W,p)$ 、长度范围和剩余输出/工作，再逐字节复制。对LZ78，先验证旧编号已经存在；利用条目中保存的短语长度计算展开长度，通过预算后才沿父链建临时栈。每个新父指针指向更早条目，因此合法字典中没有循环。

直觉

压缩文件很短，正是因为一个小指令能代表很多输出。输入大小不再是工作量的好替代物。距离1的回指只需说明“继续重复刚才那个字节”，却可能请求一百万次写入。

越早检查越有用。如果先创建一百万字节的临时数组再检查容量，失败虽被报告，资源已经花掉。如果相信头部写着四十亿就直接分配四十亿容量，一个从未解出任何有效数据的文件也能消耗巨量内存。

预算必须属于本次调用或整条处理链的共享状态。每解一小块就把预算重置，会允许攻击者通过许多块绕过总量上限；嵌套压缩也需跨层累计，否则每层各自看起来“小”并不限制最终展开。

例子与边界

按照“每token1步，每输出字节1步”的模型，Lit(A), Lit(B), Match(7,2) 有3个token、9字节输出，总工作12。若 $N_{max}=8$ ，处理两个字面量后 $p=2$ ，剩余容量6，小于匹配长7，应在第三个字节写入前拒绝整个匹配。若输出容量够但剩余工作不足，也先拒绝，不能只检查压缩比。

另一个恶意token序列是 Lit(A), Match(10^30,1)。距离1合法，问题在于长度。检查器用Python大整数先比较 $10^{30}\le N_{max}-1$ ，返回失败，不调用这么长的循环，也不生成对应临时串。距离0、距离超过历史、负长度则属于语义非法，不是“提高预算就能接受”的大文件。

LZ78接到指向现有长短语的END时，即使不新增字典条目，仍须支付这个短语的输出和父链遍历费用；“结束token免费”会漏掉最后一段。字典上限也和输出上限不同：许多短而不同的短语可以使条目数快速增长，单看某次匹配长度不够。

对Huffman/算术帧，声明原长 $2^{32}-1$ 但调用者上限十万时，解析固定头后就拒绝；无需先读完整表、更无需预分配原长缓冲。检查器另外限制有效位数，并在把字节扩展为 '0'/'1' 字符串前核对物理payload长度。这个字符串表示只为演示，生产流式解析通常直接从字节取bit。

推论与应用

可检验的资源上界

在每个动作之前扣减预算，归纳可得：任意成功前缀的累计输出不超过 $N_{max}$ ，累计计费工作不超过 $K_{max}$ 。动作内部也要保证真实工作受所收费用覆盖；如果声称一个LZ匹配算一步，却在其中循环百万次，预算不变量本身并不能限制执行时间。

固定精度的算术解码，每个符号的重归一化次数为 $O(w)$ ，表查询至多扫描 $m$ 项，限制 $n,m,w$ 和输入位数便给出有限的 $O(n(m+w))$ 工作界。Huffman最大码长为 $B$ 时，逐位树解码的工作受有效输入位数和输出数共同限制。教学检查器为展示过程保存全轨迹，算术每步还保存频数表，并重编码验证尾部；应计入这些额外的 $O(nm)$ 记录和第二遍计算，不能引用理想流式空间冒充它的峰值。