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 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 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