简介用C语言实现的RLE行程长度编码源码资源面向计算机专业学生、算法初学者以及需要快速理解无损压缩原理的开发者。工程基于Code::Blocks搭建共5个文件、压缩包仅10KB包含C源码、工程配置、编译中间文件与可执行程序打开即可查看或直接运行验证。RLE算法通过记录连续重复字符及其次数实现压缩例如将AAABBBCCCCCC表示为3A3B6C适用于位图和纯文本等含大量连续重复数据的场景。源码注释完整按读取输入、动态数组初始化、压缩计数、不同字符切换以及末尾处理等步骤组织同时给出对应的解压逻辑描述中还说明了RLE对随机非重复数据压缩效果有限并引出LZ77、Huffman等更高级算法帮助读者建立压缩算法的横向认识。目前已有2026人学习下载适合用作算法课程实验、期末设计或入门研究的小型参考工程。1. 为什么现在还值得用 C 手写一个 RLE 压缩算法RLE压缩算法C语言实现看起来像是教科书里的课后题但真正动手写过一遍的人会告诉你这个“简单算法”在编码格式、边界处理和文件模式上藏着一堆能让你调试到怀疑人生的坑。最典型的一次经历某块嵌入式显示控制板上内存按 KB 计算要压缩一屏色块位图主流压缩库一个都塞不进去最后用了几十行 RLE把大面积同色字节压到接近原来十分之一的体积代价只是几个字节的栈空间。RLE游程编码做的事情很朴素把连续重复的字节记录成“长度 值”一次遍历完成压缩和解压没有哈希表、没有动态内存分配、没有复杂状态机。它适合位图色块、传真数据、简单波形和低色彩深度的嵌入式画面不适合照片噪声、加密数据这类几乎不重复的输入。下面从数据格式设计开始把编码器、解码器、边界坑和验证方法一次讲透读完你就能照着写出一份能直接落地的 C 版本。2. RLE 数据格式怎么定控制字节、游程长度与压缩率边界2.1 游程的本质什么时候 RLE 有效什么时候它在制造膨胀游程就是连续相同的字节序列。RLE 的核心假设是数据里存在大量长游程压缩时把每个游程换成一个短记录压缩率的高低完全取决于游程平均长度与记录长度的比例。设数据里有 k 个游程平均游程长度为 L原始数据大小约等于 k × L用最朴素的“长度 值”方式记录每个游程需要 2 个字节压缩率约等于 2 / L。当平均游程长度 L 100 时压缩率接近 2%效果可观当 L 1 时压缩率等于 2数据反而膨胀一倍。这个模型能解释为什么 RLE 在二值图像和传真数据上表现极好一长串 0x00 或 0xFF 就是天然的长游程。而在随机数据上相邻字节相同的概率只有 1/256平均游程长度趋近于 1直接把每个字节都包上一层记录体积立刻翻倍。常见误区就是把 RLE 当通用压缩器来用拿到日志文本、结构化二进制流上来就压结果发现越压越大这不是实现的问题是选型的问题。判断一份数据适不适合 RLE我一般先做一次采样统计随机抽 1 KB 数据数一数连续重复长度大于等于 3 的片段占比。如果这类片段的字节数超过总字节数的三成RLE 值得一试如果几乎找不到重复段趁早换方案别浪费时间调参。RLE 是“针对性压缩”不是“万能压缩”这个认知能帮你避开后续一多半的坑。2.2 选一个不会踩坑的编码格式控制字节方案与格式表直接使用“长度 值”二元组是最原始的做法但对不重复的数据段会立刻失效。比如一段交替变化的数据 0x01 0x02 0x03 0x01 0x02 0x03每个字节都自成一个游程压缩后会输出 6 组“长度 值”体积翻倍还没换来任何压缩收益。常见做法是引入一个控制字节区分“重复游程”和“普通字面量”两种场景让不重复的数据能原样存放只付出一个控制字节的代价。我采用的格式是每个数据块以 1 字节控制头开始。控制字节的最高位bit7标记块类型低 7 位存放长度 n。n 的取值范围是 1 到 1270 被保留为非法值用来在解码时识别损坏数据。bit7 为 1 时表示这是重复游程控制字节后面紧跟 1 个字节的重复值解码时把这 1 个字节扩展成 n 份bit7 为 0 时表示这是字面量块控制字节后面紧跟 n 个原始字节解码时原样拷贝。控制字节 bit7低 7 位含义后续数据典型场景1游程长度 n1~1271 字节重复值连续重复段如大块同色像素0字面量长度 n1~127n 字节原始数据不重复的一般数据段最低控制在 127 而不是 255是因为低 7 位最多只能表达 127。9 位甚至变长编码能提高上限但会引入移位和分支复杂度对一个目标在嵌入式环境下运行几十行代码的算法来说不划算。这个设计与多种位图压缩方案同源实践经验足够多照抄不会踩格式设计的坑。字面量块的性价比也很清晰最多每 127 个字节多花 1 个控制字节膨胀率约 0.8%比朴素方案强得多。3. 编码器实现C 语言游程识别、字面量分组与缓冲管理3.1 三个关键参数和对外接口编码器有 3 个关键参数需要先定下来RLE_MIN_RUN 是触发游程压缩的最小重复长度我默认设 3。理由是一个重复游程在输出时至少需要“控制字节 值”2 个字节如果只重复 2 次输出和原始大小打平没有收益还增加了解码负担。RLE_MAX_LEN 是单块最大长度等于 127对应控制字节低 7 位的上限。第三个是输出缓冲策略由调用方提供一块预先分配好的内存编解码全程不做 malloc这是让 RLE 能跑在裸机环境的关键。对外接口只需要一个函数原型输入原始数据指针和长度输出压缩后数据指针和缓冲容量返回实际写入的压缩字节数。size_t rle_encode(const uint8_t *src, size_t src_len, uint8_t *dst, size_t dst_cap);返回值是压缩后字节数调用方在编码前要保证 dst 足够大。最保守的估算是 2 × src_len 16因为即使每个输入字节都输出一个“控制字节 值”的记录也不会超过这个量。实际操作中我一般按 2 倍原大小分配临时缓冲反正栈上给一个 4 KB 数组也就一两美元的成本。3.2 编码主循环阈值、边界与代码逐段说明#include stdint.h #include stddef.h #define RLE_MIN_RUN 3 #define RLE_MAX_LEN 127 typedef struct { uint8_t *dst; size_t cap; size_t len; int failed; } RleOut; static void out_put(RleOut *o, uint8_t v) { if (o-len o-cap) { o-failed 1; return; } o-dst[o-len] v; } static size_t count_run(const uint8_t *src, size_t len, size_t pos) { size_t n 1; while (pos n len src[pos n] src[pos] n RLE_MAX_LEN) { n; } return n; } size_t rle_encode(const uint8_t *src, size_t src_len, uint8_t *dst, size_t dst_cap) { RleOut o { dst, dst_cap, 0, 0 }; size_t i 0; while (i src_len !o.failed) { size_t run count_run(src, src_len, i); if (run RLE_MIN_RUN) { out_put(o, (uint8_t)(0x80 | run)); out_put(o, src[i]); i run; } else { size_t lit_start i; size_t lit_len 0; while (i src_len lit_len RLE_MAX_LEN) { size_t nr count_run(src, src_len, i); if (nr RLE_MIN_RUN) { break; } lit_len; i; } out_put(o, (uint8_t)lit_len); while (lit_len 0) { out_put(o, src[lit_start]); lit_start; lit_len--; } } } return o.failed ? 0 : o.len; }count_run 函数负责统计从 pos 开始的连续重复长度上限强制压到 127。为什么要在这里限制而不是等到输出时才判断因为如果放任 run 超过 127后续写入控制字节时低 7 位会被截断轻则压缩数据损坏重则解码错位。限制后主循环每次 i run天然把超长游程切成多段输出。主循环的分支选择是核心逻辑。先对当前位置计算 run如果 run RLE_MIN_RUN说明这里是值得压的重复段直接输出“0x80 | run”和重复值如果 run 小于阈值就进入字面量收集分支。字面量收集会从当前点开始逐个字节往后走直到遇到一个“从该位置起游程足够长”的断点或者收集满 127 个字节。外层每次遍历都会调用 count_run 检查当前位置内层字面量扫描也会调用 count_run 判断断点同一个字节最多被统计两次整体复杂度仍然是 O(n)。我曾见过有人在这里用内层循环逐字节对比来追踪断点结果复杂度退化到 O(n²)数据量一大就卡死。与其做这种“优化”不如保持 count_run 的单纯职责可读性和性能都更好。4. 解码器实现受控遍历、越界检查与错误返回约定4.1 解码主循环代码与两种分支的处理#include string.h size_t rle_decode(const uint8_t *src, size_t src_len, uint8_t *dst, size_t dst_cap) { size_t si 0; size_t di 0; while (si src_len) { uint8_t ctrl src[si]; size_t n ctrl 0x7F; if (n 0) { break; } if (ctrl 0x80) { if (si src_len) break; if (di n dst_cap) break; uint8_t v src[si]; for (size_t k 0; k n; k) { dst[di] v; } } else { if (si n src_len) break; if (di n dst_cap) break; memcpy(dst di, src si, n); si n; di n; } } return di; }解码器比编码器短但边界检查一个都不能少。读取控制字节后立刻拆出 n先判断 n 是否为 0。格式定义里 n 不允许为 0出现 0 说明数据损坏或格式不匹配此时直接停止解码防止后续 while(n--) 这类写法陷入死循环。游程分支处理重复段先确认 src 里还有值可取再确认目标缓冲剩余空间足够容纳 n 个字节最后用一个循环把值填充 n 次。字面量分支更简单确认 src 剩余数据足够 n 字节确认 dst 剩余空间足够然后用 memcpy 一次性搬过去。两个分支都做的是同一件事先检查后写入。我用 si 和 di 两个下标分别追踪输入和输出位置任何一次检查失败就 break 并返回已解码的字节数。这个设计让解码器永远不会越界读写即使在数据结构损坏的情况下最多也就是返回一个比预期短的长度不会造成段错误式崩溃。4.2 解码失败判定调用方如何知道数据已损坏解码器的返回值是实际写入 dst 的字节数。调用方在解压前通常知道原始数据的长度比如从文件头记录的原大小字段里读到那么只需比较返回值是否等于预期长度size_t need rle_decode(comp, comp_len, raw, raw_cap); if (need ! expected_len) { fprintf(stderr, decode failed: %zu ! %zu\n, need, expected_len); return -1; }这种约定操作简单不需要额外的错误码枚举但有一个局限如果压缩数据被篡改解码过程碰巧在错误位置生成了长度一致的数据这种检查检测不出来。对大多数存储和传输场景长度校验已经足够因为编码格式的每个块都自带长度数据错位通常会迅速导致长度不匹配或者 n 0 的非法块。如果追求更严格的保护可以在数据格式外层追加一个校验字段比如对原始数据做简单的异或校验或 CRC 校验。RLE 本身不负责完整性把校验放在调用方是常见做法也是这个算法保持简洁的前提。解码器只承诺两件事不越界、长度精确其他完整性职责交给上层。5. RLE 实现避坑指南5 个让压缩器翻车的边界场景5.1 压缩后体积反而膨胀问题不一定在算法现象对一段随机生成的数据做压缩测试输出字节数竟然比输入还多立刻怀疑编码器写错了。原因RLE 对随机数据的膨胀是数学上注定的结果不是 bug。随机数据几乎没有连续重复编码器的字面量分支里每个数据块还要额外花 1 个控制字节输出自然略大于输入。解决先统计数据的游程占比再做选型决定。如果必须在压缩率和体积膨胀之间做出权衡可以把 RLE_MIN_RUN 从 3 调到 4 或 5阈值越高字面量块越不容易被拆散抗膨胀能力越强代价是会漏掉一些短游程的压缩机会。另一个实用做法是让调用方保留“压缩失败就存原数据”的逃生通道在数据流开头用一个标志位区分压缩数据与原始数据。5.2 连续 300 个相同字节怎么编码127 上限与自动分段现象输入一段连续 300 个 0x00 的数据编码结果是 3 段游程但一次粗心实现里直接写了 run 字段结果高位置溢出解出来的数据变成几段错位的乱码。原因控制字节低 7 位只容得下 127300 这个值一塞进去就会被截断这不是运行时才暴露的 bug而是格式设计层面不允许的事情。解决count_run 函数把返回值强行限制在 127主循环里每输出一段游程就 i run然后重新从新的位置开始计数。300 个 0x00 会依次编码成 127 127 46 三段对应输出 FF 00 FF 00 AE 00解码器按规则逐个还原结果与原始数据完全一致。5.3 解码越界崩溃一切先从检查剩余长度开始现象拿一段手工构造的损坏压缩数据去解压程序直接段错误回头检查发现字面量块声称要拷贝 100 字节但 src 指针后面只剩 3 个字节。原因解码器盲目信任了输入的长度字段。RLE 数据在传输或存储过程里可能被截断、被写坏控制字节里的长度值完全可能失真解码器必须把输入当成不可信任的数据来对待。解决每个分支在写入前都检查 si n 是否超过 src_len、di n 是否超过 dst_cap任何一个检查失败就立刻停止并返回当前已解码长度。不要用“反正数据是我自己编的不会坏”这种心态写代码解码器能扛住脏数据才是真正能交付的代码。5.4 二进制文件被文本模式打开0x1A 与 CRLF 的隐形破坏现象在 Windows 上把一段 RLE 数据写入文件再读回来解压结果末尾缺失或者数据中间多出了 0x0D。压缩和解压的缓冲区看起来都没问题换了台 Linux 机器却一切正常。原因fopen 用了文本模式而不是二进制模式。文本模式下写入时 0x0A 会被替换成 0x0D 0x0A读取时 0x1A 会被当作文件结束符提前截断。RLE 压缩数据是纯二进制流0x0A、0x1A 这类字节随时可能出现文本模式一介入数据就面目全非。解决读写文件统一用二进制模式没有例外。FILE *fp fopen(data.rle, wb); /* 读入用 rb */ if (fp NULL) { perror(fopen); return -1; } fwrite(comp, 1, comp_len, fp); fclose(fp);这个坑在 Linux 上根本不存在因为文本模式和二进制模式没有区别所以特别容易在跨平台移植时突然爆发。我的习惯是只要文件内容不是纯 ASCII 文本一律用 “rb”/“wb”。5.5 把字节流当字符串strlen 与 0x00 的经典误用现象压缩数据的长度算得不准有时压缩后存的文件能解压有时存的文件解出来只有原来的一半。调试半天发现数据里出现了 0x00 字节。原因代码里用了 strlen 求长度或者用 strcpy 拷贝数据。strlen 遇到第一个 0x00 就停止计数二进制数据里 0x00 是再普通不过的字节值字符串函数拿它一点办法都没有。解决所有数据操作都依赖显式的长度参数不要依赖任何以 NUL 结尾的字符串函数。memcpy、fread、fwrite 这类函数天生适配二进制流唯一的责任是把长度参数传对。写 RLE 这类算法时从第一步就把输入输出统一抽象成“指针 长度”后面能少掉一大半晦涩的 bug。6. 进阶互逆测试、阈值调优与一次压缩率翻车教训6.1 先写 roundtrip 测试再谈压缩率拿到一个刚写完的 RLE 编解码器第一件事不是看压缩率而是做互逆测试编码再解码逐字节比对结果。我一般会构造几类固定用例空输入、全同数据、长度恰好 127 和 128 的数据、随机数据、随机数据中间插入几个长游程。每一类都验证两个方向——既能正确压缩也能正确还原。static int roundtrip(const uint8_t *src, size_t n) { uint8_t comp[4096]; uint8_t raw[4096]; size_t comp_len rle_encode(src, n, comp, sizeof(comp)); if (comp_len 0 n 0) return 0; size_t raw_len rle_decode(comp, comp_len, raw, sizeof(raw)); return raw_len n memcmp(src, raw, n) 0; }测试缓冲大小需要按源数据长度预留示例里固定 4096 字节够覆盖大部分单元测试。互逆测试全部通过之后再去统计压缩率才有意义否则一个连还原都做不到的压缩器压缩率再好看也是空中楼阁。6.2 阈值不是固定值按数据特征调RLE_MIN_RUN 默认 3但具体项目里值得按数据形态重新调。针对一屏色块位图游程动辄几十上百个字节把阈值调到 8 或 16 可以避免那些“刚好重复 3 次”的短片段被拆成两段记录减少控制字节的开销。针对日志或波形数据重复段普遍较短阈值设 3 更合适能捕捉更多压缩机会。最笨但最可靠的办法是写个脚本测几组阈值对比压缩字节数再选。6.3 一次把 RLE 用在文本日志上的教训我犯过的典型错误是把 RLE 直接压在文本日志上结果压缩率几乎等于 1完全没有收益。当时没做数据特征分析就动手事后才意识到日志行首的时间戳前缀几乎不重复行内内容也因为混入变量而很难出现长游程。后来改成先按语义分字段、把重复率高的列单独拆出来再走 RLE才终于有了可见的压缩效果。这让我养成了一个习惯任何数据压缩方案上脑之前先问一句“这份数据里到底有没有值得压的规律”没有就直接换方案。希望帮到你。本文还有配套的精品资源点击获取