src/native_client/src/trusted/validator/x86/decoder/nc_inst_state_statics.c

   1 /*
   2  * Copyright (c) 2012 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  * This file contains includes, static functions, and constants that are used
   9  * in nc_inst_state.c, but have been factored out and put into this file, so
  10  * that we can test them. That is, to allow nc_inst_state.c and
  11  * nc_inst_state_Tests.cc to use them.
  12  */
  13
  14 #ifndef NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_X86_DECODER_NC_INST_STATE_STATICS_C__
  15 #define NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_X86_DECODER_NC_INST_STATE_STATICS_C__
  16
  17 #include <stdio.h>
  18 #include <assert.h>
  19 #include "native_client/src/shared/platform/nacl_log.h"
  20 #include "native_client/src/shared/utils/debugging.h"
  21 #include "native_client/src/trusted/validator/x86/decoder/nc_decode_tables.h"
  22 #include "native_client/src/trusted/validator/x86/decoder/nc_inst_iter.h"
  23 #include "native_client/src/trusted/validator/x86/decoder/nc_inst_state_internal.h"
  24 #include "native_client/src/trusted/validator/x86/decoder/nc_inst_trans.h"
  25 #include "native_client/src/trusted/validator/x86/decoder/ncop_exps.h"
  26 #include "native_client/src/trusted/validator/x86/decoder/ncopcode_desc.h"
  27 #include "native_client/src/trusted/validator/x86/nc_segment.h"
  28
  29 #include "native_client/src/trusted/validator/x86/ncinstbuffer_inl.c"
  30 #include "native_client/src/trusted/validator/x86/x86_insts_inl.c"
  31
  32 EXTERN_C_BEGIN
  33
  34 /* Given the current location of the instruction iterator, initialize
  35  * the given state (to match).
  36  */
  37 static void NaClInstStateInit(NaClInstIter* iter, NaClInstState* state) {
  38   NaClMemorySize limit;
  39   NCInstBytesInitInline(&state->bytes);
  40   state->iter = iter;
  41   state->decoder_tables = iter->decoder_tables;
  42   state->inst_addr = iter->index;
  43   limit = iter->segment->size - iter->index;
  44   if (limit > NACL_MAX_BYTES_PER_X86_INSTRUCTION) {
  45     limit = NACL_MAX_BYTES_PER_X86_INSTRUCTION;
  46   }
  47   state->length_limit = (uint8_t) limit;
  48   DEBUG(NaClLog(LOG_INFO,
  49                 "length limit = %"NACL_PRIu8"\n", state->length_limit));
  50   state->num_prefix_bytes = 0;
  51   state->opcode_prefix = 0;
  52   state->num_opcode_bytes = 0;
  53   state->rexprefix = 0;
  54   state->num_rex_prefixes = 0;
  55   state->modrm = 0;
  56   state->has_prefix_duplicates = FALSE;
  57   state->has_ambig_segment_prefixes = FALSE;
  58   state->has_sib = FALSE;
  59   state->sib = 0;
  60   state->num_disp_bytes = 0;
  61   state->first_disp_byte = 0;
  62   state->num_imm_bytes = 0;
  63   state->first_imm_byte = 0;
  64   state->num_imm2_bytes = 0;
  65   state->prefix_mask = 0;
  66   state->inst = NULL;
  67   state->nodes.is_defined = FALSE;
  68   state->nodes.number_expr_nodes = 0;
  69   state->unchanged = FALSE;
  70 }
  71
  72 /* Returns true if data 66 prefix is specified for the instruction,
  73  * and the isntruction doesn't ignore the data 66 prefix.
  74  */
  75 #define NACL_PREFIX_INST_DATA66(state) \
  76   (NaClHasBit((state)->prefix_mask, kPrefixDATA16) && \
  77       (NACL_EMPTY_IFLAGS == \
  78        ((state)->inst->flags & NACL_IFLAG(SizeIgnoresData16))))
  79
  80 /* Computes the number of bytes defined for operands of the matched
  81  * instruction of the given state. Returns 0 if the operand size could
  82  * not be computed, due to ambiguities in the prefix bytes.
  83  */
  84 static int NaClExtractOpSize(NaClInstState* state) {
  85   if (NaClHasBit(state->inst->flags, NACL_IFLAG(OperandSize_b))) {
  86     return 1;
  87   }
  88   if (NACL_TARGET_SUBARCH == 64) {
  89     if (NaClRexW(state->rexprefix)) {
  90       if (NACL_PREFIX_INST_DATA66(state))
  91         /* According to the AMD and INTEL manuals, if both prefix 66 and
  92          * rex.w is specified, the rex.w should be used. However, rather
  93          * than tempt fate, we disallow this combination of prefixes for
  94          * any such instruction, since the same effect can be achieved
  95          * without the 66 prefix.
  96          */
  97         return 0;
  98       return 8;
  99     }
 100     if (NaClHasBit(state->inst->flags, NACL_IFLAG(OperandSizeForce64))) {
 101       return 8;
 102     }
 103     if (NACL_PREFIX_INST_DATA66(state))
 104       return 2;
 105     else if (NaClHasBit(state->inst->flags, NACL_IFLAG(OperandSizeDefaultIs64)))
 106       return 8;
 107     else
 108       return 4;
 109   } else if (NACL_PREFIX_INST_DATA66(state))
 110     return 2;
 111   else
 112     return 4;
 113 }
 114
 115 /* Computes the number of bits defined for addresses of the matched
 116  * instruction of the given state.
 117  */
 118 static int NaClExtractAddressSize(NaClInstState* state) {
 119   if (NACL_TARGET_SUBARCH == 64) {
 120     return NaClHasBit(state->prefix_mask, kPrefixADDR16) ? 32 : 64;
 121   } else {
 122     return NaClHasBit(state->prefix_mask, kPrefixADDR16) ? 16 : 32;
 123   }
 124 }
 125
 126 /* Manual implies only 4 bytes is allowed, but I have found up to 6.
 127  * Why don't we allow any number, so long as (1) There is room for
 128  * at least one opcode byte, and (2) we don't exceed the max bytes.
 129  */
 130 static const int kNaClMaximumPrefixBytes =
 131     NACL_MAX_BYTES_PER_X86_INSTRUCTION - 1;
 132
 133 /* Captures ambiguous segment prefix forms. Used to make
 134  * detection of multiple prefix segment bytes.
 135  */
 136 static const uint32_t segment_prefix_forms =
 137     kPrefixSEGCS | kPrefixSEGSS | kPrefixSEGFS |
 138     kPrefixSEGGS | kPrefixSEGES | kPrefixSEGDS;
 139
 140 /* Match any prefix bytes that can be associated with the instruction
 141  * currently being matched.
 142  */
 143 static Bool NaClConsumePrefixBytes(NaClInstState* state) {
 144   uint8_t next_byte;
 145   int i;
 146   uint32_t prefix_form;
 147   for (i = 0; i < kNaClMaximumPrefixBytes; ++i) {
 148     /* Quit early if no more bytes in segment. */
 149     if (state->bytes.length >= state->length_limit) break;
 150
 151     /* Look up the corresponding prefix bit associated
 152      * with the next byte in the segment, and record it.
 153      */
 154     next_byte = NCRemainingMemoryLookaheadInline(state->bytes.memory,0);
 155     prefix_form = state->decoder_tables->prefix_mask[next_byte];
 156     if (prefix_form == 0) break;
 157     next_byte = NCInstBytesReadInline(&state->bytes);
 158     DEBUG(NaClLog(LOG_INFO,
 159                   "Consume prefix[%d]: %02"NACL_PRIx8" => %"NACL_PRIx32"\n",
 160                   i, next_byte, prefix_form));
 161     /* Before updating prefix mask, determine if the prefix byte is
 162      * a duplicate.
 163      */
 164     if ((state->prefix_mask & prefix_form)) {
 165       state->has_prefix_duplicates = TRUE;
 166       DEBUG(NaClLog(LOG_INFO,
 167                     "duplicate prefix %02"NACL_PRIx8" detected.\n", next_byte));
 168     } else if ((prefix_form & segment_prefix_forms) &&
 169                (state->prefix_mask & segment_prefix_forms)) {
 170       state->has_ambig_segment_prefixes = TRUE;
 171       DEBUG(NaClLog(LOG_INFO,
 172                     "ambiguos segment prefix %02"NACL_PRIx8" detected.\n",
 173                     next_byte));
 174     }
 175     state->prefix_mask |= prefix_form;
 176     ++state->num_prefix_bytes;
 177     DEBUG(NaClLog(LOG_INFO,
 178                   "  prefix mask: %08"NACL_PRIx32"\n", state->prefix_mask));
 179
 180     /* If the prefix byte is a REX prefix, record its value, since
 181      * bits 5-8 of this prefix bit may be needed later.
 182      */
 183     if ((NACL_TARGET_SUBARCH == 64) && prefix_form == kPrefixREX) {
 184       state->rexprefix = next_byte;
 185       DEBUG(NaClLog(LOG_INFO,
 186                     "  rexprefix = %02"NACL_PRIx8"\n", state->rexprefix));
 187       ++state->num_rex_prefixes;
 188     }
 189   }
 190   return TRUE;
 191 }
 192
 193 /* Assuming we have matched the byte sequence OF 38, consume the corresponding
 194  * following (instruction) opcode byte, returning the most specific prefix the
 195  * patterns can match (or NaClInstPrefixEnumSize if no such patterns exist);
 196  */
 197 static void NaClConsume0F38XXNaClInstBytes(NaClInstState* state,
 198                                            NaClInstPrefixDescriptor* desc) {
 199   /* Fail if there are no more bytes. Otherwise, read the next
 200    * byte.
 201    */
 202   if (state->bytes.length >= state->length_limit) {
 203     desc->matched_prefix = NaClInstPrefixEnumSize;
 204     return;
 205   }
 206
 207   desc->opcode_byte = NCInstBytesReadInline(&state->bytes);
 208   DEBUG(NaClLog(LOG_INFO, "Consume inst byte %02"NACL_PRIx8".\n",
 209                 desc->opcode_byte));
 210   if (NaClExcludesBit(state->prefix_mask, kPrefixREP)) {
 211     if (NaClHasBit(state->prefix_mask, kPrefixREPNE)) {
 212       /* Note: Flag OpcodeAllowsData16 will explicitly clarify
 213        * ambigous case of both REP and DATA16 prefixes.
 214        */
 215       desc->matched_prefix = PrefixF20F38;
 216       desc->opcode_prefix = kValueREPNE;
 217     } else if (NaClHasBit(state->prefix_mask, kPrefixDATA16)) {
 218       desc->matched_prefix = Prefix660F38;
 219       desc->opcode_prefix = kValueDATA16;
 220     } else {
 221       desc->matched_prefix = Prefix0F38;
 222     }
 223     return;
 224   }
 225   /* If reached, can't match special prefixes, fail. */
 226   desc->matched_prefix = NaClInstPrefixEnumSize;
 227 }
 228
 229 /* Assuming we have matched the byte sequence OF 3A, consume the corresponding
 230  * following (instruction) opcode byte, returning the most specific prefix the
 231  * patterns can match (or NaClInstPrefixEnumSize if no such patterns exist).
 232  */
 233 static void NaClConsume0F3AXXNaClInstBytes(NaClInstState* state,
 234                                            NaClInstPrefixDescriptor* desc) {
 235   /* Fail if there are no more bytes. Otherwise, read the next
 236    * byte and choose appropriate prefix.
 237    */
 238   if (state->bytes.length >= state->length_limit) {
 239     desc->matched_prefix = NaClInstPrefixEnumSize;
 240     return;
 241   }
 242
 243   desc->opcode_byte = NCInstBytesReadInline(&state->bytes);
 244   DEBUG(NaClLog(LOG_INFO, "Consume inst byte %02"NACL_PRIx8".\n",
 245                 desc->opcode_byte));
 246   if (NaClExcludesBit(state->prefix_mask, kPrefixREP) &&
 247       NaClExcludesBit(state->prefix_mask, kPrefixREPNE)) {
 248     if (NaClHasBit(state->prefix_mask, kPrefixDATA16)) {
 249       desc->matched_prefix = Prefix660F3A;
 250       desc->opcode_prefix = kValueDATA16;
 251     } else {
 252       desc->matched_prefix = Prefix0F3A;
 253     }
 254     return;
 255   }
 256   /* If reached, can't match special prefixes, fail. */
 257   desc->matched_prefix = NaClInstPrefixEnumSize;
 258 }
 259
 260 /* Assuming we have matched byte OF, consume the corresponding
 261  * following (instruction) opcode byte, returning the most specific
 262  * prefix the patterns can match (or NaClInstPrefixEnumSize if no such
 263  * patterns exist).
 264  */
 265 static void NaClConsume0FXXNaClInstBytes(NaClInstState* state,
 266                                          NaClInstPrefixDescriptor* desc) {
 267   if (NaClHasBit(state->prefix_mask, kPrefixREPNE)) {
 268     if (NaClExcludesBit(state->prefix_mask, kPrefixREP)) {
 269       /* Note: Flag OpcodeAllowsData16 will explicitly clarify
 270        * ambigous case of both REPNE and DATA16 prefixes.
 271        */
 272       desc->matched_prefix = PrefixF20F;
 273       desc->opcode_prefix = kValueREPNE;
 274       return;
 275     }
 276   } else {
 277     if (NaClHasBit(state->prefix_mask, kPrefixREP)) {
 278       /* Note: Flag OpcodeAllowsData16 will explicitly clarify
 279        * ambigous case of both REP and DATA16 prefixes.
 280        */
 281       desc->matched_prefix = PrefixF30F;
 282       desc->opcode_prefix = kValueREP;
 283     } else if (NaClHasBit(state->prefix_mask, kPrefixDATA16)) {
 284       desc->matched_prefix = Prefix660F;
 285       desc->opcode_prefix = kValueDATA16;
 286     } else {
 287       desc->matched_prefix = Prefix0F;
 288     }
 289     return;
 290   }
 291   /* If reached, can't match special prefixes, fail. */
 292   desc->matched_prefix = NaClInstPrefixEnumSize;
 293 }
 294
 295 /* Consume one of the x87 instructions that begin with D8-Df, and
 296  * match the most specific prefix pattern the opcode bytes can match.
 297  */
 298 static void NaClConsumeX87NaClInstBytes(NaClInstState* state,
 299                                         NaClInstPrefixDescriptor* desc) {
 300   if (state->bytes.length < state->length_limit) {
 301     /* Can be two byte opcode. */
 302     desc->matched_prefix =
 303         (NaClInstPrefix) (PrefixD8 +
 304                           (((unsigned) desc->opcode_byte) - 0xD8));
 305     desc->opcode_byte = NCInstBytesReadInline(&state->bytes);
 306     DEBUG(NaClLog(LOG_INFO, "Consume inst byte %02"NACL_PRIx8".\n",
 307                   desc->opcode_byte));
 308     return;
 309   }
 310
 311   /* If reached, can only be single byte opcode, match as such. */
 312   desc->matched_prefix = NoPrefix;
 313 }
 314
 315 /* Consume the opcode bytes, and return the most specific prefix pattern
 316  * the opcode bytes can match (or NaClInstPrefixEnumSize if no such pattern
 317  * exists).
 318  */
 319 static void NaClConsumeInstBytes(NaClInstState* state,
 320                                  NaClInstPrefixDescriptor* desc) {
 321
 322   /* Initialize descriptor to the fail state. */
 323   desc->opcode_prefix = 0;
 324   desc->opcode_byte = 0x0;
 325   desc->matched_prefix = NaClInstPrefixEnumSize;
 326   desc->next_length_adjustment = 0;
 327
 328   /* Be sure that we don't exceed the segment length. */
 329   if (state->bytes.length >= state->length_limit) return;
 330
 331   desc->opcode_byte = NCInstBytesReadInline(&state->bytes);
 332   DEBUG(NaClLog(LOG_INFO, "Consume inst byte %02"NACL_PRIx8".\n",
 333                 desc->opcode_byte));
 334   switch (desc->opcode_byte) {
 335     case 0x0F:
 336       if (state->bytes.length >= state->length_limit) return;
 337       desc->opcode_byte = NCInstBytesReadInline(&state->bytes);
 338       DEBUG(NaClLog(LOG_INFO, "Consume inst byte %02"NACL_PRIx8".\n",
 339                     desc->opcode_byte));
 340       switch (desc->opcode_byte) {
 341         case 0x38:
 342           NaClConsume0F38XXNaClInstBytes(state, desc);
 343           break;
 344         case 0x3a:
 345           NaClConsume0F3AXXNaClInstBytes(state, desc);
 346           break;
 347         default:
 348           NaClConsume0FXXNaClInstBytes(state, desc);
 349           break;
 350       }
 351       break;
 352     case 0xD8:
 353     case 0xD9:
 354     case 0xDA:
 355     case 0xDB:
 356     case 0xDC:
 357     case 0xDD:
 358     case 0xDE:
 359     case 0xDF:
 360       NaClConsumeX87NaClInstBytes(state, desc);
 361       break;
 362     default:
 363       desc->matched_prefix = NoPrefix;
 364       break;
 365   }
 366   DEBUG(NaClLog(LOG_INFO,
 367                 "matched prefix = %s\n",
 368                 NaClInstPrefixName(desc->matched_prefix)));
 369 }
 370
 371 /* Compute the operand and address sizes for the instruction. Then, verify
 372  * that the opcode (instruction) pattern allows for such sizes. Aborts
 373  * the pattern match if any problems.
 374  */
 375 static Bool NaClConsumeAndCheckOperandSize(NaClInstState* state) {
 376   /* Get and check that operand size is defined. */
 377   state->operand_size = NaClExtractOpSize(state);
 378   DEBUG(NaClLog(LOG_INFO,
 379                 "operand size = %"NACL_PRIu8"\n", state->operand_size));
 380   if (0 == state->operand_size) {
 381     DEBUG(NaClLog(LOG_INFO,
 382                   "Fails: operand size is zero.\n"));
 383     return FALSE;
 384   }
 385
 386   /* Check if instruction has flags specifying legal sizes. If so,
 387    * make sure that the size matches.
 388    */
 389   if (state->inst->flags &
 390       (NACL_IFLAG(OperandSize_w) | NACL_IFLAG(OperandSize_v) |
 391        NACL_IFLAG(OperandSize_o))) {
 392     NaClIFlags good = 1;
 393     switch (state->operand_size) {
 394       case 2:
 395         good = NaClHasBit(state->inst->flags, NACL_IFLAG(OperandSize_w));
 396         break;
 397       case 4:
 398         good = NaClHasBit(state->inst->flags, NACL_IFLAG(OperandSize_v));
 399         break;
 400       case 8:
 401         good = NaClHasBit(state->inst->flags, NACL_IFLAG(OperandSize_o));
 402         break;
 403       default:
 404         good = 0;
 405         break;
 406     }
 407     if (!good) {
 408       /* The flags associated with the opcode (instruction) don't
 409        * allow the computed sizes, abort the  match of the instruction.
 410        */
 411       DEBUG(NaClLog(LOG_INFO,
 412                     "Operand size %"NACL_PRIu8
 413                     " doesn't match flag requirement!\n",
 414                     state->operand_size));
 415       return FALSE;
 416     }
 417
 418     /* Do special check for case where Rex.w and data 66 specified, and
 419      * the data 66 isn't part of the opcode prefix. In such cases, we
 420      * disallow both, since they are conflicting operand size specifications.
 421      */
 422     if (NaClRexW(state->rexprefix) &&
 423         NaClHasBit(state->prefix_mask, kPrefixDATA16) &&
 424         /* The following checks that both 16 and 64 bit operand
 425          * sizes are allowed.
 426          */
 427         NaClHasBits(state->inst->flags,
 428                     NACL_IFLAG(OperandSize_w) |
 429                     NACL_IFLAG(OperandSize_o)) &&
 430         /* This clause allows cases where the 66 prefix changes
 431          * the opcode rather than the operand size. Both flags are
 432          * set iff the 66 modifies the opcode. See function
 433          * NaClAddRepPrefixFlagsIfApplicable in generator/ncdecode_tablegen.c
 434          * for details.
 435          */
 436         !NaClHasBits(state->inst->flags,
 437                      NACL_IFLAG(OpcodeAllowsData16) |
 438                      NACL_IFLAG(SizeIgnoresData16))) {
 439       DEBUG(NaClLog(LOG_INFO,
 440                     "Can't specify both data prefix 66 and Rex.w\n"));
 441       return FALSE;
 442     }
 443   }
 444   return TRUE;
 445 }
 446
 447 static Bool NaClConsumeAndCheckAddressSize(NaClInstState* state) {
 448   state->address_size = NaClExtractAddressSize(state);
 449   DEBUG(NaClLog(LOG_INFO,
 450                 "Address size = %"NACL_PRIu8"\n", state->address_size));
 451   if (state->inst->flags &
 452       (NACL_IFLAG(AddressSize_w) | NACL_IFLAG(AddressSize_v) |
 453        NACL_IFLAG(AddressSize_o))) {
 454     NaClIFlags good = 1;
 455     switch (state->address_size) {
 456     case 16:
 457       good = NaClHasBit(state->inst->flags, NACL_IFLAG(AddressSize_w));
 458       break;
 459     case 32:
 460       good = NaClHasBit(state->inst->flags, NACL_IFLAG(AddressSize_v));
 461       break;
 462     case 64:
 463       good = NaClHasBit(state->inst->flags, NACL_IFLAG(AddressSize_o));
 464       break;
 465     default:
 466       good = 0;
 467       break;
 468     }
 469     if (!good) {
 470       /* The flags associated with the opcode (instruction) don't
 471        * allow the computed sizes, abort the  match of the instruction.
 472        */
 473       DEBUG(NaClLog(LOG_INFO,
 474                     "Address size %"NACL_PRIu8
 475                     " doesn't match flag requirement!\n",
 476                     state->address_size));
 477       return FALSE;
 478     }
 479   }
 480   return TRUE;
 481 }
 482
 483 /* Returns true if the instruction requires a ModRm bytes. */
 484 static Bool NaClInstRequiresModRm(NaClInstState* state) {
 485   return (Bool)
 486       (NACL_EMPTY_IFLAGS !=
 487        (state->inst->flags & NACL_IFLAG(OpcodeUsesModRm)));
 488 }
 489
 490 /* Consume the Mod/Rm byte of the instruction, if applicable.
 491  * Aborts the pattern match if any problems.
 492  */
 493 static Bool NaClConsumeModRm(NaClInstState* state) {
 494   /* First check if the opcode (instruction) pattern specifies that
 495    * a Mod/Rm byte is needed, and that reading it will not walk
 496    * past the end of the code segment.
 497    */
 498   if (NaClInstRequiresModRm(state)) {
 499     uint8_t byte;
 500     /* Has modrm byte. */
 501     if (state->bytes.length >= state->length_limit) {
 502       DEBUG(NaClLog(LOG_INFO, "Can't read mod/rm, no more bytes!\n"));
 503       return FALSE;
 504     }
 505     byte = NCInstBytesPeekInline(&state->bytes, 0);
 506
 507     /* Note: Some instructions only allow values where the ModRm mod field
 508      * is 0x3. Others only allow values where the ModRm mod field isn't 0x3.
 509      */
 510     if (modrm_modInline(byte) == 0x3) {
 511       if (NaClHasBit(state->inst->flags, NACL_IFLAG(ModRmModIsnt0x3))) {
 512         DEBUG(NaClLog(LOG_INFO, "Can't match, modrm mod field is 0x3\n"));
 513         return FALSE;
 514       }
 515     } else {
 516       if (NaClHasBit(state->inst->flags, NACL_IFLAG(ModRmModIs0x3))) {
 517         DEBUG(NaClLog(LOG_INFO, "Can't match, modrm mod field not 0x3\n"));
 518         return FALSE;
 519       }
 520     }
 521     if ((NaClHasBit(state->inst->flags, NACL_IFLAG(ModRmRegSOperand))) &&
 522         (modrm_regInline(byte) > 5)) {
 523       DEBUG(NaClLog(LOG_INFO,
 524                     "Can't match, modrm reg field doesn't index segment\n"));
 525       return FALSE;
 526     }
 527     state->modrm = NCInstBytesReadInline(&state->bytes);
 528     state->num_disp_bytes = 0;
 529     state->first_disp_byte = 0;
 530     state->sib = 0;
 531     state->has_sib = FALSE;
 532     DEBUG(NaClLog(LOG_INFO, "consume modrm = %02"NACL_PRIx8"\n", state->modrm));
 533
 534     /* Consume the remaining opcode value in the mod/rm byte
 535      * if applicable.
 536      */
 537     if (state->inst->flags & NACL_IFLAG(OpcodeInModRm)) {
 538       const NaClInst* inst = state->inst;
 539       if (modrm_opcodeInline(state->modrm) !=
 540           NaClGetOpcodeInModRm(inst->opcode_ext)) {
 541         DEBUG(
 542             NaClLog(LOG_INFO,
 543                     "Discarding, opcode in mrm byte (%02"NACL_PRIx8") "
 544                     "does not match\n",
 545                     modrm_opcodeInline(state->modrm)));
 546         return FALSE;
 547       }
 548       if (state->inst->flags & NACL_IFLAG(OpcodeInModRmRm)) {
 549         if (modrm_rmInline(state->modrm) !=
 550             NaClGetOpcodeInModRmRm(inst->opcode_ext)) {
 551           DEBUG(NaClLog(LOG_INFO,
 552                         "Discarding, opcode in mrm rm field (%02"NACL_PRIx8") "
 553                         "does not match\n",
 554                         modrm_rmInline(state->modrm)));
 555           return FALSE;
 556         }
 557       }
 558     }
 559   }
 560   return TRUE;
 561 }
 562
 563 /* Returns true if the instruction requires a SIB bytes. */
 564 static Bool NaClInstRequiresSib(NaClInstState* state) {
 565   /* Note: in 64-bit mode, 64-bit addressing is treated the same as 32-bit
 566    * addressing. Hence, required for all but 16-bit addressing, when
 567    * the right modrm bytes are specified.
 568    */
 569   return (Bool)
 570       (NaClInstRequiresModRm(state) && (16 != state->address_size) &&
 571        (modrm_rmInline(state->modrm) ==
 572         0x04 && modrm_modInline(state->modrm) != 0x3));
 573 }
 574
 575 /* Consume the SIB byte of the instruction, if applicable. Aborts the pattern
 576  * match if any problems are found.
 577  */
 578 static Bool NaClConsumeSib(NaClInstState* state) {
 579   /* First check that the opcode (instruction) pattern specifies that
 580    * a SIB byte is needed, and that reading it will not walk past
 581    * the end of the code segment.
 582    */
 583   state->sib = 0;
 584   state->has_sib = NaClInstRequiresSib(state);
 585   DEBUG(NaClLog(LOG_INFO, "has sib = %d\n", (int) state->has_sib));
 586   if (state->has_sib) {
 587     if (state->bytes.length >= state->length_limit) {
 588       DEBUG(NaClLog(LOG_INFO, "Can't consume sib, no more bytes!\n"));
 589       return FALSE;
 590     }
 591     /* Read the SIB byte and record. */
 592     state->sib = NCInstBytesReadInline(&state->bytes);
 593     DEBUG(NaClLog(LOG_INFO, "sib = %02"NACL_PRIx8"\n", state->sib));
 594     if (sib_base(state->sib) == 0x05 && modrm_modInline(state->modrm) > 2) {
 595       DEBUG(NaClLog(LOG_INFO,
 596                     "Sib byte implies modrm.mod field <= 2, match fails\n"));
 597       return FALSE;
 598     }
 599   }
 600   return TRUE;
 601 }
 602
 603 static int NaClGetNumDispBytes(NaClInstState* state) {
 604   if (NaClInstRequiresModRm(state)) {
 605     if (16 == state->address_size) {
 606       /* Corresponding to table 2-1 of the Intel manual. */
 607       switch (modrm_modInline(state->modrm)) {
 608         case 0x0:
 609           if (modrm_rmInline(state->modrm) == 0x06) {
 610             return 4;  /* disp16 */
 611           }
 612           break;
 613         case 0x1:
 614           return 1;    /* disp8 */
 615         case 0x2:
 616           return 2;    /* disp16 */
 617         default:
 618           break;
 619       }
 620     } else {
 621       /* Note: in 64-bit mode, 64-bit addressing is treated the same as 32-bit
 622        * addressing. Hence, this section covers the 32-bit addressing.
 623        */
 624       switch(modrm_modInline(state->modrm)) {
 625         case 0x0:
 626           if (modrm_rmInline(state->modrm) == 0x05) {
 627             return 4;  /* disp32 */
 628           } else if (state->has_sib && sib_base(state->sib) == 0x5) {
 629             return 4;
 630           }
 631           break;
 632         case 0x1:
 633           return 1;    /* disp8 */
 634         case 0x2:
 635           return 4;    /* disp32 */
 636         default:
 637           break;
 638       }
 639     }
 640   }
 641   return 0;
 642 }
 643
 644 /* Consume the needed displacement bytes, if applicable. Abort the
 645  * pattern match if any problems are found.
 646  */
 647 static Bool NaClConsumeDispBytes(NaClInstState* state) {
 648   /* First check if the opcode (instruction) pattern specifies that
 649    * displacement bytes should be read, and that reading it will not
 650    * walk past the end of the code segment.
 651    */
 652   state->num_disp_bytes = NaClGetNumDispBytes(state);
 653   DEBUG(NaClLog(LOG_INFO,
 654                 "num disp bytes = %"NACL_PRIu8"\n", state->num_disp_bytes));
 655   state->first_disp_byte = state->bytes.length;
 656   if (state->num_disp_bytes > 0) {
 657     int new_length = state->bytes.length + state->num_disp_bytes;
 658     if (new_length > state->length_limit) {
 659       DEBUG(NaClLog(LOG_INFO, "Can't consume disp, no more bytes!\n"));
 660       return FALSE;
 661     }
 662     /* Read the displacement bytes. */
 663     state->first_disp_byte = state->bytes.length;
 664     NCInstBytesReadBytesInline(state->num_disp_bytes, &state->bytes);
 665   }
 666   return TRUE;
 667 }
 668
 669 /* Returns the number of immediate bytes to parse. */
 670 static int NaClGetNumImmedBytes(NaClInstState* state) {
 671   /* First see if immediate bytes is specified. */
 672   if (0 == NaClHasBit(state->inst->flags,
 673                       (NACL_IFLAG(OpcodeHasImmed) |
 674                        NACL_IFLAG(OpcodeHasImmed_v) |
 675                        NACL_IFLAG(OpcodeHasImmed_b) |
 676                        NACL_IFLAG(OpcodeHasImmed_w) |
 677                        NACL_IFLAG(OpcodeHasImmed_o) |
 678                        NACL_IFLAG(OpcodeHasImmed_Addr) |
 679                        NACL_IFLAG(OpcodeHasImmed_z) |
 680                        NACL_IFLAG(OpcodeHasImmed_p)))) return 0;
 681
 682   /* Now handle specific requests. */
 683   if (state->inst->flags & NACL_IFLAG(OpcodeHasImmed)) {
 684     return state->operand_size;
 685   }
 686   if (state->inst->flags & NACL_IFLAG(OpcodeHasImmed_v)) {
 687     return 4;
 688   } else if (state->inst->flags & NACL_IFLAG(OpcodeHasImmed_b)) {
 689     return 1;
 690   } else if (state->inst->flags & NACL_IFLAG(OpcodeHasImmed_w)) {
 691     return 2;
 692   } else if (state->inst->flags & NACL_IFLAG(OpcodeHasImmed_p)) {
 693     return 6;
 694   } else if (state->inst->flags & NACL_IFLAG(OpcodeHasImmed_o)) {
 695     return 8;
 696   } else if (state->inst->flags & NACL_IFLAG(OpcodeHasImmed_Addr)) {
 697     return NaClExtractAddressSize(state) / 8;
 698   } else if (state->inst->flags & NACL_IFLAG(OpcodeHasImmed_z)) {
 699     if (state->operand_size == 2) {
 700       return 2;
 701     } else {
 702       return 4;
 703     }
 704   } else {
 705     return 0;
 706   }
 707 }
 708
 709 /* Returns the number of immedidate bytes to parse if a second immediate
 710  * number appears in the instruction (zero if no second immediate value).
 711  */
 712 static int NaClGetNumImmed2Bytes(NaClInstState* state) {
 713   if (state->inst->flags & NACL_IFLAG(OpcodeHasImmed2_b)) {
 714     return 1;
 715   } else if (state->inst->flags & NACL_IFLAG(OpcodeHasImmed2_w)) {
 716     return 2;
 717   } else if (state->inst->flags & NACL_IFLAG(OpcodeHasImmed2_v)) {
 718     return 4;
 719   } else {
 720     return 0;
 721   }
 722 }
 723
 724 /* Consume the needed immediate bytes, if applicable. Abort the
 725  * pattern match if any problems are found.
 726  */
 727 static Bool NaClConsumeImmediateBytes(NaClInstState* state) {
 728   /* find out how many immediate bytes are expected. */
 729   state->num_imm_bytes = NaClGetNumImmedBytes(state);
 730   DEBUG(NaClLog(LOG_INFO,
 731                 "num immediate bytes = %"NACL_PRIu8"\n", state->num_imm_bytes));
 732   state->first_imm_byte = 0;
 733   if (state->num_imm_bytes > 0) {
 734     int new_length;
 735     /* Before reading immediate bytes, be sure that we won't walk
 736      * past the end of the code segment.
 737      */
 738     new_length = state->bytes.length + state->num_imm_bytes;
 739     if (new_length > state->length_limit) {
 740       DEBUG(NaClLog(LOG_INFO, "Can't consume immediate, no more bytes!\n"));
 741       return FALSE;
 742     }
 743     /* Read the immediate bytes. */
 744     state->first_imm_byte = state->bytes.length;
 745     NCInstBytesReadBytesInline(state->num_imm_bytes, &state->bytes);
 746   }
 747   /* Before returning, see if second immediate value specified. */
 748   state->num_imm2_bytes = NaClGetNumImmed2Bytes(state);
 749   DEBUG(NaClLog(LOG_INFO, "num immediate 2 bytes = %"NACL_PRIu8"\n",
 750                 state->num_imm2_bytes));
 751   if (state->num_imm2_bytes > 0) {
 752     int new_length;
 753     /* Before reading immediate bytes, be sure that we don't walk
 754      * past the end of the code segment.
 755      */
 756     new_length = state->bytes.length + state->num_imm2_bytes;
 757     if (new_length > state->length_limit) {
 758       DEBUG(NaClLog(LOG_INFO, "Can't consume 2nd immediate, no more bytes!\n"));
 759       return FALSE;
 760     }
 761     /* Read the immediate bytes. */
 762     NCInstBytesReadBytesInline(state->num_imm2_bytes, &state->bytes);
 763   }
 764   return TRUE;
 765 }
 766
 767 /* Validate that any opcode (instruction) pattern prefix assumptions are
 768  * met by prefix bits. If not, abort the pattern match.
 769  */
 770 static Bool NaClValidatePrefixFlags(NaClInstState* state) {
 771   /* Check lock prefix assumptions. */
 772   if (state->prefix_mask & kPrefixLOCK) {
 773     if (state->inst->flags & NACL_IFLAG(OpcodeLockable)) {
 774       /* Only allow if all destination operands are memory stores. */
 775       uint32_t i;
 776       Bool has_lockable_dest = FALSE;
 777       NaClExpVector* vector = NaClInstStateExpVector(state);
 778       DEBUG(NaClLog(LOG_INFO, "checking if lock valid on:\n");
 779             NaClExpVectorPrint(NaClLogGetGio(), state));
 780       for (i = 0; i < vector->number_expr_nodes; ++i) {
 781         NaClExp* node = &vector->node[i];
 782         DEBUG(NaClLog(LOG_INFO, "  checking node %d\n", i));
 783         if ((NACL_EMPTY_EFLAGS != (node->flags & NACL_EFLAG(ExprSet))) &&
 784             (node->kind == ExprMemOffset)) {
 785           has_lockable_dest = TRUE;
 786           break;
 787         }
 788       }
 789       if (!has_lockable_dest) {
 790         DEBUG(NaClLog(LOG_INFO, "Instruction doesn't allow lock prefix "
 791                       "on non-memory destination"));
 792         return FALSE;
 793       }
 794     } else {
 795       DEBUG(NaClLog(LOG_INFO, "Instruction doesn't allow lock prefix\n"));
 796       return FALSE;
 797     }
 798   }
 799   /* Check REX prefix assumptions. */
 800   if (NACL_TARGET_SUBARCH == 64 &&
 801       (state->prefix_mask & kPrefixREX)) {
 802     if (state->inst->flags &
 803         (NACL_IFLAG(OpcodeUsesRexW) | NACL_IFLAG(OpcodeHasRexR) |
 804          NACL_IFLAG(OpcodeRex))) {
 805       if (((state->inst->flags & NACL_IFLAG(OpcodeUsesRexW)) &&
 806            0 == (state->rexprefix & 0x8)) ||
 807           ((state->inst->flags & NACL_IFLAG(OpcodeHasRexR)) &&
 808            0 == (state->rexprefix & 0x4))) {
 809         DEBUG(NaClLog(LOG_INFO, "can't match REX prefix requirement\n"));
 810         return FALSE;
 811       }
 812     }
 813   }
 814   return TRUE;
 815 }
 816
 817 /* Move back to point just after the prefix sequence (defined by
 818  * inst_length).
 819  */
 820 static void NaClClearInstState(NaClInstState* state, uint8_t inst_length) {
 821   if (state->bytes.length != inst_length) {
 822     NCInstBytesResetInline(&state->bytes);
 823     NCInstBytesReadBytesInline(inst_length, &state->bytes);
 824   }
 825   state->modrm = 0;
 826   state->has_sib = FALSE;
 827   state->sib = 0;
 828   state->num_disp_bytes = 0;
 829   state->first_disp_byte = 0;
 830   state->num_imm_bytes = 0;
 831   state->first_imm_byte = 0;
 832   state->num_imm2_bytes = 0;
 833   state->operand_size = 32;
 834   state->address_size = 32;
 835   state->nodes.is_defined = FALSE;
 836   state->nodes.number_expr_nodes = 0;
 837 }
 838
 839 /* Move back to the beginning of the instruction, so that we can reparse. */
 840 static void NaClResetInstState(NaClInstState* state) {
 841   if (state->bytes.length > 0) {
 842     NCInstBytesResetInline(&state->bytes);
 843   }
 844   state->num_prefix_bytes = 0;
 845   state->opcode_prefix = 0;
 846   state->num_opcode_bytes = 0;
 847   state->rexprefix = 0;
 848   state->num_rex_prefixes = 0;
 849   state->modrm = 0;
 850   state->has_prefix_duplicates = FALSE;
 851   state->has_ambig_segment_prefixes = FALSE;
 852   state->has_sib = FALSE;
 853   state->sib = 0;
 854   state->num_disp_bytes = 0;
 855   state->first_disp_byte = 0;
 856   state->num_imm_bytes = 0;
 857   state->first_imm_byte = 0;
 858   state->num_imm2_bytes = 0;
 859   state->prefix_mask = 0;
 860   state->inst = NULL;
 861   state->nodes.is_defined = FALSE;
 862   state->nodes.number_expr_nodes = 0;
 863 }
 864
 865 /* Get the corresponding instruction for the given offset. */
 866 static const NaClInst* NaClGetOpcodeInst(const NaClDecodeTables *tables,
 867                                          NaClOpcodeArrayOffset offset) {
 868   return (NACL_OPCODE_NULL_OFFSET == offset)
 869       ? NULL
 870       : &tables->opcodes_table[offset];
 871 }
 872
 873 /* Get the corresponding instruction for the given prefix and opcode. */
 874 static const NaClInst* NaClGetPrefixOpcodeInst(const NaClDecodeTables *tables,
 875                                                NaClInstPrefix prefix,
 876                                                uint8_t opcode) {
 877   const NaClPrefixOpcodeSelector* selector = &tables->opcode_selectors[prefix];
 878   if ((opcode >= selector->first_opcode) &&
 879       (opcode <= selector->last_opcode)) {
 880     return NaClGetOpcodeInst(
 881         tables,
 882         tables->opcode_entries[
 883             selector->table_offset + (opcode - selector->first_opcode)]);
 884   }
 885   return NULL;
 886 }
 887
 888 /*
 889  * Given the opcode prefix descriptor, return the list of candidate opcodes to
 890  * try and match against the byte stream in the given state. Before returning,
 891  * this function automatically advances the opcode prefix descriptor to describe
 892  * the next list to use if the returned list doesn't provide any matches.
 893  *
 894  * Parameters:
 895  *   state - The state of the instruction being decoded.
 896  *   desc - The description of how the opcode bytes have been matched.
 897  *      The value passed in is the currrent match, the value at exit is
 898  *      the value to be used the next time this function is called (to
 899  *      get the next set of possible instructions).
 900  *   opcode_length - The length (in bytes) of the opcode for the returned
 901  *       candidate opcodes.
 902  */
 903 static const NaClInst* NaClGetNextInstCandidates(
 904     NaClInstState* state, NaClInstPrefixDescriptor* desc,
 905     uint8_t* inst_length) {
 906   const NaClInst* cand_insts;
 907   if (desc->next_length_adjustment) {
 908     (*inst_length) += desc->next_length_adjustment;
 909     desc->opcode_byte = state->bytes.byte[*inst_length - 1];
 910   }
 911   cand_insts = NaClGetPrefixOpcodeInst(state->decoder_tables,
 912                                        desc->matched_prefix,
 913                                        desc->opcode_byte);
 914   DEBUG(NaClLog(LOG_INFO, "Lookup candidates using [%s][%x]\n",
 915                 NaClInstPrefixName(desc->matched_prefix), desc->opcode_byte));
 916   switch (desc->matched_prefix) {
 917     case Prefix660F:
 918       desc->matched_prefix = Prefix0F;
 919       desc->opcode_prefix = 0;
 920       break;
 921     case Prefix660F38:
 922       desc->matched_prefix = Prefix0F38;
 923       desc->opcode_prefix = 0;
 924       break;
 925     case Prefix660F3A:
 926       desc->matched_prefix = Prefix0F3A;
 927       desc->opcode_prefix = 0;
 928       break;
 929     case PrefixD8:
 930     case PrefixD9:
 931     case PrefixDA:
 932     case PrefixDB:
 933     case PrefixDC:
 934     case PrefixDD:
 935     case PrefixDE:
 936     case PrefixDF:
 937       desc->matched_prefix = NoPrefix;
 938       desc->next_length_adjustment = -1;
 939       break;
 940     default:
 941       /* No more simplier prefices, give up search after current lookup. */
 942       desc->matched_prefix = NaClInstPrefixEnumSize;
 943       break;
 944   }
 945   return cand_insts;
 946 }
 947
 948 static Bool NaClConsumeHardCodedNop(NaClInstState* state) {
 949   uint8_t next_byte;
 950   const NaClInstNode* next;
 951   uint8_t next_length = 0;
 952   const NaClInst* matching_inst = NULL;
 953   uint8_t matching_length = 0;
 954
 955   next_byte = NCInstByteInline(&state->bytes, next_length);
 956   next = state->decoder_tables->hard_coded;
 957
 958   /* Find maximal match in trie. */
 959   while (NULL != next) {
 960     if (next_byte == next->matching_byte) {
 961       DEBUG(NaClLog(LOG_INFO,
 962                     "NaClConsume opcode char: %"NACL_PRIx8"\n", next_byte));
 963       next_length++;
 964       if (NACL_OPCODE_NULL_OFFSET != next->matching_inst) {
 965         matching_inst = NaClGetOpcodeInst(state->decoder_tables,
 966                                           next->matching_inst);
 967         matching_length = next_length;
 968       }
 969       if (next_length < state->length_limit) {
 970         next = next->success;
 971         if (next != NULL) {
 972           next_byte = NCInstByteInline(&state->bytes, next_length);
 973         }
 974       } else {
 975         break;
 976       }
 977     } else if (next->matching_byte < next_byte) {
 978       next = next->fail;
 979     } else {
 980       break;
 981     }
 982   }
 983   if (NULL == matching_inst) {
 984     return FALSE;
 985   } else {
 986     /* TODO(karl) Make this more general. Currently assumes that no
 987      * additional processing (other than opcode selection) is needed.
 988      * This is currently safe only because all instructions modeled
 989      * using opcode sequences have no (useful) operands, and hence
 990      * no additional information is needed.
 991      */
 992     NaClResetInstState(state);
 993     state->inst = matching_inst;
 994     NCInstBytesReadBytesInline(matching_length, &state->bytes);
 995     DEBUG(NaClLog(LOG_INFO, "matched inst sequence [%d]!\n", matching_length));
 996     return TRUE;
 997   }
 998 }
 999
1000 EXTERN_C_END
1001
1002 #endif   /* NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_X86_DECODER_NC_INST_STATE_STATICS_C__ */