Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(287)

Unified Diff: xz/src/liblzma/common/index_hash.c

Issue 2869016: Add an unpatched version of xz, XZ Utils, to /trunk/deps/third_party (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/deps/third_party/
Patch Set: Created 10 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « xz/src/liblzma/common/index_encoder.c ('k') | xz/src/liblzma/common/stream_buffer_decoder.c » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: xz/src/liblzma/common/index_hash.c
===================================================================
--- xz/src/liblzma/common/index_hash.c (revision 0)
+++ xz/src/liblzma/common/index_hash.c (revision 0)
@@ -0,0 +1,332 @@
+///////////////////////////////////////////////////////////////////////////////
+//
+/// \file index_hash.c
+/// \brief Validates Index by using a hash function
+//
+// Author: Lasse Collin
+//
+// This file has been put into the public domain.
+// You can do whatever you want with this file.
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#include "common.h"
+#include "index.h"
+#include "check.h"
+
+
+typedef struct {
+ /// Sum of the Block sizes (including Block Padding)
+ lzma_vli blocks_size;
+
+ /// Sum of the Uncompressed Size fields
+ lzma_vli uncompressed_size;
+
+ /// Number of Records
+ lzma_vli count;
+
+ /// Size of the List of Index Records as bytes
+ lzma_vli index_list_size;
+
+ /// Check calculated from Unpadded Sizes and Uncompressed Sizes.
+ lzma_check_state check;
+
+} lzma_index_hash_info;
+
+
+struct lzma_index_hash_s {
+ enum {
+ SEQ_BLOCK,
+ SEQ_COUNT,
+ SEQ_UNPADDED,
+ SEQ_UNCOMPRESSED,
+ SEQ_PADDING_INIT,
+ SEQ_PADDING,
+ SEQ_CRC32,
+ } sequence;
+
+ /// Information collected while decoding the actual Blocks.
+ lzma_index_hash_info blocks;
+
+ /// Information collected from the Index field.
+ lzma_index_hash_info records;
+
+ /// Number of Records not fully decoded
+ lzma_vli remaining;
+
+ /// Unpadded Size currently being read from an Index Record.
+ lzma_vli unpadded_size;
+
+ /// Uncompressed Size currently being read from an Index Record.
+ lzma_vli uncompressed_size;
+
+ /// Position in variable-length integers when decoding them from
+ /// the List of Records.
+ size_t pos;
+
+ /// CRC32 of the Index
+ uint32_t crc32;
+};
+
+
+extern LZMA_API(lzma_index_hash *)
+lzma_index_hash_init(lzma_index_hash *index_hash, lzma_allocator *allocator)
+{
+ if (index_hash == NULL) {
+ index_hash = lzma_alloc(sizeof(lzma_index_hash), allocator);
+ if (index_hash == NULL)
+ return NULL;
+ }
+
+ index_hash->sequence = SEQ_BLOCK;
+ index_hash->blocks.blocks_size = 0;
+ index_hash->blocks.uncompressed_size = 0;
+ index_hash->blocks.count = 0;
+ index_hash->blocks.index_list_size = 0;
+ index_hash->records.blocks_size = 0;
+ index_hash->records.uncompressed_size = 0;
+ index_hash->records.count = 0;
+ index_hash->records.index_list_size = 0;
+ index_hash->unpadded_size = 0;
+ index_hash->uncompressed_size = 0;
+ index_hash->pos = 0;
+ index_hash->crc32 = 0;
+
+ // These cannot fail because LZMA_CHECK_BEST is known to be supported.
+ (void)lzma_check_init(&index_hash->blocks.check, LZMA_CHECK_BEST);
+ (void)lzma_check_init(&index_hash->records.check, LZMA_CHECK_BEST);
+
+ return index_hash;
+}
+
+
+extern LZMA_API(void)
+lzma_index_hash_end(lzma_index_hash *index_hash, lzma_allocator *allocator)
+{
+ lzma_free(index_hash, allocator);
+ return;
+}
+
+
+extern LZMA_API(lzma_vli)
+lzma_index_hash_size(const lzma_index_hash *index_hash)
+{
+ // Get the size of the Index from ->blocks instead of ->records for
+ // cases where application wants to know the Index Size before
+ // decoding the Index.
+ return index_size(index_hash->blocks.count,
+ index_hash->blocks.index_list_size);
+}
+
+
+/// Updates the sizes and the hash without any validation.
+static lzma_ret
+hash_append(lzma_index_hash_info *info, lzma_vli unpadded_size,
+ lzma_vli uncompressed_size)
+{
+ info->blocks_size += vli_ceil4(unpadded_size);
+ info->uncompressed_size += uncompressed_size;
+ info->index_list_size += lzma_vli_size(unpadded_size)
+ + lzma_vli_size(uncompressed_size);
+ ++info->count;
+
+ const lzma_vli sizes[2] = { unpadded_size, uncompressed_size };
+ lzma_check_update(&info->check, LZMA_CHECK_BEST,
+ (const uint8_t *)(sizes), sizeof(sizes));
+
+ return LZMA_OK;
+}
+
+
+extern LZMA_API(lzma_ret)
+lzma_index_hash_append(lzma_index_hash *index_hash, lzma_vli unpadded_size,
+ lzma_vli uncompressed_size)
+{
+ // Validate the arguments.
+ if (index_hash->sequence != SEQ_BLOCK
+ || unpadded_size < UNPADDED_SIZE_MIN
+ || unpadded_size > UNPADDED_SIZE_MAX
+ || uncompressed_size > LZMA_VLI_MAX)
+ return LZMA_PROG_ERROR;
+
+ // Update the hash.
+ return_if_error(hash_append(&index_hash->blocks,
+ unpadded_size, uncompressed_size));
+
+ // Validate the properties of *info are still in allowed limits.
+ if (index_hash->blocks.blocks_size > LZMA_VLI_MAX
+ || index_hash->blocks.uncompressed_size > LZMA_VLI_MAX
+ || index_size(index_hash->blocks.count,
+ index_hash->blocks.index_list_size)
+ > LZMA_BACKWARD_SIZE_MAX
+ || index_stream_size(index_hash->blocks.blocks_size,
+ index_hash->blocks.count,
+ index_hash->blocks.index_list_size)
+ > LZMA_VLI_MAX)
+ return LZMA_DATA_ERROR;
+
+ return LZMA_OK;
+}
+
+
+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)
+{
+ // Catch zero input buffer here, because in contrast to Index encoder
+ // and decoder functions, applications call this function directly
+ // instead of via lzma_code(), which does the buffer checking.
+ if (*in_pos >= in_size)
+ return LZMA_BUF_ERROR;
+
+ // NOTE: This function has many similarities to index_encode() and
+ // index_decode() functions found from index_encoder.c and
+ // index_decoder.c. See the comments especially in index_encoder.c.
+ const size_t in_start = *in_pos;
+ lzma_ret ret = LZMA_OK;
+
+ while (*in_pos < in_size)
+ switch (index_hash->sequence) {
+ case SEQ_BLOCK:
+ // Check the Index Indicator is present.
+ if (in[(*in_pos)++] != 0x00)
+ return LZMA_DATA_ERROR;
+
+ index_hash->sequence = SEQ_COUNT;
+ break;
+
+ case SEQ_COUNT: {
+ ret = lzma_vli_decode(&index_hash->remaining,
+ &index_hash->pos, in, in_pos, in_size);
+ if (ret != LZMA_STREAM_END)
+ goto out;
+
+ // The count must match the count of the Blocks decoded.
+ if (index_hash->remaining != index_hash->blocks.count)
+ return LZMA_DATA_ERROR;
+
+ ret = LZMA_OK;
+ index_hash->pos = 0;
+
+ // Handle the special case when there are no Blocks.
+ index_hash->sequence = index_hash->remaining == 0
+ ? SEQ_PADDING_INIT : SEQ_UNPADDED;
+ break;
+ }
+
+ case SEQ_UNPADDED:
+ case SEQ_UNCOMPRESSED: {
+ lzma_vli *size = index_hash->sequence == SEQ_UNPADDED
+ ? &index_hash->unpadded_size
+ : &index_hash->uncompressed_size;
+
+ ret = lzma_vli_decode(size, &index_hash->pos,
+ in, in_pos, in_size);
+ if (ret != LZMA_STREAM_END)
+ goto out;
+
+ ret = LZMA_OK;
+ index_hash->pos = 0;
+
+ if (index_hash->sequence == SEQ_UNPADDED) {
+ if (index_hash->unpadded_size < UNPADDED_SIZE_MIN
+ || index_hash->unpadded_size
+ > UNPADDED_SIZE_MAX)
+ return LZMA_DATA_ERROR;
+
+ index_hash->sequence = SEQ_UNCOMPRESSED;
+ } else {
+ // Update the hash.
+ return_if_error(hash_append(&index_hash->records,
+ index_hash->unpadded_size,
+ index_hash->uncompressed_size));
+
+ // Verify that we don't go over the known sizes. Note
+ // that this validation is simpler than the one used
+ // in lzma_index_hash_append(), because here we know
+ // that values in index_hash->blocks are already
+ // validated and we are fine as long as we don't
+ // exceed them in index_hash->records.
+ if (index_hash->blocks.blocks_size
+ < index_hash->records.blocks_size
+ || index_hash->blocks.uncompressed_size
+ < index_hash->records.uncompressed_size
+ || index_hash->blocks.index_list_size
+ < index_hash->records.index_list_size)
+ return LZMA_DATA_ERROR;
+
+ // Check if this was the last Record.
+ index_hash->sequence = --index_hash->remaining == 0
+ ? SEQ_PADDING_INIT : SEQ_UNPADDED;
+ }
+
+ break;
+ }
+
+ case SEQ_PADDING_INIT:
+ index_hash->pos = (LZMA_VLI_C(4) - index_size_unpadded(
+ index_hash->records.count,
+ index_hash->records.index_list_size)) & 3;
+ index_hash->sequence = SEQ_PADDING;
+
+ // Fall through
+
+ case SEQ_PADDING:
+ if (index_hash->pos > 0) {
+ --index_hash->pos;
+ if (in[(*in_pos)++] != 0x00)
+ return LZMA_DATA_ERROR;
+
+ break;
+ }
+
+ // Compare the sizes.
+ if (index_hash->blocks.blocks_size
+ != index_hash->records.blocks_size
+ || index_hash->blocks.uncompressed_size
+ != index_hash->records.uncompressed_size
+ || index_hash->blocks.index_list_size
+ != index_hash->records.index_list_size)
+ return LZMA_DATA_ERROR;
+
+ // Finish the hashes and compare them.
+ lzma_check_finish(&index_hash->blocks.check, LZMA_CHECK_BEST);
+ lzma_check_finish(&index_hash->records.check, LZMA_CHECK_BEST);
+ if (memcmp(index_hash->blocks.check.buffer.u8,
+ index_hash->records.check.buffer.u8,
+ lzma_check_size(LZMA_CHECK_BEST)) != 0)
+ return LZMA_DATA_ERROR;
+
+ // Finish the CRC32 calculation.
+ index_hash->crc32 = lzma_crc32(in + in_start,
+ *in_pos - in_start, index_hash->crc32);
+
+ index_hash->sequence = SEQ_CRC32;
+
+ // Fall through
+
+ case SEQ_CRC32:
+ do {
+ if (*in_pos == in_size)
+ return LZMA_OK;
+
+ if (((index_hash->crc32 >> (index_hash->pos * 8))
+ & 0xFF) != in[(*in_pos)++])
+ return LZMA_DATA_ERROR;
+
+ } while (++index_hash->pos < 4);
+
+ return LZMA_STREAM_END;
+
+ default:
+ assert(0);
+ return LZMA_PROG_ERROR;
+ }
+
+out:
+ // Update the CRC32,
+ index_hash->crc32 = lzma_crc32(in + in_start,
+ *in_pos - in_start, index_hash->crc32);
+
+ return ret;
+}
Property changes on: xz/src/liblzma/common/index_hash.c
___________________________________________________________________
Added: svn:eol-style
+ LF
« no previous file with comments | « xz/src/liblzma/common/index_encoder.c ('k') | xz/src/liblzma/common/stream_buffer_decoder.c » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698