hpatch 学习笔记
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 wdfk-prog的个人博客！
微信- 支付寶
相关推荐
2025-10-04
HPatch
[TOC] HDiffPatch\libHDiffPatch\HPatch\patch.cpackUInt & hpatch_packUIntWithTag 可变长度整数编码这组函数实现了一种高效的、类似于 LEB128 (Little-Endian Base 128) 或 VLQ (Variable-length quantity) 的整数编码方案。其核心目标是：用更少的字节来表示小数值，用更多的字节来表示大数值，从而在数据流中实现对数值本身的压缩。 原理与设计思路解析您提供的注释已经非常精彩地概括了其编码方案，我将在此基础上做更详细的解析。 编码规则 (Encoding Scheme):算法将一个整数 uValue 拆分成多个字节进行存储。每个字节都由两部分组成： 数据位 (Data Bits): 每个字节的低7位用于存储 uValue 的一部分数据。 连续标志位 (Continuation Bit): 每个字节的最高位 (MSB) 作为标志位。 如果 MSB 是 1，表示后面还有字节属于这个整数。 如果 MSB 是 0，表示这是这个整数的最后一个字节。 ...
2025-10-04
tinyuz
[TOC] tinyuz\compress\tuz_enc.cpptuz_compress Tuz 数据压缩核心实现 负责执行 Tuz 无损压缩算法，将输入数据流 (data) 压缩后写入输出数据流 (out_code)。该实现同时支持高效的单线程和多线程压缩模式。 原理与设计思路解析tuz_compress 函数是 Tuz 压缩器的核心，它负责编排整个压缩流程。其设计思想围绕着分块处理 (Clipping) 和并行计算，以在处理大规模数据时兼顾内存效率和执行速度。 核心压缩策略 写入文件头 (Header First): 压缩开始时，首先会向输出流写入一个头部。这个头部包含了后续解压所必需的元数据，最主要的是字典大小 (Dictionary Size)。 数据分块 (Clipping): 为了有效管理内存并为并行化创造条件，输入数据不会被一次性加载。相反，它会被切分成连续的、大小适中的数据块，称为 “clip”。每个 clip 的大小会根据字典大小进行策略性计算，以平衡压缩率和处理开销。 分块压缩: 真正的压缩逻辑由 compress_clip 函数（在本代码片段中被调用...
2025-10-04
SA-IS
[TOC] saisxx (顶层API)saisxx 是整个 sais.hxx 库提供给外部使用的公共接口函数。它本身不执行任何复杂的算法逻辑，其主要作用是作为一层封装，进行参数的合法性检查，处理一些简单的边界情况，并调用内部的核心实现 saisxx_private::suffixsort。 原理与设计思路解析 API 设计: 函数签名 template<typename string_type, typename sarray_type, typename index_type> 表明它是一个高度通用的模板函数。它可以接受任何满足随机访问迭代器 (Random Access Iterator) 条件的类型作为输入字符串 T 和输出数组 SA。例如，T 可以是 const char*、std::string 或 std::vector<unsigned char>；SA 可以是 int* 或 std::vector<long>。 k = 256 的默认参数，表明它默认处理的是8位字符（如ASCII, UTF-8字节流）的字符串。 参数校验...
2025-10-03
SuffixString
[TOC] HDiffPatch\libHDiffPatch\HDiff\private_diff\suffix_string.cpp后缀数组后缀 (Suffix)：一个字符串的后缀是指从字符串的某个位置开始到字符串末尾的所有字符组成的子串。例如，对于字符串 banana，它的所有后缀是： banana (从位置0开始) anana (从位置1开始) nana (从位置2开始) ana (从位置3开始) na (从位置4开始) a (从位置5开始) 后缀数组 (Suffix Array)：后缀数组不是存储这些后缀字符串本身，而是存储这些后缀的起始位置索引。最关键的一步是，这些索引是按照它们所代表的后缀字符串的**字典序（字母顺序）**进行排序的。 我们来为 banana 构建一个后缀数组： 列出所有后缀及其起始位置： 起始位置 后缀 0 banana 1 anana 2 nana 3 ana 4 na 5 a 按字典序对后缀进行排序： a ana anana banana na nana 构建后缀数组...
2025-10-03
hdiffpatch
[TOC] hdiffi.cpphdiffi & hdiffi_in_mem 内存模式下的补丁生成这是 HDiffPatch 工具集中负责制作补丁的核心业务逻辑。hdiffi 是一个上层封装，而 hdiffi_in_mem 实现了将整个文件加载到内存中进行差分的核心流程。 原理与设计思路解析这部分代码的 overarching goal 是协调整个补丁制作过程，它是一个高层次的控制器，调用底层的差分算法和压缩库来完成任务。 核心策略：内存模式 (In-Memory) 函数名 hdiffi_in_mem 明确指出了其核心设计：将旧文件和新文件完全读入内存中，然后再进行比较和差分。 优点： 差分算法（特别是基于后缀数组的算法）需要对数据进行大量的、非线性的随机访问。在内存中操作可以极大地提升算法的执行速度，避免了缓慢的磁盘I/O。 缺点： 这种模式的内存消耗巨大，它要求系统的可用RAM必须能同时容纳整个旧文件和新文件。因此，它不适用于超出内存容量的超大文件。 模块化与可配置性 代码通过 TDiffiSets 结构体和 compressPlugin 接口，实...
2025-10-03
hpatch_lite
[TOC] 学习笔记HPatchLite\HDiffPatch\libHDiffPatch\HPatchLite\hpatch_lite.cHptach 算法1. Hptach 的核心：加法差分 (Additive Diff)这种方法可以被称为加法差分或增量差分。 核心公式： NewData = OldData + DiffData 反向公式： DiffData = NewData - OldData (在生成补丁时计算) 工作流程图： 1234567891011121314151617181920212223242526272829303132 +----------------------+生成补丁时 (hpatch_diff) | | | 新文件 (New File) | +----------------------+ | (减法) ...
评论
