X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fcompress.c;h=c40256a045c60a9756d2766cb23d8f9b2f28cea9;hp=02ff35dd889ffb73344e2a95fc2c59d9204b658a;hb=a3bb2e86f2640f5d593d00250a627d3dcc9747a2;hpb=40beb80283a2df7af88c8359ca41adb814585e9a diff --git a/src/compress.c b/src/compress.c index 02ff35dd..c40256a0 100644 --- a/src/compress.c +++ b/src/compress.c @@ -5,7 +5,7 @@ */ /* - * Copyright (C) 2012 Eric Biggers + * Copyright (C) 2012, 2013 Eric Biggers * * This file is part of wimlib, a library for working with WIM files. * @@ -27,7 +27,8 @@ #include #include -static inline void flush_bits(struct output_bitstream *ostream) +static inline void +flush_bits(struct output_bitstream *ostream) { *(u16*)ostream->bit_output = cpu_to_le16(ostream->bitbuf); ostream->bit_output = ostream->next_bit_output; @@ -38,10 +39,11 @@ static inline void flush_bits(struct output_bitstream *ostream) /* 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) +int +bitstream_put_bits(struct output_bitstream *ostream, output_bitbuf_t bits, + unsigned num_bits) { - uint rem_bits; + unsigned rem_bits; wimlib_assert(num_bits <= 16); if (num_bits <= ostream->free_bits) { @@ -73,7 +75,8 @@ int bitstream_put_bits(struct output_bitstream *ostream, output_bitbuf_t bits, } /* Flushes any remaining bits in the output buffer to the output byte stream. */ -int flush_output_bitstream(struct output_bitstream *ostream) +int +flush_output_bitstream(struct output_bitstream *ostream) { if (ostream->num_bytes_remaining + (ostream->output - ostream->bit_output) < 2) @@ -87,8 +90,9 @@ int flush_output_bitstream(struct output_bitstream *ostream) /* 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) +void +init_output_bitstream(struct output_bitstream *ostream, void *data, + unsigned num_bytes) { wimlib_assert(num_bytes >= 4); @@ -126,7 +130,8 @@ typedef struct { /* Comparator function for HuffmanLeafNodes. Sorts primarily by symbol * frequency and secondarily by symbol value. */ -static int cmp_leaves_by_freq(const void *__leaf1, const void *__leaf2) +static int +cmp_leaves_by_freq(const void *__leaf1, const void *__leaf2) { const HuffmanLeafNode *leaf1 = __leaf1; const HuffmanLeafNode *leaf2 = __leaf2; @@ -141,7 +146,8 @@ static int cmp_leaves_by_freq(const void *__leaf1, const void *__leaf2) /* Comparator function for HuffmanLeafNodes. Sorts primarily by code length and * secondarily by symbol value. */ -static int cmp_leaves_by_code_len(const void *__leaf1, const void *__leaf2) +static int +cmp_leaves_by_code_len(const void *__leaf1, const void *__leaf2) { const HuffmanLeafNode *leaf1 = __leaf1; const HuffmanLeafNode *leaf2 = __leaf2; @@ -156,7 +162,8 @@ static int cmp_leaves_by_code_len(const void *__leaf1, const void *__leaf2) /* Recursive function to calculate the depth of the leaves in a Huffman tree. * */ -static void huffman_tree_compute_path_lengths(HuffmanNode *node, u16 cur_len) +static void +huffman_tree_compute_path_lengths(HuffmanNode *node, u16 cur_len) { if (node->sym == (u16)(-1)) { /* Intermediate node. */ @@ -168,7 +175,8 @@ static void huffman_tree_compute_path_lengths(HuffmanNode *node, u16 cur_len) } } -/* Creates a canonical Huffman code from an array of symbol frequencies. +/* make_canonical_huffman_code: - Creates a canonical Huffman code from an array + * of symbol frequencies. * * The algorithm used is similar to the well-known algorithm that builds a * Huffman tree using a minheap. In that algorithm, the leaf nodes are @@ -223,9 +231,10 @@ static void huffman_tree_compute_path_lengths(HuffmanNode *node, u16 cur_len) * 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, - const u32 freq_tab[], u8 lens[], - u16 codewords[]) +void +make_canonical_huffman_code(unsigned num_syms, unsigned max_codeword_len, + const freq_t freq_tab[], u8 lens[], + u16 codewords[]) { /* We require at least 2 possible symbols in the alphabet to produce a * valid Huffman decoding table. It is allowed that fewer than 2 symbols @@ -238,8 +247,8 @@ void make_canonical_huffman_code(uint num_syms, uint max_codeword_len, /* 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++; @@ -251,8 +260,8 @@ void make_canonical_huffman_code(uint num_syms, uint max_codeword_len, /* 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; @@ -276,7 +285,7 @@ void make_canonical_huffman_code(uint num_syms, uint max_codeword_len, * 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; @@ -350,14 +359,13 @@ try_building_tree_again: while (1) { /* Lowest frequency node. */ - HuffmanNode *f1 = NULL; + HuffmanNode *f1; /* Second lowest frequency node. */ - HuffmanNode *f2 = NULL; + HuffmanNode *f2; - /* Get the lowest and second lowest frequency nodes from - * the remaining leaves or from the intermediate nodes. - * */ + /* Get the lowest and second lowest frequency nodes from the + * remaining leaves or from the intermediate nodes. */ if (cur_leaf != end_leaf && (cur_inode == next_inode || cur_leaf->freq <= cur_inode->freq)) { @@ -371,11 +379,10 @@ try_building_tree_again: f2 = (HuffmanNode*)cur_leaf++; } else if (cur_inode != next_inode) { f2 = cur_inode++; - } - - /* All nodes used up! */ - if (f1 == NULL || f2 == NULL) + } else { + /* All nodes used up! */ break; + } /* next_inode becomes the parent of f1 and f2. */ @@ -401,7 +408,7 @@ try_building_tree_again: * 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; @@ -423,8 +430,8 @@ 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 @@ -432,7 +439,7 @@ try_building_tree_again: * 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;