wimboot/wimboot-2.7.3/src/xca.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 <stdint.h>
  28 #include <stddef.h>
  29 #include <string.h>
  30 #include <stdio.h>
  31 #include "wimboot.h"
  32 #include "huffman.h"
  33 #include "xca.h"
  34
  35 /**
  36  * Decompress XCA-compressed data
  37  *
  38  * @v data              Compressed data
  39  * @v len               Length of compressed data
  40  * @v buf               Decompression buffer, or NULL
  41  * @ret out_len         Length of decompressed data, or negative error
  42  */
  43 ssize_t xca_decompress ( const void *data, size_t len, void *buf ) {
  44         const void *src = data;
  45         const void *end = ( uint8_t * ) src + len;
  46         uint8_t *out = buf;
  47         size_t out_len = 0;
  48         size_t out_len_threshold = 0;
  49         const struct xca_huf_len *lengths;
  50         struct xca xca;
  51         uint32_t accum = 0;
  52         int extra_bits = 0;
  53         unsigned int huf;
  54         struct huffman_symbols *sym;
  55         unsigned int raw;
  56         unsigned int match_len;
  57         unsigned int match_offset_bits;
  58         unsigned int match_offset;
  59         const uint8_t *copy;
  60         int rc;
  61
  62         /* Process data stream */
  63         while ( src < end ) {
  64
  65                 /* (Re)initialise decompressor if applicable */
  66                 if ( out_len >= out_len_threshold ) {
  67
  68                         /* Construct symbol lengths */
  69                         lengths = src;
  70                         src = ( uint8_t * ) src + sizeof ( *lengths );
  71                         if ( src > end ) {
  72                                 DBG ( "XCA too short to hold Huffman lengths table.\n");
  73                                 return -1;
  74                         }
  75                         for ( raw = 0 ; raw < XCA_CODES ; raw++ )
  76                                 xca.lengths[raw] = xca_huf_len ( lengths, raw );
  77
  78                         /* Construct Huffman alphabet */
  79                         if ( ( rc = huffman_alphabet ( &xca.alphabet,
  80                                                        xca.lengths,
  81                                                        XCA_CODES ) ) != 0 )
  82                                 return rc;
  83
  84                         /* Initialise state */
  85                         accum = XCA_GET16 ( src );
  86                         accum <<= 16;
  87                         accum |= XCA_GET16 ( src );
  88                         extra_bits = 16;
  89
  90                         /* Determine next threshold */
  91                         out_len_threshold = ( out_len + XCA_BLOCK_SIZE );
  92                 }
  93
  94                 /* Determine symbol */
  95                 huf = ( accum >> ( 32 - HUFFMAN_BITS ) );
  96                 sym = huffman_sym ( &xca.alphabet, huf );
  97                 raw = huffman_raw ( sym, huf );
  98                 accum <<= huffman_len ( sym );
  99                 extra_bits -= huffman_len ( sym );
 100                 if ( extra_bits < 0 ) {
 101                         accum |= ( XCA_GET16 ( src ) << ( -extra_bits ) );
 102                         extra_bits += 16;
 103                 }
 104
 105                 /* Process symbol */
 106                 if ( raw < XCA_END_MARKER ) {
 107
 108                         /* Literal symbol - add to output stream */
 109                         if ( buf )
 110                                 *(out++) = raw;
 111                         out_len++;
 112
 113                 } else if ( ( raw == XCA_END_MARKER ) &&
 114                             ( (uint8_t *) src >= ( ( uint8_t * ) end - 1 ) ) ) {
 115
 116                         /* End marker symbol */
 117                         return out_len;
 118
 119                 } else {
 120
 121                         /* LZ77 match symbol */
 122                         raw -= XCA_END_MARKER;
 123                         match_offset_bits = ( raw >> 4 );
 124                         match_len = ( raw & 0x0f );
 125                         if ( match_len == 0x0f ) {
 126                                 match_len = XCA_GET8 ( src );
 127                                 if ( match_len == 0xff ) {
 128                                         match_len = XCA_GET16 ( src );
 129                                 } else {
 130                                         match_len += 0x0f;
 131                                 }
 132                         }
 133                         match_len += 3;
 134                         if ( match_offset_bits ) {
 135                                 match_offset =
 136                                         ( ( accum >> ( 32 - match_offset_bits ))
 137                                           + ( 1 << match_offset_bits ) );
 138                         } else {
 139                                 match_offset = 1;
 140                         }
 141                         accum <<= match_offset_bits;
 142                         extra_bits -= match_offset_bits;
 143                         if ( extra_bits < 0 ) {
 144                                 accum |= ( XCA_GET16 ( src ) << (-extra_bits) );
 145                                 extra_bits += 16;
 146                         }
 147
 148                         /* Copy data */
 149                         out_len += match_len;
 150                         if ( buf ) {
 151                                 copy = ( out - match_offset );
 152                                 while ( match_len-- )
 153                                         *(out++) = *(copy++);
 154                         }
 155                 }
 156         }
 157
 158         return out_len;
 159 }