1276541Sdes/* $OpenBSD: arc4random_uniform.c,v 1.1 2014/07/12 13:24:54 deraadt Exp $ */ 2276541Sdes 3276541Sdes/* 4276541Sdes * Copyright (c) 2008, Damien Miller <djm@openbsd.org> 5276541Sdes * 6276541Sdes * Permission to use, copy, modify, and distribute this software for any 7276541Sdes * purpose with or without fee is hereby granted, provided that the above 8276541Sdes * copyright notice and this permission notice appear in all copies. 9276541Sdes * 10276541Sdes * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11276541Sdes * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12276541Sdes * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13276541Sdes * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14276541Sdes * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15276541Sdes * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16276541Sdes * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17276541Sdes */ 18276541Sdes 19276541Sdes#include "config.h" 20276541Sdes#include <sys/types.h> 21276541Sdes#include <stdlib.h> 22276541Sdes 23276541Sdes/* 24276541Sdes * Calculate a uniformly distributed random number less than upper_bound 25276541Sdes * avoiding "modulo bias". 26276541Sdes * 27276541Sdes * Uniformity is achieved by generating new random numbers until the one 28276541Sdes * returned is outside the range [0, 2**32 % upper_bound). This 29276541Sdes * guarantees the selected random number will be inside 30276541Sdes * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 31276541Sdes * after reduction modulo upper_bound. 32276541Sdes */ 33276541Sdesuint32_t 34276541Sdesarc4random_uniform(uint32_t upper_bound) 35276541Sdes{ 36276541Sdes uint32_t r, min; 37276541Sdes 38276541Sdes if (upper_bound < 2) 39276541Sdes return 0; 40276541Sdes 41276541Sdes /* 2**32 % x == (2**32 - x) % x */ 42276541Sdes min = -upper_bound % upper_bound; 43276541Sdes 44276541Sdes /* 45276541Sdes * This could theoretically loop forever but each retry has 46276541Sdes * p > 0.5 (worst case, usually far better) of selecting a 47276541Sdes * number inside the range we need, so it should rarely need 48276541Sdes * to re-roll. 49276541Sdes */ 50276541Sdes for (;;) { 51276541Sdes r = arc4random(); 52276541Sdes if (r >= min) 53276541Sdes break; 54276541Sdes } 55276541Sdes 56276541Sdes return r % upper_bound; 57276541Sdes} 58