X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Fcompress_common.c;h=e2ad298e3f33d8ec88536df26c3c9e52d48a0428;hp=e8ed00d3c3096e810b46d67ef4617d5196618058;hb=f8223526610a6ed9410ed6ce2e704ef15ab8cade;hpb=394751ae13025edab605cd61c8e32819e3fb33a1 diff --git a/src/compress_common.c b/src/compress_common.c index e8ed00d3..e2ad298e 100644 --- a/src/compress_common.c +++ b/src/compress_common.c @@ -2,129 +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 #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 @@ -553,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 @@ -687,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