| 1 |
|
| /* tth.c - calculate TTH (Tiger Tree Hash) function. |
| 2 |
|
| * |
| 3 |
|
| * Copyright (c) 2007, Aleksey Kravchenko <rhash.admin@gmail.com> |
| 4 |
|
| * |
| 5 |
|
| * Permission to use, copy, modify, and/or distribute this software for any |
| 6 |
|
| * purpose with or without fee is hereby granted. |
| 7 |
|
| * |
| 8 |
|
| * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH |
| 9 |
|
| * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY |
| 10 |
|
| * AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, |
| 11 |
|
| * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM |
| 12 |
|
| * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE |
| 13 |
|
| * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR |
| 14 |
|
| * PERFORMANCE OF THIS SOFTWARE. |
| 15 |
|
| */ |
| 16 |
|
| |
| 17 |
|
| #include "tth.h" |
| 18 |
|
| #include "byte_order.h" |
| 19 |
|
| #include <stddef.h> |
| 20 |
|
| #include <string.h> |
| 21 |
|
| |
| 22 |
|
| /** |
| 23 |
|
| * Initialize context before calculating hash. |
| 24 |
|
| * |
| 25 |
|
| * @param ctx context to initialize |
| 26 |
|
| */ |
| 27 |
4 |
| void rhash_tth_init(tth_ctx* ctx) |
| 28 |
|
| { |
| 29 |
4 |
| rhash_tiger_init(&ctx->tiger); |
| 30 |
4 |
| ctx->tiger.message[ ctx->tiger.length++ ] = 0x00; |
| 31 |
4 |
| ctx->block_count = 0; |
| 32 |
4 |
| } |
| 33 |
|
| |
| 34 |
|
| /** |
| 35 |
|
| * The core transformation. |
| 36 |
|
| * |
| 37 |
|
| * @param ctx algorithm state |
| 38 |
|
| */ |
| 39 |
4 |
| static void rhash_tth_process_block(tth_ctx* ctx) |
| 40 |
|
| { |
| 41 |
|
| uint64_t it; |
| 42 |
4 |
| unsigned pos = 0; |
| 43 |
|
| unsigned char msg[24]; |
| 44 |
|
| |
| 45 |
4 |
▶ | for (it = 1; it & ctx->block_count; it <<= 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (it = 1; it & ctx->block_count; it <<= 1) { |
0 |
4 |
4 |
|
| 46 |
0 |
| rhash_tiger_final(&ctx->tiger, msg); |
| 47 |
0 |
| rhash_tiger_init(&ctx->tiger); |
| 48 |
0 |
| ctx->tiger.message[ctx->tiger.length++] = 0x01; |
| 49 |
0 |
| rhash_tiger_update(&ctx->tiger, (unsigned char*)(ctx->stack + pos), 24); |
| 50 |
|
| /* note: we can cut this step, if the previous rhash_tiger_final saves directly to ctx->tiger.message+25; */ |
| 51 |
0 |
| rhash_tiger_update(&ctx->tiger, msg, 24); |
| 52 |
0 |
| pos += 3; |
| 53 |
|
| } |
| 54 |
4 |
| rhash_tiger_final(&ctx->tiger, (unsigned char*)(ctx->stack + pos)); |
| 55 |
4 |
| ctx->block_count++; |
| 56 |
4 |
| } |
| 57 |
|
| |
| 58 |
|
| /** |
| 59 |
|
| * Calculate message hash. |
| 60 |
|
| * Can be called repeatedly with chunks of the message to be hashed. |
| 61 |
|
| * |
| 62 |
|
| * @param ctx the algorithm context containing current hashing state |
| 63 |
|
| * @param msg message chunk |
| 64 |
|
| * @param size length of the message chunk |
| 65 |
|
| */ |
| 66 |
3 |
| void rhash_tth_update(tth_ctx* ctx, const unsigned char* msg, size_t size) |
| 67 |
|
| { |
| 68 |
3 |
| size_t rest = 1025 - (size_t)ctx->tiger.length; |
| 69 |
|
| for (;;) { |
| 70 |
3 |
▶ | if (size < rest) rest = size; |
Branch: 1 branch
| Branch | True | False | Total |
| if (size < rest) rest = size; |
3 |
0 |
3 |
|
| 71 |
3 |
| rhash_tiger_update(&ctx->tiger, msg, rest); |
| 72 |
3 |
| msg += rest; |
| 73 |
3 |
| size -= rest; |
| 74 |
3 |
▶ | if (ctx->tiger.length < 1025) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (ctx->tiger.length < 1025) { |
3 |
0 |
3 |
|
| 75 |
3 |
| return; |
| 76 |
|
| } |
| 77 |
|
| |
| 78 |
|
| /* process block hash */ |
| 79 |
0 |
| rhash_tth_process_block(ctx); |
| 80 |
|
| |
| 81 |
|
| /* init block hash */ |
| 82 |
0 |
| rhash_tiger_init(&ctx->tiger); |
| 83 |
0 |
| ctx->tiger.message[ ctx->tiger.length++ ] = 0x00; |
| 84 |
0 |
| rest = 1024; |
| 85 |
|
| } |
| 86 |
|
| } |
| 87 |
|
| |
| 88 |
|
| /** |
| 89 |
|
| * Store calculated hash into the given array. |
| 90 |
|
| * |
| 91 |
|
| * @param ctx the algorithm context containing current hashing state |
| 92 |
|
| * @param result calculated hash in binary form |
| 93 |
|
| */ |
| 94 |
4 |
| void rhash_tth_final(tth_ctx* ctx, unsigned char result[24]) |
| 95 |
|
| { |
| 96 |
4 |
| uint64_t it = 1; |
| 97 |
4 |
| unsigned pos = 0; |
| 98 |
|
| unsigned char msg[24]; |
| 99 |
|
| const unsigned char* last_message; |
| 100 |
|
| |
| 101 |
|
| /* process the bytes left in the context buffer */ |
| 102 |
4 |
▶ | if (ctx->tiger.length > 1 || ctx->block_count == 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (ctx->tiger.length > 1 || ctx->block_count == 0) { |
1 |
3 |
4 |
| if (ctx->tiger.length > 1 || ctx->block_count == 0) { |
1 |
0 |
1 |
|
| 103 |
4 |
| rhash_tth_process_block(ctx); |
| 104 |
|
| } |
| 105 |
|
| |
| 106 |
4 |
▶ | for (; it < ctx->block_count && (it & ctx->block_count) == 0; it <<= 1) pos += 3; |
Branch: 2 branches
| Branch | True | False | Total |
| for (; it < ctx->block_count && (it & ctx->block_count) == 0; it <<= 1) pos += 3; |
0 |
4 |
4 |
| for (; it < ctx->block_count && (it & ctx->block_count) == 0; it <<= 1) pos += 3; |
0 |
0 |
0 |
|
| 107 |
4 |
| last_message = (unsigned char*)(ctx->stack + pos); |
| 108 |
|
| |
| 109 |
4 |
▶ | for (it <<= 1; it <= ctx->block_count; it <<= 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (it <<= 1; it <= ctx->block_count; it <<= 1) { |
0 |
4 |
4 |
|
| 110 |
|
| /* merge TTH sums in the tree */ |
| 111 |
0 |
| pos += 3; |
| 112 |
0 |
▶ | if (it & ctx->block_count) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (it & ctx->block_count) { |
0 |
0 |
0 |
|
| 113 |
0 |
| rhash_tiger_init(&ctx->tiger); |
| 114 |
0 |
| ctx->tiger.message[ ctx->tiger.length++ ] = 0x01; |
| 115 |
0 |
| rhash_tiger_update(&ctx->tiger, (unsigned char*)(ctx->stack + pos), 24); |
| 116 |
0 |
| rhash_tiger_update(&ctx->tiger, last_message, 24); |
| 117 |
|
| |
| 118 |
0 |
| rhash_tiger_final(&ctx->tiger, msg); |
| 119 |
0 |
| last_message = msg; |
| 120 |
|
| } |
| 121 |
|
| } |
| 122 |
|
| |
| 123 |
|
| /* save result hash */ |
| 124 |
4 |
| memcpy(ctx->tiger.hash, last_message, tiger_hash_length); |
| 125 |
4 |
▶ | if (result) memcpy(result, last_message, tiger_hash_length); |
Branch: 1 branch
| Branch | True | False | Total |
| if (result) memcpy(result, last_message, tiger_hash_length); |
4 |
0 |
4 |
|
| 126 |
4 |
| } |
| 127 |
|
| |
| 128 |
0 |
| static size_t tth_get_stack_size(uint64_t block_count) |
| 129 |
|
| { |
| 130 |
0 |
| size_t stack_size = 0; |
| 131 |
0 |
▶ | for (; block_count; block_count >>= 1) |
Branch: 1 branch
| Branch | True | False | Total |
| for (; block_count; block_count >>= 1) |
0 |
0 |
0 |
|
| 132 |
0 |
| stack_size += 24; |
| 133 |
0 |
| return stack_size; |
| 134 |
|
| } |
| 135 |
|
| |
| 136 |
|
| #if !defined(NO_IMPORT_EXPORT) |
| 137 |
|
| /** |
| 138 |
|
| * Export tth context to a memory region, or calculate the |
| 139 |
|
| * size required for context export. |
| 140 |
|
| * |
| 141 |
|
| * @param ctx the algorithm context containing current hashing state |
| 142 |
|
| * @param out pointer to the memory region or NULL |
| 143 |
|
| * @param size size of memory region |
| 144 |
|
| * @return the size of the exported data on success, 0 on fail. |
| 145 |
|
| */ |
| 146 |
0 |
| size_t rhash_tth_export(const tth_ctx* ctx, void* out, size_t size) |
| 147 |
|
| { |
| 148 |
0 |
| size_t export_size = offsetof(tth_ctx, stack) + |
| 149 |
0 |
| tth_get_stack_size(ctx->block_count); |
| 150 |
0 |
▶ | if (out != NULL) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (out != NULL) { |
0 |
0 |
0 |
|
| 151 |
0 |
▶ | if (size < export_size) |
Branch: 1 branch
| Branch | True | False | Total |
| if (size < export_size) |
0 |
0 |
0 |
|
| 152 |
0 |
| return 0; |
| 153 |
0 |
| memcpy(out, ctx, export_size); |
| 154 |
|
| } |
| 155 |
0 |
| return export_size; |
| 156 |
|
| } |
| 157 |
|
| |
| 158 |
|
| /** |
| 159 |
|
| * Import tth context from a memory region. |
| 160 |
|
| * |
| 161 |
|
| * @param ctx pointer to the algorithm context |
| 162 |
|
| * @param in pointer to the data to import |
| 163 |
|
| * @param size size of data to import |
| 164 |
|
| * @return the size of the imported data on success, 0 on fail. |
| 165 |
|
| */ |
| 166 |
0 |
| size_t rhash_tth_import(tth_ctx* ctx, const void* in, size_t size) |
| 167 |
|
| { |
| 168 |
0 |
| const size_t head_size = offsetof(tth_ctx, stack); |
| 169 |
|
| size_t stack_size; |
| 170 |
0 |
▶ | if (size < head_size) |
Branch: 1 branch
| Branch | True | False | Total |
| if (size < head_size) |
0 |
0 |
0 |
|
| 171 |
0 |
| return 0; |
| 172 |
0 |
| memset(ctx, 0, sizeof(tth_ctx)); |
| 173 |
0 |
| memcpy(ctx, in, head_size); |
| 174 |
0 |
| stack_size = tth_get_stack_size(ctx->block_count); |
| 175 |
0 |
▶ | if (size < (head_size + stack_size)) |
Branch: 1 branch
| Branch | True | False | Total |
| if (size < (head_size + stack_size)) |
0 |
0 |
0 |
|
| 176 |
0 |
| return 0; |
| 177 |
0 |
| memcpy(ctx->stack, (const char*)in + head_size, stack_size); |
| 178 |
0 |
| return head_size + stack_size; |
| 179 |
|
| } |
| 180 |
|
| #endif /* !defined(NO_IMPORT_EXPORT) */ |