X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fcompress.c;h=3a936347df6de044ca48d68a2ef10ac04e740d90;hp=c91eb5020948a36d20a7c19aa067d1c012b8ec50;hb=60523d25f34692d6f3a7c8bbda88eead17f23b12;hpb=1530b6dab02a9e1e5faf81529ab502aee68d8cd2 diff --git a/src/compress.c b/src/compress.c index c91eb502..3a936347 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,128 +23,148 @@ * 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/endianness.h" +#include "wimlib/compiler.h" +#include "wimlib/compress.h" +#include "wimlib/util.h" + #include #include -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; - ostream->next_bit_output = ostream->output; - ostream->output += 2; - ostream->num_bytes_remaining -= 2; -} - /* 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) +void +bitstream_put_bits(struct output_bitstream *ostream, u32 bits, + unsigned num_bits) { - unsigned rem_bits; + bits &= (1U << num_bits) - 1; + while (num_bits > ostream->free_bits) { + /* Buffer variable does not have space for the new bits. It + * needs to be flushed as a 16-bit integer. Bits in the second + * byte logically precede those in the first byte + * (little-endian), but within each byte the bits are ordered + * from high to low. This is true for both XPRESS and LZX + * compression. */ + + /* There must be at least 2 bytes of space remaining. */ + if (unlikely(ostream->bytes_remaining < 2)) { + ostream->overrun = true; + return; + } - wimlib_assert(num_bits <= 16); - if (num_bits <= ostream->free_bits) { - ostream->bitbuf = (ostream->bitbuf << num_bits) | bits; - ostream->free_bits -= num_bits; - } else { + /* Fill the buffer with as many bits that fit. */ + unsigned fill_bits = ostream->free_bits; + + ostream->bitbuf <<= fill_bits; + ostream->bitbuf |= bits >> (num_bits - fill_bits); - if (ostream->num_bytes_remaining + (ostream->output - - ostream->bit_output) < 2) - return 1; - - /* It is tricky to output the bits correctly. The correct way - * is to output little-endian 2-byte words, such that the bits - * in the SECOND byte logically precede those in the FIRST byte. - * While the byte order is little-endian, the bit order is - * big-endian; the first bit in a byte is the high-order one. - * Any multi-bit numbers are in bit-big-endian form, so the - * low-order bit of a multi-bit number is the LAST bit to be - * output. */ - rem_bits = num_bits - ostream->free_bits; - ostream->bitbuf <<= ostream->free_bits; - ostream->bitbuf |= bits >> rem_bits; - flush_bits(ostream); - ostream->free_bits = 16 - rem_bits; - ostream->bitbuf = bits; + *(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; + ostream->bytes_remaining -= 2; + ostream->free_bits = 16; + num_bits -= fill_bits; + bits &= (1U << num_bits) - 1; } - return 0; + + /* Buffer variable has space for the new bits. */ + ostream->bitbuf = (ostream->bitbuf << num_bits) | bits; + ostream->free_bits -= num_bits; } -/* Flushes any remaining bits in the output buffer to the output byte stream. */ -int flush_output_bitstream(struct output_bitstream *ostream) +void +bitstream_put_byte(struct output_bitstream *ostream, u8 n) { - if (ostream->num_bytes_remaining + (ostream->output - - ostream->bit_output) < 2) - return 1; - if (ostream->free_bits != 16) { - ostream->bitbuf <<= ostream->free_bits; - flush_bits(ostream); + if (unlikely(ostream->bytes_remaining < 1)) { + ostream->overrun = true; + return; } - return 0; + *ostream->output++ = n; + ostream->bytes_remaining--; +} + +/* Flushes any remaining bits to the output bitstream. + * + * Returns -1 if the stream has overrun; otherwise returns the total number of + * bytes in the output. */ +input_idx_t +flush_output_bitstream(struct output_bitstream *ostream) +{ + if (unlikely(ostream->overrun)) + return ~(input_idx_t)0; + + *(le16*)ostream->bit_output = + cpu_to_le16((u16)((u32)ostream->bitbuf << ostream->free_bits)); + *(le16*)ostream->next_bit_output = + cpu_to_le16(0); + + return ostream->output - ostream->output_start; } /* 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->num_bytes_remaining = num_bytes - 4; + ostream->output_start = data; + ostream->bit_output = data; + ostream->next_bit_output = data + 2; + ostream->output = data + 4; + ostream->bytes_remaining = num_bytes; + ostream->overrun = false; } -/* Intermediate (non-leaf) node in a Huffman tree. */ -typedef struct HuffmanNode { - u32 freq; +typedef struct { + input_idx_t 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; - - if (freq_diff == 0) - return (int)leaf1->sym - (int)leaf2->sym; + if (leaf1->freq > leaf2->freq) + return 1; + else if (leaf1->freq < leaf2->freq) + return -1; else - return freq_diff; + return (int)leaf1->sym - (int)leaf2->sym; } -/* 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,17 +174,21 @@ 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; } } @@ -224,14 +248,17 @@ 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 freq_t freq_tab[], u8 lens[], - u16 codewords[]) +void +make_canonical_huffman_code(unsigned num_syms, + unsigned max_codeword_len, + const input_idx_t freq_tab[restrict], + u8 lens[restrict], + u16 codewords[restrict]) { /* 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 * are actually used, though. */ - wimlib_assert(num_syms >= 2); + wimlib_assert(num_syms >= 2 && num_syms < INVALID_SYMBOL); /* Initialize the lengths and codewords to 0 */ memset(lens, 0, num_syms * sizeof(lens[0])); @@ -251,7 +278,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) { @@ -313,21 +340,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. */ @@ -336,7 +363,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]; @@ -360,17 +387,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; @@ -378,20 +405,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. @@ -411,15 +438,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;