Changeset 1232

Timestamp:

2000-06-23T14:25:48+12:00 (24 years ago)

Author:

gwp

Message:

Description of problem in hashing algorithm added to comments,
along with a description of two likely causes. No changes made
to code.

File:

• trunk/gsdl/src/hashfile/hashfile.cpp (modified) (3 diffs)

trunk/gsdl/src/hashfile/hashfile.cpp

@@ -143 +143 @@
 
 
+
+// create a hash string from the contents of a file.
+//
+// The file is treated as a large base 256 number (each char is a digit),
+// and the hash value is the remainder when this number is divided by a
+// very large prime.
+//
+// PROBLEM: This is a flawed hash function because the rightmost (highest)
+// value in remainder is more likely to be a "1" than it is to be any other
+// number.  
+//
+// EVIDENCE: About 50% of the files in any GSDL directory have a hash code
+// that starts with 01* which implies (based on the my_convert_num function)
+// that the rightmost "digit" of the remainder = z such that (z % 16 = 0)
+// and (z / 16 = 1) which means (z = 1).
+//
+// POSSIBLE CAUSE: Characters in the file are read one at a time; after each 
+// one is read it is prepended to the remainder, then the remainder is
+// recalculated on the string thus far seen.  I think the math here 
+// may be just plain wrong.
+//
+// ANOTHER POSSIBLE CAUSE (this appears to be a genuine bug): Each character 
+// from the file is read into  remainder at the most significant end, and
+// when that character is a zero you get a number like "01" which would
+// be considered larger than a number like "8" because it is longer (two
+// digits instead of 1).  
+//
+// These comments added by Gordon Paynter ([email protected]) on
+// June 23, 2000.  I didn't write this code, however.
+
 char *hashfile (char *filename) {
   FILE *infile = (FILE *)NULL;
   int i;
 
-  // calculate the 8 multiples of the prime number to use
-  // in the long division
   number primepow[8];
   number pow;
@@ -163 +191 @@
   pow.len = 12;
 
+  // calculate 8 multiples of the prime number.
+  // These are used to find the remainder using only subtraction operations
   for (i=0; i<8; i++) {
     primepow[i] = pow;
@@ -168 +198 @@
   }
 
+  // The "remainder" after division by the prime.  Our result.
+  remainder.len = 0;
+
+  // open the file
   infile = fopen (filename, "rb");
   if (infile == NULL) {
     return (char *)NULL;
   }
+  c = (unsigned char)fgetc(infile);
   
-  remainder.len = 0;
-  c = (unsigned char)fgetc(infile);
   while (!feof (infile)) {
-    // remainder = remainder * 256 + c
+
+    // make sure the remainder has not grown too large
     if (remainder.len == MAXNUMLEN-1) {
       fprintf (stderr, "ERROR - number overflow\n");
       return (char *)NULL;
     }
+
+    // remainder = remainder * 256 + c
     for (i=remainder.len; i>0; i--) {
       remainder.num[i] = remainder.num[i-1];
     }
     remainder.num[0] = c;
-    if (remainder.len > 0 || c != 0) remainder.len = remainder.len+1;
+    if (remainder.len > 0 || c != 0) remainder.len = remainder.len+1;
     
+    // remainder = (remainder % large-prime-number)
     for (i=7; i>=0; i--) {
       my_ifpos_dec (remainder, primepow[i]);
     }
 
+    // read a new character from the file
     c = (unsigned char)fgetc(infile);
   }