Logo Search packages:      
Sourcecode: hashcash version File versions

libfastmint.c

#if defined(__POWERPC__) && defined(__ALTIVEC__) && (!defined(__GNUC__) || !defined(__MACH__))
#include <altivec.h>
#endif

#ifdef __CARBON__
#include <CoreServices/CoreServices.h>
#endif

#if defined(__POWERPC__) && !defined(__MACH__) && !defined(__UNIX__) && !defined(__CARBON__)
#include <Gestalt.h>
#endif

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <signal.h>
#include <setjmp.h>
#include "random.h"
#include "sha1.h"

#define BUILD_DLL
#include "libfastmint.h"


/* Index into array of available minters */
static int fastest_minter = -1;
static unsigned int num_minters = 0;
#define MAX_MINTERS 20
static HC_Minter minters[MAX_MINTERS];

const char *encodeAlphabets[] = {
      "0123456789ABCDEF",
      "0123456789abcdef",
      "ABCDEFGHIJKLMNOP",
      "abcdefghijklmnop",
      "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/"
};

const int EncodeBitRate[] = { 4, 4, 4, 4, 6 };

/* Keep track of what the CPU supports */
static volatile int gIllegalInstructionTrapped = 0;
static jmp_buf gEnv;
int gProcessorSupportFlags = 0;

/* SHA-1 magic gunge */
#define H0 0x67452301
#define H1 0xEFCDAB89
#define H2 0x98BADCFE
#define H3 0x10325476
#define H4 0xC3D2E1F0
static const uInt32 SHA1_IV[ 5 ] = { H0, H1, H2, H3, H4 };

/* SIGILL handler */
static void sig_ill_handler(int sig)
{
      sig = sig;
      gIllegalInstructionTrapped = 1;
      longjmp(gEnv,1);
}

#if defined(__ALTIVEC__) && !defined(__GNUC__)
#pragma dont_inline on
/* Dummy Altivec operation for testing */
static void dummy_altivec_fn(void)
{
      volatile vector unsigned int v;
      v = vec_or(v,v);
}
#pragma dont_inline reset
#endif

/* Detect whether extended CPU features like Altivec, MMX, etc are supported */
static void hashcash_detect_features(void)
{
#if defined(__POWERPC__) && defined(__ALTIVEC__)
      int hasAltivec = 0;
      
      #if defined(__UNIX__) || defined(__MACH__)
                  /* Use generic SIGILL trap handler */
                  void *oldhandler;
                  
                  gIllegalInstructionTrapped = 0;
                  oldhandler = signal(SIGILL, sig_ill_handler);
                  
                  if(!setjmp(gEnv)) {
                        #ifdef __GNUC__
                        asm volatile ( "vor v0,v0,v0" );
                        #else
                        dummy_altivec_fn();
                        #endif
                  }
                  
                  signal(SIGILL, oldhandler);
                  
                  hasAltivec = !gIllegalInstructionTrapped;
      #else
                  /* Carbon and MacOS Classic */
                  long cpuAttributes;
                  OSErr err = Gestalt(gestaltPowerPCProcessorFeatures, &cpuAttributes);
                  if(err == 0)
                        hasAltivec = ((1 << gestaltPowerPCHasVectorInstructions) & cpuAttributes) != 0;
      #endif
      
      if(hasAltivec)
            gProcessorSupportFlags |= HC_CPU_SUPPORTS_ALTIVEC;
      else
            gProcessorSupportFlags &= ~(HC_CPU_SUPPORTS_ALTIVEC);
#elif defined(__i386__) && defined(__GNUC__)
      void *oldhandler;
      int hasMMX = 0;
      
      gIllegalInstructionTrapped = 0;
      oldhandler = signal(SIGILL, sig_ill_handler);
      
      if(!setjmp(gEnv)) {
            asm volatile (
                                                      "movl $1, %%eax\n\t"
                                                      "push %%ebx\n\t"
                                                      "cpuid\n\t"
                                                      "andl $0x800000, %%edx\n\t"
                                                      "pop %%ebx\n\t"
                                                      : "=d" (hasMMX)
                                                      : /* no input */
                                                      : "eax", "ecx"
                                                      );
      }
      
      signal(SIGILL, oldhandler);
      
      if(hasMMX && !gIllegalInstructionTrapped)
            gProcessorSupportFlags |= HC_CPU_SUPPORTS_MMX;
      else
            gProcessorSupportFlags &= ~(HC_CPU_SUPPORTS_MMX);
#elif defined(__AMD64__)
      gProcessorSupportFlags = HC_CPU_SUPPORTS_MMX;
#else
      gProcessorSupportFlags = 0;
#endif
}

