Changeset 145179 in webkit


Ignore:
Timestamp:
Mar 7, 2013 9:49:46 PM (11 years ago)
Author:
commit-queue@webkit.org
Message:

Source/ThirdParty: Replace Mersenne Twister RNG with a simple but fast RNG
​https://bugs.webkit.org/show_bug.cgi?id=111533

Patch by Andrew Bortz <​andrew@abortz.net> on 2013-03-07
Reviewed by Adam Barth.

This code is no longer used.

  • mt19937ar.c: Removed.

Source/WTF: Replace Mersenne Twister random number generator with a simpler one.
​https://bugs.webkit.org/show_bug.cgi?id=111533

Patch by Andrew Bortz <​andrew@abortz.net> on 2013-03-07
Reviewed by Adam Barth.

The new generator is only a single line long, but passes all the Diehard
statistical tests and runs ~3x faster than the Mersenne Twister, with a
guaranteed cycle length of 264 and only 8 bytes of state.

  • wtf/Platform.h: Mersenne Twister defines are no longer needed
  • wtf/RandomNumber.cpp:

(WTF::Internal::initializeRandomNumber): State initialization
(WTF::Internal::randomNumber): Actual implementation
(WTF::randomNumber): We don't need to fall back on rand()-based generator anymore,
so this code is greatly simplified.

  • wtf/RandomNumber.h:
  • wtf/RandomNumberSeed.h:

(WTF::initializeRandomNumberGenerator): This code is no longer needed.
Additionally, the code had an error, since rand() returns 32-bits, so each
initializationBuffer's upper 16-bits has more bits set than random.

