Get rid of input_idx_t

[wimlib] / include / wimlib / decompress_common.h

diff --git a/include/wimlib/decompress_common.h b/include/wimlib/decompress_common.h
index 3b20f4e09e74b744be139817df513d5b2f6c9372..fab3c3e009413c4ef9ed4b9f0a4a6a3a672cc1a9 100644 (file)
--- a/include/wimlib/decompress_common.h
+++ b/include/wimlib/decompress_common.h
@@ -2,6 +2,9 @@
  * decompress_common.h
  *
  * Header for decompression code shared by multiple compression formats.
  * decompress_common.h
  *
  * Header for decompression code shared by multiple compression formats.

+ *
+ * The author dedicates this file to the public domain.
+ * You can do whatever you want with this file.

  */
 
 #ifndef _WIMLIB_DECOMPRESS_COMMON_H
  */
 
 #ifndef _WIMLIB_DECOMPRESS_COMMON_H


@@ -9,15 +12,9 @@
 
 #include "wimlib/assert.h"
 #include "wimlib/compiler.h"
 
 #include "wimlib/assert.h"
 #include "wimlib/compiler.h"

-#include "wimlib/error.h"

 #include "wimlib/endianness.h"
 #include "wimlib/types.h"
 
 #include "wimlib/endianness.h"
 #include "wimlib/types.h"
 

-#ifndef INPUT_IDX_T_DEFINED
-#define INPUT_IDX_T_DEFINED
-typedef u32 input_idx_t;
-#endif
-

 /* Structure to encapsulate a block of in-memory data that is being interpreted
  * as a stream of bits.
  *
 /* Structure to encapsulate a block of in-memory data that is being interpreted
  * as a stream of bits.
  *


@@ -37,13 +34,13 @@ struct input_bitstream {
        const u8 *data;
 
        /* Number of bytes of data that are left.  */
        const u8 *data;
 
        /* Number of bytes of data that are left.  */

-       input_idx_t data_bytes_left;
+       u32 data_bytes_left;

 };
 
 /* Initializes a bitstream to receive its input from @data. */
 static inline void
 init_input_bitstream(struct input_bitstream *istream,
 };
 
 /* Initializes a bitstream to receive its input from @data. */
 static inline void
 init_input_bitstream(struct input_bitstream *istream,

-                    const void *data, input_idx_t num_data_bytes)
+                    const void *data, u32 num_data_bytes)

 {
        istream->bitbuf          = 0;
        istream->bitsleft        = 0;
 {
        istream->bitbuf          = 0;
        istream->bitsleft        = 0;


@@ -129,48 +126,127 @@ bitstream_read_byte(struct input_bitstream *istream)
        return *istream->data++;
 }
 
        return *istream->data++;
 }
 

+
+/* Needed alignment of decode_table parameter to make_huffman_decode_table().
+ *
+ * Reason: We may fill the entries with SSE instructions without worrying
+ * about dealing with the unaligned case.  */
+#define DECODE_TABLE_ALIGNMENT 16
+
+/* Maximum supported symbol count for make_huffman_decode_table().
+ *
+ * Reason: In direct mapping entries, we store the symbol in 11 bits.  */
+#define DECODE_TABLE_MAX_SYMBOLS 2048
+
+/* Maximum supported table bits for make_huffman_decode_table().
+ *
+ * Reason: In internal binary tree nodes, offsets are encoded in 14 bits.
+ * But the real limit is 13, because we allocate entries past the end of
+ * the direct lookup part of the table for binary tree nodes.  (Note: if
+ * needed this limit could be removed by encoding the offsets relative to
+ * &decode_table[1 << table_bits].)  */
+#define DECODE_TABLE_MAX_TABLE_BITS 13
+
+/* Maximum supported codeword length for make_huffman_decode_table().
+ *
+ * Reason: In direct mapping entries, we encode the codeword length in 5
+ * bits, and the top 2 bits can't both be set because that has special
+ * meaning.  */
+#define DECODE_TABLE_MAX_CODEWORD_LEN 23
+

 /* Reads and returns the next Huffman-encoded symbol from a bitstream.  If the
  * input data is exhausted, the Huffman symbol is decoded as if the missing bits
 /* Reads and returns the next Huffman-encoded symbol from a bitstream.  If the
  * input data is exhausted, the Huffman symbol is decoded as if the missing bits

- * are all zeroes.  */
+ * are all zeroes.
+ *
+ * XXX: This is mostly duplicated in lzms_huffman_decode_symbol() in
+ * lzms-decompress.c.  */

 static inline u16
 static inline u16

