src/testrand_impl.h

   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
  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
  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
  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
  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
  86 static void secp256k1_rand256(unsigned char *b32) {
  87     secp256k1_rfc6979_hmac_sha256_generate(&secp256k1_test_rng, b32, 32);
  88 }
  89
  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
 106 static void secp256k1_rand256_test(unsigned char *b32) {
 107     secp256k1_rand_bytes_test(b32, 32);
 108 }
 109
 110 #endif /* SECP256K1_TESTRAND_IMPL_H */