xtellect/fc Source: https://github.com/xtellect/fc # fc — Floating-Point Compressor Copyright (c) 2026 Praveen Vaddadi Licensed under the Apache License, Version 2.0. See LICENSE and NOTICE. fc 是一个针对 IEEE-754 64位双精度浮点数流（doubles）的无损压缩器。它将输入数据划分为自适应大小的块（quanta），在每个块上运行多种专用编解码器之间的竞争，并输出结果最小的那个。压缩和解压缩均使用 POSIX 线程实现多线程，且热路径已针对 x86-64 架构手动向量化（支持 AVX2 + SSE4.2 + BMI + LZCNT）。当前版本字符串为 fc 1.56（参见 fc.c 中的 fc_ver）。 ## 代表性数据 以下数据来自捆绑的 test_fc 测试框架在 17 个合成数据集上的聚合结果，每个数据集包含 1 Mi 个双精度浮点数（每个数据集 8 MiB，总计 ≈136 MiB / 142.6 MB 十进制），每个数据集取 5 次试验的中位数，使用 8 个编码线程，解码线程自动选择，测试环境为维护者的 x86-64 + AVX2 机器。“Ratio”列表示 total_original / total_compressed；吞吐量列为每个数据集 MB/s 的调和平均值。数据直接来自 test_fc.csv，在不同硬件上会有所变化——请重新运行 make test 以生成最新数据。 | Codec | Ratio | Encode (MB/s) | Decode (MB/s) | | ———– | —–: | ————: | ————: | | fc | 3.07 | 120 | 1277 | | zstd -3 | 2.07 | 528 | 1556 | | zstd -9 | 2.09 | 111 | 1572 | | fpzip | 1.71 | 123 | 121 | | lz4hc -9 | 1.69 | 51 | 5835 | | gorilla | 1.66 | 683 | 971 | | lz4 | 1.62 | 2176 | 5353 | 核心要点： fc 是本基准测试中体积压缩比最佳的浮点数压缩器，但并非综合性能最佳的全能压缩器。 它在 17 个数据集中的 10 个上直接胜出（压缩比最高），且在任何数据集上排名从未低于第三名。 fc 表现优异（通常大幅领先）的场景： - 结构化/分析型浮点数——常数序列 ≈ 39,756×（对比 zstd-9 ≈ 11,619×），抛物线序列 ≈ 2,973×（对比 2.5×），整数×1000 ≈ 5,388×（对比 4.3×），分段函数 ≈ 26.8×（对比 14.9×），股票数据 ≈ 15.6×（对比 7.1×）。 - 周期/准周期信号——低频正弦波、音频混合、AR2阻尼信号，以 1.3×–2.7× 的压缩比击败 gorilla 和 fpzip。 - 解码速度快且并行化（fc_dec 内部自动多线程）：聚合吞吐量 ≈ 1.28 GB/s，比编码快约 10 倍，比 fpzip 快约 10 倍，比 gorilla 快约 1.3 倍，达到 zstd-3 解码速度的 ~80%。非常适合“一次写入、多次读取”的时间序列存储。 fc 表现劣势的场景： - 对字节模式友好的量化数据——zstd 在 decimal-cents（zstd-9 ≈ 3,465× vs fc 268×）、dict-16（zstd-9 ≈ 10,268× vs fc 4,660×）和 quantized-4lvl（zstd-9 ≈ 9,675× vs fc 1,037×）上胜出。通用 LZ 算法能捕捉到 fc 当前未建模的结构。 - 噪声自然浮点数组——fpzip 在 random-walk（1.39 vs 1.38）、climate（1.395 vs 1.380）、geo-coords（2.012 vs 2.000）和 sensor-noisy（1.397 vs 1.386）上略胜一筹。差异虽小但一致。 - 编码吞吐量——聚合吞吐量 ~120 MB/s。模式竞争机制带来了更高的压缩比，代价是编码器 CPU 开销。如果编码是瓶颈，lz4（~2.2 GB/s）或 zstd-3（~530 MB/s）更具优势。 - 伪随机数据——压缩比 ≈ 1.000。与其他所有无损编解码器相同；fc 只是不浪费头部开销。 硬性约束： 仅支持无损压缩（无量化）。编码器接收 8 字节对齐的输入（8 字节的倍数）；启发式方法和大多数模式针对 IEEE-754 双精度位模式进行了优化，因此其他 8 字节负载也能压缩，但你可能无法获得最佳压缩比。需要支持 AVX2 + SSE4.2 + BMI + LZCNT 的 x86-64 处理器。 经验法则： - 希望获得最小的浮点数流文件，且关注解码侧延迟 → 选择 fc。 - 异构数据且编码速度是瓶颈 → 选择 zstd 或 lz4。 - 噪声科学数组，每个字节都很关键 → 在您的数据上对 fc 和 fpzip 进行基准测试；它们彼此差距约 1%。 ## 状态 这是一个研究级的单文件库。磁盘格式通过流头中的魔术数字（magic number）进行版本控制；不兼容旧版本的格式更改会提升魔术数字。请将压缩输出视为不透明数据——不要依赖其内部布局。 ## 仓库结构 | 文件 | 用途 | | ———–– | ———————————————————— | | fc.h | 公共 API（编码、解码、监控计数器）。 | | fc.c | 压缩器实现。包含 ~50 个编解码器 + 分发逻辑 + 线程。 | | gorilla.h | 捆绑的 Redis “Gorilla” XOR/差值编解码器——第三方代码。 | | gorilla.c | 捆绑的 Redis “Gorilla” XOR/差值编解码器——第三方代码。 | | test_fc.c | 针对 17 个合成数据集的往返测试 + 基准测试框架。 | | Makefile | 构建 fc.o、gorilla.o 和 test_fc 基准测试程序。 | | LICENSE | Apache License 2.0（本项目自有代码）。 | | NOTICE | 归属声明和第三方许可证披露。 | | CONTRIBUTING.md | 贡献指南和 DCO。 | ## 公共 API 整个 API 都在 fc.h 中： c typedef struct { int p, t, c; } fc_cfg; size_t fc_enc(const void *src, size_t bytes, void *dst, fc_cfg cfg); size_t fc_dec(const void *src, size_t bytes, void *dst); extern const char fc_ver[]; extern unsigned long fc_dec_mode_hist[64]; extern unsigned long fc_enc_mode_time_ns[64]; extern unsigned long fc_enc_mode_calls[64]; extern unsigned long fc_enc_mode_wins[64]; void fc_dec_mode_hist_reset(void); const char *fc_mode_name(int mode); ### fc_cfg 字段 | 字段 | 含义 | | —– | –––––––––––––––––––––––––––––––– | | p | 预测表大小的 log2。在 fc_enc 内部限制在 [10, 16] 范围内。test_fc 基准测试传入 18，会被静默截断为 16。 | | t | 编码器的工作线程数。解码器不接受 fc_cfg，并通过 sysconf(_SC_NPROCESSORS_ONLN) 自动选择线程数，上限为 128 且不超过每流的块数。 | | c | 保留字段。当前未使用（fc_enc 中有 (void)cfg.c;）。 | ### fc_enc(const void *src, size_t bytes, void *dst, fc_cfg cfg) 压缩 bytes 字节的输入（必须是 8 的倍数——每 8 字节一个 double）。返回写入的压缩字节数，失败则返回 0：当 src / dst 为 NULL、bytes 不是 8 的倍数，或内部分配失败时发生。目标缓冲区必须由调用者分配大小。库未公布闭式 comp_bound。捆绑的基准测试分配了 2 * bytes + 64 KiB（参见 test_fc.c），这对测试套件中的每个数据集都足够；对于任意输入，请至少分配那么多空间并检查返回值（编码器若发生溢出将返回 0 而非继续）。 ### fc_dec(const void *src, size_t bytes, void *dst) 解压由 fc_enc 生成的流。返回写入的解压缩字节数，失败则返回 0。失败条件包括：src / dst 为 NULL、头部截断、魔术数字错误、头部 predsizelg2 超出 [10, 16]、块头部声称的输入或输出超过剩余数据、总解码大小与头部记录的 original_bytes 不匹配，或内部分配失败。调用者负责根据流头部记录的原字节数对 dst 进行 sizing（可使用 fc_dec 先读取一次头部，或简单分配您压缩时的原始缓冲区长度）。 注意： 未知/未实现的模式 ID 当前不被视为硬性失败——受影响的块会静默地保留为零值。请据此对待来自不可信源的流。 ### 监控计数器 fc_*_mode_* 数组是按模式 ID 索引的 64 入口表格。它们原子更新，仅用于诊断： - fc_dec_mode_hist[m] — 以模式 m 解码的块数。 - fc_enc_mode_calls[m] — 在编码器竞争中模式 m 被评估的次数。 - fc_enc_mode_wins[m] — 模式 m 胜出并被写入的次数。 - fc_enc_mode_time_ns[m] — 评估模式 m 所累积的挂钟纳秒数。 fc_mode_name(m) 返回模式 m 的简短字符串（未使用的 ID 返回 "?"）；见下表。 ## 模式 fc 当前定义了 50 个模式 ID（使用 0–49；12、14 和 50–63 保留）。fc_mode_name 暴露的模式名称如下： 0 PRED 25 PRED2 1 CONST 26 PRED_ADAPTIVE 2 STRIDE 27 VITERBI 3 XORZ 28 DELTA_BINNED 4 LZ 29 PRED_RC 5 RAW 30 PRED_INTERLEAVED 6 FLOAT32 31 BWT 7 ORDERED_DELTA 32 LZ_DICT 8 FUZZY_STRIDE 33 CONV_N 9 ALP 34 SIGN_CONV 10 TRAILING_ZERO_BP 35 CONV_DOUBLE 11 BYTE_TRANSPOSE 36 MTF_LZ 13 XOR128 37 CONV_DOUBLE_BP 15 LSB_STRIP 38 CONV_N_BINNED 16 LOOKBACK_DELTA 39 PRED_SIMD_INTERLEAVED 17 FLOAT_MULT 40 FUZZY_STRIDE_ANS 18 FCM_RLE 41 PAQ_MIXER 19 DICT 42 PAQ4_MIXER 20 DELTA2 43 BWT_MTF_TANS 21 BITPLANE 44 PRED4 22 INT_MULT 45 DELTA_DP_BINNED 23 CONV1 46 CONV_N_DP_BINNED 24 PRED_TANS 47 ELF 48 LZ_SPLIT 49 BWT_MTF_RC 大致分组如下： - 预测器：PRED、PRED2、PRED4、PRED_TANS、PRED_RC、PRED_ADAPTIVE、PRED_INTERLEAVED、PRED_SIMD_INTERLEAVED、VITERBI、LSB_STRIP — 各种残差编码器（raw、tANS、范围编码）和 SIMD 布局的 FCM/DFCM 风格哈希预测器。 - XOR / 差值：XORZ、XOR128、LOOKBACK_DELTA、ORDERED_DELTA、DELTA2、DELTA_BINNED、DELTA_DP_BINNED。 - 常数 / 步长 / 字典：CONST、STRIDE、FUZZY_STRIDE、FUZZY_STRIDE_ANS、DICT、LZ_DICT、MTF_LZ。 - Lempel-Ziv：LZ、LZ_SPLIT。 - 浮点专用：FLOAT32、FLOAT_MULT、INT_MULT、ALP（自适应无损浮点）、ELF（擦除低位）。 - 变换：BYTE_TRANSPOSE、BITPLANE、TRAILING_ZERO_BP、SIGN_CONV、BWT、BWT_MTF_TANS、BWT_MTF_RC。 - 卷积 / 线性模型：CONV1、CONV_N、CONV_DOUBLE、CONV_DOUBLE_BP、CONV_N_BINNED、CONV_N_DP_BINNED。 - 混合器：PAQ_MIXER、PAQ4_MIXER、FCM_RLE。 - 回退：RAW。 fc.c 是每个模式实际行为的权威来源。 ## 工作原理 1. 头部。 流以一个固定大小的头部开始，包含魔术数字、原始字节数、使用的量子大小（quantum size）以及截断后的预测器 log2。 2. 块规划。 扫描并分割输入数据。默认量子大小为 256 KiB（C_QUANTUM_BYTES），但当数据看起来低熵时，探针（ceq_probe_chunk_values）可以将块大小增加到 1 MiB（C_QUANTUM_MAX_BYTES）。 3. 模式竞争。 工作线程从队列中拉取块。对于每个块，编码器评估受功能门控的子集模式（exp_range、sign_flips、distinct_count、looks_like_repeats 和当前最佳值决定哪些模式值得尝试），并保留输出最小的那个。每种模式的挂钟时间、调用次数和胜出次数记录在 fc_enc_mode_* 计数器中。 4. 发射。 每个块写入为 [1-byte mode][payload]，流中通过长度和偏移簿记，使 fc_dec 无需扫描有效负载即可找到块边界。 5. 解码。 fc_dec 遍历块索引，并将每个块的有效负载分发给匹配的编解码器。与编码类似，解码也是多线程的；fc_dec 本身自动选择工作线程数（在线 CPU 数，上限为 128 且不超过块数）。 ## 构建 bash make # 构建 fc.o, gorilla.o 和 test_fc 基准测试 make test # 运行 ./test_fc make clean ### 工具链 - C11 编译器（clang 或 gcc）。clang 是 Makefile 的默认设置。 - POSIX 线程。 - pthread 和 libm（默认链接）。 ### 必需的 CPU 特性 默认的 CFLAGS 启用 -mavx2 -msse4.2 -mbmi -mlzcnt。库直接使用这些内在函数；在没有这些特性的 CPU 上运行二进制文件将触发 SIGILL 错误。没有可移植的回退方案。 ### 可选基准测试依赖项 由 Makefile 自动检测，仅由 test_fc.c 用于并列比较——构建或使用库本身不需要它们： - libzstd（通过 pkg-config libzstd） - liblz4（通过 pkg-config liblz4） - fpzip（头文件探测 /usr/include/fpzip.h，链接 -lfpzip） ## 基准测试框架 test_fc 对每个 17 个合成生成器（常数、线性、抛物线、AR(2)阻尼、分段、整数倍数、美分小数、dict-16、低频正弦波、音频混合、随机游走、4级量化、气候、地理坐标、股票、噪声传感器、伪随机）各运行一次，每个数据集 1 Mi 个双精度浮点数（可通过 FCBENCH_N 覆盖），5 次试验取中位数，8 个编码线程（编译时 THREADS），并写出 test_fc.csv，包含与构建时检测到的可选基线（zstd、lz4、fpzip、gorilla）相比的压缩比和编码/解码吞吐量。每个数据集都检查往返正确性。输出中的 MISMATCH 行表示回归。 ## 局限性 - 仅限 x86-64；没有 ARM/NEON 路径。运行时需要 AVX2 + SSE4.2 + BMI + LZCNT。 - fc_dec 线程数自动选择，用户不可配置（解码 API 不接受 fc_cfg）。 - cfg.c 是保留字段，目前为空操作（(void)cfg.c;）。 - 编码器要求 bytes 是 8 的倍数（一个完整的双精度浮点数）。 - 预测器参数 cfg.p 会被静默截断到 [10, 16]。 - 压缩流中的未知模式 ID 不被标记为错误；受影响的块解码为零。 - 磁盘格式在主要版本之间不稳定。 ## 许可证 本项目自有代码（fc.c、fc.h、test_fc.c、Makefile、文档和构建基础设施）采用 Apache License, Version 2.0 许可。参见 LICENSE。 捆绑的文件 gorilla.c 和 gorilla.h 不 采用 Apache 2.0。它们 © Redis Ltd. 保留，并维持其原始三重许可：RSALv2、SSPLv1 或 AGPLv3（任选其一）。参见文件头部和 NOTICE 获取完整文本和归属声明。无法接受这三种许可证中任何一种的下游用户应在不包含 gorilla.o 的情况下重新构建（核心 fc 库不链接它；只有 test_fc 基准测试链接）。 ## 贡献 参见 CONTRIBUTING.md。接受对本项目自有文件的贡献，采用 Apache 2.0；请在提交时签名（git commit -s）。 ## 联系 - 维护者：Praveen Vaddadi — - 安全报告：相同地址；请勿为漏洞提交公开问题。