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