compilers/linux86-0.16.17/as/table.c

   1 /* table.c - keyword tables and symbol table lookup for assembler */
   2
   3 #include "syshead.h"
   4 #include "const.h"
   5 #include "type.h"
   6 #include "globvar.h"
   7 #include "opcode.h"
   8 #include "scan.h"
   9
  10 #define hconv(ch) ((unsigned char) (ch) - 0x41) /* better form for hashing */
  11
  12 #ifdef I80386
  13 # ifdef MNSIZE
  14 EXTERN char bytesizeops[];
  15 # endif
  16 #endif
  17 EXTERN char ops[];
  18 EXTERN char page1ops[];
  19 EXTERN char page2ops[];
  20 EXTERN char regs[];
  21 #ifdef I80386
  22 EXTERN char typesizes[];
  23 #endif
  24
  25 #ifdef DEBUG_HASH
  26 unsigned nhash;
  27 unsigned nlookup;
  28 unsigned nsym;
  29 unsigned nx[30];
  30 FORWARD void printchain P((void));
  31 #endif
  32
  33 FORWARD void install P((register char *keyptr, int data));
  34
  35 PUBLIC void inst_keywords()
  36 {
  37     install(regs, REGBIT);
  38 #ifdef I80386
  39     install(typesizes, SIZEBIT);
  40 #endif
  41     install(ops, 0);
  42     install(page1ops, PAGE1);
  43     install(page2ops, PAGE2);
  44 #ifdef I80386
  45 # ifdef MNSIZE
  46     install(bytesizeops, PAGE1 | PAGE2);
  47 # endif
  48 #endif
  49 }
  50
  51 PRIVATE void install(keyptr, data)
  52 register char *keyptr;
  53 unsigned char data;
  54 {
  55     char lowcasebuf[20];
  56     unsigned namelength;
  57     char *nameptr;
  58     char *namend;
  59     register struct sym_s *symptr;
  60
  61     while (*keyptr != 0)
  62     {
  63         namelength = *keyptr++;
  64         lineptr = (symname = keyptr) + namelength;
  65         for (nameptr = lowcasebuf, namend = lowcasebuf + namelength;
  66              nameptr < namend;)
  67         {
  68             if (*keyptr < 'A' || *keyptr > 'Z')
  69                 *nameptr++ = *keyptr++;
  70             else
  71                 *nameptr++ = *keyptr++ + ('a' - 'A');
  72         }
  73         symptr = lookup();
  74         symptr->type = MNREGBIT;
  75         symptr->data = data;
  76         symptr->value_reg_or_op.op.routine = *keyptr;
  77         symptr->value_reg_or_op.op.opcode = keyptr[1];
  78         lineptr = (symname = lowcasebuf) + namelength;
  79         symptr = lookup();
  80         symptr->type = MNREGBIT;
  81         symptr->data = data;
  82         symptr->value_reg_or_op.op.routine = *keyptr;
  83         symptr->value_reg_or_op.op.opcode = keyptr[1];
  84         keyptr += 2;
  85     }
  86 }
  87
  88 /* Lookup() searches symbol table for the string from symname to lineptr - 1.
  89  * If string is not found and ifflag is TRUE, string is added to table, with
  90  *      type = 0
  91  *      data = inidata (RELBIT | UNDBIT, possibly with IMPBIT | SEGM)
  92  * Returns pointer to symbol entry (NUL_PTR if not found and not installed)
  93  * unless symbol table overflows, when routine aborts.
  94  */
  95
  96 PUBLIC struct sym_s *lookup()
  97 {
  98     struct sym_s **hashptr;
  99     register char *nameptr;
 100     register struct sym_s *symptr;
 101     register unsigned hashval;
 102     register unsigned length;
 103 #ifdef DEBUG_HASH
 104     int tries;
 105
 106     ++nlookup;
 107     tries = 0;
 108 #endif
 109
 110     /* Hash function is a weighted xor of 1 to 4 chars in the string.
 111      * This works seems to work better than looking at all the chars.
 112      * It is important that the function be fast.
 113      * The string comparision function should also be fast and it helps
 114      * if it is optimized for mostly identical comparisions.
 115      * The multiplication by MULTIPLIER should compile as a shift.
 116      */
 117
 118 #define MULTIPLIER (SPTSIZ / (1 << USEFUL_BITS_IN_ASCII))
 119 #define USEFUL_BITS_IN_ASCII 6
 120
 121     nameptr = lineptr;
 122     length = nameptr - symname;
 123     if (length <= 3)
 124     {
 125         if (length <= 2)
 126             hashval  = hconv(nameptr[-1]) * MULTIPLIER;
 127         else
 128             hashval  = hconv(nameptr[-2]) * MULTIPLIER,
 129             hashval ^= hconv(nameptr[-1]);
 130     }
 131     else
 132         hashval  = hconv(symname[length-(length / 2)]) * MULTIPLIER,
 133         hashval ^= hconv(nameptr[-2]) << 2,
 134         hashval ^= hconv(nameptr[-1]);
 135     nameptr = symname;
 136     if ((symptr = *(hashptr = spt +
 137                               (hashval ^ (hconv(nameptr[0]) << 1)) % SPTSIZ))
 138         != NUL_PTR)
 139     {
 140         do
 141         {
 142 #ifdef DEBUG_HASH
 143             if (tries != 0)
 144                 --nx[tries];
 145             ++tries;
 146             if (tries < sizeof nx / sizeof nx[0])
 147                 ++nx[tries];
 148             if (tries >= 5)
 149                 printchain(hashptr - spt);
 150 #endif
 151             if ((unsigned char) length != symptr->length)
 152                 continue;
 153             if (memcmp(symptr->name, nameptr, length) == 0)
 154                 return symptr;
 155         }
 156         while ((symptr = symptr->next) != NUL_PTR);
 157
 158         /* Calculate last non-NUL_PTR hash ptr.
 159          * This is faster than keeping hashptr up to date in previous loop
 160          * since most lookups are successful and hash ptr is not needed.
 161          */
 162         do
 163         {
 164             symptr = *hashptr;
 165             hashptr = &symptr->next;
 166         }
 167         while (symptr->next != NUL_PTR);
 168     }
 169     if (!ifflag)
 170         return NUL_PTR;
 171 #ifdef DEBUG_HASH
 172     ++nsym;
 173     if (hashptr >= spt && hashptr < spt + SPTSIZ)
 174         ++nhash;
 175 #endif
 176     *hashptr = symptr = asalloc(sizeof(struct sym_s) + length);
 177     symptr->type = 0;
 178     symptr->data = inidata;
 179     symptr->length = length;
 180     symptr->value_reg_or_op.value = (offset_t) (symptr->next = NUL_PTR);
 181     memcpy(symptr->name, nameptr, length);
 182     symptr->name[length] = 0;
 183     return symptr;
 184 }
 185
 186 #ifdef DEBUG_HASH
 187
 188 static void printchain(hashval)
 189 unsigned hashval;
 190 {
 191     register struct sym_s *symptr;
 192
 193     printf("%04x ", hashval);
 194     for (symptr = spt[hashval]; symptr != NUL_PTR; symptr = symptr->next)
 195         printf("%s ", symptr->name);
 196     printf("\n");
 197 }
 198
 199 #endif
 200
 201 PUBLIC void statistics()
 202 {
 203 #ifdef DEBUG_HASH
 204     int i;
 205     int weight;
 206
 207     for (i = 0; i < SPTSIZ; ++i)
 208         printchain(i);
 209     printf("nhash = %d, nsym = %d, nlookup = %d nx =\n", nhash, nsym, nlookup);
 210     weight = 0;
 211     for (i = 0; i < 30; ++i)
 212     {
 213         printf("%5d", nx[i]);
 214         weight += nx[i] * i;
 215     }
 216     printf("\n");
 217     printf("weight = %d%d\n", weight);
 218 #endif
 219 }