{"thread":{"id":"20441","subject":"[PATCH 0/7] block-sha1: improved SHA1 hashing","startedAt":"2009-08-06T15:13:44Z","lastAt":"2009-08-08T23:36:45Z","messageCount":37,"participants":["Linus Torvalds","Artur Skawina","Bert Wesarg"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"119787","messageId":"alpine.LFD.2.01.0908060803140.3390@localhost.localdomain","threadId":"20441","inReplyTo":null,"subject":"[PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T15:13:44Z","receivedAt":"2009-08-06T15:13:44Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThe bulk of this is the patches I sent out yesterday, but there's a few \nadded tweaks from today there, and it's now one nice series instead of a \npatch followed by a \"Haa, I improved on it\" etc, so you can get the whole \nthing without actually having to hunt for the pieces.\n\nIt's a series of 7 patches:\n\n block-sha1: add new optimized C 'block-sha1' routines\n block-sha1: try to use rol/ror appropriately\n block-sha1: make the 'ntohl()' part of the first SHA1 loop\n block-sha1: re-use the temporary array as we calculate the SHA1\n block-sha1: macroize the rounds a bit further\n block-sha1: Use '(B&C)+(D&(B^C))' instead of '(B&C)|(D&(B|C))' in round 3\n block-sha1: get rid of redundant 'lenW' context\n\nwhere the thing is loosely based on the Mozilla SHA1 routines but by the \nend doesn't really resemble them all that much. The Mozilla ones suck \ndonkey d*ck in so many ways - unnecessary copies, idiotic byte-at-a-time \nbuild-up of the hash input etc.\n\nThe end result is pretty much equivalent in performance to the OpenSSL \nSHA1 code for me on x86-64. Getting rid of OpenSSL gets rid of another \ncouple of shared library loadings, and as a result my \"make -j64 test\" is \nnow a couple of seconds faster with this than with OpenSSL in my rather \nunscientific tests.\n\nThe code isn't very big:\n\n Makefile | 9 +++\n block-sha1/sha1.c | 158 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n block-sha1/sha1.h | 20 +++++++\n 3 files changed, 187 insertions(+), 0 deletions(-)\n create mode 100644 block-sha1/sha1.c\n create mode 100644 block-sha1/sha1.h\n\nand passes all my tests. It's really hard to not do the SHA1 right and \nstill pass any tests at all, so it should all be good.\n\nEnable them with BLK_SHA1=1.\n\n\t\tLinus\n"},{"id":"119788","messageId":"alpine.LFD.2.01.0908060814050.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908060803140.3390@localhost.localdomain","subject":"[PATCH 1/7] block-sha1: add new optimized C 'block-sha1' routines","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T15:15:39Z","receivedAt":"2009-08-06T15:15:39Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nFrom: Linus Torvalds \nDate: Wed, 5 Aug 2009 14:49:32 -0700\nSubject: [PATCH 1/7] block-sha1: add new optimized C 'block-sha1' routines\n\nBased ont he mozilla SHA1 routine, but doing the input data accesses a\nword at a time and with 'htonl()' instead of loading bytes and shifting.\n\nIt requires an architecture that is ok with unaligned 32-bit loads and a\nfast htonl().\n\nSigned-off-by: Linus Torvalds \n---\n\nSide note: we can get rid of the \"arch must support unaligned loads\" \nrequirement later on by telling the compiler which ones _can_ be \nunaligned. So the limitations aren't all that fundamental, really.\n\n Makefile | 9 +++\n block-sha1/sha1.c | 145 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n block-sha1/sha1.h | 21 ++++++++\n 3 files changed, 175 insertions(+), 0 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex d7669b1..f12024c 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -84,6 +84,10 @@ all::\n # specify your own (or DarwinPort's) include directories and\n # library directories by defining CFLAGS and LDFLAGS appropriately.\n #\n+# Define BLK_SHA1 environment variable if you want the C version\n+# of the SHA1 that assumes you can do unaligned 32-bit loads and\n+# have a fast htonl() function.\n+#\n # Define PPC_SHA1 environment variable when running make to make use of\n # a bundled SHA1 routine optimized for PowerPC.\n #\n@@ -1166,6 +1170,10 @@ ifdef NO_DEFLATE_BOUND\n \tBASIC_CFLAGS += -DNO_DEFLATE_BOUND\n endif\n \n+ifdef BLK_SHA1\n+\tSHA1_HEADER = \"block-sha1/sha1.h\"\n+\tLIB_OBJS += block-sha1/sha1.o\n+else\n ifdef PPC_SHA1\n \tSHA1_HEADER = \"ppc/sha1.h\"\n \tLIB_OBJS += ppc/sha1.o ppc/sha1ppc.o\n@@ -1183,6 +1191,7 @@ else\n endif\n endif\n endif\n+endif\n ifdef NO_PERL_MAKEMAKER\n \texport NO_PERL_MAKEMAKER\n endif\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nnew file mode 100644\nindex 0000000..eef32f7\n--- /dev/null\n+++ b/block-sha1/sha1.c\n@@ -0,0 +1,145 @@\n+/*\n+ * Based on the Mozilla SHA1 (see mozilla-sha1/sha1.c),\n+ * optimized to do word accesses rather than byte accesses,\n+ * and to avoid unnecessary copies into the context array.\n+ */\n+\n+#include \n+#include \n+\n+#include \"sha1.h\"\n+\n+/* Hash one 64-byte block of data */\n+static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data);\n+\n+void blk_SHA1_Init(blk_SHA_CTX *ctx)\n+{\n+\tctx->lenW = 0;\n+\tctx->size = 0;\n+\n+\t/* Initialize H with the magic constants (see FIPS180 for constants)\n+\t */\n+\tctx->H[0] = 0x67452301;\n+\tctx->H[1] = 0xefcdab89;\n+\tctx->H[2] = 0x98badcfe;\n+\tctx->H[3] = 0x10325476;\n+\tctx->H[4] = 0xc3d2e1f0;\n+}\n+\n+\n+void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *data, unsigned long len)\n+{\n+\tint lenW = ctx->lenW;\n+\n+\tctx->size += (unsigned long long) len << 3;\n+\n+\t/* Read the data into W and process blocks as they get full\n+\t */\n+\tif (lenW) {\n+\t\tint left = 64 - lenW;\n+\t\tif (len < left)\n+\t\t\tleft = len;\n+\t\tmemcpy(lenW + (char *)ctx->W, data, left);\n+\t\tlenW = (lenW + left) & 63;\n+\t\tlen -= left;\n+\t\tdata += left;\n+\t\tctx->lenW = lenW;\n+\t\tif (lenW)\n+\t\t\treturn;\n+\t\tblk_SHA1Block(ctx, ctx->W);\n+\t}\n+\twhile (len >= 64) {\n+\t\tblk_SHA1Block(ctx, data);\n+\t\tdata += 64;\n+\t\tlen -= 64;\n+\t}\n+\tif (len) {\n+\t\tmemcpy(ctx->W, data, len);\n+\t\tctx->lenW = len;\n+\t}\n+}\n+\n+\n+void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n+{\n+\tstatic const unsigned char pad[64] = { 0x80 };\n+\tunsigned int padlen[2];\n+\tint i;\n+\n+\t/* Pad with a binary 1 (ie 0x80), then zeroes, then length\n+\t */\n+\tpadlen[0] = htonl(ctx->size >> 32);\n+\tpadlen[1] = htonl(ctx->size);\n+\n+\tblk_SHA1_Update(ctx, pad, 1+ (63 & (55 - ctx->lenW)));\n+\tblk_SHA1_Update(ctx, padlen, 8);\n+\n+\t/* Output hash\n+\t */\n+\tfor (i = 0; i < 5; i++)\n+\t\t((unsigned int *)hashout)[i] = htonl(ctx->H[i]);\n+}\n+\n+#define SHA_ROT(X,n) (((X) << (n)) | ((X) >> (32-(n))))\n+\n+static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n+{\n+\tint t;\n+\tunsigned int A,B,C,D,E,TEMP;\n+\tunsigned int W[80];\n+\n+\tfor (t = 0; t < 16; t++)\n+\t\tW[t] = htonl(data[t]);\n+\n+\t/* Unroll it? */\n+\tfor (t = 16; t <= 79; t++)\n+\t\tW[t] = SHA_ROT(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16], 1);\n+\n+\tA = ctx->H[0];\n+\tB = ctx->H[1];\n+\tC = ctx->H[2];\n+\tD = ctx->H[3];\n+\tE = ctx->H[4];\n+\n+#define T_0_19(t) \\\n+\tTEMP = SHA_ROT(A,5) + (((C^D)&B)^D) + E + W[t] + 0x5a827999; \\\n+\tE = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;\n+\n+\tT_0_19( 0); T_0_19( 1); T_0_19( 2); T_0_19( 3); T_0_19( 4);\n+\tT_0_19( 5); T_0_19( 6); T_0_19( 7); T_0_19( 8); T_0_19( 9);\n+\tT_0_19(10); T_0_19(11); T_0_19(12); T_0_19(13); T_0_19(14);\n+\tT_0_19(15); T_0_19(16); T_0_19(17); T_0_19(18); T_0_19(19);\n+\n+#define T_20_39(t) \\\n+\tTEMP = SHA_ROT(A,5) + (B^C^D) + E + W[t] + 0x6ed9eba1; \\\n+\tE = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;\n+\n+\tT_20_39(20); T_20_39(21); T_20_39(22); T_20_39(23); T_20_39(24);\n+\tT_20_39(25); T_20_39(26); T_20_39(27); T_20_39(28); T_20_39(29);\n+\tT_20_39(30); T_20_39(31); T_20_39(32); T_20_39(33); T_20_39(34);\n+\tT_20_39(35); T_20_39(36); T_20_39(37); T_20_39(38); T_20_39(39);\n+\n+#define T_40_59(t) \\\n+\tTEMP = SHA_ROT(A,5) + ((B&C)|(D&(B|C))) + E + W[t] + 0x8f1bbcdc; \\\n+\tE = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;\n+\n+\tT_40_59(40); T_40_59(41); T_40_59(42); T_40_59(43); T_40_59(44);\n+\tT_40_59(45); T_40_59(46); T_40_59(47); T_40_59(48); T_40_59(49);\n+\tT_40_59(50); T_40_59(51); T_40_59(52); T_40_59(53); T_40_59(54);\n+\tT_40_59(55); T_40_59(56); T_40_59(57); T_40_59(58); T_40_59(59);\n+\n+#define T_60_79(t) \\\n+\tTEMP = SHA_ROT(A,5) + (B^C^D) + E + W[t] + 0xca62c1d6; \\\n+\tE = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;\n+\n+\tT_60_79(60); T_60_79(61); T_60_79(62); T_60_79(63); T_60_79(64);\n+\tT_60_79(65); T_60_79(66); T_60_79(67); T_60_79(68); T_60_79(69);\n+\tT_60_79(70); T_60_79(71); T_60_79(72); T_60_79(73); T_60_79(74);\n+\tT_60_79(75); T_60_79(76); T_60_79(77); T_60_79(78); T_60_79(79);\n+\n+\tctx->H[0] += A;\n+\tctx->H[1] += B;\n+\tctx->H[2] += C;\n+\tctx->H[3] += D;\n+\tctx->H[4] += E;\n+}\ndiff --git a/block-sha1/sha1.h b/block-sha1/sha1.h\nnew file mode 100644\nindex 0000000..7be2d93\n--- /dev/null\n+++ b/block-sha1/sha1.h\n@@ -0,0 +1,21 @@\n+/*\n+ * Based on the Mozilla SHA1 (see mozilla-sha1/sha1.h),\n+ * optimized to do word accesses rather than byte accesses,\n+ * and to avoid unnecessary copies into the context array.\n+ */\n+\n+typedef struct {\n+\tunsigned int H[5];\n+\tunsigned int W[16];\n+\tint lenW;\n+\tunsigned long long size;\n+} blk_SHA_CTX;\n+\n+void blk_SHA1_Init(blk_SHA_CTX *ctx);\n+void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *dataIn, unsigned long len);\n+void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx);\n+\n+#define git_SHA_CTX\tblk_SHA_CTX\n+#define git_SHA1_Init\tblk_SHA1_Init\n+#define git_SHA1_Update\tblk_SHA1_Update\n+#define git_SHA1_Final\tblk_SHA1_Final\n-- \n1.6.4.31.g154b2.dirty\n"},{"id":"119789","messageId":"alpine.LFD.2.01.0908060815430.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908060814050.3390@localhost.localdomain","subject":"[PATCH 2/7] block-sha1: try to use rol/ror appropriately","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T15:16:52Z","receivedAt":"2009-08-06T15:16:52Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nFrom: Linus Torvalds \nDate: Wed, 5 Aug 2009 19:42:15 -0700\nSubject: [PATCH 2/7] block-sha1: try to use rol/ror appropriately\n\nUse the one with the smaller constant. It _can_ generate slightly\nsmaller code (a constant of 1 is special), but perhaps more importantly\nit's possibly faster on any uarch that does a rotate with a loop.\n\nSigned-off-by: Linus Torvalds \n---\n\nOk, this is the hackiest of the bunch. I considered dropping it. But I do \nsuspect we want something like this, even if we might end up massaging the \nasm for different compilers etc.\n\n block-sha1/sha1.c | 32 ++++++++++++++++++++++----------\n 1 files changed, 22 insertions(+), 10 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex eef32f7..a45a3de 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -80,7 +80,19 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n \t\t((unsigned int *)hashout)[i] = htonl(ctx->H[i]);\n }\n \n-#define SHA_ROT(X,n) (((X) << (n)) | ((X) >> (32-(n))))\n+#if defined(__i386__) || defined(__x86_64__)\n+\n+#define SHA_ASM(op, x, n) ({ unsigned int __res; asm(op \" %1,%0\":\"=r\" (__res):\"i\" (n), \"0\" (x)); __res; })\n+#define SHA_ROL(x,n)\tSHA_ASM(\"rol\", x, n)\n+#define SHA_ROR(x,n)\tSHA_ASM(\"ror\", x, n)\n+\n+#else\n+\n+#define SHA_ROT(X,n)\t(((X) << (l)) | ((X) >> (r)))\n+#define SHA_ROL(X,n)\tSHA_ROT(X,n,32-(n))\n+#define SHA_ROR(X,n)\tSHA_ROT(X,32-(n),n)\n+\n+#endif\n \n static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n {\n@@ -93,7 +105,7 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \n \t/* Unroll it? */\n \tfor (t = 16; t <= 79; t++)\n-\t\tW[t] = SHA_ROT(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16], 1);\n+\t\tW[t] = SHA_ROL(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16], 1);\n \n \tA = ctx->H[0];\n \tB = ctx->H[1];\n@@ -102,8 +114,8 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \tE = ctx->H[4];\n \n #define T_0_19(t) \\\n-\tTEMP = SHA_ROT(A,5) + (((C^D)&B)^D) + E + W[t] + 0x5a827999; \\\n-\tE = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;\n+\tTEMP = SHA_ROL(A,5) + (((C^D)&B)^D) + E + W[t] + 0x5a827999; \\\n+\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n \n \tT_0_19( 0); T_0_19( 1); T_0_19( 2); T_0_19( 3); T_0_19( 4);\n \tT_0_19( 5); T_0_19( 6); T_0_19( 7); T_0_19( 8); T_0_19( 9);\n@@ -111,8 +123,8 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \tT_0_19(15); T_0_19(16); T_0_19(17); T_0_19(18); T_0_19(19);\n \n #define T_20_39(t) \\\n-\tTEMP = SHA_ROT(A,5) + (B^C^D) + E + W[t] + 0x6ed9eba1; \\\n-\tE = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;\n+\tTEMP = SHA_ROL(A,5) + (B^C^D) + E + W[t] + 0x6ed9eba1; \\\n+\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n \n \tT_20_39(20); T_20_39(21); T_20_39(22); T_20_39(23); T_20_39(24);\n \tT_20_39(25); T_20_39(26); T_20_39(27); T_20_39(28); T_20_39(29);\n@@ -120,8 +132,8 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \tT_20_39(35); T_20_39(36); T_20_39(37); T_20_39(38); T_20_39(39);\n \n #define T_40_59(t) \\\n-\tTEMP = SHA_ROT(A,5) + ((B&C)|(D&(B|C))) + E + W[t] + 0x8f1bbcdc; \\\n-\tE = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;\n+\tTEMP = SHA_ROL(A,5) + ((B&C)|(D&(B|C))) + E + W[t] + 0x8f1bbcdc; \\\n+\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n \n \tT_40_59(40); T_40_59(41); T_40_59(42); T_40_59(43); T_40_59(44);\n \tT_40_59(45); T_40_59(46); T_40_59(47); T_40_59(48); T_40_59(49);\n@@ -129,8 +141,8 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \tT_40_59(55); T_40_59(56); T_40_59(57); T_40_59(58); T_40_59(59);\n \n #define T_60_79(t) \\\n-\tTEMP = SHA_ROT(A,5) + (B^C^D) + E + W[t] + 0xca62c1d6; \\\n-\tE = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;\n+\tTEMP = SHA_ROL(A,5) + (B^C^D) + E + W[t] + 0xca62c1d6; \\\n+\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n \n \tT_60_79(60); T_60_79(61); T_60_79(62); T_60_79(63); T_60_79(64);\n \tT_60_79(65); T_60_79(66); T_60_79(67); T_60_79(68); T_60_79(69);\n-- \n1.6.4.31.g154b2.dirty\n"},{"id":"119790","messageId":"alpine.LFD.2.01.0908060816550.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908060815430.3390@localhost.localdomain","subject":"[PATCH 3/7] block-sha1: make the 'ntohl()' part of the first SHA1 loop","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T15:18:18Z","receivedAt":"2009-08-06T15:18:18Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds \nDate: Wed, 5 Aug 2009 20:28:07 -0700\nSubject: [PATCH 3/7] block-sha1: make the 'ntohl()' part of the first SHA1 loop\n\nThis helps a teeny bit. But what I -really- want to do is to avoid the\nwhole 80-array loop, and do the xor updates as I go along..\n\nSigned-off-by: Linus Torvalds \n---\n\nThis is a pretty trivial one, but it was the first stage to getting rid of \nthe annoying 80-word array that not only wastes precious L1 cache, but \nthat loop to initialize it was a noticeable cost.\n\n block-sha1/sha1.c | 28 ++++++++++++++++------------\n 1 files changed, 16 insertions(+), 12 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex a45a3de..39a5bbb 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -100,27 +100,31 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \tunsigned int A,B,C,D,E,TEMP;\n \tunsigned int W[80];\n \n-\tfor (t = 0; t < 16; t++)\n-\t\tW[t] = htonl(data[t]);\n-\n-\t/* Unroll it? */\n-\tfor (t = 16; t <= 79; t++)\n-\t\tW[t] = SHA_ROL(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16], 1);\n-\n \tA = ctx->H[0];\n \tB = ctx->H[1];\n \tC = ctx->H[2];\n \tD = ctx->H[3];\n \tE = ctx->H[4];\n \n-#define T_0_19(t) \\\n+#define T_0_15(t) \\\n+\tTEMP = htonl(data[t]); W[t] = TEMP; \\\n+\tTEMP += SHA_ROL(A,5) + (((C^D)&B)^D) + E + 0x5a827999; \\\n+\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP; \\\n+\n+\tT_0_15( 0); T_0_15( 1); T_0_15( 2); T_0_15( 3); T_0_15( 4);\n+\tT_0_15( 5); T_0_15( 6); T_0_15( 7); T_0_15( 8); T_0_15( 9);\n+\tT_0_15(10); T_0_15(11); T_0_15(12); T_0_15(13); T_0_15(14);\n+\tT_0_15(15);\n+\n+\t/* Unroll it? */\n+\tfor (t = 16; t <= 79; t++)\n+\t\tW[t] = SHA_ROL(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16], 1);\n+\n+#define T_16_19(t) \\\n \tTEMP = SHA_ROL(A,5) + (((C^D)&B)^D) + E + W[t] + 0x5a827999; \\\n \tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n \n-\tT_0_19( 0); T_0_19( 1); T_0_19( 2); T_0_19( 3); T_0_19( 4);\n-\tT_0_19( 5); T_0_19( 6); T_0_19( 7); T_0_19( 8); T_0_19( 9);\n-\tT_0_19(10); T_0_19(11); T_0_19(12); T_0_19(13); T_0_19(14);\n-\tT_0_19(15); T_0_19(16); T_0_19(17); T_0_19(18); T_0_19(19);\n+\tT_16_19(16); T_16_19(17); T_16_19(18); T_16_19(19);\n \n #define T_20_39(t) \\\n \tTEMP = SHA_ROL(A,5) + (B^C^D) + E + W[t] + 0x6ed9eba1; \\\n-- \n1.6.4.31.g154b2.dirty\n"},{"id":"119791","messageId":"alpine.LFD.2.01.0908060818220.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908060816550.3390@localhost.localdomain","subject":"[PATCH 4/7] block-sha1: re-use the temporary array as we calculate the SHA1","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T15:20:08Z","receivedAt":"2009-08-06T15:20:08Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds \nDate: Wed, 5 Aug 2009 20:49:41 -0700\nSubject: [PATCH 4/7] block-sha1: re-use the temporary array as we calculate the SHA1\n\nThe mozilla-SHA1 code did this 80-word array for the 80 iterations. But\nthe SHA1 state is really just 512 bits, and you can actually keep it in\na kind of \"circular queue\" of just 16 words instead.\n\nThis requires us to do the xor updates as we go along (rather than as a\npre-phase), but that's really what we want to do anyway.\n\nThis gets me really close to the OpenSSL performance on my Nehalem.\nLook ma, all C code (ok, there's the rol/ror hack, but that one doesn't\nstrictly even matter on my Nehalem, it's just a local optimization).\n\nSigned-off-by: Linus Torvalds \n---\n\nThis gets rid of the annoying pre-initialization and its need for that \nextra space. We can dynamically iterate over a 512-bit circular buffer \ninstead.\n\n block-sha1/sha1.c | 28 ++++++++++++++++------------\n 1 files changed, 16 insertions(+), 12 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex 39a5bbb..80193d4 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -96,9 +96,8 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n \n static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n {\n-\tint t;\n \tunsigned int A,B,C,D,E,TEMP;\n-\tunsigned int W[80];\n+\tunsigned int array[16];\n \n \tA = ctx->H[0];\n \tB = ctx->H[1];\n@@ -107,8 +106,8 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \tE = ctx->H[4];\n \n #define T_0_15(t) \\\n-\tTEMP = htonl(data[t]); W[t] = TEMP; \\\n-\tTEMP += SHA_ROL(A,5) + (((C^D)&B)^D) + E + 0x5a827999; \\\n+\tTEMP = htonl(data[t]); array[t] = TEMP; \\\n+\tTEMP += SHA_ROL(A,5) + (((C^D)&B)^D) + E + 0x5a827999; \\\n \tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP; \\\n \n \tT_0_15( 0); T_0_15( 1); T_0_15( 2); T_0_15( 3); T_0_15( 4);\n@@ -116,18 +115,21 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \tT_0_15(10); T_0_15(11); T_0_15(12); T_0_15(13); T_0_15(14);\n \tT_0_15(15);\n \n-\t/* Unroll it? */\n-\tfor (t = 16; t <= 79; t++)\n-\t\tW[t] = SHA_ROL(W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16], 1);\n+/* This \"rolls\" over the 512-bit array */\n+#define W(x) (array[(x)&15])\n+#define SHA_XOR(t) \\\n+\tTEMP = SHA_ROL(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1); W(t) = TEMP;\n \n #define T_16_19(t) \\\n-\tTEMP = SHA_ROL(A,5) + (((C^D)&B)^D) + E + W[t] + 0x5a827999; \\\n-\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n+\tSHA_XOR(t); \\\n+\tTEMP += SHA_ROL(A,5) + (((C^D)&B)^D) + E + 0x5a827999; \\\n+\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP; \\\n \n \tT_16_19(16); T_16_19(17); T_16_19(18); T_16_19(19);\n \n #define T_20_39(t) \\\n-\tTEMP = SHA_ROL(A,5) + (B^C^D) + E + W[t] + 0x6ed9eba1; \\\n+\tSHA_XOR(t); \\\n+\tTEMP += SHA_ROL(A,5) + (B^C^D) + E + 0x6ed9eba1; \\\n \tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n \n \tT_20_39(20); T_20_39(21); T_20_39(22); T_20_39(23); T_20_39(24);\n@@ -136,7 +138,8 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \tT_20_39(35); T_20_39(36); T_20_39(37); T_20_39(38); T_20_39(39);\n \n #define T_40_59(t) \\\n-\tTEMP = SHA_ROL(A,5) + ((B&C)|(D&(B|C))) + E + W[t] + 0x8f1bbcdc; \\\n+\tSHA_XOR(t); \\\n+\tTEMP += SHA_ROL(A,5) + ((B&C)|(D&(B|C))) + E + 0x8f1bbcdc; \\\n \tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n \n \tT_40_59(40); T_40_59(41); T_40_59(42); T_40_59(43); T_40_59(44);\n@@ -145,7 +148,8 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \tT_40_59(55); T_40_59(56); T_40_59(57); T_40_59(58); T_40_59(59);\n \n #define T_60_79(t) \\\n-\tTEMP = SHA_ROL(A,5) + (B^C^D) + E + W[t] + 0xca62c1d6; \\\n+\tSHA_XOR(t); \\\n+\tTEMP += SHA_ROL(A,5) + (B^C^D) + E + 0xca62c1d6; \\\n \tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n \n \tT_60_79(60); T_60_79(61); T_60_79(62); T_60_79(63); T_60_79(64);\n-- \n1.6.4.31.g154b2.dirty\n"},{"id":"119792","messageId":"alpine.LFD.2.01.0908060820110.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908060818220.3390@localhost.localdomain","subject":"[PATCH 5/7] block-sha1: macroize the rounds a bit further","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T15:22:33Z","receivedAt":"2009-08-06T15:22:33Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds \nDate: Thu, 6 Aug 2009 07:20:54 -0700\nSubject: [PATCH 5/7] block-sha1: macroize the rounds a bit further\n\nAvoid repeating the shared parts of the different rounds by adding a\nmacro layer or two. It was already more cpp than C.\n\nSigned-off-by: Linus Torvalds \n---\n\nThis makes things denser, and puts all the core rules in one place. That \nfirst hunk really contains just about all of the important parts of SHA1. \nThe rest is just fluff and the necessary expansions etc.\n\n block-sha1/sha1.c | 56 ++++++++++++++++++++++++----------------------------\n 1 files changed, 26 insertions(+), 30 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex 80193d4..4837d58 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -94,6 +94,27 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n \n #endif\n \n+/* This \"rolls\" over the 512-bit array */\n+#define W(x) (array[(x)&15])\n+\n+/*\n+ * Where do we get the source from? The first 16 iterations get it from\n+ * the input data, the next mix it from the 512-bit array.\n+ */\n+#define SHA_SRC(t) htonl(data[t])\n+#define SHA_MIX(t) SHA_ROL(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1)\n+\n+#define SHA_ROUND(t, input, fn, constant) \\\n+\tTEMP = input(t); W(t) = TEMP; \\\n+\tTEMP += SHA_ROL(A,5) + (fn) + E + (constant); \\\n+\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP\n+\n+#define T_0_15(t) SHA_ROUND(t, SHA_SRC, (((C^D)&B)^D) , 0x5a827999 )\n+#define T_16_19(t) SHA_ROUND(t, SHA_MIX, (((C^D)&B)^D) , 0x5a827999 )\n+#define T_20_39(t) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0x6ed9eba1 )\n+#define T_40_59(t) SHA_ROUND(t, SHA_MIX, ((B&C)|(D&(B|C))) , 0x8f1bbcdc )\n+#define T_60_79(t) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0xca62c1d6 )\n+\n static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n {\n \tunsigned int A,B,C,D,E,TEMP;\n@@ -105,53 +126,28 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \tD = ctx->H[3];\n \tE = ctx->H[4];\n \n-#define T_0_15(t) \\\n-\tTEMP = htonl(data[t]); array[t] = TEMP; \\\n-\tTEMP += SHA_ROL(A,5) + (((C^D)&B)^D) + E + 0x5a827999; \\\n-\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP; \\\n-\n+\t/* Round 1 - iterations 0-16 take their input from 'data' */\n \tT_0_15( 0); T_0_15( 1); T_0_15( 2); T_0_15( 3); T_0_15( 4);\n \tT_0_15( 5); T_0_15( 6); T_0_15( 7); T_0_15( 8); T_0_15( 9);\n \tT_0_15(10); T_0_15(11); T_0_15(12); T_0_15(13); T_0_15(14);\n \tT_0_15(15);\n \n-/* This \"rolls\" over the 512-bit array */\n-#define W(x) (array[(x)&15])\n-#define SHA_XOR(t) \\\n-\tTEMP = SHA_ROL(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1); W(t) = TEMP;\n-\n-#define T_16_19(t) \\\n-\tSHA_XOR(t); \\\n-\tTEMP += SHA_ROL(A,5) + (((C^D)&B)^D) + E + 0x5a827999; \\\n-\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP; \\\n-\n+\t/* Round 1 - tail. Input from 512-bit mixing array */\n \tT_16_19(16); T_16_19(17); T_16_19(18); T_16_19(19);\n \n-#define T_20_39(t) \\\n-\tSHA_XOR(t); \\\n-\tTEMP += SHA_ROL(A,5) + (B^C^D) + E + 0x6ed9eba1; \\\n-\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n-\n+\t/* Round 2 */\n \tT_20_39(20); T_20_39(21); T_20_39(22); T_20_39(23); T_20_39(24);\n \tT_20_39(25); T_20_39(26); T_20_39(27); T_20_39(28); T_20_39(29);\n \tT_20_39(30); T_20_39(31); T_20_39(32); T_20_39(33); T_20_39(34);\n \tT_20_39(35); T_20_39(36); T_20_39(37); T_20_39(38); T_20_39(39);\n \n-#define T_40_59(t) \\\n-\tSHA_XOR(t); \\\n-\tTEMP += SHA_ROL(A,5) + ((B&C)|(D&(B|C))) + E + 0x8f1bbcdc; \\\n-\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n-\n+\t/* Round 3 */\n \tT_40_59(40); T_40_59(41); T_40_59(42); T_40_59(43); T_40_59(44);\n \tT_40_59(45); T_40_59(46); T_40_59(47); T_40_59(48); T_40_59(49);\n \tT_40_59(50); T_40_59(51); T_40_59(52); T_40_59(53); T_40_59(54);\n \tT_40_59(55); T_40_59(56); T_40_59(57); T_40_59(58); T_40_59(59);\n \n-#define T_60_79(t) \\\n-\tSHA_XOR(t); \\\n-\tTEMP += SHA_ROL(A,5) + (B^C^D) + E + 0xca62c1d6; \\\n-\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP;\n-\n+\t/* Round 4 */\n \tT_60_79(60); T_60_79(61); T_60_79(62); T_60_79(63); T_60_79(64);\n \tT_60_79(65); T_60_79(66); T_60_79(67); T_60_79(68); T_60_79(69);\n \tT_60_79(70); T_60_79(71); T_60_79(72); T_60_79(73); T_60_79(74);\n-- \n1.6.4.31.g154b2.dirty\n"},{"id":"119793","messageId":"alpine.LFD.2.01.0908060822390.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908060820110.3390@localhost.localdomain","subject":"[PATCH 6/7] block-sha1: Use '(B&C)+(D&(B^C))' instead of '(B&C)|(D&(B|C))' in round 3","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T15:24:07Z","receivedAt":"2009-08-06T15:24:07Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds \nDate: Thu, 6 Aug 2009 07:27:57 -0700\nSubject: [PATCH 6/7] block-sha1: Use '(B&C)+(D&(B^C))' instead of '(B&C)|(D&(B|C))' in round 3\n\nIt's an equivalent expression, but the '+' gives us some freedom in\ninstruction selection (for example, we can use 'lea' rather than 'add'),\nand associates with the other additions around it to give some minor\nscheduling freedom.\n\nSuggested-by: linux@horizon.com\nSigned-off-by: Linus Torvalds \n---\n\nA small micro-optimization. It may not matter hugely, but it's definitely \nthe right thing to do. And with the new macroized thing, you can see \nclearly what part of the SHA1 rounds it affects, and how.\n\n block-sha1/sha1.c | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex 4837d58..9a060a6 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -112,7 +112,7 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n #define T_0_15(t) SHA_ROUND(t, SHA_SRC, (((C^D)&B)^D) , 0x5a827999 )\n #define T_16_19(t) SHA_ROUND(t, SHA_MIX, (((C^D)&B)^D) , 0x5a827999 )\n #define T_20_39(t) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0x6ed9eba1 )\n-#define T_40_59(t) SHA_ROUND(t, SHA_MIX, ((B&C)|(D&(B|C))) , 0x8f1bbcdc )\n+#define T_40_59(t) SHA_ROUND(t, SHA_MIX, ((B&C)+(D&(B^C))) , 0x8f1bbcdc )\n #define T_60_79(t) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0xca62c1d6 )\n \n static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n-- \n1.6.4.31.g154b2.dirty\n"},{"id":"119794","messageId":"alpine.LFD.2.01.0908060824090.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908060822390.3390@localhost.localdomain","subject":"[PATCH 7/7] block-sha1: get rid of redundant 'lenW' context","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T15:25:45Z","receivedAt":"2009-08-06T15:25:45Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds \nDate: Thu, 6 Aug 2009 07:45:46 -0700\nSubject: [PATCH 7/7] block-sha1: get rid of redundant 'lenW' context\n\n.. and simplify the ctx->size logic.\n\nWe now count the size in bytes, which means that 'lenW' was always just\nthe low 6 bits of the total size, so we don't carry it around separately\nany more. And we do the 'size in bits' shift at the end.\n\nSuggested by Nicolas Pitre and linux@horizon.com.\n\nSigned-off-by: Linus Torvalds \n---\n\nSome final cleanup. Based on two separate discussions yesterday. Trivial \nand doesn't make any difference that I can tell, but definitely the right \nthing to do.\n\n block-sha1/sha1.c | 17 +++++++----------\n block-sha1/sha1.h | 1 -\n 2 files changed, 7 insertions(+), 11 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex 9a060a6..78dcb0c 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -14,7 +14,6 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data);\n \n void blk_SHA1_Init(blk_SHA_CTX *ctx)\n {\n-\tctx->lenW = 0;\n \tctx->size = 0;\n \n \t/* Initialize H with the magic constants (see FIPS180 for constants)\n@@ -29,9 +28,9 @@ void blk_SHA1_Init(blk_SHA_CTX *ctx)\n \n void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *data, unsigned long len)\n {\n-\tint lenW = ctx->lenW;\n+\tint lenW = ctx->size & 63;\n \n-\tctx->size += (unsigned long long) len << 3;\n+\tctx->size += len;\n \n \t/* Read the data into W and process blocks as they get full\n \t */\n@@ -43,7 +42,6 @@ void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *data, unsigned long len)\n \t\tlenW = (lenW + left) & 63;\n \t\tlen -= left;\n \t\tdata += left;\n-\t\tctx->lenW = lenW;\n \t\tif (lenW)\n \t\t\treturn;\n \t\tblk_SHA1Block(ctx, ctx->W);\n@@ -53,10 +51,8 @@ void blk_SHA1_Update(blk_SHA_CTX *ctx, const void *data, unsigned long len)\n \t\tdata += 64;\n \t\tlen -= 64;\n \t}\n-\tif (len) {\n+\tif (len)\n \t\tmemcpy(ctx->W, data, len);\n-\t\tctx->lenW = len;\n-\t}\n }\n \n \n@@ -68,10 +64,11 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n \n \t/* Pad with a binary 1 (ie 0x80), then zeroes, then length\n \t */\n-\tpadlen[0] = htonl(ctx->size >> 32);\n-\tpadlen[1] = htonl(ctx->size);\n+\tpadlen[0] = htonl(ctx->size >> 29);\n+\tpadlen[1] = htonl(ctx->size << 3);\n \n-\tblk_SHA1_Update(ctx, pad, 1+ (63 & (55 - ctx->lenW)));\n+\ti = ctx->size & 63;\n+\tblk_SHA1_Update(ctx, pad, 1+ (63 & (55 - i)));\n \tblk_SHA1_Update(ctx, padlen, 8);\n \n \t/* Output hash\ndiff --git a/block-sha1/sha1.h b/block-sha1/sha1.h\nindex 7be2d93..c1ae74d 100644\n--- a/block-sha1/sha1.h\n+++ b/block-sha1/sha1.h\n@@ -7,7 +7,6 @@\n typedef struct {\n \tunsigned int H[5];\n \tunsigned int W[16];\n-\tint lenW;\n \tunsigned long long size;\n } blk_SHA_CTX;\n \n-- \n1.6.4.31.g154b2.dirty\n"},{"id":"119805","messageId":"4A7B1166.8020507@gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908060803140.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-06T17:22:46Z","receivedAt":"2009-08-06T17:22:46Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> where the thing is loosely based on the Mozilla SHA1 routines but by the \n> end doesn't really resemble them all that much. The Mozilla ones suck \n> donkey d*ck in so many ways - unnecessary copies, idiotic byte-at-a-time \n> build-up of the hash input etc.\n> \n> The end result is pretty much equivalent in performance to the OpenSSL \n> SHA1 code for me on x86-64. Getting rid of OpenSSL gets rid of another \n\nFor those curious just how close the C version is to the various\nasm and C implementations, the q&d microbenchmark is at \nhttp://www.src.multimo.pl/YDpqIo7Li27O0L0h/sha1bench.tar.gz\n\nIn short: 88% of openssl speed on P3, 42% on P4, 66% on Atom.\n\nartur\n"},{"id":"119809","messageId":"alpine.LFD.2.01.0908061052320.3390@localhost.localdomain","threadId":"20441","inReplyTo":"4A7B1166.8020507@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T18:09:25Z","receivedAt":"2009-08-06T18:09:25Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 6 Aug 2009, Artur Skawina wrote:\n> \n> For those curious just how close the C version is to the various\n> asm and C implementations, the q&d microbenchmark is at \n> http://www.src.multimo.pl/YDpqIo7Li27O0L0h/sha1bench.tar.gz\n\nHmm. That thing doesn't work at all on x86-64. Even apart from the asm \nsources, your timing thing does soem really odd things (why do you do that \nodd \"iret\" in GETCYCLES and GETTIME?). You're better off using \nlfence/mfence/cpuid, and I think you could make it work on 64-bit that \nway too.\n\nI just hacked it away for testing.\n\n> In short: 88% of openssl speed on P3, 42% on P4, 66% on Atom.\n\nI'll use this to see if I can improve the 32-bit case.\n\nOn Nehalem, with your benchmark, I get:\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 5.122 119.2\n\t# New hash result: d829b9e028e64840094ab6702f9acdf11bec3937\n\trfc3174 5.153 118.5\n\tlinus 2.092 291.8\n\tlinusas 2.056 296.8\n\tlinusas2 1.909 319.8\n\tmozilla 5.139 118.8\n\tmozillaas 5.775 105.7\n\topenssl 1.627 375.1\n\tspelvin 1.678 363.7\n\tspelvina 1.603 380.8\n\tnettle 1.592 383.4\n\nAnd with the hacked version to get some 64-bit numbers:\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 3.992 152.9\n\t# New hash result: b78fd74c0033a4dfe0ededccb85ab00cb56880ab\n\trfc3174 3.991 152.9\n\tlinus 1.54 396.3\n\tlinusas 1.533 398.1\n\tlinusas2 1.603 380.9\n\tmozilla 4.352 140.3\n\tmozillaas 4.227 144.4\n\nso as you can see, your improvements in 32-bit mode are actually \nde-provements in 64-bit mode (ok, your first one seems to be a tiny \nimprovement, but I think it's in the noise).\n\nBut you're right, I need to try to improve the 32-bit case.\n\n\t\t\tLinus\n"},{"id":"119810","messageId":"36ca99e90908061125w71c0294wd4c896dc5fb812fc@mail.gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908060815430.3390@localhost.localdomain","subject":"Re: [PATCH 2/7] block-sha1: try to use rol/ror appropriately","fromName":"Bert Wesarg","fromEmail":"bert.wesarg@googlemail.com","sentAt":"2009-08-06T18:25:35Z","receivedAt":"2009-08-06T18:25:35Z","isPatch":true,"sender":{"key":"bert.wesarg@googlemail.com","avatar":"https://avatars.githubusercontent.com/u/111934?v=4"},"body":"Hi,\n\nOn Thu, Aug 6, 2009 at 17:16, Linus\nTorvalds wrote:\n> diff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\n> index eef32f7..a45a3de 100644\n> --- a/block-sha1/sha1.c\n> +++ b/block-sha1/sha1.c\n> @@ -80,7 +80,19 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n>                ((unsigned int *)hashout)[i] = htonl(ctx->H[i]);\n>  }\n>\n> -#define SHA_ROT(X,n) (((X) << (n)) | ((X) >> (32-(n))))\n> +#if defined(__i386__) || defined(__x86_64__)\n> +\n> +#define SHA_ASM(op, x, n) ({ unsigned int __res; asm(op \" %1,%0\":\"=r\" (__res):\"i\" (n), \"0\" (x)); __res; })\n> +#define SHA_ROL(x,n)   SHA_ASM(\"rol\", x, n)\n> +#define SHA_ROR(x,n)   SHA_ASM(\"ror\", x, n)\n> +\n> +#else\n> +\n> +#define SHA_ROT(X,n)   (((X) << (l)) | ((X) >> (r)))\nI suspect, this should be:\n#define SHA_ROT(X,l.r) (((X) << (l)) | ((X) >> (r)))\n\n> +#define SHA_ROL(X,n)   SHA_ROT(X,n,32-(n))\n> +#define SHA_ROR(X,n)   SHA_ROT(X,32-(n),n)\n> +\n> +#endif\n>\n>  static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n>  {\n\nBert\n"},{"id":"119816","messageId":"4A7B2A88.2040602@gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061052320.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-06T19:10:00Z","receivedAt":"2009-08-06T19:10:00Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> On Thu, 6 Aug 2009, Artur Skawina wrote:\n>> For those curious just how close the C version is to the various\n>> asm and C implementations, the q&d microbenchmark is at \n>> http://www.src.multimo.pl/YDpqIo7Li27O0L0h/sha1bench.tar.gz\n> \n> Hmm. That thing doesn't work at all on x86-64. Even apart from the asm \n> sources, your timing thing does soem really odd things (why do you do that \n> odd \"iret\" in GETCYCLES and GETTIME?). You're better off using \n> lfence/mfence/cpuid, and I think you could make it work on 64-bit that \n> way too.\n\nyes, it's 32-bit only, i should have mentioned that. The timing\ncode was written more than a decade ago, it really works on p2,\nhaven't updated it, it's all just c&p'ed ever since. All of it\ncan be safely disabled; on p2 you could account for every cycle,\nnowadays gettimeofday is more than enough.\n\n> I just hacked it away for testing.\n> \n>> In short: 88% of openssl speed on P3, 42% on P4, 66% on Atom.\n> \n> I'll use this to see if I can improve the 32-bit case.\n> \n> On Nehalem, with your benchmark, I get:\n> \n> \t# TIME[s] SPEED[MB/s]\n> \trfc3174 5.122 119.2\n> \t# New hash result: d829b9e028e64840094ab6702f9acdf11bec3937\n> \trfc3174 5.153 118.5\n> \tlinus 2.092 291.8\n> \tlinusas 2.056 296.8\n> \tlinusas2 1.909 319.8\n> \tmozilla 5.139 118.8\n> \tmozillaas 5.775 105.7\n> \topenssl 1.627 375.1\n> \tspelvin 1.678 363.7\n> \tspelvina 1.603 380.8\n> \tnettle 1.592 383.4\n> \n> And with the hacked version to get some 64-bit numbers:\n> \n> \t# TIME[s] SPEED[MB/s]\n> \trfc3174 3.992 152.9\n> \t# New hash result: b78fd74c0033a4dfe0ededccb85ab00cb56880ab\n> \trfc3174 3.991 152.9\n> \tlinus 1.54 396.3\n> \tlinusas 1.533 398.1\n> \tlinusas2 1.603 380.9\n> \tmozilla 4.352 140.3\n> \tmozillaas 4.227 144.4\n> \n> so as you can see, your improvements in 32-bit mode are actually \n> de-provements in 64-bit mode (ok, your first one seems to be a tiny \n> improvement, but I think it's in the noise).\n\nActually i didn't keep anything that wasn't a win, one reason\nwhy linusas2 stayed was that it really surprised me, i'd have\nexpected for gcc to do a lot worse w/ the many temporaries and\nthe compiler came up w/ a 70% gain; gcc really must have improved\nwhen i wasn't looking.\n\n> But you're right, I need to try to improve the 32-bit case.\n\nI never said anything like that. :) there probably isn't all that\nmuch that can be done. I tried a few things, but never saw any \nimprovement above measurement noise (a few percent). Would have\nthough that overlapping the iterations a bit would be a gain, but\nthat didn't do much (-20%..0), maybe on 64 bit, with more registers...\n\nOh, i noticed that '-mtune' makes quite a difference, it can change\nthe relative performance of the functions significantly, in unobvious\nways; depending on which cpu gcc tunes for (build config or -mtune);\nsome implementations slow down, others become a bit faster.\n\nartur\n"},{"id":"119821","messageId":"alpine.LFD.2.01.0908061233360.3390@localhost.localdomain","threadId":"20441","inReplyTo":"4A7B2A88.2040602@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T19:41:00Z","receivedAt":"2009-08-06T19:41:00Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 6 Aug 2009, Artur Skawina wrote:\n> \n> Oh, i noticed that '-mtune' makes quite a difference, it can change\n> the relative performance of the functions significantly, in unobvious\n> ways; depending on which cpu gcc tunes for (build config or -mtune);\n> some implementations slow down, others become a bit faster.\n\nThat probably is mainly true for P4, although it's quite possible that it \nhas an effect for just what the register allocator does, and then for \nspilling.\n\nAnd it looks like _all_ the tweakability is in the spilling. Nothing else \nmatters.\n\nHow does this patch work for you? It avoids doing that C-level register \nrotation, and instead rotates the register names with the preprocessor.\n\nI realize it's ugly as hell, but it does make it easier for gcc to see \nwhat's going on.\n\nThe patch is against my git patches, but I think it should apply pretty \nmuch as-is to your sha1bench sources too. Does it make any difference for \nyou?\n\n\t\tLinus\n\n---\n block-sha1/sha1.c | 117 ++++++++++++++++++++++++++++++++++++++++------------\n 1 files changed, 90 insertions(+), 27 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex 78dcb0c..ac47162 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -101,20 +101,20 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n #define SHA_SRC(t) htonl(data[t])\n #define SHA_MIX(t) SHA_ROL(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1)\n \n-#define SHA_ROUND(t, input, fn, constant) \\\n-\tTEMP = input(t); W(t) = TEMP; \\\n-\tTEMP += SHA_ROL(A,5) + (fn) + E + (constant); \\\n-\tE = D; D = C; C = SHA_ROR(B, 2); B = A; A = TEMP\n+#define SHA_ROUND(t, input, fn, constant, A, B, C, D, E) do { \\\n+\tunsigned int TEMP = input(t); W(t) = TEMP; \\\n+\tTEMP += E + SHA_ROL(A,5) + (fn) + (constant); \\\n+\tB = SHA_ROR(B, 2); E = TEMP; } while (0)\n \n-#define T_0_15(t) SHA_ROUND(t, SHA_SRC, (((C^D)&B)^D) , 0x5a827999 )\n-#define T_16_19(t) SHA_ROUND(t, SHA_MIX, (((C^D)&B)^D) , 0x5a827999 )\n-#define T_20_39(t) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0x6ed9eba1 )\n-#define T_40_59(t) SHA_ROUND(t, SHA_MIX, ((B&C)+(D&(B^C))) , 0x8f1bbcdc )\n-#define T_60_79(t) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0xca62c1d6 )\n+#define T_0_15(t, A, B, C, D, E) SHA_ROUND(t, SHA_SRC, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )\n+#define T_16_19(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )\n+#define T_20_39(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0x6ed9eba1, A, B, C, D, E )\n+#define T_40_59(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, ((B&C)+(D&(B^C))) , 0x8f1bbcdc, A, B, C, D, E )\n+#define T_60_79(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (B^C^D) , 0xca62c1d6, A, B, C, D, E )\n \n static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n {\n-\tunsigned int A,B,C,D,E,TEMP;\n+\tunsigned int A,B,C,D,E;\n \tunsigned int array[16];\n \n \tA = ctx->H[0];\n@@ -124,31 +124,94 @@ static void blk_SHA1Block(blk_SHA_CTX *ctx, const unsigned int *data)\n \tE = ctx->H[4];\n \n \t/* Round 1 - iterations 0-16 take their input from 'data' */\n-\tT_0_15( 0); T_0_15( 1); T_0_15( 2); T_0_15( 3); T_0_15( 4);\n-\tT_0_15( 5); T_0_15( 6); T_0_15( 7); T_0_15( 8); T_0_15( 9);\n-\tT_0_15(10); T_0_15(11); T_0_15(12); T_0_15(13); T_0_15(14);\n-\tT_0_15(15);\n+\tT_0_15( 0, A, B, C, D, E);\n+\tT_0_15( 1, E, A, B, C, D);\n+\tT_0_15( 2, D, E, A, B, C);\n+\tT_0_15( 3, C, D, E, A, B);\n+\tT_0_15( 4, B, C, D, E, A);\n+\tT_0_15( 5, A, B, C, D, E);\n+\tT_0_15( 6, E, A, B, C, D);\n+\tT_0_15( 7, D, E, A, B, C);\n+\tT_0_15( 8, C, D, E, A, B);\n+\tT_0_15( 9, B, C, D, E, A);\n+\tT_0_15(10, A, B, C, D, E);\n+\tT_0_15(11, E, A, B, C, D);\n+\tT_0_15(12, D, E, A, B, C);\n+\tT_0_15(13, C, D, E, A, B);\n+\tT_0_15(14, B, C, D, E, A);\n+\tT_0_15(15, A, B, C, D, E);\n \n \t/* Round 1 - tail. Input from 512-bit mixing array */\n-\tT_16_19(16); T_16_19(17); T_16_19(18); T_16_19(19);\n+\tT_16_19(16, E, A, B, C, D);\n+\tT_16_19(17, D, E, A, B, C);\n+\tT_16_19(18, C, D, E, A, B);\n+\tT_16_19(19, B, C, D, E, A);\n \n \t/* Round 2 */\n-\tT_20_39(20); T_20_39(21); T_20_39(22); T_20_39(23); T_20_39(24);\n-\tT_20_39(25); T_20_39(26); T_20_39(27); T_20_39(28); T_20_39(29);\n-\tT_20_39(30); T_20_39(31); T_20_39(32); T_20_39(33); T_20_39(34);\n-\tT_20_39(35); T_20_39(36); T_20_39(37); T_20_39(38); T_20_39(39);\n+\tT_20_39(20, A, B, C, D, E);\n+\tT_20_39(21, E, A, B, C, D);\n+\tT_20_39(22, D, E, A, B, C);\n+\tT_20_39(23, C, D, E, A, B);\n+\tT_20_39(24, B, C, D, E, A);\n+\tT_20_39(25, A, B, C, D, E);\n+\tT_20_39(26, E, A, B, C, D);\n+\tT_20_39(27, D, E, A, B, C);\n+\tT_20_39(28, C, D, E, A, B);\n+\tT_20_39(29, B, C, D, E, A);\n+\tT_20_39(30, A, B, C, D, E);\n+\tT_20_39(31, E, A, B, C, D);\n+\tT_20_39(32, D, E, A, B, C);\n+\tT_20_39(33, C, D, E, A, B);\n+\tT_20_39(34, B, C, D, E, A);\n+\tT_20_39(35, A, B, C, D, E);\n+\tT_20_39(36, E, A, B, C, D);\n+\tT_20_39(37, D, E, A, B, C);\n+\tT_20_39(38, C, D, E, A, B);\n+\tT_20_39(39, B, C, D, E, A);\n \n \t/* Round 3 */\n-\tT_40_59(40); T_40_59(41); T_40_59(42); T_40_59(43); T_40_59(44);\n-\tT_40_59(45); T_40_59(46); T_40_59(47); T_40_59(48); T_40_59(49);\n-\tT_40_59(50); T_40_59(51); T_40_59(52); T_40_59(53); T_40_59(54);\n-\tT_40_59(55); T_40_59(56); T_40_59(57); T_40_59(58); T_40_59(59);\n+\tT_40_59(40, A, B, C, D, E);\n+\tT_40_59(41, E, A, B, C, D);\n+\tT_40_59(42, D, E, A, B, C);\n+\tT_40_59(43, C, D, E, A, B);\n+\tT_40_59(44, B, C, D, E, A);\n+\tT_40_59(45, A, B, C, D, E);\n+\tT_40_59(46, E, A, B, C, D);\n+\tT_40_59(47, D, E, A, B, C);\n+\tT_40_59(48, C, D, E, A, B);\n+\tT_40_59(49, B, C, D, E, A);\n+\tT_40_59(50, A, B, C, D, E);\n+\tT_40_59(51, E, A, B, C, D);\n+\tT_40_59(52, D, E, A, B, C);\n+\tT_40_59(53, C, D, E, A, B);\n+\tT_40_59(54, B, C, D, E, A);\n+\tT_40_59(55, A, B, C, D, E);\n+\tT_40_59(56, E, A, B, C, D);\n+\tT_40_59(57, D, E, A, B, C);\n+\tT_40_59(58, C, D, E, A, B);\n+\tT_40_59(59, B, C, D, E, A);\n \n \t/* Round 4 */\n-\tT_60_79(60); T_60_79(61); T_60_79(62); T_60_79(63); T_60_79(64);\n-\tT_60_79(65); T_60_79(66); T_60_79(67); T_60_79(68); T_60_79(69);\n-\tT_60_79(70); T_60_79(71); T_60_79(72); T_60_79(73); T_60_79(74);\n-\tT_60_79(75); T_60_79(76); T_60_79(77); T_60_79(78); T_60_79(79);\n+\tT_60_79(60, A, B, C, D, E);\n+\tT_60_79(61, E, A, B, C, D);\n+\tT_60_79(62, D, E, A, B, C);\n+\tT_60_79(63, C, D, E, A, B);\n+\tT_60_79(64, B, C, D, E, A);\n+\tT_60_79(65, A, B, C, D, E);\n+\tT_60_79(66, E, A, B, C, D);\n+\tT_60_79(67, D, E, A, B, C);\n+\tT_60_79(68, C, D, E, A, B);\n+\tT_60_79(69, B, C, D, E, A);\n+\tT_60_79(70, A, B, C, D, E);\n+\tT_60_79(71, E, A, B, C, D);\n+\tT_60_79(72, D, E, A, B, C);\n+\tT_60_79(73, C, D, E, A, B);\n+\tT_60_79(74, B, C, D, E, A);\n+\tT_60_79(75, A, B, C, D, E);\n+\tT_60_79(76, E, A, B, C, D);\n+\tT_60_79(77, D, E, A, B, C);\n+\tT_60_79(78, C, D, E, A, B);\n+\tT_60_79(79, B, C, D, E, A);\n \n \tctx->H[0] += A;\n \tctx->H[1] += B;\n"},{"id":"119828","messageId":"4A7B384C.2020407@gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061233360.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-06T20:08:44Z","receivedAt":"2009-08-06T20:08:44Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> On Thu, 6 Aug 2009, Artur Skawina wrote:\n>> Oh, i noticed that '-mtune' makes quite a difference, it can change\n>> the relative performance of the functions significantly, in unobvious\n>> ways; depending on which cpu gcc tunes for (build config or -mtune);\n>> some implementations slow down, others become a bit faster.\n> \n> That probably is mainly true for P4, although it's quite possible that it \n> has an effect for just what the register allocator does, and then for \n> spilling.\n> \n> And it looks like _all_ the tweakability is in the spilling. Nothing else \n> matters.\n> \n> How does this patch work for you? It avoids doing that C-level register \n> rotation, and instead rotates the register names with the preprocessor.\n> \n> I realize it's ugly as hell, but it does make it easier for gcc to see \n> what's going on.\n> \n> The patch is against my git patches, but I think it should apply pretty \n> much as-is to your sha1bench sources too. Does it make any difference for \n> you?\n\nit's a bit slower (P4):\n\nbefore: linus 0.6288 97.06\nafter: linus 0.6604 92.42\n\ni was trying similar things, like the example below, too, but it wasn't a\nwin on 32 bit...\n\nartur\n\n[the iteration below is functionally correct, but scheduling is most likely\n fubared as it wasn't a win and i was checking how much a difference it made\n on P4 -- ~-20..~0%, but never faster (relative to linusas2; it _is_ faster\n than 'linus'. Dropped this version when merging your new preprocessor macros.]\n\n@@ -125,6 +127,8 @@\n #define W(x) (array[(x)&15])\n #define SHA_XOR(t) \\\n TEMP = SHA_ROL(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1); W(t) = TEMP;\n+#define SHA_XOR2(t) \\\n+ SHA_ROL(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1)\n \n #define T_16_19(t) \\\n { unsigned TEMP;\\\n@@ -139,10 +143,27 @@\n #endif\n \n #define T_20_39(t) \\\n- { unsigned TEMP;\\\n- SHA_XOR(t); \\\n- TEMP += (B^C^D) + E + 0x6ed9eba1; \\\n- E = D; D = C; C = SHA_ROR(B, 2); B = A; TEMP += SHA_ROL(A,5); A = TEMP; }\n+ if (t%2==0) {\\\n+ unsigned TEMP;\\\n+ unsigned TEMP2;\\\n+ \\\n+ TEMP = SHA_XOR2(t); \\\n+ TEMP2 = SHA_XOR2(t+1); \\\n+ W(t) = TEMP;\\\n+ W(t+1) = TEMP2;\\\n+ TEMP += E + 0x6ed9eba1; \\\n+ E = C;\\\n+ TEMP += (B^E^D); \\\n+ TEMP2 += D + 0x6ed9eba1; \\\n+ D = SHA_ROR(B, 2);\\\n+ B = SHA_ROL(A, 5);\\\n+ B += TEMP;\\\n+ C = SHA_ROR(A, 2);\\\n+ A ^= E; \\\n+ A ^= D; \\\n+ A += TEMP2;\\\n+ A += SHA_ROL(B, 5);\\\n+ }\n \n #if UNROLL\n T_20_39(20); T_20_39(21); T_20_39(22); T_20_39(23); T_20_39(24);\n"},{"id":"119833","messageId":"alpine.LFD.2.01.0908061329320.3390@localhost.localdomain","threadId":"20441","inReplyTo":"4A7B384C.2020407@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T20:53:11Z","receivedAt":"2009-08-06T20:53:11Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 6 Aug 2009, Artur Skawina wrote:\n> \n> it's a bit slower (P4):\n> \n> before: linus 0.6288 97.06\n> after: linus 0.6604 92.42\n\nHmm. Ok, I just tested with your harness, and I get\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 5.1 119.7\n\trfc3174 5.097 119.7\n\tlinus 1.836 332.5\n\tlinusas 2.006 304.3\n\tlinusas2 1.879 324.9\n\tmozilla 5.562 109.7\n\tmozillaas 5.913 103.2\n\topenssl 1.613 378.5\n\tspelvin 1.698 359.5\n\tspelvina 1.602 381\n\tnettle 1.594 382.9\n\nwith it, so it is faster for me. So your slowdown seems to be yet another \nP4 thing. Dang crazy micro-architecture.\n\nOf course, it might be a compiler version difference too. I'm using \ngcc-4.4.0.\n\nWith the cpp variable renaming, the compiler really has less to be smart \nabout, but spill decisions will still matter a lot.\n\n(My old 32-bit numbers were \n\n linus 2.092 291.8\n\nso it's a clear improvement on my machine and with my compiler).\n\nIt also seems to improve the 64-bit numbers a small bit, I'm getting\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 3.98 153.3\n\trfc3174 3.972 153.7\n\tlinus 1.514 403.1\n\tlinusas 1.555 392.6\n\tlinusas2 1.599 381.7\n\tmozilla 4.34 140.6\n\tmozillaas 4.223 144.5\n\nwith my 64-bit compile, so on a Nehalem it's the best one of the C ones by \na noticeable margin. (My original 64-bit numbers were\n\n linus 1.54 396.3\n\nand while the numbers seem to fluctuate a bit, the fluctuation is roughly \nin the 1% range, so that improvement seems to be statistically \nsignificant.\n\nOh, I did make a small change, but I doubt it matters. Instead of doing\n\n\tTEMP += E + SHA_ROL(A,5) + (fn) + (constant); \\\n\tB = SHA_ROR(B, 2); E = TEMP; } while (0)\n\nI now do\n\n\tE += TEMP + SHA_ROL(A,5) + (fn) + (constant); \\\n\tB = SHA_ROR(B, 2); } while (0)\n\nwhich is a bit more logical (the old TEMP usage was just due to a fairly \nmindless conversion). That _might_ have lower register pressure if the \ncompiler is silly enough to not notice that it can do it. Maybe that \nmatters.\n\n\t\t\tLinus\n"},{"id":"119835","messageId":"alpine.LFD.2.01.0908061406330.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061329320.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T21:24:30Z","receivedAt":"2009-08-06T21:24:30Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 6 Aug 2009, Linus Torvalds wrote:\n> \n> Hmm. Ok, I just tested with your harness, and I get\n> \n> \t# TIME[s] SPEED[MB/s]\n> \trfc3174 5.1 119.7\n> \trfc3174 5.097 119.7\n> \tlinus 1.836 332.5\n> \tlinusas 2.006 304.3\n> \tlinusas2 1.879 324.9\n> \tmozilla 5.562 109.7\n> \tmozillaas 5.913 103.2\n> \topenssl 1.613 378.5\n> \tspelvin 1.698 359.5\n> \tspelvina 1.602 381\n> \tnettle 1.594 382.9\n\nOn atom, I get things like:\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 2.186 27.92\n\trfc3174 2.186 27.92\n\tlinus 0.9492 64.3\n\tlinusas 0.9656 63.21\n\tlinusas2 1.012 60.29\n\tmozilla 2.492 24.49\n\tmozillaas 2.5 24.41\n\topenssl 0.6411 95.2\n\tspelvin 0.6052 100.8\n\tspelvina 0.6655 91.71\n\tnettle 0.7149 85.37\n\nbut quite frankly, those timings aren't stable enough to say anything. \nAnother few runs got me:\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 2.207 27.65\n\trfc3174 2.21 27.62\n\tlinus 1.022 59.74\n\tlinusas 1.058 57.7\n\tlinusas2 1.008 60.58\n\tmozilla 2.485 24.56\n\tmozillaas 2.522 24.2\n\topenssl 0.6421 95.06\n\tspelvin 0.5989 101.9\n\tspelvina 0.6638 91.94\n\tnettle 0.7132 85.58\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 2.224 27.44\n\trfc3174 2.205 27.68\n\tlinus 0.9727 62.75\n\tlinusas 0.9766 62.5\n\tlinusas2 1.026 59.5\n\tmozilla 2.52 24.22\n\tmozillaas 2.547 23.96\n\topenssl 0.6459 94.5\n\tspelvin 0.6074 100.5\n\tspelvina 0.6751 90.41\n\tnettle 0.7254 84.14\n\nso whatever differences there are between linus*, they seem to be in the \nnoise, and the hand-scheduled asm beats all the C versions senseless.\n\nI'd like to get closer to the hand-tuned ones, but I don't see anything to \ndo any more. It's all about gcc register choice and avoiding spilling. So \ncompiler flags changing small details can have _huge_ differences in \nperformance. Here's the Atom numbers with gcc given the \"-Os\" flag (just \nbecause I wanted to try):\n\n\tlinus 1.072 56.94\n\tlinusas 0.9573 63.76\n\tlinusas2 0.9906 61.61\n\nWhy did 'linus' numbers go down? No idea. With -O3, it's the other way \naround:\n\n\tlinus 0.9537 64\n\tlinusas 0.9566 63.8\n\tlinusas2 1.013 60.26\n\nbut again, there's variation enough that I'd probabyl need to run ten runs \njust to see how much is noise. But the \"linusas2 sucks with -O3\" is clear, \nas is the \"linus sucks with -Os\" thing. Very odd, and very random.\n\n\t\tLinus\n"},{"id":"119838","messageId":"4A7B4D84.80906@gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061329320.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-06T21:39:16Z","receivedAt":"2009-08-06T21:39:16Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> with it, so it is faster for me. So your slowdown seems to be yet another \n> P4 thing. Dang crazy micro-architecture.\n> \n> Of course, it might be a compiler version difference too. I'm using \n> gcc-4.4.0.\n\ngcc version 4.4.1 20090603 (prerelease)\n\n> Oh, I did make a small change, but I doubt it matters. Instead of doing\n> \n> \tTEMP += E + SHA_ROL(A,5) + (fn) + (constant); \\\n> \tB = SHA_ROR(B, 2); E = TEMP; } while (0)\n> \n> I now do\n> \n> \tE += TEMP + SHA_ROL(A,5) + (fn) + (constant); \\\n> \tB = SHA_ROR(B, 2); } while (0)\n> \n> which is a bit more logical (the old TEMP usage was just due to a fairly \n> mindless conversion). That _might_ have lower register pressure if the \n> compiler is silly enough to not notice that it can do it. Maybe that \n> matters.\n\nbefore: linus 0.6622 92.17\nafter: linus 0.6631 92.05\nafter: linus 0.6601 92.46\nafter: linus 0.6624 92.14\n\nIOW, no difference, just noise.\n"},{"id":"119839","messageId":"4A7B509A.5010405@gmail.com","threadId":"20441","inReplyTo":"4A7B4D84.80906@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-06T21:52:26Z","receivedAt":"2009-08-06T21:52:26Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Artur Skawina wrote:\n> Linus Torvalds wrote:\n>> Oh, I did make a small change, but I doubt it matters. Instead of doing\n>>\n>> \tTEMP += E + SHA_ROL(A,5) + (fn) + (constant); \\\n>> \tB = SHA_ROR(B, 2); E = TEMP; } while (0)\n>>\n>> I now do\n>>\n>> \tE += TEMP + SHA_ROL(A,5) + (fn) + (constant); \\\n>> \tB = SHA_ROR(B, 2); } while (0)\n>>\n>> which is a bit more logical (the old TEMP usage was just due to a fairly \n>> mindless conversion). That _might_ have lower register pressure if the \n>> compiler is silly enough to not notice that it can do it. Maybe that \n>> matters.\n> \n> before: linus 0.6622 92.17\n> after: linus 0.6631 92.05\n> after: linus 0.6601 92.46\n> after: linus 0.6624 92.14\n> \n> IOW, no difference, just noise.\n\nJust to check, i did this: \n\ndiff -urNp sha1bench-linus.org/block-sha1/sha1.c sha1bench-linus/block-sha1/sha1.c\n--- sha1bench-linus.org/block-sha1/sha1.c\t2009-08-06 23:26:15.607321815 +0200\n+++ sha1bench-linus/block-sha1/sha1.c\t2009-08-06 23:41:36.858325807 +0200\n@@ -103,8 +103,8 @@ void blk_SHA1_Final(unsigned char hashou\n \n #define SHA_ROUND(t, input, fn, constant, A, B, C, D, E) do { \\\n \tunsigned int TEMP = input(t); W(t) = TEMP; \\\n-\tE += TEMP + SHA_ROL(A,5) + (fn) + (constant); \\\n-\tB = SHA_ROR(B, 2); } while (0)\n+\tE += TEMP + (fn) + (constant); \\\n+\tB = SHA_ROR(B, 2); E += SHA_ROL(A,5); } while (0)\n \n #define T_0_15(t, A, B, C, D, E) SHA_ROUND(t, SHA_SRC, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )\n #define T_16_19(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )\n\nand the result was:\n\n# TIME[s] SPEED[MB/s]\nrfc3174 1.47 41.51\nrfc3174 1.474 41.42\nlinus 0.3564 171.2\nlinusas 0.5736 106.4\nlinusas2 0.3568 171.1\nmozilla 1.17 52.19\nmozillaas 1.382 44.17\nopenssl 0.2636 231.5\nspelvin 0.2662 229.2\nspelvina 0.2515 242.7\nnettle 0.4386 139.2\n\nHmm. \nDoes this make any difference for you? For me it's the best one so far\n(the linusas2 number clearly shows that for me the register renaming does\nnothing; other than that the functions should be very similar)\n\nartur\n"},{"id":"119841","messageId":"alpine.LFD.2.01.0908061502570.3390@localhost.localdomain","threadId":"20441","inReplyTo":"4A7B509A.5010405@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T22:27:36Z","receivedAt":"2009-08-06T22:27:36Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 6 Aug 2009, Artur Skawina wrote:\n> \n> Does this make any difference for you? For me it's the best one so far\n> (the linusas2 number clearly shows that for me the register renaming does\n> nothing; other than that the functions should be very similar)\n\nNope. If anything, it's bit slower, but it might be in the noise. I \ngenerally got 330MB/s with my \"cpp renaming\" on Nehalem (32-bit - the \n64-bit numbers are ~400MB/s), but with this I got 325MB/s twice in a row, \nwhich matches the linusas2 numbers pretty exactly.\n\nBut it seems to make a big difference for you.\n\nBtw, _what_ P4 do you have (Northwood or Prescott)?\n\nThe Intel optimization manuals very much talk about avoiding rotates. And \nthey mention \"with a CPUID signature corresponding to family 15 and model \nencoding of 0, 1, or 2\" specifically as being longer latency. That's \nbasically pre-prescott P4, I think.\n\nAnyway, on P4 I think you have two double-speed integer issue ports (ie \nmax four ops per cycle), but only one of them takes a rotate, and only in \nthe first half of the cycle (ie just one shift per cycle).\n\nAnd afaik, that is actually the _improved_ state in Prescott. The older \nP4's didn't have a full shifter unit at all, iirc: shifts were \"complex \ninstructions\" in Northwood and weren't even single-clock.\n\nIn Core 2, I think there's still just one shifter unit, but at least it's \nas fast as all the other units. So P4 really does stand out as sucking as \nfar as shifts are concerned, and if you have an older P4, it will be even \nworse.\n\n\t\tLinus\n"},{"id":"119842","messageId":"alpine.LFD.2.01.0908061531310.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061502570.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T22:33:45Z","receivedAt":"2009-08-06T22:33:45Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 6 Aug 2009, Linus Torvalds wrote:\n> \n> Anyway, on P4 I think you have two double-speed integer issue ports (ie \n> max four ops per cycle), but only one of them takes a rotate, and only in \n> the first half of the cycle (ie just one shift per cycle).\n> \n> And afaik, that is actually the _improved_ state in Prescott. The older \n> P4's didn't have a full shifter unit at all, iirc: shifts were \"complex \n> instructions\" in Northwood and weren't even single-clock.\n\nYeah, verified. Google for\n\n\tnorthwood \"barrel shifter\"\n\nand you'll find a lot of it.\n\nBasically, older P4's will I think shift one bit at a time. So while even \nPrescott is relatively weak in the shifter department, pre-prescott \n(Willamette and Northwood) are _really_ weak. If your P4 is one of those, \nyou really shouldn't use it to decide on optimizations.\n\n\t\tLinus\n"},{"id":"119843","messageId":"4A7B5F4C.30102@gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061502570.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-06T22:55:08Z","receivedAt":"2009-08-06T22:55:08Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> On Thu, 6 Aug 2009, Artur Skawina wrote:\n>> Does this make any difference for you? For me it's the best one so far\n>> (the linusas2 number clearly shows that for me the register renaming does\n>> nothing; other than that the functions should be very similar)\n> \n> Nope. If anything, it's bit slower, but it might be in the noise. I \n> generally got 330MB/s with my \"cpp renaming\" on Nehalem (32-bit - the \n> 64-bit numbers are ~400MB/s), but with this I got 325MB/s twice in a row, \n> which matches the linusas2 numbers pretty exactly.\n> \n> But it seems to make a big difference for you.\n\nIt seems to do well on P2 and P4 here, if it works for core2 this could\nbe a good generic candidate. It only does 62% on an Atom, but the best C\nversion so far exceeds it only by ~2%.\n\n> Btw, _what_ P4 do you have (Northwood or Prescott)?\n\nnorthwood\n\n> The Intel optimization manuals very much talk about avoiding rotates. And \n> they mention \"with a CPUID signature corresponding to family 15 and model \n> encoding of 0, 1, or 2\" specifically as being longer latency. That's \n> basically pre-prescott P4, I think.\n\ncpu family : 15\nmodel : 2\nmodel name : Intel(R) Pentium(R) 4 CPU 2.80GHz\nstepping : 5\n\n> Anyway, on P4 I think you have two double-speed integer issue ports (ie \n> max four ops per cycle), but only one of them takes a rotate, and only in \n> the first half of the cycle (ie just one shift per cycle).\n> \n> And afaik, that is actually the _improved_ state in Prescott. The older \n> P4's didn't have a full shifter unit at all, iirc: shifts were \"complex \n> instructions\" in Northwood and weren't even single-clock.\n> \n> In Core 2, I think there's still just one shifter unit, but at least it's \n> as fast as all the other units. So P4 really does stand out as sucking as \n> far as shifts are concerned, and if you have an older P4, it will be even \n> worse.\n\nhmm, I might be able to try it on some old willamette, but my prescott's\nmobo died, so i can't verify that right now.\n\nI'll upload an updated sha1bench, maybe somebody else feels like checking...\n\nartur \n"},{"id":"119844","messageId":"alpine.LFD.2.01.0908061559120.3390@localhost.localdomain","threadId":"20441","inReplyTo":"4A7B5F4C.30102@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T23:04:27Z","receivedAt":"2009-08-06T23:04:27Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 7 Aug 2009, Artur Skawina wrote:\n> \n> hmm, I might be able to try it on some old willamette, but my prescott's\n> mobo died, so i can't verify that right now.\n\nI think willamette and northwood are basically the same wrt shifters (and \npretty much everything else too, for that matter). I think northwood is a \nshrink, and had an increased cache size (and higher frequencies). But I \nthink core-wise, they're very similar.\n\nIt was prescott that changed a lot (mostly for the worse - the shifter was \none of the few upsides of prescott, although increased frequency often \nmade up for the downsides).\n\n\t\tLinus\n"},{"id":"119846","messageId":"4A7B64F1.2000309@gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061531310.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-06T23:19:13Z","receivedAt":"2009-08-06T23:19:13Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> Yeah, verified. Google for\n> \n> \tnorthwood \"barrel shifter\"\n> \n> and you'll find a lot of it.\n> \n> Basically, older P4's will I think shift one bit at a time. So while even \n> Prescott is relatively weak in the shifter department, pre-prescott \n> (Willamette and Northwood) are _really_ weak. If your P4 is one of those, \n> you really shouldn't use it to decide on optimizations.\n\nActually that's even more of a reason to make sure the code doesn't suck :)\nThe difference on less perverse cpus will usually be small, but on P4 it\ncan be huge.\n\nA few years back I found my old ip checksum microbenchmark, and when I ran\nit on a P4 (prescott iirc) i didn't believe my eyes. The straightforward \n32-bit C implementation was running circles around the in-kernel one...\nAnd a few tweaks to the assembler version got me another ~100% speedup.[1]\n\nAfter that the P4 became the very first cpu to test any code on... :)\n\nartur\n\n[1] just reran the benchmark on this p4; true on northwood too:\n\nIACCK 0.9.30 Artur Skawina <...>\n[ exec time; lower is better ] [speed ] [ time ] [ok?]\nTIME-N+S TIME32 TIME33 TIME1480 MBYTES/S TIMEXXXX CSUM FUNCTION ( rdtsc_overhead=0 null=0 )\n 17901 510 557 3010 393.36 59772 56dd csum_partial_cdumb16\n 3019 154 156 431 2747.10 43106 56dd csum_partial_c32\n 2413 170 177 328 3609.76 37501 56dd csum_partial_c32l\n 2437 170 170 328 3609.76 37488 56dd csum_partial_c32i\n 5078 205 254 767 1543.68 48117 56dd csum_partial_std\n 5612 299 291 851 1391.30 53673 56dd csum_partial_686\n 1584 99 127 227 5215.86 14495 56dd csum_partial_586f\n 1738 107 121 229 5170.31 14785 56dd csum_partial_586fs\n 4893 175 171 759 1559.95 52347 56dd csum_partial_copy_generic_std\n 4949 151 189 756 1566.14 67847 56dd csum_partial_copy_generic_686\n 2072 110 134 302 3920.53 39061 56dd csum_partial_copy_generic_p4as1\n"},{"id":"119847","messageId":"alpine.LFD.2.01.0908061609340.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061559120.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T23:25:10Z","receivedAt":"2009-08-06T23:25:10Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 6 Aug 2009, Linus Torvalds wrote:\n> \n> It was prescott that changed a lot (mostly for the worse - the shifter was \n> one of the few upsides of prescott, although increased frequency often \n> made up for the downsides).\n\nAnyway, since you have a Northwood, I bet that the #1 issue for you is to \nspread out the shift instructions in a way that simply doesn't matter \nanywhere else.\n\nIn netburst, if I remember the details correcty, a \"complex instruction\" \nwill basically get the trace cache from the microcode roms. I'm not sure \nhow it interacts with the TC entries around it, but it's entirely possible \nthat it basically disables any instruction scheduling (the microcode \ntraces are presumably \"pre-scheduled\"), so you'd basically see stalls \nwhere there's little out-of-order execution.\n\nThat then explains why you see huge differences from what is basically \ntrivial scheduling decisions, and why some random placement of a shift \nmakes a big difference.\n\nJust out of curiosity, does anything change if you change the\n\n\tB = SHA_ROR(B,2)\n\ninto a\n\n\tB = SHA_ROR(SHA_ROR(B,1),1)\n\ninstead? It's very possible that it becomes _much_ worse, but I guess it's \nalso possible in theory that a single-bit rotate ends up being a simple \ninstruction and that doing two single-bit ROR's is actually faster than \none 2-bit ROR (assuming the second one is microcoded and the first one).\n\nIn particular, I'm thinking about the warnign in the intel optimization \nmanual:\n\n\tThe rotate by immediate and rotate by register instructions are \n\tmore expensive than a shift. The rotate by 1 instruction has the \n\tsame latency as a shift.\n\nso it's very possible that \"rotate by 1\" is much better than other \nrotates.\n\n\n\t\t\tLinus\n"},{"id":"119851","messageId":"alpine.LFD.2.01.0908061625300.3390@localhost.localdomain","threadId":"20441","inReplyTo":"4A7B64F1.2000309@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-06T23:42:01Z","receivedAt":"2009-08-06T23:42:01Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 7 Aug 2009, Artur Skawina wrote:\n> \n> Actually that's even more of a reason to make sure the code doesn't suck :)\n> The difference on less perverse cpus will usually be small, but on P4 it\n> can be huge.\n\nNo. First off, the things you have to do on P4 are just insane. See the \nemail I just sent out asking you to test whether two 1-bit rotates might \nbe faster than 1 2-bit rotate.\n\nSo optimizing for P4 is often the wrong thing.\n\nSecondly, P4's are going away. You may have one, but they are getting \nrare. So optimizing for them is a losing proposition in the long run.\n\n> A few years back I found my old ip checksum microbenchmark, and when I ran\n> it on a P4 (prescott iirc) i didn't believe my eyes. The straightforward \n> 32-bit C implementation was running circles around the in-kernel one...\n> And a few tweaks to the assembler version got me another ~100% speedup.[1]\n\nYeah, not very surprising. The P4 is very good at the simplest possible \nkind of code that does _nothing_ fancy.\n\nBut then it completely chokes on some code. I mean _totally_. It slows \ndown by a huge amount if there is anything but the most trivial kinds of \ninstructions. And by \"trivial\", I mean _really_ trivial. Shifts (as in \nSHA1), but iirc also things like \"adc\" (add with carry) etc.\n\nSo it's not hard to write code that works well on other uarchs, and then \ntotally blow up on P4. I think it doesn't rename the flags at all, so any \nflag dependency (carry being the most common one) will stall things \nhorrible.\n\nThere's also a very subtle store forwarding failure thing (and a lot of \nother events) that causes a nasty micro-architectural replay trap, and \nagain you go from \"running like a bat out of hell\" to \"slower than a i486 \nat a tenth the frequency\".\n\nReally. It's disgusting. Perfectly fine code can run really slowly on the \nP4 just because it hits some random internal micro-architectural flaw. And \nthere's a _lot_ of those \"glass jaw\" issues.\n\nThe best way to avoid them is to use _only_ simple ALU instructions (add, \nsub, and/or/not), and to be _very_ careful with loads and stores. \n\n\t\tLinus\n"},{"id":"119853","messageId":"alpine.LFD.2.01.0908061709400.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061609340.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-07T00:13:04Z","receivedAt":"2009-08-07T00:13:04Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 6 Aug 2009, Linus Torvalds wrote:\n> \n> In particular, I'm thinking about the warnign in the intel optimization \n> manual:\n> \n> \tThe rotate by immediate and rotate by register instructions are \n> \tmore expensive than a shift. The rotate by 1 instruction has the \n> \tsame latency as a shift.\n> \n> so it's very possible that \"rotate by 1\" is much better than other \n> rotates.\n\nHmm. Probably not. Googling more seems to indicate that rotates and shifts \nhave a fixed 4-cycle latency on Northwood. I'm not seeing anything that \nindicates that a single-bit rotate/shift would be any faster.\n\n(And remember, if 4 cycles doesn't sound so bad: that's enough of a \nlatency to do _16_ \"simple\" ALU's, since they can be double-pumped in the \ntwo regular ALU's).\n\nI think long-running ALU ops that feed into a store (spill) also happen to \nbe the thing that makes the dreaded store-buffer replay trap nasties \nhappen more (load vs store scheduled badly, and then you end up spending \ntens of cycles just replaying).\n\n\t\t\tLinus\n"},{"id":"119856","messageId":"4A7B7B21.1000001@gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061609340.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-07T00:53:53Z","receivedAt":"2009-08-07T00:53:53Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> Just out of curiosity, does anything change if you change the\n> \n> \tB = SHA_ROR(B,2)\n> \n> into a\n> \n> \tB = SHA_ROR(SHA_ROR(B,1),1)\n> \n> instead? It's very possible that it becomes _much_ worse, but I guess it's \n\nDid try that yesterday, didn't help. Will recheck now.. yep:\n\nbefore: linus 0.3554 171.7\nafter: linus 0.407 150\n\nstill true for the current version.\n\n> So optimizing for P4 is often the wrong thing.\n> \n> Secondly, P4's are going away. You may have one, but they are getting \n> rare. So optimizing for them is a losing proposition in the long run.\n\nSure, no argument; it's just that avoiding the P4 pitfalls is usually\nnot that hard and the impact on other, non-netburst, archs is low.\nThere are a lot of P4s out there and they're not going away soon.\n(i'm still keeping most of my git trees on a P3...)\n\nFor generic C code such as this the difference for your i7 was -2% and\n+70% for my P4; all the other (but one, i think) optimizations which\nworked on P4 also applied to 32-bit i7. As i happen to have a p4 i can\njust as well test the code on it, many improvements will likely apply\nto other cpus too. That's all, i doubt anybody seriously considered\n\"optimizing for P4\"; there is a reason intel discontinued them :)\n\nThe atom is a more important target, but only the asm versions did well\nthere so far.\n\nartur\n"},{"id":"119863","messageId":"4A7B83BC.1040606@gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061709400.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-07T01:30:36Z","receivedAt":"2009-08-07T01:30:36Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> On Thu, 6 Aug 2009, Linus Torvalds wrote:\n>> In particular, I'm thinking about the warnign in the intel optimization \n>> manual:\n>>\n>> \tThe rotate by immediate and rotate by register instructions are \n>> \tmore expensive than a shift. The rotate by 1 instruction has the \n>> \tsame latency as a shift.\n>>\n>> so it's very possible that \"rotate by 1\" is much better than other \n>> rotates.\n> \n> Hmm. Probably not. Googling more seems to indicate that rotates and shifts \n> have a fixed 4-cycle latency on Northwood. I'm not seeing anything that \n> indicates that a single-bit rotate/shift would be any faster.\n> \n> (And remember, if 4 cycles doesn't sound so bad: that's enough of a \n> latency to do _16_ \"simple\" ALU's, since they can be double-pumped in the \n> two regular ALU's).\n\nlooking at the generated code, there is a lot of ro[rl] movement, so it's\nlikely that contributes to the problem.\n\nI also see 44 extra lea instructions, 44 less adds and changes like:\n [...]\n mov XX(%eRX),%eRX\n xor XX(%eRX),%eRX\n- and %eRX,%eRX\n+ and XX(%eRX),%eRX\n xor XX(%eRX),%eRX\n- add %eRX,%eRX\n- ror $0x2,%eRX\n- mov %eRX,XX(%eRX)\n+ lea (%eRX,%eRX,1),%eRX\n mov XX(%eRX),%eRX\n bswap %eRX\n mov %eRX,XX(%eRX)\n mov %eRX,%eRX\n+ ror $0x2,%eRX\n+ mov %eRX,XX(%eRX)\n+ mov %eRX,%eRX\n rol $0x5,%eRX\n mov XX(%eRX),%eRX\n- mov XX(%eRX),%eRX\n [...]\nwhich could mean that gcc did a better job of register allocation\n(where \"better job\" might be just luck).\n\nartur\n"},{"id":"119866","messageId":"alpine.LFD.2.01.0908061833130.3390@localhost.localdomain","threadId":"20441","inReplyTo":"4A7B83BC.1040606@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-07T01:55:19Z","receivedAt":"2009-08-07T01:55:19Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 7 Aug 2009, Artur Skawina wrote:\n> \n> I also see 44 extra lea instructions, 44 less adds\n\nadd and lea (as long as the lea shift is 1) should be the same on a P4 \n(they are not the same on some other microarchitectures and lea can have \naddress generation stalls etc).\n\nLea, of course, gives the potential for register movement at the same time \n(three-address op), and that's likely the reason for lea-vs-adds.\n\n> and changes like:\n> [...]\n> mov XX(%eRX),%eRX\n> xor XX(%eRX),%eRX\n> - and %eRX,%eRX\n> + and XX(%eRX),%eRX\n\nYeah, different spill patterns. That's the biggest issue, I think.\n\nIn particular, on P4, with unlucky spills, you may end up with things like\n\n\tror $2,reg\n\tmov reg,x(%esp)\n\t.. a few instructions ..\n\txor x(%esp), reg\n\nand the above is exactly when one of the worst P4 problems hit: a store, \nfollowed a few cycles later by a load from the same address (and \"a few \ncycles later\" can be quite a few instructions if they are the nice ones).\n\nWhat can happen is that if the store data isn't ready yet (because it \ncomes from a long-latency op like a shift or a multiply), then you hit a \nstore buffer replay thing. The P4 (with its long pipeline) basically \nstarts the load speculatively, and if anything bad happens for the load \n(L1 cache miss, TLB miss, store buffer fault, you name it), it will cause \na replay of the whole pipeline.\n\nWhich can take tens of cycles. \n\n[ That said, it's been a long time since I did a lot of P4 worrying. So I \n may mis-remember the details. But that whole store buffer forwarding had \n some really nasty replay issues ]\n\n> which could mean that gcc did a better job of register allocation\n> (where \"better job\" might be just luck).\n\nI suspect that's the biggest issue. Just _happening_ to get the spills so \nthat they don't hurt. And with unlucky scheduling, you might hit some of \nthe P4 replay issues every single time.\n\nThere are some P4 optimizations that are simple:\n - avoid complex instructions\n - don't blow the trace cache\n - predictable branches\nbut the replay faults can really get you.\n\n\t\t\tLinus\n"},{"id":"119870","messageId":"alpine.LFD.2.01.0908061909310.3390@localhost.localdomain","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061502570.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-07T02:23:21Z","receivedAt":"2009-08-07T02:23:21Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 6 Aug 2009, Linus Torvalds wrote:\n\n> \n> \n> On Thu, 6 Aug 2009, Artur Skawina wrote:\n> > \n> > Does this make any difference for you? For me it's the best one so far\n> > (the linusas2 number clearly shows that for me the register renaming does\n> > nothing; other than that the functions should be very similar)\n> \n> Nope. If anything, it's bit slower, but it might be in the noise. I \n> generally got 330MB/s with my \"cpp renaming\" on Nehalem (32-bit - the \n> 64-bit numbers are ~400MB/s), but with this I got 325MB/s twice in a row, \n> which matches the linusas2 numbers pretty exactly.\n\nI actually found a P4 I have access to, except that one is a Prescott.\n\nAnd I can't run it in 32-bit mode, because I only have a regular user \nlogin, and it only has the 64-bit development environment.\n\nBut I can do the hacked-for-64bit sha1bench runs, and I tested your patch.\n\nIt's horrible.\n\nHere's the plain \"linus\" baseline (ie the \"Do register rotation in cpp\") \nthing, with the fixed \"E += TEMP ..\" thing):\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 1.648 37.03\n\trfc3174 1.677 36.4\n\tlinus 0.4018 151.9\n\tlinusas 0.4439 137.5\n\tlinusas2 0.4381 139.3\n\tmozilla 0.9587 63.66\n\tmozillaas 0.9434 64.7\n\nand here it is with your patch:\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 1.667 36.61\n\trfc3174 1.644 37.12\n\tlinus 0.4653 131.2\n\tlinusas 0.4412 138.3\n\tlinusas2 0.4388 139.1\n\tmozilla 0.9466 64.48\n\tmozillaas 0.9449 64.59\n\n(ok, so the numbers aren't horribly stable, but the \"plain linus\" thing \nconsistently outperforms here - and underperforms with your patch).\n\nHowever, note that since this is the 64-bit thing, there likely aren't any \nspill issues, but it's simply an issue of \"just how did the array[] \naccesses get scheduled\" etc. And since this is a Prescott (or rather \n\"Xeon\") P4, the shifter isn't quite as horrible as yours is. _And_ this is \na different gcc version (4.0.3).\n\nSo the numbers aren't really all that comparable. It's more an example of \n\"optimizing for P4 is futile, because you're just playing with total \nrandomness\". That's like a 20MB/s difference, just from moving a few ALU \nops around a bit.\n\nAnd it's entirely possible that if I had gcc-4.4 on that machine, your \npatch would magically do the right thing ;)\n\nSadly, that machine is just a ssh gateway, so there's no real development \ntools on it at all - no way to get good profiles etc. So I can't really \nsay exactly what the problem pattern is :(\n\n\t\tLinus\n"},{"id":"119880","messageId":"4A7BAAB2.8040807@gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908061909310.3390@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-07T04:16:50Z","receivedAt":"2009-08-07T04:16:50Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> Here's the plain \"linus\" baseline (ie the \"Do register rotation in cpp\") \n> thing, with the fixed \"E += TEMP ..\" thing):\n\n> \tlinus 0.4018 151.9\n\n> and here it is with your patch:\n\n> \tlinus 0.4653 131.2\n\n> (ok, so the numbers aren't horribly stable, but the \"plain linus\" thing \n> consistently outperforms here - and underperforms with your patch).\n\nWell, I'd be surprised if one C version would always be the winner on\nevery single cpu; that 13% loss[1] I think would be an acceptable compromise,\nif the goal is to have one implementation that does reasonably well on all\ncpus.\n\nThat's why i asked how the change did on nehalem; if it's a measurable loss\non anything modern (core2+), then of course the P4s must suffer; and one\ncould always blame the compiler ;)\nIt's not like the difference in sha1 overhead will be noticeable in normal\ngit use.\n\nartur\n\n[1] I suspect the old gcc is a factor (4.0.4 does <100M/s here).\n"},{"id":"119952","messageId":"alpine.LFD.2.01.0908072107170.3288@localhost.localdomain","threadId":"20441","inReplyTo":"4A7CC380.3070008@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-08T04:16:46Z","receivedAt":"2009-08-08T04:16:46Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 8 Aug 2009, Artur Skawina wrote:\n> \n> i was seeing such large variations depending on the -mtune flags that\n> i gave up and now do just -march=i686; that's what i would expect\n> for generic x86 binaries.\n\nI think I have found a way to avoid the gcc crazyness.\n\nLookie here:\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 5.094 119.8\n\trfc3174 5.098 119.7\n\tlinus 1.462 417.5\n\tlinusas 2.008 304\n\tlinusas2 1.878 325\n\tmozilla 5.566 109.6\n\tmozillaas 5.866 104.1\n\topenssl 1.609 379.3\n\tspelvin 1.675 364.5\n\tspelvina 1.601 381.3\n\tnettle 1.591 383.6\n\nnotice? I outperform all the hand-tuned asm on 32-bit too. By quite a \nmargin, in fact.\n\nNow, I didn't try a P4, and it's possible that it won't do that there, but \nthe 32-bit code generation sure looks impressive on my Nehalem box. The \nmagic? I force the stores to the 512-bit hash bucket to be done in order. \nThat seems to help a lot.\n\nThe diff is trivial (on top of the \"rename registers with cpp\" patch), as \nappended. And it does seem to fix the P4 issues too, although I can \nobviously (once again) only test Prescott, and only in 64-bit mode:\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 1.662 36.73\n\trfc3174 1.64 37.22\n\tlinus 0.2523 241.9\n\tlinusas 0.4367 139.8\n\tlinusas2 0.4487 136\n\tmozilla 0.9704 62.9\n\tmozillaas 0.9399 64.94\n\nthat's some really impressive improvement. All from just saying \"do the \nstores in the order I told you to, dammit!\" to the compiler.\n\n\t\tLinus\n\n---\n block-sha1/sha1.c | 3 ++-\n 1 files changed, 2 insertions(+), 1 deletions(-)\n\ndiff --git a/block-sha1/sha1.c b/block-sha1/sha1.c\nindex 19dc41d..f70e1ba 100644\n--- a/block-sha1/sha1.c\n+++ b/block-sha1/sha1.c\n@@ -93,6 +93,7 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n \n /* This \"rolls\" over the 512-bit array */\n #define W(x) (array[(x)&15])\n+#define setW(x, val) (*(volatile unsigned int *)&W(x) = (val))\n \n /*\n * Where do we get the source from? The first 16 iterations get it from\n@@ -102,7 +103,7 @@ void blk_SHA1_Final(unsigned char hashout[20], blk_SHA_CTX *ctx)\n #define SHA_MIX(t) SHA_ROL(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1)\n \n #define SHA_ROUND(t, input, fn, constant, A, B, C, D, E) do { \\\n-\tunsigned int TEMP = input(t); W(t) = TEMP; \\\n+\tunsigned int TEMP = input(t); setW(t, TEMP); \\\n \tE += TEMP + SHA_ROL(A,5) + (fn) + (constant); \\\n \tB = SHA_ROR(B, 2); } while (0)\n \n"},{"id":"119953","messageId":"4A7D0E7B.3030601@gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908072107170.3288@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-08T05:34:51Z","receivedAt":"2009-08-08T05:34:51Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> I think I have found a way to avoid the gcc crazyness.\n> \n> Lookie here:\n> \n> \t# TIME[s] SPEED[MB/s]\n> \trfc3174 5.094 119.8\n> \trfc3174 5.098 119.7\n> \tlinus 1.462 417.5\n> \tlinusas 2.008 304\n> \tlinusas2 1.878 325\n> \tmozilla 5.566 109.6\n> \tmozillaas 5.866 104.1\n> \topenssl 1.609 379.3\n> \tspelvin 1.675 364.5\n> \tspelvina 1.601 381.3\n> \tnettle 1.591 383.6\n> \n> notice? I outperform all the hand-tuned asm on 32-bit too. By quite a \n> margin, in fact.\n> \n> Now, I didn't try a P4, and it's possible that it won't do that there, but \n> the 32-bit code generation sure looks impressive on my Nehalem box. The \n> magic? I force the stores to the 512-bit hash bucket to be done in order. \n> That seems to help a lot.\n\nI named it 'linusv':\n\nP4/i686:\n# TIME[s] SPEED[MB/s]\nrfc3174 1.456 41.92\nrfc3174 1.445 42.22\nlinus 0.5865 104.1\nlinusph 0.5643 108.2\nlinusv 0.3697 165.1\nlinusvph 0.3618 168.7\nlinusp4 0.4312 141.5\nlinusas 0.4091 149.2\nlinusas2 0.4364 139.9\nmozilla 1.102 55.37\nmozillaas 1.297 47.07\nopenssl 0.261 233.9\nopensslb 0.2395 254.9\nspelvin 0.2653 230\nnettle 0.438 139.4\n\nand when tuning for prescott:\n\nlinus 0.6544 93.27\nlinusph 0.6523 93.57\nlinusv 0.3439 177.5\nlinusvph 0.3547 172.1\nlinusp4 0.3585 170.3\n\nso it isn't as fast as the openssl asm ones, but it does win\nin the C category.\n\n> I outperform all the hand-tuned asm on 32-bit too. By quite a \n> margin, in fact.\n\nI've inlined the byteswapping in 'opensslb', maybe that one will\ndo a bit better.\n\nhttp://www.src.multimo.pl/YDpqIo7Li27O0L0h/sha1bench.tar.gz\n\nartur\n"},{"id":"119999","messageId":"alpine.LFD.2.01.0908081004560.3288@localhost.localdomain","threadId":"20441","inReplyTo":"4A7D0E7B.3030601@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-08T17:10:35Z","receivedAt":"2009-08-08T17:10:35Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 8 Aug 2009, Artur Skawina wrote:\n> \n> I've inlined the byteswapping in 'opensslb', maybe that one will\n> do a bit better.\n> \n> http://www.src.multimo.pl/YDpqIo7Li27O0L0h/sha1bench.tar.gz\n\nHmm. Testing on my atom, the inlined bswap is worse, but the asm versions \nare generally superior to any C one:\n\n\t# TIME[s] SPEED[MB/s]\n\trfc3174 2.194 27.82\n\trfc3174 2.19 27.87\n\tlinus 0.947 64.45\n\tlinusph 0.9381 65.06\n\tlinusv 0.8943 68.25\n\tlinusvph 0.8803 69.34\n\tlinusasm 0.9349 65.29\n\tlinusp4 1.006 60.66\n\tlinusas 1.062 57.48\n\tlinusas2 1.009 60.5\n\tmozilla 2.264 26.96\n\tmozillaas 2.197 27.78\n\topenssl 0.648 94.19\n\topensslb 0.7419 82.27\n\tspelvin 0.636 95.96\n\tspelvina 0.6671 91.49\n\tnettle 0.717 85.12\n\tnettle-ror 0.7137 85.52\n\tnettle-p4sch 0.7158 85.27\n\nInterestingly, -mtune=prescott does well for that 'linusv' version on atom \ntoo, and gets it up to\n\n\tlinusv 0.8365 72.96\n\nand it's the only one that improves. Odd interactions.\n\n\t\t\tLinus\n"},{"id":"120002","messageId":"4A7DC014.1030904@gmail.com","threadId":"20441","inReplyTo":"alpine.LFD.2.01.0908081004560.3288@localhost.localdomain","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-08T18:12:36Z","receivedAt":"2009-08-08T18:12:36Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> On Sat, 8 Aug 2009, Artur Skawina wrote:\n>> I've inlined the byteswapping in 'opensslb', maybe that one will\n>> do a bit better.\n> Hmm. Testing on my atom, the inlined bswap is worse, but the asm versions \n> are generally superior to any C one:\n\nIt loses on atom, but is the best one on both P3 and P4 here.\nBased on your other numbers I was expecting it to win on 32-bit\nnehalem too. gcc doing a better job of scheduling w/ 'linusv'\nwouldn't surprise though (since there are no spills, the data reads\nare about the only other thing that could make a difference. And, yes,\nthey show up in the profiles; if x86 only had one more register...)\n\nartur\n"},{"id":"120018","messageId":"4A7E030E.2040301@gmail.com","threadId":"20441","inReplyTo":"4A7D0E7B.3030601@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-08T22:58:22Z","receivedAt":"2009-08-08T22:58:22Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Artur Skawina wrote:\n> Linus Torvalds wrote:\n>> magic? I force the stores to the 512-bit hash bucket to be done in order. \n>> That seems to help a lot.\n> \n> I named it 'linusv':\n\n> linusv 0.3697 165.1\n\nI was not going to spend even more time on the C version, but after looking\nat what gcc does to it, tried this: \n\ndiff --git a/block-sha1/sha1vol.c b/block-sha1/sha1vol.c\n--- a/block-sha1/sha1vol.c\n+++ b/block-sha1/sha1vol.c\n@@ -93,7 +93,7 @@ void blk_SHA1_Finalv(unsigned char hashout[20], blk_SHA_CTX *ctx)\n \n /* This \"rolls\" over the 512-bit array */\n #define W(x) (array[(x)&15])\n-#define setW(x, val) (*(volatile unsigned int *)&W(x) = (val))\n+#define setW(x, val) W(x) = (val); __asm__ volatile (\"\": \"+m\" (W(x)))\n \n /*\n * Where do we get the source from? The first 16 iterations get it from\n\nand got a nice improvement:\n\nrfc3174 1.436 42.49\nlinus 0.5843 104.5\nlinusph 0.5639 108.2\nlinusv 0.3098 197\nlinusvph 0.3082 198.1\nlinusasm 0.5849 104.3\nlinusp4 0.433 141\nlinusas 0.4077 149.7\nlinusas2 0.436 140\nmozilla 1.099 55.54\nmozillaas 1.295 47.11\nopenssl 0.2632 231.9\nopensslb 0.2395 254.8\nspelvin 0.2687 227.2\nspelvina 0.2526 241.7\nnettle 0.4378 139.4\nnettle-ror 0.4379 139.4\nnettle-p4sch 0.4231 144.2\n\nThe atom numbers didn't change much.\n\nartur\n"},{"id":"120019","messageId":"4A7E0C0D.9060808@gmail.com","threadId":"20441","inReplyTo":"4A7E030E.2040301@gmail.com","subject":"Re: [PATCH 0/7] block-sha1: improved SHA1 hashing","fromName":"Artur Skawina","fromEmail":"art.08.09@gmail.com","sentAt":"2009-08-08T23:36:45Z","receivedAt":"2009-08-08T23:36:45Z","isPatch":true,"sender":{"key":"art.08.09@gmail.com","avatar":null},"body":"Artur Skawina wrote:\n> Artur Skawina wrote:\n\n> -#define setW(x, val) (*(volatile unsigned int *)&W(x) = (val))\n> +#define setW(x, val) W(x) = (val); __asm__ volatile (\"\": \"+m\" (W(x)))\n\nand w/ this on top:\n\ndiff --git a/block-sha1/sha1vol.c b/block-sha1/sha1vol.c\n--- a/block-sha1/sha1vol.c\n+++ b/block-sha1/sha1vol.c\n@@ -103,9 +103,9 @@ void blk_SHA1_Finalv(unsigned char hashout[20], blk_SHA_CTX *ctx)\n #define SHA_MIX(t) SHA_ROL(W(t+13) ^ W(t+8) ^ W(t+2) ^ W(t), 1)\n \n #define SHA_ROUND(t, input, fn, constant, A, B, C, D, E) do { \\\n-\tunsigned int TEMP = input(t); setW(t, TEMP); \\\n-\tE += TEMP + SHA_ROL(A,5) + (fn) + (constant); \\\n-\tB = SHA_ROR(B, 2); } while (0)\n+\tunsigned int TEMP = SHA_ROL(A,5); E+= (fn); \\\n+\tE += (constant) + TEMP; TEMP = input(t); setW(t, TEMP); \\\n+\tB = SHA_ROR(B, 2); E += TEMP; } while (0)\n \n #define T_0_15(t, A, B, C, D, E) SHA_ROUND(t, SHA_SRC, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )\n #define T_16_19(t, A, B, C, D, E) SHA_ROUND(t, SHA_MIX, (((C^D)&B)^D) , 0x5a827999, A, B, C, D, E )\n\nI see an improvement on atom and reach ~200M/s on P4 (i686).\n.\nWhen compiled w/ '-mtune=prescott':\n\nrfc3174 1.459 41.84\nlinus 0.6574 92.85\nlinusph 0.6613 92.29\nlinusv 0.2682 227.6\nlinusvph 0.2681 227.7\nlinusasm 0.5868 104\nlinusp4 0.3586 170.2\nlinusas 0.3795 160.8\nlinusas2 0.3583 170.3\nmozilla 1.171 52.11\nmozillaas 1.381 44.2\nopenssl 0.2623 232.7\nopensslb 0.2404 253.9\nspelvin 0.2659 229.6\nspelvina 0.2492 244.9\nnettle 0.4362 139.9\nnettle-ror 0.436 140\nnettle-p4sch 0.4204 145.2\n\nit's now just 2% slower than the openssl assembler version.\n\nartur\n"}]}