Location:
trunk/Source
Files:
1 deleted
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/ThirdParty/ChangeLog

    r143529 r145179  
     12013-03-07  Andrew Bortz  <andrew@abortz.net>
     2
     3        Replace Mersenne Twister RNG with a simple but fast RNG
     4        https://bugs.webkit.org/show_bug.cgi?id=111533
     5
     6        Reviewed by Adam Barth.
     7
     8        This code is no longer used.
     9
     10        * mt19937ar.c: Removed.
     11
    1122013-02-20  Roger Fong  <roger_fong@apple.com>
    213

  • trunk/Source/WTF/ChangeLog

    r145022 r145179  
     12013-03-07  Andrew Bortz  <andrew@abortz.net>
     2
     3        Replace Mersenne Twister random number generator with a simpler one.
     4        https://bugs.webkit.org/show_bug.cgi?id=111533
     5
     6        Reviewed by Adam Barth.
     7
     8        The new generator is only a single line long, but passes all the Diehard
     9        statistical tests and runs ~3x faster than the Mersenne Twister, with a
     10        guaranteed cycle length of 2^64 and only 8 bytes of state.
     11       
     12        * wtf/Platform.h: Mersenne Twister defines are no longer needed
     13        * wtf/RandomNumber.cpp:
     14        (WTF::Internal::initializeRandomNumber): State initialization
     15        (WTF::Internal::randomNumber): Actual implementation
     16        (WTF::randomNumber): We don't need to fall back on rand()-based generator anymore,
     17        so this code is greatly simplified.
     18        * wtf/RandomNumber.h:
     19        * wtf/RandomNumberSeed.h:
     20        (WTF::initializeRandomNumberGenerator): This code is no longer needed.
     21        Additionally, the code had an error, since rand() returns 32-bits, so each
     22        initializationBuffer's upper 16-bits has more bits set than random.
     23
    1242013-03-06  Adenilson Cavalcanti  <cavalcantii@gmail.com>
    225

  • trunk/Source/WTF/wtf/Platform.h

    r144337 r145179  
    503503
    504504#if PLATFORM(BLACKBERRY)
    505 #define WTF_USE_MERSENNE_TWISTER_19937 1
    506505#define WTF_USE_SKIA 1
    507506#define WTF_USE_LOW_QUALITY_IMAGE_INTERPOLATION 1
    … …  
    513512#define WTF_USE_CAIRO 1
    514513#define ENABLE_GLOBAL_FASTMALLOC_NEW 0
    515 #endif
    516 
    517 
    518 #if OS(WINCE)
    519 #define WTF_USE_MERSENNE_TWISTER_19937 1
    520514#endif
    521515

  • trunk/Source/WTF/wtf/RandomNumber.cpp

    r111778 r145179  
    22 * Copyright (C) 2006, 2007, 2008 Apple Inc. All rights reserved.
    33 *           (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
     4 * Copyright (C) 2013 Andrew Bortz. All rights reserved.
    45 *
    56 * Redistribution and use in source and binary forms, with or without
    … …  
    3637#include <stdlib.h>
    3738
    38 #if USE(MERSENNE_TWISTER_19937)
    39 extern "C" {
    40 #include "mt19937ar.c"
     39namespace WTF {
     40
     41#if !USE(OS_RANDOMNESS)
     42namespace Internal {
     43
     44static uint64_t state;
     45
     46void initializeRandomNumber(uint64_t seed)
     47{
     48    state = seed;
     49}
     50
     51// This random number generator comes from: Klimov, A. and Shamir, A.,
     52// "A New Class of Invertible Mappings", Cryptographic Hardware and Embedded
     53// Systems 2002, http://dl.acm.org/citation.cfm?id=752741
     54//
     55// Very fast, very simple, and passes Diehard and other good statistical
     56// tests as strongly as cryptographically-secure random number generators (but
     57// is not itself cryptographically-secure).
     58uint32_t randomNumber()
     59{
     60    state += (state * state) | 5;
     61    return static_cast<uint32_t>(state >> 32);
     62}
     63
    4164}
    4265#endif
    43 
    44 namespace WTF {
    4566
    4667double randomNumber()
    … …  
    4869#if USE(OS_RANDOMNESS)
    4970    uint32_t bits = cryptographicallyRandomNumber();
     71#else
     72    uint32_t bits = Internal::randomNumber();
     73#endif
    5074    return static_cast<double>(bits) / (static_cast<double>(std::numeric_limits<uint32_t>::max()) + 1.0);
    51 #else
    52     // Without OS_RANDOMNESS, we fall back to other random number generators
    53     // that might not be cryptographically secure. Ideally, most ports would
    54     // define USE(OS_RANDOMNESS).
    55 
    56 #if USE(MERSENNE_TWISTER_19937)
    57     return genrand_res53();
    58 #else
    59     uint32_t part1 = rand() & (RAND_MAX - 1);
    60     uint32_t part2 = rand() & (RAND_MAX - 1);
    61     // rand only provides 31 bits, and the low order bits of that aren't very random
    62     // so we take the high 26 bits of part 1, and the high 27 bits of part2.
    63     part1 >>= 5; // drop the low 5 bits
    64     part2 >>= 4; // drop the low 4 bits
    65     uint64_t fullRandom = part1;
    66     fullRandom <<= 27;
    67     fullRandom |= part2;
    68 
    69     // Mask off the low 53bits
    70     fullRandom &= (1LL << 53) - 1;
    71     return static_cast<double>(fullRandom)/static_cast<double>(1LL << 53);
    72 #endif
    73 #endif
    7475}
    7576

  • trunk/Source/WTF/wtf/RandomNumber.h

    r111778 r145179  
    2929namespace WTF {
    3030
    31     // Returns a pseudo-random number in the range [0, 1), attempts to be
    32     // cryptographically secure if possible on the target platform
    33     WTF_EXPORT_PRIVATE double randomNumber();
     31#if !USE(OS_RANDOMNESS)
     32namespace Internal {
     33void initializeRandomNumber(uint64_t);
     34}
     35#endif
     36
     37// Returns a pseudo-random number in the range [0, 1), attempts to be
     38// cryptographically secure if possible on the target platform
     39WTF_EXPORT_PRIVATE double randomNumber();
    3440
    3541}

  • trunk/Source/WTF/wtf/RandomNumberSeed.h

    r111778 r145179  
    2727#define WTF_RandomNumberSeed_h
    2828
     29#include "RandomNumber.h"
    2930#include <stdlib.h>
    3031#include <time.h>
    … …  
    3940#endif
    4041
    41 #if USE(MERSENNE_TWISTER_19937)
    42 extern "C" {
    43 void init_by_array(unsigned long init_key[],int key_length);
    44 }
    45 #endif
    46 
    47 // Internal JavaScriptCore usage only
    4842namespace WTF {
    4943
    … …  
    6660#endif
    6761
    68 #if USE(MERSENNE_TWISTER_19937)
    69     // use rand() to initialize the Mersenne Twister random number generator.
    70     unsigned long initializationBuffer[4];
    71     initializationBuffer[0] = (rand() << 16) | rand();
    72     initializationBuffer[1] = (rand() << 16) | rand();
    73     initializationBuffer[2] = (rand() << 16) | rand();
    74     initializationBuffer[3] = (rand() << 16) | rand();
    75     init_by_array(initializationBuffer, 4);
     62#if !USE(OS_RANDOMNESS)
     63    uint64_t seed = static_cast<uint64_t>(rand()) << 32 | static_cast<uint64_t>(rand());
     64    Internal::initializeRandomNumber(seed);
    7665#endif
    7766}
Note: See TracChangeset for help on using the changeset viewer.