Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.1

0.9.1 / src / zstd / tests.lucb

#==============================================================================================
#
#   zstd/tests - The module's tests
#
#   DESCRIPTION:
#       Hand-made frames (empty, raw, RLE, skippable, damaged headers), the predefined
#       tables against the format's Appendix A, encoder round trips at every level over
#       text, records, runs and noise of many sizes, and every truncation and many
#       corruptions of frames failing cleanly; vectors.lucb adds reference frames.
#
#==============================================================================================

# mark: Helpers ===============================================================================

## CRC-32 (ISO 3309), bit by bit: the vectors' check, kept apart from the codecs.
func checksum(data: const u8[]) -> u32:
    var crc: u32 = 0xFFFFFFFF
    for byte in data:
        crc ^= (u32)byte
        for _ in 0..<8:
            crc = (crc >> 1) ^ (0xEDB88320 if crc & 1 != 0 else 0)
    return ~crc

## Check a frame: decoded whole and into an exact buffer, to `size` bytes of CRC-32
## `crc`; one byte less of room fails with `limit`.
func check_vector(frame: const u8[], size: usize, crc: u32) -> !:
    let whole = try decode(frame)
    assert(whole.length == size and checksum(whole) == crc)
    free(whole) in memory.heap
    var into = try new u8[size] in memory.heap
    defer free(into) in memory.heap
    assert(try decode_into(frame, into) == size and checksum(into) == crc)
    if size > 0:
        assert(failure_of(frame, size - 1) == limit)

## The failure code of decoding `frame` whole, or `invalid` when it decodes.
func failure_of(frame: const u8[], max_output: usize = default_limit) -> ErrorCode:
    let output = decode(frame, max_output) catch failure:
        return failure.code
    free(output) in memory.heap
    return invalid

## Deterministic words, as tools/zstd_vectors.py makes them.
func sample_text(output: u8[], seed: u32):
    let words = ["the", "zstd", "window", "of", "and", "frame", "<div>", "</div>", "sequence", "été",
        "\n", "for", "a", "literal", "0123", "http://", ".com/", "ing ", "The ", "block"]
    var at: usize = 0
    var state = seed
    while at < output.length:
        state = (state *% 1103515245 +% 12345) & 0x7FFFFFFF
        let word = words[(usize)((state >> 16) % 20)]
        for byte in word.bytes:
            if at < output.length:
                output[at] = byte
                at += 1
        if at < output.length:
            output[at] = 32
            at += 1

