Go中varint压缩编码原理分析
文章目录
- 编码介绍
- 无符号整数
- 较小的值
- 较大的值
- Go中的实现
- 编码PutUvarint
- 解码Uvarint
- 有符号整数
- 较小的值(指绝对值)
- 较大的负数(只绝对值)
- Go中的实现
- 编码PutVarint
- 解码Varint
- 总结
编码介绍
varint是一种将整数编码为变长字节的压缩编码算法,本篇文章就是分析该编码算法的原理以及看一看go中的源码实现。
计算机中,整型数据是按照补码进行存储的,varint编码的原理就是将整数按照7bits划分,在最高位设置一个有效位表示后面是否还有该整数的部分,当最高位为1时表示后面还有该数据的字节,为0表示该字节是最后一个字节。
无符号整数
较小的值
举个例子:对于一个uint32来说,无论数字多大,都会占用4个字节的大小空间。对0000 0000 0000 0000 0000 0000 0000 0001
进行编码:
- 首先将该数字按照7位进行分组
0000 0000000 0000000 0000000 0000001
- 依次从低字节开始读,发现只需要一个字节就能表示,后面没有可用的字节,最高位置0
0000 0001
所以最终对1的编码只占用一个字节
较大的值
对0000 1111 1111 0000 1111 0000 1111 1111
进行编码
- 首先按照7bit进行分组
0000 1111111 1000011 1100001 1111111
- 依次读取低位字节进行编码
| 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
1111 1111 1111 1111 1111 1111 1111 1111
- 按照7bit进行分组
| 1111 | 1111111 | 1111111| 1111111 | 1111111 |
- 编码
| 1111111 | 1111111 | 1111111 | 1111111 | 1111 |
| 11111111 | 11111111 | 11111111 | 11111111 | 0000 1111 |
所以最终-1占了5个字节
较大的负数(只绝对值)
对原码为1111 1111 1111 0000 0000 0000 0000 0001
的负数进行编码
- 首先计算数字的补码,负数的补码是除符号位外取反+1
1000 0000 0000 1111 1111 1111 1111 1111
- 按照7bit进行分组
1000 0000000 0111111 1111111 1111111
- 编码
| 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对负数的压缩也同样效果很好。
相关文章:
Go中varint压缩编码原理分析
文章目录 编码介绍无符号整数较小的值较大的值Go中的实现编码PutUvarint解码Uvarint 有符号整数较小的值(指绝对值)较大的负数(只绝对值)Go中的实现编码PutVarint解码Varint 总结 编码介绍 varint是一种将整数编码为变长字节的压缩编码算法,本篇文章就是分析该编码…...

在IDEA中如何用可视化界面操作数据库? 在idea中如何操作数据库? 在idea中如何像Navicat一样操作数据库?
1、找到database,创建连接 我用了中文包,英文状态下和我的操作完全一样 英文下第二列数据库名称为 database 2、配置相关属性,如IP地址,密码等 3、选择对应的库名,此处也叫架构 4、然后就可以进行愉快的操作了...

数据库安全-RedisHadoopMysql未授权访问RCE
目录 数据库安全-&Redis&Hadoop&Mysql&未授权访问&RCE定义漏洞复现Mysql-CVE-2012-2122 漏洞Hadoop-配置不当未授权三重奏&RCE 漏洞 Redis-未授权访问-Webshell&任务&密匙&RCE 等漏洞定义:漏洞成因漏洞危害漏洞复现Redis-未授权…...
辅助驾驶功能开发-功能规范篇(27)-3-导航式巡航辅助NCA华为
书接上回 2.2.2.3.7控制模块 控制模块由横向控制和纵向控制组成。根据横、纵向规划给出的行驶轨迹和给定速度,进行车辆的纵横向控制,输出方向盘转角、加速度或制动踏板开度和档位信息,必要条件下输出车灯信号等。 2.2.2.4 行为仲裁模块 纵向状态: 当纵向位于Off/Standby…...

探索UI设计|栅格系统的深入分析和应用
界面排版太乱了。你知道网格系统的用途吗?网格系统困扰着许多初级网页设计师,就像一个谜。如果您对网格在设计中的应用有任何疑问,本文是为您量身定制的,并深入分析UI设计中网格系统的基本要素和优点。 什么是网格系统 网格系统…...

AI 律助 Alpha GPT 线上实操发布会,重磅发布!
数字化时代,随着人工智能的迅猛发展,各行各业都在积极探索通过智能化工具实现工作效率翻升的可能性。“ ChatGPT 类产品”是未来办公应用软件发展的重要趋势之一,但如何将 ChatGPT 真正应用于法律人的工作,赋能效率提升?法律行业同样面临着新的挑战和机遇。 破局的关键是实现技…...

【漏洞复现】安全云平台存在任意文件下载getshell
漏洞描述 深圳市强鸿电子有限公司鸿运主动安全云平台存在任意文件下载漏洞,攻击者可通过此漏洞下载敏感文件信息。 免责声明 技术文章仅供参考,任何个人和组织使用网络应当遵守宪法法律,遵守公共秩序,尊重社会公德,不得利用网络从事危害国家安全、荣誉和利益,未经授权…...

