wimlib.net Git - wimlib/blob - src/lzx.h

   1 /*
   2  * lzx.h
   3  *
   4  * Copyright (C) 2012 Eric Biggers
   5  *
   6  * wimlib - Library for working with WIM files
   7  *
   8  * This library is free software; you can redistribute it and/or modify it under
   9  * the terms of the GNU Lesser General Public License as published by the Free
  10  * Software Foundation; either version 2.1 of the License, or (at your option) any
  11  * later version.
  12  *
  13  * This library is distributed in the hope that it will be useful, but WITHOUT ANY
  14  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
  15  * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public License along
  18  * with this library; if not, write to the Free Software Foundation, Inc., 59
  19  * Temple Place, Suite 330, Boston, MA 02111-1307 USA
  20  */
  21
  22 #ifndef _WIMLIB_LZX_H
  23 #define _WIMLIB_LZX_H
  24
  25 #include "util.h"
  26
  27 //#define ENABLE_LZX_DEBUG
  28 #ifdef ENABLE_LZX_DEBUG
  29 #       define LZX_DEBUG DEBUG
  30 #else
  31 #       define LZX_DEBUG(format, ...)
  32 #endif
  33
  34
  35 /* Constants, some defined by the LZX specification: */
  36
  37 /* The smallest and largest allowed match lengths. */
  38 #define LZX_MIN_MATCH                2
  39 #define LZX_MAX_MATCH                257
  40
  41 /* Number of values an uncompressed literal byte can represent. */
  42 #define LZX_NUM_CHARS                256
  43
  44 /* Each LZX block begins with 3 bits that determines the block type: */
  45 #define LZX_BLOCKTYPE_VERBATIM       1
  46 #define LZX_BLOCKTYPE_ALIGNED        2
  47 #define LZX_BLOCKTYPE_UNCOMPRESSED   3
  48 /* values 0, and 4 through 7, are invalid. */
  49
  50
  51 #define LZX_NUM_PRIMARY_LENS         7  /* this one missing from spec! */
  52
  53 /* Only valid for 32768 block size! */
  54 #define LZX_NUM_POSITION_SLOTS       30
  55
  56 /* Read the LZX specification for information about the Huffman trees used in
  57  * the LZX compression format.  Basically there are 4 of them: The main tree,
  58  * the length tree, the pre tree, and the aligned tree.  The main tree and
  59  * length tree are given at the beginning of VERBATIM and ALIGNED blocks as a
  60  * list of *_NUM_SYMBOLS code length values.  They are read using the
  61  * read_code_lens() function and built using the make_decode_table() function.
  62  * The decode table is not a real tree but rather a table that we can index by
  63  * some number of bits (*_TABLEBITS) of the input to quickly look up the symbol
  64  * corresponding to a Huffman code.
  65  *
  66  * The ALIGNED tree is only present on ALIGNED blocks.
  67  *
  68  * A PRETREE is used to encode the code lengths for the main tree and the length
  69  * tree.  There is a separate pretree for each half of the main tree.  */
  70
  71 #define LZX_MAINTREE_NUM_SYMBOLS         (LZX_NUM_CHARS + \
  72                                         (LZX_NUM_POSITION_SLOTS << 3))
  73 #define LZX_MAINTREE_TABLEBITS          12
  74
  75 #define LZX_LENTREE_NUM_SYMBOLS         249
  76 #define LZX_LENTREE_TABLEBITS           12
  77
  78 #define LZX_PRETREE_NUM_SYMBOLS         20
  79 #define LZX_PRETREE_TABLEBITS           6
  80 #define LZX_PRETREE_ELEMENT_SIZE        4
  81
  82
  83 #define LZX_ALIGNEDTREE_NUM_SYMBOLS     8
  84 #define LZX_ALIGNEDTREE_TABLEBITS       7
  85 #define LZX_ALIGNEDTREE_ELEMENT_SIZE    3
  86
  87 /* Maximum allowed length of a Huffman code. */
  88 #define LZX_MAX_CODEWORD_LEN            16
  89
  90 /* For the LZX-compressed blocks in WIM files, this value is always used as the
  91  * filesize parameter for the call instruction (0xe8 byte) preprocessing, even
  92  * though the blocks themselves are not this size, and the size of the actual
  93  * file resource in the WIM file is very likely to be something entirely
  94  * different as well.  */
  95 #define LZX_MAGIC_FILESIZE           12000000
  96
  97 extern const u8 lzx_extra_bits[51];
  98 extern const u32 lzx_position_base[51];
  99
 100 /* Least-recently used queue for match offsets. */
 101 struct lru_queue {
 102         int R0;
 103         int R1;
 104         int R2;
 105 };
 106
 107 extern int lzx_decompress(const void *compressed_data, uint compressed_len,
 108                           void *uncompressed_data, uint uncompressed_len);
 109
 110 extern int lzx_compress(const void *uncompressed_data, uint uncompressed_len,
 111                         void *compressed_data, uint *compressed_len_ret);
 112
 113 #endif /* _WIMLIB_LZX_H */