Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-prism

Source of release 0.6.1

0.6.1 / src / serialization / compression.lucb

## Serialization compression.
import memory
from storage import Buffer, Reader
from types import invalid, limit_exceeded, max_bytes

pub func decompress_bytes(bytes: const u8[]) -> Buffer!:
    var reader = Reader(data = bytes)
    let size = try reader.uint(8)
    if size > (u64)max_bytes:
        error(limit_exceeded, "Prism decompression exceeds 256 MiB")
    var output: Buffer
    errdefer output.close()
    while output.used < (usize)size:
        let flags = try reader.uint(1)
        for bit in 0..<8:
            if output.used == (usize)size:
                break
            if (flags & ((u64)1 << bit)) == 0:
                try output.byte((u8)try reader.uint(1))
            else:
                let distance = (usize)try reader.uint(2) + 1
                let length = (usize)try reader.uint(1) + 4
                if distance > output.used or length > (usize)size - output.used:
                    error(invalid, "invalid Prism compression back-reference")
                for i in 0..<length:
                    let byte = output.data[output.used - distance]
                    try output.byte(byte)
    if reader.remaining() != 0:
        error(invalid, "trailing Prism compressed bytes")
    return output

pub func hash_bytes(bytes: const u8[], index: usize) -> usize:
    var value: u32 = 0
    for i in 0..<(usize)4:
        value |= (u32)bytes[index + i] << (i * 8)
    return (usize)((value *% 2654435761) >> 16)

pub func compress_bytes(bytes: const u8[]) -> Buffer!:
    var output: Buffer
    errdefer output.close()
    try output.uint((u64)bytes.length, 8)
    # One most-recent candidate per hash keeps working memory fixed (512 KiB).
    # The token format is identical to C++; compressed bytes need not be identical.
    let positions = try new usize[65536] --- in memory.heap
    defer free(positions) in memory.heap
    for i in 0..<positions.length:
        positions[i] = 0
    var index: usize = 0
    var bit: usize = 8
    var flag_position: usize = 0
    while index < bytes.length:
        if bit == 8:
            flag_position = output.used
            try output.byte(0)
            bit = 0
        var length: usize = 0
        var distance: usize = 0
        if bytes.length - index >= 4:
            let previous = positions[hash_bytes(bytes, index)]
            if previous > 0 and index - (previous - 1) <= 65536:
                let candidate = previous - 1
                let maximum = 259 if bytes.length - index > 259 else bytes.length - index
                while length < maximum and bytes[candidate + length] == bytes[index + length]:
                    length += 1
                distance = index - candidate
        let end = index + (length if length >= 4 else 1)
        if length >= 4:
            output.data[flag_position] |= (u8)((u32)1 << bit)
            try output.uint((u64)(distance - 1), 2)
            try output.byte((u8)(length - 4))
        else:
            try output.byte(bytes[index])
        while index < end:
            if bytes.length - index >= 4:
                positions[hash_bytes(bytes, index)] = index + 1
            index += 1
        bit += 1
    return output