1275970Scy/* Portable arc4random.c based on arc4random.c from OpenBSD. 2275970Scy * Portable version by Chris Davis, adapted for Libevent by Nick Mathewson 3275970Scy * Copyright (c) 2010 Chris Davis, Niels Provos, and Nick Mathewson 4275970Scy * Copyright (c) 2010-2012 Niels Provos and Nick Mathewson 5275970Scy * 6275970Scy * Note that in Libevent, this file isn't compiled directly. Instead, 7275970Scy * it's included from evutil_rand.c 8275970Scy */ 9275970Scy 10275970Scy/* 11275970Scy * Copyright (c) 1996, David Mazieres <dm@uun.org> 12275970Scy * Copyright (c) 2008, Damien Miller <djm@openbsd.org> 13275970Scy * 14275970Scy * Permission to use, copy, modify, and distribute this software for any 15275970Scy * purpose with or without fee is hereby granted, provided that the above 16275970Scy * copyright notice and this permission notice appear in all copies. 17275970Scy * 18275970Scy * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 19275970Scy * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 20275970Scy * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 21275970Scy * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 22275970Scy * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 23275970Scy * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 24275970Scy * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 25275970Scy */ 26275970Scy 27275970Scy/* 28275970Scy * Arc4 random number generator for OpenBSD. 29275970Scy * 30275970Scy * This code is derived from section 17.1 of Applied Cryptography, 31275970Scy * second edition, which describes a stream cipher allegedly 32275970Scy * compatible with RSA Labs "RC4" cipher (the actual description of 33275970Scy * which is a trade secret). The same algorithm is used as a stream 34275970Scy * cipher called "arcfour" in Tatu Ylonen's ssh package. 35275970Scy * 36275970Scy * Here the stream cipher has been modified always to include the time 37275970Scy * when initializing the state. That makes it impossible to 38275970Scy * regenerate the same random sequence twice, so this can't be used 39275970Scy * for encryption, but will generate good random numbers. 40275970Scy * 41275970Scy * RC4 is a registered trademark of RSA Laboratories. 42275970Scy */ 43275970Scy 44275970Scy#ifndef ARC4RANDOM_EXPORT 45275970Scy#define ARC4RANDOM_EXPORT 46275970Scy#endif 47275970Scy 48275970Scy#ifndef ARC4RANDOM_UINT32 49275970Scy#define ARC4RANDOM_UINT32 uint32_t 50275970Scy#endif 51275970Scy 52275970Scy#ifndef ARC4RANDOM_NO_INCLUDES 53275970Scy#include "evconfig-private.h" 54275970Scy#ifdef _WIN32 55275970Scy#include <wincrypt.h> 56275970Scy#include <process.h> 57275970Scy#else 58275970Scy#include <fcntl.h> 59275970Scy#include <unistd.h> 60275970Scy#include <sys/param.h> 61275970Scy#include <sys/time.h> 62275970Scy#ifdef EVENT__HAVE_SYS_SYSCTL_H 63275970Scy#include <sys/sysctl.h> 64275970Scy#endif 65275970Scy#endif 66275970Scy#include <limits.h> 67275970Scy#include <stdlib.h> 68275970Scy#include <string.h> 69275970Scy#endif 70275970Scy 71275970Scy/* Add platform entropy 32 bytes (256 bits) at a time. */ 72275970Scy#define ADD_ENTROPY 32 73275970Scy 74275970Scy/* Re-seed from the platform RNG after generating this many bytes. */ 75275970Scy#define BYTES_BEFORE_RESEED 1600000 76275970Scy 77275970Scystruct arc4_stream { 78275970Scy unsigned char i; 79275970Scy unsigned char j; 80275970Scy unsigned char s[256]; 81275970Scy}; 82275970Scy 83275970Scy#ifdef _WIN32 84275970Scy#define getpid _getpid 85275970Scy#define pid_t int 86275970Scy#endif 87275970Scy 88275970Scystatic int rs_initialized; 89275970Scystatic struct arc4_stream rs; 90275970Scystatic pid_t arc4_stir_pid; 91275970Scystatic int arc4_count; 92275970Scystatic int arc4_seeded_ok; 93275970Scy 94275970Scystatic inline unsigned char arc4_getbyte(void); 95275970Scy 96275970Scystatic inline void 97275970Scyarc4_init(void) 98275970Scy{ 99275970Scy int n; 100275970Scy 101275970Scy for (n = 0; n < 256; n++) 102275970Scy rs.s[n] = n; 103275970Scy rs.i = 0; 104275970Scy rs.j = 0; 105275970Scy} 106275970Scy 107275970Scystatic inline void 108275970Scyarc4_addrandom(const unsigned char *dat, int datlen) 109275970Scy{ 110275970Scy int n; 111275970Scy unsigned char si; 112275970Scy 113275970Scy rs.i--; 114275970Scy for (n = 0; n < 256; n++) { 115275970Scy rs.i = (rs.i + 1); 116275970Scy si = rs.s[rs.i]; 117275970Scy rs.j = (rs.j + si + dat[n % datlen]); 118275970Scy rs.s[rs.i] = rs.s[rs.j]; 119275970Scy rs.s[rs.j] = si; 120275970Scy } 121275970Scy rs.j = rs.i; 122275970Scy} 123275970Scy 124275970Scy#ifndef _WIN32 125275970Scystatic ssize_t 126275970Scyread_all(int fd, unsigned char *buf, size_t count) 127275970Scy{ 128275970Scy size_t numread = 0; 129275970Scy ssize_t result; 130275970Scy 131275970Scy while (numread < count) { 132275970Scy result = read(fd, buf+numread, count-numread); 133275970Scy if (result<0) 134275970Scy return -1; 135275970Scy else if (result == 0) 136275970Scy break; 137275970Scy numread += result; 138275970Scy } 139275970Scy 140275970Scy return (ssize_t)numread; 141275970Scy} 142275970Scy#endif 143275970Scy 144275970Scy#ifdef _WIN32 145275970Scy#define TRY_SEED_WIN32 146275970Scystatic int 147275970Scyarc4_seed_win32(void) 148275970Scy{ 149275970Scy /* This is adapted from Tor's crypto_seed_rng() */ 150275970Scy static int provider_set = 0; 151275970Scy static HCRYPTPROV provider; 152275970Scy unsigned char buf[ADD_ENTROPY]; 153275970Scy 154275970Scy if (!provider_set) { 155275970Scy if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL, 156275970Scy CRYPT_VERIFYCONTEXT)) { 157275970Scy if (GetLastError() != (DWORD)NTE_BAD_KEYSET) 158275970Scy return -1; 159275970Scy } 160275970Scy provider_set = 1; 161275970Scy } 162275970Scy if (!CryptGenRandom(provider, sizeof(buf), buf)) 163275970Scy return -1; 164275970Scy arc4_addrandom(buf, sizeof(buf)); 165275970Scy evutil_memclear_(buf, sizeof(buf)); 166275970Scy arc4_seeded_ok = 1; 167275970Scy return 0; 168275970Scy} 169275970Scy#endif 170275970Scy 171275970Scy#if defined(EVENT__HAVE_SYS_SYSCTL_H) && defined(EVENT__HAVE_SYSCTL) 172275970Scy#if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_RANDOM && EVENT__HAVE_DECL_RANDOM_UUID 173275970Scy#define TRY_SEED_SYSCTL_LINUX 174275970Scystatic int 175275970Scyarc4_seed_sysctl_linux(void) 176275970Scy{ 177275970Scy /* Based on code by William Ahern, this function tries to use the 178275970Scy * RANDOM_UUID sysctl to get entropy from the kernel. This can work 179275970Scy * even if /dev/urandom is inaccessible for some reason (e.g., we're 180275970Scy * running in a chroot). */ 181275970Scy int mib[] = { CTL_KERN, KERN_RANDOM, RANDOM_UUID }; 182275970Scy unsigned char buf[ADD_ENTROPY]; 183275970Scy size_t len, n; 184275970Scy unsigned i; 185275970Scy int any_set; 186275970Scy 187275970Scy memset(buf, 0, sizeof(buf)); 188275970Scy 189275970Scy for (len = 0; len < sizeof(buf); len += n) { 190275970Scy n = sizeof(buf) - len; 191275970Scy 192275970Scy if (0 != sysctl(mib, 3, &buf[len], &n, NULL, 0)) 193275970Scy return -1; 194275970Scy } 195275970Scy /* make sure that the buffer actually got set. */ 196275970Scy for (i=0,any_set=0; i<sizeof(buf); ++i) { 197275970Scy any_set |= buf[i]; 198275970Scy } 199275970Scy if (!any_set) 200275970Scy return -1; 201275970Scy 202275970Scy arc4_addrandom(buf, sizeof(buf)); 203275970Scy evutil_memclear_(buf, sizeof(buf)); 204275970Scy arc4_seeded_ok = 1; 205275970Scy return 0; 206275970Scy} 207275970Scy#endif 208275970Scy 209275970Scy#if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_ARND 210275970Scy#define TRY_SEED_SYSCTL_BSD 211275970Scystatic int 212275970Scyarc4_seed_sysctl_bsd(void) 213275970Scy{ 214275970Scy /* Based on code from William Ahern and from OpenBSD, this function 215275970Scy * tries to use the KERN_ARND syscall to get entropy from the kernel. 216275970Scy * This can work even if /dev/urandom is inaccessible for some reason 217275970Scy * (e.g., we're running in a chroot). */ 218275970Scy int mib[] = { CTL_KERN, KERN_ARND }; 219275970Scy unsigned char buf[ADD_ENTROPY]; 220275970Scy size_t len, n; 221275970Scy int i, any_set; 222275970Scy 223275970Scy memset(buf, 0, sizeof(buf)); 224275970Scy 225275970Scy len = sizeof(buf); 226275970Scy if (sysctl(mib, 2, buf, &len, NULL, 0) == -1) { 227275970Scy for (len = 0; len < sizeof(buf); len += sizeof(unsigned)) { 228275970Scy n = sizeof(unsigned); 229275970Scy if (n + len > sizeof(buf)) 230275970Scy n = len - sizeof(buf); 231275970Scy if (sysctl(mib, 2, &buf[len], &n, NULL, 0) == -1) 232275970Scy return -1; 233275970Scy } 234275970Scy } 235275970Scy /* make sure that the buffer actually got set. */ 236275970Scy for (i=any_set=0; i<sizeof(buf); ++i) { 237275970Scy any_set |= buf[i]; 238275970Scy } 239275970Scy if (!any_set) 240275970Scy return -1; 241275970Scy 242275970Scy arc4_addrandom(buf, sizeof(buf)); 243275970Scy evutil_memclear_(buf, sizeof(buf)); 244275970Scy arc4_seeded_ok = 1; 245275970Scy return 0; 246275970Scy} 247275970Scy#endif 248275970Scy#endif /* defined(EVENT__HAVE_SYS_SYSCTL_H) */ 249275970Scy 250275970Scy#ifdef __linux__ 251275970Scy#define TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID 252275970Scystatic int 253275970Scyarc4_seed_proc_sys_kernel_random_uuid(void) 254275970Scy{ 255275970Scy /* Occasionally, somebody will make /proc/sys accessible in a chroot, 256275970Scy * but not /dev/urandom. Let's try /proc/sys/kernel/random/uuid. 257275970Scy * Its format is stupid, so we need to decode it from hex. 258275970Scy */ 259275970Scy int fd; 260275970Scy char buf[128]; 261275970Scy unsigned char entropy[64]; 262275970Scy int bytes, n, i, nybbles; 263275970Scy for (bytes = 0; bytes<ADD_ENTROPY; ) { 264275970Scy fd = evutil_open_closeonexec_("/proc/sys/kernel/random/uuid", O_RDONLY, 0); 265275970Scy if (fd < 0) 266275970Scy return -1; 267275970Scy n = read(fd, buf, sizeof(buf)); 268275970Scy close(fd); 269275970Scy if (n<=0) 270275970Scy return -1; 271275970Scy memset(entropy, 0, sizeof(entropy)); 272275970Scy for (i=nybbles=0; i<n; ++i) { 273275970Scy if (EVUTIL_ISXDIGIT_(buf[i])) { 274275970Scy int nyb = evutil_hex_char_to_int_(buf[i]); 275275970Scy if (nybbles & 1) { 276275970Scy entropy[nybbles/2] |= nyb; 277275970Scy } else { 278275970Scy entropy[nybbles/2] |= nyb<<4; 279275970Scy } 280275970Scy ++nybbles; 281275970Scy } 282275970Scy } 283275970Scy if (nybbles < 2) 284275970Scy return -1; 285275970Scy arc4_addrandom(entropy, nybbles/2); 286275970Scy bytes += nybbles/2; 287275970Scy } 288275970Scy evutil_memclear_(entropy, sizeof(entropy)); 289275970Scy evutil_memclear_(buf, sizeof(buf)); 290275970Scy arc4_seeded_ok = 1; 291275970Scy return 0; 292275970Scy} 293275970Scy#endif 294275970Scy 295275970Scy#ifndef _WIN32 296275970Scy#define TRY_SEED_URANDOM 297275970Scystatic char *arc4random_urandom_filename = NULL; 298275970Scy 299275970Scystatic int arc4_seed_urandom_helper_(const char *fname) 300275970Scy{ 301275970Scy unsigned char buf[ADD_ENTROPY]; 302275970Scy int fd; 303275970Scy size_t n; 304275970Scy 305275970Scy fd = evutil_open_closeonexec_(fname, O_RDONLY, 0); 306275970Scy if (fd<0) 307275970Scy return -1; 308275970Scy n = read_all(fd, buf, sizeof(buf)); 309275970Scy close(fd); 310275970Scy if (n != sizeof(buf)) 311275970Scy return -1; 312275970Scy arc4_addrandom(buf, sizeof(buf)); 313275970Scy evutil_memclear_(buf, sizeof(buf)); 314275970Scy arc4_seeded_ok = 1; 315275970Scy return 0; 316275970Scy} 317275970Scy 318275970Scystatic int 319275970Scyarc4_seed_urandom(void) 320275970Scy{ 321275970Scy /* This is adapted from Tor's crypto_seed_rng() */ 322275970Scy static const char *filenames[] = { 323275970Scy "/dev/srandom", "/dev/urandom", "/dev/random", NULL 324275970Scy }; 325275970Scy int i; 326275970Scy if (arc4random_urandom_filename) 327275970Scy return arc4_seed_urandom_helper_(arc4random_urandom_filename); 328275970Scy 329275970Scy for (i = 0; filenames[i]; ++i) { 330275970Scy if (arc4_seed_urandom_helper_(filenames[i]) == 0) { 331275970Scy return 0; 332275970Scy } 333275970Scy } 334275970Scy 335275970Scy return -1; 336275970Scy} 337275970Scy#endif 338275970Scy 339275970Scystatic int 340275970Scyarc4_seed(void) 341275970Scy{ 342275970Scy int ok = 0; 343275970Scy /* We try every method that might work, and don't give up even if one 344275970Scy * does seem to work. There's no real harm in over-seeding, and if 345275970Scy * one of these sources turns out to be broken, that would be bad. */ 346275970Scy#ifdef TRY_SEED_WIN32 347275970Scy if (0 == arc4_seed_win32()) 348275970Scy ok = 1; 349275970Scy#endif 350275970Scy#ifdef TRY_SEED_URANDOM 351275970Scy if (0 == arc4_seed_urandom()) 352275970Scy ok = 1; 353275970Scy#endif 354275970Scy#ifdef TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID 355275970Scy if (arc4random_urandom_filename == NULL && 356275970Scy 0 == arc4_seed_proc_sys_kernel_random_uuid()) 357275970Scy ok = 1; 358275970Scy#endif 359275970Scy#ifdef TRY_SEED_SYSCTL_LINUX 360275970Scy /* Apparently Linux is deprecating sysctl, and spewing warning 361275970Scy * messages when you try to use it. */ 362275970Scy if (!ok && 0 == arc4_seed_sysctl_linux()) 363275970Scy ok = 1; 364275970Scy#endif 365275970Scy#ifdef TRY_SEED_SYSCTL_BSD 366275970Scy if (0 == arc4_seed_sysctl_bsd()) 367275970Scy ok = 1; 368275970Scy#endif 369275970Scy return ok ? 0 : -1; 370275970Scy} 371275970Scy 372275970Scystatic int 373275970Scyarc4_stir(void) 374275970Scy{ 375275970Scy int i; 376275970Scy 377275970Scy if (!rs_initialized) { 378275970Scy arc4_init(); 379275970Scy rs_initialized = 1; 380275970Scy } 381275970Scy 382275970Scy arc4_seed(); 383275970Scy if (!arc4_seeded_ok) 384275970Scy return -1; 385275970Scy 386275970Scy /* 387275970Scy * Discard early keystream, as per recommendations in 388275970Scy * "Weaknesses in the Key Scheduling Algorithm of RC4" by 389275970Scy * Scott Fluhrer, Itsik Mantin, and Adi Shamir. 390275970Scy * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 391275970Scy * 392275970Scy * Ilya Mironov's "(Not So) Random Shuffles of RC4" suggests that 393275970Scy * we drop at least 2*256 bytes, with 12*256 as a conservative 394275970Scy * value. 395275970Scy * 396275970Scy * RFC4345 says to drop 6*256. 397275970Scy * 398275970Scy * At least some versions of this code drop 4*256, in a mistaken 399275970Scy * belief that "words" in the Fluhrer/Mantin/Shamir paper refers 400275970Scy * to processor words. 401275970Scy * 402275970Scy * We add another sect to the cargo cult, and choose 12*256. 403275970Scy */ 404275970Scy for (i = 0; i < 12*256; i++) 405275970Scy (void)arc4_getbyte(); 406275970Scy 407275970Scy arc4_count = BYTES_BEFORE_RESEED; 408275970Scy 409275970Scy return 0; 410275970Scy} 411275970Scy 412275970Scy 413275970Scystatic void 414275970Scyarc4_stir_if_needed(void) 415275970Scy{ 416275970Scy pid_t pid = getpid(); 417275970Scy 418275970Scy if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) 419275970Scy { 420275970Scy arc4_stir_pid = pid; 421275970Scy arc4_stir(); 422275970Scy } 423275970Scy} 424275970Scy 425275970Scystatic inline unsigned char 426275970Scyarc4_getbyte(void) 427275970Scy{ 428275970Scy unsigned char si, sj; 429275970Scy 430275970Scy rs.i = (rs.i + 1); 431275970Scy si = rs.s[rs.i]; 432275970Scy rs.j = (rs.j + si); 433275970Scy sj = rs.s[rs.j]; 434275970Scy rs.s[rs.i] = sj; 435275970Scy rs.s[rs.j] = si; 436275970Scy return (rs.s[(si + sj) & 0xff]); 437275970Scy} 438275970Scy 439275970Scystatic inline unsigned int 440275970Scyarc4_getword(void) 441275970Scy{ 442275970Scy unsigned int val; 443275970Scy 444275970Scy val = arc4_getbyte() << 24; 445275970Scy val |= arc4_getbyte() << 16; 446275970Scy val |= arc4_getbyte() << 8; 447275970Scy val |= arc4_getbyte(); 448275970Scy 449275970Scy return val; 450275970Scy} 451275970Scy 452275970Scy#ifndef ARC4RANDOM_NOSTIR 453275970ScyARC4RANDOM_EXPORT int 454275970Scyarc4random_stir(void) 455275970Scy{ 456275970Scy int val; 457275970Scy ARC4_LOCK_(); 458275970Scy val = arc4_stir(); 459275970Scy ARC4_UNLOCK_(); 460275970Scy return val; 461275970Scy} 462275970Scy#endif 463275970Scy 464275970Scy#ifndef ARC4RANDOM_NOADDRANDOM 465275970ScyARC4RANDOM_EXPORT void 466275970Scyarc4random_addrandom(const unsigned char *dat, int datlen) 467275970Scy{ 468275970Scy int j; 469275970Scy ARC4_LOCK_(); 470275970Scy if (!rs_initialized) 471275970Scy arc4_stir(); 472275970Scy for (j = 0; j < datlen; j += 256) { 473275970Scy /* arc4_addrandom() ignores all but the first 256 bytes of 474275970Scy * its input. We want to make sure to look at ALL the 475275970Scy * data in 'dat', just in case the user is doing something 476275970Scy * crazy like passing us all the files in /var/log. */ 477275970Scy arc4_addrandom(dat + j, datlen - j); 478275970Scy } 479275970Scy ARC4_UNLOCK_(); 480275970Scy} 481275970Scy#endif 482275970Scy 483275970Scy#ifndef ARC4RANDOM_NORANDOM 484275970ScyARC4RANDOM_EXPORT ARC4RANDOM_UINT32 485275970Scyarc4random(void) 486275970Scy{ 487275970Scy ARC4RANDOM_UINT32 val; 488275970Scy ARC4_LOCK_(); 489275970Scy arc4_count -= 4; 490275970Scy arc4_stir_if_needed(); 491275970Scy val = arc4_getword(); 492275970Scy ARC4_UNLOCK_(); 493275970Scy return val; 494275970Scy} 495275970Scy#endif 496275970Scy 497275970ScyARC4RANDOM_EXPORT void 498275970Scyarc4random_buf(void *buf_, size_t n) 499275970Scy{ 500275970Scy unsigned char *buf = buf_; 501275970Scy ARC4_LOCK_(); 502275970Scy arc4_stir_if_needed(); 503275970Scy while (n--) { 504275970Scy if (--arc4_count <= 0) 505275970Scy arc4_stir(); 506275970Scy buf[n] = arc4_getbyte(); 507275970Scy } 508275970Scy ARC4_UNLOCK_(); 509275970Scy} 510275970Scy 511275970Scy#ifndef ARC4RANDOM_NOUNIFORM 512275970Scy/* 513275970Scy * Calculate a uniformly distributed random number less than upper_bound 514275970Scy * avoiding "modulo bias". 515275970Scy * 516275970Scy * Uniformity is achieved by generating new random numbers until the one 517275970Scy * returned is outside the range [0, 2**32 % upper_bound). This 518275970Scy * guarantees the selected random number will be inside 519275970Scy * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 520275970Scy * after reduction modulo upper_bound. 521275970Scy */ 522275970ScyARC4RANDOM_EXPORT unsigned int 523275970Scyarc4random_uniform(unsigned int upper_bound) 524275970Scy{ 525275970Scy ARC4RANDOM_UINT32 r, min; 526275970Scy 527275970Scy if (upper_bound < 2) 528275970Scy return 0; 529275970Scy 530275970Scy#if (UINT_MAX > 0xffffffffUL) 531275970Scy min = 0x100000000UL % upper_bound; 532275970Scy#else 533275970Scy /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ 534275970Scy if (upper_bound > 0x80000000) 535275970Scy min = 1 + ~upper_bound; /* 2**32 - upper_bound */ 536275970Scy else { 537275970Scy /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ 538275970Scy min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; 539275970Scy } 540275970Scy#endif 541275970Scy 542275970Scy /* 543275970Scy * This could theoretically loop forever but each retry has 544275970Scy * p > 0.5 (worst case, usually far better) of selecting a 545275970Scy * number inside the range we need, so it should rarely need 546275970Scy * to re-roll. 547275970Scy */ 548275970Scy for (;;) { 549275970Scy r = arc4random(); 550275970Scy if (r >= min) 551275970Scy break; 552275970Scy } 553275970Scy 554275970Scy return r % upper_bound; 555275970Scy} 556275970Scy#endif 557