/* Statically guesstimate the fastest hashcash minting routine.  Takes
 * into account only the gross hardware architecture and features
 * available.  Updates fastest_minter.  Also initialises and populates
 * the available minter array if necessary.
 */

static const EncodeAlphabet encodings[] = {
      EncodeBase64,
      EncodeBase64,
      EncodeBase64,
      EncodeBase64,
      EncodeBase64,
      EncodeBase64,
      EncodeBase64,
      EncodeBase64,
      EncodeBase64,
      EncodeBase64,
      EncodeBase64 
};

void hashcash_select_minter()
{
      static const HC_Mint_Routine funcs[] = {
            minter_library,
            minter_ansi_compact_1,
            minter_ansi_standard_1,
            minter_ansi_ultracompact_1,
            minter_ansi_compact_2,
            minter_ansi_standard_2,
            minter_altivec_standard_1,
            minter_altivec_compact_2,
            minter_altivec_standard_2,
            minter_mmx_compact_1,
            minter_mmx_standard_1,
            NULL };
      static const HC_Mint_Capable_Routine tests[] = {
            minter_library_test,
            minter_ansi_compact_1_test,
            minter_ansi_standard_1_test,
            minter_ansi_ultracompact_1_test,
            minter_ansi_compact_2_test,
            minter_ansi_standard_2_test,
            minter_altivec_standard_1_test,
            minter_altivec_compact_2_test,
            minter_altivec_standard_2_test,
            minter_mmx_compact_1_test,
            minter_mmx_standard_1_test,
            NULL };
      static const char *names[] = {
#if defined( OPENSSL )
            "SHA1 library (openSSL)",
#else
            "SHA1 library (hashcash)",
#endif
            "ANSI Compact 1-pipe",
            "ANSI Standard 1-pipe",
            "ANSI Ultra-Compact 1-pipe",
            "ANSI Compact 2-pipe",
            "ANSI Standard 2-pipe",
            "PowerPC Altivec Standard 1x4-pipe",
            "PowerPC Altivec Compact 2x4-pipe",
            "PowerPC Altivec Standard 2x4-pipe",
            "AMD64/x86 MMX Compact 1x2-pipe",
            "AMD64/x86 MMX Standard 1x2-pipe",
            NULL };
      int i = 0 ;
      
      /* Populate array */
      if(!num_minters) {
            num_minters = (sizeof(funcs) / sizeof(*funcs)) - 1;
            if ( num_minters > MAX_MINTERS ) {
                  fprintf(stderr, 
                        "INTERNAL ERROR: " 
                        "increase size of MAX_MINTERS\n");
                  exit(3); /* EXIT_ERROR */
            }
            for(i=0; i < num_minters; i++) {
                  minters[i].name = names[i];
                  minters[i].func = funcs[i];
                  minters[i].test = tests[i];
                  minters[i].encoding = encodings[i];
            }
      }
      
      /* If nothing else works, just use the compact_1 minter on x86
         and standard_1 elsewhere */

      #ifdef __i386__
      fastest_minter = 1;
      #elif defined(__M68000__)
      fastest_minter = 3;
      #else
      fastest_minter = 2;
      #endif
      
      /* Detect actual CPU capabilities */
      hashcash_detect_features();
      
      /* See if any of the vectorised minters work, choose the
         highest-numbered one that does */

      for(i=6; i < num_minters; i++) {
            if(minters[i].test()) { fastest_minter = i; }
      }
}

/* Do a quick, silent benchmark of the selected backend.  Assumes it
 * works. */
