{"thread":{"id":"238","subject":"[PATCH] optimized SHA1 for powerpc","startedAt":"2005-04-22T05:52:25Z","lastAt":"2005-04-22T05:52:25Z","messageCount":1,"participants":["Paul Mackerras"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"1239","messageId":"17000.37145.799151.390802@cargo.ozlabs.ibm.com","threadId":"238","inReplyTo":null,"subject":"[PATCH] optimized SHA1 for powerpc","fromName":"Paul Mackerras","fromEmail":"paulus@samba.org","sentAt":"2005-04-22T05:52:25Z","receivedAt":"2005-04-22T05:52:25Z","isPatch":true,"sender":{"key":"paulus@samba.org","avatar":"https://avatars.githubusercontent.com/u/1606439?v=4"},"body":"Linus,\n\nJust for fun, I wrote a ppc-assembly SHA1 routine.  It appears to be\nabout 2.5x faster than the generic version.  It reduces the time for a\nfsck-cache on a linux-2.6 tree from ~6.8 seconds to ~6.0 seconds on my\nG4 powerbook.\n\nPaul.\n\ndiff -urN git.orig/Makefile git/Makefile\n--- git.orig/Makefile\t2005-04-22 15:21:10.000000000 +1000\n+++ git/Makefile\t2005-04-22 15:11:28.000000000 +1000\n@@ -25,7 +25,12 @@\n \n LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o\n LIB_FILE=libgit.a\n-LIB_H=cache.h object.h\n+LIB_H=cache.h object.h sha1.h\n+\n+arch := $(shell uname -m | tr -d 0-9)\n+ifeq ($(arch),ppc)\n+LIB_OBJS += sha1.o sha1ppc.o\n+endif\n \n $(LIB_FILE): $(LIB_OBJS)\n \t$(AR) rcs $@ $(LIB_OBJS)\ndiff -urN git.orig/cache.h git/cache.h\n--- git.orig/cache.h\t2005-04-22 15:21:10.000000000 +1000\n+++ git/cache.h\t2005-04-22 13:57:36.000000000 +1000\n@@ -12,7 +12,7 @@\n #include <sys/mman.h>\n #include <netinet/in.h>\n \n-#include <openssl/sha.h>\n+#include \"sha1.h\"\n #include <zlib.h>\n \n /*\ndiff -urN git.orig/sha1.c git/sha1.c\n--- /dev/null\t2005-04-04 12:56:19.000000000 +1000\n+++ git/sha1.c\t2005-04-22 15:17:27.000000000 +1000\n@@ -0,0 +1,72 @@\n+/*\n+ * SHA-1 implementation.\n+ *\n+ * Copyright (C) 2005 Paul Mackerras <paulus@samba.org>\n+ *\n+ * This version assumes we are running on a big-endian machine.\n+ * It calls an external sha1_core() to process blocks of 64 bytes.\n+ */\n+#include <stdio.h>\n+#include <string.h>\n+#include \"sha1.h\"\n+\n+extern void sha1_core(uint32_t *hash, const unsigned char *p,\n+\t\t      unsigned int nblocks);\n+\n+int SHA1_Init(SHA_CTX *c)\n+{\n+\tc->hash[0] = 0x67452301;\n+\tc->hash[1] = 0xEFCDAB89;\n+\tc->hash[2] = 0x98BADCFE;\n+\tc->hash[3] = 0x10325476;\n+\tc->hash[4] = 0xC3D2E1F0;\n+\tc->len = 0;\n+\tc->cnt = 0;\n+\treturn 0;\n+}\n+\n+int SHA1_Update(SHA_CTX *c, const void *ptr, unsigned long n)\n+{\n+\tunsigned long nb;\n+\tconst unsigned char *p = ptr;\n+\n+\tc->len += n << 3;\n+\twhile (n != 0) {\n+\t\tif (c->cnt || n < 64) {\n+\t\t\tnb = 64 - c->cnt;\n+\t\t\tif (nb > n)\n+\t\t\t\tnb = n;\n+\t\t\tmemcpy(&c->buf.b[c->cnt], p, nb);\n+\t\t\tif ((c->cnt += nb) == 64) {\n+\t\t\t\tsha1_core(c->hash, c->buf.b, 1);\n+\t\t\t\tc->cnt = 0;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tnb = n >> 6;\n+\t\t\tsha1_core(c->hash, p, nb);\n+\t\t\tnb <<= 6;\n+\t\t}\n+\t\tn -= nb;\n+\t\tp += nb;\n+\t}\n+\treturn 0;\n+}\t\n+\n+int SHA1_Final(unsigned char *hash, SHA_CTX *c)\n+{\n+\tunsigned int cnt = c->cnt;\n+\n+\tc->buf.b[cnt++] = 0x80;\n+\tif (cnt > 56) {\n+\t\tif (cnt < 64)\n+\t\t\tmemset(&c->buf.b[cnt], 0, 64 - cnt);\n+\t\tsha1_core(c->hash, c->buf.b, 1);\n+\t\tcnt = 0;\n+\t}\n+\tif (cnt < 56)\n+\t\tmemset(&c->buf.b[cnt], 0, 56 - cnt);\n+\tc->buf.l[7] = c->len;\n+\tsha1_core(c->hash, c->buf.b, 1);\n+\tmemcpy(hash, c->hash, 20);\n+\treturn 0;\n+}\ndiff -urN git.orig/sha1.h git/sha1.h\n--- /dev/null\t2005-04-04 12:56:19.000000000 +1000\n+++ git/sha1.h\t2005-04-22 15:06:53.000000000 +1000\n@@ -0,0 +1,19 @@\n+#ifndef __powerpc__\n+#include <openssl/sha.h>\n+#else\n+#include <stdint.h>\n+\n+typedef struct sha_context {\n+\tuint32_t hash[5];\n+\tuint32_t cnt;\n+\tuint64_t len;\n+\tunion {\n+\t\tunsigned char b[64];\n+\t\tuint64_t l[8];\n+\t} buf;\n+} SHA_CTX;\n+\n+int SHA1_Init(SHA_CTX *c);\n+int SHA1_Update(SHA_CTX *c, const void *p, unsigned long n);\n+int SHA1_Final(unsigned char *hash, SHA_CTX *c);\n+#endif\ndiff -urN git.orig/sha1ppc.S git/sha1ppc.S\n--- /dev/null\t2005-04-04 12:56:19.000000000 +1000\n+++ git/sha1ppc.S\t2005-04-22 15:18:19.000000000 +1000\n@@ -0,0 +1,185 @@\n+/*\n+ * SHA-1 implementation for PowerPC.\n+ *\n+ * Copyright (C) 2005 Paul Mackerras.\n+ */\n+#define FS\t80\n+\n+/*\n+ * We roll the registers for T, A, B, C, D, E around on each\n+ * iteration; T on iteration t is A on iteration t+1, and so on.\n+ * We use registers 7 - 12 for this.\n+ */\n+#define RT(t)\t((((t)+5)%6)+7)\n+#define RA(t)\t((((t)+4)%6)+7)\n+#define RB(t)\t((((t)+3)%6)+7)\n+#define RC(t)\t((((t)+2)%6)+7)\n+#define RD(t)\t((((t)+1)%6)+7)\n+#define RE(t)\t((((t)+0)%6)+7)\n+\n+/* We use registers 16 - 31 for the W values */\n+#define W(t)\t(((t)%16)+16)\n+\n+#define STEPD0(t)\t\t\t\t\\\n+\tand\t%r6,RB(t),RC(t);\t\t\\\n+\tandc\t%r0,RD(t),RB(t);\t\t\\\n+\trotlwi\tRT(t),RA(t),5;\t\t\t\\\n+\trotlwi\tRB(t),RB(t),30;\t\t\t\\\n+\tor\t%r6,%r6,%r0;\t\t\t\\\n+\tadd\t%r0,RE(t),%r15;\t\t\t\\\n+\tadd\tRT(t),RT(t),%r6;\t\t\\\n+\tadd\t%r0,%r0,W(t);\t\t\t\\\n+\tadd\tRT(t),RT(t),%r0\n+\n+#define STEPD1(t)\t\t\t\t\\\n+\txor\t%r6,RB(t),RC(t);\t\t\\\n+\trotlwi\tRT(t),RA(t),5;\t\t\t\\\n+\trotlwi\tRB(t),RB(t),30;\t\t\t\\\n+\txor\t%r6,%r6,RD(t);\t\t\t\\\n+\tadd\t%r0,RE(t),%r15;\t\t\t\\\n+\tadd\tRT(t),RT(t),%r6;\t\t\\\n+\tadd\t%r0,%r0,W(t);\t\t\t\\\n+\tadd\tRT(t),RT(t),%r0\n+\n+#define STEPD2(t)\t\t\t\t\\\n+\tand\t%r6,RB(t),RC(t);\t\t\\\n+\tand\t%r0,RB(t),RD(t);\t\t\\\n+\trotlwi\tRT(t),RA(t),5;\t\t\t\\\n+\trotlwi\tRB(t),RB(t),30;\t\t\t\\\n+\tor\t%r6,%r6,%r0;\t\t\t\\\n+\tand\t%r0,RC(t),RD(t);\t\t\\\n+\tor\t%r6,%r6,%r0;\t\t\t\\\n+\tadd\t%r0,RE(t),%r15;\t\t\t\\\n+\tadd\tRT(t),RT(t),%r6;\t\t\\\n+\tadd\t%r0,%r0,W(t);\t\t\t\\\n+\tadd\tRT(t),RT(t),%r0\n+\n+#define LOADW(t)\t\t\t\t\\\n+\tlwz\tW(t),(t)*4(%r4)\n+\n+#define UPDATEW(t)\t\t\t\t\\\n+\txor\t%r0,W((t)-3),W((t)-8);\t\t\\\n+\txor\tW(t),W((t)-16),W((t)-14);\t\\\n+\txor\tW(t),W(t),%r0;\t\t\t\\\n+\trotlwi\tW(t),W(t),1\n+\n+#define STEP0LD4(t)\t\t\t\t\\\n+\tSTEPD0(t);   LOADW((t)+4);\t\t\\\n+\tSTEPD0((t)+1); LOADW((t)+5);\t\t\\\n+\tSTEPD0((t)+2); LOADW((t)+6);\t\t\\\n+\tSTEPD0((t)+3); LOADW((t)+7)\n+\n+#define STEPUP4(t, fn)\t\t\t\t\\\n+\tSTEP##fn(t);   UPDATEW((t)+4);\t\t\\\n+\tSTEP##fn((t)+1); UPDATEW((t)+5);\t\\\n+\tSTEP##fn((t)+2); UPDATEW((t)+6);\t\\\n+\tSTEP##fn((t)+3); UPDATEW((t)+7)\n+\n+#define STEPUP20(t, fn)\t\t\t\t\\\n+\tSTEPUP4(t, fn);\t\t\t\t\\\n+\tSTEPUP4((t)+4, fn);\t\t\t\\\n+\tSTEPUP4((t)+8, fn);\t\t\t\\\n+\tSTEPUP4((t)+12, fn);\t\t\t\\\n+\tSTEPUP4((t)+16, fn)\n+\n+\t.globl\tsha1_core\n+sha1_core:\n+\tstwu\t%r1,-FS(%r1)\n+\tstw\t%r15,FS-68(%r1)\n+\tstw\t%r16,FS-64(%r1)\n+\tstw\t%r17,FS-60(%r1)\n+\tstw\t%r18,FS-56(%r1)\n+\tstw\t%r19,FS-52(%r1)\n+\tstw\t%r20,FS-48(%r1)\n+\tstw\t%r21,FS-44(%r1)\n+\tstw\t%r22,FS-40(%r1)\n+\tstw\t%r23,FS-36(%r1)\n+\tstw\t%r24,FS-32(%r1)\n+\tstw\t%r25,FS-28(%r1)\n+\tstw\t%r26,FS-24(%r1)\n+\tstw\t%r27,FS-20(%r1)\n+\tstw\t%r28,FS-16(%r1)\n+\tstw\t%r29,FS-12(%r1)\n+\tstw\t%r30,FS-8(%r1)\n+\tstw\t%r31,FS-4(%r1)\n+\n+\t/* Load up A - E */\n+\tlwz\tRA(0),0(%r3)\t/* A */\n+\tlwz\tRB(0),4(%r3)\t/* B */\n+\tlwz\tRC(0),8(%r3)\t/* C */\n+\tlwz\tRD(0),12(%r3)\t/* D */\n+\tlwz\tRE(0),16(%r3)\t/* E */\n+\n+\tmtctr\t%r5\n+\n+1:\tLOADW(0)\n+\tLOADW(1)\n+\tLOADW(2)\n+\tLOADW(3)\n+\n+\tlis\t%r15,0x5a82\t/* K0-19 */\n+\tori\t%r15,%r15,0x7999\n+\tSTEP0LD4(0)\n+\tSTEP0LD4(4)\n+\tSTEP0LD4(8)\n+\tSTEPUP4(12, D0)\n+\tSTEPUP4(16, D0)\n+\n+\tlis\t%r15,0x6ed9\t/* K20-39 */\n+\tori\t%r15,%r15,0xeba1\n+\tSTEPUP20(20, D1)\n+\n+\tlis\t%r15,0x8f1b\t/* K40-59 */\n+\tori\t%r15,%r15,0xbcdc\n+\tSTEPUP20(40, D2)\n+\n+\tlis\t%r15,0xca62\t/* K60-79 */\n+\tori\t%r15,%r15,0xc1d6\n+\tSTEPUP4(60, D1)\n+\tSTEPUP4(64, D1)\n+\tSTEPUP4(68, D1)\n+\tSTEPUP4(72, D1)\n+\tSTEPD1(76)\n+\tSTEPD1(77)\n+\tSTEPD1(78)\n+\tSTEPD1(79)\n+\n+\tlwz\t%r20,16(%r3)\n+\tlwz\t%r19,12(%r3)\n+\tlwz\t%r18,8(%r3)\n+\tlwz\t%r17,4(%r3)\n+\tlwz\t%r16,0(%r3)\n+\tadd\t%r20,RE(80),%r20\n+\tadd\tRD(0),RD(80),%r19\n+\tadd\tRC(0),RC(80),%r18\n+\tadd\tRB(0),RB(80),%r17\n+\tadd\tRA(0),RA(80),%r16\n+\tmr\tRE(0),%r20\n+\tstw\tRA(0),0(%r3)\n+\tstw\tRB(0),4(%r3)\n+\tstw\tRC(0),8(%r3)\n+\tstw\tRD(0),12(%r3)\n+\tstw\tRE(0),16(%r3)\n+\n+\taddi\t%r4,%r4,64\n+\tbdnz\t1b\n+\n+\tlwz\t%r15,FS-68(%r1)\n+\tlwz\t%r16,FS-64(%r1)\n+\tlwz\t%r17,FS-60(%r1)\n+\tlwz\t%r18,FS-56(%r1)\n+\tlwz\t%r19,FS-52(%r1)\n+\tlwz\t%r20,FS-48(%r1)\n+\tlwz\t%r21,FS-44(%r1)\n+\tlwz\t%r22,FS-40(%r1)\n+\tlwz\t%r23,FS-36(%r1)\n+\tlwz\t%r24,FS-32(%r1)\n+\tlwz\t%r25,FS-28(%r1)\n+\tlwz\t%r26,FS-24(%r1)\n+\tlwz\t%r27,FS-20(%r1)\n+\tlwz\t%r28,FS-16(%r1)\n+\tlwz\t%r29,FS-12(%r1)\n+\tlwz\t%r30,FS-8(%r1)\n+\tlwz\t%r31,FS-4(%r1)\n+\taddi\t%r1,%r1,FS\n+\tblr\n"}]}