Enlightenment CVS committal
Author : mej
Project : eterm
Module : libast
Dir : eterm/libast/test
Modified Files:
Makefile.am perf.c test.c
Log Message:
Thu Jan 22 20:42:40 2004 Michael Jennings (mej)
Added a few new hashes.
Fixed a typo in the old hashes.
LibAST-ized the hash tests and made new performance tests.
Anybody care to comment on the validity of my performance tests? All
6 algorithms end up with pretty much the same results. Do I need to
use a dictionary instead of random "words?" That's kinda what I'm
thinking....
===================================================================
RCS file: /cvsroot/enlightenment/eterm/libast/test/Makefile.am,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -3 -r1.6 -r1.7
--- Makefile.am 27 May 2002 02:41:01 -0000 1.6
+++ Makefile.am 23 Jan 2004 01:44:51 -0000 1.7
@@ -1,4 +1,4 @@
-# $Id: Makefile.am,v 1.6 2002/05/27 02:41:01 mej Exp $
+# $Id: Makefile.am,v 1.7 2004/01/23 01:44:51 mej Exp $
EXTRA_PROGRAMS = libast-test libast-perf
@@ -16,6 +16,8 @@
$(top_builddir)/test/libast-test
perf: libast-perf
+# Uncomment the following to run under gdb
+# vi $(top_builddir)/test/libast-perf
$(top_builddir)/test/libast-perf $(PERFOPTS)
.PHONY: test
===================================================================
RCS file: /cvsroot/enlightenment/eterm/libast/test/perf.c,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -3 -r1.11 -r1.12
--- perf.c 10 Jan 2004 21:15:17 -0000 1.11
+++ perf.c 23 Jan 2004 01:44:51 -0000 1.12
@@ -21,7 +21,7 @@
* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
-static const char cvs_ident[] = "$Id: perf.c,v 1.11 2004/01/10 21:15:17 mej Exp $";
+static const char cvs_ident[] = "$Id: perf.c,v 1.12 2004/01/23 01:44:51 mej Exp $";
#if defined(HAVE_CONFIG_H) && (HAVE_CONFIG_H != 0)
# include <config.h>
@@ -38,6 +38,7 @@
int perf_macros(void);
int perf_strings(void);
+int perf_hashes(void);
int perf_options(void);
int perf_obj(void);
int perf_str(void);
@@ -131,6 +132,265 @@
}
int
+perf_hashes(void)
+{
+ spif_uint8_t i;
+
+ for (i = 0; i < 6; i++) {
+ spifhash_func_t hash_func;
+ spif_uint32_t key_length, hash, j;
+
+ if (i == 0) {
+ PERF_NOTICE("*** Profiling Jenkins hash:");
+ hash_func = spifhash_jenkins;
+ } else if (i == 1) {
+ PERF_NOTICE("*** Profiling Jenkins32 hash:");
+ hash_func = spifhash_jenkins32;
+ } else if (i == 2) {
+#if WORDS_BIGENDIAN
+ continue;
+#else
+ PERF_NOTICE("*** Profiling JenkinsLE hash:");
+ hash_func = spifhash_jenkinsLE;
+#endif
+ } else if (i == 3) {
+ PERF_NOTICE("*** Profiling rotating hash:");
+ hash_func = spifhash_rotating;
+ } else if (i == 4) {
+ PERF_NOTICE("*** Profiling one-at-a-time hash:");
+ hash_func = spifhash_one_at_a_time;
+ } else if (i == 5) {
+ PERF_NOTICE("*** Profiling FNV hash:");
+ hash_func = spifhash_fnv;
+ }
+
+ /***
+ *** The below tests hash speed for small, medium, and
+ *** large randomly-generated keys.
+ ***/
+ PERF_SET_REPS(1000);
+
+ /*
+ * Raw hash speed for fixed-length randomly-generated key.
+ */
+#define KEYLEN 32
+ do {
+ spif_uint8_t buff[KEYLEN];
+
+ for (key_length = 0; key_length < KEYLEN; key_length++) {
+ buff[key_length] = SPIF_CAST(uint8) (rand() & 0xff);
+ }
+ PERF_BEGIN("hash speed for 32-byte key");
+ if (hash_func == spifhash_jenkins32) {
+ PERF_TEST(hash = hash_func(buff, KEYLEN / 4, hash););
+ } else {
+ PERF_TEST(hash = hash_func(buff, KEYLEN, hash););
+ }
+ PERF_END();
+ } while (0);
+#undef KEYLEN
+
+#define KEYLEN 512
+ do {
+ spif_uint8_t buff[KEYLEN];
+
+ for (key_length = 0; key_length < KEYLEN; key_length++) {
+ buff[key_length] = SPIF_CAST(uint8) (rand() & 0xff);
+ }
+ PERF_BEGIN("hash speed for 512-byte key");
+ if (hash_func == spifhash_jenkins32) {
+ PERF_TEST(hash = hash_func(buff, KEYLEN / 4, hash););
+ } else {
+ PERF_TEST(hash = hash_func(buff, KEYLEN, hash););
+ }
+ PERF_END();
+ } while (0);
+#undef KEYLEN
+
+#define KEYLEN 8192
+ do {
+ spif_uint8_t buff[KEYLEN];
+
+ for (key_length = 0; key_length < KEYLEN; key_length++) {
+ buff[key_length] = SPIF_CAST(uint8) (rand() & 0xff);
+ }
+ PERF_BEGIN("hash speed for 8192-byte key");
+ if (hash_func == spifhash_jenkins32) {
+ PERF_TEST(hash = hash_func(buff, KEYLEN / 4, hash););
+ } else {
+ PERF_TEST(hash = hash_func(buff, KEYLEN, hash););
+ }
+ PERF_END();
+ } while (0);
+#undef KEYLEN
+
+ /***
+ *** These tests measure collision rate and distribution
+ *** across a varying number of hash buckets for varying
+ *** numbers of randomly-generated alphabetical keys.
+ ***/
+
+#define KEYLEN 8
+#define HASH_BITS 16
+ /*
+ * Hash distribution for a 16-bit hash and an 8-character random word.
+ */
+#define KEYCNT 64
+ do {
+ spif_uint32_t buckets[SPIFHASH_SIZE(HASH_BITS)];
+ spif_uint32_t c_total, c_min = SPIF_CAST(uint32) (-1), c_max = 0;
+ double c_prob, avg_size;
+
+ MEMSET(buckets, 0, sizeof(buckets));
+ printf("Profiling %lu-bucket distribution for %lu-bit hashes of %lu
%lu-byte random words...",
+ SPIF_CAST_C(unsigned long) SPIFHASH_SIZE(HASH_BITS),
+ SPIF_CAST_C(unsigned long) HASH_BITS,
+ SPIF_CAST_C(unsigned long) KEYCNT,
+ SPIF_CAST_C(unsigned long) KEYLEN);
+ for (j = 0; j < KEYCNT; j++) {
+ spif_uint8_t buff[KEYLEN];
+
+ for (key_length = 0; key_length < KEYLEN; key_length++) {
+ buff[key_length] = SPIF_CAST(uint8) (rand() % 26 + 'a');
+ }
+ if (hash_func == spifhash_jenkins32) {
+ hash = hash_func(buff, KEYLEN / 4, hash);
+ } else {
+ hash = hash_func(buff, KEYLEN, hash);
+ }
+ buckets[((hash >> HASH_BITS) ^ (hash & 0xffff))]++;
+ }
+ tnum = j;
+ for (j = 0, c_total = 0, avg_size = 0; j < SPIFHASH_SIZE(HASH_BITS); j++)
{
+ spif_uint32_t c;
+
+ c = buckets[j];
+ AT_LEAST(c_max, c);
+ AT_MOST(c_min, c);
+
+ if (c) {
+ if (--c) {
+ c_total += c;
+ }
+ }
+ }
+ avg_size /= SPIFHASH_SIZE(HASH_BITS);
+ c_prob = ((SPIF_CAST_C(double) c_total) / KEYCNT * 100.0);
+ printf("%lu collisions (%lu/%lu/%.5le), %.2lf%% probability.\n",
+ SPIF_CAST_C(unsigned long) c_total,
+ SPIF_CAST_C(unsigned long) c_min,
+ SPIF_CAST_C(unsigned long) c_max,
+ avg_size, c_prob);
+ } while (0);
+#undef KEYCNT
+
+#define KEYCNT 2048
+ do {
+ spif_uint32_t buckets[SPIFHASH_SIZE(HASH_BITS)];
+ spif_uint32_t c_total, c_min = SPIF_CAST(uint32) (-1), c_max = 0;
+ double c_prob, avg_size;
+
+ MEMSET(buckets, 0, sizeof(buckets));
+ printf("Profiling %lu-bucket distribution for %lu-bit hashes of %lu
%lu-byte random words...",
+ SPIF_CAST_C(unsigned long) SPIFHASH_SIZE(HASH_BITS),
+ SPIF_CAST_C(unsigned long) HASH_BITS,
+ SPIF_CAST_C(unsigned long) KEYCNT,
+ SPIF_CAST_C(unsigned long) KEYLEN);
+ for (j = 0; j < KEYCNT; j++) {
+ spif_uint8_t buff[KEYLEN];
+
+ for (key_length = 0; key_length < KEYLEN; key_length++) {
+ buff[key_length] = SPIF_CAST(uint8) (rand() % 26 + 'a');
+ }
+ if (hash_func == spifhash_jenkins32) {
+ hash = hash_func(buff, KEYLEN / 4, hash);
+ } else {
+ hash = hash_func(buff, KEYLEN, hash);
+ }
+ buckets[((hash >> HASH_BITS) ^ (hash & 0xffff))]++;
+ }
+ tnum = j;
+ for (j = 0, c_total = 0, avg_size = 0; j < SPIFHASH_SIZE(HASH_BITS); j++)
{
+ spif_uint32_t c;
+
+ c = buckets[j];
+ AT_LEAST(c_max, c);
+ AT_MOST(c_min, c);
+
+ if (c) {
+ if (--c) {
+ c_total += c;
+ }
+ }
+ }
+ avg_size /= SPIFHASH_SIZE(HASH_BITS);
+ c_prob = ((SPIF_CAST_C(double) c_total) / KEYCNT * 100.0);
+ printf("%lu collisions (%lu/%lu/%.5le), %.2lf%% probability.\n",
+ SPIF_CAST_C(unsigned long) c_total,
+ SPIF_CAST_C(unsigned long) c_min,
+ SPIF_CAST_C(unsigned long) c_max,
+ avg_size, c_prob);
+ } while (0);
+#undef KEYCNT
+
+#define KEYCNT 32768
+ do {
+ spif_uint32_t buckets[SPIFHASH_SIZE(HASH_BITS)];
+ spif_uint32_t c_total, c_min = SPIF_CAST(uint32) (-1), c_max = 0;
+ double c_prob, avg_size;
+
+ MEMSET(buckets, 0, sizeof(buckets));
+ printf("Profiling %lu-bucket distribution for %lu-bit hashes of %lu
%lu-byte random words...",
+ SPIF_CAST_C(unsigned long) SPIFHASH_SIZE(HASH_BITS),
+ SPIF_CAST_C(unsigned long) HASH_BITS,
+ SPIF_CAST_C(unsigned long) KEYCNT,
+ SPIF_CAST_C(unsigned long) KEYLEN);
+ for (j = 0; j < KEYCNT; j++) {
+ spif_uint8_t buff[KEYLEN];
+
+ for (key_length = 0; key_length < KEYLEN; key_length++) {
+ buff[key_length] = SPIF_CAST(uint8) (rand() % 26 + 'a');
+ }
+ if (hash_func == spifhash_jenkins32) {
+ hash = hash_func(buff, KEYLEN / 4, hash);
+ } else {
+ hash = hash_func(buff, KEYLEN, hash);
+ }
+ buckets[((hash >> HASH_BITS) ^ (hash & 0xffff))]++;
+ }
+ tnum = j;
+ for (j = 0, c_total = 0, avg_size = 0; j < SPIFHASH_SIZE(HASH_BITS); j++)
{
+ spif_uint32_t c;
+
+ c = buckets[j];
+ AT_LEAST(c_max, c);
+ AT_MOST(c_min, c);
+
+ if (c) {
+ if (--c) {
+ c_total += c;
+ }
+ }
+ }
+ avg_size /= SPIFHASH_SIZE(HASH_BITS);
+ c_prob = ((SPIF_CAST_C(double) c_total) / KEYCNT * 100.0);
+ printf("%lu collisions (%lu/%lu/%.5le), %.2lf%% probability.\n",
+ SPIF_CAST_C(unsigned long) c_total,
+ SPIF_CAST_C(unsigned long) c_min,
+ SPIF_CAST_C(unsigned long) c_max,
+ avg_size, c_prob);
+ } while (0);
+#undef KEYCNT
+
+#undef HASH_BITS
+
+#undef KEYLEN
+ }
+ PERF_ENDED("hash function");
+ return 0;
+}
+
+int
perf_options(void)
{
spif_uint32_t test_flag_var = 0;
@@ -329,7 +589,7 @@
teststr = spif_str_new_from_ptr("abcdefg");
PERF_BEGIN("spif_str_clear() function");
- PERF_TEST(spif_str_clear(teststr, SPIF_CAST_C(char) (rand() % 256)););
+ PERF_TEST(spif_str_clear(teststr, SPIF_CAST_C(char) (rand() & 0xff)););
PERF_END();
spif_str_del(teststr);
@@ -447,30 +707,30 @@
for (i = 0; i < 3; i++) {
if (i == 0) {
- PERF_NOTICE("Testing list interface class, linked_list instance:");
+ PERF_NOTICE("*** Profiling list interface class, linked_list instance:");
testlist = SPIF_LIST_NEW(linked_list);
} else if (i == 1) {
- PERF_NOTICE("Testing list interface class, dlinked_list instance:");
+ PERF_NOTICE("*** Profiling list interface class, dlinked_list instance:");
testlist = SPIF_LIST_NEW(dlinked_list);
} else if (i == 2) {
- PERF_NOTICE("Testing list interface class, array instance:");
+ PERF_NOTICE("*** Profiling list interface class, array instance:");
testlist = SPIF_LIST_NEW(array);
} else if (i == 3) {
}
PERF_BEGIN("SPIF_LIST_APPEND() macro");
- buff[0] = SPIF_CAST_C(char) (rand() % 256);
+ buff[0] = SPIF_CAST_C(char) (rand() & 0xff);
PERF_TEST(SPIF_LIST_APPEND(testlist, spif_str_new_from_ptr(buff)););
PERF_END();
PERF_BEGIN("SPIF_LIST_PREPEND() macro");
- buff[0] = SPIF_CAST_C(char) (rand() % 256);
+ buff[0] = SPIF_CAST_C(char) (rand() & 0xff);
PERF_TEST(SPIF_LIST_PREPEND(testlist, spif_str_new_from_ptr(buff)););
PERF_END();
s = spif_str_new();
PERF_BEGIN("SPIF_LIST_CONTAINS() macro");
- buff[0] = SPIF_CAST_C(char) (rand() % 256);
+ buff[0] = SPIF_CAST_C(char) (rand() & 0xff);
spif_str_init_from_ptr(s, buff);
PERF_TEST(SPIF_LIST_CONTAINS(testlist, s));
spif_str_done(s);
@@ -489,7 +749,7 @@
s = spif_str_new();
PERF_BEGIN("SPIF_LIST_INDEX() macro");
- buff[0] = SPIF_CAST_C(char) (rand() % 256);
+ buff[0] = SPIF_CAST_C(char) (rand() & 0xff);
spif_str_init_from_ptr(s, buff);
PERF_TEST(SPIF_LIST_INDEX(testlist, s));
spif_str_done(s);
@@ -497,20 +757,20 @@
spif_str_del(s);
PERF_BEGIN("SPIF_LIST_INSERT() macro");
- buff[0] = SPIF_CAST_C(char) (rand() % 256);
+ buff[0] = SPIF_CAST_C(char) (rand() & 0xff);
PERF_TEST(SPIF_LIST_INSERT(testlist, spif_str_new_from_ptr(buff)););
PERF_END();
len = SPIF_LIST_COUNT(testlist);
PERF_BEGIN("SPIF_LIST_INSERT_AT() macro");
- buff[0] = SPIF_CAST_C(char) (rand() % 256);
+ buff[0] = SPIF_CAST_C(char) (rand() & 0xff);
idx = rand() % len;
PERF_TEST(SPIF_LIST_INSERT_AT(testlist, spif_str_new_from_ptr(buff), idx););
PERF_END();
s = spif_str_new();
PERF_BEGIN("SPIF_LIST_REMOVE() macro");
- buff[0] = SPIF_CAST_C(char) (rand() % 256);
+ buff[0] = SPIF_CAST_C(char) (rand() & 0xff);
spif_str_init_from_ptr(s, buff);
PERF_TEST(s2 = SPIF_CAST(str) SPIF_LIST_REMOVE(testlist, s); if
(!SPIF_STR_ISNULL(s2)) {spif_str_del(s2);});
spif_str_done(s);
@@ -553,6 +813,9 @@
if ((ret = perf_strings()) != 0) {
return ret;
}
+ if ((ret = perf_hashes()) != 0) {
+ return ret;
+ }
if ((ret = perf_options()) != 0) {
return ret;
}
===================================================================
RCS file: /cvsroot/enlightenment/eterm/libast/test/test.c,v
retrieving revision 1.32
retrieving revision 1.33
diff -u -3 -r1.32 -r1.33
--- test.c 21 Jan 2004 23:20:46 -0000 1.32
+++ test.c 23 Jan 2004 01:44:51 -0000 1.33
@@ -21,7 +21,7 @@
* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
-static const char cvs_ident[] = "$Id: test.c,v 1.32 2004/01/21 23:20:46 mej Exp $";
+static const char cvs_ident[] = "$Id: test.c,v 1.33 2004/01/23 01:44:51 mej Exp $";
#if defined(HAVE_CONFIG_H) && (HAVE_CONFIG_H != 0)
# include <config.h>
@@ -218,141 +218,220 @@
return 0;
}
-#define HASHSTATE 1
-#define HASHLEN 1
#define MAXPAIR 80
-#define MAXLEN 70
+#define MAXLEN 80
int
test_hash_functions(void)
{
- TEST_BEGIN("Jenkins hash functions");
- {
- spif_uint32_t buf[256];
- spif_uint32_t i;
- spif_uint32_t h = 0;
+ spif_uint8_t i;
- for (i = 0; i < 256; i++) {
- h = jenkins_hash(buf, i, h);
- }
- TEST_FAIL_IF(h == 0);
- for (i = 0; i < 256; i++) {
- h = jenkins_hash32(buf, i, h);
+ for (i = 0; i < 6; i++) {
+ spifhash_func_t hash_func;
+ spif_uint32_t key_length, input_byte, trials, successes = 0, hash, ref_hash;
+ spif_uint8_t buff[MAXLEN + 20], *pbuff;
+ spif_uint8_t align1[] = "This has got the amazing aroma of bovine fecal
matter...";
+ spif_uint8_t align2[] = "xThis has got the amazing aroma of bovine fecal
matter...";
+ spif_uint8_t align3[] = "xxThis has got the amazing aroma of bovine fecal
matter...";
+ spif_uint8_t align4[] = "xxxThis has got the amazing aroma of bovine fecal
matter...";
+ spif_uint32_t j;
+
+ if (i == 0) {
+ TEST_NOTICE("*** Testing Jenkins hash:");
+ hash_func = spifhash_jenkins;
+ } else if (i == 1) {
+ TEST_NOTICE("*** Testing Jenkins32 hash:");
+ hash_func = spifhash_jenkins32;
+ } else if (i == 2) {
+#if WORDS_BIGENDIAN
+ continue;
+#else
+ TEST_NOTICE("*** Testing JenkinsLE hash:");
+ hash_func = spifhash_jenkinsLE;
+#endif
+ } else if (i == 3) {
+ TEST_NOTICE("*** Testing rotating hash:");
+ hash_func = spifhash_rotating;
+ } else if (i == 4) {
+ TEST_NOTICE("*** Testing one-at-a-time hash:");
+ hash_func = spifhash_one_at_a_time;
+ } else if (i == 5) {
+ TEST_NOTICE("*** Testing FNV hash:");
+ hash_func = spifhash_fnv;
}
- TEST_FAIL_IF(h == 0);
- }
- {
- spif_uint8_t qa[MAXLEN + 1], qb[MAXLEN + 2], *a = &qa[0], *b = &qb[1];
- spif_uint32_t c[HASHSTATE], d[HASHSTATE], i, j = 0, k, l, m, z;
- spif_uint32_t e[HASHSTATE], f[HASHSTATE], g[HASHSTATE], h[HASHSTATE];
- spif_uint32_t x[HASHSTATE], y[HASHSTATE];
- spif_uint32_t hlen;
-
- /*printf("No more than %d trials should ever be needed\n", MAXPAIR / 2);*/
- for (hlen = 0; hlen < MAXLEN; hlen++) {
- z = 0;
- for (i = 0; i < hlen; i++) {
- /*----------------------- for each input byte, */
- for (j = 0; j < 8; j++) {
- /*------------------------ for each input bit, */
- for (m = 1; m < 8; m++) {
- /*------------ for several possible seeds, */
- for (l = 0; l < HASHSTATE; l++)
- e[l] = f[l] = g[l] = h[l] = x[l] = y[l] =
~(SPIF_CAST(uint32) 0);
-
- /*---- check that every output bit is affected by that input
bit */
- for (k = 0; k < MAXPAIR; k += 2) {
- spif_uint32_t finished = 1;
-
- /* keys have one bit different */
- for (l = 0; l < hlen + 1; l++) {
- a[l] = b[l] = (spif_uint8_t) 0;
+
+ TEST_BEGIN("effect of every input bit on every output bit");
+ for (key_length = 0; key_length < MAXLEN; key_length++) {
+ /* For each key length up to 70 bytes... */
+
+ if ((hash_func == spifhash_jenkins32)
+ && (key_length % 4)) {
+ successes++;
+ continue;
+ }
+ trials = 0;
+ for (input_byte = 0; input_byte < key_length; input_byte++) {
+ /* ...for each input byte... */
+ spif_uint32_t input_bit;
+
+ for (input_bit = 0; input_bit < 8; input_bit++) {
+ /* ...for each input bit... */
+ spif_uint32_t seed;
+
+ for (seed = 1; seed < 8; seed++) {
+ /* ...use several possible seeds... */
+ spif_uint32_t e, f, g, h, x, y;
+ spif_uint32_t bit_pair;
+
+ /* Initialize to ~0 (0xffffffff). */
+ e = f = g = h = x = y = ~(SPIF_CAST(uint32) 0);
+
+ /* ...to make sure every output bit is affected by every
input bit. */
+ for (bit_pair = 0; bit_pair < MAXPAIR; bit_pair += 2) {
+ spif_uint8_t buff1[MAXLEN + 1], buff2[MAXLEN + 2];
+ spif_uint8_t *pbuff1 = &buff1[0], *pbuff2 = &buff2[1];
+ spif_uint32_t hash1, hash2;
+
+ for (j = 0; j < key_length + 1; j++) {
+ /* Initialize keys to all zeros. */
+ pbuff1[j] = pbuff2[j] = (spif_uint8_t) 0;
}
- /* have a and b be two keys differing in only one bit */
- a[i] ^= (k << j);
- a[i] ^= (k >> (8 - j));
- c[0] = jenkins_hash(a, hlen, m);
- b[i] ^= ((k + 1) << j);
- b[i] ^= ((k + 1) >> (8 - j));
- d[0] = jenkins_hash(b, hlen, m);
- /* check every bit is 1, 0, set, and not set at least
once */
- for (l = 0; l < HASHSTATE; l++) {
- e[l] &= (c[l] ^ d[l]);
- f[l] &= ~(c[l] ^ d[l]);
- g[l] &= c[l];
- h[l] &= ~c[l];
- x[l] &= d[l];
- y[l] &= ~d[l];
- if (e[l] | f[l] | g[l] | h[l] | x[l] | y[l])
- finished = 0;
+
+ /* Then make them differ by exactly one bit, the
input_bit.
+ bit_pair will always end in 0, so bit_pair + 1 will
always
+ end in 1. It's then shifted by input_bit to test the
+ current bit to test all 8 of the lowest bits in
sequence. */
+ pbuff1[input_byte] ^= (bit_pair << input_bit);
+ pbuff1[input_byte] ^= (bit_pair >> (8 - input_bit));
+ pbuff2[input_byte] ^= ((bit_pair + 1) << input_bit);
+ pbuff2[input_byte] ^= ((bit_pair + 1) >> (8 - input_bit));
+
+ /* Hash them. */
+ if (hash_func == spifhash_jenkins32) {
+ hash1 = hash_func(pbuff1, key_length / 4, seed);
+ hash2 = hash_func(pbuff2, key_length / 4, seed);
+ } else {
+ hash1 = hash_func(pbuff1, key_length, seed);
+ hash2 = hash_func(pbuff2, key_length, seed);
}
- if (finished)
+
+ /* Make sure every bit is 1 or 0 at least once. */
+ e &= (hash1 ^ hash2); f &= ~(hash1 ^ hash2);
+ g &= hash1; h &= ~hash1;
+ x &= hash2; y &= ~hash2;
+ if (!(e | f | g | h | x | y)) {
+ /* They're all 0. That means they've all changed at
least once. */
break;
+ }
}
- if (k > z)
- z = k;
- if (k == MAXPAIR) {
+ if (bit_pair > trials) {
+ trials = bit_pair;
+ }
+ if (bit_pair == MAXPAIR) {
+#if UNUSED_BLOCK
printf("Some bit didn't change: ");
- printf("%.8lx %.8lx %.8lx %.8lx %.8lx %.8lx ", e[0],
f[0], g[0], h[0], x[0], y[0]);
- printf("i %ld j %ld m %ld len %ld\n", i, j, m, hlen);
+ printf("%.8lx %.8lx %.8lx %.8lx %.8lx %.8lx ",
+ SPIF_CAST_C(unsigned long) e,
+ SPIF_CAST_C(unsigned long) f,
+ SPIF_CAST_C(unsigned long) g,
+ SPIF_CAST_C(unsigned long) h,
+ SPIF_CAST_C(unsigned long) x,
+ SPIF_CAST_C(unsigned long) y);
+ printf("input_byte %lu input_bit %lu seed %lu key
length %lu\n",
+ SPIF_CAST_C(unsigned long) input_byte,
+ SPIF_CAST_C(unsigned long) input_bit,
+ SPIF_CAST_C(unsigned long) seed,
+ SPIF_CAST_C(unsigned long) key_length);
+#endif
}
- if (z == MAXPAIR)
+ if (trials == MAXPAIR) {
+ /* Easy way to break out of a crapload of for loops. */
goto done;
+ }
}
}
}
done:
- if (z < MAXPAIR) {
- printf("Mix success %2ld bytes %2ld seeds ", i, m);
- printf("required %ld trials\n", z / 2);
+ if (trials < MAXPAIR) {
+ successes++;
+#if UNUSED_BLOCK
+ printf("Mix success: %2lu-byte key required %2lu trials (%lu so
far).\n",
+ SPIF_CAST_C(unsigned long) input_byte,
+ SPIF_CAST_C(unsigned long) trials / 2,
+ SPIF_CAST_C(unsigned long) successes);
+#endif
}
}
- printf("\n");
- }
- {
- spif_uint8_t buf[MAXLEN + 20], *b;
- spif_uint32_t len;
- spif_uint8_t q[] = "This is the time for all good men to come to the aid of
their country";
- spif_uint8_t qq[] = "xThis is the time for all good men to come to the aid of
their country";
- spif_uint8_t qqq[] = "xxThis is the time for all good men to come to the aid
of their country";
- spif_uint8_t qqqq[] = "xxxThis is the time for all good men to come to the
aid of their country";
- spif_uint32_t h, i, j, ref, x, y;
-
- printf("Endianness. These should all be the same:\n");
- printf("%.8lx\n", jenkins_hash(q, sizeof(q) - 1, SPIF_CAST(uint32) 0));
- printf("%.8lx\n", jenkins_hash(qq + 1, sizeof(q) - 1, SPIF_CAST(uint32) 0));
- printf("%.8lx\n", jenkins_hash(qqq + 2, sizeof(q) - 1, SPIF_CAST(uint32) 0));
- printf("%.8lx\n", jenkins_hash(qqqq + 3, sizeof(q) - 1, SPIF_CAST(uint32) 0));
- printf("\n");
- for (h = 0, b = buf + 1; h < 8; h++, b++) {
- for (i = 0; i < MAXLEN; i++) {
- len = i;
- for (j = 0; j < i; j++)
- *(b + j) = 0;
-
- /* these should all be equal */
- ref = jenkins_hash(b, len, SPIF_CAST(uint32) 1);
- *(b + i) = (spif_uint8_t) ~ 0;
- *(b - 1) = (spif_uint8_t) ~ 0;
- x = jenkins_hash(b, len, SPIF_CAST(uint32) 1);
- y = jenkins_hash(b, len, SPIF_CAST(uint32) 1);
- if ((ref != x) || (ref != y)) {
- printf("alignment error: %.8lx %.8lx %.8lx %ld %ld\n", ref, x, y,
h, i);
- }
+ printf("%.2f%% mix success rate in %d key lengths...",
+ (100.0 * successes / key_length), key_length);
+ TEST_FAIL_IF(successes == 0);
+ TEST_PASS();
+
+ /* Make sure nothing but the key is hashed, regardless of alignment. */
+ TEST_BEGIN("endian cleanliness");
+ key_length = CONST_STRLEN(align1);
+ if (hash_func == spifhash_jenkins32) {
+ if (key_length % 4) {
+ TEST_FAIL_IF(key_length);
+ } else {
+ key_length /= 4;
}
}
- }
- {
- spif_uint8_t buf[1];
- spif_uint32_t h, i, state[HASHSTATE];
+ ref_hash = hash_func(align1, key_length, 0);
+ hash = hash_func(align2 + 1, key_length, 0);
+ /*printf("Reference hash 0x%08x, hash 0x%08x for length %lu\n", ref_hash,
hash, key_length);*/
+ TEST_FAIL_IF(hash != ref_hash);
+ hash = hash_func(align3 + 2, key_length, 0);
+ TEST_FAIL_IF(hash != ref_hash);
+ hash = hash_func(align4 + 3, key_length, 0);
+ TEST_FAIL_IF(hash != ref_hash);
+
+ for (j = 0, pbuff = buff + 1; j < 8; j++, pbuff++) {
+ for (key_length = 0; key_length < MAXLEN; key_length++) {
+ if ((hash_func == spifhash_jenkins32)
+ && (key_length % 4)) {
+ continue;
+ }
+ MEMSET(buff, 0, sizeof(buff));
+ if (hash_func == spifhash_jenkins32) {
+ ref_hash = hash_func(pbuff, key_length / 4, 1);
+ } else {
+ ref_hash = hash_func(pbuff, key_length, 1);
+ }
+ *(pbuff + key_length) = ~(SPIF_CAST(uint8) 0);
+ *(pbuff - 1) = ~(SPIF_CAST(uint8) 0);
+ if (hash_func == spifhash_jenkins32) {
+ hash = hash_func(pbuff, key_length / 4, 1);
+ } else {
+ hash = hash_func(pbuff, key_length, 1);
+ }
+ /*printf("Reference hash 0x%08x, hash 0x%08x for length %lu\n",
ref_hash, hash, key_length);*/
+ TEST_FAIL_IF(hash != ref_hash);
+ }
+ }
+ TEST_PASS();
- buf[0] = ~0;
- for (i = 0; i < HASHSTATE; i++)
- state[i] = 1;
- printf("These should all be different\n");
- for (i = 0, h = 0; i < 8; i++) {
- h = jenkins_hash(buf, SPIF_CAST(uint32) 0, h);
- printf("%2ld 0-byte strings, hash is %.8lx\n", i, h);
+ /* We cannot test the rotating hash or the FNV hash here. The
+ rotating hash repeats after 4 zero-length keys. The FNV
+ hash generates constant hash values for zero-length keys. */
+ if ((hash_func != spifhash_rotating)
+ && (hash_func != spifhash_fnv)) {
+ spif_uint32_t null_hashes[8];
+ spif_uint8_t one_byte;
+
+ TEST_BEGIN("hashes of empty strings");
+ one_byte = ~0;
+ for (j = 0, hash = 0; j < 8; j++) {
+ spif_uint32_t k;
+
+ hash = hash_func(&one_byte, SPIF_CAST(uint32) 0, hash);
+ null_hashes[j] = hash;
+ /*printf("Empty string hash %lu is 0x%08x\n", j, hash);*/
+ for (k = j - 1; k < 8; k--) {
+ TEST_FAIL_IF(null_hashes[j] == null_hashes[k]);
+ }
+ }
+ TEST_PASS();
}
}
@@ -938,13 +1017,13 @@
for (i = 0; i < 3; i++) {
if (i == 0) {
- TEST_NOTICE("Testing list interface class, linked_list instance:");
+ TEST_NOTICE("*** Testing list interface class, linked_list instance:");
testlist = SPIF_LIST_NEW(linked_list);
} else if (i == 1) {
- TEST_NOTICE("Testing list interface class, dlinked_list instance:");
+ TEST_NOTICE("*** Testing list interface class, dlinked_list instance:");
testlist = SPIF_LIST_NEW(dlinked_list);
} else if (i == 2) {
- TEST_NOTICE("Testing list interface class, array instance:");
+ TEST_NOTICE("*** Testing list interface class, array instance:");
testlist = SPIF_LIST_NEW(array);
} else if (i == 3) {
}
@@ -1204,13 +1283,13 @@
for (i = 0; i < 3; i++) {
if (i == 0) {
- TEST_NOTICE("Testing vector interface class, linked_list instance:");
+ TEST_NOTICE("*** Testing vector interface class, linked_list instance:");
testvector = SPIF_VECTOR_NEW(linked_list);
} else if (i == 1) {
- TEST_NOTICE("Testing vector interface class, dlinked_list instance:");
+ TEST_NOTICE("*** Testing vector interface class, dlinked_list instance:");
testvector = SPIF_VECTOR_NEW(dlinked_list);
} else if (i == 2) {
- TEST_NOTICE("Testing vector interface class, array instance:");
+ TEST_NOTICE("*** Testing vector interface class, array instance:");
testvector = SPIF_VECTOR_NEW(array);
} else if (i == 3) {
}
-------------------------------------------------------
The SF.Net email is sponsored by EclipseCon 2004
Premiere Conference on Open Tools Development and Integration
See the breadth of Eclipse activity. February 3-5 in Anaheim, CA.
http://www.eclipsecon.org/osdn
_______________________________________________
enlightenment-cvs mailing list
[EMAIL PROTECTED]
https://lists.sourceforge.net/lists/listinfo/enlightenment-cvs
