Digest-Hashcash/Hashcash.xs

#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

#include <time.h>
#include <stdlib.h>
#include <stdint.h>

/* NIST Secure Hash Algorithm */
/* heavily modified by Uwe Hollerbach <uh@alumni.caltech edu> */
/* from Peter C. Gutmann's implementation as found in */
/* Applied Cryptography by Bruce Schneier */
/* Further modifications to include the "UNRAVEL" stuff, below */

/* This code is in the public domain */

/* pcg: I was tempted to just rip this code off, after all, if you don't
 * demand anything I am inclined not to give anything. *Sigh* something
 * kept me from doing it, so here's the truth: I took this code from the
 * SHA1 perl module, since it looked reasonably well-crafted. I modified
 * it here and there, though.
 */

/* don't expect _too_ much from compilers for now. */
#if __GNUC_MAJOR > 2
#  define restrict __restrict__
#elif __STDC_VERSION__ < 199900
#  define restrict
#endif

/* Useful defines & typedefs */

#if defined(U64TYPE) && (defined(USE_64_BIT_INT) || ((BYTEORDER != 0x1234) && (BYTEORDER != 0x4321)))
typedef U64TYPE ULONG;
# if BYTEORDER == 0x1234
#   undef BYTEORDER
#   define BYTEORDER 0x12345678
# elif BYTEORDER == 0x4321
#   undef BYTEORDER
#   define BYTEORDER 0x87654321   
# endif
#else
typedef uint_fast32_t ULONG;     /* 32-or-more-bit quantity */
#endif

#define SHA_BLOCKSIZE           64
#define SHA_DIGESTSIZE          20

typedef struct {
    ULONG digest[5];            /* message digest */
    ULONG count;                /* 32-bit bit count */
    U8 data[SHA_BLOCKSIZE];     /* SHA data buffer */
    int local;                  /* unprocessed amount in data */
} SHA_INFO;


/* UNRAVEL should be fastest & biggest */
/* UNROLL_LOOPS should be just as big, but slightly slower */
/* both undefined should be smallest and slowest */

#define SHA_VERSION 1
#define UNRAVEL
/* #define UNROLL_LOOPS */

/* SHA f()-functions */
#define f1(x,y,z)       ((x & y) | (~x & z))
#define f2(x,y,z)       (x ^ y ^ z)
#define f3(x,y,z)       ((x & y) | (x & z) | (y & z))
#define f4(x,y,z)       (x ^ y ^ z)

/* SHA constants */
#define CONST1          0x5a827999L
#define CONST2          0x6ed9eba1L
#define CONST3          0x8f1bbcdcL
#define CONST4          0xca62c1d6L

/* truncate to 32 bits -- should be a null op on 32-bit machines */
#define T32(x)  ((x) & 0xffffffffL)

/* 32-bit rotate */
#define R32(x,n)        T32(((x << n) | (x >> (32 - n))))

