1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/random/internal/randen_slow.h"
16
17 #include <cstddef>
18 #include <cstdint>
19 #include <cstring>
20
21 #include "absl/base/attributes.h"
22 #include "absl/random/internal/platform.h"
23 #include "absl/random/internal/randen_traits.h"
24
25 #if ABSL_HAVE_ATTRIBUTE(always_inline) || \
26 (defined(__GNUC__) && !defined(__clang__))
27 #define ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE \
28 __attribute__((always_inline))
29 #elif defined(_MSC_VER)
30 // We can achieve something similar to attribute((always_inline)) with MSVC by
31 // using the __forceinline keyword, however this is not perfect. MSVC is
32 // much less aggressive about inlining, and even with the __forceinline keyword.
33 #define ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE __forceinline
34 #else
35 #define ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE
36 #endif
37
38 namespace {
39
40 // AES portions based on rijndael-alg-fst.c,
41 // https://fastcrypto.org/front/misc/rijndael-alg-fst.c
42 //
43 // Implementation of
44 // http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf
45 constexpr uint32_t te0[256] = {
46 0xc66363a5, 0xf87c7c84, 0xee777799, 0xf67b7b8d, 0xfff2f20d, 0xd66b6bbd,
47 0xde6f6fb1, 0x91c5c554, 0x60303050, 0x02010103, 0xce6767a9, 0x562b2b7d,
48 0xe7fefe19, 0xb5d7d762, 0x4dababe6, 0xec76769a, 0x8fcaca45, 0x1f82829d,
49 0x89c9c940, 0xfa7d7d87, 0xeffafa15, 0xb25959eb, 0x8e4747c9, 0xfbf0f00b,
50 0x41adadec, 0xb3d4d467, 0x5fa2a2fd, 0x45afafea, 0x239c9cbf, 0x53a4a4f7,
51 0xe4727296, 0x9bc0c05b, 0x75b7b7c2, 0xe1fdfd1c, 0x3d9393ae, 0x4c26266a,
52 0x6c36365a, 0x7e3f3f41, 0xf5f7f702, 0x83cccc4f, 0x6834345c, 0x51a5a5f4,
53 0xd1e5e534, 0xf9f1f108, 0xe2717193, 0xabd8d873, 0x62313153, 0x2a15153f,
54 0x0804040c, 0x95c7c752, 0x46232365, 0x9dc3c35e, 0x30181828, 0x379696a1,
55 0x0a05050f, 0x2f9a9ab5, 0x0e070709, 0x24121236, 0x1b80809b, 0xdfe2e23d,
56 0xcdebeb26, 0x4e272769, 0x7fb2b2cd, 0xea75759f, 0x1209091b, 0x1d83839e,
57 0x582c2c74, 0x341a1a2e, 0x361b1b2d, 0xdc6e6eb2, 0xb45a5aee, 0x5ba0a0fb,
58 0xa45252f6, 0x763b3b4d, 0xb7d6d661, 0x7db3b3ce, 0x5229297b, 0xdde3e33e,
59 0x5e2f2f71, 0x13848497, 0xa65353f5, 0xb9d1d168, 0x00000000, 0xc1eded2c,
60 0x40202060, 0xe3fcfc1f, 0x79b1b1c8, 0xb65b5bed, 0xd46a6abe, 0x8dcbcb46,
61 0x67bebed9, 0x7239394b, 0x944a4ade, 0x984c4cd4, 0xb05858e8, 0x85cfcf4a,
62 0xbbd0d06b, 0xc5efef2a, 0x4faaaae5, 0xedfbfb16, 0x864343c5, 0x9a4d4dd7,
63 0x66333355, 0x11858594, 0x8a4545cf, 0xe9f9f910, 0x04020206, 0xfe7f7f81,
64 0xa05050f0, 0x783c3c44, 0x259f9fba, 0x4ba8a8e3, 0xa25151f3, 0x5da3a3fe,
65 0x804040c0, 0x058f8f8a, 0x3f9292ad, 0x219d9dbc, 0x70383848, 0xf1f5f504,
66 0x63bcbcdf, 0x77b6b6c1, 0xafdada75, 0x42212163, 0x20101030, 0xe5ffff1a,
67 0xfdf3f30e, 0xbfd2d26d, 0x81cdcd4c, 0x180c0c14, 0x26131335, 0xc3ecec2f,
68 0xbe5f5fe1, 0x359797a2, 0x884444cc, 0x2e171739, 0x93c4c457, 0x55a7a7f2,
69 0xfc7e7e82, 0x7a3d3d47, 0xc86464ac, 0xba5d5de7, 0x3219192b, 0xe6737395,
70 0xc06060a0, 0x19818198, 0x9e4f4fd1, 0xa3dcdc7f, 0x44222266, 0x542a2a7e,
71 0x3b9090ab, 0x0b888883, 0x8c4646ca, 0xc7eeee29, 0x6bb8b8d3, 0x2814143c,
72 0xa7dede79, 0xbc5e5ee2, 0x160b0b1d, 0xaddbdb76, 0xdbe0e03b, 0x64323256,
73 0x743a3a4e, 0x140a0a1e, 0x924949db, 0x0c06060a, 0x4824246c, 0xb85c5ce4,
74 0x9fc2c25d, 0xbdd3d36e, 0x43acacef, 0xc46262a6, 0x399191a8, 0x319595a4,
75 0xd3e4e437, 0xf279798b, 0xd5e7e732, 0x8bc8c843, 0x6e373759, 0xda6d6db7,
76 0x018d8d8c, 0xb1d5d564, 0x9c4e4ed2, 0x49a9a9e0, 0xd86c6cb4, 0xac5656fa,
77 0xf3f4f407, 0xcfeaea25, 0xca6565af, 0xf47a7a8e, 0x47aeaee9, 0x10080818,
78 0x6fbabad5, 0xf0787888, 0x4a25256f, 0x5c2e2e72, 0x381c1c24, 0x57a6a6f1,
79 0x73b4b4c7, 0x97c6c651, 0xcbe8e823, 0xa1dddd7c, 0xe874749c, 0x3e1f1f21,
80 0x964b4bdd, 0x61bdbddc, 0x0d8b8b86, 0x0f8a8a85, 0xe0707090, 0x7c3e3e42,
81 0x71b5b5c4, 0xcc6666aa, 0x904848d8, 0x06030305, 0xf7f6f601, 0x1c0e0e12,
82 0xc26161a3, 0x6a35355f, 0xae5757f9, 0x69b9b9d0, 0x17868691, 0x99c1c158,
83 0x3a1d1d27, 0x279e9eb9, 0xd9e1e138, 0xebf8f813, 0x2b9898b3, 0x22111133,
84 0xd26969bb, 0xa9d9d970, 0x078e8e89, 0x339494a7, 0x2d9b9bb6, 0x3c1e1e22,
85 0x15878792, 0xc9e9e920, 0x87cece49, 0xaa5555ff, 0x50282878, 0xa5dfdf7a,
86 0x038c8c8f, 0x59a1a1f8, 0x09898980, 0x1a0d0d17, 0x65bfbfda, 0xd7e6e631,
87 0x844242c6, 0xd06868b8, 0x824141c3, 0x299999b0, 0x5a2d2d77, 0x1e0f0f11,
88 0x7bb0b0cb, 0xa85454fc, 0x6dbbbbd6, 0x2c16163a,
89 };
90
91 constexpr uint32_t te1[256] = {
92 0xa5c66363, 0x84f87c7c, 0x99ee7777, 0x8df67b7b, 0x0dfff2f2, 0xbdd66b6b,
93 0xb1de6f6f, 0x5491c5c5, 0x50603030, 0x03020101, 0xa9ce6767, 0x7d562b2b,
94 0x19e7fefe, 0x62b5d7d7, 0xe64dabab, 0x9aec7676, 0x458fcaca, 0x9d1f8282,
95 0x4089c9c9, 0x87fa7d7d, 0x15effafa, 0xebb25959, 0xc98e4747, 0x0bfbf0f0,
96 0xec41adad, 0x67b3d4d4, 0xfd5fa2a2, 0xea45afaf, 0xbf239c9c, 0xf753a4a4,
97 0x96e47272, 0x5b9bc0c0, 0xc275b7b7, 0x1ce1fdfd, 0xae3d9393, 0x6a4c2626,
98 0x5a6c3636, 0x417e3f3f, 0x02f5f7f7, 0x4f83cccc, 0x5c683434, 0xf451a5a5,
99 0x34d1e5e5, 0x08f9f1f1, 0x93e27171, 0x73abd8d8, 0x53623131, 0x3f2a1515,
100 0x0c080404, 0x5295c7c7, 0x65462323, 0x5e9dc3c3, 0x28301818, 0xa1379696,
101 0x0f0a0505, 0xb52f9a9a, 0x090e0707, 0x36241212, 0x9b1b8080, 0x3ddfe2e2,
102 0x26cdebeb, 0x694e2727, 0xcd7fb2b2, 0x9fea7575, 0x1b120909, 0x9e1d8383,
103 0x74582c2c, 0x2e341a1a, 0x2d361b1b, 0xb2dc6e6e, 0xeeb45a5a, 0xfb5ba0a0,
104 0xf6a45252, 0x4d763b3b, 0x61b7d6d6, 0xce7db3b3, 0x7b522929, 0x3edde3e3,
105 0x715e2f2f, 0x97138484, 0xf5a65353, 0x68b9d1d1, 0x00000000, 0x2cc1eded,
106 0x60402020, 0x1fe3fcfc, 0xc879b1b1, 0xedb65b5b, 0xbed46a6a, 0x468dcbcb,
107 0xd967bebe, 0x4b723939, 0xde944a4a, 0xd4984c4c, 0xe8b05858, 0x4a85cfcf,
108 0x6bbbd0d0, 0x2ac5efef, 0xe54faaaa, 0x16edfbfb, 0xc5864343, 0xd79a4d4d,
109 0x55663333, 0x94118585, 0xcf8a4545, 0x10e9f9f9, 0x06040202, 0x81fe7f7f,
110 0xf0a05050, 0x44783c3c, 0xba259f9f, 0xe34ba8a8, 0xf3a25151, 0xfe5da3a3,
111 0xc0804040, 0x8a058f8f, 0xad3f9292, 0xbc219d9d, 0x48703838, 0x04f1f5f5,
112 0xdf63bcbc, 0xc177b6b6, 0x75afdada, 0x63422121, 0x30201010, 0x1ae5ffff,
113 0x0efdf3f3, 0x6dbfd2d2, 0x4c81cdcd, 0x14180c0c, 0x35261313, 0x2fc3ecec,
114 0xe1be5f5f, 0xa2359797, 0xcc884444, 0x392e1717, 0x5793c4c4, 0xf255a7a7,
115 0x82fc7e7e, 0x477a3d3d, 0xacc86464, 0xe7ba5d5d, 0x2b321919, 0x95e67373,
116 0xa0c06060, 0x98198181, 0xd19e4f4f, 0x7fa3dcdc, 0x66442222, 0x7e542a2a,
117 0xab3b9090, 0x830b8888, 0xca8c4646, 0x29c7eeee, 0xd36bb8b8, 0x3c281414,
118 0x79a7dede, 0xe2bc5e5e, 0x1d160b0b, 0x76addbdb, 0x3bdbe0e0, 0x56643232,
119 0x4e743a3a, 0x1e140a0a, 0xdb924949, 0x0a0c0606, 0x6c482424, 0xe4b85c5c,
120 0x5d9fc2c2, 0x6ebdd3d3, 0xef43acac, 0xa6c46262, 0xa8399191, 0xa4319595,
121 0x37d3e4e4, 0x8bf27979, 0x32d5e7e7, 0x438bc8c8, 0x596e3737, 0xb7da6d6d,
122 0x8c018d8d, 0x64b1d5d5, 0xd29c4e4e, 0xe049a9a9, 0xb4d86c6c, 0xfaac5656,
123 0x07f3f4f4, 0x25cfeaea, 0xafca6565, 0x8ef47a7a, 0xe947aeae, 0x18100808,
124 0xd56fbaba, 0x88f07878, 0x6f4a2525, 0x725c2e2e, 0x24381c1c, 0xf157a6a6,
125 0xc773b4b4, 0x5197c6c6, 0x23cbe8e8, 0x7ca1dddd, 0x9ce87474, 0x213e1f1f,
126 0xdd964b4b, 0xdc61bdbd, 0x860d8b8b, 0x850f8a8a, 0x90e07070, 0x427c3e3e,
127 0xc471b5b5, 0xaacc6666, 0xd8904848, 0x05060303, 0x01f7f6f6, 0x121c0e0e,
128 0xa3c26161, 0x5f6a3535, 0xf9ae5757, 0xd069b9b9, 0x91178686, 0x5899c1c1,
129 0x273a1d1d, 0xb9279e9e, 0x38d9e1e1, 0x13ebf8f8, 0xb32b9898, 0x33221111,
130 0xbbd26969, 0x70a9d9d9, 0x89078e8e, 0xa7339494, 0xb62d9b9b, 0x223c1e1e,
131 0x92158787, 0x20c9e9e9, 0x4987cece, 0xffaa5555, 0x78502828, 0x7aa5dfdf,
132 0x8f038c8c, 0xf859a1a1, 0x80098989, 0x171a0d0d, 0xda65bfbf, 0x31d7e6e6,
133 0xc6844242, 0xb8d06868, 0xc3824141, 0xb0299999, 0x775a2d2d, 0x111e0f0f,
134 0xcb7bb0b0, 0xfca85454, 0xd66dbbbb, 0x3a2c1616,
135 };
136
137 constexpr uint32_t te2[256] = {
138 0x63a5c663, 0x7c84f87c, 0x7799ee77, 0x7b8df67b, 0xf20dfff2, 0x6bbdd66b,
139 0x6fb1de6f, 0xc55491c5, 0x30506030, 0x01030201, 0x67a9ce67, 0x2b7d562b,
140 0xfe19e7fe, 0xd762b5d7, 0xabe64dab, 0x769aec76, 0xca458fca, 0x829d1f82,
141 0xc94089c9, 0x7d87fa7d, 0xfa15effa, 0x59ebb259, 0x47c98e47, 0xf00bfbf0,
142 0xadec41ad, 0xd467b3d4, 0xa2fd5fa2, 0xafea45af, 0x9cbf239c, 0xa4f753a4,
143 0x7296e472, 0xc05b9bc0, 0xb7c275b7, 0xfd1ce1fd, 0x93ae3d93, 0x266a4c26,
144 0x365a6c36, 0x3f417e3f, 0xf702f5f7, 0xcc4f83cc, 0x345c6834, 0xa5f451a5,
145 0xe534d1e5, 0xf108f9f1, 0x7193e271, 0xd873abd8, 0x31536231, 0x153f2a15,
146 0x040c0804, 0xc75295c7, 0x23654623, 0xc35e9dc3, 0x18283018, 0x96a13796,
147 0x050f0a05, 0x9ab52f9a, 0x07090e07, 0x12362412, 0x809b1b80, 0xe23ddfe2,
148 0xeb26cdeb, 0x27694e27, 0xb2cd7fb2, 0x759fea75, 0x091b1209, 0x839e1d83,
149 0x2c74582c, 0x1a2e341a, 0x1b2d361b, 0x6eb2dc6e, 0x5aeeb45a, 0xa0fb5ba0,
150 0x52f6a452, 0x3b4d763b, 0xd661b7d6, 0xb3ce7db3, 0x297b5229, 0xe33edde3,
151 0x2f715e2f, 0x84971384, 0x53f5a653, 0xd168b9d1, 0x00000000, 0xed2cc1ed,
152 0x20604020, 0xfc1fe3fc, 0xb1c879b1, 0x5bedb65b, 0x6abed46a, 0xcb468dcb,
153 0xbed967be, 0x394b7239, 0x4ade944a, 0x4cd4984c, 0x58e8b058, 0xcf4a85cf,
154 0xd06bbbd0, 0xef2ac5ef, 0xaae54faa, 0xfb16edfb, 0x43c58643, 0x4dd79a4d,
155 0x33556633, 0x85941185, 0x45cf8a45, 0xf910e9f9, 0x02060402, 0x7f81fe7f,
156 0x50f0a050, 0x3c44783c, 0x9fba259f, 0xa8e34ba8, 0x51f3a251, 0xa3fe5da3,
157 0x40c08040, 0x8f8a058f, 0x92ad3f92, 0x9dbc219d, 0x38487038, 0xf504f1f5,
158 0xbcdf63bc, 0xb6c177b6, 0xda75afda, 0x21634221, 0x10302010, 0xff1ae5ff,
159 0xf30efdf3, 0xd26dbfd2, 0xcd4c81cd, 0x0c14180c, 0x13352613, 0xec2fc3ec,
160 0x5fe1be5f, 0x97a23597, 0x44cc8844, 0x17392e17, 0xc45793c4, 0xa7f255a7,
161 0x7e82fc7e, 0x3d477a3d, 0x64acc864, 0x5de7ba5d, 0x192b3219, 0x7395e673,
162 0x60a0c060, 0x81981981, 0x4fd19e4f, 0xdc7fa3dc, 0x22664422, 0x2a7e542a,
163 0x90ab3b90, 0x88830b88, 0x46ca8c46, 0xee29c7ee, 0xb8d36bb8, 0x143c2814,
164 0xde79a7de, 0x5ee2bc5e, 0x0b1d160b, 0xdb76addb, 0xe03bdbe0, 0x32566432,
165 0x3a4e743a, 0x0a1e140a, 0x49db9249, 0x060a0c06, 0x246c4824, 0x5ce4b85c,
166 0xc25d9fc2, 0xd36ebdd3, 0xacef43ac, 0x62a6c462, 0x91a83991, 0x95a43195,
167 0xe437d3e4, 0x798bf279, 0xe732d5e7, 0xc8438bc8, 0x37596e37, 0x6db7da6d,
168 0x8d8c018d, 0xd564b1d5, 0x4ed29c4e, 0xa9e049a9, 0x6cb4d86c, 0x56faac56,
169 0xf407f3f4, 0xea25cfea, 0x65afca65, 0x7a8ef47a, 0xaee947ae, 0x08181008,
170 0xbad56fba, 0x7888f078, 0x256f4a25, 0x2e725c2e, 0x1c24381c, 0xa6f157a6,
171 0xb4c773b4, 0xc65197c6, 0xe823cbe8, 0xdd7ca1dd, 0x749ce874, 0x1f213e1f,
172 0x4bdd964b, 0xbddc61bd, 0x8b860d8b, 0x8a850f8a, 0x7090e070, 0x3e427c3e,
173 0xb5c471b5, 0x66aacc66, 0x48d89048, 0x03050603, 0xf601f7f6, 0x0e121c0e,
174 0x61a3c261, 0x355f6a35, 0x57f9ae57, 0xb9d069b9, 0x86911786, 0xc15899c1,
175 0x1d273a1d, 0x9eb9279e, 0xe138d9e1, 0xf813ebf8, 0x98b32b98, 0x11332211,
176 0x69bbd269, 0xd970a9d9, 0x8e89078e, 0x94a73394, 0x9bb62d9b, 0x1e223c1e,
177 0x87921587, 0xe920c9e9, 0xce4987ce, 0x55ffaa55, 0x28785028, 0xdf7aa5df,
178 0x8c8f038c, 0xa1f859a1, 0x89800989, 0x0d171a0d, 0xbfda65bf, 0xe631d7e6,
179 0x42c68442, 0x68b8d068, 0x41c38241, 0x99b02999, 0x2d775a2d, 0x0f111e0f,
180 0xb0cb7bb0, 0x54fca854, 0xbbd66dbb, 0x163a2c16,
181 };
182
183 constexpr uint32_t te3[256] = {
184 0x6363a5c6, 0x7c7c84f8, 0x777799ee, 0x7b7b8df6, 0xf2f20dff, 0x6b6bbdd6,
185 0x6f6fb1de, 0xc5c55491, 0x30305060, 0x01010302, 0x6767a9ce, 0x2b2b7d56,
186 0xfefe19e7, 0xd7d762b5, 0xababe64d, 0x76769aec, 0xcaca458f, 0x82829d1f,
187 0xc9c94089, 0x7d7d87fa, 0xfafa15ef, 0x5959ebb2, 0x4747c98e, 0xf0f00bfb,
188 0xadadec41, 0xd4d467b3, 0xa2a2fd5f, 0xafafea45, 0x9c9cbf23, 0xa4a4f753,
189 0x727296e4, 0xc0c05b9b, 0xb7b7c275, 0xfdfd1ce1, 0x9393ae3d, 0x26266a4c,
190 0x36365a6c, 0x3f3f417e, 0xf7f702f5, 0xcccc4f83, 0x34345c68, 0xa5a5f451,
191 0xe5e534d1, 0xf1f108f9, 0x717193e2, 0xd8d873ab, 0x31315362, 0x15153f2a,
192 0x04040c08, 0xc7c75295, 0x23236546, 0xc3c35e9d, 0x18182830, 0x9696a137,
193 0x05050f0a, 0x9a9ab52f, 0x0707090e, 0x12123624, 0x80809b1b, 0xe2e23ddf,
194 0xebeb26cd, 0x2727694e, 0xb2b2cd7f, 0x75759fea, 0x09091b12, 0x83839e1d,
195 0x2c2c7458, 0x1a1a2e34, 0x1b1b2d36, 0x6e6eb2dc, 0x5a5aeeb4, 0xa0a0fb5b,
196 0x5252f6a4, 0x3b3b4d76, 0xd6d661b7, 0xb3b3ce7d, 0x29297b52, 0xe3e33edd,
197 0x2f2f715e, 0x84849713, 0x5353f5a6, 0xd1d168b9, 0x00000000, 0xeded2cc1,
198 0x20206040, 0xfcfc1fe3, 0xb1b1c879, 0x5b5bedb6, 0x6a6abed4, 0xcbcb468d,
199 0xbebed967, 0x39394b72, 0x4a4ade94, 0x4c4cd498, 0x5858e8b0, 0xcfcf4a85,
200 0xd0d06bbb, 0xefef2ac5, 0xaaaae54f, 0xfbfb16ed, 0x4343c586, 0x4d4dd79a,
201 0x33335566, 0x85859411, 0x4545cf8a, 0xf9f910e9, 0x02020604, 0x7f7f81fe,
202 0x5050f0a0, 0x3c3c4478, 0x9f9fba25, 0xa8a8e34b, 0x5151f3a2, 0xa3a3fe5d,
203 0x4040c080, 0x8f8f8a05, 0x9292ad3f, 0x9d9dbc21, 0x38384870, 0xf5f504f1,
204 0xbcbcdf63, 0xb6b6c177, 0xdada75af, 0x21216342, 0x10103020, 0xffff1ae5,
205 0xf3f30efd, 0xd2d26dbf, 0xcdcd4c81, 0x0c0c1418, 0x13133526, 0xecec2fc3,
206 0x5f5fe1be, 0x9797a235, 0x4444cc88, 0x1717392e, 0xc4c45793, 0xa7a7f255,
207 0x7e7e82fc, 0x3d3d477a, 0x6464acc8, 0x5d5de7ba, 0x19192b32, 0x737395e6,
208 0x6060a0c0, 0x81819819, 0x4f4fd19e, 0xdcdc7fa3, 0x22226644, 0x2a2a7e54,
209 0x9090ab3b, 0x8888830b, 0x4646ca8c, 0xeeee29c7, 0xb8b8d36b, 0x14143c28,
210 0xdede79a7, 0x5e5ee2bc, 0x0b0b1d16, 0xdbdb76ad, 0xe0e03bdb, 0x32325664,
211 0x3a3a4e74, 0x0a0a1e14, 0x4949db92, 0x06060a0c, 0x24246c48, 0x5c5ce4b8,
212 0xc2c25d9f, 0xd3d36ebd, 0xacacef43, 0x6262a6c4, 0x9191a839, 0x9595a431,
213 0xe4e437d3, 0x79798bf2, 0xe7e732d5, 0xc8c8438b, 0x3737596e, 0x6d6db7da,
214 0x8d8d8c01, 0xd5d564b1, 0x4e4ed29c, 0xa9a9e049, 0x6c6cb4d8, 0x5656faac,
215 0xf4f407f3, 0xeaea25cf, 0x6565afca, 0x7a7a8ef4, 0xaeaee947, 0x08081810,
216 0xbabad56f, 0x787888f0, 0x25256f4a, 0x2e2e725c, 0x1c1c2438, 0xa6a6f157,
217 0xb4b4c773, 0xc6c65197, 0xe8e823cb, 0xdddd7ca1, 0x74749ce8, 0x1f1f213e,
218 0x4b4bdd96, 0xbdbddc61, 0x8b8b860d, 0x8a8a850f, 0x707090e0, 0x3e3e427c,
219 0xb5b5c471, 0x6666aacc, 0x4848d890, 0x03030506, 0xf6f601f7, 0x0e0e121c,
220 0x6161a3c2, 0x35355f6a, 0x5757f9ae, 0xb9b9d069, 0x86869117, 0xc1c15899,
221 0x1d1d273a, 0x9e9eb927, 0xe1e138d9, 0xf8f813eb, 0x9898b32b, 0x11113322,
222 0x6969bbd2, 0xd9d970a9, 0x8e8e8907, 0x9494a733, 0x9b9bb62d, 0x1e1e223c,
223 0x87879215, 0xe9e920c9, 0xcece4987, 0x5555ffaa, 0x28287850, 0xdfdf7aa5,
224 0x8c8c8f03, 0xa1a1f859, 0x89898009, 0x0d0d171a, 0xbfbfda65, 0xe6e631d7,
225 0x4242c684, 0x6868b8d0, 0x4141c382, 0x9999b029, 0x2d2d775a, 0x0f0f111e,
226 0xb0b0cb7b, 0x5454fca8, 0xbbbbd66d, 0x16163a2c,
227 };
228
229 // Software implementation of the Vector128 class, using uint32_t
230 // as an underlying vector register.
231 struct alignas(16) Vector128 {
232 uint32_t s[4];
233 };
234
235 inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128
Vector128Load(const void * from)236 Vector128Load(const void* from) {
237 Vector128 result;
238 const uint8_t* src = reinterpret_cast<const uint8_t*>(from);
239 result.s[0] = static_cast<uint32_t>(src[0]) << 24 |
240 static_cast<uint32_t>(src[1]) << 16 |
241 static_cast<uint32_t>(src[2]) << 8 |
242 static_cast<uint32_t>(src[3]);
243 result.s[1] = static_cast<uint32_t>(src[4]) << 24 |
244 static_cast<uint32_t>(src[5]) << 16 |
245 static_cast<uint32_t>(src[6]) << 8 |
246 static_cast<uint32_t>(src[7]);
247 result.s[2] = static_cast<uint32_t>(src[8]) << 24 |
248 static_cast<uint32_t>(src[9]) << 16 |
249 static_cast<uint32_t>(src[10]) << 8 |
250 static_cast<uint32_t>(src[11]);
251 result.s[3] = static_cast<uint32_t>(src[12]) << 24 |
252 static_cast<uint32_t>(src[13]) << 16 |
253 static_cast<uint32_t>(src[14]) << 8 |
254 static_cast<uint32_t>(src[15]);
255 return result;
256 }
257
Vector128Store(const Vector128 & v,void * to)258 inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void Vector128Store(
259 const Vector128& v, void* to) {
260 uint8_t* dst = reinterpret_cast<uint8_t*>(to);
261 dst[0] = static_cast<uint8_t>(v.s[0] >> 24);
262 dst[1] = static_cast<uint8_t>(v.s[0] >> 16);
263 dst[2] = static_cast<uint8_t>(v.s[0] >> 8);
264 dst[3] = static_cast<uint8_t>(v.s[0]);
265 dst[4] = static_cast<uint8_t>(v.s[1] >> 24);
266 dst[5] = static_cast<uint8_t>(v.s[1] >> 16);
267 dst[6] = static_cast<uint8_t>(v.s[1] >> 8);
268 dst[7] = static_cast<uint8_t>(v.s[1]);
269 dst[8] = static_cast<uint8_t>(v.s[2] >> 24);
270 dst[9] = static_cast<uint8_t>(v.s[2] >> 16);
271 dst[10] = static_cast<uint8_t>(v.s[2] >> 8);
272 dst[11] = static_cast<uint8_t>(v.s[2]);
273 dst[12] = static_cast<uint8_t>(v.s[3] >> 24);
274 dst[13] = static_cast<uint8_t>(v.s[3] >> 16);
275 dst[14] = static_cast<uint8_t>(v.s[3] >> 8);
276 dst[15] = static_cast<uint8_t>(v.s[3]);
277 }
278
279 // One round of AES. "round_key" is a public constant for breaking the
280 // symmetry of AES (ensures previously equal columns differ afterwards).
281 inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE Vector128
AesRound(const Vector128 & state,const Vector128 & round_key)282 AesRound(const Vector128& state, const Vector128& round_key) {
283 Vector128 result;
284 result.s[0] = round_key.s[0] ^ //
285 te0[uint8_t(state.s[0] >> 24)] ^ //
286 te1[uint8_t(state.s[1] >> 16)] ^ //
287 te2[uint8_t(state.s[2] >> 8)] ^ //
288 te3[uint8_t(state.s[3])];
289 result.s[1] = round_key.s[1] ^ //
290 te0[uint8_t(state.s[1] >> 24)] ^ //
291 te1[uint8_t(state.s[2] >> 16)] ^ //
292 te2[uint8_t(state.s[3] >> 8)] ^ //
293 te3[uint8_t(state.s[0])];
294 result.s[2] = round_key.s[2] ^ //
295 te0[uint8_t(state.s[2] >> 24)] ^ //
296 te1[uint8_t(state.s[3] >> 16)] ^ //
297 te2[uint8_t(state.s[0] >> 8)] ^ //
298 te3[uint8_t(state.s[1])];
299 result.s[3] = round_key.s[3] ^ //
300 te0[uint8_t(state.s[3] >> 24)] ^ //
301 te1[uint8_t(state.s[0] >> 16)] ^ //
302 te2[uint8_t(state.s[1] >> 8)] ^ //
303 te3[uint8_t(state.s[2])];
304 return result;
305 }
306
307 using ::absl::random_internal::RandenTraits;
308
309 // Randen operates on 128-bit vectors.
310 struct alignas(16) u64x2 {
311 uint64_t data[2];
312 };
313
314 // The improved Feistel block shuffle function for 16 blocks.
BlockShuffle(u64x2 * state)315 inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void BlockShuffle(
316 u64x2* state) {
317 static_assert(RandenTraits::kFeistelBlocks == 16,
318 "Feistel block shuffle only works for 16 blocks.");
319
320 constexpr size_t shuffle[RandenTraits::kFeistelBlocks] = {
321 7, 2, 13, 4, 11, 8, 3, 6, 15, 0, 9, 10, 1, 14, 5, 12};
322
323 // The fully unrolled loop without the memcpy improves the speed by about
324 // 30% over the equivalent:
325 #if 0
326 u64x2 source[RandenTraits::kFeistelBlocks];
327 std::memcpy(source, state, sizeof(source));
328 for (size_t i = 0; i < RandenTraits::kFeistelBlocks; i++) {
329 const u64x2 v0 = source[shuffle[i]];
330 state[i] = v0;
331 }
332 return;
333 #endif
334
335 const u64x2 v0 = state[shuffle[0]];
336 const u64x2 v1 = state[shuffle[1]];
337 const u64x2 v2 = state[shuffle[2]];
338 const u64x2 v3 = state[shuffle[3]];
339 const u64x2 v4 = state[shuffle[4]];
340 const u64x2 v5 = state[shuffle[5]];
341 const u64x2 v6 = state[shuffle[6]];
342 const u64x2 v7 = state[shuffle[7]];
343 const u64x2 w0 = state[shuffle[8]];
344 const u64x2 w1 = state[shuffle[9]];
345 const u64x2 w2 = state[shuffle[10]];
346 const u64x2 w3 = state[shuffle[11]];
347 const u64x2 w4 = state[shuffle[12]];
348 const u64x2 w5 = state[shuffle[13]];
349 const u64x2 w6 = state[shuffle[14]];
350 const u64x2 w7 = state[shuffle[15]];
351 state[0] = v0;
352 state[1] = v1;
353 state[2] = v2;
354 state[3] = v3;
355 state[4] = v4;
356 state[5] = v5;
357 state[6] = v6;
358 state[7] = v7;
359 state[8] = w0;
360 state[9] = w1;
361 state[10] = w2;
362 state[11] = w3;
363 state[12] = w4;
364 state[13] = w5;
365 state[14] = w6;
366 state[15] = w7;
367 }
368
369 // Feistel round function using two AES subrounds. Very similar to F()
370 // from Simpira v2, but with independent subround keys. Uses 17 AES rounds
371 // per 16 bytes (vs. 10 for AES-CTR). Computing eight round functions in
372 // parallel hides the 7-cycle AESNI latency on HSW. Note that the Feistel
373 // XORs are 'free' (included in the second AES instruction).
FeistelRound(u64x2 * ABSL_RANDOM_INTERNAL_RESTRICT state,const u64x2 * ABSL_RANDOM_INTERNAL_RESTRICT keys)374 inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE const u64x2* FeistelRound(
375 u64x2* ABSL_RANDOM_INTERNAL_RESTRICT state,
376 const u64x2* ABSL_RANDOM_INTERNAL_RESTRICT keys) {
377 for (size_t branch = 0; branch < RandenTraits::kFeistelBlocks; branch += 4) {
378 const Vector128 s0 = Vector128Load(state + branch);
379 const Vector128 s1 = Vector128Load(state + branch + 1);
380 const Vector128 f0 = AesRound(s0, Vector128Load(keys));
381 keys++;
382 const Vector128 o1 = AesRound(f0, s1);
383 Vector128Store(o1, state + branch + 1);
384
385 // Manually unroll this loop once. about 10% better than not unrolled.
386 const Vector128 s2 = Vector128Load(state + branch + 2);
387 const Vector128 s3 = Vector128Load(state + branch + 3);
388 const Vector128 f2 = AesRound(s2, Vector128Load(keys));
389 keys++;
390 const Vector128 o3 = AesRound(f2, s3);
391 Vector128Store(o3, state + branch + 3);
392 }
393 return keys;
394 }
395
396 // Cryptographic permutation based via type-2 Generalized Feistel Network.
397 // Indistinguishable from ideal by chosen-ciphertext adversaries using less than
398 // 2^64 queries if the round function is a PRF. This is similar to the b=8 case
399 // of Simpira v2, but more efficient than its generic construction for b=16.
Permute(u64x2 * state,const u64x2 * ABSL_RANDOM_INTERNAL_RESTRICT keys)400 inline ABSL_RANDOM_INTERNAL_ATTRIBUTE_ALWAYS_INLINE void Permute(
401 u64x2* state, const u64x2* ABSL_RANDOM_INTERNAL_RESTRICT keys) {
402 for (size_t round = 0; round < RandenTraits::kFeistelRounds; ++round) {
403 keys = FeistelRound(state, keys);
404 BlockShuffle(state);
405 }
406 }
407
408 } // namespace
409
410 namespace absl {
411 ABSL_NAMESPACE_BEGIN
412 namespace random_internal {
413
GetKeys()414 const void* RandenSlow::GetKeys() {
415 // Round keys for one AES per Feistel round and branch.
416 // The canonical implementation uses first digits of Pi.
417 return kRandenRoundKeys;
418 }
419
Absorb(const void * seed_void,void * state_void)420 void RandenSlow::Absorb(const void* seed_void, void* state_void) {
421 auto* state =
422 reinterpret_cast<uint64_t * ABSL_RANDOM_INTERNAL_RESTRICT>(state_void);
423 const auto* seed =
424 reinterpret_cast<const uint64_t * ABSL_RANDOM_INTERNAL_RESTRICT>(
425 seed_void);
426
427 constexpr size_t kCapacityBlocks =
428 RandenTraits::kCapacityBytes / sizeof(uint64_t);
429 static_assert(
430 kCapacityBlocks * sizeof(uint64_t) == RandenTraits::kCapacityBytes,
431 "Not i*V");
432
433 for (size_t i = kCapacityBlocks;
434 i < RandenTraits::kStateBytes / sizeof(uint64_t); ++i) {
435 state[i] ^= seed[i - kCapacityBlocks];
436 }
437 }
438
Generate(const void * keys_void,void * state_void)439 void RandenSlow::Generate(const void* keys_void, void* state_void) {
440 static_assert(RandenTraits::kCapacityBytes == sizeof(u64x2),
441 "Capacity mismatch");
442
443 auto* state = reinterpret_cast<u64x2*>(state_void);
444 const auto* keys = reinterpret_cast<const u64x2*>(keys_void);
445
446 const u64x2 prev_inner = state[0];
447
448 Permute(state, keys);
449
450 // Ensure backtracking resistance.
451 state[0].data[0] ^= prev_inner.data[0];
452 state[0].data[1] ^= prev_inner.data[1];
453 }
454
455 } // namespace random_internal
456 ABSL_NAMESPACE_END
457 } // namespace absl
458