dymokomi/luce-compress
Source of release 0.9.0
## The DEFLATE tables the incremental codecs share (decoder.lucb,
## encoder.lucb): canonical Huffman trees and the length and distance
## bases. The whole-buffer codec is flate's (compress.lucb calls it).
## Adapted from luce-image 422e1cf, Copyright (c) 2026 Dy Mokomi; see NOTICE.md.
from binary import corrupt
pub struct Tree:
pub var counts: u32[16]
pub var symbols: u32[288]
pub func build(lengths: const u32[], code_lengths: bool = false) -> !:
self = Tree()
for length in lengths:
if length > 15:
error(corrupt, "invalid Huffman code length")
self.counts[(usize)length] += 1
var left: i32 = 1
var offsets: u32[16]
for n in 1..<16:
left = left * 2 - (i32)self.counts[n]
if left < 0:
error(corrupt, "oversubscribed Huffman tree")
if n < 15:
offsets[n + 1] = offsets[n] + self.counts[n]
## Only a single one-bit symbol may be incomplete in literal/distance
## alphabets. An empty distance alphabet is accepted but cannot decode.
let present = (u32)lengths.length - self.counts[0]
if left > 0 and (code_lengths or (present > 0 and (present != 1 or self.counts[1] != 1))):
error(corrupt, "incomplete Huffman tree")
for i in 0..<lengths.length:
let length = (usize)lengths[i]
if length > 0:
self.symbols[(usize)offsets[length]] = (u32)i
offsets[length] += 1
pub let length_base: u32[29] = [3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,51,59,67,83,99,115,131,163,195,227,258]
pub let length_extra: u32[29] = [0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0]
pub let distance_base: u32[30] = [1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577]
pub let distance_extra: u32[30] = [0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13]