///|
/// Internal inflate state
priv struct InflateState {
mut lm : FixedArray[Int]? // length map
mut dm : FixedArray[Int]? // distance map
mut lbt : Int // length bits
mut dbt : Int // distance bits
mut final_ : Int // final block flag
mut pos : Int // bit position
mut bt : Int // byte count (output position)
i : Int // state info (0=streaming, 2=one-shot)
}
///|
fn InflateState::new(i : Int) -> InflateState {
{ lm: None, dm: None, lbt: 0, dbt: 0, final_: 0, pos: 0, bt: 0, i }
}
///|
/// Choose an initial one-shot output buffer size.
fn initial_inflate_size(sl : Int, max_output_size : Int) -> Int raise FzipError {
let max_safe = max_output_size / 3
if sl > max_safe {
raise fzip_err(InvalidZipData, msg="input too large for safe allocation")
}
let base = sl * 3
if sl >= 512 && sl < 2048 {
// Small inputs in this range are frequently highly compressible (runs,
// periodic data, sparse buffers) and expand by well over 100x. fzip's
// periodic encoder packs 100 KiB into ~700 bytes (~140x), so a smaller
// multiplier would force a mid-decode realloc + buffer copy. Estimate
// generously here (the buffer is trimmed to the exact length afterwards)
// so these streams decode in a single allocation.
let expanded = sl * 160
if expanded > max_output_size {
max_output_size
} else {
expanded
}
} else {
base
}
}
///|
/// Core DEFLATE decompression with 32-bit bit buffer.
/// Instead of calling bits()/bits16() per read (each doing p/8 division +
/// 2-3 array accesses + boundary checks), we maintain a bit accumulator
/// (bbuf/bcnt) and refill from dat[bpos] only when needed. This reduces
/// array accesses from ~8-12 to ~3-4 per decoded symbol.
fn inflt(
dat : FixedArray[Byte],
st : InflateState,
buf : FixedArray[Byte]?,
dict : FixedArray[Byte]?,
max_input_size : Int,
max_output_size : Int,
dat_off? : Int = 0,
dat_end? : Int = dat.length(),
crc_state? : CRC32State? = None,
adler_state? : AdlerState? = None,
) -> (FixedArray[Byte], Int) raise FzipError {
let sl = dat_end - dat_off
// Check input size against configured limit (before any processing)
if sl > max_input_size {
raise fzip_err(InvalidZipData, msg="input exceeds max_input_size")
}
let dl = match dict {
Some(d) => d.length()
None => 0
}
if sl == 0 || (st.final_ != 0 && st.lm is None) {
return match buf {
Some(b) => (b, st.bt)
None => (FixedArray::make(0, b'\x00'), 0)
}
}
let no_buf = buf is None
let resize = no_buf || st.i != 2
let no_st = st.i
let mut buf = match buf {
Some(b) => b
None => {
let initial_size = initial_inflate_size(sl, max_output_size)
FixedArray::make(initial_size, b'\x00')
}
}
let fixed_limit = buf.length()
// Scale buffer growth headroom based on input size to avoid
// over-allocation for small data (was hardcoded 131072 = 128KB)
let grow = if sl < 43690 { // 131072 / 3
let safe_grow = sl * 3
if safe_grow < 131072 {
safe_grow + 512
} else {
131072
}
} else {
131072
}
let tbts = dat_end * 8
let mut final_ = st.final_
// Initialize 32-bit bit buffer from saved state position
let init_pos = st.pos + dat_off * 8
let mut bpos = init_pos >> 3 // next byte to load from dat
let mut bbuf = 0 // accumulated bits (lowest bits = next to consume)
let mut bcnt = 0 // number of valid bits in bbuf
let boff = init_pos & 7
if boff > 0 && bpos < dat_end {
bbuf = dat[bpos].to_int() >> boff
bcnt = 8 - boff
bpos += 1
}
let mut bt = st.bt
let mut cksum_bt = bt
let mut lm = st.lm
let mut dm = st.dm
let mut lbt = st.lbt
let mut dbt = st.dbt
// main loop over blocks
let mut continue_loop = true
while continue_loop {
if lm is None {
// If we already read the final block, stop
if final_ != 0 {
break
}
// read BFINAL (1 bit) + BTYPE (2 bits) = 3 bits total
while bcnt < 3 && bpos < dat_end {
bbuf = bbuf | (dat[bpos].to_int() << bcnt)
bpos += 1
bcnt += 8
}
final_ = bbuf & 1
let btype = (bbuf >> 1) & 3
bbuf = bbuf >> 3
bcnt -= 3
if btype == 0 {
// Stored block: align to byte boundary, reset bit buffer
let cur_pos = bpos * 8 - bcnt
let s = shft(cur_pos) + 4
bbuf = 0
bcnt = 0
// Check if we have enough bytes for the stored block header (4 bytes)
if s > dat_end {
if no_st != 0 {
raise fzip_err(UnexpectedEOF)
}
break
}
let l = dat[s - 4].to_int() | (dat[s - 3].to_int() << 8)
let t = s + l
if t > dat_end {
if no_st != 0 {
raise fzip_err(UnexpectedEOF)
}
break
}
if resize {
buf = ensure_buf(buf, bt + l, max_output_size)
} else if bt + l > fixed_limit {
raise fzip_err(InvalidZipData, msg="output buffer too small")
}
dat.blit_to(buf, len=l, src_offset=s, dst_offset=bt)
match crc_state {
Some(cs) => cs.push_range(buf, bt, l)
None => ()
}
match adler_state {
Some(a_s) => a_s.push_range(buf, bt, l)
None => ()
}
st.bt = {
bt += l
bt
}
cksum_bt = bt
st.pos = {
bpos = t
bpos * 8
}
st.final_ = final_
continue
} else if btype == 1 {
lm = Some(flrm)
dm = Some(fdrm)
lbt = 9
dbt = 5
} else if btype == 2 {
// Dynamic Huffman: read 14-bit header (HLIT + HDIST + HCLEN)
while bcnt < 14 && bpos < dat_end {
bbuf = bbuf | (dat[bpos].to_int() << bcnt)
bpos += 1
bcnt += 8
}
let h_lit = (bbuf & 31) + 257
let tl = h_lit + ((bbuf >> 5) & 31) + 1
let hc_len = ((bbuf >> 10) & 15) + 4
bbuf = bbuf >> 14
bcnt -= 14
// RFC 1951 §3.2.7: the length/literal alphabet has only 286 symbols
// (sym 0..285) and the distance alphabet has only 30 (sym 0..29).
// HLIT > 286 or HDIST > 30 is malformed and would let a crafted
// dynamic-Huffman block reach `fl[29..30]` / `fd[30]` — derived
// freb values that are either spec-meaningless or out of bounds
// (`fd` has length 31, so `dsym=31` traps on `fd[31]`). Reject
// before we allocate the trees.
if h_lit > 286 {
raise fzip_err(
InvalidLengthLiteral,
msg="HLIT exceeds 286-symbol length/literal alphabet",
)
}
if tl - h_lit > 30 {
raise fzip_err(
InvalidDistance,
msg="HDIST exceeds 30-symbol distance alphabet",
)
}
// length+distance tree
let ldt : FixedArray[Byte] = FixedArray::make(tl, b'\x00')
// code length tree
let clt_arr : FixedArray[Byte] = FixedArray::make(19, b'\x00')
// Read code length code lengths (3 bits each)
for i in 0..> 3
bcnt -= 3
}
let clb = max_val(clt_arr)
let clbmsk = (1 << clb) - 1
let clm = h_map(clt_arr, clb, 1)
// Decode the combined length+distance code length tree
let mut i = 0
while i < tl {
while bcnt < clb && bpos < dat_end {
bbuf = bbuf | (dat[bpos].to_int() << bcnt)
bpos += 1
bcnt += 8
}
let r = clm[bbuf & clbmsk]
let rbits = r & 15
bbuf = bbuf >> rbits
bcnt -= rbits
let s = r >> 4
if s < 16 {
ldt[i] = s.to_byte()
i += 1
} else {
let mut c = 0
let mut n = 0
if s == 16 {
if i == 0 {
raise fzip_err(InvalidLengthLiteral)
}
while bcnt < 2 && bpos < dat_end {
bbuf = bbuf | (dat[bpos].to_int() << bcnt)
bpos += 1
bcnt += 8
}
n = 3 + (bbuf & 3)
bbuf = bbuf >> 2
bcnt -= 2
c = ldt[i - 1].to_int()
} else if s == 17 {
while bcnt < 3 && bpos < dat_end {
bbuf = bbuf | (dat[bpos].to_int() << bcnt)
bpos += 1
bcnt += 8
}
n = 3 + (bbuf & 7)
bbuf = bbuf >> 3
bcnt -= 3
} else if s == 18 {
while bcnt < 7 && bpos < dat_end {
bbuf = bbuf | (dat[bpos].to_int() << bcnt)
bpos += 1
bcnt += 8
}
n = 11 + (bbuf & 127)
bbuf = bbuf >> 7
bcnt -= 7
}
if n > tl - i {
raise fzip_err(InvalidLengthLiteral)
}
while n > 0 {
ldt[i] = c.to_byte()
i += 1
n -= 1
}
}
}
// split into length tree and distance tree
let lt : FixedArray[Byte] = FixedArray::make(h_lit, b'\x00')
let dt : FixedArray[Byte] = FixedArray::make(tl - h_lit, b'\x00')
ldt.blit_to(lt, len=h_lit, src_offset=0, dst_offset=0)
ldt.blit_to(dt, len=tl - h_lit, src_offset=h_lit, dst_offset=0)
lbt = max_val(lt)
dbt = max_val(dt)
lm = Some(h_map(lt, lbt, 1))
dm = Some(h_map(dt, dbt, 1))
} else {
raise fzip_err(InvalidBlockType)
}
if bpos * 8 - bcnt > tbts {
if no_st != 0 {
raise fzip_err(UnexpectedEOF)
}
break
}
}
// decode symbols using bit buffer
if resize {
let growth_target = if grow > max_output_size - bt {
max_output_size
} else {
bt + grow
}
buf = ensure_buf(buf, growth_target, max_output_size)
}
let lms = (1 << lbt) - 1
let dms = (1 << dbt) - 1
let mut lpos = bpos * 8 - bcnt
let lm_arr = match lm {
Some(a) => a
None => FixedArray::make(0, 0) // should not happen
}
let dm_arr = match dm {
Some(a) => a
None => FixedArray::make(0, 0)
}
let mut break_outer = false
while true {
lpos = bpos * 8 - bcnt
// Fill and lookup length/literal Huffman code
while bcnt < lbt && bpos < dat_end {
bbuf = bbuf | (dat[bpos].to_int() << bcnt)
bpos += 1
bcnt += 8
}
let c = lm_arr[bbuf & lms]
let sym = c >> 4
let cbits = c & 15
bbuf = bbuf >> cbits
bcnt -= cbits
if bpos * 8 - bcnt > tbts {
if no_st != 0 {
raise fzip_err(UnexpectedEOF)
}
break_outer = true
break
}
if c == 0 {
raise fzip_err(InvalidLengthLiteral)
}
if sym < 256 {
if bt >= buf.length() {
if resize {
buf = ensure_buf(buf, bt + 1, max_output_size)
} else {
raise fzip_err(InvalidZipData, msg="output buffer too small")
}
}
buf[bt] = sym.to_byte()
bt += 1
} else if sym == 256 {
if bt > cksum_bt {
match crc_state {
Some(cs) => cs.push_range(buf, cksum_bt, bt - cksum_bt)
None => ()
}
match adler_state {
Some(a_s) => a_s.push_range(buf, cksum_bt, bt - cksum_bt)
None => ()
}
cksum_bt = bt
}
lpos = bpos * 8 - bcnt
lm = None
break
} else {
let mut add = sym - 254
if sym > 264 {
let idx = sym - 257
let b = fleb[idx].to_int()
// Fill for extra length bits
while bcnt < b && bpos < dat_end {
bbuf = bbuf | (dat[bpos].to_int() << bcnt)
bpos += 1
bcnt += 8
}
add = (bbuf & ((1 << b) - 1)) + fl[idx]
bbuf = bbuf >> b
bcnt -= b
}
// distance Huffman lookup
while bcnt < dbt && bpos < dat_end {
bbuf = bbuf | (dat[bpos].to_int() << bcnt)
bpos += 1
bcnt += 8
}
let d = dm_arr[bbuf & dms]
let dsym = d >> 4
if d == 0 {
raise fzip_err(InvalidDistance)
}
let dbits = d & 15
bbuf = bbuf >> dbits
bcnt -= dbits
let mut dt_val = fd[dsym]
if dsym > 3 {
let b = fdeb[dsym].to_int()
// Fill for extra distance bits
while bcnt < b && bpos < dat_end {
bbuf = bbuf | (dat[bpos].to_int() << bcnt)
bpos += 1
bcnt += 8
}
dt_val += bbuf & ((1 << b) - 1)
bbuf = bbuf >> b
bcnt -= b
}
if bpos * 8 - bcnt > tbts {
if no_st != 0 {
raise fzip_err(UnexpectedEOF)
}
break_outer = true
break
}
let end = bt + add
if resize {
if end > buf.length() {
if end > max_output_size || end < 0 {
raise fzip_err(
InvalidZipData,
msg="uncompressed size exceeds max_output_size",
)
}
let growth_target = if grow > max_output_size - bt {
max_output_size
} else {
bt + grow
}
buf = ensure_buf(buf, growth_target, max_output_size)
}
} else if end > fixed_limit {
raise fzip_err(InvalidZipData, msg="output buffer too small")
}
// dictionary reference: fill from the preset dictionary when the
// back-reference distance reaches into the dictionary region. Stops at
// `min(dt_val, end)` so the writer never overruns the requested length.
if bt < dt_val {
let shift = dl - dt_val
let dend = if dt_val < end { dt_val } else { end }
if shift + bt < 0 {
raise fzip_err(InvalidDistance)
}
match dict {
Some(dict_arr) =>
while bt < dend {
buf[bt] = dict_arr[shift + bt]
bt += 1
}
None => raise fzip_err(InvalidDistance)
}
}
// Copy the remaining bytes from the output buffer (LZ77 back-reference).
// Skip when the dict branch already produced all `add` bytes — otherwise
// `bt - dt_val` would be negative (when `dt_val > end`) and `blit_to`
// would trap on a negative `src_offset`. Using `need = end - bt`
// (instead of the original `add`) keeps the slice math correct after
// the dict branch advanced `bt`.
if bt < end {
let need = end - bt
if dt_val == 1 {
// RLE: fill with single repeated byte
buf.fill(buf[bt - 1], start=bt, end~)
bt = end
} else if dt_val >= need {
// Non-overlapping: block copy
buf.blit_to(buf, len=need, src_offset=bt - dt_val, dst_offset=bt)
bt = end
} else {
// Overlapping pattern: copy with doubling strategy
buf.blit_to(buf, len=dt_val, src_offset=bt - dt_val, dst_offset=bt)
let copied = for copied = dt_val; copied + copied <= need; {
buf.blit_to(
buf,
len=copied,
src_offset=bt,
dst_offset=bt + copied,
)
continue copied + copied
} nobreak {
copied
}
if copied < need {
buf.blit_to(
buf,
len=need - copied,
src_offset=bt,
dst_offset=bt + copied,
)
}
bt = end
}
}
}
}
if break_outer {
break
}
st.lm = lm
st.pos = lpos
st.bt = bt
st.final_ = final_
if !(lm is None) {
final_ = 1
st.lbt = lbt
st.dm = dm
st.dbt = dbt
}
if final_ != 0 {
continue_loop = false
}
}
if bt > cksum_bt {
match crc_state {
Some(cs) => cs.push_range(buf, cksum_bt, bt - cksum_bt)
None => ()
}
match adler_state {
Some(a_s) => a_s.push_range(buf, cksum_bt, bt - cksum_bt)
None => ()
}
}
(buf, bt)
}
///|
/// Ensure buffer has at least `need` capacity
fn ensure_buf(
buf : FixedArray[Byte],
need : Int,
max_size : Int,
) -> FixedArray[Byte] raise FzipError {
let bl = buf.length()
if need > bl {
// Check against configured maximum output size
if need > max_size || need < 0 {
raise fzip_err(
InvalidZipData,
msg="uncompressed size exceeds max_output_size",
)
}
// Check for integer overflow in doubling calculation
let new_size = if bl > 0 && bl < max_size / 2 && bl * 2 > need {
bl * 2
} else {
need
}
let nbuf = FixedArray::make(new_size, b'\x00')
buf.blit_to(nbuf, len=bl, src_offset=0, dst_offset=0)
nbuf
} else {
buf
}
}
///|
/// Decompress a raw DEFLATE stream.
///
/// The input must be raw DEFLATE data without a GZIP or Zlib wrapper. Use
/// `decompress_sync` when the format is unknown. `InflateOptions` can provide a
/// preset dictionary, a caller-owned output buffer, and input/output size
/// limits for defensive decompression.
pub fn inflate_sync(
data : FixedArray[Byte],
opts? : InflateOptions = InflateOptions::default(),
) -> FixedArray[Byte] raise FzipError {
let (buf, len) = inflt(
data,
InflateState::new(2),
opts.out,
opts.dictionary,
opts.max_input_size,
opts.max_output_size,
)
trim_buf(buf, len)
}