GRUB2/MOD_SRC/grub-2.04/grub-core/ventoy/xpress.c

   1 /*
   2  * Copyright (C) 2012 Michael Brown <mbrown@fensystems.co.uk>.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17  * 02110-1301, USA.
  18  */
  19
  20 /**
  21  * @file
  22  *
  23  * Xpress Compression Algorithm (MS-XCA) decompression
  24  *
  25  */
  26
  27 #include "wimboot.h"
  28 #include "huffman.h"
  29 #include "xpress.h"
  30
  31 #pragma GCC diagnostic ignored "-Wcast-align"
  32
  33 /**
  34  * Decompress XCA-compressed data
  35  *
  36  * @v data              Compressed data
  37  * @v len               Length of compressed data
  38  * @v buf               Decompression buffer, or NULL
  39  * @ret out_len         Length of decompressed data, or negative error
  40  */
  41 ssize_t xca_decompress ( const void *data, size_t len, void *buf ) {
  42         const void *src = data;
  43         const void *end = ( uint8_t * ) src + len;
  44         uint8_t *out = buf;
  45         size_t out_len = 0;
  46         size_t out_len_threshold = 0;
  47         const struct xca_huf_len *lengths;
  48         struct xca xca;
  49         uint32_t accum = 0;
  50         int extra_bits = 0;
  51         unsigned int huf;
  52         struct huffman_symbols *sym;
  53         unsigned int raw;
  54         unsigned int match_len;
  55         unsigned int match_offset_bits;
  56         unsigned int match_offset;
  57         const uint8_t *copy;
  58         int rc;
  59
  60         /* Process data stream */
  61         while ( src < end ) {
  62
  63                 /* (Re)initialise decompressor if applicable */
  64                 if ( out_len >= out_len_threshold ) {
  65
  66                         /* Construct symbol lengths */
  67                         lengths = src;
  68                         src = ( uint8_t * ) src + sizeof ( *lengths );
  69                         if ( src > end ) {
  70                                 DBG ( "XCA too short to hold Huffman lengths table.\n");
  71                                 return -1;
  72                         }
  73                         for ( raw = 0 ; raw < XCA_CODES ; raw++ )
  74                                 xca.lengths[raw] = xca_huf_len ( lengths, raw );
  75
  76                         /* Construct Huffman alphabet */
  77                         if ( ( rc = huffman_alphabet ( &xca.alphabet,
  78                                                        xca.lengths,
  79                                                        XCA_CODES ) ) != 0 )
  80                                 return rc;
  81
  82                         /* Initialise state */
  83                         accum = XCA_GET16 ( src );
  84                         accum <<= 16;
  85                         accum |= XCA_GET16 ( src );
  86                         extra_bits = 16;
  87
  88                         /* Determine next threshold */
  89                         out_len_threshold = ( out_len + XCA_BLOCK_SIZE );
  90                 }
  91
  92                 /* Determine symbol */
  93                 huf = ( accum >> ( 32 - HUFFMAN_BITS ) );
  94                 sym = huffman_sym ( &xca.alphabet, huf );
  95                 raw = huffman_raw ( sym, huf );
  96                 accum <<= huffman_len ( sym );
  97                 extra_bits -= huffman_len ( sym );
  98                 if ( extra_bits < 0 ) {
  99                         accum |= ( XCA_GET16 ( src ) << ( -extra_bits ) );
 100                         extra_bits += 16;
 101                 }
 102
 103                 /* Process symbol */
 104                 if ( raw < XCA_END_MARKER ) {
 105
 106                         /* Literal symbol - add to output stream */
 107                         if ( buf )
 108                                 *(out++) = raw;
 109                         out_len++;
 110
 111                 } else if ( ( raw == XCA_END_MARKER ) &&
 112                             ( (uint8_t *) src >= ( ( uint8_t * ) end - 1 ) ) ) {
 113
 114                         /* End marker symbol */
 115                         return out_len;
 116
 117                 } else {
 118
 119                         /* LZ77 match symbol */
 120                         raw -= XCA_END_MARKER;
 121                         match_offset_bits = ( raw >> 4 );
 122                         match_len = ( raw & 0x0f );
 123                         if ( match_len == 0x0f ) {
 124                                 match_len = XCA_GET8 ( src );
 125                                 if ( match_len == 0xff ) {
 126                                         match_len = XCA_GET16 ( src );
 127                                 } else {
 128                                         match_len += 0x0f;
 129                                 }
 130                         }
 131                         match_len += 3;
 132                         if ( match_offset_bits ) {
 133                                 match_offset =
 134                                         ( ( accum >> ( 32 - match_offset_bits ))
 135                                           + ( 1 << match_offset_bits ) );
 136                         } else {
 137                                 match_offset = 1;
 138                         }
 139                         accum <<= match_offset_bits;
 140                         extra_bits -= match_offset_bits;
 141                         if ( extra_bits < 0 ) {
 142                                 accum |= ( XCA_GET16 ( src ) << (-extra_bits) );
 143                                 extra_bits += 16;
 144                         }
 145
 146                         /* Copy data */
 147                         out_len += match_len;
 148                         if ( buf ) {
 149                                 copy = ( out - match_offset );
 150                                 while ( match_len-- )
 151                                         *(out++) = *(copy++);
 152                         }
 153                 }
 154         }
 155
 156         return out_len;
 157 }