Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-usd

Source of release 0.9.6

0.9.6 / src / usdc / compression.lucb

## The crate's compression layers: TfFastCompression's LZ4 wrapper
## (pxr/base/tf/fastCompression.cpp: a chunk-count byte, then one LZ4 block,
## or int32-sized chunks for inputs past LZ4's 2 GiB block limit) and
## Sdf_IntegerCompression (pxr/usd/sdf/integerCoding.cpp): integers as
## deltas from the previous one, the most common delta written once, a 2-bit
## code per integer (common, small, medium, large), then the variable-width
## deltas, all LZ4-compressed.
import memory
from luce_compress import lz4
import errors

## Decompress a TfFastCompression buffer into `output`; its length.
pub func decompress(input: const u8[], output: u8[]) -> usize!:
    if input.length == 0: error(errors.invalid, "an empty compressed block in a crate file")
    let chunks = (usize)input[0]
    if chunks == 0:
        return lz4.decompress(input[1..], output) catch failure:
            error(errors.invalid, "a damaged LZ4 block in a crate file")
    var at: usize = 1
    var out: usize = 0
    for _ in 0..<chunks:
        if input.length - at < 4: error(errors.invalid, "a truncated compressed chunk in a crate file")
        let size = (usize)memory.read[i32]((void*)&input[at])
        at += 4
        if size > input.length - at: error(errors.invalid, "a compressed chunk runs past its buffer")
        out += lz4.decompress(input[at..<at + size], output[out..]) catch failure:
            error(errors.invalid, "a damaged LZ4 chunk in a crate file")
        at += size
    return out

## The most bytes `compress` writes for `size` input bytes (one chunk).
pub func compressed_bound(size: usize) -> usize:
    return lz4.bound(size) + 1

## Compress `input` into `output` (at least `compressed_bound` bytes) as one
## TfFastCompression chunk; the compressed length.
pub func compress(input: const u8[], output: u8[]) -> usize!:
    if input.length > lz4.most_input: error(errors.limit, "a crate block larger than LZ4 holds")
    output[0] = 0
    return 1 + try lz4.compress(input, output[1..])

## Bytes the integer encoding of `count` integers of `width` bytes may take.
pub func encoded_bound(count: usize, width: usize) -> usize:
    if count == 0: return 0
    return width + (count * 2 + 7) // 8 + count * width