unsigned long hashcash_per_sec_calc( void )
{
      static const unsigned int test_bits = 64;
      static const char *test_string = 
            "1:32:040404:foo@fnord.gov::0123456789abcdef:00000000";
      static const int test_tail = 52;
      unsigned long rate = 0, iter_count = 256;
      volatile clock_t begin = 0 , end = 0 , tmp = 0 , res = 0 , taken = 0 ;
      double elapsed = 0 , multiple = 0 ;
      unsigned char block[SHA1_INPUT_BYTES] = {0};
      int gotbits = 0;
      HC_Mint_Routine best_minter_fp;
      
      /* Ensure a valid minter backend is selected */
      if(!num_minters) { hashcash_select_minter(); }
      best_minter_fp = minters[fastest_minter].func;
      
      /* Determine clock resolution */
      end = clock();
      while((begin = clock()) == end)
            ;
      while((end = clock()) == begin)
            ;
      if ( end < begin ) { tmp = begin; begin = end; end = tmp; }
      res = end - begin;
      
        /* where there is poor resolution use this */
      /* less accurate but faster -- otherwise takes 0.5secs */

      if ( res > 1000 ) {
            /* Run minter, with clock running */
            begin = end;
            do {
                  /* set up SHA-1 block */
                  strncpy(block, test_string, SHA1_INPUT_BYTES);
                  block[test_tail] = 0x80;
                  memset(block+test_tail+1, 0, 59-test_tail);
                  PUT_WORD(block+60, test_tail << 3);

                  best_minter_fp(test_bits, &gotbits, block, 
                               SHA1_IV, test_tail, iter_count, 
                               NULL, NULL, 0, 0);
                  if ( gotbits >= test_bits) {
                        /* The benchmark will be inaccurate 
                           if we actually find a collision! */
                        fprintf(stderr, 
"Error in hashcash_quickbench(): found collision while trying to benchmark!\n");
                        return 1;
                  }
                  rate += iter_count;
                  end = clock();
                  if ( end < begin ) { taken = begin-end; }
                  else { taken = end-begin; }
            } while ( taken < 8*res );
            multiple = CLOCKS_PER_SEC / (double)(8*res);
            rate *= multiple;
            
            return rate;
      }

      /* Run increasing lengths of minting until we have sufficient
       * elapsed time for precision */
      while(iter_count) {
            /* set up SHA-1 block */
            strncpy(block, test_string, SHA1_INPUT_BYTES);
            block[test_tail] = 0x80;
            memset(block+test_tail+1, 0, 59-test_tail);
            PUT_WORD(block+60, test_tail << 3);
            
            /* Run minter, with clock running */
            end = clock();
            while((begin = clock()) == end) {}
            best_minter_fp(test_bits,&gotbits,block,SHA1_IV,test_tail,
                         iter_count, NULL, NULL, 0, 0);
            if ( gotbits >= test_bits) {
                  /* The benchmark will be inaccurate if we
                   * actually find a collision! */
                  fprintf(stderr, "Error in hashcash_quickbench(): found collision while trying to benchmark!\n");
                  return 1;
            }
            end = clock();
            if ( end < begin ) { tmp = begin; begin = end; end = tmp; }
            elapsed = (end-begin) / (double) CLOCKS_PER_SEC;
            
            if(end-begin > (res * 16))
                  break;
            
            iter_count <<= 1;
      }
      
      rate = iter_count / elapsed;
      return rate;
}

/* version of hashcash_per_sec_calc which caches result, so only doing
 * the work once.  Note: hashcash_use_core will dirty the cache to
 * trigger a recalc
 */

static int cached_per_sec = 0;

unsigned long hashcash_per_sec(void)
{
      static unsigned long cache = 0;
        if ( !cached_per_sec ) {
                cache = hashcash_per_sec_calc();
                cached_per_sec = 1;
        }
        return cache;
}

/* Test and benchmark available hashcash minting backends.  Returns
 * the speed of the fastest valid routine, and updates fastest_minter
 * as appropriate.
 */
