Zstandard/Double-fast 匹配器

用长短两个哈希索引寻找压缩匹配

Zstandard 的 double-fast 策略分别索引长、短前缀，在少量候选之间查验并延长真实匹配。

49cf51799存储与数据放置核验 2026-10-12

工程问题#

快速压缩希望用少量内存访问找到可编码的重复串。只索引短前缀容易碰撞，只索引长前缀又会漏掉较短匹配；遍历很长的候选链会提高搜索开销。

实际实现#

noDict 匹配器把 hashTable 用作 8 字节前缀索引，把 chainTable 用作较短前缀索引，二者保存历史位置而非完整字符串。哈希命中后检查窗口边界并比较真实字节，随后延长匹配。短匹配分支还比较 ip1 处的长匹配；最终记录字面量长度、偏移和匹配长度。

处理流程#

进入 double-fast 的 noDict 分支，并按 minMatch 选择实例
从长、短前缀哈希表读取历史候选，同时更新当前位置
检查候选仍在允许的前缀窗口内，再比较并延长字节匹配
在有限候选间取舍，写入序列并推进输入位置

源码片段#

固定版本 · 原文摘录

lib/compress/zstd_compress.c49cf51799ea051457f57243527aa2058f999f005 · L3443–L3453

查看原文件

3443        } else {   /* not long range mode and no external matchfinder */3444            ZSTD_BlockCompressor_f const blockCompressor = ZSTD_selectBlockCompressor(3445                    zc->appliedParams.cParams.strategy,3446                    zc->appliedParams.useRowMatchFinder,3447                    dictMode);3448            ms->ldmSeqStore = NULL;3449            lastLLSize = blockCompressor(ms, &zc->seqStore, zc->blockState.nextCBlock->rep, src, srcSize);3450        }3451        {   const BYTE* const lastLiterals = (const BYTE*)src + srcSize - lastLLSize;3452            ZSTD_storeLastLiterals(&zc->seqStore, lastLiterals, lastLLSize);3453    }   }

ZSTD_buildSeqStore

常规块压缩路径依据 strategy 和字典模式选择匹配器，再调用它生成序列。

CBSD-3-Clause（双许可中选择 BSD 条款）

lib/compress/zstd_double_fast.c49cf51799ea051457f57243527aa2058f999f005 · L568–L585

查看原文件

568size_t ZSTD_compressBlock_doubleFast(569        ZSTD_MatchState_t* ms, SeqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],570        void const* src, size_t srcSize)571{572    const U32 mls = ms->cParams.minMatch;573    switch(mls)574    {575    default: /* includes case 3 */576    case 4 :577        return ZSTD_compressBlock_doubleFast_noDict_4(ms, seqStore, rep, src, srcSize);578    case 5 :579        return ZSTD_compressBlock_doubleFast_noDict_5(ms, seqStore, rep, src, srcSize);580    case 6 :581        return ZSTD_compressBlock_doubleFast_noDict_6(ms, seqStore, rep, src, srcSize);582    case 7 :583        return ZSTD_compressBlock_doubleFast_noDict_7(ms, seqStore, rep, src, srcSize);584    }585}

ZSTD_compressBlock_doubleFast

入口按 minMatch 分派到 noDict 的特化实例，其他字典模式有独立函数。

CBSD-3-Clause（双许可中选择 BSD 条款）

lib/compress/zstd_double_fast.c49cf51799ea051457f57243527aa2058f999f005 · L109–L123

查看原文件

109    ZSTD_compressionParameters const* cParams = &ms->cParams;110    U32* const hashLong = ms->hashTable;111    const U32 hBitsL = cParams->hashLog;112    U32* const hashSmall = ms->chainTable;113    const U32 hBitsS = cParams->chainLog;114    const BYTE* const base = ms->window.base;115    const BYTE* const istart = (const BYTE*)src;116    const BYTE* anchor = istart;117    const U32 endIndex = (U32)((size_t)(istart - base) + srcSize);118    /* presumes that, if there is a dictionary, it must be using Attach mode */119    const U32 prefixLowestIndex = ZSTD_getLowestPrefixIndex(ms, endIndex, cParams->windowLog);120    const BYTE* const prefixLowest = base + prefixLowestIndex;121    const BYTE* const iend = istart + srcSize;122    const BYTE* const ilimit = iend - HASH_READ_SIZE;123    U32 offset_1=rep[0], offset_2=rep[1];

ZSTD_compressBlock_doubleFast_noDict_generic

两表保存不同长度前缀的候选；prefixLowestIndex 限制可引用的历史。

CBSD-3-Clause（双许可中选择 BSD 条款）

lib/compress/zstd_double_fast.c49cf51799ea051457f57243527aa2058f999f005 · L170–L187

查看原文件

