1#!/usr/bin/env perl 2# Copyright 2017-2020 The OpenSSL Project Authors. All Rights Reserved. 3# 4# Licensed under the OpenSSL license (the "License"). You may not use 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 7# https://www.openssl.org/source/license.html 8# 9# ==================================================================== 10# Written by Andy Polyakov <appro@openssl.org> for the OpenSSL 11# project. The module is, however, dual licensed under OpenSSL and 12# CRYPTOGAMS licenses depending on where you obtain it. For further 13# details see http://www.openssl.org/~appro/cryptogams/. 14# ==================================================================== 15# 16# Keccak-1600 for x86 MMX. 17# 18# June 2017. 19# 20# Below code is KECCAK_2X implementation (see sha/keccak1600.c) with 21# C[5] held in register bank and D[5] offloaded to memory. Though 22# instead of actually unrolling the loop pair-wise I simply flip 23# pointers to T[][] and A[][] and the end of round. Since number of 24# rounds is even, last round writes to A[][] and everything works out. 25# It's argued that MMX is the only code path meaningful to implement 26# for x86. This is because non-MMX-capable processors is an extinct 27# breed, and they as well can lurk executing compiler-generated code. 28# For reference gcc-5.x-generated KECCAK_2X code takes 89 cycles per 29# processed byte on Pentium. Which is fair result. But older compilers 30# produce worse code. On the other hand one can wonder why not 128-bit 31# SSE2? Well, SSE2 won't provide double improvement, rather far from 32# that, if any at all on some processors, because it will take extra 33# permutations and inter-bank data transfers. Besides, contemporary 34# CPUs are better off executing 64-bit code, and it makes lesser sense 35# to invest into fancy 32-bit code. And the decision doesn't seem to 36# be inadequate, if one compares below results to "64-bit platforms in 37# 32-bit mode" SIMD data points available at 38# http://keccak.noekeon.org/sw_performance.html. 39# 40######################################################################## 41# Numbers are cycles per processed byte out of large message. 42# 43# r=1088(i) 44# 45# PIII 30/+150% 46# Pentium M 27/+150% 47# P4 40/+85% 48# Core 2 19/+170% 49# Sandy Bridge(ii) 18/+140% 50# Atom 33/+180% 51# Silvermont(ii) 30/+180% 52# VIA Nano(ii) 43/+60% 53# Sledgehammer(ii)(iii) 24/+130% 54# 55# (i) Corresponds to SHA3-256. Numbers after slash are improvement 56# coefficients over KECCAK_2X [with bit interleave and lane 57# complementing] position-independent *scalar* code generated 58# by gcc-5.x. It's not exactly fair comparison, but it's a 59# datapoint... 60# (ii) 64-bit processor executing 32-bit code. 61# (iii) Result is considered to be representative even for older AMD 62# processors. 63 64$0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1; 65push(@INC,"${dir}","${dir}../../perlasm"); 66require "x86asm.pl"; 67 68$output=pop; 69open STDOUT,">$output"; 70 71&asm_init($ARGV[0],$ARGV[$#ARGV] eq "386"); 72 73my @C = map("mm$_",(0..4)); 74my @T = map("mm$_",(5..7)); 75my @A = map([ 8*$_-100, 8*($_+1)-100, 8*($_+2)-100, 76 8*($_+3)-100, 8*($_+4)-100 ], (0,5,10,15,20)); 77my @D = map(8*$_+4, (0..4)); 78my @rhotates = ([ 0, 1, 62, 28, 27 ], 79 [ 36, 44, 6, 55, 20 ], 80 [ 3, 10, 43, 25, 39 ], 81 [ 41, 45, 15, 21, 8 ], 82 [ 18, 2, 61, 56, 14 ]); 83 84&static_label("iotas"); 85 86&function_begin_B("_KeccakF1600"); 87 &movq (@C[0],&QWP($A[4][0],"esi")); 88 &movq (@C[1],&QWP($A[4][1],"esi")); 89 &movq (@C[2],&QWP($A[4][2],"esi")); 90 &movq (@C[3],&QWP($A[4][3],"esi")); 91 &movq (@C[4],&QWP($A[4][4],"esi")); 92 93 &mov ("ecx",24); # loop counter 94 &jmp (&label("loop")); 95 96 &set_label("loop",16); 97 ######################################### Theta 98 &pxor (@C[0],&QWP($A[0][0],"esi")); 99 &pxor (@C[1],&QWP($A[0][1],"esi")); 100 &pxor (@C[2],&QWP($A[0][2],"esi")); 101 &pxor (@C[3],&QWP($A[0][3],"esi")); 102 &pxor (@C[4],&QWP($A[0][4],"esi")); 103 104 &pxor (@C[0],&QWP($A[1][0],"esi")); 105 &pxor (@C[1],&QWP($A[1][1],"esi")); 106 &pxor (@C[2],&QWP($A[1][2],"esi")); 107 &pxor (@C[3],&QWP($A[1][3],"esi")); 108 &pxor (@C[4],&QWP($A[1][4],"esi")); 109 110 &pxor (@C[0],&QWP($A[2][0],"esi")); 111 &pxor (@C[1],&QWP($A[2][1],"esi")); 112 &pxor (@C[2],&QWP($A[2][2],"esi")); 113 &pxor (@C[3],&QWP($A[2][3],"esi")); 114 &pxor (@C[4],&QWP($A[2][4],"esi")); 115 116 &pxor (@C[2],&QWP($A[3][2],"esi")); 117 &pxor (@C[0],&QWP($A[3][0],"esi")); 118 &pxor (@C[1],&QWP($A[3][1],"esi")); 119 &pxor (@C[3],&QWP($A[3][3],"esi")); 120 &movq (@T[0],@C[2]); 121 &pxor (@C[4],&QWP($A[3][4],"esi")); 122 123 &movq (@T[2],@C[2]); 124 &psrlq (@T[0],63); 125 &movq (@T[1],@C[0]); 126 &psllq (@T[2],1); 127 &pxor (@T[0],@C[0]); 128 &psrlq (@C[0],63); 129 &pxor (@T[0],@T[2]); 130 &psllq (@T[1],1); 131 &movq (@T[2],@C[1]); 132 &movq (&QWP(@D[1],"esp"),@T[0]); # D[1] = E[0] = ROL64(C[2], 1) ^ C[0]; 133 134 &pxor (@T[1],@C[0]); 135 &psrlq (@T[2],63); 136 &pxor (@T[1],@C[3]); 137 &movq (@C[0],@C[1]); 138 &movq (&QWP(@D[4],"esp"),@T[1]); # D[4] = E[1] = ROL64(C[0], 1) ^ C[3]; 139 140 &psllq (@C[0],1); 141 &pxor (@T[2],@C[4]); 142 &pxor (@C[0],@T[2]); 143 144 &movq (@T[2],@C[3]); 145 &psrlq (@C[3],63); 146 &movq (&QWP(@D[0],"esp"),@C[0]); # D[0] = C[0] = ROL64(C[1], 1) ^ C[4]; 147 &psllq (@T[2],1); 148 &movq (@T[0],@C[4]); 149 &psrlq (@C[4],63); 150 &pxor (@C[1],@C[3]); 151 &psllq (@T[0],1); 152 &pxor (@C[1],@T[2]); 153 &pxor (@C[2],@C[4]); 154 &movq (&QWP(@D[2],"esp"),@C[1]); # D[2] = C[1] = ROL64(C[3], 1) ^ C[1]; 155 &pxor (@C[2],@T[0]); 156 157 ######################################### first Rho(0) is special 158 &movq (@C[3],&QWP($A[3][3],"esi")); 159 &movq (&QWP(@D[3],"esp"),@C[2]); # D[3] = C[2] = ROL64(C[4], 1) ^ C[2]; 160 &pxor (@C[3],@C[2]); 161 &movq (@C[4],&QWP($A[4][4],"esi")); 162 &movq (@T[2],@C[3]); 163 &psrlq (@C[3],64-$rhotates[3][3]); 164 &pxor (@C[4],@T[1]); 165 &psllq (@T[2],$rhotates[3][3]); 166 &movq (@T[1],@C[4]); 167 &psrlq (@C[4],64-$rhotates[4][4]); 168 &por (@C[3],@T[2]); # C[3] = ROL64(A[3][3] ^ C[2], rhotates[3][3]); /* D[3] */ 169 &psllq (@T[1],$rhotates[4][4]); 170 171 &movq (@C[2],&QWP($A[2][2],"esi")); 172 &por (@C[4],@T[1]); # C[4] = ROL64(A[4][4] ^ E[1], rhotates[4][4]); /* D[4] */ 173 &pxor (@C[2],@C[1]); 174 &movq (@C[1],&QWP($A[1][1],"esi")); 175 &movq (@T[1],@C[2]); 176 &psrlq (@C[2],64-$rhotates[2][2]); 177 &pxor (@C[1],&QWP(@D[1],"esp")); 178 &psllq (@T[1],$rhotates[2][2]); 179 180 &movq (@T[2],@C[1]); 181 &psrlq (@C[1],64-$rhotates[1][1]); 182 &por (@C[2],@T[1]); # C[2] = ROL64(A[2][2] ^ C[1], rhotates[2][2]); /* D[2] */ 183 &psllq (@T[2],$rhotates[1][1]); 184 &pxor (@C[0],&QWP($A[0][0],"esi")); # /* rotate by 0 */ /* D[0] */ 185 &por (@C[1],@T[2]); # C[1] = ROL64(A[1][1] ^ D[1], rhotates[1][1]); 186 187sub Chi() { ######### regular Chi step 188 my ($y,$xrho) = @_; 189 190 &movq (@T[0],@C[1]); 191 &movq (@T[1],@C[2]); 192 &pandn (@T[0],@C[2]); 193 &pandn (@C[2],@C[3]); 194 &pxor (@T[0],@C[0]); 195 &pxor (@C[2],@C[1]); 196 &pxor (@T[0],&QWP(0,"ebx")) if ($y == 0); 197 &lea ("ebx",&DWP(8,"ebx")) if ($y == 0); 198 199 &movq (@T[2],@C[3]); 200 &movq (&QWP($A[$y][0],"edi"),@T[0]); # R[0][0] = C[0] ^ (~C[1] & C[2]) ^ iotas[i]; 201 &movq (@T[0],@C[4]); 202 &pandn (@C[3],@C[4]); 203 &pandn (@C[4],@C[0]); 204 &pxor (@C[3],@T[1]); 205 &movq (&QWP($A[$y][1],"edi"),@C[2]); # R[0][1] = C[1] ^ (~C[2] & C[3]); 206 &pxor (@C[4],@T[2]); 207 &movq (@T[2],&QWP($A[0][$xrho],"esi")) if (defined($xrho)); 208 209 &movq (&QWP($A[$y][2],"edi"),@C[3]); # R[0][2] = C[2] ^ (~C[3] & C[4]); 210 &pandn (@C[0],@C[1]); 211 &movq (&QWP($A[$y][3],"edi"),@C[4]); # R[0][3] = C[3] ^ (~C[4] & C[0]); 212 &pxor (@C[0],@T[0]); 213 &pxor (@T[2],&QWP(@D[$xrho],"esp")) if (defined($xrho)); 214 &movq (&QWP($A[$y][4],"edi"),@C[0]); # R[0][4] = C[4] ^ (~C[0] & C[1]); 215} 216 &Chi (0, 3); 217 218sub Rho() { ######### regular Rho step 219 my $x = shift; 220 221 #&movq (@T[2],&QWP($A[0][$x],"esi")); # moved to Chi 222 #&pxor (@T[2],&QWP(@D[$x],"esp")); # moved to Chi 223 &movq (@C[0],@T[2]); 224 &psrlq (@T[2],64-$rhotates[0][$x]); 225 &movq (@C[1],&QWP($A[1][($x+1)%5],"esi")); 226 &psllq (@C[0],$rhotates[0][$x]); 227 &pxor (@C[1],&QWP(@D[($x+1)%5],"esp")); 228 &por (@C[0],@T[2]); # C[0] = ROL64(A[0][3] ^ D[3], rhotates[0][3]); 229 230 &movq (@T[1],@C[1]); 231 &psrlq (@C[1],64-$rhotates[1][($x+1)%5]); 232 &movq (@C[2],&QWP($A[2][($x+2)%5],"esi")); 233 &psllq (@T[1],$rhotates[1][($x+1)%5]); 234 &pxor (@C[2],&QWP(@D[($x+2)%5],"esp")); 235 &por (@C[1],@T[1]); # C[1] = ROL64(A[1][4] ^ D[4], rhotates[1][4]); 236 237 &movq (@T[2],@C[2]); 238 &psrlq (@C[2],64-$rhotates[2][($x+2)%5]); 239 &movq (@C[3],&QWP($A[3][($x+3)%5],"esi")); 240 &psllq (@T[2],$rhotates[2][($x+2)%5]); 241 &pxor (@C[3],&QWP(@D[($x+3)%5],"esp")); 242 &por (@C[2],@T[2]); # C[2] = ROL64(A[2][0] ^ D[0], rhotates[2][0]); 243 244 &movq (@T[0],@C[3]); 245 &psrlq (@C[3],64-$rhotates[3][($x+3)%5]); 246 &movq (@C[4],&QWP($A[4][($x+4)%5],"esi")); 247 &psllq (@T[0],$rhotates[3][($x+3)%5]); 248 &pxor (@C[4],&QWP(@D[($x+4)%5],"esp")); 249 &por (@C[3],@T[0]); # C[3] = ROL64(A[3][1] ^ D[1], rhotates[3][1]); 250 251 &movq (@T[1],@C[4]); 252 &psrlq (@C[4],64-$rhotates[4][($x+4)%5]); 253 &psllq (@T[1],$rhotates[4][($x+4)%5]); 254 &por (@C[4],@T[1]); # C[4] = ROL64(A[4][2] ^ D[2], rhotates[4][2]); 255} 256 &Rho (3); &Chi (1, 1); 257 &Rho (1); &Chi (2, 4); 258 &Rho (4); &Chi (3, 2); 259 &Rho (2); ###&Chi (4); 260 261 &movq (@T[0],@C[0]); ######### last Chi(4) is special 262 &xor ("edi","esi"); # &xchg ("esi","edi"); 263 &movq (&QWP(@D[1],"esp"),@C[1]); 264 &xor ("esi","edi"); 265 &xor ("edi","esi"); 266 267 &movq (@T[1],@C[1]); 268 &movq (@T[2],@C[2]); 269 &pandn (@T[1],@C[2]); 270 &pandn (@T[2],@C[3]); 271 &pxor (@C[0],@T[1]); 272 &pxor (@C[1],@T[2]); 273 274 &movq (@T[1],@C[3]); 275 &movq (&QWP($A[4][0],"esi"),@C[0]); # R[4][0] = C[0] ^= (~C[1] & C[2]); 276 &pandn (@T[1],@C[4]); 277 &movq (&QWP($A[4][1],"esi"),@C[1]); # R[4][1] = C[1] ^= (~C[2] & C[3]); 278 &pxor (@C[2],@T[1]); 279 &movq (@T[2],@C[4]); 280 &movq (&QWP($A[4][2],"esi"),@C[2]); # R[4][2] = C[2] ^= (~C[3] & C[4]); 281 282 &pandn (@T[2],@T[0]); 283 &pandn (@T[0],&QWP(@D[1],"esp")); 284 &pxor (@C[3],@T[2]); 285 &pxor (@C[4],@T[0]); 286 &movq (&QWP($A[4][3],"esi"),@C[3]); # R[4][3] = C[3] ^= (~C[4] & D[0]); 287 &sub ("ecx",1); 288 &movq (&QWP($A[4][4],"esi"),@C[4]); # R[4][4] = C[4] ^= (~D[0] & D[1]); 289 &jnz (&label("loop")); 290 291 &lea ("ebx",&DWP(-192,"ebx")); # rewind iotas 292 &ret (); 293&function_end_B("_KeccakF1600"); 294 295&function_begin("KeccakF1600"); 296 &mov ("esi",&wparam(0)); 297 &mov ("ebp","esp"); 298 &sub ("esp",240); 299 &call (&label("pic_point")); 300 &set_label("pic_point"); 301 &blindpop("ebx"); 302 &lea ("ebx",&DWP(&label("iotas")."-".&label("pic_point"),"ebx")); 303 &and ("esp",-8); 304 &lea ("esi",&DWP(100,"esi")); # size optimization 305 &lea ("edi",&DWP(8*5+100,"esp")); # size optimization 306 307 &call ("_KeccakF1600"); 308 309 &mov ("esp","ebp"); 310 &emms (); 311&function_end("KeccakF1600"); 312 313&function_begin("SHA3_absorb"); 314 &mov ("esi",&wparam(0)); # A[][] 315 &mov ("eax",&wparam(1)); # inp 316 &mov ("ecx",&wparam(2)); # len 317 &mov ("edx",&wparam(3)); # bsz 318 &mov ("ebp","esp"); 319 &sub ("esp",240+8); 320 &call (&label("pic_point")); 321 &set_label("pic_point"); 322 &blindpop("ebx"); 323 &lea ("ebx",&DWP(&label("iotas")."-".&label("pic_point"),"ebx")); 324 &and ("esp",-8); 325 326 &mov ("edi","esi"); 327 &lea ("esi",&DWP(100,"esi")); # size optimization 328 &mov (&DWP(-4,"ebp"),"edx"); # save bsz 329 &jmp (&label("loop")); 330 331&set_label("loop",16); 332 &cmp ("ecx","edx"); # len < bsz? 333 &jc (&label("absorbed")); 334 335 &shr ("edx",3); # bsz /= 8 336&set_label("block"); 337 &movq ("mm0",&QWP(0,"eax")); 338 &lea ("eax",&DWP(8,"eax")); 339 &pxor ("mm0",&QWP(0,"edi")); 340 &lea ("edi",&DWP(8,"edi")); 341 &sub ("ecx",8); # len -= 8 342 &movq (&QWP(-8,"edi"),"mm0"); 343 &dec ("edx"); # bsz-- 344 &jnz (&label("block")); 345 346 &lea ("edi",&DWP(8*5+100,"esp")); # size optimization 347 &mov (&DWP(-8,"ebp"),"ecx"); # save len 348 &call ("_KeccakF1600"); 349 &mov ("ecx",&DWP(-8,"ebp")); # pull len 350 &mov ("edx",&DWP(-4,"ebp")); # pull bsz 351 &lea ("edi",&DWP(-100,"esi")); 352 &jmp (&label("loop")); 353 354&set_label("absorbed",16); 355 &mov ("eax","ecx"); # return value 356 &mov ("esp","ebp"); 357 &emms (); 358&function_end("SHA3_absorb"); 359 360&function_begin("SHA3_squeeze"); 361 &mov ("esi",&wparam(0)); # A[][] 362 &mov ("eax",&wparam(1)); # out 363 &mov ("ecx",&wparam(2)); # len 364 &mov ("edx",&wparam(3)); # bsz 365 &mov ("ebp","esp"); 366 &sub ("esp",240+8); 367 &call (&label("pic_point")); 368 &set_label("pic_point"); 369 &blindpop("ebx"); 370 &lea ("ebx",&DWP(&label("iotas")."-".&label("pic_point"),"ebx")); 371 &and ("esp",-8); 372 373 &shr ("edx",3); # bsz /= 8 374 &mov ("edi","esi"); 375 &lea ("esi",&DWP(100,"esi")); # size optimization 376 &mov (&DWP(-4,"ebp"),"edx"); # save bsz 377 &jmp (&label("loop")); 378 379&set_label("loop",16); 380 &cmp ("ecx",8); # len < 8? 381 &jc (&label("tail")); 382 383 &movq ("mm0",&QWP(0,"edi")); 384 &lea ("edi",&DWP(8,"edi")); 385 &movq (&QWP(0,"eax"),"mm0"); 386 &lea ("eax",&DWP(8,"eax")); 387 &sub ("ecx",8); # len -= 8 388 &jz (&label("done")); 389 390 &dec ("edx"); # bsz-- 391 &jnz (&label("loop")); 392 393 &lea ("edi",&DWP(8*5+100,"esp")); # size optimization 394 &mov (&DWP(-8,"ebp"),"ecx"); # save len 395 &call ("_KeccakF1600"); 396 &mov ("ecx",&DWP(-8,"ebp")); # pull len 397 &mov ("edx",&DWP(-4,"ebp")); # pull bsz 398 &lea ("edi",&DWP(-100,"esi")); 399 &jmp (&label("loop")); 400 401&set_label("tail",16); 402 &mov ("esi","edi"); 403 &mov ("edi","eax"); 404 &data_word("0xA4F39066"); # rep movsb 405 406&set_label("done"); 407 &mov ("esp","ebp"); 408 &emms (); 409&function_end("SHA3_squeeze"); 410 411&set_label("iotas",32); 412 &data_word(0x00000001,0x00000000); 413 &data_word(0x00008082,0x00000000); 414 &data_word(0x0000808a,0x80000000); 415 &data_word(0x80008000,0x80000000); 416 &data_word(0x0000808b,0x00000000); 417 &data_word(0x80000001,0x00000000); 418 &data_word(0x80008081,0x80000000); 419 &data_word(0x00008009,0x80000000); 420 &data_word(0x0000008a,0x00000000); 421 &data_word(0x00000088,0x00000000); 422 &data_word(0x80008009,0x00000000); 423 &data_word(0x8000000a,0x00000000); 424 &data_word(0x8000808b,0x00000000); 425 &data_word(0x0000008b,0x80000000); 426 &data_word(0x00008089,0x80000000); 427 &data_word(0x00008003,0x80000000); 428 &data_word(0x00008002,0x80000000); 429 &data_word(0x00000080,0x80000000); 430 &data_word(0x0000800a,0x00000000); 431 &data_word(0x8000000a,0x80000000); 432 &data_word(0x80008081,0x80000000); 433 &data_word(0x00008080,0x80000000); 434 &data_word(0x80000001,0x00000000); 435 &data_word(0x80008008,0x80000000); 436&asciz("Keccak-1600 absorb and squeeze for MMX, CRYPTOGAMS by <appro\@openssl.org>"); 437 438&asm_finish(); 439 440close STDOUT or die "error closing STDOUT: $!"; 441