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 vint32 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 129