pdns/dns_random.hh

   1 /*
   2  * This file is part of PowerDNS or dnsdist.
   3  * Copyright -- PowerDNS.COM B.V. and its contributors
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of version 2 of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * In addition, for the avoidance of any doubt, permission is granted to
  10  * link this program with OpenSSL and to (re)distribute the binaries
  11  * produced as the result of such linking.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21  */
  22 #pragma once
  23 #include <cstdint>
  24 #include <limits>
  25 #include <string>
  26
  27 #include <ext/arc4random/arc4random.hh>
  28
  29 inline uint32_t dns_random(uint32_t upper_bound)
  30 {
  31   return arc4random_uniform(upper_bound);
  32 }
  33
  34 inline uint32_t dns_random_uint32()
  35 {
  36   return arc4random();
  37 }
  38
  39 inline uint16_t dns_random_uint16()
  40 {
  41   return arc4random() & 0xffff;
  42 }
  43
  44 namespace pdns
  45 {
  46 struct dns_random_engine
  47 {
  48
  49   using result_type = uint32_t;
  50
  51   static constexpr result_type min()
  52   {
  53     return 0;
  54   }
  55
  56   static constexpr result_type max()
  57   {
  58     return std::numeric_limits<result_type>::max();
  59   }
  60
  61   result_type operator()()
  62   {
  63     return dns_random_uint32();
  64   }
  65 };
  66
  67 /* minimum value that a PRNG should return for this upper bound to avoid a modulo bias */
  68 inline unsigned int random_minimum_acceptable_value(uint32_t upper_bound)
  69 {
  70   /* Parts of this code come from arc4random_uniform */
  71   /* To avoid "modulo bias" for some methods, calculate
  72      minimum acceptable value for random number to improve
  73      uniformity.
  74
  75      On applicable rngs, we loop until the rng spews out
  76      value larger than min, and then take modulo out of that.
  77   */
  78   unsigned int min = 0;
  79 #if (ULONG_MAX > 0xffffffffUL)
  80   min = 0x100000000UL % upper_bound;
  81 #else
  82   /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
  83   if (upper_bound > 0x80000000)
  84     min = 1 + ~upper_bound; /* 2**32 - upper_bound */
  85   else {
  86     /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
  87     min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
  88   }
  89 #endif
  90   return min;
  91 }
  92 }