File Coverage

_aich.c

Criterion	Covered	Total	%
statement	32	213	15.0
branch	11	166	6.6
condition			n/a
subroutine			n/a
pod			n/a
total	43	379	11.3

/* aich.c - an implementation of EMule AICH Algorithm.
 * Description: http://www.amule.org/wiki/index.php/AICH.
 *
 * Copyright (c) 2008, Aleksey Kravchenko
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE  INCLUDING ALL IMPLIED WARRANTIES OF  MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT,  OR CONSEQUENTIAL DAMAGES  OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE,  DATA OR PROFITS,  WHETHER IN AN ACTION OF CONTRACT,  NEGLIGENCE
 * OR OTHER TORTIOUS ACTION,  ARISING OUT OF  OR IN CONNECTION  WITH THE USE  OR
 * PERFORMANCE OF THIS SOFTWARE.
 *
 * The AICH Algorithm:
 *
 * Each ed2k chunk (9728000 bytes) is divided into 53 parts (52x 180KB and
 * 1x 140KB) and each of these parts are hashed using the SHA1 algorithm.
 * Each of these hashes is called a Block Hash. By combining pairs of Block
 * Hashes (i.e. each part with the part next to it) algorithm will get a whole
 * tree of hashes (this tree which is therefore a hashset made of all of the
 * other Block Hashes is called the AICH Hashset). Each hash which is neither
 * a Block Hash nor the Root Hash, is a Verifying Hash. The hash at the top
 * level is the Root Hash and it is supposed to be provided by the ed2k link
 * when releasing.
 */

#include "aich.h"
#include "util.h"
#include
#include
#include
#include

#if defined(USE_OPENSSL)
#define SHA1_INIT(ctx) ((pinit_t)ctx->sha1_methods.init)(&ctx->sha1_context)
#define SHA1_UPDATE(ctx, msg, size) ((pupdate_t)ctx->sha1_methods.update)(&ctx->sha1_context, (msg), (size))
#define SHA1_FINAL(ctx, result) ((pfinal_t)ctx->sha1_methods.final)(&ctx->sha1_context, (result))
#else
# define SHA1_INIT(ctx) rhash_sha1_init(&ctx->sha1_context)
# define SHA1_UPDATE(ctx, msg, size) rhash_sha1_update(&ctx->sha1_context, (msg), (size))
# define SHA1_FINAL(ctx, result) rhash_sha1_final(&ctx->sha1_context, (result))
#endif

#define ED2K_CHUNK_SIZE  9728000
#define FULL_BLOCK_SIZE  184320
#define LAST_BLOCK_SIZE  143360
#define BLOCKS_PER_CHUNK 53
#define BLOCK_HASHES_SIZE (BLOCKS_PER_CHUNK * sha1_hash_size)

/*
 * AICH algorithm could be implemented a bit faster if it knows
 * a hashed message size beforehand. It would allow
 * to build balanced tree while hashing the message.
 *
 * This AICH implementation works with unknown
 * message size like other well-known hash algorithms.
 * So, it just stores sha1 hashes and builds balanced tree
 * only on the last step, when the full message processed
 * and its size got to be known.
 */

/**
 * Initialize algorithm context before calculating hash.
 *
 * @param ctx context to initialize
 */
void rhash_aich_init(aich_ctx* ctx)
{
	memset(ctx, 0, sizeof(aich_ctx));

#if defined(USE_OPENSSL)
	assert(rhash_info_table[3].info->hash_id == RHASH_SHA1);
	assert(rhash_info_table[3].context_size <= (sizeof(sha1_ctx) + sizeof(unsigned long)));
	rhash_load_sha1_methods(&ctx->sha1_methods, METHODS_SELECTED);
#endif

	SHA1_INIT(ctx);
}

/* define macrosses to access chunk table */
#define CT_BITS 8
#define CT_GROUP_SIZE (1 << CT_BITS)
typedef unsigned char hash_pair_t[2][sha1_hash_size];
typedef hash_pair_t hash_pairs_group_t[CT_GROUP_SIZE];

#define CT_INDEX(chunk_num) ((chunk_num) & (CT_GROUP_SIZE - 1))
#define GET_HASH_PAIR(ctx, chunk_num) \
	(((hash_pair_t*)(ctx->chunk_table[chunk_num >> CT_BITS]))[CT_INDEX(chunk_num)])

/**
 * Resize the table if needed to ensure it contains space for given chunk_num.
 * and allocate hash_pairs_group_t element at this index.
 *
 * @param ctx algorithm context
 * @param chunk_num the number of chunks required
 */
