Changeset 1279 for branches/New_Config_Format-branch/gsdl/src/hashfile/hashfile.cpp

Timestamp:

2000-07-13T10:21:53+12:00 (24 years ago)

Author:

sjboddie

Message:

merged changes to trunk into New_Config_Format branch

File:

• branches/New_Config_Format-branch/gsdl/src/hashfile/hashfile.cpp (modified) (3 diffs)

branches/New_Config_Format-branch/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).
+//
+// MAJOR REASON: suppose our prime number was 19.  Then, if we have a 
+// reasonably random distribution of numbers for which we are going to 
+// calculate (N % 19), we expect to get a roughly uniform distribution
+// of remainders where the possible values are 0, 1, 2, 3... 18.  The
+// problem is that 9 out of the 19 possible values (10,11... 18) start
+// with the digit 1.  Thus our hascode will start with "01".
+//
+// ANOTHER PROBLEM: 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 am sure the math here 
+// is wrong - if I try calculating (111 mod 7) by the same algorithm, it
+// simply does nor work.
+//
+// ANOTHER POSSIBLE PROLEM: 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]) in
+// June 2000.  I didn't write any 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 +199 @@
   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 +206 @@
   }
 
+  // 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);
   }