/* Writes @num_bits bits, given by the @num_bits least significant bits of
* @bits, to the output @ostream. */
int bitstream_put_bits(struct output_bitstream *ostream, output_bitbuf_t bits,
- uint num_bits)
+ unsigned num_bits)
{
- uint rem_bits;
+ unsigned rem_bits;
wimlib_assert(num_bits <= 16);
if (num_bits <= ostream->free_bits) {
/* Initializes an output bit buffer to write its output to the memory location
* pointer to by @data. */
void init_output_bitstream(struct output_bitstream *ostream, void *data,
- uint num_bytes)
+ unsigned num_bytes)
{
wimlib_assert(num_bytes >= 4);
* lens[i] bits of codewords[i] will contain the codeword
* for symbol i.
*/
-void make_canonical_huffman_code(uint num_syms, uint max_codeword_len,
+void make_canonical_huffman_code(unsigned num_syms, unsigned max_codeword_len,
const u32 freq_tab[], u8 lens[],
u16 codewords[])
{
/* Calculate how many symbols have non-zero frequency. These are the
* symbols that actually appeared in the input. */
- uint num_used_symbols = 0;
- for (uint i = 0; i < num_syms; i++)
+ unsigned num_used_symbols = 0;
+ for (unsigned i = 0; i < num_syms; i++)
if (freq_tab[i] != 0)
num_used_symbols++;
/* Initialize the array of leaf nodes with the symbols and their
* frequencies. */
HuffmanLeafNode leaves[num_used_symbols];
- uint leaf_idx = 0;
- for (uint i = 0; i < num_syms; i++) {
+ unsigned leaf_idx = 0;
+ for (unsigned i = 0; i < num_syms; i++) {
if (freq_tab[i] != 0) {
leaves[leaf_idx].freq = freq_tab[i];
leaves[leaf_idx].sym = i;
* encoded data take up more room anyway, since binary
* data itself has 2 symbols. */
- uint sym = leaves[0].sym;
+ unsigned sym = leaves[0].sym;
codewords[0] = 0;
lens[0] = 1;
* codewords approach the length
* log_2(num_used_symbols).
* */
- for (uint i = 0; i < num_used_symbols; i++)
+ for (unsigned i = 0; i < num_used_symbols; i++)
if (leaves[i].freq > 1)
leaves[i].freq >>= 1;
goto try_building_tree_again;
qsort(leaves, num_used_symbols, sizeof(leaves[0]), cmp_leaves_by_code_len);
u16 cur_codeword = 0;
- uint cur_codeword_len = 0;
- for (uint i = 0; i < num_used_symbols; i++) {
+ unsigned cur_codeword_len = 0;
+ for (unsigned i = 0; i < num_used_symbols; i++) {
/* Each time a codeword becomes one longer, the current codeword
* is left shifted by one place. This is part of the procedure
* whenever a codeword is used, 1 is added to the current
* codeword. */
- uint len_diff = leaves[i].path_len - cur_codeword_len;
+ unsigned len_diff = leaves[i].path_len - cur_codeword_len;
cur_codeword <<= len_diff;
cur_codeword_len += len_diff;
* entries from pointers by the fact that values less than @num_syms must be
* symbol values.
*/
-int make_huffman_decode_table(u16 decode_table[], uint num_syms,
- uint num_bits, const u8 lens[],
- uint max_code_len)
+int make_huffman_decode_table(u16 decode_table[], unsigned num_syms,
+ unsigned num_bits, const u8 lens[],
+ unsigned max_code_len)
{
/* Number of entries in the decode table. */
u32 table_num_entries = 1 << num_bits;
* array, and both symbols have the same code length, then we know that
* the code for A numerically precedes the code for B.
* */
- for (uint code_len = 1; code_len <= num_bits; code_len++) {
+ for (unsigned code_len = 1; code_len <= num_bits; code_len++) {
/* Number of entries that a code of length @code_length would
* need. */
/* For each symbol of length @code_len, fill in its entries in
* the decode table. */
- for (uint sym = 0; sym < num_syms; sym++) {
+ for (unsigned sym = 0; sym < num_syms; sym++) {
if (lens[sym] != code_len)
continue;
/* Fill all possible lookups of this symbol with
* the symbol itself. */
- for (uint i = 0; i < code_num_entries; i++)
+ for (unsigned i = 0; i < code_num_entries; i++)
decode_table[decode_table_pos + i] = sym;
/* Increment the position in the decode table by
/* First, zero out the rest of the entries; this is necessary so
* that the entries appear as "unallocated" in the next part. */
- for (uint i = decode_table_pos; i < table_num_entries; i++)
+ for (unsigned i = decode_table_pos; i < table_num_entries; i++)
decode_table[i] = 0;
/* Assert that 2**num_bits is at least num_syms. If this wasn't the
/* The current Huffman code. */
- uint current_code = decode_table_pos;
+ unsigned current_code = decode_table_pos;
/* The tree nodes are allocated starting at
* decode_table[table_num_entries]. Remember that the full size of the
* table, including the extra space for the tree nodes, is actually
* 2**num_bits + 2 * num_syms slots, while table_num_entries is only
* 2**num_bits. */
- uint next_free_tree_slot = table_num_entries;
+ unsigned next_free_tree_slot = table_num_entries;
/* Go through every codeword of length greater than @num_bits. Note:
* the LZX format guarantees that the codeword length can be at most 16
* bits. */
- for (uint code_len = num_bits + 1; code_len <= max_code_len;
+ for (unsigned code_len = num_bits + 1; code_len <= max_code_len;
code_len++)
{
current_code <<= 1;
- for (uint sym = 0; sym < num_syms; sym++) {
+ for (unsigned sym = 0; sym < num_syms; sym++) {
if (lens[sym] != code_len)
continue;
/* i is the index of the current node; find it from the
* prefix of the current Huffman code. */
- uint i = current_code >> (code_len - num_bits);
+ unsigned i = current_code >> (code_len - num_bits);
if (i >= (1 << num_bits)) {
ERROR("Invalid canonical Huffman code");
if (decode_table_pos != table_num_entries) {
- for (uint i = 0; i < num_syms; i++) {
+ for (unsigned i = 0; i < num_syms; i++) {
if (lens[i] != 0) {
ERROR("Lengths do not form a valid canonical "
"Huffman tree (only filled %u of %u "
static int read_huffsym_near_end_of_input(struct input_bitstream *istream,
const u16 decode_table[],
const u8 lens[],
- uint num_syms,
- uint table_bits,
- uint *n)
+ unsigned num_syms,
+ unsigned table_bits,
+ unsigned *n)
{
- uint bitsleft = istream->bitsleft;
- uint key_size;
+ unsigned bitsleft = istream->bitsleft;
+ unsigned key_size;
u16 sym;
u16 key_bits;
const u8 lengths[],
unsigned num_symbols,
unsigned table_bits,
- uint *n,
+ unsigned *n,
unsigned max_codeword_len)
{
/* In the most common case, there are at least max_codeword_len bits
* The AND operation guarantees that only 3 characters will affect the hash
* value, so every identical 3-character string will have the same hash value.
*/
-static inline uint update_hash(uint hash, u8 c)
+static inline unsigned update_hash(unsigned hash, u8 c)
{
return ((hash << HASH_SHIFT) ^ c) & HASH_MASK;
}
* to walk through the hash chain, until the special index `0' is reached,
* indicating the end of the hash chain.
*/
-static inline uint insert_string(u16 hash_tab[], u16 prev_tab[],
- const u8 window[], uint str_pos, uint hash)
+static inline unsigned insert_string(u16 hash_tab[], u16 prev_tab[],
+ const u8 window[], unsigned str_pos,
+ unsigned hash)
{
hash = update_hash(hash, window[str_pos + LZ_MIN_MATCH - 1]);
prev_tab[str_pos] = hash_tab[hash];
*
* Returns the length of the match that was found.
*/
-static uint longest_match(const u8 window[], uint bytes_remaining,
- uint strstart, const u16 prev_tab[],
- uint cur_match, uint prev_len,
- uint *match_start_ret,
- const struct lz_params *params)
+static unsigned longest_match(const u8 window[], unsigned bytes_remaining,
+ unsigned strstart, const u16 prev_tab[],
+ unsigned cur_match, unsigned prev_len,
+ unsigned *match_start_ret,
+ const struct lz_params *params)
{
- uint chain_len = params->max_chain_len;
+ unsigned chain_len = params->max_chain_len;
const u8 *scan = window + strstart;
const u8 *match;
- uint len;
- uint best_len = prev_len;
- uint match_start = cur_match;
+ unsigned len;
+ unsigned best_len = prev_len;
+ unsigned match_start = cur_match;
- uint nice_match = min(params->nice_match, bytes_remaining);
+ unsigned nice_match = min(params->nice_match, bytes_remaining);
const u8 *strend = scan + min(params->max_match, bytes_remaining);
* is the number of slots in @match_tab that have been filled with the
* intermediate representation of a match or literal byte.
*/
-uint lz_analyze_block(const u8 uncompressed_data[], uint uncompressed_len,
- u32 match_tab[], lz_record_match_t record_match,
- lz_record_literal_t record_literal, void *record_match_arg1,
- void *record_match_arg2, void *record_literal_arg,
- const struct lz_params *params)
+unsigned lz_analyze_block(const u8 uncompressed_data[],
+ unsigned uncompressed_len,
+ u32 match_tab[],
+ lz_record_match_t record_match,
+ lz_record_literal_t record_literal,
+ void *record_match_arg1,
+ void *record_match_arg2,
+ void *record_literal_arg,
+ const struct lz_params *params)
{
- uint cur_match_pos = 0;
- uint cur_input_pos = 0;
- uint hash = 0;
- uint hash_head = 0;
- uint prev_len = params->min_match - 1;
- uint prev_start;
- uint match_len = params->min_match - 1;
- uint match_start = 0;
+ unsigned cur_match_pos = 0;
+ unsigned cur_input_pos = 0;
+ unsigned hash = 0;
+ unsigned hash_head = 0;
+ unsigned prev_len = params->min_match - 1;
+ unsigned prev_start;
+ unsigned match_len = params->min_match - 1;
+ unsigned match_start = 0;
bool match_available = false;
u16 hash_tab[HASH_SIZE];
u32 match;
if (prev_len >= params->min_match && match_len <= prev_len) {
/* Do not insert strings in hash table beyond this. */
- uint max_insert = uncompressed_len - params->min_match;
+ unsigned max_insert = uncompressed_len - params->min_match;
/*DEBUG("Recording match (pos = %u, offset = %u, len = %u)\n",*/
/*cur_input_pos - 1, */
typedef uint32_t u32;
typedef uint64_t u64;
#endif
-typedef unsigned uint;
#ifndef min
#define min(a, b) ({ typeof(a) __a = (a); typeof(b) __b = (b); \
git://wimlib.net / wimlib / commitdiff