草庐IT

Go:二进制编码机制

coder 2023-06-26 原文

我正在尝试制作一个新的二进制编码包，因为标准的 Go 编码/二进制包并不完全符合我的要求。

我不明白的是为什么编码/二进制在 binary.PutUvarint 中使用 x >>= 7 而不是 x >>= 8。如果我理解正确的话，这是故意将位移动 7 而不是 8，这导致总大小为 80 位来存储 uint64 而不是 64 位，这显然是所需的位数。为什么？这是什么原因？这一定与它正在生成可变长度的 byte slice 这一事实有关，但为什么 >>7 会对此有所帮助？

这里给出二进制编码函数供大家引用:

func PutUvarint(buf []byte, x uint64) int {
    i := 0
    for x >= 0x80 {
        buf[i] = byte(x) | 0x80
        x >>= 7
        i++
    }
    buf[i] = byte(x)
    return i + 1
}

最佳答案

encoding/binary/varint.go

package binary

// This file implements "varint" encoding of 64-bit integers.
// The encoding is:
// - unsigned integers are serialized 7 bits at a time, starting with the
//   least significant bits
// - the most significant bit (msb) in each output byte indicates if there
//   is a continuation byte (msb = 1)
// - signed integers are mapped to unsigned integers using "zig-zag"
//   encoding: Positive values x are written as 2*x + 0, negative values
//   are written as 2*(^x) + 1; that is, negative numbers are complemented
//   and whether to complement is encoded in bit 0.
//
// Design note:
// At most 10 bytes are needed for 64-bit values. The encoding could
// be more dense: a full 64-bit value needs an extra byte just to hold bit 63.
// Instead, the msb of the previous byte could be used to hold bit 63 since we
// know there can't be more than 64 bits. This is a trivial improvement and
// would reduce the maximum encoding length to 9 bytes. However, it breaks the
// invariant that the msb is always the "continuation bit" and thus makes the
// format incompatible with a varint encoding for larger numbers (say 128-bit).

无损数据压缩的经典技术是霍夫曼编码，其中较常见的符号通常使用比不太常见的符号更少的位数来表示。实际上，较小的数字最常出现。因此，如果我们能够有效地表示小数，即使较大数的表示效率较低，我们也将获得无损数据压缩。

Uvarint 是一种使用一个或多个字节序列化无符号整数的方法。较小的数字占用较少的字节数。 uvarint 中的每个字节，除了最后一个字节，都设置了最高有效位 (msb)——这表明还有更多的字节要来。每个字节的低 7 位用于存储 7 位组中的数字，最低有效组在前。我们可以对具有任意位数的无符号整数执行此操作。

例如，

uint bits : uvarint bytes
7 7f : 1 7f 
14 3fff : 2 ff7f 
21 1fffff : 3 ffff7f 
28 fffffff : 4 ffffff7f 
35 7ffffffff : 5 ffffffff7f 
42 3ffffffffff : 6 ffffffffff7f 
49 1ffffffffffff : 7 ffffffffffff7f 
56 ffffffffffffff : 8 ffffffffffffff7f 
63 7fffffffffffffff : 9 ffffffffffffffff7f 
64 ffffffffffffffff : 10 ffffffffffffffffff01

依此类推，对于我们想要的任意多的 uint 位。

如果我们有很多数字表示为无符号 64 位整数的 1 到 49 位，序列化为 1 到 7 字节的 uvarint，我们不会关心是否有几个数字表示为 57到 64 位无符号 64 位整数，序列化为 9 到 10 字节的 uvarint。

引用资料:

Huffman coding

Variable-length quantity

关于Go:二进制编码机制，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25377752/

Go二进制编码codeencodingsection

有关Go:二进制编码机制的更多相关文章

  1. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  2. ruby - 用逗号、双引号和编码解析 csv - 2

    我正在使用ruby​​1.9解析以下带有MacRoman字符的csv文件#encoding:ISO-8859-1#csv_parse.csvName,main-dialogue"Marceu","Giveittohimóhe,hiswife."我做了以下解析。require'csv'input_string=File.read("../csv_parse.rb").force_encoding("ISO-8859-1").encode("UTF-8")#=>"Name,main-dialogue\r\n\"Marceu\",\"Giveittohim\x97he,hiswife.\"\

  3. C# 到 Ruby sha1 base64 编码 - 2

    我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha

  4. ruby - 我如何添加二进制数据来遏制 POST - 2

    我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_

  5. Ruby - 如何将消息长度表示为 2 个二进制字节 - 2

    我正在使用Ruby，我正在与一个网络端点通信，该端点在发送消息本身之前需要格式化“header”。header中的第一个字段必须是消息长度，它被定义为网络字节顺序中的2二进制字节消息长度。比如我的消息长度是1024。如何将1024表示为二进制双字节？ 最佳答案 Ruby(以及Perl和Python等)中字节整理的标准工具是pack和unpack。ruby的packisinArray.您的长度应该是两个字节长，并且按网络字节顺序排列，这听起来像是n格式说明符的工作:n|Integer|16-bitunsigned,network(bi

  6. ruby-on-rails - 有没有一种工具可以在编码时自动保存对文件的增量更改？ - 2

    我最喜欢的Google文档功能之一是它会在我工作时不断自动保存我的文档版本。这意味着即使我在进行关键更改之前忘记在某个点进行保存，也很有可能会自动创建一个保存点。至少，我可以将文档恢复到错误更改之前的状态，并从该点继续工作。对于在MacOS(或UNIX)上运行的Ruby编码器，是否有具有等效功能的工具？例如，一个工具会每隔几分钟自动将Gitcheckin我的本地存储库以获取我正在处理的文件。也许我有点偏执，但这点小保险可以让我在日常工作中安心。 最佳答案 虚拟机有些人可能讨厌我对此的回应，但我在编码时经常使用VIM，它具有自动保存功

  7. ruby - ruby 脚本可以预编译成二进制文件吗？ - 2

    我正在开发一个Ruby脚本，需要在没有Ruby解释器的情况下部署到系统上。它将需要在使用ELF格式的FreeBSD系统上运行。我知道有一个ruby​​2exe项目可以编译在Windows上运行的ruby​​脚本，但是在其他操作系统上这样做容易吗？甚至可能吗？ 最佳答案 您是否检查过Rubinius或JRuby是否允许您预编译您的代码？ 关于ruby-ruby脚本可以预编译成二进制文件吗？，我们在StackOverflow上找到一个类似的问题： https://

  8. c - Ruby - 源代码 - 编码风格 - 2

    查看Ruby代码，它具有以下proc_arity:staticVALUEproc_arity(VALUEself){intarity=rb_proc_arity(self);returnINT2FIX(arity);}更多的是C编码风格问题，但为什么staticVALUE在单独的一行而不是像这样的:staticVALUEproc_arity(VALUEself) 最佳答案 它来自UNIX世界，因为它有助于轻松grep函数的定义:$grep-n'^proc_arity'*.c或使用vim:/^proc_arity

  9. ruby - 如何以编程方式删除实例上的 "singleton information"以使其编码(marshal)？ - 2

    我创建了一个由于“在运行时执行的单例元类定义”而无法编码的对象(这段代码的描述是否正确？)。这是通过以下代码执行的:#defineclassXthatmyusesingletonclassmetaprogrammingfeatures#throughcallofmethod:break_marshalling!classXdefbreak_marshalling!meta_class=class我该怎么做才能使对象编码正确？是否可以从对象instance_of_x的classX中“移除”单例组件？我真的需要一个建议，因为我们的一些对象需要通过Marshal.dump序列化机制进行缓存。

  10. ruby - 如何在 Ruby 中将负整数转换为二进制 - 2

    问题1:我无法通过以下方式找到将负整数转换为二进制的方法。我应该像这样转换它。-3=>"11111111111111111111111111111101"我在下面试过:sprintf('%b',-3)=>"..101"#..appearsanddoesnotshow111111bit.-3.to_s(2)=>"-11"#Thisjustadds-tothebinaryofthepositiveinteger3.问题2:有趣的是，如果我使用在线转换器，它告诉我-3的二进制是“0010110100110011”。"11111111111111111111111111111101"和"001

随机推荐