1 /*
2  * Copyright 2016 The OpenSSL Project Authors. All Rights Reserved.
3  *
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
8  */
10 #include <stdint.h>
11 #include <string.h>
12 #include <assert.h>
14 #define ROL64(a, offset) ((offset) ? (((a) << offset) | ((a) >> (64-offset))) \
15                                    : a)
17 #if defined(KECCAK_REF)
18 /*
19  * This is straightforward or "maximum clarity" implementation aiming
20  * to resemble section 3.2 of the FIPS PUB 202 "SHA-3 Standard:
21  * Permutation-Based Hash and Extendible-Output Functions" as much as
22  * possible. With one caveat. Because of the way C stores matrices,
23  * references to A[x,y] in the specification are presented as A[y][x].
24  * Implementation unrolls inner x-loops so that modulo 5 operations are
25  * explicitly pre-computed.
26  */
27 static void Theta(uint64_t A)
28 {
29     uint64_t C, D;
30     size_t y;
32     C = A;
33     C = A;
34     C = A;
35     C = A;
36     C = A;
38     for (y = 1; y < 5; y++) {
39         C ^= A[y];
40         C ^= A[y];
41         C ^= A[y];
42         C ^= A[y];
43         C ^= A[y];
44     }
46     D = ROL64(C, 1) ^ C;
47     D = ROL64(C, 1) ^ C;
48     D = ROL64(C, 1) ^ C;
49     D = ROL64(C, 1) ^ C;
50     D = ROL64(C, 1) ^ C;
52     for (y = 0; y < 5; y++) {
53         A[y] ^= D;
54         A[y] ^= D;
55         A[y] ^= D;
56         A[y] ^= D;
57         A[y] ^= D;
58     }
59 }
61 static void Rho(uint64_t A)
62 {
63     static const unsigned char rhotates = {
64         {  0,  1, 62, 28, 27 },
65         { 36, 44,  6, 55, 20 },
66         {  3, 10, 43, 25, 39 },
67         { 41, 45, 15, 21,  8 },
68         { 18,  2, 61, 56, 14 }
69     };
70     size_t y;
72     for (y = 0; y < 5; y++) {
73         A[y] = ROL64(A[y], rhotates[y]);
74         A[y] = ROL64(A[y], rhotates[y]);
75         A[y] = ROL64(A[y], rhotates[y]);
76         A[y] = ROL64(A[y], rhotates[y]);
77         A[y] = ROL64(A[y], rhotates[y]);
78     }
79 }
81 static void Pi(uint64_t A)
82 {
83     uint64_t T;
85     /*
86      * T = A
87      * A[y][x] = T[x][(3*y+x)%5]
88      */
89     memcpy(T, A, sizeof(T));
91     A = T;
92     A = T;
93     A = T;
94     A = T;
95     A = T;
97     A = T;
98     A = T;
99     A = T;
100     A = T;
101     A = T;
103     A = T;
104     A = T;
105     A = T;
106     A = T;
107     A = T;
109     A = T;
110     A = T;
111     A = T;
112     A = T;
113     A = T;
115     A = T;
116     A = T;
117     A = T;
118     A = T;
119     A = T;
120 }
122 static void Chi(uint64_t A)
123 {
124     uint64_t C;
125     size_t y;
127     for (y = 0; y < 5; y++) {
128         C = A[y] ^ (~A[y] & A[y]);
129         C = A[y] ^ (~A[y] & A[y]);
130         C = A[y] ^ (~A[y] & A[y]);
131         C = A[y] ^ (~A[y] & A[y]);
132         C = A[y] ^ (~A[y] & A[y]);
134         A[y] = C;
135         A[y] = C;
136         A[y] = C;
137         A[y] = C;
138         A[y] = C;
139     }
140 }
142 static void Iota(uint64_t A, size_t i)
143 {
144     static const uint64_t iotas[] = {
145         0x0000000000000001U, 0x0000000000008082U, 0x800000000000808aU,
146         0x8000000080008000U, 0x000000000000808bU, 0x0000000080000001U,
147         0x8000000080008081U, 0x8000000000008009U, 0x000000000000008aU,
148         0x0000000000000088U, 0x0000000080008009U, 0x000000008000000aU,
149         0x000000008000808bU, 0x800000000000008bU, 0x8000000000008089U,
150         0x8000000000008003U, 0x8000000000008002U, 0x8000000000000080U,
151         0x000000000000800aU, 0x800000008000000aU, 0x8000000080008081U,
152         0x8000000000008080U, 0x0000000080000001U, 0x8000000080008008U
153     };
155     assert(i < (sizeof(iotas) / sizeof(iotas)));
156     A ^= iotas[i];
157 }
159 void KeccakF1600(uint64_t A)
160 {
161     size_t i;
163     for (i = 0; i < 24; i++) {
164         Theta(A);
165         Rho(A);
166         Pi(A);
167         Chi(A);
168         Iota(A, i);
169     }
170 }
172 #elif defined(KECCAK_1X)
173 /*
174  * This implementation is optimization of above code featuring unroll
175  * of even y-loops, their fusion and code motion. It also minimizes
176  * temporary storage. Compiler would normally do all these things for
177  * you, purpose of manual optimization is to provide "unobscured"
178  * reference for assembly implementation [in case this approach is
179  * chosen for implementation on some platform]. In the nutshell it's
180  * equivalent of "plane-per-plane processing" approach discussed in
181  * section 2.4 of "Keccak implementation overview".
182  */
183 static void Round(uint64_t A, size_t i)
184 {
185     uint64_t C, D, T;
186     static const unsigned char rhotates = {
187         {  0,  1, 62, 28, 27 },
188         { 36, 44,  6, 55, 20 },
189         {  3, 10, 43, 25, 39 },
190         { 41, 45, 15, 21,  8 },
191         { 18,  2, 61, 56, 14 }
192     };
193     static const uint64_t iotas[] = {
194         0x0000000000000001U, 0x0000000000008082U, 0x800000000000808aU,
195         0x8000000080008000U, 0x000000000000808bU, 0x0000000080000001U,
196         0x8000000080008081U, 0x8000000000008009U, 0x000000000000008aU,
197         0x0000000000000088U, 0x0000000080008009U, 0x000000008000000aU,
198         0x000000008000808bU, 0x800000000000008bU, 0x8000000000008089U,
199         0x8000000000008003U, 0x8000000000008002U, 0x8000000000000080U,
200         0x000000000000800aU, 0x800000008000000aU, 0x8000000080008081U,
201         0x8000000000008080U, 0x0000000080000001U, 0x8000000080008008U
202     };
204     assert(i < (sizeof(iotas) / sizeof(iotas)));
206     C = A ^ A ^ A ^ A ^ A;
207     C = A ^ A ^ A ^ A ^ A;
208     C = A ^ A ^ A ^ A ^ A;
209     C = A ^ A ^ A ^ A ^ A;
210     C = A ^ A ^ A ^ A ^ A;
212     D = ROL64(C, 1) ^ C;
213     D = ROL64(C, 1) ^ C;
214     D = ROL64(C, 1) ^ C;
215     D = ROL64(C, 1) ^ C;
216     D = ROL64(C, 1) ^ C;
218     C =       A ^ D; /* rotate by 0 */
219     C = ROL64(A ^ D, rhotates);
220     C = ROL64(A ^ D, rhotates);
221     C = ROL64(A ^ D, rhotates);
222     C = ROL64(A ^ D, rhotates);
224     T = A ^ D; /* borrow T */
225     T = A ^ D;
226     T = A ^ D;
227     T = A ^ D;
228     T = A ^ D;
230     A = C ^ (~C & C) ^ iotas[i];
231     A = C ^ (~C & C);
232     A = C ^ (~C & C);
233     A = C ^ (~C & C);
234     A = C ^ (~C & C);
236     C = ROL64(T,        rhotates);
237     C = ROL64(A ^ D, rhotates);
238     C = ROL64(A ^ D, rhotates);
239     C = ROL64(A ^ D, rhotates);
240     C = ROL64(A ^ D, rhotates);
242     T = A ^ D;
243     T = A ^ D; /* borrow T */
244     T = A ^ D;
245     T = A ^ D;
246     T = A ^ D; /* borrow T */
248     A = C ^ (~C & C);
249     A = C ^ (~C & C);
250     A = C ^ (~C & C);
251     A = C ^ (~C & C);
252     A = C ^ (~C & C);
254     C = ROL64(T,        rhotates);
255     C = ROL64(T,        rhotates);
256     C = ROL64(A ^ D, rhotates);
257     C = ROL64(A ^ D, rhotates);
258     C = ROL64(A ^ D, rhotates);
260     A = C ^ (~C & C);
261     A = C ^ (~C & C);
262     A = C ^ (~C & C);
263     A = C ^ (~C & C);
264     A = C ^ (~C & C);
266     C = ROL64(T,        rhotates);
267     C = ROL64(T,        rhotates);
268     C = ROL64(T,        rhotates); /* originally A */
269     C = ROL64(A ^ D, rhotates);
270     C = ROL64(A ^ D, rhotates);
272     A = C ^ (~C & C);
273     A = C ^ (~C & C);
274     A = C ^ (~C & C);
275     A = C ^ (~C & C);
276     A = C ^ (~C & C);
278     C = ROL64(T,        rhotates);
279     C = ROL64(T,        rhotates);
280     C = ROL64(T,        rhotates); /* originally A */
281     C = ROL64(T,        rhotates); /* originally A */
282     C = ROL64(A ^ D, rhotates);
284     A = C ^ (~C & C);
285     A = C ^ (~C & C);
286     A = C ^ (~C & C);
287     A = C ^ (~C & C);
288     A = C ^ (~C & C);
289 }
291 void KeccakF1600(uint64_t A)
292 {
293     size_t i;
295     for (i = 0; i < 24; i++) {
296         Round(A, i);
297     }
298 }
300 #elif defined(KECCAK_2X)
301 /*
302  * This implementation is variant of KECCAK_1X above with outer-most
303  * round loop unrolled twice. This allows to take temporary storage
304  * out of round procedure and simplify references to it by alternating
305  * it with actual data (see round loop below). Just like original, it's
306  * rather meant as reference for an assembly implementation. It's likely
307  * to provide best instruction per processed byte ratio at minimal
308  * round unroll factor...
309  */
310 static void Round(uint64_t R, uint64_t A, size_t i)
311 {
312     uint64_t C, D;
313     static const unsigned char rhotates = {
314         {  0,  1, 62, 28, 27 },
315         { 36, 44,  6, 55, 20 },
316         {  3, 10, 43, 25, 39 },
317         { 41, 45, 15, 21,  8 },
318         { 18,  2, 61, 56, 14 }
319     };
320     static const uint64_t iotas[] = {
321         0x0000000000000001U, 0x0000000000008082U, 0x800000000000808aU,
322         0x8000000080008000U, 0x000000000000808bU, 0x0000000080000001U,
323         0x8000000080008081U, 0x8000000000008009U, 0x000000000000008aU,
324         0x0000000000000088U, 0x0000000080008009U, 0x000000008000000aU,
325         0x000000008000808bU, 0x800000000000008bU, 0x8000000000008089U,
326         0x8000000000008003U, 0x8000000000008002U, 0x8000000000000080U,
327         0x000000000000800aU, 0x800000008000000aU, 0x8000000080008081U,
328         0x8000000000008080U, 0x0000000080000001U, 0x8000000080008008U
329     };
331     assert(i < (sizeof(iotas) / sizeof(iotas)));
333     C = A ^ A ^ A ^ A ^ A;
334     C = A ^ A ^ A ^ A ^ A;
335     C = A ^ A ^ A ^ A ^ A;
336     C = A ^ A ^ A ^ A ^ A;
337     C = A ^ A ^ A ^ A ^ A;
339     D = ROL64(C, 1) ^ C;
340     D = ROL64(C, 1) ^ C;
341     D = ROL64(C, 1) ^ C;
342     D = ROL64(C, 1) ^ C;
343     D = ROL64(C, 1) ^ C;
345     C =       A ^ D; /* rotate by 0 */
346     C = ROL64(A ^ D, rhotates);
347     C = ROL64(A ^ D, rhotates);
348     C = ROL64(A ^ D, rhotates);
349     C = ROL64(A ^ D, rhotates);
351     R = C ^ (~C & C) ^ iotas[i];
352     R = C ^ (~C & C);
353     R = C ^ (~C & C);
354     R = C ^ (~C & C);
355     R = C ^ (~C & C);
357     C = ROL64(A ^ D, rhotates);
358     C = ROL64(A ^ D, rhotates);
359     C = ROL64(A ^ D, rhotates);
360     C = ROL64(A ^ D, rhotates);
361     C = ROL64(A ^ D, rhotates);
363     R = C ^ (~C & C);
364     R = C ^ (~C & C);
365     R = C ^ (~C & C);
366     R = C ^ (~C & C);
367     R = C ^ (~C & C);
369     C = ROL64(A ^ D, rhotates);
370     C = ROL64(A ^ D, rhotates);
371     C = ROL64(A ^ D, rhotates);
372     C = ROL64(A ^ D, rhotates);
373     C = ROL64(A ^ D, rhotates);
375     R = C ^ (~C & C);
376     R = C ^ (~C & C);
377     R = C ^ (~C & C);
378     R = C ^ (~C & C);
379     R = C ^ (~C & C);
381     C = ROL64(A ^ D, rhotates);
382     C = ROL64(A ^ D, rhotates);
383     C = ROL64(A ^ D, rhotates);
384     C = ROL64(A ^ D, rhotates);
385     C = ROL64(A ^ D, rhotates);
387     R = C ^ (~C & C);
388     R = C ^ (~C & C);
389     R = C ^ (~C & C);
390     R = C ^ (~C & C);
391     R = C ^ (~C & C);
393     C = ROL64(A ^ D, rhotates);
394     C = ROL64(A ^ D, rhotates);
395     C = ROL64(A ^ D, rhotates);
396     C = ROL64(A ^ D, rhotates);
397     C = ROL64(A ^ D, rhotates);
399     R = C ^ (~C & C);
400     R = C ^ (~C & C);
401     R = C ^ (~C & C);
402     R = C ^ (~C & C);
403     R = C ^ (~C & C);
404 }
406 void KeccakF1600(uint64_t A)
407 {
408     uint64_t T;
409     size_t i;
411     for (i = 0; i < 24; i += 2) {
412         Round(T, A, i);
413         Round(A, T, i + 1);
414     }
415 }
417 #else
418 /*
419  * This implementation is KECCAK_1X from above combined 4 times with
420  * a twist that allows to omit temporary storage and perform in-place
421  * processing. It's discussed in section 2.5 of "Keccak implementation
422  * overview". It's likely to be best suited for processors with large
423  * register bank...
424  */
425 static void FourRounds(uint64_t A, size_t i)
426 {
427     uint64_t B, C, D;
428     static const unsigned char rhotates = {
429         {  0,  1, 62, 28, 27 },
430         { 36, 44,  6, 55, 20 },
431         {  3, 10, 43, 25, 39 },
432         { 41, 45, 15, 21,  8 },
433         { 18,  2, 61, 56, 14 }
434     };
435     static const uint64_t iotas[] = {
436         0x0000000000000001U, 0x0000000000008082U, 0x800000000000808aU,
437         0x8000000080008000U, 0x000000000000808bU, 0x0000000080000001U,
438         0x8000000080008081U, 0x8000000000008009U, 0x000000000000008aU,
439         0x0000000000000088U, 0x0000000080008009U, 0x000000008000000aU,
440         0x000000008000808bU, 0x800000000000008bU, 0x8000000000008089U,
441         0x8000000000008003U, 0x8000000000008002U, 0x8000000000000080U,
442         0x000000000000800aU, 0x800000008000000aU, 0x8000000080008081U,
443         0x8000000000008080U, 0x0000000080000001U, 0x8000000080008008U
444     };
446     assert(i <= (sizeof(iotas) / sizeof(iotas) - 4));
448     /* Round 4*n */
449     C = A ^ A ^ A ^ A ^ A;
450     C = A ^ A ^ A ^ A ^ A;
451     C = A ^ A ^ A ^ A ^ A;
452     C = A ^ A ^ A ^ A ^ A;
453     C = A ^ A ^ A ^ A ^ A;
455     D = ROL64(C, 1) ^ C;
456     D = ROL64(C, 1) ^ C;
457     D = ROL64(C, 1) ^ C;
458     D = ROL64(C, 1) ^ C;
459     D = ROL64(C, 1) ^ C;
461     B =       A ^ D; /* rotate by 0 */
462     B = ROL64(A ^ D, rhotates);
463     B = ROL64(A ^ D, rhotates);
464     B = ROL64(A ^ D, rhotates);
465     B = ROL64(A ^ D, rhotates);
467     C = A = B ^ (~B & B) ^ iotas[i];
468     C = A = B ^ (~B & B);
469     C = A = B ^ (~B & B);
470     C = A = B ^ (~B & B);
471     C = A = B ^ (~B & B);
473     B = ROL64(A ^ D, rhotates);
474     B = ROL64(A ^ D, rhotates);
475     B = ROL64(A ^ D, rhotates);
476     B = ROL64(A ^ D, rhotates);
477     B = ROL64(A ^ D, rhotates);
479     C ^= A = B ^ (~B & B);
480     C ^= A = B ^ (~B & B);
481     C ^= A = B ^ (~B & B);
482     C ^= A = B ^ (~B & B);
483     C ^= A = B ^ (~B & B);
485     B = ROL64(A ^ D, rhotates);
486     B = ROL64(A ^ D, rhotates);
487     B = ROL64(A ^ D, rhotates);
488     B = ROL64(A ^ D, rhotates);
489     B = ROL64(A ^ D, rhotates);
491     C ^= A = B ^ (~B & B);
492     C ^= A = B ^ (~B & B);
493     C ^= A = B ^ (~B & B);
494     C ^= A = B ^ (~B & B);
495     C ^= A = B ^ (~B & B);
497     B = ROL64(A ^ D, rhotates);
498     B = ROL64(A ^ D, rhotates);
499     B = ROL64(A ^ D, rhotates);
500     B = ROL64(A ^ D, rhotates);
501     B = ROL64(A ^ D, rhotates);
503     C ^= A = B ^ (~B & B);
504     C ^= A = B ^ (~B & B);
505     C ^= A = B ^ (~B & B);
506     C ^= A = B ^ (~B & B);
507     C ^= A = B ^ (~B & B);
509     B = ROL64(A ^ D, rhotates);
510     B = ROL64(A ^ D, rhotates);
511     B = ROL64(A ^ D, rhotates);
512     B = ROL64(A ^ D, rhotates);
513     B = ROL64(A ^ D, rhotates);
515     C ^= A = B ^ (~B & B);
516     C ^= A = B ^ (~B & B);
517     C ^= A = B ^ (~B & B);
518     C ^= A = B ^ (~B & B);
519     C ^= A = B ^ (~B & B);
521     /* Round 4*n+1 */
522     D = ROL64(C, 1) ^ C;
523     D = ROL64(C, 1) ^ C;
524     D = ROL64(C, 1) ^ C;
525     D = ROL64(C, 1) ^ C;
526     D = ROL64(C, 1) ^ C;
528     B =       A ^ D; /* rotate by 0 */
529     B = ROL64(A ^ D, rhotates);
530     B = ROL64(A ^ D, rhotates);
531     B = ROL64(A ^ D, rhotates);
532     B = ROL64(A ^ D, rhotates);
534     C = A = B ^ (~B & B) ^ iotas[i + 1];
535     C = A = B ^ (~B & B);
536     C = A = B ^ (~B & B);
537     C = A = B ^ (~B & B);
538     C = A = B ^ (~B & B);
540     B = ROL64(A ^ D, rhotates);
541     B = ROL64(A ^ D, rhotates);
542     B = ROL64(A ^ D, rhotates);
543     B = ROL64(A ^ D, rhotates);
544     B = ROL64(A ^ D, rhotates);
546     C ^= A = B ^ (~B & B);
547     C ^= A = B ^ (~B & B);
548     C ^= A = B ^ (~B & B);
549     C ^= A = B ^ (~B & B);
550     C ^= A = B ^ (~B & B);
552     B = ROL64(A ^ D, rhotates);
553     B = ROL64(A ^ D, rhotates);
554     B = ROL64(A ^ D, rhotates);
555     B = ROL64(A ^ D, rhotates);
556     B = ROL64(A ^ D, rhotates);
558     C ^= A = B ^ (~B & B);
559     C ^= A = B ^ (~B & B);
560     C ^= A = B ^ (~B & B);
561     C ^= A = B ^ (~B & B);
562     C ^= A = B ^ (~B & B);
564     B = ROL64(A ^ D, rhotates);
565     B = ROL64(A ^ D, rhotates);
566     B = ROL64(A ^ D, rhotates);
567     B = ROL64(A ^ D, rhotates);
568     B = ROL64(A ^ D, rhotates);
570     C ^= A = B ^ (~B & B);
571     C ^= A = B ^ (~B & B);
572     C ^= A = B ^ (~B & B);
573     C ^= A = B ^ (~B & B);
574     C ^= A = B ^ (~B & B);
576     B = ROL64(A ^ D, rhotates);
577     B = ROL64(A ^ D, rhotates);
578     B = ROL64(A ^ D, rhotates);
579     B = ROL64(A ^ D, rhotates);
580     B = ROL64(A ^ D, rhotates);
582     C ^= A = B ^ (~B & B);
583     C ^= A = B ^ (~B & B);
584     C ^= A = B ^ (~B & B);
585     C ^= A = B ^ (~B & B);
586     C ^= A = B ^ (~B & B);
588     /* Round 4*n+2 */
589     D = ROL64(C, 1) ^ C;
590     D = ROL64(C, 1) ^ C;
591     D = ROL64(C, 1) ^ C;
592     D = ROL64(C, 1) ^ C;
593     D = ROL64(C, 1) ^ C;
595     B =       A ^ D; /* rotate by 0 */
596     B = ROL64(A ^ D, rhotates);
597     B = ROL64(A ^ D, rhotates);
598     B = ROL64(A ^ D, rhotates);
599     B = ROL64(A ^ D, rhotates);
601     C = A = B ^ (~B & B) ^ iotas[i + 2];
602     C = A = B ^ (~B & B);
603     C = A = B ^ (~B & B);
604     C = A = B ^ (~B & B);
605     C = A = B ^ (~B & B);
607     B = ROL64(A ^ D, rhotates);
608     B = ROL64(A ^ D, rhotates);
609     B = ROL64(A ^ D, rhotates);
610     B = ROL64(A ^ D, rhotates);
611     B = ROL64(A ^ D, rhotates);
613     C ^= A = B ^ (~B & B);
614     C ^= A = B ^ (~B & B);
615     C ^= A = B ^ (~B & B);
616     C ^= A = B ^ (~B & B);
617     C ^= A = B ^ (~B & B);
619     B = ROL64(A ^ D, rhotates);
620     B = ROL64(A ^ D, rhotates);
621     B = ROL64(A ^ D, rhotates);
622     B = ROL64(A ^ D, rhotates);
623     B = ROL64(A ^ D, rhotates);
625     C ^= A = B ^ (~B & B);
626     C ^= A = B ^ (~B & B);
627     C ^= A = B ^ (~B & B);
628     C ^= A = B ^ (~B & B);
629     C ^= A = B ^ (~B & B);
631     B = ROL64(A ^ D, rhotates);
632     B = ROL64(A ^ D, rhotates);
633     B = ROL64(A ^ D, rhotates);
634     B = ROL64(A ^ D, rhotates);
635     B = ROL64(A ^ D, rhotates);
637     C ^= A = B ^ (~B & B);
638     C ^= A = B ^ (~B & B);
639     C ^= A = B ^ (~B & B);
640     C ^= A = B ^ (~B & B);
641     C ^= A = B ^ (~B & B);
643     B = ROL64(A ^ D, rhotates);
644     B = ROL64(A ^ D, rhotates);
645     B = ROL64(A ^ D, rhotates);
646     B = ROL64(A ^ D, rhotates);
647     B = ROL64(A ^ D, rhotates);
649     C ^= A = B ^ (~B & B);
650     C ^= A = B ^ (~B & B);
651     C ^= A = B ^ (~B & B);
652     C ^= A = B ^ (~B & B);
653     C ^= A = B ^ (~B & B);
655     /* Round 4*n+3 */
656     D = ROL64(C, 1) ^ C;
657     D = ROL64(C, 1) ^ C;
658     D = ROL64(C, 1) ^ C;
659     D = ROL64(C, 1) ^ C;
660     D = ROL64(C, 1) ^ C;
662     B =       A ^ D; /* rotate by 0 */
663     B = ROL64(A ^ D, rhotates);
664     B = ROL64(A ^ D, rhotates);
665     B = ROL64(A ^ D, rhotates);
666     B = ROL64(A ^ D, rhotates);
668     /* C = */ A = B ^ (~B & B) ^ iotas[i + 3];
669     /* C = */ A = B ^ (~B & B);
670     /* C = */ A = B ^ (~B & B);
671     /* C = */ A = B ^ (~B & B);
672     /* C = */ A = B ^ (~B & B);
674     B = ROL64(A ^ D, rhotates);
675     B = ROL64(A ^ D, rhotates);
676     B = ROL64(A ^ D, rhotates);
677     B = ROL64(A ^ D, rhotates);
678     B = ROL64(A ^ D, rhotates);
680     /* C ^= */ A = B ^ (~B & B);
681     /* C ^= */ A = B ^ (~B & B);
682     /* C ^= */ A = B ^ (~B & B);
683     /* C ^= */ A = B ^ (~B & B);
684     /* C ^= */ A = B ^ (~B & B);
686     B = ROL64(A ^ D, rhotates);
687     B = ROL64(A ^ D, rhotates);
688     B = ROL64(A ^ D, rhotates);
689     B = ROL64(A ^ D, rhotates);
690     B = ROL64(A ^ D, rhotates);
692     /* C ^= */ A = B ^ (~B & B);
693     /* C ^= */ A = B ^ (~B & B);
694     /* C ^= */ A = B ^ (~B & B);
695     /* C ^= */ A = B ^ (~B & B);
696     /* C ^= */ A = B ^ (~B & B);
698     B = ROL64(A ^ D, rhotates);
699     B = ROL64(A ^ D, rhotates);
700     B = ROL64(A ^ D, rhotates);
701     B = ROL64(A ^ D, rhotates);
702     B = ROL64(A ^ D, rhotates);
704     /* C ^= */ A = B ^ (~B & B);
705     /* C ^= */ A = B ^ (~B & B);
706     /* C ^= */ A = B ^ (~B & B);
707     /* C ^= */ A = B ^ (~B & B);
708     /* C ^= */ A = B ^ (~B & B);
710     B = ROL64(A ^ D, rhotates);
711     B = ROL64(A ^ D, rhotates);
712     B = ROL64(A ^ D, rhotates);
713     B = ROL64(A ^ D, rhotates);
714     B = ROL64(A ^ D, rhotates);
716     /* C ^= */ A = B ^ (~B & B);
717     /* C ^= */ A = B ^ (~B & B);
718     /* C ^= */ A = B ^ (~B & B);
719     /* C ^= */ A = B ^ (~B & B);
720     /* C ^= */ A = B ^ (~B & B);
721 }
723 void KeccakF1600(uint64_t A)
724 {
725     size_t i;
727     for (i = 0; i < 24; i += 4) {
728         FourRounds(A, i);
729     }
730 }
732 #endif
734 /*
735  * SHA3_absorb can be called multiple times, but at each invocation
736  * largest multiple of |r| out of |len| bytes are processed. Then
737  * remaining amount of bytes are returned. This is done to spare caller
738  * trouble of calculating the largest multiple of |r|, effectively the
739  * blocksize. It is commonly (1600 - 256*n)/8, e.g. 168, 136, 104, 72,
740  * but can also be (1600 - 448)/8 = 144. All this means that message
741  * padding and intermediate sub-block buffering, byte- or bitwise, is
742  * caller's reponsibility.
743  */
744 size_t SHA3_absorb(uint64_t A, const unsigned char *inp, size_t len,
745                    size_t r)
746 {
747     uint64_t *A_flat = (uint64_t *)A;
748     size_t i, w = r / 8;
750     assert(r < (25 * sizeof(A)) && (r % 8) == 0);
752     while (len >= r) {
753         for (i = 0; i < w; i++) {
754             A_flat[i] ^= (uint64_t)inp       | (uint64_t)inp << 8  |
755                          (uint64_t)inp << 16 | (uint64_t)inp << 24 |
756                          (uint64_t)inp << 32 | (uint64_t)inp << 40 |
757                          (uint64_t)inp << 48 | (uint64_t)inp << 56;
758             inp += 8;
759         }
760         KeccakF1600(A);
761         len -= r;
762     }
764     return len;
765 }
767 /*
768  * SHA3_squeeze is called once at the end to generate |out| hash value
769  * of |len| bytes.
770  */
771 void SHA3_squeeze(uint64_t A, unsigned char *out, size_t len, size_t r)
772 {
773     uint64_t *A_flat = (uint64_t *)A;
774     size_t i, rem, w = r / 8;
776     assert(r < (25 * sizeof(A)) && (r % 8) == 0);
778     while (len >= r) {
779         for (i = 0; i < w; i++) {
780             uint64_t Ai = A_flat[i];
782             out = (unsigned char)(Ai);
783             out = (unsigned char)(Ai >> 8);
784             out = (unsigned char)(Ai >> 16);
785             out = (unsigned char)(Ai >> 24);
786             out = (unsigned char)(Ai >> 32);
787             out = (unsigned char)(Ai >> 40);
788             out = (unsigned char)(Ai >> 48);
789             out = (unsigned char)(Ai >> 56);
790             out += 8;
791         }
792         len -= r;
793         if (len)
794             KeccakF1600(A);
795     }
797     rem = len % 8;
798     len /= 8;
800     for (i = 0; i < len; i++) {
801         uint64_t Ai = A_flat[i];
803         out = (unsigned char)(Ai);
804         out = (unsigned char)(Ai >> 8);
805         out = (unsigned char)(Ai >> 16);
806         out = (unsigned char)(Ai >> 24);
807         out = (unsigned char)(Ai >> 32);
808         out = (unsigned char)(Ai >> 40);
809         out = (unsigned char)(Ai >> 48);
810         out = (unsigned char)(Ai >> 56);
811         out += 8;
812     }
814     if (rem) {
815         uint64_t Ai = A_flat[i];
817         for (i = 0; i < rem; i++) {
818             *out++ = (unsigned char)Ai;
819             Ai >>= 8;
820         }
821     }
822 }
824 #ifdef SELFTEST
825 /*
826  * Post-padding one-shot implementations would look as following:
827  *
828  * SHA3_224     SHA3_sponge(inp, len, out, 224/8, (1600-448)/8);
829  * SHA3_256     SHA3_sponge(inp, len, out, 256/8, (1600-512)/8);
830  * SHA3_384     SHA3_sponge(inp, len, out, 384/8, (1600-768)/8);
831  * SHA3_512     SHA3_sponge(inp, len, out, 512/8, (1600-1024)/8);
832  * SHAKE_128    SHA3_sponge(inp, len, out, d, (1600-256)/8);
833  * SHAKE_256    SHA3_sponge(inp, len, out, d, (1600-512)/8);
834  */
836 void SHA3_sponge(const unsigned char *inp, size_t len,
837                  unsigned char *out, size_t d, size_t r)
838 {
839     uint64_t A;
841     memset(A, 0, sizeof(A));
842     SHA3_absorb(A, inp, len, r);
843     SHA3_squeeze(A, out, d, r);
844 }
846 # include <stdio.h>
848 int main()
849 {
850     /*
851      * This is 5-bit SHAKE128 test from http://csrc.nist.gov/groups/ST/toolkit/examples.html#aHashing
852      */
853     unsigned char test = { '\xf3', '\x3' };
854     unsigned char out;
855     size_t i;
856     static const unsigned char result = {
857         0x2E, 0x0A, 0xBF, 0xBA, 0x83, 0xE6, 0x72, 0x0B,
858         0xFB, 0xC2, 0x25, 0xFF, 0x6B, 0x7A, 0xB9, 0xFF,
859         0xCE, 0x58, 0xBA, 0x02, 0x7E, 0xE3, 0xD8, 0x98,
860         0x76, 0x4F, 0xEF, 0x28, 0x7D, 0xDE, 0xCC, 0xCA,
861         0x3E, 0x6E, 0x59, 0x98, 0x41, 0x1E, 0x7D, 0xDB,
862         0x32, 0xF6, 0x75, 0x38, 0xF5, 0x00, 0xB1, 0x8C,
863         0x8C, 0x97, 0xC4, 0x52, 0xC3, 0x70, 0xEA, 0x2C,
864         0xF0, 0xAF, 0xCA, 0x3E, 0x05, 0xDE, 0x7E, 0x4D,
865         0xE2, 0x7F, 0xA4, 0x41, 0xA9, 0xCB, 0x34, 0xFD,
866         0x17, 0xC9, 0x78, 0xB4, 0x2D, 0x5B, 0x7E, 0x7F,
867         0x9A, 0xB1, 0x8F, 0xFE, 0xFF, 0xC3, 0xC5, 0xAC,
868         0x2F, 0x3A, 0x45, 0x5E, 0xEB, 0xFD, 0xC7, 0x6C,
869         0xEA, 0xEB, 0x0A, 0x2C, 0xCA, 0x22, 0xEE, 0xF6,
870         0xE6, 0x37, 0xF4, 0xCA, 0xBE, 0x5C, 0x51, 0xDE,
871         0xD2, 0xE3, 0xFA, 0xD8, 0xB9, 0x52, 0x70, 0xA3,
872         0x21, 0x84, 0x56, 0x64, 0xF1, 0x07, 0xD1, 0x64,
873         0x96, 0xBB, 0x7A, 0xBF, 0xBE, 0x75, 0x04, 0xB6,
874         0xED, 0xE2, 0xE8, 0x9E, 0x4B, 0x99, 0x6F, 0xB5,
875         0x8E, 0xFD, 0xC4, 0x18, 0x1F, 0x91, 0x63, 0x38,
876         0x1C, 0xBE, 0x7B, 0xC0, 0x06, 0xA7, 0xA2, 0x05,
877         0x98, 0x9C, 0x52, 0x6C, 0xD1, 0xBD, 0x68, 0x98,
878         0x36, 0x93, 0xB4, 0xBD, 0xC5, 0x37, 0x28, 0xB2,
879         0x41, 0xC1, 0xCF, 0xF4, 0x2B, 0xB6, 0x11, 0x50,
880         0x2C, 0x35, 0x20, 0x5C, 0xAB, 0xB2, 0x88, 0x75,
881         0x56, 0x55, 0xD6, 0x20, 0xC6, 0x79, 0x94, 0xF0,
882         0x64, 0x51, 0x18, 0x7F, 0x6F, 0xD1, 0x7E, 0x04,
883         0x66, 0x82, 0xBA, 0x12, 0x86, 0x06, 0x3F, 0xF8,
884         0x8F, 0xE2, 0x50, 0x8D, 0x1F, 0xCA, 0xF9, 0x03,
885         0x5A, 0x12, 0x31, 0xAD, 0x41, 0x50, 0xA9, 0xC9,
886         0xB2, 0x4C, 0x9B, 0x2D, 0x66, 0xB2, 0xAD, 0x1B,
887         0xDE, 0x0B, 0xD0, 0xBB, 0xCB, 0x8B, 0xE0, 0x5B,
888         0x83, 0x52, 0x29, 0xEF, 0x79, 0x19, 0x73, 0x73,
889         0x23, 0x42, 0x44, 0x01, 0xE1, 0xD8, 0x37, 0xB6,
890         0x6E, 0xB4, 0xE6, 0x30, 0xFF, 0x1D, 0xE7, 0x0C,
891         0xB3, 0x17, 0xC2, 0xBA, 0xCB, 0x08, 0x00, 0x1D,
892         0x34, 0x77, 0xB7, 0xA7, 0x0A, 0x57, 0x6D, 0x20,
893         0x86, 0x90, 0x33, 0x58, 0x9D, 0x85, 0xA0, 0x1D,
894         0xDB, 0x2B, 0x66, 0x46, 0xC0, 0x43, 0xB5, 0x9F,
895         0xC0, 0x11, 0x31, 0x1D, 0xA6, 0x66, 0xFA, 0x5A,
896         0xD1, 0xD6, 0x38, 0x7F, 0xA9, 0xBC, 0x40, 0x15,
897         0xA3, 0x8A, 0x51, 0xD1, 0xDA, 0x1E, 0xA6, 0x1D,
898         0x64, 0x8D, 0xC8, 0xE3, 0x9A, 0x88, 0xB9, 0xD6,
899         0x22, 0xBD, 0xE2, 0x07, 0xFD, 0xAB, 0xC6, 0xF2,
900         0x82, 0x7A, 0x88, 0x0C, 0x33, 0x0B, 0xBF, 0x6D,
901         0xF7, 0x33, 0x77, 0x4B, 0x65, 0x3E, 0x57, 0x30,
902         0x5D, 0x78, 0xDC, 0xE1, 0x12, 0xF1, 0x0A, 0x2C,
903         0x71, 0xF4, 0xCD, 0xAD, 0x92, 0xED, 0x11, 0x3E,
904         0x1C, 0xEA, 0x63, 0xB9, 0x19, 0x25, 0xED, 0x28,
905         0x19, 0x1E, 0x6D, 0xBB, 0xB5, 0xAA, 0x5A, 0x2A,
906         0xFD, 0xA5, 0x1F, 0xC0, 0x5A, 0x3A, 0xF5, 0x25,
907         0x8B, 0x87, 0x66, 0x52, 0x43, 0x55, 0x0F, 0x28,
908         0x94, 0x8A, 0xE2, 0xB8, 0xBE, 0xB6, 0xBC, 0x9C,
909         0x77, 0x0B, 0x35, 0xF0, 0x67, 0xEA, 0xA6, 0x41,
910         0xEF, 0xE6, 0x5B, 0x1A, 0x44, 0x90, 0x9D, 0x1B,
911         0x14, 0x9F, 0x97, 0xEE, 0xA6, 0x01, 0x39, 0x1C,
912         0x60, 0x9E, 0xC8, 0x1D, 0x19, 0x30, 0xF5, 0x7C,
913         0x18, 0xA4, 0xE0, 0xFA, 0xB4, 0x91, 0xD1, 0xCA,
914         0xDF, 0xD5, 0x04, 0x83, 0x44, 0x9E, 0xDC, 0x0F,
915         0x07, 0xFF, 0xB2, 0x4D, 0x2C, 0x6F, 0x9A, 0x9A,
916         0x3B, 0xFF, 0x39, 0xAE, 0x3D, 0x57, 0xF5, 0x60,
917         0x65, 0x4D, 0x7D, 0x75, 0xC9, 0x08, 0xAB, 0xE6,
918         0x25, 0x64, 0x75, 0x3E, 0xAC, 0x39, 0xD7, 0x50,
919         0x3D, 0xA6, 0xD3, 0x7C, 0x2E, 0x32, 0xE1, 0xAF,
920         0x3B, 0x8A, 0xEC, 0x8A, 0xE3, 0x06, 0x9C, 0xD9
921     };
923     test = '\x80';
924     SHA3_sponge(test, sizeof(test), out, sizeof(out), sizeof(test));
926     /*
927      * Rationale behind keeping output [formatted as below] is that
928      * one should be able to redirect it to a file, then copy-n-paste
929      * final "output val" from official example to another file, and
930      * compare the two with diff(1).
931      */
932     for (i = 0; i < sizeof(out);) {
933         printf("%02X", out[i]);
934         printf(++i % 16 && i != sizeof(out) ? " " : "\n");
935     }
937     if (memcmp(out,result,sizeof(out))) {
938         fprintf(stderr,"failure\n");
939         return 1;
940     } else {
941         fprintf(stderr,"success\n");
942         return 0;
943     }
944 }
945 #endif