Update of /cvsroot/perl-win32-gui/Win32-GUI/Win32-GUI-Constants/hash
In directory
sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv23641/Win32-GUI-Constants/hash
Added Files:
Makefile.PL README lookupa.c lookupa.h perfect.c perfect.h
perfhex.c recycle.c recycle.h standard.h
Log Message:
Add Win32-GUI-Constants directory and module code
--- NEW FILE: lookupa.h ---
/*
------------------------------------------------------------------------------
By Bob Jenkins, September 1996.
lookupa.h, a hash function for table lookup, same function as lookup.c.
Use this code in any way you wish. Public Domain. It has no warranty.
Source is http://burtleburtle.net/bob/c/lookupa.h
------------------------------------------------------------------------------
*/
#ifndef STANDARD
#include "standard.h"
#endif
#ifndef LOOKUPA
#define LOOKUPA
#define CHECKSTATE 8
#define hashsize(n) ((ub4)1<<(n))
#define hashmask(n) (hashsize(n)-1)
ub4 lookup(/*_ ub1 *k, ub4 length, ub4 level _*/);
void checksum(/*_ ub1 *k, ub4 length, ub4 *state _*/);
#endif /* LOOKUPA */
--- NEW FILE: Makefile.PL ---
#!perl -w
use strict;
use warnings;
# Makefile.PL for perfect.exe
# Writes a makefile that supports enough targets to play
# nicely with ExtUtils::MakeMaker.
# $Id: Makefile.PL,v 1.1 2006/05/13 15:39:30 robertemay Exp $
use 5.006;
use Config;
print "Writing Makefile for Win32::GUI::Constants - perfect.exe\n";
my $file = 'Makefile';
open my $fh, '>', $file or die "Failed to open $file for writing: $!";
END { close $fh; }
select $fh;
# Generic configuration
my $nologo = "";
my $output = '-o $@';
my $cflags = "-O";
if($Config{cc} =~ /gcc/) { # gcc, e.g. MinGW
$cflags .= " -fno-builtin-log2";
}
elsif($Config{cc} =~ /cl/) { # MSVC
$nologo = "-nologo";
$output = "-Fe\$@";
}
print <<MAKEFILE;
#Makefile for Win32::GUI::Constants helper
#perfect.exe
PERL=$Config{perlpath}
RM_RF= \$(PERL) -MExtUtils::Command -e rm_rf
CC=$Config{cc}
CFLAGS=$cflags
NOLOGO=$nologo
OBJECT= lookupa$Config{obj_ext} recycle$Config{obj_ext} perfhex$Config{obj_ext}
perfect$Config{obj_ext}
all: perfect.exe
perfect.exe: \$(OBJECT)
\$(CC) \$(NOLOGO) $output \$(OBJECT)
.c$Config{obj_ext}:
\$(CC) \$(NOLOGO) \$(CFLAGS) -c \$<
# CLEAN
clean:
\$(RM_RF) perfect.exe \$(OBJECT)
realclean: clean
\$(RM_RF) $file
veryclean: realclean
#Test - will be call by parent Makefiles
test:
# DEPENDENCIES
lookupa.o : lookupa.c standard.h lookupa.h
recycle.o : recycle.c standard.h recycle.h
perfhex.o : perfhex.c standard.h lookupa.h recycle.h perfect.h
perfect.o : perfect.c standard.h lookupa.h recycle.h perfect.h
MAKEFILE
--- NEW FILE: lookupa.c ---
/*
--------------------------------------------------------------------
lookupa.c, by Bob Jenkins, December 1996. Same as lookup2.c
Use this code however you wish. Public Domain. No warranty.
Source is http://burtleburtle.net/bob/c/lookupa.c
--------------------------------------------------------------------
*/
#ifndef STANDARD
#include "standard.h"
#endif
#ifndef LOOKUPA
#include "lookupa.h"
#endif
/*
--------------------------------------------------------------------
mix -- mix 3 32-bit values reversibly.
For every delta with one or two bit set, and the deltas of all three
high bits or all three low bits, whether the original value of a,b,c
is almost all zero or is uniformly distributed,
* If mix() is run forward or backward, at least 32 bits in a,b,c
have at least 1/4 probability of changing.
* If mix() is run forward, every bit of c will change between 1/3 and
2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
mix() was built out of 36 single-cycle latency instructions in a
structure that could supported 2x parallelism, like so:
a -= b;
a -= c; x = (c>>13);
b -= c; a ^= x;
b -= a; x = (a<<8);
c -= a; b ^= x;
c -= b; x = (b>>13);
...
Unfortunately, superscalar Pentiums and Sparcs can't take advantage
of that parallelism. They've also turned some of those single-cycle
latency instructions into multi-cycle latency instructions. Still,
this is the fastest good hash I could find. There were about 2^^68
to choose from. I only looked at a billion or so.
--------------------------------------------------------------------
*/
#define mix(a,b,c) \
{ \
a -= b; a -= c; a ^= (c>>13); \
b -= c; b -= a; b ^= (a<<8); \
c -= a; c -= b; c ^= (b>>13); \
a -= b; a -= c; a ^= (c>>12); \
b -= c; b -= a; b ^= (a<<16); \
c -= a; c -= b; c ^= (b>>5); \
a -= b; a -= c; a ^= (c>>3); \
b -= c; b -= a; b ^= (a<<10); \
c -= a; c -= b; c ^= (b>>15); \
}
/*
--------------------------------------------------------------------
lookup() -- hash a variable-length key into a 32-bit value
k : the key (the unaligned variable-length array of bytes)
len : the length of the key, counting by bytes
level : can be any 4-byte value
Returns a 32-bit value. Every bit of the key affects every bit of
the return value. Every 1-bit and 2-bit delta achieves avalanche.
About 6len+35 instructions.
The best hash table sizes are powers of 2. There is no need to do
mod a prime (mod is sooo slow!). If you need less than 32 bits,
use a bitmask. For example, if you need only 10 bits, do
h = (h & hashmask(10));
In which case, the hash table should have hashsize(10) elements.
If you are hashing n strings (ub1 **)k, do it like this:
for (i=0, h=0; i<n; ++i) h = lookup( k[i], len[i], h);
By Bob Jenkins, 1996. [EMAIL PROTECTED] You may use this
code any way you wish, private, educational, or commercial.
See http://burtleburtle.net/bob/hash/evahash.html
Use for hash table lookup, or anything where one collision in 2^32 is
acceptable. Do NOT use for cryptographic purposes.
--------------------------------------------------------------------
*/
ub4 lookup( k, length, level)
register ub1 *k; /* the key */
register ub4 length; /* the length of the key */
register ub4 level; /* the previous hash, or an arbitrary value */
{
register ub4 a,b,c,len;
/* Set up the internal state */
len = length;
a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
c = level; /* the previous hash value */
/*---------------------------------------- handle most of the key */
while (len >= 12)
{
a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
mix(a,b,c);
k += 12; len -= 12;
}
/*------------------------------------- handle the last 11 bytes */
c += length;
switch(len) /* all the case statements fall through */
{
case 11: c+=((ub4)k[10]<<24);
case 10: c+=((ub4)k[9]<<16);
case 9 : c+=((ub4)k[8]<<8);
/* the first byte of c is reserved for the length */
case 8 : b+=((ub4)k[7]<<24);
case 7 : b+=((ub4)k[6]<<16);
case 6 : b+=((ub4)k[5]<<8);
case 5 : b+=k[4];
case 4 : a+=((ub4)k[3]<<24);
case 3 : a+=((ub4)k[2]<<16);
case 2 : a+=((ub4)k[1]<<8);
case 1 : a+=k[0];
/* case 0: nothing left to add */
}
mix(a,b,c);
/*-------------------------------------------- report the result */
return c;
}
/*
--------------------------------------------------------------------
mixc -- mixc 8 4-bit values as quickly and thoroughly as possible.
Repeating mix() three times achieves avalanche.
Repeating mix() four times eliminates all funnels and all
characteristics stronger than 2^{-11}.
--------------------------------------------------------------------
*/
#define mixc(a,b,c,d,e,f,g,h) \
{ \
a^=b<<11; d+=a; b+=c; \
b^=c>>2; e+=b; c+=d; \
c^=d<<8; f+=c; d+=e; \
d^=e>>16; g+=d; e+=f; \
e^=f<<10; h+=e; f+=g; \
f^=g>>4; a+=f; g+=h; \
g^=h<<8; b+=g; h+=a; \
h^=a>>9; c+=h; a+=b; \
}
/*
--------------------------------------------------------------------
checksum() -- hash a variable-length key into a 256-bit value
k : the key (the unaligned variable-length array of bytes)
len : the length of the key, counting by bytes
state : an array of CHECKSTATE 4-byte values (256 bits)
The state is the checksum. Every bit of the key affects every bit of
the state. There are no funnels. About 112+6.875len instructions.
If you are hashing n strings (ub1 **)k, do it like this:
for (i=0; i<8; ++i) state[i] = 0x9e3779b9;
for (i=0, h=0; i<n; ++i) checksum( k[i], len[i], state);
(c) Bob Jenkins, 1996. [EMAIL PROTECTED] You may use this
code any way you wish, private, educational, or commercial, as long
as this whole comment accompanies it.
See http://burtleburtle.net/bob/hash/evahash.html
Use to detect changes between revisions of documents, assuming nobody
is trying to cause collisions. Do NOT use for cryptography.
--------------------------------------------------------------------
*/
void checksum( k, len, state)
register ub1 *k;
register ub4 len;
register ub4 *state;
{
register ub4 a,b,c,d,e,f,g,h,length;
/* Use the length and level; add in the golden ratio. */
length = len;
a=state[0]; b=state[1]; c=state[2]; d=state[3];
e=state[4]; f=state[5]; g=state[6]; h=state[7];
/*---------------------------------------- handle most of the key */
while (len >= 32)
{
a += (k[0] +(k[1]<<8) +(k[2]<<16) +(k[3]<<24));
b += (k[4] +(k[5]<<8) +(k[6]<<16) +(k[7]<<24));
c += (k[8] +(k[9]<<8) +(k[10]<<16)+(k[11]<<24));
d += (k[12]+(k[13]<<8)+(k[14]<<16)+(k[15]<<24));
e += (k[16]+(k[17]<<8)+(k[18]<<16)+(k[19]<<24));
f += (k[20]+(k[21]<<8)+(k[22]<<16)+(k[23]<<24));
g += (k[24]+(k[25]<<8)+(k[26]<<16)+(k[27]<<24));
h += (k[28]+(k[29]<<8)+(k[30]<<16)+(k[31]<<24));
mixc(a,b,c,d,e,f,g,h);
mixc(a,b,c,d,e,f,g,h);
mixc(a,b,c,d,e,f,g,h);
mixc(a,b,c,d,e,f,g,h);
k += 32; len -= 32;
}
/*------------------------------------- handle the last 31 bytes */
h += length;
switch(len)
{
case 31: h+=(k[30]<<24);
case 30: h+=(k[29]<<16);
case 29: h+=(k[28]<<8);
case 28: g+=(k[27]<<24);
case 27: g+=(k[26]<<16);
case 26: g+=(k[25]<<8);
case 25: g+=k[24];
case 24: f+=(k[23]<<24);
case 23: f+=(k[22]<<16);
case 22: f+=(k[21]<<8);
case 21: f+=k[20];
case 20: e+=(k[19]<<24);
case 19: e+=(k[18]<<16);
case 18: e+=(k[17]<<8);
case 17: e+=k[16];
case 16: d+=(k[15]<<24);
case 15: d+=(k[14]<<16);
case 14: d+=(k[13]<<8);
case 13: d+=k[12];
case 12: c+=(k[11]<<24);
case 11: c+=(k[10]<<16);
case 10: c+=(k[9]<<8);
case 9 : c+=k[8];
case 8 : b+=(k[7]<<24);
case 7 : b+=(k[6]<<16);
case 6 : b+=(k[5]<<8);
case 5 : b+=k[4];
case 4 : a+=(k[3]<<24);
case 3 : a+=(k[2]<<16);
case 2 : a+=(k[1]<<8);
case 1 : a+=k[0];
}
mixc(a,b,c,d,e,f,g,h);
mixc(a,b,c,d,e,f,g,h);
mixc(a,b,c,d,e,f,g,h);
mixc(a,b,c,d,e,f,g,h);
/*-------------------------------------------- report the result */
state[0]=a; state[1]=b; state[2]=c; state[3]=d;
state[4]=e; state[5]=f; state[6]=g; state[7]=h;
}
--- NEW FILE: recycle.c ---
/*
--------------------------------------------------------------------
By Bob Jenkins, September 1996. recycle.c
You may use this code in any way you wish, and it is free. No warranty.
This manages memory for commonly-allocated structures.
It allocates RESTART to REMAX items at a time.
Timings have shown that, if malloc is used for every new structure,
malloc will consume about 90% of the time in a program. This
module cuts down the number of mallocs by an order of magnitude.
This also decreases memory fragmentation, and freeing structures
only requires freeing the root.
--------------------------------------------------------------------
*/
#ifndef STANDARD
# include "standard.h"
#endif
#ifndef RECYCLE
# include "recycle.h"
#endif
reroot *remkroot(size)
size_t size;
{
reroot *r = (reroot *)remalloc(sizeof(reroot), "recycle.c, root");
r->list = (recycle *)0;
r->trash = (recycle *)0;
r->size = align(size);
r->logsize = RESTART;
r->numleft = 0;
return r;
}
void refree(r)
struct reroot *r;
{
recycle *temp;
if (temp = r->list) while (r->list)
{
temp = r->list->next;
free((char *)r->list);
r->list = temp;
}
free((char *)r);
return;
}
/* to be called from the macro renew only */
char *renewx(r)
struct reroot *r;
{
recycle *temp;
if (r->trash)
{ /* pull a node off the trash heap */
temp = r->trash;
r->trash = temp->next;
(void)memset((void *)temp, 0, r->size);
}
else
{ /* allocate a new block of nodes */
r->numleft = r->size*((ub4)1<<r->logsize);
if (r->numleft < REMAX) ++r->logsize;
temp = (recycle *)remalloc(sizeof(recycle) + r->numleft,
"recycle.c, data");
temp->next = r->list;
r->list = temp;
r->numleft-=r->size;
temp = (recycle *)((char *)(r->list+1)+r->numleft);
}
return (char *)temp;
}
char *remalloc(len, purpose)
size_t len;
char *purpose;
{
char *x = (char *)malloc(len);
if (!x)
{
fprintf(stderr, "malloc of %d failed for %s\n",
len, purpose);
exit(SUCCESS);
}
return x;
}
--- NEW FILE: perfect.h ---
/*
------------------------------------------------------------------------------
perfect.h: code to generate code for a hash for perfect hashing.
(c) Bob Jenkins, September 1996
You may use this code in any way you wish, and it is free. No warranty.
I hereby place this in the public domain.
Source is http://burtleburtle.net/bob/c/perfect.h
------------------------------------------------------------------------------
*/
#ifndef STANDARD
#include "standard.h"
#endif
#ifndef PERFECT
#define PERFECT
#define MAXKEYLEN 32 /* maximum length of a key */
#define USE_SCRAMBLE 4096 /* use scramble if blen >= USE_SCRAMBLE */
#define SCRAMBLE_LEN ((ub4)1<<16) /* length of *scramble* */
#define RETRY_INITKEY 2048 /* number of times to try to find distinct (a,b) */
#define RETRY_PERFECT 1 /* number of times to try to make a perfect hash */
#define RETRY_HEX 200 /* RETRY_PERFECT when hex keys given */
/* the generated code for the final hash, assumes initial hash is done */
struct gencode
{
char **line; /* array of text lines, 80 bytes apiece */
/*
* The code placed here must declare "ub4 rsl"
* and assign it the value of the perfect hash using the function inputs.
* Later code will be tacked on which returns rsl or manipulates it according
* to the user directives.
*
* This code is at the top of the routine; it may and must declare any
* local variables it needs.
*
* Each way of filling in **line should be given a comment that is a unique
* tag. A testcase named with that tag should also be found which tests
* the generated code.
*/
ub4 len; /* number of lines available for final hash */
ub4 used; /* number of lines used by final hash */
ub4 lowbit; /* for HEX, lowest interesting bit */
ub4 highbit; /* for HEX, highest interesting bit */
ub4 diffbits; /* bits which differ for some key */
ub4 i,j,k,l,m,n,o; /* state machine used in hexn() */
};
typedef struct gencode gencode;
/* user directives: perfect hash? minimal perfect hash? input is an int? */
struct hashform
{
enum {
NORMAL_HM, /* key is a string */
INLINE_HM, /* user will do initial hash, we must choose salt for them */
HEX_HM, /* key to be hashed is a hexidecimal 4-byte integer */
DECIMAL_HM, /* key to be hashed is a decimal 4-byte integer */
AB_HM, /* key to be hashed is "A B", where A and B are (A,B) in hex */
ABDEC_HM /* like AB_HM, but in decimal */
} mode;
enum {
STRING_HT, /* key is a string */
INT_HT, /* key is an integer */
AB_HT /* dunno what key is, but input is distinct (A,B) pair */
} hashtype;
enum {
NORMAL_HP, /* just find a perfect hash */
MINIMAL_HP /* find a minimal perfect hash */
} perfect;
enum {
FAST_HS, /* fast mode */
SLOW_HS /* slow mode */
} speed;
};
typedef struct hashform hashform;
/* representation of a key */
struct key
{
ub1 *name_k; /* the actual key */
ub4 len_k; /* the length of the actual key */
ub4 hash_k; /* the initial hash value for this key */
struct key *next_k; /* next key */
/* beyond this point is mapping-dependent */
ub4 a_k; /* a, of the key maps to (a,b) */
ub4 b_k; /* b, of the key maps to (a,b) */
struct key *nextb_k; /* next key with this b */
};
typedef struct key key;
/* things indexed by b of original (a,b) pair */
struct bstuff
{
ub2 val_b; /* hash=a^tabb[b].val_b */
key *list_b; /* tabb[i].list_b is list of keys with b==i */
ub4 listlen_b; /* length of list_b */
ub4 water_b; /* high watermark of who has visited this map node */
};
typedef struct bstuff bstuff;
/* things indexed by final hash value */
struct hstuff
{
key *key_h; /* tabh[i].key_h is the key with a hash of i */
};
typedef struct hstuff hstuff;
/* things indexed by queue position */
struct qstuff
{
bstuff *b_q; /* b that currently occupies this hash */
ub4 parent_q; /* queue position of parent that could use this hash */
ub2 newval_q; /* what to change parent tab[b] to to use this hash */
ub2 oldval_q; /* original value of tab[b] */
};
typedef struct qstuff qstuff;
/* return ceiling(log based 2 of x) */
ub4 log2(/*_ ub4 x _*/);
/* Given the keys, scramble[], and hash mode, find the perfect hash */
void findhash(/*_ bstuff **tabb, ub4 *alen, ub4 *blen, ub4 *salt,
gencode *final, ub4 *scramble, ub4 smax, key *keys, ub4 nkeys,
hashform *form _*/);
/* private, but in a different file because it's excessively verbose */
int inithex(/*_ key *keys, ub4 *alen, ub4 *blen, ub4 smax, ub4 nkeys,
ub4 salt, gencode *final, gencode *form _*/);
#endif /* PERFECT */
--- NEW FILE: README ---
This directory contsins code for generating a minimal perfect hash that
is used for fast lookup of constants with a relatively small code
footprint.
The source code in this directory is modified from the original source
taken from http://burtleburtle.net/bob/hash/perfect.html
Modifications were made by Robert May - most of the functionality that
is not required at this time by the Win32::GUI::Constants build
process has been disabled.
--- NEW FILE: standard.h ---
/*
------------------------------------------------------------------------------
Standard definitions and types, Bob Jenkins
------------------------------------------------------------------------------
*/
#ifndef STANDARD
# define STANDARD
# ifndef STDIO
# include <stdio.h>
# define STDIO
# endif
# ifndef STDDEF
# include <stddef.h>
# define STDDEF
# endif
#ifdef _MSC_VER
typedef unsigned __int64 ub8;
typedef signed __int64 sb8;
#else
typedef unsigned long long ub8;
typedef signed long long sb8;
#endif /* _MSVC */
#define UB8MAXVAL 0xffffffffffffffffLL
#define UB8BITS 64
#define SB8MAXVAL 0x7fffffffffffffffLL
typedef unsigned long int ub4; /* unsigned 4-byte quantities */
#define UB4MAXVAL 0xffffffff
typedef signed long int sb4;
#define UB4BITS 32
#define SB4MAXVAL 0x7fffffff
typedef unsigned short int ub2;
#define UB2MAXVAL 0xffff
#define UB2BITS 16
typedef signed short int sb2;
#define SB2MAXVAL 0x7fff
typedef unsigned char ub1;
#define UB1MAXVAL 0xff
#define UB1BITS 8
typedef signed char sb1; /* signed 1-byte quantities */
#define SB1MAXVAL 0x7f
typedef int word; /* fastest type available */
#define bis(target,mask) ((target) |= (mask))
#define bic(target,mask) ((target) &= ~(mask))
#define bit(target,mask) ((target) & (mask))
#ifndef min
# define min(a,b) (((a)<(b)) ? (a) : (b))
#endif /* min */
#ifndef max
# define max(a,b) (((a)<(b)) ? (b) : (a))
#endif /* max */
#ifndef align
# define align(a) (((ub4)a+(sizeof(void *)-1))&(~(sizeof(void *)-1)))
#endif /* align */
#ifndef abs
# define abs(a) (((a)>0) ? (a) : -(a))
#endif
#define TRUE 1
#define FALSE 0
#define SUCCESS 0 /* 1 on VAX */
#endif /* STANDARD */
--- NEW FILE: recycle.h ---
/*
--------------------------------------------------------------------
By Bob Jenkins, September 1996. recycle.h
You may use this code in any way you wish, and it is free. No warranty.
This manages memory for commonly-allocated structures.
It allocates RESTART to REMAX items at a time.
Timings have shown that, if malloc is used for every new structure,
malloc will consume about 90% of the time in a program. This
module cuts down the number of mallocs by an order of magnitude.
This also decreases memory fragmentation, and freeing all structures
only requires freeing the root.
--------------------------------------------------------------------
*/
#ifndef STANDARD
#include "standard.h"
#endif
#ifndef RECYCLE
#define RECYCLE
#define RESTART 0
#define REMAX 32000
struct recycle
{
struct recycle *next;
};
typedef struct recycle recycle;
struct reroot
{
struct recycle *list; /* list of malloced blocks */
struct recycle *trash; /* list of deleted items */
size_t size; /* size of an item */
size_t logsize; /* log_2 of number of items in a block */
word numleft; /* number of bytes left in this block */
};
typedef struct reroot reroot;
/* make a new recycling root */
reroot *remkroot(/*_ size_t mysize _*/);
/* free a recycling root and all the items it has made */
void refree(/*_ struct reroot *r _*/);
/* get a new (cleared) item from the root */
#define renew(r) ((r)->numleft ? \
(((char *)((r)->list+1))+((r)->numleft-=(r)->size)) : renewx(r))
char *renewx(/*_ struct reroot *r _*/);
/* delete an item; let the root recycle it */
/* void redel(/o_ struct reroot *r, struct recycle *item _o/); */
#define redel(root,item) { \
((recycle *)item)->next=(root)->trash; \
(root)->trash=(recycle *)(item); \
}
/* malloc, but complain to stderr and exit program if no joy */
/* use plain free() to free memory allocated by remalloc() */
char *remalloc(/*_ size_t len, char *purpose _*/);
#endif /* RECYCLE */
--- NEW FILE: perfect.c ---
/*
------------------------------------------------------------------------------
perfect.c: code to generate code for a hash for perfect hashing.
(c) Bob Jenkins, September 1996, December 1999
You may use this code in any way you wish, and it is free. No warranty.
I hereby place this in the public domain.
Source is http://burtleburtle.net/bob/c/perfect.c
Modified by Robert May, May 2006. Changes are in the Public Domain.
Alterations are for the Win32::GUI::Constants build process, and result
in a new single outputfile that contains the has function and a suitable
lookup table. For more information goto
http://perl-win32-gui.sourceforge.net/
This generates a minimal perfect hash function. That means, given a
set of n keys, this determines a hash function that maps each of
those keys into a value in 0..n-1 with no collisions.
[...1460 lines suppressed...]
form.speed = FAST_HS; break;
case 's': case 'S':
form.speed = SLOW_HS; break;
}
speed_given = TRUE;
break;
default:
usage_error();
}
break;
#endif /* 0 */
default:
usage_error();
}
/* Generate the [minimal] perfect hash */
driver(&form);
return SUCCESS;
}
--- NEW FILE: perfhex.c ---
/*
------------------------------------------------------------------------------
perfhex.c: code to generate code for a hash for perfect hashing.
(c) Bob Jenkins, December 31 1999
You may use this code in any way you wish, and it is free. No warranty.
I hereby place this in the public domain.
Source is http://burtleburtle.net/bob/c/perfhex.c
The task of this file is to do the minimal amount of mixing needed to
find distinct (a,b) for each key when each key is a distinct ub4. That
means trying all possible ways to mix starting with the fastest. The
output is those (a,b) pairs and code in the *final* structure for producing
those pairs.
------------------------------------------------------------------------------
*/
#ifndef STANDARD
#include "standard.h"
#endif
[...1267 lines suppressed...]
sprintf(final->line[0], " ub4 a, b, rsl;\n");
sprintf(final->line[1], "\n");
sprintf(final->line[2], "\n");
sprintf(final->line[3], "\n");
sprintf(final->line[4], "\n");
sprintf(final->line[5], "\n");
sprintf(final->line[6], "\n");
if (blen < USE_SCRAMBLE)
{ /* hns */
sprintf(final->line[7], " rsl = (a^tab[b]);\n");
}
else
{ /* hnt */
sprintf(final->line[7], " rsl = (a^scramble[tab[b]]);\n");
}
}
hexn(keys, salt, alen, blen, final);
return FALSE;
}
}
