{"thread":{"id":"1886","subject":"[PATCH] ARM optimized SHA1 implementation","startedAt":"2005-09-20T16:27:13Z","lastAt":"2005-09-20T16:27:13Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"8999","messageId":"Pine.LNX.4.63.0509201149150.18381@localhost.localdomain","threadId":"1886","inReplyTo":null,"subject":"[PATCH] ARM optimized SHA1 implementation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-09-20T16:27:13Z","receivedAt":"2005-09-20T16:27:13Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This is my ARM assembly SHA1 implementation for GIT. It is approximately \n50% faster than the generic C version. On an XScale processor running at \n400MHz:\n\n\tgeneric C version:\t9.8 MB/s\n\tmy version:\t\t14.5 MB/s\n\nIt's not that I expect a lot of big GIT users on ARM, but I stillknow \nabout one important ARM user that might benefit from it, and writing \nthat code was fun.\n\nI also reworked the makefile a bit so any optimized SHA1 implementations \nis used regardless of whether NO_OPENSSL is defined or not.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\ndiff --git a/arm/sha1.c b/arm/sha1.c\nnew file mode 100644\n--- /dev/null\n+++ b/arm/sha1.c\n@@ -0,0 +1,82 @@\n+/*\n+ * SHA-1 implementation optimized for ARM\n+ *\n+ * Copyright:   (C) 2005 by Nicolas Pitre <nico@cam.org>\n+ * Created:     September 17, 2005\n+ */\n+\n+#include <string.h>\n+#include \"sha1.h\"\n+\n+extern void sha_transform(uint32_t *hash, const unsigned char *data, uint32_t *W);\n+\n+void SHA1_Init(SHA_CTX *c)\n+{\n+\tc->len = 0;\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+}\n+\n+void SHA1_Update(SHA_CTX *c, const void *p, unsigned long n)\n+{\n+\tuint32_t workspace[80];\n+\tunsigned int partial;\n+\tunsigned long done;\n+\n+\tpartial = c->len & 0x3f;\n+\tc->len += n;\n+\tif ((partial + n) >= 64) {\n+\t\tif (partial) {\n+\t\t\tdone = 64 - partial;\n+\t\t\tmemcpy(c->buffer + partial, p, done);\n+\t\t\tsha_transform(c->hash, c->buffer, workspace);\n+\t\t\tpartial = 0;\n+\t\t} else\n+\t\t\tdone = 0;\n+\t\twhile (n >= done + 64) {\n+\t\t\tsha_transform(c->hash, p + done, workspace);\n+\t\t\tdone += 64;\n+\t\t}\n+\t} else\n+\t\tdone = 0;\n+\tif (n - done)\n+\t\tmemcpy(c->buffer + partial, p + done, n - done);\n+}\n+\n+void SHA1_Final(unsigned char *hash, SHA_CTX *c)\n+{\n+\tuint64_t bitlen;\n+\tuint32_t bitlen_hi, bitlen_lo; \n+\tunsigned int i, offset, padlen;\n+\tunsigned char bits[8];\n+\tstatic const unsigned char padding[64] = { 0x80, };\n+\n+\tbitlen = c->len << 3;\n+\toffset = c->len & 0x3f;\n+\tpadlen = ((offset < 56) ? 56 : (64 + 56)) - offset;\n+\tSHA1_Update(c, padding, padlen);\n+\n+\tbitlen_hi = bitlen >> 32;\n+\tbitlen_lo = bitlen & 0xffffffff;\n+\tbits[0] = bitlen_hi >> 24;\n+\tbits[1] = bitlen_hi >> 16;\n+\tbits[2] = bitlen_hi >> 8;\n+\tbits[3] = bitlen_hi;\n+\tbits[4] = bitlen_lo >> 24;\n+\tbits[5] = bitlen_lo >> 16;\n+\tbits[6] = bitlen_lo >> 8;\n+\tbits[7] = bitlen_lo;\n+\tSHA1_Update(c, bits, 8); \n+\n+\tfor (i = 0; i < 5; i++) {\n+\t\tuint32_t v = c->hash[i];\n+\t\thash[0] = v >> 24;\n+\t\thash[1] = v >> 16;\n+\t\thash[2] = v >> 8;\n+\t\thash[3] = v;\n+\t\thash += 4;\n+\t}\n+}\ndiff --git a/arm/sha1.h b/arm/sha1.h\nnew file mode 100644\n--- /dev/null\n+++ b/arm/sha1.h\n@@ -0,0 +1,18 @@\n+/*\n+ * SHA-1 implementation optimized for ARM\n+ *\n+ * Copyright:\t(C) 2005 by Nicolas Pitre <nico@cam.org>\n+ * Created:\tSeptember 17, 2005\n+ */\n+\n+#include <stdint.h>\n+\n+typedef struct sha_context {\n+\tuint64_t len;\n+\tuint32_t hash[5];\n+\tunsigned char buffer[64];\n+} SHA_CTX;\n+\n+void SHA1_Init(SHA_CTX *c);\n+void SHA1_Update(SHA_CTX *c, const void *p, unsigned long n);\n+void SHA1_Final(unsigned char *hash, SHA_CTX *c);\ndiff --git a/arm/sha1_arm.S b/arm/sha1_arm.S\nnew file mode 100644\n--- /dev/null\n+++ b/arm/sha1_arm.S\n@@ -0,0 +1,184 @@\n+/*\n+ *  SHA transform optimized for ARM\n+ *\n+ *  Copyright:\t(C) 2005 by Nicolas Pitre <nico@cam.org>\n+ *  Created:\tSeptember 17, 2005\n+ *\n+ *  This program is free software; you can redistribute it and/or modify\n+ *  it under the terms of the GNU General Public License version 2 as\n+ *  published by the Free Software Foundation.\n+ */\n+\n+\t.text\n+\t.globl\tsha_transform\n+\n+/*\n+ * void sha_transform(uint32_t *hash, const unsigned char *data, uint32_t *W);\n+ *\n+ * note: the \"data\" pointer may be unaligned.\n+ */\n+\n+sha_transform:\n+\n+\tstmfd\tsp!, {r4 - r8, lr}\n+\n+\t@ for (i = 0; i < 16; i++)\n+\t@         W[i] = ntohl(((uint32_t *)data)[i]); */\n+\n+#ifdef __ARMEB__\n+\tmov\tr4, r0\n+\tmov\tr0, r2\n+\tmov\tr2, #64\n+\tbl\tmemcpy\n+\tmov\tr2, r0\n+\tmov\tr0, r4\n+#else\n+\tmov\tr3, r2\n+\tmov\tlr, #16\n+1:\tldrb\tr4, [r1], #1\n+\tldrb\tr5, [r1], #1\n+\tldrb\tr6, [r1], #1\n+\tldrb\tr7, [r1], #1\n+\tsubs\tlr, lr, #1\n+\torr\tr5, r5, r4, lsl #8\n+\torr\tr6, r6, r5, lsl #8\n+\torr\tr7, r7, r6, lsl #8\n+\tstr\tr7, [r3], #4\n+\tbne\t1b\n+#endif\n+\n+\t@ for (i = 0; i < 64; i++)\n+\t@         W[i+16] = ror(W[i+13] ^ W[i+8] ^ W[i+2] ^ W[i], 31);\n+\n+\tsub\tr3, r2, #4\n+\tmov\tlr, #64\n+2:\tldr\tr4, [r3, #4]!\n+\tsubs\tlr, lr, #1\n+\tldr\tr5, [r3, #8]\n+\tldr\tr6, [r3, #32]\n+\tldr\tr7, [r3, #52]\n+\teor\tr4, r4, r5\n+\teor\tr4, r4, r6\n+\teor\tr4, r4, r7\n+\tmov\tr4, r4, ror #31\n+\tstr\tr4, [r3, #64]\n+\tbne\t2b\n+\n+\t/*\n+\t * The SHA functions are:\n+\t *\n+\t * f1(B,C,D) = (D ^ (B & (C ^ D)))\n+\t * f2(B,C,D) = (B ^ C ^ D)\n+\t * f3(B,C,D) = ((B & C) | (D & (B | C)))\n+\t *\n+\t * Then the sub-blocks are processed as follows:\n+\t *\n+\t * A' = ror(A, 27) + f(B,C,D) + E + K + *W++\n+\t * B' = A\n+\t * C' = ror(B, 2)\n+\t * D' = C\n+\t * E' = D\n+\t *\n+\t * We therefore unroll each loop 5 times to avoid register shuffling.\n+\t * Also the ror for C (and also D and E which are successivelyderived\n+\t * from it) is applied in place to cut on an additional mov insn for\n+\t * each round.\n+\t */\n+\n+\t.macro\tsha_f1, A, B, C, D, E\n+\tldr\tr3, [r2], #4\n+\teor\tip, \\C, \\D\n+\tadd\t\\E, r1, \\E, ror #2\n+\tand\tip, \\B, ip, ror #2\n+\tadd\t\\E, \\E, \\A, ror #27\n+\teor\tip, ip, \\D, ror #2\n+\tadd\t\\E, \\E, r3\n+\tadd\t\\E, \\E, ip\n+\t.endm\n+\n+\t.macro\tsha_f2, A, B, C, D, E\n+\tldr\tr3, [r2], #4\n+\tadd\t\\E, r1, \\E, ror #2\n+\teor\tip, \\B, \\C, ror #2\n+\tadd\t\\E, \\E, \\A, ror #27\n+\teor\tip, ip, \\D, ror #2\n+\tadd\t\\E, \\E, r3\n+\tadd\t\\E, \\E, ip\n+\t.endm\n+\n+\t.macro\tsha_f3, A, B, C, D, E\n+\tldr\tr3, [r2], #4\n+\tadd\t\\E, r1, \\E, ror #2\n+\torr\tip, \\B, \\C, ror #2\n+\tadd\t\\E, \\E, \\A, ror #27\n+\tand\tip, ip, \\D, ror #2\n+\tadd\t\\E, \\E, r3\n+\tand\tr3, \\B, \\C, ror #2\n+\torr\tip, ip, r3\n+\tadd\t\\E, \\E, ip\n+\t.endm\n+\n+\tldmia\tr0, {r4 - r8}\n+\n+\tmov\tlr, #4\n+\tldr\tr1, .L_sha_K + 0\n+\n+\t/* adjust initial values */\n+\tmov\tr6, r6, ror #30\n+\tmov\tr7, r7, ror #30\n+\tmov\tr8, r8, ror #30\n+\n+3:\tsubs\tlr, lr, #1\n+\tsha_f1\tr4, r5, r6, r7, r8\n+\tsha_f1\tr8, r4, r5, r6, r7\n+\tsha_f1\tr7, r8, r4, r5, r6\n+\tsha_f1\tr6, r7, r8, r4, r5\n+\tsha_f1\tr5, r6, r7, r8, r4\n+\tbne\t3b\n+\n+\tldr\tr1, .L_sha_K + 4\n+\tmov\tlr, #4\n+\n+4:\tsubs\tlr, lr, #1\n+\tsha_f2\tr4, r5, r6, r7, r8\n+\tsha_f2\tr8, r4, r5, r6, r7\n+\tsha_f2\tr7, r8, r4, r5, r6\n+\tsha_f2\tr6, r7, r8, r4, r5\n+\tsha_f2\tr5, r6, r7, r8, r4\n+\tbne\t4b\n+\n+\tldr\tr1, .L_sha_K + 8\n+\tmov\tlr, #4\n+\n+5:\tsubs\tlr, lr, #1\n+\tsha_f3\tr4, r5, r6, r7, r8\n+\tsha_f3\tr8, r4, r5, r6, r7\n+\tsha_f3\tr7, r8, r4, r5, r6\n+\tsha_f3\tr6, r7, r8, r4, r5\n+\tsha_f3\tr5, r6, r7, r8, r4\n+\tbne\t5b\n+\n+\tldr\tr1, .L_sha_K + 12\n+\tmov\tlr, #4\n+\n+6:\tsubs\tlr, lr, #1\n+\tsha_f2\tr4, r5, r6, r7, r8\n+\tsha_f2\tr8, r4, r5, r6, r7\n+\tsha_f2\tr7, r8, r4, r5, r6\n+\tsha_f2\tr6, r7, r8, r4, r5\n+\tsha_f2\tr5, r6, r7, r8, r4\n+\tbne\t6b\n+\n+\tldmia\tr0, {r1, r2, r3, ip, lr}\n+\tadd\tr4, r1, r4\n+\tadd\tr5, r2, r5\n+\tadd\tr6, r3, r6, ror #2\n+\tadd\tr7, ip, r7, ror #2\n+\tadd\tr8, lr, r8, ror #2\n+\tstmia\tr0, {r4 - r8}\n+\n+\tldmfd\tsp!, {r4 - r8, pc}\n+\n+.L_sha_K:\n+\t.word\t0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xca62c1d6\n+\ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -12,6 +12,9 @@\n # Define PPC_SHA1 environment variable when running make to make use of\n # a bundled SHA1 routine optimized for PowerPC.\n #\n+# Define ARM_SHA1 environment variable when running make to make use of\n+# a bundled SHA1 routine optimized for ARM.\n+#\n # Define NEEDS_SSL_WITH_CRYPTO if you need -lcrypto with -lssl (Darwin).\n #\n # Define NEEDS_LIBICONV if linking with libc is not enough (Darwin).\n@@ -155,6 +158,10 @@ ifeq ($(shell uname -s),SunOS)\n \tPLATFORM_DEFINES += -D__EXTENSIONS__\n endif\n \n+ifneq (,$(findstring arm,$(shell uname -m)))\n+\tARM_SHA1 = YesPlease\n+endif\n+\n ifndef SHELL_PATH\n \tSHELL_PATH = /bin/sh\n endif\n@@ -183,18 +190,6 @@ ifdef NEEDS_LIBICONV\n else\n \tLIB_4_ICONV =\n endif\n-ifdef MOZILLA_SHA1\n-\tSHA1_HEADER = \"mozilla-sha1/sha1.h\"\n-\tLIB_OBJS += mozilla-sha1/sha1.o\n-else\n-\tifdef PPC_SHA1\n-\t\tSHA1_HEADER = \"ppc/sha1.h\"\n-\t\tLIB_OBJS += ppc/sha1.o ppc/sha1ppc.o\n-\telse\n-\t\tSHA1_HEADER = <openssl/sha.h>\n-\t\tLIBS += $(LIB_4_CRYPTO)\n-\tendif\n-endif\n ifdef NEEDS_SOCKET\n \tLIBS += -lsocket\n \tSIMPLE_LIB += -lsocket\n@@ -204,6 +199,24 @@ ifdef NEEDS_NSL\n \tSIMPLE_LIB += -lnsl\n endif\n \n+ifdef PPC_SHA1\n+\tSHA1_HEADER = \"ppc/sha1.h\"\n+\tLIB_OBJS += ppc/sha1.o ppc/sha1ppc.o\n+else\n+ifdef ARM_SHA1\n+\tSHA1_HEADER = \"arm/sha1.h\"\n+\tLIB_OBJS += arm/sha1.o arm/sha1_arm.o\n+else\n+ifdef MOZILLA_SHA1\n+\tSHA1_HEADER = \"mozilla-sha1/sha1.h\"\n+\tLIB_OBJS += mozilla-sha1/sha1.o\n+else\n+\tSHA1_HEADER = <openssl/sha.h>\n+\tLIBS += $(LIB_4_CRYPTO)\n+endif\n+endif\n+endif\n+\n DEFINES += '-DSHA1_HEADER=$(SHA1_HEADER)'\n \n SCRIPTS = $(patsubst %.sh,%,$(SCRIPT_SH)) \\\n"}]}