知识卡片
压缩格式需明确整数与边界
正文称前4字节存原符号数,源码实际memcpy sizeof(int)字节的本机int,随后预留256个频数字节。htons仅作用于码表code字段,没有把头部int变成固定宽度网络字节序,因此该格式不能据文字描述直接认定跨平台。
解码接口没有压缩缓冲长度,无法在读取头部和后续位之前核对剩余字节;只依靠头部size停止还需要验证合法范围并限制恢复输出。文件格式应明确整数宽度、字节序、频数表长度、有效结束方式及容量限制。这里是改进所需条件,原实现没有完成这些检查。
270⁄03041 LZ77头部仍memcpy本机int,解码无压缩输入长度,读取类型/偏移/长度/next时不能核对剩余位;未验证offset+length在历史窗口范围,就从window[offset+i]读取。原长度计数能限制恢复符号数,并不验证压缩缓冲足够或引用位置合法;不得据剩余计数宣称能处理恶意输入。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
四字节的值,表示待编码的符号个数,后面紧跟着的是所有256个可能的符号出现的缩放频率,也包括0。最后,对数据编码,一次读取一个符号,在表中查找它的霍夫曼编码,并将每个编码存到压缩缓冲区中。在压缩缓冲区中为每个字节分配空间,因为我们需要这样做。 huffman_compress的时间复杂度为O(n),
- · 查看原书依据
首先,该函数从压缩数据中读取字符,并初始化滑动窗口和前向缓冲区。 解压缩过程在一个循环中执行,此循环会持续迭代执行直到所有符号处理完。使用ipos来保存向压缩数据缓冲区写入的当前位,并用opos来保存写入恢复数据缓冲区中当前字节。在循环的每次迭代过程中,首先从压缩数据读取一位来确定要解码标记的类型。
参考来源
- 位置:《算法精解:C语言描述》第14章《huffman_compress》(spine1385;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1351.html;u260-ch14-017)。
- 结论依据:260头部全文及03026–03029 hsize、memcpy、bit_get和停止条件逐行实读。
- 原始内容:四字节的值,表示待编码的符号个数,后面紧跟着的是所有256个可能的符号出现的缩放频率,也包括0。最后,对数据编码,一次读取一个符号,在表中查找它的霍夫曼编码,并将每个编码存到压缩缓冲区中。在压缩缓冲区中为每个字节分配空间,因为我们需要这样做。 huffman_compress的时间复杂度为O(n),
- 位置:《算法精解:C语言描述》第14章《lz77_uncompress》(spine1393;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1359.html;u270-ch14-017)。
- 结论依据:270/03041 LZ77头部仍memcpy本机int,解码无压缩输入长度,读取类型/偏移/长度/next时不能核对剩余位;未验证offset+length在历史窗口范围,就从window[offset+i]读取。原长度计数能限制恢复符号数,并不验证压缩缓冲足够或引用位置合法;不得据剩余计数宣称能处理恶意输入。
- 原始内容:首先,该函数从压缩数据中读取字符,并初始化滑动窗口和前向缓冲区。 解压缩过程在一个循环中执行,此循环会持续迭代执行直到所有符号处理完。使用ipos来保存向压缩数据缓冲区写入的当前位,并用opos来保存写入恢复数据缓冲区中当前字节。在循环的每次迭代过程中,首先从压缩数据读取一位来确定要解码标记的类型。