1 /**********************************************************************
2 * Copyright (c) 2013-2015 Pieter Wuille *
3 * Distributed under the MIT software license, see the accompanying *
4 * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
5 **********************************************************************/
6
7 #ifndef SECP256K1_TESTRAND_IMPL_H
8 #define SECP256K1_TESTRAND_IMPL_H
9
10 #include <stdint.h>
11 #include <string.h>
12
13 #include "testrand.h"
14 #include "hash.h"
15
16 static secp256k1_rfc6979_hmac_sha256_t secp256k1_test_rng;
17 static uint32_t secp256k1_test_rng_precomputed[8];
18 static int secp256k1_test_rng_precomputed_used = 8;
19 static uint64_t secp256k1_test_rng_integer;
20 static int secp256k1_test_rng_integer_bits_left = 0;
21
secp256k1_rand_seed(const unsigned char * seed16)22 SECP256K1_INLINE static void secp256k1_rand_seed(const unsigned char *seed16) {
23 secp256k1_rfc6979_hmac_sha256_initialize(&secp256k1_test_rng, seed16, 16);
24 }
25
secp256k1_rand32(void)26 SECP256K1_INLINE static uint32_t secp256k1_rand32(void) {
27 if (secp256k1_test_rng_precomputed_used == 8) {
28 secp256k1_rfc6979_hmac_sha256_generate(&secp256k1_test_rng, (unsigned char*)(&secp256k1_test_rng_precomputed[0]), sizeof(secp256k1_test_rng_precomputed));
29 secp256k1_test_rng_precomputed_used = 0;
30 }
31 return secp256k1_test_rng_precomputed[secp256k1_test_rng_precomputed_used++];
32 }
33
secp256k1_rand_bits(int bits)34 static uint32_t secp256k1_rand_bits(int bits) {
35 uint32_t ret;
36 if (secp256k1_test_rng_integer_bits_left < bits) {
37 secp256k1_test_rng_integer |= (((uint64_t)secp256k1_rand32()) << secp256k1_test_rng_integer_bits_left);
38 secp256k1_test_rng_integer_bits_left += 32;
39 }
40 ret = secp256k1_test_rng_integer;
41 secp256k1_test_rng_integer >>= bits;
42 secp256k1_test_rng_integer_bits_left -= bits;
43 ret &= ((~((uint32_t)0)) >> (32 - bits));
44 return ret;
45 }
46
secp256k1_rand_int(uint32_t range)47 static uint32_t secp256k1_rand_int(uint32_t range) {
48 /* We want a uniform integer between 0 and range-1, inclusive.
49 * B is the smallest number such that range <= 2**B.
50 * two mechanisms implemented here:
51 * - generate B bits numbers until one below range is found, and return it
52 * - find the largest multiple M of range that is <= 2**(B+A), generate B+A
53 * bits numbers until one below M is found, and return it modulo range
54 * The second mechanism consumes A more bits of entropy in every iteration,
55 * but may need fewer iterations due to M being closer to 2**(B+A) then
56 * range is to 2**B. The array below (indexed by B) contains a 0 when the
57 * first mechanism is to be used, and the number A otherwise.
58 */
59 static const int addbits[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0};
60 uint32_t trange, mult;
61 int bits = 0;
62 if (range <= 1) {
63 return 0;
64 }
65 trange = range - 1;
66 while (trange > 0) {
67 trange >>= 1;
68 bits++;
69 }
70 if (addbits[bits]) {
71 bits = bits + addbits[bits];
72 mult = ((~((uint32_t)0)) >> (32 - bits)) / range;
73 trange = range * mult;
74 } else {
75 trange = range;
76 mult = 1;
77 }
78 while(1) {
79 uint32_t x = secp256k1_rand_bits(bits);
80 if (x < trange) {
81 return (mult == 1) ? x : (x % range);
82 }
83 }
84 }
85
secp256k1_rand256(unsigned char * b32)86 static void secp256k1_rand256(unsigned char *b32) {
87 secp256k1_rfc6979_hmac_sha256_generate(&secp256k1_test_rng, b32, 32);
88 }
89
secp256k1_rand_bytes_test(unsigned char * bytes,size_t len)90 static void secp256k1_rand_bytes_test(unsigned char *bytes, size_t len) {
91 size_t bits = 0;
92 memset(bytes, 0, len);
93 while (bits < len * 8) {
94 int now;
95 uint32_t val;
96 now = 1 + (secp256k1_rand_bits(6) * secp256k1_rand_bits(5) + 16) / 31;
97 val = secp256k1_rand_bits(1);
98 while (now > 0 && bits < len * 8) {
99 bytes[bits / 8] |= val << (bits % 8);
100 now--;
101 bits++;
102 }
103 }
104 }
105
secp256k1_rand256_test(unsigned char * b32)106 static void secp256k1_rand256_test(unsigned char *b32) {
107 secp256k1_rand_bytes_test(b32, 32);
108 }
109
110 #endif /* SECP256K1_TESTRAND_IMPL_H */
111