git.8kb.co.uk Git - dataflex/df32func/blob - src/df32/hash.inc

   1 //-------------------------------------------------------------------------\r
   2 // hash.inc\r
   3 //      This file contains some DataFlex 3.2 Console Mode functions\r
   4 //      to provide limited hashing algorithms.  More advanced hashing\r
   5 //      can be found in win32.inc.\r
   6 //\r
   7 // This file is to be included in df32func.mk\r
   8 //\r
   9 // Copyright (c) 2006-2009, glyn@8kb.co.uk\r
  10 // \r
  11 // df32func/hash.inc\r
  12 //-------------------------------------------------------------------------\r
  13 \r
  14 //-------------------------------------------------------------------------\r
  15 // Functions\r
  16 //-------------------------------------------------------------------------\r
  17 \r
  18 // Produces an integer hash value for indexing into a DataFlex array.\r
  19 //\r
  20 // This is a rather unaccomplished hash, but is specifically designed to produce\r
  21 // positive hashed values with a relatively low integer range (< 10,000,000)\r
  22 // in order to give a decent distribution and still fit into a DataFlex 3.2 \r
  23 // array object.\r
  24 // It can without doubt be improved.\r
  25 //\r
  26 // Note that whilst this hash may appear to preserve ascii order to some \r
  27 // degree this is an artifact rather than by design and cannot be relied on.\r
  28 function hash_for_df_arrays global string argv returns integer\r
  29     local integer l_iHash\r
  30     local string l_sTmp\r
  31     \r
  32     move 0 to l_iHash\r
  33     move (lowercase(trim(argv))) to l_sTmp\r
  34     \r
  35     if (l_sTmp <> "") begin\r
  36         // Start at the first character of the string and produce distributed starting points for integer hash values\r
  37         if (mid(l_sTmp,1,1)) in "1234567890" move (((ascii(mid(l_sTmp,1,1)))-47)*200000) to l_iHash                 //index at 1-10\r
  38         if (mid(l_sTmp,1,1)) in "abcdefghijklmnopqrstuvwxyz" move (((ascii(mid(l_sTmp,1,1)))-86)*200000) to l_iHash //index at 11-36        \r
  39         if not (mid(l_sTmp,1,1)) in "1234567890abcdefghijklmnopqrstuvwxyz" move (37*200000) to l_iHash              //index at 37+\r
  40 \r
  41         // Take the sum of the second, last and middle chars (upper and lowercase) in the string and add to the hash\r
  42         if (length(argv) > 1) calc (l_iHash + (ascii(mid(argv,1,2)))) to l_iHash\r
  43         if (length(argv) > 2) calc (l_iHash + (ascii(mid(argv,1,(length(argv)))))) to l_iHash\r
  44         if (length(argv) > 4) calc (l_iHash + (ascii(mid(argv,1,(length(argv)/2))))) to l_iHash\r
  45 \r
  46         // If the string is longer than 9 chars add the second last val * 100 to the hash\r
  47         if (length(argv) > 9) calc (l_iHash + (100*(ascii(mid(argv,1,(length(argv)-2)))))) to l_iHash\r
  48 \r
  49         // Add the length of the string onto the hash if shorter than 255 chars, else add 256.\r
  50         if (length(argv) > 255) calc (l_iHash + 256) to l_iHash\r
  51         else calc (l_iHash + length(argv)) to l_iHash\r
  52     end\r
  53     else begin\r
  54         move 0 to l_iHash\r
  55     end\r
  56     \r
  57     function_return l_iHash\r
  58 end_function\r
  59 \r
  60 // Chop up an integer hash that is out of the optimal DataFlex 3.2 array\r
  61 // size range and make it fit. This reduces the uniqueness of the hash but\r
  62 // unfortuantely is a necessary evil when using out of range hashes.\r
  63 function reduce_hash global integer argv returns integer\r
  64     local integer l_iHash\r
  65     \r
  66     // Make sure positive\r
  67     if (argv < 0) calc (argv*-1) to l_iHash\r
  68     else move argv to l_iHash\r
  69     \r
  70     // Unashamedly chop out the middle range\r
  71     if (length(string(l_iHash)) > 7) begin\r
  72         move (integer(left(string(l_iHash),3)+right(string(l_iHash), 3))) to l_iHash\r
  73     end\r
  74         \r
  75     function_return l_iHash\r
  76 end_function\r
  77 \r
  78 // Djb2 hashing from Dan Bernstein\r
  79 //\r
  80 // The main info is here http://fr.wikipedia.org/wiki/Table_de_hachage#Fonction_de_Hachage\r
  81 //\r
  82 // http://en.wikipedia.org/wiki/Daniel_J._Bernstein\r
  83 // http://cr.yp.to/djb.html\r
  84 // http://www.cse.yorku.ca/~oz/hash.html\r
  85 function hash_djb2 global string argv returns integer\r
  86     local integer l_iHash l_i\r
  87     \r
  88     move 5381 to l_iHash\r
  89     \r
  90     for l_i from 1 to (length(argv))\r
  91         move ((LShift(l_iHash,5) + l_iHash) + (ascii(mid(argv,1,L_i)))) to l_iHash\r
  92     loop\r
  93     \r
  94     function_return l_iHash\r
  95 end_function\r
  96 \r
  97 // This is the SDBM hashing algorithm as used in berkeley DB\r
  98 //\r
  99 // http://cpansearch.perl.org/src/RGARCIA/perl-5.10.0/ext/SDBM_File/sdbm/README\r
 100 // http://en.wikipedia.org/wiki/Dbm\r
 101 // http://en.wikipedia.org/wiki/Sleepycat_Software\r
 102 // http://en.wikipedia.org/wiki/Berkeley_DB\r
 103 function hash_sdbm global string argv returns integer\r
 104     local integer l_iHash l_i\r
 105     \r
 106     move 0 to l_iHash\r
 107     \r
 108     for l_i from 1 to (length(argv))\r
 109         move ((ascii(mid(argv,1,L_i))) + (LShift(l_iHash,6)) + (LShift(l_iHash,16)) - l_iHash) to l_iHash\r
 110     loop\r
 111     \r
 112     function_return l_iHash\r
 113 end_function\r
 114 \r
 115 // Lazy hash, efficient for small fairly unique strings.\r
 116 function hash_lazy global string argv returns integer\r
 117     local integer l_iHash l_i\r
 118     \r
 119     move 0 to l_iHash\r
 120     \r
 121     for l_i from 1 to (length(argv))\r
 122         move (l_iHash + (ascii(mid(argv,1,L_i)))) to l_iHash\r
 123     loop\r
 124     \r
 125     function_return l_iHash\r
 126 end_function\r