dymokomi/luce-compress
Source of release 0.9.1
0.9.1 / src / zstd / frame.lucb
#==============================================================================================
#
# zstd/frame - Frame headers, blocks and frames
#
# DESCRIPTION:
# Input is a run of frames: Zstandard frames (magic 0xFD2FB528) and skippable
# frames (0x184D2A50 to 0x184D2A5F) that are passed over. A frame header gives the
# window (or a single segment of the content's size), an optional dictionary ID,
# the content size and whether a checksum follows the last block. Blocks are raw,
# one byte repeated, or compressed; none may hold or make more than the frame's
# block size, the smaller of its window and 128 KiB. Huffman and FSE tables and the
# recent offsets carry from block to block within a frame (`Context`).
#
#==============================================================================================
let frame_magic: u32 = 0xFD2FB528
let skippable_magic: u32 = 0x184D2A50
## The largest block a frame may hold.
let block_largest: usize = 131072
## The largest window accepted: 2^31, the reference decoder's limit.
let window_largest_log: u32 = 31
## What a frame's header says.
struct FrameHeader:
var size: usize
var window: u64
var content: u64
var has_content: bool
var checksum: bool
## The bytes of a dictionary ID field by its flag: 0, 1, 2 or 4 (twice that for a
## content size field of flag 1 to 3).
inline func field_bytes(flag: u32) -> usize:
return 4 if flag == 3 else (usize)flag
## The header of the frame at the start of `data` (its magic already checked).
func read_frame_header(data: const u8[]) -> FrameHeader!:
if data.length < 5: error(corrupt, "truncated zstd frame header")
let descriptor = (u32)data[4]
let content_flag = descriptor >> 6
let single = (descriptor >> 5) & 1 != 0
if (descriptor >> 3) & 1 != 0: error(corrupt, "reserved zstd frame header bit")
let dictionary_bytes = field_bytes(descriptor & 3)
var content_bytes = field_bytes(content_flag) * 2 if content_flag > 0 else 0
if content_flag == 0 and single: content_bytes = 1
var header: FrameHeader
header.checksum = (descriptor >> 2) & 1 != 0
header.size = 5 + (0 if single else 1) + dictionary_bytes + content_bytes
if data.length < header.size: error(corrupt, "truncated zstd frame header")
var at: usize = 5
if not single:
let window = (u32)data[at]
at += 1
let log = 10 + (window >> 3)
if log > window_largest_log: error(unsupported, "zstd window larger than 2 GiB")
let base = (u64)1 << (u64)log
header.window = base + (base >> 3) * (u64)(window & 7)
var dictionary: u64 = 0
for index in 0..<dictionary_bytes: dictionary |= (u64)data[at + index] << (u64)(index * 8)
at += dictionary_bytes
if dictionary != 0: error(unsupported, "zstd frame needs a dictionary")
if content_bytes > 0:
var content: u64 = 0
for index in 0..<content_bytes: content |= (u64)data[at + index] << (u64)(index * 8)
if content_bytes == 2: content += 256
header.content = content
header.has_content = true
if single: header.window = header.content
return header
## The little-endian u32 at `at` of `data` (which holds it).
inline func u32_at(data: const u8[], at: usize) -> u32:
return (u32)data[at] | (u32)data[at + 1] << 8 | (u32)data[at + 2] << 16 | (u32)data[at + 3] << 24
## The total content size the frames of `data` declare, or none when one does not
## declare it or the frames cannot be walked.
func content_size(data: const u8[]) -> u64?:
var at: usize = 0
var total: u64 = 0
while at + 4 <= data.length:
let magic = u32_at(data, at)
if magic & 0xFFFFFFF0 == skippable_magic:
if at + 8 > data.length: return none
at += 8 + (usize)u32_at(data, at + 4)
continue
if magic != frame_magic: return none
let header = read_frame_header(data[at..]) catch failure: return none
if not header.has_content: return none
total = total +? header.content else return none
at += header.size
# Skip the blocks by their headers.
while true:
if at + 3 > data.length: return none
let block = (usize)data[at] | (usize)data[at + 1] << 8 | (usize)data[at + 2] << 16
let kind = (block >> 1) & 3
at += 3 + (1 if kind == 1 else block >> 3)
if block & 1 != 0: break
if header.checksum: at += 4
return total
## A frame's decoding state: the tables and offsets its blocks pass on, and scratch.
struct Context:
var huffman: u16[4096]
var huffman_log: u32
var literal_lengths: SeqTable
var offsets: SeqTable
var match_lengths: SeqTable
var repeats: u64[3]
## The block's literals: the largest block and a word of slack.
var literals: u8[]
var literal_count: usize
var block_most: usize
## Start a frame: no tables, the initial recent offsets.
func reset(block_most: usize):
self.huffman_log = 0
self.literal_lengths.ready = false
self.offsets.ready = false
self.match_lengths.ready = false
self.repeats = [1, 4, 8]
self.block_most = block_most
## Decode the frames of `data` into `output`.
func decode_frames(data: const u8[], output: Output*, allow_trailing: bool) -> !:
if data.length == 0: error(corrupt, "empty zstd input")
let context = try new Context in memory.heap
defer free(context) in memory.heap
context.literals = try new u8[block_largest + slack] in memory.heap
defer free(context.literals) in memory.heap
var at: usize = 0
var frames: usize = 0
while at < data.length:
if data.length - at < 4:
if allow_trailing and frames > 0: return
error(corrupt, "truncated zstd frame")
let magic = u32_at(data, at)
if magic & 0xFFFFFFF0 == skippable_magic:
if data.length - at < 8: error(corrupt, "truncated zstd skippable frame")
let size = (usize)u32_at(data, at + 4)
if size > data.length - at - 8: error(corrupt, "truncated zstd skippable frame")
at += 8 + size
frames += 1
continue
if magic != frame_magic:
if allow_trailing and frames > 0: return
error(corrupt, "not a zstd frame")
at += try decode_frame(data[at..], output, context)
frames += 1
## Decode the frame at the start of `data` into `output`; its bytes.
func decode_frame(data: const u8[], output: Output*, context: Context*) -> usize!:
let header = try read_frame_header(data)
let block_most = (usize)(header.window if header.window < (u64)block_largest else (u64)block_largest)
context.reset(block_most)
let start = output.used
var at = header.size
while true:
if data.length - at < 3: error(corrupt, "truncated zstd block header")
let block = (usize)data[at] | (usize)data[at + 1] << 8 | (usize)data[at + 2] << 16
at += 3
let kind = (block >> 1) & 3
let size = block >> 3
if kind == 3: error(corrupt, "reserved zstd block type")
if size > block_most: error(corrupt, "zstd block larger than its frame allows")
try output.reserve(block_most)
if kind == 1:
if at >= data.length: error(corrupt, "truncated zstd block")
if size > output.limit - output.used: error(limit, "zstd output exceeds its limit")
memory.set(output.data[output.used..<output.used + size], data[at])
output.used += size
at += 1
else:
if size > data.length - at: error(corrupt, "truncated zstd block")
let content = data[at..<at + size]
if kind == 0:
if size > output.limit - output.used: error(limit, "zstd output exceeds its limit")
if size > 0: memory.copy(output.data[output.used..], content, size)
output.used += size
else:
let literals = try context.read_literals(content)
try context.run_sequences(content[literals..], output, start, output.used + block_most)
at += size
if block & 1 != 0: break
let made = output.used - start
if header.has_content and (u64)made != header.content: error(corrupt, "zstd frame content size mismatch")
if header.checksum:
if data.length - at < 4: error(corrupt, "truncated zstd checksum")
let expected = u32_at(data, at)
if (u32)xxhash64(output.data[start..<output.used]) != expected: error(corrupt, "zstd checksum mismatch")
at += 4
return at