VirtualBox

Changeset 11064 in vbox for trunk/src/VBox/Runtime


Ignore:
Timestamp:
Aug 1, 2008 2:12:37 PM (17 years ago)
Author:
vboxsync
svn:sync-xref-src-repo-rev:
33962
Message:

iprt/RTRandUxy: Improved the distribution when not using the max ranges. Changed the pseudo/cpuid fallback so it makes sure the cpuid has changed sufficiently and then only takes 3-bits from it, dropping the lower 5 since some of these are no longer reliable (5 is a bit too high, hopefully). Added tstRand for testing the distribution and limits.

Location:
trunk/src/VBox/Runtime
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/VBox/Runtime/common/misc/rand.cpp

    r11019 r11064  
    108108
    109109/**
     110 * Generate a 32-bit unsigned random number in the set [u32First..u32Last].
     111 *
     112 * @returns The random number.
     113 * @param   u32First    First number in the set.
     114 * @param   u32Last     Last number in the set.
     115 */
     116RTDECL(uint32_t) RTRandU32Ex(uint32_t u32First, uint32_t u32Last) RT_NO_THROW
     117{
     118    union
     119    {
     120        uint32_t    off;
     121        uint8_t     ab[5];
     122    } u;
     123
     124    const uint32_t offLast = u32Last - u32First;
     125    if (offLast == UINT32_MAX)
     126        /* get 4 random bytes and return them raw. */
     127        rtRandGenBytes(&u.ab, sizeof(u.off));
     128    else if (!(offLast & UINT32_C(0xf0000000)))
     129    {
     130        /* get 4 random bytes and do simple squeeze. */
     131        rtRandGenBytes(&u.ab, sizeof(u.off));
     132        u.off %= offLast + 1;
     133        u.off += u32First;
     134    }
     135    else
     136    {
     137        /* get 5 random bytes and do shifted squeeze. (this ain't perfect) */
     138        rtRandGenBytes(&u.ab, sizeof(u.ab));
     139        u.off %= (offLast >> 4) + 1;
     140        u.off <<= 4;
     141        u.off |= u.ab[4] & 0xf;
     142        if (u.off > offLast)
     143            u.off = offLast;
     144        u.off += u32First;
     145    }
     146    return u.off;
     147}
     148
     149
     150/**
     151 * Generate a 32-bit unsigned random number.
     152 *
     153 * @returns The random number.
     154 */
     155RTDECL(uint32_t) RTRandU32(void) RT_NO_THROW
     156{
     157    return RTRandU32Ex(0, UINT32_MAX);
     158}
     159
     160
     161/**
    110162 * Generate a 32-bit signed random number in the set [i32First..i32Last].
    111163 *
    … …  
    116168RTDECL(int32_t) RTRandS32Ex(int32_t i32First, int32_t i32Last) RT_NO_THROW
    117169{
    118     /* get 4 random bytes. */
     170    if (i32First == INT32_MIN && i32Last == INT32_MAX)
     171        return (int32_t)RTRandU32Ex(0, UINT32_MAX);
     172    return RTRandU32Ex(0, i32Last - i32First) + i32First;
     173}
     174
     175
     176/**
     177 * Generate a 32-bit signed random number.
     178 *
     179 * @returns The random number.
     180 */
     181RTDECL(int32_t) RTRandS32(void) RT_NO_THROW
     182{
     183    return (int32_t)RTRandU32Ex(0, UINT32_MAX);
     184}
     185
     186
     187/**
     188 * Generate a 64-bit unsigned random number in the set [u64First..u64Last].
     189 *
     190 * @returns The random number.
     191 * @param   u64First    First number in the set.
     192 * @param   u64Last     Last number in the set.
     193 */
     194RTDECL(uint64_t) RTRandU64Ex(uint64_t u64First, uint64_t u64Last) RT_NO_THROW
     195{
    119196    union
    120197    {
    121         uint32_t    off;
    122         uint8_t     ab[4];
     198        uint64_t    off;
     199        uint32_t    off32;
     200        uint8_t     ab[5];
    123201    } u;
    124     rtRandGenBytes(&u.ab, sizeof(u));
    125 
    126 
    127     /* squeeze it into the requested range. */
    128     uint32_t offLast = i32Last - i32First;
    129     if (u.off > offLast)
    130     {
    131         do
    132         {
    133             u.off >>= 1;
    134         } while (u.off > offLast);
    135     }
    136     return i32First + u.off;
    137 }
    138 
    139 
    140 /**
    141  * Generate a 32-bit signed random number.
    142  *
    143  * @returns The random number.
    144  */
    145 RTDECL(int32_t) RTRandS32(void) RT_NO_THROW
    146 {
    147     return RTRandS32Ex(INT32_MIN, INT32_MAX);
    148 }
    149 
    150 
    151 /**
    152  * Generate a 32-bit unsigned random number in the set [u32First..u32Last].
    153  *
    154  * @returns The random number.
    155  * @param   u32First    First number in the set.
    156  * @param   u32Last     Last number in the set.
    157  */
    158 RTDECL(uint32_t) RTRandU32Ex(uint32_t u32First, uint32_t u32Last) RT_NO_THROW
    159 {
    160     /* get 4 random bytes. */
    161     union
    162     {
    163         uint32_t    off;
    164         uint8_t     ab[4];
    165     } u;
    166     rtRandGenBytes(&u.ab, sizeof(u));
    167 
    168 
    169     /* squeeze it into the requested range. */
    170     const uint32_t offLast = u32Last - u32First;
    171     if (u.off > offLast)
    172     {
    173         do
    174         {
    175             u.off >>= 1;
    176         } while (u.off > offLast);
    177     }
    178     return u32First + u.off;
    179 }
    180 
    181 
    182 /**
    183  * Generate a 32-bit unsigned random number.
    184  *
    185  * @returns The random number.
    186  */
    187 RTDECL(uint32_t) RTRandU32(void) RT_NO_THROW
    188 {
    189     return RTRandU32Ex(0, UINT32_MAX);
     202
     203    const uint64_t offLast = u64Last - u64First;
     204    if (offLast == UINT64_MAX)
     205        /* get 8 random bytes and return them raw. */
     206        rtRandGenBytes(&u.ab, sizeof(u.off));
     207    else if (!(offLast & UINT64_C(0xf000000000000000)))
     208    {
     209        /* get 8 random bytes and do simple squeeze. */
     210        rtRandGenBytes(&u.ab, sizeof(u.off));
     211        u.off %= offLast + 1;
     212        u.off += u64First;
     213    }
     214    else
     215    {
     216        /* get 9 random bytes and do shifted squeeze. (this ain't perfect) */
     217        rtRandGenBytes(&u.ab, sizeof(u.ab));
     218        u.off %= (offLast >> 4) + 1;
     219        u.off <<= 4;
     220        u.off |= u.ab[8] & 0xf;
     221        if (u.off > offLast)
     222            u.off = offLast;
     223        u.off += u64First;
     224    }
     225    return u.off;
     226}
     227
     228
     229/**
     230 * Generate a 64-bit unsigned random number.
     231 *
     232 * @returns The random number.
     233 */
     234RTDECL(uint64_t) RTRandU64(void) RT_NO_THROW
     235{
     236    return RTRandU64Ex(0, UINT64_MAX);
    190237}
    191238
    … …  
    200247RTDECL(int64_t) RTRandS64Ex(int64_t i64First, int64_t i64Last) RT_NO_THROW
    201248{
    202     /* get 8 random bytes. */
    203     union
    204     {
    205         uint64_t    off;
    206         uint8_t     ab[8];
    207     } u;
    208     rtRandGenBytes(&u.ab, sizeof(u));
    209 
    210     /* squeeze it into the requested range. */
    211     uint64_t offLast = i64Last - i64First;
    212     if (u.off > offLast)
    213     {
    214         do
    215         {
    216             u.off >>= 1;
    217         } while (u.off > offLast);
    218     }
    219     return i64First + u.off;
     249    if (i64First == INT64_MIN && i64Last == INT64_MAX)
     250        return (int64_t)RTRandU64Ex(0, UINT64_MAX);
     251    return (int64_t)RTRandU64Ex(0, i64Last - i64First) + i64First;
    220252}
    221253
    … …  
    228260RTDECL(int64_t) RTRandS64(void) RT_NO_THROW
    229261{
    230     return RTRandS64Ex(INT64_MIN, INT64_MAX);
    231 }
    232 
    233 
    234 /**
    235  * Generate a 64-bit unsigned random number in the set [u64First..u64Last].
    236  *
    237  * @returns The random number.
    238  * @param   u64First    First number in the set.
    239  * @param   u64Last     Last number in the set.
    240  */
    241 RTDECL(uint64_t) RTRandU64Ex(uint64_t u64First, uint64_t u64Last) RT_NO_THROW
    242 {
    243     /* get 8 random bytes. */
    244     union
    245     {
    246         uint64_t    off;
    247         uint8_t     ab[8];
    248     } u;
    249     rtRandGenBytes(&u.ab, sizeof(u));
    250 
    251     /* squeeze it into the requested range. */
    252     const uint64_t offLast = u64Last - u64First;
    253     if (u.off > offLast)
    254     {
    255         do
    256         {
    257             u.off >>= 1;
    258         } while (u.off > offLast);
    259     }
    260     return u64First + u.off;
    261 }
    262 
    263 
    264 /**
    265  * Generate a 64-bit unsigned random number.
    266  *
    267  * @returns The random number.
    268  */
    269 RTDECL(uint64_t) RTRandU64(void) RT_NO_THROW
    270 {
    271     return RTRandU64Ex(0, UINT64_MAX);
     262    return (int64_t)RTRandU64Ex(0, UINT64_MAX);
    272263}
    273264
    … …  
    281272void rtRandGenBytesFallback(void *pv, size_t cb) RT_NO_THROW
    282273{
     274    uint64_t u64Last;
    283275    uint8_t *pb = (uint8_t *)pv;
    284276    for (unsigned i = 0;; i++)
    … …  
    300292            break;
    301293
    302         /* Is this really a good idea? */
     294        /*
     295         * Is this really a good idea? Looks like we cannot
     296         * quite trust the lower bits here for instance...
     297         */
    303298        if (!(i % 3))
    304299        {
    305             if (i)
    306                 RTThreadYield();
    307             *pb++ = (uint8_t)ASMReadTSC();
    308             if (!--cb)
    309                 break;
     300            uint64_t u64 = ASMReadTSC();
     301            uint64_t u64Delta = u64 - u64Last;
     302            if (u64Delta > 0xff)
     303            {
     304                u32 >>= 8;
     305                *pb++ = ((uint8_t)u64 >> 5) | (u32 << 3);
     306                if (!--cb)
     307                    break;
     308                u64Last = u64;
     309            }
    310310        }
    311311    }
    312 
    313312}
    314313

  • trunk/src/VBox/Runtime/testcase/Makefile.kmk

    r11016 r11064  
    7979        tstPath \
    8080        tstPrfRT \
     81        tstRand \
    8182        tstRTFsQueries \
    8283        tstStrFormat \
    … …  
    277278tstPrfRT_SOURCES = tstPrfRT.cpp
    278279
     280tstRand_SOURCES = tstRand.cpp
     281
    279282tstRTFsQueries_SOURCES = tstRTFsQueries.cpp
    280283
Note: See TracChangeset for help on using the changeset viewer.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette