13、位操作与压缩：用位运算实现游程编码(RLE)的变体
说到数据压缩，很多人第一反应是那些高大上的算法——LZ77、霍夫曼编码、算术编码。但在嵌入式世界里，尤其是资源受限的MCU上，这些算法往往太重了。你想想看，一个只有几KB RAM的单片机，跑个解压库都费劲。
这时候，游程编码（RLE）就派上用场了。它简单、高效，而且——嗯，这正是我们今天要聊的重点——可以用位运算玩出很多花样来。
13.1 经典RLE的痛点
先回顾一下标准RLE的原理：遇到连续重复的字节，就记录「重复次数+数据值」。比如 0xAA 0xAA 0xAA 0xAA 0xAA 压缩成 0x05 0xAA。
听起来挺美好，但实际用起来有几个坑：
- 标志位开销：需要额外一个字节来区分「原始数据」和「压缩对」
- 阈值问题：重复次数少于3次时，压缩反而更占空间
- 位宽浪费：很多传感器数据、图像数据，有效位宽只有4位或2位，用8位存太奢侈
我在项目中遇到过这样一个场景：采集一个12位ADC的数据，连续采样时低4位几乎不变，高8位在缓慢漂移。如果用标准RLE，每个样本都要占2字节，压缩率惨不忍睹。
核心思路：RLE的变体，本质上是在「如何编码重复信息」上做文章。位运算给了我们一把手术刀，可以精确地切分、重组、标记数据。
13.2 位级RLE变体：按位游程编码
说白了，就是把游程编码的单位从「字节」降到「位」。对于二值图像、位图字体、状态机日志这类数据，效果出奇的好。
举个例子：一个8x8的像素图案，全是黑白两色。用字节存要64字节，但用位存只需要8字节。如果再跑一遍RLE呢？
// 按位游程编码：对位流进行RLE
// 输入：src - 原始位数据，bit_len - 总位数
// 输出：dst - 压缩后的数据流
// 返回：压缩后的字节数
int rle_bits_encode(const uint8_t *src, int bit_len, uint8_t *dst) {
int src_idx = 0; // 当前处理的位索引
int dst_idx = 0; // 输出缓冲区索引
int run_len; // 当前游程长度
while (src_idx < bit_len) {
// 获取当前位的值（0或1）
uint8_t cur_bit = (src[src_idx / 8] >> (7 - (src_idx % 8))) & 1;
// 统计连续相同位的长度
run_len = 0;
while (src_idx < bit_len) {
uint8_t bit = (src[src_idx / 8] >> (7 - (src_idx % 8))) & 1;
if (bit != cur_bit) break;
run_len++;
src_idx++;
}
// 编码：高1位存位值，低7位存长度（最大127）
// 如果长度超过127，拆分成多个编码对
while (run_len > 0) {
int chunk = (run_len > 127) ? 127 : run_len;
dst[dst_idx++] = (cur_bit << 7) | (chunk & 0x7F);
run_len -= chunk;
}
}
return dst_idx;
}个人经验：我习惯把位值放在最高位，长度放在低7位。这样解码时只需要一次移位和一次掩码操作，效率极高。曾经在一个SPI闪存的日志系统中用这个方案，把存储寿命延长了3倍。
13.3 半字节RLE：4位游程编码
很多嵌入式数据天然就是4位对齐的——比如颜色索引、音频采样值的低4位、传感器数据的差值。这时候用半字节RLE，压缩率能再上一个台阶。
编码格式设计：
| 字节值 | 含义 |
|---|---|
| 0x00 - 0x7F | 原始半字节数据（低4位有效） |
| 0x80 - 0xFF | 游程编码对：高4位为重复次数，低4位为数据值 |
你看，这里用最高位作为标志位。0x00-0x7F表示原始数据，0x80-0xFF表示压缩对。解码时只需要检查最高位：
// 半字节RLE解码
// 输入：src - 压缩数据，src_len - 压缩数据长度
// 输出：dst - 解压后的半字节数组
// 返回：解压出的半字节个数
int rle_nibble_decode(const uint8_t *src, int src_len, uint8_t *dst) {
int dst_idx = 0;
for (int i = 0; i < src_len; i++) {
uint8_t byte = src[i];
if (byte & 0x80) {
// 压缩对：高4位是重复次数，低4位是数据
int count = (byte >> 4) & 0x07; // 实际只有3位表示次数（1-8）
uint8_t value = byte & 0x0F;
// 注意：count=0表示重复1次，count=7表示重复8次
for (int j = 0; j <= count; j++) {
dst[dst_idx++] = value;
}
} else {
// 原始数据：直接输出低4位
dst[dst_idx++] = byte & 0x0F;
}
}
return dst_idx;
}避坑指南：我曾经在这个设计上栽过跟头——用3位表示重复次数（1-8），结果遇到连续9个相同半字节时，编码效率反而下降。后来我改成用4位表示次数（1-16），虽然压缩对占用了0x80-0xFF全部空间，但实际测试下来整体压缩率提升了12%。
13.4 差分RLE：专治缓慢变化的数据
还记得我前面提到的12位ADC数据吗？连续采样时，相邻样本的差值往往很小。这时候可以先做差分，再对差值做RLE。
差分RLE的编码流程：
- 计算相邻样本的差值（delta）
- 如果差值为0，启动游程计数
- 如果差值非零，输出「游程长度+差值」对
// 差分RLE编码（针对16位数据）
// 输入：src - 原始16位数据数组，count - 样本个数
// 输出：dst - 压缩后的字节流
// 返回：压缩后的字节数
int delta_rle_encode(const uint16_t *src, int count, uint8_t *dst) {
int dst_idx = 0;
int run_len = 0;
int16_t prev = src[0];
// 先输出第一个原始值
dst[dst_idx++] = (prev >> 8) & 0xFF;
dst[dst_idx++] = prev & 0xFF;
for (int i = 1; i < count; i++) {
int16_t delta = src[i] - prev;
prev = src[i];
if (delta == 0) {
run_len++;
} else {
// 输出之前的游程（如果有）
if (run_len > 0) {
// 用两个字节编码游程：0xFFFF + 长度
dst[dst_idx++] = 0xFF;
dst[dst_idx++] = run_len & 0xFF;
run_len = 0;
}
// 输出差值（用1或2字节，取决于范围）
if (delta >= -128 && delta <= 127) {
dst[dst_idx++] = (uint8_t)(delta & 0xFF);
} else {
dst[dst_idx++] = 0xFE; // 扩展标志
dst[dst_idx++] = (delta >> 8) & 0xFF;
dst[dst_idx++] = delta & 0xFF;
}
}
}
// 处理末尾的游程
if (run_len > 0) {
dst[dst_idx++] = 0xFF;
dst[dst_idx++] = run_len & 0xFF;
}
return dst_idx;
}实际效果：在一个温度采集项目中，原始数据每样本2字节，1000个样本就是2KB。用差分RLE压缩后，平均只有300-400字节。压缩率超过80%。而且解压代码只有几十行，跑在Cortex-M0上毫无压力。
13.5 混合模式：自适应RLE变体
没有一种RLE变体是万能的。我个人的做法是：在编码时尝试多种模式，选择压缩率最高的那个，然后把模式标记写在头部。
比如这样设计头部字节：
| 位[7:6] | 模式 | 说明 |
|---|---|---|
| 00 | 原始数据 | 未压缩，直接存储 |
| 01 | 字节级RLE | 标准RLE，适合重复字节多的数据 |
| 10 | 半字节RLE | 适合4位对齐的数据 |
| 11 | 差分RLE | 适合缓慢变化的数据 |
解码器先读头部，根据模式选择对应的解码函数。这样一套框架下来，无论遇到什么类型的数据，都能找到最优的压缩方式。
我的建议：别在一开始就追求完美。先实现最简单的字节级RLE，跑通流程。然后根据实际数据的特征，逐步加入变体。我在一个项目里就是这样迭代了3个版本，最终压缩率从30%提升到了75%。
13.6 本章小结
位操作和RLE的结合，说白了就是「用位运算的精度，去匹配数据的冗余特征」。按位RLE适合二值数据，半字节RLE适合4位数据，差分RLE适合缓慢变化的数据。每种变体都有自己的适用场景，没有银弹。
嗯，最后提醒一句：压缩算法一定要做边界测试。我曾经在测试时发现，全0数据和全1数据的压缩率天差地别——有些变体对全0数据压缩率极高，但对全1数据反而膨胀。所以，了解你的数据特征，比了解算法本身更重要。