src/liblzma/common/index_hash.c - jrn/xz - Git at Google

 ///////////////////////////////////////////////////////////////////////////////
 //
 /// \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,
 		const 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,
 		const 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;
 }
	///////////////////////////////////////////////////////////////////////////////
	//
	/// \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,
	const 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,
	const 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;
	}