Re: Linus' sha1 is much faster!

<div type="legal digression"> Actually, I would. I did a lot more than text search and replace; I re-implemented it from FIPS 180-2 (work of U.S. government, no copyright) and then merged in the *ideas* from the mailing list.

(And from elsewhere; the idea of a five-round macro is from Brian Gladman.)

Remember, to the extent that something is *functional*, it is not copyrightable; copyright only covers the non-functional expressive bits. The vast majority of that code is simply required by the standard, or the desired calling interface.

For a large portion of the rest, remember that standard programming conventions (e.g. brace style, macro names IN CAPS, etc.) that's also non-copyrightable "scene a faire" material.

It's well established that paraphrasing a recipe avoids copyright; the proportions and treatment of the ingredients is not copyrightable.

For more details, see the extensive coverage of the NEC v. Intel decision (1989) regarding the firmware for NEC's 8086-clone V20 microprocessor. It was found non-infringing despite non-clean-room implementation and substantial similarities. </div>

As for politeness, that's exactly why I did post it and solicit objections. The purpose of the rewrite is to avoid having to make pessimistic assumptions about people who don't respond.

I suppose I should have made that request clearer: Is there anyone who claims copyright on anything here? Or would just like credit? If so, are you willing to donate it to the public domain?

I like the GPL, but some code is generally applicable enough, and unlikely to be improved on by others enough, that I'd rather just let everyone use the same version.

Oops. And the "||" in get_be32() doesn't help either. There was another major bug I found, too.

And I'm still trying to match "linusv" performance.

Thanks, I'll work on it.

Thanks.  That's certainly surprising!

If anyone cares, my current code (adapted to fit sha1bench) is appended.

/*
 * Secure Hash Algorith SHA-1, as published in FIPS PUB 180-2.
 *
 * This implementation is in the public domain.  Copyright abandoned.
 * You may do anything you like with it, including evil things.
 *
 * This is a rewrite from scratch, based on Linus Torvalds' "block-sha1"
 * from the git mailing list (August, 2009).  Additional optimization
 * ideas cribbed from
 * - Artur Skawina (x86, particularly P4, and much benchmarking)
 * - Nicolas Pitre (ARM)
 *
 * Contributors to this code are requested to donate their changes to
 * the public domain to avoid version skew.  If you don't want to, be
 * sure to change the copyright waiver above.
 */

#include <string.h> /* For memcpy() */ #include <arpa/inet.h> /* For ntohl() */

#include "pdsha1.h"

#define SHA_CTX pd_SHA_CTX #define SHA_context pd_SHA_context #define SHA1_Init pd_SHA1_Init #define SHA1_Update pd_SHA1_Update #define SHA1_Final pd_SHA1_Final

static void sha1_core(uint32_t iv[5], unsigned char const *p);

void SHA1_Init(struct SHA_context *c)
{
	/* This is a prefix of the SHA_context structure */
	static struct {
		uint64_t len;
		uint32_t iv[5];
	} const iv = { 0,
		{ 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0 }
	};

	memcpy(c, &iv, sizeof iv);
}

void SHA1_Update(struct SHA_context *c, void const *p, size_t n)
{
	size_t pos = c->len & 63;	/* Offset into current input block */
	size_t nblocks;

	c->len += n;

	/* Initial partial block (if any) */
	if (pos) {
		size_t space = 63 - pos;
		if (n < space)
			goto end;
		memcpy(c->buf + pos, p, space);
		sha1_core(c->iv, c->buf);
		n -= space;
		p = (char const *)p + space;
	}

	/* The large middle piece */
	nblocks = n >> 6;
	while (nblocks--) {
		sha1_core(c->iv, p);
		p += 64;
	}
	n &= 63;
	pos = 0;
end:
	/* Final partial block (may be zero size) */
	memcpy(c->buf + pos, p, n);
}

