Last active
October 11, 2019 02:51
-
-
Save doloopwhile/1419f460fbe2c3561714a4cd3a20c390 to your computer and use it in GitHub Desktop.
Variable width bytes representation of uint64_t
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment