一起谈.NET技术，用c#实现Protocol Buffers的变长字节整形编码

我就是我 2021-12-15 22:53 206阅读 0赞

## 　　摘要 ##

int在.net里固定占4个字节，如果我们存储和传输大量的int数据，并且大部分数的值比较小，我们就会浪费很多的网络流量和磁盘存储。Protocol Buffers对整数的编码是让值小的数占少量几个的字节，值大的数占多个字节。

## 　　编码算法 ##

首先看如下链接，了解Protocol Buffers对整形的编码算法。[http://code.google.com/intl/zh-CN/apis/protocolbuffers/docs/encoding.html][http_code.google.com_intl_zh-CN_apis_protocolbuffers_docs_encoding.html]

它举了个对300的编码，编码后是两个字节：

1010  1100  0000  0010

它这个例子是每个字节左边是高位，可以看到每个字节的最高位是一个标识位，从左到右第一个字节是10101100，最高位是1，说明后面还有字节需要解码，然后第二个字节是00000010，最高位是0，后面没字节了。所以这两个字节就需要解码成一个整数，再往下看。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 代码

1010  1100  0000  0010   
→  010  1100  000  0010  // 每个字节去掉最高位   
 →  000  0010  010  1100  // 字节序转换，两个字节互换位置   
 →  000  0010  \++  010  1100  // 两个字节进行链接操作（不是相加）   
 →  100101100  // 合并后的结果，高位位0的部分截取掉   
 →  256  \+  32  \+  8  \+  4  =  300  // 每个值为1的bit位乘以以2为底的幂，得出编码后的值

这个例子是以一个正数为例的，负数也是一样的，不过以补码表示负数的话，有个符号位，而且高位都是1，编码比较复杂，它没有给举例。不过后面咱们用c\#实现的变字节编码是支持对负数进行编码的，只是对负数的编码没有压缩的效果。

## 　　c\#的的二进制基本操作 ##

我们先来熟悉下c\#的二进制的位操作，位了查看方便，我们先写一个按二进制打印字节数组的辅助函数：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 代码

static  string  ByteToString( byte \[\] bytes)  
\{  
BitArray array  =  new  BitArray(bytes);  
StringBuilder sb  =  new  StringBuilder();  
 for  ( int  i  =  0 ; i  <  array.Length; i \++ )  
\{  
sb.Append(array\[i\]  ?  ' 1 '  :  ' 0 ' );  
 if  ((i  \+  1 )  %  8  ==  0 )  
sb.Append( '  ' );  
\}  
 return  sb.ToString();  
\}

来测试查看几个常见的位操作，具体情况详见注释：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 代码

private  static  void  StudyBitOperation()  
\{  
 // 16进制换算成二进制，每个16进制位转换成4个二进制位  
 // 高位的3是0011，低位的2是0010，因为.net下是小字节序  
 // 所以0x32的二进制表示是01001100   
  byte \[\] temp  =  new  byte \[\] \{  0x32  \};  
Console.Write( " 0x32的原始二进制表示: " );  
Console.WriteLine(ByteToString(temp));  
  
 // 左移运算符 (<<) 将第一个操作数向左移动第二个操作数指定的位数。  
 // 第一个操作数的高序位被放弃，低序空位用 0 填充。移位操作从不导致溢出。  
 // 01001100左移3位应该是00001001   
  temp\[ 0 \]  <<=  3 ;  
Console.Write( " 左移3位表示: " );  
Console.WriteLine(ByteToString(temp));  
  
 // 00001001右移2位应该是01001000   
  temp\[ 0 \]  >>=  3 ;  
Console.Write( " 右移2位表示: " );  
Console.WriteLine(ByteToString(temp));  
  
 // 判断高位第4位是否为1,0x80二进制表示是00000001  
 // 右移3位是00001000,高位（从右向左以1开始数）第4位是1  
 // 如果要检查的数高位第4位是1的话，那么两个数按位与后  
 // 得出的数就只有这位是1，也就是还是00001000   
  int  checkInt  =  0x80  >>  3 ;  
Console.WriteLine( " 高位第4位是:\{0\} " , (temp\[ 0 \]  &  checkInt)  ==  checkInt);  
  
 // 把高位第4位设置为0，0x80右移3位是00001000  
 // 取反后是11110111，和原始字节01001000按位与后  
 // 就是01000000   
  checkInt  =  ~ ( 0x80  >>  3 );  
temp\[ 0 \]  &=  ( byte )checkInt;  
Console.Write( " 把高位第4位设置为0: " );  
Console.WriteLine(ByteToString(temp));  
  
 // 把高位第3位设置为1,0x80右移2位是00000100  
 // 和原始字节01000000按位或后就是01000100   
  checkInt  =  0x80  >>  2 ;  
temp\[ 0 \]  |=  ( byte )checkInt;  
Console.Write( " 把高位第3位设置为1: " );  
Console.WriteLine(ByteToString(temp));  
\}

输出结果：

0x32的原始二进制表示: 01001100   
左移3位表示: 00001001   
右移2位表示: 01001000   
高位第4位是:True  
把高位第4位设置为0: 01000000   
把高位第3位设置为1: 01000100

## 　　实现编码及单元测试 ##

响应刀总号召，先写单元测试，我们设计了GetBytesFromInt和GetIntFromBytes分别用来对int数据进行编码和解码，然后单元测试里对各种整数进行编码，然后解码查看是否还是原始数据。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 代码

private  static  void  UnitTest()  
\{  
UnitTest( 300 );  
UnitTest( \- 1 );  
UnitTest( int .MaxValue);  
UnitTest( 255 );  
UnitTest( 1024 );  
UnitTest( 12234234 );  
UnitTest( \- 12234234 );  
\}  
  
 private  static  void  UnitTest( int  input)  
\{  
 byte \[\] bytes  =  GetBytesFromInt(input);  
 if  (\_debug)  
Console.WriteLine(ByteToString(bytes));  
  
 int  result  =  GetIntFromBytes(bytes);  
System.Diagnostics.Debug.Assert(input  ==  result);  
  
 if  (\_debug)  
Console.WriteLine(result);  
\}

代码实现，详细算法见注释：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 代码

static  byte \[\] GetBytesFromInt( int  input)  
\{  
 // 1、得到int的原始字节，.net的整数的二进制表示高位在右边   
  byte \[\] bytes  =  BitConverter.GetBytes(input);  
BitArray array  =  new  BitArray(bytes);  
 if  (\_debug)  
Console.WriteLine(ByteToString(bytes));  
  
 // 2、得到多字节编码的字节数，并初始化输出数组  
 // 原始二进制的每7位要编码到一个字节里，根据这个信息  
 // 计算出需要多少个字节编码，因为高位在右边，我们就  
 // 从右往左数，找到第一个为1的二进制位，从这位往  
 // 左数就都是有效数据位了。   
  int  firstOneIndex  =  0 ;  
 for  (firstOneIndex  =  array.Length  \-  1 ; firstOneIndex  >=  0 ; firstOneIndex \-- )  
\{  
 if  (array\[firstOneIndex\])  
 break ;  
\}  
 int  resultBytesLength  =  ( int )Math.Ceiling(( double )(firstOneIndex  \+  1 )  /  7 );  
 byte \[\] resultBytes  =  new  byte \[resultBytesLength\];  
  
 // 3、设置多字节编码中的每一位,  
 // 每个字节的低7位表示数据位,最高位如果是1表示后面还有数据需要解码   
  for  ( int  i  =  0 ; i  <=  firstOneIndex; i \++ )  
\{  
 // 3.1、计算出本次要编码的目标字节   
  int  byteindex  =  i  /  7 ;  
 byte  b  =  resultBytes\[byteindex\];  
  
 // 3.2、设置本次编码字节的每一位   
  int  checkInt  =  i  %  7 ;  
b  |=  array\[i\]  ?  ( byte )( 0x01  <<  checkInt) : ( byte ) 0 ;  
  
 // 3.3、设置最高位，如果后面还有字节编码则为1，否则为0   
  if  (byteindex  <  resultBytes.Length  \-  1 )  
b  |=  0x80 ;  
  
resultBytes\[byteindex\]  =  b;  
\}  
  
 return  resultBytes;  
\}  
  
 static  int  GetIntFromBytes( byte \[\] input)  
\{  
 // 1、初始化目标整数的字节数组，  
 // 因为编码数据里有冗余数据,所以要多出一个字节来   
  byte \[\] result  =  new  byte \[ 5 \];  
 for  ( int  i  =  0 ; i  <  input.Length; i \++ )  
\{  
 // 2、先把多字节编码的每个字节拷贝到目标整数字节中  
 // 并完成移位，移位是因为多字节编码每字节是7个有效  
 // 数据位，而.NET的整数的二进制表示是每个字节8个有效  
 // 数据位，这样目标字节填充几次后，高位就会空出多个  
 // 位的无效数据   
  result\[i\]  =  input\[i\];  
result\[i\]  >>=  i;  
  
 // 3、从下一个字节的最低位拷贝N位到本次编码的最高位  
 // 因为本字节右移了i位，所以要从下一个字节拷贝i位数据  
 // 到本字节   
  for  ( int  j  =  0 ; j  <=  i; j \++ )  
\{  
 // 3.1、得到下一个字节要拷贝的位   
  int  checkInt  =  0x80  >>  ( 7  \-  j);  
 if  (i  \+  1  <  input.Length)  
\{  
 // 3.2、如果要拷贝的位是1，则设置本字节相应的位为1   
  if  ((input\[i  \+  1 \]  &  checkInt)  ==  checkInt)  
\{  
checkInt  =  0x80  >>  (i  \-  j);  
result\[i\]  |=  ( byte )checkInt;  
\}  
 else  // 3.3、如果要拷贝的位是0，则设置本字节相应的位为1   
  \{  
checkInt  =  ~ ( 0x80  >>  (i  \-  j));  
result\[i\]  &=  ( byte )checkInt;  
\}  
\}  
\}  
\}  
  
 if  (\_debug)  
Console.WriteLine(ByteToString(result));  
  
 return  BitConverter.ToInt32(result,  0 );  
\}

单元测试均通过。

## 　　存储测试 ##

我们假设要编码的数据都是几万，几千的值，只有很少是大于ushort.max的，随机生成一些整数，用变长字节编码看看是否能起到压缩的效果。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] 代码