unsigned long hashcash_benchtest(int verbose, int core)
{
      unsigned long i, a, b;
      int best_minter = -1, got_bits = 0;
      static const unsigned int test_bits = 22;
      static const char *test_string = 
            "1:22:040404:foo@bar.net::0123456789abcdef:0000000000";
      static const int test_tail = 52;  /* must be less than 56 */
      static const int bit_stats[] = { 8, 10, 16, 20, 22, 
                               24, 26, 28, 30, 0 };
      unsigned char block[SHA1_INPUT_BYTES+1] = {0};
      volatile clock_t begin = 0, end = 0, tmp = 0;
      double elapsed = 0, rate = 0, peak_rate = 0;
      SHA1_ctx crypter;
      unsigned char hash[SHA1_DIGEST_BYTES] = {0};
      const char *p = NULL , *q = NULL ;
      int start = 0, stop = 0;

      /* If minter list isn't valid, make it so */
      hashcash_select_minter();
      
      /* print header */
      if(verbose > 0 ) {
              printf("    Rate  Name (* machine default)\n");
      }
      if(verbose >= 3) { printf("\n"); }
      
      if ( core >= 0 ) { 
        start = core; stop = start+1; 
      } else { 
        start = 0; stop = num_minters;
      }
      for(i = start; i < stop; i++) {
            /* If the minter can't run... */
            if(!minters[i].test()) {
                  if(verbose >= 2) {
                        printf("   ---    %s  (Not available on this machine)\n", minters[i].name);
                  }
                  continue;
            }
            
            if(verbose) {
                  printf("          %s\r", minters[i].name);
                  fflush(stdout);
            }
            
            /* set up SHA-1 block */
            strncpy(block, test_string, SHA1_INPUT_BYTES);
            block[test_tail] = 0x80;
            memset(block+test_tail+1, 0, 59-test_tail);
            PUT_WORD(block+60, test_tail << 3);
            
            /* Run minter, with clock running */
            end = clock();
            while((begin = clock()) == end) {}
            minters[i].func(test_bits, &got_bits, block, SHA1_IV, 
                        test_tail, 1 << 30, NULL, NULL, 0, 0);
            end = clock();
            if ( end < begin ) { tmp = begin; begin = end; end = tmp; }
            elapsed = (end-begin) / (double) CLOCKS_PER_SEC;
            
            /* Different minter iteration patterns will find
             * different solutions */
            /* Verify solution correctness first, using reference
             * SHA-1 library */

            SHA1_Init(&crypter);
            SHA1_Update(&crypter, block, test_tail);
            SHA1_Final(&crypter, hash);
            for(a=0; a < SHA1_DIGEST_BYTES-1 && hash[a] == 0; a++) {}
            for(b=0; b < 8 && (hash[a] & 0x80) == 0; b++) {
                  hash[a] <<= 1;
            }
            if(got_bits != (a*8)+b || got_bits < test_bits || 
               block[test_tail] != (unsigned char) 0x80) {
                  if(verbose) {
                        printf("ERROR!\n");
                        printf("    Wanted %u bits, reported %d bits, got %lu bits.\n", test_bits, got_bits, (a*8)+b);
                        if(block[test_tail] == (unsigned char) 0x80) {
                              printf("    End-of-block marker remains intact.\n");
                        } else {
                              printf("    End-of-block marker damaged!\n");
                        }
                        block[test_tail] = 0;
                        printf("    \"%s\"\n", block);
                        printf("    Time taken: %.3f\n\n", elapsed);
                  }
                  continue;
            }
            
            /* Use knowledge of encoding alphabet to calculate
               iterations taken */
            a = test_tail-8;
            b = 0;
            p = encodeAlphabets[minters[i].encoding];
            while(a < test_tail && block[a] == '0') {
                  a++;
            }
            for( ; a < test_tail; a++) {
                  q = strchr(p, block[a]);
                  if(!q)
                        break;
                  b = (b * strlen(p)) + (q - p);
            }
            if(a != test_tail) {
                  if(verbose) {
                        printf("ERROR!\n");
                        printf("    Unable to parse iteration count.\n");
                        printf("    \"%s\"\n", block);
                        printf("    \"%s\"\n", p);
                  }
                  continue;
            }
            
            /* We know the elapsed time and the iteration count,
               so calculate the rate */
            rate = b / elapsed;
            if(verbose) {
                  printf("%9lu %s %c\n", (unsigned long) rate, 
                         minters[i].name, 
                         (i == fastest_minter) ? '*' : ' ');
            }

            if(rate > peak_rate) {
                  peak_rate = rate;
                  best_minter = i;
            }
            
            /* Optionally print out the stats */
            if(verbose >= 3) {
                  block[test_tail] = 0;
                  printf("    Solution:   %s\n", block);
                  printf("    Iterations: %lu\n", b);
                  printf("    Time taken: %.3f\n\n", elapsed);
            }
      }
      
      fastest_minter = best_minter;
      
      if(verbose && best_minter >= 0) {
            printf("Best minter: %s (%lu hashes/sec)\n", 
                   minters[best_minter].name, (unsigned long) peak_rate);
      }
      if(verbose >= 2 && best_minter >= 0) {
            printf("Projected average times to mint:\n");
            
            for(i = 0; bit_stats[i]; i++) {
                  elapsed = (1 << bit_stats[i]) / peak_rate;
                  printf("%3d bits: %9.3f seconds", bit_stats[i], 
                         elapsed);
                  if(elapsed > 200000) {
                        printf(" (%.1f days)", elapsed/(3600*24));
                  } else if(elapsed > 5000) {
                        printf(" (%.1f hours)", elapsed/3600);
                  } else if(elapsed > 100) {
                        printf(" (%.1f minutes)", elapsed/60);
                  } else if(elapsed < 0.005) {
                        printf(" (%.1f microseconds)", elapsed * 
                               1000000);
                  }
                  printf("\n");
            }
      }
      
      return (unsigned long) peak_rate;
}

