GRUB2/MOD_SRC/grub-2.04/grub-core/ventoy/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 "huffman.h"
  31
  32 /** Number of aligned offset codes */
  33 #define LZX_ALIGNOFFSET_CODES 8
  34
  35 /** Aligned offset code length (in bits) */
  36 #define LZX_ALIGNOFFSET_BITS 3
  37
  38 /** Number of pretree codes */
  39 #define LZX_PRETREE_CODES 20
  40
  41 /** Pretree code length (in bits) */
  42 #define LZX_PRETREE_BITS 4
  43
  44 /** Number of literal main codes */
  45 #define LZX_MAIN_LIT_CODES 256
  46
  47 /** Number of position slots */
  48 #define LZX_POSITION_SLOTS 30
  49
  50 /** Number of main codes */
  51 #define LZX_MAIN_CODES ( LZX_MAIN_LIT_CODES + ( 8 * LZX_POSITION_SLOTS ) )
  52
  53 /** Number of length codes */
  54 #define LZX_LENGTH_CODES 249
  55
  56 /** Block type length (in bits) */
  57 #define LZX_BLOCK_TYPE_BITS 3
  58
  59 /** Default block length */
  60 #define LZX_DEFAULT_BLOCK_LEN 32768
  61
  62 /** Number of repeated offsets */
  63 #define LZX_REPEATED_OFFSETS 3
  64
  65 /** Don't ask */
  66 #define LZX_WIM_MAGIC_FILESIZE 12000000
  67
  68 /** Block types */
  69 enum lzx_block_type {
  70         /** Verbatim block */
  71         LZX_BLOCK_VERBATIM = 1,
  72         /** Aligned offset block */
  73         LZX_BLOCK_ALIGNOFFSET = 2,
  74         /** Uncompressed block */
  75         LZX_BLOCK_UNCOMPRESSED = 3,
  76 };
  77
  78 /** An LZX input stream */
  79 struct lzx_input_stream {
  80         /** Data */
  81         const uint8_t *data;
  82         /** Length */
  83         size_t len;
  84         /** Offset within stream */
  85         size_t offset;
  86 };
  87
  88 /** An LZX output stream */
  89 struct lzx_output_stream {
  90         /** Data, or NULL */
  91         uint8_t *data;
  92         /** Offset within stream */
  93         size_t offset;
  94         /** End of current block within stream */
  95         size_t threshold;
  96 };
  97
  98 /** LZX decompressor */
  99 struct lzx {
 100         /** Input stream */
 101         struct lzx_input_stream input;
 102         /** Output stream */
 103         struct lzx_output_stream output;
 104         /** Accumulator */
 105         uint32_t accumulator;
 106         /** Number of bits in accumulator */
 107         unsigned int bits;
 108         /** Block type */
 109         enum lzx_block_type block_type;
 110         /** Repeated offsets */
 111         unsigned int repeated_offset[LZX_REPEATED_OFFSETS];
 112
 113         /** Aligned offset Huffman alphabet */
 114         struct huffman_alphabet alignoffset;
 115         /** Aligned offset raw symbols
 116          *
 117          * Must immediately follow the aligned offset Huffman
 118          * alphabet.
 119          */
 120         huffman_raw_symbol_t alignoffset_raw[LZX_ALIGNOFFSET_CODES];
 121         /** Aligned offset code lengths */
 122         uint8_t alignoffset_lengths[LZX_ALIGNOFFSET_CODES];
 123
 124         /** Pretree Huffman alphabet */
 125         struct huffman_alphabet pretree;
 126         /** Pretree raw symbols
 127          *
 128          * Must immediately follow the pretree Huffman alphabet.
 129          */
 130         huffman_raw_symbol_t pretree_raw[LZX_PRETREE_CODES];
 131         /** Preetree code lengths */
 132         uint8_t pretree_lengths[LZX_PRETREE_CODES];
 133
 134         /** Main Huffman alphabet */
 135         struct huffman_alphabet main;
 136         /** Main raw symbols
 137          *
 138          * Must immediately follow the main Huffman alphabet.
 139          */
 140         huffman_raw_symbol_t main_raw[LZX_MAIN_CODES];
 141         /** Main code lengths */
 142         struct {
 143                 /** Literals */
 144                 uint8_t literals[LZX_MAIN_LIT_CODES];
 145                 /** Remaining symbols */
 146                 uint8_t remainder[ LZX_MAIN_CODES - LZX_MAIN_LIT_CODES ];
 147         } __attribute__ (( packed )) main_lengths;
 148
 149         /** Length Huffman alphabet */
 150         struct huffman_alphabet length;
 151         /** Length raw symbols
 152          *
 153          * Must immediately follow the length Huffman alphabet.
 154          */
 155         huffman_raw_symbol_t length_raw[LZX_LENGTH_CODES];
 156         /** Length code lengths */
 157         uint8_t length_lengths[LZX_LENGTH_CODES];
 158 };
 159
 160 /**
 161  * Calculate number of footer bits for a given position slot
 162  *
 163  * @v position_slot     Position slot
 164  * @ret footer_bits     Number of footer bits
 165  */
 166 static inline unsigned int lzx_footer_bits ( unsigned int position_slot ) {
 167
 168         if ( position_slot < 2 ) {
 169                 return 0;
 170         } else if ( position_slot < 38 ) {
 171                 return ( ( position_slot / 2 ) - 1 );
 172         } else {
 173                 return 17;
 174         }
 175 }
 176
 177 extern ssize_t lzx_decompress ( const void *data, size_t len, void *buf );
 178
 179 #endif /* _LZX_H */