{"thread":{"id":"20624","subject":"Re: Linus' sha1 is much faster!","startedAt":"2009-08-17T07:23:15Z","lastAt":"2009-08-17T23:12:08Z","messageCount":7,"participants":["George Spelvin","Nicolas Pitre","Paolo Bonzini"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"120836","messageId":"20090817072315.4314.qmail@science.horizon.com","threadId":"20624","inReplyTo":null,"subject":"Re: Linus' sha1 is much faster!","fromName":"George Spelvin","fromEmail":"linux@horizon.com","sentAt":"2009-08-17T07:23:15Z","receivedAt":"2009-08-17T07:23:15Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"If it helps anyone resolve license issues, here's a from-FIPS-180-2\nimplementation that's placed in the public domain.  That should be\ncompatible with any license.\n\nIt uses Linus's and Artur's performance ideas, and some of Linus' macro\nideas (in the rotate implementation), but tries to be textually different.\nIs there anything recognizable that anyone cares to clam copyright to?\n\nIt's not quite 100% finished, as I haven't benchmarked it against Linus's\ncode yet, but it's functionally correct.\n\nIt's also clean with -W -Wall -Wextra.\n\nTODO: Check if an initial copy to w[] is faster on i386 (less register\npressure).\n\n/*\n * Secure Hash Algorith SHA-1, as published in FIPS PUB 180-2.\n *\n * This implementation is in the public domain.  Copyright abandoned.\n * You may do anything you like with it, including evil things.\n *\n * This is a rewrite from scratch, based on Linus Torvalds' \"block-sha1\"\n * from the git mailing list (August, 2009).  Additional optimization\n * ideas cribbed from\n * - Artur Skawina (x86, particularly P4, and much benchmarking)\n * - Nicilas Pitre (ARM)\n */\n\n/* Cut here for sha1.h */\n#include <stddef.h>\t/* For size_t */\n#include <stdint.h>\t/* For uint32_t, uint64_t */\n\ntypedef struct SHA_context {\n\tuint64_t len;\t\t/* May be shrunk to uint32_t */\n\tuint32_t iv[5];\n\tunsigned char buf[64];\t\t/* Must be 32-bit aligned */\n} SHA_CTX;\n\nvoid SHA1_Init(struct SHA_context *c);\nvoid SHA1_Update(struct SHA_context *c, void const *p, size_t n);\nvoid SHA1_Final(unsigned char hash[20], struct SHA_context *c);\n/* End of sha1.h */\n\n#include <string.h>\t/* For memcpy() */\n#include <arpa/inet.h>\t/* For ntohl() */\n\nstatic void sha1_core(uint32_t iv[5], unsigned char const *p, size_t nblocks);\n\n/* Machine specific hacks */\n#if defined(__i386__) || defined(__x86_64__) || defined (__ppc__) || \\\n    defined(__ppc64__) || defined(__powerpc__) || defined (__powerpc64__) || \\\n    defined(__s390__) || defined(__s390x__)\n/* Unaligned access is okay */\nstatic inline uint32_t get_be32(unsigned char const *p)\n{\n\treturn ntohl(*(uint32_t const *)p);\n}\nstatic inline void put_be32(unsigned char const *p, uint32_t v)\n{\n\t*(uint32_t *)p = htonl(v);\n}\n\n#else\n/* Unaligned access is not okay; do conversion as byte fetches */\nstatic inline uint32_t get_be32(unsigned char const *p)\n{\n\treturn p[0] << 24 || p[1] << 16 | p[8] << 8 | p[3];\n}\nstatic inline void put_be32(unsigned char const *p, uint32_t v)\n{\n\tp[0] = v >> 24;\n\tp[1] = v >> 16;\n\tp[2] = v >> 8;\n\tp[3] = v;\n}\n#endif\n\nvoid SHA1_Init(struct SHA_context *c)\n{\n\t/* This is a prefix of the SHA_context structure */\n\tstatic struct {\n\t\tuint64_t len;\n\t\tuint32_t iv[5];\n\t} const iv = { 0,\n\t\t{ 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0 }\n\t};\n\n\tmemcpy(c, &iv, sizeof iv);\n}\n\nvoid SHA1_Update(struct SHA_context *c, void const *p, size_t n)\n{\n\tsize_t pos = c->len & 63;\t/* Offset into current input block */\n\n\tc->len += n;\n\n\t/* Initial partial block (if any) */\n\tif (pos) {\n\t\tsize_t space = 63 - pos;\n\t\tif (n < space)\n\t\t\tgoto end;\n\t\tmemcpy(c->buf + pos, p, space);\n\t\tsha1_core(c->iv, c->buf, 1);\n\t\tn -= space;\n\t\tp = (char const *)p + space;\n\t}\n\n\t/* The large middle piece */\n\tif (n >> 6) {\n\t\tsha1_core(c->iv, p, n >> 6);\n\t\tp = (char const *)p + (n & -(size_t)64);\n\t\tn &= 63;\n\t}\n\tpos = 0;\nend:\n\t/* Final partial block (may be zero size) */\n\tmemcpy(c->buf + pos, p, n);\n}\n\nvoid SHA1_Final(unsigned char hash[20], struct SHA_context *c)\n{\n\tsize_t pos = c->len & 63;\n\tunsigned i;\n\n\t/* Append a single 1 bit */\n\tc->buf[pos++] = 0x80;\n\n\t/* Append 0 bits until 64 bits remain in a block */\n\tif (pos > 56) {\n\t\tmemset(c->buf + pos, 0, 64 - pos);\n\t\tsha1_core(c->iv, c->buf, 1);\n\t\tpos = 0;\n\t}\n\tmemset(c->buf + pos, 0, 56 - pos);\n\n\t/* Append total input length in bits */\n\t((uint32_t *)c->buf)[14] = htonl((uint32_t)(c->len >> 29));\n\t((uint32_t *)c->buf)[15] = htonl((uint32_t)c->len << 3);\n\n\t/* Final hash round */\n\tsha1_core(c->iv, c->buf, 1);\n\n\t/* Copy hash result out */\n\tfor (i = 0; i < 5; i++)\n\t\tput_be32(hash + 4*i, c->iv[i]);\n}\n\n\n/*\n * Helper macros for sha1_core function.  To avoid clutter, these macros\n * are NOT fully parenthesized if it doesn't matter to the actual use.\n */\n\n#if __GNUC__ && (defined(__i386__) || defined(__x86_64__))\n/*\n * GCC by itself only generates left rotates.  Use right rotates if\n * possible to be kinder to dinky implementations with iterative rotate\n * instructions.\n */\n#define ROT(op, x, k) \\\n\t({ uint32_t y; asm(op \" %1,%0\" : \"=r\" (y) : \"I\" (k), \"0\" (x)); y; })\n#define ROL(x,k) ROT(\"roll\", x, k)\n#define ROR(x,k) ROT(\"rorl\", x, k)\n\n#else\n/* Generic C equivalent */\n#define ROT(x,l,r) ((x) << (l) | (x) >> (r))\n#define ROL(x,k) ROT(x,k,32-(k))\n#define ROR(x,k) ROT(x,32-(k),k)\n#endif\n\n\n/*\n * An important temporary array in SHA-1 is the working array W[],\n * which holds a scheduled key word per round.  Only the last 16 words\n * are relevant, so only use 16 words...\n */\n#define W(i) w[(i) & 15]\n\n/*\n * If you have a small register set, it helps GCC to force stores to\n * the w[] array to memory.  Given 22 or more registers (e.g. PowerPC),\n * GCC can map the entire w[] array to registers and this becomes\n * counterproductive.\n *\n * The optimal kludge seems to differ between x86 and ARM.  On the latter,\n * forcing a full memory barrier is required to stop GCC from splitting\n * live ranges for each round and generating a separate stack slot for\n * each.  (Which produces a huge stack frame and kills performance.)\n */\n#if defined(__i386__) || defined(__x86_64__)\n#define STORE(i, x) *(volatile uint32_t *)&W(i) = x\n#elif __GNUC__ && defined(__arm__)\n#define STORE(i, x) W(i) = x; __asm__(\"\":::\"memory\")\n#else\n#define STORE(i, x) W(i) = x\n#endif\n\n\n/* The three round functions.  F2 is also used as F4 */\n#define F1(b,c,d) (((d ^ c) & b) ^ d)\t\t/* Bitwise b ? c : d */\n#define F2(b,c,d) (d ^ c ^ b)\t\t\t/* Even parity */\n#define F3(b,c,d) (d & c) + ((d ^ c) & b)\t/* Majority function */\n\n/* The four round constants */\n#define K1 0x5a827999\t/* 2^30 * sqrt(2) */\n#define K2 0x6ed9eba1\t/* 2^30 * sqrt(3) */\n#define K3 0x8f1bbcdc\t/* 2^30 * sqrt(5) */\n#define K4 0xca62c1d6\t/* 2^30 * sqrt(10) */\n\n/* Rounds 0..15 fetch a word from the input */\n#define FETCH(t,i)\tt = get_be32(p + 4*(i)); STORE(i,t)\n/* Rounds 16..79 mix previous words to get a new one */\n#define MIX(t,i)\tt = W(i) ^ W(i+2) ^ W(i+8) ^ W(i+13); t = ROL(t, 1)\n/* Rounds 16..76 have to store back the result */\n#define CALC(t,i)\tMIX(t,i); STORE(i,t)\n\n/* The basic SHA-1 round */\n#define SHA_ROUND(a,b,c,d,e,f,k,src,t,i)\t\\\n\tsrc(t,i);\t\t\t\t\\\n\te += t + f(b,c,d) + k + ROL(a,5);\t\\\n\tb = ROR(b,2)\n\n/* An aligned group of 5 rounds */\n#define SHA_ROUND5(f,k,src,t,i) \\\n\tSHA_ROUND(a,b,c,d,e, f,k,src,t,i);\t\\\n\tSHA_ROUND(e,a,b,c,d, f,k,src,t,i+1);\t\\\n\tSHA_ROUND(d,e,a,b,c, f,k,src,t,i+2);\t\\\n\tSHA_ROUND(c,d,e,a,b, f,k,src,t,i+3);\t\\\n\tSHA_ROUND(b,c,d,e,a, f,k,src,t,i+4)\n\n/*\n * The core SHA-1 transform.\n *\n * iv[5] = Current SHA-1 hash state.\n * p = Pointer to source data.  Not necessarily aligned.\n * nblocks = Number of 64-byte blocks at p.  Guaranteed non-zero.\n */\nstatic void\nsha1_core(uint32_t iv[5], unsigned char const *p, size_t nblocks)\n{\n\tuint32_t e = iv[4], d = iv[3], c = iv[2], b = iv[1], a = iv[0];\n\tuint32_t w[16];\n\n\tdo {\n\t\tuint32_t t;\n\n\t\tSHA_ROUND5(F1, K1, FETCH, t,  0);\n\t\tSHA_ROUND5(F1, K1, FETCH, t,  5);\n\t\tSHA_ROUND5(F1, K1, FETCH, t, 10);\n\t\tSHA_ROUND(a,b,c,d,e, F1, K1, FETCH, t, 15);\n\t\tSHA_ROUND(e,a,b,c,d, F1, K1, CALC, t, 16);\n\t\tSHA_ROUND(d,e,a,b,c, F1, K1, CALC, t, 17);\n\t\tSHA_ROUND(c,d,e,a,b, F1, K1, CALC, t, 18);\n\t\tSHA_ROUND(b,c,d,e,a, F1, K1, CALC, t, 19);\n\n\t\tSHA_ROUND5(F2, K2, CALC, t, 20);\n\t\tSHA_ROUND5(F2, K2, CALC, t, 25);\n\t\tSHA_ROUND5(F2, K2, CALC, t, 30);\n\t\tSHA_ROUND5(F2, K2, CALC, t, 35);\n\n\t\tSHA_ROUND5(F3, K3, CALC, t, 40);\n\t\tSHA_ROUND5(F3, K3, CALC, t, 45);\n\t\tSHA_ROUND5(F3, K3, CALC, t, 50);\n\t\tSHA_ROUND5(F3, K3, CALC, t, 55);\n\n\t\tSHA_ROUND5(F2, K4, CALC, t, 60);\n\t\tSHA_ROUND5(F2, K4, CALC, t, 65);\n\t\tSHA_ROUND5(F2, K4, CALC, t, 70);\n\n\t\tSHA_ROUND(a,b,c,d,e, F2, K4, CALC, t, 75);\n\t\tSHA_ROUND(e,a,b,c,d, F2, K4, CALC, t, 76);\n\t\t/* Last 3 rounds don't need to store mixed value */\n\t\tSHA_ROUND(d,e,a,b,c, F2, K4, MIX, t, 77);\n\t\tSHA_ROUND(c,d,e,a,b, F2, K4, MIX, t, 78);\n\t\tSHA_ROUND(b,c,d,e,a, F2, K4, MIX, t, 79);\n\n\t\tiv[4] = e += iv[4];\n\t\tiv[3] = d += iv[3];\n\t\tiv[2] = c += iv[2];\n\t\tiv[1] = b += iv[1];\n\t\tiv[0] = a += iv[0];\n\t} while (--nblocks);\n}\n\n\n/* Compile with -DUNITTEST for self-tests */\n#if UNITTEST\n\n#include <stdio.h>\n\n/* Known answer test */\nstatic void katest(char const *text, size_t len, unsigned char const hash[20])\n{\n\tSHA_CTX c;\n\tunsigned char hash2[20];\n\tint i;\n\n\tSHA1_Init(&c);\n\tSHA1_Update(&c, text, len);\n\tSHA1_Final(hash2, &c);\n\n\tfor (i = 0; i < 20; i++)\n\t\tif (hash[i] != hash2[i])\n\t\t\tgoto mismatch;\n\tprintf(\"%u-byte known answer test PASSED\\n\", len);\n\treturn;\n\nmismatch:\n\tprintf(\"%u-byte known answer test FAILED:\\n\", len);\n\tprintf(\"Input: \\\"%.*s\\\"\\n\", len, text);\n\tprintf(\"Computed:\");\n\tfor (i = 0; i < 20; i++)\n\t\tprintf(\" %02x\", hash2[i]);\n\tprintf(\"\\nExpected:\");\n\tfor (i = 0; i < 20; i++)\n\t\tprintf(\" %02x\", hash[i]);\n\tputchar('\\n');\n}\n\nint\nmain(void)\n{\n\t/* FIPS PUB 180.1 example A.1 */\n\tstatic char const text1[3] = \"abc\";\n\tstatic unsigned char const hash1[20] = {\n\t\t0xa9, 0x99, 0x3e, 0x36, 0x47, 0x06, 0x81, 0x6a, 0xba, 0x3e,\n\t\t0x25, 0x71, 0x78, 0x50, 0xc2, 0x6c, 0x9c, 0xd0, 0xd8, 0x9d };\n\n\t/* FIPS PUB 180.1 example A.2 */\n\tstatic char const text2[56] =\n\t\t\"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq\";\n\tstatic unsigned char const hash2[20] = {\n\t\t0x84, 0x98, 0x3e, 0x44, 0x1c, 0x3b, 0xd2, 0x6e, 0xba, 0xae,\n\t\t0x4a, 0xa1, 0xf9, 0x51, 0x29, 0xe5, 0xe5, 0x46, 0x70, 0xf1 };\n\n\tkatest(text1, sizeof text1, hash1);\n\tkatest(text2, sizeof text2, hash2);\n\n\treturn 0;\n}\n#endif\n"},{"id":"120890","messageId":"alpine.LFD.2.00.0908171008070.6044@xanadu.home","threadId":"20624","inReplyTo":"20090817072315.4314.qmail@science.horizon.com","subject":"Re: Linus' sha1 is much faster!","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-17T14:20:22Z","receivedAt":"2009-08-17T14:20:22Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 17 Aug 2009, George Spelvin wrote:\n\n> If it helps anyone resolve license issues, here's a from-FIPS-180-2\n> implementation that's placed in the public domain.  That should be\n> compatible with any license.\n> \n> It uses Linus's and Artur's performance ideas, and some of Linus' macro\n> ideas (in the rotate implementation), but tries to be textually different.\n> Is there anything recognizable that anyone cares to clam copyright to?\n> \n> It's not quite 100% finished, as I haven't benchmarked it against Linus's\n> code yet, but it's functionally correct.\n> \n> It's also clean with -W -Wall -Wextra.\n> \n> TODO: Check if an initial copy to w[] is faster on i386 (less register\n> pressure).\n> \n> /*\n>  * Secure Hash Algorith SHA-1, as published in FIPS PUB 180-2.\n>  *\n>  * This implementation is in the public domain.  Copyright abandoned.\n>  * You may do anything you like with it, including evil things.\n>  *\n>  * This is a rewrite from scratch, based on Linus Torvalds' \"block-sha1\"\n>  * from the git mailing list (August, 2009).  Additional optimization\n>  * ideas cribbed from\n>  * - Artur Skawina (x86, particularly P4, and much benchmarking)\n>  * - Nicilas Pitre (ARM)\n\nPlease be careful to spell my name correctly.\n\n\nNicolas\n"},{"id":"120940","messageId":"alpine.LFD.2.00.0908171228570.6044@xanadu.home","threadId":"20624","inReplyTo":"20090817072315.4314.qmail@science.horizon.com","subject":"Re: Linus' sha1 is much faster!","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-17T17:06:45Z","receivedAt":"2009-08-17T17:06:45Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 17 Aug 2009, George Spelvin wrote:\n\n> If it helps anyone resolve license issues, here's a from-FIPS-180-2\n> implementation that's placed in the public domain.  That should be\n> compatible with any license.\n> \n> It uses Linus's and Artur's performance ideas, and some of Linus' macro\n> ideas (in the rotate implementation), but tries to be textually different.\n> Is there anything recognizable that anyone cares to clam copyright to?\n\nI don't think this trick of making source code textually different from \nanother work while still intimately mimicking the same structure entitles \nyou to any copyright (or non copyright) claims over that other work.  I \ncertainly wouldn't bet any dime for this standing up in court.  \nOtherwise anyone could grab any copyrighted source code and perform a \nbunch of search-and-replace ops on it, and maybe some code reordering \nfor good measure, to be able to claim own copyright on it. It is \nprobably much safer to simply ask the people involved to agree with your \nrelicensing.  And so far I don't see anyone with a stake in this \nfiercely wanting to stick to a particular license.\n\n> It's not quite 100% finished, as I haven't benchmarked it against Linus's\n> code yet, but it's functionally correct.\n> \n> It's also clean with -W -Wall -Wextra.\n\nNot if you try with the unaligned put_be32() as the destination pointer \nis marked const.\n\nAs to the actual result on ARM... Well, the assembly _looks_ much worse \nthan Linus' version.  It uses a stack frame of 152 bytes instead of 64 \nbytes.  The resulting binary is also 6868 bytes large compared to 6180 \nbytes.  Surprisingly, the performance is not that bad (the reason for \nthe underlined \"looks\" above) albeit still a bit worse, like 5% slower.  \nI was expecting much worse than that.\n\nOne possible reason for the bad assembly is probably due to the fact \nthat gcc is not smart enough to propagate constant address offsets \nacross different pointer types.  For example, my first version of \nget_be32() was a macro that did this:\n\n#define SHA_SRC(t) \\\n  ({ unsigned char *__d = (unsigned char *)&data[t]; \\\n     (__d[0] << 24) | (__d[1] << 16) | (__d[2] << 8) | (__d[3] << 0); })\n\nWith such a construct, gcc would always allocate a register to hold __d \nand then dereference that with an offset from 0 to 3.  Whereas:\n\n#define SHA_SRC(t) \\\n   ({   unsigned char *__d = (unsigned char *)data; \\\n        (__d[(t)*4 + 0] << 24) | (__d[(t)*4 + 1] << 16) | \\\n        (__d[(t)*4 + 2] <<  8) | (__d[(t)*4 + 3] <<  0); })\n\ndoes produce optimal assembly as only the register holding the data \npointer is dereferenced with the absolute byte offset.  I suspect your \nusage of inline functions has the same effect as the first SHA_SRC \ndefinition above.\n\nAlso, wrt skipping the last 3 write back to the 16 word array...  For \nall the (limited) attempts I've made so far to do that, it always ended \nup making things worse.  I've yet to investigate why though.\n\n\nNicolas\n"},{"id":"120946","messageId":"4A899152.8070607@gnu.org","threadId":"20624","inReplyTo":"alpine.LFD.2.00.0908171228570.6044@xanadu.home","subject":"Re: Linus' sha1 is much faster!","fromName":"Paolo Bonzini","fromEmail":"bonzini@gnu.org","sentAt":"2009-08-17T17:20:18Z","receivedAt":"2009-08-17T17:20:18Z","isPatch":false,"sender":{"key":"bonzini@gnu.org","avatar":"https://avatars.githubusercontent.com/u/42082?v=4"},"body":"> my first version of\n> get_be32() was a macro that did this:\n>\n> #define SHA_SRC(t) \\\n>    ({ unsigned char *__d = (unsigned char *)&data[t]; \\\n>       (__d[0]<<  24) | (__d[1]<<  16) | (__d[2]<<  8) | (__d[3]<<  0); })\n>\n> With such a construct, gcc would always allocate a register to hold __d\n> and then dereference that with an offset from 0 to 3.  Whereas:\n>\n> #define SHA_SRC(t) \\\n>     ({   unsigned char *__d = (unsigned char *)data; \\\n>          (__d[(t)*4 + 0]<<  24) | (__d[(t)*4 + 1]<<  16) | \\\n>          (__d[(t)*4 + 2]<<   8) | (__d[(t)*4 + 3]<<   0); })\n>\n> does produce optimal assembly as only the register holding the data\n> pointer is dereferenced with the absolute byte offset.  I suspect your\n> usage of inline functions has the same effect as the first SHA_SRC\n> definition above.\n\nYes, that's what happens.\n\nPaolo\n"},{"id":"120959","messageId":"20090817185448.30254.qmail@science.horizon.com","threadId":"20624","inReplyTo":"alpine.LFD.2.00.0908171228570.6044@xanadu.home","subject":"Re: Linus' sha1 is much faster!","fromName":"George Spelvin","fromEmail":"linux@horizon.com","sentAt":"2009-08-17T18:54:48Z","receivedAt":"2009-08-17T18:54:48Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> I don't think this trick of making source code textually different from \n> another work while still intimately mimicking the same structure entitles \n> you to any copyright (or non copyright) claims over that other work.  I \n> certainly wouldn't bet any dime for this standing up in court.  \n\n<div type=\"legal digression\">\nActually, I would.  I did a lot more than text search and replace;\nI re-implemented it from FIPS 180-2 (work of U.S. government, no copyright)\nand then merged in the *ideas* from the mailing list.  \n\n(And from elsewhere; the idea of a five-round macro is from Brian Gladman.)\n\nRemember, to the extent that something is *functional*, it is not\ncopyrightable; copyright only covers the non-functional expressive bits.\nThe vast majority of that code is simply required by the standard,\nor the desired calling interface.\n\nFor a large portion of the rest, remember that standard programming\nconventions (e.g.  brace style, macro names IN CAPS, etc.) that's also\nnon-copyrightable \"scene a faire\" material.\n\nIt's well established that paraphrasing a recipe avoids copyright;\nthe proportions and treatment of the ingredients is not copyrightable.\n\nFor more details, see the extensive coverage of the NEC v. Intel decision\n(1989) regarding the firmware for NEC's 8086-clone V20 microprocessor.\nIt was found non-infringing despite non-clean-room implementation and\nsubstantial similarities.\n</div>\n\n> It is probably much safer to simply ask the people involved to agree\n> with your relicensing.  And so far I don't see anyone with a stake in\n> this fiercely wanting to stick to a particular license.\n\nAs for politeness, that's exactly why I did post it and solicit\nobjections.  The purpose of the rewrite is to avoid having to make\npessimistic assumptions about people who don't respond.\n\nI suppose I should have made that request clearer:\nIs there anyone who claims copyright on anything here?\nOr would just like credit?\nIf so, are you willing to donate it to the public domain?\n\nI like the GPL, but some code is generally applicable enough, and unlikely\nto be improved on by others enough, that I'd rather just let everyone\nuse the same version.\n\n> It's not quite 100% finished, as I haven't benchmarked it against Linus's\n> code yet, but it's functionally correct.\n> \n> It's also clean with -W -Wall -Wextra.\n\n> Not if you try with the unaligned put_be32() as the destination pointer \n> is marked const.\n\nOops.  And the \"||\" in get_be32() doesn't help either.\nThere was another major bug I found, too.\n\nAnd I'm still trying to match \"linusv\" performance.\n\n> As to the actual result on ARM... Well, the assembly _looks_ much worse \n> than Linus' version.  It uses a stack frame of 152 bytes instead of 64 \n> bytes.  The resulting binary is also 6868 bytes large compared to 6180 \n> bytes.  Surprisingly, the performance is not that bad (the reason for \n> the underlined \"looks\" above) albeit still a bit worse, like 5% slower.  \n> I was expecting much worse than that.\n\nThanks, I'll work on it.\n\n> Also, wrt skipping the last 3 write back to the 16 word array...  For \n> all the (limited) attempts I've made so far to do that, it always ended \n> up making things worse.  I've yet to investigate why though.\n\nThanks.  That's certainly surprising!\n\n\nIf anyone cares, my current code (adapted to fit sha1bench) is appended.\n\n/*\n * Secure Hash Algorith SHA-1, as published in FIPS PUB 180-2.\n *\n * This implementation is in the public domain.  Copyright abandoned.\n * You may do anything you like with it, including evil things.\n *\n * This is a rewrite from scratch, based on Linus Torvalds' \"block-sha1\"\n * from the git mailing list (August, 2009).  Additional optimization\n * ideas cribbed from\n * - Artur Skawina (x86, particularly P4, and much benchmarking)\n * - Nicolas Pitre (ARM)\n *\n * Contributors to this code are requested to donate their changes to\n * the public domain to avoid version skew.  If you don't want to, be\n * sure to change the copyright waiver above.\n */\n\n#include <string.h>\t/* For memcpy() */\n#include <arpa/inet.h>\t/* For ntohl() */\n\n#include \"pdsha1.h\"\n\n#define SHA_CTX pd_SHA_CTX\n#define SHA_context pd_SHA_context\n#define SHA1_Init pd_SHA1_Init\n#define SHA1_Update pd_SHA1_Update\n#define SHA1_Final pd_SHA1_Final\n\nstatic void sha1_core(uint32_t iv[5], unsigned char const *p);\n\n\nvoid SHA1_Init(struct SHA_context *c)\n{\n\t/* This is a prefix of the SHA_context structure */\n\tstatic struct {\n\t\tuint64_t len;\n\t\tuint32_t iv[5];\n\t} const iv = { 0,\n\t\t{ 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0 }\n\t};\n\n\tmemcpy(c, &iv, sizeof iv);\n}\n\nvoid SHA1_Update(struct SHA_context *c, void const *p, size_t n)\n{\n\tsize_t pos = c->len & 63;\t/* Offset into current input block */\n\tsize_t nblocks;\n\n\tc->len += n;\n\n\t/* Initial partial block (if any) */\n\tif (pos) {\n\t\tsize_t space = 63 - pos;\n\t\tif (n < space)\n\t\t\tgoto end;\n\t\tmemcpy(c->buf + pos, p, space);\n\t\tsha1_core(c->iv, c->buf);\n\t\tn -= space;\n\t\tp = (char const *)p + space;\n\t}\n\n\t/* The large middle piece */\n\tnblocks = n >> 6;\n\twhile (nblocks--) {\n\t\tsha1_core(c->iv, p);\n\t\tp += 64;\n\t}\n\tn &= 63;\n\tpos = 0;\nend:\n\t/* Final partial block (may be zero size) */\n\tmemcpy(c->buf + pos, p, n);\n}\n\n/* Machine specific hacks */\n#if defined(__i386__) || defined(__x86_64__) || defined (__ppc__) || \\\n    defined(__ppc64__) || defined(__powerpc__) || defined (__powerpc64__) || \\\n    defined(__s390__) || defined(__s390x__)\n/* Unaligned access is okay */\n#define GET_BE32(p) ntohl(*(uint32_t const *)(p))\n#define PUT_BE32(p,v) (*(uint32_t *)(p) = htonl(v))\n\n#else\n/*\n * Unaligned access is not okay; do conversion as byte fetches\n * These macros are IN_CAPS, as they are not side-effect safe\n * The argument p must be an \"unsigned char *\" or \"uint8_t *\"\n */\n#define GET_BE32(p) \\\n\t((uint32_t)(p)[0]<<24 | (p)[1]<<16 | (p)[2]<<8 | (p)[3])\n#define PUT_BE32(p,v) \\\n\t( (p)[0] = (v)>>24, (p)[1] = (v)>>16, (p)[2] = (v)>>8, (p)[3] = (v) )\n#endif\n\nvoid SHA1_Final(unsigned char hash[20], struct SHA_context *c)\n{\n\tsize_t pos = c->len & 63;\n\tunsigned i;\n\n\t/* Append a single 1 bit */\n\tc->buf[pos++] = 0x80;\n\n\t/* Append 0 bits until 64 bits remain in a block */\n\tif (pos > 56) {\n\t\tmemset(c->buf + pos, 0, 64 - pos);\n\t\tsha1_core(c->iv, c->buf);\n\t\tpos = 0;\n\t}\n\tmemset(c->buf + pos, 0, 56 - pos);\n\n\t/* Append total input length in bits */\n\t((uint32_t *)c->buf)[14] = htonl((uint32_t)(c->len >> 29));\n\t((uint32_t *)c->buf)[15] = htonl((uint32_t)c->len << 3);\n\n\t/* Final hash round */\n\tsha1_core(c->iv, c->buf);\n\n\t/* Copy hash result out */\n\tfor (i = 0; i < 5; i++)\n\t\tPUT_BE32(hash + 4*i, c->iv[i]);\n}\n\n\n/*\n * Helper macros for sha1_core function.  To avoid clutter, these macros\n * are NOT fully parenthesized if it doesn't matter to the actual use.\n */\n\n#if __GNUC__ && (defined(__i386__) || defined(__x86_64__))\n/*\n * GCC by itself only generates left rotates.  Use right rotates if\n * possible to be kinder to dinky implementations with iterative rotate\n * instructions.\n */\n#define ROT(op, x, k) \\\n\t({ uint32_t y; __asm__(op \" %1,%0\" : \"=r\" (y) : \"I\" (k), \"0\" (x)); y; })\n#define ROL(x,k) ROT(\"roll\", x, k)\n#define ROR(x,k) ROT(\"rorl\", x, k)\n\n#else\n/* Generic C equivalent */\n#define ROT(x,l,r) ((x) << (l) | (x) >> (r))\n#define ROL(x,k) ROT(x,k,32-(k))\n#define ROR(x,k) ROT(x,32-(k),k)\n#endif\n\n\n/*\n * An important temporary array in SHA-1 is the working array W[],\n * which holds a scheduled key word per round.  Only the last 16 words\n * are relevant, so only use 16 words...\n */\n#define W(i) w[(i) & 15]\n\n/*\n * If you have a small register set, it helps GCC to force stores to\n * the w[] array to memory.  Given 22 or more registers (e.g. PowerPC),\n * GCC can map the entire w[] array to registers and this becomes\n * counterproductive.\n *\n * The optimal kludge seems to differ between x86 and ARM.  On the latter,\n * forcing a full memory barrier is required to stop GCC from splitting\n * live ranges for each round and generating a separate stack slot for\n * each.  (Which produces a huge stack frame and kills performance.)\n */\n#if __GNUC__ && defined(__i386__) || defined(__x86_64__)\n#define STORE(i, x) W(i) = x; __asm__ volatile(\"\" : \"+m\" (W(x)))\n\n#elif defined(__i386__) || defined(__x86_64__)\n#define STORE(i, x) *(volatile uint32_t *)&W(i) = x\n\n#elif __GNUC__ && defined(__arm__)\n#define STORE(i, x) W(i) = x; __asm__(\"\":::\"memory\")\n\n#else\n#define STORE(i, x) W(i) = x\n#endif\n\n\n/* The three round functions.  F2 is also used as F4 */\n#define F1(b,c,d) (((d ^ c) & b) ^ d)\t\t/* Bitwise b ? c : d */\n#define F2(b,c,d) (d ^ c ^ b)\t\t\t/* Even parity */\n#define F3(b,c,d) (d & c) + ((d ^ c) & b)\t/* Majority function */\n\n/* The four round constants */\n#define K1 0x5a827999\t/* 2^30 * sqrt(2) */\n#define K2 0x6ed9eba1\t/* 2^30 * sqrt(3) */\n#define K3 0x8f1bbcdc\t/* 2^30 * sqrt(5) */\n#define K4 0xca62c1d6\t/* 2^30 * sqrt(10) */\n\n/* Rounds 0..15 fetch a word from the input */\n#define FETCH(t,i)\tt = GET_BE32(p + 4*(i)); STORE(i,t)\n//#define FETCH(t,i)\tt = W(i)\n/* Rounds 16..79 mix previous words to get a new one */\n#define MIX(t,i)\tt = W(i) ^ W(i+2) ^ W(i+8) ^ W(i+13); t = ROL(t, 1)\n/* Rounds 16..76 have to store back the result */\n#define CALC(t,i)\tMIX(t,i); STORE(i,t)\n\n/* The basic SHA-1 round */\n#if 0\n#define SHA_ROUND(a,b,c,d,e,f,k,src,t,i)\t\\\n\tsrc(t,i);\t\t\t\t\\\n\te += t + f(b,c,d) + k + ROL(a,5);\t\\\n\tb = ROR(b,2)\n#elif 0\n#define SHA_ROUND(a,b,c,d,e,f,k,src,t,i) do {\t\\\n\tuint32_t t;\t\t\t\t\\\n\tsrc(t,i);\t\t\t\t\\\n\te += f(b,c,d);\t\t\t\t\\\n\te += t + k;\t\t\t\t\\\n\tb = ROR(b,2);\t\t\t\t\\\n\te += ROL(a,5); } while (0)\n#else\n#define SHA_ROUND(a,b,c,d,e,f,k,src,t,i) do {\t\\\n\tuint32_t t = ROL(a,5);\t\t\t\\\n\te += f(b,c,d);\t\t\t\t\\\n\te += k + t;\t\t\t\t\\\n\tsrc(t,i);\t\t\t\t\\\n\tb = ROR(b,2);\t\t\t\t\\\n\te += t;\t} while(0)\t\t\t\n#endif\n\n/* An aligned group of 5 rounds */\n#define SHA_ROUND5(f,k,src,t,i) \\\n\tSHA_ROUND(a,b,c,d,e, f,k,src,t,i);\t\\\n\tSHA_ROUND(e,a,b,c,d, f,k,src,t,i+1);\t\\\n\tSHA_ROUND(d,e,a,b,c, f,k,src,t,i+2);\t\\\n\tSHA_ROUND(c,d,e,a,b, f,k,src,t,i+3);\t\\\n\tSHA_ROUND(b,c,d,e,a, f,k,src,t,i+4)\n\n/*\n * The core SHA-1 transform.\n *\n * iv[5] = Current SHA-1 hash state.\n * p = Pointer to 64 bytes of source data.  Not necessarily aligned.\n */\nstatic void\nsha1_core(uint32_t iv[5], unsigned char const *p)\n{\n\t//uint32_t e = iv[4], d = iv[3], c = iv[2], b = iv[1], a = iv[0];\n\tuint32_t a = iv[0], b = iv[1], c = iv[2], d = iv[3], e = iv[4];\n\tuint32_t w[16];\n\n#if 0\n\t{\n\t\tint i;\n\t\tfor (i = 0; i < 16; i++) {\n\t\t\tSTORE(i, get_be32(p + 4*i));\n\t\t}\n\t}\n#endif\n\tSHA_ROUND5(F1, K1, FETCH, t,  0);\n\tSHA_ROUND5(F1, K1, FETCH, t,  5);\n\tSHA_ROUND5(F1, K1, FETCH, t, 10);\n\tSHA_ROUND(a,b,c,d,e, F1, K1, FETCH, t, 15);\n\tSHA_ROUND(e,a,b,c,d, F1, K1, CALC, t, 16);\n\tSHA_ROUND(d,e,a,b,c, F1, K1, CALC, t, 17);\n\tSHA_ROUND(c,d,e,a,b, F1, K1, CALC, t, 18);\n\tSHA_ROUND(b,c,d,e,a, F1, K1, CALC, t, 19);\n\n\tSHA_ROUND5(F2, K2, CALC, t, 20);\n\tSHA_ROUND5(F2, K2, CALC, t, 25);\n\tSHA_ROUND5(F2, K2, CALC, t, 30);\n\tSHA_ROUND5(F2, K2, CALC, t, 35);\n\n\tSHA_ROUND5(F3, K3, CALC, t, 40);\n\tSHA_ROUND5(F3, K3, CALC, t, 45);\n\tSHA_ROUND5(F3, K3, CALC, t, 50);\n\tSHA_ROUND5(F3, K3, CALC, t, 55);\n\n\tSHA_ROUND5(F2, K4, CALC, t, 60);\n\tSHA_ROUND5(F2, K4, CALC, t, 65);\n\tSHA_ROUND5(F2, K4, CALC, t, 70);\n\n\tSHA_ROUND(a,b,c,d,e, F2, K4, CALC, t, 75);\n\tSHA_ROUND(e,a,b,c,d, F2, K4, CALC, t, 76);\n\t/* Last 3 rounds don't need to store mixed value */\n\tSHA_ROUND(d,e,a,b,c, F2, K4, MIX, t, 77);\n\tSHA_ROUND(c,d,e,a,b, F2, K4, MIX, t, 78);\n\tSHA_ROUND(b,c,d,e,a, F2, K4, MIX, t, 79);\n\n\tiv[0] += a;\n\tiv[1] += b;\n\tiv[2] += c;\n\tiv[3] += d;\n\tiv[4] += e;\n}\n\n\n/* Compile with -DUNITTEST for self-tests */\n#if UNITTEST\n\n#include <stdio.h>\n#include <stdlib.h>\n\n/* Known answer test */\nstatic void katest(char const *text, size_t len, unsigned char const hash[20])\n{\n\tSHA_CTX c;\n\tunsigned char hash2[20];\n\tint i;\n\n\tSHA1_Init(&c);\n\tSHA1_Update(&c, text, len);\n\tSHA1_Final(hash2, &c);\n\n\tfor (i = 0; i < 20; i++)\n\t\tif (hash[i] != hash2[i])\n\t\t\tgoto mismatch;\n\tprintf(\"%u-byte known answer test PASSED\\n\", len);\n\treturn;\n\nmismatch:\n\tprintf(\"%u-byte known answer test FAILED:\\n\", len);\n\tif (len < 64)\n\t\tprintf(\"Input: \\\"%.*s\\\"\\n\", len, text);\n\telse\n\t\tprintf(\"Input: \\\"%.64s\\\"...\\n\", text);\n\tprintf(\"Computed:\");\n\tfor (i = 0; i < 20; i++)\n\t\tprintf(\" %02x\", hash2[i]);\n\tprintf(\"\\nExpected:\");\n\tfor (i = 0; i < 20; i++)\n\t\tprintf(\" %02x\", hash[i]);\n\tputchar('\\n');\n}\n\nint\nmain(void)\n{\n\t/* FIPS PUB 180.1 example A.1 */\n\tstatic char const text1[3] = \"abc\";\n\tstatic unsigned char const hash1[20] = {\n\t\t0xa9, 0x99, 0x3e, 0x36, 0x47, 0x06, 0x81, 0x6a, 0xba, 0x3e,\n\t\t0x25, 0x71, 0x78, 0x50, 0xc2, 0x6c, 0x9c, 0xd0, 0xd8, 0x9d };\n\n\t/* FIPS PUB 180.1 example A.2 */\n\tstatic char const text2[56] =\n\t\t\"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq\";\n\tstatic unsigned char const hash2[20] = {\n\t\t0x84, 0x98, 0x3e, 0x44, 0x1c, 0x3b, 0xd2, 0x6e, 0xba, 0xae,\n\t\t0x4a, 0xa1, 0xf9, 0x51, 0x29, 0xe5, 0xe5, 0x46, 0x70, 0xf1 };\n\n\t/* FIPS PUB 180.1 example A.3 */\n\tchar *text3;\n\tstatic unsigned char const hash3[20] = {\n\t\t0x34, 0xaa, 0x97, 0x3c, 0xd4, 0xc4, 0xda, 0xa4, 0xf6, 0x1e,\n\t\t0xeb, 0x2b, 0xdb, 0xad, 0x27, 0x31, 0x65, 0x34, 0x01, 0x6f };\n\n\tkatest(text1, sizeof text1, hash1);\n\tkatest(text2, sizeof text2, hash2);\n\ttext3 = malloc(1000000);\n\tmemset(text3, 'a', 1000000);\n\tkatest(text3, 1000000, hash3);\n\t\n\treturn 0;\n}\n#endif\n"},{"id":"120965","messageId":"alpine.LFD.2.00.0908171513230.6044@xanadu.home","threadId":"20624","inReplyTo":"20090817185448.30254.qmail@science.horizon.com","subject":"Re: Linus' sha1 is much faster!","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2009-08-17T19:34:11Z","receivedAt":"2009-08-17T19:34:11Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 17 Aug 2009, George Spelvin wrote:\n\n> > I don't think this trick of making source code textually different from \n> > another work while still intimately mimicking the same structure entitles \n> > you to any copyright (or non copyright) claims over that other work.  I \n> > certainly wouldn't bet any dime for this standing up in court.  \n> \n> <div type=\"legal digression\">\n> Actually, I would.  I did a lot more than text search and replace;\n> I re-implemented it from FIPS 180-2 (work of U.S. government, no copyright)\n> and then merged in the *ideas* from the mailing list.  \n> \n> (And from elsewhere; the idea of a five-round macro is from Brian Gladman.)\n> \n> Remember, to the extent that something is *functional*, it is not\n> copyrightable; copyright only covers the non-functional expressive bits.\n> The vast majority of that code is simply required by the standard,\n> or the desired calling interface.\n> \n> For a large portion of the rest, remember that standard programming\n> conventions (e.g.  brace style, macro names IN CAPS, etc.) that's also\n> non-copyrightable \"scene a faire\" material.\n> \n> It's well established that paraphrasing a recipe avoids copyright;\n> the proportions and treatment of the ingredients is not copyrightable.\n> \n> For more details, see the extensive coverage of the NEC v. Intel decision\n> (1989) regarding the firmware for NEC's 8086-clone V20 microprocessor.\n> It was found non-infringing despite non-clean-room implementation and\n> substantial similarities.\n> </div>\n\nWhatever.  NEC and Intel were certainly commercial competitors.  They \nwere far from being friends.  So if you feel like having too many \nfriends then just go ahead with that stance.\n\n> As for politeness, that's exactly why I did post it and solicit\n> objections.\n\nYou said:\n\n|It uses Linus's and Artur's performance ideas, and some of Linus' macro \n|ideas (in the rotate implementation), but tries to be textually \n|different. Is there anything recognizable that anyone cares to clam \n|copyright to?\n\nthe \"try to be textually different\" in order to ask for \"anything \nrecognizable that anyone cares to clam copyright to\" is what I find \ndubious.\n\n> The purpose of the rewrite is to avoid having to make\n> pessimistic assumptions about people who don't respond.\n> \n> I suppose I should have made that request clearer:\n> Is there anyone who claims copyright on anything here?\n> Or would just like credit?\n> If so, are you willing to donate it to the public domain?\n\nI think this is much nicer to everyone involved.\n\nAs far as I'm concerned, I'm OK with giving any small copyright I might \nhave in this SHA1 implementation, if any, to the public domain.  \nCredits are always nice.\n\n\nNicolas\n"},{"id":"121021","messageId":"20090817231208.32039.qmail@science.horizon.com","threadId":"20624","inReplyTo":"alpine.LFD.2.00.0908171513230.6044@xanadu.home","subject":"Re: Linus' sha1 is much faster!","fromName":"George Spelvin","fromEmail":"linux@horizon.com","sentAt":"2009-08-17T23:12:08Z","receivedAt":"2009-08-17T23:12:08Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":">> The purpose of the rewrite is to avoid having to make\n>> pessimistic assumptions about people who don't respond.\n>> \n>> I suppose I should have made that request clearer:\n>> Is there anyone who claims copyright on anything here?\n>> Or would just like credit?\n>> If so, are you willing to donate it to the public domain?\n\n> I think this is much nicer to everyone involved.\n>\n> As far as I'm concerned, I'm OK with giving any small copyright I might \n> have in this SHA1 implementation, if any, to the public domain.  \n> Credits are always nice.\n\nMy apologies.  I read a lot of people talking about wanting the code\nunder different licenses, and thought I'd just cut through it by\nproviding some PD code.\n\nI didn't turn around and look at it from the point of view of the\npeople who'd put the work into developing it.  I don't mean to deny\nanyone credit for their work.  In fact, providing more detail is on\nthe to-do list, but I haven't waded through the mail archives and\ntracked down who contributed what yet.\n\nI'll work on those polish details once I have it producing the same\nassembly code as Linus'.\n\nThere are a lot of possible highly-permissive licenses if one is wanted\n(zlib, MIT, CC-by), but public domain seems simpler.\n"}]}