1/* 2 * Copyright (C) 2010 Julien BLACHE <jb@jblache.org> 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation; either version 2 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, write to the Free Software 16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 17 */ 18 19#include <stdio.h> 20#include <string.h> 21#include <errno.h> 22#include <unistd.h> 23#include <fcntl.h> 24#include <sys/types.h> 25#include <stdint.h> 26 27#include <gcrypt.h> 28 29#include "rng.h" 30 31 32/* Park & Miller Minimal Standard PRNG 33 * w/ Bays-Durham shuffle 34 * From Numerical Recipes in C, 2nd ed. 35 */ 36static int32_t 37rng_rand_internal(int32_t *seed) 38{ 39 int32_t hi; 40 int32_t lo; 41 int32_t res; 42 43 hi = *seed / 127773; 44 lo = *seed % 127773; 45 46 res = 16807 * lo - 2836 * hi; 47 48 if (res < 0) 49 res += 0x7fffffffL; /* 2147483647 */ 50 51 *seed = res; 52 53 return res; 54} 55 56void 57rng_init(struct rng_ctx *ctx) 58{ 59 int32_t val; 60 int i; 61 62 gcry_randomize(&ctx->seed, sizeof(ctx->seed), GCRY_STRONG_RANDOM); 63 64 /* Load the shuffle array - first 8 iterations discarded */ 65 for (i = sizeof(ctx->iv) / sizeof(ctx->iv[0]) + 7; i >= 0; i--) 66 { 67 val = rng_rand_internal(&ctx->seed); 68 69 if (i < sizeof(ctx->iv) / sizeof(ctx->iv[0])) 70 ctx->iv[i] = val; 71 } 72 73 ctx->iy = ctx->iv[0]; 74} 75 76int32_t 77rng_rand(struct rng_ctx *ctx) 78{ 79 int i; 80 81 /* Select return value */ 82 i = ctx->iy / (1 + (0x7fffffffL - 1) / (sizeof(ctx->iv) / sizeof(ctx->iv[0]))); 83 ctx->iy = ctx->iv[i]; 84 85 /* Refill */ 86 ctx->iv[i] = rng_rand_internal(&ctx->seed); 87 88 return ctx->iy; 89} 90 91/* Integer in [min, max[ */ 92/* Taken from GLib 2.0 v2.25.3, g_rand_int_range(), GPLv2+ */ 93int32_t 94rng_rand_range(struct rng_ctx *ctx, int32_t min, int32_t max) 95{ 96 int32_t res; 97 int32_t dist; 98 uint32_t maxvalue; 99 uint32_t leftover; 100 101 dist = max - min; 102 103 if (dist <= 0) 104 return min; 105 106 /* maxvalue is set to the predecessor of the greatest 107 * multiple of dist less or equal 2^32. */ 108 if (dist <= 0x80000000u) /* 2^31 */ 109 { 110 /* maxvalue = 2^32 - 1 - (2^32 % dist) */ 111 leftover = (0x80000000u % dist) * 2; 112 if (leftover >= dist) 113 leftover -= dist; 114 maxvalue = 0xffffffffu - leftover; 115 } 116 else 117 maxvalue = dist - 1; 118 do 119 res = rng_rand(ctx); 120 while (res > maxvalue); 121 122 res %= dist; 123 124 return min + res; 125} 126 127/* Fisher-Yates shuffling algorithm 128 * Durstenfeld in-place shuffling variant 129 */ 130void 131shuffle_ptr(struct rng_ctx *ctx, void **values, int len) 132{ 133 int i; 134 int32_t j; 135 void *tmp; 136 137 for (i = len - 1; i > 0; i--) 138 { 139 j = rng_rand_range(ctx, 0, i + 1); 140 141 tmp = values[i]; 142 values[i] = values[j]; 143 values[j] = tmp; 144 } 145} 146 147