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