src/system/kernel/util/Random.cpp

   1 /*
   2  * Copyright 2013 Haiku, Inc. All rights reserved.
   3  * Distributed under the terms of the MIT License.
   4  *
   5  * Authors:
   6  *              Paweł Dziepak, pdziepak@quarnos.org
   7  */
   8
   9
  10 #include <util/Random.h>
  11
  12 #include <OS.h>
  13
  14
  15 static uint32   sFastLast       = 0;
  16 static uint32   sLast           = 0;
  17 static uint32   sSecureLast     = 0;
  18
  19 // MD4 helper definitions, based on RFC 1320
  20 #define F(x, y, z)      (((x) & (y)) | (~(x) & (z)))
  21 #define G(x, y, z)      (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
  22 #define H(x, y, z)      ((x) ^ (y) ^ (z))
  23
  24 #define STEP(f, a, b, c, d, xk, s)      \
  25         (a += f((b), (c), (d)) + (xk), a = (a << (s)) | (a >> (32 - (s))))
  26
  27
  28 // MD4 based hash function. Simplified in order to improve performance.
  29 static uint32
  30 hash(uint32* data)
  31 {
  32                 const uint32 kMD4Round2 = 0x5a827999;
  33                 const uint32 kMD4Round3 = 0x6ed9eba1;
  34
  35                 uint32 a = 0x67452301;
  36                 uint32 b = 0xefcdab89;
  37                 uint32 c = 0x98badcfe;
  38                 uint32 d = 0x10325476;
  39
  40                 STEP(F, a, b, c, d, data[0], 3);
  41                 STEP(F, d, a, b, c, data[1], 7);
  42                 STEP(F, c, d, a, b, data[2], 11);
  43                 STEP(F, b, c, d, a, data[3], 19);
  44                 STEP(F, a, b, c, d, data[4], 3);
  45                 STEP(F, d, a, b, c, data[5], 7);
  46                 STEP(F, c, d, a, b, data[6], 11);
  47                 STEP(F, b, c, d, a, data[7], 19);
  48
  49                 STEP(G, a, b, c, d, data[1] + kMD4Round2, 3);
  50                 STEP(G, d, a, b, c, data[5] + kMD4Round2, 5);
  51                 STEP(G, c, d, a, b, data[6] + kMD4Round2, 9);
  52                 STEP(G, b, c, d, a, data[2] + kMD4Round2, 13);
  53                 STEP(G, a, b, c, d, data[3] + kMD4Round2, 3);
  54                 STEP(G, d, a, b, c, data[7] + kMD4Round2, 5);
  55                 STEP(G, c, d, a, b, data[4] + kMD4Round2, 9);
  56                 STEP(G, b, c, d, a, data[0] + kMD4Round2, 13);
  57
  58                 STEP(H, a, b, c, d, data[1] + kMD4Round3, 3);
  59                 STEP(H, d, a, b, c, data[6] + kMD4Round3, 9);
  60                 STEP(H, c, d, a, b, data[5] + kMD4Round3, 11);
  61                 STEP(H, b, c, d, a, data[2] + kMD4Round3, 15);
  62                 STEP(H, a, b, c, d, data[3] + kMD4Round3, 3);
  63                 STEP(H, d, a, b, c, data[4] + kMD4Round3, 9);
  64                 STEP(H, c, d, a, b, data[7] + kMD4Round3, 11);
  65                 STEP(H, b, c, d, a, data[0] + kMD4Round3, 15);
  66
  67                 return b;
  68 }
  69
  70
  71 // In the following functions there are race conditions when many threads
  72 // attempt to update static variable last. However, since such conflicts
  73 // are non-deterministic it is not a big problem.
  74
  75
  76 // A simple linear congruential generator
  77 unsigned int
  78 fast_random_value()
  79 {
  80         if (sFastLast == 0)
  81                 sFastLast = system_time();
  82
  83         uint32 random = sFastLast * 1103515245 + 12345;
  84         sFastLast = random;
  85         return (random >> 16) & 0x7fff;
  86 }
  87
  88
  89 // Taken from "Random number generators: good ones are hard to find",
  90 // Park and Miller, Communications of the ACM, vol. 31, no. 10,
  91 // October 1988, p. 1195.
  92 unsigned int
  93 random_value()
  94 {
  95         if (sLast == 0)
  96                 sLast = system_time();
  97
  98         uint32 hi = sLast / 127773;
  99         uint32 lo = sLast % 127773;
 100
 101         int32 random = 16807 * lo - 2836 * hi;
 102         if (random <= 0)
 103                 random += MAX_RANDOM_VALUE;
 104         sLast = random;
 105         return random % (MAX_RANDOM_VALUE + 1);
 106 }
 107
 108
 109 unsigned int
 110 secure_random_value()
 111 {
 112         static int32 count = 0;
 113
 114         uint32 data[8];
 115         data[0] = atomic_add(&count, 1);
 116         data[1] = system_time();
 117         data[2] = find_thread(NULL);
 118         data[3] = smp_get_current_cpu();
 119         data[4] = real_time_clock();
 120         data[5] = sFastLast;
 121         data[6] = sLast;
 122         data[7] = sSecureLast;
 123
 124         uint32 random = hash(data);
 125         sSecureLast = random;
 126         return random;
 127 }
 128