RLE压缩解压算法

算法描述

压缩

连续重复数据

? 当压缩文件遇到一组重复数据 aaaaaaaa 时，便可将其看作8个a，将其编码为 8a，所以压缩之后就变成了[1000 1000] ['a']。

? 这里将最高位视为标志位，之后的数据为重复数据则置为1，低7位表示长度，最大位127(0x7f)，所以超过这个大小，就需要将数据截断，将之后的数据视为下一组数据。

非重复数据

? 当遇到另外一组数据 abcdefgh 时，那么此时该组数据有8个不相同的字节，类似遇到连续重复数据的方法，在该组数据前加一个长度属性字节，将其编码为 8abcdefgh，所以压缩之后就变成了[0000 1000] ['a'] ['b'] ['c'] ['d'] ['e'] ['f'] ['g'] ['h']。这里同样将8看做一个长度属性字节，该长度属性字节一共有8位，最高位为标志位，因为之后的字节为非重复字节，所以标志为0，剩余的7位用来存储长度，最大为111 1111(2^7-1 = 127 = 0x7f)，超过127对数据进行截断。

? 总结：在这两种情况下，原数据均为8个字节，所以长度均为000 1000(二进制)，再加上标志位1或0，组成长度属性字节。

解压缩

连续重复数据

? 在解压缩时，如果遇到了[1000 1000] ['a']，首先将该组数据的第一个长度属性字节sign拿出来，令sign & 0111 1111，那么得到的结果8，就是该组数据接下来字节的个数len，然后再sign & 1000 0000，得到的1即为标志位，那么接下来连续输出8个'a'，即完成了解码，所以解压之后就变成了 aaaaaaaa。

非重复数据

? 如果遇到了[0000 1000] ['a'] ['b'] ['c'] ['d'] ['e'] ['f'] ['g'] ['h']，同样可以得到长度属性字节之后有多少个字节，即len=8，然后再令sign & 1000 0000，得到的0即为标志位，所以这里需要对长度属性字节之后的len个字节进行遍历输出，完成解码。所以解压之后就变成了 abcdefgh

程序分析

? 程序由几个主要函数组成：isRepetition(), getRepeatLen(), getNotRepeatLen(), rleEncode(), rleDecode(), compress(), decompress().

? isRepetition()函数负责判断接下来是否有连续重复字节，返回1，说明是连续重复字节，否则返回0。只有连续重复3个以上才视为重复，对只重复了两次的字节压缩没有意义。

int isRepetition(unsigned char *raw, int ramainLen) {  //remainLen 剩余字节个数
    if (ramainLen < 3) {    //小于3默认不构成连续重复字节
        return 0;
    }
    if ((raw[0] == raw[1]) && (raw[1] == raw[2])) { //构成连续重复字符串
        return 1;
    }
    return 0;   //否则不构成连续重复字节
}

? getRepeatLen()函数负责返回最大连续重复字节的个数。参数中的raw为原数据，remainLen表示原数据还有多少个字节没有被使用RLE算法处理。

unsigned char getRepeatLen(unsigned char *raw, int remainLen) {    //获取连续重复的长度
    int repeatedBuff = raw[0];   //获取重复的字节
    int length = 1;
    // 0x7f(8进制) = 0111 1111(二进制)，能表示的最大的连续重复字节个数
    while (length < remainLen && length < 0x7f && raw[length] == repeatedBuff) {
        length++;
    }
    return length;
}

? getNotRepeatLen()函数负责返回最大的非重复字节的个数。但如果出现比如 12345aaaa 的情况，为了避免非重复字节 12345 也将后面的2个a算进去从而导致4个a被拆开，无法组成连续重复字节，压缩的效果下降了，所以这种情况下将len -= 2后再返回。