/* the generic case, for when the overall rotation is not unraveled */
#define FG(n)   \
    T = T32(R32(A,5) + f##n(B,C,D) + E + *WP++ + CONST##n);     \
    E = D; D = C; C = R32(B,30); B = A; A = T

/* specific cases, for when the overall rotation is unraveled */
#define FA(n)   \
    T = T32(R32(A,5) + f##n(B,C,D) + E + *WP++ + CONST##n); B = R32(B,30)

#define FB(n)   \
    E = T32(R32(T,5) + f##n(A,B,C) + D + *WP++ + CONST##n); A = R32(A,30)

#define FC(n)   \
    D = T32(R32(E,5) + f##n(T,A,B) + C + *WP++ + CONST##n); T = R32(T,30)

#define FD(n)   \
    C = T32(R32(D,5) + f##n(E,T,A) + B + *WP++ + CONST##n); E = R32(E,30)

#define FE(n)   \
    B = T32(R32(C,5) + f##n(D,E,T) + A + *WP++ + CONST##n); D = R32(D,30)

#define FT(n)   \
    A = T32(R32(B,5) + f##n(C,D,E) + T + *WP++ + CONST##n); C = R32(C,30)


static void sha_transform(restrict SHA_INFO *sha_info)
{
    int i;
    U8 *dp;
    ULONG T, A, B, C, D, E, W[80], *WP;

    dp = sha_info->data;

/*
the following makes sure that at least one code block below is
traversed or an error is reported, without the necessity for nested
preprocessor if/else/endif blocks, which are a great pain in the
nether regions of the anatomy...
*/
#undef SWAP_DONE

#if BYTEORDER == 0x1234
#define SWAP_DONE
    assert(sizeof(ULONG) == 4);
    for (i = 0; i < 16; ++i) {
        T = *((ULONG *) dp);
        dp += 4;
        W[i] =  ((T << 24) & 0xff000000) | ((T <<  8) & 0x00ff0000) |
                ((T >>  8) & 0x0000ff00) | ((T >> 24) & 0x000000ff);
    }
#endif

#if BYTEORDER == 0x4321
#define SWAP_DONE
    assert(sizeof(ULONG) == 4);
    for (i = 0; i < 16; ++i) {
        T = *((ULONG *) dp);
        dp += 4;
        W[i] = T32(T);
    }
#endif

#if BYTEORDER == 0x12345678
#define SWAP_DONE
    assert(sizeof(ULONG) == 8);
    for (i = 0; i < 16; i += 2) {
        T = *((ULONG *) dp);
        dp += 8;
        W[i] =  ((T << 24) & 0xff000000) | ((T <<  8) & 0x00ff0000) |
                ((T >>  8) & 0x0000ff00) | ((T >> 24) & 0x000000ff);
        T >>= 32;
        W[i+1] = ((T << 24) & 0xff000000) | ((T <<  8) & 0x00ff0000) |
                 ((T >>  8) & 0x0000ff00) | ((T >> 24) & 0x000000ff);
    }
#endif

#if BYTEORDER == 0x87654321
#define SWAP_DONE
    assert(sizeof(ULONG) == 8);
    for (i = 0; i < 16; i += 2) {
        T = *((ULONG *) dp);
        dp += 8;
        W[i] = T32(T >> 32);
        W[i+1] = T32(T);
    }
#endif

#ifndef SWAP_DONE
#error Unknown byte order -- you need to add code here
#endif /* SWAP_DONE */

    for (i = 16; i < 80; ++i) {
        W[i] = W[i-3] ^ W[i-8] ^ W[i-14] ^ W[i-16];
#if (SHA_VERSION == 1)
        W[i] = R32(W[i], 1);
#endif /* SHA_VERSION */
    }
    A = sha_info->digest[0];
    B = sha_info->digest[1];
    C = sha_info->digest[2];
    D = sha_info->digest[3];
    E = sha_info->digest[4];
    WP = W;
#ifdef UNRAVEL
    FA(1); FB(1); FC(1); FD(1); FE(1); FT(1); FA(1); FB(1); FC(1); FD(1);
    FE(1); FT(1); FA(1); FB(1); FC(1); FD(1); FE(1); FT(1); FA(1); FB(1);
    FC(2); FD(2); FE(2); FT(2); FA(2); FB(2); FC(2); FD(2); FE(2); FT(2);
    FA(2); FB(2); FC(2); FD(2); FE(2); FT(2); FA(2); FB(2); FC(2); FD(2);
    FE(3); FT(3); FA(3); FB(3); FC(3); FD(3); FE(3); FT(3); FA(3); FB(3);
    FC(3); FD(3); FE(3); FT(3); FA(3); FB(3); FC(3); FD(3); FE(3); FT(3);
    FA(4); FB(4); FC(4); FD(4); FE(4); FT(4); FA(4); FB(4); FC(4); FD(4);
    FE(4); FT(4); FA(4); FB(4); FC(4); FD(4); FE(4); FT(4); FA(4); FB(4);
    sha_info->digest[0] = T32(sha_info->digest[0] + E);
    sha_info->digest[1] = T32(sha_info->digest[1] + T);
    sha_info->digest[2] = T32(sha_info->digest[2] + A);
    sha_info->digest[3] = T32(sha_info->digest[3] + B);
    sha_info->digest[4] = T32(sha_info->digest[4] + C);
#else /* !UNRAVEL */
#ifdef UNROLL_LOOPS
    FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1);
    FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1);
    FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2);
    FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2);
    FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3);
    FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3);
    FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4);
    FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4);
#else /* !UNROLL_LOOPS */
    for (i =  0; i < 20; ++i) { FG(1); }
    for (i = 20; i < 40; ++i) { FG(2); }
    for (i = 40; i < 60; ++i) { FG(3); }
    for (i = 60; i < 80; ++i) { FG(4); }
#endif /* !UNROLL_LOOPS */
    sha_info->digest[0] = T32(sha_info->digest[0] + A);
    sha_info->digest[1] = T32(sha_info->digest[1] + B);
    sha_info->digest[2] = T32(sha_info->digest[2] + C);
    sha_info->digest[3] = T32(sha_info->digest[3] + D);
    sha_info->digest[4] = T32(sha_info->digest[4] + E);
