diff options
Diffstat (limited to 'src/crypto')
33 files changed, 112 insertions, 97 deletions
diff --git a/src/crypto/CMakeLists.txt b/src/crypto/CMakeLists.txt index 28f845d47..277ee64c2 100644 --- a/src/crypto/CMakeLists.txt +++ b/src/crypto/CMakeLists.txt @@ -1,4 +1,4 @@ -# Copyright (c) 2014-2016, The Monero Project +# Copyright (c) 2014-2017, The Monero Project # # All rights reserved. # @@ -68,9 +68,9 @@ set(crypto_private_headers skein.h skein_port.h) -bitmonero_private_headers(crypto +monero_private_headers(crypto ${crypto_private_headers}) -bitmonero_add_library(crypto +monero_add_library(crypto ${crypto_sources} ${crypto_headers} ${crypto_private_headers}) @@ -89,3 +89,14 @@ if (ARM) PROPERTY COMPILE_DEFINITIONS "NO_OPTIMIZED_MULTIPLY_ON_ARM") endif() endif() + +# Because of the way Qt works on android with JNI, the code does not live in the main android thread +# So this code runs with a 1 MB default stack size. +# This will force the use of the heap for the allocation of the scratchpad +if (ANDROID OR IOS) + if( BUILD_GUI_DEPS ) + add_definitions(-DFORCE_USE_HEAP=1) + endif() +endif() + + diff --git a/src/crypto/blake256.c b/src/crypto/blake256.c index 1cb1cf344..1e43f9c4d 100644 --- a/src/crypto/blake256.c +++ b/src/crypto/blake256.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/blake256.h b/src/crypto/blake256.h index e262d1b4b..921fcd2fd 100644 --- a/src/crypto/blake256.h +++ b/src/crypto/blake256.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/chacha8.h b/src/crypto/chacha8.h index 94c0ba721..80557e9f5 100644 --- a/src/crypto/chacha8.h +++ b/src/crypto/chacha8.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/crypto-ops-data.c b/src/crypto/crypto-ops-data.c index 60ee38096..4bd75b77c 100644 --- a/src/crypto/crypto-ops-data.c +++ b/src/crypto/crypto-ops-data.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/crypto-ops.c b/src/crypto/crypto-ops.c index 1b390e402..4edfee0ce 100644 --- a/src/crypto/crypto-ops.c +++ b/src/crypto/crypto-ops.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/crypto-ops.h b/src/crypto/crypto-ops.h index 4986499f4..37edf5b6d 100644 --- a/src/crypto/crypto-ops.h +++ b/src/crypto/crypto-ops.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/crypto.cpp b/src/crypto/crypto.cpp index 250779ac3..98da466cc 100644 --- a/src/crypto/crypto.cpp +++ b/src/crypto/crypto.cpp @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // @@ -42,7 +42,7 @@ #include "crypto.h" #include "hash.h" -#if !defined(__FreeBSD__) && !defined(__OpenBSD__) +#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__DragonFly__) #include <alloca.h> #else #include <stdlib.h> diff --git a/src/crypto/crypto.h b/src/crypto/crypto.h index b396fc7db..3b8c7996b 100644 --- a/src/crypto/crypto.h +++ b/src/crypto/crypto.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // @@ -236,6 +236,6 @@ namespace crypto { } } -CRYPTO_MAKE_COMPARABLE(public_key) +CRYPTO_MAKE_HASHABLE(public_key) CRYPTO_MAKE_HASHABLE(key_image) CRYPTO_MAKE_COMPARABLE(signature) diff --git a/src/crypto/crypto_ops_builder/README.md b/src/crypto/crypto_ops_builder/README.md index eec3e21e7..3b87966f5 100644 --- a/src/crypto/crypto_ops_builder/README.md +++ b/src/crypto/crypto_ops_builder/README.md @@ -1,6 +1,6 @@ # Monero -Copyright (c) 2014-2016, The Monero Project +Copyright (c) 2014-2017, The Monero Project ## Crypto Ops Builder diff --git a/src/crypto/crypto_ops_builder/crypto-ops-data.c b/src/crypto/crypto_ops_builder/crypto-ops-data.c index 60ee38096..4bd75b77c 100644 --- a/src/crypto/crypto_ops_builder/crypto-ops-data.c +++ b/src/crypto/crypto_ops_builder/crypto-ops-data.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/crypto_ops_builder/crypto-ops-old.c b/src/crypto/crypto_ops_builder/crypto-ops-old.c index 910801c57..b7a290b4a 100644 --- a/src/crypto/crypto_ops_builder/crypto-ops-old.c +++ b/src/crypto/crypto_ops_builder/crypto-ops-old.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/crypto_ops_builder/crypto-ops.h b/src/crypto/crypto_ops_builder/crypto-ops.h index 84ef12ae2..47d5b46ae 100644 --- a/src/crypto/crypto_ops_builder/crypto-ops.h +++ b/src/crypto/crypto_ops_builder/crypto-ops.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/crypto_ops_builder/ref10CommentedCombined/MakeCryptoOps.py b/src/crypto/crypto_ops_builder/ref10CommentedCombined/MakeCryptoOps.py index 9d996f9d1..5f8776a49 100644 --- a/src/crypto/crypto_ops_builder/ref10CommentedCombined/MakeCryptoOps.py +++ b/src/crypto/crypto_ops_builder/ref10CommentedCombined/MakeCryptoOps.py @@ -15,7 +15,7 @@ print("maybe someone smart can replace the sed with perl..") a = "" license = textwrap.dedent("""\ - // Copyright (c) 2014-2016, The Monero Project + // Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/crypto_ops_builder/ref10CommentedCombined/crypto-ops.h b/src/crypto/crypto_ops_builder/ref10CommentedCombined/crypto-ops.h index cdc5ac1ee..b432efade 100644 --- a/src/crypto/crypto_ops_builder/ref10CommentedCombined/crypto-ops.h +++ b/src/crypto/crypto_ops_builder/ref10CommentedCombined/crypto-ops.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/generic-ops.h b/src/crypto/generic-ops.h index a8d8fdb19..1a135ffcf 100644 --- a/src/crypto/generic-ops.h +++ b/src/crypto/generic-ops.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/groestl.h b/src/crypto/groestl.h index ac749d1d8..89a073a4c 100644 --- a/src/crypto/groestl.h +++ b/src/crypto/groestl.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/groestl_tables.h b/src/crypto/groestl_tables.h index c271fd367..8fa6d7a83 100644 --- a/src/crypto/groestl_tables.h +++ b/src/crypto/groestl_tables.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/hash-extra-blake.c b/src/crypto/hash-extra-blake.c index 15357dc7a..236479880 100644 --- a/src/crypto/hash-extra-blake.c +++ b/src/crypto/hash-extra-blake.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/hash-extra-groestl.c b/src/crypto/hash-extra-groestl.c index 69546ee44..b15075306 100644 --- a/src/crypto/hash-extra-groestl.c +++ b/src/crypto/hash-extra-groestl.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/hash-extra-jh.c b/src/crypto/hash-extra-jh.c index 5da0894f6..8950687d3 100644 --- a/src/crypto/hash-extra-jh.c +++ b/src/crypto/hash-extra-jh.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/hash-extra-skein.c b/src/crypto/hash-extra-skein.c index babf5006f..e63e7da20 100644 --- a/src/crypto/hash-extra-skein.c +++ b/src/crypto/hash-extra-skein.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/hash-ops.h b/src/crypto/hash-ops.h index 612d94efe..6e3a5c6c9 100644 --- a/src/crypto/hash-ops.h +++ b/src/crypto/hash-ops.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/hash.c b/src/crypto/hash.c index 93f7353e4..ed95391d8 100644 --- a/src/crypto/hash.c +++ b/src/crypto/hash.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/hash.h b/src/crypto/hash.h index 803992078..22991e513 100644 --- a/src/crypto/hash.h +++ b/src/crypto/hash.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/initializer.h b/src/crypto/initializer.h index fefc3b7c3..619038ae6 100644 --- a/src/crypto/initializer.h +++ b/src/crypto/initializer.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/oaes_lib.c b/src/crypto/oaes_lib.c index 4c1446898..0afec6212 100644 --- a/src/crypto/oaes_lib.c +++ b/src/crypto/oaes_lib.c @@ -34,12 +34,13 @@ #include <stdio.h> // OS X, FreeBSD, and OpenBSD don't need malloc.h -#if !defined(__APPLE__) && !defined(__FreeBSD__) && !defined(__OpenBSD__) +#if !defined(__APPLE__) && !defined(__FreeBSD__) && !defined(__OpenBSD__) \ + && !defined(__DragonFly__) #include <malloc.h> #endif -// FreeBSD, and OpenBSD also don't need timeb.h -#if !defined(__FreeBSD__) && !defined(__OpenBSD__) +// ANDROID, FreeBSD, and OpenBSD also don't need timeb.h +#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__ANDROID__) #include <sys/timeb.h> #else #include <sys/time.h> @@ -498,7 +499,7 @@ static void oaes_get_seed( char buf[RANDSIZ + 1] ) #else static uint32_t oaes_get_seed(void) { - #if !defined(__FreeBSD__) && !defined(__OpenBSD__) + #if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__ANDROID__) struct timeb timer; struct tm *gmTimer; char * _test = NULL; @@ -639,7 +640,10 @@ static OAES_RET oaes_key_gen( OAES_CTX * ctx, size_t key_size ) _key->data = (uint8_t *) calloc( key_size, sizeof( uint8_t )); if( NULL == _key->data ) + { + free( _key ); return OAES_RET_MEM; + } for( _i = 0; _i < key_size; _i++ ) #ifdef OAES_HAVE_ISAAC diff --git a/src/crypto/random.c b/src/crypto/random.c index 6a9f63c12..691c31f62 100644 --- a/src/crypto/random.c +++ b/src/crypto/random.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/random.h b/src/crypto/random.h index b0d2303b6..75d23fd04 100644 --- a/src/crypto/random.h +++ b/src/crypto/random.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/skein.c b/src/crypto/skein.c index 9c8ac288d..65e4525c3 100644 --- a/src/crypto/skein.c +++ b/src/crypto/skein.c @@ -77,7 +77,7 @@ typedef struct /* 1024-bit Skein hash context stru } Skein1024_Ctxt_t; /* Skein APIs for (incremental) "straight hashing" */ -#if SKEIN_256_NIST_MAX_HASH_BITS +#if SKEIN_256_NIST_MAX_HASHBITS static int Skein_256_Init (Skein_256_Ctxt_t *ctx, size_t hashBitLen); #endif static int Skein_512_Init (Skein_512_Ctxt_t *ctx, size_t hashBitLen); @@ -1941,7 +1941,7 @@ static HashReturn Final (hashState *state, BitSequence *hashval); /* select the context size and init the context */ static HashReturn Init(hashState *state, int hashbitlen) { -#if SKEIN_256_NIST_MAX_HASH_BITS +#if SKEIN_256_NIST_MAX_HASHBITS if (hashbitlen <= SKEIN_256_NIST_MAX_HASHBITS) { Skein_Assert(hashbitlen > 0,BAD_HASHLEN); diff --git a/src/crypto/skein_port.h b/src/crypto/skein_port.h index 0b3d071ee..a06ef30a2 100644 --- a/src/crypto/skein_port.h +++ b/src/crypto/skein_port.h @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // diff --git a/src/crypto/slow-hash.c b/src/crypto/slow-hash.c index 2ac303a36..6afa28934 100644 --- a/src/crypto/slow-hash.c +++ b/src/crypto/slow-hash.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // @@ -44,6 +44,9 @@ #define INIT_SIZE_BLK 8 #define INIT_SIZE_BYTE (INIT_SIZE_BLK * AES_BLOCK_SIZE) +extern int aesb_single_round(const uint8_t *in, uint8_t*out, const uint8_t *expandedKey); +extern int aesb_pseudo_round(const uint8_t *in, uint8_t *out, const uint8_t *expandedKey); + #if defined(__x86_64__) || (defined(_MSC_VER) && defined(_WIN64)) // Optimised code below, uses x86-specific intrinsics, SSE2, AES-NI // Fall back to more portable code is down at the bottom @@ -138,9 +141,6 @@ #define THREADV __thread #endif -extern int aesb_single_round(const uint8_t *in, uint8_t*out, const uint8_t *expandedKey); -extern int aesb_pseudo_round(const uint8_t *in, uint8_t *out, const uint8_t *expandedKey); - #pragma pack(push, 1) union cn_slow_hash_state { @@ -442,7 +442,8 @@ void slow_hash_allocate_state(void) hp_state = (uint8_t *) VirtualAlloc(hp_state, MEMORY, MEM_LARGE_PAGES | MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE); #else -#if defined(__APPLE__) || defined(__FreeBSD__) || defined(__OpenBSD__) +#if defined(__APPLE__) || defined(__FreeBSD__) || defined(__OpenBSD__) || \ + defined(__DragonFly__) hp_state = mmap(0, MEMORY, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, 0, 0); #else @@ -493,7 +494,7 @@ void slow_hash_free_state(void) * buffer of pseudorandom data by hashing the supplied data. It then uses this * random data to fill a large 2MB buffer with pseudorandom data by iteratively * encrypting it using 10 rounds of AES per entry. After this initialization, - * it executes 500,000 rounds of mixing through the random 2MB buffer using + * it executes 524,288 rounds of mixing through the random 2MB buffer using * AES (typically provided in hardware on modern CPUs) and a 64 bit multiply. * Finally, it re-mixes this large buffer back into * the 200 byte "text" buffer, and then hashes this buffer using one of four @@ -529,7 +530,7 @@ void cn_slow_hash(const void *data, size_t length, char *hash) size_t i, j; uint64_t *p = NULL; - oaes_ctx *aes_ctx; + oaes_ctx *aes_ctx = NULL; int useAes = !force_software_aes() && check_aes_hw(); static void (*const extra_hashes[4])(const void *, size_t, char *) = @@ -577,8 +578,8 @@ void cn_slow_hash(const void *data, size_t length, char *hash) U64(b)[0] = U64(&state.k[16])[0] ^ U64(&state.k[48])[0]; U64(b)[1] = U64(&state.k[16])[1] ^ U64(&state.k[48])[1]; - /* CryptoNight Step 3: Bounce randomly 1 million times through the mixing buffer, - * using 500,000 iterations of the following mixing function. Each execution + /* CryptoNight Step 3: Bounce randomly 1,048,576 times (1<<20) through the mixing buffer, + * using 524,288 iterations of the following mixing function. Each execution * performs two reads and writes from the mixing buffer. */ @@ -721,32 +722,24 @@ union cn_slow_hash_state * key schedule. Don't try to use this for vanilla AES. */ static void aes_expand_key(const uint8_t *key, uint8_t *expandedKey) { -__asm__("mov x2, %1\n\t" : : "r"(key), "r"(expandedKey)); +static const int rcon[] = { + 0x01,0x01,0x01,0x01, + 0x0c0f0e0d,0x0c0f0e0d,0x0c0f0e0d,0x0c0f0e0d, // rotate-n-splat + 0x1b,0x1b,0x1b,0x1b }; __asm__( -" adr x3,Lrcon\n" -"\n" " eor v0.16b,v0.16b,v0.16b\n" -" ld1 {v3.16b},[x0],#16\n" -" ld1 {v1.4s,v2.4s},[x3],#32\n" -" b L256\n" -".align 5\n" -"Lrcon:\n" -".long 0x01,0x01,0x01,0x01\n" -".long 0x0c0f0e0d,0x0c0f0e0d,0x0c0f0e0d,0x0c0f0e0d // rotate-n-splat\n" -".long 0x1b,0x1b,0x1b,0x1b\n" +" ld1 {v3.16b},[%0],#16\n" +" ld1 {v1.4s,v2.4s},[%2],#32\n" +" ld1 {v4.16b},[%0]\n" +" mov w2,#5\n" +" st1 {v3.4s},[%1],#16\n" "\n" -".align 4\n" -"L256:\n" -" ld1 {v4.16b},[x0]\n" -" mov w1,#5\n" -" st1 {v3.4s},[x2],#16\n" -"\n" -"Loop256:\n" +"1:\n" " tbl v6.16b,{v4.16b},v2.16b\n" " ext v5.16b,v0.16b,v3.16b,#12\n" -" st1 {v4.4s},[x2],#16\n" +" st1 {v4.4s},[%1],#16\n" " aese v6.16b,v0.16b\n" -" subs w1,w1,#1\n" +" subs w2,w2,#1\n" "\n" " eor v3.16b,v3.16b,v5.16b\n" " ext v5.16b,v0.16b,v5.16b,#12\n" @@ -756,8 +749,8 @@ __asm__( " eor v3.16b,v3.16b,v5.16b\n" " shl v1.16b,v1.16b,#1\n" " eor v3.16b,v3.16b,v6.16b\n" -" st1 {v3.4s},[x2],#16\n" -" b.eq Ldone\n" +" st1 {v3.4s},[%1],#16\n" +" b.eq 2f\n" "\n" " dup v6.4s,v3.s[3] // just splat\n" " ext v5.16b,v0.16b,v4.16b,#12\n" @@ -770,9 +763,9 @@ __asm__( " eor v4.16b,v4.16b,v5.16b\n" "\n" " eor v4.16b,v4.16b,v6.16b\n" -" b Loop256\n" +" b 1b\n" "\n" -"Ldone:\n"); +"2:\n" : : "r"(key), "r"(expandedKey), "r"(rcon)); } /* An ordinary AES round is a sequence of SubBytes, ShiftRows, MixColumns, AddRoundKey. There @@ -894,8 +887,8 @@ void cn_slow_hash(const void *data, size_t length, char *hash) U64(b)[0] = U64(&state.k[16])[0] ^ U64(&state.k[48])[0]; U64(b)[1] = U64(&state.k[16])[1] ^ U64(&state.k[48])[1]; - /* CryptoNight Step 3: Bounce randomly 1 million times through the mixing buffer, - * using 500,000 iterations of the following mixing function. Each execution + /* CryptoNight Step 3: Bounce randomly 1,048,576 times (1<<20) through the mixing buffer, + * using 524,288 iterations of the following mixing function. Each execution * performs two reads and writes from the mixing buffer. */ @@ -1051,7 +1044,6 @@ STATIC INLINE void xor_blocks(uint8_t* a, const uint8_t* b) void cn_slow_hash(const void *data, size_t length, char *hash) { - uint8_t long_state[MEMORY]; uint8_t text[INIT_SIZE_BYTE]; uint8_t a[AES_BLOCK_SIZE]; uint8_t b[AES_BLOCK_SIZE]; @@ -1069,6 +1061,13 @@ void cn_slow_hash(const void *data, size_t length, char *hash) hash_extra_blake, hash_extra_groestl, hash_extra_jh, hash_extra_skein }; +#ifndef FORCE_USE_HEAP + uint8_t long_state[MEMORY]; +#else + uint8_t *long_state = NULL; + long_state = (uint8_t *)malloc(MEMORY); +#endif + hash_process(&state.hs, data, length); memcpy(text, state.init, INIT_SIZE_BYTE); @@ -1128,6 +1127,9 @@ void cn_slow_hash(const void *data, size_t length, char *hash) memcpy(state.init, text, INIT_SIZE_BYTE); hash_permutation(&state.hs); extra_hashes[state.hs.b[0] & 3](&state, 200, hash); +#ifdef FORCE_USE_HEAP + free(long_state); +#endif } #endif /* !aarch64 || !crypto */ diff --git a/src/crypto/tree-hash.c b/src/crypto/tree-hash.c index 7a128e4b0..eb98c31b7 100644 --- a/src/crypto/tree-hash.c +++ b/src/crypto/tree-hash.c @@ -1,4 +1,4 @@ -// Copyright (c) 2014-2016, The Monero Project +// Copyright (c) 2014-2017, The Monero Project // // All rights reserved. // @@ -34,33 +34,34 @@ #include "hash-ops.h" -#if !defined(__FreeBSD__) && !defined(__OpenBSD__) +#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__DragonFly__) #include <alloca.h> #else #include <stdlib.h> #endif -/// Quick check if this is power of two (use on unsigned types; in this case for size_t only) -bool ispowerof2_size_t(size_t x) { - return x && !(x & (x - 1)); -} - /*** * Round to power of two, for count>=3 and for count being not too large (as reasonable for tree hash calculations) */ size_t tree_hash_cnt(size_t count) { - assert( count >= 3); // cases for 0,1,2 are handled elsewhere - // Round down the count size: fun(2**n)= 2**(n-1) to round down to power of two - size_t tmp = count - 1; - size_t jj = 1; - for (jj=1 ; tmp != 0 ; ++jj) { - tmp /= 2; // dividing by 2 until to get how many powers of 2 fits size_to tmp - } - size_t cnt = 1 << (jj-2); // cnt is the count, but rounded down to power of two - // printf("count=%zu cnt=%zu jj=%zu tmp=%zu \n" , count,cnt,jj,tmp); - assert( cnt > 0 ); assert( cnt >= count/2 ); assert( cnt <= count ); - assert( ispowerof2_size_t( cnt )); - return cnt; + // This algo has some bad history but all we are doing is 1 << floor(log2(count)) + // There are _many_ ways to do log2, for some reason the one selected was the most obscure one, + // and fixing it made it even more obscure. + // + // Iterative method implemented below aims for clarity over speed, if performance is needed + // then my advice is to use the BSR instruction on x86 + // + // All the paranoid asserts have been removed since it is trivial to mathematically prove that + // the return will always be a power of 2. + // Problem space has been defined as 3 <= count <= 2^28. Of course quarter of a billion transactions + // is not a sane upper limit for a block, so there will be tighter limits in other parts of the code + + assert( count >= 3 ); // cases for 0,1,2 are handled elsewhere + assert( count <= 0x10000000 ); // sanity limit to 2^28, MSB=1 will cause an inf loop + + size_t pow = 2; + while(pow < count) pow <<= 1; + return pow >> 1; } void tree_hash(const char (*hashes)[HASH_SIZE], size_t count, char *root_hash) { @@ -86,9 +87,6 @@ void tree_hash(const char (*hashes)[HASH_SIZE], size_t count, char *root_hash) { size_t i, j; size_t cnt = tree_hash_cnt( count ); - size_t max_size_t = (size_t) -1; // max allowed value of size_t - assert( cnt < max_size_t/2 ); // reasonable size to avoid any overflows. /2 is extra; Anyway should be limited much stronger by logical code - // as we have sane limits on transactions counts in blockchain rules char (*ints)[HASH_SIZE]; size_t ints_size = cnt * HASH_SIZE; |