wimboot/wimboot-2.7.3/src/lznt1.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  * LZNT1 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 "lznt1.h"
  33
  34 /**
  35  * Decompress LZNT1-compressed data block
  36  *
  37  * @v data              Compressed data
  38  * @v limit             Length of compressed data up to end of block
  39  * @v offset            Starting offset within compressed data
  40  * @v block             Decompression buffer for this block, or NULL
  41  * @ret out_len         Length of decompressed block, or negative error
  42  */
  43 static ssize_t lznt1_block ( const void *data, size_t limit, size_t offset,
  44                              void *block ) {
  45         const uint16_t *tuple;
  46         const uint8_t *copy_src;
  47         uint8_t *copy_dest = block;
  48         size_t copy_len;
  49         size_t block_out_len = 0;
  50         unsigned int split = 12;
  51         unsigned int next_threshold = 16;
  52         unsigned int tag_bit = 0;
  53         unsigned int tag = 0;
  54
  55         while ( offset != limit ) {
  56
  57                 /* Extract tag */
  58                 if ( tag_bit == 0 ) {
  59                         tag = *( ( uint8_t * ) ( data + offset ) );
  60                         offset++;
  61                         if ( offset == limit )
  62                                 break;
  63                 }
  64
  65                 /* Calculate copy source and length */
  66                 if ( tag & 1 ) {
  67
  68                         /* Compressed value */
  69                         if ( offset + sizeof ( *tuple ) > limit ) {
  70                                 DBG ( "LZNT1 compressed value overrun at "
  71                                       "%#zx\n", offset );
  72                                 return -1;
  73                         }
  74                         tuple = ( data + offset );
  75                         offset += sizeof ( *tuple );
  76                         copy_len = LZNT1_VALUE_LEN ( *tuple, split );
  77                         block_out_len += copy_len;
  78                         if ( copy_dest ) {
  79                                 copy_src = ( copy_dest -
  80                                              LZNT1_VALUE_OFFSET ( *tuple,
  81                                                                   split ) );
  82                                 while ( copy_len-- )
  83                                         *(copy_dest++) = *(copy_src++);
  84                         }
  85
  86                 } else {
  87
  88                         /* Uncompressed value */
  89                         copy_src = ( data + offset );
  90                         if ( copy_dest )
  91                                 *(copy_dest++) = *copy_src;
  92                         offset++;
  93                         block_out_len++;
  94                 }
  95
  96                 /* Update split, if applicable */
  97                 while ( block_out_len > next_threshold ) {
  98                         split--;
  99                         next_threshold <<= 1;
 100                 }
 101
 102                 /* Move to next value */
 103                 tag >>= 1;
 104                 tag_bit = ( ( tag_bit + 1 ) % 8 );
 105         }
 106
 107         return block_out_len;
 108 }
 109
 110 /**
 111  * Decompress LZNT1-compressed data
 112  *
 113  * @v data              Compressed data
 114  * @v len               Length of compressed data
 115  * @v buf               Decompression buffer, or NULL
 116  * @ret out_len         Length of decompressed data, or negative error
 117  */
 118 ssize_t lznt1_decompress ( const void *data, size_t len, void *buf ) {
 119         const uint16_t *header;
 120         const uint8_t *end;
 121         size_t offset = 0;
 122         ssize_t out_len = 0;
 123         size_t block_len;
 124         size_t limit;
 125         void *block;
 126         ssize_t block_out_len;
 127
 128         while ( offset != len ) {
 129
 130                 /* Check for end marker */
 131                 if ( ( offset + sizeof ( *end ) ) == len ) {
 132                         end = ( data + offset );
 133                         if ( *end == 0 )
 134                                 break;
 135                 }
 136
 137                 /* Extract block header */
 138                 if ( ( offset + sizeof ( *header ) ) > len ) {
 139                         DBG ( "LZNT1 block header overrun at %#zx\n", offset );
 140                         return -1;
 141                 }
 142                 header = ( data + offset );
 143                 offset += sizeof ( *header );
 144
 145                 /* Process block */
 146                 block_len = LZNT1_BLOCK_LEN ( *header );
 147                 if ( LZNT1_BLOCK_COMPRESSED ( *header ) ) {
 148
 149                         /* Compressed block */
 150                         DBG2 ( "LZNT1 compressed block %#zx+%#zx\n",
 151                                offset, block_len );
 152                         limit = ( offset + block_len );
 153                         block = ( buf ? ( buf + out_len ) : NULL );
 154                         block_out_len = lznt1_block ( data, limit, offset,
 155                                                       block );
 156                         if ( block_out_len < 0 )
 157                                 return block_out_len;
 158                         offset += block_len;
 159                         out_len += block_out_len;
 160
 161                 } else {
 162
 163                         /* Uncompressed block */
 164                         if ( ( offset + block_len ) > len ) {
 165                                 DBG ( "LZNT1 uncompressed block overrun at "
 166                                       "%#zx+%#zx\n", offset, block_len );
 167                                 return -1;
 168                         }
 169                         DBG2 ( "LZNT1 uncompressed block %#zx+%#zx\n",
 170                                offset, block_len );
 171                         if ( buf ) {
 172                                 memcpy ( ( buf + out_len ), ( data + offset ),
 173                                          block_len );
 174                         }
 175                         offset += block_len;
 176                         out_len += block_len;
 177                 }
 178         }
 179
 180         return out_len;
 181 }