src/liblzma/common/index_hash.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //
   3 /// \file       index_hash.c
   4 /// \brief      Validates Index by using a hash function
   5 //
   6 //  Copyright (C) 2008 Lasse Collin
   7 //
   8 //  This library is free software; you can redistribute it and/or
   9 //  modify it under the terms of the GNU Lesser General Public
  10 //  License as published by the Free Software Foundation; either
  11 //  version 2.1 of the License, or (at your option) any later version.
  12 //
  13 //  This library is distributed in the hope that it will be useful,
  14 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16 //  Lesser General Public License for more details.
  17 //
  18 ///////////////////////////////////////////////////////////////////////////////
  19
  20 #include "common.h"
  21 #include "index.h"
  22 #include "check.h"
  23
  24
  25 typedef struct {
  26         /// Sum of the Block sizes (including Block Padding)
  27         lzma_vli blocks_size;
  28
  29         /// Sum of the Uncompressed Size fields
  30         lzma_vli uncompressed_size;
  31
  32         /// Number of Records
  33         lzma_vli count;
  34
  35         /// Size of the List of Index Records as bytes
  36         lzma_vli index_list_size;
  37
  38         /// Check calculated from Unpadded Sizes and Uncompressed Sizes.
  39         lzma_check_state check;
  40
  41 } lzma_index_hash_info;
  42
  43
  44 struct lzma_index_hash_s {
  45         enum {
  46                 SEQ_BLOCK,
  47                 SEQ_COUNT,
  48                 SEQ_UNPADDED,
  49                 SEQ_UNCOMPRESSED,
  50                 SEQ_PADDING_INIT,
  51                 SEQ_PADDING,
  52                 SEQ_CRC32,
  53         } sequence;
  54
  55         /// Information collected while decoding the actual Blocks.
  56         lzma_index_hash_info blocks;
  57
  58         /// Information collected from the Index field.
  59         lzma_index_hash_info records;
  60
  61         /// Number of Records not fully decoded
  62         lzma_vli remaining;
  63
  64         /// Unpadded Size currently being read from an Index Record.
  65         lzma_vli unpadded_size;
  66
  67         /// Uncompressed Size currently being read from an Index Record.
  68         lzma_vli uncompressed_size;
  69
  70         /// Position in variable-length integers when decoding them from
  71         /// the List of Records.
  72         size_t pos;
  73
  74         /// CRC32 of the Index
  75         uint32_t crc32;
  76 };
  77
  78
  79 extern LZMA_API lzma_index_hash *
  80 lzma_index_hash_init(lzma_index_hash *index_hash, lzma_allocator *allocator)
  81 {
  82         if (index_hash == NULL) {
  83                 index_hash = lzma_alloc(sizeof(lzma_index_hash), allocator);
  84                 if (index_hash == NULL)
  85                         return NULL;
  86         }
  87
  88         index_hash->sequence = SEQ_BLOCK;
  89         index_hash->blocks.blocks_size = 0;
  90         index_hash->blocks.uncompressed_size = 0;
  91         index_hash->blocks.count = 0;
  92         index_hash->blocks.index_list_size = 0;
  93         index_hash->records.blocks_size = 0;
  94         index_hash->records.uncompressed_size = 0;
  95         index_hash->records.count = 0;
  96         index_hash->records.index_list_size = 0;
  97         index_hash->unpadded_size = 0;
  98         index_hash->uncompressed_size = 0;
  99         index_hash->pos = 0;
 100         index_hash->crc32 = 0;
 101
 102         // These cannot fail because LZMA_CHECK_BEST is known to be supported.
 103         (void)lzma_check_init(&index_hash->blocks.check, LZMA_CHECK_BEST);
 104         (void)lzma_check_init(&index_hash->records.check, LZMA_CHECK_BEST);
 105
 106         return index_hash;
 107 }
 108
 109
 110 extern LZMA_API void
 111 lzma_index_hash_end(lzma_index_hash *index_hash, lzma_allocator *allocator)
 112 {
 113         lzma_free(index_hash, allocator);
 114         return;
 115 }
 116
 117
 118 extern LZMA_API lzma_vli
 119 lzma_index_hash_size(const lzma_index_hash *index_hash)
 120 {
 121         // Get the size of the Index from ->blocks instead of ->records for
 122         // cases where application wants to know the Index Size before
 123         // decoding the Index.
 124         return index_size(index_hash->blocks.count,
 125                         index_hash->blocks.index_list_size);
 126 }
 127
 128
 129 /// Updates the sizes and the hash without any validation.
 130 static lzma_ret
 131 hash_append(lzma_index_hash_info *info, lzma_vli unpadded_size,
 132                 lzma_vli uncompressed_size)
 133 {
 134         info->blocks_size += vli_ceil4(unpadded_size);
 135         info->uncompressed_size += uncompressed_size;
 136         info->index_list_size += lzma_vli_size(unpadded_size)
 137                         + lzma_vli_size(uncompressed_size);
 138         ++info->count;
 139
 140         const lzma_vli sizes[2] = { unpadded_size, uncompressed_size };
 141         lzma_check_update(&info->check, LZMA_CHECK_BEST,
 142                         (const uint8_t *)(sizes), sizeof(sizes));
 143
 144         return LZMA_OK;
 145 }
 146
 147
 148 extern LZMA_API lzma_ret
 149 lzma_index_hash_append(lzma_index_hash *index_hash, lzma_vli unpadded_size,
 150                 lzma_vli uncompressed_size)
 151 {
 152         // Validate the arguments.
 153         if (index_hash->sequence != SEQ_BLOCK
 154                         || unpadded_size < UNPADDED_SIZE_MIN
 155                         || unpadded_size > UNPADDED_SIZE_MAX
 156                         || uncompressed_size > LZMA_VLI_MAX)
 157                 return LZMA_PROG_ERROR;
 158
 159         // Update the hash.
 160         return_if_error(hash_append(&index_hash->blocks,
 161                         unpadded_size, uncompressed_size));
 162
 163         // Validate the properties of *info are still in allowed limits.
 164         if (index_hash->blocks.blocks_size > LZMA_VLI_MAX
 165                         || index_hash->blocks.uncompressed_size > LZMA_VLI_MAX
 166                         || index_size(index_hash->blocks.count,
 167                                         index_hash->blocks.index_list_size)
 168                                 > LZMA_BACKWARD_SIZE_MAX
 169                         || index_stream_size(index_hash->blocks.blocks_size,
 170                                         index_hash->blocks.count,
 171                                         index_hash->blocks.index_list_size)
 172                                 > LZMA_VLI_MAX)
 173                 return LZMA_DATA_ERROR;
 174
 175         return LZMA_OK;
 176 }
 177
 178
 179 extern LZMA_API lzma_ret
 180 lzma_index_hash_decode(lzma_index_hash *index_hash, const uint8_t *in,
 181                 size_t *in_pos, size_t in_size)
 182 {
 183         // Catch zero input buffer here, because in contrast to Index encoder
 184         // and decoder functions, applications call this function directly
 185         // instead of via lzma_code(), which does the buffer checking.
 186         if (*in_pos >= in_size)
 187                 return LZMA_BUF_ERROR;
 188
 189         // NOTE: This function has many similarities to index_encode() and
 190         // index_decode() functions found from index_encoder.c and
 191         // index_decoder.c. See the comments especially in index_encoder.c.
 192         const size_t in_start = *in_pos;
 193         lzma_ret ret = LZMA_OK;
 194
 195         while (*in_pos < in_size)
 196         switch (index_hash->sequence) {
 197         case SEQ_BLOCK:
 198                 // Check the Index Indicator is present.
 199                 if (in[(*in_pos)++] != 0x00)
 200                         return LZMA_DATA_ERROR;
 201
 202                 index_hash->sequence = SEQ_COUNT;
 203                 break;
 204
 205         case SEQ_COUNT: {
 206                 ret = lzma_vli_decode(&index_hash->remaining,
 207                                 &index_hash->pos, in, in_pos, in_size);
 208                 if (ret != LZMA_STREAM_END)
 209                         goto out;
 210
 211                 // The count must match the count of the Blocks decoded.
 212                 if (index_hash->remaining != index_hash->blocks.count)
 213                         return LZMA_DATA_ERROR;
 214
 215                 ret = LZMA_OK;
 216                 index_hash->pos = 0;
 217
 218                 // Handle the special case when there are no Blocks.
 219                 index_hash->sequence = index_hash->remaining == 0
 220                                 ? SEQ_PADDING_INIT : SEQ_UNPADDED;
 221                 break;
 222         }
 223
 224         case SEQ_UNPADDED:
 225         case SEQ_UNCOMPRESSED: {
 226                 lzma_vli *size = index_hash->sequence == SEQ_UNPADDED
 227                                 ? &index_hash->unpadded_size
 228                                 : &index_hash->uncompressed_size;
 229
 230                 ret = lzma_vli_decode(size, &index_hash->pos,
 231                                 in, in_pos, in_size);
 232                 if (ret != LZMA_STREAM_END)
 233                         goto out;
 234
 235                 ret = LZMA_OK;
 236                 index_hash->pos = 0;
 237
 238                 if (index_hash->sequence == SEQ_UNPADDED) {
 239                         if (index_hash->unpadded_size < UNPADDED_SIZE_MIN
 240                                         || index_hash->unpadded_size
 241                                                 > UNPADDED_SIZE_MAX)
 242                                 return LZMA_DATA_ERROR;
 243
 244                         index_hash->sequence = SEQ_UNCOMPRESSED;
 245                 } else {
 246                         // Update the hash.
 247                         return_if_error(hash_append(&index_hash->records,
 248                                         index_hash->unpadded_size,
 249                                         index_hash->uncompressed_size));
 250
 251                         // Verify that we don't go over the known sizes. Note
 252                         // that this validation is simpler than the one used
 253                         // in lzma_index_hash_append(), because here we know
 254                         // that values in index_hash->blocks are already
 255                         // validated and we are fine as long as we don't
 256                         // exceed them in index_hash->records.
 257                         if (index_hash->blocks.blocks_size
 258                                         < index_hash->records.blocks_size
 259                                         || index_hash->blocks.uncompressed_size
 260                                         < index_hash->records.uncompressed_size
 261                                         || index_hash->blocks.index_list_size
 262                                         < index_hash->records.index_list_size)
 263                                 return LZMA_DATA_ERROR;
 264
 265                         // Check if this was the last Record.
 266                         index_hash->sequence = --index_hash->remaining == 0
 267                                         ? SEQ_PADDING_INIT : SEQ_UNPADDED;
 268                 }
 269
 270                 break;
 271         }
 272
 273         case SEQ_PADDING_INIT:
 274                 index_hash->pos = (LZMA_VLI_C(4) - index_size_unpadded(
 275                                 index_hash->records.count,
 276                                 index_hash->records.index_list_size)) & 3;
 277                 index_hash->sequence = SEQ_PADDING;
 278
 279         // Fall through
 280
 281         case SEQ_PADDING:
 282                 if (index_hash->pos > 0) {
 283                         --index_hash->pos;
 284                         if (in[(*in_pos)++] != 0x00)
 285                                 return LZMA_DATA_ERROR;
 286
 287                         break;
 288                 }
 289
 290                 // Compare the sizes.
 291                 if (index_hash->blocks.blocks_size
 292                                 != index_hash->records.blocks_size
 293                                 || index_hash->blocks.uncompressed_size
 294                                 != index_hash->records.uncompressed_size
 295                                 || index_hash->blocks.index_list_size
 296                                 != index_hash->records.index_list_size)
 297                         return LZMA_DATA_ERROR;
 298
 299                 // Finish the hashes and compare them.
 300                 lzma_check_finish(&index_hash->blocks.check, LZMA_CHECK_BEST);
 301                 lzma_check_finish(&index_hash->records.check, LZMA_CHECK_BEST);
 302                 if (memcmp(index_hash->blocks.check.buffer.u8,
 303                                 index_hash->records.check.buffer.u8,
 304                                 lzma_check_size(LZMA_CHECK_BEST)) != 0)
 305                         return LZMA_DATA_ERROR;
 306
 307                 // Finish the CRC32 calculation.
 308                 index_hash->crc32 = lzma_crc32(in + in_start,
 309                                 *in_pos - in_start, index_hash->crc32);
 310
 311                 index_hash->sequence = SEQ_CRC32;
 312
 313         // Fall through
 314
 315         case SEQ_CRC32:
 316                 do {
 317                         if (*in_pos == in_size)
 318                                 return LZMA_OK;
 319
 320                         if (((index_hash->crc32 >> (index_hash->pos * 8))
 321                                         & 0xFF) != in[(*in_pos)++])
 322                                 return LZMA_DATA_ERROR;
 323
 324                 } while (++index_hash->pos < 4);
 325
 326                 return LZMA_STREAM_END;
 327
 328         default:
 329                 assert(0);
 330                 return LZMA_PROG_ERROR;
 331         }
 332
 333 out:
 334         // Update the CRC32,
 335         index_hash->crc32 = lzma_crc32(in + in_start,
 336                         *in_pos - in_start, index_hash->crc32);
 337
 338         return ret;
 339 }