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 ZH, 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         .endfunc
 344
 345         .global keccak_f1600
 346         .func keccak_f1600
 347 keccak_f1600:
 348         push_range 2, 9
 349         push r16
 350         push_range 28, 29
 351
 352         stack_alloc_large 200, r26, r27
 353         adiw XL, 1
 354
 355         clr r9
 356 5:
 357         movw r30, r24 ; Z = a
 358
 359         ldi r19, 5
 360 10:
 361         ldi r20, 8
 362 20:
 363         ld  r22, Z
 364         adiw ZL, 40
 365         ld  r21, Z
 366         eor r22, r21
 367         adiw ZL, 40
 368         ld  r21, Z
 369         eor r22, r21
 370         adiw ZL, 40
 371         ld  r21, Z
 372         eor r22, r21
 373         adiw ZL, 40
 374         ld  r21, Z
 375         eor r22, r21
 376         adiw r24, 1
 377         movw r30, r24
 378         st X+, r22
 379         dec r20
 380         brne 20b
 381
 382         adiw XL, 8 * 4
 383         dec r19
 384         brne 10b
 385 /*
 386         for(i = 0; i < 5; ++i){
 387                 for(j = 0; j < 5; ++j){
 388                         a[j][i] ^= b[(4 + i) % 5][0];
 389                 }
 390         }
 391
 392 */
 393 /* a[0..4][0]{0..7} ^= b[4][0]{0..7} */
 394         sbiw XL, 5 * 8
 395         sbiw r24, 40
 396         rcall theta_2a
 397 /* a[0..4][1]{0..7} ^= b[0][0]{0..7} */
 398         subi XL, lo8(4 * 5 * 8 + 8)
 399         sbci XH, hi8(4 * 5 * 8 + 8)
 400         rcall theta_2a
 401 /* a[0..4][2]{0..7} ^= b[1][0]{0..7} */
 402         adiw XL, 4 * 8
 403         rcall theta_2a
 404 /* a[0..4][3]{0..7} ^= b[2][0]{0..7} */
 405         adiw XL, 4 * 8
 406         rcall theta_2a
 407 /* a[0..4][4]{0..7} ^= b[3][0]{0..7} */
 408         adiw XL, 4 * 8
 409         rcall theta_2a
 410 /*
 411         for(i = 0; i < 5; ++i){
 412         for(j = 0; j < 5; ++j){
 413             a[j][i] ^= rotate64_1bit_left(b[(i + 1) % 5][0]);
 414         }
 415     }
 416 */
 417 /* a[0..4][0]{0..7} ^= rol(b[1][0]{0..7}) */
 418         subi r24, lo8(5 * 8 - 1)
 419         sbci r25, hi8(5 * 8 - 1)
 420         subi XL, lo8(2 * 5 * 8 + 8)
 421         sbci XH, hi8(2 * 5 * 8 + 8)
 422         rcall theta_2b
 423 /* a[0..4][1]{0..7} ^= rol(b[2][0]{0..7}) */
 424         adiw XL, 4 * 8
 425         rcall theta_2b
 426 /* a[0..4][21]{0..7} ^= rol(b[3][0]{0..7}) */
 427         adiw XL, 4 * 8
 428         rcall theta_2b
 429 /* a[0..4][3]{0..7} ^= rol(b[4][0]{0..7}) */
 430         adiw XL, 4 * 8
 431         rcall theta_2b
 432 /* a[0..4][4]{0..7} ^= rol(b[0][0]{0..7}) */
 433         subi XL, lo8(4 * 5 * 8 + 8)
 434         sbci XH, hi8(4 * 5 * 8 + 8)
 435         rcall theta_2b
 436
 437 ;       ret
 438 /*
 439    -- rho & pi --
 440         for(i = 0; i < 5; ++i){
 441                 for(j = 0; j < 5; ++j){
 442                         b[(2 * i + 3 * j) % 5][j] =
 443               rotate64left_code(a[j][i], pgm_read_byte(&(keccak_rotate_codes[i][j])));
 444                 }
 445         }
 446
 447    -- or --
 448
 449         const uint8_t* rot_code = (const uint8_t*)keccak_rotate_codes;
 450     const uint8_t* idx_idx = (const uint8_t*)rho_pi_idx_table;
 451     uint64_t *a_tmp = (uint64_t*)a;
 452         for(i = 0; i < 25; ++i){
 453                     *((uint64_t*)(((uint8_t*)b) + pgm_read_byte(idx_idx++))) =
 454                 rotate64left_code(*a_tmp++, pgm_read_byte(rot_code++));
 455
 456         }
 457
 458 */
 459
 460 .equ B_REG_L, 6
 461 .equ B_REG_H, 7
 462
 463         ldi r18, lo8(keccak_rotate_codes)
 464         ldi r19, hi8(keccak_rotate_codes)
 465         movw r2, r18
 466         ldi r18, lo8(rho_pi_idx_table)
 467         ldi r19, hi8(rho_pi_idx_table)
 468         movw r4, r18
 469         ldi r16, 25
 470         mov r8, r16
 471
 472         sbiw r24, 5 * 8 + 1
 473         movw YL, r24
 474         sbiw XL, 8
 475         movw B_REG_L, XL
 476
 477 10:
 478         ld r18, Y+
 479         ld r19, Y+
 480         ld r20, Y+
 481         ld r21, Y+
 482         ld r22, Y+
 483         ld r23, Y+
 484         ld r24, Y+
 485         ld r25, Y+
 486         movw ZL, r2
 487         lpm r16, Z+
 488         movw r2, ZL
 489 rotate64left_code:
 490         ldi r30, pm_lo8(byte_rot_jmp_table)
 491         ldi r31, pm_hi8(byte_rot_jmp_table)
 492         mov r0, r16
 493         andi r16, 0x70
 494         swap r16
 495         add r30, r16
 496         adc r31, r1
 497         mov r16, r0
 498         andi r16, 0x0f
 499         icall
 500         clr r1
 501 rotate64_nbit_autodir:
 502         lsr r16
 503         brcc rotate64_nbit_left
 504 rotate64_nbit_right:
 505         ldi r30, pm_lo8(rotate64_1bit_right)
 506         ldi r31, pm_hi8(rotate64_1bit_right)
 507         rjmp icall_r16_times
 508 rotate64_nbit_left:
 509         ldi r30, pm_lo8(rotate64_1bit_left)
 510         ldi r31, pm_hi8(rotate64_1bit_left)
 511 icall_r16_times:
 512 1:      dec r16
 513         brmi 2f
 514         icall
 515         rjmp 1b
 516 2:
 517         movw ZL, r4
 518         lpm r16, Z+
 519         movw r4, ZL
 520         movw XL, B_REG_L
 521         add XL, r16
 522         adc XH, __zero_reg__
 523         st X+, r18
 524         st X+, r19
 525         st X+, r20
 526         st X+, r21
 527         st X+, r22
 528         st X+, r23
 529         st X+, r24
 530         st X+, r25
 531
 532         dec r8
 533         brne 10b
 534 /*
 535         -- chi --
 536         for(i = 0; i < 5; ++i){
 537         a[i][0] ^= ((~(b[i][1])) & (b[i][2]));
 538         a[i][1] ^= ((~(b[i][2])) & (b[i][3]));
 539         a[i][2] ^= ((~(b[i][3])) & (b[i][4]));
 540         a[i][3] ^= ((~(b[i][4])) & (b[i][0]));
 541         a[i][4] ^= ((~(b[i][0])) & (b[i][1]));
 542
 543         }
 544 */
 545         ; memcpy(a, b, 200)
 546         ; X points at b + 32 + 8 = b + 40 = b[1][0] has to point to b[0][0]
 547         ldi r16, 200
 548         sbiw XL, 5 * 8
 549         movw ZL, XL
 550         subi YL, lo8(5 * 5 * 8)
 551         sbci YH, hi8(5 * 5 * 8)
 552         movw r2, YL
 553 10:
 554         ld r22, X+
 555         st Y+, r22
 556         dec r16
 557         brne 10b
 558
 559         ; Z points at b
 560         movw XL, ZL
 561         movw r4, ZL
 562         adiw XL, 8
 563         adiw ZL, 16
 564         movw YL, r2
 565         ldi r18, 5
 566 10:
 567         rcall chi_step
 568         rcall chi_step
 569         rcall chi_step
 570         sbiw ZL, 5 * 8
 571         rcall chi_step
 572         sbiw XL, 5 * 8
 573         rcall chi_step
 574         adiw XL, 5 * 8
 575         adiw ZL, 5 * 8
 576         dec r18
 577         brne 10b
 578
 579         /* -- iota -- */
 580         ldi r30, lo8(keccak_rc_comp)
 581         ldi r31, hi8(keccak_rc_comp)
 582         add r30, r9
 583         adc r31, __zero_reg__
 584         lpm r20, Z+
 585         movw YL, r2
 586         ldi r21, 0x80
 587         bst r20, 6
 588         brtc 10f
 589         ldd r22, Y+7
 590         eor r22, r21
 591         std Y+7, r22
 592 10:
 593         bst r20, 5
 594         brtc 10f
 595         ldd r22, Y+3
 596         eor r22, r21
 597         std Y+3, r22
 598 10:
 599         bst r20, 4
 600         brtc 10f
 601         ldd r22, Y+1
 602         eor r22, r21
 603         std Y+1, r22
 604 10:
 605         andi r20, 0x8f
 606         ld r22, Y
 607         eor r22, r20
 608         st Y, r22
 609
 610         inc r9
 611         mov r16, r9
 612         cpi r16, 24
 613         breq 20f
 614         movw r24, YL
 615         movw r26, r4
 616         rjmp 5b
 617 20:
 618
 619         stack_free_large3 200
 620
 621         pop_range 28, 29
 622         pop r16
 623         pop_range 2, 9
 624         ret
 625         .endfunc
 626
 627 /*
 628 void keccak_ctx2hash(void* dest, uint16_t length_b, keccak_ctx_t* ctx){
 629         while(length_b>=ctx->r){
 630                 memcpy(dest, ctx->a, ctx->bs);
 631                 dest = (uint8_t*)dest + ctx->bs;
 632                 length_b -= ctx->r;
 633                 keccak_f1600(ctx->a);
 634         }
 635         memcpy(dest, ctx->a, (length_b+7)/8);
 636 }
 637 */
 638         .global keccak_ctx2hash
 639         .func keccak_ctx2hash
 640 keccak_ctx2hash:
 641         push_range 2, 10
 642         movw r4, r20
 643         movw r6, r24
 644         movw ZL, r24
 645         movw r8, r22
 646         subi ZL, lo8(-ctx_r)
 647         subi ZH, hi8(-ctx_r)
 648         ld r2, Z+
 649         ld r3, Z+
 650         ldd r10, Z+3 ; load blocksize (in bytes)
 651 10:
 652         cp  r8, r2
 653         cpc r9, r3
 654         brcc 40f
 655         movw XL, r4
 656         movw ZL, r6
 657         mov r24, r10
 658 20:
 659         ld r22, X+
 660         st Z+, r22
 661         dec r24
 662         brne 20b
 663         movw r6, ZL
 664         sub r8, r2
 665         sbc r9, r3
 666         movw r24, r4
 667         rcall keccak_f1600
 668         rjmp 10b
 669 40:
 670         movw XL, r4
 671         movw ZL, r6
 672         movw r24, r8
 673         adiw r24, 7
 674         lsr r25
 675         ror r24
 676         lsr r25
 677         ror r24
 678         lsr r25
 679         ror r24
 680         adiw r24, 0
 681         breq 99f
 682 10:
 683         ld r22, X+
 684         st Z+, r22
 685         sbiw r24, 1
 686         brne 10b
 687 99:
 688         pop_range 2, 10
 689         ret
 690         .endfunc
 691