Regular instructions golden file test.

src/trusted/validator_ragel/compress_regular_instructions.py

+# Copyright (c) 2013 The Native Client Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+"""
+Traverse the validator's DFA, collect all "normal" instruction and then
+compress output.  Note: "anybyte fields" (immediates and displacements)
+are always filled with zeros.  Otherwise processing of sextillions (sic!)
+of possibilities will take too long.
+
+Each rule is applied only when all variants are accepted by validator.
+The following compression rules are present:
+
+1. Compress ModR/M (+SIB & displacement).
+  Instruction: 00 00  add %al,(%rax)
+  ...
+  Instruction: 00 ff  add %bh,%bh
+    becomes
+  Instruction: 00 XX  add [%al..%bh],[%al..%bh or memory]
+
+1a. Compress ModR/M (+SIB & displacement) memory-only.
+  Instruction: f0 01 00  lock add %eax,(%eax)
+  ...
+  Instruction: f0 01 bf 00 00 00 00  lock add %edi,0x0(%edi)
+    becomes
+  Instruction: f0 01 XX  lock add [%eax..edi],[memory]
+
+1b. Compress ModR/M register only.
+  Instruction: 66 0f 50 c0  movmskpd %xmm0,%eax
+  ...
+  Instruction: 66 0f 50 ff  movmskpd %xmm7,%edi
+    becomes
+  Instruction: 66 0f 50 XX  movmskpd [%xmm0..%xmm7],[%eax..edi]
+
+2. Compress ModR/M (+SIB & displacement) with opcode extension.
+  Instruction: 0f 90 00  seto (%eax)
+  ...
+  Instruction: 0f 90 c7  seto %bh
+    becomes
+  Instruction: 0f 90 XX/0  seto [%al..%bh or memory]
+
+2a. Compress ModR/M (+SIB & displacement) memory-only with opcode extension.
+  Instruction: f0 ff 00  lock incl (%eax)
+  ...
+  Instruction: f0 ff 84 ff 00 00 00 00  lock incl 0x0(%edi,%edi,8)
+    becomes
+  Instruction: f0 ff XX/1  lock decl [memory]
+
+2b. Compress ModR/M register-only with opcode extension.
+  Instruction: 0f 71 d0 00  psrlw $0x0,%mm0
+  ...
+  Instruction: 0f 71 d7 00  psrlw $0x0,%mm7
+    becomes
+  Instruction: 66 0f 71 XX/2 00  psrlw $0x0,[%mm0..%mm7]
+
+3. Compress register-in-opcode.
+  Instruction: d9 c0  fld %st(0)
+  ...
+  Instruction: d9 c7  fld %st(7)
+    becomes
+  Instruction: Instruction: d9 c[0..7]  fld [%st(0)..%st(7)]
+
+  Only applies if all possible register accesses are accepted by validator.
+
+4. Special compressor for "set" instruction.
+  Instruction: 0f 90 XX/0  seto [%al..%bh or memory]
+  ...
+  Instruction: 0f 90 XX/7  seto [%al..%bh or memory]
+    becomes
+  Instruction: 0f 90 XX  seto [%al..%bh or memory]
+"""
+
+import itertools
+import multiprocessing
+import optparse
+import os
+import re
+import subprocess
+import sys
+import tempfile
+import traceback
+
+import dfa_parser
+import dfa_traversal
+import validator
+
+
+# Register names in 'natual' order (as defined by IA32/x86-64 ABI)
+#
+# X86-64 ABI splits all registers in groups of 8 because it uses 3-bit field
+# in opcode, ModR/M, and/or SIB bytes to encode them.
+#
+# In most cases there are 16 registers of a given kind and two such groups,
+# but there are couple of exceptions:
+#   1. There are 20 8-bit registers and three groups (two of them overlap)
+#   2. There are eight X87 and MMX registers thus two groups are identical
+#
+# We use typical register from a group to name the whole group.  Most groups
+# use first register, but 'spl' group uses fifth register because it's first
+# four registers are the same as 'al' group.  We use mnemonic name 'mmalt'
+# to represent the "evil mirror" of the 'mm0' group.
+REGISTERS = {
+     'al': [  'al',  'cl',  'dl',  'bl',  'ah',  'ch',  'dh',  'bh' ],
+    'spl': [  'al',  'cl',  'dl',  'bl', 'spl', 'bpl', 'sil', 'dil' ],
+     'ax': [  'ax',  'cx',  'dx',  'bx',  'sp',  'bp',  'si',  'di' ],
+    'eax': [ 'eax', 'ecx', 'edx', 'ebx', 'esp', 'ebp', 'esi', 'edi' ],
+    'rax': [ 'rax', 'rcx', 'rdx', 'rbx', 'rsp', 'rbp', 'rsi', 'rdi' ],
+    'r8b': [ 'r{}b'.format(N) for N in range(8,16)                  ],
+    'r8w': [ 'r{}w'.format(N) for N in range(8,16)                  ],
+    'r8d': [ 'r{}d'.format(N) for N in range(8,16)                  ],
+     'r8': [ 'r{}'.format(N) for N in range(8,16)                   ],
+    'mm0': [ 'mm{}'.format(N) for N in range(8)                     ],
+  'mmalt': [ 'mm{}'.format(N) for N in range(8)                     ],
+  'st(0)': [ 'st({})'.format(N) for N in range(8)                   ],
+   'xmm0': [ 'xmm{}'.format(N) for N in range(8)                    ],
+   'xmm8': [ 'xmm{}'.format(N) for N in range(8,16)                 ],
+   'ymm0': [ 'ymm{}'.format(N) for N in range(8)                    ],
+   'ymm8': [ 'ymm{}'.format(N) for N in range(8,16)                 ]
+}
+
+
+NOP = 0x90
+
+
+def PadToBundleSize(bytes):
+  assert len(bytes) <= validator.BUNDLE_SIZE
+  return bytes + [NOP] * (validator.BUNDLE_SIZE - len(bytes))
+
+
+# In x86-64 mode we have so-called 'restricted register' which is used to
+# tie two groups together.  Some instructions require particular value to
+# be stored in this variable, while some accept any non-special restricted
+# register (%ebp and %esp are special because they can only be accepted by
+# a few 'special' instructions).
+#
+# You can find more details in the "NaCl SFI model on x86-64 systems" manual.
+#
+# We try to feed all possible 'restricted registers' into validator and then
+# classify the instruction using this map.  If set of acceptable 'restricted
+# registers' is not here, then it's an error in validator.
+ACCEPTABLE_X86_64_INPUTS = {
+  0x00001: 'input_rr=%eax',
+  0x00002: 'input_rr=%ecx',
+  0x00004: 'input_rr=%edx',
+  0x00008: 'input_rr=%ebx',
+  0x00010: 'input_rr=%esp',
+  0x00020: 'input_rr=%ebp',
+  0x00040: 'input_rr=%esi',
+  0x00080: 'input_rr=%edi',
+  0x00100: 'input_rr=%r8d',
+  0x00200: 'input_rr=%r9d',
+  0x00400: 'input_rr=%r10d',
+  0x00800: 'input_rr=%r11d',
+  0x01000: 'input_rr=%r12d',
+  0x02000: 'input_rr=%r13d',
+  0x04000: 'input_rr=%r14d',
+  0x08000: 'input_rr=%r15d',
+  0x1ffcf: 'input_rr=any_nonspecial'
+}
+
+# Any instruction must produce either None or one of fifteen registers as an
+# output 'restricted register' value.  'r15d' is NOT acceptable as an output.
+ACCEPTABLE_X86_64_OUTPUT_REGISTERS = tuple(
+    '%' + reg for reg in (REGISTERS['eax'] + REGISTERS['r8d'])[0:-1])
+
+
+def ValidateInstruction(instruction, validator_inst):
+  bundle = ''.join(map(chr, PadToBundleSize(instruction)))
+  if options.bitness == 32:
+    result = validator_inst.ValidateChunk(bundle, bitness=32)
+    return result, []
+  else:
+    valid_inputs = 0
+    known_final_rr = None
+    output_rr = None
+    # Note that iteration order is aligned with ACCEPTABLE_X86_64_INPUTS array
+    # above.
+    for bit, initial_rr in enumerate(validator.ALL_REGISTERS + [None]):
+      valid, final_rr = validator_inst.ValidateAndGetFinalRestrictedRegister(
+          bundle, len(instruction), initial_rr)
+      if valid:
+        # final_rr should not depend on input_rr
+        assert valid_inputs == 0 or known_final_rr == final_rr
+        valid_inputs |= 1 << bit
+        known_final_rr = final_rr
+    # If nothing is accepted then instruction is not valid.  Easy and simple.
+    if valid_inputs == 0: return False, []
+    # If returned value in unacceptable we'll get IndexError here and this
+    # test will fail
+    if known_final_rr is not None:
+      output_rr = ACCEPTABLE_X86_64_OUTPUT_REGISTERS[known_final_rr]
+    # If collected valid_inputs are unacceptable we'll get KeyError here and
+    # this test will fail
+    return True, [ACCEPTABLE_X86_64_INPUTS[valid_inputs],
+                  'output_rr={}'.format(output_rr)]
+
+
+class WorkerState(object):
+  def __init__(self, prefix, validator):
+    self.total_instructions = 0
+    self.num_valid = 0
+    self.validator = validator
+    self.output = set()
+    self.trace = []
+
+
+  def ReceiveInstruction(self, bytes):
+    self.total_instructions += 1
+    result, notes = ValidateInstruction(bytes, self.validator)
+    if result:
+      self.num_valid += 1
+      dis = self.validator.DisassembleChunk(
+          ''.join(map(chr, bytes)),
+          bitness=options.bitness)
+      for line_nr in xrange(len(dis)):
+        dis[line_nr] = str(dis[line_nr])
+        assert dis[line_nr][0:17] == 'Instruction(0x' + str(line_nr) + ': '
+        assert dis[line_nr][-1:] == ')'
+        dis[line_nr] = dis[line_nr][17:-1]
+      # If %rip is involved then comment will be different depending on the
+      # instruction length.  Eliminate it.
+      if '(%rip)' in dis[0]:
+        dis[0] = re.sub(' # 0x[ ]*[0-9a-fA-F]*', '', dis[0])
+      # Zero displacements are represented as 0x0 for all instructions except
+      # jumps where they disassembled as non-zero due to %eip/%rip-relative
+      # addressing. We replace this displacement with %eip/%rip to simplify
+      # compression.
+      if ' 0x' in dis[0] and ' 0x0' not in dis[0]:
+        for bytes in xrange(1, 16):
+          dis[0] = re.sub(
+              '(' + '(?:[0-9a-fA-F][0-9a-fA-F] ){' + str(bytes) + '} .* )' +
+              hex(bytes) + '(.*)',
+              '\\1%eip\\2' if options.bitness == 32 else '\\1%rip\\2',
+              dis[0]);
+      dis[0] = 'Instruction: ' + dis[0]
+      dis += notes
+      self.output.add('; '.join(dis))
+
+
+  def RecordTrace(self, compressor_nr, instruction):
+    self.trace.append((compressor_nr, instruction))
+
+
+# Compressor has three slots: regex (which picks apart given instruction),
+# subst (which is used to denote compressed version) and replacements (which
+# are used to generate set of instructions from a given code).
+#
+# Example compressor:
+#   regex = '.*?[0-9a-fA-F]([0-7])  \\w* (%e(?:[abcd]x|[sb]p|[sd]i)).*()'
+#   subst = ('[0-7]', '[%eax..%edi]', ' # register in opcode')
+#   replacements = ((0, '%eax'), (1, '%ecx'), (2, '%edx'), (3, '%ebx')
+#                   (4, '%esp'), (5, '%ebp'), (6, '%esi'), (7, '%edi'))
+#
+# When faced with instriuction '40  inc %eax' it will capture the following
+# pieces of said instruction: '4[0]  inc [%eax]'.
+#
+# Then it will produce the following eight instructions:
+#   '40  inc %eax'
+#   '41  inc %ecx'
+#   '42  inc %edx'
+#   '43  inc %ebx'
+#   '44  inc %esp'
+#   '45  inc %ebp'
+#   '46  inc %esi'
+#   '47  inc %edi'
+#
+# If all these instructions can be found in a set of instructions then
+# compressor will remove them from said set and will insert one replacement
+# "compressed instruction" '4[0-7]  inc [%eax..%edi] # register in opcode'.
+#
+# Note that last group is only used in the replacement.  It's used to grab marks
+# added by previous compressors and to replace them with a new mark.
+class Compressor(object):
+  __slots__ = [
+    'regex',
+    'subst',
+    'replacements'
+  ]
+
+  def __init__(self, regex, subst, replacements=None):
+    self.regex = re.compile(regex)
+    self.subst = subst
+    self.replacements = [] if replacements is None else replacements
+
+
+def CompressionTemplate(instruction, match, mark):
+  """ Replace all match groups with the mark. """
+  pos = 0
+  format_str = ''
+  for group in range(1, len(match.groups())):
+    format_str += instruction[pos:match.start(group)] + mark
+    pos = match.end(group)
+  return format_str + instruction[pos:match.start(len(match.groups()))]
+
+
+def CompressOneMatch(instructions, instruction, match, compressor):
+  format_str = CompressionTemplate(instruction, match, '{}')
+  subset = set()
+  for replacement in compressor.replacements:
+    replacement_str = format_str.format(*replacement)
+    if not replacement_str in instructions:
+      return (False, instructions)
+    subset.add(replacement_str)
+  instructions -= subset
+  instructions.add((format_str + '{}').format(*compressor.subst))
+  return (True, instructions)
+
+
+def CompressOneInstruction(instructions, compressors, split, cache):
+  sorted_instructions = (sorted(i for i in instructions if i > split) +
+                         sorted(i for i in instructions if i < split))
+  for instruction in sorted_instructions:
+    if instruction in cache:
+      compressors_list = cache[instruction]
+      for compressor_nr, match, compressor in compressors_list:
+        result, instructions = CompressOneMatch(
+            instructions, instruction, match, compressor)
+        if result:
+          return (instructions, compressor_nr, instruction)
+    else:
+      compressors_list = []
+      for compressor_nr, compressor in enumerate(compressors):
+        match = compressor.regex.match(instruction)
+        if match:
+          compressors_list.append((compressor_nr, match, compressor))
+          result, instructions = CompressOneMatch(
+              instructions, instruction, match, compressor)
+          if result:
+            return (instructions, compressor_nr, instruction)
+      cache[instruction] = compressors_list
+  return (instructions, False, False)
+
+
+def Compressed(instructions, compressors, show_progress):
+  split = ''
+  cache = {}
+  while True:
+    instructions, rule, split = CompressOneInstruction(
+        instructions, compressors, split, cache)
+    if rule is False: break
+    show_progress(rule, split)
+  return instructions
+
+
+def Worker((prefix, state_index)):
+  worker_state = WorkerState(prefix, worker_validator)
+
+  try:
+    dfa_traversal.TraverseTree(
+        dfa.states[state_index],
+        final_callback=worker_state.ReceiveInstruction,
+        prefix=prefix,
+        anyfield=0)
+    if (prefix[0] != 0x0f or prefix[1] != 0x0f): # Skip 3DNow! instructions
+      worker_state.output = Compressed(set(worker_state.output),
+                                       compressors,
+                                       worker_state.RecordTrace)
+  except Exception as e:
+    traceback.print_exc() # because multiprocessing imap swallows traceback
+    raise
+
+  return (
+      prefix,
+      worker_state.total_instructions,
+      worker_state.num_valid,
+      worker_state.output,
+      worker_state.trace)
+
+
+def ParseOptions():
+  parser = optparse.OptionParser(usage='%prog [options] xmlfile')
+
+  parser.add_option('--bitness',
+                    choices=['32', '64'],
+                    help='The subarchitecture: 32 or 64')
+  parser.add_option('--validator_dll',
+                    help='Path to librdfa_validator_dll')
+  parser.add_option('--decoder_dll',
+                    help='Path to librdfa_decoder_dll')
+
+  options, args = parser.parse_args()
+  options.bitness = int(options.bitness)
+
+  if len(args) != 1:
+    parser.error('specify one xml file')
+
+  (xml_file, ) = args
+
+  return options, xml_file
+
+
+# Version suitable for use in regular expressions
+REGISTERS_RE = REGISTERS.copy()
+REGISTERS_RE['st(0)'] = [ 'st\\({}\\)'.format(N) for N in range(8) ]
+REGISTERS_RE['st\\(0\\)'] = REGISTERS_RE['st(0)']
+
+# Index names in 'natual' order (as defined by IA32/x86-64 ABI)
+INDEXES = {
+  'eax': [ 'eax', 'ecx', 'edx', 'ebx', 'eiz', 'ebp', 'esi', 'edi' ],
+  'rax': [ 'rax', 'rcx', 'rdx', 'rbx', 'riz', 'rbp', 'rsi', 'rdi' ],
+   'r8': [  'r8',  'r9', 'r10', 'r11', 'r12', 'r13', 'r14', 'r15' ]
+}
+# Register which can not be used as base in 64-bit mode in all incarnations
+X86_64_BASE_REGISTERS = set([
+  '%spl', '%bpl', '%r15b',
+   '%sp',  '%bp', '%r15w',
+  '%esp', '%ebp', '%r15d',
+  '%rsp', '%rbp',  '%r15',
+  '%rip'
+])
+
+
+def ModRMRegisterReplacements(rm, reg=None, writes_to='rm', opcode_bits=0,
+                              memory_accessed=True, register_write='ignore'):
+  """Creates replacement tuples list for register-to-register instructions
+
+  Args:
+    rm: rm operand kind (see REGISTERS array)
+    reg: reg operand kind (see REGISTERS array) or None if reg is not used
+    writes_to: three-state selector
+      'reg'  - instruction uses rm as source, reg as destination
+      'rm'   - instruction uses reg as source, rm as destination
+      'both' - instruction writes to both reg and rm
+    opcode_bits: opcode extensions code (used when reg is None)
+    memory_accessed: True if instruction accesses memory

