ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/Digest-Hashcash/Hashcash.xs
Revision: 1.3
Committed: Thu Sep 11 06:20:26 2003 UTC (21 years, 1 month ago) by root
Branch: MAIN
Changes since 1.2: +6 -0 lines
Log Message:
*** empty log message ***

File Contents

# 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 root 1.2 #if __GNUC__ > 2
26 root 1.1 # define restrict __restrict__
27 root 1.2 # define inline __inline__
28     # ifdef __i386
29     # define GCCX86ASM 1
30     # endif
31 root 1.1 #elif __STDC_VERSION__ < 199900
32     # define restrict
33 root 1.2 # define inline
34 root 1.1 #endif
35    
36     /* Useful defines & typedefs */
37    
38     #if defined(U64TYPE) && (defined(USE_64_BIT_INT) || ((BYTEORDER != 0x1234) && (BYTEORDER != 0x4321)))
39     typedef U64TYPE ULONG;
40     # if BYTEORDER == 0x1234
41     # undef BYTEORDER
42     # define BYTEORDER 0x12345678
43     # elif BYTEORDER == 0x4321
44     # undef BYTEORDER
45     # define BYTEORDER 0x87654321
46     # endif
47     #else
48     typedef uint_fast32_t ULONG; /* 32-or-more-bit quantity */
49     #endif
50    
51 root 1.2 #if GCCX86ASM
52     # define zprefix(n) ({ int _r; __asm__ ("bsrl %1, %0" : "=r" (_r) : "r" (n)); 31 - _r ; })
53     #else
54     static int zprefix (ULONG n)
55     {
56     static char zp[256] =
57     {
58     8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
59     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
60     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
61     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
62     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
63     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
64     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
65     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
66     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
67     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
68     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
69     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
70     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
71     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
72     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
73     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
74     };
75    
76     return
77     n > 0xffffff ? zp[n >> 24]
78     : n > 0xffff ? 8 + zp[n >> 16]
79     : n > 0xff ? 16 + zp[n >> 8]
80     : 24 + zp[n];
81     }
82     #endif
83    
84 root 1.1 #define SHA_BLOCKSIZE 64
85     #define SHA_DIGESTSIZE 20
86    
87     typedef struct {
88     ULONG digest[5]; /* message digest */
89     ULONG count; /* 32-bit bit count */
90 root 1.2 int local; /* unprocessed amount in data */
91 root 1.1 U8 data[SHA_BLOCKSIZE]; /* SHA data buffer */
92     } SHA_INFO;
93    
94    
95     /* SHA f()-functions */
96     #define f1(x,y,z) ((x & y) | (~x & z))
97     #define f2(x,y,z) (x ^ y ^ z)
98     #define f3(x,y,z) ((x & y) | (x & z) | (y & z))
99     #define f4(x,y,z) (x ^ y ^ z)
100    
101     /* SHA constants */
102     #define CONST1 0x5a827999L
103     #define CONST2 0x6ed9eba1L
104     #define CONST3 0x8f1bbcdcL
105     #define CONST4 0xca62c1d6L
106    
107     /* truncate to 32 bits -- should be a null op on 32-bit machines */
108     #define T32(x) ((x) & 0xffffffffL)
109    
110     /* 32-bit rotate */
111     #define R32(x,n) T32(((x << n) | (x >> (32 - n))))
112    
113     /* specific cases, for when the overall rotation is unraveled */
114     #define FA(n) \
115     T = T32(R32(A,5) + f##n(B,C,D) + E + *WP++ + CONST##n); B = R32(B,30)
116    
117     #define FB(n) \
118     E = T32(R32(T,5) + f##n(A,B,C) + D + *WP++ + CONST##n); A = R32(A,30)
119    
120     #define FC(n) \
121     D = T32(R32(E,5) + f##n(T,A,B) + C + *WP++ + CONST##n); T = R32(T,30)
122    
123     #define FD(n) \
124     C = T32(R32(D,5) + f##n(E,T,A) + B + *WP++ + CONST##n); E = R32(E,30)
125    
126     #define FE(n) \
127     B = T32(R32(C,5) + f##n(D,E,T) + A + *WP++ + CONST##n); D = R32(D,30)
128    
129     #define FT(n) \
130     A = T32(R32(B,5) + f##n(C,D,E) + T + *WP++ + CONST##n); C = R32(C,30)
131    
132 root 1.2 static void sha_transform(SHA_INFO *restrict sha_info)
133 root 1.1 {
134     int i;
135     U8 *dp;
136 root 1.2 ULONG T, A, B, C, D, E, W[80], *restrict WP;
137 root 1.1
138     dp = sha_info->data;
139    
140     #if BYTEORDER == 0x1234
141     assert(sizeof(ULONG) == 4);
142 root 1.2 # ifdef HAS_NTOHL
143     for (i = 0; i < 16; ++i) {
144     T = *((ULONG *) dp);
145     dp += 4;
146     W[i] = ntohl (T);
147     }
148     # else
149 root 1.1 for (i = 0; i < 16; ++i) {
150     T = *((ULONG *) dp);
151     dp += 4;
152     W[i] = ((T << 24) & 0xff000000) | ((T << 8) & 0x00ff0000) |
153     ((T >> 8) & 0x0000ff00) | ((T >> 24) & 0x000000ff);
154     }
155 root 1.2 # endif
156     #elif BYTEORDER == 0x4321
157 root 1.1 assert(sizeof(ULONG) == 4);
158     for (i = 0; i < 16; ++i) {
159     T = *((ULONG *) dp);
160     dp += 4;
161     W[i] = T32(T);
162     }
163 root 1.2 #elif BYTEORDER == 0x12345678
164 root 1.1 assert(sizeof(ULONG) == 8);
165     for (i = 0; i < 16; i += 2) {
166     T = *((ULONG *) dp);
167     dp += 8;
168     W[i] = ((T << 24) & 0xff000000) | ((T << 8) & 0x00ff0000) |
169     ((T >> 8) & 0x0000ff00) | ((T >> 24) & 0x000000ff);
170     T >>= 32;
171     W[i+1] = ((T << 24) & 0xff000000) | ((T << 8) & 0x00ff0000) |
172     ((T >> 8) & 0x0000ff00) | ((T >> 24) & 0x000000ff);
173     }
174 root 1.2 #elif BYTEORDER == 0x87654321
175 root 1.1 assert(sizeof(ULONG) == 8);
176     for (i = 0; i < 16; i += 2) {
177     T = *((ULONG *) dp);
178     dp += 8;
179     W[i] = T32(T >> 32);
180     W[i+1] = T32(T);
181     }
182 root 1.2 #else
183     #error Unknown byte order -- you need to add code here
184 root 1.1 #endif
185    
186 root 1.2 for (i = 16; i < 80; ++i)
187     {
188     T = W[i-3] ^ W[i-8] ^ W[i-14] ^ W[i-16];
189     W[i] = R32(T,1);
190     }
191 root 1.1
192     A = sha_info->digest[0];
193     B = sha_info->digest[1];
194     C = sha_info->digest[2];
195     D = sha_info->digest[3];
196     E = sha_info->digest[4];
197 root 1.2
198 root 1.1 WP = W;
199     FA(1); FB(1); FC(1); FD(1); FE(1); FT(1); FA(1); FB(1); FC(1); FD(1);
200     FE(1); FT(1); FA(1); FB(1); FC(1); FD(1); FE(1); FT(1); FA(1); FB(1);
201     FC(2); FD(2); FE(2); FT(2); FA(2); FB(2); FC(2); FD(2); FE(2); FT(2);
202     FA(2); FB(2); FC(2); FD(2); FE(2); FT(2); FA(2); FB(2); FC(2); FD(2);
203     FE(3); FT(3); FA(3); FB(3); FC(3); FD(3); FE(3); FT(3); FA(3); FB(3);
204     FC(3); FD(3); FE(3); FT(3); FA(3); FB(3); FC(3); FD(3); FE(3); FT(3);
205     FA(4); FB(4); FC(4); FD(4); FE(4); FT(4); FA(4); FB(4); FC(4); FD(4);
206     FE(4); FT(4); FA(4); FB(4); FC(4); FD(4); FE(4); FT(4); FA(4); FB(4);
207 root 1.2
208 root 1.1 sha_info->digest[0] = T32(sha_info->digest[0] + E);
209     sha_info->digest[1] = T32(sha_info->digest[1] + T);
210     sha_info->digest[2] = T32(sha_info->digest[2] + A);
211     sha_info->digest[3] = T32(sha_info->digest[3] + B);
212     sha_info->digest[4] = T32(sha_info->digest[4] + C);
213     }
214    
215     /* initialize the SHA digest */
216    
217 root 1.2 static void sha_init(SHA_INFO *restrict sha_info)
218 root 1.1 {
219     sha_info->digest[0] = 0x67452301L;
220     sha_info->digest[1] = 0xefcdab89L;
221     sha_info->digest[2] = 0x98badcfeL;
222     sha_info->digest[3] = 0x10325476L;
223     sha_info->digest[4] = 0xc3d2e1f0L;
224     sha_info->count = 0L;
225     sha_info->local = 0;
226     }
227    
228     /* update the SHA digest */
229    
230 root 1.2 static void sha_update(SHA_INFO *restrict sha_info, U8 *restrict buffer, int count)
231 root 1.1 {
232     int i;
233    
234 root 1.2 sha_info->count += count;
235 root 1.1 if (sha_info->local) {
236     i = SHA_BLOCKSIZE - sha_info->local;
237     if (i > count) {
238     i = count;
239     }
240     memcpy(((U8 *) sha_info->data) + sha_info->local, buffer, i);
241     count -= i;
242     buffer += i;
243     sha_info->local += i;
244     if (sha_info->local == SHA_BLOCKSIZE) {
245     sha_transform(sha_info);
246     } else {
247     return;
248     }
249     }
250     while (count >= SHA_BLOCKSIZE) {
251     memcpy(sha_info->data, buffer, SHA_BLOCKSIZE);
252     buffer += SHA_BLOCKSIZE;
253     count -= SHA_BLOCKSIZE;
254     sha_transform(sha_info);
255     }
256     memcpy(sha_info->data, buffer, count);
257     sha_info->local = count;
258     }
259    
260     /* finish computing the SHA digest */
261 root 1.2 static int sha_final(SHA_INFO *sha_info)
262 root 1.1 {
263 root 1.2 int count = sha_info->count;
264     int local = sha_info->local;
265 root 1.1
266 root 1.2 sha_info->data[local] = 0x80;
267 root 1.1
268 root 1.2 if (sha_info->local >= SHA_BLOCKSIZE - 8) {
269     memset(sha_info->data + local + 1, 0, SHA_BLOCKSIZE - 1 - local);
270     sha_transform(sha_info);
271     memset(sha_info->data, 0, SHA_BLOCKSIZE - 2);
272     } else {
273     memset(sha_info->data + local + 1, 0, SHA_BLOCKSIZE - 3 - local);
274     }
275    
276     sha_info->data[62] = count >> 5;
277     sha_info->data[63] = count << 3;
278    
279     sha_transform (sha_info);
280    
281     return sha_info->digest[0]
282     ? zprefix (sha_info->digest[0])
283     : zprefix (sha_info->digest[1]) + 32;
284 root 1.1 }
285    
286     #define TRIALCHAR "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!#$%&()*+,-./;<=>?@[]{}^_|"
287    
288     static char nextenc[256];
289    
290     static char rand_char ()
291     {
292     return TRIALCHAR[rand () % sizeof (TRIALCHAR)];
293     }
294    
295 root 1.2 typedef double (*NVTime)(void);
296    
297     static double simple_nvtime (void)
298     {
299     return time (0);
300     }
301    
302     static NVTime get_nvtime (void)
303 root 1.1 {
304 root 1.2 SV **svp = hv_fetch (PL_modglobal, "Time::NVtime", 12, 0);
305    
306     if (svp && SvIOK(*svp))
307     return INT2PTR(NVTime, SvIV(*svp));
308     else
309     return simple_nvtime;
310 root 1.1
311     }
312    
313     MODULE = Digest::Hashcash PACKAGE = Digest::Hashcash
314    
315     BOOT:
316     {
317     int i;
318    
319     for (i = 0; i < sizeof (TRIALCHAR); i++)
320     nextenc[TRIALCHAR[i]] = TRIALCHAR[(i + 1) % sizeof (TRIALCHAR)];
321     }
322    
323     PROTOTYPES: ENABLE
324    
325 root 1.2 # could be improved quite a bit in accuracy
326     NV
327     _estimate_rounds ()
328 root 1.1 CODE:
329 root 1.3 {
330 root 1.2 char data[40];
331     NVTime nvtime = get_nvtime ();
332     NV t1, t2, t;
333     int count = 0;
334     SHA_INFO ctx;
335    
336     t = nvtime ();
337     do {
338     t1 = nvtime ();
339     } while (t == t1);
340    
341     t = t2 = nvtime ();
342     do {
343     volatile int i;
344     sha_init (&ctx);
345     sha_update (&ctx, data, sizeof (data));
346     i = sha_final (&ctx);
347    
348     if (!(++count & 1023))
349     t2 = nvtime ();
350    
351     } while (t == t2);
352    
353     RETVAL = (NV)count / (t2 - t1);
354 root 1.3 }
355 root 1.1 OUTPUT:
356     RETVAL
357    
358     SV *
359 root 1.2 _gentoken (int size, IV timestamp, char *resource, char *trial = "", int extrarand = 0)
360 root 1.1 CODE:
361 root 1.3 {
362 root 1.1 SHA_INFO ctx1, ctx;
363     char *token, *seq, *s;
364     int toklen, i;
365     time_t tstamp = timestamp ? timestamp : time (0);
366     struct tm *tm = gmtime (&tstamp);
367    
368     New (0, token,
369     1 + 1 // version
370     + 12 + 1 // time field sans century
371     + strlen (resource) + 1 // ressource
372     + strlen (trial) + extrarand + 8 + 1 // trial
373     + 1,
374     char);
375    
376     if (!token)
377     croak ("out of memory");
378    
379 root 1.2 if (size > 64)
380     croak ("size must be <= 64 in this implementation\n");
381 root 1.1
382     toklen = sprintf (token, "%d:%02d%02d%02d%02d%02d%02d:%s:%s",
383     0, tm->tm_year % 100, tm->tm_mon + 1, tm->tm_mday,
384     tm->tm_hour, tm->tm_min, tm->tm_sec,
385     resource, trial);
386    
387 root 1.2 if (toklen > 8000)
388     croak ("token length must be <= 8000 in this implementation\n");
389    
390 root 1.1 i = toklen + extrarand;
391     while (toklen < i)
392     token[toklen++] = rand_char ();
393    
394     sha_init (&ctx1);
395     sha_update (&ctx1, token, toklen);
396    
397     seq = token + toklen;
398     i += 8;
399     while (toklen < i)
400     token[toklen++] = rand_char ();
401    
402     for (;;)
403     {
404     ctx = ctx1; // this "optimization" can help a lot for longer resource strings
405     sha_update (&ctx, seq, 8);
406 root 1.2 i = sha_final (&ctx);
407 root 1.1
408 root 1.2 if (i >= size)
409 root 1.1 break;
410    
411     s = seq;
412     do {
413     *s = nextenc [*s];
414     } while (*s++ == 'a');
415     }
416    
417     RETVAL = newSVpvn (token, toklen);
418 root 1.3 }
419 root 1.1 OUTPUT:
420     RETVAL
421    
422     int
423     _prefixlen (SV *tok)
424     CODE:
425 root 1.3 {
426 root 1.1 STRLEN toklen;
427     char *token = SvPV (tok, toklen);
428     SHA_INFO ctx;
429    
430     sha_init (&ctx);
431     sha_update (&ctx, token, toklen);
432 root 1.2 RETVAL = sha_final (&ctx);
433 root 1.3 }
434 root 1.1 OUTPUT:
435     RETVAL
436    
437