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