[Commit] nickle ChangeLog, 1.104, 1.105 float.c, 1.23, 1.24 hash.c,
1.8, 1.9 natural.c, 1.24, 1.25 string.c, 1.18, 1.19 value.c,
1.48, 1.49 value.h, 1.107, 1.108
Keith Packard
commit at keithp.com
Tue Nov 30 11:51:20 PST 2004
Committed by: keithp
Update of /local/src/CVS/nickle
In directory home.keithp.com:/tmp/cvs-serv28065
Modified Files:
ChangeLog float.c hash.c natural.c string.c value.c value.h
Log Message:
2004-11-30 Keith Packard <keithp at keithp.com>
* float.c: (FloatHash):
Provide hash function for float representation
* hash.c: (generate_crc32_table), (HashCrc32), (HashInit):
* value.h:
Implement general purpose crc32 function for hashing
* natural.c: (NaturalHash):
* string.c: (StringHash):
Use crc32 hash for naturals and strings
* value.c: (ValueHash), (NewDataCache):
Return Zero for representations without hash functions
instead of uninit (oops).
Initialize datacache to zero before adding as a root (just a cleanup)
Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/nickle/ChangeLog,v
retrieving revision 1.104
retrieving revision 1.105
diff -u -d -r1.104 -r1.105
--- ChangeLog 30 Nov 2004 18:28:21 -0000 1.104
+++ ChangeLog 30 Nov 2004 19:51:16 -0000 1.105
@@ -1,3 +1,21 @@
+2004-11-30 Keith Packard <keithp at keithp.com>
+
+ * float.c: (FloatHash):
+ Provide hash function for float representation
+
+ * hash.c: (generate_crc32_table), (HashCrc32), (HashInit):
+ * value.h:
+ Implement general purpose crc32 function for hashing
+
+ * natural.c: (NaturalHash):
+ * string.c: (StringHash):
+ Use crc32 hash for naturals and strings
+
+ * value.c: (ValueHash), (NewDataCache):
+ Return Zero for representations without hash functions
+ instead of uninit (oops).
+ Initialize datacache to zero before adding as a root (just a cleanup)
+
2004-11-30 Bart Massey <bart at cs.pdx.edu>
* math.5c
Index: float.c
===================================================================
RCS file: /local/src/CVS/nickle/float.c,v
retrieving revision 1.23
retrieving revision 1.24
diff -u -d -r1.23 -r1.24
--- float.c 27 Feb 2004 03:50:16 -0000 1.23
+++ float.c 30 Nov 2004 19:51:16 -0000 1.24
@@ -971,6 +971,15 @@
return True;
}
+static HashValue
+FloatHash (Value av)
+{
+ Float *a = &av->floats;
+
+ return (NaturalHash(a->mant->mag) ^ a->mant->sign ^
+ NaturalHash(a->exp->mag) ^ a->exp->sign);
+}
+
static void
FloatMark (void *object)
{
@@ -1002,7 +1011,9 @@
},
FloatPromote,
FloatReduce,
- FloatPrint
+ FloatPrint,
+ 0,
+ FloatHash,
};
Value
Index: hash.c
===================================================================
RCS file: /local/src/CVS/nickle/hash.c,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -d -r1.8 -r1.9
--- hash.c 29 Jul 2004 00:23:32 -0000 1.8
+++ hash.c 30 Nov 2004 19:51:16 -0000 1.9
@@ -140,9 +140,44 @@
EXIT ();
}
+#if HAVE_STDINT_H
+typedef uint32_t crc32_t;
+#else
+typedef unsigned int crc32_t;
+#endif
+
+static crc32_t crc32_table[256];
+
+static void
+generate_crc32_table(void)
+{
+ crc32_t c, p;
+ int n, m;
+
+ p = 0xedb88320;
+ for (n = 0; n < 256; n++)
+ {
+ c = n;
+ for (m = 0; m < 8; m++)
+ c = (c >> 1) ^ ((c & 1) ? p : 0);
+ crc32_table[n] = c;
+ }
+}
+
+HashValue
+HashCrc32 (unsigned char *bytes, int nbytes)
+{
+ crc32_t crc32 = ~0;
+ if (crc32_table[1] == 0) abort ();
+ while (nbytes--)
+ crc32 = (crc32 >> 8) ^ crc32_table[(crc32 ^ *bytes++) & 0xff];
+ return (HashValue) ~crc32;
+}
+
int
HashInit (void)
{
+ generate_crc32_table ();
return 1;
}
Index: natural.c
===================================================================
RCS file: /local/src/CVS/nickle/natural.c,v
retrieving revision 1.24
retrieving revision 1.25
diff -u -d -r1.24 -r1.25
--- natural.c 27 May 2004 23:30:55 -0000 1.24
+++ natural.c 30 Nov 2004 19:51:16 -0000 1.25
@@ -1410,20 +1410,11 @@
return True;
}
-#define hrot(i) (((i) << 1) | ((i) >> (sizeof (HashValue) * 8 - 1)))
-
HashValue
NaturalHash (Natural *a)
{
- HashValue h = 0;
- digit *at;
- int index;
-
- at = NaturalDigits (a);
- index = a->length;
- while (index--)
- h = hrot(h) ^ (HashValue) *at++;
- return h;
+ return HashCrc32 ((unsigned char *) &a->length,
+ sizeof (int) + sizeof (digit) * a->length);
}
int
Index: string.c
===================================================================
RCS file: /local/src/CVS/nickle/string.c,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -d -r1.18 -r1.19
--- string.c 8 Jun 2004 09:30:54 -0000 1.18
+++ string.c 30 Nov 2004 19:51:16 -0000 1.19
@@ -194,18 +194,11 @@
return StringChars (&v->string);
}
-#define hrot(i) (((i) << 1) | ((i) >> (sizeof (HashValue) * 8 - 1)))
-
static HashValue
StringHash (Value av)
{
- char *string = StringChars (&av->string);
- long len = av->string.length;
- HashValue h = 0;
-
- while (len--)
- h = hrot(h) ^ (HashValue) *string++;
- return h;
+ return HashCrc32 ((unsigned char *) StringChars(&av->string),
+ av->string.length);
}
ValueRep StringRep = {
Index: value.c
===================================================================
RCS file: /local/src/CVS/nickle/value.c,v
retrieving revision 1.48
retrieving revision 1.49
diff -u -d -r1.48 -r1.49
--- value.c 9 Oct 2004 22:38:28 -0000 1.48
+++ value.c 30 Nov 2004 19:51:16 -0000 1.49
@@ -679,10 +679,10 @@
ValueRep *rep;
if (!v)
- return 0;
+ return Zero;
rep = ValueRep(v);
if (!rep->hash)
- return 0;
+ return Zero;
return NewInt ((*rep->hash) (v) & MAX_NICKLE_INT);
}
@@ -810,8 +810,8 @@
sizeof (DataCache) +
size * sizeof (void *));
dc->size = size;
- MemAddRoot (dc);
memset (DataCacheValues(dc), '\0', size * sizeof (Value));
+ MemAddRoot (dc);
RETURN (dc);
}
Index: value.h
===================================================================
RCS file: /local/src/CVS/nickle/value.h,v
retrieving revision 1.107
retrieving revision 1.108
diff -u -d -r1.107 -r1.108
--- value.h 7 Jul 2004 07:32:47 -0000 1.107
+++ value.h 30 Nov 2004 19:51:16 -0000 1.108
@@ -1106,6 +1106,7 @@
Value Popcount(Value);
Bool Print (Value, Value, char format, int base, int width, int prec, int fill);
void PrintError (char *s, ...);
+HashValue HashCrc32 (unsigned char *bytes, int nbytes);
Value CopyMutable (Value v);
#ifdef HAVE_C_INLINE
static inline Value
More information about the Commit
mailing list