## Decode `count` integers of `width` bytes (4 or 8) from the integer
## encoding `data` into `out` (count * width bytes).
pub func decode_integers(data: const u8[], count: usize, width: usize, out: u8[]) -> !:
    if count == 0: return
    let codes_bytes = (count * 2 + 7) // 8
    if data.length < width + codes_bytes: error(errors.invalid, "truncated integer codes in a crate file")
    var codes = width
    var values = width + codes_bytes
    if width == 4:
        let common = (i64)memory.read[i32]((void*)&data[0])
        var previous: i32 = 0
        for index in 0..<count:
            let code = (data[codes + index // 4] >> (u8)((index % 4) * 2)) & 3
            var delta: i64 = common
            if code == 1:
                if values + 1 > data.length: error(errors.invalid, "truncated integer data in a crate file")
                delta = (i64)(i8)data[values]
                values += 1
            elif code == 2:
                if values + 2 > data.length: error(errors.invalid, "truncated integer data in a crate file")
                delta = (i64)memory.read[i16]((void*)&data[values])
                values += 2
            elif code == 3:
                if values + 4 > data.length: error(errors.invalid, "truncated integer data in a crate file")
                delta = (i64)memory.read[i32]((void*)&data[values])
                values += 4
            previous = previous +% (i32)delta
            memory.write[i32]((void*)&out[index * 4], previous)
        return
    let common = memory.read[i64]((void*)&data[0])
    var previous: i64 = 0
    for index in 0..<count:
        let code = (data[codes + index // 4] >> (u8)((index % 4) * 2)) & 3
        var delta = common
        if code == 1:
            if values + 2 > data.length: error(errors.invalid, "truncated integer data in a crate file")
            delta = (i64)memory.read[i16]((void*)&data[values])
            values += 2
        elif code == 2:
            if values + 4 > data.length: error(errors.invalid, "truncated integer data in a crate file")
            delta = (i64)memory.read[i32]((void*)&data[values])
            values += 4
        elif code == 3:
            if values + 8 > data.length: error(errors.invalid, "truncated integer data in a crate file")
            delta = memory.read[i64]((void*)&data[values])
            values += 8
        previous = previous +% delta
        memory.write[i64]((void*)&out[index * 8], previous)

## Decompress then decode `count` integers of `width` bytes from `input`
## into `out`.
pub func decompress_integers(input: const u8[], count: usize, width: usize, out: u8[]) -> !:
    if count == 0: return
    let bound = encoded_bound(count, width)
    let scratch = try new u8[bound] --- in memory.heap
    defer free(scratch) in memory.heap
    let length = try decompress(input, scratch)
    try decode_integers(scratch[..<length], count, width, out)

## Encode `count` integers of `width` bytes from `values` into `out` (at
## least `encoded_bound` bytes); the encoded length. The common value is
## the most frequent delta, the larger on ties, as Sdf chooses it.
pub func encode_integers(values: const u8[], count: usize, width: usize, out: u8[]) -> usize!:
    if count == 0: return 0
    let common = try most_common_delta(values, count, width)
    let codes_bytes = (count * 2 + 7) // 8
    for index in 0..<codes_bytes: out[width + index] = 0
    var at = width + codes_bytes
    if width == 4:
        memory.write[i32]((void*)&out[0], (i32)common)
        var previous: i64 = 0
        for index in 0..<count:
            let value = (i64)memory.read[i32]((void*)&values[index * 4])
            let delta = (i64)((i32)value -% (i32)previous)
            previous = value
            var code: u8 = 3
            if delta == common: code = 0
            elif delta >= -128 and delta <= 127:
                code = 1
                out[at] = (u8)(i8)delta
                at += 1
            elif delta >= -32768 and delta <= 32767:
                code = 2
                memory.write[i16]((void*)&out[at], (i16)delta)
                at += 2
            else:
                memory.write[i32]((void*)&out[at], (i32)delta)
                at += 4
            out[width + index // 4] |= code << (u8)((index % 4) * 2)
        return at
    memory.write[i64]((void*)&out[0], common)
    var previous: i64 = 0
    for index in 0..<count:
        let value = memory.read[i64]((void*)&values[index * 8])
        let delta = value -% previous
        previous = value
        var code: u8 = 3
        if delta == common: code = 0
        elif delta >= -32768 and delta <= 32767:
            code = 1
            memory.write[i16]((void*)&out[at], (i16)delta)
            at += 2
        elif delta >= -2147483648 and delta <= 2147483647:
            code = 2
            memory.write[i32]((void*)&out[at], (i32)delta)
            at += 4
        else:
            memory.write[i64]((void*)&out[at], delta)
            at += 8
        out[width + index // 4] |= code << (u8)((index % 4) * 2)
    return at

## The most frequent delta (the larger on a tie), over an open-addressed
## count table.
func most_common_delta(values: const u8[], count: usize, width: usize) -> i64!:
    var capacity: usize = 64
    while capacity < count * 2: capacity *= 2
    if capacity > 1 << 26: capacity = 1 << 26
    let keys = try new i64[capacity] --- in memory.heap
    defer free(keys) in memory.heap
    let counts = try new u32[capacity] in memory.heap
    defer free(counts) in memory.heap
    let mask = capacity - 1
    var common: i64 = 0
    var common_count: u32 = 0
    var previous: i64 = 0
    var used: usize = 0
    for index in 0..<count:
        var value: i64 = 0
        var delta: i64 = 0
        if width == 4:
            value = (i64)memory.read[i32]((void*)&values[index * 4])
            delta = (i64)((i32)value -% (i32)previous)
        else:
            value = memory.read[i64]((void*)&values[index * 8])
            delta = value -% previous
        previous = value
        var slot = (usize)(((u64)delta *% 0x9E3779B97F4A7C15) >> 32) & mask
        while counts[slot] != 0 and keys[slot] != delta: slot = (slot + 1) & mask
        if counts[slot] == 0:
            # A full table stops counting new deltas; the result stays a
            # valid (if less compact) choice.
            if used * 2 >= capacity: continue
            keys[slot] = delta
            used += 1
        counts[slot] += 1
        let seen = counts[slot]
        if seen > common_count or (seen == common_count and delta > common):
            common = delta
            common_count = seen
    return common