static void rhash_aich_chunk_table_extend(aich_ctx* ctx, unsigned chunk_num)
{
	unsigned index = (chunk_num >> CT_BITS);
	assert(CT_INDEX(chunk_num) == 0);
	RHASH_ASSERT(sizeof(hash_pair_t) == 40);
	RHASH_ASSERT(sizeof(hash_pairs_group_t) == (40 * CT_GROUP_SIZE)); /* 10KiB */
	RHASH_ASSERT(CT_GROUP_SIZE == 256);

	/* check main assumptions */
	assert(ctx->chunk_table == 0 || ctx->chunk_table[index - 1] != 0); /* table is empty or full */
	assert(index <= ctx->allocated);

	/* check if there is enough space allocated */
	if (index >= ctx->allocated) {
		/* resize the table by allocating some extra space */
		size_t new_size = (ctx->allocated == 0 ? 64 : ctx->allocated * 2);
		void** new_block;
		assert(index == ctx->allocated);

		/* re-size the chunk table to new_size */
		new_block = (void**)realloc(ctx->chunk_table, new_size * sizeof(void*));
		if (new_block == 0) {
			free(ctx->chunk_table);
			ctx->chunk_table = 0;
			ctx->error = 1;
			return;
		}

		memset(new_block + ctx->allocated, 0, (new_size - ctx->allocated) * sizeof(void*));
		ctx->chunk_table = new_block;
		ctx->allocated = new_size;
	}

	/* add new hash_pairs_group_t block to the table */
	assert(index < ctx->allocated);
	assert(ctx->chunk_table != 0);
	assert(ctx->chunk_table[index] == 0);

	ctx->chunk_table[index] = malloc(sizeof(hash_pairs_group_t));
	if (ctx->chunk_table[index] == 0)
		ctx->error = 1;
}

/**
 * Free dynamically allocated memory for internal structures
 * used by hashing algorithm.
 *
 * @param ctx AICH algorithm context to cleanup
 */
void rhash_aich_cleanup(aich_ctx* ctx)
{
	size_t i;
	size_t table_size = (ctx->chunks_count + CT_GROUP_SIZE - 1) / CT_GROUP_SIZE;

	if (ctx->chunk_table != 0) {
		assert(table_size <= ctx->allocated);
		assert(table_size == ctx->allocated || ctx->chunk_table[table_size] == 0);
		for (i = 0;  i < table_size; i++)
			free(ctx->chunk_table[i]);
		free(ctx->chunk_table);
		ctx->chunk_table = 0;
	}

	free(ctx->block_hashes);
	ctx->block_hashes = 0;
}

#define AICH_HASH_FULL_TREE 0
#define AICH_HASH_LEFT_BRANCH 1
#define AICH_HASH_RIGHT_BRANCH 2

/**
 * Calculate an AICH tree hash, based ether on hashes of 180KB parts
 * (for an ed2k chunk) or on stored ed2k chunks (for the whole tree hash).
 *
 * @param ctx algorithm context
 * @param result pointer to receive calculated tree hash
 * @param type the type of hash to calculate, can be one of constants
 *   AICH_HASH_LEFT_BRANCH, AICH_HASH_RIGHT_BRANCH or AICH_HASH_FULL_TREE.
 */
