• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 <libintl.h>
39 #include <math.h>
40 #include <obstack.h>
41 #include <search.h>
42 #include <stdbool.h>
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <string.h>
46 
47 #include <libeu.h>
48 #include <system.h>
49 
50 #define obstack_chunk_alloc xmalloc
51 #define obstack_chunk_free free
52 
53 /* The error handler.  */
54 static void yyerror (const char *s);
55 
56 extern int yylex (void);
57 extern int i386_lineno;
58 extern char *infname;
59 
60 
61 struct known_bitfield
62 {
63   char *name;
64   unsigned long int bits;
65   int tmp;
66 };
67 
68 
69 struct bitvalue
70 {
71   enum bittype { zeroone, field, failure } type;
72   union
73   {
74     unsigned int value;
75     struct known_bitfield *field;
76   };
77   struct bitvalue *next;
78 };
79 
80 
81 struct argname
82 {
83   enum nametype { string, nfield } type;
84   union
85   {
86     char *str;
87     struct known_bitfield *field;
88   };
89   struct argname *next;
90 };
91 
92 
93 struct argument
94 {
95   struct argname *name;
96   struct argument *next;
97 };
98 
99 
100 struct instruction
101 {
102   /* The byte encoding.  */
103   struct bitvalue *bytes;
104 
105   /* Prefix possible.  */
106   int repe;
107   int rep;
108 
109   /* Mnemonic.  */
110   char *mnemonic;
111 
112   /* Suffix.  */
113   enum { suffix_none = 0, suffix_w, suffix_w0, suffix_W, suffix_tttn,
114 	 suffix_w1, suffix_W1, suffix_D } suffix;
115 
116   /* Flag set if modr/m is used.  */
117   int modrm;
118 
119   /* Operands.  */
120   struct operand
121   {
122     char *fct;
123     char *str;
124     int off1;
125     int off2;
126     int off3;
127   } operands[3];
128 
129   struct instruction *next;
130 };
131 
132 
133 struct synonym
134 {
135   char *from;
136   char *to;
137 };
138 
139 
140 struct suffix
141 {
142   char *name;
143   int idx;
144 };
145 
146 
147 struct argstring
148 {
149   char *str;
150   int idx;
151   int off;
152 };
153 
154 
155 static struct known_bitfield ax_reg =
156   {
157     .name = "ax", .bits = 0, .tmp = 0
158   };
159 
160 static struct known_bitfield dx_reg =
161   {
162     .name = "dx", .bits = 0, .tmp = 0
163   };
164 
165 static struct known_bitfield di_reg =
166   {
167     .name = "es_di", .bits = 0, .tmp = 0
168   };
169 
170 static struct known_bitfield si_reg =
171   {
172     .name = "ds_si", .bits = 0, .tmp = 0
173   };
174 
175 static struct known_bitfield bx_reg =
176   {
177     .name = "ds_bx", .bits = 0, .tmp = 0
178   };
179 
180 
181 static int bitfield_compare (const void *p1, const void *p2);
182 static void new_bitfield (char *name, unsigned long int num);
183 static void check_bits (struct bitvalue *value);
184 static int check_duplicates (struct bitvalue *val);
185 static int check_argsdef (struct bitvalue *bitval, struct argument *args);
186 static int check_bitsused (struct bitvalue *bitval,
187 			   struct known_bitfield *suffix,
188 			   struct argument *args);
189 static struct argname *combine (struct argname *name);
190 static void fillin_arg (struct bitvalue *bytes, struct argname *name,
191 			struct instruction *instr, int n);
192 static void find_numbers (void);
193 static int compare_syn (const void *p1, const void *p2);
194 static int compare_suf (const void *p1, const void *p2);
195 static void instrtable_out (void);
196 #if 0
197 static void create_mnemonic_table (void);
198 #endif
199 
200 static void *bitfields;
201 static struct instruction *instructions;
202 static size_t ninstructions;
203 static void *synonyms;
204 static void *suffixes;
205 static int nsuffixes;
206 static void *mnemonics;
207 size_t nmnemonics;
208 extern FILE *outfile;
209 
210 /* Number of bits used mnemonics.  */
211 #if 0
212 static size_t best_mnemonic_bits;
213 #endif
214 %}
215 
216 %union {
217   unsigned long int num;
218   char *str;
219   char ch;
220   struct known_bitfield *field;
221   struct bitvalue *bit;
222   struct argname *name;
223   struct argument *arg;
224 }
225 
226 %token kMASK
227 %token kPREFIX
228 %token kSUFFIX
229 %token kSYNONYM
230 %token <str> kID
231 %token <num> kNUMBER
232 %token kPERCPERC
233 %token <str> kBITFIELD
234 %token <ch> kCHAR
235 %token kSPACE
236 
237 %type <bit> bit byte bytes
238 %type <field> bitfieldopt
239 %type <name> argcomp arg
240 %type <arg> args optargs
241 
242 %defines
243 
244 %%
245 
246 spec:		  masks kPERCPERC '\n' instrs
247 		    {
248 		      if (error_message_count != 0)
249 			error (EXIT_FAILURE, 0,
250 			       "terminated due to previous error");
251 
252 		      instrtable_out ();
253 		    }
254 		;
255 
256 masks:		  masks '\n' mask
257 		| mask
258 		;
259 
260 mask:		  kMASK kBITFIELD kNUMBER
261 		    { new_bitfield ($2, $3); }
262 		| kPREFIX kBITFIELD
263 		    { new_bitfield ($2, -1); }
264 		| kSUFFIX kBITFIELD
265 		    { new_bitfield ($2, -2); }
266 		| kSYNONYM kBITFIELD kBITFIELD
267 		    {
268 		      struct synonym *newp = xmalloc (sizeof (*newp));
269 		      newp->from = $2;
270 		      newp->to = $3;
271 		      if (tfind (newp, &synonyms, compare_syn) != NULL)
272 			error (0, 0,
273 			       "%d: duplicate definition for synonym '%s'",
274 			       i386_lineno, $2);
275 		      else if (tsearch ( newp, &synonyms, compare_syn) == NULL)
276 			error (EXIT_FAILURE, 0, "tsearch");
277 		    }
278 		|
279 		;
280 
281 instrs:		  instrs '\n' instr
282 		| instr
283 		;
284 
285 instr:		  bytes ':' bitfieldopt kID bitfieldopt optargs
286 		    {
287 		      if ($3 != NULL && strcmp ($3->name, "RE") != 0
288 			  && strcmp ($3->name, "R") != 0)
289 			{
290 			  error (0, 0, "%d: only 'R' and 'RE' prefix allowed",
291 				 i386_lineno - 1);
292 			}
293 		      if (check_duplicates ($1) == 0
294 			  && check_argsdef ($1, $6) == 0
295 			  && check_bitsused ($1, $5, $6) == 0)
296 			{
297 			  struct instruction *newp = xcalloc (sizeof (*newp),
298 							      1);
299 			  if ($3 != NULL)
300 			    {
301 			      if (strcmp ($3->name, "RE") == 0)
302 				newp->repe = 1;
303 			      else if (strcmp ($3->name, "R") == 0)
304 				newp->rep = 1;
305 			    }
306 
307 			  newp->bytes = $1;
308 			  newp->mnemonic = $4;
309 			  if (newp->mnemonic != (void *) -1l
310 			      && tfind ($4, &mnemonics,
311 					(int (*)(const void *, const void *)) strcmp) == NULL)
312 			    {
313 			      if (tsearch ($4, &mnemonics,
314 					   (int (*)(const void *, const void *)) strcmp) == NULL)
315 				error (EXIT_FAILURE, errno, "tsearch");
316 			      ++nmnemonics;
317 			    }
318 
319 			  if ($5 != NULL)
320 			    {
321 			      if (strcmp ($5->name, "w") == 0)
322 				newp->suffix = suffix_w;
323 			      else if (strcmp ($5->name, "w0") == 0)
324 				newp->suffix = suffix_w0;
325 			      else if (strcmp ($5->name, "tttn") == 0)
326 				newp->suffix = suffix_tttn;
327 			      else if (strcmp ($5->name, "w1") == 0)
328 				newp->suffix = suffix_w1;
329 			      else if (strcmp ($5->name, "W") == 0)
330 				newp->suffix = suffix_W;
331 			      else if (strcmp ($5->name, "W1") == 0)
332 				newp->suffix = suffix_W1;
333 			      else if (strcmp ($5->name, "D") == 0)
334 				newp->suffix = suffix_D;
335 			      else
336 				error (EXIT_FAILURE, 0,
337 				       "%s: %d: unknown suffix '%s'",
338 				       infname, i386_lineno - 1, $5->name);
339 
340 			      struct suffix search = { .name = $5->name };
341 			      if (tfind (&search, &suffixes, compare_suf)
342 				  == NULL)
343 				{
344 				  struct suffix *ns = xmalloc (sizeof (*ns));
345 				  ns->name = $5->name;
346 				  ns->idx = ++nsuffixes;
347 				  if (tsearch (ns, &suffixes, compare_suf)
348 				      == NULL)
349 				    error (EXIT_FAILURE, errno, "tsearch");
350 				}
351 			    }
352 
353 			  struct argument *args = $6;
354 			  int n = 0;
355 			  while (args != NULL)
356 			    {
357 			      fillin_arg ($1, args->name, newp, n);
358 
359 			      args = args->next;
360 			      ++n;
361 			    }
362 
363 			  newp->next = instructions;
364 			  instructions = newp;
365 			  ++ninstructions;
366 			}
367 		    }
368 		|
369 		;
370 
371 bitfieldopt:	  kBITFIELD
372 		    {
373 		      struct known_bitfield search;
374 		      search.name = $1;
375 		      struct known_bitfield **res;
376 		      res = tfind (&search, &bitfields, bitfield_compare);
377 		      if (res == NULL)
378 			{
379 			  error (0, 0, "%d: unknown bitfield '%s'",
380 				 i386_lineno, search.name);
381 			  $$ = NULL;
382 			}
383 		      else
384 			$$ = *res;
385 		    }
386 		|
387 		    { $$ = NULL; }
388 		;
389 
390 bytes:		  bytes ',' byte
391 		    {
392 		      check_bits ($3);
393 
394 		      struct bitvalue *runp = $1;
395 		      while (runp->next != NULL)
396 			runp = runp->next;
397 		      runp->next = $3;
398 		      $$ = $1;
399 		    }
400 		| byte
401 		    {
402 		      check_bits ($1);
403 		      $$ = $1;
404 		    }
405 		;
406 
407 byte:		  byte bit
408 		    {
409 		      struct bitvalue *runp = $1;
410 		      while (runp->next != NULL)
411 			runp = runp->next;
412 		      runp->next = $2;
413 		      $$ = $1;
414 		    }
415 		| bit
416 		    { $$ = $1; }
417 		;
418 
419 bit:		  '0'
420 		    {
421 		      $$ = xmalloc (sizeof (struct bitvalue));
422 		      $$->type = zeroone;
423 		      $$->value = 0;
424 		      $$->next = NULL;
425 		    }
426 		| '1'
427 		    {
428 		      $$ = xmalloc (sizeof (struct bitvalue));
429 		      $$->type = zeroone;
430 		      $$->value = 1;
431 		      $$->next = NULL;
432 		    }
433 		| kBITFIELD
434 		    {
435 		      $$ = xmalloc (sizeof (struct bitvalue));
436 		      struct known_bitfield search;
437 		      search.name = $1;
438 		      struct known_bitfield **res;
439 		      res = tfind (&search, &bitfields, bitfield_compare);
440 		      if (res == NULL)
441 			{
442 			  error (0, 0, "%d: unknown bitfield '%s'",
443 				 i386_lineno, search.name);
444 			  $$->type = failure;
445 			}
446 		      else
447 			{
448 			  $$->type = field;
449 			  $$->field = *res;
450 			}
451 		      $$->next = NULL;
452 		    }
453 		;
454 
455 optargs:	  kSPACE args
456 		    { $$ = $2; }
457 		|
458 		    { $$ = NULL; }
459 		;
460 
461 args:		  args ',' arg
462 		    {
463 		      struct argument *runp = $1;
464 		      while (runp->next != NULL)
465 			runp = runp->next;
466 		      runp->next = xmalloc (sizeof (struct argument));
467 		      runp->next->name = combine ($3);
468 		      runp->next->next = NULL;
469 		      $$ = $1;
470 		    }
471 		| arg
472 		    {
473 		      $$ = xmalloc (sizeof (struct argument));
474 		      $$->name = combine ($1);
475 		      $$->next = NULL;
476 		    }
477 		;
478 
479 arg:		  arg argcomp
480 		    {
481 		      struct argname *runp = $1;
482 		      while (runp->next != NULL)
483 			runp = runp->next;
484 		      runp->next = $2;
485 		      $$ = $1;
486 		    }
487 		| argcomp
488 		    { $$ = $1; }
489 		;
490 argcomp:	  kBITFIELD
491 		    {
492 		      $$ = xmalloc (sizeof (struct argname));
493 		      $$->type = nfield;
494 		      $$->next = NULL;
495 
496 		      struct known_bitfield search;
497 		      search.name = $1;
498 		      struct known_bitfield **res;
499 		      res = tfind (&search, &bitfields, bitfield_compare);
500 		      if (res == NULL)
501 			{
502 			  if (strcmp ($1, "ax") == 0)
503 			    $$->field = &ax_reg;
504 			  else if (strcmp ($1, "dx") == 0)
505 			    $$->field = &dx_reg;
506 			  else if (strcmp ($1, "es_di") == 0)
507 			    $$->field = &di_reg;
508 			  else if (strcmp ($1, "ds_si") == 0)
509 			    $$->field = &si_reg;
510 			  else if (strcmp ($1, "ds_bx") == 0)
511 			    $$->field = &bx_reg;
512 			  else
513 			    {
514 			      error (0, 0, "%d: unknown bitfield '%s'",
515 				     i386_lineno, search.name);
516 			      $$->field = NULL;
517 			    }
518 			}
519 		      else
520 			$$->field = *res;
521 		    }
522 		| kCHAR
523 		    {
524 		      $$ = xmalloc (sizeof (struct argname));
525 		      $$->type = string;
526 		      $$->next = NULL;
527 		      $$->str = xmalloc (2);
528 		      $$->str[0] = $1;
529 		      $$->str[1] = '\0';
530 		    }
531 		| kID
532 		    {
533 		      $$ = xmalloc (sizeof (struct argname));
534 		      $$->type = string;
535 		      $$->next = NULL;
536 		      $$->str = $1;
537 		    }
538 		| ':'
539 		    {
540 		      $$ = xmalloc (sizeof (struct argname));
541 		      $$->type = string;
542 		      $$->next = NULL;
543 		      $$->str = xmalloc (2);
544 		      $$->str[0] = ':';
545 		      $$->str[1] = '\0';
546 		    }
547 		;
548 
549 %%
550 
551 static void
552 yyerror (const char *s)
553 {
554   error (0, 0, gettext ("while reading i386 CPU description: %s at line %d"),
555          gettext (s), i386_lineno);
556 }
557 
558 
559 static int
bitfield_compare(const void * p1,const void * p2)560 bitfield_compare (const void *p1, const void *p2)
561 {
562   struct known_bitfield *f1 = (struct known_bitfield *) p1;
563   struct known_bitfield *f2 = (struct known_bitfield *) p2;
564 
565   return strcmp (f1->name, f2->name);
566 }
567 
568 
569 static void
new_bitfield(char * name,unsigned long int num)570 new_bitfield (char *name, unsigned long int num)
571 {
572   struct known_bitfield *newp = xmalloc (sizeof (struct known_bitfield));
573   newp->name = name;
574   newp->bits = num;
575   newp->tmp = 0;
576 
577   if (tfind (newp, &bitfields, bitfield_compare) != NULL)
578     {
579       error (0, 0, "%d: duplicated definition of bitfield '%s'",
580 	     i386_lineno, name);
581       free (name);
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
check_bits(struct bitvalue * val)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
check_duplicates(struct bitvalue * val)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
check_argsdef(struct bitvalue * bitval,struct argument * args)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
check_bitsused(struct bitvalue * bitval,struct known_bitfield * suffix,struct argument * args)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 *
combine(struct argname * name)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
fillin_arg(struct bitvalue * bytes,struct argname * name,struct instruction * instr,int n)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
compare_argstring(const void * p1,const void * p2)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
find_numbers(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
compare_syn(const void * p1,const void * p2)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
compare_suf(const void * p1,const void * p2)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
print_op_str(const void * nodep,VISIT value,int level)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
print_op_str_idx(const void * nodep,VISIT value,int level)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
print_op_fct(const void * nodep,VISIT value,int level)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
instrtable_out(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
1687