Compress-Stream-Zstd
view release on metacpan or search on metacpan
ext/zstd/doc/educational_decoder/zstd_decompress.c view on Meta::CPAN
/// Advances the stream by `len` bytes, and returns a pointer to the chunk that
/// was skipped so it can be written to.
static inline u8 *IO_get_write_ptr(ostream_t *const out, size_t len);
/// Advance the inner state by `len` bytes. The stream must be byte aligned.
static inline void IO_advance_input(istream_t *const in, size_t len);
/// Returns an `ostream_t` constructed from the given pointer and length.
static inline ostream_t IO_make_ostream(u8 *out, size_t len);
/// Returns an `istream_t` constructed from the given pointer and length.
static inline istream_t IO_make_istream(const u8 *in, size_t len);
/// Returns an `istream_t` with the same base as `in`, and length `len`.
/// Then, advance `in` to account for the consumed bytes.
/// `in` must be byte aligned.
static inline istream_t IO_make_sub_istream(istream_t *const in, size_t len);
/*** END IO STREAM OPERATIONS *********/
/*** BITSTREAM OPERATIONS *************/
/// Read `num` bits (up to 64) from `src + offset`, where `offset` is in bits,
/// and return them interpreted as a little-endian unsigned integer.
static inline u64 read_bits_LE(const u8 *src, const int num_bits,
const size_t offset);
/// Read bits from the end of a HUF or FSE bitstream. `offset` is in bits, so
/// it updates `offset` to `offset - bits`, and then reads `bits` bits from
/// `src + offset`. If the offset becomes negative, the extra bits at the
/// bottom are filled in with `0` bits instead of reading from before `src`.
static inline u64 STREAM_read_bits(const u8 *src, const int bits,
i64 *const offset);
/*** END BITSTREAM OPERATIONS *********/
/*** BIT COUNTING OPERATIONS **********/
/// Returns the index of the highest set bit in `num`, or `-1` if `num == 0`
static inline int highest_set_bit(const u64 num);
/*** END BIT COUNTING OPERATIONS ******/
/*** HUFFMAN PRIMITIVES ***************/
// Table decode method uses exponential memory, so we need to limit depth
#define HUF_MAX_BITS (16)
// Limit the maximum number of symbols to 256 so we can store a symbol in a byte
#define HUF_MAX_SYMBS (256)
/// Structure containing all tables necessary for efficient Huffman decoding
typedef struct {
u8 *symbols;
u8 *num_bits;
int max_bits;
} HUF_dtable;
/// Decode a single symbol and read in enough bits to refresh the state
static inline u8 HUF_decode_symbol(const HUF_dtable *const dtable,
u16 *const state, const u8 *const src,
i64 *const offset);
/// Read in a full state's worth of bits to initialize it
static inline void HUF_init_state(const HUF_dtable *const dtable,
u16 *const state, const u8 *const src,
i64 *const offset);
/// Decompresses a single Huffman stream, returns the number of bytes decoded.
/// `src_len` must be the exact length of the Huffman-coded block.
static size_t HUF_decompress_1stream(const HUF_dtable *const dtable,
ostream_t *const out, istream_t *const in);
/// Same as previous but decodes 4 streams, formatted as in the Zstandard
/// specification.
/// `src_len` must be the exact length of the Huffman-coded block.
static size_t HUF_decompress_4stream(const HUF_dtable *const dtable,
ostream_t *const out, istream_t *const in);
/// Initialize a Huffman decoding table using the table of bit counts provided
static void HUF_init_dtable(HUF_dtable *const table, const u8 *const bits,
const int num_symbs);
/// Initialize a Huffman decoding table using the table of weights provided
/// Weights follow the definition provided in the Zstandard specification
static void HUF_init_dtable_usingweights(HUF_dtable *const table,
const u8 *const weights,
const int num_symbs);
/// Free the malloc'ed parts of a decoding table
static void HUF_free_dtable(HUF_dtable *const dtable);
/*** END HUFFMAN PRIMITIVES ***********/
/*** FSE PRIMITIVES *******************/
/// For more description of FSE see
/// https://github.com/Cyan4973/FiniteStateEntropy/
// FSE table decoding uses exponential memory, so limit the maximum accuracy
#define FSE_MAX_ACCURACY_LOG (15)
// Limit the maximum number of symbols so they can be stored in a single byte
#define FSE_MAX_SYMBS (256)
/// The tables needed to decode FSE encoded streams
typedef struct {
u8 *symbols;
u8 *num_bits;
u16 *new_state_base;
int accuracy_log;
} FSE_dtable;
/// Return the symbol for the current state
static inline u8 FSE_peek_symbol(const FSE_dtable *const dtable,
const u16 state);
/// Read the number of bits necessary to update state, update, and shift offset
/// back to reflect the bits read
static inline void FSE_update_state(const FSE_dtable *const dtable,
u16 *const state, const u8 *const src,
i64 *const offset);
/// Combine peek and update: decode a symbol and update the state
static inline u8 FSE_decode_symbol(const FSE_dtable *const dtable,
u16 *const state, const u8 *const src,
i64 *const offset);
/// Read bits from the stream to initialize the state and shift offset back
static inline void FSE_init_state(const FSE_dtable *const dtable,
u16 *const state, const u8 *const src,
i64 *const offset);
/// Decompress two interleaved bitstreams (e.g. compressed Huffman weights)
/// using an FSE decoding table. `src_len` must be the exact length of the
/// block.
static size_t FSE_decompress_interleaved2(const FSE_dtable *const dtable,
ostream_t *const out,
istream_t *const in);
/// Initialize a decoding table using normalized frequencies.
static void FSE_init_dtable(FSE_dtable *const dtable,
const i16 *const norm_freqs, const int num_symbs,
const int accuracy_log);
/// Decode an FSE header as defined in the Zstandard format specification and
/// use the decoded frequencies to initialize a decoding table.
static void FSE_decode_header(FSE_dtable *const dtable, istream_t *const in,
const int max_accuracy_log);
/// Initialize an FSE table that will always return the same symbol and consume
/// 0 bits per symbol, to be used for RLE mode in sequence commands
static void FSE_init_dtable_rle(FSE_dtable *const dtable, const u8 symb);
/// Free the malloc'ed parts of a decoding table
static void FSE_free_dtable(FSE_dtable *const dtable);
/*** END FSE PRIMITIVES ***************/
/******* END IMPLEMENTATION PRIMITIVE PROTOTYPES ******************************/
/******* ZSTD HELPER STRUCTS AND PROTOTYPES ***********************************/
/// A small structure that can be reused in various places that need to access
/// frame header information
typedef struct {
// The size of window that we need to be able to contiguously store for
// references
size_t window_size;
// The total output size of this compressed frame
size_t frame_content_size;
// The dictionary id if this frame uses one
u32 dictionary_id;
// Whether or not the content of this frame has a checksum
int content_checksum_flag;
// Whether or not the output for this frame is in a single segment
int single_segment_flag;
} frame_header_t;
/// The context needed to decode blocks in a frame
typedef struct {
frame_header_t header;
// The total amount of data available for backreferences, to determine if an
// offset too large to be correct
size_t current_total_output;
const u8 *dict_content;
size_t dict_content_len;
// Entropy encoding tables so they can be repeated by future blocks instead
// of retransmitting
HUF_dtable literals_dtable;
FSE_dtable ll_dtable;
FSE_dtable ml_dtable;
FSE_dtable of_dtable;
// The last 3 offsets for the special "repeat offsets".
u64 previous_offsets[3];
} frame_context_t;
/// The decoded contents of a dictionary so that it doesn't have to be repeated
/// for each frame that uses it
struct dictionary_s {
// Entropy tables
HUF_dtable literals_dtable;
FSE_dtable ll_dtable;
FSE_dtable ml_dtable;
FSE_dtable of_dtable;
// Raw content for backreferences
u8 *content;
size_t content_size;
// Offset history to prepopulate the frame's history
u64 previous_offsets[3];
u32 dictionary_id;
};
/// A tuple containing the parts necessary to decode and execute a ZSTD sequence
/// command
typedef struct {
u32 literal_length;
u32 match_length;
u32 offset;
} sequence_command_t;
/// The decoder works top-down, starting at the high level like Zstd frames, and
/// working down to lower more technical levels such as blocks, literals, and
/// sequences. The high-level functions roughly follow the outline of the
/// format specification:
/// https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md
/// Before the implementation of each high-level function declared here, the
/// prototypes for their helper functions are defined and explained
/// Decode a single Zstd frame, or error if the input is not a valid frame.
/// Accepts a dict argument, which may be NULL indicating no dictionary.
/// See
/// https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#frame-concatenation
static void decode_frame(ostream_t *const out, istream_t *const in,
const dictionary_t *const dict);
// Decode data in a compressed block
static void decompress_block(frame_context_t *const ctx, ostream_t *const out,
istream_t *const in);
// Decode the literals section of a block
static size_t decode_literals(frame_context_t *const ctx, istream_t *const in,
u8 **const literals);
// Decode the sequences part of a block
static size_t decode_sequences(frame_context_t *const ctx, istream_t *const in,
sequence_command_t **const sequences);
// Execute the decoded sequences on the literals block
static void execute_sequences(frame_context_t *const ctx, ostream_t *const out,
const u8 *const literals,
const size_t literals_len,
const sequence_command_t *const sequences,
const size_t num_sequences);
// Copies literals and returns the total literal length that was copied
static u32 copy_literals(const size_t seq, istream_t *litstream,
ostream_t *const out);
// Given an offset code from a sequence command (either an actual offset value
// or an index for previous offset), computes the correct offset and updates
// the offset history
static size_t compute_offset(sequence_command_t seq, u64 *const offset_hist);
// Given an offset, match length, and total output, as well as the frame
// context for the dictionary, determines if the dictionary is used and
// executes the copy operation
static void execute_match_copy(frame_context_t *const ctx, size_t offset,
size_t match_length, size_t total_output,
ostream_t *const out);
/******* END ZSTD HELPER STRUCTS AND PROTOTYPES *******************************/
size_t ZSTD_decompress(void *const dst, const size_t dst_len,
const void *const src, const size_t src_len) {
dictionary_t* const uninit_dict = create_dictionary();
size_t const decomp_size = ZSTD_decompress_with_dict(dst, dst_len, src,
src_len, uninit_dict);
free_dictionary(uninit_dict);
return decomp_size;
}
size_t ZSTD_decompress_with_dict(void *const dst, const size_t dst_len,
const void *const src, const size_t src_len,
dictionary_t* parsed_dict) {
istream_t in = IO_make_istream(src, src_len);
ostream_t out = IO_make_ostream(dst, dst_len);
// "A content compressed by Zstandard is transformed into a Zstandard frame.
// Multiple frames can be appended into a single file or stream. A frame is
// totally independent, has a defined beginning and end, and a set of
// parameters which tells the decoder how to decompress it."
/* this decoder assumes decompression of a single frame */
decode_frame(&out, &in, parsed_dict);
return (size_t)(out.ptr - (u8 *)dst);
}
/******* FRAME DECODING ******************************************************/
static void decode_data_frame(ostream_t *const out, istream_t *const in,
const dictionary_t *const dict);
static void init_frame_context(frame_context_t *const context,
istream_t *const in,
const dictionary_t *const dict);
static void free_frame_context(frame_context_t *const context);
static void parse_frame_header(frame_header_t *const header,
ext/zstd/doc/educational_decoder/zstd_decompress.c view on Meta::CPAN
const int block_type,
const int size_format) {
size_t regenerated_size, compressed_size;
// Only size_format=0 has 1 stream, so default to 4
int num_streams = 4;
switch (size_format) {
case 0:
// "A single stream. Both Compressed_Size and Regenerated_Size use 10
// bits (0-1023)."
num_streams = 1;
// Fall through as it has the same size format
/* fallthrough */
case 1:
// "4 streams. Both Compressed_Size and Regenerated_Size use 10 bits
// (0-1023)."
regenerated_size = IO_read_bits(in, 10);
compressed_size = IO_read_bits(in, 10);
break;
case 2:
// "4 streams. Both Compressed_Size and Regenerated_Size use 14 bits
// (0-16383)."
regenerated_size = IO_read_bits(in, 14);
compressed_size = IO_read_bits(in, 14);
break;
case 3:
// "4 streams. Both Compressed_Size and Regenerated_Size use 18 bits
// (0-262143)."
regenerated_size = IO_read_bits(in, 18);
compressed_size = IO_read_bits(in, 18);
break;
default:
// Impossible
IMPOSSIBLE();
}
if (regenerated_size > MAX_LITERALS_SIZE) {
CORRUPTION();
}
*literals = malloc(regenerated_size);
if (!*literals) {
BAD_ALLOC();
}
ostream_t lit_stream = IO_make_ostream(*literals, regenerated_size);
istream_t huf_stream = IO_make_sub_istream(in, compressed_size);
if (block_type == 2) {
// Decode the provided Huffman table
// "This section is only present when Literals_Block_Type type is
// Compressed_Literals_Block (2)."
HUF_free_dtable(&ctx->literals_dtable);
decode_huf_table(&ctx->literals_dtable, &huf_stream);
} else {
// If the previous Huffman table is being repeated, ensure it exists
if (!ctx->literals_dtable.symbols) {
CORRUPTION();
}
}
size_t symbols_decoded;
if (num_streams == 1) {
symbols_decoded = HUF_decompress_1stream(&ctx->literals_dtable, &lit_stream, &huf_stream);
} else {
symbols_decoded = HUF_decompress_4stream(&ctx->literals_dtable, &lit_stream, &huf_stream);
}
if (symbols_decoded != regenerated_size) {
CORRUPTION();
}
return regenerated_size;
}
// Decode the Huffman table description
static void decode_huf_table(HUF_dtable *const dtable, istream_t *const in) {
// "All literal values from zero (included) to last present one (excluded)
// are represented by Weight with values from 0 to Max_Number_of_Bits."
// "This is a single byte value (0-255), which describes how to decode the list of weights."
const u8 header = IO_read_bits(in, 8);
u8 weights[HUF_MAX_SYMBS];
memset(weights, 0, sizeof(weights));
int num_symbs;
if (header >= 128) {
// "This is a direct representation, where each Weight is written
// directly as a 4 bits field (0-15). The full representation occupies
// ((Number_of_Symbols+1)/2) bytes, meaning it uses a last full byte
// even if Number_of_Symbols is odd. Number_of_Symbols = headerByte -
// 127"
num_symbs = header - 127;
const size_t bytes = (num_symbs + 1) / 2;
const u8 *const weight_src = IO_get_read_ptr(in, bytes);
for (int i = 0; i < num_symbs; i++) {
// "They are encoded forward, 2
// weights to a byte with the first weight taking the top four bits
// and the second taking the bottom four (e.g. the following
// operations could be used to read the weights: Weight[0] =
// (Byte[0] >> 4), Weight[1] = (Byte[0] & 0xf), etc.)."
if (i % 2 == 0) {
weights[i] = weight_src[i / 2] >> 4;
} else {
weights[i] = weight_src[i / 2] & 0xf;
}
}
} else {
// The weights are FSE encoded, decode them before we can construct the
// table
istream_t fse_stream = IO_make_sub_istream(in, header);
ostream_t weight_stream = IO_make_ostream(weights, HUF_MAX_SYMBS);
fse_decode_hufweights(&weight_stream, &fse_stream, &num_symbs);
}
// Construct the table using the decoded weights
HUF_init_dtable_usingweights(dtable, weights, num_symbs);
}
static void fse_decode_hufweights(ostream_t *weights, istream_t *const in,
int *const num_symbs) {
const int MAX_ACCURACY_LOG = 7;
FSE_dtable dtable;
// "An FSE bitstream starts by a header, describing probabilities
// distribution. It will create a Decoding Table. For a list of Huffman
// weights, maximum accuracy is 7 bits."
FSE_decode_header(&dtable, in, MAX_ACCURACY_LOG);
// Decode the weights
*num_symbs = FSE_decompress_interleaved2(&dtable, weights, in);
FSE_free_dtable(&dtable);
}
/******* END LITERALS DECODING ************************************************/
/******* SEQUENCE DECODING ****************************************************/
/// The combination of FSE states needed to decode sequences
typedef struct {
FSE_dtable ll_table;
FSE_dtable of_table;
FSE_dtable ml_table;
u16 ll_state;
u16 of_state;
u16 ml_state;
} sequence_states_t;
/// Different modes to signal to decode_seq_tables what to do
typedef enum {
seq_literal_length = 0,
seq_offset = 1,
seq_match_length = 2,
} seq_part_t;
typedef enum {
seq_predefined = 0,
seq_rle = 1,
seq_fse = 2,
seq_repeat = 3,
} seq_mode_t;
/// The predefined FSE distribution tables for `seq_predefined` mode
static const i16 SEQ_LITERAL_LENGTH_DEFAULT_DIST[36] = {
4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2,
2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1, -1, -1, -1, -1};
static const i16 SEQ_OFFSET_DEFAULT_DIST[29] = {
1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1};
static const i16 SEQ_MATCH_LENGTH_DEFAULT_DIST[53] = {
1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1};
/// The sequence decoding baseline and number of additional bits to read/add
ext/zstd/doc/educational_decoder/zstd_decompress.c view on Meta::CPAN
static void decompress_sequences(frame_context_t *const ctx, istream_t *in,
sequence_command_t *const sequences,
const size_t num_sequences) {
// "The Sequences_Section regroup all symbols required to decode commands.
// There are 3 symbol types : literals lengths, offsets and match lengths.
// They are encoded together, interleaved, in a single bitstream."
// "Symbol compression modes
//
// This is a single byte, defining the compression mode of each symbol
// type."
//
// Bit number : Field name
// 7-6 : Literals_Lengths_Mode
// 5-4 : Offsets_Mode
// 3-2 : Match_Lengths_Mode
// 1-0 : Reserved
u8 compression_modes = IO_read_bits(in, 8);
if ((compression_modes & 3) != 0) {
// Reserved bits set
CORRUPTION();
}
// "Following the header, up to 3 distribution tables can be described. When
// present, they are in this order :
//
// Literals lengths
// Offsets
// Match Lengths"
// Update the tables we have stored in the context
decode_seq_table(&ctx->ll_dtable, in, seq_literal_length,
(compression_modes >> 6) & 3);
decode_seq_table(&ctx->of_dtable, in, seq_offset,
(compression_modes >> 4) & 3);
decode_seq_table(&ctx->ml_dtable, in, seq_match_length,
(compression_modes >> 2) & 3);
sequence_states_t states;
// Initialize the decoding tables
{
states.ll_table = ctx->ll_dtable;
states.of_table = ctx->of_dtable;
states.ml_table = ctx->ml_dtable;
}
const size_t len = IO_istream_len(in);
const u8 *const src = IO_get_read_ptr(in, len);
// "After writing the last bit containing information, the compressor writes
// a single 1-bit and then fills the byte with 0-7 0 bits of padding."
const int padding = 8 - highest_set_bit(src[len - 1]);
// The offset starts at the end because FSE streams are read backwards
i64 bit_offset = (i64)(len * 8 - (size_t)padding);
// "The bitstream starts with initial state values, each using the required
// number of bits in their respective accuracy, decoded previously from
// their normalized distribution.
//
// It starts by Literals_Length_State, followed by Offset_State, and finally
// Match_Length_State."
FSE_init_state(&states.ll_table, &states.ll_state, src, &bit_offset);
FSE_init_state(&states.of_table, &states.of_state, src, &bit_offset);
FSE_init_state(&states.ml_table, &states.ml_state, src, &bit_offset);
for (size_t i = 0; i < num_sequences; i++) {
// Decode sequences one by one
sequences[i] = decode_sequence(&states, src, &bit_offset);
}
if (bit_offset != 0) {
CORRUPTION();
}
}
// Decode a single sequence and update the state
static sequence_command_t decode_sequence(sequence_states_t *const states,
const u8 *const src,
i64 *const offset) {
// "Each symbol is a code in its own context, which specifies Baseline and
// Number_of_Bits to add. Codes are FSE compressed, and interleaved with raw
// additional bits in the same bitstream."
// Decode symbols, but don't update states
const u8 of_code = FSE_peek_symbol(&states->of_table, states->of_state);
const u8 ll_code = FSE_peek_symbol(&states->ll_table, states->ll_state);
const u8 ml_code = FSE_peek_symbol(&states->ml_table, states->ml_state);
// Offset doesn't need a max value as it's not decoded using a table
if (ll_code > SEQ_MAX_CODES[seq_literal_length] ||
ml_code > SEQ_MAX_CODES[seq_match_length]) {
CORRUPTION();
}
// Read the interleaved bits
sequence_command_t seq;
// "Decoding starts by reading the Number_of_Bits required to decode Offset.
// It then does the same for Match_Length, and then for Literals_Length."
seq.offset = ((u32)1 << of_code) + STREAM_read_bits(src, of_code, offset);
seq.match_length =
SEQ_MATCH_LENGTH_BASELINES[ml_code] +
STREAM_read_bits(src, SEQ_MATCH_LENGTH_EXTRA_BITS[ml_code], offset);
seq.literal_length =
SEQ_LITERAL_LENGTH_BASELINES[ll_code] +
STREAM_read_bits(src, SEQ_LITERAL_LENGTH_EXTRA_BITS[ll_code], offset);
// "If it is not the last sequence in the block, the next operation is to
// update states. Using the rules pre-calculated in the decoding tables,
// Literals_Length_State is updated, followed by Match_Length_State, and
// then Offset_State."
// If the stream is complete don't read bits to update state
if (*offset != 0) {
FSE_update_state(&states->ll_table, &states->ll_state, src, offset);
FSE_update_state(&states->ml_table, &states->ml_state, src, offset);
FSE_update_state(&states->of_table, &states->of_state, src, offset);
}
return seq;
}
/// Given a sequence part and table mode, decode the FSE distribution
/// Errors if the mode is `seq_repeat` without a pre-existing table in `table`
static void decode_seq_table(FSE_dtable *const table, istream_t *const in,
const seq_part_t type, const seq_mode_t mode) {
// Constant arrays indexed by seq_part_t
const i16 *const default_distributions[] = {SEQ_LITERAL_LENGTH_DEFAULT_DIST,
SEQ_OFFSET_DEFAULT_DIST,
SEQ_MATCH_LENGTH_DEFAULT_DIST};
const size_t default_distribution_lengths[] = {36, 29, 53};
const size_t default_distribution_accuracies[] = {6, 5, 6};
const size_t max_accuracies[] = {9, 8, 9};
if (mode != seq_repeat) {
// Free old one before overwriting
FSE_free_dtable(table);
}
switch (mode) {
case seq_predefined: {
// "Predefined_Mode : uses a predefined distribution table."
const i16 *distribution = default_distributions[type];
const size_t symbs = default_distribution_lengths[type];
const size_t accuracy_log = default_distribution_accuracies[type];
FSE_init_dtable(table, distribution, symbs, accuracy_log);
break;
ext/zstd/doc/educational_decoder/zstd_decompress.c view on Meta::CPAN
static inline u8 HUF_decode_symbol(const HUF_dtable *const dtable,
u16 *const state, const u8 *const src,
i64 *const offset) {
// Look up the symbol and number of bits to read
const u8 symb = dtable->symbols[*state];
const u8 bits = dtable->num_bits[*state];
const u16 rest = STREAM_read_bits(src, bits, offset);
// Shift `bits` bits out of the state, keeping the low order bits that
// weren't necessary to determine this symbol. Then add in the new bits
// read from the stream.
*state = ((*state << bits) + rest) & (((u16)1 << dtable->max_bits) - 1);
return symb;
}
static inline void HUF_init_state(const HUF_dtable *const dtable,
u16 *const state, const u8 *const src,
i64 *const offset) {
// Read in a full `dtable->max_bits` bits to initialize the state
const u8 bits = dtable->max_bits;
*state = STREAM_read_bits(src, bits, offset);
}
static size_t HUF_decompress_1stream(const HUF_dtable *const dtable,
ostream_t *const out,
istream_t *const in) {
const size_t len = IO_istream_len(in);
if (len == 0) {
INP_SIZE();
}
const u8 *const src = IO_get_read_ptr(in, len);
// "Each bitstream must be read backward, that is starting from the end down
// to the beginning. Therefore it's necessary to know the size of each
// bitstream.
//
// It's also necessary to know exactly which bit is the latest. This is
// detected by a final bit flag : the highest bit of latest byte is a
// final-bit-flag. Consequently, a last byte of 0 is not possible. And the
// final-bit-flag itself is not part of the useful bitstream. Hence, the
// last byte contains between 0 and 7 useful bits."
const int padding = 8 - highest_set_bit(src[len - 1]);
// Offset starts at the end because HUF streams are read backwards
i64 bit_offset = len * 8 - padding;
u16 state;
HUF_init_state(dtable, &state, src, &bit_offset);
size_t symbols_written = 0;
while (bit_offset > -dtable->max_bits) {
// Iterate over the stream, decoding one symbol at a time
IO_write_byte(out, HUF_decode_symbol(dtable, &state, src, &bit_offset));
symbols_written++;
}
// "The process continues up to reading the required number of symbols per
// stream. If a bitstream is not entirely and exactly consumed, hence
// reaching exactly its beginning position with all bits consumed, the
// decoding process is considered faulty."
// When all symbols have been decoded, the final state value shouldn't have
// any data from the stream, so it should have "read" dtable->max_bits from
// before the start of `src`
// Therefore `offset`, the edge to start reading new bits at, should be
// dtable->max_bits before the start of the stream
if (bit_offset != -dtable->max_bits) {
CORRUPTION();
}
return symbols_written;
}
static size_t HUF_decompress_4stream(const HUF_dtable *const dtable,
ostream_t *const out, istream_t *const in) {
// "Compressed size is provided explicitly : in the 4-streams variant,
// bitstreams are preceded by 3 unsigned little-endian 16-bits values. Each
// value represents the compressed size of one stream, in order. The last
// stream size is deducted from total compressed size and from previously
// decoded stream sizes"
const size_t csize1 = IO_read_bits(in, 16);
const size_t csize2 = IO_read_bits(in, 16);
const size_t csize3 = IO_read_bits(in, 16);
istream_t in1 = IO_make_sub_istream(in, csize1);
istream_t in2 = IO_make_sub_istream(in, csize2);
istream_t in3 = IO_make_sub_istream(in, csize3);
istream_t in4 = IO_make_sub_istream(in, IO_istream_len(in));
size_t total_output = 0;
// Decode each stream independently for simplicity
// If we wanted to we could decode all 4 at the same time for speed,
// utilizing more execution units
total_output += HUF_decompress_1stream(dtable, out, &in1);
total_output += HUF_decompress_1stream(dtable, out, &in2);
total_output += HUF_decompress_1stream(dtable, out, &in3);
total_output += HUF_decompress_1stream(dtable, out, &in4);
return total_output;
}
/// Initializes a Huffman table using canonical Huffman codes
/// For more explanation on canonical Huffman codes see
/// https://www.cs.scranton.edu/~mccloske/courses/cmps340/huff_canonical_dec2015.html
/// Codes within a level are allocated in symbol order (i.e. smaller symbols get
/// earlier codes)
static void HUF_init_dtable(HUF_dtable *const table, const u8 *const bits,
const int num_symbs) {
memset(table, 0, sizeof(HUF_dtable));
if (num_symbs > HUF_MAX_SYMBS) {
ERROR("Too many symbols for Huffman");
}
u8 max_bits = 0;
u16 rank_count[HUF_MAX_BITS + 1];
memset(rank_count, 0, sizeof(rank_count));
// Count the number of symbols for each number of bits, and determine the
// depth of the tree
for (int i = 0; i < num_symbs; i++) {
if (bits[i] > HUF_MAX_BITS) {
ERROR("Huffman table depth too large");
}
max_bits = MAX(max_bits, bits[i]);
rank_count[bits[i]]++;
}
const size_t table_size = 1 << max_bits;
table->max_bits = max_bits;
table->symbols = malloc(table_size);
table->num_bits = malloc(table_size);
if (!table->symbols || !table->num_bits) {
free(table->symbols);
free(table->num_bits);
BAD_ALLOC();
}
// "Symbols are sorted by Weight. Within same Weight, symbols keep natural
// order. Symbols with a Weight of zero are removed. Then, starting from
ext/zstd/doc/educational_decoder/zstd_decompress.c view on Meta::CPAN
// the lower bits
const u16 len = 1 << (max_bits - bits[i]);
memset(&table->symbols[code], i, len);
rank_idx[bits[i]] += len;
}
}
}
static void HUF_init_dtable_usingweights(HUF_dtable *const table,
const u8 *const weights,
const int num_symbs) {
// +1 because the last weight is not transmitted in the header
if (num_symbs + 1 > HUF_MAX_SYMBS) {
ERROR("Too many symbols for Huffman");
}
u8 bits[HUF_MAX_SYMBS];
u64 weight_sum = 0;
for (int i = 0; i < num_symbs; i++) {
// Weights are in the same range as bit count
if (weights[i] > HUF_MAX_BITS) {
CORRUPTION();
}
weight_sum += weights[i] > 0 ? (u64)1 << (weights[i] - 1) : 0;
}
// Find the first power of 2 larger than the sum
const int max_bits = highest_set_bit(weight_sum) + 1;
const u64 left_over = ((u64)1 << max_bits) - weight_sum;
// If the left over isn't a power of 2, the weights are invalid
if (left_over & (left_over - 1)) {
CORRUPTION();
}
// left_over is used to find the last weight as it's not transmitted
// by inverting 2^(weight - 1) we can determine the value of last_weight
const int last_weight = highest_set_bit(left_over) + 1;
for (int i = 0; i < num_symbs; i++) {
// "Number_of_Bits = Number_of_Bits ? Max_Number_of_Bits + 1 - Weight : 0"
bits[i] = weights[i] > 0 ? (max_bits + 1 - weights[i]) : 0;
}
bits[num_symbs] =
max_bits + 1 - last_weight; // Last weight is always non-zero
HUF_init_dtable(table, bits, num_symbs + 1);
}
static void HUF_free_dtable(HUF_dtable *const dtable) {
free(dtable->symbols);
free(dtable->num_bits);
memset(dtable, 0, sizeof(HUF_dtable));
}
/******* END HUFFMAN PRIMITIVES ***********************************************/
/******* FSE PRIMITIVES *******************************************************/
/// For more description of FSE see
/// https://github.com/Cyan4973/FiniteStateEntropy/
/// Allow a symbol to be decoded without updating state
static inline u8 FSE_peek_symbol(const FSE_dtable *const dtable,
const u16 state) {
return dtable->symbols[state];
}
/// Consumes bits from the input and uses the current state to determine the
/// next state
static inline void FSE_update_state(const FSE_dtable *const dtable,
u16 *const state, const u8 *const src,
i64 *const offset) {
const u8 bits = dtable->num_bits[*state];
const u16 rest = STREAM_read_bits(src, bits, offset);
*state = dtable->new_state_base[*state] + rest;
}
/// Decodes a single FSE symbol and updates the offset
static inline u8 FSE_decode_symbol(const FSE_dtable *const dtable,
u16 *const state, const u8 *const src,
i64 *const offset) {
const u8 symb = FSE_peek_symbol(dtable, *state);
FSE_update_state(dtable, state, src, offset);
return symb;
}
static inline void FSE_init_state(const FSE_dtable *const dtable,
u16 *const state, const u8 *const src,
i64 *const offset) {
// Read in a full `accuracy_log` bits to initialize the state
const u8 bits = dtable->accuracy_log;
*state = STREAM_read_bits(src, bits, offset);
}
static size_t FSE_decompress_interleaved2(const FSE_dtable *const dtable,
ostream_t *const out,
istream_t *const in) {
const size_t len = IO_istream_len(in);
if (len == 0) {
INP_SIZE();
}
const u8 *const src = IO_get_read_ptr(in, len);
// "Each bitstream must be read backward, that is starting from the end down
// to the beginning. Therefore it's necessary to know the size of each
// bitstream.
//
// It's also necessary to know exactly which bit is the latest. This is
// detected by a final bit flag : the highest bit of latest byte is a
// final-bit-flag. Consequently, a last byte of 0 is not possible. And the
// final-bit-flag itself is not part of the useful bitstream. Hence, the
// last byte contains between 0 and 7 useful bits."
const int padding = 8 - highest_set_bit(src[len - 1]);
i64 offset = len * 8 - padding;
u16 state1, state2;
// "The first state (State1) encodes the even indexed symbols, and the
// second (State2) encodes the odd indexes. State1 is initialized first, and
// then State2, and they take turns decoding a single symbol and updating
// their state."
FSE_init_state(dtable, &state1, src, &offset);
FSE_init_state(dtable, &state2, src, &offset);
// Decode until we overflow the stream
// Since we decode in reverse order, overflowing the stream is offset going
// negative
size_t symbols_written = 0;
while (1) {
// "The number of symbols to decode is determined by tracking bitStream
// overflow condition: If updating state after decoding a symbol would
// require more bits than remain in the stream, it is assumed the extra
// bits are 0. Then, the symbols for each of the final states are
// decoded and the process is complete."
IO_write_byte(out, FSE_decode_symbol(dtable, &state1, src, &offset));
symbols_written++;
if (offset < 0) {
// There's still a symbol to decode in state2
IO_write_byte(out, FSE_peek_symbol(dtable, state2));
symbols_written++;
break;
}
IO_write_byte(out, FSE_decode_symbol(dtable, &state2, src, &offset));
symbols_written++;
if (offset < 0) {
// There's still a symbol to decode in state1
IO_write_byte(out, FSE_peek_symbol(dtable, state1));
symbols_written++;
break;
}
}
return symbols_written;
}
static void FSE_init_dtable(FSE_dtable *const dtable,
const i16 *const norm_freqs, const int num_symbs,
const int accuracy_log) {
if (accuracy_log > FSE_MAX_ACCURACY_LOG) {
ERROR("FSE accuracy too large");
}
if (num_symbs > FSE_MAX_SYMBS) {
ERROR("Too many symbols for FSE");
}
dtable->accuracy_log = accuracy_log;
const size_t size = (size_t)1 << accuracy_log;
dtable->symbols = malloc(size * sizeof(u8));
dtable->num_bits = malloc(size * sizeof(u8));
dtable->new_state_base = malloc(size * sizeof(u16));
if (!dtable->symbols || !dtable->num_bits || !dtable->new_state_base) {
BAD_ALLOC();
}
// Used to determine how many bits need to be read for each state,
// and where the destination range should start
// Needs to be u16 because max value is 2 * max number of symbols,
// which can be larger than a byte can store
u16 state_desc[FSE_MAX_SYMBS];
// "Symbols are scanned in their natural order for "less than 1"
// probabilities. Symbols with this probability are being attributed a
// single cell, starting from the end of the table. These symbols define a
// full state reset, reading Accuracy_Log bits."
int high_threshold = size;
for (int s = 0; s < num_symbs; s++) {
// Scan for low probability symbols to put at the top
if (norm_freqs[s] == -1) {
dtable->symbols[--high_threshold] = s;
state_desc[s] = 1;
}
}
// "All remaining symbols are sorted in their natural order. Starting from
// symbol 0 and table position 0, each symbol gets attributed as many cells
// as its probability. Cell allocation is spread, not linear."
// Place the rest in the table
const u16 step = (size >> 1) + (size >> 3) + 3;
const u16 mask = size - 1;
u16 pos = 0;
for (int s = 0; s < num_symbs; s++) {
if (norm_freqs[s] <= 0) {
continue;
}
state_desc[s] = norm_freqs[s];
for (int i = 0; i < norm_freqs[s]; i++) {
// Give `norm_freqs[s]` states to symbol s
dtable->symbols[pos] = s;
// "A position is skipped if already occupied, typically by a "less
// than 1" probability symbol."
do {
pos = (pos + step) & mask;
} while (pos >=
high_threshold);
// Note: no other collision checking is necessary as `step` is
// coprime to `size`, so the cycle will visit each position exactly
// once
}
}
if (pos != 0) {
CORRUPTION();
}
// Now we can fill baseline and num bits
for (size_t i = 0; i < size; i++) {
u8 symbol = dtable->symbols[i];
u16 next_state_desc = state_desc[symbol]++;
// Fills in the table appropriately, next_state_desc increases by symbol
// over time, decreasing number of bits
dtable->num_bits[i] = (u8)(accuracy_log - highest_set_bit(next_state_desc));
// Baseline increases until the bit threshold is passed, at which point
// it resets to 0
dtable->new_state_base[i] =
((u16)next_state_desc << dtable->num_bits[i]) - size;
}
}
/// Decode an FSE header as defined in the Zstandard format specification and
/// use the decoded frequencies to initialize a decoding table.
static void FSE_decode_header(FSE_dtable *const dtable, istream_t *const in,
const int max_accuracy_log) {
// "An FSE distribution table describes the probabilities of all symbols
// from 0 to the last present one (included) on a normalized scale of 1 <<
// Accuracy_Log .
//
// It's a bitstream which is read forward, in little-endian fashion. It's
// not necessary to know its exact size, since it will be discovered and
// reported by the decoding process.
if (max_accuracy_log > FSE_MAX_ACCURACY_LOG) {
ERROR("FSE accuracy too large");
}
// The bitstream starts by reporting on which scale it operates.
// Accuracy_Log = low4bits + 5. Note that maximum Accuracy_Log for literal
// and match lengths is 9, and for offsets is 8. Higher values are
// considered errors."
const int accuracy_log = 5 + IO_read_bits(in, 4);
if (accuracy_log > max_accuracy_log) {
ERROR("FSE accuracy too large");
}
// "Then follows each symbol value, from 0 to last present one. The number
// of bits used by each field is variable. It depends on :
//
// Remaining probabilities + 1 : example : Presuming an Accuracy_Log of 8,
// and presuming 100 probabilities points have already been distributed, the
// decoder may read any value from 0 to 255 - 100 + 1 == 156 (inclusive).
// Therefore, it must read log2sup(156) == 8 bits.
//
// Value decoded : small values use 1 less bit : example : Presuming values
// from 0 to 156 (inclusive) are possible, 255-156 = 99 values are remaining
// in an 8-bits field. They are used this way : first 99 values (hence from
// 0 to 98) use only 7 bits, values from 99 to 156 use 8 bits. "
i32 remaining = 1 << accuracy_log;
i16 frequencies[FSE_MAX_SYMBS];
int symb = 0;
while (remaining > 0 && symb < FSE_MAX_SYMBS) {
// Log of the number of possible values we could read
int bits = highest_set_bit(remaining + 1) + 1;
u16 val = IO_read_bits(in, bits);
// Try to mask out the lower bits to see if it qualifies for the "small
// value" threshold
const u16 lower_mask = ((u16)1 << (bits - 1)) - 1;
const u16 threshold = ((u16)1 << bits) - 1 - (remaining + 1);
if ((val & lower_mask) < threshold) {
IO_rewind_bits(in, 1);
val = val & lower_mask;
} else if (val > lower_mask) {
val = val - threshold;
}
// "Probability is obtained from Value decoded by following formula :
// Proba = value - 1"
const i16 proba = (i16)val - 1;
// "It means value 0 becomes negative probability -1. -1 is a special
// probability, which means "less than 1". Its effect on distribution
// table is described in next paragraph. For the purpose of calculating
// cumulated distribution, it counts as one."
remaining -= proba < 0 ? -proba : proba;
frequencies[symb] = proba;
symb++;
// "When a symbol has a probability of zero, it is followed by a 2-bits
// repeat flag. This repeat flag tells how many probabilities of zeroes
// follow the current one. It provides a number ranging from 0 to 3. If
// it is a 3, another 2-bits repeat flag follows, and so on."
if (proba == 0) {
// Read the next two bits to see how many more 0s
int repeat = IO_read_bits(in, 2);
while (1) {
for (int i = 0; i < repeat && symb < FSE_MAX_SYMBS; i++) {
frequencies[symb++] = 0;
}
if (repeat == 3) {
repeat = IO_read_bits(in, 2);
} else {
break;
}
}
}
}
IO_align_stream(in);
// "When last symbol reaches cumulated total of 1 << Accuracy_Log, decoding
// is complete. If the last symbol makes cumulated total go above 1 <<
// Accuracy_Log, distribution is considered corrupted."
if (remaining != 0 || symb >= FSE_MAX_SYMBS) {
CORRUPTION();
}
// Initialize the decoding table using the determined weights
FSE_init_dtable(dtable, frequencies, symb, accuracy_log);
}
static void FSE_init_dtable_rle(FSE_dtable *const dtable, const u8 symb) {
dtable->symbols = malloc(sizeof(u8));
dtable->num_bits = malloc(sizeof(u8));
dtable->new_state_base = malloc(sizeof(u16));
if (!dtable->symbols || !dtable->num_bits || !dtable->new_state_base) {
BAD_ALLOC();
}
// This setup will always have a state of 0, always return symbol `symb`,
// and never consume any bits
dtable->symbols[0] = symb;
dtable->num_bits[0] = 0;
dtable->new_state_base[0] = 0;
dtable->accuracy_log = 0;
( run in 0.629 second using v1.01-cache-2.11-cpan-39bf76dae61 )