1 /* 2 * zrand - subtractive 100 shuffle generator 3 * 4 * Copyright (C) 1999-2007,2014 Landon Curt Noll 5 * 6 * Calc is open software; you can redistribute it and/or modify it under 7 * the terms of the version 2.1 of the GNU Lesser General Public License 8 * as published by the Free Software Foundation. 9 * 10 * Calc is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General 13 * Public License for more details. 14 * 15 * A copy of version 2.1 of the GNU Lesser General Public License is 16 * distributed with calc under the filename COPYING-LGPL. You should have 17 * received a copy with calc; if not, write to Free Software Foundation, Inc. 18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 19 * 20 * Under source code control: 1995/01/07 09:45:26 21 * File existed as early as: 1994 22 * 23 * chongo <was here> /\oo/\ http://www.isthe.com/chongo/ 24 * Share and enjoy! :-) http://www.isthe.com/chongo/tech/comp/calc/ 25 */ 26 27 /* 28 * random number generator - see zrand.c for details 29 */ 30 31 32 #if !defined(INCLUDE_ZRAND_H) 33 #define INCLUDE_ZRAND_H 34 35 36 #if defined(CALC_SRC) /* if we are building from the calc source tree */ 37 # include "value.h" 38 # include "have_const.h" 39 #else 40 # include <calc/value.h> 41 # include <calc/have_const.h> 42 #endif 43 44 45 /* 46 * s100 generator defines 47 * 48 * NOTE: SBITS must be a power of two to make the (&= (SBITS-1)) 49 * in slotcp() to work. 50 */ 51 #define SBITS (64) /* size of subtractive or shuffle entry in bits */ 52 #define SBYTES (SBITS/8) /* size of subtractive or shuffle entry in bytes */ 53 #define SHALFS (SBYTES/sizeof(HALF)) /* size in HALFs */ 54 55 /* 56 * seed defines 57 */ 58 #define SEEDXORBITS 64 /* low bits of s100 seed devoted to xor */ 59 60 /* 61 * shuffle table defines 62 */ 63 #define SHUFPOW 8 /* power of 2 size of the shuffle table */ 64 #define SHUFCNT (1 << SHUFPOW) /* size of shuffle table */ 65 #define SHUFLEN (SLEN*SHUFCNT) /* length of shuffle table in FULLs */ 66 #define SHUFMASK (SHUFLEN-1) /* mask for shuffle table entry selection */ 67 68 /* 69 * subtractive 100 constants 70 */ 71 #define S100 100 /* slots in an subtractive 100 table */ 72 #define INIT_J 36 /* initial first walking table index */ 73 #define INIT_K 99 /* initial second walking table index */ 74 75 /* 76 * subtractive 100 table defines 77 * 78 * SLEN - length in FULLs of an subtractive 100 slot 79 * 80 * SLOAD(s,i,z) - load table slot i from subtractive 100 state s with zvalue z 81 * s: type RAND 82 * i: type int, s.slot[i] slot index 83 * z: type ZVALUE, what to load into s.slot[i] 84 * 85 * SSUB(s,k,j) - slot[k] -= slot[j] 86 * s: type RAND 87 * k: type int, s.slot[k] slot index, what to gets changed 88 * j: type int, s.slot[j] slot index, what to add to s.slot[k] 89 * (may use local variable tmp) 90 * 91 * SINDX(s,k) - select the shuffle table entry from slot[k] (uses top bits) 92 * s: type RAND 93 * k: type int, s.slot[k] slot index, selects shuffle entry 94 * result type int, refers to s.shuf[SINDX(s,k)] 95 * 96 * SBUFFER(s,t) - load s100 buffer with t 97 * s: type RAND 98 * t: type int, s.shuf[t] entry index, replace buffer with it 99 * 100 * SSHUF(s,t,k) - save slot[k] into shuffle entry t 101 * s: type RAND 102 * t: type int, s.shuf[t] entry index, what gets changed 103 * k: type int, s.slot[k] slot index, load into s.shuf[t] 104 * 105 * SSWAP(s,j,k) - swap slot[j] with slot[k] 106 * s: type RAND 107 * j: type int, s.slot[j] slot index, goes into s.slot[k] 108 * k: type int, s.slot[k] slot index, goes into s.slot[j] 109 * (uses local variable tmp) 110 * 111 * SMOD64(t,z) - t = seed z mod 2^64 112 * t: type FULL*, array of FULLs that get z mod 2^64 113 * z: type ZVALUE, what gets (mod 2^64) placed into t 114 * 115 * SOXR(s,i,v) - xor slot[i] with lower 64 bits of slot value v 116 * s: type RAND 117 * i: type int, s.slot[i] slot index, what gets xored 118 * v: type FULL*, 64 bit value to xor into s.slot[i] 119 * 120 * SCNT - length of an subtractive 100 table in FULLs 121 */ 122 #if FULL_BITS == SBITS 123 124 # define SLEN 1 /* a 64 bit slot can be held in a FULL */ 125 #define SLOAD(s,i,z) ((s).slot[i] = ztofull(z)) 126 #define SSUB(s,k,j) ((s).slot[k] -= (s).slot[j]) 127 #define SINDX(s,k) ((int)((s).slot[k] >> (FULL_BITS - SHUFPOW))) 128 #define SBUFFER(s,t) {(s).buffer[0] = ((s).shuf[t] & BASE1); \ 129 (s).buffer[1] = ((s).shuf[t] >> BASEB); \ 130 } 131 #define SSHUF(s,t,k) ((s).shuf[t] = (s).slot[k]) 132 #define SSWAP(s,j,k) {FULL tmp = (s).slot[j]; \ 133 (s).slot[j] = (s).slot[k]; \ 134 (s).slot[k] = tmp; \ 135 } 136 #define SMOD64(t,z) ((t)[0] = ztofull(z)) 137 #define SXOR(s,i,v) ((s).slot[i] ^= (v)[0]) 138 139 #elif 2*FULL_BITS == SBITS 140 141 # define SLEN 2 /* a 64 bit slot needs 2 FULLs */ 142 #define SLOAD(s,i,z) {(s).slot[(i)<<1] = ztofull(z); \ 143 (s).slot[1+((i)<<1)] = \ 144 (((z).len <= 2) ? (FULL)0 : \ 145 (((z).len == 3) ? (FULL)((z).v[2]) : \ 146 ((FULL)((z).v[2]) + ((FULL)((z).v[3]) << BASEB)))); \ 147 } 148 #define SSUB(s,k,j) {FULL tmp = (s).slot[(k)<<1]; \ 149 (s).slot[(k)<<1] -= (s).slot[(j)<<1]; \ 150 (s).slot[1+((k)<<1)] -= ((tmp <= (s).slot[(k)<<1]) ? \ 151 (s).slot[1+((j)<<1)] : \ 152 (s).slot[1+((j)<<1)] + 1); \ 153 } 154 #define SINDX(s,k) ((int)((s).slot[1+((k)<<1)] >> (FULL_BITS - SHUFPOW))) 155 #define SBUFFER(s,t) {(s).buffer[0] = ((s).shuf[(t)<<1] & BASE1); \ 156 (s).buffer[1] = ((s).shuf[(t)<<1] >> BASEB); \ 157 (s).buffer[2] = ((s).shuf[1+((t)<<1)] & BASE1); \ 158 (s).buffer[3] = ((s).shuf[1+((t)<<1)] >> BASEB); \ 159 } 160 #define SSHUF(s,t,k) {(s).shuf[(t)<<1] = (s).slot[(k)<<1]; \ 161 (s).shuf[1+((t)<<1)] = (s).slot[1+((k)<<1)]; \ 162 } 163 #define SSWAP(s,j,k) {FULL tmp = (s).slot[(j)<<1]; \ 164 (s).slot[(j)<<1] = (s).slot[(k)<<1]; \ 165 (s).slot[(k)<<1] = tmp; \ 166 tmp = (s).slot[1+((j)<<1)]; \ 167 (s).slot[1+((j)<<1)] = (s).slot[1+((k)<<1)]; \ 168 (s).slot[1+((k)<<1)] = tmp; \ 169 } 170 #define SMOD64(t,z) {(t)[0] = ztofull(z); \ 171 (t)[1] = (((z).len <= 2) ? (FULL)0 : \ 172 (((z).len == 3) ? (FULL)((z).v[2]) : \ 173 ((FULL)((z).v[2]) + ((FULL)((z).v[3]) << BASEB)))); \ 174 } 175 #define SXOR(s,i,v) {(s).slot[(i)<<1] ^= (v)[0]; \ 176 (s).slot[1+((i)<<1)] ^= (v)[1]; \ 177 } 178 179 #else 180 181 /\../\ FULL_BITS must be 32 or 64 /\../\ !!! 182 183 #endif 184 185 #define SCNT (SLEN*S100) /* length of subtractive 100 table in FULLs */ 186 187 #define RAND_CONSEQ_USE (100) /* use this many before skipping */ 188 #define RAND_SKIP (1009-RAND_CONSEQ_USE) /* skip this many after use */ 189 190 191 /* 192 * s100 generator state 193 */ 194 struct rand { 195 int seeded; /* 1 => state has been seeded */ 196 int bits; /* buffer bit count */ 197 FULL buffer[SLEN]; /* unused random bits from last call */ 198 int j; /* first walking table index */ 199 int k; /* second walking table index */ 200 int need_to_skip; /* 1 => skip the next 909 values */ 201 FULL slot[SCNT]; /* subtractive 100 table */ 202 FULL shuf[SHUFLEN]; /* shuffle table entries */ 203 }; 204 205 206 /* 207 * s100 generator function declarations 208 */ 209 E_FUNC RAND *zsrand(CONST ZVALUE *seed, CONST MATRIX *pmat100); 210 E_FUNC RAND *zsetrand(CONST RAND *state); 211 E_FUNC void zrandskip(long count); 212 E_FUNC void zrand(long count, ZVALUE *res); 213 E_FUNC void zrandrange(CONST ZVALUE low, CONST ZVALUE beyond, ZVALUE *res); 214 E_FUNC long irand(long s); 215 E_FUNC RAND *randcopy(CONST RAND *rand); 216 E_FUNC void randfree(RAND *rand); 217 E_FUNC BOOL randcmp(CONST RAND *s1, CONST RAND *s2); 218 E_FUNC void randprint(CONST RAND *state, int flags); 219 220 221 #endif /* !INCLUDE_ZRAND_H */ 222