压缩算法入门

本文将简要地介绍三种著名的压缩算法：游程长度编码、LZ77编码和Huffman编码。这三种算法易于理解，易于实现，即便是没有任何编程经验的人，也能轻易地理解其中的思想。对于每种压缩算法，本文均提供了相应的压缩和解压缩代码供读者参考。

0.约定和注意事项
本文的数据类型采用“符号+位宽”的表示方式。例如，8位无符号整数类型表示为u8，32位有符号整数类型表示为s32。
本文提供的算法压缩效果并不会非常好，且在某些地方会采用非直观的实现方式。原因会在文章最后说明。
每种算法的压缩后数据的前四字节用于存储压缩头。压缩头的高24位指示原始数据的大小size，低8位用于存储压缩算法的相关属性attr。对于attr，高4位指示采用何种压缩算法（LZ77：1，Huff：2，RL：3），低4位指示Huff算法一次性应当写入多少位。
压缩函数返回压缩后数据的大小，解压缩函数返回原始数据的大小。
两个宏，会在压缩函数中使用：
#define IS_IN_RANGE(p) (p < src + src_size)
#define CHECK_IN_RANGE(p) if (!IS_IN_RANGE(p)) break
本文提供的代码仅适用于32位环境，不要尝试将其用64位编译器编译。代码在以下编译器中编译通过：
tcc version 0.9.27 (i386 Windows)
gcc (MinGW.org GCC-6.3.0-1) 6.3.0
gcc (MinGW-W64 i686-ucrt-mcf-dwarf, built by Brecht Sanders) 13.2.0
不确保提供的代码没有bug。仅测试了一个helloworld的EXE程序以及一张png图片。

1.游程长度编码
游程长度编码是一种非常简单的压缩算法，它基于一个非常朴素的想法，即：将重复的连续字节用“长度+单个字节”的方式来表示。譬如，aaabbbbbb可以压缩为3a6b。
这种算法是如此简单，以至于它经常会在高中的VB程序填空题中出现。故而，我们不在这里浪费过多口舌。
接下来我们来实现一个简单的RLComp和RLUnComp。
假如我们用一字节表示长度，然后用接下来的一字节表示数据，这显然不太妥当。当大量连续数据并不重复时，这样操作未免过于浪费空间，压缩率直逼200%。
因此，不妨用一个bit来表示我们接下来是要写重复的数据还是不重复的数据，然后用剩下的7个bit来表示长度。这样虽然在一定程度上减少了允许最大长度，但是有效地避免了前一种方法会出现的弊端。
能否把最大长度127再增大一点呢？由于不重复数据最小长度是1，并且我们可以规定重复数据的最小长度为3，那么我们把最小长度存为0，并在解压时再加上最小长度，如此这般，我们便可以略微增大最大长度。
基于上述说明，我们可以很容易地写出以下代码：
解压缩函数