X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fcompress_common.c;h=8b85d9d55d84703ebfa12a99c4240494937bcc29;hp=959e1deb2d704b359acba3cdb4a8d5b1b04d3522;hb=873a86a1a5097f2a161494341d8d962453a30465;hpb=55f1b41f8c2e4b53fbdd1f601389abc49795e4d4 diff --git a/src/compress_common.c b/src/compress_common.c index 959e1deb..8b85d9d5 100644 --- a/src/compress_common.c +++ b/src/compress_common.c @@ -2,128 +2,22 @@ * compress_common.c * * Code for compression shared among multiple compression formats. - */ - -/* - * Copyright (C) 2012, 2013, 2014 Eric Biggers - * - * This file is part of wimlib, a library for working with WIM files. - * - * wimlib is free software; you can redistribute it and/or modify it under the - * terms of the GNU General Public License as published by the Free - * Software Foundation; either version 3 of the License, or (at your option) - * any later version. * - * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY - * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR - * A PARTICULAR PURPOSE. See the GNU General Public License for more - * details. + * Author: Eric Biggers + * Year: 2012 - 2014 * - * You should have received a copy of the GNU General Public License - * along with wimlib; if not, see http://www.gnu.org/licenses/. + * The author dedicates this file to the public domain. + * You can do whatever you want with this file. */ #ifdef HAVE_CONFIG_H # include "config.h" #endif -#include "wimlib/assert.h" -#include "wimlib/endianness.h" -#include "wimlib/compiler.h" -#include "wimlib/compress_common.h" -#include "wimlib/util.h" - #include -/* Writes @num_bits bits, given by the @num_bits least significant bits of - * @bits, to the output @ostream. */ -void -bitstream_put_bits(struct output_bitstream *ostream, u32 bits, - unsigned num_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; - } - - /* 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); - - *(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; - } - - /* Buffer variable has space for the new bits. */ - ostream->bitbuf = (ostream->bitbuf << num_bits) | bits; - ostream->free_bits -= num_bits; -} - -void -bitstream_put_byte(struct output_bitstream *ostream, u8 n) -{ - if (unlikely(ostream->bytes_remaining < 1)) { - ostream->overrun = true; - return; - } - *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) -{ - wimlib_assert(num_bytes >= 4); - - ostream->bitbuf = 0; - ostream->free_bits = 16; - ostream->output_start = data; - ostream->bit_output = data; - ostream->next_bit_output = data + 2; - ostream->output = data + 4; - ostream->bytes_remaining = num_bytes - 4; - ostream->overrun = false; -} +#include "wimlib/compress_common.h" +#include "wimlib/util.h" /* Given the binary tree node A[subtree_idx] whose children already * satisfy the maxheap property, swap the node with its greater child @@ -231,7 +125,7 @@ sort_symbols(unsigned num_syms, const u32 freqs[restrict], * Tests were done with building the codes for LZX. Results may * vary for different compression algorithms...! */ - num_counters = (DIV_ROUND_UP(num_syms, 4) + 3) & ~3; + num_counters = ALIGN(DIV_ROUND_UP(num_syms, 4), 4); unsigned counters[num_counters]; @@ -552,8 +446,8 @@ gen_codewords(u32 A[restrict], u8 lens[restrict], * approximately (with the algorithm used here) the minimum weighted path * length from the root, given this constraint. * - * A canonical Huffman code satisfies the properties that a codeword - * never lexicographically precedes a shorter codeword, and the + * A canonical Huffman code satisfies the properties that a longer + * codeword never lexicographically precedes a shorter codeword, and the * lexicographic ordering of codewords of the same length is the same as * the lexicographic ordering of the corresponding symbols. A canonical * Huffman code, or more generally a canonical prefix code, can be @@ -686,12 +580,6 @@ make_canonical_huffman_code(unsigned num_syms, unsigned max_codeword_len, u32 *A = codewords; unsigned num_used_syms; - /* Assumptions */ - wimlib_assert2(num_syms >= 2); - wimlib_assert2(num_syms <= (1 << NUM_SYMBOL_BITS)); - wimlib_assert2(max_codeword_len > 0); - wimlib_assert2(max_codeword_len <= 32); - /* We begin by sorting the symbols primarily by frequency and * secondarily by symbol value. As an optimization, the array * used for this purpose ('A') shares storage with the space in