unsigned char getNotRepeatLen(unsigned char *raw, int remainLen) {  //获取非连续重复的长度
    if(remainLen < 3) {     //remainLen < 3默认非连续重复
        return remainLen;
    }
    int length = 2;     //调用该函数时，就说明了至少检查的一组数据中，至少已经有两个不同的字节
    int now = raw[0], next = raw[1];    //遍历比较每个字节与该字节后面的那个字节是否相同
    int flag = 1;
    while (length < remainLen && length < 0x7f && ((now != next) || (next != raw[length]))) {
        flag = 0;	//表示此时已经出现了不重复的字节
        now = next;
        next = raw[length];     //next变为此时next后面的那个字节
        length++;
    }
    if (flag == 0) length -= 2;	//flag=0说明之前出现过非重复的字节，而不是只有两个相同字节的情况，lenth > 2
    return length;
}

? rleEncode()函数负责将长度属性单位字节和被压缩的字节组成一组组数据存储到数组中，并返回给compress()方法，最终所返回的被压缩的数据是由很多组数据组成的。

int rleEncode(unsigned char *inbuf, int inSize, unsigned char *outbuf, int outSize) {
    unsigned char *raw = inbuf; //raw为输入指针
    int encSize = 0;    //编码之后的长度
    int remainLen = inSize;       //remainLen为剩余数组元素
    while (remainLen > 0) {         //remainLen = 0时代表输入结束
        unsigned char count = 0;
        if (isRepetition(raw, remainLen)) { //是否连续三个字节数据相同
            if ((encSize + 2) > outSize) {      //缓存数组（至少需要两个字节）太小时
                return -1;
            }
            count = getRepeatLen(raw, remainLen); //得到重复的个数
            //0x80（八进制） = 1000 0000（二进制），将最高位标志位置为1，表示之后的数据为重复数据
            outbuf[encSize++] = count | 0x80;          //将标志位1 + 重复个数写入输出数组
            outbuf[encSize++] = *raw;                  //将会重复的字节存入输出数组
            raw += count;                            //移动输入数组指针，右移count个单位长度（字节）
            remainLen -= count;	//剩余字节个数少了count个
        } else {
            count = getNotRepeatLen(raw, remainLen);    //得到不重复的个数
            //缓存数组至少存储需要一个属性字节（标志位0 + 长度）以及后续的count个不重复字节
            if((encSize + count + 1) > outSize){   //缓存数组设置太小了
                return -1;
            }
            outbuf[encSize++] = count;      //存入长度（最高位为0）
            for (int i = 0; i < count; i++) {            //逐个写入这些数据
                outbuf[encSize++] = *raw++; //raw++先返回raw，再将raw指针右移一个字节
            }
            remainLen -= count;	//剩余字节个数少了count个
        }
    }
    return encSize;
}

? rleDecode()函数负责将每组数据的长度属性字节和被压缩的字节拆分，根据长度属性字节将被压缩的字节解码为原始数据，再将一组组原始数据填入到数组中并返回给decompress()。

int rleDecode(unsigned char *inbuf, int inSize, unsigned char *outbuf, int outSize) {
    unsigned char *raw = inbuf; //获取输入指针，为了不直接移动inbuf指针
    int remainLen = inSize;	//输入的数组的长度
    int decSize = 0;	//解码之后的长度
    while (remainLen > 0) {
        //获取属性字节，每组数据的第一个字节
        unsigned char sign = *raw++;
        remainLen--;
        //获取该组数据长度, 0x7f = 0111 1111(二进制)，除去标志位，取出表示长度的七位
        int len = sign & 0x7f;
        //检查输出数组是否会越界
        if (decSize + len > outSize) {
            return -1;  //缓存数组不够用
        }
        if (sign & 0x80) {  //如果最高位为1，那么是标志位后是连续重复数据
            unsigned char repeatedData = *raw++;
            remainLen--;	//remainLen只减少了1个字节
            for (int i = 0; i < len; i++) {
                outbuf[decSize++] = repeatedData;
            }
        } else {    //如果最高位是0，那么标志位后是非重复数据
            for (int i = 0; i < len; i++) {
                outbuf[decSize++] = *raw++; //对接下来的len个字节进行遍历输出
            }
            remainLen -= len;	//remainLen减少了len个不同的字节
        }
    }
    return decSize;
}

