12940b44dSPeter Avalos ///////////////////////////////////////////////////////////////////////////////
22940b44dSPeter Avalos //
32940b44dSPeter Avalos /// \file index_hash.c
42940b44dSPeter Avalos /// \brief Validates Index by using a hash function
52940b44dSPeter Avalos //
62940b44dSPeter Avalos // Author: Lasse Collin
72940b44dSPeter Avalos //
82940b44dSPeter Avalos // This file has been put into the public domain.
92940b44dSPeter Avalos // You can do whatever you want with this file.
102940b44dSPeter Avalos //
112940b44dSPeter Avalos ///////////////////////////////////////////////////////////////////////////////
122940b44dSPeter Avalos
132940b44dSPeter Avalos #include "common.h"
142940b44dSPeter Avalos #include "index.h"
152940b44dSPeter Avalos #include "check.h"
162940b44dSPeter Avalos
172940b44dSPeter Avalos
182940b44dSPeter Avalos typedef struct {
192940b44dSPeter Avalos /// Sum of the Block sizes (including Block Padding)
202940b44dSPeter Avalos lzma_vli blocks_size;
212940b44dSPeter Avalos
222940b44dSPeter Avalos /// Sum of the Uncompressed Size fields
232940b44dSPeter Avalos lzma_vli uncompressed_size;
242940b44dSPeter Avalos
252940b44dSPeter Avalos /// Number of Records
262940b44dSPeter Avalos lzma_vli count;
272940b44dSPeter Avalos
282940b44dSPeter Avalos /// Size of the List of Index Records as bytes
292940b44dSPeter Avalos lzma_vli index_list_size;
302940b44dSPeter Avalos
312940b44dSPeter Avalos /// Check calculated from Unpadded Sizes and Uncompressed Sizes.
322940b44dSPeter Avalos lzma_check_state check;
332940b44dSPeter Avalos
342940b44dSPeter Avalos } lzma_index_hash_info;
352940b44dSPeter Avalos
362940b44dSPeter Avalos
372940b44dSPeter Avalos struct lzma_index_hash_s {
382940b44dSPeter Avalos enum {
392940b44dSPeter Avalos SEQ_BLOCK,
402940b44dSPeter Avalos SEQ_COUNT,
412940b44dSPeter Avalos SEQ_UNPADDED,
422940b44dSPeter Avalos SEQ_UNCOMPRESSED,
432940b44dSPeter Avalos SEQ_PADDING_INIT,
442940b44dSPeter Avalos SEQ_PADDING,
452940b44dSPeter Avalos SEQ_CRC32,
462940b44dSPeter Avalos } sequence;
472940b44dSPeter Avalos
482940b44dSPeter Avalos /// Information collected while decoding the actual Blocks.
492940b44dSPeter Avalos lzma_index_hash_info blocks;
502940b44dSPeter Avalos
512940b44dSPeter Avalos /// Information collected from the Index field.
522940b44dSPeter Avalos lzma_index_hash_info records;
532940b44dSPeter Avalos
542940b44dSPeter Avalos /// Number of Records not fully decoded
552940b44dSPeter Avalos lzma_vli remaining;
562940b44dSPeter Avalos
572940b44dSPeter Avalos /// Unpadded Size currently being read from an Index Record.
582940b44dSPeter Avalos lzma_vli unpadded_size;
592940b44dSPeter Avalos
602940b44dSPeter Avalos /// Uncompressed Size currently being read from an Index Record.
612940b44dSPeter Avalos lzma_vli uncompressed_size;
622940b44dSPeter Avalos
632940b44dSPeter Avalos /// Position in variable-length integers when decoding them from
642940b44dSPeter Avalos /// the List of Records.
652940b44dSPeter Avalos size_t pos;
662940b44dSPeter Avalos
672940b44dSPeter Avalos /// CRC32 of the Index
682940b44dSPeter Avalos uint32_t crc32;
692940b44dSPeter Avalos };
702940b44dSPeter Avalos
712940b44dSPeter Avalos
722940b44dSPeter Avalos extern LZMA_API(lzma_index_hash *)
lzma_index_hash_init(lzma_index_hash * index_hash,const lzma_allocator * allocator)73*15ab8c86SJohn Marino lzma_index_hash_init(lzma_index_hash *index_hash,
74*15ab8c86SJohn Marino const lzma_allocator *allocator)
752940b44dSPeter Avalos {
762940b44dSPeter Avalos if (index_hash == NULL) {
772940b44dSPeter Avalos index_hash = lzma_alloc(sizeof(lzma_index_hash), allocator);
782940b44dSPeter Avalos if (index_hash == NULL)
792940b44dSPeter Avalos return NULL;
802940b44dSPeter Avalos }
812940b44dSPeter Avalos
822940b44dSPeter Avalos index_hash->sequence = SEQ_BLOCK;
832940b44dSPeter Avalos index_hash->blocks.blocks_size = 0;
842940b44dSPeter Avalos index_hash->blocks.uncompressed_size = 0;
852940b44dSPeter Avalos index_hash->blocks.count = 0;
862940b44dSPeter Avalos index_hash->blocks.index_list_size = 0;
872940b44dSPeter Avalos index_hash->records.blocks_size = 0;
882940b44dSPeter Avalos index_hash->records.uncompressed_size = 0;
892940b44dSPeter Avalos index_hash->records.count = 0;
902940b44dSPeter Avalos index_hash->records.index_list_size = 0;
912940b44dSPeter Avalos index_hash->unpadded_size = 0;
922940b44dSPeter Avalos index_hash->uncompressed_size = 0;
932940b44dSPeter Avalos index_hash->pos = 0;
942940b44dSPeter Avalos index_hash->crc32 = 0;
952940b44dSPeter Avalos
962940b44dSPeter Avalos // These cannot fail because LZMA_CHECK_BEST is known to be supported.
972940b44dSPeter Avalos (void)lzma_check_init(&index_hash->blocks.check, LZMA_CHECK_BEST);
982940b44dSPeter Avalos (void)lzma_check_init(&index_hash->records.check, LZMA_CHECK_BEST);
992940b44dSPeter Avalos
1002940b44dSPeter Avalos return index_hash;
1012940b44dSPeter Avalos }
1022940b44dSPeter Avalos
1032940b44dSPeter Avalos
1042940b44dSPeter Avalos extern LZMA_API(void)
lzma_index_hash_end(lzma_index_hash * index_hash,const lzma_allocator * allocator)105*15ab8c86SJohn Marino lzma_index_hash_end(lzma_index_hash *index_hash,
106*15ab8c86SJohn Marino const lzma_allocator *allocator)
1072940b44dSPeter Avalos {
1082940b44dSPeter Avalos lzma_free(index_hash, allocator);
1092940b44dSPeter Avalos return;
1102940b44dSPeter Avalos }
1112940b44dSPeter Avalos
1122940b44dSPeter Avalos
1132940b44dSPeter Avalos extern LZMA_API(lzma_vli)
lzma_index_hash_size(const lzma_index_hash * index_hash)1142940b44dSPeter Avalos lzma_index_hash_size(const lzma_index_hash *index_hash)
1152940b44dSPeter Avalos {
1162940b44dSPeter Avalos // Get the size of the Index from ->blocks instead of ->records for
1172940b44dSPeter Avalos // cases where application wants to know the Index Size before
1182940b44dSPeter Avalos // decoding the Index.
1192940b44dSPeter Avalos return index_size(index_hash->blocks.count,
1202940b44dSPeter Avalos index_hash->blocks.index_list_size);
1212940b44dSPeter Avalos }
1222940b44dSPeter Avalos
1232940b44dSPeter Avalos
1242940b44dSPeter Avalos /// Updates the sizes and the hash without any validation.
1252940b44dSPeter Avalos static lzma_ret
hash_append(lzma_index_hash_info * info,lzma_vli unpadded_size,lzma_vli uncompressed_size)1262940b44dSPeter Avalos hash_append(lzma_index_hash_info *info, lzma_vli unpadded_size,
1272940b44dSPeter Avalos lzma_vli uncompressed_size)
1282940b44dSPeter Avalos {
1292940b44dSPeter Avalos info->blocks_size += vli_ceil4(unpadded_size);
1302940b44dSPeter Avalos info->uncompressed_size += uncompressed_size;
1312940b44dSPeter Avalos info->index_list_size += lzma_vli_size(unpadded_size)
1322940b44dSPeter Avalos + lzma_vli_size(uncompressed_size);
1332940b44dSPeter Avalos ++info->count;
1342940b44dSPeter Avalos
1352940b44dSPeter Avalos const lzma_vli sizes[2] = { unpadded_size, uncompressed_size };
1362940b44dSPeter Avalos lzma_check_update(&info->check, LZMA_CHECK_BEST,
1372940b44dSPeter Avalos (const uint8_t *)(sizes), sizeof(sizes));
1382940b44dSPeter Avalos
1392940b44dSPeter Avalos return LZMA_OK;
1402940b44dSPeter Avalos }
1412940b44dSPeter Avalos
1422940b44dSPeter Avalos
1432940b44dSPeter Avalos extern LZMA_API(lzma_ret)
lzma_index_hash_append(lzma_index_hash * index_hash,lzma_vli unpadded_size,lzma_vli uncompressed_size)1442940b44dSPeter Avalos lzma_index_hash_append(lzma_index_hash *index_hash, lzma_vli unpadded_size,
1452940b44dSPeter Avalos lzma_vli uncompressed_size)
1462940b44dSPeter Avalos {
1472940b44dSPeter Avalos // Validate the arguments.
1482940b44dSPeter Avalos if (index_hash->sequence != SEQ_BLOCK
1492940b44dSPeter Avalos || unpadded_size < UNPADDED_SIZE_MIN
1502940b44dSPeter Avalos || unpadded_size > UNPADDED_SIZE_MAX
1512940b44dSPeter Avalos || uncompressed_size > LZMA_VLI_MAX)
1522940b44dSPeter Avalos return LZMA_PROG_ERROR;
1532940b44dSPeter Avalos
1542940b44dSPeter Avalos // Update the hash.
1552940b44dSPeter Avalos return_if_error(hash_append(&index_hash->blocks,
1562940b44dSPeter Avalos unpadded_size, uncompressed_size));
1572940b44dSPeter Avalos
1582940b44dSPeter Avalos // Validate the properties of *info are still in allowed limits.
1592940b44dSPeter Avalos if (index_hash->blocks.blocks_size > LZMA_VLI_MAX
1602940b44dSPeter Avalos || index_hash->blocks.uncompressed_size > LZMA_VLI_MAX
1612940b44dSPeter Avalos || index_size(index_hash->blocks.count,
1622940b44dSPeter Avalos index_hash->blocks.index_list_size)
1632940b44dSPeter Avalos > LZMA_BACKWARD_SIZE_MAX
1642940b44dSPeter Avalos || index_stream_size(index_hash->blocks.blocks_size,
1652940b44dSPeter Avalos index_hash->blocks.count,
1662940b44dSPeter Avalos index_hash->blocks.index_list_size)
1672940b44dSPeter Avalos > LZMA_VLI_MAX)
1682940b44dSPeter Avalos return LZMA_DATA_ERROR;
1692940b44dSPeter Avalos
1702940b44dSPeter Avalos return LZMA_OK;
1712940b44dSPeter Avalos }
1722940b44dSPeter Avalos
1732940b44dSPeter Avalos
1742940b44dSPeter Avalos extern LZMA_API(lzma_ret)
lzma_index_hash_decode(lzma_index_hash * index_hash,const uint8_t * in,size_t * in_pos,size_t in_size)1752940b44dSPeter Avalos lzma_index_hash_decode(lzma_index_hash *index_hash, const uint8_t *in,
1762940b44dSPeter Avalos size_t *in_pos, size_t in_size)
1772940b44dSPeter Avalos {
1782940b44dSPeter Avalos // Catch zero input buffer here, because in contrast to Index encoder
1792940b44dSPeter Avalos // and decoder functions, applications call this function directly
1802940b44dSPeter Avalos // instead of via lzma_code(), which does the buffer checking.
1812940b44dSPeter Avalos if (*in_pos >= in_size)
1822940b44dSPeter Avalos return LZMA_BUF_ERROR;
1832940b44dSPeter Avalos
1842940b44dSPeter Avalos // NOTE: This function has many similarities to index_encode() and
1852940b44dSPeter Avalos // index_decode() functions found from index_encoder.c and
1862940b44dSPeter Avalos // index_decoder.c. See the comments especially in index_encoder.c.
1872940b44dSPeter Avalos const size_t in_start = *in_pos;
1882940b44dSPeter Avalos lzma_ret ret = LZMA_OK;
1892940b44dSPeter Avalos
1902940b44dSPeter Avalos while (*in_pos < in_size)
1912940b44dSPeter Avalos switch (index_hash->sequence) {
1922940b44dSPeter Avalos case SEQ_BLOCK:
1932940b44dSPeter Avalos // Check the Index Indicator is present.
1942940b44dSPeter Avalos if (in[(*in_pos)++] != 0x00)
1952940b44dSPeter Avalos return LZMA_DATA_ERROR;
1962940b44dSPeter Avalos
1972940b44dSPeter Avalos index_hash->sequence = SEQ_COUNT;
1982940b44dSPeter Avalos break;
1992940b44dSPeter Avalos
2002940b44dSPeter Avalos case SEQ_COUNT: {
2012940b44dSPeter Avalos ret = lzma_vli_decode(&index_hash->remaining,
2022940b44dSPeter Avalos &index_hash->pos, in, in_pos, in_size);
2032940b44dSPeter Avalos if (ret != LZMA_STREAM_END)
2042940b44dSPeter Avalos goto out;
2052940b44dSPeter Avalos
2062940b44dSPeter Avalos // The count must match the count of the Blocks decoded.
2072940b44dSPeter Avalos if (index_hash->remaining != index_hash->blocks.count)
2082940b44dSPeter Avalos return LZMA_DATA_ERROR;
2092940b44dSPeter Avalos
2102940b44dSPeter Avalos ret = LZMA_OK;
2112940b44dSPeter Avalos index_hash->pos = 0;
2122940b44dSPeter Avalos
2132940b44dSPeter Avalos // Handle the special case when there are no Blocks.
2142940b44dSPeter Avalos index_hash->sequence = index_hash->remaining == 0
2152940b44dSPeter Avalos ? SEQ_PADDING_INIT : SEQ_UNPADDED;
2162940b44dSPeter Avalos break;
2172940b44dSPeter Avalos }
2182940b44dSPeter Avalos
2192940b44dSPeter Avalos case SEQ_UNPADDED:
2202940b44dSPeter Avalos case SEQ_UNCOMPRESSED: {
2212940b44dSPeter Avalos lzma_vli *size = index_hash->sequence == SEQ_UNPADDED
2222940b44dSPeter Avalos ? &index_hash->unpadded_size
2232940b44dSPeter Avalos : &index_hash->uncompressed_size;
2242940b44dSPeter Avalos
2252940b44dSPeter Avalos ret = lzma_vli_decode(size, &index_hash->pos,
2262940b44dSPeter Avalos in, in_pos, in_size);
2272940b44dSPeter Avalos if (ret != LZMA_STREAM_END)
2282940b44dSPeter Avalos goto out;
2292940b44dSPeter Avalos
2302940b44dSPeter Avalos ret = LZMA_OK;
2312940b44dSPeter Avalos index_hash->pos = 0;
2322940b44dSPeter Avalos
2332940b44dSPeter Avalos if (index_hash->sequence == SEQ_UNPADDED) {
2342940b44dSPeter Avalos if (index_hash->unpadded_size < UNPADDED_SIZE_MIN
2352940b44dSPeter Avalos || index_hash->unpadded_size
2362940b44dSPeter Avalos > UNPADDED_SIZE_MAX)
2372940b44dSPeter Avalos return LZMA_DATA_ERROR;
2382940b44dSPeter Avalos
2392940b44dSPeter Avalos index_hash->sequence = SEQ_UNCOMPRESSED;
2402940b44dSPeter Avalos } else {
2412940b44dSPeter Avalos // Update the hash.
2422940b44dSPeter Avalos return_if_error(hash_append(&index_hash->records,
2432940b44dSPeter Avalos index_hash->unpadded_size,
2442940b44dSPeter Avalos index_hash->uncompressed_size));
2452940b44dSPeter Avalos
2462940b44dSPeter Avalos // Verify that we don't go over the known sizes. Note
2472940b44dSPeter Avalos // that this validation is simpler than the one used
2482940b44dSPeter Avalos // in lzma_index_hash_append(), because here we know
2492940b44dSPeter Avalos // that values in index_hash->blocks are already
2502940b44dSPeter Avalos // validated and we are fine as long as we don't
2512940b44dSPeter Avalos // exceed them in index_hash->records.
2522940b44dSPeter Avalos if (index_hash->blocks.blocks_size
2532940b44dSPeter Avalos < index_hash->records.blocks_size
2542940b44dSPeter Avalos || index_hash->blocks.uncompressed_size
2552940b44dSPeter Avalos < index_hash->records.uncompressed_size
2562940b44dSPeter Avalos || index_hash->blocks.index_list_size
2572940b44dSPeter Avalos < index_hash->records.index_list_size)
2582940b44dSPeter Avalos return LZMA_DATA_ERROR;
2592940b44dSPeter Avalos
2602940b44dSPeter Avalos // Check if this was the last Record.
2612940b44dSPeter Avalos index_hash->sequence = --index_hash->remaining == 0
2622940b44dSPeter Avalos ? SEQ_PADDING_INIT : SEQ_UNPADDED;
2632940b44dSPeter Avalos }
2642940b44dSPeter Avalos
2652940b44dSPeter Avalos break;
2662940b44dSPeter Avalos }
2672940b44dSPeter Avalos
2682940b44dSPeter Avalos case SEQ_PADDING_INIT:
2692940b44dSPeter Avalos index_hash->pos = (LZMA_VLI_C(4) - index_size_unpadded(
2702940b44dSPeter Avalos index_hash->records.count,
2712940b44dSPeter Avalos index_hash->records.index_list_size)) & 3;
2722940b44dSPeter Avalos index_hash->sequence = SEQ_PADDING;
2732940b44dSPeter Avalos
2742940b44dSPeter Avalos // Fall through
2752940b44dSPeter Avalos
2762940b44dSPeter Avalos case SEQ_PADDING:
2772940b44dSPeter Avalos if (index_hash->pos > 0) {
2782940b44dSPeter Avalos --index_hash->pos;
2792940b44dSPeter Avalos if (in[(*in_pos)++] != 0x00)
2802940b44dSPeter Avalos return LZMA_DATA_ERROR;
2812940b44dSPeter Avalos
2822940b44dSPeter Avalos break;
2832940b44dSPeter Avalos }
2842940b44dSPeter Avalos
2852940b44dSPeter Avalos // Compare the sizes.
2862940b44dSPeter Avalos if (index_hash->blocks.blocks_size
2872940b44dSPeter Avalos != index_hash->records.blocks_size
2882940b44dSPeter Avalos || index_hash->blocks.uncompressed_size
2892940b44dSPeter Avalos != index_hash->records.uncompressed_size
2902940b44dSPeter Avalos || index_hash->blocks.index_list_size
2912940b44dSPeter Avalos != index_hash->records.index_list_size)
2922940b44dSPeter Avalos return LZMA_DATA_ERROR;
2932940b44dSPeter Avalos
2942940b44dSPeter Avalos // Finish the hashes and compare them.
2952940b44dSPeter Avalos lzma_check_finish(&index_hash->blocks.check, LZMA_CHECK_BEST);
2962940b44dSPeter Avalos lzma_check_finish(&index_hash->records.check, LZMA_CHECK_BEST);
2972940b44dSPeter Avalos if (memcmp(index_hash->blocks.check.buffer.u8,
2982940b44dSPeter Avalos index_hash->records.check.buffer.u8,
2992940b44dSPeter Avalos lzma_check_size(LZMA_CHECK_BEST)) != 0)
3002940b44dSPeter Avalos return LZMA_DATA_ERROR;
3012940b44dSPeter Avalos
3022940b44dSPeter Avalos // Finish the CRC32 calculation.
3032940b44dSPeter Avalos index_hash->crc32 = lzma_crc32(in + in_start,
3042940b44dSPeter Avalos *in_pos - in_start, index_hash->crc32);
3052940b44dSPeter Avalos
3062940b44dSPeter Avalos index_hash->sequence = SEQ_CRC32;
3072940b44dSPeter Avalos
3082940b44dSPeter Avalos // Fall through
3092940b44dSPeter Avalos
3102940b44dSPeter Avalos case SEQ_CRC32:
3112940b44dSPeter Avalos do {
3122940b44dSPeter Avalos if (*in_pos == in_size)
3132940b44dSPeter Avalos return LZMA_OK;
3142940b44dSPeter Avalos
3152940b44dSPeter Avalos if (((index_hash->crc32 >> (index_hash->pos * 8))
3162940b44dSPeter Avalos & 0xFF) != in[(*in_pos)++])
3172940b44dSPeter Avalos return LZMA_DATA_ERROR;
3182940b44dSPeter Avalos
3192940b44dSPeter Avalos } while (++index_hash->pos < 4);
3202940b44dSPeter Avalos
3212940b44dSPeter Avalos return LZMA_STREAM_END;
3222940b44dSPeter Avalos
3232940b44dSPeter Avalos default:
3242940b44dSPeter Avalos assert(0);
3252940b44dSPeter Avalos return LZMA_PROG_ERROR;
3262940b44dSPeter Avalos }
3272940b44dSPeter Avalos
3282940b44dSPeter Avalos out:
3292940b44dSPeter Avalos // Update the CRC32,
3302940b44dSPeter Avalos index_hash->crc32 = lzma_crc32(in + in_start,
3312940b44dSPeter Avalos *in_pos - in_start, index_hash->crc32);
3322940b44dSPeter Avalos
3332940b44dSPeter Avalos return ret;
3342940b44dSPeter Avalos }
335