## Records like SPZ's attribute streams: quantized fields with some noise.
func sample_records(output: u8[], seed: u32):
    var state = seed
    for at in 0..<output.length:
        state = state *% 1103515245 +% 12345
        let noise = (u8)(state >> 24)
        output[at] = (u8)(at // 3 % 7) +% (noise & 7) if at % 3 != 2 else noise

## Bytes from a 32-bit LCG: incompressible.
func sample_noise(output: u8[], seed: u32):
    var state = seed
    for at in 0..<output.length:
        state = state *% 1664525 +% 1013904223
        output[at] = (u8)(state >> 24)

## Encode `data` at `level` and decode it back.
func round_trip(data: const u8[], level: i32) -> !:
    let packed = try encode(data, level)
    defer free(packed) in memory.heap
    let back = try decode(packed, data.length)
    defer free(back) in memory.heap
    assert(back.length == data.length)
    for at in 0..<data.length:
        assert(back[at] == data[at])

# mark: Hand-made frames ======================================================================

test "raw, RLE and empty blocks, single segment and windowed":
    # Single segment of 5 bytes, one raw last block "hello", no checksum.
    let raw = b"\x28\xb5\x2f\xfd\x20\x05\x29\x00\x00hello"
    let out = try decode(raw)
    assert((str)out == "hello")
    free(out) in memory.heap
    # Window 1 KiB, no content size: an RLE block of 7 'z', then an empty last raw block.
    let rle = b"\x28\xb5\x2f\xfd\x00\x00\x3a\x00\x00z\x01\x00\x00"
    let zs = try decode(rle)
    assert((str)zs == "zzzzzzz")
    free(zs) in memory.heap
    # Trailing bytes, a reserved bit, a reserved block type, a dictionary and a size lie.
    assert(failure_of(b"\x28\xb5\x2f\xfd\x20\x05\x29\x00\x00helloX") == corrupt)
    let trailing = try decode(b"\x28\xb5\x2f\xfd\x20\x05\x29\x00\x00hello!!!!!", allow_trailing = true)
    free(trailing) in memory.heap
    assert(failure_of(b"\x28\xb5\x2f\xfd\x28\x05\x29\x00\x00hello") == corrupt)
    assert(failure_of(b"\x28\xb5\x2f\xfd\x20\x05\x2f\x00\x00hello") == corrupt)
    assert(failure_of(b"\x28\xb5\x2f\xfd\x21\x07\x05\x29\x00\x00hello") == unsupported)
    assert(failure_of(b"\x28\xb5\x2f\xfd\x20\x06\x29\x00\x00hello") == corrupt)
    assert(failure_of(b"") == corrupt)
    assert(failure_of(b"\x28\xb5\x2f") == corrupt)

test "a skippable frame alone, and a block larger than the window":
    let skip = b"\x5f\x2a\x4d\x18\x02\x00\x00\x00ab"
    let out = try decode(skip)
    assert(out.length == 0)
    free(out) in memory.heap
    assert(failure_of(b"\x5f\x2a\x4d\x18\x03\x00\x00\x00ab") == corrupt)
    # A 1 KiB window holds at most 1 KiB blocks: an RLE block of 1025 fails.
    assert(failure_of(b"\x28\xb5\x2f\xfd\x00\x00\x0b\x20\x00z") == corrupt)

test "a compressed block of exactly 128 KiB of raw literals":
    # zstd's golden block-128k.zst: window 128 KiB, one compressed block of 131072
    # bytes holding 131068 raw literals and no sequences.
    var frame = try new u8[131081] in memory.heap
    defer free(frame) in memory.heap
    let head = b"\x28\xb5\x2f\xfd\x00\x38\x05\x00\x10\xcc\xff\x1f"
    memory.copy(frame, head, head.length)
    try check_vector(frame, 131068, 2334817000)

test "the predefined tables match the format's Appendix A":
    var table: SeqTable
    table.build(&literals_default[0], 36, 6, &literals_bases[0], &literals_extras[0])
    # State: baseline (the code's), state bits, next-state base.
    assert(table.rows[0].base == 0 and table.rows[0].bits == 4 and table.rows[0].next == 0)
    assert(table.rows[1].base == 0 and table.rows[1].bits == 4 and table.rows[1].next == 16)
    assert(table.rows[2].base == 1 and table.rows[2].bits == 5 and table.rows[2].next == 32)
    assert(table.rows[31].base == 13 and table.rows[63].base == 8192 and table.rows[63].bits == 6 and table.rows[63].next == 0)
    table.build(&match_default[0], 53, 6, &match_bases[0], &match_extras[0])
    assert(table.rows[0].base == 3 and table.rows[0].bits == 6 and table.rows[0].next == 0)
    assert(table.rows[1].base == 4 and table.rows[1].bits == 4 and table.rows[1].next == 0)
    assert(table.rows[31].base == 21 and table.rows[63].base == 1027 and table.rows[63].bits == 6)
    table.build(&offset_default[0], 29, 5, &offset_bases[0], &offset_extras[0])
    assert(table.rows[0].extra == 0 and table.rows[0].bits == 5)
    assert(table.rows[1].extra == 6 and table.rows[1].bits == 4 and table.rows[1].next == 0)
    assert(table.rows[2].extra == 9 and table.rows[31].extra == 24 and table.rows[31].bits == 5)

test "XXH64 of known inputs":
    assert(xxhash64(b"") == 0xEF46DB3751D8E999)
    assert(xxhash64(b"a") == 0xD24EC4F1A98C6E5B)
    assert(xxhash64(b"abc") == 0x44BC2CF5AD770999)
    assert(xxhash64(b"Nobody inspects the spammish repetition") == 0xFBCEA83C8A378BF1)

# mark: Encoder round trips ===================================================================

test "every level round-trips text, records, runs and noise of many sizes":
    let sizes: usize[9] = [0, 1, 15, 16, 100, 1000, 70000, 140000, 300000]
    var data = try new u8[300000] in memory.heap
    defer free(data) in memory.heap
    for kind in 0..<(usize)4:
        if kind == 0: sample_text(data, 3)
        elif kind == 1: sample_records(data, 5)
        elif kind == 2: memory.set(data, 7)
        else: sample_noise(data, 9)
        for level in 1..<(i32)10:
            for size in sizes:
                try round_trip(data[..<size], level)

test "encoded frames shrink what compresses and barely grow noise":
    var data = try new u8[200000] in memory.heap
    defer free(data) in memory.heap
    sample_text(data, 21)
    let text = try encode(data, 3)
    assert(text.length < data.length // 3)
    free(text) in memory.heap
    sample_noise(data, 22)
    let noise = try encode(data, 3)
    assert(noise.length < data.length + 64)
    free(noise) in memory.heap
    assert(failure_of_encode(0) == invalid)

## The failure code of encoding at `level`, or `closed` when it encodes.
func failure_of_encode(level: i32) -> ErrorCode:
    let packed = encode(b"abc", level) catch failure:
        return failure.code
    free(packed) in memory.heap
    return closed

# mark: Damage ================================================================================

test "every truncation of a frame fails and damage never traps":
    var data = try new u8[3000] in memory.heap
    defer free(data) in memory.heap
    sample_text(data, 31)
    for level in [(i32)1, 3, 7]:
        let packed = try encode(data, level)
        defer free(packed) in memory.heap
        for length in 0..<packed.length:
            assert(failure_of(packed[..<length]) == corrupt)
        var damaged = try new u8[packed.length] in memory.heap
        defer free(damaged) in memory.heap
        var state: u32 = 77
        for _ in 0..<(usize)3000:
            memory.copy(damaged, packed, packed.length)
            state = state *% 1103515245 +% 12345
            let at = (usize)(state >> 8) % packed.length
            damaged[at] ^= (u8)(1 << ((state >> 4) & 7))
            if state & 0x10000 != 0:
                damaged[(at + 7) % packed.length] = (u8)(state >> 20)
            _ = failure_of(damaged)