1 /* $OpenBSD: shuffle.c,v 1.4 2015/01/22 17:42:09 reyk Exp $ */
2
3 /*
4 * Portions Copyright (C) 2008 Theo de Raadt
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM
11 * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL
12 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL
13 * INTERNET SOFTWARE CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT,
14 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING
15 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
16 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
17 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19
20 /* based on: bind/lib/isc/shuffle.c,v 1.4 2008/07/09 17:07:32 reyk Exp $ */
21
22 #include <sys/types.h>
23
24 #include <stdlib.h>
25 #include <assert.h>
26
27 #include "relayd.h"
28
29 #define VALID_SHUFFLE(x) (x != NULL)
30
31 void
shuffle_init(struct shuffle * shuffle)32 shuffle_init(struct shuffle *shuffle)
33 {
34 int i, i2;
35
36 assert(VALID_SHUFFLE(shuffle));
37
38 shuffle->isindex = 0;
39 /* Initialize using a Knuth shuffle */
40 for (i = 0; i < 65536; ++i) {
41 i2 = arc4random_uniform(i + 1);
42 shuffle->id_shuffle[i] = shuffle->id_shuffle[i2];
43 shuffle->id_shuffle[i2] = i;
44 }
45 }
46
47 u_int16_t
shuffle_generate16(struct shuffle * shuffle)48 shuffle_generate16(struct shuffle *shuffle)
49 {
50 u_int32_t si;
51 u_int16_t r;
52 int i, i2;
53
54 assert(VALID_SHUFFLE(shuffle));
55
56 do {
57 si = arc4random();
58 i = shuffle->isindex & 0xFFFF;
59 i2 = (shuffle->isindex - (si & 0x7FFF)) & 0xFFFF;
60 r = shuffle->id_shuffle[i];
61 shuffle->id_shuffle[i] = shuffle->id_shuffle[i2];
62 shuffle->id_shuffle[i2] = r;
63 shuffle->isindex++;
64 } while (r == 0);
65
66 return (r);
67 }
68