[halyavin, 2013/11/12 11:44:06]

Not used. Default to True makes it even more misleading.

[khim, 2013/11/13 00:32:00]

Done.

+    register_write: three-state selector
+      'sandbox' - instruction can be used to produce "restricted register"
+      'protect' - instruction can damage output, protect "special registers"
+      'ignore'  - instruction does not affect it's operands (e.g. test) or
+                  is used with non-GP registers (X87, MMX, XMM, etc)
+
+  Returns:
+    List of replacement tuples
+  """
+  output_key = (options.bitness, reg, rm, writes_to, opcode_bits,
+                memory_accessed, register_write)
+  if output_key in ModRMRegisterReplacements.replacements:
+    return ModRMRegisterReplacements.replacements[output_key]
+
+  replacements = []
+

[halyavin, 2013/11/12 11:44:06]

# Two upper bits of ModR/M byte (mod field) must be equal to 11.

[khim, 2013/11/13 00:32:00]

Done.

+  if reg is None:
+    # reg field is used as opcode extension
+    byte_range = [byte
+                  for byte in range(0xff, 0xbf, -1)
+                  if byte & 0x38 == opcode_bits << 3]

[halyavin, 2013/11/12 11:44:06]

if (byte >> 3) & 0x7 == opcode_bits

[khim, 2013/11/13 00:32:00]

Done.

+  else:
+    byte_range = range(0xff, 0xbf, -1)
+
+  for modrm in byte_range:
+    # Parse ModRM
+    mod_field = (modrm & 0xc0) >> 6

[halyavin, 2013/11/12 11:44:06]

(modrm >> 6) & 0x3

[khim, 2013/11/13 00:32:00]

I don't really like it: reight now it's easy to see that we've grabbed all the
bits from ModR/M because 0xc0 | 0x38 | 0x7 == 0xff.

But whatever, I'll not fight for that.

Done.

+    reg_field = (modrm & 0x38) >> 3

[halyavin, 2013/11/12 11:44:06]

(modrm >> 3) & 0x7

[khim, 2013/11/13 00:32:00]

Done.

+    rm_field  = (modrm & 0x07)
+    if reg is not None:
+      reg_text = '%' + REGISTERS[reg][reg_field]
+    bytes = '{:02x}'.format(modrm)

[halyavin, 2013/11/12 11:44:06]

bytes->byte_text

[khim, 2013/11/13 00:32:00]

Done.

+    rm_text = '%' + REGISTERS[rm][rm_field]
+    replacement = [bytes]

[halyavin, 2013/11/12 11:44:06]

It is not clear to me which variables can be equal to None in code below. I
think some asserts will help to clear this up.

[khim, 2013/11/13 00:32:00]

Done.

+    if reg is None:
+      replacement.append(rm_text)
+    else:
+      replacement.append(rm_text if writes_to == 'reg' else reg_text)

[halyavin, 2013/11/12 11:44:06]

Can any on these 2 fields equal to None?

[khim, 2013/11/13 00:32:00]

Hmm... Reg can be None - that's why we are checking for that case two lines
above! Rm can not be none (there are actually couple of such instructions but
this will just complicate logic immensely for little benefit thus we don't
handle this case here).

+      replacement.append(reg_text if writes_to == 'reg' else rm_text)
+    if options.bitness == 64:
+      replacement.append('any_nonspecial')
+      output = reg_text if writes_to == 'reg' else rm_text

[halyavin, 2013/11/12 11:44:06]

Can output equal to None?

[khim, 2013/11/13 00:32:00]

Sure.

+      replacement.append(output if register_write == 'sandbox' else None)

[halyavin, 2013/11/12 11:44:06]

Why we are pushing None here? I thought that replacement is an array of strings
without None values since they will lead to an exception during replacement.

[khim, 2013/11/13 00:32:00]

Replacement uses .format(...) which means None becomes 'None'

+      if register_write == 'protect' and output in X86_64_BASE_REGISTERS:

[halyavin, 2013/11/12 11:44:06]

# Do not generate replacements that will violate sandboxing rules.

[khim, 2013/11/13 00:32:00]

Done.

+        continue
+      if register_write == 'sandbox' and output == '%r15d':
+        continue
+      if writes_to == 'both' and reg_text in X86_64_BASE_REGISTERS:

[halyavin, 2013/11/12 11:44:06]

Can reg_text equal to None here?

[khim, 2013/11/13 00:32:00]

Makes no sense, really but should be handled correctly.

Added assert to clarify the situation.

+        continue
+    replacement = tuple(replacement)
+    replacements.append(replacement)

[halyavin, 2013/11/12 11:44:06]

We can join these 2 lines to avoid changing type of replacement variable.

[khim, 2013/11/13 00:32:00]

Done.

+  ModRMRegisterReplacements.replacements[output_key] = tuple(replacements)
+  return ModRMRegisterReplacements.replacements[output_key]
+ModRMRegisterReplacements.replacements = {}
+
+
+def ModRMMemoryReplacements(rm, reg=None, writes_to='rm', opcode_bits=0,
+                            memory_accessed=True, register_write='ignore',
+                            index_r8=False):
+  """Creates replacement tuples list for register-to-register instructions

