libcpu/i386_parse.y

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