Help us understand the problem. What is going on with this article?

UTF-8風の可変長な整数の符号化方法をPythonで実装する

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))

https://gist.github.com/doloopwhile/1419f460fbe2c3561714a4cd3a20c390

補足

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')
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした