zstd 深度解剖：FSE 与字典训练

// 压缩流
ZSTD_CStream* cstream = ZSTD_createCStream();
ZSTD_initCStream(cstream, compressionLevel);
ZSTD_compressStream(cstream, &output, &input);
ZSTD_endStream(cstream, &output);

// 解压流
ZSTD_DStream* dstream = ZSTD_createDStream();
ZSTD_initDStream(dstream);
ZSTD_decompressStream(dstream, &output, &input);

// 简化的哈希链匹配查找
uint32_t hash = ZSTD_hashPtr(ip, hashLog, mls);
uint32_t matchIndex = hashTable[hash];
hashTable[hash] = (uint32_t)(ip - base);

while (matchIndex >= lowLimit) {
    const BYTE* match = base + matchIndex;
    if (MEM_read32(match) == MEM_read32(ip)) {
        // 找到匹配，尝试扩展
        size_t matchLen = ZSTD_count(ip + 4, match + 4, iend) + 4;
        // 记录最佳匹配
        if (matchLen > bestLen) {
            bestLen = matchLen;
            bestOffset = (size_t)(ip - match);
        }
    }
    matchIndex = chainTable[matchIndex & chainMask];
    if (--searchCount == 0) break;  // 限制搜索深度
}

// fast 策略的核心循环
size_t hash = ZSTD_hashPtr(ip, hBits, mls);
size_t matchIndex = hashTable[hash];
hashTable[hash] = (size_t)(ip - base);
if (MEM_read32(base + matchIndex) == MEM_read32(ip)) {
    // 匹配成功，编码
} else {
    ip += step;  // step 会逐渐增大（加速跳过不可压缩区域）
}

size_t hashSmall = ZSTD_hashPtr(ip, hBitsS, 4);
size_t hashLong  = ZSTD_hashPtr(ip, hBitsL, 8);
size_t matchSmall = smallTable[hashSmall];
size_t matchLong  = longTable[hashLong];
// 优先选择长匹配

# 基本训练
zstd --train samples/* -o mydict.zstd

# 指定字典大小
zstd --train --maxdict=110000 --dictID=1 -o mydict.zstd samples/*

# 使用 fastCOVER 算法
zstd --train-fastcover=k=64,d=8 samples/* -o mydict.zstd

// 加载字典
ZSTD_CDict* cdict = ZSTD_createCDict(dictBuffer, dictSize, level);

// 使用字典压缩
ZSTD_CCtx* cctx = ZSTD_createCCtx();
size_t compressedSize = ZSTD_compress_usingCDict(
    cctx, dst, dstCapacity, src, srcSize, cdict);

// 解压时也需要同一个字典
ZSTD_DDict* ddict = ZSTD_createDDict(dictBuffer, dictSize);
ZSTD_DCtx* dctx = ZSTD_createDCtx();
size_t decompressedSize = ZSTD_decompress_usingDDict(
    dctx, dst, dstCapacity, src, srcSize, ddict);

// 传统有分支写法
if (offset > 8) {
    memcpy(op, match, 8);
} else {
    op[0] = match[0];
    op[1] = match[1];
    // ... 逐字节复制
}

// zstd 的无分支写法
ZSTD_copy8(op, match);  // 总是复制 8 字节
// 如果 offset < 8，后续用覆盖写修正
ZSTD_overlapCopy8(op, match, offset);

// FSE 解码热循环（简化）
typedef struct {
    size_t newState;
    BYTE   symbol;
    BYTE   nbBits;
} FSE_decode_t;

// 解码一个符号：完全无分支
#define FSE_DECODE_SYMBOL(statePtr, bitDPtr) \
    { \
        const FSE_decode_t entry = table[*statePtr]; \
        *statePtr = entry.newState + BIT_readBitsFast(bitDPtr, entry.nbBits); \
        return entry.symbol; \
    }

// 在处理当前序列之前，预取下一个匹配位置的内存
PREFETCH_L1(oLitEnd + sequence.offset);

// 在 FSE 解码中，预取下一个状态的表项
PREFETCH_L1(&table[nextState]);

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

/* ============================================================
 * Simple FSE (Finite State Entropy) Encoder
 * 基于 tANS (table-based Asymmetric Numeral Systems)
 *
 * 本实现用于教学目的，展示 FSE 的核心原理。
 * 生产代码请使用 Yann Collet 的 FiniteStateEntropy 库。
 * ============================================================ */

