算法 | byte值的按位不定长存储算法 [C/C++]

问题背景：
首先，在基于动态规划的灰度图像压缩算法中，压缩前灰度值序列的每个值原本以8bit，即1byte进行存储，压缩后，灰度值序列分为n个段，每个段中的每个元素都不一定以8bit存储，具体存储位数存放在一个大小为n的byte数组中。我们称这为不定长存储。

其次，我们知道在计算机中一般为按字节编址和存储，在Python、C/C++等编程语言中主要提供的读写的最小单位也是字节，而不是比特。但要实现灰度值序列的不定长存储，按比特读写是更方便的。

解决问题：现有一个byte值序列data[data_size]，和另外一个byte值序列B[data_size]。其中第i个元素B[i]，表示data[i]将以B[i]个bit存储。例如B[i]=3表示data[i]希望以3个bit存储。

输出结果：

将12个值不定长存入byte数组（buffer）

输入输出原理解释

代码：

//Compiler: TDM-GCC 4.8.1 64-bit Release 
#include<stdio.h>
#include<math.h>

#define SUCCESS 1;
#define FAIL -1;
#define OUT_OF_BUFFER -2;

typedef unsigned char byte ;

int dynamic(byte *B,byte *data,byte *buffer,int data_size,int buffer_size){

    //params:
    int i = 0;//buffer下标 
    int n = 0;//data和B的下标 
    int pre = 0;//用于记录前一个byte遗留的数的尾巴 
    
    //start:
    for(i=0;i<buffer_size;i++){
        if(n==data_size) {
            break;//数据遍历完退出 
        }
        int ei=8;//buffer的第i个位置空余的bit数 
        buffer[i]=0;//初始化buffer的第i个位置 
        
        //while循环保证buffer的每个byte填满
        //最后一个byte可以有空 
        while(ei>0 && n<data_size){
            if(pre==0){//前一个byte没有遗留尾巴 
                buffer[i]=buffer[i]|((data[n]<<(8-B[n]))>>(8-ei));
                ei=ei-B[n];
                
                if(ei<0){
                    pre=abs(ei);//data的值没塞完，遗留了尾巴给下一个byte 
                    ei=0;
                }else{
                    ++n;
                }
            }else{//前一个byte遗留了位长为pre个bit的尾巴 
                buffer[i] = data[n]<<(8-pre);
                ei=ei-pre;
                pre=0;
                ++n;
            }
        }
        printf("buffer[%d]=%d\n",i,buffer[i]);
    }
    
    //data还没全部放入buffer，说明buffer_size小了 
    if(n<data_size){
        return OUT_OF_BUFFER;
    }
    return SUCCESS;
}

int main(){
    //dynamic storage
    //inputs:
    byte *B=new byte[12];
    byte *data=new byte[12];
    byte *buffer=new byte[8];
    
    //init inputs:
    B[0]=3;
    B[1]=3;
    B[2]=3;
    B[3]=3;
    B[4]=8;
    B[5]=8;
    B[6]=5;
    B[7]=5;
    B[8]=5;
    B[9]=5;
    B[10]=5;
    B[11]=5;
    

    data[0]=6;
    data[1]=5;
    data[2]=7;
    data[3]=5;
    data[4]=245;
    data[5]=180;
    data[6]=28;
    data[7]=28;
    data[8]=19;
    data[9]=22;
    data[10]=25;
    data[11]=20;
    
    //test:
    dynamic(B,data,buffer,12,8);
}