/* Attempt to mint a hashcash token with a given bit-value.
 * Will append a random string to token that produces the required
 * collision, then return a pointer to the resultant string in result.
 * Caller must free() result buffer after use.
 * Returns the number of bits actually minted (may be more or less
 * than requested).
 */

#define BIG_ITER 0x40000000U  /* 2^30 */

double hashcash_fastmint(const int bits, const char *token, int compress,
                   char **result, hashcash_callback cb, void* user_args)
{
      SHA1_ctx crypter;
      unsigned char hash[SHA1_DIGEST_BYTES] = {0};
      unsigned int IV[SHA1_DIGEST_WORDS] = {0};
      unsigned char *buffer = NULL, *block = NULL, c = 0;
      unsigned int buflen = 0, tail = 0, a = 0, b = 0, save_tail = 0;
      unsigned long t = 0, loop = 0, iters = 0, i = 0;
      HC_Mint_Routine best_minter;
      double counter = 0, expected = 0;
      /* this is to allow this fn to call the same callback macro */
      MINTER_CALLBACK_VARS;
      int gotBits = 0, bit_rate = 6, chars = 0, blocks = 1, oldblocks = 0;
      int* best;        /* NB this is needed for CALLBACK macros */

      best = &gotBits;
      
      /* Make sure list of minters is valid */
      if(fastest_minter < 0) { hashcash_select_minter(); }

      /* only the library minter can cope with split blocks */
      if ( compress > 1 ) { fastest_minter = 0; }

      best_minter = minters[fastest_minter].func;

      expected = hashcash_expected_tries( bits );

 again:
      /* Set up string for hashing */
      tail = strlen(token);
      buflen = (tail - (tail % SHA1_INPUT_BYTES)) + 2*SHA1_INPUT_BYTES;
      buffer = malloc(buflen);
      memset(buffer, 0, buflen);
      strncpy(buffer, token, buflen);
      
      /* Add 96 bits of random data */
      t = tail + 16;
      for( ; tail < t; tail++) {
            random_getbytes(&c, 1);
            buffer[tail] = encodeAlphabets[EncodeBase64][c & 0x3f];
      }
      
      /* Add separator and zeroed count field (for v1 hashcash format) */
      buffer[tail++] = ':';
      save_tail = tail;

      bit_rate = EncodeBitRate[encodings[fastest_minter]];
      chars = 31/bit_rate;
      for ( i = compress ? 1 : chars; i <= chars && gotBits < bits; i++ ) {
            tail = save_tail;
            t = tail + i;
            for( ; tail < t; tail++) { buffer[tail] = '0'; }
            switch (compress) {
            case 0:           /* fast stamps */
                    /* Align to optimal counting positions */
                  for( ; (tail % SHA1_INPUT_BYTES) != 32 && 
                         (tail % SHA1_INPUT_BYTES) != 52; tail++) {
                        buffer[tail] = '0';
                  }
                  break;
            case 1:            /* produce moderately compact stamps */
                  /* ensure counting is all within one SHA-1 block */
                  for( ; (tail % SHA1_INPUT_BYTES) < i ||
                         (tail % SHA1_INPUT_BYTES) >= 56; tail++) {
                        buffer[tail] = '0';
                  }
                  break;
            default:    /* produce very compact stamps */
                  oldblocks = blocks;
                  if ( (tail % SHA1_INPUT_BYTES) < i ||
                       (tail % SHA1_INPUT_BYTES) >= 56 ) {
                        blocks = 2; /* split across block */
                  }
                  /* no padding at all! */
            }

            /* Hash all but the final block, due to invariance */
            t = tail - (tail % SHA1_INPUT_BYTES);
            if ( blocks > 1 && t >= 64 && (tail % SHA1_INPUT_BYTES) < i ) {
                  t -= 64;
            }
            SHA1_Init(&crypter);
            SHA1_Update(&crypter, buffer, t);
#if defined(OPENSSL)
            IV[0]=crypter.h0;
            IV[1]=crypter.h1;
            IV[2]=crypter.h2;
            IV[3]=crypter.h3;
            IV[4]=crypter.h4;
#else
            for(a=0; a < 5; a++) { IV[a] = crypter.H[a]; }
#endif
            block = buffer + t;

            /* Fill in the padding and trailer */
            buffer[tail] = 0x80;
            /* if number of blocks change get rid of old padding */
            if ( blocks > oldblocks) { 
                  /* note only need 7 chars as 1 char wider */
                  memset(buffer+tail+1,0,7); 
            }
            PUT_WORD(block+(blocks>1?64:0)+60, tail << 3);
            tail -= t;
      
            /* Run the minter over the last block */
            loop=best_minter(bits, &gotBits, block, IV, tail,
                         0x1U << (i*bit_rate), cb,
                         user_args,counter,expected);
            if (loop==0) {
                  free(buffer);
                  if (*best==-1) {return -1;}
                  else { return 0; }
            }
            counter += (double)loop;
      }

      /* if we succeeded call the callback also */
      if ( gotBits >= bits ) { MINTER_CALLBACK(); }
      block[tail] = 0;
      
      /* Verify solution using reference library */
      SHA1_Update(&crypter, block, tail);
      SHA1_Final(&crypter, hash);
      for(a=0; a < SHA1_DIGEST_BYTES-1 && hash[a] == 0; a++)
            ;
      for(b=0; b < 8 && (hash[a] & 0x80) == 0; b++)
            hash[a] <<= 1;
      b += a*8;
      
      /* The minter appears to be broken! */
      if(b < gotBits) {
            fprintf(stderr, "ERROR: requested %d bits, reported %d bits, got %d bits using %s minter: \"%s\"\n",
                  bits, gotBits, b, minters[fastest_minter].name, 
                  buffer);
            exit(3);
      }
      
      /* The minter might not be able to detect unusually large
       * (32+) bit counts, so we're allowed to give it another try.
       */
      if(b < bits) {
        /*        fprintf( stderr, "buffer = %s\n", buffer );
                  fprintf( stderr, "wrapped\n" ); */
            free(buffer);
            goto again;
      }

      *result = (char*)buffer;
      return counter;
}

int hashcash_core(void) 
{
      if (!num_minters) { hashcash_select_minter(); }
      return fastest_minter;
}

int hashcash_use_core(int core)
{
      if (!num_minters) { hashcash_select_minter(); }
      if ( core < 0 || core >= num_minters ) { return -1; }
      if ( !minters[core].test() ) { return 0; }
      fastest_minter = core;
      /* force recalc */
      cached_per_sec = 0;
      return 1;
}

const char* hashcash_core_name(int core)
{
      if (!num_minters) { hashcash_select_minter(); }
      if ( core < 0 || core >= num_minters ) {
            return "undefined core";
      }
      return minters[core].name;
}

Generated by  Doxygen 1.6.0   Back to index