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