源程序

#include 
#include 
#include 

int isRepetition(unsigned char *raw, int ramainLen) {  //remainLen 剩余字节个数
    if (ramainLen < 3) {    //小于3默认不构成连续重复字节
        return 0;
    }
    if ((raw[0] == raw[1]) && (raw[1] == raw[2])) { //构成连续重复字符串
        return 1;
    }
    return 0;   //否则不构成连续重复字节
}

unsigned char getRepeatLen(unsigned char *raw, int ramainLen) {    //获取连续重复的长度
    int repeatedBuff = raw[0];   //获取重复的字节
    int length = 1;
    // 0x7f(8进制) = 0111 1111(二进制)，能表示的最大的连续重复字节个数
    while (length < ramainLen && length < 0x7f && raw[length] == repeatedBuff) {
        length++;
    }
    return length;
}

unsigned char getNotRepeatLen(unsigned char *raw, int remainLen) {  //获取非连续重复的长度
    if(remainLen < 3) {     //remainLen < 3默认非连续重复
        return remainLen;
    }
    int length = 2;     //调用该函数时，就说明了至少检查的一组数据中，至少有两个不同的字节
    int now = raw[0], next = raw[1];    //遍历比较每个字节与该字节后面的那个字节是否相同
    int flag = 1;
    while (length < remainLen && length < 0x7f && ((now != next) || (next != raw[length]))) {
        flag = 0;
        now = next;
        next = raw[length];     //next变为此时next后面的那个字节
        length++;
    }
    if (flag == 0) length -= 2;
    return length;
}

int rleEncode(unsigned char *inbuf, int inSize, unsigned char *outbuf, int outSize) {
    unsigned char *raw = inbuf; //raw为输入指针
    int encSize = 0;    //编码之后的长度
    int remainLen = inSize;       //remainLen为剩余数组元素
    while (remainLen > 0) {         //remainLen = 0时代表输入结束
        unsigned char count = 0;
        if (isRepetition(raw, remainLen)) { //是否连续三个字节数据相同
            if ((encSize + 2) > outSize) {      //缓存数组（至少需要两个字节）太小时
                return -1;
            }
            count = getRepeatLen(raw, remainLen); //得到重复的个数
            //0x80（八进制） = 1000 0000（二进制），将最高位标志位置为1，表示之后的数据为重复数据
            outbuf[encSize++] = count | 0x80;          //将标志位1 + 重复个数写入输出数组
            outbuf[encSize++] = *raw;                  //将会重复的字节存入输出数组
            raw += count;                            //移动输入数组指针，右移count个单位长度（字节）
            remainLen -= count;
        } else {
            count = getNotRepeatLen(raw, remainLen);    //得到不重复的个数
            //缓存数组至少存储需要一个属性字节（标志位0 + 长度）以及后续的count个不重复字节
            if((encSize + count + 1) > outSize){   //缓存数组设置太小了
                return -1;
            }
            outbuf[encSize++] = count;      //存入长度（最高位为0）
            for (int i = 0; i < count; i++) {            //逐个写入这些数据
                outbuf[encSize++] = *raw++; //raw++先返回raw，再将raw指针右移一个字节
            }
            remainLen -= count;
        }
    }
    return encSize;
}

int rleDecode(unsigned char *inbuf, int inSize, unsigned char *outbuf, int outSize) {
    unsigned char *raw = inbuf; //获取输入指针，为了不直接移动inbuf指针
    int remainLen = inSize;
    int decSize = 0;
    while (remainLen > 0) {
        //获取属性字节，每组数据的第一个字节
        unsigned char sign = *raw++;
        remainLen--;
        //获取该组数据长度, 0x7f = 0111 1111(二进制)，除去标志位，取出表示长度的七位
        int len = sign & 0x7f;
        //检查输出数组是否会越界
        if (decSize + len > outSize) {
            return -1;  //缓存数组不够用
        }
        if (sign & 0x80) {  //如果最高位为1，那么是标志位后是连续重复数据
            unsigned char repeatedData = *raw++;
            remainLen--;
            for (int i = 0; i < len; i++) {
                outbuf[decSize++] = repeatedData;
            }
        } else {    //如果最高位是0，那么标志位后是非重复数据
            for (int i = 0; i < len; i++) {
                outbuf[decSize++] = *raw++;	//对接下来的len个字节进行遍历输出
            }
            remainLen -= len;
        }
    }
    return decSize;
}

