Re: Linus' sha1 is much faster!

["George Spelvin" <linux@horizon.com>]

> I don't think this trick of making source code textually different from 
> another work while still intimately mimicking the same structure entitles 
> you to any copyright (or non copyright) claims over that other work.  I 
> certainly wouldn't bet any dime for this standing up in court.  

<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>

> It is probably much safer to simply ask the people involved to agree
> with your relicensing.  And so far I don't see anyone with a stake in
> this fiercely wanting to stick to a particular license.

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.

> It's not quite 100% finished, as I haven't benchmarked it against Linus's
> code yet, but it's functionally correct.
> 
> It's also clean with -W -Wall -Wextra.

> Not if you try with the unaligned put_be32() as the destination pointer 
> is marked const.

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.

> As to the actual result on ARM... Well, the assembly _looks_ much worse 
> than Linus' version.  It uses a stack frame of 152 bytes instead of 64 
> bytes.  The resulting binary is also 6868 bytes large compared to 6180 
> bytes.  Surprisingly, the performance is not that bad (the reason for 
> the underlined "looks" above) albeit still a bit worse, like 5% slower.  
> I was expecting much worse than that.

Thanks, I'll work on it.

> Also, wrt skipping the last 3 write back to the 16 word array...  For 
> all the (limited) attempts I've made so far to do that, it always ended 
> up making things worse.  I've yet to investigate why though.

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