private  static  void  StoreTest()  
\{  
Random rnd  =  new  Random();  
 const  int  MAX  =  1000 ;  
 int  sum  =  0 ;  
 for  ( int  i  =  0 ; i  <  MAX; i \++ )  
\{  
sum  \+=  GetBytesFromInt(rnd.Next( 0 ,  ushort .MaxValue)).Length;  
\}  
Console.WriteLine( " .net编码\{0\}个int需要\{1\}字节 " , MAX, MAX  \*  4 );  
Console.WriteLine( " Protocol Buffer编码\{0\}个int需要\{1\}字节 " , MAX, sum);  
Console.WriteLine( " 节省了\{0:p\}的存储空间 " ,  1  \-  ( double )sum  /  (MAX  \*  4 ));  
\}

测试输出：

.net编码1000个int需要4000字节  
Protocol Buffer编码1000个int需要2787字节  
节省了30. 33 % 的存储空间

当然这个测试数据并不具有代表性，如果要编码的整数大多都是负数，或者很大的正数，那么这种编码不仅不会比原始的int编码小，反而会比.net对整形的定长编码要大。

## 　　小节 ##

计算机组成原理讲的知识离我们并不遥远，没准什么时候有个需求来了，你就得用到这些知识。

转载于:https://www.cnblogs.com/waw/archive/2011/09/01/2162777.html

[http_code.google.com_intl_zh-CN_apis_protocolbuffers_docs_encoding.html]: http://code.google.com/intl/zh-CN/apis/protocolbuffers/docs/encoding.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211215/2a1b046095b04ec3bcd9850977704c5e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，206人围观）

还没有评论，来说两句吧...

相关阅读

相关【Google Protocol Buffers】Protocol Buffer基础：C++篇

注：这是本人的翻译，可能不准确，可能有错误，但是基本上可以理解，希望能对大家有所帮助！（转载请注明出处：本文来自learnhard的博客：[http://www.codelas

曾经终败给现在/ 2022年09月30日 06:17/ 0 赞/ 235 阅读

相关 protocol buffer的高效编码方式

文章目录简介定义一个简单的message Base 128 Varints 消息体的结构符号整数字符串嵌套的消息

╰半橙微兮°/ 2022年09月07日 14:56/ 0 赞/ 183 阅读

相关 Protocol Buffer技术详解(C++实例)

这篇Blog仍然是以Google的官方文档为主线，代码实例则完全取自于我们正在开发的一个Demo项目，通过前一段时间的尝试，感觉这种结合的方式比较有利于培训和内部的技术交流。还

矫情吗；*/ 2022年08月18日 01:00/ 0 赞/ 300 阅读

相关 Protocol Buffer技术详解

一、生成目标语言代码。下面的命令帮助我们将MyMessage.proto文件中定义的一组Protocol Buffer格式的消息编译成目标语言（Java）的代

布满荆棘的人生/ 2022年08月17日 14:11/ 0 赞/ 19 阅读

相关 Google Protocol Buffers 之.Net应用

原文：[http://www.cnblogs.com/wu-jian/archive/2011/02/22/1961104.html][http_www.cnblogs.com

一时失言乱红尘/ 2022年08月10日 14:53/ 0 赞/ 33 阅读

相关 protocol buffers

该系列Blog的内容主体主要源自于Protocol Buffer的官方文档，而代码示例则抽取于当前正在开发的一个公司内部项目的Demo。这样做的目的主要在于不仅可以保持Goog

分手后的思念是犯贱/ 2022年08月10日 05:00/ 0 赞/ 214 阅读

相关一起谈.NET技术，反编译Silverlight项目

　　在互联网上，每天都会有很多Silverlight项目发布，有的是开源，有的只是为了展示。在Silverlight学习的初期，多数都需要模仿学习，所以，发现一个Silverl

一时失言乱红尘/ 2022年03月28日 05:59/ 0 赞/ 213 阅读

相关 Protocol Buffers 3.0 技术手册

[简介][Link 1] [proto3语法][proto3] [定义一个 Message][Message] [定义多个 m

本是古典何须时尚/ 2022年03月02日 14:37/ 0 赞/ 265 阅读

相关 Protocol Buffers（2）：编码与解码

文章目录 Message Structure 解码代码一窥 varint Protobuf中的整数和浮点数 Length-delimited

青旅半醒/ 2022年02月19日 00:31/ 0 赞/ 357 阅读

相关一起谈.NET技术，用c#实现Protocol Buffers的变长字节整形编码

　　摘要　　int在.net里固定占4个字节，如果我们存储和传输大量的int数据，并且大部分数的值比较小，我们就会浪费很多的网络流量和磁盘存储。Protocol Buf

我就是我/ 2021年12月15日 22:53/ 0 赞/ 207 阅读