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.
6 This file is free software; you can redistribute it and/or modify
7 it under the terms of either
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
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
19 or both in parallel, as here.
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.
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/>. */
47 #include <sys/param.h>
51 #define obstack_chunk_alloc xmalloc
52 #define obstack_chunk_free free
54 /* The error handler. */
55 static void yyerror (const char *s);
57 extern int yylex (void);
58 extern int i386_lineno;
65 unsigned long int bits;
72 enum bittype { zeroone, field, failure } type;
76 struct known_bitfield *field;
78 struct bitvalue *next;
84 enum nametype { string, nfield } type;
88 struct known_bitfield *field;
97 struct argument *next;
103 /* The byte encoding. */
104 struct bitvalue *bytes;
106 /* Prefix possible. */
114 enum { suffix_none = 0, suffix_w, suffix_w0, suffix_W, suffix_tttn,
115 suffix_w1, suffix_W1, suffix_D } suffix;
117 /* Flag set if modr/m is used. */
130 struct instruction *next;
156 static struct known_bitfield ax_reg =
158 .name = "ax", .bits = 0, .tmp = 0
161 static struct known_bitfield dx_reg =
163 .name = "dx", .bits = 0, .tmp = 0
166 static struct known_bitfield di_reg =
168 .name = "es_di", .bits = 0, .tmp = 0
171 static struct known_bitfield si_reg =
173 .name = "ds_si", .bits = 0, .tmp = 0
176 static struct known_bitfield bx_reg =
178 .name = "ds_bx", .bits = 0, .tmp = 0
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);
198 static void create_mnemonic_table (void);
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;
209 extern FILE *outfile;
211 /* Number of bits used mnemonics. */
213 static size_t best_mnemonic_bits;
218 unsigned long int num;
221 struct known_bitfield *field;
222 struct bitvalue *bit;
223 struct argname *name;
224 struct argument *arg;
234 %token <str> kBITFIELD
238 %type <bit> bit byte bytes
239 %type <field> bitfieldopt
240 %type <name> argcomp arg
241 %type <arg> args optargs
247 spec: masks kPERCPERC '\n' instrs
249 if (error_message_count != 0)
250 error (EXIT_FAILURE, 0,
251 "terminated due to previous error");
257 masks: masks '\n' mask
261 mask: kMASK kBITFIELD kNUMBER
262 { new_bitfield ($2, $3); }
264 { new_bitfield ($2, -1); }
266 { new_bitfield ($2, -2); }
267 | kSYNONYM kBITFIELD kBITFIELD
269 struct synonym *newp = xmalloc (sizeof (*newp));
272 if (tfind (newp, &synonyms, compare_syn) != NULL)
274 "%d: duplicate definition for synonym '%s'",
276 else if (tsearch ( newp, &synonyms, compare_syn) == NULL)
277 error (EXIT_FAILURE, 0, "tsearch");
282 instrs: instrs '\n' instr
286 instr: bytes ':' bitfieldopt kID bitfieldopt optargs
288 if ($3 != NULL && strcmp ($3->name, "RE") != 0
289 && strcmp ($3->name, "R") != 0)
291 error (0, 0, "%d: only 'R' and 'RE' prefix allowed",
294 if (check_duplicates ($1) == 0
295 && check_argsdef ($1, $6) == 0
296 && check_bitsused ($1, $5, $6) == 0)
298 struct instruction *newp = xcalloc (sizeof (*newp),
302 if (strcmp ($3->name, "RE") == 0)
304 else if (strcmp ($3->name, "R") == 0)
310 if (newp->mnemonic != (void *) -1l
311 && tfind ($4, &mnemonics,
312 (comparison_fn_t) strcmp) == NULL)
314 if (tsearch ($4, &mnemonics,
315 (comparison_fn_t) strcmp) == NULL)
316 error (EXIT_FAILURE, errno, "tsearch");
322 if (strcmp ($5->name, "w") == 0)
323 newp->suffix = suffix_w;
324 else if (strcmp ($5->name, "w0") == 0)
325 newp->suffix = suffix_w0;
326 else if (strcmp ($5->name, "tttn") == 0)
327 newp->suffix = suffix_tttn;
328 else if (strcmp ($5->name, "w1") == 0)
329 newp->suffix = suffix_w1;
330 else if (strcmp ($5->name, "W") == 0)
331 newp->suffix = suffix_W;
332 else if (strcmp ($5->name, "W1") == 0)
333 newp->suffix = suffix_W1;
334 else if (strcmp ($5->name, "D") == 0)
335 newp->suffix = suffix_D;
337 error (EXIT_FAILURE, 0,
338 "%s: %d: unknown suffix '%s'",
339 infname, i386_lineno - 1, $5->name);
341 struct suffix search = { .name = $5->name };
342 if (tfind (&search, &suffixes, compare_suf)
345 struct suffix *ns = xmalloc (sizeof (*ns));
347 ns->idx = ++nsuffixes;
348 if (tsearch (ns, &suffixes, compare_suf)
350 error (EXIT_FAILURE, errno, "tsearch");
354 struct argument *args = $6;
358 fillin_arg ($1, args->name, newp, n);
364 newp->next = instructions;
372 bitfieldopt: kBITFIELD
374 struct known_bitfield search;
376 struct known_bitfield **res;
377 res = tfind (&search, &bitfields, bitfield_compare);
380 error (0, 0, "%d: unknown bitfield '%s'",
381 i386_lineno, search.name);
391 bytes: bytes ',' byte
395 struct bitvalue *runp = $1;
396 while (runp->next != NULL)
410 struct bitvalue *runp = $1;
411 while (runp->next != NULL)
422 $$ = xmalloc (sizeof (struct bitvalue));
429 $$ = xmalloc (sizeof (struct bitvalue));
436 $$ = xmalloc (sizeof (struct bitvalue));
437 struct known_bitfield search;
439 struct known_bitfield **res;
440 res = tfind (&search, &bitfields, bitfield_compare);
443 error (0, 0, "%d: unknown bitfield '%s'",
444 i386_lineno, search.name);
464 struct argument *runp = $1;
465 while (runp->next != NULL)
467 runp->next = xmalloc (sizeof (struct argument));
468 runp->next->name = combine ($3);
469 runp->next->next = NULL;
474 $$ = xmalloc (sizeof (struct argument));
475 $$->name = combine ($1);
482 struct argname *runp = $1;
483 while (runp->next != NULL)
493 $$ = xmalloc (sizeof (struct argname));
497 struct known_bitfield search;
499 struct known_bitfield **res;
500 res = tfind (&search, &bitfields, bitfield_compare);
503 if (strcmp ($1, "ax") == 0)
505 else if (strcmp ($1, "dx") == 0)
507 else if (strcmp ($1, "es_di") == 0)
509 else if (strcmp ($1, "ds_si") == 0)
511 else if (strcmp ($1, "ds_bx") == 0)
515 error (0, 0, "%d: unknown bitfield '%s'",
516 i386_lineno, search.name);
525 $$ = xmalloc (sizeof (struct argname));
528 $$->str = xmalloc (2);
534 $$ = xmalloc (sizeof (struct argname));
541 $$ = xmalloc (sizeof (struct argname));
544 $$->str = xmalloc (2);
553 yyerror (const char *s)
555 error (0, 0, gettext ("while reading i386 CPU description: %s at line %d"),
556 gettext (s), i386_lineno);
561 bitfield_compare (const void *p1, const void *p2)
563 struct known_bitfield *f1 = (struct known_bitfield *) p1;
564 struct known_bitfield *f2 = (struct known_bitfield *) p2;
566 return strcmp (f1->name, f2->name);
571 new_bitfield (char *name, unsigned long int num)
573 struct known_bitfield *newp = xmalloc (sizeof (struct known_bitfield));
578 if (tfind (newp, &bitfields, bitfield_compare) != NULL)
580 error (0, 0, "%d: duplicated definition of bitfield '%s'",
586 if (tsearch (newp, &bitfields, bitfield_compare) == NULL)
587 error (EXIT_FAILURE, errno, "%d: cannot insert new bitfield '%s'",
592 /* Check that the number of bits is a multiple of 8. */
594 check_bits (struct bitvalue *val)
596 struct bitvalue *runp = val;
597 unsigned int total = 0;
601 if (runp->type == zeroone)
603 else if (runp->field == NULL)
604 /* No sense doing anything, the field is not known. */
607 total += runp->field->bits;
619 if (val->type == zeroone)
620 obstack_printf (&os, "%u", val->value);
622 obstack_printf (&os, "{%s}", val->field->name);
625 obstack_1grow (&os, '\0');
627 error (0, 0, "%d: field '%s' not a multiple of 8 bits in size",
628 i386_lineno, (char *) obstack_finish (&os));
630 obstack_free (&os, NULL);
636 check_duplicates (struct bitvalue *val)
644 if (val->type == field && val->field != NULL)
646 if (val->field->tmp == testcnt)
648 error (0, 0, "%d: bitfield '%s' used more than once",
649 i386_lineno - 1, val->field->name);
652 val->field->tmp = testcnt;
663 check_argsdef (struct bitvalue *bitval, struct argument *args)
669 for (struct argname *name = args->name; name != NULL; name = name->next)
670 if (name->type == nfield && name->field != NULL
671 && name->field != &ax_reg && name->field != &dx_reg
672 && name->field != &di_reg && name->field != &si_reg
673 && name->field != &bx_reg)
675 struct bitvalue *runp = bitval;
678 if (runp->type == field && runp->field == name->field)
685 error (0, 0, "%d: unknown bitfield '%s' used in output format",
686 i386_lineno - 1, name->field->name);
699 check_bitsused (struct bitvalue *bitval, struct known_bitfield *suffix,
700 struct argument *args)
704 while (bitval != NULL)
706 if (bitval->type == field && bitval->field != NULL
707 && bitval->field != suffix
708 /* {w} is handled special. */
709 && strcmp (bitval->field->name, "w") != 0)
711 struct argument *runp;
712 for (runp = args; runp != NULL; runp = runp->next)
714 struct argname *name = runp->name;
717 if (name->type == nfield && name->field == bitval->field)
729 error (0, 0, "%d: bitfield '%s' not used",
730 i386_lineno - 1, bitval->field->name);
736 bitval = bitval->next;
743 static struct argname *
744 combine (struct argname *name)
746 struct argname *last_str = NULL;
747 for (struct argname *runp = name; runp != NULL; runp = runp->next)
749 if (runp->type == string)
751 if (last_str == NULL)
755 last_str->str = xrealloc (last_str->str,
756 strlen (last_str->str)
757 + strlen (runp->str) + 1);
758 strcat (last_str->str, runp->str);
759 last_str->next = runp->next;
769 #define obstack_grow_str(ob, str) obstack_grow (ob, str, strlen (str))
773 fillin_arg (struct bitvalue *bytes, struct argname *name,
774 struct instruction *instr, int n)
776 static struct obstack ob;
777 static int initialized;
784 struct argname *runp = name;
788 /* We ignore strings in the function name. */
789 if (runp->type == string)
791 if (instr->operands[n].str != NULL)
792 error (EXIT_FAILURE, 0,
793 "%d: cannot have more than one string parameter",
796 instr->operands[n].str = runp->str;
800 assert (runp->type == nfield);
802 /* Construct the function name. */
804 obstack_1grow (&ob, '$');
806 if (runp->field == NULL)
807 /* Add some string which contains invalid characters. */
808 obstack_grow_str (&ob, "!!!INVALID!!!");
811 char *fieldname = runp->field->name;
813 struct synonym search = { .from = fieldname };
815 struct synonym **res = tfind (&search, &synonyms, compare_syn);
817 fieldname = (*res)->to;
819 obstack_grow_str (&ob, fieldname);
822 /* Now compute the bit offset of the field. */
823 struct bitvalue *b = bytes;
825 if (runp->field != NULL)
828 if (b->type == field && b->field != NULL)
830 if (strcmp (b->field->name, runp->field->name) == 0)
832 bitoff += b->field->bits;
839 if (instr->operands[n].off1 == 0)
840 instr->operands[n].off1 = bitoff;
841 else if (instr->operands[n].off2 == 0)
842 instr->operands[n].off2 = bitoff;
843 else if (instr->operands[n].off3 == 0)
844 instr->operands[n].off3 = bitoff;
846 error (EXIT_FAILURE, 0,
847 "%d: cannot have more than three fields in parameter",
850 if (runp->field != NULL
851 && strncasecmp (runp->field->name, "mod", 3) == 0)
857 if (obstack_object_size (&ob) == 0)
858 obstack_grow_str (&ob, "string");
859 obstack_1grow (&ob, '\0');
860 char *fct = obstack_finish (&ob);
862 instr->operands[n].fct = fct;
868 nameout (const void *nodep, VISIT value, int level)
870 if (value == leaf || value == postorder)
871 printf (" %s\n", *(const char **) nodep);
877 compare_argstring (const void *p1, const void *p2)
879 const struct argstring *a1 = (const struct argstring *) p1;
880 const struct argstring *a2 = (const struct argstring *) p2;
882 return strcmp (a1->str, a2->str);
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];
894 static void *strs[3];
895 static int nbitstr[3];
896 static int total_bits = 2; // Already counted the rep/repe bits.
901 int nfct_names[3] = { 0, 0, 0 };
902 int nstrs[3] = { 0, 0, 0 };
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
907 struct instruction *reversed = NULL;
909 struct instruction *runp = instructions;
912 for (int i = 0; i < 3; ++i)
913 if (runp->operands[i].fct != NULL)
915 struct argstring search = { .str = runp->operands[i].fct };
916 if (tfind (&search, &fct_names[i], compare_argstring) == NULL)
918 struct argstring *newp = xmalloc (sizeof (*newp));
919 newp->str = runp->operands[i].fct;
921 if (tsearch (newp, &fct_names[i], compare_argstring) == NULL)
922 error (EXIT_FAILURE, errno, "tsearch");
926 if (runp->operands[i].str != NULL)
928 search.str = runp->operands[i].str;
929 if (tfind (&search, &strs[i], compare_argstring) == NULL)
931 struct argstring *newp = xmalloc (sizeof (*newp));
932 newp->str = runp->operands[i].str;
934 if (tsearch (newp, &strs[i], compare_argstring) == NULL)
935 error (EXIT_FAILURE, errno, "tsearch");
940 maxoff[i][0] = MAX (maxoff[i][0], runp->operands[i].off1);
941 maxoff[i][1] = MAX (maxoff[i][1], runp->operands[i].off2);
942 maxoff[i][2] = MAX (maxoff[i][2], runp->operands[i].off3);
944 if (runp->operands[i].off1 > 0)
945 minoff[i][0] = MIN (minoff[i][0], runp->operands[i].off1);
946 if (runp->operands[i].off2 > 0)
947 minoff[i][1] = MIN (minoff[i][1], runp->operands[i].off2);
948 if (runp->operands[i].off3 > 0)
949 minoff[i][2] = MIN (minoff[i][2], runp->operands[i].off3);
952 struct instruction *old = runp;
955 old->next = reversed;
958 instructions = reversed;
962 for (int i = 0; i < 3; ++i)
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]);
967 if (minoff[i][0] == 1000)
972 d = maxoff[i][0] - minoff[i][0];
979 total_bits += nbitoff[i][0];
982 if (minoff[i][1] == 1000)
987 d = maxoff[i][1] - minoff[i][1];
994 total_bits += nbitoff[i][1];
997 if (minoff[i][2] == 1000)
1002 d = maxoff[i][2] - minoff[i][2];
1009 total_bits += nbitoff[i][2];
1011 // printf ("off1 = %d, off2 = %d, off3 = %d\n", nbitoff[i][0], nbitoff[i][1], nbitoff[i][2]);
1021 total_bits += nbitfct[i];
1022 // printf ("%d fct[%d], %d bits\n", nfct_names[i], i, nbitfct[i]);
1034 total_bits += nbitstr[i];
1037 // twalk (fct_names[i], nameout);
1048 total_bits += nbitsuf;
1049 // printf ("%d suffixes, %d bits\n", nsuffixes, nbitsuf);
1054 compare_syn (const void *p1, const void *p2)
1056 const struct synonym *s1 = (const struct synonym *) p1;
1057 const struct synonym *s2 = (const struct synonym *) p2;
1059 return strcmp (s1->from, s2->from);
1064 compare_suf (const void *p1, const void *p2)
1066 const struct suffix *s1 = (const struct suffix *) p1;
1067 const struct suffix *s2 = (const struct suffix *) p2;
1069 return strcmp (s1->name, s2->name);
1073 static int count_op_str;
1074 static int off_op_str;
1076 print_op_str (const void *nodep, VISIT value,
1077 int level __attribute__ ((unused)))
1079 if (value == leaf || value == postorder)
1081 const char *str = (*(struct argstring **) nodep)->str;
1082 fprintf (outfile, "%s\n \"%s",
1083 count_op_str == 0 ? "" : "\\0\"", str);
1084 (*(struct argstring **) nodep)->idx = ++count_op_str;
1085 (*(struct argstring **) nodep)->off = off_op_str;
1086 off_op_str += strlen (str) + 1;
1092 print_op_str_idx (const void *nodep, VISIT value,
1093 int level __attribute__ ((unused)))
1095 if (value == leaf || value == postorder)
1096 printf (" %d,\n", (*(struct argstring **) nodep)->off);
1101 print_op_fct (const void *nodep, VISIT value,
1102 int level __attribute__ ((unused)))
1104 if (value == leaf || value == postorder)
1106 fprintf (outfile, " FCT_%s,\n", (*(struct argstring **) nodep)->str);
1107 (*(struct argstring **) nodep)->idx = ++count_op_str;
1113 # error "bogus NMNES value"
1117 instrtable_out (void)
1122 create_mnemonic_table ();
1124 fprintf (outfile, "#define MNEMONIC_BITS %zu\n", best_mnemonic_bits);
1126 fprintf (outfile, "#define MNEMONIC_BITS %ld\n",
1127 lrint (ceil (log2 (NMNES))));
1129 fprintf (outfile, "#define SUFFIX_BITS %d\n", nbitsuf);
1130 for (int i = 0; i < 3; ++i)
1132 fprintf (outfile, "#define FCT%d_BITS %d\n", i + 1, nbitfct[i]);
1133 if (nbitstr[i] != 0)
1134 fprintf (outfile, "#define STR%d_BITS %d\n", i + 1, nbitstr[i]);
1135 fprintf (outfile, "#define OFF%d_1_BITS %d\n", i + 1, nbitoff[i][0]);
1136 fprintf (outfile, "#define OFF%d_1_BIAS %d\n", i + 1, minoff[i][0]);
1137 if (nbitoff[i][1] != 0)
1139 fprintf (outfile, "#define OFF%d_2_BITS %d\n", i + 1, nbitoff[i][1]);
1140 fprintf (outfile, "#define OFF%d_2_BIAS %d\n", i + 1, minoff[i][1]);
1142 if (nbitoff[i][2] != 0)
1144 fprintf (outfile, "#define OFF%d_3_BITS %d\n", i + 1, nbitoff[i][2]);
1145 fprintf (outfile, "#define OFF%d_3_BIAS %d\n", i + 1, minoff[i][2]);
1149 fputs ("\n#include <i386_data.h>\n\n", outfile);
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))
1165 fputc_unlocked ('\n', outfile);
1167 for (int i = 0; i < 3; ++i)
1171 fprintf (outfile, "static const opfct_t op%d_fct[] =\n{\n NULL,\n",
1173 twalk (fct_names[i], print_op_fct);
1174 fputs ("};\n", outfile);
1176 /* The operand strings. */
1177 if (nbitstr[i] != 0)
1181 fprintf (outfile, "static const char op%d_str[] =", i + 1);
1182 twalk (strs[i], print_op_str);
1183 fputs ("\";\n", outfile);
1185 fprintf (outfile, "static const uint8_t op%d_str_idx[] = {\n",
1187 twalk (strs[i], print_op_str_idx);
1188 fputs ("};\n", outfile);
1193 fputs ("static const struct instr_enc instrtab[] =\n{\n", outfile);
1194 struct instruction *instr;
1195 for (instr = instructions; instr != NULL; instr = instr->next)
1197 fputs (" {", outfile);
1198 if (instr->mnemonic == (void *) -1l)
1199 fputs (" .mnemonic = MNE_INVALID,", outfile);
1201 fprintf (outfile, " .mnemonic = MNE_%s,", instr->mnemonic);
1202 fprintf (outfile, " .rep = %d,", instr->rep);
1203 fprintf (outfile, " .repe = %d,", instr->repe);
1204 fprintf (outfile, " .suffix = %d,", instr->suffix);
1205 fprintf (outfile, " .modrm = %d,", instr->modrm);
1207 for (int i = 0; i < 3; ++i)
1210 if (instr->operands[i].fct != NULL)
1212 struct argstring search = { .str = instr->operands[i].fct };
1213 struct argstring **res = tfind (&search, &fct_names[i],
1215 assert (res != NULL);
1218 fprintf (outfile, " .fct%d = %d,", i + 1, idx);
1221 if (instr->operands[i].str != NULL)
1223 struct argstring search = { .str = instr->operands[i].str };
1224 struct argstring **res = tfind (&search, &strs[i],
1226 assert (res != NULL);
1229 if (nbitstr[i] != 0)
1230 fprintf (outfile, " .str%d = %d,", i + 1, idx);
1232 fprintf (outfile, " .off%d_1 = %d,", i + 1,
1233 MAX (0, instr->operands[i].off1 - minoff[i][0]));
1235 if (nbitoff[i][1] != 0)
1236 fprintf (outfile, " .off%d_2 = %d,", i + 1,
1237 MAX (0, instr->operands[i].off2 - minoff[i][1]));
1239 if (nbitoff[i][2] != 0)
1240 fprintf (outfile, " .off%d_3 = %d,", i + 1,
1241 MAX (0, instr->operands[i].off3 - minoff[i][2]));
1244 fputs (" },\n", outfile);
1246 fputs ("};\n", outfile);
1248 fputs ("static const uint8_t match_data[] =\n{\n", outfile);
1250 for (instr = instructions; instr != NULL; instr = instr->next, ++cnt)
1252 /* First count the number of bytes. */
1253 size_t totalbits = 0;
1254 size_t zerobits = 0;
1255 bool leading_p = true;
1256 size_t leadingbits = 0;
1257 struct bitvalue *b = instr->bytes;
1260 if (b->type == zeroone)
1269 totalbits += b->field->bits;
1270 /* We must always count the mod/rm byte. */
1271 if (strncasecmp (b->field->name, "mod", 3) == 0)
1274 zerobits += b->field->bits;
1279 size_t nbytes = (totalbits - zerobits + 7) / 8;
1280 assert (nbytes > 0);
1281 size_t leadingbytes = leadingbits / 8;
1283 fprintf (outfile, " %#zx,", nbytes | (leadingbytes << 4));
1285 /* Now create the mask and byte values. */
1292 if (b->type == zeroone)
1294 byte = (byte << 1) | b->value;
1295 mask = (mask << 1) | 1;
1298 if (leadingbytes > 0)
1300 assert (mask == 0xff);
1301 fprintf (outfile, " %#" PRIx8 ",", byte);
1305 fprintf (outfile, " %#" PRIx8 ", %#" PRIx8 ",",
1307 byte = mask = nbits = 0;
1314 assert (leadingbytes == 0);
1316 unsigned long int remaining = b->field->bits;
1317 while (nbits + remaining > 8)
1319 fprintf (outfile, " %#" PRIx8 ", %#" PRIx8 ",",
1320 mask << (8 - nbits), byte << (8 - nbits));
1321 remaining = nbits + remaining - 8;
1322 byte = mask = nbits = 0;
1331 fprintf (outfile, " %#" PRIx8 ", %#" PRIx8 ",", mask, byte);
1332 byte = mask = nbits = 0;
1340 fputc_unlocked ('\n', outfile);
1342 fputs ("};\n", outfile);
1347 static size_t mnemonic_maxlen;
1348 static size_t mnemonic_minlen;
1350 which_chars (const char *str[], size_t nstr)
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)
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));
1362 used_char[*cp++] = 1;
1363 while (*cp != '\0');
1365 size_t nused_char = 0;
1366 for (size_t cnt = 0; cnt < 256; ++cnt)
1367 if (used_char[cnt] != 0)
1373 static const char **mnemonic_strs;
1374 static size_t nmnemonic_strs;
1376 add_mnemonics (const void *nodep, VISIT value,
1377 int level __attribute__ ((unused)))
1379 if (value == leaf || value == postorder)
1380 mnemonic_strs[nmnemonic_strs++] = *(const char **) nodep;
1389 static struct charfreq pfxfreq[256];
1390 static struct charfreq sfxfreq[256];
1394 compare_freq (const void *p1, const void *p2)
1396 const struct charfreq *c1 = (const struct charfreq *) p1;
1397 const struct charfreq *c2 = (const struct charfreq *) p2;
1399 if (c1->freq > c2->freq)
1401 if (c1->freq < c2->freq)
1408 compute_pfxfreq (const char *str[], size_t nstr)
1410 memset (pfxfreq, '\0', sizeof (pfxfreq));
1412 for (size_t i = 0; i < nstr; ++i)
1415 for (size_t i = 0; i < nstr; ++i)
1416 ++pfxfreq[*((const unsigned char *) str[i])].freq;
1418 qsort (pfxfreq, 256, sizeof (struct charfreq), compare_freq);
1421 while (n < 256 && pfxfreq[n].freq != 0)
1434 compute_sfxfreq (size_t nstr, struct strsnlen *strsnlen)
1436 memset (sfxfreq, '\0', sizeof (sfxfreq));
1438 for (size_t i = 0; i < nstr; ++i)
1441 for (size_t i = 0; i < nstr; ++i)
1442 ++sfxfreq[((const unsigned char *) strchrnul (strsnlen[i].str, '\0'))[-1]].freq;
1444 qsort (sfxfreq, 256, sizeof (struct charfreq), compare_freq);
1447 while (n < 256 && sfxfreq[n].freq != 0)
1454 create_mnemonic_table (void)
1456 mnemonic_strs = xmalloc (nmnemonics * sizeof (char *));
1458 twalk (mnemonics, add_mnemonics);
1460 (void) which_chars (mnemonic_strs, nmnemonic_strs);
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;
1470 /* We can precompute the prefix characters. */
1471 size_t npfx_char = compute_pfxfreq (mnemonic_strs, nmnemonic_strs);
1473 /* Compute best size for string representation including explicit NUL. */
1474 for (size_t pfxbits = 0; (1u << pfxbits) < 2 * npfx_char; ++pfxbits)
1476 char prefix[1 << pfxbits];
1478 for (i = 0; i < (1u << pfxbits) - 1; ++i)
1479 prefix[i] = pfxfreq[i].ch;
1482 struct strsnlen strsnlen[nmnemonic_strs];
1484 for (i = 0; i < nmnemonic_strs; ++i)
1486 if (strchr (prefix, *mnemonic_strs[i]) != NULL)
1487 strsnlen[i].str = mnemonic_strs[i] + 1;
1489 strsnlen[i].str = mnemonic_strs[i];
1490 strsnlen[i].len = strlen (strsnlen[i].str);
1493 /* With the prefixes gone, try to combine strings. */
1494 size_t nstrsnlen = 1;
1495 for (i = 1; i < nmnemonic_strs; ++i)
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)
1504 strsnlen[j] = strsnlen[i];
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)
1514 strsnlen[nstrsnlen++] = strsnlen[i];
1517 size_t nsfx_char = compute_sfxfreq (nstrsnlen, strsnlen);
1519 for (size_t sfxbits = 0; (1u << sfxbits) < 2 * nsfx_char; ++sfxbits)
1521 char suffix[1 << sfxbits];
1523 for (i = 0; i < (1u << sfxbits) - 1; ++i)
1524 suffix[i] = sfxfreq[i].ch;
1527 size_t newlen[nstrsnlen];
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;
1533 newlen[i] = strsnlen[i].len;
1536 memset (charused, '\0', sizeof (charused));
1537 size_t ncharused = 0;
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)
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]),
1552 table += newlen[i] - newlen[j];
1553 tablestr[j] = strsnlen[i].str;
1554 newlen[j] = newlen[i];
1557 else if (newlen[i] < newlen[j]
1558 && memcmp (strsnlen[i].str,
1559 tablestr[j] + (newlen[j] - newlen[i]),
1565 table += newlen[i] + 1;
1566 tablestr[ntablestr] = strsnlen[i].str;
1567 newlen[ntablestr] = newlen[i];
1572 for (size_t x = 0; x < newlen[j]; ++x)
1573 if (charused[((const unsigned char *) tablestr[j])[x]]++ == 0)
1577 size_t ncharused_bits = 0;
1579 while (i < ncharused)
1585 size_t table_bits = 0;
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)
1600 if (new_total < best_so_far)
1602 best_so_far = new_total;
1603 best_mnemonic_bits = mnemonic_bits;
1606 best_suffix = xstrdup (suffix);
1609 best_prefix = xstrdup (prefix);
1610 best_prefix_bits = pfxbits;
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)
1617 assert (cp + newlen[i] + 1 <= best_table + table);
1618 cp = mempcpy (cp, tablestr[i], newlen[i]);
1621 assert (cp == best_table + table);
1626 fputs ("static const char mnemonic_table[] =\n\"", outfile);
1627 for (size_t i = 0; i < best_table_size; ++i)
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]);
1634 fputc (best_table[i], outfile);
1636 fputs ("\";\n", outfile);
1638 if (best_prefix[0] != '\0')
1640 "static const char prefix[%zu] = \"%s\";\n"
1641 "#define PREFIXCHAR_BITS %zu\n",
1642 strlen (best_prefix), best_prefix, best_prefix_bits);
1644 fputs ("#define NO_PREFIX\n", outfile);
1646 if (best_suffix[0] != '\0')
1647 fprintf (outfile, "static const char suffix[%zu] = \"%s\";\n",
1648 strlen (best_suffix), best_suffix);
1650 fputs ("#define NO_SUFFIX\n", outfile);
1652 for (size_t i = 0; i < nmnemonic_strs; ++i)
1654 const char *mne = mnemonic_strs[i];
1657 char *cp = strchr (best_prefix, *mne);
1660 pfxval = 1 + (cp - best_prefix);
1664 size_t l = strlen (mne);
1667 cp = strchr (best_suffix, mne[l - 1]);
1670 sfxval = 1 + (cp - best_suffix);
1674 char *off = memmem (best_table, best_table_size, mne, l);
1675 while (off[l] != '\0')
1677 off = memmem (off + 1, best_table_size, mne, l);
1678 assert (off != NULL);
1681 fprintf (outfile, "#define MNE_%s %#zx\n",
1684 + ((pfxval + (sfxval << best_prefix_bits)) << best_table_bits));