home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume15 / hash8 / hash8.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-06-05  |  10.9 KB  |  397 lines
  1. /*
  2.  * Date: March 17 1985            Author: Arch D. Robison
  3.  *                        Dept. of Computer Science
  4.  *                        University of Illinois
  5.  *                        Urbana-Champaign
  6.  *
  7.  *                    USENET:    robison@uiucdcs
  8.  *
  9.  * Hash8 copies stdin to stdout, while replacing certain identifiers.
  10.  * lint can be converted to accept long identifiers by hacking in hash8
  11.  * between /lib/cpp and /usr/lib/lint/lint appropriately.
  12.  *
  13.  * There are three ways to call hash8:
  14.  *
  15.  *     hash8 encode table
  16.  *         Map long identifiers and those beginning with Q 
  17.  *       into short identifiers Q%d
  18.  *
  19.  *     hash8 decode table
  20.  *         Map short identifiers Q%d into their long equivalents
  21.  *
  22.  *     hash8 _decode table
  23.  *         Map short identifiers _Q%d into their long equivalents
  24.  *        This is used to decode the linker's error messages
  25.  *
  26.  * The 'table' argument is the file name for the identifier map.
  27.  * The 'encode' calls will either create or expand the table.
  28.  *
  29.  * Typically, the encode option is used to preprocess input to the compiler
  30.  * or lint, and the decode option is used to decode error messages from
  31.  * the compiler.
  32.  *
  33.  * The constant HASHBITS may need to be changed.  It is the base two
  34.  * log of the number of distinct long identifiers which may be found.
  35.  * E.g. the value of 12 allows for 4096 long identifiers.
  36.  *
  37.  * Hash8 has not been thoroughly tested, though it can translate itself
  38.  * correctly.  Note that itself contains all sorts of quotes within quotes.
  39.  */
  40. #include <stdio.h>
  41. #include <ctype.h>
  42.  
  43. /*
  44.  * Reserved is an array of words which we don't want modified, such
  45.  * as the key word "register", or system functions longer than 7 characters.
  46.  * Feel free to add any others, though remember to clear your hash table
  47.  * files after recompiling.
  48.  */
  49. char **Reserved = NULL;
  50. int Res_max = 0;
  51. int Res_count = 0;
  52. char *Def_reserved[] = {
  53.    "continue",
  54.    "register",
  55.    "unsigned"
  56. };
  57.  
  58. extern char *malloc (), *strcpy ();
  59.  
  60. #define SIGCHARS 7        /* significant characters in identifier */
  61. #define HASHBITS 12        /* hash table address size */
  62. #define HASHLIMIT (1<<HASHBITS)
  63. #define HASHMASK (HASHLIMIT-1)
  64. #define PAGESIZE 4096        /* Memory allocation pagesize */ 
  65. #define MAXLINE 1024        /* Maximum length of a source line allowed */
  66.  
  67. #define W_SHORTEN  0        /* Identifier classes */
  68. #define W_NORMAL   1
  69. #define W_RESERVED 2
  70. #define W_Valid(N) ((N) >= 0 && (N) <= 2)
  71.  
  72. /*
  73.  * HashTab
  74.  *
  75.  * The identifier map is a hash table.  The table uses open addressing
  76.  * with linear probing for collision resolution.  Identifiers in the
  77.  * table are mapped into Qxxx, where xxx is the table address in hex.
  78.  *
  79.  * The hash table is effectively declared:
  80.  *
  81.  *      char *HashTab[HASHLIMIT];
  82.  *
  83.  * though the memory allocation is done with malloc.  Each empty hash table
  84.  * item is NULL.  Full entries point to an identifier.  The first byte of
  85.  * the identifier classifies the identifier:
  86.  *
  87.  *      W_NORMAL - don't modify this identifier
  88.  *    W_SHORTEN - shorten this identifier
  89.  *    W_RESERVE - reserved word 
  90.  */
  91. char **HashTab;
  92. int HashSize = 0;    /* Number of elements in hash table             */
  93. int NewTab;          /* Flag which is set to true if hash table is modified */
  94.  
  95. char *StrFree;         /* Pointer to base of free string area                 */
  96. int StrLeft = 0;     /* Number of characters left in free string area       */
  97.  
  98. /*
  99.  * Insert
  100.  * 
  101.  * Insert identifier in hash table
  102.  *
  103.  * In
  104.  *      k = index into hash table
  105.  *      S = identifier
  106.  *    Class = class of identifier (W_NORMAL,W_SHORTEN,W_RESERVED)
  107.  */
  108. void Insert (k,S,Class)
  109.    int k;
  110.    char *S;
  111.    int Class;
  112.    {
  113.       register int L;
  114.  
  115.       NewTab = 1;
  116.       HashSize++;
  117.       if ((StrLeft -= (L=2+strlen (S))) < 0)
  118.          StrFree = malloc (StrLeft=PAGESIZE);
  119.       *(HashTab[k] = StrFree) = Class;
  120.       strcpy (StrFree+1, S);
  121.       StrFree += L;
  122.       StrLeft -= L;
  123.    }               
  124.  
  125. /*
  126.  * LookUp
  127.  *
  128.  * Look up an identifer in the identifier hash table.
  129.  * If not found, then insert it in the table.
  130.  *
  131.  * The hashing uses open addressing with linear probing.
  132.  * The algorithm is a blue-light special, a better hash function
  133.  * (double hashing?) should be used.
  134.  * 
  135.  * In
  136.  *      S = identifier (must be at least seven characters if Duplicate == 0)
  137.  *      Class = identifier class (W_NORMAL,W_SHORTEN,W_RESERVED)
  138.  * Out
  139.  *      result = index into hash table 
  140.  */
  141. int LookUp (S,Class)
  142.    char *S;
  143.    int Class;
  144.    {
  145.       register int k,j;
  146.       register char *T;
  147.  
  148.       if (Class != W_SHORTEN) {
  149.  
  150.          /* Hash first seven characters of identifier */ 
  151.          for (j=0,k=0,T=S; j<SIGCHARS; j++, k+= *T++) k = (k<<1) + k;
  152.  
  153.          /* 7-character search for identifier in table */
  154.          for (j=k; HashTab[j&=HASHMASK] != NULL; j++) 
  155.             if (!strncmp (HashTab[j]+1,S,SIGCHARS)) 
  156.                if (!strcmp (HashTab[j]+1,S)) return j;
  157.            else {
  158.           Class = W_SHORTEN;
  159.           break;
  160.            }
  161.      /* The following test and assignment cause identifiers to be
  162.       * hashed even if they are the first long identifier.  This
  163.       * protects from truncation by the compiler.  Othewise, when
  164.       * you run adb you have to know which long id came first.
  165.       * Geoff Kuenning 11/8/86
  166.       */
  167.          if (Class == W_NORMAL  &&  strlen (S) > SIGCHARS)
  168.         Class = W_SHORTEN;
  169.       }
  170.  
  171.       if (Class == W_SHORTEN) {
  172.      /* 
  173.       * There is another identifier with the same 7-character prefix. 
  174.       * Hash the complete identifier and look it up in the table.
  175.       */
  176.          for (j=k; *T; j+= *T++) j = (j<<1) + j;
  177.  
  178.      /* all characters search for identifier in table */
  179.      for (; HashTab[j&=HASHMASK] != NULL; j++)
  180.            if (!strcmp (HashTab[j]+1,S)) return j;
  181.       }
  182.  
  183.       /* Identifier was not found - insert it in hash table */
  184.       Insert (j,S,Class);
  185.       if (HashSize == HASHLIMIT) 
  186.      fprintf (stderr,"hash8: table overflow\n"), exit (1);
  187.       return j;
  188.    }
  189.  
  190. #define C_CODE 0    /* Defines for translator states */
  191. #define S_QUOTE 1
  192. #define D_QUOTE 2
  193. #define COMMENT 3
  194.  
  195. #define ENCODE 0    /* Mode values for translator */
  196. #define DECODE 1
  197. #define _DECODE 2
  198.  
  199. /*
  200.  * Translate
  201.  *
  202.  * Translate input stream with identifier map.
  203.  *
  204.  * This should have been written with lex.
  205.  */
  206. Translate (Mode) 
  207.    int Mode;
  208.    {
  209.       register char C, *P, *Q;
  210.       char S[MAXLINE];
  211.       int k, state=C_CODE, IsQ;
  212.  
  213.       while (NULL != fgets (S,MAXLINE,stdin)) 
  214.          for (P=S; C= *P; )
  215.         switch (state) {
  216.            case COMMENT:
  217.               putchar (*P++);
  218.                   if (C == '*' && *P == '/') state=C_CODE, putchar (*P++);
  219.           break;
  220.            case S_QUOTE:
  221.            case D_QUOTE:
  222.           putchar (*P++);
  223.           switch (C) {
  224.              case '\'': if (state == S_QUOTE) state = C_CODE; break;
  225.              case '"' : if (state == D_QUOTE) state = C_CODE; break;
  226.              case '\\': putchar (*P++); break;
  227.              default: break; 
  228.           }
  229.               break;
  230.            
  231.                case C_CODE:
  232.           if (isalpha (C) || C=='_') {
  233.                  /* Beginning of identifier */
  234.                        for (Q=P; C= *Q, isalnum(C)||C=='_'; Q++);
  235.                  *Q = '\0';
  236.                     switch (Mode) {
  237.  
  238.             case ENCODE: /* We are encoding C source */
  239.                    IsQ = *P=='Q' && isdigit (P[1]);
  240.                           if (Q-P <= SIGCHARS && !IsQ) 
  241.                              fputs (P,stdout);
  242.                    else {
  243.                   k = LookUp (P,IsQ ? W_SHORTEN : W_NORMAL);
  244.                   if (*HashTab[k] != W_SHORTEN) fputs (P,stdout);
  245.                       else printf ("Q%d",k);
  246.                    }
  247.                break;
  248.  
  249.             case _DECODE: /* We are decoding linker messages */
  250.                    if (*P != '_') {
  251.                   fputs (P,stdout);
  252.                   break;
  253.                }
  254.                putchar (*P++);
  255.                /* continue on down to case DECODE */
  256.  
  257.             case DECODE: /* We are decoding error message */
  258.                           if (*P=='Q' && isdigit (P[1])) { 
  259.                   k=atoi(P+1);
  260.                   if (!(k &~HASHMASK) && HashTab[k]!=NULL) 
  261.                  P = HashTab[k] + 1;
  262.                }
  263.                    fputs (P,stdout);
  264.                break;
  265.              }
  266.                     *(P=Q) = C;
  267.                  } else if (isdigit (C)) {
  268.                  /* Skip number to avoid changing long numbers */
  269.                  while (isalnum(*P)) putchar (*P++);
  270.               } else {
  271.              putchar (*P++);
  272.              switch (C) {
  273.                 default: break;
  274.             case '\'': state = S_QUOTE; break;
  275.                         case '"' : state = D_QUOTE; break;
  276.                         case '/' : if (*P != '*') continue;
  277.                        state=COMMENT;
  278.                 case '\\': putchar (*P++); break;
  279.              }
  280.               }
  281.            }
  282.    }
  283.  
  284. /*
  285.  * ReadTab
  286.  *
  287.  * Read the hash table.
  288.  *
  289.  * In
  290.  *      Name = name of hash table file
  291.  */
  292. ReadTab (Name)
  293.    char *Name;
  294.    {
  295.       FILE *Table;
  296.       char S[MAXLINE];
  297.       int k,L,Class;
  298.  
  299.       /* First record all words we don't want mangled in hash table */      
  300.       for (k = 0;  k < sizeof (Def_reserved) / sizeof (char *);  k++)
  301.          LookUp (Def_reserved[k], W_RESERVED);
  302.       for (k = 0;  k < Res_count;  k++) 
  303.          LookUp (Reserved[k],W_RESERVED);
  304.  
  305.       if (NULL == (Table = fopen (Name,"r"))) return;
  306.       while (EOF != (L = fscanf (Table,"%d %d %s",&k,&Class,S))) 
  307.      if (L != 3 || k &~HASHMASK || !W_Valid (Class))
  308.         fprintf (stderr,"hash8 table error\n"),
  309.         exit (1);
  310.          else Insert (k,S,Class);
  311.       fclose (Table); 
  312.       NewTab = 0;
  313.    }
  314.  
  315. /*
  316.  * WriteTab
  317.  *
  318.  * Write out the hash table
  319.  *
  320.  * In
  321.  *      Name = name of hash table file
  322.  */
  323. WriteTab (Name)
  324.    char *Name; 
  325.    { 
  326.       FILE *Table;
  327.       int i;
  328.  
  329.       if (NULL == (Table = fopen (Name,"w"))) 
  330.      fprintf (stderr,"hash8: can't open hash table file '%s'\n",Name),
  331.      exit (1);
  332.       for (i=0; i<HASHLIMIT; i++)
  333.          if (HashTab[i] != NULL && *HashTab[i] != W_RESERVED) 
  334.             fprintf (Table,"%d    %d    %s\n",i,*HashTab[i],HashTab[i]+1);
  335.       fclose (Table); 
  336.    }
  337.  
  338. main (argc,argv)
  339.    int argc; char *argv[];
  340.    {
  341.       register char **h;
  342.       int Mode;
  343.  
  344.       /*
  345.        * Set up the reserved-word list.
  346.        */
  347.       while (argc > 3  &&  argv[1][0] == '-'  &&  argv[1][1] == 'r') {
  348.      argv[1] += 2;
  349.      if (argv[1][0] == '\0') {
  350.         argc--;
  351.         argv++;
  352.      }
  353.      if (Res_count == Res_max) {
  354.         Res_max += 5;
  355.         if (Reserved == NULL)
  356.            Reserved = (char **) malloc (5 * sizeof (char *));
  357.         else
  358.            Reserved = (char **)
  359.             realloc ((char *) Reserved, Res_max * sizeof (char *));
  360.      }
  361.      Reserved[Res_count] = argv[1];
  362.      Res_count++;
  363.      argc--;
  364.      argv++;
  365.       }
  366.       if (argc != 3) {
  367.          fprintf (stderr,
  368.            "usage: hash8 [-r reserved] ... (encode|[_]decode) table\n");
  369.          exit (1);
  370.       }
  371.  
  372.       /*
  373.        * If either stdin or stdout is a tty, set both unbuffered, for use
  374.        * in pipes.
  375.        * Geoff Kuenning, 11/8/86
  376.        */
  377.       if (isatty (fileno (stdin))  ||  isatty (fileno (stdout))) {
  378.      setbuf (stdin, NULL);
  379.      setbuf (stdout, NULL);
  380.       }
  381.       HashTab = (char **) malloc ((sizeof (char*)) * (HASHLIMIT));
  382.       for (h = HashTab+HASHLIMIT; --h > HashTab; ) *h = NULL;
  383.      
  384.       ReadTab(argv[2]); 
  385.       
  386.       if (!strcmp (argv[1],"encode")) Mode = ENCODE;
  387.       else if (!strcmp (argv[1],"decode")) Mode = DECODE; 
  388.       else if (!strcmp (argv[1],"_decode")) Mode = _DECODE; 
  389.       else
  390.          fprintf (stderr,"hash8: second arg must be 'encode' or 'decode'\n"),
  391.      exit (1);
  392.  
  393.       Translate (Mode);
  394.       if (NewTab) WriteTab(argv[2]);
  395.    }
  396.  
  397.