static void rhash_aich_hash_tree(aich_ctx* ctx, unsigned char* result, int type)
{
	unsigned index = 0; /* leaf index */
	unsigned blocks;
	int      level = 0;
	unsigned is_left_branch = (type == AICH_HASH_RIGHT_BRANCH ? 0x0 : 0x1);
	uint64_t path  = is_left_branch;
	unsigned blocks_stack[56];
	unsigned char sha1_stack[56][sha1_hash_size];

	if (ctx->error)
		return;
	assert(ctx->index <= ED2K_CHUNK_SIZE);
	assert(type == AICH_HASH_FULL_TREE ? ctx->chunk_table != 0 : ctx->block_hashes != 0);

	/* calculate number of leafs in the tree */
	blocks_stack[0] = blocks = (unsigned)(type == AICH_HASH_FULL_TREE ?
		ctx->chunks_count : (ctx->index + FULL_BLOCK_SIZE - 1) / FULL_BLOCK_SIZE);

	while (1) {
		unsigned char sha1_message[sha1_hash_size];
		unsigned char* leaf_hash;

		/* go into the left branches until a leaf block is reached */
		while (blocks > 1) {
			/* step down into the left branch */
			blocks = (blocks + ((unsigned)path & 0x1)) / 2;
			level++;
			assert(level < 56); /* assumption filesize < (2^56 * 9MiB) */
			blocks_stack[level] = blocks;
			path = (path << 1) | 0x1; /* mark branch as left */
		}

		/* read a leaf hash */
		leaf_hash = &(ctx->block_hashes[index][0]);

		if (type == AICH_HASH_FULL_TREE) {
			is_left_branch = (unsigned)path & 0x1;

			leaf_hash = GET_HASH_PAIR(ctx, index)[is_left_branch];
		}
		index++;

		/* climb up the tree until a left branch is reached */
		for (; level > 0 && (path & 0x01) == 0; path >>= 1) {
			SHA1_INIT(ctx);
			SHA1_UPDATE(ctx, sha1_stack[level], sha1_hash_size);
			SHA1_UPDATE(ctx, leaf_hash, sha1_hash_size);
			SHA1_FINAL(ctx, sha1_message);
			leaf_hash = sha1_message;
			level--;
		}
		memcpy((level > 0 ? sha1_stack[level] : result), leaf_hash, 20);

		if (level == 0) break;

		/* jump at the current level from left to right branch */
		path &= ~0x1; /* mark branch as right */
		is_left_branch = ((unsigned)path >> 1) & 1;

		/* calculate number of blocks at right branch of the current level */
		blocks_stack[level] =
			(blocks_stack[level - 1] + 1 - is_left_branch) / 2;
		blocks = blocks_stack[level];
	}
}

#define AICH_PROCESS_FINAL_BLOCK 1
#define AICH_PROCESS_FLUSH_BLOCK 2

/**
 * Calculate and store a hash for a 180K/140K block.
 * Also, if it is the last block of a 9.2MiB ed2k chunk or of the hashed message,
 * then also calculate the AICH tree-hash of the current ed2k chunk.
 *
 * @param ctx algorithm context
 * @param type the actions to take, can be combination of bits AICH_PROCESS_FINAL_BLOCK
 *             and AICH_PROCESS_FLUSH_BLOCK
 */
static void rhash_aich_process_block(aich_ctx* ctx, int type)
{
	assert(type != 0);
	assert(ctx->index <= ED2K_CHUNK_SIZE);

	/* if there is unprocessed data left in the current 180K block. */
	if ((type & AICH_PROCESS_FLUSH_BLOCK) != 0)
	{
		/* ensure that the block_hashes array is allocated to save the result */
		if (ctx->block_hashes == NULL) {
			ctx->block_hashes = (unsigned char (*)[sha1_hash_size])malloc(BLOCK_HASHES_SIZE);
			if (ctx->block_hashes == NULL) {
				ctx->error = 1;
				return;
			}
		}

		/* store the 180-KiB block hash to the block_hashes array */
		assert(((ctx->index - 1) / FULL_BLOCK_SIZE) < BLOCKS_PER_CHUNK);
		SHA1_FINAL(ctx, ctx->block_hashes[(ctx->index - 1) / FULL_BLOCK_SIZE]);
	}

	/* check, if it's time to calculate the tree hash for the current ed2k chunk */
	if (ctx->index >= ED2K_CHUNK_SIZE || (type & AICH_PROCESS_FINAL_BLOCK)) {
		unsigned char (*pair)[sha1_hash_size];

		/* ensure, that we have the space to store tree hash */
		if (CT_INDEX(ctx->chunks_count) == 0) {
			rhash_aich_chunk_table_extend(ctx, (unsigned)ctx->chunks_count);
			if (ctx->error)
				return;
		}
		assert(ctx->chunk_table  != 0);
		assert(ctx->block_hashes != 0);

		/* calculate tree hash and save results to chunk_table */
		pair = GET_HASH_PAIR(ctx, ctx->chunks_count);

		/* small optimization: skip a left-branch-hash for the last chunk */
		if (!(type & AICH_PROCESS_FINAL_BLOCK) || ctx->chunks_count == 0) {
			/* calculate a tree hash to be used in left branch */
			rhash_aich_hash_tree(ctx, pair[1], AICH_HASH_LEFT_BRANCH);
		}

		/* small optimization: skip right-branch-hash for the very first chunk */
		if (ctx->chunks_count > 0) {
			/* calculate a tree hash to be used in right branch */
			rhash_aich_hash_tree(ctx, pair[0], AICH_HASH_RIGHT_BRANCH);
		}

		ctx->index = 0; /* mark that the entire ed2k chunk has been processed */
		ctx->chunks_count++;
	}
}

