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