-read_huffsym(struct input_bitstream * restrict istream,
-            const u16 decode_table[restrict],
-            const u8 lens[restrict],
-            unsigned num_syms,
-            unsigned table_bits,
-            unsigned max_codeword_len)
+read_huffsym(struct input_bitstream *istream, const u16 decode_table[],
+            unsigned table_bits, unsigned max_codeword_len)

 {
 {

+       u16 entry;
+       u16 key_bits;

 
        bitstream_ensure_bits(istream, max_codeword_len);
 
 
        bitstream_ensure_bits(istream, max_codeword_len);
 

-       /* Use the next table_bits of the input as an index into the
-        * decode_table.  */
-       u16 key_bits = bitstream_peek_bits(istream, table_bits);
-
-       u16 sym = decode_table[key_bits];
-
-       if (likely(sym < num_syms)) {
-               /* Fast case: The decode table directly provided the symbol.  */
-               bitstream_remove_bits(istream, lens[sym]);
+       /* Index the decode table by the next table_bits bits of the input.  */
+       key_bits = bitstream_peek_bits(istream, table_bits);
+       entry = decode_table[key_bits];
+       if (likely(entry < 0xC000)) {
+               /* Fast case: The decode table directly provided the
+                * symbol and codeword length.  The low 11 bits are the
+                * symbol, and the high 5 bits are the codeword length.  */
+               bitstream_remove_bits(istream, entry >> 11);
+               return entry & 0x7FF;

        } else {
        } else {

-               /* Slow case: The symbol took too many bits to include directly
-                * in the decode table, so search for it in a binary tree at the
-                * end of the decode table.  */
+               /* Slow case: The codeword for the symbol is longer than
+                * table_bits, so the symbol does not have an entry
+                * directly in the first (1 << table_bits) entries of the
+                * decode table.  Traverse the appropriate binary tree
+                * bit-by-bit to decode the symbol.  */

                bitstream_remove_bits(istream, table_bits);
                do {
                bitstream_remove_bits(istream, table_bits);
                do {

-                       key_bits = sym + bitstream_pop_bits(istream, 1);
-               } while ((sym = decode_table[key_bits]) >= num_syms);
+                       key_bits = (entry & 0x3FFF) + bitstream_pop_bits(istream, 1);
+               } while ((entry = decode_table[key_bits]) >= 0xC000);
+               return entry;

        }
        }

-       return sym;

 }
 
 extern int
 make_huffman_decode_table(u16 decode_table[], unsigned num_syms,
 }
 
 extern int
 make_huffman_decode_table(u16 decode_table[], unsigned num_syms,

-                         unsigned num_bits, const u8 lengths[],
+                         unsigned num_bits, const u8 lens[],

                          unsigned max_codeword_len);
 
                          unsigned max_codeword_len);
 

-/* Minimum alignment for the decode_table parameter to
- * make_huffman_decode_table().  */
-#define DECODE_TABLE_ALIGNMENT 16

 
 

-#endif /* _WIMLIB_DECOMPRESS_H */
+/*
+ * Copy a LZ77 match at (dst - offset) to dst.
+ *
+ * The length and offset must be already validated --- that is, (dst - offset)
+ * can't underrun the output buffer, and (dst + length) can't overrun the output
+ * buffer.  Also, the length cannot be 0.
+ *
+ * @winend points to the byte past the end of the output buffer.
+ * This function won't write any data beyond this position.
+ */
+static inline void
+lz_copy(u8 *dst, unsigned length, unsigned offset, const u8 *winend)
+{
+       const u8 *src = dst - offset;
+#if defined(__x86_64__) || defined(__i386__)
+       /* Copy one 'unsigned long' at a time.  On i386 and x86_64 this is
+        * faster than copying one byte at a time, unless the data is
+        * near-random and all the matches have very short lengths.  Note that
+        * since this requires unaligned memory accesses, it won't necessarily
+        * be faster on every architecture.
+        *
+        * Also note that we might copy more than the length of the match.  For
+        * example, if an 'unsigned long' is 8 bytes and the match is of length
+        * 5, then we'll simply copy 8 bytes.  This is okay as long as we don't
+        * write beyond the end of the output buffer, hence the check for
+        * (winend - (dst + length) >= sizeof(unsigned long) - 1).  */
+       if (offset >= sizeof(unsigned long) &&
+                       winend - (dst + length) >= sizeof(unsigned long) - 1)
+       {
+               /* Access memory through a packed struct.  This tricks the
+                * compiler into allowing unaligned memory accesses.  */
+               struct ulong_wrapper {
+                       unsigned long v;
+               } _packed_attribute;
+
+               const u8 *end = dst + length;
+               do {
+                       unsigned long v = ((struct ulong_wrapper *)src)->v;
+                       ((struct ulong_wrapper *)dst)->v = v;
+                       dst += sizeof(unsigned long);
+                       src += sizeof(unsigned long);
+               } while (dst < end);
+
+               return;
+       }
+#endif
+       do {
+               *dst++ = *src++;
+       } while (--length);
+}
+
+#endif /* _WIMLIB_DECOMPRESS_COMMON_H */