"""Pure-Python Zstandard frame decoder, stdlib-only (ADR-0001).

Independently written from RFC 8878 ("Zstandard Compression and the

application/zstd Media Type"): frame/block format (section 3.1.1), literals

section with Huffman coding (3.1.1.3.1, 4.2), sequences section with FSE

(3.1.1.3.2, 4.1), sequence execution and repeat offsets (3.1.1.4-3.1.1.5),

and the optional XXH64 content checksum. Dictionaries are not supported (Oak

never uses them). It shares no code with libzstd, which both Oak and the

``zstandard`` Python package link, so a decode here is independent of the

subject's codec. Every malformed input raises ``ZstdError``; bounds raise

``ZstdBoundError`` so callers can separate harness limits from bad bytes.

``encode_raw`` builds a valid frame of uncompressed (Raw) blocks; tests use

it to author stored objects without a compressor dependency.

"""

from __future__ import annotations

import struct

MAGIC = 0xFD2FB528

MAX_BLOCK = 128 * 1024

class ZstdError(ValueError):

    """Positively malformed or inconsistent compressed bytes."""

class ZstdBoundError(ValueError):

    """Input is well-formed so far but exceeds a caller-imposed bound."""

# --- XXH64 (content checksum) -------------------------------------------------

_P1, _P2, _P3, _P4, _P5 = (11400714785074694791, 14029467366897019727, 1609587929392839161,

                           9650029242287828579, 2870177450012600261)

_U64 = 0xFFFFFFFFFFFFFFFF

def _rotl(x, r):

    return ((x << r) | (x >> (64 - r))) & _U64

def _round(acc, lane):

    return (_rotl((acc + lane * _P2) & _U64, 31) * _P1) & _U64

def xxh64(data: bytes, seed: int = 0) -> int:

    n = len(data)

    i = 0

    if n >= 32:

        v1, v2, v3, v4 = (seed + _P1 + _P2) & _U64, (seed + _P2) & _U64, seed, (seed - _P1) & _U64

        while i + 32 <= n:

            a, b, c, d = struct.unpack_from('<4Q', data, i)

            v1, v2, v3, v4 = _round(v1, a), _round(v2, b), _round(v3, c), _round(v4, d)

            i += 32

        h = (_rotl(v1, 1) + _rotl(v2, 7) + _rotl(v3, 12) + _rotl(v4, 18)) & _U64

        for v in (v1, v2, v3, v4):

            h = ((h ^ _round(0, v)) * _P1 + _P4) & _U64

    else:

        h = (seed + _P5) & _U64

    h = (h + n) & _U64

    while i + 8 <= n:

        (lane,) = struct.unpack_from('<Q', data, i)

        h = (_rotl(h ^ _round(0, lane), 27) * _P1 + _P4) & _U64

        i += 8

    if i + 4 <= n:

        (lane,) = struct.unpack_from('<I', data, i)

        h = (_rotl(h ^ (lane * _P1 & _U64), 23) * _P2 + _P3) & _U64

        i += 4

    while i < n:

        h = (_rotl(h ^ (data[i] * _P5 & _U64), 11) * _P1) & _U64

        i += 1

    h ^= h >> 33

    h = (h * _P2) & _U64

    h ^= h >> 29

    h = (h * _P3) & _U64

    h ^= h >> 32

    return h

# --- bit readers --------------------------------------------------------------

class _ForwardBits:

    """Little-endian forward bit reader (FSE table descriptions)."""

    def __init__(self, data: bytes, start: int, end: int):

        self.data, self.pos, self.end = data, start * 8, end * 8

    def read(self, n: int) -> int:

        if n == 0:

            return 0

        if self.pos + n > self.end:

            raise ZstdError('FSE table description overruns its section')

        byte = self.pos >> 3

        value = int.from_bytes(self.data[byte:byte + 8], 'little') >> (self.pos & 7)

        self.pos += n

        return value & ((1 << n) - 1)

    def peek(self, n: int) -> int:

        byte = self.pos >> 3

        value = int.from_bytes(self.data[byte:byte + 8], 'little') >> (self.pos & 7)

        available = self.end - self.pos

        if available < n:

            value &= (1 << max(available, 0)) - 1

        return value & ((1 << n) - 1)

    def consumed_bytes(self, start: int) -> int:

        return (self.pos + 7) // 8 - start