#define FSE_MAX_TABLELOG    12
#define FSE_MAX_TABLESIZE   (1 << FSE_MAX_TABLELOG)
#define FSE_MAX_SYMBOL      255
#define FSE_MIN_TABLELOG    5

/* ---- 比特流写入器 ---- */
typedef struct {
    uint64_t  bitContainer;
    unsigned  bitPos;
    uint8_t*  startPtr;
    uint8_t*  ptr;
    uint8_t*  endPtr;
} BitWriter;

static void BW_init(BitWriter* bw, void* dst, size_t dstSize) {
    bw->bitContainer = 0;
    bw->bitPos = 0;
    bw->startPtr = (uint8_t*)dst;
    bw->ptr = bw->startPtr;
    bw->endPtr = bw->startPtr + dstSize;
}

static void BW_addBits(BitWriter* bw, uint64_t value, unsigned nbBits) {
    bw->bitContainer |= (value & ((1ULL << nbBits) - 1)) << bw->bitPos;
    bw->bitPos += nbBits;
}

static void BW_flush(BitWriter* bw) {
    /* 将完整字节写出 */
    while (bw->bitPos >= 8) {
        if (bw->ptr < bw->endPtr)
            *(bw->ptr++) = (uint8_t)(bw->bitContainer & 0xFF);
        bw->bitContainer >>= 8;
        bw->bitPos -= 8;
    }
}

static size_t BW_close(BitWriter* bw) {
    /* 标记结束位：写入一个 1-bit 作为哨兵 */
    BW_addBits(bw, 1, 1);
    BW_flush(bw);
    if (bw->bitPos > 0) {
        if (bw->ptr < bw->endPtr)
            *(bw->ptr++) = (uint8_t)(bw->bitContainer & 0xFF);
    }
    return (size_t)(bw->ptr - bw->startPtr);
}

/* ---- 比特流读取器（简化版） ---- */
typedef struct {
    uint64_t      bitContainer;
    unsigned      bitsConsumed;
    const uint8_t *ptr;
    const uint8_t *start;
} BitReader;

static void BR_init(BitReader* br, const void* src, size_t srcSize) {
    br->start = (const uint8_t*)src;
    br->ptr = br->start + srcSize;
    br->bitsConsumed = 0;
    br->bitContainer = 0;
    size_t nbBytes = srcSize < 8 ? srcSize : 8;
    const uint8_t* p = br->ptr - nbBytes;
    br->ptr = p;
    for (size_t i = 0; i < nbBytes; i++)
        br->bitContainer |= ((uint64_t)p[i]) << (i * 8);
    unsigned lastByte = ((const uint8_t*)src)[srcSize - 1];
    unsigned sentinel = 0;
    while (sentinel < 8 && !((lastByte >> (7 - sentinel)) & 1))
        sentinel++;
    br->bitsConsumed = (unsigned)(8 * (8 - nbBytes)) + sentinel + 1;
}

static uint64_t BR_readBits(BitReader* br, unsigned nbBits) {
    uint64_t value = (br->bitContainer >> br->bitsConsumed) & ((1ULL << nbBits) - 1);
    br->bitsConsumed += nbBits;
    return value;
}

static void BR_reload(BitReader* br) {
    while (br->bitsConsumed >= 8 && br->ptr > br->start) {
        br->ptr--;
        br->bitContainer |= ((uint64_t)(*br->ptr)) << (64 - br->bitsConsumed);
        br->bitsConsumed -= 8;
    }
}

/* ---- FSE 编码表 ---- */
typedef struct {
    int16_t   deltaFindState;
    uint16_t  deltaNbBits;
} FSE_CTableEntry;

typedef struct {
    uint8_t   symbol;
    uint8_t   nbBits;
    uint16_t  newStateBaseline;
} FSE_DTableEntry;

typedef struct {
    unsigned        tableLog;
    unsigned        maxSymbol;
    int16_t         normalizedCounter[FSE_MAX_SYMBOL + 1];
    uint8_t         symbolTable[FSE_MAX_TABLESIZE];
    FSE_CTableEntry encodeTable[FSE_MAX_TABLESIZE];
    FSE_DTableEntry decodeTable[FSE_MAX_TABLESIZE];
} FSE_Table;

