Rubyの中間表現では、こんなのが使われているようです。
2. 整数値の符号化方法を変更
また、出力に含まれていたあらゆる整数値はほぼすべてが固定長で符号化され、4byteや8byteのデータ長で出力されていました。 しかし、出力される整数値はその出現頻度に大きな偏りがあり、多くが 0 や 1 などの少ないbit数で表現できる値です。 そこで、UTF-8を参考に可変長な整数の符号化方法を考え、導入することにしました。
0x0000000000000000 - 0x000000000000007f: 1byte | XXXXXXX1 | 0x0000000000000080 - 0x0000000000003fff: 2byte | XXXXXX10 | XXXXXXXX | 0x0000000000004000 - 0x00000000001fffff: 3byte | XXXXX100 | XXXXXXXX | XXXXXXXX | 0x0000000000020000 - 0x000000000fffffff: 4byte | XXXX1000 | XXXXXXXX | XXXXXXXX | XXXXXXXX | ... 0x0001000000000000 - 0x00ffffffffffffff: 8byte | 10000000 | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | 0x0100000000000000 - 0xffffffffffffffff: 9byte | 00000000 | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX |この方法では、7bitで十分に表現できる値は1byteに、14bitで表現できる値は2byteに、というように符号化する整数の大きさによって必要なバイト長を変化させています。
Ruby中間表現のバイナリ出力を改善する - クックパッド開発者ブログ
https://techlife.cookpad.com/
Pythonでこれを実装してみましょう。
実装してみた
実装してみました。
書きやすさ優先で、Rubyのと若干仕様を変えています。
なお、（言うまでもなく）Python標準の数値演算は遅いので、今回のコードはあまり実用的ではないでしょう。
'''
Variable width bytes representation of uint64_t.
Inspired by Ruby interpreter。
https://techlife.cookpad.com/entry/2019/09/26/143000
> 0x0000000000000000 - 0x000000000000007f: 1byte | 1XXXXXXX |
> 0x0000000000000080 - 0x0000000000003fff: 2bytes | 01XXXXXX | XXXXXXXX |
> 0x0000000000004000 - 0x00000000001fffff: 3bytes | 001XXXXX | XXXXXXXX | XXXXXXXX |
> 0x0000000000020000 - 0x000000000fffffff: 4bytes | 0001XXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX |
> ...
> 0x0001000000000000 - 0x00ffffffffffffff: 8bytes | 00000001 | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX |
> 0x0100000000000000 - 0xffffffffffffffff: 9bytes | 00000000 | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX | XXXXXXXX |
'''
from typing import List, Tuple
def pack(n: int) -> bytes:
if n < 0:
raise ValueError("negative number is not supported")
l = n.bit_length()
if l > 64:
raise ValueError("too large")
s = (l - 1) // 7 + 1
if s > 8:
return b"\0" + n.to_bytes(8, "big")
else:
packed = bytearray(n.to_bytes(s, "big"))
packed[0] = packed[0] | (0x100 >> s)
return bytes(packed)
def unpack(packed: bytes) -> Tuple[int, int]:
size = 8 - packed[0].bit_length()
b = bytearray(packed[:size])
b[0] = packed[0] & (0xFF >> size)
return int.from_bytes(b, "big"), size
def test():
cases = [
(1, 0b10000001 .to_bytes(1, "big")),
(0b01111111, 0b11111111 .to_bytes(1, "big")),
(0b00111111_11111111, 0b01111111_11111111 .to_bytes(2, "big")),
(
0b00000000_11111111_11111111_11111111_11111111_11111111_11111111_11111111,
0b00000001_11111111_11111111_11111111_11111111_11111111_11111111_11111111 .to_bytes(
8, "big"
),
),
(
0b00000000_11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111,
0b00000000_11111111_11111111_11111111_11111111_11111111_11111111_11111111_11111111 .to_bytes(
9, "big"
),
),
]
for n, packed in cases:
assert pack(n) == packed
assert unpack(packed) == (n, len(packed))
補足
Pythonにはビット単位演算 が昔からあります。内容はC言語と同じです（x ^ y, x & y, x | y, x << n, x >> n, ~x）。
また、整数←→バイト列の変換をするためのライブラリとして、structも昔から備わっています。
2バイト整数×2 と 4バイト整数×1 のエンコード・デコード
>>> from struct import *
>>> pack('hhl', 1, 2, 3)
b'\x00\x01\x00\x02\x00\x00\x00\x03'
>>> unpack('hhl', b'\x00\x01\x00\x02\x00\x00\x00\x03')
(1, 2, 3)
今回のコードでは、最近（と言っても3.2で）追加されたint型のメンバ関数を使っています。
-
int.bit_length(): 整数を表現するのに必要なビット数 -
int.to_bytes(length, byteorder): 整数 → バイト列 -
int.from_bytes(bytes, byteorder): バイト列 → 整数
開発中に数値のビット表現を見るには組み込み関数の bin(n)や、format関数、f-string が使えます。
>>> bin(3)
'0b11'
>>> bin(-10)
'-0b1010'
>>> format(14, '#b'), format(14, 'b')
('0b1110', '1110')
>>> f'{14:#b}', f'{14:b}'
('0b1110', '1110')