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
inst_keywords()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
install(keyptr,data)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
lookup()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
printchain(hashval)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
statistics()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 }
220