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