[halyavin, 2013/11/12 11:44:06]

Copy paste error: "register-to-register"

[khim, 2013/11/13 00:32:00]

Done.

+
+  Args:
+    rm: rm operand kind (see REGISTERS array)
+    reg: reg operand kind (see REGISTERS array) or None if reg is not used
+    writes_to: three-state selector
+      'reg'  - instruction uses rm as source, reg as destination
+      'rm'   - instruction uses reg as source, rm as destination
+      'both' - instruction writes to both reg and rm
+    opcode_bits: opcode extensions code (used when reg is None)
+    memory_accessed: True if instruction accesses memory
+    register_write: three-state selector
+      'sandbox' - instruction can be used to produce "restricted register"
+      'protect' - instruction can damage output, protect "special registers"
+      'ignore'  - instruction does not affect it's operands (e.g. test) or
+                  is used with non-GP registers (X87, MMX, XMM, etc)
+    index_r8: True if REX.X bit in the instruction set to 1
+
+  Returns:
+    List of replacement tuples
+  """
+  output_key = (options.bitness, reg, rm, writes_to, opcode_bits, index_r8,
+                memory_accessed, register_write)
+  if output_key in ModRMMemoryReplacements.replacements:
+    return ModRMMemoryReplacements.replacements[output_key]
+
+  if options.bitness == 32:
+    base = 'eax'
+    index = 'eax'
+  else:
+    base = 'r8' if '8' in rm or rm == 'mmalt' else 'rax'

[halyavin, 2013/11/12 11:44:06]

We wanted to replace it with the access to dictionary.

[khim, 2013/11/13 00:32:00]

Done.

+    index = 'r8' if index_r8 else 'rax'
+    input = 'r8d' if index_r8 else 'eax'
+
+  replacements = []
+

[halyavin, 2013/11/12 11:44:06]

# Two upper bits in ModR/M byte (mod field) must be equal to 00, 01 or 10.

[khim, 2013/11/13 00:32:00]

Done.

+  if reg is None:
+    # reg field is used as opcode extension
+    byte_range = [byte
+                  for byte in range(0xbf, -1, -1)
+                  if byte & 0x38 == opcode_bits << 3]
+  else:
+    byte_range = range(0xbf, -1, -1)
+
+  for modrm in byte_range:
+    # Parse ModRM
+    mod_field = (modrm & 0xc0) >> 6
+    reg_field = (modrm & 0x38) >> 3
+    rm_field  = (modrm & 0x07)
+    if reg is not None:
+      reg_text = '%' + REGISTERS[reg][reg_field]
+    # If RM field != %rsp then there are no index
+    if rm_field != validator.REG_RSP:
+      base_text = '%' + REGISTERS[base][rm_field]
+      # If RM field == %rbp and MOD fiels is zero then it's absolute address

[halyavin, 2013/11/12 11:44:06]

fiels->field

[khim, 2013/11/13 00:32:00]

Done.

+      if mod_field == 0 and rm_field == validator.REG_RBP:
+        bytes = '{:02x} 00 00 00 00'.format(modrm)
+        rm_text = '0x0' if options.bitness == 32 else '0x0(%rip)'
+        base_text = '%rip'
+      # Memory access with just a base register
+      elif mod_field == 0:
+        bytes = '{:02x}'.format(modrm)
+        rm_text = '({})'.format(base_text)
+      # Memory access with base and 8bit offset
+      elif mod_field == 1:
+        bytes = '{:02x} 00'.format(modrm)
+        rm_text = '0x0({})'.format(base_text)
+      # Memory access with base and 32bit offset
+      else: # mod_field == 2
+        bytes = '{:02x} 00 00 00 00'.format(modrm)
+        rm_text = '0x0({})'.format(base_text)
+      replacement = [bytes]
+      if reg is None:
+        replacement.append(rm_text)
+      else:
+        replacement.append(rm_text if writes_to == 'reg' else reg_text)
+        replacement.append(reg_text if writes_to == 'reg' else rm_text)
+      if options.bitness == 64:
+        replacement.append('any_nonspecial')
+        output = reg_text if writes_to == 'reg' else None
+        replacement.append(output if register_write == 'sandbox' else None)
+        if memory_accessed and base_text not in X86_64_BASE_REGISTERS:
+          continue
+        if register_write == 'protect' and output in X86_64_BASE_REGISTERS:
+          continue
+        if register_write == 'sandbox' and output == '%r15d':
+          continue
+        if writes_to == 'both' and reg_text in X86_64_BASE_REGISTERS:
+          continue
+      replacement = tuple(replacement)
+      replacements.append(replacement)
+    else:
+      # If RM field == %rsp then we have SIB byte
+      for sib in xrange(0x100):
+        scale_field = (sib & 0xc0) >> 6
+        index_field = (sib & 0x38) >> 3
+        base_field  = (sib & 0x07)
+        index_text = '%' + INDEXES[index][index_field]
+        base_text = '%' + REGISTERS[base][base_field]
+        scale_text = pow(2, scale_field)

[halyavin, 2013/11/12 11:44:06]

Use shift instead and apply str().

[khim, 2013/11/13 00:32:00]

str() is not really needed, but to make sure "..._text" actually text... It's
not time-critical part of the code thus probably Ok

+        # If BASE is %rbp and MOD == 0 then index with 32bit offset is used
+        if mod_field == 0 and base_field == validator.REG_RBP:
+          bytes = '{:02x} {:02x} 00 00 00 00'.format(modrm, sib)
+          if (options.bitness == 32 or

[halyavin, 2013/11/12 11:44:06]

Reverting this if will reduce amount of negative logic here.

[khim, 2013/11/13 00:32:00]

Done.

+              index_field != validator.REG_RSP or
+              scale_field != 0 or index[0:2] == 'r8'):

[halyavin, 2013/11/12 11:44:06]

Can index be equal to r8d/r8w/r8b here?

[khim, 2013/11/13 00:32:00]

Apparently not. We don't support this form of lea and all other instructions are
forbidden because of security rules.

+            rm_text = '0x0(,{},{})'.format(index_text, scale_text)
+          else:
+            rm_text = '0x0'
+          base_text = ''
+        # Memory access with base and index (no offset)
+        elif mod_field == 0:
+          bytes = '{:02x} {:02x}'.format(modrm, sib)
+          rm_text = '({},{},{})'.format(base_text, index_text, scale_text)
+        # Memory access with base, index and 8bit offset
+        elif mod_field == 1:
+          bytes = '{:02x} {:02x} 00'.format(modrm, sib)
+          rm_text = '0x0({},{},{})'.format(base_text, index_text, scale_text)
+        # Memory access with base, index and 32bit offset
+        elif mod_field == 2:
+          bytes = '{:02x} {:02x} 00 00 00 00'.format(modrm, sib)
+          rm_text = '0x0({},{},{})'.format(base_text, index_text, scale_text)
+        # Pretty-printing of access via %rsp
+        if (scale_field == 0 and index != 'r8' and
+            base_field == validator.REG_RSP and
+            index_field == validator.REG_RSP):
+          #index_text = 'any_nonspecial'
+          rm_text = ('0x0({})' if mod_field else '({})').format(base_text)
+        if index_text == "%riz":

[halyavin, 2013/11/12 11:44:06]

Use singular quotes.

[khim, 2013/11/13 00:32:00]

Done.

+          index_text = 'any_nonspecial'

[halyavin, 2013/11/12 11:44:06]

Why we need this replacement?

[khim, 2013/11/13 00:32:00]

Because i've copy-pasted check from another place and it expected to see
'any_nonspecial' there.

Fixed.

+        replacement = [bytes]
+        if reg is None:
+          replacement.append(rm_text)
+        else:
+          replacement.append(rm_text if writes_to == 'reg' else reg_text)
+          replacement.append(reg_text if writes_to == 'reg' else rm_text)
+        if options.bitness == 64:
+          if not memory_accessed or index_text == 'any_nonspecial':
+            replacement.append('any_nonspecial')
+          else:
+            replacement.append('%' + REGISTERS[input][index_field])
+          # Currently xchg can not used used for sandboxing
+          output = reg_text if writes_to == 'reg' else None
+          replacement.append(output if register_write == 'sandbox' else None)
+          if memory_accessed:
+            if base_text not in X86_64_BASE_REGISTERS: continue
+            if index_text in X86_64_BASE_REGISTERS - set(['%r15']): continue
+          if register_write == 'protect' and output in X86_64_BASE_REGISTERS:
+            continue
+          if register_write == 'sandbox' and output == '%r15d':
+            continue
+          if (writes_to == 'both' and
+              reg_text in X86_64_BASE_REGISTERS): continue
+        replacement = tuple(replacement)
+        replacements.append(replacement)
+  ModRMMemoryReplacements.replacements[output_key] = tuple(replacements)
+  return ModRMMemoryReplacements.replacements[output_key]
+ModRMMemoryReplacements.replacements = {}
+
+
+def PrepareCompressors():
+  global compressors
+  global main_compressors
+  global register_compressors
+  global memory_compressors
+
+  # "Larger" compressors should be tried first, then "smaller" ones.
+  main_compressors = []
+  register_compressors = []
+  memory_compressors = []
+  extra_compressors = []
+
+  if options.bitness == 32:
+    register_kinds = ('al', 'ax', 'eax', 'mm0', 'xmm0', 'ymm0')
+    register_kind_pairs = (
+      (  'al',   'al'),
+      (  'ax',   'al'),
+      (  'ax',   'ax'),
+      ( 'eax',   'al'),
+      ( 'eax',   'ax'),
+      ( 'eax',  'eax'),
+      ( 'eax',  'mm0'),
+      ( 'mm0',  'eax'),
+      ( 'eax', 'xmm0'),
+      ('xmm0',  'eax'),
+      ( 'mm0',  'mm0'),
+      ( 'mm0', 'xmm0'),
+      ('xmm0',  'mm0'),
+      ('xmm0', 'xmm0'),
+      ('xmm0', 'ymm0'),
+      ('ymm0', 'xmm0'),
+      ('ymm0', 'ymm0')
+    )
+  else:
+    register_kinds = ('al', 'spl', 'ax', 'eax', 'rax', 'mm0', 'xmm0', 'ymm0',
+                      'r8b', 'r8w', 'r8d', 'r8', 'mmalt', 'xmm8', 'ymm8')
+    register_kind_pairs = (
+      (  'al',   'al'),
+      ( 'spl',  'spl'), ( 'spl',  'r8b'), ( 'r8b',  'spl'), ( 'r8b',   'r8b'),
+      (  'ax',   'al'),
+      (  'ax',  'spl'), (  'ax',  'r8b'), ( 'r8w',  'spl'), ( 'r8w',   'r8b'),
+      (  'ax',   'ax'), (  'ax',  'r8w'), ( 'r8w',   'ax'), ( 'r8w',   'r8w'),
+      ( 'eax',   'al'),
+      ( 'eax',  'spl'), ( 'eax',  'r8b'), ( 'r8d',  'spl'), ( 'r8d',   'r8b'),
+      ( 'eax',   'ax'), ( 'eax',  'r8w'), ( 'r8d',   'ax'), ( 'r8d',   'r8w'),
+      ( 'eax',  'eax'), ( 'eax',  'r8d'), ( 'r8d',  'eax'), ( 'r8d',   'r8d'),
+      ( 'rax',   'al'),
+      ( 'rax',  'spl'), ( 'rax',  'r8b'), (  'r8',  'spl'), (  'r8',   'r8b'),
+      ( 'rax',   'ax'), ( 'rax',  'r8w'), (  'r8',   'ax'), (  'r8',   'r8w'),
+      ( 'rax',  'eax'), ( 'rax',  'r8d'), (  'r8',  'eax'), (  'r8',   'r8d'),
+      ( 'rax',  'rax'), ( 'rax',   'r8'), (  'r8',  'rax'), (  'r8',    'r8'),
+      ( 'eax',  'mm0'), ( 'eax','mmalt'), ( 'r8d',  'mm0'), ( 'eax', 'mmalt'),
+      ( 'rax',  'mm0'), ( 'rax','mmalt'), (  'r8',  'mm0'), (  'r8', 'mmalt'),
+      ( 'mm0',  'eax'), ('mmalt', 'eax'), ( 'mm0',  'r8d'), ('mmalt',  'r8d'),
+      ( 'mm0',  'rax'), ('mmalt', 'rax'), ( 'mm0',   'r8'), ('mmalt',   'r8'),
+      ( 'eax', 'xmm0'), ( 'eax', 'xmm8'), ( 'r8d', 'xmm0'), ( 'r8d',  'xmm8'),
+      ( 'rax', 'xmm0'), ( 'rax', 'xmm8'), (  'r8', 'xmm0'), (  'r8',  'xmm8'),
+      ('xmm0',  'eax'), ('xmm0',  'r8d'), ('xmm8',  'eax'), ('xmm8',   'r8d'),
+      ('xmm0',  'rax'), ('xmm0',   'r8'), ('xmm8',  'rax'), ('xmm8',    'r8'),
+      ( 'mm0',  'mm0'), ('mmalt', 'mm0'), ( 'mm0','mmalt'), ('mmalt','mmalt'),
+      ( 'mm0', 'xmm0'), ('mmalt','xmm0'), ( 'mm0', 'xmm8'), ('mmalt', 'xmm8'),
+      ('xmm0',  'mm0'), ('xmm8',  'mm0'), ('xmm0','mmalt'), ('xmm8', 'mmalt'),
+      ('xmm0', 'xmm0'), ('xmm0', 'xmm8'), ('xmm8', 'xmm0'), ('xmm8',  'xmm8'),
+      ('xmm0', 'ymm0'), ('xmm0', 'ymm8'), ('xmm8', 'ymm0'), ('xmm8',  'ymm8'),
+      ('ymm0', 'xmm0'), ('ymm0', 'xmm8'), ('ymm8', 'xmm0'), ('ymm8',  'xmm8'),
+      ('ymm0', 'ymm0'), ('ymm0', 'ymm8'), ('ymm8', 'ymm0'), ('ymm8',  'ymm8')
+    )
+
+  # Largest compressors: both reg and rm fields are used
+  for reg, rm in register_kind_pairs:
+    start_reg = REGISTERS[reg][0]
+    end_reg = REGISTERS[reg][-1 if reg[0:2] != 'r8' else -2]
+    start_rm = REGISTERS[rm][0]
+    end_rm = REGISTERS[rm][-1 if rm[0:2] != 'r8' else -2]
+    instruction_kinds = [
+      # Normal instructions with two operands (rm to reg)
+      ({'writes_to':'reg'}, '', ' # rm to reg', ''),
+      # Normal instructions with two operands (reg to rm)
+      ({'writes_to':'rm'}, '', ' # reg to rm', '')
+    ]
+    # Lea in 64 bit mode is truly unique instruction for now
+    if options.bitness == 64 and reg in ('eax', 'r8d', 'rax', 'r8'):
+      instruction_kinds = [
+          ({'writes_to':'reg', 'memory_accessed':False,
+            'register_write':'sandbox' if reg in ('eax', 'r8d') else 'protect'},
+           ' # lea', ' # rm to reg; lea', ' # lea')] + instruction_kinds
+    # There are few more forms in 64 bit case (rm to reg)
+    if options.bitness == 64 and reg in ('eax', 'r8d'):
+      # Zero-extending version.
+      instruction_kinds.append(
+          ({'writes_to':'reg', 'register_write':'sandbox'},
+            '', ' # rm to reg', ''))
+    # More forms in 64 bit case (reg to rm)
+    if options.bitness == 64 and rm in ('eax', 'r8d'):
+      # Zero-extending version.
+      instruction_kinds.append(
+          ({'writes_to':'rm', 'register_write':'sandbox'},
+            '', ' # reg to rm', ''))
+      # Zero-extending xchg/xadd
+      instruction_kinds.append(
+          ({'writes_to':'both', 'register_write':'sandbox'},
+           ' # write to both',
+           ' # reg to rm; write to both',
+           ' # write to both'))
+    # Still more forms for 64 bit case (rm to reg).
+    if options.bitness == 64 and reg in ('al', 'spl', 'ax', 'eax', 'rax',
+                                         'r8b', 'r8w', 'r8d', 'r8'):
+      # Dangerous instructions (rm to reg)
+      instruction_kinds.append(
+          ({'writes_to':'reg', 'register_write':'protect'},
+           '', ' # rm to reg', ''))
+    # Still more forms for 64 bit case (reg to rm)
+    if options.bitness == 64 and rm in ('al', 'spl', 'ax', 'eax', 'rax',
+                                        'r8b', 'r8w', 'r8d', 'r8'):
+      # Dangerous instructions (reg to rm)
+      instruction_kinds.append(
+          ({'writes_to':'rm', 'register_write':'protect'},
+           '', ' # reg to rm', ''))
+      # Dangerous xchg/xadd
+      instruction_kinds.append(
+          ({'writes_to':'both', 'register_write':'protect'},
+           ' # write to both',
+           ' # reg to rm; write to both',
+           ' # write to both'))
+    # 3DNow! instructions
+    instruction_kinds.append(
+        ({'writes_to':'reg', '3dnow':'yes'}, '', ' # rm to reg', ''))
+    if options.bitness == 64:
+      instruction_kinds_index_r8 = []
+      for instruction_kind in instruction_kinds:
+        args = instruction_kind[0].copy()
+        args['index_r8'] = True
+        instruction_kinds_index_r8.append((args, ) + instruction_kind[1:])
+      instruction_kinds.extend(instruction_kinds_index_r8)
+    for args, notes, notes_register, notes_memory in instruction_kinds:
+      regex = '(?: 00)*'
+      # Additional byte is opcode extension with 3DNow! instructions.
+      if '3dnow' in args:
+        regex = ' [0-9a-fA-F][0-9a-fA-F]'
+        args.pop('3dnow')
+      regex += '  (?:lock )?\\w* (?:\\$0x0,|\\$0x0,\\$0x0,|%cl,|%xmm0,)?'
+      # We only need to process ModR/M+SIB '04 04' or '04 07' here
+      if options.bitness == 32:
+        regex_mem = '\\(%esp,%eax,1\\)'
+      else:
+        regex_mem = '\\((?:%rsp|%r15),(?:%rax|%r8),1\\)'
+      output = None
+      output_note = None
+      if args['writes_to'] == 'reg':
+        regex += '(%' + REGISTERS[rm][0] + '|' + regex_mem + ')'
+        regex += ',(%' + REGISTERS[reg][0] + ')'
+        if 'register_write' in args and args['register_write'] == 'sandbox':
+          assert reg in ('eax', 'r8d')
+          output = '%' + reg + '|None'
+          output_note = '[%eax..%edi]' if reg == 'eax' else '[%r8d..%r14d]'
+        subst = (
+            'XX', '[%{}..%{} or memory]'.format(start_rm, end_rm),
+            '[%{}..%{}]'.format(start_reg, end_reg), notes)
+        subst_register = (
+            'XX', '[%{}..%{}]'.format(start_rm, end_rm),
+            '[%{}..%{}]'.format(start_reg, end_reg), notes_register)
+        subst_memory = (
+            'XX', '[memory]',
+            '[%{}..%{}]'.format(start_reg, end_reg), notes_memory)
+      else:
+        regex += '(%' + REGISTERS[reg][0] + ')'
+        regex += ',(%' + REGISTERS[rm][0] + '|' + regex_mem + ')'
+        if 'register_write'in args and args['register_write'] == 'sandbox':
+          assert rm in ('eax', 'r8d')
+          output = '%' + rm + '|None'
+          output_note = '[%eax..%edi]' if rm == 'eax' else '[%r8d..%r14d]'
+        subst = (
+            'XX', '[%{}..%{}]'.format(start_reg, end_reg),
+            '[%{}..%{} or memory]'.format(start_rm, end_rm), notes)
+        subst_register = (
+            'XX', '[%{}..%{}]'.format(start_reg, end_reg),
+            '[%{}..%{}]'.format(start_rm, end_rm), notes_register)
+        subst_memory = (
+            'XX', '[%{}..%{}]'.format(start_reg, end_reg),
+            '[memory]', notes_memory)
+      regex += '.*'
+      if options.bitness == 64:
+        regex += '; input_rr=(%eax|%r8d|any_nonspecial)'
+        regex += '; output_rr=({})'.format(output)
+        if 'memory_accessed' in args:
+          input_note = 'any_nonspecial'
+        else:
+          input_note = '[%r8d..%r15d]' if 'index_r8' in args else '[%eax..%edi]'
+        subst = subst[0:-1] + (input_note, output_note) + subst[-1:]
+        subst_register = subst_register[0:-1] + (
+            'any_nonspecial', output_note) + subst_register[-1:]
+        subst_memory = subst_memory[0:-1] + (
+            input_note, output_note) + subst_memory[-1:]
+      regex += '()'
+      if not 'index_r8' in args:
+        register_replacement = ModRMRegisterReplacements(rm=rm, reg=reg, **args)
+      memory_replacement = ModRMMemoryReplacements(rm=rm, reg=reg, **args)
+      main_replacement = register_replacement + memory_replacement
+      main_compressors.append(Compressor(
+          '.*?(04 0[47])' + regex, subst, main_replacement))
+      memory_compressors.append(Compressor(
+          '.*?(04 0[47])' + regex, subst_memory, memory_replacement))
+      register_compressors.append(Compressor(
+          '.*?(c0)' + regex, subst_register, register_replacement))
+
+  # Smaller compressors: only rm field is used.
+  for rm in register_kinds:
+    start_rm = REGISTERS[rm][0]
+    end_rm = REGISTERS[rm][-1 if rm[0:2] != 'r8' else -2]
+    for opcode_bits in xrange(8):
+      XX_byte_mark = 'XX/' + str(opcode_bits)
+      instruction_kinds = [
+        # The most basic form
+        ({}, '', '', '')
+      ]
+      if options.bitness == 64:
+        # No memory access (e.g. prefetch)
+        instruction_kinds = [
+          ({'memory_accessed':False}, '', '', '')] + instruction_kinds
+      # More forms in 64 bit case.
+      if options.bitness == 64 and rm in ('eax', 'r8d'):
+        # Zero-extending version.
+        instruction_kinds.append(
+            ({'register_write':'sandbox'}, '', '', ''))
+      # Still more forms for 64 bit case (reg to rm).
+      if options.bitness == 64 and rm in ('al', 'spl', 'ax', 'eax', 'rax',
+                                          'r8b', 'r8w', 'r8d', 'r8'):
+        # Dangerous instructions.
+        instruction_kinds.append(
+            ({'register_write':'protect'}, '', '', ''))
+      if options.bitness == 64:
+        instruction_kinds_index_r8 = []
+        for instruction_kind in instruction_kinds:
+          args = instruction_kind[0].copy()
+          args['index_r8'] = True
+          instruction_kinds_index_r8.append((args, ) + instruction_kind[1:])
+        instruction_kinds.extend(instruction_kinds_index_r8)
+      for args, notes, notes_register, notes_memory in instruction_kinds:
+        subst = (XX_byte_mark, '[%{}..%{} or memory]'.format(start_rm, end_rm),
+             notes)
+        subst_register = (XX_byte_mark, '[%{}..%{}]'.format(start_rm, end_rm),
+             notes_register)
+        subst_memory = (XX_byte_mark, '[memory]',
+             notes_memory)
+        regex = ('(?: 00)*  (?:lock )?\\w* (?:\\$0x0,|%cl,)?'
+                 '(%' + REGISTERS[rm][0] + '|' + regex_mem + ').*')
+        output = None
+        output_note = None
+        if options.bitness == 64:
+          if 'register_write' in args and args['register_write'] == 'sandbox':
+            assert rm in ('eax', 'r8d')
+            output = '%' + rm + '|None'
+            output_note = '[%eax..%edi]' if rm == 'eax' else '[%r8d..%r14d]'
+          regex += '; input_rr=(%eax|%r8d|any_nonspecial)'
+          regex += '; output_rr=({})'.format(output)
+          if 'memory_accessed' in args:
+            input_note = 'any_nonspecial'
+          elif 'index_r8' in args:
+            input_note = '[%r8d..%r15d]'
+          else:
+            input_note = '[%eax..%edi]'
+          subst = subst[0:-1] + (input_note, output_note) + subst[-1:]
+          subst_register = subst_register[0:-1] + (
+              'any_nonspecial', output_note) + subst_register[-1:]
+          subst_memory = subst_memory[0:-1] + (
+              input_note, output_note) + subst_memory[-1:]
+        regex += '()'
+        if not 'index_r8' in args:
+          register_replacement = ModRMRegisterReplacements(
+              reg=None, rm=rm, opcode_bits=opcode_bits, **args)
+        memory_replacement = ModRMMemoryReplacements(
+            reg=None, rm=rm, opcode_bits=opcode_bits, **args)
+        main_replacement = register_replacement + memory_replacement
+        main_compressors.append(Compressor(
+            '.*?({:02x} 0[47])'.format(0x04 + opcode_bits * 8) + regex,
+            subst, main_replacement))
+        memory_compressors.append(Compressor(
+            '.*?({:02x} 0[47])'.format(0x04 + opcode_bits * 8) + regex,
+            subst_memory, memory_replacement))
+        register_compressors.append(Compressor(
+            '.*?({:02x})'.format(0xc0 + opcode_bits * 8) + regex,
+            subst_register, register_replacement))
+
+  # Even smaller compressors: only low 3 bits of opcode are used.
+  for reg in register_kinds + ('st(0)',):
+    start_reg = REGISTERS[reg][0]
+    end_reg = REGISTERS[reg][-1 if reg[0:2] != 'r8' else -2]
+    for opcode in xrange(8):
+      for text1, text2, nibble in (
+        ('[0..7]', '[8..f]', xrange(8)),
+        ('[012367]', '[89abef]', (0, 1, 2, 3, 6, 7)),
+        ('[0..6]', '[8..e]', xrange(7))
+      ):
+        # Operand is encoded in opcode
+        extra_compressors.append(Compressor(
+          '.*?[0-9a-fA-F](1)(?: 00)*'
+          '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+          '(%(?:' + REGISTERS_RE[reg][1] + ')).*()',
+          (text1, '[%{}..%{}]'.format(start_reg, end_reg), ''),
+          tuple(('{:x}'.format(n), '%' + REGISTERS[reg][n])
+                for n in nibble)))
+        extra_compressors.append(Compressor(
+          '.*?[0-9a-fA-F](8)(?: 00)*'
+          '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+          '(%(?:' + REGISTERS_RE[reg][0] + ')).*()',
+          (text2, '[%{}..%{}]'.format(start_reg, end_reg), ''),
+          tuple(('{:x}'.format(n + 8), '%' + REGISTERS[reg][n])
+                 for n in nibble)))
+        # Another version for 64 bit case
+        if options.bitness == 64 and reg in ('eax', 'r8d'):
+          # Operand is encoded in opcode and output
+          extra_compressors.append(Compressor(
+            '.*?[0-9a-fA-F](1)(?: 00)*'
+            '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+            '(%(?:' + REGISTERS_RE[reg][1] + ')).*'
+            'output_rr=(%(?:'+ REGISTERS_RE[reg][1] + ')).*()',
+            tuple([text1] + ['[%{}..%{}]'.format(start_reg, end_reg)] * 2 +
+                  ['']),
+            tuple(['{:x}'.format(n)] + ['%' + REGISTERS[reg][n]] * 2
+                   for n in nibble)))
+          extra_compressors.append(Compressor(
+            '.*?[0-9a-fA-F](8)(?: 00)*'
+            '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+            '(%(?:' + REGISTERS_RE[reg][0] + ')).*'
+            'output_rr=(%(?:'+ REGISTERS_RE[reg][0] + ')).*()',
+            tuple([text2] + ['[%{}..%{}]'.format(start_reg, end_reg)] * 2 +
+                  ['']),
+            tuple(['{:x}'.format(n + 8)] + ['%' + REGISTERS[reg][n]] * 2
+                   for n in nibble)))
+  compressors = (main_compressors + memory_compressors + register_compressors +
+      extra_compressors)
+
+  # Special compressors: will handle some cosmetic issues.
+  #
+  # SETxx ignores reg field and thus are described as many separate instructions
+  compressors.append(Compressor(
+      '.*0f 9[0-9a-fA-F] XX(/[0-7])  set.*()', ('', ''),
+      [('/' + str(i), ) for i in range(8)]))
+  # BSWAP is described with opcode "0f c8+r", not "0f /1" in manual
+  if options.bitness == 32:
+    compressors.append(Compressor(
+        '.*(XX/1)  bswap.*ax.*()', ('c[8..f]', ''), [('XX/1', )]))
+  else:
+    compressors.append(Compressor(
+        '.*(XX/1)  bswap.*ax.*()', ('c[89abef]', ''), [('XX/1', )]))
+    compressors.append(Compressor(
+        '.*(XX/1)  bswap.*r8.*()', ('c[8..e]', ''), [('XX/1', )]))
+  # Add mark '# write to both' to certain versions of CMPXCHG, XADD, and XCHG
+  if options.bitness == 64:
+    compressors.append(Compressor(
+          '.* (?:cmpxchg|xadd|xchg).*%al\\.\\.%bh[^#]*()$',
+          (' # write to both', ), ((), )))
+  # "and $0xe0,[%eax..%edi]" is treated specially which means that we list all
+  # versions of and "[$0x1..$0xff],[%eax..%edi]" separately here.
+  # Without this rule these ands comprise 2/3 of the whole output!
+  if options.bitness == 32:
+    compressors.append(Compressor(
+        '.*83 (e0 01  and \\$0x1,%eax)()',
+        ('XX/4 00  and[l]? $0x0,[%eax..%edi or memory]', ' # special and'),
+        [('e{} {:02x}  and $0x{:x},%{}'.format(r, i, i, REGISTERS['eax'][r]), )
+         for i in range(0x01, 0x100) for r in range(8)] +
+        [('XX/4 00  and[l]? $0x0,[%eax..%edi or memory]', )]))
+  else:
+    for reg in ('eax', 'r8d'):
+      start_reg = REGISTERS[reg][0]
+      end_reg = REGISTERS[reg][-1 if reg[0:2] != 'r8' else -2]
+      for index_reg in ('eax', 'r8d'):
+        start_index = REGISTERS[index_reg][0]
+        end_index = REGISTERS[index_reg][-1]
+        compressors.append(Compressor(
+            '.*83 (e0 01  and \\$0x1,%' + reg + ').*'
+            'input_rr=(any_nonspecial); output_rr=(%' + reg + ')()',
+            ('XX/4 00  and[l]? $0x0,[%{}..%{} or memory]'.format(start_reg,
+             end_reg), '[%{}..%{}]'.format(start_index, end_index),
+             '[%{}..%{}]'.format(start_reg, end_reg),
+             ' # special and'),
+            [('e{} {:02x}  and $0x{:x},%{}'.format(r, i, i, REGISTERS[reg][r]),
+              'any_nonspecial', '%' + REGISTERS[reg][r])
+             for i in range(0x01, 0x100) for r in range(7 + (reg == 'eax'))] +
+            [('XX/4 00  and[l]? $0x0,[%{}..%{} or memory]'.format(start_reg,
+              end_reg), '[%{}..%{}]'.format(start_index, end_index),
+              '[%{}..%{}]'.format(start_reg, end_reg))]))
+
+  # "and $e0" and similar are used to align %rsp.  All negative values are
+  # accepted by validator and there are 127 of these.
+  # Consolidate them into one line.
+  if options.bitness == 64:
+    compressors.append(Compressor(
+        '.*(?:81|83) (?:e4|e5) (80) (?:00 00 00 |) and \\$0x(80),%r[bs]p.*()',
+        ('[80..ff]', '[80..ff]', ' # alignment and'),
+        [('{:02x}'.format(i), '{:02x}'.format(i)) for i in range(0x80, 0x100)]))
+
+  # Merge memory and non-memory access
+  if options.bitness == 32:
+    letters_and_registers = (('b', 'al', ''), ('w', 'ax', ''), ('l', 'eax', ''))
+  else:
+    letters_and_registers = (
+       ('b',  'al', 'eax'), ('b', 'spl', 'eax'), ('b', 'r8b', 'r8d'),
+       ('w',  'ax', 'eax'), ('w', 'r8w', 'r8d'),
+       ('l', 'eax', 'eax'), ('l', 'r8d', 'r8d'),
+       ('q', 'rax', 'eax'), ('q',  'r8', 'r8d')
+    )
+  for letter, reg, out_reg in letters_and_registers:
+    start_reg = REGISTERS[reg][0]
+    end_reg = REGISTERS[reg][-1 if reg[0:2] != 'r8' else -2]
+    all_regs = '[%{}..%{}]'.format(start_reg, end_reg)
+    regs_mark = '[%{}..%{} or memory]'.format(start_reg, end_reg)
+    if options.bitness == 64:
+      start_out = REGISTERS[out_reg][0]
+      end_out = REGISTERS[out_reg][-1 if out_reg[0:2] != 'r8' else -2]
+      out_regs = '[%{}..%{}]'.format(start_out, end_out)
+    for notes in ('', ' # rm to reg', ' # reg to rm'):
+      compressors.append(Compressor(
+          '.*  \\w*(' + letter + ') .*(\\[memory]).*()()',
+          ('[{}]?'.format(letter), regs_mark, '', ''),
+          ((letter, '[memory]', ''), ('', all_regs, notes))))
+      if options.bitness == 64:
+        for index_reg in ('eax', 'r8d'):
+          start_index = REGISTERS[index_reg][0]
+          end_index = REGISTERS[index_reg][-1]
+          index_regs = '[%{}..%{}]'.format(start_index, end_index)
+          for output_rrs in ((None, out_regs), (out_regs, None), (None, None)):
+            compressors.append(Compressor(
+                '.*  \\w*(' + letter + ') .*(\\[memory]).*; '
+                'input_rr=(\\[%[a-z0-9]*..%[a-z0-9]*\\]); '
+                'output_rr=(\\[%[a-z0-9]*..%[a-z0-9]*\\]|None)()()',
+                ('[{}]?'.format(letter), regs_mark, index_regs,
+                 output_rrs[0] if output_rrs[0] is not None else output_rrs[1],
+                 '', ''),
+                ((letter, '[memory]', index_regs, output_rrs[0], ''),
+                 ('', all_regs, 'any_nonspecial', output_rrs[1], notes))))
+
+  # REX compressors
+  if options.bitness == 64:
+    # First pretty complex set of compressors to combine versions of REX with
+    # three lowest bits in different states.
+    register_kind_pairs = (
+      (  None,   None),
+      (  'al',   'al'), (  'al',  None), (None,   'al'),
+      (  'ax',   'al'), (  'al',  'ax'),
+      (  'ax',   'ax'), (  'ax',  None), (None,   'ax'),
+      ( 'eax',   'al'), (  'al', 'eax'),
+      ( 'eax',   'ax'), (  'ax', 'eax'),
+      ( 'eax',  'eax'), ( 'eax',  None), (None,  'eax'),
+      ( 'rax',   'al'), (  'al', 'rax'),
+      ( 'rax',   'ax'), (  'ax', 'rax'),
+      ( 'rax',  'eax'), ( 'eax', 'rax'),
+      ( 'rax',  'rax'), ( 'rax',  None), (None,  'rax'),
+      ( 'eax',  'mm0'), ( 'mm0', 'eax'),
+      ( 'rax',  'mm0'), ( 'mm0', 'rax'),
+      ( 'mm0',  'eax'), ( 'eax', 'mm0'),
+      ( 'mm0',  'rax'), ( 'rax', 'mm0'),
+      ( 'eax', 'xmm0'),
+      ( 'rax', 'xmm0'),
+      ('xmm0',  'eax'),
+      ('xmm0',  'rax'),
+      ( 'mm0',  'mm0'), ( 'mm0',  None), (None,  'mm0'),
+      ( 'mm0', 'xmm0'),
+      ('xmm0',  'mm0'),
+      ('xmm0', 'xmm0'),
+      ('xmm0', 'ymm0'), ('xmm0',  None), (None, 'xmm0'),
+      ('ymm0', 'xmm0'),
+      ('ymm0', 'ymm0'), ('ymm0',  None), (None, 'ymm0'),
+    )
+    r8 = {
+      'al': 'r8b',
+      'ax': 'r8w',
+      'eax': 'r8d',
+      'rax': 'r8',
+      'mm0': 'mmalt',
+      'xmm0': 'xmm8',
+      'ymm0': 'ymm8'
+    }
+    for reg, rm in register_kind_pairs:
+      for last_reg, last_rm in ((-1, -1), (-1, -2), (-2, -1), (-2, -2)):
+        if reg:
+          start_reg = REGISTERS[reg][0]
+          start_reg8 = REGISTERS[r8[reg]][0]
+          end_reg = REGISTERS[reg][-1]
+          end_reg0 = 'dil' if reg == 'al' else end_reg
+          end_reg8 = REGISTERS[r8[reg]][last_reg]
+          reg_regex = '\\[(%' + start_reg + '\\.\\.%' + end_reg + ')]'
+          reg_regex0 = '\\[(%' + start_reg + '\\.\\.%' + end_reg0 + ')]'
+        elif last_reg == -2:
+          continue
+        if rm:
+          start_rm = REGISTERS[rm][0]
+          start_rm8 = REGISTERS[r8[rm]][0]
+          end_rm = REGISTERS[rm][-1]
+          end_rm0 = 'dil' if rm == 'al' else end_rm
+          end_rm8 = REGISTERS[r8[rm]][last_rm]
+          rm_regex = ('\\[(%' + start_rm + '\\.\\.%' + end_rm + ')'
+                      '(?: or memory)?]')
+          rm_regex0 = ('\\[(%' + start_rm + '\\.\\.%' + end_rm0 + ')'
+                       '(?: or memory)?]')
+        elif last_rm == -2:
+          continue
+        for rexw in (True, False):
+          for input_rr in (True, False):
+            for output_rr in (True, False) if reg or rm else (None, ):
+              for rm_to_reg in (True, False) if reg and rm else (None, ):
+                # Legacy prefixes
+                regex = '.*:(?: 26| 2e| 36| 3e| 64| 65| 66| 67| f0| f2| f3)*'
+                # REX
+                regex += '( 48).*' if rexw else '( 40|).*'
+                # Replacement text
+                replacement_tuple = (
+                    ' [REX:48..4f]' if rexw else ' [REX:40..47]?', )
+                if reg:
+                  replacement_regs = '%{}..%{}'.format(start_reg, end_reg8)
+                if rm:
+                  replacement_rms = '%{}..%{}'.format(start_rm, end_rm8)
+                # Instruction arguments
+                if not reg and not rm:
+                  pass
+                elif not reg and rm:
+                  if rexw:
+                    regex += rm_regex0 + '.*'
+                  else:
+                    regex += rm_regex + '.*'
+                  replacement_tuple += (replacement_rms, )
+                elif reg and not rm:
+                  if rexw:
+                    regex += reg_regex0 + '.*'
+                  else:
+                    regex += reg_regex + '.*'
+                  replacement_tuple += (replacement_regs, )
+                elif rm_to_reg:
+                  if rexw:
+                    regex += rm_regex0 + ',' + reg_regex0 + '.*'
+                  else:
+                    regex += rm_regex + ',' + reg_regex + '.*'
+                  replacement_tuple += (replacement_rms, replacement_regs)
+                else:
+                  if rexw:
+                    regex += reg_regex0 + ',' + rm_regex0 + '.*'
+                  else:
+                    regex += reg_regex + ',' + rm_regex + '.*'
+                  replacement_tuple += (replacement_regs, replacement_rms)
+                # Input and output restricted registers
+                if input_rr:
+                  regex += 'input_rr=\\[(%eax\\.\\.%edi)].*'
+                  replacement_tuple += ('%eax..%r15d', )
+                if output_rr:
+                  regex += 'output_rr=\\[(%eax\\.\\.%edi)].*'
+                  replacement_tuple += ('%eax..%r14d', )
+                regex += '()'
+                replacement_tuple += ('', )
+                # Replacement cases
+                replacement_tuples = ()
+                for byte in (range(0x48, 0x50)
+                             if rexw
+                             else range(0x40, 0x48) + ['']):
+                  replacement_case = (
+                      ' {:02x}'.format(byte) if byte else byte, )
+                  if byte:
+                    if rm:
+                      if byte & 0x1:
+                        replacement_rms = '%{}..%{}'.format(start_rm8, end_rm8)
+                      else:
+                        replacement_rms = '%{}..%{}'.format(start_rm, end_rm0)
+                    if byte & 0x2:
+                      replacement_index = '%r8d..%r15d'
+                    else:
+                      replacement_index = '%eax..%edi'
+                    if reg:
+                      if byte & 0x4:
+                        replacement_regs = '%{}..%{}'.format(start_reg8,
+                                                             end_reg8)
+                      else:
+                        replacement_regs = '%{}..%{}'.format(start_reg,
+                                                             end_reg0)
+                  else:
+                    if rm:
+                      replacement_rms = '%{}..%{}'.format(start_rm, end_rm)
+                    replacement_index = '%eax..%edi'
+                    if reg:
+                      replacement_regs = '%{}..%{}'.format(start_reg, end_reg)
+                  if not reg and not rm:
+                    pass
+                  elif not reg and rm:
+                    replacement_case += (replacement_rms, )
+                    if byte:
+                      final_rr = '%r8d..%r14d' if byte & 0x1 else '%eax..%edi'
+                    else:
+                      final_rr = '%eax..%edi'
+                  elif reg and not rm:
+                    replacement_case += (replacement_regs, )
+                    if byte:
+                      final_rr = '%r8d..%r14d' if byte & 0x4 else '%eax..%edi'
+                    else:
+                      final_rr = '%eax..%edi'
+                  elif rm_to_reg:
+                    replacement_case += (replacement_rms, replacement_regs)
+                    if byte:
+                      final_rr = '%r8d..%r14d' if byte & 0x4 else '%eax..%edi'
+                    else:
+                      final_rr = '%eax..%edi'
+                  else:
+                    replacement_case += (replacement_regs, replacement_rms)
+                    if byte:
+                      final_rr = '%r8d..%r14d' if byte & 0x1 else '%eax..%edi'
+                    else:
+                      final_rr = '%eax..%edi'
+                  if input_rr: replacement_case += (replacement_index, )
+                  if output_rr: replacement_case += (final_rr, )
+                  replacement_tuples += (replacement_case, )
+                compressors.append(Compressor(
+                    regex, replacement_tuple, replacement_tuples))
+    # This is pretty simple compressor to combine two lines with different REX.W
+    # bits (only if they are otherwise identical).
+    compressors.append(Compressor(
+        '.*(\\[REX:40\\.\\.47]\\?).*()', ('[REX:40..4f]?', ''),
+        (('[REX:40..47]?', ), ('[REX:48..4f]', ))))
+
+
+def ShowProgress(rule, instruction):
+  if rule not in ShowProgress.rules_shown:
+    first_print = True
+    ShowProgress.rules_shown[rule]=len(ShowProgress.rules_shown)
+  else:
+    first_print = False
+  print >> sys.stderr, '-------- Compressed --------'
+  print >> sys.stderr, 'Rule:', ShowProgress.rules_shown[rule]
+  print >> sys.stderr, '--------'
+  compressor = compressors[rule]
+  match = compressor.regex.match(instruction)
+  assert match
+  format_str = CompressionTemplate(instruction, match, '{{{}}}')
+  replacements = sorted(format_str.format(*replacement)
+                        for replacement in compressor.replacements)
+  if len(compressor.replacements) <= 4 or first_print:
+    for replacement in replacements:
+      print >> sys.stderr, replacement
+  else:
+    print >> sys.stderr, replacements[0]
+    print >> sys.stderr, "..."
+    print >> sys.stderr, replacements[-1]
+  print >> sys.stderr, '--------'
+  print >> sys.stderr, 'Compressed', (
+      format_str + '{{{}}}').format(*compressor.subst)
+ShowProgress.rules_shown = {}
+
+
+def main():
+  # We are keeping these global to share state graph and compressors
+  # between workers spawned by multiprocess. Passing them every time is slow.
+  global options, xml_file
+  global dfa
+  global worker_validator
+  options, xml_file = ParseOptions()
+  dfa = dfa_parser.ParseXml(xml_file)
+  worker_validator = validator.Validator(
+      validator_dll=options.validator_dll,
+      decoder_dll=options.decoder_dll)
+  PrepareCompressors()
+
+  assert dfa.initial_state.is_accepting
+  assert not dfa.initial_state.any_byte
+
+  print >> sys.stderr, len(dfa.states), 'states'
+
+  num_suffixes = dfa_traversal.GetNumSuffixes(dfa.initial_state)
+
+  # We can't just write 'num_suffixes[dfa.initial_state]' because
+  # initial state is accepting.
+  total_instructions = sum(
+      num_suffixes[t.to_state]
+      for t in dfa.initial_state.forward_transitions.values())
+  print >> sys.stderr, total_instructions, 'regular instructions total'
+
+  tasks = dfa_traversal.CreateTraversalTasks(dfa.states, dfa.initial_state)
+  print >> sys.stderr, len(tasks), 'tasks'
+
+  pool = multiprocessing.Pool()
+
+  results = pool.imap(Worker, tasks)
+
+  total = 0
+  num_valid = 0
+  full_output = set()
+  for prefix, count, valid_count, output, trace in results:
+    print >> sys.stderr, 'Prefix:', ', '.join(map(hex, prefix))
+    total += count
+    num_valid += valid_count
+    full_output |= output
+    for rule, instruction in trace:
+      ShowProgress(rule, instruction)
+  for instruction in sorted(Compressed(full_output,
+                                       compressors,
+                                       ShowProgress)):
+    print instruction
+
+  print >> sys.stderr, total, 'instructions were processed'
+  print >> sys.stderr, num_valid, 'valid instructions'
+
+
+if __name__ == '__main__':
+  main()