home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_10_02 / 1002049a < prev    next >
Text File  |  1991-12-09  |  11KB  |  365 lines
  1. /*
  2.  *  (C) Copyright 1990 Ron Burk
  3.  *  All Rights Reserved
  4.  *
  5.  *  makehash.c - program to make hashing functions.
  6.  *
  7.  *  Note that this is a C++ program.  It has been compiled with Turbo C++
  8.  *  and Zortech C++.  There is conditional code to hack around the fact that
  9.  *  Zortech does not allow a member function and a const member function of
  10.  *  the same name.
  11.  */
  12.  
  13. #ifdef __ZTC__
  14.     #define CONST
  15. #else
  16.     #define CONST const
  17. #endif
  18.  
  19. #include <assert.h>
  20. #include <ctype.h>
  21. #include <limits.h>
  22. #include <stdio.h>
  23. #include <stdlib.h>
  24. #include <string.h>
  25.  
  26. typedef unsigned char   uchar;
  27. enum    bool            { FALSE, TRUE };
  28.  
  29. FILE    *OpenFile(const char *FileName, const char *IOMode)
  30.     {
  31.     assert(FileName != 0);
  32.     if(IOMode == 0)
  33.         IOMode  = "r";
  34.     FILE    *FileDescriptor = fopen(FileName, IOMode);
  35.     if(FileDescriptor == 0)
  36.         {
  37.         fprintf(stderr, "'%s': Can't open for mode '%s'\n",
  38.                     FileName, IOMode);
  39.         exit(EXIT_FAILURE);
  40.         }
  41.     return FileDescriptor;
  42.     }
  43.  
  44. char    *strdup(const char *s, size_t len)
  45.     {
  46.     char    *ret    = (char *)malloc(len+1);
  47.     memcpy(ret, s, len);
  48.     ret[len]      = '\0';
  49.     return ret;
  50.     }
  51.  
  52. inline  char    *strdup(const char *s)
  53.     {
  54.     return strdup(s, strlen(s));
  55.     }
  56.  
  57. class   KeyWord
  58.     {
  59. public:
  60.     KeyWord(char *Name=0, char *Value=0);
  61.     char    *Name()
  62.         { return Name_; }
  63.     char    *Value()
  64.         { return Value_; }
  65.     bool    Read(FILE *FileDescriptor);
  66. private:
  67.     char    *Name_;
  68.     char    *Value_;
  69.     };
  70.  
  71. class   KeyTable
  72.     {
  73. public:
  74.     KeyTable(const char *FileName);
  75.     int     NumberOfKeys()
  76.         { return NumberOfKeys_; }
  77.     KeyWord *operator[](int KeyWordNumber);
  78.     void    MoveTo(int Position1, int Position2);
  79.     static const int MAXKEYWORDS;
  80. private:
  81.     int     NumberOfKeys_;
  82.     KeyWord **Table;
  83.     };
  84. const int KeyTable::MAXKEYWORDS = 100;
  85.  
  86. class   ByteTable
  87.     {
  88. public:
  89.     ByteTable();
  90.     void    SetAscending();
  91.     void    Shuffle(int Shuffles=1);
  92.     int     Index(int Value);
  93.     uchar   &operator[](int ByteNumber);
  94. #ifndef __ZTC__
  95.     uchar   operator[](int ByteNumber)  const;
  96. #endif
  97.     ByteTable &operator=(int Value);
  98. private:
  99.     uchar   *Table;
  100.     };
  101.  
  102. // KeyWord member functions
  103. KeyWord::KeyWord(char *Name__, char *Value__)
  104.     : Name_(Name__), Value_(Value__)
  105.     {
  106.     }
  107.  
  108. /********************************
  109. KeyWord::Read - read a KeyWord from an open file.
  110.  
  111.     Each line in the KeyWord file must be a KeyWord line, an empty line,
  112. or a comment.  A KeyWord line is a line that contains a KeyWord
  113. optionally followed by white space and a value.  The KeyWord and the
  114. value can contain any characters except white space (except the KeyWord
  115. cannot begin with '#').  An empty line is a line that only contains
  116. white space.  A comment is any line that begins with a '#' (optionally
  117. preceeded by white space). 
  118.  
  119. ********************************/
  120.  
  121. bool    KeyWord::Read(FILE *FileDescriptor)
  122.     {
  123.     const int MAXLINE = 256;
  124.     char    Line[MAXLINE+1];
  125.  
  126.     Name_   = Value_    = 0;
  127.     while(fgets(Line, MAXLINE, FileDescriptor))
  128.         {
  129.         char *Scanner = Line;
  130.         while(*Scanner && isspace(*Scanner))    // allow leading white space
  131.             ++Scanner;
  132.         if(*Scanner && *Scanner != '#') // if not empty and not comment
  133.             {
  134.             Name_   = Scanner;      // remember start of KeyWord name
  135.             while(*Scanner && !isspace(*Scanner))
  136.                 ++Scanner;          // skip over name
  137.             if(*Scanner)            // if something follows the name
  138.                 {
  139.                 *Scanner++  = '\0'; // NUL-terminate the name
  140.                 while(*Scanner && isspace(*Scanner))
  141.                     ++Scanner;
  142.                 if(*Scanner)
  143.                     {
  144.                     Value_  = Scanner;  // remember start of value
  145.                     while(*Scanner && !isspace(*Scanner))
  146.                         ++Scanner;
  147.                     *Scanner    = '\0';
  148.                     Value_  = strdup(Value_);   // make permanent copy
  149.                     }
  150.                 }
  151.             Name_   = strdup(Name_);    // make permanent copy
  152.             return TRUE;
  153.             }
  154.         }
  155.  
  156.     return FALSE;   // hit End-Of-File
  157.     }
  158.  
  159. // KeyTable member functions
  160.  
  161. KeyTable::KeyTable(const char *FileName)
  162.     {
  163.     Table   = new KeyWord *[MAXKEYWORDS];
  164.     assert(Table != 0);
  165.     FILE    *KeyWordFile    = OpenFile(FileName, "r");
  166.     KeyWord CurrentKeyWord;
  167.     for(int KeyWordNumber=0; CurrentKeyWord.Read(KeyWordFile); ++KeyWordNumber)
  168.         {
  169.         Table[KeyWordNumber]    = new KeyWord;
  170.         *Table[KeyWordNumber]   = CurrentKeyWord;
  171.         printf( "name='%s', value='%s'\n", Table[KeyWordNumber]->Name(),
  172.             Table[KeyWordNumber]->Value());
  173.         }
  174.     NumberOfKeys_   = KeyWordNumber;
  175.     printf( "read %d keywords\n", KeyWordNumber);
  176.     }
  177.  
  178. KeyWord *KeyTable::operator[](int KeyWordNumber)
  179.     {
  180.     assert(KeyWordNumber >= 0);
  181.     assert(KeyWordNumber < NumberOfKeys());
  182.     return Table[KeyWordNumber];
  183.     }
  184. void    KeyTable::MoveTo(int MovePosition, int ToPosition)
  185.     {
  186.     KeyWord *Value  = Table[MovePosition];
  187.     int     Position;
  188.     for(Position=MovePosition; Position < NumberOfKeys()-1; ++Position)
  189.         Table[Position]     = Table[Position+1];
  190.     for(Position=NumberOfKeys()-1; Position >= ToPosition; --Position)
  191.         Table[Position]     = Table[Position-1];
  192.     Table[ToPosition]       = Value;
  193.     }
  194.  
  195.  
  196. // ByteTable member functions
  197.  
  198. ByteTable::ByteTable()
  199.     {
  200.     Table   = new uchar[256];
  201.     assert(Table != 0);
  202.     memset(Table, 0, 256);
  203.     }
  204.  
  205. void    ByteTable::SetAscending()
  206.     {
  207.     for(int ByteNumber=0; ByteNumber < 256; ++ByteNumber)
  208.         Table[ByteNumber]   = ByteNumber;
  209.     }
  210.  
  211. void    ByteTable::Shuffle(int Shuffles)
  212.     {
  213.     // swap each entry in the table with a randomly chosen entry
  214.  
  215.     for(int PassNumber=0; PassNumber < Shuffles; ++PassNumber)
  216.         {
  217.         for(int ByteNumber=0; ByteNumber < 256; ++ByteNumber)
  218.             {
  219.             int     RandomPartner   = rand() % 256;
  220.             uchar   OtherValue      = Table[RandomPartner];
  221.             Table[RandomPartner]    = Table[ByteNumber];
  222.             Table[ByteNumber]       = OtherValue;
  223.             }
  224.         }
  225.     }
  226.  
  227. uchar   &ByteTable::operator[](int ByteNumber)
  228.     {
  229.     assert(ByteNumber >= 0);
  230.     assert(ByteNumber <= 255);
  231.  
  232.     return Table[ByteNumber];
  233.     }
  234. #ifndef __ZTC__
  235. uchar   ByteTable::operator[](int ByteNumber) const
  236.     {
  237.     assert(ByteNumber >= 0);
  238.     assert(ByteNumber <= 255);
  239.  
  240.     return Table[ByteNumber];
  241.     }
  242. #endif
  243.  
  244. int     ByteTable::Index(int Value)
  245.     {
  246.     uchar    *Found  = (uchar *)memchr(Table, Value, 256);
  247.     if(Found)
  248.         return Found - Table;
  249.     else
  250.         return -1;
  251.     }
  252.  
  253. inline
  254. ByteTable &ByteTable::operator=(int Value)
  255.     {
  256.     assert(Value >= 0);
  257.     assert(Value <= 255);
  258.     memset(Table, Value, 256);
  259.     return *this;
  260.     }
  261.  
  262. int     ByteHash(const char *Text, const ByteTable &HashTable)
  263.     {
  264.     int     Hash    = 0;
  265.     while(*Text)
  266.         Hash    =   HashTable[*Text++ ^ Hash];
  267.     return Hash;
  268.     }
  269.  
  270. int     MakeHash(const char *KeyWordFileName);
  271.  
  272. void    Usage()
  273.     {
  274.     fprintf(stderr, "Usage: makehash keyfile\n");
  275.     exit(EXIT_FAILURE);
  276.     }
  277.  
  278. int     main(int argc, char **argv)
  279.     {
  280.     if(argc < 2)
  281.         Usage();
  282.     char    *KeyWordFileName    = argv[1];
  283.     exit(MakeHash(KeyWordFileName));
  284.     }
  285.  
  286. int     MakeHash(const char *KeyWordFileName)
  287.     {
  288.     KeyTable    InputTable(KeyWordFileName);
  289.     int         iKeyWord;
  290.     int         *Failures   = new int[InputTable.NumberOfKeys()];
  291.     assert(Failures != 0);
  292.     ByteTable   HashBytes;
  293.     for(int Attempts=0; Attempts < 999; ++Attempts)
  294.         {
  295.         for(int xx=0; xx < InputTable.NumberOfKeys(); ++xx) Failures[xx]=0;
  296.         for(int TableBase = 0; TableBase < 256; ++TableBase)
  297.             {
  298.         HashBytes.SetAscending();   // set equal to 0,1,2,...255
  299.         HashBytes.Shuffle();        // randomize
  300.             int         NotEligible[256];
  301.             for(int x=0; x < 256; ++x) NotEligible[x]   = 0;
  302.             for(int iKeyWord = 0; iKeyWord < InputTable.NumberOfKeys(); ++iKeyWord)
  303.                 {
  304.                 const char *Text    = InputTable[iKeyWord]->Name();
  305.                 int     TextLength  = strlen(Text);
  306.                 int         RandomWalk[99];
  307.                 int Hash = 0;
  308.                 uchar   H[99];
  309.                 for(int i = 0; i < TextLength; ++i)
  310.                     {
  311.                     int   j = Hash ^ Text[i];
  312.                     Hash    =   H[i]    = HashBytes[j];
  313.                     ++NotEligible[j];
  314.                     RandomWalk[i]   = j;
  315.                     }
  316.                 int     DesiredValue   = (iKeyWord + TableBase) % 256;
  317.                 for(i = TextLength-1; i >= 0; --i)
  318.                     {
  319.                     int     Pos = RandomWalk[i];
  320.                     --NotEligible[Pos];
  321.                     int Other   = HashBytes.Index(DesiredValue);
  322.     
  323.                     assert(Other >= 0);
  324.                     if(NotEligible[Pos] == 0 && NotEligible[Other] == 0)
  325.                         {
  326.                         HashBytes[Other]    = HashBytes[Pos];
  327.                         HashBytes[Pos]     = DesiredValue;
  328.                         ++NotEligible[Other];
  329.                         ++NotEligible[Pos];
  330.                         assert(ByteHash(Text, HashBytes)
  331.                                 == (iKeyWord + TableBase)%256);
  332.                         break;
  333.                         }
  334.                     else                        // else not eligible for swapping
  335.                         {
  336.                         DesiredValue    = Other ^ Text[i];
  337.                         ++NotEligible[Other];
  338.                         }
  339.                     }
  340.                 if(i < 0)
  341.                     break;
  342.                 }
  343.             if(iKeyWord >= InputTable.NumberOfKeys())
  344.                 {
  345.                 for(iKeyWord = 0; iKeyWord < InputTable.NumberOfKeys(); ++iKeyWord)
  346.                     {
  347.                     const char *Name = InputTable[iKeyWord]->Name();
  348.                     printf( "Hash('%s') = %d\n", Name, ByteHash(Name, HashBytes));
  349.                     }
  350.                 return EXIT_SUCCESS;
  351.                 }
  352.             else
  353.                 {
  354.                 if(++Failures[iKeyWord] > 20)
  355.                     {
  356.                     InputTable.MoveTo(iKeyWord, 0);
  357.                     break;
  358.                     }
  359.                 }
  360.             }
  361.         }
  362.     
  363.     return EXIT_FAILURE;
  364.     }
  365.