数值压缩存储方法Varint

转自：http://www.cnblogs.com/smark/archive/2012/05/03/2480034.html

在编写网络通讯的时候我们经常需要把一些数据存储到byte[]中然后再发送出去，数值则是我们经常处理的数据成员。发越少的东西意味着使用更少的IO和带宽 ，所以对传输数据进行压缩也是件非常重要的事情。接下来提到的就是一种基于数字存储的方式在大多数情况下可以节省数值存储空间。

 

    Varint 是一种紧凑的表示数字的方法。它用一个或多个字节来表示一个数字，值越小的数字使用越少的字节数。这能减少用来表示数字的字节数。比如对于 int32 类型的数字，一般需要 4 个 byte 来表示。但是采用 Varint，对于很小的 int32 类型的数字，则可以用 1 个 byte 来表示。当然凡事都有好的也有不好的一面，采用 Varint 表示法，大的数字则需要 5 个 byte 来表示。从统计的角度来说，一般不会所有的消息中的数字都是大数，因此大多数情况下，采用 Varint 后，可以用更少的字节数来表示数字信息。下面就详细介绍一下 Varint。

 

    Varint 中的每个 byte 的最高位 bit 有特殊的含义，如果该位为 1，表示后续的 byte 也是该数字的一部分，如果该位为 0，则结束。其他的 7 个 bit 都用来表示数字。因此小于 128 的数字都可以用一个 byte 表示。大于 128 的数字，比如 300，会用两个字节来表示：1010 1100 0000 0010

 

 

 

    由于负数的高位为1,所以采用这种压缩处理的时候必须负数转成正数，可以通过以下代码实现int to uint的转换

 

private static int Zag(uint ziggedValue)

{

    int value = (int)ziggedValue;

    return (-(value & 0x01)) ^ ((value >> 1) & ~( 1<< 31));

}

private static uint Zig(int value)

{

    return (uint)((value << 1) ^ (value >> 31));

 

}

    以下操作是对一个uint进行编码处理

 

private static ArraySegment<byte> WriteUInt32Variant(uint value)

      {

          byte[] data = new byte[5];

          int count = 0;

          do

          {

              data[count] = (byte)((value & 0x7F) | 0x80);

              count++;

          } while ((value >>= 7) != 0);

          data[count - 1] &= 0x7F;

          return new ArraySegment<byte>(data, 0, count);

      }

    data[count] = (byte)((value & 0x7F) | 0x80);   得到头7位的数值， | 0x80是表明后面的byte也是数字的一部分。

 

    while ((value >>= 7) != 0)    右移7位如果不为零的情况下则继续上面的工作。

 

    data[count - 1] &= 0x7F 把最后byte的最高位设置成0;

 

    接下来就是一个uint的解码过程

 

private static uint ReadUInt32Variant(ArraySegment<byte> data)

        {

            uint value = data.Array[0];

            if ((value & 0x80) == 0) return value;

            value &= 0x7F;

            uint chunk = data.Array[1];

            value |= (chunk & 0x7F) << 7;

            if ((chunk & 0x80) == 0) return value;

            chunk = data.Array[2];

            value |= (chunk & 0x7F) << 14;

            if ((chunk & 0x80) == 0) return value;

            chunk = data.Array[3];

            value |= (chunk & 0x7F) << 21;

            if ((chunk & 0x80) == 0) return value;

            chunk = data.Array[4]; ;

            value |= chunk << 28;

            if ((chunk & 0xF0) == 0) return value;

            throw new OverflowException("ReadUInt32Variant Error!");

        }

    (value & 0x80) == 0 表示最高位为0，说明后面的byte已经不是数值组成部分。

 

    (chunk & 0xF0) == 0 chunk只有4位，如果不是则表明这个byte不是数值存储的一部分。

 

    测试一下看下编码效果

 

 

ArraySegment<byte> data = WriteUInt32Variant(Zig(0));

            Console.WriteLine(data.Count);

            data = WriteUInt32Variant(Zig(567));

            Console.WriteLine(data.Count);

            data = WriteUInt32Variant(Zig(10000));

            Console.WriteLine(data.Count);

            data = WriteUInt32Variant(Zig(-100000));

            Console.WriteLine(data.Count);

分别是1byte,2byte,3byte,3byte

 

    其实有人会有凝问，为什么不根据情况来用int16等来存储，如果一旦用了int16就说明以后需要转int32就是件非常麻烦的事情，双方程序都需要调整。如果采用Varint进行处理就能达到最好扩展效果和带宽利用率.