]> git.cryptolib.org Git - avr-crypto-lib.git/blob - keccak/keccak-asm.S
[keccak-asm] improving last block handling (reducing stack space)
[avr-crypto-lib.git] / keccak / keccak-asm.S
1 /* keccac-asm.S */
2 /*
3     This file is part of the AVR-Crypto-Lib.
4     Copyright (C) 2012  Daniel Otte (daniel.otte@rub.de)
5
6     This program is free software: you can redistribute it and/or modify
7     it under the terms of the GNU General Public License as published by
8     the Free Software Foundation, either version 3 of the License, or
9     (at your option) any later version.
10
11     This program is distributed in the hope that it will be useful,
12     but WITHOUT ANY WARRANTY; without even the implied warranty of
13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14     GNU General Public License for more details.
15
16     You should have received a copy of the GNU General Public License
17     along with this program.  If not, see <http://www.gnu.org/licenses/>.
18 */
19 /**
20  * \file     keccak-asm.S
21  * \email    daniel.otte@rub.de
22  * \author   Daniel Otte
23  * \date     2012-12-16
24  * \license  GPLv3 or later
25  *
26  */
27
28 .nolist
29 #include "avr-asm-macros.S"
30 .list
31
32 .equ __zero_reg__, 1
33
34 .global rho_pi_idx_table
35 rho_pi_idx_table:
36         .irp i, 0, 1, 2, 3, 4
37                 .irp j, 0, 1, 2, 3, 4
38                         .byte (((2 * \j + 3 * \i) % 5) * 5 + \i) * 8
39                 .endr
40         .endr
41
42 .align 2
43
44 .global rotate64_1bit_left
45 rotate64_1bit_left:
46         bst r25, 7
47         rol r18
48         rol r19
49         rol r20
50         rol r21
51         rol r22
52         rol r23
53         rol r24
54         rol r25
55         bld r18, 0
56         ret
57
58 .global rotate64_1bit_right
59 rotate64_1bit_right:
60         bst r18, 0
61         ror r25
62         ror r24
63         ror r23
64         ror r22
65         ror r21
66         ror r20
67         ror r19
68         ror r18
69         bld r25, 7
70         ret
71
72 .global rotate64_nbit_autodir
73 rotate64_nbit_autodir:
74         lsr r16
75         brcc rotate64_nbit_left
76 .global rotate64_nbit_right
77 rotate64_nbit_right:
78         ldi r30, pm_lo8(rotate64_1bit_right)
79         ldi r31, pm_hi8(rotate64_1bit_right)
80         rjmp icall_r16_times
81 .global rotate64_nbit_left
82 rotate64_nbit_left:
83         ldi r30, pm_lo8(rotate64_1bit_left)
84         ldi r31, pm_hi8(rotate64_1bit_left)
85 icall_r16_times:
86 1:      dec r16
87         brmi 2f
88         icall
89         rjmp 1b
90 2:
91     ret
92
93 rotate64_1byte_left:
94         mov r0, r25
95         mov r25, r24
96         mov r24, r23
97         mov r23, r22
98         mov r22, r21
99         mov r21, r20
100         mov r20, r19
101         mov r19, r18
102         mov r18, r0
103         ret
104
105 rotate64_2byte_left:
106         movw r0, r24
107         movw r24, r22
108         movw r22, r20
109         movw r20, r18
110         movw r18, r0
111         ret
112
113 rotate64_3byte_left:
114         mov r0, r25
115         mov r25, r22
116         mov r22, r19
117         mov r19, r24
118         mov r24, r21
119         mov r21, r18
120         mov r18, r23
121         mov r23, r20
122         mov r20, r0
123         ret
124
125 rotate64_4byte_left:
126         movw r0, r24
127         movw r24, r20
128         movw r20, r0
129         movw r0, r22
130         movw r22, r18
131         movw r18, r0
132         ret
133
134 rotate64_5byte_left:
135         mov r0, r25
136         mov r25, r20
137         mov r20, r23
138         mov r23, r18
139         mov r18, r21
140         mov r21, r24
141         mov r24, r19
142         mov r19, r22
143         mov r22, r0
144         ret
145
146 rotate64_6byte_left:
147         movw r0, r18
148         movw r18, r20
149         movw r20, r22
150         movw r22, r24
151         movw r24, r0
152         ret
153
154 rotate64_7byte_left:
155         mov r0, r18
156         mov r18, r19
157         mov r19, r20
158         mov r20, r21
159         mov r21, r22
160         mov r22, r23
161         mov r23, r24
162         mov r24, r25
163         mov r25, r0
164         ret
165
166
167 byte_rot_jmp_table:
168         ret
169         rjmp rotate64_1byte_left
170         rjmp rotate64_2byte_left
171         rjmp rotate64_3byte_left
172         rjmp rotate64_4byte_left
173         rjmp rotate64_5byte_left
174         rjmp rotate64_6byte_left
175         rjmp rotate64_7byte_left
176
177 .global rotate64left_code
178 rotate64left_code:
179         ldi r30, pm_lo8(byte_rot_jmp_table)
180         ldi r31, pm_hi8(byte_rot_jmp_table)
181         mov r0, r16
182         andi r16, 0x70
183         swap r16
184         add r30, r16
185         adc r31, r1
186         mov r16, r0
187         andi r16, 0x0f
188         icall
189         clr r1
190         rjmp rotate64_nbit_autodir
191
192
193 /*
194         void keccak_theta (uint64_t *a, uint64_t *b){
195         // uint64_t b[5][5];
196                 for(i = 0; i < 5; ++i){
197                         b[i][0] = a[0][i] ^ a[1][i] ^ a[2][i] ^ a[3][i] ^ a[4][i];
198                 }
199         }
200 */
201
202 /*********************************************
203  * theta_2a
204  *********************************************
205         input:
206                 r24:r25 = a ; uint64_t a[5][5]
207                 X = b       ; uint64_t *b
208         output:
209                 a[0..4][0] ^= b
210                 r20 = 0
211                 r21 = XX
212                 r22 = XX
213                 r24:r25 += 8
214                 X += 8
215                 Z = r24:r25 + 7 + 4 * 40
216 */
217 theta_2a:
218         ldi r20, 8
219 10:
220         movw ZL, r24
221         ld  r21, X+
222         .irp r, 0, 1, 2, 3, 4
223                 ld  r22, Z
224                 eor r22, r21
225                 st  Z, r22
226         .if \r != 4
227                 adiw ZL, 40
228         .endif
229         .endr
230         adiw r24, 1
231         dec r20
232         brne 10b
233         ret
234
235 /*********************************************
236  * theta_2b
237  *********************************************
238         input:
239                 r24:r25 = a+1 ; uint64_t a[5][5]
240                 X = b       ; uint64_t *b
241         output:
242                 a[0..4][0] ^= rol(b,1)
243                 r19 = XX
244                 r20 = 0
245                 r21 = XX
246                 r22 = XX
247                 r24:r25 += 8
248                 X += 8
249                 Z = r24:r25 + 7 + 4 * 40
250 */
251 theta_2b:
252         ldi r20, 7
253         ld r19, X+
254         lsl r19
255         rol __zero_reg__
256 10:
257         movw ZL, r24
258         ld  r21, X+
259         ror __zero_reg__
260         rol r21
261         rol __zero_reg__
262         .irp r, 0, 1, 2, 3, 4
263                 ld  r22, Z
264                 eor r22, r21
265                 st  Z, r22
266         .if \r != 4
267                 adiw ZL, 40
268         .endif
269         .endr
270         adiw r24, 1
271         dec r20
272         brne 10b
273         add r19, __zero_reg__
274         sbiw r24, 8
275         movw ZL, r24
276         .irp r, 0, 1, 2, 3, 4
277                 ld  r22, Z
278                 eor r22, r19
279                 st  Z, r22
280         .if \r != 4
281                 adiw ZL, 40
282         .endif
283         .endr
284         adiw r24, 9
285         clr __zero_reg__
286         ret
287
288 ;       a[i][j] =  b[i][j] ^ ((~(b[i][(j + 1) % 5])) & (b[i][(j + 2) % 5]));
289
290 /*********************************************
291  * chi_step
292  *********************************************
293         input:
294                 Y = a; uint8t *a;
295                 X = b; uint8t *b;
296                 Z = c; uint8t *c;
297         output:
298                 a[0..7] ^= ~b[0..7] & c[0..7]
299                 X += 8
300                 Y += 8
301                 Z += 8
302                 r16 = 0
303                 trash r21, r22, r23
304 */
305 chi_step:
306         ldi r16, 8
307 10:
308         ld r21, Y
309         ld r22, X+
310         ld r23, Z+
311         com r22
312         and r22, r23
313         eor r21, r22
314         st Y+, r21
315         dec r16
316         brne 10b
317         ret
318
319 .global keccak_f1600
320 keccak_f1600:
321         push_range 2, 9
322         push r16
323         push_range 28, 29
324
325         stack_alloc_large 200, r26, r27
326         adiw XL, 1
327
328         clr r9
329 5:
330         movw r30, r24 ; Z = a
331
332         ldi r19, 5
333 10:
334         ldi r20, 8
335 20:
336         ld  r22, Z
337         adiw ZL, 40
338         ld  r21, Z
339         eor r22, r21
340         adiw ZL, 40
341         ld  r21, Z
342         eor r22, r21
343         adiw ZL, 40
344         ld  r21, Z
345         eor r22, r21
346         adiw ZL, 40
347         ld  r21, Z
348         eor r22, r21
349         adiw r24, 1
350         movw r30, r24
351         st X+, r22
352         dec r20
353         brne 20b
354
355         adiw XL, 8 * 4
356         dec r19
357         brne 10b
358 /*
359         for(i = 0; i < 5; ++i){
360                 for(j = 0; j < 5; ++j){
361                         a[j][i] ^= b[(4 + i) % 5][0];
362                 }
363         }
364
365 */
366 /* a[0..4][0]{0..7} ^= b[4][0]{0..7} */
367         sbiw XL, 5 * 8
368         sbiw r24, 40
369         rcall theta_2a
370 /* a[0..4][1]{0..7} ^= b[0][0]{0..7} */
371         subi XL, lo8(4 * 5 * 8 + 8)
372         sbci XH, hi8(4 * 5 * 8 + 8)
373         rcall theta_2a
374 /* a[0..4][2]{0..7} ^= b[1][0]{0..7} */
375         adiw XL, 4 * 8
376         rcall theta_2a
377 /* a[0..4][3]{0..7} ^= b[2][0]{0..7} */
378         adiw XL, 4 * 8
379         rcall theta_2a
380 /* a[0..4][4]{0..7} ^= b[3][0]{0..7} */
381         adiw XL, 4 * 8
382         rcall theta_2a
383 /*
384         for(i = 0; i < 5; ++i){
385         for(j = 0; j < 5; ++j){
386             a[j][i] ^= rotate64_1bit_left(b[(i + 1) % 5][0]);
387         }
388     }
389 */
390 /* a[0..4][0]{0..7} ^= rol(b[1][0]{0..7}) */
391         subi r24, lo8(5 * 8 - 1)
392         sbci r25, hi8(5 * 8 - 1)
393         subi XL, lo8(2 * 5 * 8 + 8)
394         sbci XH, hi8(2 * 5 * 8 + 8)
395         rcall theta_2b
396 /* a[0..4][1]{0..7} ^= rol(b[2][0]{0..7}) */
397         adiw XL, 4 * 8
398         rcall theta_2b
399 /* a[0..4][21]{0..7} ^= rol(b[3][0]{0..7}) */
400         adiw XL, 4 * 8
401         rcall theta_2b
402 /* a[0..4][3]{0..7} ^= rol(b[4][0]{0..7}) */
403         adiw XL, 4 * 8
404         rcall theta_2b
405 /* a[0..4][4]{0..7} ^= rol(b[0][0]{0..7}) */
406         subi XL, lo8(4 * 5 * 8 + 8)
407         sbci XH, hi8(4 * 5 * 8 + 8)
408         rcall theta_2b
409
410 ;       ret
411 /*
412    -- rho & pi --
413         for(i = 0; i < 5; ++i){
414                 for(j = 0; j < 5; ++j){
415                         b[(2 * i + 3 * j) % 5][j] =
416               rotate64left_code(a[j][i], pgm_read_byte(&(keccak_rotate_codes[i][j])));
417                 }
418         }
419
420    -- or --
421
422         const uint8_t* rot_code = (const uint8_t*)keccak_rotate_codes;
423     const uint8_t* idx_idx = (const uint8_t*)rho_pi_idx_table;
424     uint64_t *a_tmp = (uint64_t*)a;
425         for(i = 0; i < 25; ++i){
426                     *((uint64_t*)(((uint8_t*)b) + pgm_read_byte(idx_idx++))) =
427                 rotate64left_code(*a_tmp++, pgm_read_byte(rot_code++));
428
429         }
430
431 */
432
433 .equ B_REG_L, 6
434 .equ B_REG_H, 7
435
436         ldi r18, lo8(keccak_rotate_codes)
437         ldi r19, hi8(keccak_rotate_codes)
438         movw r2, r18
439         ldi r18, lo8(rho_pi_idx_table)
440         ldi r19, hi8(rho_pi_idx_table)
441         movw r4, r18
442         ldi r16, 25
443         mov r8, r16
444
445         sbiw r24, 5 * 8 + 1
446         movw YL, r24
447         sbiw XL, 8
448         movw B_REG_L, XL
449
450 10:
451         ld r18, Y+
452         ld r19, Y+
453         ld r20, Y+
454         ld r21, Y+
455         ld r22, Y+
456         ld r23, Y+
457         ld r24, Y+
458         ld r25, Y+
459         movw ZL, r2
460         lpm r16, Z+
461         movw r2, ZL
462         rcall rotate64left_code
463         movw ZL, r4
464         lpm r16, Z+
465         movw r4, ZL
466         movw XL, B_REG_L
467         add XL, r16
468         adc XH, __zero_reg__
469         st X+, r18
470         st X+, r19
471         st X+, r20
472         st X+, r21
473         st X+, r22
474         st X+, r23
475         st X+, r24
476         st X+, r25
477
478         dec r8
479         brne 10b
480 /*
481         -- chi --
482         for(i = 0; i < 5; ++i){
483         a[i][0] ^= ((~(b[i][1])) & (b[i][2]));
484         a[i][1] ^= ((~(b[i][2])) & (b[i][3]));
485         a[i][2] ^= ((~(b[i][3])) & (b[i][4]));
486         a[i][3] ^= ((~(b[i][4])) & (b[i][0]));
487         a[i][4] ^= ((~(b[i][0])) & (b[i][1]));
488
489         }
490 */
491         ; memcpy(a, b, 200)
492         ; X points at b + 32 + 8 = b + 40 = b[1][0] has to point to b[0][0]
493         ldi r16, 200
494         sbiw XL, 5 * 8
495         movw ZL, XL
496         subi YL, lo8(5 * 5 * 8)
497         sbci YH, hi8(5 * 5 * 8)
498         movw r2, YL
499 10:
500         ld r22, X+
501         st Y+, r22
502         dec r16
503         brne 10b
504
505         ; Z points at b
506         movw XL, ZL
507         movw r4, ZL
508         adiw XL, 8
509         adiw ZL, 16
510         movw YL, r2
511         ldi r18, 5
512 10:
513         rcall chi_step
514         rcall chi_step
515         rcall chi_step
516         sbiw ZL, 5 * 8
517         rcall chi_step
518         sbiw XL, 5 * 8
519         rcall chi_step
520         adiw XL, 5 * 8
521         adiw ZL, 5 * 8
522         dec r18
523         brne 10b
524
525         /* -- iota -- */
526         ldi r30, lo8(keccak_rc_comp)
527         ldi r31, hi8(keccak_rc_comp)
528         add r30, r9
529         adc r31, __zero_reg__
530         lpm r20, Z+
531         movw YL, r2
532         ldi r21, 0x80
533         bst r20, 6
534         brtc 10f
535         ldd r22, Y+7
536         eor r22, r21
537         std Y+7, r22
538 10:
539         bst r20, 5
540         brtc 10f
541         ldd r22, Y+3
542         eor r22, r21
543         std Y+3, r22
544 10:
545         bst r20, 4
546         brtc 10f
547         ldd r22, Y+1
548         eor r22, r21
549         std Y+1, r22
550 10:
551         andi r20, 0x8f
552         ld r22, Y
553         eor r22, r20
554         st Y, r22
555
556         inc r9
557         mov r16, r9
558         cpi r16, 24
559         breq 20f
560         movw r24, YL
561         movw r26, r4
562         rjmp 5b
563 20:
564
565         stack_free_large3 200
566
567         pop_range 28, 29
568         pop r16
569         pop_range 2, 9
570
571         ret