/**
 * Calculate message hash.
 * Can be called repeatedly with chunks of the message to be hashed.
 *
 * @param ctx the algorithm context containing current hashing state
 * @param msg message chunk
 * @param size length of the message chunk
 */
void rhash_aich_update(aich_ctx* ctx, const unsigned char* msg, size_t size)
{
	if (ctx->error)
		return;
	while (size > 0) {
		unsigned left_in_chunk = ED2K_CHUNK_SIZE - ctx->index;
		unsigned block_left = (left_in_chunk <= LAST_BLOCK_SIZE ? left_in_chunk :
			FULL_BLOCK_SIZE - ctx->index % FULL_BLOCK_SIZE);
		assert(block_left > 0);

		if (size >= block_left) {
			SHA1_UPDATE(ctx, msg, block_left);
			msg  += block_left;
			size -= block_left;
			ctx->index += block_left;

			/* process a 180KiB-blok */
			rhash_aich_process_block(ctx, AICH_PROCESS_FLUSH_BLOCK);
			SHA1_INIT(ctx);
		} else {
			/* add to a leaf block */
			SHA1_UPDATE(ctx, msg, size);
			ctx->index += (unsigned)size;
			break;
		}
	}
	assert(ctx->index < ED2K_CHUNK_SIZE);
}

/**
 * Store calculated hash into the given array.
 *
 * @param ctx the algorithm context containing current hashing state
 * @param result calculated hash in binary form
 */
void rhash_aich_final(aich_ctx* ctx, unsigned char result[20])
{
	uint64_t total_size =
		((uint64_t)ctx->chunks_count * ED2K_CHUNK_SIZE) + ctx->index;
	unsigned char* const hash = (unsigned char*)ctx->sha1_context.hash;

	if (ctx->chunks_count == 0 && ctx->block_hashes == NULL) {
		assert(ctx->index < FULL_BLOCK_SIZE);
#if defined(USE_OPENSSL)
		SHA1_FINAL(ctx, hash); /* return just sha1 hash */
#else
		SHA1_FINAL(ctx, 0); /* return just sha1 hash */
#if IS_LITTLE_ENDIAN
		rhash_u32_mem_swap(ctx->sha1_context.hash, 5);
#endif
#endif
		if (result) memcpy(result, hash, sha1_hash_size);
		return;
	}

	/* if there is unprocessed data left in the last 180K block */
	if ((ctx->index % FULL_BLOCK_SIZE) > 0) {
		/* then process the last block */
		rhash_aich_process_block(ctx, ctx->block_hashes != NULL ?
			AICH_PROCESS_FINAL_BLOCK | AICH_PROCESS_FLUSH_BLOCK : AICH_PROCESS_FLUSH_BLOCK);
	}

	/* if processed message was shorter than a ed2k chunk */
	if (ctx->chunks_count == 0) {
		/* then return the aich hash for the first chunk */
		rhash_aich_hash_tree(ctx, hash, AICH_HASH_LEFT_BRANCH);
	} else {
		if (ctx->index > 0) {
			/* process the last block of the message */
			rhash_aich_process_block(ctx, AICH_PROCESS_FINAL_BLOCK);
		}
		assert(ctx->chunks_count > 0);
		assert(ctx->block_hashes != NULL);

		rhash_aich_hash_tree(ctx, hash, AICH_HASH_FULL_TREE);
	}

	rhash_aich_cleanup(ctx);
	ctx->sha1_context.length = total_size; /* store total message size  */
	if (result) memcpy(result, hash, sha1_hash_size);
}

#if !defined(NO_IMPORT_EXPORT)
# define AICH_CTX_OSSL_FLAG 0x10

/**
 * Export aich context to a memory region, or calculate the
 * size required for context export.
 *
 * @param ctx the algorithm context containing current hashing state
 * @param out pointer to the memory region or NULL
 * @param size size of memory region
 * @return the size of the exported data on success, 0 on fail.
 */