#endif /* !UNRAVEL */
}

/* initialize the SHA digest */

static void sha_init(restrict SHA_INFO *sha_info)
{
    sha_info->digest[0] = 0x67452301L;
    sha_info->digest[1] = 0xefcdab89L;
    sha_info->digest[2] = 0x98badcfeL;
    sha_info->digest[3] = 0x10325476L;
    sha_info->digest[4] = 0xc3d2e1f0L;
    sha_info->count = 0L;
    sha_info->local = 0;
}

/* update the SHA digest */

static void sha_update(restrict SHA_INFO *sha_info, restrict U8 *buffer, int count)
{
    int i;

    sha_info->count += count << 3;
    if (sha_info->local) {
        i = SHA_BLOCKSIZE - sha_info->local;
        if (i > count) {
            i = count;
        }
        memcpy(((U8 *) sha_info->data) + sha_info->local, buffer, i);
        count -= i;
        buffer += i;
        sha_info->local += i;
        if (sha_info->local == SHA_BLOCKSIZE) {
            sha_transform(sha_info);
        } else {
            return;
        }
    }
    while (count >= SHA_BLOCKSIZE) {
        memcpy(sha_info->data, buffer, SHA_BLOCKSIZE);
        buffer += SHA_BLOCKSIZE;
        count -= SHA_BLOCKSIZE;
        sha_transform(sha_info);
    }
    memcpy(sha_info->data, buffer, count);
    sha_info->local = count;
}


#if 0
static void sha_transform_and_copy (unsigned char digest[20], restrict SHA_INFO *sha_info)
{
    sha_transform (sha_info);

    digest[ 0] = (unsigned char) ((sha_info->digest[0] >> 24) & 0xff);
    digest[ 1] = (unsigned char) ((sha_info->digest[0] >> 16) & 0xff);
    digest[ 2] = (unsigned char) ((sha_info->digest[0] >>  8) & 0xff);
    digest[ 3] = (unsigned char) ((sha_info->digest[0]      ) & 0xff);
    digest[ 4] = (unsigned char) ((sha_info->digest[1] >> 24) & 0xff);
    digest[ 5] = (unsigned char) ((sha_info->digest[1] >> 16) & 0xff);
    digest[ 6] = (unsigned char) ((sha_info->digest[1] >>  8) & 0xff);
    digest[ 7] = (unsigned char) ((sha_info->digest[1]      ) & 0xff);
    digest[ 8] = (unsigned char) ((sha_info->digest[2] >> 24) & 0xff);
    digest[ 9] = (unsigned char) ((sha_info->digest[2] >> 16) & 0xff);
    digest[10] = (unsigned char) ((sha_info->digest[2] >>  8) & 0xff);
    digest[11] = (unsigned char) ((sha_info->digest[2]      ) & 0xff);
    digest[12] = (unsigned char) ((sha_info->digest[3] >> 24) & 0xff);
    digest[13] = (unsigned char) ((sha_info->digest[3] >> 16) & 0xff);
    digest[14] = (unsigned char) ((sha_info->digest[3] >>  8) & 0xff);
    digest[15] = (unsigned char) ((sha_info->digest[3]      ) & 0xff);
    digest[16] = (unsigned char) ((sha_info->digest[4] >> 24) & 0xff);
    digest[17] = (unsigned char) ((sha_info->digest[4] >> 16) & 0xff);
    digest[18] = (unsigned char) ((sha_info->digest[4] >>  8) & 0xff);
    digest[19] = (unsigned char) ((sha_info->digest[4]      ) & 0xff);
}
#endif

/* finish computing the SHA digest */
static void sha_final(SHA_INFO *sha_info)
{
    int count;
    U32 bit_count;

    bit_count = sha_info->count;
    count = (int) ((bit_count >> 3) & 0x3f);
    ((U8 *) sha_info->data)[count++] = 0x80;

    if (count > SHA_BLOCKSIZE - 8) {
        memset(((U8 *) sha_info->data) + count, 0, SHA_BLOCKSIZE - count);
        sha_transform(sha_info);
        memset((U8 *) sha_info->data, 0, SHA_BLOCKSIZE - 8);
    } else {
        memset(((U8 *) sha_info->data) + count, 0, SHA_BLOCKSIZE - 8 - count);
    }

    sha_info->data[56] = 0;
    sha_info->data[57] = 0;
    sha_info->data[58] = 0;
    sha_info->data[59] = 0;
    sha_info->data[60] = (bit_count >> 24) & 0xff;
    sha_info->data[61] = (bit_count >> 16) & 0xff;
    sha_info->data[62] = (bit_count >>  8) & 0xff;
    sha_info->data[63] = (bit_count >>  0) & 0xff;

    sha_transform (sha_info);
}

