in 未分类

BASE64 VLQ 编码规则

首先我们先来了解下 VLQ 是什么,VLQ 是 Variable-length quantity 的缩写,是一种通用的,使用任意位数的二进制来表示一个任意大的数字的一种编码方式。这个编码方式是在 MIDI 文件格式中定义的,用来节省空间。在其他地方也有很多类似这样的编码格式,比如在 Google’s protocol buffers 中,还有我们马上要讨论到的 BASE64 VLQ 中。想了解的更多,请参考wikipedia

我们先来看看 MIDI 中的 VLQ 编码是如何编码 137 这个数字的吧:(摘抄自 wikipedia)

  • 先把 137 转换成二进制:10001001
  • 7 bit 一组,把二进制分开,不足的补 0 ,变成 0000001 0001001
  • 把最低的7位拿出来,在最高位补0表示最后一位,变成 0000 1001,这个作为最低位,放在最后边。
  • 在其他组的最高位补 1 ,表示没有结束,后面跟着还有数据。在这里就是 1000 0001
  • 拼在一起,就变成了 1000 0001 0000 1001 .

这就是 VLQ 的变化过程。

那么什么是 Base64 VLQ 呢?和上面的变换过程有什么区别呢?

我们可以先来参考我博客的另外一篇文章,先来回顾下 Base64 编码:BASE64 编码规则

我们可以看到 Base64 是一种可以把二进制数据编码成用 ASCII 表示的一种编码规则,但是受限于 Base64 采用的字符集,一个 Base64 字符只能表示 6bit 的数据。所以上面的 VLQ 中 7 bit 一组的分组方式,在这里就要变成 5 bit 一组的分组了。

另外,Base64 VLQ 需要能够表示负数,于是规定了需要先把数字变成无符号数,用最后一位来作为符号标志位。我们直接来做一个变换吧,这样理解的最快。在例子中可以看到和上面的 VLQ 编码还是有一定差别的。

不妨还拿 137 来做示例吧。

  • 先把 137 转换成二进制:10001001
  • 由于 137 是正数,所以在最低位补0 变成 100010010
  • 按照 5bit 一组的方式分组,变成 01000 10010
  • 按照从低位到高位的顺序,以 5bit 一组为单位,依次拿出数据做转换。
  • 先拿出第一组 10010 , 因为后面还有数据,所以需要在高位补 1,变成 110010 ,编码成 Base64: y
  • 再拿出第二组,也是我们这里的最后一组,01000 , 由于是最后一组,所以在高位补 0 变成 001000,编码成 Base64: I
  • 按照从低位到高位的顺序把这些 ASCII 字符拼接起来,变成 yI

可以看到在 VLQ 中,编码顺序是从高位到低位,在 Base64 VLQ 中,编码顺序是从低位到高位。

那么如何解码呢?相信了解了编码过程后,解码过程就不必再讲解了。平时也基本不会去手工去算这些东西。这里推荐一个在线编码解码的网站:http://murzwin.com/base64vlq.html , 同时如果你想在代码中使用,Mozilla 的一个开源库里有相关实现:https://github.com/mozilla/source-map/blob/master/lib/source-map/base64-vlq.js,这个是 javascript 的实现,其他语言的实现,如果你需要,请自己找找,或者根据编码规则自己写一个。

说了这么多,好像还没讲 Base64 VLQ 运用在什么地方,这次我不打算说了,准备下一篇博客再来解释这个问题。