glyph-pixmaps merged

[Edgar Toernig]

Keith Packard wrote:
>
> We need a strong hash function as this replaces the previous weak hash +
> memcmp when checking incoming glyphs for matches with the existing set
> of server-resident glyphs. One could argue that this must be
> cryptographically secure to avoid applications uploading misleading
> glyph images.
> 
> Patches to use alternate SHA1 implementation would also be welcome, if
> anyone has reason to choose other bits.

Below is a modified sha1 routine.  The algorithm has been kept
but support for byte streams and byte-order independence has
been dropped.  That simplifies the code and makes it faster.

Compiles to about 700 bytes on x86 and is public domain.

Ciao, ET.

----8<----
#include <sys/types.h>
#include <string.h>

typedef unsigned int u32;

#define f1(x,y,z)   (z ^ (x & (y ^ z)))		/* x ? y : z */
#define f2(x,y,z)   (x ^ y ^ z)			/* xor */
#define f3(x,y,z)   ((x & y) + (z & (x ^ y)))	/* majority */

#define K1  0x5A827999L	/* Rounds  0-19: sqrt(2) * 2^30 */
#define K2  0x6ED9EBA1L	/* Rounds 20-39: sqrt(3) * 2^30 */
#define K3  0x8F1BBCDCL	/* Rounds 40-59: sqrt(5) * 2^30 */
#define K4  0xCA62C1D6L	/* Rounds 60-79: sqrt(10) * 2^30 */

static inline u32
rol32(u32 val, int n)
{
    return (val << n) | (val >> (32 - n));
}

static void
sha1(u32 digest[5], u32 *W)
{
    u32 a, b, c, d, e, t;
    int i;

    for (i = 0; i < 64; i++)
	W[i+16] = rol32(W[i+13] ^ W[i+8] ^ W[i+2] ^ W[i], 1);

    a = digest[0];
    b = digest[1];
    c = digest[2];
    d = digest[3];
    e = digest[4];

    for (i = 0; i < 20; i++)
    {
	t = f1(b, c, d) + K1 + rol32(a, 5) + e + W[i];
	e = d; d = c; c = rol32(b, 30); b = a; a = t;
    }

    for (; i < 40; i++)
    {
	t = f2(b, c, d) + K2 + rol32(a, 5) + e + W[i];
	e = d; d = c; c = rol32(b, 30); b = a; a = t;
    }

    for (; i < 60; i++)
    {
	t = f3(b, c, d) + K3 + rol32(a, 5) + e + W[i];
	e = d; d = c; c = rol32(b, 30); b = a; a = t;
    }

    for (; i < 80; i++)
    {
	t = f2(b, c, d) + K4 + rol32(a, 5) + e + W[i];
	e = d; d = c; c = rol32(b, 30); b = a; a = t;
    }

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

void
hash_buffer(u32 digest[5], char *buf, size_t n)
{
    u32 W[80];
    u32 size = n;

    digest[0] = 0x67452301;
    digest[1] = 0xefcdab89;
    digest[2] = 0x98badcfe;
    digest[3] = 0x10325476;
    digest[4] = 0xc3d2e1f0;

    if (n < 64)
	memset((char *)W + n, 0, 64 - n);
    while (n >= 64)
    {
	memcpy((char *)W, buf, 64);
	sha1(digest, W);
	buf += 64;
	n -= 64;
    }
    if (n > 0)
	memcpy((char *)W, buf, n);
    if (n > 60)
	sha1(digest, W);
    W[15] = size;
    sha1(digest, W);
}