src/native_client/src/trusted/validator/x86/decoder/generator/ncdecode_tablegen.c

   1 /*
   2  * Copyright (c) 2011 The Native Client Authors. All rights reserved.
   3  * Use of this source code is governed by a BSD-style license that can be
   4  * found in the LICENSE file.
   5  */
   6
   7 /*
   8  * New table driven generator for a decoder of x86 code.
   9  *
  10  * Note: Most of the organization of this document is based on the
  11  * NaClOpcode Map appendix of one of the following documents:
  12
  13  * (1) "Intel 64 and IA-32 Architectures
  14  * Software Developer's Manual (volumes 1, 2a, and 2b; documents
  15  * 253665.pdf, 253666.pdf, and 253667.pdf)".
  16  *
  17  * (2) "Intel 80386 Reference Programmer's Manual" (document
  18  * http://pdos.csail.mit.edu/6.828/2004/readings/i386/toc.htm).
  19  */
  20
  21 #ifndef NACL_TRUSTED_BUT_NOT_TCB
  22 #error("This file is not meant for use in the TCB")
  23 #endif
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <assert.h>
  28 #include <string.h>
  29
  30 #include "native_client/src/trusted/validator/x86/decoder/generator/ncdecode_tablegen.h"
  31
  32
  33 #include "native_client/src/include/portability.h"
  34 #include "native_client/src/include/portability_io.h"
  35 #include "native_client/src/shared/utils/flags.h"
  36 #include "native_client/src/shared/platform/nacl_log.h"
  37 #include "native_client/src/trusted/validator/x86/x86_insts.h"
  38 #include "native_client/src/trusted/validator/x86/decoder/generator/gen/nacl_disallows.h"
  39 #include "native_client/src/trusted/validator/x86/decoder/generator/nacl_regsgen.h"
  40 #include "native_client/src/trusted/validator/x86/decoder/generator/ncdecode_forms.h"
  41 #include "native_client/src/trusted/validator/x86/decoder/generator/ncdecode_st.h"
  42 #include "native_client/src/trusted/validator/x86/decoder/generator/ncval_simplify.h"
  43 #include "native_client/src/trusted/validator/x86/decoder/generator/nc_compress.h"
  44
  45 /* To turn on debugging of instruction decoding, change value of
  46  * DEBUGGING to 1.
  47  */
  48 #define DEBUGGING 0
  49
  50 #include "native_client/src/shared/utils/debugging.h"
  51
  52 /* Define the default buffer size to use. */
  53 #define BUFFER_SIZE 256
  54
  55 /* Model an NaClInst, sorted by OpcodeInModRm values. */
  56 typedef struct NaClMrmInst {
  57   NaClModeledInst inst;
  58   struct NaClMrmInst* next;
  59 } NaClMrmInst;
  60
  61 /* Note: in general all errors in this module will be fatal.
  62  * To debug: use gdb or your favorite debugger.
  63  */
  64 void NaClFatal(const char* s) {
  65   NaClLog(LOG_FATAL, "Error: %s\n", s);
  66   NaClLog(LOG_FATAL, "Fatal: cannot recover\n");
  67   exit(-1);
  68 }
  69
  70 /* Returns the print name of the given run mode. */
  71 static const char* NaClRunModeName(NaClRunMode mode) {
  72   switch (mode) {
  73     case X86_32: return "x86-32 bit mode";
  74     case X86_64: return "x86-64 bit mode";
  75     default: assert(0);
  76   }
  77
  78   /* NOTREACHED */
  79   return NULL;
  80 }
  81
  82 /* Defines if we should simplify the instructions to
  83  * what is needed by the validator.
  84  */
  85 static Bool NACL_FLAGS_validator_decoder = FALSE;
  86
  87 /* Defines the run mode files that should be generated. */
  88 NaClRunMode NACL_FLAGS_run_mode = NaClRunModeSize;
  89
  90 /* Defines whether the output of the instruction set should
  91  * be as a header file, or human readable (for documentation).
  92  */
  93 static Bool NACL_FLAGS_human_readable = FALSE;
  94
  95 /* Defines whether the output should be instruction modeling tables,
  96  * or hardware registers.
  97  */
  98 static Bool NACL_FLAGS_nacl_subregs = FALSE;
  99
 100 /* Holds the current instruction prefix. */
 101 static NaClInstPrefix current_opcode_prefix = NoPrefix;
 102
 103 /* Holds the default instruction prefix. */
 104 static NaClInstPrefix default_opcode_prefix = NoPrefix;
 105
 106 /* Holds the current instruction being built. */
 107 static NaClModeledInst* current_inst = NULL;
 108
 109 /* Holds the current opcode sequence to be associated with the next
 110  * defined opcode.
 111  */
 112 static NaClModeledInstNode* current_inst_node = NULL;
 113
 114 /* Holds the candidate for the current_inst_node, when
 115  * NaClDefInst is called.
 116  */
 117 static NaClModeledInstNode* current_cand_inst_node = NULL;
 118
 119 /* Holds the current instruction with mrm extention being built. */
 120 static NaClMrmInst* current_inst_mrm = NULL;
 121
 122 /* Holds tables used to generate/compress the modeled instructions. */
 123 NaClInstTables tables;
 124
 125 /* True if we are to apply sanity checks as we define operantions. */
 126 static Bool apply_sanity_checks = TRUE;
 127
 128 #define NACL_DEFAULT_CHOICE_COUNT (-1)
 129
 130 #define NACL_NO_MODRM_OPCODE 8
 131
 132 #define NACL_MODRM_OPCODE_SIZE (NACL_NO_MODRM_OPCODE + 1)
 133
 134 /* Holds the expected number of entries in the defined instructions.
 135  * Note: the last index corresponds to the modrm opcode, or
 136  * NACL_NO_MODRM_OPCODE if no modrm opcode.
 137  */
 138 static int NaClInstCount[NCDTABLESIZE]
 139           [NaClInstPrefixEnumSize][NACL_MODRM_OPCODE_SIZE];
 140
 141 static NaClMrmInst* NaClInstMrmTable[NCDTABLESIZE]
 142           [NaClInstPrefixEnumSize][NACL_MODRM_OPCODE_SIZE];
 143
 144 /* Holds encodings of prefix bytes. */
 145 static const char* NaClPrefixTable[NCDTABLESIZE];
 146
 147
 148 /* Prints out the opcode prefix being defined, the opcode pattern
 149  * being defined, and the given error message. Then aborts the
 150  * execution of the program.
 151  */
 152 static void NaClFatalInst(const char* message) {
 153   NaClLog(LOG_INFO, "Prefix: %s\n", NaClInstPrefixName(current_opcode_prefix));
 154   NaClModeledInstPrint(NaClLogGetGio(), current_inst);
 155   NaClFatal(message);
 156 }
 157
 158 /* Prints out what operand is currently being defined, followed by the given
 159  * error message. Then aborts the execution of the program.
 160  */
 161 static void NaClFatalOp(int index, const char* message) {
 162   if (0 <= index && index <= current_inst->num_operands) {
 163     NaClLog(LOG_ERROR, "On operand %d: %s\n", index,
 164             NaClOpKindName(current_inst->operands[index].kind));
 165   } else {
 166     NaClLog(LOG_ERROR, "On operand %d:\n", index);
 167   }
 168   NaClFatalInst(message);
 169 }
 170
 171 /* Advance the buffer/buffer_size values by count characters. */
 172 static void CharAdvance(char** buffer, size_t* buffer_size, size_t count) {
 173   *buffer += count;
 174   *buffer_size += count;
 175 }
 176
 177 /* Generates a (malloc allocated) string describing the form for the
 178  * operands.
 179  * Note: This code used to be part of the validator (runtime) library.
 180  * By moving it here, we remove this code, and runtime cost, from
 181  * the validator runtime.
 182  */
 183 static void NaClFillOperandDescs(NaClModeledInst* inst) {
 184   char buffer[BUFFER_SIZE];
 185   int i;
 186
 187   /* Make sure inst is defined before trying to fix. */
 188   if (NULL == inst) return;
 189
 190   for (i = 0; i < inst->num_operands; ++i) {
 191     char* buf = buffer;
 192     size_t buf_size = BUFFER_SIZE;
 193     Bool is_implicit = (NACL_EMPTY_OPFLAGS != (inst->operands[i].flags &
 194                                                NACL_OPFLAG(OpImplicit)));
 195     NaClOpKind kind = inst->operands[i].kind;
 196
 197     if (NULL != inst->operands[i].format_string) continue;
 198
 199     buffer[0] = '\0';  /* just in case there isn't any operands. */
 200     if (is_implicit) {
 201       CharAdvance(&buf, &buf_size,
 202                   SNPRINTF(buf, buf_size, "{"));
 203     }
 204     switch (kind) {
 205       case A_Operand:
 206         CharAdvance(&buf, &buf_size,
 207                     SNPRINTF(buf, buf_size, "$A"));
 208         break;
 209       case E_Operand:
 210       case Eb_Operand:
 211       case Ew_Operand:
 212       case Ev_Operand:
 213       case Eo_Operand:
 214       case Edq_Operand:
 215         CharAdvance(&buf, &buf_size,
 216                     SNPRINTF(buf, buf_size, "$E"));
 217         break;
 218       case G_Operand:
 219       case Gb_Operand:
 220       case Gw_Operand:
 221       case Gv_Operand:
 222       case Go_Operand:
 223       case Gdq_Operand:
 224         CharAdvance(&buf, &buf_size,
 225                     SNPRINTF(buf, buf_size, "$G"));
 226         break;
 227       case Seg_G_Operand:
 228         CharAdvance(&buf, &buf_size,
 229                     SNPRINTF(buf, buf_size, "$SegG"));
 230         break;
 231       case G_OpcodeBase:
 232         CharAdvance(&buf, &buf_size,
 233                     SNPRINTF(buf, buf_size, "$/r"));
 234         break;
 235       case I_Operand:
 236       case Ib_Operand:
 237       case Iw_Operand:
 238       case Iv_Operand:
 239       case Io_Operand:
 240       case I2_Operand:
 241       case J_Operand:
 242       case Jb_Operand:
 243       case Jw_Operand:
 244       case Jv_Operand:
 245         CharAdvance(&buf, &buf_size,
 246                     SNPRINTF(buf, buf_size, "$I"));
 247         break;
 248       case M_Operand:
 249       case Mb_Operand:
 250       case Mw_Operand:
 251       case Mv_Operand:
 252       case Mo_Operand:
 253       case Mdq_Operand:
 254         /* Special case $Ma, which adds two operands. */
 255         if ((i > 0) && (NULL != inst->operands[i-1].format_string) &&
 256             (0 == strcmp(inst->operands[i-1].format_string, "$Ma"))) {
 257           /* Don't add a format string in this case. */
 258           continue;
 259         } else {
 260           CharAdvance(&buf, &buf_size,
 261                       SNPRINTF(buf, buf_size, "$M"));
 262         }
 263         break;
 264       case Mpw_Operand:
 265         CharAdvance(&buf, &buf_size,
 266                     SNPRINTF(buf, buf_size, "m16:16"));
 267         break;
 268       case Mpv_Operand:
 269         CharAdvance(&buf, &buf_size,
 270                     SNPRINTF(buf, buf_size, "m16:32"));
 271         break;
 272       case Mpo_Operand:
 273         CharAdvance(&buf, &buf_size,
 274                     SNPRINTF(buf, buf_size, "m16:64"));
 275         break;
 276       case Mmx_E_Operand:
 277       case Mmx_N_Operand:
 278         CharAdvance(&buf, &buf_size,
 279                     SNPRINTF(buf, buf_size, "$E(mmx)"));
 280         break;
 281       case Mmx_G_Operand:
 282       case Mmx_Gd_Operand:
 283         CharAdvance(&buf, &buf_size,
 284                     SNPRINTF(buf, buf_size, "$G(mmx)"));
 285         break;
 286       case Xmm_E_Operand:
 287       case Xmm_Eo_Operand:
 288         CharAdvance(&buf, &buf_size,
 289                     SNPRINTF(buf, buf_size, "$E(xmm)"));
 290         break;
 291       case Xmm_G_Operand:
 292       case Xmm_Go_Operand:
 293         CharAdvance(&buf, &buf_size,
 294                     SNPRINTF(buf, buf_size, "$G(xmm)"));
 295         break;
 296       case O_Operand:
 297       case Ob_Operand:
 298       case Ow_Operand:
 299       case Ov_Operand:
 300       case Oo_Operand:
 301         CharAdvance(&buf, &buf_size,
 302                     SNPRINTF(buf, buf_size, "$O"));
 303         break;
 304       case S_Operand:
 305         CharAdvance(&buf, &buf_size,
 306                     SNPRINTF(buf, buf_size, "%%Sreg"));
 307         break;
 308       case C_Operand:
 309         CharAdvance(&buf, &buf_size,
 310                     SNPRINTF(buf, buf_size, "%%Creg"));
 311         break;
 312       case D_Operand:
 313         CharAdvance(&buf, &buf_size,
 314                     SNPRINTF(buf, buf_size, "%%Dreg"));
 315         break;
 316       case St_Operand:
 317         CharAdvance(&buf, &buf_size,
 318                     SNPRINTF(buf, buf_size, "%%st"));
 319         break;
 320       case RegAL:
 321       case RegBL:
 322       case RegCL:
 323       case RegDL:
 324       case RegAH:
 325       case RegBH:
 326       case RegCH:
 327       case RegDH:
 328       case RegDIL:
 329       case RegSIL:
 330       case RegBPL:
 331       case RegSPL:
 332       case RegR8B:
 333       case RegR9B:
 334       case RegR10B:
 335       case RegR11B:
 336       case RegR12B:
 337       case RegR13B:
 338       case RegR14B:
 339       case RegR15B:
 340       case RegAX:
 341       case RegBX:
 342       case RegCX:
 343       case RegDX:
 344       case RegSI:
 345       case RegDI:
 346       case RegBP:
 347       case RegSP:
 348       case RegR8W:
 349       case RegR9W:
 350       case RegR10W:
 351       case RegR11W:
 352       case RegR12W:
 353       case RegR13W:
 354       case RegR14W:
 355       case RegR15W:
 356       case RegEAX:
 357       case RegEBX:
 358       case RegECX:
 359       case RegEDX:
 360       case RegESI:
 361       case RegEDI:
 362       case RegEBP:
 363       case RegESP:
 364       case RegR8D:
 365       case RegR9D:
 366       case RegR10D:
 367       case RegR11D:
 368       case RegR12D:
 369       case RegR13D:
 370       case RegR14D:
 371       case RegR15D:
 372       case RegCS:
 373       case RegDS:
 374       case RegSS:
 375       case RegES:
 376       case RegFS:
 377       case RegGS:
 378       case RegEFLAGS:
 379       case RegRFLAGS:
 380       case RegEIP:
 381       case RegRIP:
 382       case RegRAX:
 383       case RegRBX:
 384       case RegRCX:
 385       case RegRDX:
 386       case RegRSI:
 387       case RegRDI:
 388       case RegRBP:
 389       case RegRSP:
 390       case RegR8:
 391       case RegR9:
 392       case RegR10:
 393       case RegR11:
 394       case RegR12:
 395       case RegR13:
 396       case RegR14:
 397       case RegR15:
 398       case RegREIP:
 399       case RegREAX:
 400       case RegREBX:
 401       case RegRECX:
 402       case RegREDX:
 403       case RegRESP:
 404       case RegREBP:
 405       case RegRESI:
 406       case RegREDI:
 407       case RegDS_EDI:
 408       case RegDS_EBX:
 409       case RegES_EDI:
 410       case RegST0:
 411       case RegST1:
 412       case RegST2:
 413       case RegST3:
 414       case RegST4:
 415       case RegST5:
 416       case RegST6:
 417       case RegST7:
 418       case RegMMX0:
 419       case RegMMX1:
 420       case RegMMX2:
 421       case RegMMX3:
 422       case RegMMX4:
 423       case RegMMX5:
 424       case RegMMX6:
 425       case RegMMX7:
 426       case RegXMM0:
 427       case RegXMM1:
 428       case RegXMM2:
 429       case RegXMM3:
 430       case RegXMM4:
 431       case RegXMM5:
 432       case RegXMM6:
 433       case RegXMM7:
 434       case RegXMM8:
 435       case RegXMM9:
 436       case RegXMM10:
 437       case RegXMM11:
 438       case RegXMM12:
 439       case RegXMM13:
 440       case RegXMM14:
 441       case RegXMM15:
 442         CharAdvance(&buf, &buf_size,
 443                     SNPRINTF(buf, buf_size, "%%%s",
 444                              NaClOpKindName(kind) + strlen("Reg")));
 445         break;
 446       case Const_1:
 447         CharAdvance(&buf, &buf_size,
 448                     SNPRINTF(buf, buf_size, "1"));
 449         break;
 450       default:
 451         CharAdvance(&buf, &buf_size,
 452                     SNPRINTF(buf, buf_size, "???"));
 453         break;
 454     }
 455     if (is_implicit) {
 456       CharAdvance(&buf, &buf_size,
 457                   SNPRINTF(buf, buf_size, "}"));
 458     }
 459     *((char**)(inst->operands[i].format_string)) = strdup(buffer);
 460   }
 461 }
 462
 463 /* Define the prefix name for the given opcode, for the given run mode. */
 464 static void NaClEncodeModedPrefixName(const uint8_t byte, const char* name,
 465                                       const NaClRunMode mode) {
 466   if (NACL_FLAGS_run_mode == mode) {
 467     NaClPrefixTable[byte] = name;
 468   }
 469 }
 470
 471 /* Define the prefix name for the given opcode, for all run modes. */
 472 static void NaClEncodePrefixName(const uint8_t byte, const char* name) {
 473   NaClEncodeModedPrefixName(byte, name, NACL_FLAGS_run_mode);
 474 }
 475
 476 /* Change the current opcode prefix to the given value. */
 477 void NaClDefInstPrefix(const NaClInstPrefix prefix) {
 478   current_opcode_prefix = prefix;
 479 }
 480
 481 void NaClResetToDefaultInstPrefix(void) {
 482   NaClDefInstPrefix(default_opcode_prefix);
 483 }
 484
 485 NaClModeledInst* NaClGetDefInst(void) {
 486   return current_inst;
 487 }
 488
 489 /* Check if an E_Operand operand has been repeated, since it should
 490  * never appear for more than one argument. If repeated, generate an
 491  * appropriate error message and terminate.
 492  */
 493 static void NaClCheckIfERepeated(int index) {
 494   int i;
 495   for (i = 0; i < index; ++i) {
 496     const NaClOp* operand = &current_inst->operands[i];
 497     switch (operand->kind) {
 498       case Mmx_E_Operand:
 499       case Xmm_E_Operand:
 500       case Xmm_Eo_Operand:
 501       case E_Operand:
 502       case Eb_Operand:
 503       case Ew_Operand:
 504       case Ev_Operand:
 505       case Eo_Operand:
 506       case Edq_Operand:
 507         NaClFatalOp(index, "Can't use E Operand more than once");
 508         break;
 509       default:
 510         break;
 511     }
 512   }
 513 }
 514
 515 /* Called if operand is a G_Operand. Checks that the opcode doesn't specify
 516  * that the REG field of modrm is an opcode, since G_Operand doesn't make
 517  * sense in such cases.
 518  */
 519 static void NaClCheckIfOpcodeInModRm(int index) {
 520   if ((current_inst->flags & NACL_IFLAG(OpcodeInModRm)) &&
 521       (NACL_EMPTY_OPFLAGS == (current_inst->operands[index].flags &
 522                               NACL_IFLAG(AllowGOperandWithOpcodeInModRm)))) {
 523     NaClFatalOp(index,
 524                  "Can't use G Operand, bits being used for opcode in modrm");
 525   }
 526 }
 527
 528 /* Check if an G_Operand operand has been repeated, since it should
 529  * never appear for more than one argument. If repeated, generate an
 530  * appropriate error message and terminate.
 531  */
 532 static void NaClCheckIfGRepeated(int index) {
 533   int i;
 534   for (i = 0; i < index; ++i) {
 535     const NaClOp* operand = &current_inst->operands[i];
 536     switch (operand->kind) {
 537       case Mmx_G_Operand:
 538       case Xmm_G_Operand:
 539       case Xmm_Go_Operand:
 540       case G_Operand:
 541       case Gb_Operand:
 542       case Gw_Operand:
 543       case Gv_Operand:
 544       case Go_Operand:
 545       case Gdq_Operand:
 546         NaClFatalOp(index, "Can't use G Operand more than once");
 547         break;
 548       default:
 549         break;
 550     }
 551   }
 552 }
 553
 554 /* Check if an I_Operand/J_OPerand operand has been repeated, since it should
 555  * never appear for more than one argument (both come from the immediate field
 556  * of the instruction). If repeated, generate an appropriate error message
 557  * and terminate.
 558  */
 559 static void NaClCheckIfIRepeated(int index) {
 560   int i;
 561   for (i = 0; i < index; ++i) {
 562     const NaClOp* operand = &current_inst->operands[i];
 563     switch (operand->kind) {
 564       case I_Operand:
 565       case Ib_Operand:
 566       case Iw_Operand:
 567       case Iv_Operand:
 568       case Io_Operand:
 569         NaClFatalOp(index, "Can't use I_Operand more than once");
 570         break;
 571       case J_Operand:
 572       case Jb_Operand:
 573       case Jv_Operand:
 574         NaClFatalOp(index, "Can't use both I_Operand and J_Operand");
 575         break;
 576       default:
 577         break;
 578     }
 579   }
 580 }
 581
 582 /* Returns the set of operand size flags defined for the given instruction. */
 583 NaClIFlags NaClOperandSizes(NaClModeledInst* inst) {
 584   NaClIFlags flags = inst->flags & (NACL_IFLAG(OperandSize_b) |
 585                                     NACL_IFLAG(OperandSize_w) |
 586                                     NACL_IFLAG(OperandSize_v) |
 587                                     NACL_IFLAG(OperandSize_o));
 588   /* Note: if no sizes specified, assume all sizes possible. */
 589   if (NACL_EMPTY_IFLAGS == flags) {
 590     flags = NACL_IFLAG(OperandSize_b) |
 591         NACL_IFLAG(OperandSize_w) |
 592         NACL_IFLAG(OperandSize_v) |
 593         NACL_IFLAG(OperandSize_o);
 594   }
 595   return flags;
 596 }
 597
 598 /* Check that the operand being defined (via the given index), does not
 599  * specify any inconsistent flags.
 600  */
 601 static void NaClApplySanityChecksToOp(int index) {
 602   const NaClOp* operand = &current_inst->operands[index];
 603   const NaClIFlags operand_sizes = NaClOperandSizes(current_inst);
 604
 605   if (!apply_sanity_checks) return;
 606
 607   /* Check that operand is consistent with other operands defined, or flags
 608    * defined on the opcode.
 609    */
 610   switch (operand->kind) {
 611     case E_Operand:
 612       NaClCheckIfERepeated(index);
 613       break;
 614     case Eb_Operand:
 615       if (NACL_IFLAG(OperandSize_b) == operand_sizes) {
 616         /* Singlton set already specifies size, so no need for extra
 617          * size specification.
 618          */
 619         NaClFatalOp(index,
 620                      "Size implied by OperandSize_b, use E_Operand instead");
 621       }
 622       NaClCheckIfERepeated(index);
 623       break;
 624     case Ew_Operand:
 625       if (NACL_IFLAG(OperandSize_w) == operand_sizes) {
 626         /* Singlton set already specifies size, so no need for extra
 627          * size specification.
 628          */
 629         NaClFatalOp(index,
 630                      "Size implied by OperandSize_w, use E_Operand instead");
 631       }
 632       NaClCheckIfERepeated(index);
 633       break;
 634     case Ev_Operand:
 635       if (NACL_IFLAG(OperandSize_v) == operand_sizes) {
 636         /* Singlton set already specifies size, so no need for extra
 637          * size specification.
 638          */
 639         NaClFatalOp(index,
 640                      "Size implied by OperandSize_v, use E_Operand instead");
 641       }
 642       NaClCheckIfERepeated(index);
 643       break;
 644     case Eo_Operand:
 645       if (NACL_IFLAG(OperandSize_o) == operand_sizes) {
 646         /* Singlton set already specifies size, so no need for extra
 647          * size specification.
 648          */
 649         NaClFatalOp(index,
 650                      "Size implied by OperandSize_o, use E_Operand instead");
 651       }
 652       NaClCheckIfERepeated(index);
 653       break;
 654     case Edq_Operand:
 655       NaClCheckIfERepeated(index);
 656       break;
 657     case Mmx_E_Operand:
 658     case Xmm_E_Operand:
 659       NaClCheckIfERepeated(index);
 660       break;
 661     case Xmm_Eo_Operand:
 662       if (NACL_IFLAG(OperandSize_o) == operand_sizes) {
 663         /* Singlton set already specifies size, so no need for extra
 664          * size specification.
 665          */
 666         NaClFatalOp
 667             (index,
 668              "Size implied by OperandSize_o, use Xmm_E_Operand instead");
 669       }
 670       NaClCheckIfERepeated(index);
 671       break;
 672     case G_Operand:
 673       NaClCheckIfGRepeated(index);
 674       NaClCheckIfOpcodeInModRm(index);
 675       break;
 676     case Gb_Operand:
 677       if (NACL_IFLAG(OperandSize_b) == operand_sizes) {
 678         /* Singlton set already specifies size, so no need for extra
 679          * size specification.
 680          */
 681         NaClFatalOp(index,
 682                      "Size implied by OperandSize_b, use G_Operand instead");
 683       }
 684       NaClCheckIfGRepeated(index);
 685       NaClCheckIfOpcodeInModRm(index);
 686       break;
 687     case Gw_Operand:
 688       if (NACL_IFLAG(OperandSize_w) == operand_sizes) {
 689         /* Singlton set already specifies size, so no need for extra
 690          * size specification.
 691          */
 692         NaClFatalOp(index,
 693                      "Size implied by OperandSize_w, use G_Operand instead");
 694       }
 695       NaClCheckIfGRepeated(index);
 696       NaClCheckIfOpcodeInModRm(index);
 697       break;
 698     case Gv_Operand:
 699       if (NACL_IFLAG(OperandSize_v) == operand_sizes) {
 700         /* Singlton set already specifies size, so no need for extra
 701          * size specification.
 702          */
 703         NaClFatalOp(index,
 704                      "Size implied by OperandSize_v, use G_Operand instead");
 705       }
 706       NaClCheckIfGRepeated(index);
 707       NaClCheckIfOpcodeInModRm(index);
 708       break;
 709     case Go_Operand:
 710       if (NACL_IFLAG(OperandSize_o) == operand_sizes) {
 711         /* Singlton set already specifies size, so no need for extra
 712          * size specification.
 713          */
 714         NaClFatalOp(index,
 715                      "Size implied by OperandSize_o, use G_Operand instead");
 716       }
 717       NaClCheckIfGRepeated(index);
 718       NaClCheckIfOpcodeInModRm(index);
 719       break;
 720     case Gdq_Operand:
 721       NaClCheckIfGRepeated(index);
 722       NaClCheckIfOpcodeInModRm(index);
 723       break;
 724     case Mmx_G_Operand:
 725     case Xmm_G_Operand:
 726       NaClCheckIfGRepeated(index);
 727       NaClCheckIfOpcodeInModRm(index);
 728       break;
 729     case Xmm_Go_Operand:
 730       if (NACL_IFLAG(OperandSize_o) == operand_sizes) {
 731         /* Singlton set already specifies size, so no need for extra
 732          * size specification.
 733          */
 734         NaClFatalOp
 735             (index,
 736              "Size implied by OperandSize_o, use Xmm_G_Operand instead");
 737       }
 738       NaClCheckIfGRepeated(index);
 739       NaClCheckIfOpcodeInModRm(index);
 740       break;
 741     case I_Operand:
 742       NaClCheckIfIRepeated(index);
 743       break;
 744     case Ib_Operand:
 745       if (NACL_IFLAG(OperandSize_b) == operand_sizes) {
 746         /* Singlton set already specifies size, so no need for extra
 747          * size specification.
 748          */
 749         NaClFatalOp(index,
 750                      "Size implied by OperandSize_b, use I_Operand instead");
 751       }
 752       if (current_inst->flags & NACL_IFLAG(OpcodeHasImmed_b)) {
 753         NaClFatalOp(index,
 754                      "Size implied by OpcodeHasImmed_b, use I_Operand instead");
 755       }
 756       NaClCheckIfIRepeated(index);
 757       break;
 758     case Iw_Operand:
 759       if (NACL_IFLAG(OperandSize_w) == operand_sizes) {
 760         /* Singlton set already specifies size, so no need for extra
 761          * size specification.
 762          */
 763         NaClFatalOp(index,
 764                      "Size implied by OperandSize_w, use I_Operand instead");
 765       }
 766       if (current_inst->flags & NACL_IFLAG(OpcodeHasImmed_w)) {
 767         NaClFatalOp(index,
 768                      "Size implied by OpcodeHasImmed_w, use I_Operand instead");
 769       }
 770       NaClCheckIfIRepeated(index);
 771       break;
 772     case Iv_Operand:
 773       if (NACL_IFLAG(OperandSize_v) == operand_sizes) {
 774         /* Singlton set already specifies size, so no need for extra
 775          * size specification.
 776          */
 777         NaClFatalOp(index,
 778                      "Size implied by OperandSize_v, use I_Operand instead");
 779       }
 780       if (current_inst->flags & NACL_IFLAG(OpcodeHasImmed_v)) {
 781         NaClFatalOp(index,
 782                      "Size implied by OpcodeHasImmed_v, use I_Operand instead");
 783       }
 784       NaClCheckIfIRepeated(index);
 785       break;
 786     case Io_Operand:
 787       if (NACL_IFLAG(OperandSize_o) == operand_sizes) {
 788         /* Singlton set already specifies size, so no need for extra
 789          * size specification.
 790          */
 791         NaClFatalOp(index,
 792                      "Size implied by OperandSize_o, use I_Operand instead");
 793       }
 794       if (current_inst->flags & NACL_IFLAG(OpcodeHasImmed_o)) {
 795         NaClFatalOp(index,
 796                      "Size implied by OpcodeHasImmed_o, use I_Operand instead");
 797       }
 798       NaClCheckIfIRepeated(index);
 799       break;
 800     default:
 801       break;
 802   }
 803 }
 804
 805 /* Define the next operand of the current opcode to have
 806  * the given kind and flags.
 807  */
 808 static void NaClDefOpInternal(NaClOpKind kind, NaClOpFlags flags) {
 809   int index;
 810   assert(NULL != current_inst);
 811   if (tables.operands_size >= NACL_MAX_OPERANDS_TOTAL) {
 812     NaClFatal("Out of operand space. "
 813               "Increase size of NACL_MAX_OPERANDS_TOTAL!");
 814   }
 815   tables.operands_size++;
 816   index = current_inst->num_operands++;
 817   current_inst->operands[index].kind = kind;
 818   current_inst->operands[index].flags = flags;
 819   current_inst->operands[index].format_string = NULL;
 820 }
 821
 822 static void NaClInstallCurrentIntoOpcodeMrm(const NaClInstPrefix prefix,
 823                                             const uint8_t opcode,
 824                                             int mrm_index) {
 825   DEBUG(NaClLog(LOG_INFO, "  Installing into [%x][%s][%d]\n",
 826                 opcode, NaClInstPrefixName(prefix), mrm_index));
 827   if (NULL == NaClInstMrmTable[opcode][prefix][mrm_index]) {
 828     NaClInstMrmTable[opcode][prefix][mrm_index] = current_inst_mrm;
 829   } else {
 830     NaClMrmInst* next = NaClInstMrmTable[opcode][prefix][mrm_index];
 831     while (NULL != next->next) {
 832       next = next->next;
 833     }
 834     next->next = current_inst_mrm;
 835   }
 836 }
 837
 838 /* Removes the current_inst_mrm from the corresponding instruction table.
 839  * Used when Opcode32Only or Opcode64Only flag is added, and
 840  * the flag doesn't match the subarchitecture being modeled.
 841  */
 842 static void NaClRemoveCurrentInstMrmFromInstTable(void) {
 843   uint8_t opcode = current_inst->opcode[current_inst->num_opcode_bytes - 1];
 844   NaClModeledInst* prev = NULL;
 845   NaClModeledInst* next = tables.inst_table[opcode][current_inst->prefix];
 846   while (NULL != next) {
 847     if (current_inst == next) {
 848       /* Found - remove! */
 849       if (NULL == prev) {
 850         tables.inst_table[opcode][current_inst->prefix] = next->next_rule;
 851       } else {
 852         prev->next_rule = next->next_rule;
 853       }
 854       return;
 855     } else  {
 856       prev = next;
 857       next = next->next_rule;
 858     }
 859   }
 860 }
 861
 862 /* Removes the current_inst_mrm from the corresponding
 863  * NaClInstMrmTable.
 864  *
 865  * Used when Opcode32Only or Opcode64Only flag is added, and
 866  * the flag doesn't match the subarchitecture being modeled.
 867  */
 868 static void NaClRemoveCurrentInstMrmFromInstMrmTable(void) {
 869   /* Be sure to try opcode in first operand (if applicable),
 870    * and the default list NACL_NO_MODRM_OPCODE, in case
 871    * the operand hasn't been processed yet.
 872    */
 873   int mrm_opcode = NACL_NO_MODRM_OPCODE;
 874   if (current_inst->flags & NACL_IFLAG(OpcodeInModRm)) {
 875     mrm_opcode = NaClGetOpcodeInModRm(current_inst->opcode_ext);
 876   }
 877
 878   while (1) {
 879     uint8_t opcode = current_inst->opcode[current_inst->num_opcode_bytes - 1];
 880     NaClMrmInst* prev = NULL;
 881     NaClMrmInst* next =
 882         NaClInstMrmTable[opcode][current_inst->prefix][mrm_opcode];
 883     DEBUG(NaClLog(LOG_INFO, "Removing [%02x][%s][%d]?",
 884                   opcode, NaClInstPrefixName(current_inst->prefix),
 885                   mrm_opcode));
 886     while (NULL != next) {
 887       if (current_inst_mrm == next) {
 888         /* Found - remove! */
 889         if (NULL == prev) {
 890           NaClInstMrmTable[opcode][current_inst->prefix][mrm_opcode] =
 891               next->next;
 892         } else {
 893           prev->next = next->next;
 894         }
 895         return;
 896       } else {
 897         prev = next;
 898         next = next->next;
 899       }
 900     }
 901     if (mrm_opcode == NACL_NO_MODRM_OPCODE) return;
 902     mrm_opcode = NACL_NO_MODRM_OPCODE;
 903   }
 904 }
 905
 906 static void NaClMoveCurrentToMrmIndex(int mrm_index) {
 907   /* First remove from default location. */
 908   uint8_t opcode = current_inst->opcode[current_inst->num_opcode_bytes - 1];
 909   NaClMrmInst* prev = NULL;
 910   NaClMrmInst* next =
 911       NaClInstMrmTable[opcode][current_opcode_prefix]
 912                       [NACL_NO_MODRM_OPCODE];
 913   while (current_inst_mrm != next) {
 914     if (next == NULL) return;
 915     prev = next;
 916     next = next->next;
 917   }
 918   if (NULL == prev) {
 919     NaClInstMrmTable[opcode][current_opcode_prefix]
 920                     [NACL_NO_MODRM_OPCODE] =
 921         next->next;
 922   } else {
 923     prev->next = next->next;
 924   }
 925   current_inst_mrm = next;
 926   current_inst_mrm->next = NULL;
 927   NaClInstallCurrentIntoOpcodeMrm(current_opcode_prefix, opcode, mrm_index);
 928 }
 929
 930 static void NaClPrintlnOpFlags(struct Gio* g, NaClOpFlags flags) {
 931   int i;
 932   for (i = 0; i < NaClOpFlagEnumSize; ++i) {
 933     if (flags & NACL_OPFLAG(i)) {
 934       gprintf(g, " %s", NaClOpFlagName(i));
 935     }
 936   }
 937   gprintf(g, "\n");
 938 }
 939
 940 static void NaClApplySanityChecksToInst(void);
 941
 942 void NaClDefOpcodeExtension(int opcode) {
 943   uint8_t byte_opcode;
 944   byte_opcode = (uint8_t) opcode;
 945   if ((opcode < 0) || (opcode > 7)) {
 946     NaClFatalInst("Attempted to define opcode extension not in range [0..7]");
 947   }
 948   if (NACL_EMPTY_IFLAGS ==
 949       (current_inst->flags & NACL_IFLAG(OpcodeInModRm))) {
 950     NaClFatalInst(
 951         "Opcode extension in [0..7], but not OpcodeInModRm");
 952   }
 953   DEBUG(NaClLog(LOG_INFO, "Defining opcode extension %d\n", opcode));
 954   NaClMoveCurrentToMrmIndex(byte_opcode);
 955   NaClSetOpcodeInModRm(byte_opcode, &current_inst->opcode_ext);
 956 }
 957
 958 void NaClDefineOpcodeModRmRmExtension(int value) {
 959   uint8_t byte_opcode = (uint8_t) value;
 960   if ((value < 0) || (value > 7)) {
 961     NaClFatalInst("Attempted to defined Opcode modrm rm extension "
 962                   "not in range [0..7]");
 963   }
 964   if (NACL_EMPTY_IFLAGS ==
 965       (current_inst->flags & NACL_IFLAG(OpcodeInModRm))) {
 966     NaClFatalInst(
 967         "Opcode modrm rm extension in [0..7], but not OpcodeInModRm");
 968   }
 969   DEBUG(NaClLog(LOG_INFO, "Defining modrm r/m opcode extension %d", value));
 970   NaClAddIFlags(NACL_IFLAG(OpcodeInModRmRm));
 971   if (current_inst->num_opcode_bytes + 1 < NACL_MAX_ALL_OPCODE_BYTES) {
 972     NaClSetOpcodeInModRmRm(byte_opcode, &current_inst->opcode_ext);
 973   } else {
 974     NaClFatalInst("No room for opcode modrm rm extension");
 975   }
 976 }
 977
 978 void NaClDefOpcodeRegisterValue(int r) {
 979   uint8_t byte_r;
 980   byte_r = (uint8_t) r;
 981   if ((r < 0) || (r > 7)) {
 982     NaClFatalInst("Attempted to define an embedded opcode register value "
 983                   "not in range [0.. 7]");
 984   }
 985   if (NACL_EMPTY_IFLAGS ==
 986       (current_inst->flags & NACL_IFLAG(OpcodePlusR))) {
 987     NaClFatalInst(
 988         "Attempted to define opcode register value when not OpcodePlusR");
 989   }
 990   NaClSetOpcodePlusR(byte_r, &current_inst->opcode_ext);
 991 }
 992
 993 /* Same as previous function, except that sanity checks
 994  * are applied to see if inconsistent information is
 995  * being defined.
 996  */
 997 void NaClDefOp(
 998     NaClOpKind kind,
 999     NaClOpFlags flags) {
1000   int index = current_inst->num_operands;
1001   DEBUG(NaClLog(LOG_INFO, "  %s:", NaClOpKindName(kind));
1002         NaClPrintlnOpFlags(NaClLogGetGio(), flags));
1003   /* If one of the M_Operands, make sure that the ModRm mod field isn't 0x3,
1004    * so that we don't return registers.
1005    * If one specifies an operand that implies the use of a ModRm byte, add
1006    * the corresponding flag.
1007    * Note: See section A.2.5 of Intel manual (above) for an explanation of the
1008    * ModRm mod field being any value except 0x3, for values having an
1009    * explicit memory operand.
1010    */
1011   switch (kind) {
1012     case M_Operand:
1013     case Mb_Operand:
1014     case Mw_Operand:
1015     case Mv_Operand:
1016     case Mo_Operand:
1017     case Mdq_Operand:
1018     case Mpw_Operand:
1019     case Mpv_Operand:
1020     case Mpo_Operand:
1021       NaClAddIFlags(NACL_IFLAG(OpcodeUsesModRm) | NACL_IFLAG(ModRmModIsnt0x3));
1022       break;
1023     case Mmx_N_Operand:
1024       kind = Mmx_E_Operand;
1025       NaClAddIFlags(NACL_IFLAG(OpcodeUsesModRm) | NACL_IFLAG(ModRmModIs0x3));
1026       /* Automatically fall to the next case. */
1027     case E_Operand:
1028     case Eb_Operand:
1029     case Ew_Operand:
1030     case Ev_Operand:
1031     case Eo_Operand:
1032     case Edq_Operand:
1033     case G_Operand:
1034     case Gb_Operand:
1035     case Gw_Operand:
1036     case Gv_Operand:
1037     case Go_Operand:
1038     case Gdq_Operand:
1039     case Mmx_G_Operand:
1040     case Mmx_Gd_Operand:
1041     case Xmm_E_Operand:
1042     case Xmm_Eo_Operand:
1043     case Xmm_G_Operand:
1044     case Xmm_Go_Operand:
1045       NaClAddIFlags(NACL_IFLAG(OpcodeUsesModRm));
1046       break;
1047     default:
1048       break;
1049   }
1050   /* Define and apply sanity checks. */
1051   NaClDefOpInternal(kind, flags);
1052   NaClApplySanityChecksToOp(index);
1053 }
1054
1055 void NaClAddOpFlags(uint8_t operand_index, NaClOpFlags more_flags) {
1056   DEBUG(
1057       struct Gio* g = NaClLogGetGio();
1058       gprintf(g, "Adding flags:");
1059       NaClPrintlnOpFlags(g, more_flags));
1060   if (operand_index < current_inst->num_operands) {
1061     NaClAddBits(current_inst->operands[operand_index].flags, more_flags);
1062     NaClApplySanityChecksToOp(operand_index);
1063   } else {
1064     NaClFatalOp((int) operand_index, "NaClAddOpFlags: index out of range\n");
1065   }
1066 }
1067
1068 void NaClRemoveOpFlags(uint8_t operand_index, NaClOpFlags more_flags) {
1069   DEBUG(NaClLog(LOG_INFO, "Removing flags:");
1070         NaClPrintlnOpFlags(NaClLogGetGio(), more_flags));
1071   if (operand_index < current_inst->num_operands) {
1072     NaClRemoveBits(current_inst->operands[operand_index].flags, more_flags);
1073     NaClApplySanityChecksToOp(operand_index);
1074   } else {
1075     NaClFatalOp((int) operand_index, "NaClRemoveOpFlags: index out of range\n");
1076   }
1077 }
1078
1079 void NaClAddOpFormat(uint8_t operand_index, const char* format) {
1080   DEBUG(NaClLog(LOG_INFO, "Adding format[%"NACL_PRIu8"]: '%s'\n",
1081                 operand_index, format));
1082   if (operand_index < current_inst->num_operands) {
1083     current_inst->operands[operand_index].format_string =
1084         strdup(format);
1085   } else {
1086     NaClFatalOp((int) operand_index, "NaClAddOpFormat: index out of range\n");
1087   }
1088 }
1089
1090 /* Returns true if the given opcode flags are consistent
1091  * with the value of NACL_FLAGS_run_mode.
1092  */
1093 static Bool NaClIFlagsMatchesRunMode(NaClIFlags flags) {
1094   if (flags & NACL_IFLAG(Opcode32Only)) {
1095     if (flags & NACL_IFLAG(Opcode64Only)) {
1096       NaClFatal("Can't specify both Opcode32Only and Opcode64Only");
1097     }
1098     return NACL_FLAGS_run_mode == X86_32;
1099   } else if (flags & NACL_IFLAG(Opcode64Only)) {
1100     return NACL_FLAGS_run_mode == X86_64;
1101   } else if (flags & NACL_IFLAG(Opcode32Only)) {
1102     return NACL_FLAGS_run_mode == X86_32;
1103   } else {
1104     return TRUE;
1105   }
1106 }
1107
1108 /* Check that the flags defined for an opcode make sense. */
1109 static void NaClApplySanityChecksToInst(void) {
1110   const NaClIFlags operand_sizes = NaClOperandSizes(current_inst);
1111   if (!apply_sanity_checks) return;
1112   if ((current_inst->flags & NACL_IFLAG(Opcode32Only)) &&
1113       (current_inst->flags & NACL_IFLAG(Opcode64Only))) {
1114     NaClFatalInst("Can't be both Opcode32Only and Opcode64Only");
1115   }
1116   /* Fix case where both OperandSize_w and SizeIgnoresData16 are specified. */
1117   if ((current_inst->flags & NACL_IFLAG(OperandSize_w)) &&
1118       (current_inst->flags & NACL_IFLAG(SizeIgnoresData16))) {
1119     NaClRemoveBits(current_inst->flags, NACL_IFLAG(OperandSize_w));
1120   }
1121   if ((current_inst->flags & NACL_IFLAG(OperandSize_b)) &&
1122       (current_inst->flags & (NACL_IFLAG(OperandSize_w) |
1123                               NACL_IFLAG(OperandSize_v) |
1124                               NACL_IFLAG(OperandSize_o) |
1125                               NACL_IFLAG(OperandSizeDefaultIs64) |
1126                               NACL_IFLAG(OperandSizeForce64)))) {
1127     NaClFatalInst(
1128         "Can't specify other operand sizes when specifying OperandSize_b");
1129   }
1130   if ((current_inst->flags & NACL_IFLAG(OpcodeInModRm)) &&
1131       (current_inst->flags & NACL_IFLAG(OpcodePlusR))) {
1132     NaClFatalInst(
1133         "Can't specify both OpcodeInModRm and OpcodePlusR");
1134   }
1135   if ((current_inst->flags & NACL_IFLAG(OpcodeHasImmed_b)) &&
1136       (operand_sizes == NACL_IFLAG(OperandSize_b))) {
1137     NaClFatalInst(
1138         "Size implied by OperandSize_b, use OpcodeHasImmed "
1139         "rather than OpcodeHasImmed_b");
1140   }
1141   if ((current_inst->flags & NACL_IFLAG(OpcodeHasImmed_w)) &&
1142       (operand_sizes == NACL_IFLAG(OperandSize_w))) {
1143     NaClFatalInst(
1144         "Size implied by OperandSize_w, use OpcodeHasImmed "
1145         "rather than OpcodeHasImmed_w");
1146   }
1147   if ((current_inst->flags & NACL_IFLAG(OpcodeHasImmed_v)) &&
1148       (operand_sizes == NACL_IFLAG(OperandSize_v))) {
1149     NaClFatalInst(
1150         "Size implied by OperandSize_v, use OpcodeHasImmed "
1151         "rather than OpcodeHasImmed_v");
1152   }
1153   if ((current_inst->flags & NACL_IFLAG(ModRmModIs0x3)) &&
1154       (NACL_EMPTY_IFLAGS == (current_inst->flags &
1155                              (NACL_IFLAG(OpcodeUsesModRm) |
1156                               NACL_IFLAG(OpcodeInModRm))))) {
1157     NaClFatalInst(
1158         "Can't specify ModRmModIs0x3 unless Opcode has modrm byte");
1159   }
1160   if ((current_inst->flags & NACL_IFLAG(ModRmModIs0x3)) &&
1161       (current_inst->flags & NACL_IFLAG(ModRmModIsnt0x3))) {
1162     NaClFatalInst(
1163         "Can't specify ModRmModIs0x3 and ModRmModIsnt0x3");
1164   }
1165 }
1166
1167 static void NaClDefBytes(uint8_t opcode) {
1168   uint8_t index;
1169   current_inst->prefix = current_opcode_prefix;
1170
1171   /* Start by clearing all entries. */
1172   for (index = 0; index < NACL_MAX_ALL_OPCODE_BYTES; ++index) {
1173     current_inst->opcode[index] = 0x00;
1174   }
1175
1176   /* Now fill in non-final bytes. */
1177   index = 0;
1178   switch (current_opcode_prefix) {
1179     case NoPrefix:
1180       break;
1181     case Prefix0F:
1182     case Prefix660F:
1183     case PrefixF20F:
1184     case PrefixF30F:
1185       current_inst->opcode[0] = 0x0F;
1186       index = 1;
1187       break;
1188     case Prefix0F0F:
1189       current_inst->opcode[0] = 0x0F;
1190       current_inst->opcode[1] = 0x0F;
1191       index = 2;
1192       break;
1193     case Prefix0F38:
1194     case Prefix660F38:
1195     case PrefixF20F38:
1196       current_inst->opcode[0] = 0x0F;
1197       current_inst->opcode[1] = 0x38;
1198       index = 2;
1199       break;
1200     case Prefix0F3A:
1201     case Prefix660F3A:
1202       current_inst->opcode[0] = 0x0F;
1203       current_inst->opcode[1] = 0x3A;
1204       index = 2;
1205       break;
1206     case PrefixD8:
1207       current_inst->opcode[0] = 0xD8;
1208       index = 1;
1209       break;
1210     case PrefixD9:
1211       current_inst->opcode[0] = 0xD9;
1212       index = 1;
1213       break;
1214     case PrefixDA:
1215       current_inst->opcode[0] = 0xDA;
1216       index = 1;
1217       break;
1218     case PrefixDB:
1219       current_inst->opcode[0] = 0xDB;
1220       index = 1;
1221       break;
1222     case PrefixDC:
1223       current_inst->opcode[0] = 0xDC;
1224       index = 1;
1225       break;
1226     case PrefixDD:
1227       current_inst->opcode[0] = 0xDD;
1228       index = 1;
1229       break;
1230     case PrefixDE:
1231       current_inst->opcode[0] = 0xDE;
1232       index = 1;
1233       break;
1234     case PrefixDF:
1235       current_inst->opcode[0] = 0xDF;
1236       index = 1;
1237       break;
1238     default:
1239       NaClFatal("Unrecognized opcode prefix in NaClDefBytes");
1240       break;
1241   }
1242
1243   /* Now add final byte. */
1244   current_inst->opcode[index] = opcode;
1245   current_inst->num_opcode_bytes = index + 1;
1246 }
1247
1248 static void NaClPrintInstDescriptor(struct Gio* out,
1249                                     const NaClInstPrefix prefix,
1250                                     const int opcode,
1251                                     const int modrm_index) {
1252   if (NACL_NO_MODRM_OPCODE == modrm_index) {
1253     gprintf(out, "%s 0x%02x: ",
1254             NaClInstPrefixName(prefix), opcode);
1255   } else {
1256     gprintf(out, "%s 0x%02x /%x: ",
1257             NaClInstPrefixName(prefix), opcode, modrm_index);
1258   }
1259 }
1260
1261 static void VerifyModRmOpcodeRange(NaClInstPrefix prefix,
1262                                    uint8_t opcode,
1263                                    uint8_t modrm_opcode) {
1264   if (modrm_opcode > NACL_NO_MODRM_OPCODE) {
1265     NaClPrintInstDescriptor(NaClLogGetGio(), prefix, opcode, modrm_opcode);
1266     NaClFatal("Illegal modrm opcode specification when defined opcode choices");
1267   }
1268 }
1269
1270 void NaClDefPrefixInstMrmChoices_32_64(const NaClInstPrefix prefix,
1271                                        const uint8_t opcode,
1272                                        const uint8_t modrm_opcode,
1273                                        const int count_32,
1274                                        const int count_64) {
1275   VerifyModRmOpcodeRange(prefix, opcode, modrm_opcode);
1276   if (NaClInstCount[opcode][prefix][modrm_opcode] !=
1277       NACL_DEFAULT_CHOICE_COUNT) {
1278     NaClPrintInstDescriptor(NaClLogGetGio(), prefix, opcode, modrm_opcode);
1279     NaClFatal("Redefining NaClOpcode choice count");
1280   }
1281   if (NACL_FLAGS_run_mode == X86_32) {
1282     NaClInstCount[opcode][prefix][modrm_opcode] = count_32;
1283   } else if (NACL_FLAGS_run_mode == X86_64) {
1284     NaClInstCount[opcode][prefix][modrm_opcode] = count_64;
1285   }
1286 }
1287
1288 void NaClDefPrefixInstChoices(const NaClInstPrefix prefix,
1289                               const uint8_t opcode,
1290                               const int count) {
1291   NaClDefPrefixInstChoices_32_64(prefix, opcode, count, count);
1292 }
1293
1294 void NaClDefPrefixInstMrmChoices(const NaClInstPrefix prefix,
1295                                  const uint8_t opcode,
1296                                  const uint8_t modrm_opcode,
1297                                  const int count) {
1298   NaClDefPrefixInstMrmChoices_32_64(prefix, opcode, modrm_opcode,
1299                                          count, count);
1300 }
1301
1302 void NaClDefPrefixInstChoices_32_64(const NaClInstPrefix prefix,
1303                                     const uint8_t opcode,
1304                                     const int count_32,
1305                                     const int count_64) {
1306   NaClDefPrefixInstMrmChoices_32_64(prefix, opcode, NACL_NO_MODRM_OPCODE,
1307                                     count_32, count_64);
1308 }
1309
1310 /* Adds opcode flags corresponding to REP/REPNE flags if defined by
1311  * the prefix.
1312  */
1313 static void NaClAddRepPrefixFlagsIfApplicable(void) {
1314   switch (current_opcode_prefix) {
1315     case Prefix660F:
1316     case Prefix660F38:
1317     case Prefix660F3A:
1318       NaClAddBits(current_inst->flags, NACL_IFLAG(OpcodeAllowsData16) |
1319                   NACL_IFLAG(SizeIgnoresData16));
1320       break;
1321     case PrefixF20F:
1322     case PrefixF20F38:
1323       NaClAddBits(current_inst->flags, NACL_IFLAG(OpcodeAllowsRepne));
1324       break;
1325     case PrefixF30F:
1326       NaClAddBits(current_inst->flags, NACL_IFLAG(OpcodeAllowsRep));
1327       break;
1328     default:
1329       break;
1330   }
1331 }
1332
1333 /* Define the next opcode (instruction), initializing with
1334  * no operands.
1335  */
1336 static void NaClDefInstInternal(
1337     const uint8_t opcode,
1338     const NaClInstType insttype,
1339     NaClIFlags flags,
1340     const NaClMnemonic name,
1341     Bool no_install) {
1342   /* TODO(karl) If we can deduce a more specific prefix that
1343    * must be used, due to the flags associated with the opcode,
1344    * then put on the more specific prefix list. This will make
1345    * the defining of instructions easier, in that the caller doesn't
1346    * need to specify the prefix to use.
1347    */
1348
1349   /* Before starting, install an opcode sequence if applicable. */
1350   if (NULL != current_cand_inst_node) {
1351     current_inst_node = current_cand_inst_node;
1352   }
1353   current_cand_inst_node = NULL;
1354
1355   /* Before starting, expand appropriate implicit flag assumnptions. */
1356   if (flags & NACL_IFLAG(OpcodeLtC0InModRm)) {
1357     NaClAddBits(flags, NACL_IFLAG(OpcodeInModRm) | NACL_IFLAG(ModRmModIsnt0x3));
1358   }
1359
1360   DEBUG(NaClLog(LOG_INFO, "Define %s %"NACL_PRIx8": %s(%02x)\n",
1361                 NaClInstPrefixName(current_opcode_prefix),
1362                 opcode, NaClMnemonicName(name), name);
1363         NaClIFlagsPrint(NaClLogGetGio(), flags));
1364
1365   if (NaClMnemonicEnumSize <= name) {
1366     NaClFatal("Badly defined mnemonic name");
1367   }
1368
1369   if (kNaClInstTypeRange <= insttype) {
1370     NaClFatal("Badly defined inst type");
1371   }
1372
1373   /* Create opcode and initialize */
1374   current_inst_mrm = (NaClMrmInst*) malloc(sizeof(NaClMrmInst));
1375   if (NULL == current_inst_mrm) {
1376     NaClFatal("NaClDefInst: malloc failed");
1377   }
1378   DEBUG(NaClLog(LOG_INFO,
1379                 "current = %p\n", (void*) current_inst_mrm));
1380   current_inst_mrm->next = NULL;
1381   current_inst = &(current_inst_mrm->inst);
1382   NaClDefBytes(opcode);
1383   current_inst->insttype = insttype;
1384   current_inst->flags = NACL_EMPTY_IFLAGS;
1385   current_inst->name = name;
1386   current_inst->opcode_ext = 0;
1387   current_inst->next_rule = NULL;
1388
1389   /* undefine all operands. */
1390   current_inst->num_operands = 0;
1391   current_inst->operands = tables.operands + tables.operands_size;
1392
1393   NaClAddIFlags(flags);
1394
1395   NaClAddRepPrefixFlagsIfApplicable();
1396
1397   NaClApplySanityChecksToInst();
1398
1399   if (no_install || !NaClIFlagsMatchesRunMode(flags)) {
1400     return;
1401   }
1402
1403   if (NULL == current_inst_node) {
1404     /* Install NaClOpcode. */
1405     DEBUG(NaClLog(LOG_INFO, "  standard install\n"));
1406     if (NULL == tables.inst_table[opcode][current_opcode_prefix]) {
1407       tables.inst_table[opcode][current_opcode_prefix] = current_inst;
1408     } else {
1409       NaClModeledInst* next = tables.inst_table[opcode][current_opcode_prefix];
1410       while (NULL != next->next_rule) {
1411         next = next->next_rule;
1412       }
1413       next->next_rule = current_inst;
1414     }
1415     /* Install assuming no modrm opcode. Let NaClDefOp move if needed. */
1416     NaClInstallCurrentIntoOpcodeMrm(current_opcode_prefix, opcode,
1417                                 NACL_NO_MODRM_OPCODE);
1418   } else if (NULL == current_inst_node->matching_inst) {
1419     DEBUG(NaClLog(LOG_INFO, "  instruction sequence install\n"));
1420     current_inst_node->matching_inst = current_inst;
1421   } else {
1422     NaClFatalInst(
1423         "Can't define more than one opcode for the same opcode sequence");
1424   }
1425 }
1426
1427 void NaClDefInst(
1428     const uint8_t opcode,
1429     const NaClInstType insttype,
1430     NaClIFlags flags,
1431     const NaClMnemonic name) {
1432   NaClDefInstInternal(opcode, insttype, flags, name, FALSE);
1433 }
1434
1435 /* Simple (fast hack) routine to extract a byte value from a character string.
1436  */
1437 static int NaClExtractByte(const char* chars, const char* opcode_seq) {
1438   char buffer[3];
1439   int i;
1440   for (i = 0; i < 2; ++i) {
1441     char ch = *(chars++);
1442     if ('\0' == ch) {
1443       NaClLog(LOG_ERROR,
1444               "Odd number of characters in opcode sequence: '%s'\n",
1445               opcode_seq);
1446       NaClFatal("Fix before continuing!");
1447     }
1448     buffer[i] = ch;
1449   }
1450   buffer[2] = '\0';
1451   return strtoul(buffer, NULL, 16);
1452 }
1453
1454 static NaClModeledInstNode* NaClNewInstNode(uint8_t byte) {
1455   NaClModeledInstNode* root =
1456       (NaClModeledInstNode*) malloc(sizeof(NaClModeledInstNode));
1457   root->matching_byte = byte;
1458   root->matching_inst = NULL;
1459   root->success = NULL;
1460   root->fail = NULL;
1461   return root;
1462 }
1463
1464 /* Install an opcode sequence into the instruction trie. */
1465 static void NaClDefInstSeq(const char* opcode_seq) {
1466   /* Next is a (reference) pointer to the next node. The reference
1467    * is used so that we can easily update the trie when we add nodes.
1468    */
1469   NaClModeledInstNode** next = &tables.inst_node_root;
1470   /* Last is the last visited node in trie that is still matching
1471    * the opcode sequence being added.
1472    */
1473   NaClModeledInstNode* last = NULL;
1474   /* Index is the position of the next byte in the opcode sequence. */
1475   int index = 0;
1476
1477   /* First check that opcode sequence not defined twice without a corresponding
1478    * call to NaClDefInst.
1479    */
1480   if (NULL != current_cand_inst_node) {
1481     NaClLog(LOG_ERROR,
1482             "Multiple definitions for opcode sequence: '%s'\n", opcode_seq);
1483     NaClFatal("Fix before continuing!");
1484   }
1485
1486   /* Now install into lookup trie. */
1487   while (opcode_seq[index]) {
1488     uint8_t byte = (uint8_t) NaClExtractByte(opcode_seq + index, opcode_seq);
1489     if (index >= 2 * NACL_MAX_BYTES_PER_X86_INSTRUCTION) {
1490       NaClLog(LOG_ERROR,
1491               "Too many bytes specified for opcode sequence: '%s'\n",
1492               opcode_seq);
1493       NaClFatal("Fix before continuing!\n");
1494     }
1495     if ((NULL == *next) || (byte < (*next)->matching_byte)) {
1496       /* byte not in trie, add. */
1497       NaClModeledInstNode* node = NaClNewInstNode(byte);
1498       node->fail = *next;
1499       *next = node;
1500     }
1501     if (byte == (*next)->matching_byte) {
1502       last = *next;
1503       next = &((*next)->success);
1504       index += 2;
1505     } else {
1506       next = &((*next)->fail);
1507     }
1508   }
1509   /* Last points to matching node, make it candidate instruction. */
1510   current_cand_inst_node = last;
1511 }
1512
1513 /* Apply checks to current instruction flags, and update model as
1514  * appropriate.
1515  */
1516 static void NaClRecheckIFlags(void) {
1517   if (!NaClIFlagsMatchesRunMode(current_inst->flags)) {
1518     NaClRemoveCurrentInstMrmFromInstTable();
1519     NaClRemoveCurrentInstMrmFromInstMrmTable();
1520   }
1521   /* If the instruction has an opcode in modrm, then it uses modrm. */
1522   if (NACL_EMPTY_IFLAGS != (current_inst->flags & NACL_IFLAG(OpcodeInModRm))) {
1523     NaClAddBits(current_inst->flags, NACL_IFLAG(OpcodeUsesModRm));
1524   }
1525   /* If the instruction allows a two byte value, add DATA16 flag. */
1526   if (NACL_EMPTY_IFLAGS != (current_inst->flags &
1527                             (NACL_IFLAG(OperandSize_w) |
1528                              NACL_IFLAG(OpcodeHasImmed_z)))) {
1529     NaClAddBits(current_inst->flags, NACL_IFLAG(OpcodeAllowsData16));
1530   }
1531   /* If the instruction uses the modrm rm field as an opcode value,
1532    * it also requires that the modrm mod field is 0x3.
1533    */
1534   if (current_inst->flags & NACL_IFLAG(OpcodeInModRmRm)) {
1535     NaClAddBits(current_inst->flags, NACL_IFLAG(ModRmModIs0x3));
1536   }
1537   NaClApplySanityChecksToInst();
1538 }
1539
1540 void NaClAddIFlags(NaClIFlags more_flags) {
1541   DEBUG(
1542       struct Gio* g = NaClLogGetGio();
1543       NaClLog(LOG_INFO, "Adding instruction flags: ");
1544       NaClIFlagsPrint(g, more_flags);
1545       gprintf(g, "\n"));
1546   NaClAddBits(current_inst->flags, more_flags);
1547   NaClRecheckIFlags();
1548 }
1549
1550 void NaClRemoveIFlags(NaClIFlags less_flags) {
1551   DEBUG(
1552       struct Gio* g = NaClLogGetGio();
1553       NaClLog(LOG_INFO, "Removing instruction flags: ");
1554       NaClIFlagsPrint(g, less_flags);
1555       gprintf(g, "\n"));
1556   NaClRemoveBits(current_inst->flags, less_flags);
1557   NaClRecheckIFlags();
1558 }
1559
1560 void NaClDelaySanityChecks(void) {
1561   apply_sanity_checks = FALSE;
1562 }
1563
1564 void NaClApplySanityChecks(void) {
1565   apply_sanity_checks = TRUE;
1566   if (NULL != current_inst) {
1567     int i;
1568     NaClApplySanityChecksToInst();
1569     for (i = 0; i < current_inst->num_operands; i++) {
1570       NaClApplySanityChecksToOp(i);
1571     }
1572   }
1573 }
1574
1575 static void NaClInitInstTables(void) {
1576   int i;
1577   NaClInstPrefix prefix;
1578   int j;
1579   /* Before starting, verify that we have defined NaClOpcodeFlags
1580    * and NaClOpFlags big enough to hold the flags associated with it.
1581    */
1582   assert(NaClIFlagEnumSize <= sizeof(NaClIFlags) * 8);
1583   assert(NaClOpFlagEnumSize <= sizeof(NaClOpFlags) * 8);
1584   assert(NaClDisallowsFlagEnumSize <= sizeof(NaClDisallowsFlags) * 8);
1585
1586   for (i = 0; i < NCDTABLESIZE; ++i) {
1587     for (prefix = NoPrefix; prefix < NaClInstPrefixEnumSize; ++prefix) {
1588       tables.inst_table[i][prefix] = NULL;
1589       for (j = 0; j <= NACL_NO_MODRM_OPCODE; ++j) {
1590         NaClInstCount[i][prefix][j] = NACL_DEFAULT_CHOICE_COUNT;
1591       }
1592     }
1593     NaClPrefixTable[i] = "0";
1594   }
1595   NaClDefInstPrefix(NoPrefix);
1596   NaClDefInstInternal(0x0, NACLi_INVALID, 0, InstInvalid, TRUE);
1597   tables.undefined_inst = current_inst;
1598 }
1599
1600 static void NaClDefPrefixBytes(void) {
1601   NaClEncodePrefixName(kValueSEGES,  "kPrefixSEGES");
1602   NaClEncodePrefixName(kValueSEGCS,  "kPrefixSEGCS");
1603   NaClEncodePrefixName(kValueSEGSS,  "kPrefixSEGSS");
1604   NaClEncodePrefixName(kValueSEGDS,  "kPrefixSEGDS");
1605   NaClEncodePrefixName(kValueSEGFS,  "kPrefixSEGFS");
1606   NaClEncodePrefixName(kValueSEGGS,  "kPrefixSEGGS");
1607   NaClEncodePrefixName(kValueDATA16, "kPrefixDATA16");
1608   NaClEncodePrefixName(kValueADDR16, "kPrefixADDR16");
1609   NaClEncodePrefixName(kValueLOCK,   "kPrefixLOCK");
1610   NaClEncodePrefixName(kValueREPNE,  "kPrefixREPNE");
1611   NaClEncodePrefixName(kValueREP,    "kPrefixREP");
1612
1613   if (NACL_FLAGS_run_mode == X86_64) {
1614     int i;
1615     for (i = 0; i < 16; ++i) {
1616       NaClEncodePrefixName(0x40+i, "kPrefixREX");
1617     }
1618   }
1619 }
1620
1621 /* Define the given character sequence, associated with the given byte
1622  * opcode and instruction mnemonic, as a nop.
1623  */
1624 static void NaClDefNopLikeSeq(const char* sequence, uint8_t opcode,
1625                               NaClMnemonic name ) {
1626   NaClDefInstSeq(sequence);
1627   NaClDefInst(opcode, NACLi_386, NACL_EMPTY_IFLAGS, name);
1628 }
1629
1630 /* Define the given character sequence, associated with the given byte
1631  * opcode, as a nop.
1632  */
1633 static void NaClDefNopSeq(const char* sequence, uint8_t opcode) {
1634   NaClDefNopLikeSeq(sequence, opcode, InstNop);
1635 }
1636
1637 static void NaClDefNops(void) {
1638   /* Note: The following could be recognized as nops, but are already
1639    * parsed and accepted by the validator.
1640    *
1641    * 89 f6             mov %esi, %esi
1642    * 8d742600          lea %esi, [%rsi]
1643    * 8d7600            lea %esi, [%rsi]
1644    * 8d b6 00 00 00 00 lea %esi, [%rsi]
1645    * 8d b4 26 00 00 00 00 lea %esi, [%rsi]
1646    * 8d bc 27 00 00 00 00 lea %edi, [%rdi]
1647    * 8d bf 00 00 00 00 lea %edi, [%rdi]
1648    * 0f 1f 00                                     nop
1649    * 0f 1f 40 00                                  nop
1650    * 0f 1f 44 00 00                               nop
1651    * 0f 1f 80 00 00 00 00                         nop
1652    * 0f 1f 84 00 00 00 00 00                      nop
1653    */
1654   /* Note: For performance reasons, the function NaClMaybeHardCodedNop in
1655    * src/trusted/validator/x86/decoder/nc_inst_state.c
1656    * has been tuned to not look for these Nop instructions, unless
1657    * the opcode byte sequence is one of "90", "0f1f",  or "0f0b". If you add
1658    * any nop instruction that doesn't meet this criteria, be sure
1659    * to update NaClMaybeHardCodedNop accordingly.
1660    */
1661   /* nop */
1662   NaClDefNopSeq("90", 0x90);
1663   NaClDefNopSeq("6690", 0x90);
1664   NaClDefNopLikeSeq("f390", 0x90, InstPause);
1665   /* nop [%[re]ax] */
1666   NaClDefNopSeq("0f1f00", 0x1f);
1667   /* nop [%[re]ax+0] */
1668   NaClDefNopSeq("0f1f4000", 0x1f);
1669   /* nop [%[re]ax*1+0] */
1670   NaClDefNopSeq("0f1f440000", 0x1f);
1671   /* nop [%[re]ax+%[re]ax*1+0] */
1672   NaClDefNopSeq("660f1f440000", 0x1f);
1673   /* nop [%[re]ax+0] */
1674   NaClDefNopSeq("0f1f8000000000", 0x1f);
1675   /* nop [%[re]ax+%[re]ax*1+0] */
1676   NaClDefNopSeq("0f1f840000000000", 0x1f);
1677   /* nop [%[re]ax+%[re]ax+1+0] */
1678   NaClDefNopSeq("660f1f840000000000", 0x1f);
1679   /* nop %cs:[%re]ax+%[re]ax*1+0] */
1680   NaClDefNopSeq("662e0f1f840000000000", 0x1f);
1681   /* nop %cs:[%re]ax+%[re]ax*1+0] */
1682   NaClDefNopSeq("66662e0f1f840000000000", 0x1f);
1683   /* nop %cs:[%re]ax+%[re]ax*1+0] */
1684   NaClDefNopSeq("6666662e0f1f840000000000", 0x1f);
1685   /* nop %cs:[%re]ax+%[re]ax*1+0] */
1686   NaClDefNopSeq("666666662e0f1f840000000000", 0x1f);
1687   /* nop %cs:[%re]ax+%[re]ax*1+0] */
1688   NaClDefNopSeq("66666666662e0f1f840000000000", 0x1f);
1689   /* nop %cs:[%re]ax+%[re]ax*1+0] */
1690   NaClDefNopSeq("6666666666662e0f1f840000000000", 0x1f);
1691   /* UD2 */
1692   NaClDefNopLikeSeq("0f0b", 0x0b, InstUd2);
1693 }
1694
1695 /* Build the set of x64 opcode (instructions). */
1696 static void NaClBuildInstTables(void) {
1697   struct NaClSymbolTable* st = NaClSymbolTableCreate(5, NULL);
1698
1699   /* Create common (global) symbol table with instruction set presumptions. */
1700   NaClSymbolTablePutText(
1701       "sp", ((X86_32 == NACL_FLAGS_run_mode) ? "esp" : "rsp"), st);
1702   NaClSymbolTablePutText(
1703       "ip", ((X86_32 == NACL_FLAGS_run_mode) ? "eip" : "rip"), st);
1704   NaClSymbolTablePutText(
1705       "bp", ((X86_32 == NACL_FLAGS_run_mode) ? "ebp" : "rbp"), st);
1706
1707   NaClInitInstTables();
1708   NaClDefPrefixBytes();
1709   NaClDefOneByteInsts(st);
1710   NaClDef0FInsts(st);
1711   NaClDefSseInsts(st);
1712   NaClDefX87Insts(st);
1713   NaClDefNops();
1714
1715   NaClSymbolTableDestroy(st);
1716 }
1717
1718 static int NaClInstMrmListLength(NaClMrmInst* next) {
1719   int count = 0;
1720   while (NULL != next) {
1721     ++count;
1722     next = next->next;
1723   }
1724   return count;
1725 }
1726
1727 static void NaClFatalChoiceCount(const int expected,
1728                                  const int found,
1729                                  const NaClInstPrefix prefix,
1730                                  const int opcode,
1731                                  const int modrm_index,
1732                                  NaClMrmInst* insts) {
1733   struct Gio* g = NaClLogGetGio();
1734   NaClPrintInstDescriptor(g, prefix, opcode, modrm_index);
1735   NaClLog(LOG_ERROR, "Expected %d rules but found %d:\n", expected, found);
1736   while (NULL != insts) {
1737     NaClModeledInstPrint(g, &(insts->inst));
1738     insts = insts->next;
1739   }
1740   NaClFatal("fix before continuing...\n");
1741 }
1742
1743 /* Verify that the number of possible choies for each prefix:opcode matches
1744  * what was explicitly defined.
1745  */
1746 static void NaClVerifyInstCounts(void) {
1747   int i, j;
1748   NaClInstPrefix prefix;
1749   for (i = 0; i < NCDTABLESIZE; ++i) {
1750     for (prefix = NoPrefix; prefix < NaClInstPrefixEnumSize; ++prefix) {
1751       for (j = 0; j < NACL_MODRM_OPCODE_SIZE; ++j) {
1752         NaClMrmInst* insts = NaClInstMrmTable[i][prefix][j];
1753         int found = NaClInstMrmListLength(insts);
1754         int expected = NaClInstCount[i][prefix][j];
1755         if (expected == NACL_DEFAULT_CHOICE_COUNT) {
1756           if (found > 1) {
1757             NaClFatalChoiceCount(1, found, prefix, i, j, insts);
1758           }
1759         } else if (expected != found) {
1760           NaClFatalChoiceCount(expected, found, prefix, i, j, insts);
1761         }
1762       }
1763     }
1764   }
1765 }
1766
1767 /* Removes X86-32 specific flags from the given instruction. */
1768 static void NaClInstRemove32Stuff(NaClModeledInst* inst) {
1769   NaClRemoveBits(inst->flags, NACL_IFLAG(Opcode32Only));
1770 }
1771
1772 /* Removes X86-64 specific flags from the given instruction. */
1773 static void NaClInstRemove64Stuff(NaClModeledInst* inst) {
1774   NaClRemoveBits(inst->flags,
1775                  NACL_IFLAG(OpcodeRex) |
1776                  NACL_IFLAG(OpcodeUsesRexW) |
1777                  NACL_IFLAG(OpcodeHasRexR) |
1778                  NACL_IFLAG(Opcode64Only) |
1779                  NACL_IFLAG(OperandSize_o) |
1780                  NACL_IFLAG(AddressSize_o) |
1781                  NACL_IFLAG(OperandSizeDefaultIs64) |
1782                  NACL_IFLAG(OperandSizeForce64));
1783 }
1784
1785 /* Simplifies the instructions if possible. Mostly removes flags that
1786  * don't correspond to the run mode.
1787  */
1788 static void NaClSimplifyIfApplicable(void) {
1789   int i;
1790   for (i = 0; i < NCDTABLESIZE; ++i) {
1791     NaClInstPrefix prefix;
1792     for (prefix = NoPrefix; prefix < NaClInstPrefixEnumSize; ++prefix) {
1793       NaClModeledInst* next = tables.inst_table[i][prefix];
1794       while (NULL != next) {
1795         if (X86_64 != NACL_FLAGS_run_mode) {
1796           NaClInstRemove64Stuff(next);
1797         }
1798         if (X86_32 != NACL_FLAGS_run_mode) {
1799           NaClInstRemove32Stuff(next);
1800         }
1801         /* Remove size only flags, since already compiled into tables. */
1802         NaClRemoveBits(next->flags,
1803                        NACL_IFLAG(Opcode64Only) | NACL_IFLAG(Opcode32Only));
1804         next = next->next_rule;
1805       }
1806     }
1807   }
1808 }
1809
1810 /* Prints out the set of defined instruction flags. */
1811 static void NaClIFlagsPrintInternal(struct Gio* f, NaClIFlags flags) {
1812   if (flags) {
1813     int i;
1814     Bool first = TRUE;
1815     for (i = 0; i < NaClIFlagEnumSize; ++i) {
1816       if (flags & NACL_IFLAG(i)) {
1817         if (first) {
1818           first = FALSE;
1819         } else {
1820           gprintf(f, " | ");
1821         }
1822         gprintf(f, "NACL_IFLAG(%s)", NaClIFlagName(i));
1823       }
1824     }
1825   } else {
1826     gprintf(f, "NACL_EMPTY_IFLAGS");
1827   }
1828 }
1829
1830 /* Prints out the set of defined Operand flags. */
1831 static void NaClOpFlagsPrintInternal(struct Gio* f, NaClOpFlags flags) {
1832   if (flags) {
1833     NaClOpFlag i;
1834     Bool first = TRUE;
1835     for (i = 0; i < NaClOpFlagEnumSize; ++i) {
1836       if (flags & NACL_OPFLAG(i)) {
1837         if (first) {
1838           first = FALSE;
1839         } else {
1840           gprintf(f, " | ");
1841         }
1842         gprintf(f, "NACL_OPFLAG(%s)", NaClOpFlagName(i));
1843       }
1844     }
1845   } else {
1846     gprintf(f, "NACL_EMPTY_OPFLAGS");
1847   }
1848 }
1849
1850 /* Print out the opcode operand. */
1851 static void NaClOpPrintInternal(struct Gio* f, const NaClOp* operand) {
1852   gprintf(f, "{ %s, ", NaClOpKindName(operand->kind));
1853   NaClOpFlagsPrintInternal(f, operand->flags);
1854   gprintf(f, ", ");
1855   if (NULL == operand->format_string) {
1856     gprintf(f, "NULL");
1857   } else {
1858     gprintf(f, "\"%s\"", operand->format_string);
1859   }
1860   gprintf(f, " },\n");
1861 }
1862
1863 /* Converts the (compressed) operand to the corresponding
1864  * index in tables.ops_compressed.
1865  */
1866 size_t NaClOpOffset(const NaClOp* op) {
1867   /* Note: This function is innefficient, but doesn't slow things down
1868    * enough to worry about. Especially since this only effects the
1869    * generator.
1870    */
1871   size_t i;
1872   for (i = 0; i <= tables.ops_compressed_size; ++i) {
1873     if (op == (tables.ops_compressed + i)) return i;
1874   }
1875   /* If reached, we have a bug! */
1876   NaClFatal("Can't find offset for operand");
1877   /* NOT REACHED */
1878   return 0;
1879 }
1880
1881 static void NaClPrintInstIndex(struct Gio* f,
1882                                size_t index) {
1883   if (NACL_OPCODE_NULL_OFFSET == index) {
1884     gprintf(f, "NACL_OPCODE_NULL_OFFSET");
1885   } else {
1886     gprintf(f, "%d", index);
1887   }
1888 }
1889
1890 /* Print out the given opcode offset value corresponding to the
1891  * given instruction.
1892  */
1893 static void NaClPrintInstOffset(struct Gio* f,
1894                                 const NaClModeledInst* inst) {
1895   NaClPrintInstIndex(f, NaClFindInstIndex(&tables, inst));
1896 }
1897
1898 /* Prints out the given instruction to the given file. If index >= 0,
1899  * print out a comment, with the value of index, before the printed
1900  * instruction. Lookahead is used to convert the next_rule pointer into
1901  * a symbolic reference using the name "g_Opcodes", plus the index defined by
1902  * the lookahead. Argument as_array_element is true if the element is
1903  * assumed to be in an array static initializer.
1904  */
1905 static void NaClInstPrintInternal(struct Gio* f, Bool as_array_element,
1906                                   size_t index, const NaClModeledInst* inst) {
1907   gprintf(f, "  /* %d */\n", index);
1908   gprintf(f, "  { %s,\n", NaClInstTypeString(inst->insttype));
1909   gprintf(f, "    ");
1910   NaClIFlagsPrintInternal(f, inst->flags);
1911   gprintf(f, ",\n");
1912   gprintf(f, "    Inst%s, 0x%02x, ", NaClMnemonicName(inst->name),
1913           inst->opcode_ext);
1914   gprintf(f, "%u, %"NACL_PRIuS", ",
1915           inst->num_operands, NaClOpOffset(inst->operands));
1916   NaClPrintInstOffset(f, inst->next_rule);
1917   gprintf(f, "  }%c\n", as_array_element ? ',' : ';');
1918 }
1919
1920 /* Generate header information, based on the executable name in argv0,
1921  * and the file to be generated (defined by fname).
1922  */
1923 static void NaClPrintHeader(struct Gio* f, const char* argv0,
1924                             const char* fname) {
1925   gprintf(f, "/*\n");
1926   gprintf(f, " * THIS FILE IS AUTO-GENERATED. DO NOT EDIT.\n");
1927   gprintf(f, " * Compiled for %s.\n", NaClRunModeName(NACL_FLAGS_run_mode));
1928   gprintf(f, " *\n");
1929   gprintf(f, " * You must include ncopcode_desc.h before this file.\n");
1930   gprintf(f, " */\n\n");
1931 }
1932
1933 /* Print out which bytes correspond to prefix bytes. */
1934 static void NaClPrintPrefixTable(struct Gio* f) {
1935   int opc;
1936   gprintf(f, "static const uint32_t kNaClPrefixTable[NCDTABLESIZE] = {");
1937   for (opc = 0; opc < NCDTABLESIZE; opc++) {
1938     if (0 == opc % 16) {
1939       gprintf(f, "\n  /* 0x%02x-0x%02x */\n  ", opc, opc + 15);
1940     }
1941     gprintf(f, "%s, ", NaClPrefixTable[opc]);
1942   }
1943   gprintf(f, "\n};\n\n");
1944 }
1945
1946 static int NaClCountInstNodes(const NaClModeledInstNode* root) {
1947   if (NULL == root) {
1948     return 0;
1949   } else {
1950     int count = 1;
1951     count += NaClCountInstNodes(root->success);
1952     count += NaClCountInstNodes(root->fail);
1953     return count;
1954   }
1955 }
1956
1957 static void NaClPrintInstTrieEdge(const NaClModeledInstNode* edge,
1958                                   int* edge_index,
1959                                   struct Gio* f) {
1960   gprintf(f, "    ");
1961   if (NULL == edge) {
1962     gprintf(f, "NULL");
1963   }
1964   else {
1965     gprintf(f, "g_OpcodeSeq + %d", *edge_index);
1966     *edge_index += NaClCountInstNodes(edge);
1967   }
1968   gprintf(f, ",\n");
1969 }
1970
1971 static void NaClPrintInstTrieNode(const NaClModeledInstNode* root,
1972                                   int root_index, struct Gio* f) {
1973   if (NULL == root) {
1974     return;
1975   } else {
1976     int next_index = root_index + 1;
1977     gprintf(f, "  /* %d */\n", root_index);
1978     gprintf(f, "  { 0x%02x,\n    ", root->matching_byte);
1979     NaClPrintInstOffset(f, root->matching_inst);
1980     gprintf(f, ",\n");
1981     NaClPrintInstTrieEdge(root->success, &next_index, f);
1982     NaClPrintInstTrieEdge(root->fail, &next_index, f);
1983     gprintf(f, "  },\n");
1984     next_index = root_index + 1;
1985     NaClPrintInstTrieNode(root->success, next_index, f);
1986     next_index += NaClCountInstNodes(root->success);
1987     NaClPrintInstTrieNode(root->fail, next_index, f);
1988   }
1989 }
1990
1991 /* Prints out the contents of the opcode sequence overrides into the
1992  * given file.
1993  */
1994 static void NaClPrintInstSeqTrie(const NaClModeledInstNode* root,
1995                                  struct Gio* f) {
1996   /* Make sure trie isn't empty, since empty arrays create warning messages. */
1997   int num_trie_nodes;
1998   if (root == NULL) root = NaClNewInstNode(0);
1999   num_trie_nodes = NaClCountInstNodes(root);
2000   gprintf(f, "static const NaClInstNode g_OpcodeSeq[%d] = {\n", num_trie_nodes);
2001   NaClPrintInstTrieNode(root, 0, f);
2002   gprintf(f, "};\n");
2003 }
2004
2005 /* Prints out the array of (compressed) operands. */
2006 static void NaClPrintOperandTable(struct Gio* f) {
2007   size_t i;
2008   gprintf(f, "static const NaClOp g_Operands[%"NACL_PRIuS"] = {\n",
2009           tables.ops_compressed_size);
2010   for (i = 0; i < tables.ops_compressed_size; ++i) {
2011     gprintf(f,"  /* %"NACL_PRIuS" */ ", i);
2012     NaClOpPrintInternal(f, tables.ops_compressed+i);
2013   }
2014   gprintf(f, "};\n\n");
2015 }
2016
2017 static const size_t NaClOffsetsPerLine = 10;
2018
2019 /* Print out instruction table. */
2020 static void NaClPrintInstTable(struct Gio* f) {
2021   size_t i;
2022   gprintf(f,
2023           "static const NaClInst g_Opcodes[%d] = {\n",
2024           tables.inst_compressed_size);
2025   for (i = 0; i < tables.inst_compressed_size; ++i) {
2026     const NaClModeledInst* next = tables.inst_compressed[i];
2027     NaClInstPrintInternal(f, TRUE, i, next);
2028   }
2029   gprintf(f, "};\n\n");
2030 }
2031
2032 /* Print lookup table of rules, based on prefix and opcode byte. */
2033 static void NaClPrintLookupTable(struct Gio* f) {
2034   size_t i;
2035   NaClInstPrefix prefix;
2036
2037   gprintf(f, "static const NaClPrefixOpcodeArrayOffset g_LookupTable[%d] = {",
2038           (int) tables.opcode_lookup_size);
2039   for (i = 0; i < tables.opcode_lookup_size; ++i) {
2040     if (0 == (i % NaClOffsetsPerLine)) {
2041       gprintf(f, "\n  /* %5d */ ", (int) i);
2042     }
2043     NaClPrintInstIndex(f, tables.opcode_lookup[i]);
2044     gprintf(f, ", ");
2045   }
2046   gprintf(f, "};\n\n");
2047
2048   gprintf(f, "static const NaClPrefixOpcodeSelector "
2049           "g_PrefixOpcode[NaClInstPrefixEnumSize] = {\n");
2050   for (prefix = NoPrefix; prefix < NaClInstPrefixEnumSize; ++prefix) {
2051     gprintf(f, "  /* %20s */ { %d , 0x%02x, 0x%02x },\n",
2052             NaClInstPrefixName(prefix),
2053             tables.opcode_lookup_entry[prefix],
2054             tables.opcode_lookup_first[prefix],
2055             tables.opcode_lookup_last[prefix]);
2056   }
2057   gprintf(f, "};\n\n");
2058 }
2059
2060 /* Print out the contents of the defined instructions into the given file. */
2061 static void NaClPrintDecodeTables(struct Gio* f) {
2062   NaClPrintOperandTable(f);
2063   NaClPrintInstTable(f);
2064   NaClPrintLookupTable(f);
2065   NaClPrintPrefixTable(f);
2066   NaClPrintInstSeqTrie(tables.inst_node_root, f);
2067 }
2068
2069 /* Print out the sequence of bytes used to encode an instruction sequence. */
2070 static void PrintInstructionSequence(
2071     struct Gio* f, uint8_t* inst_sequence, int length) {
2072   int i;
2073   for (i = 0; i < length; ++i) {
2074     if (i > 0) gprintf(f, " ");
2075     gprintf(f, "%02x", inst_sequence[i]);
2076   }
2077 }
2078
2079 /* Print out instruction sequences defined for the given (Trie) node,
2080  * and all of its descendants.
2081  * Note: To keep recursive base cases simple, we allow one more byte
2082  * in the instruction sequence that is actually possible.
2083  */
2084 static void PrintHardCodedInstructionsNode(
2085     struct Gio* f, const NaClModeledInstNode* node,
2086     uint8_t inst_sequence[NACL_MAX_BYTES_PER_X86_INSTRUCTION+1], int length) {
2087   if (NULL == node) return;
2088   inst_sequence[length] = node->matching_byte;
2089   ++length;
2090   if (NACL_MAX_BYTES_PER_X86_INSTRUCTION < length) {
2091     struct Gio* glog = NaClLogGetGio();
2092     NaClLog(LOG_ERROR, "%s", "");
2093     PrintInstructionSequence(glog, inst_sequence, length);
2094     gprintf(glog, "\n");
2095     NaClFatal("Hard coded instruction too long, aborting\n");
2096   }
2097   if (NULL != node->matching_inst) {
2098     gprintf(f, "  --- ");
2099     PrintInstructionSequence(f, inst_sequence, length);
2100     gprintf(f, " ---\n");
2101     NaClModeledInstPrint(f, node->matching_inst);
2102     gprintf(f, "\n");
2103   }
2104   PrintHardCodedInstructionsNode(f, node->success, inst_sequence, length);
2105   PrintHardCodedInstructionsNode(f, node->fail, inst_sequence, length-1);
2106 }
2107
2108 /* Walks over specifically encoded instruction trie, and prints
2109  * out corresponding implemented instructions.
2110  */
2111 static void NaClPrintHardCodedInstructions(struct Gio* f) {
2112   uint8_t inst_sequence[NACL_MAX_BYTES_PER_X86_INSTRUCTION+1];
2113   PrintHardCodedInstructionsNode(f, tables.inst_node_root, inst_sequence, 0);
2114 }
2115
2116 /* Prints out documentation on the modeled instruction set. */
2117 static void NaClPrintInstructionSet(struct Gio* f) {
2118   NaClInstPrefix prefix;
2119   int i;
2120   gprintf(f, "*** Automatically generated file, do not edit! ***\n");
2121   gprintf(f, "\n");
2122   gprintf(f, "Target: %s\n", NaClRunModeName(NACL_FLAGS_run_mode));
2123   gprintf(f, "\n");
2124   gprintf(f, "*** Hard coded instructions ***\n");
2125   gprintf(f, "\n");
2126   NaClPrintHardCodedInstructions(f);
2127
2128   for (prefix = NoPrefix; prefix < NaClInstPrefixEnumSize;  ++prefix) {
2129     Bool printed_rules = FALSE;
2130     gprintf(f, "*** %s ***\n", NaClInstPrefixName(prefix));
2131     gprintf(f, "\n");
2132     for (i = 0; i < NCDTABLESIZE; ++i) {
2133       Bool is_first = TRUE;
2134       const NaClModeledInst* inst = tables.inst_table[i][prefix];
2135       while (NULL != inst) {
2136         if (is_first) {
2137           gprintf(f, "  --- %02x ---\n", i);
2138           is_first = FALSE;
2139         }
2140         NaClModeledInstPrint(f, inst);
2141         printed_rules = TRUE;
2142         inst = inst->next_rule;
2143       }
2144     }
2145     if (printed_rules) gprintf(f, "\n");
2146   }
2147 }
2148
2149 /* Open the given file using the given directives (how). */
2150 static void NaClMustOpen(struct GioFile* g,
2151                          const char* fname, const char* how) {
2152   if (!GioFileCtor(g, fname, how)) {
2153     NaClLog(LOG_ERROR, "could not fopen(%s, %s)\n", fname, how);
2154     NaClFatal("exiting now");
2155   }
2156 }
2157
2158 /* Recognizes flags in argv, processes them, and then removes them.
2159  * Returns the updated value for argc.
2160  */
2161 static int NaClGrokFlags(int argc, const char* argv[]) {
2162   int i;
2163   int new_argc;
2164   if (argc == 0) return 0;
2165   new_argc = 1;
2166   for (i = 1; i < argc; ++i) {
2167     if (0 == strcmp("-m32", argv[i])) {
2168       NACL_FLAGS_run_mode = X86_32;
2169     } else if (0 == strcmp("-m64", argv[i])) {
2170       NACL_FLAGS_run_mode = X86_64;
2171     } else if (GrokBoolFlag("-documentation", argv[i],
2172                             &NACL_FLAGS_human_readable) ||
2173                GrokBoolFlag("-validator_decoder", argv[i],
2174                             &NACL_FLAGS_validator_decoder) ||
2175                GrokBoolFlag("-nacl_subregs", argv[i],
2176                             &NACL_FLAGS_nacl_subregs)) {
2177       continue;
2178     } else {
2179       argv[new_argc++] = argv[i];
2180     }
2181   }
2182   return new_argc;
2183 }
2184
2185 static void GenerateTables(struct Gio* f, const char* cmd,
2186                            const char* filename) {
2187   if (NACL_FLAGS_human_readable) {
2188     NaClPrintInstructionSet(f);
2189   } else {
2190     /* Generate header file defining instruction set. */
2191     NaClPrintHeader(f, cmd, filename);
2192     if (NACL_FLAGS_nacl_subregs) {
2193       if (NACL_FLAGS_run_mode == X86_64) {
2194         NaClPrintGpRegisterIndexes_64(f);
2195       } else {
2196         NaClPrintGpRegisterIndexes_32(f);
2197       }
2198     } else {
2199       NaClPrintDecodeTables(f);
2200     }
2201   }
2202 }
2203
2204 /* Walk the trie of explicitly defined opcode sequences, and
2205  * fill in the operands description field if it hasn't been
2206  * explicitly defined.
2207  */
2208 static void FillInTrieMissingOperandsDescs(NaClModeledInstNode* node) {
2209   NaClModeledInst* inst;
2210   if (NULL == node) return;
2211   inst = node->matching_inst;
2212   NaClFillOperandDescs(inst);
2213   FillInTrieMissingOperandsDescs(node->success);
2214   FillInTrieMissingOperandsDescs(node->fail);
2215 }
2216
2217 /* Define the operands description field of each modeled
2218  * opcode instruction, if it hasn't explicitly been defined.
2219  */
2220 static void FillInMissingOperandsDescs(void) {
2221   int i;
2222   NaClInstPrefix prefix;
2223   for (prefix = NoPrefix; prefix < NaClInstPrefixEnumSize; ++prefix) {
2224     for (i = 0; i < NCDTABLESIZE; ++i) {
2225       NaClModeledInst* next = tables.inst_table[i][prefix];
2226       while (NULL != next) {
2227         NaClFillOperandDescs(next);
2228         next = next->next_rule;
2229       }
2230     }
2231   }
2232   FillInTrieMissingOperandsDescs(tables.inst_node_root);
2233 }
2234
2235 static void InitTables(void) {
2236   tables.inst_node_root = NULL;
2237   tables.operands_size = 0;
2238   tables.ops_compressed_size = 0;
2239   tables.opcode_lookup_size = 0;
2240   tables.inst_compressed_size = 0;
2241   tables.undefined_inst = 0;
2242 }
2243
2244 int main(const int argc, const char* argv[]) {
2245   struct GioFile gfile;
2246   struct Gio* g = (struct Gio*) &gfile;
2247   int new_argc = NaClGrokFlags(argc, argv);
2248   if ((new_argc < 1) || (new_argc > 2) ||
2249       (NACL_FLAGS_human_readable && NACL_FLAGS_nacl_subregs) ||
2250       (NACL_FLAGS_run_mode == NaClRunModeSize)) {
2251     fprintf(stderr,
2252             "ERROR: usage: ncdecode_tablegen <architecture_flag> "
2253             "[-documentation | -validator_decoder -nacl_subregs] [file]\n");
2254     return -1;
2255   }
2256   InitTables();
2257   NaClLogModuleInit();
2258   NaClBuildInstTables();
2259   NaClSimplifyIfApplicable();
2260   NaClVerifyInstCounts();
2261   FillInMissingOperandsDescs();
2262
2263   if (NACL_FLAGS_validator_decoder)
2264     NaClNcvalInstSimplify(&tables);
2265
2266   /* Don't compress if output is to be readable! Compression
2267    * ignores extra (redundant) data used by print routines of
2268    * modeled instructions, since this data is not needed at
2269    * runtime when the corresponding data is defined in the
2270    * parsed instruction.
2271    */
2272   if (!NACL_FLAGS_human_readable) {
2273     NaClOpCompress(&tables);
2274   }
2275
2276   if (new_argc == 1) {
2277     GioFileRefCtor(&gfile, stdout);
2278     GenerateTables(g, argv[0], "<stdout>");
2279   } else {
2280     NaClMustOpen(&gfile, argv[1], "w");
2281     GenerateTables(g, argv[0], argv[1]);
2282   }
2283   NaClLogModuleFini();
2284   GioFileDtor(g);
2285   return 0;
2286 }