class _BackwardBits:

    """Reverse bitstream (RFC 8878 4.1/4.2.2): read from the end toward the start.

    ``offset`` may go negative: missing low bits read as zero, and callers use

    the sign to detect overflow exactly as the RFC's end-of-stream rules do.

    """

    def __init__(self, data: bytes):

        if not data:

            raise ZstdError('empty bitstream')

        last = data[-1]

        if last == 0:

            raise ZstdError('bitstream final byte lacks padding marker')

        self.data = data

        self.offset = len(data) * 8 - (8 - (last.bit_length() - 1))

    def _at(self, offset: int, n: int) -> int:

        if n == 0:

            return 0

        if offset >= 0:

            byte = offset >> 3

            value = int.from_bytes(self.data[byte:byte + 8], 'little') >> (offset & 7)

            return value & ((1 << n) - 1)

        if offset + n <= 0:

            return 0

        value = int.from_bytes(self.data[:8], 'little') << (-offset)

        return value & ((1 << n) - 1)

    def read(self, n: int) -> int:

        self.offset -= n

        return self._at(self.offset, n)

    def peek(self, n: int) -> int:

        return self._at(self.offset - n, n)

# --- FSE ----------------------------------------------------------------------

def _read_fse_description(data: bytes, start: int, end: int, max_log: int, max_symbol: int):

    """Normalized counts from an FSE table description; returns (probs, log, used_bytes)."""

    bits = _ForwardBits(data, start, end)

    log = bits.read(4) + 5

    if log > max_log:

        raise ZstdError('FSE accuracy log too large')

    size = 1 << log

    remaining = size + 1

    threshold = size

    nb = log + 1

    probs = []

    while remaining > 1:

        if len(probs) > max_symbol:

            raise ZstdError('FSE description has too many symbols')

        maximum = 2 * threshold - 1 - remaining

        low = bits.peek(nb - 1)

        if low < maximum:

            count = low

            bits.read(nb - 1)

        else:

            count = bits.peek(nb)

            if count >= threshold:

                count -= maximum

            bits.read(nb)

        count -= 1

        remaining -= abs(count)

        probs.append(count)

        if count == 0:

            while True:

                repeat = bits.read(2)

                probs.extend([0] * repeat)

                if repeat != 3:

                    break

        while remaining < threshold and threshold > 1:

            nb -= 1

            threshold >>= 1

    if remaining != 1 or len(probs) > max_symbol + 1:

        raise ZstdError('FSE description probabilities do not sum to table size')

    return probs, log, bits.consumed_bytes(start)

def _build_fse(probs, log):

    """Decoding table: list of (symbol, nb_bits, baseline) indexed by state."""

    size = 1 << log

    symbol = [0] * size

    high = size - 1

    next_count = [0] * len(probs)

    for s, p in enumerate(probs):

        if p == -1:

            symbol[high] = s

            high -= 1

            next_count[s] = 1

        else:

            next_count[s] = p

    step = (size >> 1) + (size >> 3) + 3

    mask = size - 1

    position = 0

    for s, p in enumerate(probs):

        for _ in range(p if p > 0 else 0):

            symbol[position] = s

            position = (position + step) & mask

            while position > high:

                position = (position + step) & mask

    if position != 0:

        raise ZstdError('FSE table spread inconsistent')

    table = []

    for state in range(size):

        s = symbol[state]

        n = next_count[s]

        next_count[s] += 1

        nb = log - (n.bit_length() - 1)

        table.append((s, nb, (n << nb) - size))

    return table, log

def _rle_table(value):

    return [(value, 0, 0)], 0

# Predefined distributions (RFC 8878 3.1.1.3.2.2).

_LL_DEFAULT = _build_fse([4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1,

                          1, 1, -1, -1, -1, -1], 6)

_ML_DEFAULT = _build_fse([1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

                          1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1], 6)

_OF_DEFAULT = _build_fse([1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1,

                          -1], 5)

_LL_BASE = list(range(16)) + [16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 128, 256, 512, 1024, 2048, 4096,

                              8192, 16384, 32768, 65536]

