当前位置: 首页 > news >正文

Go中varint压缩编码原理分析

文章目录

    • 编码介绍
    • 无符号整数
      • 较小的值
      • 较大的值
      • Go中的实现
        • 编码PutUvarint
        • 解码Uvarint
    • 有符号整数
      • 较小的值(指绝对值)
      • 较大的负数(只绝对值)
      • Go中的实现
        • 编码PutVarint
        • 解码Varint
    • 总结

编码介绍

varint是一种将整数编码为变长字节的压缩编码算法,本篇文章就是分析该编码算法的原理以及看一看go中的源码实现。

计算机中,整型数据是按照补码进行存储的,varint编码的原理就是将整数按照7bits划分,在最高位设置一个有效位表示后面是否还有该整数的部分,当最高位为1时表示后面还有该数据的字节,为0表示该字节是最后一个字节。

无符号整数

较小的值

举个例子:对于一个uint32来说,无论数字多大,都会占用4个字节的大小空间。对0000 0000 0000 0000 0000 0000 0000 0001 进行编码:

  1. 首先将该数字按照7位进行分组
0000 0000000 0000000 0000000 0000001
  1. 依次从低字节开始读,发现只需要一个字节就能表示,后面没有可用的字节,最高位置0
0000 0001

所以最终对1的编码只占用一个字节

较大的值

0000 1111 1111 0000 1111 0000 1111 1111 进行编码

  1. 首先按照7bit进行分组
0000 1111111 1000011 1100001 1111111
  1. 依次读取低位字节进行编码
|  1111111 |  1100001 |  1000011 |  1111111 | 0000 || 11111111 | 11100001 | 11000011 | 01111111 |  

所以最终该数字占用 4 个字节

Go中的实现

go中关于varint编码的实现在binary包下,这里参考的是Go1.20

