数据压缩算法

1. varint （数字）

1.1 评价

数字压缩算法
算法逻辑：每个字节的首bit代表是否还需要下一位（0表示不需要，1表示需要），每个字节的可用位为7位

1.2 优缺

优点：对于int类型数值较小的数起到压缩作用，比如，2的(3*7)次方以下的数字都能起到压缩作用，由于实际传输过程中，我们大多用到的都是小类型的int数值，故这种方法能起到压缩字符的作用。

缺点：

1. 对于数值较大的数字，比如int类型，2的(4*7)次方以上的数字是需要5个字节来表示。
2. 对于负值，如-1，本质上首位为1导致数极大，必须要5个字节才能表示。

1.3编码与解析(java)

32位加密算法：

static void write32ForVarint(int value,byte[] buffer,int position){
        while (true) {
            if ((value & ~0x7F) == 0) {
                buffer[position++] = (byte) value;
                return ;
            } else {
                buffer[position++] = (byte) ((value & 0x7F) | 0x80);//|0x80代表首位bit置1
                value >>>= 7;
            }
        }
    }

32位解密算法:

static int read32ForVarint(byte[] buffer,int position){
        int result = 0;
        for (int shift = 0; shift < 32; shift += 7) {//这个32 可以写29反正只要大于或等于28就行。
            final byte b = buffer[position++];
            result |= (long) (b & 0x7F) << shift;
            if ((b & 0x80) == 0) {
                return result;
            }
        }
        return -1;
    }

2. zigzag （数字）

2.1 评价

数字压缩算法
由于表示负数时，varint花费的字节太大，所以需要一种弥补办法，来解决这种冲突!
由于考虑到varint之所以表示负数占用字节大，主要因为负数表示方法是首位且为1，而varint一般从末尾向前压缩，所以varint压缩负数通常很大，基于这种考虑，我们想到当数字为负数时，将首位挪到尾位，并按位取反把1全部变为0。最后在按照varint压缩字节，这样就能够使得我们可以用少量的字节表示值小的负数。

2.2 优缺

优点：相较于varint，能够用少量字节表示负数。
缺点：对于数值大的的正数或特别小的负数仍然需要大很多的字节数，且解析相较于varint需要更多逻辑。

2.3编码与解析(java)

编码: 先转换int，然后在带入varint编码

static int transform32ForZigzag(int num){
    return (num << 1) ^ (num >> 31);//看清楚"^" 在java代表抑或的意思
}

解码：先用varint解码，然后转换int

static int detransform32ForZigzag(int num){
    return (num >>> 1) ^ -(num & 1);
}

3. UTF-8变长方案

3.1评价

字符编码方案

对于某一个字符的UTF-8编码，如果只有一个字节则其最高二进制位为0；如果是多字节，其第一个字节从最高位开始，连续的二进制位值为1的个数决定了其编码的位数，其余各字节均以10开头。UTF-8最多可用到6个字节。
如表：
1字节 0xxxxxxx
2字节 110xxxxx 10xxxxxx
3字节 1110xxxx 10xxxxxx 10xxxxxx
4字节 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
5字节 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
6字节 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
因此UTF-8中可以用来表示字符编码的实际位数最多有31位，即上表中x所表示的位。除去那些控制位（每字节开头的10等），这些x表示的位与UNICODE编码是一一对应的，位高低顺序也相同。
整个方案显得特别的臃肿，很难理解是什么考虑下回用到这种臃肿的方案，简直让人窒息!

3.2优缺

优点：几乎统一了编码
缺点：臃肿的让人窒息

3.3编解码

解码

static int encode(int unicode,byte[] bytes,int position){
  if(unicode < (int)Math.pow(2,7)){
      bytes[position++] = (byte)unicode & 0x7f;
      return position;
  }
  else if(unicode < (int)Math.pow(2,5+6)){
      byte[position++] = (byte)(unicode & 0xbf | 0x80);
      byte[position++] = (byte)(unicode >> 6) & 0x1f | 0xdf ;
      return position;
  }
  else if 
    //some code
}

编码：

static String utf8Decode (byte[] bytes){
  char[] chars = new char[bytes.length];//最多不可能超过bytes.length
int charsLen = 0;
  for(int i=0;i<bytes.length;i++){
      byte tmp = bytes[i];
      if(tmp & 0x80 == 0x80){
          chars[charsLen++] = bytes[i] & 0x3f;
      } else {
          //some code
      }
  }
}

4. MQTT剩余长度方案 （数字）

4.1介绍

和varint方案基本一致，最高位做符号位，符号位1表示最高位为前面还有值，否则为0，则表示结束

字节数	最小值	最大值
1	0 (0x00)	127 (0x7F)
2	128 (0x80, 0x01)	16 383 (0xFF, 0x7F)
3	16 384 (0x80, 0x80, 0x01)	2 097 151 (0xFF, 0xFF, 0x7F)
4	2 097 152 (0x80, 0x80, 0x80, 0x01)	268 435 455 (0xFF, 0xFF, 0xFF, 0x7F)

分别表示（每个字节的低7位用于编码数据，最高位是标志位）

4.2优缺

和varint一样

4.3编解码

netty解码：

int remainingLength = 0;//剩下长度
int multiplier = 1;
short digit;
int loops = 0;
    do {
    digit = buffer.readUnsignedByte();//读取一个无符号的byte用short来存;
    remainingLength += (digit & 127) * multiplier;
    multiplier *= 128;
    loops++;
} while ((digit & 128) != 0 && loops < 4);

参考：

1. 详细谈了 zigzag 算法
2. 对 protoBuf中的 varint ，zigzag算法做了介绍
3. 详细谈了 protoBuf中varint，zigzag的优点和缺点等