_LL_BITS = [0] * 16 + [1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

_ML_BASE = [n + 3 for n in range(32)] + [35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 131, 259, 515, 1027,

                                         2051, 4099, 8195, 16387, 32771, 65539]

_ML_BITS = [0] * 32 + [1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

# --- Huffman ------------------------------------------------------------------

def _read_huffman(data: bytes, start: int, end: int):

    """Decode a Huffman tree description; returns ((symbols, bits, max_bits), used)."""

    if start >= end:

        raise ZstdError('missing Huffman tree description')

    header = data[start]

    if header >= 128:

        count = header - 127

        used = 1 + (count + 1) // 2

        if start + used > end:

            raise ZstdError('Huffman weights overrun')

        weights = []

        for i in range(count):

            byte = data[start + 1 + i // 2]

            weights.append(byte >> 4 if i % 2 == 0 else byte & 15)

    else:

        used = 1 + header

        if start + used > end:

            raise ZstdError('Huffman FSE weights overrun')

        probs, log, desc = _read_fse_description(data, start + 1, start + used, 6, 255)

        table, log = _build_fse(probs, log)

        stream = data[start + 1 + desc:start + used]

        bits = _BackwardBits(stream)

        state1 = bits.read(log)

        state2 = bits.read(log)

        weights = []

        while True:

            if len(weights) > 255:

                raise ZstdError('too many Huffman weights')

            s, nb, base = table[state1]

            weights.append(s)

            state1 = base + bits.read(nb)

            if bits.offset < 0:

                weights.append(table[state2][0])

                break

            s, nb, base = table[state2]

            weights.append(s)

            state2 = base + bits.read(nb)

            if bits.offset < 0:

                weights.append(table[state1][0])

                break

    if len(weights) > 255:

        raise ZstdError('too many Huffman weights')

    total = 0

    for w in weights:

        if w > 11:

            raise ZstdError('Huffman weight too large')

        if w:

            total += 1 << (w - 1)

    if total == 0:

        raise ZstdError('empty Huffman weights')

    max_bits = total.bit_length()

    left = (1 << max_bits) - total

    if left & (left - 1):

        raise ZstdError('Huffman weights do not complete a power of two')

    weights.append(left.bit_length())

    if max_bits > 11:

        raise ZstdError('Huffman code too long')

    bits_per_symbol = [max_bits + 1 - w if w else 0 for w in weights]

    rank_count = [0] * (max_bits + 2)

    for b in bits_per_symbol:

        if b:

            rank_count[b] += 1

    rank_index = [0] * (max_bits + 2)

    for b in range(max_bits, 0, -1):

        rank_index[b - 1] = rank_index[b] + rank_count[b] * (1 << (max_bits - b))

    size = 1 << max_bits

    symbols = [0] * size

    lengths = [0] * size

    for symbol, b in enumerate(bits_per_symbol):

        if not b:

            continue

        span = 1 << (max_bits - b)

        code = rank_index[b]

        if code + span > size:

            raise ZstdError('Huffman table overflow')

        for j in range(code, code + span):

            symbols[j] = symbol

            lengths[j] = b

        rank_index[b] += span

    return (symbols, lengths, max_bits), used

def _huffman_stream(stream: bytes, table, count: int, out: bytearray):

    symbols, lengths, max_bits = table

    bits = _BackwardBits(stream)

    for _ in range(count):

        index = bits.peek(max_bits)

        out.append(symbols[index])

        bits.offset -= lengths[index]

    if bits.offset != 0:

        raise ZstdError('Huffman stream not fully consumed')

# --- frames and blocks --------------------------------------------------------

class _FrameState:

    def __init__(self):

        self.huffman = None

        self.tables = [None, None, None]  # LL, OF, ML

        self.reps = [1, 4, 8]

def _literals(block: bytes, state: _FrameState):

    kind = block[0] & 3

    size_format = (block[0] >> 2) & 3

    if kind in (0, 1):

        if size_format in (0, 2):

            regen, header = block[0] >> 3, 1

        elif size_format == 1:

            if len(block) < 2:

                raise ZstdError('truncated literals header')

            regen, header = (block[0] | block[1] << 8) >> 4, 2

        else:

            if len(block) < 3:

                raise ZstdError('truncated literals header')

            regen, header = (block[0] | block[1] << 8 | block[2] << 16) >> 4, 3

        if kind == 0:

            if header + regen > len(block):

                raise ZstdError('raw literals overrun block')

            return bytes(block[header:header + regen]), header + regen

        if header + 1 > len(block):

            raise ZstdError('RLE literals overrun block')

        return bytes([block[header]]) * regen, header + 1

    header = {0: 3, 1: 3, 2: 4, 3: 5}[size_format]

    if len(block) < header:

        raise ZstdError('truncated literals header')

    h = int.from_bytes(block[:header], 'little')

    if size_format in (0, 1):

        regen, comp = (h >> 4) & 0x3FF, (h >> 14) & 0x3FF

    elif size_format == 2:

        regen, comp = (h >> 4) & 0x3FFF, (h >> 18) & 0x3FFF

    else:

        regen, comp = (h >> 4) & 0x3FFFF, (h >> 22) & 0x3FFFF

    if regen > MAX_BLOCK or header + comp > len(block):

        raise ZstdError('compressed literals overrun block')

    start, end = header, header + comp

    if kind == 2:

        state.huffman, used = _read_huffman(block, start, end)

        start += used

    elif state.huffman is None:

        raise ZstdError('treeless literals without a previous Huffman table')

    out = bytearray()

    if size_format == 0:

        _huffman_stream(block[start:end], state.huffman, regen, out)

    else:

        if start + 6 > end:

            raise ZstdError('truncated literal jump table')

        s1, s2, s3 = struct.unpack_from('<3H', block, start)

        start += 6

        s4 = end - start - s1 - s2 - s3

        if s4 < 1:

            raise ZstdError('invalid literal stream sizes')

        each = (regen + 3) // 4

        counts = (each, each, each, regen - 3 * each)

        if counts[3] < 0:

            raise ZstdError('invalid literal regenerated size')

        for size, count in zip((s1, s2, s3, s4), counts):

            _huffman_stream(block[start:start + size], state.huffman, count, out)

            start += size

    if len(out) != regen:

        raise ZstdError('literal size mismatch')

    return bytes(out), end

def _sequence_table(block, pos, mode, index, state, default, max_log, max_symbol):

    if mode == 0:

        table = default

    elif mode == 1:

        if pos >= len(block):

            raise ZstdError('truncated RLE sequence table')

        if block[pos] > max_symbol:

            raise ZstdError('RLE sequence symbol out of range')

        table = _rle_table(block[pos])

        pos += 1

    elif mode == 2:

        probs, log, used = _read_fse_description(block, pos, len(block), max_log, max_symbol)

        table = _build_fse(probs, log)

        pos += used

    else:

        table = state.tables[index]

        if table is None:

            raise ZstdError('repeat sequence table without a previous table')

    state.tables[index] = table

    return pos

def _compressed_block(block: bytes, state: _FrameState, out: bytearray, limit: int,

                      frame_start: int = 0, window: int = None):

    if not block:

        raise ZstdError('empty compressed block')

    literals, pos = _literals(block, state)

    if pos >= len(block):

        raise ZstdError('missing sequences section')

    b0 = block[pos]

    if b0 == 0:

        count, pos = 0, pos + 1

    elif b0 < 128:

        count, pos = b0, pos + 1

    elif b0 < 255:

        if pos + 2 > len(block):

            raise ZstdError('truncated sequence count')

        count, pos = ((b0 - 128) << 8) + block[pos + 1], pos + 2

    else:

        if pos + 3 > len(block):

            raise ZstdError('truncated sequence count')

        count, pos = block[pos + 1] + (block[pos + 2] << 8) + 0x7F00, pos + 3

    if count == 0:

        if pos != len(block):

            raise ZstdError('trailing bytes after empty sequences section')

        if len(out) + len(literals) > limit:

            raise ZstdBoundError('decompressed output exceeds bound')

        out += literals

        return

    if pos >= len(block):

        raise ZstdError('missing sequence modes')

    modes = block[pos]

    if modes & 3:

        raise ZstdError('reserved sequence mode bits set')

    pos += 1

    pos = _sequence_table(block, pos, modes >> 6, 0, state, _LL_DEFAULT, 9, 35)

    pos = _sequence_table(block, pos, (modes >> 4) & 3, 1, state, _OF_DEFAULT, 8, 31)

    pos = _sequence_table(block, pos, (modes >> 2) & 3, 2, state, _ML_DEFAULT, 9, 52)

    if pos >= len(block):

        raise ZstdError('missing sequence bitstream')

    (ll_table, ll_log), (of_table, of_log), (ml_table, ml_log) = state.tables

    bits = _BackwardBits(block[pos:])

    ll_state = bits.read(ll_log)

    of_state = bits.read(of_log)

    ml_state = bits.read(ml_log)

    reps = state.reps

    lit_pos = 0

    for i in range(count):

        of_code = of_table[of_state][0]

        ll_code = ll_table[ll_state][0]

        ml_code = ml_table[ml_state][0]

        if of_code > 31:

            raise ZstdError('offset code out of range')

        offset_value = (1 << of_code) + bits.read(of_code)

        ml = _ML_BASE[ml_code] + bits.read(_ML_BITS[ml_code])

        ll = _LL_BASE[ll_code] + bits.read(_LL_BITS[ll_code])

        if offset_value > 3:

            offset = offset_value - 3

            reps[2], reps[1], reps[0] = reps[1], reps[0], offset

        else:

            index = offset_value - 1 + (1 if ll == 0 else 0)

            if index == 0:

                offset = reps[0]

            else:

                offset = reps[index] if index < 3 else reps[0] - 1

                if index > 1:

                    reps[2] = reps[1]

                reps[1] = reps[0]

                reps[0] = offset

        if lit_pos + ll > len(literals):

            raise ZstdError('sequence literal length overruns literals')

        if len(out) + ll + ml > limit:

            raise ZstdBoundError('decompressed output exceeds bound')

        out += literals[lit_pos:lit_pos + ll]

        lit_pos += ll

        # Matches may reach only this frame's own output (no dictionary, no

        # previous frame) and never further back than the declared window.

        if offset == 0 or offset > len(out) - frame_start or (window is not None and offset > window):

            raise ZstdError('match offset outside frame window')

        start = len(out) - offset

        if offset >= ml:

            out += out[start:start + ml]

        else:

            for j in range(ml):

                out.append(out[start + j])

        if i != count - 1:

            s, nb, base = ll_table[ll_state]

            ll_state = base + bits.read(nb)

            s, nb, base = ml_table[ml_state]

            ml_state = base + bits.read(nb)

            s, nb, base = of_table[of_state]

            of_state = base + bits.read(nb)

    if bits.offset != 0:

        raise ZstdError('sequence bitstream not fully consumed')

    rest = literals[lit_pos:]

    if len(out) + len(rest) > limit:

        raise ZstdBoundError('decompressed output exceeds bound')

    out += rest

def frame_content_size(data: bytes):

    """Declared content size of the first frame, or None when absent."""

    return _frame_header(data, 0)[1]

def _frame_header(data: bytes, pos: int):

    if len(data) < pos + 5:

        raise ZstdError('truncated frame header')

    (magic,) = struct.unpack_from('<I', data, pos)

    if magic != MAGIC:

        raise ZstdError('not a zstd frame')

    descriptor = data[pos + 4]

    fcs_flag = descriptor >> 6

    single = (descriptor >> 5) & 1

    if descriptor & 0x08:

        raise ZstdError('reserved frame descriptor bit set')

    checksum = (descriptor >> 2) & 1

    dict_flag = descriptor & 3

    pos += 5

    window = None

    if not single:

        if pos >= len(data):

            raise ZstdError('truncated window descriptor')

        wd = data[pos]

        exponent, mantissa = wd >> 3, wd & 7

        base = 1 << (10 + exponent)

        window = base + (base // 8) * mantissa

        pos += 1

    dict_size = (0, 1, 2, 4)[dict_flag]

    if dict_size:

        if pos + dict_size > len(data):

            raise ZstdError('truncated dictionary id')

        if int.from_bytes(data[pos:pos + dict_size], 'little'):

            raise ZstdError('dictionary frames are not supported')

        pos += dict_size

    fcs_size = (1 if single else 0, 2, 4, 8)[fcs_flag]

    content_size = None

    if fcs_size:

        if pos + fcs_size > len(data):

            raise ZstdError('truncated frame content size')

        content_size = int.from_bytes(data[pos:pos + fcs_size], 'little')

        if fcs_size == 2:

            content_size += 256

        pos += fcs_size

    if single:

        window = content_size

    return pos, content_size, window, checksum

def decompress(data: bytes, max_output: int = 64 * 1024 * 1024, max_window: int = None) -> bytes:

    """Decode every frame in ``data`` (skippable frames ignored); trailing garbage is an error."""

    try:

        return _decompress(data, max_output, max_window)

    except (IndexError, KeyError, struct.error, OverflowError) as exc:

        # Malformed input must never escape as an instrument crash.

        raise ZstdError(f'malformed frame: {type(exc).__name__}') from exc

def _decompress(data, max_output, max_window):

    data = bytes(data)

    out = bytearray()

    pos = 0

    frames = 0

    while pos < len(data) or frames == 0:

        if len(data) - pos >= 4 and (struct.unpack_from('<I', data, pos)[0] & 0xFFFFFFF0) == 0x184D2A50:

            if pos + 8 > len(data):

                raise ZstdError('truncated skippable frame')

            (size,) = struct.unpack_from('<I', data, pos + 4)

            if pos + 8 + size > len(data):

                raise ZstdError('truncated skippable frame')

            pos += 8 + size

            frames += 1

            continue

        pos, content_size, window, checksum = _frame_header(data, pos)

        if max_window is not None and window is not None and window > max_window:

            raise ZstdBoundError('decompression window exceeds bound')

        if content_size is not None and content_size > max_output - len(out):

            raise ZstdBoundError('declared content size exceeds bound')

        frame_start = len(out)

        state = _FrameState()

        while True:

            if pos + 3 > len(data):

                raise ZstdError('truncated block header')

            header = data[pos] | data[pos + 1] << 8 | data[pos + 2] << 16

            pos += 3

            last, kind, size = header & 1, (header >> 1) & 3, header >> 3

            if kind == 3:

                raise ZstdError('reserved block type')

            if size > MAX_BLOCK:

                raise ZstdError('block exceeds maximum size')

            if kind == 1:

                if pos + 1 > len(data):

                    raise ZstdError('truncated RLE block')

                if len(out) + size > max_output:

                    raise ZstdBoundError('decompressed output exceeds bound')

                out += bytes([data[pos]]) * size

                pos += 1

            else:

                if pos + size > len(data):

                    raise ZstdError('truncated block')

                if kind == 0:

                    if len(out) + size > max_output:

                        raise ZstdBoundError('decompressed output exceeds bound')

                    out += data[pos:pos + size]

                else:

                    _compressed_block(data[pos:pos + size], state, out, max_output, frame_start, window)

                pos += size

            if last:

                break

        produced = len(out) - frame_start

        if content_size is not None and produced != content_size:

            raise ZstdError('frame content size mismatch')

        if checksum:

            if pos + 4 > len(data):

                raise ZstdError('truncated content checksum')

            (stored,) = struct.unpack_from('<I', data, pos)

            if xxh64(bytes(out[frame_start:])) & 0xFFFFFFFF != stored:

                raise ZstdError('content checksum mismatch')

            pos += 4

        frames += 1

    return bytes(out)

def encode_raw(payload: bytes, checksum: bool = True) -> bytes:

    """A valid zstd frame holding ``payload`` in Raw blocks (no compression)."""

    payload = bytes(payload)

    descriptor = (3 << 6) | (4 if checksum else 0)  # 8-byte content size, not single-segment

    out = bytearray(struct.pack('<IB', MAGIC, descriptor))

    out.append((17 - 10) << 3)  # window 128 KiB

    out += struct.pack('<Q', len(payload))

    blocks = [payload[i:i + MAX_BLOCK] for i in range(0, len(payload), MAX_BLOCK)] or [b'']

    for index, block in enumerate(blocks):

        last = 1 if index == len(blocks) - 1 else 0

        header = last | (0 << 1) | (len(block) << 3)

        out += header.to_bytes(3, 'little') + block

    if checksum:

        out += struct.pack('<I', xxh64(payload) & 0xFFFFFFFF)

    return bytes(out)