dymokomi/luce-compress
Source of release 0.9.0
0.9.0 / tools / brotli_vectors.py
#!/usr/bin/env python3
"""Generate src/brotli/vectors.lucb: Brotli test vectors as tests of the module.
tools/brotli_vectors.py [--brotli BROTLI_CLI] [--python VENV_PYTHON]
Two kinds of stream:
* Reference streams: Google's `brotli` CLI compressing deterministic inputs (text and
binary made by a small generator the tests repeat in Luce) at a range of qualities
and windows, one with a metadata comment.
* A crafted stream that names a static dictionary word of every length (4-24) through
each of the 121 transforms, written here with simple and single-length prefix codes.
Google's decoder (Python's brotli module) must accept it; its output's CRC-32 and
length are what the test expects.
Each vector becomes a `test` block (compiled only for tests) that decodes the stream
whole and in small pieces and checks the output's length and CRC-32.
"""
import argparse
import shutil
import subprocess
import sys
import tempfile
import zlib
from pathlib import Path
ROOT = Path(__file__).resolve().parents[1]
OUTPUT = ROOT / "src/brotli/vectors.lucb"
NDBITS = [0, 0, 0, 0, 10, 10, 11, 11, 10, 10, 10, 10, 10, 9, 9, 8, 7, 7, 8, 7, 7, 6, 6, 5, 5]
COPY_BASE = [2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 18, 22, 30, 38, 54, 70, 102, 134, 198, 326, 582, 1094, 2118]
COPY_EXTRA = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 24]
def text(size, seed):
"""Deterministic words: an LCG over a word list."""
words = [b"the", b"brotli", b"window", b"of", b"and", b"stream", b"<div>", b"</div>", b"compression", b"\xc3\xa9t\xc3\xa9",
b"\xd0\xb4\xd0\xb0", b"\n", b"for", b"a", b"dictionary", b"0123", b"http://", b".com/", b"ing ", b"The "]
out, state = bytearray(), seed
while len(out) < size:
state = (state * 1103515245 + 12345) & 0x7FFFFFFF
out += words[(state >> 16) % len(words)] + b" "
return bytes(out[:size])
def binary(size, seed):
"""Records: a counter, a small varying field and a noisy byte."""
out, state = bytearray(), seed
while len(out) < size:
state = (state * 1103515245 + 12345) & 0x7FFFFFFF
out += (len(out) // 8).to_bytes(4, "little") + bytes([(state >> 16) & 3, 0, (state >> 20) & 0xFF, 7])
return bytes(out[:size])
class Bits:
def __init__(self):
self.value, self.count = 0, 0
def put(self, value, bits):
assert 0 <= value < (1 << bits) or bits == 0
self.value |= value << self.count
self.count += bits
def bytes(self):
return self.value.to_bytes((self.count + 7) // 8, "little")
def distance_code(distance):
"""Distance symbol and extra bits for NPOSTFIX 0, NDIRECT 0 (section 4)."""
for symbol in range(16, 64):
bits = 1 + ((symbol - 16) >> 1)
offset = ((2 + ((symbol - 16) & 1)) << bits) - 4
if offset < distance <= offset + (1 << bits):
return symbol, distance - offset - 1, bits
raise ValueError(distance)
def every_transform():
"""A stream of one meta-block per word length, each naming one word through every
transform (insert nothing, copy a dictionary word)."""
sys.path.insert(0, str(ROOT / "tools"))
import brotli_dictionary
rfc = (ROOT.parent / ".donors/rfc/rfc7932.txt").read_text(encoding="latin-1")
table = brotli_dictionary.rfc_transforms(rfc)
def produced(length, transform):
prefix, kind, suffix = table[transform]
word = length
if 3 <= kind <= 11:
word = max(0, word - (kind - 2))
elif kind >= 12:
word = max(0, word - (kind - 11))
return len(prefix) + word + len(suffix)
bits = Bits()
bits.put(0b0100001, 7) # WBITS 10: windows wrap
window = (1 << 10) - 16
total = 0
for length in range(4, 25):
code = next(c for c in range(24) if COPY_BASE[c] <= length < COPY_BASE[c] + (1 << COPY_EXTRA[c]))
symbol = 128 + code if code < 8 else 192 + code - 8 if code < 16 else 384 + code - 16
size = sum(produced(length, t) for t in range(121))
bits.put(0, 1) # ISLAST
nibbles = max(4, (size - 1).bit_length() + 3 >> 2)
bits.put(nibbles - 4, 2)
bits.put(size - 1, nibbles * 4)
bits.put(0, 1) # ISUNCOMPRESSED
for _ in range(3):
bits.put(0, 1) # NBLTYPES = 1
bits.put(0, 2) # NPOSTFIX
bits.put(0, 4) # NDIRECT
bits.put(2, 2) # literal context mode UTF8
bits.put(0, 1) # NTREESL = 1
bits.put(0, 1) # NTREESD = 1
bits.put(1, 2); bits.put(0, 2); bits.put(ord("x"), 8) # literals: one symbol
bits.put(1, 2); bits.put(0, 2); bits.put(symbol, 10) # commands: one symbol
# Distances: 64 symbols of 6 bits, a code length code of the single length 6.
bits.put(0, 2) # HSKIP 0
for value in (1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15):
if value == 6:
bits.put(0b10, 2) # code length 3 (any one nonzero length)
else:
bits.put(0, 2)
for transform in range(121):
index = (transform * 37 + length * 11) % (1 << NDBITS[length])
word_id = (transform << NDBITS[length]) | index
reach = min(total, window)
distance_symbol, extra, extra_bits = distance_code(reach + 1 + word_id)
bits.put(length - COPY_BASE[code], COPY_EXTRA[code])
reversed_code = int(f"{distance_symbol:06b}"[::-1], 2)
bits.put(reversed_code, 6)
bits.put(extra, extra_bits)
total += produced(length, transform)
bits.put(0b11, 2) # ISLAST, ISLASTEMPTY
return bits.bytes()
def rows(data):
"""`data` as little-endian 64-bit words, six to a line."""
data = data + bytes(-len(data) % 8)
words = [int.from_bytes(data[i:i + 8], "little") for i in range(0, len(data), 8)]
return ",\n".join(" " + ", ".join(f"0x{w:016x}" for w in words[i:i + 6]) for i in range(0, len(words), 6)) + ","
def main():
parser = argparse.ArgumentParser(description=__doc__)
parser.add_argument("--brotli", default=shutil.which("brotli"))
parser.add_argument("--python", required=True, help="an interpreter with the brotli module")
args = parser.parse_args()
vectors = []
with tempfile.TemporaryDirectory() as temporary:
source = Path(temporary) / "input"
for name, kind, size, seed, options in [
("text, quality 0, window 10", "text", 10000, 1, ["-q", "0", "-w", "10"]),
("text, quality 1, window 16", "text", 10000, 2, ["-q", "1", "-w", "16"]),
("text, quality 5, window 18", "text", 10000, 3, ["-q", "5", "-w", "18"]),
("text, quality 9, window 22", "text", 10000, 4, ["-q", "9", "-w", "22"]),
("text, quality 11, window 10", "text", 10000, 5, ["-q", "11", "-w", "10"]),
("text, quality 11, window 24, metadata", "text", 10000, 6, ["-q", "11", "-w", "24", "-C", "THVjZSBjb21wcmVzcw=="]),
("binary, quality 4, window 12", "binary", 12000, 7, ["-q", "4", "-w", "12"]),
("binary, quality 11, window 16", "binary", 12000, 8, ["-q", "11", "-w", "16"])]:
data = text(size, seed) if kind == "text" else binary(size, seed)
source.write_bytes(data)
packed = subprocess.run([args.brotli, *options, "-c", source], capture_output=True, check=True).stdout
vectors.append((name, kind, size, seed, packed, data))
crafted = every_transform()
check = "import brotli, sys; sys.stdout.buffer.write(brotli.decompress(sys.stdin.buffer.read()))"
expected = subprocess.run([args.python, "-c", check], input=crafted, capture_output=True, check=True).stdout
vectors.append(("every transform of a word of every length", "crafted", len(expected), 0, crafted, expected))
blocks = []
for name, kind, size, seed, packed, data in vectors:
blocks.append(f'''test "{name}":
let stream: u64[{(len(packed) + 7) // 8}] = [
{rows(packed)}
]
try check_vector(u8[]((u8*)&stream[0], {len(packed)}), {len(data)}, {zlib.crc32(data)})
''')
OUTPUT.write_text(f"""#==============================================================================================
#
# brotli/vectors - Reference and crafted streams (generated tests)
#
# DESCRIPTION:
# Generated by tools/brotli_vectors.py; do not edit. Streams from Google's brotli CLI
# (version {subprocess.run([args.brotli, "--version"], capture_output=True, text=True).stdout.split()[-1]}) over deterministic inputs, and a crafted stream naming a
# dictionary word of every length through each of the 121 transforms, which Google's
# decoder accepts. Each decodes whole and in pieces to the output's length and CRC-32 (the stream is held
# as little-endian 64-bit words).
#
#==============================================================================================
{chr(10).join(blocks)}""")
print(f"wrote {OUTPUT.relative_to(ROOT)}: {len(vectors)} vectors")
if __name__ == "__main__":
main()