编码PutUvarint
func PutUvarint(buf []byte, x uint64) int {i := 0for x >= 0x80 {// 将该字节的最高位置 1, 表示后面还有数据buf[i] = byte(x) | 0x80// 将x向右移动7位(按照7bit进行分组的过程)x >>= 7i++}buf[i] = byte(x)return i + 1
}

循环条件就是判断当前x的值是否能用一个字节表示,大于0x80说明不能使用一个字节表示。

解码Uvarint
func Uvarint(buf []byte) (uint64, int) {var x uint64var s uint// 遍历buf中的每个字节,低位字节表示原数据的高位for i, b := range buf {// 如果i达到了64位数据所能编码的最大字节数,说明溢出if i == MaxVarintLen64 {// Catch byte reads past MaxVarintLen64.// See issue https://golang.org/issues/41185return 0, -(i + 1) // overflow}// 如果该字节小于0x80,说明该字节是最后一个有效字节if b < 0x80 {// 对于一个uint64的数据来说,64 % 7 = 1,所以最终只会多出1bit// 如果 b > 1,说明原数据并不是64位的,溢出if i == MaxVarintLen64-1 && b > 1 {return 0, -(i + 1) // overflow}return x | uint64(b)<<s, i + 1}// 将b最高位置0,加到x上x |= uint64(b&0x7f) << ss += 7}return 0, 0
}

有符号整数

较小的值(指绝对值)

对原码为1000 0000 0000 0000 0000 0000 0000 0001 的负数进行编码

负数的补码 = 除符号位外的位取反 + 1

  1. 首先计算数字的补码,负数的补码是除符号位外取反+1
1111 1111 1111 1111 1111 1111 1111 1111
  1. 按照7bit进行分组
 | 1111 | 1111111 | 1111111| 1111111 | 1111111 |
  1. 编码
|  1111111 |  1111111 |  1111111 |  1111111 | 1111 |
| 11111111 | 11111111 | 11111111 | 11111111 | 0000 1111 |

所以最终-1占了5个字节

较大的负数(只绝对值)

对原码为1111 1111 1111 0000 0000 0000 0000 0001 的负数进行编码

  1. 首先计算数字的补码,负数的补码是除符号位外取反+1
1000 0000 0000 1111 1111 1111 1111 1111
  1. 按照7bit进行分组
1000 0000000 0111111 1111111 1111111
  1. 编码
|  1111111 |  1111111 |  0111111 |  0000000 | 1000 |
| 11111111 | 11111111 | 10111111 | 10000000 | 0000 1000 |

由此可得,最终占用5个字节

Go中的实现

编码PutVarint

妙!!!

func PutVarint(buf []byte, x int64) int {// 去掉符号位,忽略符号位的影响,更方便处理ux := uint64(x) << 1// 如果x为负数,则对ux进行取反,此时最低位一定是1// 而对于正数来说,最低位始终为 0,也为解码时判断正负做了铺垫if x < 0 {ux = ^ux}// 经过上面的处理,ux 为 x 的绝对值return PutUvarint(buf, ux)
}
解码Varint
func Varint(buf []byte) (int64, int) {ux, n := Uvarint(buf) // ok to continue in presence of error// 和上面的操作是相对的,因为最低位原本不属于原数据x := int64(ux >> 1)// 如果 ux 最低位为 1,说明原数据是负数,取反if ux&1 != 0 {x = ^x}return x, n
}

总结

varint编码的思想是:

  • 对于小的数字使用更好的字节进行编码
  • 对于大的数字使用更多的字节进行编码

因为大多数时候,我们的应用程序中会大量使用小的数字,而只是少量使用大的数字,所以使用varint压缩编码,在一定程度上可以节省空间。

但是通过原始的算法思想对负数进行编码时,由于负数在计算机中存储的特殊性,所以不会起到很好的作用,所以go在实对负数进行压缩编码时,首先将负数转化为正数表示,也就是取绝对值的操作,并在解码时通过最后一位来判断原数据是正数还是负数,这样varint对负数的压缩也同样效果很好。

http://www.lryc.cn/news/191892.html

相关文章:

  • 在IDEA中如何用可视化界面操作数据库? 在idea中如何操作数据库? 在idea中如何像Navicat一样操作数据库?
  • 数据库安全-RedisHadoopMysql未授权访问RCE
  • 辅助驾驶功能开发-功能规范篇(27)-3-导航式巡航辅助NCA华为
  • 探索UI设计|栅格系统的深入分析和应用
  • AI 律助 Alpha GPT 线上实操发布会,重磅发布!
  • 【漏洞复现】安全云平台存在任意文件下载getshell
  • 【JUC】原子操作类及LongAddr源码分析
  • 203、RabbitMQ 之 使用 direct 类型的 Exchange 实现 消息路由 (RoutingKey)
  • 微服务+Java+Spring Cloud +UniApp +MySql智慧工地综合管理云平台源码,SaaS模式
  • QMidi Pro for Mac:打造您的专属卡拉OK体验
  • bindtap和catchtap的区别?
  • IDEA—java: 常量字符串过长问题解决
  • 云原生SIEM解决方案
  • 工艺边与定位孔设计经验规则总结
  • 软件架构设计(业务架构、应用架构、数据架构、技术架构)
  • 我们又组织了一次欧洲最大开源社区活动,Hugging Face 博客欢迎社区成员发帖、Hugging Chat 功能更新!...
  • 学信息系统项目管理师第4版系列26_项目绩效域(下)
  • SQL sever中的索引
  • 多目标鳟海鞘算法(Multi-objective Salp Swarm Algorithm,MSSA)求解微电网优化MATLAB
  • 软件测试之概念篇(需求,测试用例,BUG描述,产品的生命周期)
  • jwt详细介绍
  • 电子笔记真的好用吗?手机上适合记录学习笔记的工具
  • 用 SQL 找出某只股票连续上涨的最长天数
  • Vue 绑定 class 与 style
  • 【微服务部署】九、使用Docker Compose搭建高可用双机热备MySQL数据库
  • HTTP Basic 认证
  • 计算机网络第2章-HTTP和Web协议(2)
  • css3 table表格
  • 【【萌新的SOC学习之AXI DMA环路测试介绍】】
  • 07 | @Entity 之间的关联关系注解如何正确使用?