/* Machine specific hacks */
#if defined(__i386__) || defined(__x86_64__) || defined (__ppc__) || \
    defined(__ppc64__) || defined(__powerpc__) || defined (__powerpc64__) || \
    defined(__s390__) || defined(__s390x__)
/* Unaligned access is okay */
#define GET_BE32(p) ntohl(*(uint32_t const *)(p))
#define PUT_BE32(p,v) (*(uint32_t *)(p) = htonl(v))

#else
/*
 * Unaligned access is not okay; do conversion as byte fetches
 * These macros are IN_CAPS, as they are not side-effect safe
 * The argument p must be an "unsigned char *" or "uint8_t *"
 */
#define GET_BE32(p) \
	((uint32_t)(p)[0]<<24 | (p)[1]<<16 | (p)[2]<<8 | (p)[3])
#define PUT_BE32(p,v) \
	( (p)[0] = (v)>>24, (p)[1] = (v)>>16, (p)[2] = (v)>>8, (p)[3] = (v) )
#endif

void SHA1_Final(unsigned char hash[20], struct SHA_context *c)
{
	size_t pos = c->len & 63;
	unsigned i;

	/* Append a single 1 bit */
	c->buf[pos++] = 0x80;

	/* Append 0 bits until 64 bits remain in a block */
	if (pos > 56) {
		memset(c->buf + pos, 0, 64 - pos);
		sha1_core(c->iv, c->buf);
		pos = 0;
	}
	memset(c->buf + pos, 0, 56 - pos);

	/* Append total input length in bits */
	((uint32_t *)c->buf)[14] = htonl((uint32_t)(c->len >> 29));
	((uint32_t *)c->buf)[15] = htonl((uint32_t)c->len << 3);

	/* Final hash round */
	sha1_core(c->iv, c->buf);

	/* Copy hash result out */
	for (i = 0; i < 5; i++)
		PUT_BE32(hash + 4*i, c->iv[i]);
}

/*
 * Helper macros for sha1_core function.  To avoid clutter, these macros
 * are NOT fully parenthesized if it doesn't matter to the actual use.
 */

#if __GNUC__ && (defined(__i386__) || defined(__x86_64__))
/*
 * GCC by itself only generates left rotates.  Use right rotates if
 * possible to be kinder to dinky implementations with iterative rotate
 * instructions.
 */
#define ROT(op, x, k) \
	({ uint32_t y; __asm__(op " %1,%0" : "=r" (y) : "I" (k), "0" (x)); y; })
#define ROL(x,k) ROT("roll", x, k)
#define ROR(x,k) ROT("rorl", x, k)

#else /* Generic C equivalent */ #define ROT(x,l,r) ((x) << (l) | (x) >> (r)) #define ROL(x,k) ROT(x,k,32-(k)) #define ROR(x,k) ROT(x,32-(k),k) #endif

/*
 * An important temporary array in SHA-1 is the working array W[],
 * which holds a scheduled key word per round.  Only the last 16 words
 * are relevant, so only use 16 words...
 */
#define W(i) w[(i) & 15]

/*
 * If you have a small register set, it helps GCC to force stores to
 * the w[] array to memory.  Given 22 or more registers (e.g. PowerPC),
 * GCC can map the entire w[] array to registers and this becomes
 * counterproductive.
 *
 * The optimal kludge seems to differ between x86 and ARM.  On the latter,
 * forcing a full memory barrier is required to stop GCC from splitting
 * live ranges for each round and generating a separate stack slot for
 * each.  (Which produces a huge stack frame and kills performance.)
 */
#if __GNUC__ && defined(__i386__) || defined(__x86_64__)
#define STORE(i, x) W(i) = x; __asm__ volatile("" : "+m" (W(x)))

#elif defined(__i386__) || defined(__x86_64__) #define STORE(i, x) *(volatile uint32_t *)&W(i) = x

#elif __GNUC__ && defined(__arm__) #define STORE(i, x) W(i) = x; __asm__("":::"memory")

#else #define STORE(i, x) W(i) = x #endif

