busybox/shell/random.c

/* vi: set sw=4 ts=4: */
/*
 * $RANDOM support.
 *
 * Copyright (C) 2009 Denys Vlasenko
 *
 * Licensed under GPLv2, see file LICENSE in this tarball for details.
 */
#include "libbb.h"
#include "random.h"

uint32_t FAST_FUNC
next_random(random_t *rnd)
{
	/* Galois LFSR parameter */
	/* Taps at 32 31 29 1: */
	enum { MASK = 0x8000000b };
	/* Another example - taps at 32 31 30 10: */
	/* MASK = 0x00400007 */

	uint32_t t;

	if (UNINITED_RANDOM_T(rnd)) {
		/* Can use monotonic_ns() for better randomness but for now
		 * it is not used anywhere else in busybox... so avoid bloat
		 */
		INIT_RANDOM_T(rnd, getpid(), monotonic_us());
	}

	/* LCG has period of 2^32 and alternating lowest bit */
	rnd->LCG = 1664525 * rnd->LCG + 1013904223;
	/* Galois LFSR has period of 2^32-1 = 3 * 5 * 17 * 257 * 65537 */
	t = (rnd->galois_LFSR << 1);
	if (rnd->galois_LFSR < 0) /* if we just shifted 1 out of msb... */
		t ^= MASK;
	rnd->galois_LFSR = t;
	/* Both are weak, combining them gives better randomness
	 * and ~2^64 period. & 0x7fff is probably bash compat
	 * for $RANDOM range. Combining with subtraction is
	 * just for fun. + and ^ would work equally well. */
	t = (t - rnd->LCG) & 0x7fff;

	return t;
}
1	/* vi: set sw=4 ts=4: */
2	/*
3	* $RANDOM support.
4	*
5	* Copyright (C) 2009 Denys Vlasenko
6	*
7	* Licensed under GPLv2, see file LICENSE in this tarball for details.
8	*/
9	#include "libbb.h"
10	#include "random.h"
11
12	uint32_t FAST_FUNC
13	next_random(random_t *rnd)
14	{
15	/* Galois LFSR parameter */
16	/* Taps at 32 31 29 1: */
17	enum { MASK = 0x8000000b };
18	/* Another example - taps at 32 31 30 10: */
19	/* MASK = 0x00400007 */
20
21	uint32_t t;
22
23	if (UNINITED_RANDOM_T(rnd)) {
24	/* Can use monotonic_ns() for better randomness but for now
25	* it is not used anywhere else in busybox... so avoid bloat
26	*/
27	INIT_RANDOM_T(rnd, getpid(), monotonic_us());
28	}
29
30	/* LCG has period of 2^32 and alternating lowest bit */
31	rnd->LCG = 1664525 * rnd->LCG + 1013904223;
32	/* Galois LFSR has period of 2^32-1 = 3 * 5 * 17 * 257 * 65537 */
33	t = (rnd->galois_LFSR << 1);
34	if (rnd->galois_LFSR < 0) /* if we just shifted 1 out of msb... */
35	t ^= MASK;
36	rnd->galois_LFSR = t;
37	/* Both are weak, combining them gives better randomness
38	* and ~2^64 period. & 0x7fff is probably bash compat
39	* for $RANDOM range. Combining with subtraction is
40	* just for fun. + and ^ would work equally well. */
41	t = (t - rnd->LCG) & 0x7fff;
42
43	return t;
44	}