/* ---- 统计频率并归一化 ---- */
static void FSE_countFrequencies(const uint8_t* src, size_t srcSize,
                                  unsigned* count, unsigned* maxSymbolPtr)
{
    memset(count, 0, sizeof(unsigned) * (FSE_MAX_SYMBOL + 1));
    unsigned maxSymbol = 0;
    for (size_t i = 0; i < srcSize; i++) {
        count[src[i]]++;
        if (src[i] > maxSymbol) maxSymbol = src[i];
    }
    *maxSymbolPtr = maxSymbol;
}

static void FSE_normalizeCount(int16_t* normalizedCounter,
                                unsigned tableLog,
                                const unsigned* count,
                                size_t srcSize,
                                unsigned maxSymbol)
{
    unsigned tableSize = 1u << tableLog;
    uint64_t scale = ((uint64_t)tableSize << 16) / (uint64_t)srcSize;
    int32_t distributed = 0;

    for (unsigned s = 0; s <= maxSymbol; s++) {
        if (count[s] == 0) {
            normalizedCounter[s] = 0;
            continue;
        }
        if (count[s] == srcSize) {
            /* 唯一符号：全部分配 */
            normalizedCounter[s] = (int16_t)tableSize;
            return;
        }
        int32_t proba = (int32_t)((count[s] * scale) >> 16);
        if (proba < 1) proba = 1;   /* 确保每个出现的符号至少分配 1 */
        normalizedCounter[s] = (int16_t)proba;
        distributed += proba;
    }

    /* 修正总和使其等于 tableSize */
    int32_t diff = (int32_t)tableSize - distributed;
    /* 将差值加到最频繁的符号上 */
    unsigned bestSymbol = 0;
    unsigned bestCount = 0;
    for (unsigned s = 0; s <= maxSymbol; s++) {
        if (count[s] > bestCount) {
            bestCount = count[s];
            bestSymbol = s;
        }
    }
    normalizedCounter[bestSymbol] += (int16_t)diff;
}

/* ---- 构建符号分配表 ---- */
static void FSE_buildSymbolTable(FSE_Table* table) {
    unsigned tableSize = 1u << table->tableLog;
    unsigned highThreshold = tableSize - 1;
    unsigned position = 0;

    /* 步长采用 zstd 使用的散布公式 */
    unsigned step = (tableSize >> 1) + (tableSize >> 3) + 3;
    unsigned tableMask = tableSize - 1;

    /* 首先处理概率为 -1 的符号（低概率） */
    for (unsigned s = 0; s <= table->maxSymbol; s++) {
        if (table->normalizedCounter[s] == -1) {
            table->symbolTable[highThreshold--] = (uint8_t)s;
            /* -1 实际代表概率 < 1，占用 1 个位置 */
        }
    }

    /* 按概率散布其他符号 */
    for (unsigned s = 0; s <= table->maxSymbol; s++) {
        int16_t nc = table->normalizedCounter[s];
        if (nc <= 0) continue;
        for (int16_t i = 0; i < nc; i++) {
            table->symbolTable[position] = (uint8_t)s;
            /* 跳过已被低概率符号占用的位置 */
            do {
                position = (position + step) & tableMask;
            } while (position > highThreshold);
        }
    }
}

/* ---- 构建编码表 ---- */
static void FSE_buildEncodeTable(FSE_Table* table) {
    unsigned tableSize = 1u << table->tableLog;
    unsigned symbolNext[FSE_MAX_SYMBOL + 1];

    /* 初始化每个符号的起始状态 */
    for (unsigned s = 0; s <= table->maxSymbol; s++) {
        int16_t nc = table->normalizedCounter[s];
        if (nc <= 0) {
            symbolNext[s] = 0;
            continue;
        }
        symbolNext[s] = (unsigned)nc;
    }

    /* 为每个表位构建编码条目 */
    for (unsigned i = 0; i < tableSize; i++) {
        uint8_t symbol = table->symbolTable[i];
        unsigned stateValue = symbolNext[symbol]++;

        /* 计算该状态需要输出多少位 */
        unsigned nbBitsOut = table->tableLog
                             - __builtin_clz(stateValue)
                             + __builtin_clz(1);
        /* 简化：用对数关系计算 */
        unsigned k = 0;
        while ((1u << k) <= stateValue) k++;
        k = table->tableLog - k + 1;
        if (stateValue == (1u << (table->tableLog - k)))
            k--;

        table->encodeTable[stateValue].deltaNbBits =
            (uint16_t)((table->tableLog - k) << 16);
        table->encodeTable[stateValue].deltaFindState =
            (int16_t)(i - stateValue);
    }
}

/* ---- 构建解码表 ---- */
static void FSE_buildDecodeTable(FSE_Table* table) {
    unsigned tableSize = 1u << table->tableLog;
    unsigned symbolNext[FSE_MAX_SYMBOL + 1];

    for (unsigned s = 0; s <= table->maxSymbol; s++) {
        int16_t nc = table->normalizedCounter[s];
        if (nc <= 0) {
            symbolNext[s] = 0;
            continue;
        }
        symbolNext[s] = (unsigned)nc;
    }

    for (unsigned i = 0; i < tableSize; i++) {
        uint8_t sym = table->symbolTable[i];
        unsigned stateVal = symbolNext[sym]++;

        /* 确定需要读取的位数 */
        unsigned highBit = 0;
        {
            unsigned v = stateVal;
            while (v > 0) { highBit++; v >>= 1; }
        }
        unsigned nbBits = table->tableLog - highBit;

        table->decodeTable[i].symbol = sym;
        table->decodeTable[i].nbBits = (uint8_t)nbBits;
        table->decodeTable[i].newStateBaseline =
            (uint16_t)((stateVal << nbBits) - tableSize);
    }
}

/* ---- FSE 编码（反向遍历） ---- */
static size_t FSE_encode(void* dst, size_t dstCapacity,
                          const uint8_t* src, size_t srcSize,
                          const FSE_Table* table)
{
    BitWriter bw;
    BW_init(&bw, dst, dstCapacity);

    unsigned state = (unsigned)(1u << table->tableLog);
    /* 初始化状态 */
    uint8_t firstSym = src[srcSize - 1];
    /* 简化：找到符号在表中的第一个位置作为初始状态 */
    for (unsigned i = 0; i < (1u << table->tableLog); i++) {
        if (table->symbolTable[i] == firstSym) {
            state = i;
            break;
        }
    }

    /* 反向编码所有符号（跳过最后一个，已用于初始化） */
    for (size_t idx = srcSize - 1; idx > 0; idx--) {
        uint8_t symbol = src[idx - 1];

        /* 找到当前状态对应的编码信息 */
        unsigned tableSize = 1u << table->tableLog;
        unsigned nbBitsOut = 0;
        unsigned threshold = tableSize;

        /* 计算需要输出的位数 */
        int16_t nc = table->normalizedCounter[symbol];
        if (nc > 0) {
            unsigned k = 0;
            unsigned v = (unsigned)nc;
            while ((1u << k) < (int)v) k++;
            unsigned maxBitsOut = table->tableLog - k;
            unsigned minBitsOut = maxBitsOut;
            if ((unsigned)(1 << k) > (unsigned)nc)
                minBitsOut = maxBitsOut + 1;

            threshold = (unsigned)nc << (maxBitsOut + 1);
            nbBitsOut = (state < threshold) ? minBitsOut : (minBitsOut + 1);
        }

        /* 输出状态低位 */
        BW_addBits(&bw, state, nbBitsOut);
        BW_flush(&bw);

        /* 查找新状态 */
        unsigned decodedState = state >> nbBitsOut;
        /* 在符号表中找对应位置 */
        unsigned count = 0;
        unsigned target = decodedState;
        for (unsigned i = 0; i < tableSize; i++) {
            if (table->symbolTable[i] == symbol) {
                if (count == target) {
                    state = i;
                    break;
                }
                count++;
            }
        }
    }

    /* 写出最终状态 */
    BW_addBits(&bw, state, table->tableLog);
    return BW_close(&bw);
}

/* ---- FSE 解码 ---- */
static size_t FSE_decode(uint8_t* dst, size_t dstCapacity,
                          const void* src, size_t srcSize,
                          size_t originalSize,
                          const FSE_Table* table)
{
    BitReader br;
    BR_init(&br, src, srcSize);

    /* 读取初始状态 */
    unsigned state = (unsigned)BR_readBits(&br, table->tableLog);

    size_t written = 0;
    while (written < originalSize && written < dstCapacity) {
        /* 解码符号 */
        FSE_DTableEntry entry = table->decodeTable[state];
        dst[written++] = entry.symbol;

        if (written >= originalSize) break;

        /* 更新状态 */
        BR_reload(&br);
        uint64_t bits = BR_readBits(&br, entry.nbBits);
        state = entry.newStateBaseline + (unsigned)bits;
    }

    return written;
}

/* ---- 演示主函数 ---- */
int main(void) {
    const char* testStr =
        "aaaaaaaaaaaabbbbbbcccddddddddddddddddeeeeeeee"
        "aaaaaaaaabbbbcccccdddddddddddddddddddeeeee"
        "aaaaaaaaaaabbbbbccddddddddddddddddddeeeeeeee";
    const uint8_t* src = (const uint8_t*)testStr;
    size_t srcSize = strlen(testStr);

    printf("=== Simple FSE Encoder Demo ===\n");
    printf("Input:  %zu bytes\n", srcSize);

    unsigned count[FSE_MAX_SYMBOL + 1];
    unsigned maxSymbol;
    FSE_countFrequencies(src, srcSize, count, &maxSymbol);

    FSE_Table table;
    table.tableLog = 6;
    table.maxSymbol = maxSymbol;
    FSE_normalizeCount(table.normalizedCounter, table.tableLog,
                        count, srcSize, maxSymbol);
    FSE_buildSymbolTable(&table);
    FSE_buildEncodeTable(&table);
    FSE_buildDecodeTable(&table);

    uint8_t compressed[4096];
    size_t compSize = FSE_encode(compressed, sizeof(compressed),
                                  src, srcSize, &table);
    printf("Compressed: %zu bytes (ratio: %.2f:1)\n",
           compSize, (double)srcSize / compSize);

    uint8_t decompressed[4096];
    size_t decSize = FSE_decode(decompressed, sizeof(decompressed),
                                 compressed, compSize, srcSize, &table);
    printf("Decode: %s\n",
           (decSize == srcSize && memcmp(src, decompressed, srcSize) == 0)
           ? "PASSED" : "FAILED");

    double entropy = 0.0;
    for (unsigned s = 0; s <= maxSymbol; s++) {
        if (count[s] > 0) {
            double p = (double)count[s] / srcSize;
            entropy -= p * log2(p);
        }
    }
    printf("Theoretical minimum: %.1f bytes (entropy: %.3f bits/symbol)\n",
           entropy * srcSize / 8.0, entropy);
    return 0;
}

gcc -O2 -o fse_demo fse_demo.c -lm
./fse_demo

# 内核配置
CONFIG_KERNEL_ZSTD=y
CONFIG_RD_ZSTD=y

# Btrfs 文件系统压缩
mount -o compress=zstd:3 /dev/sda1 /mnt

# SquashFS（Ubuntu 22.04+ 默认使用 zstd）
mksquashfs /source /output.sqfs -comp zstd -Xcompression-level 15

CREATE TABLE logs (
    id BIGINT AUTO_INCREMENT PRIMARY KEY,
    timestamp DATETIME NOT NULL,
    message TEXT
) ENGINE=InnoDB COMPRESSION='zstd';

// RocksDB 配置 zstd 压缩
rocksdb::Options options;

// 分层压缩策略：L0-L1 用 lz4（快速），L2+ 用 zstd（省空间）
options.compression_per_level = {
    rocksdb::kLZ4Compression,      // L0
    rocksdb::kLZ4Compression,      // L1
    rocksdb::kZSTD,                // L2
    rocksdb::kZSTD,                // L3
    rocksdb::kZSTD,                // L4
    rocksdb::kZSTD,                // L5
    rocksdb::kZSTD                 // L6
};

// 最底层使用字典压缩
options.bottommost_compression = rocksdb::kZSTD;
options.bottommost_compression_opts.max_dict_bytes = 16384;
options.bottommost_compression_opts.zstd_max_train_bytes = 1048576;
options.bottommost_compression_opts.enabled = true;

/* 错误：每次都创建和销毁上下文（频繁 malloc/free） */
void compress_bad(const void* src, size_t srcSize) {
    ZSTD_CCtx* ctx = ZSTD_createCCtx();
    ZSTD_compress(/* ... */);
    ZSTD_freeCCtx(ctx);
}

/* 正确：复用上下文，预分配输出缓冲区 */
void compress_good(ZSTD_CCtx* ctx, void* dst, size_t dstCap,
                    const void* src, size_t srcSize) {
    size_t rc = ZSTD_compressCCtx(ctx, dst, dstCap, src, srcSize, 3);
    if (ZSTD_isError(rc)) {
        fprintf(stderr, "zstd error: %s\n", ZSTD_getErrorName(rc));
    }
    /* 上下文自动重置，内部缓冲区被复用 */
}