wimboot/wimboot-2.7.3/src/lzx.h

   1 #ifndef _LZX_H
   2 #define _LZX_H
   3
   4 /*
   5  * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License as
   9  * published by the Free Software Foundation; either version 2 of the
  10  * License, or (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20  * 02110-1301, USA.
  21  */
  22
  23 /**
  24  * @file
  25  *
  26  * LZX decompression
  27  *
  28  */
  29
  30 #include <stdint.h>
  31 #include "huffman.h"
  32
  33 /** Number of aligned offset codes */
  34 #define LZX_ALIGNOFFSET_CODES 8
  35
  36 /** Aligned offset code length (in bits) */
  37 #define LZX_ALIGNOFFSET_BITS 3
  38
  39 /** Number of pretree codes */
  40 #define LZX_PRETREE_CODES 20
  41
  42 /** Pretree code length (in bits) */
  43 #define LZX_PRETREE_BITS 4
  44
  45 /** Number of literal main codes */
  46 #define LZX_MAIN_LIT_CODES 256
  47
  48 /** Number of position slots */
  49 #define LZX_POSITION_SLOTS 30
  50
  51 /** Number of main codes */
  52 #define LZX_MAIN_CODES ( LZX_MAIN_LIT_CODES + ( 8 * LZX_POSITION_SLOTS ) )
  53
  54 /** Number of length codes */
  55 #define LZX_LENGTH_CODES 249
  56
  57 /** Block type length (in bits) */
  58 #define LZX_BLOCK_TYPE_BITS 3
  59
  60 /** Default block length */
  61 #define LZX_DEFAULT_BLOCK_LEN 32768
  62
  63 /** Number of repeated offsets */
  64 #define LZX_REPEATED_OFFSETS 3
  65
  66 /** Don't ask */
  67 #define LZX_WIM_MAGIC_FILESIZE 12000000
  68
  69 /** Block types */
  70 enum lzx_block_type {
  71         /** Verbatim block */
  72         LZX_BLOCK_VERBATIM = 1,
  73         /** Aligned offset block */
  74         LZX_BLOCK_ALIGNOFFSET = 2,
  75         /** Uncompressed block */
  76         LZX_BLOCK_UNCOMPRESSED = 3,
  77 };
  78
  79 /** An LZX input stream */
  80 struct lzx_input_stream {
  81         /** Data */
  82         const uint8_t *data;
  83         /** Length */
  84         size_t len;
  85         /** Offset within stream */
  86         size_t offset;
  87 };
  88
  89 /** An LZX output stream */
  90 struct lzx_output_stream {
  91         /** Data, or NULL */
  92         uint8_t *data;
  93         /** Offset within stream */
  94         size_t offset;
  95         /** End of current block within stream */
  96         size_t threshold;
  97 };
  98
  99 /** LZX decompressor */
 100 struct lzx {
 101         /** Input stream */
 102         struct lzx_input_stream input;
 103         /** Output stream */
 104         struct lzx_output_stream output;
 105         /** Accumulator */
 106         uint32_t accumulator;
 107         /** Number of bits in accumulator */
 108         unsigned int bits;
 109         /** Block type */
 110         enum lzx_block_type block_type;
 111         /** Repeated offsets */
 112         unsigned int repeated_offset[LZX_REPEATED_OFFSETS];
 113
 114         /** Aligned offset Huffman alphabet */
 115         struct huffman_alphabet alignoffset;
 116         /** Aligned offset raw symbols
 117          *
 118          * Must immediately follow the aligned offset Huffman
 119          * alphabet.
 120          */
 121         huffman_raw_symbol_t alignoffset_raw[LZX_ALIGNOFFSET_CODES];
 122         /** Aligned offset code lengths */
 123         uint8_t alignoffset_lengths[LZX_ALIGNOFFSET_CODES];
 124
 125         /** Pretree Huffman alphabet */
 126         struct huffman_alphabet pretree;
 127         /** Pretree raw symbols
 128          *
 129          * Must immediately follow the pretree Huffman alphabet.
 130          */
 131         huffman_raw_symbol_t pretree_raw[LZX_PRETREE_CODES];
 132         /** Preetree code lengths */
 133         uint8_t pretree_lengths[LZX_PRETREE_CODES];
 134
 135         /** Main Huffman alphabet */
 136         struct huffman_alphabet main;
 137         /** Main raw symbols
 138          *
 139          * Must immediately follow the main Huffman alphabet.
 140          */
 141         huffman_raw_symbol_t main_raw[LZX_MAIN_CODES];
 142         /** Main code lengths */
 143         struct {
 144                 /** Literals */
 145                 uint8_t literals[LZX_MAIN_LIT_CODES];
 146                 /** Remaining symbols */
 147                 uint8_t remainder[ LZX_MAIN_CODES - LZX_MAIN_LIT_CODES ];
 148         } __attribute__ (( packed )) main_lengths;
 149
 150         /** Length Huffman alphabet */
 151         struct huffman_alphabet length;
 152         /** Length raw symbols
 153          *
 154          * Must immediately follow the length Huffman alphabet.
 155          */
 156         huffman_raw_symbol_t length_raw[LZX_LENGTH_CODES];
 157         /** Length code lengths */
 158         uint8_t length_lengths[LZX_LENGTH_CODES];
 159 };
 160
 161 /**
 162  * Calculate number of footer bits for a given position slot
 163  *
 164  * @v position_slot     Position slot
 165  * @ret footer_bits     Number of footer bits
 166  */
 167 static inline unsigned int lzx_footer_bits ( unsigned int position_slot ) {
 168
 169         if ( position_slot < 2 ) {
 170                 return 0;
 171         } else if ( position_slot < 38 ) {
 172                 return ( ( position_slot / 2 ) - 1 );
 173         } else {
 174                 return 17;
 175         }
 176 }
 177
 178 extern ssize_t lzx_decompress ( const void *data, size_t len, void *buf );
 179
 180 #endif /* _LZX_H */