66 {0x0000000000000000ull, 0x0000000000000000ull, 0x0000000000000000ull},
67 {0x6366f25ae368399cull, 0x9b03784b5be08490ull, 0x0b5d69bac77ec398ull},
68 {0xca507cfab1d27f98ull, 0xcc53826144575ac3ull, 0x1663f6fac913167cull},
69 {0x9e77fd40e0401d05ull, 0x4f78dfa14aa5157aull, 0x2118b119b4f3c72cull},
70 {0x49e7cd4744b36080ull, 0x401624140d175ba2ull, 0x2b803473f7ad0f3full},
71 {0x41057dd4287e22f1ull, 0xc23d9780306c696aull, 0x359ebc5b69d927dfull},
72 {0x99eaddb5a9520d6aull, 0x51b3314f09de6be4ull, 0x3f782d7204d01447ull},
73 {0x41e86a7632602708ull, 0x16e52e91300efeefull, 0x49101eac381ce609ull},
74 {0x65b157f8deceb53aull, 0x24afdbfd36bf6d33ull, 0x5269e12f346e2bf9ull},
75 {0x9f890503285f6d81ull, 0x35482d13dc0f110cull, 0x5b8887367433795eull},
76 {0x5dba8beba3cb180bull, 0xcad415ae1a715618ull, 0x646eea247c5c22d2ull},
77 {0x14a805ee427197fcull, 0x51bbe3f6289e3ab7ull, 0x6d1fafdce20a8290ull},
78 {0x3e730bb7410e895bull, 0xfaf866415554d6bfull, 0x759d4f80cba83bf8ull},
79 {0xaf992540238215bbull, 0x64c6001143d6c8d5ull, 0x7dea15a32c1b3b38ull},
80 {0x3f2869dd6be1d1ccull, 0x12ba94db12ef0aa8ull, 0x86082806b1d532c4ull},
81 {0xeac6aab2e0ef8a67ull, 0xa89d4ee66c3700e3ull, 0x8df988f4ae806f1dull},
82 {0x24f3e6a3a259b040ull, 0xa00b120a068badd1ull, 0x95c01a39fbd6879full},
83 {0x718d4a9002e2cf95ull, 0x5592074827cb508eull, 0x9d5d9fd5010b3666ull},
84 {0xcb62aff1bd9d6a74ull, 0x495fb7fa6d7eda66ull, 0xa4d3c25e68dc57f2ull},
85 {0xef44639e542c2fd8ull, 0x6c5e946b4ae30894ull, 0xac241134c4e99e1cull},
86 {0x1cf483d2900676c7ull, 0x76da1c872983511eull, 0xb35004723c465e69ull},
87 {0xbf0dfbe6ebff7d3bull, 0x2bc1fe8a8648e9ebull, 0xba58feb2703a9e37ull},
88 {0x6edbb3eae70d10c1ull, 0xe021361e13a30973ull, 0xc1404eadf38396deull},
89 {0xa42463b01fdd3e95ull, 0x1fa8423e8c1443f2ull, 0xc80730b0001667f2ull},
90 {0x38c6a548017167caull, 0x2ac903a413e5a847ull, 0xceaecfea80859b33ull},
91 {0xbedec4594babbdabull, 0xf1be4359106a19b5ull, 0xd53847ac00a69be6ull},
92 {0x05d84c6e2eadff07ull, 0x5b8a19b1c637671full, 0xdba4a47aa996d25aull},
93 {0x712f104646b61eb0ull, 0x4c5a724dbd8180f8ull, 0xe1f4e5170d02a99bull},
94 {0x8aa53e9c8128657aull, 0xc4baee073d4b1b04ull, 0xe829fb693044b398ull},
95 {0xa7bd10d27c064978ull, 0x39d5d6a218c6339full, 0xee44cd59ffab62f3ull},
96 {0x06c1f1d26c710872ull, 0x0d1e3f80fbc71454ull, 0xf446359b13539551ull},
97 {0x82ae728f4624c84bull, 0x6adf27b820fd03e9ull, 0xfa2f045e7832aa72ull}
101 {0x0000000000000000ull, 0x0800000000000000ull},
102 {0x7c1f07c1f07c1f07ull, 0x07c1f07c1f07c1f0ull},
103 {0x8787878787878787ull, 0x0787878787878787ull},
104 {0x7507507507507507ull, 0x0750750750750750ull},
105 {0x71c71c71c71c71c7ull, 0x071c71c71c71c71cull},
106 {0x5306eb3e45306eb3ull, 0x06eb3e45306eb3e4ull},
107 {0xf286bca1af286bcaull, 0x06bca1af286bca1aull},
108 {0x6906906906906906ull, 0x0690690690690690ull},
109 {0x6666666666666666ull, 0x0666666666666666ull},
110 {0x63e7063e7063e706ull, 0x063e7063e7063e70ull},
111 {0x6186186186186186ull, 0x0618618618618618ull},
112 {0xf417d05f417d05f4ull, 0x05f417d05f417d05ull},
113 {0x5d1745d1745d1745ull, 0x05d1745d1745d174ull},
114 {0x5b05b05b05b05b05ull, 0x05b05b05b05b05b0ull},
115 {0x21642c8590b21642ull, 0x0590b21642c8590bull},
116 {0x882b9310572620aeull, 0x0572620ae4c415c9ull},
117 {0x5555555555555555ull, 0x0555555555555555ull},
118 {0x0a72f05397829cbcull, 0x05397829cbc14e5eull},
119 {0x51eb851eb851eb85ull, 0x051eb851eb851eb8ull},
120 {0x0505050505050505ull, 0x0505050505050505ull},
121 {0x4ec4ec4ec4ec4ec4ull, 0x04ec4ec4ec4ec4ecull},
122 {0x4873ecade304d487ull, 0x04d4873ecade304dull},
123 {0xf684bda12f684bdaull, 0x04bda12f684bda12ull},
124 {0x4a7904a7904a7904ull, 0x04a7904a7904a790ull},
125 {0x4924924924924924ull, 0x0492492492492492ull},
126 {0xf7047dc11f7047dcull, 0x047dc11f7047dc11ull},
127 {0x69ee58469ee58469ull, 0x0469ee58469ee584ull},
128 {0x15b1e5f75270d045ull, 0x0456c797dd49c341ull},
129 {0x4444444444444444ull, 0x0444444444444444ull},
130 {0x4325c53ef368eb04ull, 0x04325c53ef368eb0ull},
131 {0x4210842108421084ull, 0x0421084210842108ull},
132 {0x4104104104104104ull, 0x0410410410410410ull}
136 {0x0000000000000000ull, 0x0000000000000000ull},
137 {0x8b92b71842a98364ull, 0x0b5586cf9890f629ull},
138 {0xf7c8c50eb14a7920ull, 0x172b83c7d517adcdull},
139 {0x1fadb1c15cb593b0ull, 0x2387a6e75623866cull},
140 {0x8d5a46305c85ededull, 0x306fe0a31b7152deull},
141 {0x41223e13d773fba3ull, 0x3dea64c12342235bull},
142 {0x397afec42e20e036ull, 0x4bfdad5362a271d4ull},
143 {0x93015191eb345d89ull, 0x5ab07dd48542958cull},
144 {0xb2fb1366ea957d3eull, 0x6a09e667f3bcc908ull},
145 {0x51023f6cda1f5ef4ull, 0x7a11473eb0186d7dull},
146 {0x7c55a192c9bb3e6full, 0x8ace5422aa0db5baull},
147 {0xc46b071f2be58ddbull, 0x9c49182a3f0901c7ull},
148 {0x734d1773205a7fbcull, 0xae89f995ad3ad5e8ull},
149 {0x0cb12a091ba66794ull, 0xc199bdd85529c222ull},
150 {0xa05aeb66e0dca9f6ull, 0xd5818dcfba48725dull},
151 {0xf73a18f5db301f87ull, 0xea4afa2a490d9858ull}
155 {0x0000000000000000ull, 0x0000000000000000ull, 0x0000000000000000ull},
156 {0x03ec04c360be2404ull, 0x4a66ae336dcdfa40ull, 0x0163da9fb33356d8ull},
157 {0x3d70a2cabc5cb89cull, 0xf7caca4f7a29bde9ull, 0x02c9a3e778060ee6ull},
158 {0x40bb4bfc05af6456ull, 0x38f9a20da47e6ed0ull, 0x04315e86e7f84bd7ull},
159 {0x53e3495f7df4baf8ull, 0x7c548eb68ca417feull, 0x059b0d31585743aeull},
160 {0xcb8b092ac75e3117ull, 0xc403a9d87b27ed07ull, 0x0706b29ddf6ddc6dull},
161 {0x1b2d6829d8993a0dull, 0x35f25d9427fa2b04ull, 0x0874518759bc808cull},
162 {0x2e023da730e7fccbull, 0x1e060c584d6b74baull, 0x09e3ecac6f383452ull}
166 {0xbe87fed0691d3e88ull, 0xb8aa3b295c17f0bbull},
167 {0xdf43ff68348e9f44ull, 0x5c551d94ae0bf85dull},
168 {0x3f82aa45785f14d8ull, 0x3d8e13b87407fae9ull},
169 {0xefa1ffb41a474fa2ull, 0x2e2a8eca5705fc2eull},
170 {0x594e6629ae9f72e8ull, 0x24eed8a1df37fcf2ull},
171 {0x9fc15522bc2f8a6cull, 0x1ec709dc3a03fd74ull},
172 {0x645c921dc5df9b38ull, 0x1a61762a7aded93full},
173 {0x77d0ffda0d23a7d1ull, 0x171547652b82fe17ull},
174 {0x6a80e36c7d7506f2ull, 0x1484b13d7c02a8f8ull},
175 {0x2ca73314d74fb974ull, 0x12776c50ef9bfe79ull},
176 {0x5723a2cd20d41cf5ull, 0x10c9a84994022d28ull},
177 {0x4fe0aa915e17c536ull, 0x0f6384ee1d01febaull},
178 {0x711e274b1bc72c31ull, 0x0e347ab4698bb00eull},
179 {0xb22e490ee2efcd9cull, 0x0d30bb153d6f6c9full},
180 {0x731a220de4dfd0f8ull, 0x0c4f9d8b4a67fefbull},
181 {0xbbe87fed0691d3e8ull, 0x0b8aa3b295c17f0bull},
182 {0xa1cbc3b1e810c771ull, 0x0adcd64dba1f86a1ull},
183 {0x354071b63eba8379ull, 0x0a42589ebe01547cull},
184 {0x4d65793363d91e3dull, 0x09b81e0fa687ff32ull},
185 {0x9653998a6ba7dcbaull, 0x093bb62877cdff3cull},
186 {0x76c98609ec9fde68ull, 0x08cb27637e4a486aull},
187 {0x2b91d166906a0e7aull, 0x0864d424ca011694ull},
188 {0x77969bc6475a50a1ull, 0x080766bf04010a77ull},
189 {0x27f05548af0be29bull, 0x07b1c2770e80ff5dull},
190 {0xab76146ebc864a2eull, 0x0762f8205fd7ff63ull},
191 {0x388f13a58de39618ull, 0x071a3d5a34c5d807ull},
192 {0xce2af6797f270250ull, 0x06d6e5bf29563852ull}
195static const uint64_t
xp2_c[13][2] = {
196 {0xc9e3b39803f2f6afull, 0xb17217f7d1cf79abull},
197 {0xde2d60dd92e6bf95ull, 0x3d7f7bff058b1d50ull},
198 {0x99d3b15d995e96f7ull, 0x0e35846b82505fc5ull},
199 {0x39977c16a7dd58a0ull, 0x0276556df749cee5ull},
200 {0x41c5fda69452fb0cull, 0x005761ff9e299cc4ull},
201 {0xb7a58544c3591a0full, 0x000a184897c363c3ull},
202 {0x34358a8e643ec734ull, 0x0000ffe5fe2c4586ull},
203 {0x23fd8ffe606da77cull, 0x0000162c0223a5c8ull},
204 {0x7c3da4a70e5a4ff9ull, 0x000001b5253d395eull},
205 {0x8ec9f6fda1d952e7ull, 0x0000001e4cf5158bull},
206 {0x1bb24c0f57995e47ull, 0x00000001e8cac735ull},
207 {0xfc2985e2b5687e17ull, 0x000000001c3bd650ull},
208 {0x166d0f96281ac300ull, 0x0000000001816193ull}
393 unsigned i = (unsigned)(high >> 59);
394 uint64_t h2 = high & 0x07FFFFFFFFFFFFFFull;
397 uint64_t xls[2] = {low << 5, (h2 << 5) | (low >> 59)};
400 uint64_t v[2] = {rr[2], rr[3]};
404 __uint128_t wf = ((__uint128_t)rr[3] << 64) | rr[2];
418 for (
int k = 22;
k >= 5;
k -= 2) {
430 uint64_t t1[3], t2[3];
435 _umul128to256_((uint64_t)(wf >> 64), (uint64_t)wf, (uint64_t)(
A >> 64), (uint64_t)
A, rr);
440 t1[2] = (t1[2] << 1) | (t1[1] >> 63);
441 t1[1] = (t1[1] << 1) | (t1[0] >> 63);
447 dst[0] = dst[1] = UINT64_MAX;
450 t1[0] += 0x8000000000000000ull;
451 if (t1[0] < 0x8000000000000000ull) {
452 if (++t1[1] == 0 && ++t1[2] == 0) {
453 dst[0] = dst[1] = UINT64_MAX;
462 unsigned i = (unsigned)(high >> 57);
463 uint64_t W[2] = {low, high & 0x01FFFFFFFFFFFFFFull};
466 uint64_t rr[4], zz[4];
468 __uint128_t wfe = ((__uint128_t)rr[3] << 64) | rr[2];
477 __uint128_t
B = ((__uint128_t)
xp2_c[12][1] << 64) |
xp2_c[12][0];
478 __uint128_t
A = ((__uint128_t)
xp2_c[11][1] << 64) |
xp2_c[11][0];
492 uint64_t S[3], u2[3];
497 _umul128to256_((uint64_t)(wfe >> 64), (uint64_t)wfe, (uint64_t)(
A >> 64), (uint64_t)
A, zz);
503 sh[0] = S[1] + (S[0] >> 63);
504 sh[1] = S[2] + (sh[0] < S[1]);
507 unsigned k = i >> 3, m = i & 7;
509 uint64_t t8t[2] = {t8h,
xp2_T8[m][2] + (t8h <
xp2_T8[m][1])};
510 uint64_t q[2], m2[2];
512 m2[0] = rr[2] + (rr[1] >> 63);
513 m2[1] = rr[3] + (m2[0] < rr[2]);
524 m2[0] = rr[2] + (rr[1] >> 63);
525 m2[1] = rr[3] + (m2[0] < rr[2]);
526 uint64_t
r0 = q[0],
r1 = q[1], cy;
527 r0 += sh[0], cy = (
r0 < sh[0]);
528 r1 += cy, cy = (
r1 < cy);
529 r1 += sh[1], cy += (
r1 < sh[1]);
531 dst[0] = dst[1] = UINT64_MAX;
534 r0 += m2[0], cy = (
r0 < m2[0]);
535 r1 += cy, cy = (
r1 < cy);
536 r1 += m2[1], cy += (
r1 < m2[1]);