/* The three round functions. F2 is also used as F4 */ #define F1(b,c,d) (((d ^ c) & b) ^ d) /* Bitwise b ? c : d */ #define F2(b,c,d) (d ^ c ^ b) /* Even parity */ #define F3(b,c,d) (d & c) + ((d ^ c) & b) /* Majority function */

/* The four round constants */ #define K1 0x5a827999 /* 2^30 * sqrt(2) */ #define K2 0x6ed9eba1 /* 2^30 * sqrt(3) */ #define K3 0x8f1bbcdc /* 2^30 * sqrt(5) */ #define K4 0xca62c1d6 /* 2^30 * sqrt(10) */

/* Rounds 0..15 fetch a word from the input */ #define FETCH(t,i) t = GET_BE32(p + 4*(i)); STORE(i,t) //#define FETCH(t,i) t = W(i) /* Rounds 16..79 mix previous words to get a new one */ #define MIX(t,i) t = W(i) ^ W(i+2) ^ W(i+8) ^ W(i+13); t = ROL(t, 1) /* Rounds 16..76 have to store back the result */ #define CALC(t,i) MIX(t,i); STORE(i,t)

/* The basic SHA-1 round */
#if 0
#define SHA_ROUND(a,b,c,d,e,f,k,src,t,i)	\
	src(t,i);				\
	e += t + f(b,c,d) + k + ROL(a,5);	\
	b = ROR(b,2)
#elif 0
#define SHA_ROUND(a,b,c,d,e,f,k,src,t,i) do {	\
	uint32_t t;				\
	src(t,i);				\
	e += f(b,c,d);				\
	e += t + k;				\
	b = ROR(b,2);				\
	e += ROL(a,5); } while (0)
#else
#define SHA_ROUND(a,b,c,d,e,f,k,src,t,i) do {	\
	uint32_t t = ROL(a,5);			\
	e += f(b,c,d);				\
	e += k + t;				\
	src(t,i);				\
	b = ROR(b,2);				\
	e += t;	} while(0)			
#endif

/* An aligned group of 5 rounds */
#define SHA_ROUND5(f,k,src,t,i) \
	SHA_ROUND(a,b,c,d,e, f,k,src,t,i);	\
	SHA_ROUND(e,a,b,c,d, f,k,src,t,i+1);	\
	SHA_ROUND(d,e,a,b,c, f,k,src,t,i+2);	\
	SHA_ROUND(c,d,e,a,b, f,k,src,t,i+3);	\
	SHA_ROUND(b,c,d,e,a, f,k,src,t,i+4)

/*
 * The core SHA-1 transform.
 *
 * iv[5] = Current SHA-1 hash state.
 * p = Pointer to 64 bytes of source data.  Not necessarily aligned.
 */
