c_cpp/etc/calc/seed.c

   1 /*
   2  * seed - produce a pseudo-random seeds
   3  *
   4  * Copyright (C) 1999-2007  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  * @(#) $Revision: 30.1 $
  21  * @(#) $Id: seed.c,v 30.1 2007/03/16 11:09:46 chongo Exp $
  22  * @(#) $Source: /usr/local/src/bin/calc/RCS/seed.c,v $
  23  *
  24  * Under source code control:   1999/10/03 10:06:53
  25  * File existed as early as:    1999
  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  * Generate a quasi-random seed based on system and process information.
  33  *
  34  * NOTE: This is not a good source of chaotic data.  The LavaRnd
  35  *       system does a much better job of that.  See:
  36  *
  37  *              http://www.LavaRnd.org/
  38  */
  39
  40
  41 #include <stdio.h>
  42 #include <errno.h>
  43
  44 #include "have_stdlib.h"
  45 #if defined(HAVE_STDLIB_H)
  46 #include <stdlib.h>
  47 #endif
  48
  49 #include "have_unistd.h"
  50 #if defined(HAVE_UNISTD_H)
  51 #include <unistd.h>
  52 #endif
  53
  54 #if defined(_WIN32)
  55 # include <process.h>
  56 # define pid_t int
  57 #endif
  58
  59 /*
  60  * PORTING NOTE:
  61  *      These includes are used by pseudo_seed().  If for some
  62  *      reason some of these include files are missing or damaged
  63  *      on your system, feel free to remove them (and the related
  64  *      calls inside pseudo_seed()), add or replace them.  The
  65  *      pseudo_seed() function just needs to gather a bunch of
  66  *      information about the process and system state so the
  67  *      loss or inclusion of a few other calls should not hurt
  68  *      that much.
  69  */
  70 #include <sys/types.h>
  71 #include <sys/stat.h>
  72 #include "have_times.h"
  73 #if defined(HAVE_TIME_H)
  74 #include <time.h>
  75 #endif
  76 #if defined(HAVE_SYS_TIME_H)
  77 #include <sys/time.h>
  78 #endif
  79 #if defined(HAVE_SYS_TIMES_H)
  80 #include <sys/times.h>
  81 #endif
  82 #if !defined(_WIN32)
  83 # include <sys/resource.h>
  84 #endif
  85 #include <setjmp.h>
  86 #include "qmath.h"
  87 #include "longbits.h"
  88 #include "have_ustat.h"
  89 #include "have_getsid.h"
  90 #include "have_getpgid.h"
  91 #include "have_gettime.h"
  92 #include "have_getprid.h"
  93 #include "have_urandom.h"
  94 #include "have_rusage.h"
  95 #include "have_uid_t.h"
  96 #if defined(HAVE_USTAT)
  97 # include <ustat.h>
  98 #endif
  99 #if defined(HAVE_URANDOM)
 100 # include <fcntl.h>
 101 # define DEV_URANDOM "/dev/urandom"
 102 # define DEV_URANDOM_POOL 16
 103 #endif
 104
 105
 106 /*
 107  * 64 bit hash value
 108  */
 109 #if defined(HAVE_B64)
 110 typedef USB64 hash64;
 111 #else
 112 struct s_hash64 {
 113         USB32 w32[2];
 114 };
 115 typedef struct s_hash64 hash64;
 116 #endif
 117
 118
 119 /*
 120  * FNV-1 initial basis
 121  *
 122  * We start the hash at a non-zero value at the beginning so that
 123  * hashing blocks of data with all 0 bits do not map onto the same
 124  * 0 hash value.  The virgin value that we use below is the hash value
 125  * that we would get from following 32 ASCII characters:
 126  *
 127  *              chongo <Landon Curt Noll> /\../\
 128  *
 129  * Note that the \'s above are not back-slashing escape characters.
 130  * They are literal ASCII  backslash 0x5c characters.
 131  *
 132  * The effect of this virgin initial value is the same as starting
 133  * with 0 and pre-pending those 32 characters onto the data being
 134  * hashed.
 135  *
 136  * Yes, even with this non-zero virgin value there is a set of data
 137  * that will result in a zero hash value.  Worse, appending any
 138  * about of zero bytes will continue to produce a zero hash value.
 139  * But that would happen with any initial value so long as the
 140  * hash of the initial was the `inverse' of the virgin prefix string.
 141  *
 142  * But then again for any hash function, there exists sets of data
 143  * which that the hash of every member is the same value.  That is
 144  * life with many to few mapping functions.  All we do here is to
 145  * prevent sets whose members consist of 0 or more bytes of 0's from
 146  * being such an awkward set.
 147  *
 148  * And yes, someone can figure out what the magic 'inverse' of the
 149  * 32 ASCII character are ... but this hash function is NOT intended
 150  * to be a cryptographic hash function, just a fast and reasonably
 151  * good hash function.
 152  */
 153 #if defined(HAVE_B64)
 154 # define FNV1_64_BASIS ((hash64)(0xcbf29ce484222325ULL))
 155 #else
 156 # define FNV1_64_BASIS_0 ((USB32)0x2325)
 157 # define FNV1_64_BASIS_1 ((USB32)0x8422)
 158 # define FNV1_64_BASIS_2 ((USB32)0x9ce4)
 159 # define FNV1_64_BASIS_3 ((USB32)0xcbf2)
 160 #endif
 161
 162
 163 /*
 164  * hash_buf - perform a Fowler/Noll/Vo-1 64 bit hash
 165  *
 166  * input:
 167  *      buf     - start of buffer to hash
 168  *      len     - length of buffer in octets
 169  *      hval    - the hash value to modify
 170  *
 171  * returns:
 172  *      64 bit hash as a static hash64 structure
 173  */
 174 S_FUNC hash64
 175 hash_buf(char *buf, unsigned len)
 176 {
 177         hash64 hval;            /* current hash value */
 178 #if !defined(HAVE_B64)
 179         USB32 val[4];           /* hash value in base 2^16 */
 180         USB32 tmp[4];           /* tmp 64 bit value */
 181 #endif /* HAVE_B64 */
 182         char *buf_end = buf+len;        /* beyond end of hash area */
 183
 184         /*
 185          * FNV-1 - Fowler/Noll/Vo-1 64 bit hash
 186          *
 187          * The basis of this hash algorithm was taken from an idea sent
 188          * as reviewer comments to the IEEE POSIX P1003.2 committee by:
 189          *
 190          *      Phong Vo (http://www.research.att.com/info/kpv/)
 191          *      Glenn Fowler (http://www.research.att.com/~gsf/)
 192          *
 193          * In a subsequent ballot round:
 194          *
 195          *      Landon Curt Noll (http://www.isthe.com/chongo/)
 196          *
 197          * improved on their algorithm.  Some people tried this hash
 198          * and found that it worked rather well.  In an EMail message
 199          * to Landon, they named it ``Fowler/Noll/Vo'' or the FNV hash.
 200          *
 201          * FNV hashes are architected to be fast while maintaining a low
 202          * collision rate. The FNV speed allows one to quickly hash lots
 203          * of data while maintaining a reasonable collision rate.  See:
 204          *
 205          *      http://www.isthe.com/chongo/tech/comp/fnv/
 206          *
 207          * for more details as well as other forms of the FNV hash.
 208          */
 209 #if defined(HAVE_B64)
 210         /* hash each octet of the buffer */
 211         for (hval = FNV1_64_BASIS; buf < buf_end; ++buf) {
 212
 213             /* multiply by 1099511628211ULL mod 2^64 using 64 bit longs */
 214             hval *= (hash64)1099511628211ULL;
 215
 216             /* xor the bottom with the current octet */
 217             hval ^= (hash64)(*buf);
 218         }
 219
 220 #else /* HAVE_B64 */
 221
 222         /* hash each octet of the buffer */
 223         val[0] = FNV1_64_BASIS_0;
 224         val[1] = FNV1_64_BASIS_1;
 225         val[2] = FNV1_64_BASIS_2;
 226         val[3] = FNV1_64_BASIS_3;
 227         for (; buf < buf_end; ++buf) {
 228
 229             /*
 230              * multiply by 1099511628211 mod 2^64 using 32 bit longs
 231              *
 232              * Using 1099511628211, we have the following digits base 2^16:
 233              *
 234              *  0x0     0x100   0x0     0x1b3
 235              */
 236             /* multiply by the lowest order digit base 2^16 */
 237             tmp[0] = val[0] * 0x1b3;
 238             tmp[1] = val[1] * 0x1b3;
 239             tmp[2] = val[2] * 0x1b3;
 240             tmp[3] = val[3] * 0x1b3;
 241             /* multiply by the other non-zero digit */
 242             tmp[2] += val[0] << 8;              /* tmp[2] += val[0] * 0x100 */
 243             tmp[3] += val[1] << 8;              /* tmp[1] += val[1] * 0x100 */
 244             /* proapage carries */
 245             tmp[1] += (tmp[0] >> 16);
 246             val[0] = tmp[0] & 0xffff;
 247             tmp[2] += (tmp[1] >> 16);
 248             val[1] = tmp[1] & 0xffff;
 249             val[3] = tmp[3] + (tmp[2] >> 16);
 250             val[2] = tmp[2] & 0xffff;
 251             /*
 252              * Doing a val[3] &= 0xffff; is not really needed since it simply
 253              * removes multiples of 2^64.  We can discard these excess bits
 254              * outside of the loop when we convert to hash64.
 255              */
 256
 257             /* xor the bottom with the current octet */
 258             val[0] ^= (USB32)(*buf);
 259         }
 260
 261         /* convert to hash64 */
 262         /* hval.w32[1] = 0xffff&(val[3]<<16)+val[2]; */
 263         hval.w32[1] = (val[3]<<16) + val[2];
 264         hval.w32[0] = (val[1]<<16) + val[0];
 265
 266 #endif /* HAVE_B64 */
 267
 268         /* return our hash value */
 269         return hval;
 270 }
 271
 272
 273 /*
 274  * pseudo_seed - seed the generator with a quasi-random seed
 275  *
 276  * Generate a quasi-random seed based on system and process information.
 277  *
 278  * NOTE: This is not a good source of chaotic data.  The LavaRnd
 279  *       system does a much better job of that.  See:
 280  *
 281  *              http://www.LavaRnd.org/
 282  *
 283  * PORTING NOTE:
 284  *    If when porting this code to your system and something
 285  *    won't compile, just remove that line or replace it with
 286  *    some other system call.  We don't have to have every call
 287  *    operating below.  We only want to hash the resulting data.
 288  *
 289  * returns:
 290  *      a pseudo-seed as a NUMBER over the range [0, 2^64)
 291  */
 292 NUMBER *
 293 pseudo_seed(void)
 294 {
 295     struct {                    /* data used for quasi-random seed */
 296 #if defined(HAVE_GETTIME)
 297 # if defined(CLOCK_SGI_CYCLE)
 298         struct timespec sgi_cycle;      /* SGI hardware clock */
 299 # endif
 300 # if defined(CLOCK_REALTIME)
 301         struct timespec realtime;       /* POSIX realtime clock */
 302 # endif
 303 #endif
 304 #if defined(HAVE_GETPRID)
 305         prid_t getprid;                 /* project ID */
 306 #endif
 307 #if defined(HAVE_URANDOM)
 308         int urandom_fd;                 /* open descriptor for /dev/urandom */
 309         int urandom_ret;                /* read() of /dev/random */
 310         char urandom_pool[DEV_URANDOM_POOL];    /* /dev/urandom data pool */
 311 #endif
 312 #if defined(HAVE_SYS_TIME_H)
 313         struct timeval tp;              /* time of day */
 314 #endif
 315         pid_t getpid;                   /* process ID */
 316 #if !defined(_WIN32)
 317         pid_t getppid;                  /* parent process ID */
 318 #endif
 319 #if defined(HAVE_UID_T)
 320         uid_t getuid;                   /* real user ID */
 321         uid_t geteuid;                  /* effective user ID */
 322         gid_t getgid;                   /* real group ID */
 323         gid_t getegid;                  /* effective group ID */
 324 #endif
 325         struct stat stat_dot;           /* stat of "." */
 326         struct stat stat_dotdot;        /* stat of ".." */
 327         struct stat stat_tmp;           /* stat of "/tmp" */
 328         struct stat stat_root;          /* stat of "/" */
 329         struct stat fstat_stdin;        /* stat of stdin */
 330         struct stat fstat_stdout;       /* stat of stdout */
 331         struct stat fstat_stderr;       /* stat of stderr */
 332 #if defined(HAVE_USTAT)
 333         struct ustat ustat_dot;         /* usage stat of "." */
 334         struct ustat ustat_dotdot;      /* usage stat of ".." */
 335         struct ustat ustat_tmp;         /* usage stat of "/tmp" */
 336         struct ustat ustat_root;        /* usage stat of "/" */
 337         struct ustat ustat_stdin;       /* usage stat of stdin */
 338         struct ustat ustat_stdout;      /* usage stat of stdout */
 339         struct ustat ustat_stderr;      /* usage stat of stderr */
 340 #endif
 341 #if defined(HAVE_GETSID)
 342         pid_t getsid;                   /* session ID */
 343 #endif
 344 #if defined(HAVE_GETPGID)
 345         pid_t getpgid;                  /* process group ID */
 346 #endif
 347 #if defined(HAVE_GETRUSAGE)
 348         struct rusage rusage;           /* resource utilization */
 349         struct rusage rusage_chld;      /* resource utilization of children */
 350 #endif
 351 #if defined(HAVE_SYS_TIME_H)
 352         struct timeval tp2;             /* time of day again */
 353         struct tms times;               /* process times */
 354 #endif
 355         time_t time;                    /* local time */
 356         size_t size;                    /* size of this data structure */
 357         jmp_buf env;                    /* setjmp() context */
 358         char *sdata_p;                  /* address of this structure */
 359     } sdata;
 360     hash64 hash_val;                    /* fnv64 hash of sdata */
 361     ZVALUE hash;                        /* hash_val as a ZVALUE */
 362     NUMBER *ret;                        /* return seed as a NUMBER */
 363
 364     /*
 365      * pick up process/system information
 366      *
 367      * NOTE:
 368      *    We do care (that much) if these calls fail.  We do not
 369      *    need to process any data in the 'sdata' structure.
 370      */
 371 #if defined(HAVE_GETTIME)
 372 # if defined(CLOCK_SGI_CYCLE)
 373     (void) clock_gettime(CLOCK_SGI_CYCLE, &sdata.sgi_cycle);
 374 # endif
 375 # if defined(CLOCK_REALTIME)
 376     (void) clock_gettime(CLOCK_REALTIME, &sdata.realtime);
 377 # endif
 378 #endif
 379 #if defined(HAVE_GETPRID)
 380     sdata.getprid = getprid();
 381 #endif
 382 #if defined(HAVE_URANDOM)
 383     sdata.urandom_fd = open(DEV_URANDOM, O_NONBLOCK|O_RDONLY);
 384     if (sdata.urandom_fd >= 0) {
 385         sdata.urandom_ret = read(sdata.urandom_fd,
 386                                 &sdata.urandom_pool, DEV_URANDOM_POOL);
 387         close(sdata.urandom_fd);
 388     } else {
 389         memset(&sdata.urandom_pool, EOF, DEV_URANDOM_POOL);
 390         sdata.urandom_ret = EOF;
 391     }
 392 #endif /* HAVE_URANDOM */
 393 #if defined(HAVE_SYS_TIME_H)
 394     (void) gettimeofday(&sdata.tp, NULL);
 395 #endif
 396     sdata.getpid = getpid();
 397 #if !defined(_WIN32)
 398     sdata.getppid = getppid();
 399 #endif
 400 #if defined(HAVE_UID_T)
 401     sdata.getuid = getuid();
 402     sdata.geteuid = geteuid();
 403     sdata.getgid = getgid();
 404     sdata.getegid = getegid();
 405 #endif
 406     (void) stat(".", &sdata.stat_dot);
 407     (void) stat("..", &sdata.stat_dotdot);
 408     (void) stat("/tmp", &sdata.stat_tmp);
 409     (void) stat("/", &sdata.stat_root);
 410     (void) fstat(0, &sdata.fstat_stdin);
 411     (void) fstat(1, &sdata.fstat_stdout);
 412     (void) fstat(2, &sdata.fstat_stderr);
 413 #if defined(HAVE_USTAT)
 414     (void) ustat(sdata.stat_dotdot.st_dev, &sdata.ustat_dotdot);
 415     (void) ustat(sdata.stat_dot.st_dev, &sdata.ustat_dot);
 416     (void) ustat(sdata.stat_tmp.st_dev, &sdata.ustat_tmp);
 417     (void) ustat(sdata.stat_root.st_dev, &sdata.ustat_root);
 418     (void) ustat(sdata.fstat_stdin.st_dev, &sdata.ustat_stdin);
 419     (void) ustat(sdata.fstat_stdout.st_dev, &sdata.ustat_stdout);
 420     (void) ustat(sdata.fstat_stderr.st_dev, &sdata.ustat_stderr);
 421 #endif
 422 #if defined(HAVE_GETSID)
 423     sdata.getsid = getsid((pid_t)0);
 424 #endif
 425 #if defined(HAVE_GETPGID)
 426     sdata.getpgid = getpgid((pid_t)0);
 427 #endif
 428 #if defined(HAVE_GETRUSAGE)
 429     (void) getrusage(RUSAGE_SELF, &sdata.rusage);
 430     (void) getrusage(RUSAGE_CHILDREN, &sdata.rusage_chld);
 431 #endif
 432 #if defined(HAVE_SYS_TIME_H)
 433     (void) gettimeofday(&sdata.tp2, NULL);
 434     (void) times(&sdata.times);
 435 #endif
 436     sdata.time = time(NULL);
 437     sdata.size = sizeof(sdata);
 438     (void) setjmp(sdata.env);
 439     sdata.sdata_p = (char *)&sdata;
 440
 441     /*
 442      * seed the generator with the above data
 443      */
 444     hash_val = hash_buf((char *)&sdata, sizeof(sdata));
 445
 446     /*
 447      * load the hash data into the ZVALUE
 448      *
 449      * We do not care about byte-order or endian issues, we just
 450      * want to load in data.
 451      */
 452     hash.len = sizeof(hash_val) / sizeof(HALF);
 453     hash.v = alloc(hash.len);
 454     hash.sign = 0;
 455     memcpy((void *)hash.v, (void *)&hash_val, hash.len*sizeof(HALF));
 456     ztrim(&hash);
 457
 458     /*
 459      * return a number
 460      */
 461     ret = qalloc();
 462     ret->num = hash;
 463     return ret;
 464 }