#define TRIALCHAR "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!#$%&()*+,-./;<=>?@[]{}^_|"

static char       nextenc[256];

static char rand_char ()
{
  return TRIALCHAR[rand () % sizeof (TRIALCHAR)];
}

static int zprefix (ULONG n)
{
  static char zp[256] =
    {
      8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
      3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
      2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
      2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    };

  return
    n > 0xffffff ?      zp[n >> 24]
    : n > 0xffff ?  8 + zp[n >> 16]
    : n >   0xff ? 16 + zp[n >>  8]
    :              24 + zp[n];
}

MODULE = Digest::Hashcash               PACKAGE = Digest::Hashcash

BOOT:
{
   int i;

   for (i = 0; i < sizeof (TRIALCHAR); i++)
     nextenc[TRIALCHAR[i]] = TRIALCHAR[(i + 1) % sizeof (TRIALCHAR)];
}

PROTOTYPES: ENABLE

int
_estimate_time (float seconds = 2, float minfactor = 1)
        CODE:
        RETVAL = minfactor;
        OUTPUT:
        RETVAL

SV *
_gentoken (int collisions, IV timestamp, char *resource, char *trial = "", int extrarand = 0)
        CODE:
        SHA_INFO ctx1, ctx;
        char *token, *seq, *s;
        int toklen, i;
        time_t tstamp = timestamp ? timestamp : time (0);
        struct tm *tm = gmtime (&tstamp);

        New (0, token,
            1 + 1                    // version
            + 12 + 1                 // time field sans century
            + strlen (resource) + 1  // ressource
            + strlen (trial) + extrarand + 8 + 1 // trial
            + 1,
            char);

        if (!token)
          croak ("out of memory");

        if (collisions > 32)
          croak ("collisions must be <= 32 in this implementation\n");

        toklen = sprintf (token, "%d:%02d%02d%02d%02d%02d%02d:%s:%s",
                          0, tm->tm_year % 100, tm->tm_mon + 1, tm->tm_mday,
                          tm->tm_hour, tm->tm_min, tm->tm_sec,
                          resource, trial);

        i = toklen + extrarand;
        while (toklen < i)
          token[toklen++] = rand_char ();

        sha_init (&ctx1);
        sha_update (&ctx1, token, toklen);

        seq = token + toklen;
        i +=  8;
        while (toklen < i)
          token[toklen++] = rand_char ();

        for (;;)
          {
            ctx = ctx1; // this "optimization" can help a lot for longer resource strings
            sha_update (&ctx, seq, 8);
            sha_final (&ctx);

            i = zprefix (ctx.digest[0]);

            if (i >= collisions)
              break;

            s = seq;
            do {
              *s = nextenc [*s];
            } while (*s++ == 'a');
          }

        RETVAL = newSVpvn (token, toklen);
        OUTPUT:
        RETVAL

int
_prefixlen (SV *tok)
        CODE:
        STRLEN toklen;
        char *token = SvPV (tok, toklen);
        SHA_INFO ctx;

        sha_init (&ctx);
        sha_update (&ctx, token, toklen);
        sha_final (&ctx);

        RETVAL = zprefix (ctx.digest[0]);
        OUTPUT:
        RETVAL


