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_bs:
  47
  48         .section .text
  49
  50         .global rho_pi_idx_table
  51 rho_pi_idx_table:
  52         .irp i, 0, 1, 2, 3, 4
  53                 .irp j, 0, 1, 2, 3, 4
  54                         .byte (((2 * \j + 3 * \i) % 5) * 5 + \i) * 8
  55                 .endr
  56         .endr
  57
  58 /*
  59 #define ROT_BIT(a) (( (a) <= 4) ? ((a) << 1) : (0x01 | ((8 - (a)) << 1)))
  60 #define ROT_CODE(a) ((((a) / 8 + ((((a) % 8) > 4) ? 1 : 0)) << 4) | ROT_BIT(((a) % 8)))
  61
  62 const uint8_t keccak_rotate_codes[5][5] PROGMEM = {
  63         { ROT_CODE( 0), ROT_CODE( 1), ROT_CODE(62), ROT_CODE(28), ROT_CODE(27) },
  64         { ROT_CODE(36), ROT_CODE(44), ROT_CODE( 6), ROT_CODE(55), ROT_CODE(20) },
  65         { ROT_CODE( 3), ROT_CODE(10), ROT_CODE(43), ROT_CODE(25), ROT_CODE(39) },
  66         { ROT_CODE(41), ROT_CODE(45), ROT_CODE(15), ROT_CODE(21), ROT_CODE( 8) },
  67         { ROT_CODE(18), ROT_CODE( 2), ROT_CODE(61), ROT_CODE(56), ROT_CODE(14) }
  68 };
  69 */
  70
  71 keccak_rotate_codes:
  72 .byte   0x00, 0x02, 0x85, 0x38, 0x36
  73 .byte   0x48, 0x58, 0x15, 0x73, 0x28
  74 .byte   0x06, 0x14, 0x56, 0x32, 0x53
  75 .byte   0x52, 0x67, 0x23, 0x37, 0x10
  76 .byte   0x24, 0x04, 0x87, 0x70, 0x25
  77
  78 keccak_rc_comp:
  79 .byte   0x01, 0x92, 0xda, 0x70
  80 .byte   0x9b, 0x21, 0xf1, 0x59
  81 .byte   0x8a, 0x88, 0x39, 0x2a
  82 .byte   0xbb, 0xcb, 0xd9, 0x53
  83 .byte   0x52, 0xc0, 0x1a, 0x6a
  84 .byte   0xf1, 0xd0, 0x21, 0x78
  85
  86         .align 2
  87
  88 rotate64_1bit_left:
  89         bst r25, 7
  90         rol r18
  91         rol r19
  92         rol r20
  93         rol r21
  94         rol r22
  95         rol r23
  96         rol r24
  97         rol r25
  98         bld r18, 0
  99         ret
 100
 101 rotate64_1bit_right:
 102         bst r18, 0
 103         ror r25
 104         ror r24
 105         ror r23
 106         ror r22
 107         ror r21
 108         ror r20
 109         ror r19
 110         ror r18
 111         bld r25, 7
 112         ret
 113
 114 rotate64_1byte_left:
 115         mov r0, r25
 116         mov r25, r24
 117         mov r24, r23
 118         mov r23, r22
 119         mov r22, r21
 120         mov r21, r20
 121         mov r20, r19
 122         mov r19, r18
 123         mov r18, r0
 124         ret
 125
 126 rotate64_2byte_left:
 127         movw r0, r24
 128         movw r24, r22
 129         movw r22, r20
 130         movw r20, r18
 131         movw r18, r0
 132         ret
 133
 134 rotate64_3byte_left:
 135         mov r0, r25
 136         mov r25, r22
 137         mov r22, r19
 138         mov r19, r24
 139         mov r24, r21
 140         mov r21, r18
 141         mov r18, r23
 142         mov r23, r20
 143         mov r20, r0
 144         ret
 145
 146 rotate64_4byte_left:
 147         movw r0, r24
 148         movw r24, r20
 149         movw r20, r0
 150         movw r0, r22
 151         movw r22, r18
 152         movw r18, r0
 153         ret
 154
 155 rotate64_5byte_left:
 156         mov r0, r25
 157         mov r25, r20
 158         mov r20, r23
 159         mov r23, r18
 160         mov r18, r21
 161         mov r21, r24
 162         mov r24, r19
 163         mov r19, r22
 164         mov r22, r0
 165         ret
 166
 167 rotate64_6byte_left:
 168         movw r0, r18
 169         movw r18, r20
 170         movw r20, r22
 171         movw r22, r24
 172         movw r24, r0
 173         ret
 174
 175 rotate64_7byte_left:
 176         mov r0, r18
 177         mov r18, r19
 178         mov r19, r20
 179         mov r20, r21
 180         mov r21, r22
 181         mov r22, r23
 182         mov r23, r24
 183         mov r24, r25
 184         mov r25, r0
 185
 186 byte_rot_jmp_table:
 187         ret
 188         rjmp rotate64_1byte_left
 189         rjmp rotate64_2byte_left
 190         rjmp rotate64_3byte_left
 191         rjmp rotate64_4byte_left
 192         rjmp rotate64_5byte_left
 193         rjmp rotate64_6byte_left
 194         rjmp rotate64_7byte_left
 195
 196
 197 /*
 198         void keccak_theta (uint64_t *a, uint64_t *b){
 199         // uint64_t b[5][5];
 200                 for(i = 0; i < 5; ++i){
 201                         b[i][0] = a[0][i] ^ a[1][i] ^ a[2][i] ^ a[3][i] ^ a[4][i];
 202                 }
 203         }
 204 */
 205
 206 /*********************************************
 207  * theta_2a
 208  *********************************************
 209         input:
 210                 r24:r25 = a ; uint64_t a[5][5]
 211                 X = b       ; uint64_t *b
 212         output:
 213                 a[0..4][0] ^= b
 214                 r20 = 0
 215                 r21 = XX
 216                 r22 = XX
 217                 r24:r25 += 8
 218                 X += 8
 219                 Z = r24:r25 + 7 + 4 * 40
 220 */
 221 theta_2a:
 222         ldi r20, 8
 223 10:
 224         movw ZL, r24
 225         ld  r21, X+
 226         .irp r, 0, 1, 2, 3, 4
 227                 ld  r22, Z
 228                 eor r22, r21
 229                 st  Z, r22
 230         .if \r != 4
 231                 adiw ZL, 40
 232         .endif
 233         .endr
 234         adiw r24, 1
 235         dec r20
 236         brne 10b
 237         ret
 238
 239 /*********************************************
 240  * theta_2b
 241  *********************************************
 242         input:
 243                 r24:r25 = a+1 ; uint64_t a[5][5]
 244                 X = b       ; uint64_t *b
 245         output:
 246                 a[0..4][0] ^= rol(b,1)
 247                 r19 = XX
 248                 r20 = 0
 249                 r21 = XX
 250                 r22 = XX
 251                 r24:r25 += 8
 252                 X += 8
 253                 Z = r24:r25 + 7 + 4 * 40
 254 */
 255 theta_2b:
 256         ldi r20, 7
 257         ld r19, X+
 258         lsl r19
 259         rol __zero_reg__
 260 10:
 261         movw ZL, r24
 262         ld  r21, X+
 263         ror __zero_reg__
 264         rol r21
 265         rol __zero_reg__
 266         .irp r, 0, 1, 2, 3, 4
 267                 ld  r22, Z
 268                 eor r22, r21
 269                 st  Z, r22
 270         .if \r != 4
 271                 adiw ZL, 40
 272         .endif
 273         .endr
 274         adiw r24, 1
 275         dec r20
 276         brne 10b
 277         add r19, __zero_reg__
 278         sbiw r24, 8
 279         movw ZL, r24
 280         .irp r, 0, 1, 2, 3, 4
 281                 ld  r22, Z
 282                 eor r22, r19
 283                 st  Z, r22
 284         .if \r != 4
 285                 adiw ZL, 40
 286         .endif
 287         .endr
 288         adiw r24, 9
 289         clr __zero_reg__
 290         ret
 291
 292 ;       a[i][j] =  b[i][j] ^ ((~(b[i][(j + 1) % 5])) & (b[i][(j + 2) % 5]));
 293
 294 /*********************************************
 295  * chi_step
 296  *********************************************
 297         input:
 298                 Y = a; uint8t *a;
 299                 X = b; uint8t *b;
 300                 Z = c; uint8t *c;
 301         output:
 302                 a[0..7] ^= ~b[0..7] & c[0..7]
 303                 X += 8
 304                 Y += 8
 305                 Z += 8
 306                 r16 = 0
 307                 trash r21, r22, r23
 308 */
 309 chi_step:
 310         ldi r16, 8
 311 10:
 312         ld r21, Y
 313         ld r22, X+
 314         ld r23, Z+
 315         com r22
 316         and r22, r23
 317         eor r21, r22
 318         st Y+, r21
 319         dec r16
 320         brne 10b
 321         ret
 322
 323         .global keccak_nextBlock
 324         .func keccak_nextBlock
 325 keccak_nextBlock:
 326         movw ZL, r24
 327         subi ZL, lo8(-ctx_bs)
 328         sbci ZH, hi8(-ctx_bs)
 329         ld r20, Z
 330         movw XL, r24
 331         movw ZL, r22
 332 10:
 333         ld r22, X
 334         ld r23, Z+
 335         eor r22, r23
 336         st X+, r22
 337         dec r20
 338         brne 10b
 339         .endfunc
 340
 341         .global keccak_f1600
 342         .func keccak_f1600
 343 keccak_f1600:
 344         push_range 2, 9
 345         push r16
 346         push_range 28, 29
 347
 348         stack_alloc_large 200, r26, r27
 349         adiw XL, 1
 350
 351         clr r9
 352 5:
 353         movw r30, r24 ; Z = a
 354
 355         ldi r19, 5
 356 10:
 357         ldi r20, 8
 358 20:
 359         ld  r22, Z
 360         adiw ZL, 40
 361         ld  r21, Z
 362         eor r22, r21
 363         adiw ZL, 40
 364         ld  r21, Z
 365         eor r22, r21
 366         adiw ZL, 40
 367         ld  r21, Z
 368         eor r22, r21
 369         adiw ZL, 40
 370         ld  r21, Z
 371         eor r22, r21
 372         adiw r24, 1
 373         movw r30, r24
 374         st X+, r22
 375         dec r20
 376         brne 20b
 377
 378         adiw XL, 8 * 4
 379         dec r19
 380         brne 10b
 381 /*
 382         for(i = 0; i < 5; ++i){
 383                 for(j = 0; j < 5; ++j){
 384                         a[j][i] ^= b[(4 + i) % 5][0];
 385                 }
 386         }
 387
 388 */
 389 /* a[0..4][0]{0..7} ^= b[4][0]{0..7} */
 390         sbiw XL, 5 * 8
 391         sbiw r24, 40
 392         rcall theta_2a
 393 /* a[0..4][1]{0..7} ^= b[0][0]{0..7} */
 394         subi XL, lo8(4 * 5 * 8 + 8)
 395         sbci XH, hi8(4 * 5 * 8 + 8)
 396         rcall theta_2a
 397 /* a[0..4][2]{0..7} ^= b[1][0]{0..7} */
 398         adiw XL, 4 * 8
 399         rcall theta_2a
 400 /* a[0..4][3]{0..7} ^= b[2][0]{0..7} */
 401         adiw XL, 4 * 8
 402         rcall theta_2a
 403 /* a[0..4][4]{0..7} ^= b[3][0]{0..7} */
 404         adiw XL, 4 * 8
 405         rcall theta_2a
 406 /*
 407         for(i = 0; i < 5; ++i){
 408         for(j = 0; j < 5; ++j){
 409             a[j][i] ^= rotate64_1bit_left(b[(i + 1) % 5][0]);
 410         }
 411     }
 412 */
 413 /* a[0..4][0]{0..7} ^= rol(b[1][0]{0..7}) */
 414         subi r24, lo8(5 * 8 - 1)
 415         sbci r25, hi8(5 * 8 - 1)
 416         subi XL, lo8(2 * 5 * 8 + 8)
 417         sbci XH, hi8(2 * 5 * 8 + 8)
 418         rcall theta_2b
 419 /* a[0..4][1]{0..7} ^= rol(b[2][0]{0..7}) */
 420         adiw XL, 4 * 8
 421         rcall theta_2b
 422 /* a[0..4][21]{0..7} ^= rol(b[3][0]{0..7}) */
 423         adiw XL, 4 * 8
 424         rcall theta_2b
 425 /* a[0..4][3]{0..7} ^= rol(b[4][0]{0..7}) */
 426         adiw XL, 4 * 8
 427         rcall theta_2b
 428 /* a[0..4][4]{0..7} ^= rol(b[0][0]{0..7}) */
 429         subi XL, lo8(4 * 5 * 8 + 8)
 430         sbci XH, hi8(4 * 5 * 8 + 8)
 431         rcall theta_2b
 432
 433 ;       ret
 434 /*
 435    -- rho & pi --
 436         for(i = 0; i < 5; ++i){
 437                 for(j = 0; j < 5; ++j){
 438                         b[(2 * i + 3 * j) % 5][j] =
 439               rotate64left_code(a[j][i], pgm_read_byte(&(keccak_rotate_codes[i][j])));
 440                 }
 441         }
 442
 443    -- or --
 444
 445         const uint8_t* rot_code = (const uint8_t*)keccak_rotate_codes;
 446     const uint8_t* idx_idx = (const uint8_t*)rho_pi_idx_table;
 447     uint64_t *a_tmp = (uint64_t*)a;
 448         for(i = 0; i < 25; ++i){
 449                     *((uint64_t*)(((uint8_t*)b) + pgm_read_byte(idx_idx++))) =
 450                 rotate64left_code(*a_tmp++, pgm_read_byte(rot_code++));
 451
 452         }
 453
 454 */
 455
 456 .equ B_REG_L, 6
 457 .equ B_REG_H, 7
 458
 459         ldi r18, lo8(keccak_rotate_codes)
 460         ldi r19, hi8(keccak_rotate_codes)
 461         movw r2, r18
 462         ldi r18, lo8(rho_pi_idx_table)
 463         ldi r19, hi8(rho_pi_idx_table)
 464         movw r4, r18
 465         ldi r16, 25
 466         mov r8, r16
 467
 468         sbiw r24, 5 * 8 + 1
 469         movw YL, r24
 470         sbiw XL, 8
 471         movw B_REG_L, XL
 472
 473 10:
 474         ld r18, Y+
 475         ld r19, Y+
 476         ld r20, Y+
 477         ld r21, Y+
 478         ld r22, Y+
 479         ld r23, Y+
 480         ld r24, Y+
 481         ld r25, Y+
 482         movw ZL, r2
 483         lpm r16, Z+
 484         movw r2, ZL
 485 rotate64left_code:
 486         ldi r30, pm_lo8(byte_rot_jmp_table)
 487         ldi r31, pm_hi8(byte_rot_jmp_table)
 488         mov r0, r16
 489         andi r16, 0x70
 490         swap r16
 491         add r30, r16
 492         adc r31, r1
 493         mov r16, r0
 494         andi r16, 0x0f
 495         icall
 496         clr r1
 497 rotate64_nbit_autodir:
 498         lsr r16
 499         brcc rotate64_nbit_left
 500 rotate64_nbit_right:
 501         ldi r30, pm_lo8(rotate64_1bit_right)
 502         ldi r31, pm_hi8(rotate64_1bit_right)
 503         rjmp icall_r16_times
 504 rotate64_nbit_left:
 505         ldi r30, pm_lo8(rotate64_1bit_left)
 506         ldi r31, pm_hi8(rotate64_1bit_left)
 507 icall_r16_times:
 508 1:      dec r16
 509         brmi 2f
 510         icall
 511         rjmp 1b
 512 2:
 513         movw ZL, r4
 514         lpm r16, Z+
 515         movw r4, ZL
 516         movw XL, B_REG_L
 517         add XL, r16
 518         adc XH, __zero_reg__
 519         st X+, r18
 520         st X+, r19
 521         st X+, r20
 522         st X+, r21
 523         st X+, r22
 524         st X+, r23
 525         st X+, r24
 526         st X+, r25
 527
 528         dec r8
 529         brne 10b
 530 /*
 531         -- chi --
 532         for(i = 0; i < 5; ++i){
 533         a[i][0] ^= ((~(b[i][1])) & (b[i][2]));
 534         a[i][1] ^= ((~(b[i][2])) & (b[i][3]));
 535         a[i][2] ^= ((~(b[i][3])) & (b[i][4]));
 536         a[i][3] ^= ((~(b[i][4])) & (b[i][0]));
 537         a[i][4] ^= ((~(b[i][0])) & (b[i][1]));
 538
 539         }
 540 */
 541         ; memcpy(a, b, 200)
 542         ; X points at b + 32 + 8 = b + 40 = b[1][0] has to point to b[0][0]
 543         ldi r16, 200 / 8
 544         sbiw XL, 5 * 8
 545         movw ZL, XL
 546         subi YL, lo8(5 * 5 * 8)
 547         sbci YH, hi8(5 * 5 * 8)
 548         movw r2, YL
 549 10:
 550         .rept 8
 551         ld r22, X+
 552         st Y+, r22
 553         .endr
 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         ret
 623         .endfunc
 624
 625
 626         .global keccak224_ctx2hash
 627         .func keccak224_ctx2hash
 628 keccak224_ctx2hash:
 629         movw r20, r22
 630         ldi r22, lo8(224)
 631         ldi r23, hi8(224)
 632         rjmp keccak_ctx2hash
 633         .endfunc
 634
 635         .global keccak384_ctx2hash
 636         .func keccak384_ctx2hash
 637 keccak384_ctx2hash:
 638         movw r20, r22
 639         ldi r22, lo8(384)
 640         ldi r23, hi8(384)
 641         rjmp keccak_ctx2hash
 642         .endfunc
 643
 644         .global keccak512_ctx2hash
 645         .func keccak512_ctx2hash
 646 keccak512_ctx2hash:
 647         movw r20, r22
 648         ldi r22, lo8(512)
 649         ldi r23, hi8(512)
 650         rjmp keccak_ctx2hash
 651         .endfunc
 652
 653         .global keccak256_ctx2hash
 654         .func keccak256_ctx2hash
 655 keccak256_ctx2hash:
 656         movw r20, r22
 657         ldi r22, lo8(256)
 658         ldi r23, hi8(256)
 659         .endfunc
 660
 661 /*
 662 void keccak_ctx2hash(void* dest, uint16_t length_b, keccak_ctx_t* ctx){
 663         while(length_b>=ctx->r){
 664                 memcpy(dest, ctx->a, ctx->bs);
 665                 dest = (uint8_t*)dest + ctx->bs;
 666                 length_b -= ctx->r;
 667                 keccak_f1600(ctx->a);
 668         }
 669         memcpy(dest, ctx->a, (length_b+7)/8);
 670 }
 671 */
 672         .global keccak_ctx2hash
 673         .func keccak_ctx2hash
 674 keccak_ctx2hash:
 675         push_range 2, 10
 676         movw r4, r20
 677         movw r6, r24
 678         movw ZL, r20
 679         movw r8, r22
 680         subi ZL, lo8(-ctx_r)
 681         sbci ZH, hi8(-ctx_r)
 682         ld r2, Z+
 683         ld r3, Z+
 684         ldd r10, Z+3 ; load blocksize (in bytes)
 685 10:
 686         ; length_b = (r9:r8) ; r = (r3:r2) ; (H:L)
 687         cp  r2, r8
 688         cpc r3, r9
 689 ;       rjmp 40f
 690         brsh 40f
 691         movw XL, r4
 692         movw ZL, r6
 693         mov r24, r10
 694 20:
 695         ld r22, X+
 696         st Z+, r22
 697         dec r24
 698         brne 20b
 699         movw r6, ZL
 700         sub r8, r2
 701         sbc r9, r3
 702         movw r24, r4
 703         rcall keccak_f1600
 704         rjmp 10b
 705 40:
 706         movw XL, r4
 707         movw ZL, r6
 708         movw r24, r8
 709         adiw r24, 7
 710         lsr r25
 711         ror r24
 712         lsr r25
 713         ror r24
 714         lsr r25
 715         ror r24
 716         adiw r24, 0
 717         breq 99f
 718 10:
 719         ld r22, X+
 720         st Z+, r22
 721         sbiw r24, 1
 722         brne 10b
 723 99:
 724         pop_range 2, 10
 725         ret
 726         .endfunc
 727