Line data    Source code

       1             : /* Copyright (C) 2010 Wildfire Games.
       2             :  *
       3             :  * Permission is hereby granted, free of charge, to any person obtaining
       4             :  * a copy of this software and associated documentation files (the
       5             :  * "Software"), to deal in the Software without restriction, including
       6             :  * without limitation the rights to use, copy, modify, merge, publish,
       7             :  * distribute, sublicense, and/or sell copies of the Software, and to
       8             :  * permit persons to whom the Software is furnished to do so, subject to
       9             :  * the following conditions:
      10             :  *
      11             :  * The above copyright notice and this permission notice shall be included
      12             :  * in all copies or substantial portions of the Software.
      13             :  *
      14             :  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
      15             :  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
      16             :  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
      17             :  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
      18             :  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
      19             :  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
      20             :  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
      21             :  */
      22             : 
      23             : /*
      24             :  * pseudorandom number generator
      25             :  */
      26             : 
      27             : #include "precompiled.h"
      28             : #include "lib/rand.h"
      29             : 
      30             : // avoids several common pitfalls; see discussion at
      31             : // http://www.azillionmonkeys.com/qed/random.html
      32             : 
      33             : // rand() is poorly implemented (e.g. in VC7) and only returns < 16 bits;
      34             : // double that amount by concatenating 2 random numbers.
      35             : // this is not to fix poor rand() randomness - the number returned will be
      36             : // folded down to a much smaller interval anyway. instead, a larger XRAND_MAX
      37             : // decreases the probability of having to repeat the loop.
      38             : #if RAND_MAX < 65536
      39             : static const size_t XRAND_MAX = (RAND_MAX+1)*(RAND_MAX+1) - 1;
      40             : static size_t xrand()
      41             : {
      42             :     return rand()*(RAND_MAX+1) + rand();
      43             : }
      44             : // rand() is already ok; no need to do anything.
      45             : #else
      46             : static const size_t XRAND_MAX = RAND_MAX;
      47         228 : static size_t xrand()
      48             : {
      49         228 :     return rand();
      50             : }
      51             : #endif
      52             : 
      53         202 : size_t rand(size_t min_inclusive, size_t max_exclusive)
      54             : {
      55         202 :     const size_t range = (max_exclusive-min_inclusive);
      56             :     // huge interval or min >= max
      57         202 :     if(range == 0 || range > XRAND_MAX)
      58             :     {
      59           2 :         WARN_IF_ERR(ERR::INVALID_PARAM);
      60           2 :         return 0;
      61             :     }
      62             : 
      63         200 :     const size_t inv_range = XRAND_MAX / range;
      64             : 
      65             :     // generate random number in [0, range)
      66             :     // idea: avoid skewed distributions when <range> doesn't evenly divide
      67             :     // XRAND_MAX by simply discarding values in the "remainder".
      68             :     // not expected to run often since XRAND_MAX is large.
      69             :     size_t x;
      70          28 :     do
      71             :     {
      72         228 :         x = xrand();
      73             :     }
      74         228 :     while(x >= range * inv_range);
      75         200 :     x /= inv_range;
      76             : 
      77         200 :     x += min_inclusive;
      78         200 :     ENSURE(x < max_exclusive);
      79         200 :     return x;
      80           3 : }