calc/calc/zrand.h

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