size_t rhash_aich_export(const aich_ctx* ctx, void* out, size_t size)
{
	const size_t head_size = sizeof(size_t);
	const size_t ctx_head_size = offsetof(aich_ctx, block_hashes);
	const size_t block_hashes_size = (ctx->block_hashes ? BLOCK_HASHES_SIZE : 0);
	const size_t chunk_table_size = sizeof(hash_pair_t) * ctx->chunks_count;
	const size_t exported_size = head_size + ctx_head_size + block_hashes_size + chunk_table_size;
	char* out_ptr = (char*)out;
	if (!out)
		return exported_size;
	if (size < exported_size)
		return 0;
	*(size_t*)out_ptr = sizeof(aich_ctx);
	out_ptr += head_size;
	memcpy(out_ptr, ctx, ctx_head_size);
	out_ptr += ctx_head_size;
	if (ctx->block_hashes) {
		memcpy(out_ptr, ctx->block_hashes, BLOCK_HASHES_SIZE);
		out_ptr += BLOCK_HASHES_SIZE;
	}
	if (chunk_table_size > 0) {
		size_t left_size = chunk_table_size;
		size_t index;
		assert(ctx->chunk_table != NULL);
		for (index = 0; left_size > 0; index++) {
			size_t group_size = (left_size < sizeof(hash_pairs_group_t) ?
				left_size : sizeof(hash_pairs_group_t));
			memcpy(out_ptr, ctx->chunk_table[index], group_size);
			out_ptr += group_size;
			left_size -= group_size;
		}
		assert(left_size == 0);
	}
	assert(!out || (size_t)(out_ptr - (char*)out) == exported_size);
#if defined(USE_OPENSSL)
	if (out_ptr && ARE_OPENSSL_METHODS(ctx->sha1_methods)) {
		int* error_ptr = (int*)((char*)out + head_size + offsetof(aich_ctx, error));
		*error_ptr |= AICH_CTX_OSSL_FLAG;
		RHASH_ASSERT(sizeof(*error_ptr) == sizeof(ctx->error));
	}
#endif
	return exported_size;
}

/**
 * Import aich context from a memory region.
 *
 * @param ctx pointer to the algorithm context
 * @param in pointer to the data to import
 * @param size size of data to import
 * @return the size of the imported data on success, 0 on fail.
 */
size_t rhash_aich_import(aich_ctx* ctx, const void* in, size_t size)
{
	const size_t head_size = sizeof(size_t);
	const size_t ctx_head_size = offsetof(aich_ctx, block_hashes);
	const char* in_ptr = (const char*)in;
	size_t imported_size = head_size + ctx_head_size;
	size_t block_hashes_size;
	size_t chunk_table_size;
	if (size < imported_size)
		return 0;
	if(*(size_t*)in_ptr != sizeof(aich_ctx))
		return 0;
	in_ptr += head_size;
	memset(ctx, 0, sizeof(aich_ctx));
	memcpy(ctx, in_ptr, ctx_head_size);
	in_ptr += ctx_head_size;
	block_hashes_size = (ctx->block_hashes ? BLOCK_HASHES_SIZE : 0);
	chunk_table_size = sizeof(hash_pair_t) * ctx->chunks_count;
	imported_size += block_hashes_size + chunk_table_size;
	if (size < imported_size)
		return 0;
	if (ctx->block_hashes != NULL) {
		ctx->block_hashes = (unsigned char (*)[sha1_hash_size])malloc(BLOCK_HASHES_SIZE);
		if (!ctx->block_hashes)
			return 0;
		memcpy(ctx->block_hashes, in_ptr, BLOCK_HASHES_SIZE);
		in_ptr += BLOCK_HASHES_SIZE;
	}
	if (ctx->allocated > 0) {
		size_t index;
		ctx->chunk_table = (void**)malloc(ctx->allocated * sizeof(void*));
		if (!ctx->chunk_table) {
			ctx->error = 1;
			return 0;
		}
		memset(ctx->chunk_table, 0, ctx->allocated * sizeof(void*));
		for (index = 0; chunk_table_size > 0; index++) {
			size_t group_size = (chunk_table_size < sizeof(hash_pairs_group_t) ?
				chunk_table_size : sizeof(hash_pairs_group_t));
			assert(index < ctx->allocated);
			ctx->chunk_table[index] = malloc(sizeof(hash_pairs_group_t));
			if (ctx->chunk_table[index] == 0) {
				ctx->error = 1;
				return 0;
			}
			memcpy(ctx->chunk_table[index], in_ptr, group_size);
			chunk_table_size -= group_size;
			in_ptr += group_size;
		}
	}
	assert((size_t)(in_ptr - (char*)in) == imported_size);
#if defined(USE_OPENSSL)
	if ((ctx->error & AICH_CTX_OSSL_FLAG) != 0) {
		ctx->error &= ~AICH_CTX_OSSL_FLAG;
		rhash_load_sha1_methods(&ctx->sha1_methods, METHODS_OPENSSL);
	} else {
		rhash_load_sha1_methods(&ctx->sha1_methods, METHODS_RHASH);
	}
#endif
	return imported_size;
}
#endif /* !defined(NO_IMPORT_EXPORT) */