int compress(char* inFileName, char* outFileName) {
    FILE *inFile = fopen(inFileName, "rb");
    FILE *outFile = fopen(outFileName, "wb");
    if(outFile == NULL || inFile == NULL) {
        printf("%s does not exit/n",inFileName);
        return -1;
    }
    //缓冲区的大小跟读入写出的速度有关
    unsigned char *inbuf = (unsigned char*)malloc(1034 * sizeof(unsigned char));
    unsigned char *outbuf = (unsigned char*)malloc(2 * 1034 * sizeof(unsigned char));
    int len;
    while((len = fread(inbuf, sizeof(unsigned char), 1024, inFile)) != 0) {
        int codeSize = rleEncode(inbuf, len, outbuf, 2 * 1024);
        if (codeSize == -1) {
            return -1;
        }
        fwrite(outbuf, sizeof(unsigned char), codeSize, outFile);
    }
    free(inbuf);
    free(outbuf);
    fclose(inFile);
    fclose(outFile);
    return 1;
}

int decompress(char* inFileName, char* outFileName) {
    FILE *inFile = fopen(inFileName, "rb");
    FILE *outFile = fopen(outFileName, "wb");
    if(outFile == NULL || inFile == NULL) {
        printf("%s does not exit/n",inFileName);
        return -1;
    }
    int fileSize = 128 * 1024 * 1024;   //128M
    unsigned char *inbuf = (unsigned char*)malloc(fileSize * sizeof(unsigned char));
    unsigned char *outbuf = (unsigned char*)malloc(fileSize * sizeof(unsigned char));
    int len;
    while((len = fread(inbuf, sizeof(unsigned char), fileSize, inFile)) != 0) {
        int codeSize = rleDecode(inbuf, len, outbuf, fileSize);
        if (codeSize == -1) {
            return -1;
        }
        fwrite(outbuf, sizeof(unsigned char), codeSize, outFile);
    }
    free(inbuf);
    free(outbuf);
    fclose(inFile);
    fclose(outFile);
    return 1;
}

int main(int argc, char *argv[]) {
    // char in[] = "1.txt";
    // char out[] = "2.txt";
    // compress(in, out);
    // char in[] = "2.txt";
    // char out[] = "3.txt";
    // decompress(in, out);
    printf("argv[1]:%s\n",argv[1]);
	printf("argv[3]:%s\n",argv[3]);
    if (strcmp(argv[2], "-c") == 0) {
        compress(argv[1], argv[3]);
    } else if (strcmp(argv[2], "-d") == 0) {
        decompress(argv[1], argv[3]);
    }
    return 0;
}

测试

在命令行输入参数，完成指定文件的压缩解压，命令行参数如下

rle file1 –c(-d) file2

第一个参数为可执行程序名称，第二个参数为原始文件名，第三个参数为压缩或解压缩选项，第四个参数为新文件名

//cmd里的测试命令
rle 1.txt -c 2.txt
rle 2.txt -d 3.txt

rle j1.jpg -c j2.jpg
rle j2.jpg -d j3.jpg

rle m1.mp4 -c m2.mp4
rle m2.mp4 -d m3.mp4

rle w1.docx -c w2.docx
rle w2.docx -d w3.docx

? 对txt文件的压缩解压应该没有问题

? 对图片的压缩解压没有大问题，不过不知道为什么没有达到压缩的效果，反而占的空间更大了，看了半天代码也不知道为什么，对视频压缩的是时候也是这个样子。

? 对视频的压缩解压

? 对.docx文件的压缩解压没有问题，达到了压缩的效果