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.  */
52static void yyerror (const char *s);
53
54extern int yylex (void);
55extern int i386_lineno;
56extern char *infname;
57
58
59struct known_bitfield
60{
61  char *name;
62  unsigned long int bits;
63  int tmp;
64};
65
66
67struct 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
79struct 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
91struct argument
92{
93  struct argname *name;
94  struct argument *next;
95};
96
97
98struct 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
131struct synonym
132{
133  char *from;
134  char *to;
135};
136
137
138struct suffix
139{
140  char *name;
141  int idx;
142};
143
144
145struct argstring
146{
147  char *str;
148  int idx;
149  int off;
150};
151
152
153static struct known_bitfield ax_reg =
154  {
155    .name = "ax", .bits = 0, .tmp = 0
156  };
157
158static struct known_bitfield dx_reg =
159  {
160    .name = "dx", .bits = 0, .tmp = 0
161  };
162
163static struct known_bitfield di_reg =
164  {
165    .name = "es_di", .bits = 0, .tmp = 0
166  };
167
168static struct known_bitfield si_reg =
169  {
170    .name = "ds_si", .bits = 0, .tmp = 0
171  };
172
173static struct known_bitfield bx_reg =
174  {
175    .name = "ds_bx", .bits = 0, .tmp = 0
176  };
177
178
179static int bitfield_compare (const void *p1, const void *p2);
180static void new_bitfield (char *name, unsigned long int num);
181static void check_bits (struct bitvalue *value);
182static int check_duplicates (struct bitvalue *val);
183static int check_argsdef (struct bitvalue *bitval, struct argument *args);
184static int check_bitsused (struct bitvalue *bitval,
185			   struct known_bitfield *suffix,
186			   struct argument *args);
187static struct argname *combine (struct argname *name);
188static void fillin_arg (struct bitvalue *bytes, struct argname *name,
189			struct instruction *instr, int n);
190static void find_numbers (void);
191static int compare_syn (const void *p1, const void *p2);
192static int compare_suf (const void *p1, const void *p2);
193static void instrtable_out (void);
194#if 0
195static void create_mnemonic_table (void);
196#endif
197
198static void *bitfields;
199static struct instruction *instructions;
200static size_t ninstructions;
201static void *synonyms;
202static void *suffixes;
203static int nsuffixes;
204static void *mnemonics;
205size_t nmnemonics;
206extern FILE *outfile;
207
208/* Number of bits used mnemonics.  */
209#if 0
210static 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
244spec:		  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
254masks:		  masks '\n' mask
255		| mask
256		;
257
258mask:		  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
279instrs:		  instrs '\n' instr
280		| instr
281		;
282
283instr:		  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
369bitfieldopt:	  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
388bytes:		  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
405byte:		  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
417bit:		  '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
453optargs:	  kSPACE args
454		    { $$ = $2; }
455		|
456		    { $$ = NULL; }
457		;
458
459args:		  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
477arg:		  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		;
488argcomp:	  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
549static void
550yyerror (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
557static int
558bitfield_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
567static void
568new_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.  */
590static void
591check_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
632static int
633check_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
659static int
660check_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
695static int
696check_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
740static struct argname *
741combine (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
769static void
770fillin_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
864static void
865nameout (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
873static int
874compare_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
883static int maxoff[3][3];
884static int minoff[3][3] = { { 1000, 1000, 1000 },
885			    { 1000, 1000, 1000 },
886			    { 1000, 1000, 1000 } };
887static int nbitoff[3][3];
888static void *fct_names[3];
889static int nbitfct[3];
890static int nbitsuf;
891static void *strs[3];
892static int nbitstr[3];
893static int total_bits = 2;	// Already counted the rep/repe bits.
894
895static void
896find_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
1050static int
1051compare_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
1060static int
1061compare_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
1070static int count_op_str;
1071static int off_op_str;
1072static void
1073print_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
1088static void
1089print_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
1097static void
1098print_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
1113static void
1114instrtable_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
1344static size_t mnemonic_maxlen;
1345static size_t mnemonic_minlen;
1346static size_t
1347which_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
1370static const char **mnemonic_strs;
1371static size_t nmnemonic_strs;
1372static void
1373add_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
1381struct charfreq
1382{
1383  char ch;
1384  int freq;
1385};
1386static struct charfreq pfxfreq[256];
1387static struct charfreq sfxfreq[256];
1388
1389
1390static int
1391compare_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
1404static size_t
1405compute_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
1424struct strsnlen
1425{
1426  const char *str;
1427  size_t len;
1428};
1429
1430static size_t
1431compute_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
1450static void
1451create_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
1685