Line data Source code
1 : %{
2 : /* Parser for i386 CPU description.
3 : Copyright (C) 2004, 2005, 2007, 2008, 2009 Red Hat, Inc.
4 : Written by Ulrich Drepper <drepper@redhat.com>, 2004.
5 :
6 : This file is free software; you can redistribute it and/or modify
7 : it under the terms of either
8 :
9 : * the GNU Lesser General Public License as published by the Free
10 : Software Foundation; either version 3 of the License, or (at
11 : your option) any later version
12 :
13 : or
14 :
15 : * the GNU General Public License as published by the Free
16 : Software Foundation; either version 2 of the License, or (at
17 : your option) any later version
18 :
19 : or both in parallel, as here.
20 :
21 : elfutils is distributed in the hope that it will be useful, but
22 : WITHOUT ANY WARRANTY; without even the implied warranty of
23 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
24 : General Public License for more details.
25 :
26 : You should have received copies of the GNU General Public License and
27 : the GNU Lesser General Public License along with this program. If
28 : not, see <http://www.gnu.org/licenses/>. */
29 :
30 : #ifdef HAVE_CONFIG_H
31 : # include <config.h>
32 : #endif
33 :
34 : #include <assert.h>
35 : #include <ctype.h>
36 : #include <errno.h>
37 : #include <error.h>
38 : #include <inttypes.h>
39 : #include <libintl.h>
40 : #include <math.h>
41 : #include <obstack.h>
42 : #include <search.h>
43 : #include <stdbool.h>
44 : #include <stdio.h>
45 : #include <stdlib.h>
46 : #include <string.h>
47 :
48 : #include <libeu.h>
49 : #include <system.h>
50 :
51 : #define obstack_chunk_alloc xmalloc
52 : #define obstack_chunk_free free
53 :
54 : /* The error handler. */
55 : static void yyerror (const char *s);
56 :
57 : extern int yylex (void);
58 : extern int i386_lineno;
59 : extern char *infname;
60 :
61 :
62 : struct known_bitfield
63 : {
64 : char *name;
65 : unsigned long int bits;
66 : int tmp;
67 : };
68 :
69 :
70 : struct bitvalue
71 : {
72 : enum bittype { zeroone, field, failure } type;
73 : union
74 : {
75 : unsigned int value;
76 : struct known_bitfield *field;
77 : };
78 : struct bitvalue *next;
79 : };
80 :
81 :
82 : struct argname
83 : {
84 : enum nametype { string, nfield } type;
85 : union
86 : {
87 : char *str;
88 : struct known_bitfield *field;
89 : };
90 : struct argname *next;
91 : };
92 :
93 :
94 : struct argument
95 : {
96 : struct argname *name;
97 : struct argument *next;
98 : };
99 :
100 :
101 : struct instruction
102 : {
103 : /* The byte encoding. */
104 : struct bitvalue *bytes;
105 :
106 : /* Prefix possible. */
107 : int repe;
108 : int rep;
109 :
110 : /* Mnemonic. */
111 : char *mnemonic;
112 :
113 : /* Suffix. */
114 : enum { suffix_none = 0, suffix_w, suffix_w0, suffix_W, suffix_tttn,
115 : suffix_w1, suffix_W1, suffix_D } suffix;
116 :
117 : /* Flag set if modr/m is used. */
118 : int modrm;
119 :
120 : /* Operands. */
121 : struct operand
122 : {
123 : char *fct;
124 : char *str;
125 : int off1;
126 : int off2;
127 : int off3;
128 : } operands[3];
129 :
130 : struct instruction *next;
131 : };
132 :
133 :
134 : struct synonym
135 : {
136 : char *from;
137 : char *to;
138 : };
139 :
140 :
141 : struct suffix
142 : {
143 : char *name;
144 : int idx;
145 : };
146 :
147 :
148 : struct argstring
149 : {
150 : char *str;
151 : int idx;
152 : int off;
153 : };
154 :
155 :
156 : static struct known_bitfield ax_reg =
157 : {
158 : .name = "ax", .bits = 0, .tmp = 0
159 : };
160 :
161 : static struct known_bitfield dx_reg =
162 : {
163 : .name = "dx", .bits = 0, .tmp = 0
164 : };
165 :
166 : static struct known_bitfield di_reg =
167 : {
168 : .name = "es_di", .bits = 0, .tmp = 0
169 : };
170 :
171 : static struct known_bitfield si_reg =
172 : {
173 : .name = "ds_si", .bits = 0, .tmp = 0
174 : };
175 :
176 : static struct known_bitfield bx_reg =
177 : {
178 : .name = "ds_bx", .bits = 0, .tmp = 0
179 : };
180 :
181 :
182 : static int bitfield_compare (const void *p1, const void *p2);
183 : static void new_bitfield (char *name, unsigned long int num);
184 : static void check_bits (struct bitvalue *value);
185 : static int check_duplicates (struct bitvalue *val);
186 : static int check_argsdef (struct bitvalue *bitval, struct argument *args);
187 : static int check_bitsused (struct bitvalue *bitval,
188 : struct known_bitfield *suffix,
189 : struct argument *args);
190 : static struct argname *combine (struct argname *name);
191 : static void fillin_arg (struct bitvalue *bytes, struct argname *name,
192 : struct instruction *instr, int n);
193 : static void find_numbers (void);
194 : static int compare_syn (const void *p1, const void *p2);
195 : static int compare_suf (const void *p1, const void *p2);
196 : static void instrtable_out (void);
197 : #if 0
198 : static void create_mnemonic_table (void);
199 : #endif
200 :
201 : static void *bitfields;
202 : static struct instruction *instructions;
203 : static size_t ninstructions;
204 : static void *synonyms;
205 : static void *suffixes;
206 : static int nsuffixes;
207 : static void *mnemonics;
208 : size_t nmnemonics;
209 : extern FILE *outfile;
210 :
211 : /* Number of bits used mnemonics. */
212 : #if 0
213 : static size_t best_mnemonic_bits;
214 : #endif
215 : %}
216 :
217 : %union {
218 : unsigned long int num;
219 : char *str;
220 : char ch;
221 : struct known_bitfield *field;
222 : struct bitvalue *bit;
223 : struct argname *name;
224 : struct argument *arg;
225 : }
226 :
227 : %token kMASK
228 : %token kPREFIX
229 : %token kSUFFIX
230 : %token kSYNONYM
231 : %token <str> kID
232 : %token <num> kNUMBER
233 : %token kPERCPERC
234 : %token <str> kBITFIELD
235 : %token <ch> kCHAR
236 : %token kSPACE
237 :
238 : %type <bit> bit byte bytes
239 : %type <field> bitfieldopt
240 : %type <name> argcomp arg
241 : %type <arg> args optargs
242 :
243 : %defines
244 :
245 : %%
246 :
247 : spec: masks kPERCPERC '\n' instrs
248 : {
249 2 : if (error_message_count != 0)
250 : error (EXIT_FAILURE, 0,
251 : "terminated due to previous error");
252 :
253 2 : instrtable_out ();
254 : }
255 : ;
256 :
257 : masks: masks '\n' mask
258 : | mask
259 : ;
260 :
261 : mask: kMASK kBITFIELD kNUMBER
262 94 : { new_bitfield ($2, $3); }
263 : | kPREFIX kBITFIELD
264 4 : { new_bitfield ($2, -1); }
265 : | kSUFFIX kBITFIELD
266 4 : { new_bitfield ($2, -2); }
267 : | kSYNONYM kBITFIELD kBITFIELD
268 : {
269 10 : struct synonym *newp = xmalloc (sizeof (*newp));
270 10 : newp->from = $2;
271 10 : newp->to = $3;
272 10 : if (tfind (newp, &synonyms, compare_syn) != NULL)
273 0 : error (0, 0,
274 : "%d: duplicate definition for synonym '%s'",
275 : i386_lineno, $2);
276 10 : else if (tsearch ( newp, &synonyms, compare_syn) == NULL)
277 : error (EXIT_FAILURE, 0, "tsearch");
278 : }
279 : |
280 : ;
281 :
282 : instrs: instrs '\n' instr
283 : | instr
284 : ;
285 :
286 : instr: bytes ':' bitfieldopt kID bitfieldopt optargs
287 : {
288 1501 : if ($3 != NULL && strcmp ($3->name, "RE") != 0
289 10 : && strcmp ($3->name, "R") != 0)
290 : {
291 0 : error (0, 0, "%d: only 'R' and 'RE' prefix allowed",
292 : i386_lineno - 1);
293 : }
294 1501 : if (check_duplicates ($1) == 0
295 1501 : && check_argsdef ($1, $6) == 0
296 1501 : && check_bitsused ($1, $5, $6) == 0)
297 : {
298 1501 : struct instruction *newp = xcalloc (sizeof (*newp),
299 : 1);
300 1501 : if ($3 != NULL)
301 : {
302 14 : if (strcmp ($3->name, "RE") == 0)
303 4 : newp->repe = 1;
304 10 : else if (strcmp ($3->name, "R") == 0)
305 10 : newp->rep = 1;
306 : }
307 :
308 1501 : newp->bytes = $1;
309 1501 : newp->mnemonic = $4;
310 1501 : if (newp->mnemonic != (void *) -1l
311 1483 : && tfind ($4, &mnemonics,
312 : (int (*)(const void *, const void *)) strcmp) == NULL)
313 : {
314 1018 : if (tsearch ($4, &mnemonics,
315 : (int (*)(const void *, const void *)) strcmp) == NULL)
316 0 : error (EXIT_FAILURE, errno, "tsearch");
317 1018 : ++nmnemonics;
318 : }
319 :
320 1501 : if ($5 != NULL)
321 : {
322 201 : if (strcmp ($5->name, "w") == 0)
323 114 : newp->suffix = suffix_w;
324 87 : else if (strcmp ($5->name, "w0") == 0)
325 2 : newp->suffix = suffix_w0;
326 85 : else if (strcmp ($5->name, "tttn") == 0)
327 10 : newp->suffix = suffix_tttn;
328 75 : else if (strcmp ($5->name, "w1") == 0)
329 18 : newp->suffix = suffix_w1;
330 57 : else if (strcmp ($5->name, "W") == 0)
331 33 : newp->suffix = suffix_W;
332 24 : else if (strcmp ($5->name, "W1") == 0)
333 2 : newp->suffix = suffix_W1;
334 22 : else if (strcmp ($5->name, "D") == 0)
335 22 : newp->suffix = suffix_D;
336 : else
337 0 : error (EXIT_FAILURE, 0,
338 : "%s: %d: unknown suffix '%s'",
339 : infname, i386_lineno - 1, $5->name);
340 :
341 201 : struct suffix search = { .name = $5->name };
342 201 : if (tfind (&search, &suffixes, compare_suf)
343 : == NULL)
344 : {
345 13 : struct suffix *ns = xmalloc (sizeof (*ns));
346 13 : ns->name = $5->name;
347 13 : ns->idx = ++nsuffixes;
348 13 : if (tsearch (ns, &suffixes, compare_suf)
349 : == NULL)
350 0 : error (EXIT_FAILURE, errno, "tsearch");
351 : }
352 : }
353 :
354 1501 : struct argument *args = $6;
355 1501 : int n = 0;
356 5466 : while (args != NULL)
357 : {
358 2464 : fillin_arg ($1, args->name, newp, n);
359 :
360 2464 : args = args->next;
361 2464 : ++n;
362 : }
363 :
364 1501 : newp->next = instructions;
365 1501 : instructions = newp;
366 1501 : ++ninstructions;
367 : }
368 : }
369 : |
370 : ;
371 :
372 : bitfieldopt: kBITFIELD
373 : {
374 : struct known_bitfield search;
375 215 : search.name = $1;
376 : struct known_bitfield **res;
377 215 : res = tfind (&search, &bitfields, bitfield_compare);
378 215 : if (res == NULL)
379 : {
380 0 : error (0, 0, "%d: unknown bitfield '%s'",
381 : i386_lineno, search.name);
382 0 : $$ = NULL;
383 : }
384 : else
385 215 : $$ = *res;
386 : }
387 : |
388 2787 : { $$ = NULL; }
389 : ;
390 :
391 : bytes: bytes ',' byte
392 : {
393 3175 : check_bits ($3);
394 :
395 3175 : struct bitvalue *runp = $1;
396 3175 : while (runp->next != NULL)
397 : runp = runp->next;
398 3175 : runp->next = $3;
399 3175 : $$ = $1;
400 : }
401 : | byte
402 : {
403 1501 : check_bits ($1);
404 1501 : $$ = $1;
405 : }
406 : ;
407 :
408 : byte: byte bit
409 : {
410 25897 : struct bitvalue *runp = $1;
411 25897 : while (runp->next != NULL)
412 : runp = runp->next;
413 25897 : runp->next = $2;
414 25897 : $$ = $1;
415 : }
416 : | bit
417 4676 : { $$ = $1; }
418 : ;
419 :
420 : bit: '0'
421 : {
422 13145 : $$ = xmalloc (sizeof (struct bitvalue));
423 13145 : $$->type = zeroone;
424 13145 : $$->value = 0;
425 13145 : $$->next = NULL;
426 : }
427 : | '1'
428 : {
429 13839 : $$ = xmalloc (sizeof (struct bitvalue));
430 13839 : $$->type = zeroone;
431 13839 : $$->value = 1;
432 13839 : $$->next = NULL;
433 : }
434 : | kBITFIELD
435 : {
436 3589 : $$ = xmalloc (sizeof (struct bitvalue));
437 : struct known_bitfield search;
438 3589 : search.name = $1;
439 : struct known_bitfield **res;
440 3589 : res = tfind (&search, &bitfields, bitfield_compare);
441 3589 : if (res == NULL)
442 : {
443 0 : error (0, 0, "%d: unknown bitfield '%s'",
444 : i386_lineno, search.name);
445 0 : $$->type = failure;
446 : }
447 : else
448 : {
449 3589 : $$->type = field;
450 3589 : $$->field = *res;
451 : }
452 3589 : $$->next = NULL;
453 : }
454 : ;
455 :
456 : optargs: kSPACE args
457 1322 : { $$ = $2; }
458 : |
459 179 : { $$ = NULL; }
460 : ;
461 :
462 : args: args ',' arg
463 : {
464 1142 : struct argument *runp = $1;
465 1142 : while (runp->next != NULL)
466 : runp = runp->next;
467 1142 : runp->next = xmalloc (sizeof (struct argument));
468 1142 : runp->next->name = combine ($3);
469 1142 : runp->next->next = NULL;
470 1142 : $$ = $1;
471 : }
472 : | arg
473 : {
474 1322 : $$ = xmalloc (sizeof (struct argument));
475 1322 : $$->name = combine ($1);
476 1322 : $$->next = NULL;
477 : }
478 : ;
479 :
480 : arg: arg argcomp
481 : {
482 1413 : struct argname *runp = $1;
483 1413 : while (runp->next != NULL)
484 : runp = runp->next;
485 1413 : runp->next = $2;
486 1413 : $$ = $1;
487 : }
488 : | argcomp
489 2464 : { $$ = $1; }
490 : ;
491 : argcomp: kBITFIELD
492 : {
493 3661 : $$ = xmalloc (sizeof (struct argname));
494 3661 : $$->type = nfield;
495 3661 : $$->next = NULL;
496 :
497 : struct known_bitfield search;
498 3661 : search.name = $1;
499 : struct known_bitfield **res;
500 3661 : res = tfind (&search, &bitfields, bitfield_compare);
501 3661 : if (res == NULL)
502 : {
503 66 : if (strcmp ($1, "ax") == 0)
504 38 : $$->field = &ax_reg;
505 28 : else if (strcmp ($1, "dx") == 0)
506 8 : $$->field = &dx_reg;
507 20 : else if (strcmp ($1, "es_di") == 0)
508 10 : $$->field = &di_reg;
509 10 : else if (strcmp ($1, "ds_si") == 0)
510 8 : $$->field = &si_reg;
511 2 : else if (strcmp ($1, "ds_bx") == 0)
512 2 : $$->field = &bx_reg;
513 : else
514 : {
515 0 : error (0, 0, "%d: unknown bitfield '%s'",
516 : i386_lineno, search.name);
517 0 : $$->field = NULL;
518 : }
519 : }
520 : else
521 3595 : $$->field = *res;
522 : }
523 : | kCHAR
524 : {
525 112 : $$ = xmalloc (sizeof (struct argname));
526 112 : $$->type = string;
527 112 : $$->next = NULL;
528 112 : $$->str = xmalloc (2);
529 112 : $$->str[0] = $1;
530 112 : $$->str[1] = '\0';
531 : }
532 : | kID
533 : {
534 104 : $$ = xmalloc (sizeof (struct argname));
535 104 : $$->type = string;
536 104 : $$->next = NULL;
537 104 : $$->str = $1;
538 : }
539 : | ':'
540 : {
541 0 : $$ = xmalloc (sizeof (struct argname));
542 0 : $$->type = string;
543 0 : $$->next = NULL;
544 0 : $$->str = xmalloc (2);
545 0 : $$->str[0] = ':';
546 0 : $$->str[1] = '\0';
547 : }
548 : ;
549 :
550 : %%
551 :
552 : static void
553 0 : yyerror (const char *s)
554 : {
555 0 : error (0, 0, gettext ("while reading i386 CPU description: %s at line %d"),
556 : gettext (s), i386_lineno);
557 0 : }
558 :
559 :
560 : static int
561 39235 : bitfield_compare (const void *p1, const void *p2)
562 : {
563 39235 : struct known_bitfield *f1 = (struct known_bitfield *) p1;
564 39235 : struct known_bitfield *f2 = (struct known_bitfield *) p2;
565 :
566 39235 : return strcmp (f1->name, f2->name);
567 : }
568 :
569 :
570 : static void
571 102 : new_bitfield (char *name, unsigned long int num)
572 : {
573 102 : struct known_bitfield *newp = xmalloc (sizeof (struct known_bitfield));
574 102 : newp->name = name;
575 102 : newp->bits = num;
576 102 : newp->tmp = 0;
577 :
578 102 : if (tfind (newp, &bitfields, bitfield_compare) != NULL)
579 : {
580 0 : error (0, 0, "%d: duplicated definition of bitfield '%s'",
581 : i386_lineno, name);
582 0 : free (name);
583 102 : return;
584 : }
585 :
586 102 : if (tsearch (newp, &bitfields, bitfield_compare) == NULL)
587 0 : error (EXIT_FAILURE, errno, "%d: cannot insert new bitfield '%s'",
588 : i386_lineno, name);
589 : }
590 :
591 :
592 : /* Check that the number of bits is a multiple of 8. */
593 : static void
594 4676 : check_bits (struct bitvalue *val)
595 : {
596 4676 : struct bitvalue *runp = val;
597 4676 : unsigned int total = 0;
598 :
599 39925 : while (runp != NULL)
600 : {
601 30573 : if (runp->type == zeroone)
602 26984 : ++total;
603 3589 : else if (runp->field == NULL)
604 : /* No sense doing anything, the field is not known. */
605 4676 : return;
606 : else
607 3589 : total += runp->field->bits;
608 :
609 30573 : runp = runp->next;
610 : }
611 :
612 4676 : if (total % 8 != 0)
613 : {
614 : struct obstack os;
615 0 : obstack_init (&os);
616 :
617 0 : while (val != NULL)
618 : {
619 0 : if (val->type == zeroone)
620 0 : obstack_printf (&os, "%u", val->value);
621 : else
622 0 : obstack_printf (&os, "{%s}", val->field->name);
623 0 : val = val->next;
624 : }
625 0 : obstack_1grow (&os, '\0');
626 :
627 0 : error (0, 0, "%d: field '%s' not a multiple of 8 bits in size",
628 0 : i386_lineno, (char *) obstack_finish (&os));
629 :
630 0 : obstack_free (&os, NULL);
631 : }
632 : }
633 :
634 :
635 : static int
636 1501 : check_duplicates (struct bitvalue *val)
637 : {
638 : static int testcnt;
639 1501 : ++testcnt;
640 :
641 1501 : int result = 0;
642 33575 : while (val != NULL)
643 : {
644 30573 : if (val->type == field && val->field != NULL)
645 : {
646 3589 : if (val->field->tmp == testcnt)
647 : {
648 0 : error (0, 0, "%d: bitfield '%s' used more than once",
649 : i386_lineno - 1, val->field->name);
650 0 : result = 1;
651 : }
652 3589 : val->field->tmp = testcnt;
653 : }
654 :
655 30573 : val = val->next;
656 : }
657 :
658 1501 : return result;
659 : }
660 :
661 :
662 : static int
663 1501 : check_argsdef (struct bitvalue *bitval, struct argument *args)
664 : {
665 1501 : int result = 0;
666 :
667 5466 : while (args != NULL)
668 : {
669 6237 : for (struct argname *name = args->name; name != NULL; name = name->next)
670 3773 : if (name->type == nfield && name->field != NULL
671 3661 : && name->field != &ax_reg && name->field != &dx_reg
672 3615 : && name->field != &di_reg && name->field != &si_reg
673 3597 : && name->field != &bx_reg)
674 : {
675 : struct bitvalue *runp = bitval;
676 :
677 73449 : while (runp != NULL)
678 73449 : if (runp->type == field && runp->field == name->field)
679 : break;
680 : else
681 69854 : runp = runp->next;
682 :
683 3595 : if (runp == NULL)
684 : {
685 0 : error (0, 0, "%d: unknown bitfield '%s' used in output format",
686 : i386_lineno - 1, name->field->name);
687 0 : result = 1;
688 : }
689 : }
690 :
691 2464 : args = args->next;
692 : }
693 :
694 1501 : return result;
695 : }
696 :
697 :
698 : static int
699 1501 : check_bitsused (struct bitvalue *bitval, struct known_bitfield *suffix,
700 : struct argument *args)
701 : {
702 1501 : int result = 0;
703 :
704 33575 : while (bitval != NULL)
705 : {
706 30573 : if (bitval->type == field && bitval->field != NULL
707 3589 : && bitval->field != suffix
708 : /* {w} is handled special. */
709 3441 : && strcmp (bitval->field->name, "w") != 0)
710 : {
711 : struct argument *runp;
712 1378 : for (runp = args; runp != NULL; runp = runp->next)
713 : {
714 4727 : struct argname *name = runp->name;
715 :
716 12738 : while (name != NULL)
717 6633 : if (name->type == nfield && name->field == bitval->field)
718 : break;
719 : else
720 3284 : name = name->next;
721 :
722 4727 : if (name != NULL)
723 : break;
724 : }
725 :
726 : #if 0
727 : if (runp == NULL)
728 : {
729 : error (0, 0, "%d: bitfield '%s' not used",
730 : i386_lineno - 1, bitval->field->name);
731 : result = 1;
732 : }
733 : #endif
734 : }
735 :
736 30573 : bitval = bitval->next;
737 : }
738 :
739 1501 : return result;
740 : }
741 :
742 :
743 : static struct argname *
744 2464 : combine (struct argname *name)
745 : {
746 2464 : struct argname *last_str = NULL;
747 6341 : for (struct argname *runp = name; runp != NULL; runp = runp->next)
748 : {
749 3877 : if (runp->type == string)
750 : {
751 216 : if (last_str == NULL)
752 : last_str = runp;
753 : else
754 : {
755 104 : last_str->str = xrealloc (last_str->str,
756 104 : strlen (last_str->str)
757 104 : + strlen (runp->str) + 1);
758 104 : strcat (last_str->str, runp->str);
759 104 : last_str->next = runp->next;
760 : }
761 : }
762 : else
763 : last_str = NULL;
764 : }
765 2464 : return name;
766 : }
767 :
768 :
769 : #define obstack_grow_str(ob, str) obstack_grow (ob, str, strlen (str))
770 :
771 :
772 : static void
773 2464 : fillin_arg (struct bitvalue *bytes, struct argname *name,
774 : struct instruction *instr, int n)
775 : {
776 : static struct obstack ob;
777 : static int initialized;
778 2464 : if (! initialized)
779 : {
780 2 : initialized = 1;
781 2 : obstack_init (&ob);
782 : }
783 :
784 2464 : struct argname *runp = name;
785 2464 : int cnt = 0;
786 8701 : while (runp != NULL)
787 : {
788 : /* We ignore strings in the function name. */
789 3773 : if (runp->type == string)
790 : {
791 112 : if (instr->operands[n].str != NULL)
792 0 : error (EXIT_FAILURE, 0,
793 : "%d: cannot have more than one string parameter",
794 : i386_lineno - 1);
795 :
796 112 : instr->operands[n].str = runp->str;
797 : }
798 : else
799 : {
800 3661 : assert (runp->type == nfield);
801 :
802 : /* Construct the function name. */
803 3661 : if (cnt++ > 0)
804 1301 : obstack_1grow (&ob, '$');
805 :
806 3661 : if (runp->field == NULL)
807 : /* Add some string which contains invalid characters. */
808 0 : obstack_grow_str (&ob, "!!!INVALID!!!");
809 : else
810 : {
811 3661 : char *fieldname = runp->field->name;
812 :
813 3661 : struct synonym search = { .from = fieldname };
814 :
815 3661 : struct synonym **res = tfind (&search, &synonyms, compare_syn);
816 3661 : if (res != NULL)
817 35 : fieldname = (*res)->to;
818 :
819 7322 : obstack_grow_str (&ob, fieldname);
820 : }
821 :
822 : /* Now compute the bit offset of the field. */
823 3661 : struct bitvalue *b = bytes;
824 3661 : int bitoff = 0;
825 3661 : if (runp->field != NULL)
826 74065 : while (b != NULL)
827 : {
828 73999 : if (b->type == field && b->field != NULL)
829 : {
830 7207 : if (strcmp (b->field->name, runp->field->name) == 0)
831 : break;
832 3612 : bitoff += b->field->bits;
833 : }
834 : else
835 66792 : ++bitoff;
836 :
837 70404 : b = b->next;
838 : }
839 3661 : if (instr->operands[n].off1 == 0)
840 2360 : instr->operands[n].off1 = bitoff;
841 1301 : else if (instr->operands[n].off2 == 0)
842 1177 : instr->operands[n].off2 = bitoff;
843 124 : else if (instr->operands[n].off3 == 0)
844 124 : instr->operands[n].off3 = bitoff;
845 : else
846 0 : error (EXIT_FAILURE, 0,
847 : "%d: cannot have more than three fields in parameter",
848 : i386_lineno - 1);
849 :
850 3661 : if (runp->field != NULL
851 3661 : && strncasecmp (runp->field->name, "mod", 3) == 0)
852 1051 : instr->modrm = 1;
853 : }
854 :
855 3773 : runp = runp->next;
856 : }
857 2464 : if (obstack_object_size (&ob) == 0)
858 208 : obstack_grow_str (&ob, "string");
859 2464 : obstack_1grow (&ob, '\0');
860 2464 : char *fct = obstack_finish (&ob);
861 :
862 2464 : instr->operands[n].fct = fct;
863 2464 : }
864 :
865 :
866 : #if 0
867 : static void
868 : nameout (const void *nodep, VISIT value, int level)
869 : {
870 : if (value == leaf || value == postorder)
871 : printf (" %s\n", *(const char **) nodep);
872 : }
873 : #endif
874 :
875 :
876 : static int
877 16303 : compare_argstring (const void *p1, const void *p2)
878 : {
879 16303 : const struct argstring *a1 = (const struct argstring *) p1;
880 16303 : const struct argstring *a2 = (const struct argstring *) p2;
881 :
882 16303 : return strcmp (a1->str, a2->str);
883 : }
884 :
885 :
886 : static int maxoff[3][3];
887 : static int minoff[3][3] = { { 1000, 1000, 1000 },
888 : { 1000, 1000, 1000 },
889 : { 1000, 1000, 1000 } };
890 : static int nbitoff[3][3];
891 : static void *fct_names[3];
892 : static int nbitfct[3];
893 : static int nbitsuf;
894 : static void *strs[3];
895 : static int nbitstr[3];
896 : static int total_bits = 2; // Already counted the rep/repe bits.
897 :
898 : static void
899 2 : find_numbers (void)
900 : {
901 2 : int nfct_names[3] = { 0, 0, 0 };
902 2 : int nstrs[3] = { 0, 0, 0 };
903 :
904 : /* We reverse the order of the instruction list while processing it.
905 : Later phases need it in the order in which the input file has
906 : them. */
907 2 : struct instruction *reversed = NULL;
908 :
909 2 : struct instruction *runp = instructions;
910 1505 : while (runp != NULL)
911 : {
912 4503 : for (int i = 0; i < 3; ++i)
913 4503 : if (runp->operands[i].fct != NULL)
914 : {
915 2464 : struct argstring search = { .str = runp->operands[i].fct };
916 2464 : if (tfind (&search, &fct_names[i], compare_argstring) == NULL)
917 : {
918 125 : struct argstring *newp = xmalloc (sizeof (*newp));
919 125 : newp->str = runp->operands[i].fct;
920 125 : newp->idx = 0;
921 125 : if (tsearch (newp, &fct_names[i], compare_argstring) == NULL)
922 0 : error (EXIT_FAILURE, errno, "tsearch");
923 125 : ++nfct_names[i];
924 : }
925 :
926 2464 : if (runp->operands[i].str != NULL)
927 : {
928 112 : search.str = runp->operands[i].str;
929 112 : if (tfind (&search, &strs[i], compare_argstring) == NULL)
930 : {
931 18 : struct argstring *newp = xmalloc (sizeof (*newp));
932 18 : newp->str = runp->operands[i].str;
933 18 : newp->idx = 0;
934 18 : if (tsearch (newp, &strs[i], compare_argstring) == NULL)
935 0 : error (EXIT_FAILURE, errno, "tsearch");
936 18 : ++nstrs[i];
937 : }
938 : }
939 :
940 2464 : maxoff[i][0] = MAX (maxoff[i][0], runp->operands[i].off1);
941 2464 : maxoff[i][1] = MAX (maxoff[i][1], runp->operands[i].off2);
942 2464 : maxoff[i][2] = MAX (maxoff[i][2], runp->operands[i].off3);
943 :
944 2464 : if (runp->operands[i].off1 > 0)
945 2360 : minoff[i][0] = MIN (minoff[i][0], runp->operands[i].off1);
946 2464 : if (runp->operands[i].off2 > 0)
947 1177 : minoff[i][1] = MIN (minoff[i][1], runp->operands[i].off2);
948 2464 : if (runp->operands[i].off3 > 0)
949 124 : minoff[i][2] = MIN (minoff[i][2], runp->operands[i].off3);
950 : }
951 :
952 1501 : struct instruction *old = runp;
953 1501 : runp = runp->next;
954 :
955 1501 : old->next = reversed;
956 1501 : reversed = old;
957 : }
958 2 : instructions = reversed;
959 :
960 : int d;
961 : int c;
962 8 : for (int i = 0; i < 3; ++i)
963 : {
964 : // printf ("min1 = %d, min2 = %d, min3 = %d\n", minoff[i][0], minoff[i][1], minoff[i][2]);
965 : // printf ("max1 = %d, max2 = %d, max3 = %d\n", maxoff[i][0], maxoff[i][1], maxoff[i][2]);
966 :
967 6 : if (minoff[i][0] == 1000)
968 0 : nbitoff[i][0] = 0;
969 : else
970 : {
971 6 : nbitoff[i][0] = 1;
972 6 : d = maxoff[i][0] - minoff[i][0];
973 6 : c = 1;
974 46 : while (c < d)
975 : {
976 34 : ++nbitoff[i][0];
977 34 : c *= 2;
978 : }
979 6 : total_bits += nbitoff[i][0];
980 : }
981 :
982 6 : if (minoff[i][1] == 1000)
983 0 : nbitoff[i][1] = 0;
984 : else
985 : {
986 6 : nbitoff[i][1] = 1;
987 6 : d = maxoff[i][1] - minoff[i][1];
988 6 : c = 1;
989 36 : while (c < d)
990 : {
991 24 : ++nbitoff[i][1];
992 24 : c *= 2;
993 : }
994 6 : total_bits += nbitoff[i][1];
995 : }
996 :
997 6 : if (minoff[i][2] == 1000)
998 2 : nbitoff[i][2] = 0;
999 : else
1000 : {
1001 4 : nbitoff[i][2] = 1;
1002 4 : d = maxoff[i][2] - minoff[i][2];
1003 4 : c = 1;
1004 14 : while (c < d)
1005 : {
1006 6 : ++nbitoff[i][2];
1007 6 : c *= 2;
1008 : }
1009 4 : total_bits += nbitoff[i][2];
1010 : }
1011 : // printf ("off1 = %d, off2 = %d, off3 = %d\n", nbitoff[i][0], nbitoff[i][1], nbitoff[i][2]);
1012 :
1013 6 : nbitfct[i] = 1;
1014 6 : d = nfct_names[i];
1015 6 : c = 1;
1016 40 : while (c < d)
1017 : {
1018 28 : ++nbitfct[i];
1019 28 : c *= 2;
1020 : }
1021 6 : total_bits += nbitfct[i];
1022 : // printf ("%d fct[%d], %d bits\n", nfct_names[i], i, nbitfct[i]);
1023 :
1024 6 : if (nstrs[i] != 0)
1025 : {
1026 6 : nbitstr[i] = 1;
1027 6 : d = nstrs[i];
1028 6 : c = 1;
1029 20 : while (c < d)
1030 : {
1031 8 : ++nbitstr[i];
1032 8 : c *= 2;
1033 : }
1034 6 : total_bits += nbitstr[i];
1035 : }
1036 :
1037 : // twalk (fct_names[i], nameout);
1038 : }
1039 :
1040 2 : nbitsuf = 0;
1041 2 : d = nsuffixes;
1042 2 : c = 1;
1043 10 : while (c < d)
1044 : {
1045 6 : ++nbitsuf;
1046 6 : c *= 2;
1047 : }
1048 2 : total_bits += nbitsuf;
1049 : // printf ("%d suffixes, %d bits\n", nsuffixes, nbitsuf);
1050 2 : }
1051 :
1052 :
1053 : static int
1054 10968 : compare_syn (const void *p1, const void *p2)
1055 : {
1056 10968 : const struct synonym *s1 = (const struct synonym *) p1;
1057 10968 : const struct synonym *s2 = (const struct synonym *) p2;
1058 :
1059 10968 : return strcmp (s1->from, s2->from);
1060 : }
1061 :
1062 :
1063 : static int
1064 467 : compare_suf (const void *p1, const void *p2)
1065 : {
1066 467 : const struct suffix *s1 = (const struct suffix *) p1;
1067 467 : const struct suffix *s2 = (const struct suffix *) p2;
1068 :
1069 467 : return strcmp (s1->name, s2->name);
1070 : }
1071 :
1072 :
1073 : static int count_op_str;
1074 : static int off_op_str;
1075 : static void
1076 34 : print_op_str (const void *nodep, VISIT value,
1077 : int level __attribute__ ((unused)))
1078 : {
1079 34 : if (value == leaf || value == postorder)
1080 : {
1081 18 : const char *str = (*(struct argstring **) nodep)->str;
1082 18 : fprintf (outfile, "%s\n \"%s",
1083 18 : count_op_str == 0 ? "" : "\\0\"", str);
1084 18 : (*(struct argstring **) nodep)->idx = ++count_op_str;
1085 18 : (*(struct argstring **) nodep)->off = off_op_str;
1086 18 : off_op_str += strlen (str) + 1;
1087 : }
1088 34 : }
1089 :
1090 :
1091 : static void
1092 34 : print_op_str_idx (const void *nodep, VISIT value,
1093 : int level __attribute__ ((unused)))
1094 : {
1095 34 : if (value == leaf || value == postorder)
1096 18 : printf (" %d,\n", (*(struct argstring **) nodep)->off);
1097 34 : }
1098 :
1099 :
1100 : static void
1101 265 : print_op_fct (const void *nodep, VISIT value,
1102 : int level __attribute__ ((unused)))
1103 : {
1104 265 : if (value == leaf || value == postorder)
1105 : {
1106 125 : fprintf (outfile, " FCT_%s,\n", (*(struct argstring **) nodep)->str);
1107 125 : (*(struct argstring **) nodep)->idx = ++count_op_str;
1108 : }
1109 265 : }
1110 :
1111 :
1112 : #if NMNES < 2
1113 : # error "bogus NMNES value"
1114 : #endif
1115 :
1116 : static void
1117 2 : instrtable_out (void)
1118 : {
1119 2 : find_numbers ();
1120 :
1121 : #if 0
1122 : create_mnemonic_table ();
1123 :
1124 : fprintf (outfile, "#define MNEMONIC_BITS %zu\n", best_mnemonic_bits);
1125 : #else
1126 2 : fprintf (outfile, "#define MNEMONIC_BITS %ld\n",
1127 : lrint (ceil (log2 (NMNES))));
1128 : #endif
1129 2 : fprintf (outfile, "#define SUFFIX_BITS %d\n", nbitsuf);
1130 8 : for (int i = 0; i < 3; ++i)
1131 : {
1132 6 : fprintf (outfile, "#define FCT%d_BITS %d\n", i + 1, nbitfct[i]);
1133 6 : if (nbitstr[i] != 0)
1134 6 : fprintf (outfile, "#define STR%d_BITS %d\n", i + 1, nbitstr[i]);
1135 6 : fprintf (outfile, "#define OFF%d_1_BITS %d\n", i + 1, nbitoff[i][0]);
1136 6 : fprintf (outfile, "#define OFF%d_1_BIAS %d\n", i + 1, minoff[i][0]);
1137 6 : if (nbitoff[i][1] != 0)
1138 : {
1139 6 : fprintf (outfile, "#define OFF%d_2_BITS %d\n", i + 1, nbitoff[i][1]);
1140 6 : fprintf (outfile, "#define OFF%d_2_BIAS %d\n", i + 1, minoff[i][1]);
1141 : }
1142 6 : if (nbitoff[i][2] != 0)
1143 : {
1144 4 : fprintf (outfile, "#define OFF%d_3_BITS %d\n", i + 1, nbitoff[i][2]);
1145 4 : fprintf (outfile, "#define OFF%d_3_BIAS %d\n", i + 1, minoff[i][2]);
1146 : }
1147 : }
1148 :
1149 2 : fputs ("\n#include <i386_data.h>\n\n", outfile);
1150 :
1151 :
1152 : #define APPEND(a, b) APPEND_ (a, b)
1153 : #define APPEND_(a, b) a##b
1154 : #define EMIT_SUFFIX(suf) \
1155 : fprintf (outfile, "#define suffix_%s %d\n", #suf, APPEND (suffix_, suf))
1156 2 : EMIT_SUFFIX (none);
1157 2 : EMIT_SUFFIX (w);
1158 2 : EMIT_SUFFIX (w0);
1159 2 : EMIT_SUFFIX (W);
1160 2 : EMIT_SUFFIX (tttn);
1161 2 : EMIT_SUFFIX (D);
1162 2 : EMIT_SUFFIX (w1);
1163 2 : EMIT_SUFFIX (W1);
1164 :
1165 2 : fputc_unlocked ('\n', outfile);
1166 :
1167 6 : for (int i = 0; i < 3; ++i)
1168 : {
1169 : /* Functions. */
1170 6 : count_op_str = 0;
1171 6 : fprintf (outfile, "static const opfct_t op%d_fct[] =\n{\n NULL,\n",
1172 : i + 1);
1173 6 : twalk (fct_names[i], print_op_fct);
1174 6 : fputs ("};\n", outfile);
1175 :
1176 : /* The operand strings. */
1177 6 : if (nbitstr[i] != 0)
1178 : {
1179 6 : count_op_str = 0;
1180 6 : off_op_str = 0;
1181 6 : fprintf (outfile, "static const char op%d_str[] =", i + 1);
1182 6 : twalk (strs[i], print_op_str);
1183 6 : fputs ("\";\n", outfile);
1184 :
1185 6 : fprintf (outfile, "static const uint8_t op%d_str_idx[] = {\n",
1186 : i + 1);
1187 6 : twalk (strs[i], print_op_str_idx);
1188 6 : fputs ("};\n", outfile);
1189 : }
1190 : }
1191 :
1192 :
1193 2 : fputs ("static const struct instr_enc instrtab[] =\n{\n", outfile);
1194 : struct instruction *instr;
1195 1503 : for (instr = instructions; instr != NULL; instr = instr->next)
1196 : {
1197 1501 : fputs (" {", outfile);
1198 1501 : if (instr->mnemonic == (void *) -1l)
1199 18 : fputs (" .mnemonic = MNE_INVALID,", outfile);
1200 : else
1201 1483 : fprintf (outfile, " .mnemonic = MNE_%s,", instr->mnemonic);
1202 1501 : fprintf (outfile, " .rep = %d,", instr->rep);
1203 1501 : fprintf (outfile, " .repe = %d,", instr->repe);
1204 1501 : fprintf (outfile, " .suffix = %d,", instr->suffix);
1205 1501 : fprintf (outfile, " .modrm = %d,", instr->modrm);
1206 :
1207 6004 : for (int i = 0; i < 3; ++i)
1208 : {
1209 4503 : int idx = 0;
1210 4503 : if (instr->operands[i].fct != NULL)
1211 : {
1212 2464 : struct argstring search = { .str = instr->operands[i].fct };
1213 2464 : struct argstring **res = tfind (&search, &fct_names[i],
1214 : compare_argstring);
1215 2464 : assert (res != NULL);
1216 2464 : idx = (*res)->idx;
1217 : }
1218 4503 : fprintf (outfile, " .fct%d = %d,", i + 1, idx);
1219 :
1220 4503 : idx = 0;
1221 4503 : if (instr->operands[i].str != NULL)
1222 : {
1223 112 : struct argstring search = { .str = instr->operands[i].str };
1224 112 : struct argstring **res = tfind (&search, &strs[i],
1225 : compare_argstring);
1226 112 : assert (res != NULL);
1227 112 : idx = (*res)->idx;
1228 : }
1229 4503 : if (nbitstr[i] != 0)
1230 4503 : fprintf (outfile, " .str%d = %d,", i + 1, idx);
1231 :
1232 4503 : fprintf (outfile, " .off%d_1 = %d,", i + 1,
1233 4503 : MAX (0, instr->operands[i].off1 - minoff[i][0]));
1234 :
1235 4503 : if (nbitoff[i][1] != 0)
1236 4503 : fprintf (outfile, " .off%d_2 = %d,", i + 1,
1237 4503 : MAX (0, instr->operands[i].off2 - minoff[i][1]));
1238 :
1239 4503 : if (nbitoff[i][2] != 0)
1240 3002 : fprintf (outfile, " .off%d_3 = %d,", i + 1,
1241 3002 : MAX (0, instr->operands[i].off3 - minoff[i][2]));
1242 : }
1243 :
1244 1501 : fputs (" },\n", outfile);
1245 : }
1246 2 : fputs ("};\n", outfile);
1247 :
1248 2 : fputs ("static const uint8_t match_data[] =\n{\n", outfile);
1249 2 : size_t cnt = 0;
1250 1503 : for (instr = instructions; instr != NULL; instr = instr->next, ++cnt)
1251 : {
1252 : /* First count the number of bytes. */
1253 1501 : size_t totalbits = 0;
1254 1501 : size_t zerobits = 0;
1255 1501 : bool leading_p = true;
1256 1501 : size_t leadingbits = 0;
1257 1501 : struct bitvalue *b = instr->bytes;
1258 33575 : while (b != NULL)
1259 : {
1260 30573 : if (b->type == zeroone)
1261 : {
1262 26984 : ++totalbits;
1263 26984 : zerobits = 0;
1264 26984 : if (leading_p)
1265 25852 : ++leadingbits;
1266 : }
1267 : else
1268 : {
1269 3589 : totalbits += b->field->bits;
1270 : /* We must always count the mod/rm byte. */
1271 3589 : if (strncasecmp (b->field->name, "mod", 3) == 0)
1272 : zerobits = 0;
1273 : else
1274 2538 : zerobits += b->field->bits;
1275 : leading_p = false;
1276 : }
1277 30573 : b = b->next;
1278 : }
1279 1501 : size_t nbytes = (totalbits - zerobits + 7) / 8;
1280 1501 : assert (nbytes > 0);
1281 1501 : size_t leadingbytes = leadingbits / 8;
1282 :
1283 1501 : fprintf (outfile, " %#zx,", nbytes | (leadingbytes << 4));
1284 :
1285 : /* Now create the mask and byte values. */
1286 1501 : uint8_t byte = 0;
1287 1501 : uint8_t mask = 0;
1288 1501 : int nbits = 0;
1289 1501 : b = instr->bytes;
1290 31844 : while (b != NULL)
1291 : {
1292 30343 : if (b->type == zeroone)
1293 : {
1294 26984 : byte = (byte << 1) | b->value;
1295 26984 : mask = (mask << 1) | 1;
1296 26984 : if (++nbits == 8)
1297 : {
1298 3027 : if (leadingbytes > 0)
1299 : {
1300 2943 : assert (mask == 0xff);
1301 2943 : fprintf (outfile, " %#" PRIx8 ",", byte);
1302 2943 : --leadingbytes;
1303 : }
1304 : else
1305 84 : fprintf (outfile, " %#" PRIx8 ", %#" PRIx8 ",",
1306 : mask, byte);
1307 3027 : byte = mask = nbits = 0;
1308 3027 : if (--nbytes == 0)
1309 : break;
1310 : }
1311 : }
1312 : else
1313 : {
1314 3359 : assert (leadingbytes == 0);
1315 :
1316 3359 : unsigned long int remaining = b->field->bits;
1317 6718 : while (nbits + remaining > 8)
1318 : {
1319 0 : fprintf (outfile, " %#" PRIx8 ", %#" PRIx8 ",",
1320 0 : mask << (8 - nbits), byte << (8 - nbits));
1321 0 : remaining = nbits + remaining - 8;
1322 0 : byte = mask = nbits = 0;
1323 0 : if (--nbytes == 0)
1324 : break;
1325 : }
1326 3359 : byte <<= remaining;
1327 3359 : mask <<= remaining;
1328 3359 : nbits += remaining;
1329 3359 : if (nbits == 8)
1330 : {
1331 1419 : fprintf (outfile, " %#" PRIx8 ", %#" PRIx8 ",", mask, byte);
1332 1419 : byte = mask = nbits = 0;
1333 1419 : if (--nbytes == 0)
1334 : break;
1335 : }
1336 : }
1337 28842 : b = b->next;
1338 : }
1339 :
1340 1501 : fputc_unlocked ('\n', outfile);
1341 : }
1342 2 : fputs ("};\n", outfile);
1343 2 : }
1344 :
1345 :
1346 : #if 0
1347 : static size_t mnemonic_maxlen;
1348 : static size_t mnemonic_minlen;
1349 : static size_t
1350 : which_chars (const char *str[], size_t nstr)
1351 : {
1352 : char used_char[256];
1353 : memset (used_char, '\0', sizeof (used_char));
1354 : mnemonic_maxlen = 0;
1355 : mnemonic_minlen = 10000;
1356 : for (size_t cnt = 0; cnt < nstr; ++cnt)
1357 : {
1358 : const unsigned char *cp = (const unsigned char *) str[cnt];
1359 : mnemonic_maxlen = MAX (mnemonic_maxlen, strlen ((char *) cp));
1360 : mnemonic_minlen = MIN (mnemonic_minlen, strlen ((char *) cp));
1361 : do
1362 : used_char[*cp++] = 1;
1363 : while (*cp != '\0');
1364 : }
1365 : size_t nused_char = 0;
1366 : for (size_t cnt = 0; cnt < 256; ++cnt)
1367 : if (used_char[cnt] != 0)
1368 : ++nused_char;
1369 : return nused_char;
1370 : }
1371 :
1372 :
1373 : static const char **mnemonic_strs;
1374 : static size_t nmnemonic_strs;
1375 : static void
1376 : add_mnemonics (const void *nodep, VISIT value,
1377 : int level __attribute__ ((unused)))
1378 : {
1379 : if (value == leaf || value == postorder)
1380 : mnemonic_strs[nmnemonic_strs++] = *(const char **) nodep;
1381 : }
1382 :
1383 :
1384 : struct charfreq
1385 : {
1386 : char ch;
1387 : int freq;
1388 : };
1389 : static struct charfreq pfxfreq[256];
1390 : static struct charfreq sfxfreq[256];
1391 :
1392 :
1393 : static int
1394 : compare_freq (const void *p1, const void *p2)
1395 : {
1396 : const struct charfreq *c1 = (const struct charfreq *) p1;
1397 : const struct charfreq *c2 = (const struct charfreq *) p2;
1398 :
1399 : if (c1->freq > c2->freq)
1400 : return -1;
1401 : if (c1->freq < c2->freq)
1402 : return 1;
1403 : return 0;
1404 : }
1405 :
1406 :
1407 : static size_t
1408 : compute_pfxfreq (const char *str[], size_t nstr)
1409 : {
1410 : memset (pfxfreq, '\0', sizeof (pfxfreq));
1411 :
1412 : for (size_t i = 0; i < nstr; ++i)
1413 : pfxfreq[i].ch = i;
1414 :
1415 : for (size_t i = 0; i < nstr; ++i)
1416 : ++pfxfreq[*((const unsigned char *) str[i])].freq;
1417 :
1418 : qsort (pfxfreq, 256, sizeof (struct charfreq), compare_freq);
1419 :
1420 : size_t n = 0;
1421 : while (n < 256 && pfxfreq[n].freq != 0)
1422 : ++n;
1423 : return n;
1424 : }
1425 :
1426 :
1427 : struct strsnlen
1428 : {
1429 : const char *str;
1430 : size_t len;
1431 : };
1432 :
1433 : static size_t
1434 : compute_sfxfreq (size_t nstr, struct strsnlen *strsnlen)
1435 : {
1436 : memset (sfxfreq, '\0', sizeof (sfxfreq));
1437 :
1438 : for (size_t i = 0; i < nstr; ++i)
1439 : sfxfreq[i].ch = i;
1440 :
1441 : for (size_t i = 0; i < nstr; ++i)
1442 : ++sfxfreq[((const unsigned char *) strchrnul (strsnlen[i].str, '\0'))[-1]].freq;
1443 :
1444 : qsort (sfxfreq, 256, sizeof (struct charfreq), compare_freq);
1445 :
1446 : size_t n = 0;
1447 : while (n < 256 && sfxfreq[n].freq != 0)
1448 : ++n;
1449 : return n;
1450 : }
1451 :
1452 :
1453 : static void
1454 : create_mnemonic_table (void)
1455 : {
1456 : mnemonic_strs = xmalloc (nmnemonics * sizeof (char *));
1457 :
1458 : twalk (mnemonics, add_mnemonics);
1459 :
1460 : (void) which_chars (mnemonic_strs, nmnemonic_strs);
1461 :
1462 : size_t best_so_far = 100000000;
1463 : char *best_prefix = NULL;
1464 : char *best_suffix = NULL;
1465 : char *best_table = NULL;
1466 : size_t best_table_size = 0;
1467 : size_t best_table_bits = 0;
1468 : size_t best_prefix_bits = 0;
1469 :
1470 : /* We can precompute the prefix characters. */
1471 : size_t npfx_char = compute_pfxfreq (mnemonic_strs, nmnemonic_strs);
1472 :
1473 : /* Compute best size for string representation including explicit NUL. */
1474 : for (size_t pfxbits = 0; (1u << pfxbits) < 2 * npfx_char; ++pfxbits)
1475 : {
1476 : char prefix[1 << pfxbits];
1477 : size_t i;
1478 : for (i = 0; i < (1u << pfxbits) - 1; ++i)
1479 : prefix[i] = pfxfreq[i].ch;
1480 : prefix[i] = '\0';
1481 :
1482 : struct strsnlen strsnlen[nmnemonic_strs];
1483 :
1484 : for (i = 0; i < nmnemonic_strs; ++i)
1485 : {
1486 : if (strchr (prefix, *mnemonic_strs[i]) != NULL)
1487 : strsnlen[i].str = mnemonic_strs[i] + 1;
1488 : else
1489 : strsnlen[i].str = mnemonic_strs[i];
1490 : strsnlen[i].len = strlen (strsnlen[i].str);
1491 : }
1492 :
1493 : /* With the prefixes gone, try to combine strings. */
1494 : size_t nstrsnlen = 1;
1495 : for (i = 1; i < nmnemonic_strs; ++i)
1496 : {
1497 : size_t j;
1498 : for (j = 0; j < nstrsnlen; ++j)
1499 : if (strsnlen[i].len > strsnlen[j].len
1500 : && strcmp (strsnlen[j].str,
1501 : strsnlen[i].str + (strsnlen[i].len
1502 : - strsnlen[j].len)) == 0)
1503 : {
1504 : strsnlen[j] = strsnlen[i];
1505 : break;
1506 : }
1507 : else if (strsnlen[i].len < strsnlen[j].len
1508 : && strcmp (strsnlen[i].str,
1509 : strsnlen[j].str + (strsnlen[j].len
1510 : - strsnlen[i].len)) == 0)
1511 : break;
1512 : ;
1513 : if (j == nstrsnlen)
1514 : strsnlen[nstrsnlen++] = strsnlen[i];
1515 : }
1516 :
1517 : size_t nsfx_char = compute_sfxfreq (nstrsnlen, strsnlen);
1518 :
1519 : for (size_t sfxbits = 0; (1u << sfxbits) < 2 * nsfx_char; ++sfxbits)
1520 : {
1521 : char suffix[1 << sfxbits];
1522 :
1523 : for (i = 0; i < (1u << sfxbits) - 1; ++i)
1524 : suffix[i] = sfxfreq[i].ch;
1525 : suffix[i] = '\0';
1526 :
1527 : size_t newlen[nstrsnlen];
1528 :
1529 : for (i = 0; i < nstrsnlen; ++i)
1530 : if (strchr (suffix, strsnlen[i].str[strsnlen[i].len - 1]) != NULL)
1531 : newlen[i] = strsnlen[i].len - 1;
1532 : else
1533 : newlen[i] = strsnlen[i].len;
1534 :
1535 : char charused[256];
1536 : memset (charused, '\0', sizeof (charused));
1537 : size_t ncharused = 0;
1538 :
1539 : const char *tablestr[nstrsnlen];
1540 : size_t ntablestr = 1;
1541 : tablestr[0] = strsnlen[0].str;
1542 : size_t table = newlen[0] + 1;
1543 : for (i = 1; i < nstrsnlen; ++i)
1544 : {
1545 : size_t j;
1546 : for (j = 0; j < ntablestr; ++j)
1547 : if (newlen[i] > newlen[j]
1548 : && memcmp (tablestr[j],
1549 : strsnlen[i].str + (newlen[i] - newlen[j]),
1550 : newlen[j]) == 0)
1551 : {
1552 : table += newlen[i] - newlen[j];
1553 : tablestr[j] = strsnlen[i].str;
1554 : newlen[j] = newlen[i];
1555 : break;
1556 : }
1557 : else if (newlen[i] < newlen[j]
1558 : && memcmp (strsnlen[i].str,
1559 : tablestr[j] + (newlen[j] - newlen[i]),
1560 : newlen[i]) == 0)
1561 : break;
1562 :
1563 : if (j == ntablestr)
1564 : {
1565 : table += newlen[i] + 1;
1566 : tablestr[ntablestr] = strsnlen[i].str;
1567 : newlen[ntablestr] = newlen[i];
1568 :
1569 : ++ntablestr;
1570 : }
1571 :
1572 : for (size_t x = 0; x < newlen[j]; ++x)
1573 : if (charused[((const unsigned char *) tablestr[j])[x]]++ == 0)
1574 : ++ncharused;
1575 : }
1576 :
1577 : size_t ncharused_bits = 0;
1578 : i = 1;
1579 : while (i < ncharused)
1580 : {
1581 : i *= 2;
1582 : ++ncharused_bits;
1583 : }
1584 :
1585 : size_t table_bits = 0;
1586 : i = 1;
1587 : while (i < table)
1588 : {
1589 : i *= 2;
1590 : ++table_bits;
1591 : }
1592 :
1593 : size_t mnemonic_bits = table_bits + pfxbits + sfxbits;
1594 : size_t new_total = (((table + 7) / 8) * ncharused_bits + ncharused
1595 : + (pfxbits == 0 ? 0 : (1 << pfxbits) - 1)
1596 : + (sfxbits == 0 ? 0 : (1 << sfxbits) - 1)
1597 : + (((total_bits + mnemonic_bits + 7) / 8)
1598 : * ninstructions));
1599 :
1600 : if (new_total < best_so_far)
1601 : {
1602 : best_so_far = new_total;
1603 : best_mnemonic_bits = mnemonic_bits;
1604 :
1605 : free (best_suffix);
1606 : best_suffix = xstrdup (suffix);
1607 :
1608 : free (best_prefix);
1609 : best_prefix = xstrdup (prefix);
1610 : best_prefix_bits = pfxbits;
1611 :
1612 : best_table_size = table;
1613 : best_table_bits = table_bits;
1614 : char *cp = best_table = xrealloc (best_table, table);
1615 : for (i = 0; i < ntablestr; ++i)
1616 : {
1617 : assert (cp + newlen[i] + 1 <= best_table + table);
1618 : cp = mempcpy (cp, tablestr[i], newlen[i]);
1619 : *cp++ = '\0';
1620 : }
1621 : assert (cp == best_table + table);
1622 : }
1623 : }
1624 : }
1625 :
1626 : fputs ("static const char mnemonic_table[] =\n\"", outfile);
1627 : for (size_t i = 0; i < best_table_size; ++i)
1628 : {
1629 : if (((i + 1) % 60) == 0)
1630 : fputs ("\"\n\"", outfile);
1631 : if (!isascii (best_table[i]) || !isprint (best_table[i]))
1632 : fprintf (outfile, "\\%03o", best_table[i]);
1633 : else
1634 : fputc (best_table[i], outfile);
1635 : }
1636 : fputs ("\";\n", outfile);
1637 :
1638 : if (best_prefix[0] != '\0')
1639 : fprintf (outfile,
1640 : "static const char prefix[%zu] = \"%s\";\n"
1641 : "#define PREFIXCHAR_BITS %zu\n",
1642 : strlen (best_prefix), best_prefix, best_prefix_bits);
1643 : else
1644 : fputs ("#define NO_PREFIX\n", outfile);
1645 :
1646 : if (best_suffix[0] != '\0')
1647 : fprintf (outfile, "static const char suffix[%zu] = \"%s\";\n",
1648 : strlen (best_suffix), best_suffix);
1649 : else
1650 : fputs ("#define NO_SUFFIX\n", outfile);
1651 :
1652 : for (size_t i = 0; i < nmnemonic_strs; ++i)
1653 : {
1654 : const char *mne = mnemonic_strs[i];
1655 :
1656 : size_t pfxval = 0;
1657 : char *cp = strchr (best_prefix, *mne);
1658 : if (cp != NULL)
1659 : {
1660 : pfxval = 1 + (cp - best_prefix);
1661 : ++mne;
1662 : }
1663 :
1664 : size_t l = strlen (mne);
1665 :
1666 : size_t sfxval = 0;
1667 : cp = strchr (best_suffix, mne[l - 1]);
1668 : if (cp != NULL)
1669 : {
1670 : sfxval = 1 + (cp - best_suffix);
1671 : --l;
1672 : }
1673 :
1674 : char *off = memmem (best_table, best_table_size, mne, l);
1675 : while (off[l] != '\0')
1676 : {
1677 : off = memmem (off + 1, best_table_size, mne, l);
1678 : assert (off != NULL);
1679 : }
1680 :
1681 : fprintf (outfile, "#define MNE_%s %#zx\n",
1682 : mnemonic_strs[i],
1683 : (off - best_table)
1684 : + ((pfxval + (sfxval << best_prefix_bits)) << best_table_bits));
1685 : }
1686 : }
1687 : #endif
|
