cbrng.dox (9236B)
1 /** 2 @page CBRNG Counter Based RNGs (CBRNGs). 3 4 The counter-based random number generators (CBRNGs) 5 in the Random123 library are described in more detail in 6 <a href="http://dl.acm.org/citation.cfm?doid=2063405"><i>Parallel Random Numbers: As Easy as 1, 2, 3</i> </a>, 7 which was named the Best Paper at the ACM SC'11 International Conference on High Performance Computing, Networking, 8 Storage, and Analysis. 9 All the CBRNGs in the library conform to a consistent 10 interface. Basically: 11 \verbatim 12 value = CBRNGname(counter, key) 13 \endverbatim 14 15 Thus, with some care, they can be used 16 interchangeably in applications. (Since code 17 compiled with AES-NI instructions will result 18 in an illegal instruction exception on processors 19 without those instructions, Random123 provides a 20 @ref haveAESNI function that can be used 21 to detect the existence of AES at run-time; 22 user code could use it to either report an 23 error or substitute an alternative compatible 24 CBRNG.) 25 26 The API descriptions below are generic, but apply to 27 all the different @ref families "families" of 28 Random123 CBRNGs. 29 30 \section arrays Fixed-size Array Types 31 32 Data is passed into and back from the Random123 functions as 33 @ref arrayNxW "r123arrayNxW" 34 types; these types 35 contain fixed-size arrays of W-bit types (\c uintW_t for the 36 most part, but also a special r123m128i wrapper for the @ref 37 AESNI "ARS and AESNI" CBRNGs). The counter argument 38 and the return value have the same type, 39 referred to as \c ctr_type in C++, and \c ctr_t in C. The 40 type of the key argument is referred to as \c key_type in C++, 41 and \c key_t in C. 42 For an @ref arrayNxW "r123arrayNxW", \c r, the data member \c r.v is an array of N elements, 43 each of width W (each element is 44 type \c uintW_t or an r123m128i wrapper object). 45 C programs can access these elements as \c r.v[0], ... \c r.v[N-1] for 46 the \c uintW_t types. 47 48 In C++, these array types closely resemble the C++0x std::array<N, uintW_t> template, but do not 49 require C++11 libraries or compiler features. 50 C++ programs can access array elements via operator[] 51 \c r[0], ... \c r[N-1], or via most of the capabilities 52 of a C++ "Container" e.g. \c at(), \c begin(), \c end(), 53 \c size() and others. In addition, containers have <c> incr() </c> and <c> incr(unsigned long long)</c> 54 member function that do increment-with-carry, which facilitate 55 using r123arrays as very-long-period counters. 56 57 If the compiler environment supports it, 58 \c Random123/array.h also declares \c r123array1xm128i, which contains an array of one 59 \c r123m128i, which in turn is a class wrapping a single element 60 of \c __m128i SSE type, which can be accessed as \c r.v[0].m. 61 The @ref r123::ARS1xm128i_R RNGs 62 use \c r123array1xm128i for both \c ctr_type and \c key_type. 63 For the @ref AESNI "AESNI" RNG, \c ctr_type is an \c r123array1xm128i, but 64 \c key_type is an opaque type, which must be initialized 65 by assignment from a <c>userkey_type</c> (an r123array1xm128i). 66 67 \section aliasing A note on aliasing and type-punning 68 It is easiest (though not necessarily fastest) to choose a CBRNG whose 69 \c ctr_type matches the width of the random data needed by the 70 application, e.g., Philox4x32 for applications that need random data in 71 32-bit words. If the application's needs don't match the counter's value_type, 72 it is tempting to use "type punning" and pointer casts to interconvert between 73 types. Such conversions require great care and are very difficult to do 74 safely without use of unions or memcpy. 75 See <a 76 href="http://blog.worldofcoding.com/2010/02/solving-gcc-44-strict-aliasing-problems.html"> 77 here</a> 78 and 79 <a href="http://dbp-consulting.com/tutorials/StrictAliasing.html"> 80 here</a> 81 for discussions of the pitfalls related to aliasing. 82 The C++ 83 @ref r123::ReinterpretCtr template is a safe way to reinterpret \c CBRNG 84 counter types. 85 Gcc's \c 86 -Wstrict-aliasing=2 warning level will warn if strict aliasing 87 violations are detected. If you find yourself ignoring or disabling 88 warnings about strict aliasing, you should strongly consider adding something 89 like gcc's \c -fnostrict-aliasing option to your compiler 90 flags. 91 92 \section cxxapi C++ API 93 94 There are four families of CBRNGs in the library: 95 <ul> 96 <li> @ref ThreefryNxW "Threefry": @ref r123::Threefry2x32, @ref r123::Threefry4x32, @ref r123::Threefry2x64, @ref r123::Threefry4x64 97 <li> @ref PhiloxNxW "Philox": @ref r123::Philox2x32, @ref r123::Philox4x32, @ref r123::Philox2x64, @ref r123::Philox4x64 98 <li> @ref r123::AESNI4x32, r123::AESNI1xm128i 99 <li> @ref r123::ARS4x32_R 100 </ul> 101 102 A <i> counter based RNG </i> (CBRNG) with a name of the form 103 <i>FamilynameN</i>x<i>W</i> is a type G 104 with the three member typedefs: 105 106 <ul> 107 <li> G::ctr_type, which is an @ref arrayNxW "r123arrayNxW" container class. 108 <li> G::ukey_type, which is an @ref arrayNxW "r123arrayMxV" container class. 109 Note that the width, \c MxV of the key 110 may not be the same as the width \c NxW of 111 the ctr_type (@ref PhiloxNxW "Philox" keys are half as wide as the counter, 112 and future CBRNGs may well have different widths). 113 <li> G::key_type, which in most cases is identical to 114 G::ukey_type, but is different for the @ref AESNI "AESNI" types. 115 In all cases, there is a G::key_type(G::ukey_type) constructor 116 and a G::key_type assignment operator for a G::ukey_type 117 right-hand-side. In general, one can always write: 118 @code 119 G::ukey_type uk1, uk2; 120 // user code initializes uk1 and uk2 121 G::key_type k1(uk1), k2; 122 k2 = uk2; 123 @endcode 124 </ul> 125 For most CBRNG's, i.e., any one not in the @ref AESNI "AESNI" family, it is also 126 perfectly acceptable to set the elements of a G::key_type directly from application variables. 127 The quality of the results will not be compromised by using highly correlated 128 or "non-random" keys. 129 130 A value \c g of type \c G can be invoked as <c>g(c,k)</c>, where \c c 131 is a value of type \c G::ctr_type and \c k is a value of type \c G::key_type, 132 and <c>g(c,k)</c> returns a value of type \c G::ctr_type. 133 134 <ul> 135 <li> g() is a stateless, pure function. That is, g(c,k) may be called 136 any number of times in any context and always returns the same result 137 for the same inputs. In particular, c1==c2 and k1==k2 implies that g(c1,k1) 138 == g(c2,k2). 139 <li> For constant k, g(*,k) is a bijection. That is, 140 g(c1,k) == g(c2,k) if and only if c1 == c2. 141 <li> g "randomizes" its inputs. That is, 142 for most sequences of inputs (c1,k1), 143 (c2, k2), ... (including those obtained by following highly 144 regular patterns of incrementing and striding 145 through the counter and user key spaces) the output sequence, g(c1, k1), 146 g(c2, k2), ... looks like a a sequence of uniformly distributed 147 random variables drawn from the set of all ctr_types. 148 </ul> 149 150 All the CBRNGs in the library work by iterating a randomization function for a specific number of \e rounds. 151 Too few rounds and the CBRNG is a poor (perhaps 152 catastrophically poor) random number generator. Too many rounds and time is wasted 153 with little or no improvement in the randomness of the output. Each of the CBRNGs 154 has a specific number of rounds which the authors believe is a reasonable compromise 155 between speed and quality. In all cases, the default number of rounds includes a margin 156 of safety above the minimum number of rounds that have passed all of the SmallCrush, Crush and BigCrush 157 tests in the <a href="http://www.iro.umontreal.ca/~simardr/testu01/tu01.html"> TestU01</a> suite. 158 159 Users may, however wish to employ a different numbers of rounds. Each of the above 160 classes is actually a typedef of a more general class with a template parameter that 161 specifies the number of rounds as <i>name</i>_rounds. The template classes all end in \c _R: 162 163 <ul> 164 <li> @ref ThreefryNxW "Threefry": @ref r123::Threefry2x32_R, @ref r123::Threefry4x32_R, @ref r123::Threefry2x64_R, @ref r123::Threefry4x64_R 165 <li> @ref PhiloxNxW "Philox": @ref r123::Philox2x32_R, @ref r123::Philox4x32_R, @ref r123::Philox2x64_R, @ref r123::Philox4x64_R 166 <li> @ref r123::AESNI4x32_R, r123::AESNI1xm128i_R 167 <li> @ref r123::ARS4x32_R 168 </ul> 169 170 \section capi C API 171 172 A subset of the C++ interface 173 is also directly usable by C programs. All header files may be 174 safely included in C files. The C API to each of the 175 supported RNGs consists of two typedefs, <i>name</i>_ctr_t, 176 <i>name</i>_key_t, two functions <i>name</i>() and <i>name</i>_R(), and 177 the enum <i>name</i>_rounds which specifies the recommended number of rounds. 178 <ul> 179 <li> <i>name</i>(c, k), performs the recommended number of rounds of the <i>name</i> CBRNG. 180 <li> <i>name_R</i>(R,c,k), performs an R-round version of the <i>name</i> CBRNG. 181 <i>name</i>(c,k) is equivalent to 182 <i>name</i>_R(<i>name</i>_rounds, c, k). 183 </ul> 184 185 The \c _R functions are designed and implemented so that an optimizing compiler can achieve good performance 186 when the number of rounds is a compile-time constant. It is likely that <c>philox4x32_R(10,c,k) </c> 187 will perform much better than <c>philox4x32_R(r,c,k)</c> if \c r cannot be 188 evaluated at compile-time. 189 190 The supported names for the C API are 191 <ul> 192 <li> @ref ThreefryNxW "threefry": @ref threefry2x32, @ref threefry4x32, @ref threefry2x64, @ref threefry4x64. 193 <li> @ref PhiloxNxW "philox": @ref philox2x32, @ref philox4x32, @ref philox2x64, @ref philox4x64. 194 <li> @ref ars4x32_R, @ref ars1xm128i_R 195 <li> @ref aesni4x32, @ref aesni1xm128i 196 </ul> 197 198 */