这是一个关于 XZ 和 LZMA 压缩算法的五部分系列博客文章的第一部分。

• 背景：XZ 是一种通用的压缩文件格式，压缩比很好，通常优于 gzip/deflate 和 bzip2，虽有新格式如 brotli 和 zstd 有竞争力，但仍被广泛使用。XZ 是容器格式，LZMA 是压缩算法，7z 和 LZIP 也可使用 LZMA。几周前，xz/liblzma发现后门，本文将介绍 LZMA 压缩算法的工作原理。
• 符号表示：用[lb, ub)表示半开数值范围，还引入“无操作下划线”，[lb, ub)与(lb ++ width)等价，宽度width = (ub - lb)，宽度可以是隐式的，如«834626841»表示[0.834626841, 0.834626842)。
• Byms（二进制符号）：LZMA 是结合“Lempel-Ziv 回溯引用”和范围编码的压缩技术，解码需逆序进行，范围解码将压缩字节转换为符号流，LZMA 使用 2 符号流（蓝色 0 和绿色 1），蓝色和绿色在字节流中不必等权重，范围编码的优势是符号概率不必是二分之一的幂。
• 寻宝类比：解码 LZMA 时，窄范围转换为 bym 流可用“寻宝”类比，在 1 维岛上寻找宝藏，用宝藏地图（精确的数字列表）定位，由于不能记住多于 4 位数字，需保持包含实际宝藏范围的宝藏前缀范围，每次迭代“缩放”（读取更多数字，缩小范围），同时保持覆盖范围，最终得到 bym 流。
• 缩放：需要跟踪 4 个数字，但可用转换来解决，只跟踪覆盖范围和宝藏前缀范围的下界差bits和宽度width，都以 ZLU（缩放级别单位）为整数倍，开始时设置bits为宝藏地图的前 4 位（实际前 5 位，首位为 0 简化编码器），width为 9999，ZLU 为 1e-5，每次迭代根据选择的颜色调整width，当width过小时进行缩放。
• 解码器：解码器内循环代码根据阈值t判断选择蓝色或绿色 bym，然后根据 bym 调整width，必要时进行缩放，mul(width, prob)表达式用于乘法，目前概率是固定的。
• 编码器：编码与解码相反，从 bym 流生成宝藏地图，编码器有类似解码器的两个状态变量low和width，low是范围的下界，width是覆盖宽度，编码过程与解码类似，都在width足够小时进行缩放。
• ShiftLow：shiftLow函数用于处理编码中的数字移位，将low的左移一位并将右移一位补 0，对于 base-256 数字用位运算符，out形成宝藏地图数字，但要注意不能提前写出可能导致溢出的数字，编码器可以跟踪 N+1 个待处理数字（包含一个非零数字和 N 个 9）。
• 初始零字节：对于 LZMA 解码器是否应强制初始宝藏地图数字为零存在分歧，xz和lzma-sdk要求初始字节为零，而 LZIP 有ignore_marking配置选项允许非零初始字节，Linux 内核的 MicroLZMA 变体也重新利用了这个初始零字节。

接下来是第二部分：Part 2: A Complete Toy Range Coder，发布时间为 2024-04-14。