Revision:	1.1
Committed:	Sat Sep 6 22:12:00 2003 UTC (21 years ago) by root
Branch:	MAIN
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	#include "EXTERN.h"
2			#include "perl.h"
3			#include "XSUB.h"
4
5			#include <time.h>
6			#include <stdlib.h>
7			#include <stdint.h>
8
9			/* NIST Secure Hash Algorithm */
10			/* heavily modified by Uwe Hollerbach <uh@alumni.caltech edu> */
11			/* from Peter C. Gutmann's implementation as found in */
12			/* Applied Cryptography by Bruce Schneier */
13			/* Further modifications to include the "UNRAVEL" stuff, below */
14
15			/* This code is in the public domain */
16
17			/* pcg: I was tempted to just rip this code off, after all, if you don't
18			* demand anything I am inclined not to give anything. Sigh something
19			* kept me from doing it, so here's the truth: I took this code from the
20			* SHA1 perl module, since it looked reasonably well-crafted. I modified
21			* it here and there, though.
22			*/
23
24			/* don't expect _too_ much from compilers for now. */
25			#if __GNUC_MAJOR > 2
26			# define restrict __restrict__
27			#elif __STDC_VERSION__ < 199900
28			# define restrict
29			#endif
30
31			/* Useful defines & typedefs */
32
33			#if defined(U64TYPE) && (defined(USE_64_BIT_INT) \|\| ((BYTEORDER != 0x1234) && (BYTEORDER != 0x4321)))
34			typedef U64TYPE ULONG;
35			# if BYTEORDER == 0x1234
36			# undef BYTEORDER
37			# define BYTEORDER 0x12345678
38			# elif BYTEORDER == 0x4321
39			# undef BYTEORDER
40			# define BYTEORDER 0x87654321
41			# endif
42			#else
43			typedef uint_fast32_t ULONG; /* 32-or-more-bit quantity */
44			#endif
45
46			#define SHA_BLOCKSIZE 64
47			#define SHA_DIGESTSIZE 20
48
49			typedef struct {
50			ULONG digest[5]; /* message digest */
51			ULONG count; /* 32-bit bit count */
52			U8 data[SHA_BLOCKSIZE]; /* SHA data buffer */
53			int local; /* unprocessed amount in data */
54			} SHA_INFO;
55
56
57			/* UNRAVEL should be fastest & biggest */
58			/* UNROLL_LOOPS should be just as big, but slightly slower */
59			/* both undefined should be smallest and slowest */
60
61			#define SHA_VERSION 1
62			#define UNRAVEL
63			/* #define UNROLL_LOOPS */
64
65			/* SHA f()-functions */
66			#define f1(x,y,z) ((x & y) \| (~x & z))
67			#define f2(x,y,z) (x ^ y ^ z)
68			#define f3(x,y,z) ((x & y) \| (x & z) \| (y & z))
69			#define f4(x,y,z) (x ^ y ^ z)
70
71			/* SHA constants */
72			#define CONST1 0x5a827999L
73			#define CONST2 0x6ed9eba1L
74			#define CONST3 0x8f1bbcdcL
75			#define CONST4 0xca62c1d6L
76
77			/* truncate to 32 bits -- should be a null op on 32-bit machines */
78			#define T32(x) ((x) & 0xffffffffL)
79
80			/* 32-bit rotate */
81			#define R32(x,n) T32(((x << n) \| (x >> (32 - n))))
82
83			/* the generic case, for when the overall rotation is not unraveled */
84			#define FG(n) \
85			T = T32(R32(A,5) + f##n(B,C,D) + E + *WP++ + CONST##n); \
86			E = D; D = C; C = R32(B,30); B = A; A = T
87
88			/* specific cases, for when the overall rotation is unraveled */
89			#define FA(n) \
90			T = T32(R32(A,5) + f##n(B,C,D) + E + *WP++ + CONST##n); B = R32(B,30)
91
92			#define FB(n) \
93			E = T32(R32(T,5) + f##n(A,B,C) + D + *WP++ + CONST##n); A = R32(A,30)
94
95			#define FC(n) \
96			D = T32(R32(E,5) + f##n(T,A,B) + C + *WP++ + CONST##n); T = R32(T,30)
97
98			#define FD(n) \
99			C = T32(R32(D,5) + f##n(E,T,A) + B + *WP++ + CONST##n); E = R32(E,30)
100
101			#define FE(n) \
102			B = T32(R32(C,5) + f##n(D,E,T) + A + *WP++ + CONST##n); D = R32(D,30)
103
104			#define FT(n) \
105			A = T32(R32(B,5) + f##n(C,D,E) + T + *WP++ + CONST##n); C = R32(C,30)
106
107
108			static void sha_transform(restrict SHA_INFO *sha_info)
109			{
110			int i;
111			U8 *dp;
112			ULONG T, A, B, C, D, E, W[80], *WP;
113
114			dp = sha_info->data;
115
116			/*
117			the following makes sure that at least one code block below is
118			traversed or an error is reported, without the necessity for nested
119			preprocessor if/else/endif blocks, which are a great pain in the
120			nether regions of the anatomy...
121			*/
122			#undef SWAP_DONE
123
124			#if BYTEORDER == 0x1234
125			#define SWAP_DONE
126			assert(sizeof(ULONG) == 4);
127			for (i = 0; i < 16; ++i) {
128			T = ((ULONG ) dp);
129			dp += 4;
130			W[i] = ((T << 24) & 0xff000000) \| ((T << 8) & 0x00ff0000) \|
131			((T >> 8) & 0x0000ff00) \| ((T >> 24) & 0x000000ff);
132			}
133			#endif
134
135			#if BYTEORDER == 0x4321
136			#define SWAP_DONE
137			assert(sizeof(ULONG) == 4);
138			for (i = 0; i < 16; ++i) {
139			T = ((ULONG ) dp);
140			dp += 4;
141			W[i] = T32(T);
142			}
143			#endif
144
145			#if BYTEORDER == 0x12345678
146			#define SWAP_DONE
147			assert(sizeof(ULONG) == 8);
148			for (i = 0; i < 16; i += 2) {
149			T = ((ULONG ) dp);
150			dp += 8;
151			W[i] = ((T << 24) & 0xff000000) \| ((T << 8) & 0x00ff0000) \|
152			((T >> 8) & 0x0000ff00) \| ((T >> 24) & 0x000000ff);
153			T >>= 32;
154			W[i+1] = ((T << 24) & 0xff000000) \| ((T << 8) & 0x00ff0000) \|
155			((T >> 8) & 0x0000ff00) \| ((T >> 24) & 0x000000ff);
156			}
157			#endif
158
159			#if BYTEORDER == 0x87654321
160			#define SWAP_DONE
161			assert(sizeof(ULONG) == 8);
162			for (i = 0; i < 16; i += 2) {
163			T = ((ULONG ) dp);
164			dp += 8;
165			W[i] = T32(T >> 32);
166			W[i+1] = T32(T);
167			}
168			#endif
169
170			#ifndef SWAP_DONE
171			#error Unknown byte order -- you need to add code here
172			#endif /* SWAP_DONE */
173
174			for (i = 16; i < 80; ++i) {
175			W[i] = W[i-3] ^ W[i-8] ^ W[i-14] ^ W[i-16];
176			#if (SHA_VERSION == 1)
177			W[i] = R32(W[i], 1);
178			#endif /* SHA_VERSION */
179			}
180			A = sha_info->digest[0];
181			B = sha_info->digest[1];
182			C = sha_info->digest[2];
183			D = sha_info->digest[3];
184			E = sha_info->digest[4];
185			WP = W;
186			#ifdef UNRAVEL
187			FA(1); FB(1); FC(1); FD(1); FE(1); FT(1); FA(1); FB(1); FC(1); FD(1);
188			FE(1); FT(1); FA(1); FB(1); FC(1); FD(1); FE(1); FT(1); FA(1); FB(1);
189			FC(2); FD(2); FE(2); FT(2); FA(2); FB(2); FC(2); FD(2); FE(2); FT(2);
190			FA(2); FB(2); FC(2); FD(2); FE(2); FT(2); FA(2); FB(2); FC(2); FD(2);
191			FE(3); FT(3); FA(3); FB(3); FC(3); FD(3); FE(3); FT(3); FA(3); FB(3);
192			FC(3); FD(3); FE(3); FT(3); FA(3); FB(3); FC(3); FD(3); FE(3); FT(3);
193			FA(4); FB(4); FC(4); FD(4); FE(4); FT(4); FA(4); FB(4); FC(4); FD(4);
194			FE(4); FT(4); FA(4); FB(4); FC(4); FD(4); FE(4); FT(4); FA(4); FB(4);
195			sha_info->digest[0] = T32(sha_info->digest[0] + E);
196			sha_info->digest[1] = T32(sha_info->digest[1] + T);
197			sha_info->digest[2] = T32(sha_info->digest[2] + A);
198			sha_info->digest[3] = T32(sha_info->digest[3] + B);
199			sha_info->digest[4] = T32(sha_info->digest[4] + C);
200			#else /* !UNRAVEL */
201			#ifdef UNROLL_LOOPS
202			FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1);
203			FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1); FG(1);
204			FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2);
205			FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2); FG(2);
206			FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3);
207			FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3); FG(3);
208			FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4);
209			FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4); FG(4);
210			#else /* !UNROLL_LOOPS */
211			for (i = 0; i < 20; ++i) { FG(1); }
212			for (i = 20; i < 40; ++i) { FG(2); }
213			for (i = 40; i < 60; ++i) { FG(3); }
214			for (i = 60; i < 80; ++i) { FG(4); }
215			#endif /* !UNROLL_LOOPS */
216			sha_info->digest[0] = T32(sha_info->digest[0] + A);
217			sha_info->digest[1] = T32(sha_info->digest[1] + B);
218			sha_info->digest[2] = T32(sha_info->digest[2] + C);
219			sha_info->digest[3] = T32(sha_info->digest[3] + D);
220			sha_info->digest[4] = T32(sha_info->digest[4] + E);
221			#endif /* !UNRAVEL */
222			}
223
224			/* initialize the SHA digest */
225
226			static void sha_init(restrict SHA_INFO *sha_info)
227			{
228			sha_info->digest[0] = 0x67452301L;
229			sha_info->digest[1] = 0xefcdab89L;
230			sha_info->digest[2] = 0x98badcfeL;
231			sha_info->digest[3] = 0x10325476L;
232			sha_info->digest[4] = 0xc3d2e1f0L;
233			sha_info->count = 0L;
234			sha_info->local = 0;
235			}
236
237			/* update the SHA digest */
238
239			static void sha_update(restrict SHA_INFO sha_info, restrict U8 buffer, int count)
240			{
241			int i;
242
243			sha_info->count += count << 3;
244			if (sha_info->local) {
245			i = SHA_BLOCKSIZE - sha_info->local;
246			if (i > count) {
247			i = count;
248			}
249			memcpy(((U8 *) sha_info->data) + sha_info->local, buffer, i);
250			count -= i;
251			buffer += i;
252			sha_info->local += i;
253			if (sha_info->local == SHA_BLOCKSIZE) {
254			sha_transform(sha_info);
255			} else {
256			return;
257			}
258			}
259			while (count >= SHA_BLOCKSIZE) {
260			memcpy(sha_info->data, buffer, SHA_BLOCKSIZE);
261			buffer += SHA_BLOCKSIZE;
262			count -= SHA_BLOCKSIZE;
263			sha_transform(sha_info);
264			}
265			memcpy(sha_info->data, buffer, count);
266			sha_info->local = count;
267			}
268
269
270			#if 0
271			static void sha_transform_and_copy (unsigned char digest[20], restrict SHA_INFO *sha_info)
272			{
273			sha_transform (sha_info);
274
275			digest[ 0] = (unsigned char) ((sha_info->digest[0] >> 24) & 0xff);
276			digest[ 1] = (unsigned char) ((sha_info->digest[0] >> 16) & 0xff);
277			digest[ 2] = (unsigned char) ((sha_info->digest[0] >> 8) & 0xff);
278			digest[ 3] = (unsigned char) ((sha_info->digest[0] ) & 0xff);
279			digest[ 4] = (unsigned char) ((sha_info->digest[1] >> 24) & 0xff);
280			digest[ 5] = (unsigned char) ((sha_info->digest[1] >> 16) & 0xff);
281			digest[ 6] = (unsigned char) ((sha_info->digest[1] >> 8) & 0xff);
282			digest[ 7] = (unsigned char) ((sha_info->digest[1] ) & 0xff);
283			digest[ 8] = (unsigned char) ((sha_info->digest[2] >> 24) & 0xff);
284			digest[ 9] = (unsigned char) ((sha_info->digest[2] >> 16) & 0xff);
285			digest[10] = (unsigned char) ((sha_info->digest[2] >> 8) & 0xff);
286			digest[11] = (unsigned char) ((sha_info->digest[2] ) & 0xff);
287			digest[12] = (unsigned char) ((sha_info->digest[3] >> 24) & 0xff);
288			digest[13] = (unsigned char) ((sha_info->digest[3] >> 16) & 0xff);
289			digest[14] = (unsigned char) ((sha_info->digest[3] >> 8) & 0xff);
290			digest[15] = (unsigned char) ((sha_info->digest[3] ) & 0xff);
291			digest[16] = (unsigned char) ((sha_info->digest[4] >> 24) & 0xff);
292			digest[17] = (unsigned char) ((sha_info->digest[4] >> 16) & 0xff);
293			digest[18] = (unsigned char) ((sha_info->digest[4] >> 8) & 0xff);
294			digest[19] = (unsigned char) ((sha_info->digest[4] ) & 0xff);
295			}
296			#endif
297
298			/* finish computing the SHA digest */
299			static void sha_final(SHA_INFO *sha_info)
300			{
301			int count;
302			U32 bit_count;
303
304			bit_count = sha_info->count;
305			count = (int) ((bit_count >> 3) & 0x3f);
306			((U8 *) sha_info->data)[count++] = 0x80;
307
308			if (count > SHA_BLOCKSIZE - 8) {
309			memset(((U8 *) sha_info->data) + count, 0, SHA_BLOCKSIZE - count);
310			sha_transform(sha_info);
311			memset((U8 *) sha_info->data, 0, SHA_BLOCKSIZE - 8);
312			} else {
313			memset(((U8 *) sha_info->data) + count, 0, SHA_BLOCKSIZE - 8 - count);
314			}
315
316			sha_info->data[56] = 0;
317			sha_info->data[57] = 0;
318			sha_info->data[58] = 0;
319			sha_info->data[59] = 0;
320			sha_info->data[60] = (bit_count >> 24) & 0xff;
321			sha_info->data[61] = (bit_count >> 16) & 0xff;
322			sha_info->data[62] = (bit_count >> 8) & 0xff;
323			sha_info->data[63] = (bit_count >> 0) & 0xff;
324
325			sha_transform (sha_info);
326			}
327
328			#define TRIALCHAR "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!#$%&()*+,-./;<=>?@[]{}^_\|"
329
330			static char nextenc[256];
331
332			static char rand_char ()
333			{
334			return TRIALCHAR[rand () % sizeof (TRIALCHAR)];
335			}
336
337			static int zprefix (ULONG n)
338			{
339			static char zp[256] =
340			{
341			8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
342			3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
343			2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
344			2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
345			1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
346			1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
347			1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
348			1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
349			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
350			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
351			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
352			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
353			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
354			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
355			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
356			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
357			};
358
359			return
360			n > 0xffffff ? zp[n >> 24]
361			: n > 0xffff ? 8 + zp[n >> 16]
362			: n > 0xff ? 16 + zp[n >> 8]
363			: 24 + zp[n];
364			}
365
366			MODULE = Digest::Hashcash PACKAGE = Digest::Hashcash
367
368			BOOT:
369			{
370			int i;
371
372			for (i = 0; i < sizeof (TRIALCHAR); i++)
373			nextenc[TRIALCHAR[i]] = TRIALCHAR[(i + 1) % sizeof (TRIALCHAR)];
374			}
375
376			PROTOTYPES: ENABLE
377
378			int
379			_estimate_time (float seconds = 2, float minfactor = 1)
380			CODE:
381			RETVAL = minfactor;
382			OUTPUT:
383			RETVAL
384
385			SV *
386			_gentoken (int collisions, IV timestamp, char resource, char trial = "", int extrarand = 0)
387			CODE:
388			SHA_INFO ctx1, ctx;
389			char token, seq, *s;
390			int toklen, i;
391			time_t tstamp = timestamp ? timestamp : time (0);
392			struct tm *tm = gmtime (&tstamp);
393
394			New (0, token,
395			1 + 1 // version
396			+ 12 + 1 // time field sans century
397			+ strlen (resource) + 1 // ressource
398			+ strlen (trial) + extrarand + 8 + 1 // trial
399			+ 1,
400			char);
401
402			if (!token)
403			croak ("out of memory");
404
405			if (collisions > 32)
406			croak ("collisions must be <= 32 in this implementation\n");
407
408			toklen = sprintf (token, "%d:%02d%02d%02d%02d%02d%02d:%s:%s",
409			0, tm->tm_year % 100, tm->tm_mon + 1, tm->tm_mday,
410			tm->tm_hour, tm->tm_min, tm->tm_sec,
411			resource, trial);
412
413			i = toklen + extrarand;
414			while (toklen < i)
415			token[toklen++] = rand_char ();
416
417			sha_init (&ctx1);
418			sha_update (&ctx1, token, toklen);
419
420			seq = token + toklen;
421			i += 8;
422			while (toklen < i)
423			token[toklen++] = rand_char ();
424
425			for (;;)
426			{
427			ctx = ctx1; // this "optimization" can help a lot for longer resource strings
428			sha_update (&ctx, seq, 8);
429			sha_final (&ctx);
430
431			i = zprefix (ctx.digest[0]);
432
433			if (i >= collisions)
434			break;
435
436			s = seq;
437			do {
438			s = nextenc [s];
439			} while (*s++ == 'a');
440			}
441
442			RETVAL = newSVpvn (token, toklen);
443			OUTPUT:
444			RETVAL
445
446			int
447			_prefixlen (SV *tok)
448			CODE:
449			STRLEN toklen;
450			char *token = SvPV (tok, toklen);
451			SHA_INFO ctx;
452
453			sha_init (&ctx);
454			sha_update (&ctx, token, toklen);
455			sha_final (&ctx);
456
457			RETVAL = zprefix (ctx.digest[0]);
458			OUTPUT:
459			RETVAL
460
461