static void
sha1_core(uint32_t iv[5], unsigned char const *p)
{
	//uint32_t e = iv[4], d = iv[3], c = iv[2], b = iv[1], a = iv[0];
	uint32_t a = iv[0], b = iv[1], c = iv[2], d = iv[3], e = iv[4];
	uint32_t w[16];

#if 0
	{
		int i;
		for (i = 0; i < 16; i++) {
			STORE(i, get_be32(p + 4*i));
		}
	}
#endif
	SHA_ROUND5(F1, K1, FETCH, t,  0);
	SHA_ROUND5(F1, K1, FETCH, t,  5);
	SHA_ROUND5(F1, K1, FETCH, t, 10);
	SHA_ROUND(a,b,c,d,e, F1, K1, FETCH, t, 15);
	SHA_ROUND(e,a,b,c,d, F1, K1, CALC, t, 16);
	SHA_ROUND(d,e,a,b,c, F1, K1, CALC, t, 17);
	SHA_ROUND(c,d,e,a,b, F1, K1, CALC, t, 18);
	SHA_ROUND(b,c,d,e,a, F1, K1, CALC, t, 19);

	SHA_ROUND5(F2, K2, CALC, t, 20);
	SHA_ROUND5(F2, K2, CALC, t, 25);
	SHA_ROUND5(F2, K2, CALC, t, 30);
	SHA_ROUND5(F2, K2, CALC, t, 35);

	SHA_ROUND5(F3, K3, CALC, t, 40);
	SHA_ROUND5(F3, K3, CALC, t, 45);
	SHA_ROUND5(F3, K3, CALC, t, 50);
	SHA_ROUND5(F3, K3, CALC, t, 55);

	SHA_ROUND5(F2, K4, CALC, t, 60);
	SHA_ROUND5(F2, K4, CALC, t, 65);
	SHA_ROUND5(F2, K4, CALC, t, 70);

	SHA_ROUND(a,b,c,d,e, F2, K4, CALC, t, 75);
	SHA_ROUND(e,a,b,c,d, F2, K4, CALC, t, 76);
	/* Last 3 rounds don't need to store mixed value */
	SHA_ROUND(d,e,a,b,c, F2, K4, MIX, t, 77);
	SHA_ROUND(c,d,e,a,b, F2, K4, MIX, t, 78);
	SHA_ROUND(b,c,d,e,a, F2, K4, MIX, t, 79);

	iv[0] += a;
	iv[1] += b;
	iv[2] += c;
	iv[3] += d;
	iv[4] += e;
}

/* Compile with -DUNITTEST for self-tests */ #if UNITTEST

#include <stdio.h> #include <stdlib.h>

/* Known answer test */
static void katest(char const *text, size_t len, unsigned char const hash[20])
{
	SHA_CTX c;
	unsigned char hash2[20];
	int i;

	SHA1_Init(&c);
	SHA1_Update(&c, text, len);
	SHA1_Final(hash2, &c);

	for (i = 0; i < 20; i++)
		if (hash[i] != hash2[i])
			goto mismatch;
	printf("%u-byte known answer test PASSED\n", len);
	return;

mismatch:
	printf("%u-byte known answer test FAILED:\n", len);
	if (len < 64)
		printf("Input: \"%.*s\"\n", len, text);
	else
		printf("Input: \"%.64s\"...\n", text);
	printf("Computed:");
	for (i = 0; i < 20; i++)
		printf(" %02x", hash2[i]);
	printf("\nExpected:");
	for (i = 0; i < 20; i++)
		printf(" %02x", hash[i]);
	putchar('\n');
}

int
main(void)
{
	/* FIPS PUB 180.1 example A.1 */
	static char const text1[3] = "abc";
	static unsigned char const hash1[20] = {
		0xa9, 0x99, 0x3e, 0x36, 0x47, 0x06, 0x81, 0x6a, 0xba, 0x3e,
		0x25, 0x71, 0x78, 0x50, 0xc2, 0x6c, 0x9c, 0xd0, 0xd8, 0x9d };

	/* FIPS PUB 180.1 example A.2 */
	static char const text2[56] =
		"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq";
	static unsigned char const hash2[20] = {
		0x84, 0x98, 0x3e, 0x44, 0x1c, 0x3b, 0xd2, 0x6e, 0xba, 0xae,
		0x4a, 0xa1, 0xf9, 0x51, 0x29, 0xe5, 0xe5, 0x46, 0x70, 0xf1 };

	/* FIPS PUB 180.1 example A.3 */
	char *text3;
	static unsigned char const hash3[20] = {
		0x34, 0xaa, 0x97, 0x3c, 0xd4, 0xc4, 0xda, 0xa4, 0xf6, 0x1e,
		0xeb, 0x2b, 0xdb, 0xad, 0x27, 0x31, 0x65, 0x34, 0x01, 0x6f };

	katest(text1, sizeof text1, hash1);
	katest(text2, sizeof text2, hash2);
	text3 = malloc(1000000);
	memset(text3, 'a', 1000000);
	katest(text3, 1000000, hash3);
	
	return 0;
}
#endif