RLE压缩算法C语言实现：游程编码原理与嵌入式避坑指南

简介：用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 到 127，0 被保留为非法值，用来在解码时识别损坏数据。bit7 为 1 时，表示这是重复游程，控制字节后面紧跟 1 个字节的重复值，解码时把这 1 个字节扩展成 n 份；bit7 为 0 时，表示这是字面量块，控制字节后面紧跟 n 个原始字节，解码时原样拷贝。

最低控制在 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 位只容得下 127，300 这个值一塞进去就会被截断，这不是运行时才暴露的 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，才终于有了可见的压缩效果。这让我养成了一个习惯：任何数据压缩方案上脑之前，先问一句“这份数据里到底有没有值得压的规律”，没有就直接换方案。希望帮到你。

本文还有配套的精品资源，点击获取