diff options
Diffstat (limited to 'libcpu/i386_parse.y')
-rw-r--r-- | libcpu/i386_parse.y | 1641 |
1 files changed, 1641 insertions, 0 deletions
diff --git a/libcpu/i386_parse.y b/libcpu/i386_parse.y new file mode 100644 index 00000000..9ad11622 --- /dev/null +++ b/libcpu/i386_parse.y @@ -0,0 +1,1641 @@ +%{ +/* Parser for i386 CPU description. + Copyright (C) 2004, 2005, 2007 Red Hat, Inc. + Written by Ulrich Drepper <drepper@redhat.com>, 2004. + + This program is Open Source software; you can redistribute it and/or + modify it under the terms of the Open Software License version 1.0 as + published by the Open Source Initiative. + + You should have received a copy of the Open Software License along + with this program; if not, you may obtain a copy of the Open Software + License version 1.0 from http://www.opensource.org/licenses/osl.php or + by writing the Open Source Initiative c/o Lawrence Rosen, Esq., + 3001 King Ranch Road, Ukiah, CA 95482. */ + +#ifdef HAVE_CONFIG_H +# include <config.h> +#endif + +#include <assert.h> +#include <ctype.h> +#include <errno.h> +#include <error.h> +#include <inttypes.h> +#include <libintl.h> +#include <math.h> +#include <obstack.h> +#include <search.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/param.h> + +#include <system.h> + +#define obstack_chunk_alloc xmalloc +#define obstack_chunk_free free + +/* The error handler. */ +static void yyerror (const char *s); + +extern int yylex (void); +extern int i386_lineno; +extern char *infname; + + +struct known_bitfield +{ + char *name; + unsigned long int bits; + int tmp; +}; + + +struct bitvalue +{ + enum bittype { zeroone, field, failure } type; + union + { + unsigned int value; + struct known_bitfield *field; + }; + struct bitvalue *next; +}; + + +struct argname +{ + enum nametype { string, nfield } type; + union + { + char *str; + struct known_bitfield *field; + }; + struct argname *next; +}; + + +struct argument +{ + struct argname *name; + struct argument *next; +}; + + +struct instruction +{ + /* The byte encoding. */ + struct bitvalue *bytes; + + /* Prefix possible. */ + int repe; + int rep; + + /* Mnemonic. */ + char *mnemonic; + + /* Suffix. */ + enum { suffix_none = 0, suffix_w, suffix_w0, suffix_W, suffix_tttn, + suffix_w1, suffix_gg, suffix_GG, suffix_0g, suffix_gG, + suffix_predpd, suffix_predps, suffix_predsd, suffix_predss, + suffix_D } suffix; + + /* Flag set if modr/m is used. */ + int modrm; + + /* Operands. */ + struct operand + { + char *fct; + char *str; + int off1; + int off2; + int off3; + } operands[3]; + + struct instruction *next; +}; + + +struct synonym +{ + char *from; + char *to; +}; + + +struct suffix +{ + char *name; + int idx; +}; + + +struct argstring +{ + char *str; + int idx; +}; + + +static struct known_bitfield ax_reg = + { + .name = "ax", .bits = 0, .tmp = 0 + }; + +static struct known_bitfield dx_reg = + { + .name = "dx", .bits = 0, .tmp = 0 + }; + +static struct known_bitfield di_reg = + { + .name = "es_di", .bits = 0, .tmp = 0 + }; + +static struct known_bitfield si_reg = + { + .name = "ds_si", .bits = 0, .tmp = 0 + }; + +static struct known_bitfield bx_reg = + { + .name = "ds_bx", .bits = 0, .tmp = 0 + }; + + +static int bitfield_compare (const void *p1, const void *p2); +static void new_bitfield (char *name, unsigned long int num); +static void check_bits (struct bitvalue *value); +static int check_duplicates (struct bitvalue *val); +static int check_argsdef (struct bitvalue *bitval, struct argument *args); +static int check_bitsused (struct bitvalue *bitval, + struct known_bitfield *suffix, + struct argument *args); +static struct argname *combine (struct argname *name); +static void fillin_arg (struct bitvalue *bytes, struct argname *name, + struct instruction *instr, int n); +static void find_numbers (void); +static int compare_syn (const void *p1, const void *p2); +static int compare_suf (const void *p1, const void *p2); +static void instrtable_out (void); +#if 0 +static void create_mnemonic_table (void); +#endif + +static void *bitfields; +static struct instruction *instructions; +static size_t ninstructions; +static void *synonyms; +static void *suffixes; +static int nsuffixes; +static void *mnemonics; +size_t nmnemonics; +extern FILE *outfile; + +/* Number of bits used mnemonics. */ +#if 0 +static size_t best_mnemonic_bits; +#endif +%} + +%union { + unsigned long int num; + char *str; + char ch; + struct known_bitfield *field; + struct bitvalue *bit; + struct argname *name; + struct argument *arg; +} + +%token kMASK +%token kPREFIX +%token kSUFFIX +%token kSYNONYM +%token <str> kID +%token <num> kNUMBER +%token kPERCPERC +%token <str> kBITFIELD +%token <ch> kCHAR +%token kSPACE + +%type <bit> bit byte bytes +%type <field> bitfieldopt +%type <name> argcomp arg +%type <arg> args optargs + +%defines + +%% + +spec: masks kPERCPERC '\n' instrs + { + if (error_message_count != 0) + error (EXIT_FAILURE, 0, + "terminated due to previous error"); + + instrtable_out (); + } + ; + +masks: masks '\n' mask + | mask + ; + +mask: kMASK kBITFIELD kNUMBER + { new_bitfield ($2, $3); } + | kPREFIX kBITFIELD + { new_bitfield ($2, -1); } + | kSUFFIX kBITFIELD + { new_bitfield ($2, -2); } + | kSYNONYM kBITFIELD kBITFIELD + { + struct synonym *newp = xmalloc (sizeof (*newp)); + newp->from = $2; + newp->to = $3; + if (tfind (newp, &synonyms, compare_syn) != NULL) + error (0, 0, + "%d: duplicate definition for synonym '%s'", + i386_lineno, $2); + else if (tsearch ( newp, &synonyms, compare_syn) == NULL) + error (EXIT_FAILURE, 0, "tsearch"); + } + | + ; + +instrs: instrs '\n' instr + | instr + ; + +instr: bytes ':' bitfieldopt kID bitfieldopt optargs + { + if ($3 != NULL && strcmp ($3->name, "RE") != 0 + && strcmp ($3->name, "R") != 0) + { + error (0, 0, "%d: only 'R' and 'RE' prefix allowed", + i386_lineno - 1); + } + if (check_duplicates ($1) == 0 + && check_argsdef ($1, $6) == 0 + && check_bitsused ($1, $5, $6) == 0) + { + struct instruction *newp = xcalloc (sizeof (*newp), + 1); + if ($3 != NULL) + { + if (strcmp ($3->name, "RE") == 0) + newp->repe = 1; + else if (strcmp ($3->name, "R") == 0) + newp->rep = 1; + } + + newp->bytes = $1; + newp->mnemonic = $4; + if (newp->mnemonic != (void *) -1l + && tfind ($4, &mnemonics, + (comparison_fn_t) strcmp) == NULL) + { + if (tsearch ($4, &mnemonics, + (comparison_fn_t) strcmp) == NULL) + error (EXIT_FAILURE, errno, "tsearch"); + ++nmnemonics; + } + + if ($5 != NULL) + { + if (strcmp ($5->name, "w") == 0) + newp->suffix = suffix_w; + else if (strcmp ($5->name, "w0") == 0) + newp->suffix = suffix_w0; + else if (strcmp ($5->name, "tttn") == 0) + newp->suffix = suffix_tttn; + else if (strcmp ($5->name, "w1") == 0) + newp->suffix = suffix_w1; + else if (strcmp ($5->name, "W") == 0) + newp->suffix = suffix_W; + else if (strcmp ($5->name, "gg") == 0) + newp->suffix = suffix_gg; + else if (strcmp ($5->name, "GG") == 0) + newp->suffix = suffix_GG; + else if (strcmp ($5->name, "0g") == 0) + newp->suffix = suffix_0g; + else if (strcmp ($5->name, "gG") == 0) + newp->suffix = suffix_gG; + else if (strcmp ($5->name, "predpd") == 0) + newp->suffix = suffix_predpd; + else if (strcmp ($5->name, "predps") == 0) + newp->suffix = suffix_predps; + else if (strcmp ($5->name, "predsd") == 0) + newp->suffix = suffix_predsd; + else if (strcmp ($5->name, "predss") == 0) + newp->suffix = suffix_predss; + else if (strcmp ($5->name, "D") == 0) + newp->suffix = suffix_D; + else + error (EXIT_FAILURE, 0, + "%s: %d: unknown suffix '%s'", + infname, i386_lineno - 1, $5->name); + + struct suffix search = { .name = $5->name }; + if (tfind (&search, &suffixes, compare_suf) + == NULL) + { + struct suffix *ns = xmalloc (sizeof (*ns)); + ns->name = $5->name; + ns->idx = ++nsuffixes; + if (tsearch (ns, &suffixes, compare_suf) + == NULL) + error (EXIT_FAILURE, errno, "tsearch"); + } + } + + struct argument *args = $6; + int n = 0; + while (args != NULL) + { + fillin_arg ($1, args->name, newp, n); + + args = args->next; + ++n; + } + + newp->next = instructions; + instructions = newp; + ++ninstructions; + } + } + | + ; + +bitfieldopt: kBITFIELD + { + struct known_bitfield search; + search.name = $1; + struct known_bitfield **res; + res = tfind (&search, &bitfields, bitfield_compare); + if (res == NULL) + { + error (0, 0, "%d: unknown bitfield '%s'", + i386_lineno, search.name); + $$ = NULL; + } + else + $$ = *res; + } + | + { $$ = NULL; } + ; + +bytes: bytes ',' byte + { + check_bits ($3); + + struct bitvalue *runp = $1; + while (runp->next != NULL) + runp = runp->next; + runp->next = $3; + $$ = $1; + } + | byte + { + check_bits ($1); + $$ = $1; + } + ; + +byte: byte bit + { + struct bitvalue *runp = $1; + while (runp->next != NULL) + runp = runp->next; + runp->next = $2; + $$ = $1; + } + | bit + { $$ = $1; } + ; + +bit: '0' + { + $$ = xmalloc (sizeof (struct bitvalue)); + $$->type = zeroone; + $$->value = 0; + $$->next = NULL; + } + | '1' + { + $$ = xmalloc (sizeof (struct bitvalue)); + $$->type = zeroone; + $$->value = 1; + $$->next = NULL; + } + | kBITFIELD + { + $$ = xmalloc (sizeof (struct bitvalue)); + struct known_bitfield search; + search.name = $1; + struct known_bitfield **res; + res = tfind (&search, &bitfields, bitfield_compare); + if (res == NULL) + { + error (0, 0, "%d: unknown bitfield '%s'", + i386_lineno, search.name); + $$->type = failure; + } + else + { + $$->type = field; + $$->field = *res; + } + $$->next = NULL; + } + ; + +optargs: kSPACE args + { $$ = $2; } + | + { $$ = NULL; } + ; + +args: args ',' arg + { + struct argument *runp = $1; + while (runp->next != NULL) + runp = runp->next; + runp->next = xmalloc (sizeof (struct argument)); + runp->next->name = combine ($3); + runp->next->next = NULL; + $$ = $1; + } + | arg + { + $$ = xmalloc (sizeof (struct argument)); + $$->name = combine ($1); + $$->next = NULL; + } + ; + +arg: arg argcomp + { + struct argname *runp = $1; + while (runp->next != NULL) + runp = runp->next; + runp->next = $2; + $$ = $1; + } + | argcomp + { $$ = $1; } + ; +argcomp: kBITFIELD + { + $$ = xmalloc (sizeof (struct argname)); + $$->type = nfield; + $$->next = NULL; + + struct known_bitfield search; + search.name = $1; + struct known_bitfield **res; + res = tfind (&search, &bitfields, bitfield_compare); + if (res == NULL) + { + if (strcmp ($1, "ax") == 0) + $$->field = &ax_reg; + else if (strcmp ($1, "dx") == 0) + $$->field = &dx_reg; + else if (strcmp ($1, "es_di") == 0) + $$->field = &di_reg; + else if (strcmp ($1, "ds_si") == 0) + $$->field = &si_reg; + else if (strcmp ($1, "ds_bx") == 0) + $$->field = &bx_reg; + else + { + error (0, 0, "%d: unknown bitfield '%s'", + i386_lineno, search.name); + $$->field = NULL; + } + } + else + $$->field = *res; + } + | kCHAR + { + $$ = xmalloc (sizeof (struct argname)); + $$->type = string; + $$->next = NULL; + $$->str = xmalloc (2); + $$->str[0] = $1; + $$->str[1] = '\0'; + } + | kID + { + $$ = xmalloc (sizeof (struct argname)); + $$->type = string; + $$->next = NULL; + $$->str = $1; + } + | ':' + { + $$ = xmalloc (sizeof (struct argname)); + $$->type = string; + $$->next = NULL; + $$->str = xmalloc (2); + $$->str[0] = ':'; + $$->str[1] = '\0'; + } + ; + +%% + +static void +yyerror (const char *s) +{ + error (0, 0, gettext ("while reading i386 CPU description: %s at line %d"), + gettext (s), i386_lineno); +} + + +static int +bitfield_compare (const void *p1, const void *p2) +{ + struct known_bitfield *f1 = (struct known_bitfield *) p1; + struct known_bitfield *f2 = (struct known_bitfield *) p2; + + return strcmp (f1->name, f2->name); +} + + +static void +new_bitfield (char *name, unsigned long int num) +{ + struct known_bitfield *newp = xmalloc (sizeof (struct known_bitfield)); + newp->name = name; + newp->bits = num; + newp->tmp = 0; + + if (tfind (newp, &bitfields, bitfield_compare) != NULL) + { + error (0, 0, "%d: duplicated definition of bitfield '%s'", + i386_lineno, name); + free (name); + return; + } + + if (tsearch (newp, &bitfields, bitfield_compare) == NULL) + error (EXIT_FAILURE, errno, "%d: cannot insert new bitfield '%s'", + i386_lineno, name); +} + + +/* Check that the number of bits is a multiple of 8. */ +static void +check_bits (struct bitvalue *val) +{ + struct bitvalue *runp = val; + unsigned int total = 0; + + while (runp != NULL) + { + if (runp->type == zeroone) + ++total; + else if (runp->field == NULL) + /* No sense doing anything, the field is not known. */ + return; + else + total += runp->field->bits; + + runp = runp->next; + } + + if (total % 8 != 0) + { + struct obstack os; + obstack_init (&os); + + while (val != NULL) + { + if (val->type == zeroone) + obstack_printf (&os, "%u", val->value); + else + obstack_printf (&os, "{%s}", val->field->name); + val = val->next; + } + obstack_1grow (&os, '\0'); + + error (0, 0, "%d: field '%s' not a multiple of 8 bits in size", + i386_lineno, (char *) obstack_finish (&os)); + + obstack_free (&os, NULL); + } +} + + +static int +check_duplicates (struct bitvalue *val) +{ + static int testcnt; + ++testcnt; + + int result = 0; + while (val != NULL) + { + if (val->type == field && val->field != NULL) + { + if (val->field->tmp == testcnt) + { + error (0, 0, "%d: bitfield '%s' used more than once", + i386_lineno - 1, val->field->name); + result = 1; + } + val->field->tmp = testcnt; + } + + val = val->next; + } + + return result; +} + + +static int +check_argsdef (struct bitvalue *bitval, struct argument *args) +{ + int result = 0; + + while (args != NULL) + { + for (struct argname *name = args->name; name != NULL; name = name->next) + if (name->type == nfield && name->field != NULL + && name->field != &ax_reg && name->field != &dx_reg + && name->field != &di_reg && name->field != &si_reg + && name->field != &bx_reg) + { + struct bitvalue *runp = bitval; + + while (runp != NULL) + if (runp->type == field && runp->field == name->field) + break; + else + runp = runp->next; + + if (runp == NULL) + { + error (0, 0, "%d: unknown bitfield '%s' used in output format", + i386_lineno - 1, name->field->name); + result = 1; + } + } + + args = args->next; + } + + return result; +} + + +static int +check_bitsused (struct bitvalue *bitval, struct known_bitfield *suffix, + struct argument *args) +{ + int result = 0; + + while (bitval != NULL) + { + if (bitval->type == field && bitval->field != NULL + && bitval->field != suffix + /* {w} is handled special. */ + && strcmp (bitval->field->name, "w") != 0) + { + struct argument *runp; + for (runp = args; runp != NULL; runp = runp->next) + { + struct argname *name = runp->name; + + while (name != NULL) + if (name->type == nfield && name->field == bitval->field) + break; + else + name = name->next; + + if (name != NULL) + break; + } + +#if 0 + if (runp == NULL) + { + error (0, 0, "%d: bitfield '%s' not used", + i386_lineno - 1, bitval->field->name); + result = 1; + } +#endif + } + + bitval = bitval->next; + } + + return result; +} + + +static struct argname * +combine (struct argname *name) +{ + struct argname *last_str = NULL; + for (struct argname *runp = name; runp != NULL; runp = runp->next) + { + if (runp->type == string) + { + if (last_str == NULL) + last_str = runp; + else + { + last_str->str = xrealloc (last_str->str, + strlen (last_str->str) + + strlen (runp->str) + 1); + strcat (last_str->str, runp->str); + last_str->next = runp->next; + } + } + else + last_str = NULL; + } + return name; +} + + +#define obstack_grow_str(ob, str) obstack_grow (ob, str, strlen (str)) + + +static void +fillin_arg (struct bitvalue *bytes, struct argname *name, + struct instruction *instr, int n) +{ + static struct obstack ob; + static int initialized; + if (! initialized) + { + initialized = 1; + obstack_init (&ob); + } + + struct argname *runp = name; + int cnt = 0; + while (runp != NULL) + { + /* We ignore strings in the function name. */ + if (runp->type == string) + { + if (instr->operands[n].str != NULL) + error (EXIT_FAILURE, 0, + "%d: cannot have more than one string parameter", + i386_lineno - 1); + + instr->operands[n].str = runp->str; + } + else + { + assert (runp->type == nfield); + + /* Construct the function name. */ + if (cnt++ > 0) + obstack_1grow (&ob, '$'); + + if (runp->field == NULL) + /* Add some string which contains invalid characters. */ + obstack_grow_str (&ob, "!!!INVALID!!!"); + else + obstack_grow_str (&ob, runp->field->name); + + /* Now compute the bit offset of the field. */ + struct bitvalue *b = bytes; + int bitoff = 0; + if (runp->field != NULL) + while (b != NULL) + { + if (b->type == field && b->field != NULL) + { + if (strcmp (b->field->name, runp->field->name) == 0) + break; + bitoff += b->field->bits; + } + else + ++bitoff; + + b = b->next; + } + if (instr->operands[n].off1 == 0) + instr->operands[n].off1 = bitoff; + else if (instr->operands[n].off2 == 0) + instr->operands[n].off2 = bitoff; + else if (instr->operands[n].off3 == 0) + instr->operands[n].off3 = bitoff; + else + error (EXIT_FAILURE, 0, + "%d: cannot have more than three fields in parameter", + i386_lineno - 1); + + if (runp->field != NULL + && strncasecmp (runp->field->name, "mod", 3) == 0) + instr->modrm = 1; + } + + runp = runp->next; + } + if (obstack_object_size (&ob) == 0) + obstack_grow_str (&ob, "string"); + obstack_1grow (&ob, '\0'); + char *fct = obstack_finish (&ob); + + struct synonym search = { .from = fct }; + struct synonym **res = tfind (&search, &synonyms, compare_syn); + if (res != NULL) + fct = (*res)->to; + + instr->operands[n].fct = fct; +} + + +#if 0 +static void +nameout (const void *nodep, VISIT value, int level) +{ + if (value == leaf || value == postorder) + printf (" %s\n", *(const char **) nodep); +} +#endif + + +static int +compare_argstring (const void *p1, const void *p2) +{ + const struct argstring *a1 = (const struct argstring *) p1; + const struct argstring *a2 = (const struct argstring *) p2; + + return strcmp (a1->str, a2->str); +} + + +static int maxoff[3][3]; +static int minoff[3][3] = { { 1000, 1000, 1000 }, + { 1000, 1000, 1000 }, + { 1000, 1000, 1000 } }; +static int nbitoff[3][3]; +static void *fct_names[3]; +static int nbitfct[3]; +static int nbitsuf; +static void *strs[3]; +static int nbitstr[3]; +static int total_bits = 2; // Already counted the rep/repe bits. + +static void +find_numbers (void) +{ + int nfct_names[3] = { 0, 0, 0 }; + int nstrs[3] = { 0, 0, 0 }; + + /* We reverse the order of the instruction list while processing it. + Later phases need it in the order in which the input file has + them. */ + struct instruction *reversed = NULL; + + struct instruction *runp = instructions; + while (runp != NULL) + { + for (int i = 0; i < 3; ++i) + if (runp->operands[i].fct != NULL) + { + struct argstring search = { .str = runp->operands[i].fct }; + if (tfind (&search, &fct_names[i], compare_argstring) == NULL) + { + struct argstring *newp = xmalloc (sizeof (*newp)); + newp->str = runp->operands[i].fct; + newp->idx = 0; + if (tsearch (newp, &fct_names[i], compare_argstring) == NULL) + error (EXIT_FAILURE, errno, "tsearch"); + ++nfct_names[i]; + } + + if (runp->operands[i].str != NULL) + { + search.str = runp->operands[i].str; + if (tfind (&search, &strs[i], compare_argstring) == NULL) + { + struct argstring *newp = xmalloc (sizeof (*newp)); + newp->str = runp->operands[i].str; + newp->idx = 0; + if (tsearch (newp, &strs[i], compare_argstring) == NULL) + error (EXIT_FAILURE, errno, "tsearch"); + ++nstrs[i]; + } + } + + maxoff[i][0] = MAX (maxoff[i][0], runp->operands[i].off1); + maxoff[i][1] = MAX (maxoff[i][1], runp->operands[i].off2); + maxoff[i][2] = MAX (maxoff[i][2], runp->operands[i].off3); + + if (runp->operands[i].off1 > 0) + minoff[i][0] = MIN (minoff[i][0], runp->operands[i].off1); + if (runp->operands[i].off2 > 0) + minoff[i][1] = MIN (minoff[i][1], runp->operands[i].off2); + if (runp->operands[i].off3 > 0) + minoff[i][2] = MIN (minoff[i][2], runp->operands[i].off3); + } + + struct instruction *old = runp; + runp = runp->next; + + old->next = reversed; + reversed = old; + } + instructions = reversed; + + int d; + int c; + for (int i = 0; i < 3; ++i) + { + // printf ("min1 = %d, min2 = %d, min3 = %d\n", minoff[i][0], minoff[i][1], minoff[i][2]); + // printf ("max1 = %d, max2 = %d, max3 = %d\n", maxoff[i][0], maxoff[i][1], maxoff[i][2]); + + if (minoff[i][0] == 1000) + nbitoff[i][0] = 0; + else + { + nbitoff[i][0] = 1; + d = maxoff[i][0] - minoff[i][0]; + c = 1; + while (c < d) + { + ++nbitoff[i][0]; + c *= 2; + } + total_bits += nbitoff[i][0]; + } + + if (minoff[i][1] == 1000) + nbitoff[i][1] = 0; + else + { + nbitoff[i][1] = 1; + d = maxoff[i][1] - minoff[i][1]; + c = 1; + while (c < d) + { + ++nbitoff[i][1]; + c *= 2; + } + total_bits += nbitoff[i][1]; + } + + if (minoff[i][2] == 1000) + nbitoff[i][2] = 0; + else + { + nbitoff[i][2] = 1; + d = maxoff[i][2] - minoff[i][2]; + c = 1; + while (c < d) + { + ++nbitoff[i][2]; + c *= 2; + } + total_bits += nbitoff[i][2]; + } + // printf ("off1 = %d, off2 = %d, off3 = %d\n", nbitoff[i][0], nbitoff[i][1], nbitoff[i][2]); + + nbitfct[i] = 1; + d = nfct_names[i]; + c = 1; + while (c < d) + { + ++nbitfct[i]; + c *= 2; + } + total_bits += nbitfct[i]; + // printf ("%d fct[%d], %d bits\n", nfct_names[i], i, nbitfct[i]); + + if (nstrs[i] != 0) + { + nbitstr[i] = 1; + d = nstrs[i]; + c = 1; + while (c < d) + { + ++nbitstr[i]; + c *= 2; + } + total_bits += nbitstr[i]; + } + + // twalk (fct_names[i], nameout); + } + + nbitsuf = 0; + d = nsuffixes; + c = 1; + while (c < d) + { + ++nbitsuf; + c *= 2; + } + total_bits += nbitsuf; + // printf ("%d suffixes, %d bits\n", nsuffixes, nbitsuf); +} + + +static int +compare_syn (const void *p1, const void *p2) +{ + const struct synonym *s1 = (const struct synonym *) p1; + const struct synonym *s2 = (const struct synonym *) p2; + + return strcmp (s1->from, s2->from); +} + + +static int +compare_suf (const void *p1, const void *p2) +{ + const struct suffix *s1 = (const struct suffix *) p1; + const struct suffix *s2 = (const struct suffix *) p2; + + return strcmp (s1->name, s2->name); +} + + +static int count_op_str; +static void +print_op_str (const void *nodep, VISIT value, + int level __attribute__ ((unused))) +{ + if (value == leaf || value == postorder) + { + fprintf (outfile, " \"%s\",\n", (*(struct argstring **) nodep)->str); + (*(struct argstring **) nodep)->idx = ++count_op_str; + } +} + + +static void +print_op_fct (const void *nodep, VISIT value, + int level __attribute__ ((unused))) +{ + if (value == leaf || value == postorder) + { + fprintf (outfile, " FCT_%s,\n", (*(struct argstring **) nodep)->str); + (*(struct argstring **) nodep)->idx = ++count_op_str; + } +} + + +static void +instrtable_out (void) +{ + find_numbers (); + +#if 0 + create_mnemonic_table (); + + fprintf (outfile, "#define MNEMONIC_BITS %zu\n", best_mnemonic_bits); +#else + fprintf (outfile, "#define MNEMONIC_BITS %ld\n", + lrint (ceil (log2 (NMNES)))); +#endif + fprintf (outfile, "#define SUFFIX_BITS %d\n", nbitsuf); + for (int i = 0; i < 3; ++i) + { + fprintf (outfile, "#define FCT%d_BITS %d\n", i + 1, nbitfct[i]); + if (nbitstr[i] != 0) + fprintf (outfile, "#define STR%d_BITS %d\n", i + 1, nbitstr[i]); + fprintf (outfile, "#define OFF%d_1_BITS %d\n", i + 1, nbitoff[i][0]); + fprintf (outfile, "#define OFF%d_1_BIAS %d\n", i + 1, minoff[i][0]); + if (nbitoff[i][1] != 0) + { + fprintf (outfile, "#define OFF%d_2_BITS %d\n", i + 1, nbitoff[i][1]); + fprintf (outfile, "#define OFF%d_2_BIAS %d\n", i + 1, minoff[i][1]); + } + if (nbitoff[i][2] != 0) + { + fprintf (outfile, "#define OFF%d_3_BITS %d\n", i + 1, nbitoff[i][2]); + fprintf (outfile, "#define OFF%d_3_BIAS %d\n", i + 1, minoff[i][2]); + } + } + + fputs ("\n#include <i386_data.h>\n\n", outfile); + + +#define APPEND(a, b) APPEND_ (a, b) +#define APPEND_(a, b) a##b +#define EMIT_SUFFIX(suf) \ + fprintf (outfile, "#define suffix_%s %d\n", #suf, APPEND (suffix_, suf)) + EMIT_SUFFIX (none); + EMIT_SUFFIX (w); + EMIT_SUFFIX (w0); + EMIT_SUFFIX (W); + EMIT_SUFFIX (tttn); + EMIT_SUFFIX (D); + EMIT_SUFFIX (w1); + + fputc_unlocked ('\n', outfile); + + for (int i = 0; i < 3; ++i) + { + /* Functions. */ + count_op_str = 0; + fprintf (outfile, "static opfct_t op%d_fct[] =\n{\n NULL,\n", i + 1); + twalk (fct_names[i], print_op_fct); + fputs ("};\n", outfile); + + /* The operand strings. */ + if (nbitstr[i] != 0) + { + count_op_str = 0; + fprintf (outfile, "static const char *op%d_str[] =\n{\n NULL,\n", + i + 1); + twalk (strs[i], print_op_str); + fputs ("};\n", outfile); + } + } + + + fputs ("static const struct instr_enc instrtab[] =\n{\n", outfile); + struct instruction *instr; + for (instr = instructions; instr != NULL; instr = instr->next) + { + fputs (" {", outfile); + if (instr->mnemonic == (void *) -1l) + fputs (" .mnemonic = MNE_INVALID,", outfile); + else + fprintf (outfile, " .mnemonic = MNE_%s,", instr->mnemonic); + fprintf (outfile, " .rep = %d,", instr->rep); + fprintf (outfile, " .repe = %d,", instr->repe); + fprintf (outfile, " .suffix = %d,", instr->suffix); + fprintf (outfile, " .modrm = %d,", instr->modrm); + + for (int i = 0; i < 3; ++i) + { + int idx = 0; + if (instr->operands[i].fct != NULL) + { + struct argstring search = { .str = instr->operands[i].fct }; + struct argstring **res = tfind (&search, &fct_names[i], + compare_argstring); + assert (res != NULL); + idx = (*res)->idx; + } + fprintf (outfile, " .fct%d = %d,", i + 1, idx); + + idx = 0; + if (instr->operands[i].str != NULL) + { + struct argstring search = { .str = instr->operands[i].str }; + struct argstring **res = tfind (&search, &strs[i], + compare_argstring); + assert (res != NULL); + idx = (*res)->idx; + } + if (nbitstr[i] != 0) + fprintf (outfile, " .str%d = %d,", i + 1, idx); + + fprintf (outfile, " .off%d_1 = %d,", i + 1, + MAX (0, instr->operands[i].off1 - minoff[i][0])); + + if (nbitoff[i][1] != 0) + fprintf (outfile, " .off%d_2 = %d,", i + 1, + MAX (0, instr->operands[i].off2 - minoff[i][1])); + + if (nbitoff[i][2] != 0) + fprintf (outfile, " .off%d_3 = %d,", i + 1, + MAX (0, instr->operands[i].off3 - minoff[i][2])); + } + + fputs (" },\n", outfile); + } + fputs ("};\n", outfile); + + fputs ("static const uint8_t match_data[] =\n{\n", outfile); + size_t cnt = 0; + for (instr = instructions; instr != NULL; instr = instr->next, ++cnt) + { + /* First count the number of bytes. */ + size_t totalbits = 0; + size_t zerobits = 0; + struct bitvalue *b = instr->bytes; + while (b != NULL) + { + if (b->type == zeroone) + { + ++totalbits; + zerobits = 0; + } + else + { + totalbits += b->field->bits; + /* We must always count the mod/rm byte. */ + if (strncasecmp (b->field->name, "mod", 3) == 0) + zerobits = 0; + else + zerobits += b->field->bits; + } + b = b->next; + } + size_t nbytes = (totalbits - zerobits + 7) / 8; + assert (nbytes > 0); + + fprintf (outfile, " %#zx,", nbytes); + + /* Now create the mask and byte values. */ + uint8_t byte = 0; + uint8_t mask = 0; + int nbits = 0; + b = instr->bytes; + while (b != NULL) + { + if (b->type == zeroone) + { + byte = (byte << 1) | b->value; + mask = (mask << 1) | 1; + if (++nbits == 8) + { + fprintf (outfile, " %#" PRIx8 ", %#" PRIx8 ",", mask, byte); + byte = mask = nbits = 0; + if (--nbytes == 0) + break; + } + } + else + { + unsigned long int remaining = b->field->bits; + while (nbits + remaining > 8) + { + fprintf (outfile, " %#" PRIx8 ", %#" PRIx8 ",", + mask << (8 - nbits), byte << (8 - nbits)); + remaining = nbits + remaining - 8; + byte = mask = nbits = 0; + if (--nbytes == 0) + break; + } + byte <<= remaining; + mask <<= remaining; + nbits += remaining; + if (nbits == 8) + { + fprintf (outfile, " %#" PRIx8 ", %#" PRIx8 ",", mask, byte); + byte = mask = nbits = 0; + if (--nbytes == 0) + break; + } + } + b = b->next; + } + + fprintf (outfile, " %#zx, %#zx,\n", cnt & 0xff, cnt >> 8); + } + fputs ("};\n", outfile); +} + + +#if 0 +static size_t mnemonic_maxlen; +static size_t mnemonic_minlen; +static size_t +which_chars (const char *str[], size_t nstr) +{ + char used_char[256]; + memset (used_char, '\0', sizeof (used_char)); + mnemonic_maxlen = 0; + mnemonic_minlen = 10000; + for (size_t cnt = 0; cnt < nstr; ++cnt) + { + const unsigned char *cp = (const unsigned char *) str[cnt]; + mnemonic_maxlen = MAX (mnemonic_maxlen, strlen ((char *) cp)); + mnemonic_minlen = MIN (mnemonic_minlen, strlen ((char *) cp)); + do + used_char[*cp++] = 1; + while (*cp != '\0'); + } + size_t nused_char = 0; + for (size_t cnt = 0; cnt < 256; ++cnt) + if (used_char[cnt] != 0) + ++nused_char; + return nused_char; +} + + +static const char **mnemonic_strs; +static size_t nmnemonic_strs; +static void +add_mnemonics (const void *nodep, VISIT value, + int level __attribute__ ((unused))) +{ + if (value == leaf || value == postorder) + mnemonic_strs[nmnemonic_strs++] = *(const char **) nodep; +} + + +struct charfreq +{ + char ch; + int freq; +}; +static struct charfreq pfxfreq[256]; +static struct charfreq sfxfreq[256]; + + +static int +compare_freq (const void *p1, const void *p2) +{ + const struct charfreq *c1 = (const struct charfreq *) p1; + const struct charfreq *c2 = (const struct charfreq *) p2; + + if (c1->freq > c2->freq) + return -1; + if (c1->freq < c2->freq) + return 1; + return 0; +} + + +static size_t +compute_pfxfreq (const char *str[], size_t nstr) +{ + memset (pfxfreq, '\0', sizeof (pfxfreq)); + + for (size_t i = 0; i < nstr; ++i) + pfxfreq[i].ch = i; + + for (size_t i = 0; i < nstr; ++i) + ++pfxfreq[*((const unsigned char *) str[i])].freq; + + qsort (pfxfreq, 256, sizeof (struct charfreq), compare_freq); + + size_t n = 0; + while (n < 256 && pfxfreq[n].freq != 0) + ++n; + return n; +} + + +struct strsnlen +{ + const char *str; + size_t len; +}; + +static size_t +compute_sfxfreq (size_t nstr, struct strsnlen *strsnlen) +{ + memset (sfxfreq, '\0', sizeof (sfxfreq)); + + for (size_t i = 0; i < nstr; ++i) + sfxfreq[i].ch = i; + + for (size_t i = 0; i < nstr; ++i) + ++sfxfreq[((const unsigned char *) strchrnul (strsnlen[i].str, '\0'))[-1]].freq; + + qsort (sfxfreq, 256, sizeof (struct charfreq), compare_freq); + + size_t n = 0; + while (n < 256 && sfxfreq[n].freq != 0) + ++n; + return n; +} + + +static void +create_mnemonic_table (void) +{ + mnemonic_strs = xmalloc (nmnemonics * sizeof (char *)); + + twalk (mnemonics, add_mnemonics); + + (void) which_chars (mnemonic_strs, nmnemonic_strs); + + size_t best_so_far = 100000000; + char *best_prefix = NULL; + char *best_suffix = NULL; + char *best_table = NULL; + size_t best_table_size = 0; + size_t best_table_bits = 0; + size_t best_prefix_bits = 0; + + /* We can precompute the prefix characters. */ + size_t npfx_char = compute_pfxfreq (mnemonic_strs, nmnemonic_strs); + + /* Compute best size for string representation including explicit NUL. */ + for (size_t pfxbits = 0; (1u << pfxbits) < 2 * npfx_char; ++pfxbits) + { + char prefix[1 << pfxbits]; + size_t i; + for (i = 0; i < (1u << pfxbits) - 1; ++i) + prefix[i] = pfxfreq[i].ch; + prefix[i] = '\0'; + + struct strsnlen strsnlen[nmnemonic_strs]; + + for (i = 0; i < nmnemonic_strs; ++i) + { + if (strchr (prefix, *mnemonic_strs[i]) != NULL) + strsnlen[i].str = mnemonic_strs[i] + 1; + else + strsnlen[i].str = mnemonic_strs[i]; + strsnlen[i].len = strlen (strsnlen[i].str); + } + + /* With the prefixes gone, try to combine strings. */ + size_t nstrsnlen = 1; + for (i = 1; i < nmnemonic_strs; ++i) + { + size_t j; + for (j = 0; j < nstrsnlen; ++j) + if (strsnlen[i].len > strsnlen[j].len + && strcmp (strsnlen[j].str, + strsnlen[i].str + (strsnlen[i].len + - strsnlen[j].len)) == 0) + { + strsnlen[j] = strsnlen[i]; + break; + } + else if (strsnlen[i].len < strsnlen[j].len + && strcmp (strsnlen[i].str, + strsnlen[j].str + (strsnlen[j].len + - strsnlen[i].len)) == 0) + break; +; + if (j == nstrsnlen) + strsnlen[nstrsnlen++] = strsnlen[i]; + } + + size_t nsfx_char = compute_sfxfreq (nstrsnlen, strsnlen); + + for (size_t sfxbits = 0; (1u << sfxbits) < 2 * nsfx_char; ++sfxbits) + { + char suffix[1 << sfxbits]; + + for (i = 0; i < (1u << sfxbits) - 1; ++i) + suffix[i] = sfxfreq[i].ch; + suffix[i] = '\0'; + + size_t newlen[nstrsnlen]; + + for (i = 0; i < nstrsnlen; ++i) + if (strchr (suffix, strsnlen[i].str[strsnlen[i].len - 1]) != NULL) + newlen[i] = strsnlen[i].len - 1; + else + newlen[i] = strsnlen[i].len; + + char charused[256]; + memset (charused, '\0', sizeof (charused)); + size_t ncharused = 0; + + const char *tablestr[nstrsnlen]; + size_t ntablestr = 1; + tablestr[0] = strsnlen[0].str; + size_t table = newlen[0] + 1; + for (i = 1; i < nstrsnlen; ++i) + { + size_t j; + for (j = 0; j < ntablestr; ++j) + if (newlen[i] > newlen[j] + && memcmp (tablestr[j], + strsnlen[i].str + (newlen[i] - newlen[j]), + newlen[j]) == 0) + { + table += newlen[i] - newlen[j]; + tablestr[j] = strsnlen[i].str; + newlen[j] = newlen[i]; + break; + } + else if (newlen[i] < newlen[j] + && memcmp (strsnlen[i].str, + tablestr[j] + (newlen[j] - newlen[i]), + newlen[i]) == 0) + break; + + if (j == ntablestr) + { + table += newlen[i] + 1; + tablestr[ntablestr] = strsnlen[i].str; + newlen[ntablestr] = newlen[i]; + + ++ntablestr; + } + + for (size_t x = 0; x < newlen[j]; ++x) + if (charused[((const unsigned char *) tablestr[j])[x]]++ == 0) + ++ncharused; + } + + size_t ncharused_bits = 0; + i = 1; + while (i < ncharused) + { + i *= 2; + ++ncharused_bits; + } + + size_t table_bits = 0; + i = 1; + while (i < table) + { + i *= 2; + ++table_bits; + } + + size_t mnemonic_bits = table_bits + pfxbits + sfxbits; + size_t new_total = (((table + 7) / 8) * ncharused_bits + ncharused + + (pfxbits == 0 ? 0 : (1 << pfxbits) - 1) + + (sfxbits == 0 ? 0 : (1 << sfxbits) - 1) + + (((total_bits + mnemonic_bits + 7) / 8) + * ninstructions)); + + if (new_total < best_so_far) + { + best_so_far = new_total; + best_mnemonic_bits = mnemonic_bits; + + free (best_suffix); + best_suffix = xstrdup (suffix); + + free (best_prefix); + best_prefix = xstrdup (prefix); + best_prefix_bits = pfxbits; + + best_table_size = table; + best_table_bits = table_bits; + char *cp = best_table = xrealloc (best_table, table); + for (i = 0; i < ntablestr; ++i) + { + assert (cp + newlen[i] + 1 <= best_table + table); + cp = mempcpy (cp, tablestr[i], newlen[i]); + *cp++ = '\0'; + } + assert (cp == best_table + table); + } + } + } + + fputs ("static const char mnemonic_table[] =\n\"", outfile); + for (size_t i = 0; i < best_table_size; ++i) + { + if (((i + 1) % 60) == 0) + fputs ("\"\n\"", outfile); + if (!isascii (best_table[i]) || !isprint (best_table[i])) + fprintf (outfile, "\\%03o", best_table[i]); + else + fputc (best_table[i], outfile); + } + fputs ("\";\n", outfile); + + if (best_prefix[0] != '\0') + fprintf (outfile, + "static const char prefix[%zu] = \"%s\";\n" + "#define PREFIXCHAR_BITS %zu\n", + strlen (best_prefix), best_prefix, best_prefix_bits); + else + fputs ("#define NO_PREFIX\n", outfile); + + if (best_suffix[0] != '\0') + fprintf (outfile, "static const char suffix[%zu] = \"%s\";\n", + strlen (best_suffix), best_suffix); + else + fputs ("#define NO_SUFFIX\n", outfile); + + for (size_t i = 0; i < nmnemonic_strs; ++i) + { + const char *mne = mnemonic_strs[i]; + + size_t pfxval = 0; + char *cp = strchr (best_prefix, *mne); + if (cp != NULL) + { + pfxval = 1 + (cp - best_prefix); + ++mne; + } + + size_t l = strlen (mne); + + size_t sfxval = 0; + cp = strchr (best_suffix, mne[l - 1]); + if (cp != NULL) + { + sfxval = 1 + (cp - best_suffix); + --l; + } + + char *off = memmem (best_table, best_table_size, mne, l); + while (off[l] != '\0') + { + off = memmem (off + 1, best_table_size, mne, l); + assert (off != NULL); + } + + fprintf (outfile, "#define MNE_%s %#zx\n", + mnemonic_strs[i], + (off - best_table) + + ((pfxval + (sfxval << best_prefix_bits)) << best_table_bits)); + } +} +#endif |