【JUC】原子操作类及LongAddr源码分析
文章目录 1. 十八罗汉2. 原子类再分类2.1 基本类型原子类2.2 数组类型原子类2.3 引用类型原子类2.4 对象的属性修改原子类2.5 原子操作增强类 3. 代码演示及性能比较:4. LongAddr原理5. LongAddr源码分析5.1 add()5.2 longAccumulate()5.3 sum() 6. 小总结6.1 Atomi…...

203、RabbitMQ 之 使用 direct 类型的 Exchange 实现 消息路由 (RoutingKey)
目录 ★ 使用direct实现消息路由代码演示这个情况二ConstantUtil 常量工具类ConnectionUtil 连接RabbitMQ的工具类Publisher 消息生产者测试消息生产者 Consumer01 消息消费者01测试消费者结果: Consumer02 消息消费者02测试消费者结果: 完整代码&#x…...

微服务+Java+Spring Cloud +UniApp +MySql智慧工地综合管理云平台源码,SaaS模式
智慧工地围绕工程现场人、机、料、法、环及施工过程中质量、安全、进度、成本等各项数据满足工地多角色、多视角的有效监管,实现工程建设管理的降本增效. 智慧工地综合管理云平台源码,PC监管端、项目端;APP监管端、项目端、数据可视化大屏端源码…...

QMidi Pro for Mac:打造您的专属卡拉OK体验
你是否曾经厌倦于在KTV里与朋友们争夺麦克风?是否想要在家中享受自定义的卡拉OK体验?现在,有了QMidi Pro for Mac,一切变得简单而愉快! QMidi Pro是一款功能强大的卡拉OK播放器,专为Mac用户设计。它充分利…...
bindtap和catchtap的区别?
bindtap和catchtap都是小程序中用于绑定点击事件的方法。 1.bindtap的作用是绑定一个触摸事件并指定对应的处理函数。当用户点击或触摸相关元素时,会触发该事件,并执行相应的处理逻辑。 示例: <button bindtap"handleTap">…...

IDEA—java: 常量字符串过长问题解决
问题描述: Error: java: 常量字符串过长 问题分析: 字符串长度过长,导致 idea 默认使用的 javac 编译器编译不了。 解决办法: Javac 编译器改为 Eclipse 编译器。 File -> Settings -> Build,Execution,Deployment -&…...

云原生SIEM解决方案
云原生(Cloud Native)是一种基于云计算的软件开发和部署方法论,它强调将应用程序和服务设计为云环境下的原生应用,以实现高可用性、可扩展性和灵活性。 云原生的优势有哪些 高可用性:云原生可以实现应用程序的高可用…...
工艺边与定位孔设计经验规则总结
🏡《总目录》 目录 1,什么是工艺边和定位孔2,工艺边的设计经验原则2.1,避免尖锐角2.2,工艺边宽度设置2.3,工艺边的方向2.4,定位孔尺寸2.5,定位孔的位置3,去除工艺边的方法注意事项4,总结1,什么是工艺边和定位孔 工艺边是在SMT焊接时,为了PCB和导轨接触预留的PCB边…...

软件架构设计(业务架构、应用架构、数据架构、技术架构)
一、架构相关概念 1、系统 系统:由一群有关联的个体组成,根据某种规则运作,能完成个别原件不能独立完成的工作的群体。大的系统可以嵌套小系统,被嵌套的小系统往往称为大系统的子系统。 2、模块 模块是从逻辑上将系统分解&#…...

我们又组织了一次欧洲最大开源社区活动,Hugging Face 博客欢迎社区成员发帖、Hugging Chat 功能更新!...
每一周,我们的同事都会向社区的成员们发布一些关于 Hugging Face 相关的更新,包括我们的产品和平台更新、社区活动、学习资源和内容更新、开源库和模型更新等,我们将其称之为「Hugging News」。本期 Hugging News 有哪些有趣的消息࿰…...

学信息系统项目管理师第4版系列26_项目绩效域(下)
1. 项目工作绩效域 1.1. 涉及项目工作相关的活动和职能 1.2. 预期目标 1.2.1. 高效且有效的项目绩效 1.2.2. 适合项目和环境的项目过程 1.2.3. 干系人适当的沟通和参与 1.2.4. 对实物资源进行了有效管理 1.2.5. 对采购进行了有效管理 1.2.6. 有效处理了变更 1.2.7. 通…...

SQL sever中的索引
目录 一、索引定义 二、索引结构 2.1. B-树索引结构: 2.2. 哈希索引结构: 三、索引作用 四、索引与约束区别 五、索引级别 六、索引分类 6.1. 聚集索引(Clustered Index): 6.2. 非聚集索引(Noncl…...

多目标鳟海鞘算法(Multi-objective Salp Swarm Algorithm,MSSA)求解微电网优化MATLAB
一、微网系统运行优化模型 微电网优化模型介绍: 微电网多目标优化调度模型简介_IT猿手的博客-CSDN博客 参考文献: [1]李兴莘,张靖,何宇,等.基于改进粒子群算法的微电网多目标优化调度[J].电力科学与工程, 2021, 37(3):7 二、多目标鳟海鞘算法MSSA 多…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...

聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...