GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/rebound/randomid.c Lines: 0 17 0.0 %
Date: 2017-11-13 Branches: 0 6 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: randomid.c,v 1.1 2015/10/15 19:43:30 tedu Exp $ */
2
3
/*
4
 * Copyright (c) 2008 Theo de Raadt, Ryan McBride
5
 *
6
 * Slightly different algorithm from the one designed by
7
 * Matthew Dillon <dillon@backplane.com> for The DragonFly Project
8
 *
9
 * Permission to use, copy, modify, and distribute this software for any
10
 * purpose with or without fee is hereby granted, provided that the above
11
 * copyright notice and this permission notice appear in all copies.
12
 *
13
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
14
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
16
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
18
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
19
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20
 */
21
22
/*
23
 * This code was used for generating IP IDs. It also works for DNS IDs.
24
 */
25
26
/*
27
 * Random DNS sequence number generator.  Use the system PRNG to shuffle
28
 * the 65536 entry ID space.  We reshuffle the ID we pick out of the array
29
 * into the previous 32767 cells, providing an guarantee that an ID will not
30
 * be reused for at least 32768 calls.
31
 */
32
#include <stdlib.h>
33
#define nitems(arr) (sizeof(arr) / sizeof(arr[0]))
34
35
static u_int16_t ip_shuffle[65536];
36
static int isindex = 0;
37
38
/*
39
 * Return a random DNS id.  Shuffle the new value we get into the previous half
40
 * of the ip_shuffle ring (-32767 or swap with ourself), to avoid duplicates
41
 * occuring too quickly but also still be random.
42
 *
43
 * 0 is a special DNS ID -- don't return it.
44
 */
45
uint16_t
46
randomid(void)
47
{
48
	static int ipid_initialized;
49
	u_int16_t si, r;
50
	int i, i2;
51
52
	if (!ipid_initialized) {
53
		ipid_initialized = 1;
54
55
		/*
56
		 * Initialize with a random permutation. Do so using Knuth
57
		 * which avoids the exchange in the Durstenfeld shuffle.
58
		 * (See "The Art of Computer Programming, Vol 2" 3rd ed, pg. 145).
59
		 */
60
		for (i = 0; i < nitems(ip_shuffle); ++i) {
61
			i2 = arc4random_uniform(i + 1);
62
			ip_shuffle[i] = ip_shuffle[i2];
63
			ip_shuffle[i2] = i;
64
		}
65
	}
66
67
	do {
68
		arc4random_buf(&si, sizeof(si));
69
		i = isindex & 0xFFFF;
70
		i2 = (isindex - (si & 0x7FFF)) & 0xFFFF;
71
		r = ip_shuffle[i];
72
		ip_shuffle[i] = ip_shuffle[i2];
73
		ip_shuffle[i2] = r;
74
		isindex++;
75
	} while (r == 0);
76
77
	return (r);
78
}