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