170        ip1 = ip + step;171172        if (ip1 > ilimit) {173            goto _cleanup;174        }175176        hl0 = ZSTD_hashPtr(ip, hBitsL, 8);177        idxl0 = hashLong[hl0];178        matchl0 = base + idxl0;179180        /* Inner Loop: one iteration per search / position */181        do {182            const size_t hs0 = ZSTD_hashPtr(ip, hBitsS, mls);183            const U32 idxs0 = hashSmall[hs0];184            curr = (U32)(ip-base);185            matchs0 = base + idxs0;186187            hashLong[hl0] = hashSmall[hs0] = curr;   /* update hash tables */

ZSTD_compressBlock_doubleFast_noDict_generic

ip1 随 step 前进；先读取旧候选，再把当前索引写入长短两表。

CBSD-3-Clause（双许可中选择 BSD 条款）

lib/compress/zstd_double_fast.c49cf51799ea051457f57243527aa2058f999f005 · L203–L221

查看原文件

203            {   const BYTE*  const matchl0_safe = ZSTD_selectAddr(idxl0, prefixLowestIndex, matchl0, &dummy[0]);204205                /* check prefix long match */206                if (MEM_read64(matchl0_safe) == MEM_read64(ip) && matchl0_safe == matchl0) {207                    mLength = ZSTD_count(ip+8, matchl0+8, iend) + 8;208                    offset = (U32)(ip-matchl0);209                    while (((ip>anchor) & (matchl0>prefixLowest)) && (ip[-1] == matchl0[-1])) { ip--; matchl0--; mLength++; } /* catch up */210                    goto _match_found;211            }   }212213            idxl1 = hashLong[hl1];214            matchl1 = base + idxl1;215216            /* Same optimization as matchl0 above */217            matchs0_safe = ZSTD_selectAddr(idxs0, prefixLowestIndex, matchs0, &dummy[0]);218219            /* check prefix short match */220            if(MEM_read32(matchs0_safe) == MEM_read32(ip) && matchs0_safe == matchs0) {221                  goto _search_next_long;

ZSTD_compressBlock_doubleFast_noDict_generic

哈希命中之后仍核验地址范围和真实字节，并分别处理长、短匹配。

CBSD-3-Clause（双许可中选择 BSD 条款）

lib/compress/zstd_double_fast.c49cf51799ea051457f57243527aa2058f999f005 · L253–L271

查看原文件

253_search_next_long:254255        /* short match found: let's check for a longer one */256        mLength = ZSTD_count(ip+4, matchs0+4, iend) + 4;257        offset = (U32)(ip - matchs0);258259        /* check long match at +1 position */260        if ((idxl1 > prefixLowestIndex) && (MEM_read64(matchl1) == MEM_read64(ip1))) {261            size_t const l1len = ZSTD_count(ip1+8, matchl1+8, iend) + 8;262            if (l1len > mLength) {263                /* use the long match instead */264                ip = ip1;265                mLength = l1len;266                offset = (U32)(ip-matchl1);267                matchs0 = matchl1;268            }269        }270271        while (((ip>anchor) & (matchs0>prefixLowest)) && (ip[-1] == matchs0[-1])) { ip--; matchs0--; mLength++; } /* complete backward */

_search_next_long

延长短候选，并比较 ip1 的长候选；不能把源码 +1 注释当作所有迭代的实际步长。

CBSD-3-Clause（双许可中选择 BSD 条款）

lib/compress/zstd_double_fast.c49cf51799ea051457f57243527aa2058f999f005 · L287–L299

查看原文件

287            hashLong[hl1] = (U32)(ip1 - base);288        }289290        ZSTD_storeSeq(seqStore, (size_t)(ip-anchor), anchor, iend, OFFSET_TO_OFFBASE(offset), mLength);291292_match_stored:293        /* match found */294        ip += mLength;295        anchor = ip;296297        if (ip <= ilimit) {298            /* Complementary insertion */299            /* done after iLimit test, as candidates could be > iend-8 */

_match_found / _match_stored

把已核验的匹配写成序列，再推进输入和字面量起点；后续阶段才编码序列。

CBSD-3-Clause（双许可中选择 BSD 条款）

摘录分别保留调用入口、核心机制及边界；完整上下文见各段源码链接。

收益与取舍#

工程分析

带来的收益

用两个不同前缀长度的索引兼顾长匹配和短匹配机会
每桶只保留位置，避免遍历任意长的哈希冲突链

付出的代价

哈希桶覆盖旧位置会丢弃候选，不能保证全局最长匹配或最佳压缩率
两张表需要额外空间；字节延长比较和未命中时的步长变化也影响实际工作量
chainTable 在此策略下充当短哈希表，不能因为字段名就把它解释为链表

可比较的选择

哈希链匹配可沿同桶查找更多历史候选，但搜索量需要额外控制。

单哈希快速匹配状态更少，但前缀长度的选择更直接影响碰撞与短匹配机会。

版本与适用范围#

固定到提交 49cf51799ea0。仅分析该提交的 doubleFast_noDict_generic，不代表 Zstandard 全部压缩级别、字典模式或熵编码；重复偏移 repcode 快路径未完整展开。源码注释称 +1 的候选实际为 ip1=ip+step；step 可能增长，因此不能无条件写成只查看下一字节。

参考来源#

源码、官方文档与原始论文

Zstandard · ZSTD_buildSeqStore

lib/compress/zstd_compress.c · ZSTD_buildSeqStore

源码49cf51799ea051457f57243527aa2058f999f005

Zstandard · ZSTD_compressBlock_doubleFast

lib/compress/zstd_double_fast.c · ZSTD_compressBlock_doubleFast

源码49cf51799ea051457f57243527aa2058f999f005

用长短两个哈希索引寻找压缩匹配

工程问题#

实际实现#

处理流程#

源码片段#

收益与取舍#

带来的收益

付出的代价

可比较的选择

版本与适用范围#

参考来源#

相关实现与比较#

在有限窗口中查找重复串，并比较相邻匹配

复用已翻译的机器代码块

让名称和 UUID 指向同一虚拟机对象

用块哈希复用 prompt 前缀