X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fcompress.c;h=b25938f15d5dacda8fe590163eefe9483a5b7bef;hp=c1a52ff63df7c04527f0d74e8c34832fd6929ed3;hb=5123a1ae75747ddc4984bfe104c75e3974cede35;hpb=056bca7aee6a336b5418bf2d8ae3dd5a7ca432a2 diff --git a/src/compress.c b/src/compress.c index c1a52ff6..b25938f1 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. * @@ -23,13 +23,22 @@ * along with wimlib; if not, see http://www.gnu.org/licenses/. */ -#include "compress.h" +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + + +#include "wimlib/assert.h" +#include "wimlib/compress.h" +#include "wimlib/util.h" + #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); + *(le16*)ostream->bit_output = cpu_to_le16(ostream->bitbuf); ostream->bit_output = ostream->next_bit_output; ostream->next_bit_output = ostream->output; ostream->output += 2; @@ -38,8 +47,9 @@ 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, - unsigned num_bits) +int +bitstream_put_bits(struct output_bitstream *ostream, output_bitbuf_t bits, + unsigned num_bits) { unsigned rem_bits; @@ -73,7 +83,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,49 +98,43 @@ 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, - unsigned num_bytes) +void +init_output_bitstream(struct output_bitstream *ostream, + void *data, unsigned num_bytes) { wimlib_assert(num_bytes >= 4); ostream->bitbuf = 0; ostream->free_bits = 16; - ostream->bit_output = (u8*)data; - ostream->next_bit_output = (u8*)data + 2; - ostream->output = (u8*)data + 4; + ostream->bit_output = data; + ostream->next_bit_output = data + 2; + ostream->output = data + 4; ostream->num_bytes_remaining = num_bytes - 4; } -/* Intermediate (non-leaf) node in a Huffman tree. */ -typedef struct HuffmanNode { +typedef struct { u32 freq; u16 sym; union { u16 path_len; u16 height; }; - struct HuffmanNode *left_child; - struct HuffmanNode *right_child; } HuffmanNode; -/* Leaf node in a Huffman tree. The fields are in the same order as the - * HuffmanNode, so it can be cast to a HuffmanNode. There are no pointers to - * the children in the leaf node. */ -typedef struct { - u32 freq; - u16 sym; - union { - u16 path_len; - u16 height; - }; -} HuffmanLeafNode; +typedef struct HuffmanIntermediateNode { + HuffmanNode node_base; + HuffmanNode *left_child; + HuffmanNode *right_child; +} HuffmanIntermediateNode; + -/* Comparator function for HuffmanLeafNodes. Sorts primarily by symbol +/* Comparator function for HuffmanNodes. 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_nodes_by_freq(const void *_leaf1, const void *_leaf2) { - const HuffmanLeafNode *leaf1 = __leaf1; - const HuffmanLeafNode *leaf2 = __leaf2; + const HuffmanNode *leaf1 = _leaf1; + const HuffmanNode *leaf2 = _leaf2; int freq_diff = (int)leaf1->freq - (int)leaf2->freq; @@ -139,12 +144,13 @@ static int cmp_leaves_by_freq(const void *__leaf1, const void *__leaf2) return freq_diff; } -/* Comparator function for HuffmanLeafNodes. Sorts primarily by code length and +/* Comparator function for HuffmanNodes. 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_nodes_by_code_len(const void *_leaf1, const void *_leaf2) { - const HuffmanLeafNode *leaf1 = __leaf1; - const HuffmanLeafNode *leaf2 = __leaf2; + const HuffmanNode *leaf1 = _leaf1; + const HuffmanNode *leaf2 = _leaf2; int code_len_diff = (int)leaf1->path_len - (int)leaf2->path_len; @@ -154,21 +160,26 @@ static int cmp_leaves_by_code_len(const void *__leaf1, const void *__leaf2) return code_len_diff; } +#define INVALID_SYMBOL 0xffff + /* 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 *base_node, u16 cur_len) { - if (node->sym == (u16)(-1)) { + if (base_node->sym == INVALID_SYMBOL) { /* Intermediate node. */ + HuffmanIntermediateNode *node = (HuffmanIntermediateNode*)base_node; huffman_tree_compute_path_lengths(node->left_child, cur_len + 1); huffman_tree_compute_path_lengths(node->right_child, cur_len + 1); } else { /* Leaf node. */ - node->path_len = cur_len; + base_node->path_len = 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 +234,12 @@ 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(unsigned num_syms, unsigned 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 * restrict freq_tab, + u8 * restrict lens, + u16 * restrict 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 @@ -250,7 +264,7 @@ void make_canonical_huffman_code(unsigned num_syms, unsigned max_codeword_len, /* Initialize the array of leaf nodes with the symbols and their * frequencies. */ - HuffmanLeafNode leaves[num_used_symbols]; + HuffmanNode leaves[num_used_symbols]; unsigned leaf_idx = 0; for (unsigned i = 0; i < num_syms; i++) { if (freq_tab[i] != 0) { @@ -312,21 +326,21 @@ void make_canonical_huffman_code(unsigned num_syms, unsigned max_codeword_len, * format constrains codes to 16 bits or less each. However, it is * still possible for there to be more than 16 intermediate nodes, as * long as no leaf has a depth of more than 16. */ - HuffmanNode inodes[num_used_symbols - 1]; + HuffmanIntermediateNode inodes[num_used_symbols - 1]; /* Pointer to the leaf node of lowest frequency that hasn't already been * added as the child of some intermediate note. */ - HuffmanLeafNode *cur_leaf; + HuffmanNode *cur_leaf; /* Pointer past the end of the array of leaves. */ - HuffmanLeafNode *end_leaf = &leaves[num_used_symbols]; + HuffmanNode *end_leaf = &leaves[num_used_symbols]; /* Pointer to the intermediate node of lowest frequency. */ - HuffmanNode *cur_inode; + HuffmanIntermediateNode *cur_inode; /* Pointer to the next unallocated intermediate node. */ - HuffmanNode *next_inode; + HuffmanIntermediateNode *next_inode; /* Only jump back to here if the maximum length of the codewords allowed * by the LZX format (16 bits) is exceeded. */ @@ -335,7 +349,7 @@ try_building_tree_again: /* Sort the leaves from those that correspond to the least frequent * symbol, to those that correspond to the most frequent symbol. If two * leaves have the same frequency, they are sorted by symbol. */ - qsort(leaves, num_used_symbols, sizeof(leaves[0]), cmp_leaves_by_freq); + qsort(leaves, num_used_symbols, sizeof(leaves[0]), cmp_nodes_by_freq); cur_leaf = &leaves[0]; cur_inode = &inodes[0]; @@ -359,17 +373,17 @@ try_building_tree_again: * remaining leaves or from the intermediate nodes. */ if (cur_leaf != end_leaf && (cur_inode == next_inode || - cur_leaf->freq <= cur_inode->freq)) { - f1 = (HuffmanNode*)cur_leaf++; + cur_leaf->freq <= cur_inode->node_base.freq)) { + f1 = cur_leaf++; } else if (cur_inode != next_inode) { - f1 = cur_inode++; + f1 = (HuffmanNode*)cur_inode++; } if (cur_leaf != end_leaf && (cur_inode == next_inode || - cur_leaf->freq <= cur_inode->freq)) { - f2 = (HuffmanNode*)cur_leaf++; + cur_leaf->freq <= cur_inode->node_base.freq)) { + f2 = cur_leaf++; } else if (cur_inode != next_inode) { - f2 = cur_inode++; + f2 = (HuffmanNode*)cur_inode++; } else { /* All nodes used up! */ break; @@ -377,20 +391,20 @@ try_building_tree_again: /* next_inode becomes the parent of f1 and f2. */ - next_inode->freq = f1->freq + f2->freq; - next_inode->sym = (u16)(-1); /* Invalid symbol. */ - next_inode->left_child = f1; - next_inode->right_child = f2; + next_inode->node_base.freq = f1->freq + f2->freq; + next_inode->node_base.sym = INVALID_SYMBOL; + next_inode->left_child = f1; + next_inode->right_child = f2; /* We need to keep track of the height so that we can detect if * the length of a codeword has execeed max_codeword_len. The * parent node has a height one higher than the maximum height * of its children. */ - next_inode->height = max(f1->height, f2->height) + 1; + next_inode->node_base.height = max(f1->height, f2->height) + 1; /* Check to see if the code length of the leaf farthest away * from next_inode has exceeded the maximum code length. */ - if (next_inode->height > max_codeword_len) { + if (next_inode->node_base.height > max_codeword_len) { /* The code lengths can be made more uniform by making * the frequencies more uniform. Divide all the * frequencies by 2, leaving 1 as the minimum frequency. @@ -410,15 +424,15 @@ try_building_tree_again: /* The Huffman tree is now complete, and its height is no more than * max_codeword_len. */ - HuffmanNode *root = next_inode - 1; - wimlib_assert(root->height <= max_codeword_len); + HuffmanIntermediateNode *root = next_inode - 1; + wimlib_assert(root->node_base.height <= max_codeword_len); /* Compute the path lengths for the leaf nodes. */ - huffman_tree_compute_path_lengths(root, 0); + huffman_tree_compute_path_lengths(&root->node_base, 0); /* Sort the leaf nodes primarily by code length and secondarily by * symbol. */ - qsort(leaves, num_used_symbols, sizeof(leaves[0]), cmp_leaves_by_code_len); + qsort(leaves, num_used_symbols, sizeof(leaves[0]), cmp_nodes_by_code_len); u16 cur_codeword = 0; unsigned cur_codeword_len = 0;