// Dictionaries (RFC 8878 section 5): bytes that come, for every frame, as if
// just before its output, so that its first matches can reach into them.
// The frame names a dictionary by its Dictionary_ID; one of raw content has
// none, and is used for frames that name none. A formatted dictionary, as
// `zstd --train` writes them, also holds entropy tables and repeat offsets
// that a frame starts from.
///|
/// The magic number of a formatted dictionary.
const DICT_MAGIC : UInt32 = 0xEC30A437
///|
/// What a formatted dictionary gives a frame to start from: the literals'
/// Huffman table, the three sequence tables, and the repeat offsets.
priv struct Entropy {
huffman : Huffman
of : Fse
ml : Fse
ll : Fse
rep : FixedArray[UInt32]
// What an encoder starts from: the literals' weights, and each sequence
// table's normalized counts and accuracy log.
weights : FixedArray[Int32]
of_norm : FixedArray[Int32]
ml_norm : FixedArray[Int32]
ll_norm : FixedArray[Int32]
}
///|
/// The longest dictionary content the encoder puts before a frame: of a
/// longer one, its last this many bytes. The encoder's history holds twice
/// the window and the dictionary in 32-bit indices, and 512 MiB keeps that
/// within range at every level; a decoder given the whole dictionary still
/// reads the frames, which never reach before what the encoder kept.
const MAX_ENCODER_DICTIONARY : Int32 = 1 << 29
///|
/// The part of `content` the encoder uses: all of it, or its last
/// `MAX_ENCODER_DICTIONARY` bytes.
fn encoder_view(content : BytesView) -> BytesView {
content[(content.length() - MAX_ENCODER_DICTIONARY).max(0):]
}
///|
/// A dictionary for `Decoder` and `Encoder`: its content, held by reference
/// (the bytes it is a view of stay alive as long as it does), and its id.
pub struct Dictionary {
priv content : BytesView
priv id : UInt32
priv entropy : Entropy?
}
///|
/// A dictionary of raw content, `content` itself: its id is 0, so it is
/// used for frames that name no dictionary, as RFC 8878 section 5 and zstd
/// use one, and RFC 9842's `dcz` coding does.
pub fn Dictionary::raw(content : BytesView) -> Dictionary {
{ content, id: 0, entropy: None, }
}
///|
/// A dictionary from `data`, as `zstd -D` reads one: a formatted
/// dictionary (RFC 8878 section 5, as `zstd --train` writes them) if it
/// starts with the magic number 0xEC30A437, raw content otherwise. The
/// content is a view of `data`.
///
/// Raises `Corrupt` for a formatted dictionary whose entropy tables do not
/// parse, whose repeat offsets are 0 or longer than its content, or that
/// ends inside them.
pub fn Dictionary::parse(
data : BytesView,
) -> Dictionary raise @codec.CodecError {
if data.length() < 8 ||
(
data[0].to_uint() |
(data[1].to_uint() << 8) |
(data[2].to_uint() << 16) |
(data[3].to_uint() << 24)
) !=
DICT_MAGIC {
return Dictionary::raw(data)
}
let bytes = data.to_fixedarray()
let le32 = (at : Int32) => {
bytes[at].to_uint() |
(bytes[at + 1].to_uint() << 8) |
(bytes[at + 2].to_uint() << 16) |
(bytes[at + 3].to_uint() << 24)
}
let id = le32(4)
let end = bytes.length()
let scratch = FseScratch::new()
let huffman = Huffman::new()
let of = Fse::new(8)
let ml = Fse::new(9)
let ll = Fse::new(9)
let norm = () => FixedArray::makei(scratch.count, i => scratch.probs[i])
let (at, of_norm, ml_norm, ll_norm) = try {
let mut at = 8
at += huffman.read(bytes, at, end, scratch)
at += of.read(bytes, at, end, 8, MAX_OF_SYMBOL, scratch)
let of_norm = norm()
at += ml.read(bytes, at, end, 9, MAX_ML_CODE, scratch)
let ml_norm = norm()
at += ll.read(bytes, at, end, 9, MAX_LL_CODE, scratch)
(at, of_norm, ml_norm, norm())
} catch {
Fail(_, message) =>
raise CodecError(Corrupt, "a dictionary's entropy tables: \{message}")
NeedInput =>
raise CodecError(Corrupt, "a dictionary's entropy tables are cut short")
}
guard end - at >= 12 else {
raise CodecError(Corrupt, "a dictionary that ends in its repeat offsets")
}
let content = data[at + 12:]
let rep = FixedArray::makei(3, i => le32(at + 4 * i))
for r in rep {
if r == 0 || r.to_uint64() > content.length().to_uint64() {
raise CodecError(
Corrupt,
"a dictionary's repeat offset \{r} outside its \{content.length()}-byte content",
)
}
}
let weights = FixedArray::makei(huffman.symbols, i => huffman.weights[i])
{
content,
id,
entropy: Some({
huffman,
of,
ml,
ll,
rep,
weights,
of_norm,
ml_norm,
ll_norm,
}),
}
}
///|
/// Whether the dictionary is formatted: has entropy tables and repeat
/// offsets of its own.
pub fn Dictionary::is_formatted(self : Dictionary) -> Bool {
self.entropy is Some(_)
}
///|
/// The id a frame names this dictionary by: 0 for raw content.
pub fn Dictionary::id(self : Dictionary) -> UInt32 {
self.id
}
///|
/// The content: the bytes that come before every frame's output.
pub fn Dictionary::content(self : Dictionary) -> BytesView {
self.content
}
///|
/// Copies a match of `n` bytes from `offset` back that reaches before the
/// frame's output, into the dictionary: `offset` more than the `p` bytes
/// of output so far and at most `p` plus the dictionary's length, as zstd
/// takes it (the dictionary stays reachable however long the frame is). The
/// bytes before the frame's output come from the dictionary's end; a match
/// that runs on past them reads the output from the frame's start, which
/// must still be within the window. Anything else is an offset beyond the
/// decoded data.
fn Decoder::copy_from_dictionary(
self : Decoder,
offset : Int32,
n : Int32,
) -> Unit raise Stop {
let p = self.frame_out + self.block_out.to_uint64()
let reach = offset.to_uint64()
guard self.dictionary is Some(dict) &&
offset > 0 &&
reach > p &&
reach - p <= dict.content.length().to_uint64() else {
raise corrupt("an offset beyond the decoded data")
}
let content = dict.content
// `reach - p` is at most the dictionary's length, an Int.
let back = (reach - p).to_int()
let from_dict = back.min(n)
self.reserve_window(n)
let mut at = content.length() - back
let mut remaining = from_dict
while remaining > 0 {
let chunk = remaining.min(self.ring.length() - self.wpos)
self.ring.blit_from_bytesview(self.wpos, content[at:at + chunk])
self.advance(chunk)
at += chunk
remaining -= chunk
}
let rest = n - from_dict
if rest > 0 {
// The match reaches the frame's first byte, `offset` back.
if offset > self.filled {
raise corrupt("an offset beyond the decoded data")
}
self.copy_back(offset, rest)
}
}