File Coverage

_aich.c
Criterion Covered Total %
statement 32 134 23.8
branch 11 122 9.0
condition n/a
subroutine n/a
pod n/a
total 43 256 16.8


line stmt bran cond sub pod time code
1             /* aich.c - an implementation of EMule AICH Algorithm.
2             * Description: http://www.amule.org/wiki/index.php/AICH.
3             *
4             * Copyright (c) 2008, Aleksey Kravchenko
5             *
6             * Permission to use, copy, modify, and/or distribute this software for any
7             * purpose with or without fee is hereby granted.
8             *
9             * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
10             * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
11             * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
12             * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
13             * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
14             * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15             * PERFORMANCE OF THIS SOFTWARE.
16             *
17             * The AICH Algorithm:
18             *
19             * Each ed2k chunk (9728000 bytes) is divided into 53 parts (52x 180KB and
20             * 1x 140KB) and each of these parts are hashed using the SHA1 algorithm.
21             * Each of these hashes is called a Block Hash. By combining pairs of Block
22             * Hashes (i.e. each part with the part next to it) algorithm will get a whole
23             * tree of hashes (this tree which is therefore a hashset made of all of the
24             * other Block Hashes is called the AICH Hashset). Each hash which is neither
25             * a Block Hash nor the Root Hash, is a Verifying Hash. The hash at the top
26             * level is the Root Hash and it is supposed to be provided by the ed2k link
27             * when releasing.
28             */
29              
30             #include
31             #include
32             #include
33             #include "byte_order.h"
34             #include "algorithms.h"
35             #include "aich.h"
36              
37             #define ED2K_CHUNK_SIZE 9728000
38             #define FULL_BLOCK_SIZE 184320
39             #define LAST_BLOCK_SIZE 143360
40             #define BLOCKS_PER_CHUNK 53
41              
42             /*
43             * The Algorithm could be a little faster if it knows a
44             * hashed message size beforehand. This would allow
45             * to build balanced tree while hashing the message.
46             *
47             * But this AICH implementation works with unknown
48             * message size like other well-known hash algorithms
49             * (it was fun to write a such one).
50             * So, it just stores sha1 hashes and builds balanced tree
51             * only on the last step, when the full message processed
52             * and its size is already known.
53             */
54              
55             #ifdef USE_OPENSSL
56             #define SHA1_INIT(ctx) ((pinit_t)ctx->sha_init)(&ctx->sha1_context)
57             #define SHA1_UPDATE(ctx, msg, size) ((pupdate_t)ctx->sha_update)(&ctx->sha1_context, (msg), (size))
58             #define SHA1_FINAL(ctx, result) ((pfinal_t)ctx->sha_final)(&ctx->sha1_context, (result))
59             #else
60             #define SHA1_INIT(ctx) rhash_sha1_init(&ctx->sha1_context)
61             #define SHA1_UPDATE(ctx, msg, size) rhash_sha1_update(&ctx->sha1_context, (msg), (size))
62             #define SHA1_FINAL(ctx, result) rhash_sha1_final(&ctx->sha1_context, (result))
63             #endif
64              
65             /**
66             * Initialize algorithm context before calculaing hash.
67             *
68             * @param ctx context to initialize
69             */
70 2           void rhash_aich_init(aich_ctx* ctx)
71             {
72 2           memset(ctx, 0, sizeof(aich_ctx));
73              
74             #ifdef USE_OPENSSL
75             {
76             rhash_hash_info* sha1_info = &rhash_info_table[3];
77             assert(sha1_info->info->hash_id == RHASH_SHA1);
78             assert(sha1_info->context_size <= (sizeof(sha1_ctx) + sizeof(unsigned long)));
79             ctx->sha_init = sha1_info->init;
80             ctx->sha_update = sha1_info->update;
81             ctx->sha_final = sha1_info->final;
82             }
83             #endif
84              
85 2           SHA1_INIT(ctx);
86 2           }
87              
88             /* define macrosses to access chunk table */
89             #define CT_BITS 8
90             #define CT_GROUP_SIZE (1 << CT_BITS)
91             typedef unsigned char hash_pair_t[2][sha1_hash_size];
92             typedef hash_pair_t hash_pairs_group_t[CT_GROUP_SIZE];
93              
94             #define CT_INDEX(chunk_num) ((chunk_num) & (CT_GROUP_SIZE - 1))
95             #define GET_HASH_PAIR(ctx, chunk_num) \
96             (((hash_pair_t*)(ctx->chunk_table[chunk_num >> CT_BITS]))[CT_INDEX(chunk_num)])
97              
98             /**
99             * Resize the table if needed to ensure it contains space for given chunk_num.
100             * and allocate hash_pairs_group_t element at this index.
101             *
102             * @param ctx algorithm context
103             * @param chunk_num the number of chunks required
104             */
105 0           static void rhash_aich_chunk_table_extend(aich_ctx* ctx, unsigned chunk_num)
106             {
107 0           unsigned index = (chunk_num >> CT_BITS);
108             assert(sizeof(hash_pair_t) == 40);
109             assert(sizeof(hash_pairs_group_t) == (40 * CT_GROUP_SIZE)); /* 10KiB */
110             assert(CT_GROUP_SIZE == 256);
111 0 0         assert(CT_INDEX(chunk_num) == 0);
112              
113             /* check main assumptions */
114 0 0         assert(ctx->chunk_table == 0 || ctx->chunk_table[index - 1] != 0); /* table is empty or full */
    0          
115 0 0         assert(index <= ctx->allocated);
116              
117             /* check if there is enough space allocated */
118 0 0         if (index >= ctx->allocated) {
119             /* resize the table by allocating some extra space */
120 0 0         size_t new_size = (ctx->allocated == 0 ? 64 : ctx->allocated * 2);
121 0 0         assert(index == ctx->allocated);
122              
123             /* re-allocate the chunk table to contain new_size void*-pointers */
124 0           ctx->chunk_table = (void**)realloc(ctx->chunk_table, new_size * sizeof(void*));
125 0 0         if (ctx->chunk_table == 0) {
126 0           ctx->error = 1;
127 0           return;
128             }
129              
130 0           memset(ctx->chunk_table + ctx->allocated, 0, (new_size - ctx->allocated) * sizeof(void*));
131 0           ctx->allocated = new_size;
132             }
133              
134             /* add new hash_pairs_group_t block to the table */
135 0 0         assert(index < ctx->allocated);
136 0 0         assert(ctx->chunk_table != 0);
137 0 0         assert(ctx->chunk_table[index] == 0);
138              
139 0           ctx->chunk_table[index] = malloc(sizeof(hash_pairs_group_t));
140 0 0         if (ctx->chunk_table[index] == 0) ctx->error = 1;
141             }
142              
143             /**
144             * Free dynamically allocated memory for internal structures
145             * used by hashing algorithm.
146             *
147             * @param ctx AICH algorithm context to cleanup
148             */
149 1           void rhash_aich_cleanup(aich_ctx* ctx)
150             {
151             size_t i;
152 1           size_t table_size = (ctx->chunks_number + CT_GROUP_SIZE - 1) / CT_GROUP_SIZE;
153              
154 1 50         if (ctx->chunk_table != 0) {
155 0 0         assert(table_size <= ctx->allocated);
156 0 0         assert(table_size == ctx->allocated || ctx->chunk_table[table_size] == 0);
    0          
157 0 0         for (i = 0; i < table_size; i++) free(ctx->chunk_table[i]);
158 0           free(ctx->chunk_table);
159 0           ctx->chunk_table = 0;
160             }
161              
162 1           free(ctx->block_hashes);
163 1           ctx->block_hashes = 0;
164 1           }
165              
166             #define AICH_HASH_FULL_TREE 0
167             #define AICH_HASH_LEFT_BRANCH 1
168             #define AICH_HASH_RIGHT_BRANCH 2
169              
170             /**
171             * Calculate an AICH tree hash, based ether on hashes of 180KB parts
172             * (for an ed2k chunk) or on stored ed2k chunks (for the whole tree hash).
173             *
174             * @param ctx algorithm context
175             * @param result pointer to receive calculated tree hash
176             * @param type the type of hash to calculate, can be one of constants
177             * AICH_HASH_LEFT_BRANCH, AICH_HASH_RIGHT_BRANCH or AICH_HASH_FULL_TREE.
178             */
179 0           static void rhash_aich_hash_tree(aich_ctx* ctx, unsigned char* result, int type)
180             {
181 0           unsigned index = 0; /* leaf index */
182             unsigned blocks;
183 0           int level = 0;
184 0           unsigned is_left_branch = (type == AICH_HASH_RIGHT_BRANCH ? 0x0 : 0x1);
185 0           uint64_t path = is_left_branch;
186             unsigned blocks_stack[56];
187             unsigned char sha1_stack[56][sha1_hash_size];
188              
189 0 0         if (ctx->error) return;
190 0 0         assert(ctx->index <= ED2K_CHUNK_SIZE);
191 0 0         assert(type == AICH_HASH_FULL_TREE ? ctx->chunk_table != 0 : ctx->block_hashes != 0);
    0          
192              
193             /* calculate number of leafs in the tree */
194 0 0         blocks_stack[0] = blocks = (unsigned)(type == AICH_HASH_FULL_TREE ?
195 0           ctx->chunks_number : (ctx->index + FULL_BLOCK_SIZE - 1) / FULL_BLOCK_SIZE);
196              
197             while (1) {
198             unsigned char sha1_message[sha1_hash_size];
199             unsigned char* leaf_hash;
200              
201             /* go into the left branches until a leaf block is reached */
202 0 0         while (blocks > 1) {
203             /* step down into the left branch */
204 0           blocks = (blocks + ((unsigned)path & 0x1)) / 2;
205 0           level++;
206 0 0         assert(level < 56); /* assumption filesize < (2^56 * 9MiB) */
207 0           blocks_stack[level] = blocks;
208 0           path = (path << 1) | 0x1; /* mark branch as left */
209             }
210              
211             /* read a leaf hash */
212 0           leaf_hash = &(ctx->block_hashes[index][0]);
213              
214 0 0         if (type == AICH_HASH_FULL_TREE) {
215 0           is_left_branch = (unsigned)path & 0x1;
216              
217 0           leaf_hash = GET_HASH_PAIR(ctx, index)[is_left_branch];
218             }
219 0           index++;
220              
221             /* climb up the tree until a left branch is reached */
222 0 0         for (; level > 0 && (path & 0x01) == 0; path >>= 1) {
    0          
223 0           SHA1_INIT(ctx);
224 0           SHA1_UPDATE(ctx, sha1_stack[level], sha1_hash_size);
225 0           SHA1_UPDATE(ctx, leaf_hash, sha1_hash_size);
226 0           SHA1_FINAL(ctx, sha1_message);
227 0           leaf_hash = sha1_message;
228 0           level--;
229             }
230 0 0         memcpy((level > 0 ? sha1_stack[level] : result), leaf_hash, 20);
231              
232 0 0         if (level == 0) break;
233              
234             /* jump at the current level from left to right branch */
235 0           path &= ~0x1; /* mark branch as right */
236 0           is_left_branch = ((unsigned)path >> 1) & 1;
237              
238             /* calculate number of blocks at right branch of the current level */
239 0           blocks_stack[level] =
240 0           (blocks_stack[level - 1] + 1 - is_left_branch) / 2;
241 0           blocks = blocks_stack[level];
242 0           }
243             }
244              
245             #define AICH_PROCESS_FINAL_BLOCK 1
246             #define AICH_PROCESS_FLUSH_BLOCK 2
247              
248             /**
249             * Calculate and store a hash for a 180K/140K block.
250             * Also, if it is the last block of a 9.2MiB ed2k chunk or of the hashed message,
251             * then also calculate the AICH tree-hash of the current ed2k chunk.
252             *
253             * @param ctx algorithm context
254             * @param type the actions to take, can be combination of bits AICH_PROCESS_FINAL_BLOCK
255             * and AICH_PROCESS_FLUSH_BLOCK
256             */
257 0           static void rhash_aich_process_block(aich_ctx* ctx, int type)
258             {
259 0 0         assert(type != 0);
260 0 0         assert(ctx->index <= ED2K_CHUNK_SIZE);
261              
262             /* if there is unprocessed data left in the current 180K block. */
263 0 0         if ((type & AICH_PROCESS_FLUSH_BLOCK) != 0)
264             {
265             /* ensure that the block_hashes array is allocated to save the result */
266 0 0         if (ctx->block_hashes == NULL) {
267 0           ctx->block_hashes = (unsigned char (*)[sha1_hash_size])malloc(BLOCKS_PER_CHUNK * sha1_hash_size);
268 0 0         if (ctx->block_hashes == NULL) {
269 0           ctx->error = 1;
270 0           return;
271             }
272             }
273              
274             /* store the 180-KiB block hash to the block_hashes array */
275 0 0         assert(((ctx->index - 1) / FULL_BLOCK_SIZE) < BLOCKS_PER_CHUNK);
276 0           SHA1_FINAL(ctx, ctx->block_hashes[(ctx->index - 1) / FULL_BLOCK_SIZE]);
277             }
278              
279             /* check, if it's time to calculate the tree hash for the current ed2k chunk */
280 0 0         if (ctx->index >= ED2K_CHUNK_SIZE || (type & AICH_PROCESS_FINAL_BLOCK)) {
    0          
281             unsigned char (*pair)[sha1_hash_size];
282              
283             /* ensure, that we have the space to store tree hash */
284 0 0         if (CT_INDEX(ctx->chunks_number) == 0) {
285 0           rhash_aich_chunk_table_extend(ctx, (unsigned)ctx->chunks_number);
286 0 0         if (ctx->error) return;
287             }
288 0 0         assert(ctx->chunk_table != 0);
289 0 0         assert(ctx->block_hashes != 0);
290              
291             /* calculate tree hash and save results to chunk_table */
292 0           pair = GET_HASH_PAIR(ctx, ctx->chunks_number);
293              
294             /* small optimization: skip a left-branch-hash for the last chunk */
295 0 0         if (!(type & AICH_PROCESS_FINAL_BLOCK) || ctx->chunks_number == 0) {
    0          
296             /* calculate a tree hash to be used in left branch */
297 0           rhash_aich_hash_tree(ctx, pair[1], AICH_HASH_LEFT_BRANCH);
298             }
299              
300             /* small optimization: skip right-branch-hash for the very first chunk */
301 0 0         if (ctx->chunks_number > 0) {
302             /* calculate a tree hash to be used in right branch */
303 0           rhash_aich_hash_tree(ctx, pair[0], AICH_HASH_RIGHT_BRANCH);
304             }
305              
306 0           ctx->index = 0; /* mark that the whole ed2k chunk was processed */
307 0           ctx->chunks_number++;
308             }
309             }
310              
311             /**
312             * Calculate message hash.
313             * Can be called repeatedly with chunks of the message to be hashed.
314             *
315             * @param ctx the algorithm context containing current hashing state
316             * @param msg message chunk
317             * @param size length of the message chunk
318             */
319 2           void rhash_aich_update(aich_ctx* ctx, const unsigned char* msg, size_t size)
320             {
321 2 50         if (ctx->error) return;
322              
323 2 50         while (size > 0) {
324 2           unsigned left_in_chunk = ED2K_CHUNK_SIZE - ctx->index;
325 2 50         unsigned block_left = (left_in_chunk <= LAST_BLOCK_SIZE ? left_in_chunk :
326 2           FULL_BLOCK_SIZE - ctx->index % FULL_BLOCK_SIZE);
327 2 50         assert(block_left > 0);
328              
329 2 50         if (size >= block_left) {
330 0           SHA1_UPDATE(ctx, msg, block_left);
331 0           msg += block_left;
332 0           size -= block_left;
333 0           ctx->index += block_left;
334              
335             /* process a 180KiB-blok */
336 0           rhash_aich_process_block(ctx, AICH_PROCESS_FLUSH_BLOCK);
337 0           SHA1_INIT(ctx);
338             } else {
339             /* add to a leaf block */
340 2           SHA1_UPDATE(ctx, msg, size);
341 2           ctx->index += (unsigned)size;
342 2           break;
343             }
344             }
345 2 50         assert(ctx->index < ED2K_CHUNK_SIZE);
346             }
347              
348             /**
349             * Store calculated hash into the given array.
350             *
351             * @param ctx the algorithm context containing current hashing state
352             * @param result calculated hash in binary form
353             */
354 2           void rhash_aich_final(aich_ctx* ctx, unsigned char result[20])
355             {
356 2           uint64_t total_size =
357 2           ((uint64_t)ctx->chunks_number * ED2K_CHUNK_SIZE) + ctx->index;
358 2           unsigned char* const hash = (unsigned char*)ctx->sha1_context.hash;
359              
360 2 50         if (ctx->chunks_number == 0 && ctx->block_hashes == NULL) {
    50          
361 2 50         assert(ctx->index < FULL_BLOCK_SIZE);
362             #ifdef USE_OPENSSL
363             SHA1_FINAL(ctx, hash); /* return just sha1 hash */
364             #else
365 2           SHA1_FINAL(ctx, 0); /* return just sha1 hash */
366             #if IS_LITTLE_ENDIAN
367 2           rhash_u32_mem_swap(ctx->sha1_context.hash, 5);
368             #endif
369             #endif
370 2 50         if (result) memcpy(result, hash, sha1_hash_size);
371 2           return;
372             }
373              
374             /* if there is unprocessed data left in the last 180K block */
375 0 0         if ((ctx->index % FULL_BLOCK_SIZE) > 0) {
376             /* then process the last block */
377 0 0         rhash_aich_process_block(ctx, ctx->block_hashes != NULL ?
378             AICH_PROCESS_FINAL_BLOCK | AICH_PROCESS_FLUSH_BLOCK : AICH_PROCESS_FLUSH_BLOCK);
379             }
380              
381             /* if processed message was shorter than a ed2k chunk */
382 0 0         if (ctx->chunks_number == 0) {
383             /* then return the aich hash for the first chunk */
384 0           rhash_aich_hash_tree(ctx, hash, AICH_HASH_LEFT_BRANCH);
385             } else {
386 0 0         if (ctx->index > 0) {
387             /* process the last block of the message */
388 0           rhash_aich_process_block(ctx, AICH_PROCESS_FINAL_BLOCK);
389             }
390 0 0         assert(ctx->chunks_number > 0);
391 0 0         assert(ctx->block_hashes != NULL);
392              
393 0           rhash_aich_hash_tree(ctx, hash, AICH_HASH_FULL_TREE);
394             }
395              
396 0           rhash_aich_cleanup(ctx);
397 0           ctx->sha1_context.length = total_size; /* store total message size */
398 0 0         if (result) memcpy(result, hash, sha1_hash_size);
399             }