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 /*
  35 typedef struct{
  36         uint64_t a[5][5];
  37         uint16_t r, c;
  38         uint8_t  d, bs;
  39 } keccak_ctx_t;
  40 */
  41         .struct 0
  42 ctx_a:
  43         .struct ctx_a + 8 * 5 * 5
  44 ctx_r:
  45         .struct ctx_r + 2
  46 ctx_c:
  47         .struct ctx_c + 2
  48 ctx_d:
  49         .struct ctx_d + 1
  50 ctx_bs:
  51
  52         .section .text
  53
  54         .global rho_pi_idx_table
  55 rho_pi_idx_table:
  56         .irp i, 0, 1, 2, 3, 4
  57                 .irp j, 0, 1, 2, 3, 4
  58                         .byte (((2 * \j + 3 * \i) % 5) * 5 + \i) * 8
  59                 .endr
  60         .endr
  61
  62 /*
  63 #define ROT_BIT(a) (( (a) <= 4) ? ((a) << 1) : (0x01 | ((8 - (a)) << 1)))
  64 #define ROT_CODE(a) ((((a) / 8 + ((((a) % 8) > 4) ? 1 : 0)) << 4) | ROT_BIT(((a) % 8)))
  65
  66 const uint8_t keccak_rotate_codes[5][5] PROGMEM = {
  67         { ROT_CODE( 0), ROT_CODE( 1), ROT_CODE(62), ROT_CODE(28), ROT_CODE(27) },
  68         { ROT_CODE(36), ROT_CODE(44), ROT_CODE( 6), ROT_CODE(55), ROT_CODE(20) },
  69         { ROT_CODE( 3), ROT_CODE(10), ROT_CODE(43), ROT_CODE(25), ROT_CODE(39) },
  70         { ROT_CODE(41), ROT_CODE(45), ROT_CODE(15), ROT_CODE(21), ROT_CODE( 8) },
  71         { ROT_CODE(18), ROT_CODE( 2), ROT_CODE(61), ROT_CODE(56), ROT_CODE(14) }
  72 };
  73 */
  74
  75 keccak_rotate_codes:
  76 .byte   0x00, 0x02, 0x85, 0x38, 0x36
  77 .byte   0x48, 0x58, 0x15, 0x73, 0x28
  78 .byte   0x06, 0x14, 0x56, 0x32, 0x53
  79 .byte   0x52, 0x67, 0x23, 0x37, 0x10
  80 .byte   0x24, 0x04, 0x87, 0x70, 0x25
  81
  82 keccak_rc_comp:
  83 .byte   0x01, 0x92, 0xda, 0x70
  84 .byte   0x9b, 0x21, 0xf1, 0x59
  85 .byte   0x8a, 0x88, 0x39, 0x2a
  86 .byte   0xbb, 0xcb, 0xd9, 0x53
  87 .byte   0x52, 0xc0, 0x1a, 0x6a
  88 .byte   0xf1, 0xd0, 0x21, 0x78
  89
  90         .align 2
  91
  92 rotate64_1bit_left:
  93         bst r25, 7
  94         rol r18
  95         rol r19
  96         rol r20
  97         rol r21
  98         rol r22
  99         rol r23
 100         rol r24
 101         rol r25
 102         bld r18, 0
 103         ret
 104
 105 rotate64_1bit_right:
 106         bst r18, 0
 107         ror r25
 108         ror r24
 109         ror r23
 110         ror r22
 111         ror r21
 112         ror r20
 113         ror r19
 114         ror r18
 115         bld r25, 7
 116         ret
 117
 118 rotate64_1byte_left:
 119         mov r0, r25
 120         mov r25, r24
 121         mov r24, r23
 122         mov r23, r22
 123         mov r22, r21
 124         mov r21, r20
 125         mov r20, r19
 126         mov r19, r18
 127         mov r18, r0
 128         ret
 129
 130 rotate64_2byte_left:
 131         movw r0, r24
 132         movw r24, r22
 133         movw r22, r20
 134         movw r20, r18
 135         movw r18, r0
 136         ret
 137
 138 rotate64_3byte_left:
 139         mov r0, r25
 140         mov r25, r22
 141         mov r22, r19
 142         mov r19, r24
 143         mov r24, r21
 144         mov r21, r18
 145         mov r18, r23
 146         mov r23, r20
 147         mov r20, r0
 148         ret
 149
 150 rotate64_4byte_left:
 151         movw r0, r24
 152         movw r24, r20
 153         movw r20, r0
 154         movw r0, r22
 155         movw r22, r18
 156         movw r18, r0
 157         ret
 158
 159 rotate64_5byte_left:
 160         mov r0, r25
 161         mov r25, r20
 162         mov r20, r23
 163         mov r23, r18
 164         mov r18, r21
 165         mov r21, r24
 166         mov r24, r19
 167         mov r19, r22
 168         mov r22, r0
 169         ret
 170
 171 rotate64_6byte_left:
 172         movw r0, r18
 173         movw r18, r20
 174         movw r20, r22
 175         movw r22, r24
 176         movw r24, r0
 177         ret
 178
 179 rotate64_7byte_left:
 180         mov r0, r18
 181         mov r18, r19
 182         mov r19, r20
 183         mov r20, r21
 184         mov r21, r22
 185         mov r22, r23
 186         mov r23, r24
 187         mov r24, r25
 188         mov r25, r0
 189
 190 byte_rot_jmp_table:
 191         ret
 192         rjmp rotate64_1byte_left
 193         rjmp rotate64_2byte_left
 194         rjmp rotate64_3byte_left
 195         rjmp rotate64_4byte_left
 196         rjmp rotate64_5byte_left
 197         rjmp rotate64_6byte_left
 198         rjmp rotate64_7byte_left
 199
 200
 201 /*
 202         void keccak_theta (uint64_t *a, uint64_t *b){
 203         // uint64_t b[5][5];
 204                 for(i = 0; i < 5; ++i){
 205                         b[i][0] = a[0][i] ^ a[1][i] ^ a[2][i] ^ a[3][i] ^ a[4][i];
 206                 }
 207         }
 208 */
 209
 210 /*********************************************
 211  * theta_2a
 212  *********************************************
 213         input:
 214                 r24:r25 = a ; uint64_t a[5][5]
 215                 X = b       ; uint64_t *b
 216         output:
 217                 a[0..4][0] ^= b
 218                 r20 = 0
 219                 r21 = XX
 220                 r22 = XX
 221                 r24:r25 += 8
 222                 X += 8
 223                 Z = r24:r25 + 7 + 4 * 40
 224 */
 225 theta_2a:
 226         ldi r20, 8
 227 10:
 228         movw ZL, r24
 229         ld  r21, X+
 230         .irp r, 0, 1, 2, 3, 4
 231                 ld  r22, Z
 232                 eor r22, r21
 233                 st  Z, r22
 234         .if \r != 4
 235                 adiw ZL, 40
 236         .endif
 237         .endr
 238         adiw r24, 1
 239         dec r20
 240         brne 10b
 241         ret
 242
 243 /*********************************************
 244  * theta_2b
 245  *********************************************
 246         input:
 247                 r24:r25 = a+1 ; uint64_t a[5][5]
 248                 X = b       ; uint64_t *b
 249         output:
 250                 a[0..4][0] ^= rol(b,1)
 251                 r19 = XX
 252                 r20 = 0
 253                 r21 = XX
 254                 r22 = XX
 255                 r24:r25 += 8
 256                 X += 8
 257                 Z = r24:r25 + 7 + 4 * 40
 258 */
 259 theta_2b:
 260         ldi r20, 7
 261         ld r19, X+
 262         lsl r19
 263         rol __zero_reg__
 264 10:
 265         movw ZL, r24
 266         ld  r21, X+
 267         ror __zero_reg__
 268         rol r21
 269         rol __zero_reg__
 270         .irp r, 0, 1, 2, 3, 4
 271                 ld  r22, Z
 272                 eor r22, r21
 273                 st  Z, r22
 274         .if \r != 4
 275                 adiw ZL, 40
 276         .endif
 277         .endr
 278         adiw r24, 1
 279         dec r20
 280         brne 10b
 281         add r19, __zero_reg__
 282         sbiw r24, 8
 283         movw ZL, r24
 284         .irp r, 0, 1, 2, 3, 4
 285                 ld  r22, Z
 286                 eor r22, r19
 287                 st  Z, r22
 288         .if \r != 4
 289                 adiw ZL, 40
 290         .endif
 291         .endr
 292         adiw r24, 9
 293         clr __zero_reg__
 294         ret
 295
 296 ;       a[i][j] =  b[i][j] ^ ((~(b[i][(j + 1) % 5])) & (b[i][(j + 2) % 5]));
 297
 298 /*********************************************
 299  * chi_step
 300  *********************************************
 301         input:
 302                 Y = a; uint8t *a;
 303                 X = b; uint8t *b;
 304                 Z = c; uint8t *c;
 305         output:
 306                 a[0..7] ^= ~b[0..7] & c[0..7]
 307                 X += 8
 308                 Y += 8
 309                 Z += 8
 310                 r16 = 0
 311                 trash r21, r22, r23
 312 */
 313 chi_step:
 314         ldi r16, 8
 315 10:
 316         ld r21, Y
 317         ld r22, X+
 318         ld r23, Z+
 319         com r22
 320         and r22, r23
 321         eor r21, r22
 322         st Y+, r21
 323         dec r16
 324         brne 10b
 325         ret
 326
 327         .global keccak_nextBlock
 328         .func keccak_nextBlock
 329 keccak_nextBlock:
 330         movw ZL, r24
 331         subi ZL, lo8(-ctx_bs)
 332         sbci ZL, hi8(-ctx_bs)
 333         ld r20, Z
 334         movw XL, r24
 335         movw ZL, r22
 336 10:
 337         ld r22, X
 338         ld r23, Z+
 339         eor r22, r23
 340         st X+, r22
 341         dec r20
 342         brne 10b
 343
 344         .global keccak_f1600
 345 keccak_f1600:
 346         push_range 2, 9
 347         push r16
 348         push_range 28, 29
 349
 350         stack_alloc_large 200, r26, r27
 351         adiw XL, 1
 352
 353         clr r9
 354 5:
 355         movw r30, r24 ; Z = a
 356
 357         ldi r19, 5
 358 10:
 359         ldi r20, 8
 360 20:
 361         ld  r22, Z
 362         adiw ZL, 40
 363         ld  r21, Z
 364         eor r22, r21
 365         adiw ZL, 40
 366         ld  r21, Z
 367         eor r22, r21
 368         adiw ZL, 40
 369         ld  r21, Z
 370         eor r22, r21
 371         adiw ZL, 40
 372         ld  r21, Z
 373         eor r22, r21
 374         adiw r24, 1
 375         movw r30, r24
 376         st X+, r22
 377         dec r20
 378         brne 20b
 379
 380         adiw XL, 8 * 4
 381         dec r19
 382         brne 10b
 383 /*
 384         for(i = 0; i < 5; ++i){
 385                 for(j = 0; j < 5; ++j){
 386                         a[j][i] ^= b[(4 + i) % 5][0];
 387                 }
 388         }
 389
 390 */
 391 /* a[0..4][0]{0..7} ^= b[4][0]{0..7} */
 392         sbiw XL, 5 * 8
 393         sbiw r24, 40
 394         rcall theta_2a
 395 /* a[0..4][1]{0..7} ^= b[0][0]{0..7} */
 396         subi XL, lo8(4 * 5 * 8 + 8)
 397         sbci XH, hi8(4 * 5 * 8 + 8)
 398         rcall theta_2a
 399 /* a[0..4][2]{0..7} ^= b[1][0]{0..7} */
 400         adiw XL, 4 * 8
 401         rcall theta_2a
 402 /* a[0..4][3]{0..7} ^= b[2][0]{0..7} */
 403         adiw XL, 4 * 8
 404         rcall theta_2a
 405 /* a[0..4][4]{0..7} ^= b[3][0]{0..7} */
 406         adiw XL, 4 * 8
 407         rcall theta_2a
 408 /*
 409         for(i = 0; i < 5; ++i){
 410         for(j = 0; j < 5; ++j){
 411             a[j][i] ^= rotate64_1bit_left(b[(i + 1) % 5][0]);
 412         }
 413     }
 414 */
 415 /* a[0..4][0]{0..7} ^= rol(b[1][0]{0..7}) */
 416         subi r24, lo8(5 * 8 - 1)
 417         sbci r25, hi8(5 * 8 - 1)
 418         subi XL, lo8(2 * 5 * 8 + 8)
 419         sbci XH, hi8(2 * 5 * 8 + 8)
 420         rcall theta_2b
 421 /* a[0..4][1]{0..7} ^= rol(b[2][0]{0..7}) */
 422         adiw XL, 4 * 8
 423         rcall theta_2b
 424 /* a[0..4][21]{0..7} ^= rol(b[3][0]{0..7}) */
 425         adiw XL, 4 * 8
 426         rcall theta_2b
 427 /* a[0..4][3]{0..7} ^= rol(b[4][0]{0..7}) */
 428         adiw XL, 4 * 8
 429         rcall theta_2b
 430 /* a[0..4][4]{0..7} ^= rol(b[0][0]{0..7}) */
 431         subi XL, lo8(4 * 5 * 8 + 8)
 432         sbci XH, hi8(4 * 5 * 8 + 8)
 433         rcall theta_2b
 434
 435 ;       ret
 436 /*
 437    -- rho & pi --
 438         for(i = 0; i < 5; ++i){
 439                 for(j = 0; j < 5; ++j){
 440                         b[(2 * i + 3 * j) % 5][j] =
 441               rotate64left_code(a[j][i], pgm_read_byte(&(keccak_rotate_codes[i][j])));
 442                 }
 443         }
 444
 445    -- or --
 446
 447         const uint8_t* rot_code = (const uint8_t*)keccak_rotate_codes;
 448     const uint8_t* idx_idx = (const uint8_t*)rho_pi_idx_table;
 449     uint64_t *a_tmp = (uint64_t*)a;
 450         for(i = 0; i < 25; ++i){
 451                     *((uint64_t*)(((uint8_t*)b) + pgm_read_byte(idx_idx++))) =
 452                 rotate64left_code(*a_tmp++, pgm_read_byte(rot_code++));
 453
 454         }
 455
 456 */
 457
 458 .equ B_REG_L, 6
 459 .equ B_REG_H, 7
 460
 461         ldi r18, lo8(keccak_rotate_codes)
 462         ldi r19, hi8(keccak_rotate_codes)
 463         movw r2, r18
 464         ldi r18, lo8(rho_pi_idx_table)
 465         ldi r19, hi8(rho_pi_idx_table)
 466         movw r4, r18
 467         ldi r16, 25
 468         mov r8, r16
 469
 470         sbiw r24, 5 * 8 + 1
 471         movw YL, r24
 472         sbiw XL, 8
 473         movw B_REG_L, XL
 474
 475 10:
 476         ld r18, Y+
 477         ld r19, Y+
 478         ld r20, Y+
 479         ld r21, Y+
 480         ld r22, Y+
 481         ld r23, Y+
 482         ld r24, Y+
 483         ld r25, Y+
 484         movw ZL, r2
 485         lpm r16, Z+
 486         movw r2, ZL
 487 rotate64left_code:
 488         ldi r30, pm_lo8(byte_rot_jmp_table)
 489         ldi r31, pm_hi8(byte_rot_jmp_table)
 490         mov r0, r16
 491         andi r16, 0x70
 492         swap r16
 493         add r30, r16
 494         adc r31, r1
 495         mov r16, r0
 496         andi r16, 0x0f
 497         icall
 498         clr r1
 499 rotate64_nbit_autodir:
 500         lsr r16
 501         brcc rotate64_nbit_left
 502 rotate64_nbit_right:
 503         ldi r30, pm_lo8(rotate64_1bit_right)
 504         ldi r31, pm_hi8(rotate64_1bit_right)
 505         rjmp icall_r16_times
 506 rotate64_nbit_left:
 507         ldi r30, pm_lo8(rotate64_1bit_left)
 508         ldi r31, pm_hi8(rotate64_1bit_left)
 509 icall_r16_times:
 510 1:      dec r16
 511         brmi 2f
 512         icall
 513         rjmp 1b
 514 2:
 515         movw ZL, r4
 516         lpm r16, Z+
 517         movw r4, ZL
 518         movw XL, B_REG_L
 519         add XL, r16
 520         adc XH, __zero_reg__
 521         st X+, r18
 522         st X+, r19
 523         st X+, r20
 524         st X+, r21
 525         st X+, r22
 526         st X+, r23
 527         st X+, r24
 528         st X+, r25
 529
 530         dec r8
 531         brne 10b
 532 /*
 533         -- chi --
 534         for(i = 0; i < 5; ++i){
 535         a[i][0] ^= ((~(b[i][1])) & (b[i][2]));
 536         a[i][1] ^= ((~(b[i][2])) & (b[i][3]));
 537         a[i][2] ^= ((~(b[i][3])) & (b[i][4]));
 538         a[i][3] ^= ((~(b[i][4])) & (b[i][0]));
 539         a[i][4] ^= ((~(b[i][0])) & (b[i][1]));
 540
 541         }
 542 */
 543         ; memcpy(a, b, 200)
 544         ; X points at b + 32 + 8 = b + 40 = b[1][0] has to point to b[0][0]
 545         ldi r16, 200
 546         sbiw XL, 5 * 8
 547         movw ZL, XL
 548         subi YL, lo8(5 * 5 * 8)
 549         sbci YH, hi8(5 * 5 * 8)
 550         movw r2, YL
 551 10:
 552         ld r22, X+
 553         st Y+, r22
 554         dec r16
 555         brne 10b
 556
 557         ; Z points at b
 558         movw XL, ZL
 559         movw r4, ZL
 560         adiw XL, 8
 561         adiw ZL, 16
 562         movw YL, r2
 563         ldi r18, 5
 564 10:
 565         rcall chi_step
 566         rcall chi_step
 567         rcall chi_step
 568         sbiw ZL, 5 * 8
 569         rcall chi_step
 570         sbiw XL, 5 * 8
 571         rcall chi_step
 572         adiw XL, 5 * 8
 573         adiw ZL, 5 * 8
 574         dec r18
 575         brne 10b
 576
 577         /* -- iota -- */
 578         ldi r30, lo8(keccak_rc_comp)
 579         ldi r31, hi8(keccak_rc_comp)
 580         add r30, r9
 581         adc r31, __zero_reg__
 582         lpm r20, Z+
 583         movw YL, r2
 584         ldi r21, 0x80
 585         bst r20, 6
 586         brtc 10f
 587         ldd r22, Y+7
 588         eor r22, r21
 589         std Y+7, r22
 590 10:
 591         bst r20, 5
 592         brtc 10f
 593         ldd r22, Y+3
 594         eor r22, r21
 595         std Y+3, r22
 596 10:
 597         bst r20, 4
 598         brtc 10f
 599         ldd r22, Y+1
 600         eor r22, r21
 601         std Y+1, r22
 602 10:
 603         andi r20, 0x8f
 604         ld r22, Y
 605         eor r22, r20
 606         st Y, r22
 607
 608         inc r9
 609         mov r16, r9
 610         cpi r16, 24
 611         breq 20f
 612         movw r24, YL
 613         movw r26, r4
 614         rjmp 5b
 615 20:
 616
 617         stack_free_large3 200
 618
 619         pop_range 28, 29
 620         pop r16
 621         pop_range 2, 9
 622
 623         ret