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

[halyavin, 2013/12/07 17:27:15]

instruction -> instructions

[khim, 2013/12/08 23:22:31]

Done.

+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

[halyavin, 2013/12/07 17:27:15]

are named by the first register but 'spl' group is named by the fifth register

[khim, 2013/12/08 23:22:31]

Done.

+# 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

[halyavin, 2013/12/07 17:27:15]

which is used to create the compressed version

[khim, 2013/12/08 23:22:31]

Done.

+# 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

[halyavin, 2013/12/07 17:27:15]

with instruction

[khim, 2013/12/08 23:22:31]

Done.

+# pieces of said instruction: '4[0]  inc [%eax]'.

[halyavin, 2013/12/07 17:27:15]

Add the empty group which will be replaced with the note.

[khim, 2013/12/08 23:22:31]

Done.

+#
+# 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

[halyavin, 2013/12/07 17:27:15]

the last group

[halyavin, 2013/12/07 17:27:15]

Replacement is a poor choice of word in this sentence because it is exactly
replacements field that doesn't contain the last group. I suggest to reformulate
the last 2 paragraphs to avoid using 'replacement' word in this meaning (but it
is ok to use 'replacement' word in the other meaning).
For example: ... Then it will replace groups to produce the following 8
instructions: ...
...and will substitute one "compressed instruction"...
... Note that the last group is only used in the substitution ... 
... It matches marks added by the previous compressors and allows us to insert
the new mark. ...

[khim, 2013/12/08 23:22:31]

Done.

[khim, 2013/12/08 23:22:31]

Done.

+# 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):

[halyavin, 2013/12/07 17:27:15]

replacements are never None. Such rules are useless.

[khim, 2013/12/08 23:22:31]

Done.

+    self.regex = re.compile(regex)
+    self.subst = subst
+    self.replacements = [] if replacements is None else replacements

[halyavin, 2013/12/07 17:27:15]

This line can be simplified to self.replacements=replacements

[khim, 2013/12/08 23:22:31]

Done.

+
+
+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()))]

[halyavin, 2013/12/07 17:27:15]

You are not replacing the last group with the mark. As far as I understand this
is intended behavior but you need to update the comment.

We need to rethink this moment. Does regex always ends with '.*()'? Why ignoring
the comment completely is ok? If the last group matches '# reg to rm' for
example, then it means that there is no replacement that will match the original
instruction itself.

If the last group is always '()' and at the end of the regex, we can use simpler
expression instruction[pos:] here. This will mean that we always replace last
group with itself. This behavior is easy to understand.

Also, in this case we must fix the comment above about last group grabbing
comments leaved by previous compressors.

[khim, 2013/12/08 23:22:31]

Actually this behavior is bad.

Take a look on AllMemoryNonMemoryCompressors, e.g.: there we need to use '()()'
in regex to handle this case.

This is remnant of very early [bad] design decision, but sadly it was not all
that easy to fix since it must be changed in all callsites.
I've bitten the bullet and fixed all the callsites instead. I've tried to add
some logic to CompressOneMatch instead and quickly found out that it's basically
impossible to change anything there: add couple of pythong instructions (ifs,
etc) and execution time goes up two, three times!

+
+
+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

[halyavin, 2013/12/07 19:51:15]

Add "assert instruction in subset". We may see a few surprises here.

[khim, 2013/12/08 20:13:04]

No surprises. Done.

+  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)']

[halyavin, 2013/12/07 17:27:15]

Do we need this line?

[khim, 2013/12/08 23:22:31]

Probably not. Removed.

+
+# 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

[halyavin, 2013/12/07 17:27:15]

The comment is wrong. We do can use %r15, %rbp, %rsp and %rip as base.

[khim, 2013/12/08 23:22:31]

Done.

+X86_64_BASE_REGISTERS = set([
+  '%spl', '%bpl', '%r15b',
+   '%sp',  '%bp', '%r15w',
+  '%esp', '%ebp', '%r15d',
+  '%rsp', '%rbp',  '%r15',
+  '%rip'
+])
+
+
+def InstructionIsDangerous(input, output, register_write,
+                           writes_to, memory_accessed=False,
+                           base_text='%riz', index_text='%riz'):
+  """ Check if instruction with given replacements will be dangerous
+
+  Args:
+    input: input argument
+    output: output argument
+    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)
+    memory_accessed: True if instruction accesses memory
+    base: base register (if memory is accessed)
+    index: index register (if memory is accessed)
+
+  Returns:
+    True if instruction should be rejected by validator
+  """
+  if memory_accessed:
+    if base_text not in X86_64_BASE_REGISTERS:
+      return True
+    if index_text in X86_64_BASE_REGISTERS - set(['%r15']):

[halyavin, 2013/12/07 17:27:15]

We wanted to add comment here.

[khim, 2013/12/08 23:22:31]

Done.

+      return True
+  if register_write == 'protect' and output in X86_64_BASE_REGISTERS:
+    return True
+  if register_write == 'sandbox' and output == '%r15d':
+    return True
+  if writes_to == 'both' and input in X86_64_BASE_REGISTERS:
+    return True
+  return False
+
+
+def AppendOperandsReplacement(replacement, rm_text, reg, modrm, writes_to):
+  """ Appends replacement text to replacement list
+
+  Args:
+    replacement: replacement list
+    rm_text: replacement for rm field
+    reg: register kind (or None if reg field is used as opcode extension)
+    modrm: modrm byte
+    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
+
+  Returns:
+    input: textual representation of input argument
+    output: textual representation of output argument
+
+  Side-effect:
+    output (if reg is None) or (input, output) tuple (if reg is not None)
+    are added to replacement list.
+  """
+  if reg is None:
+    assert writes_to == 'rm'
+    input, output = None, rm_text
+    replacement.append(output)
+  else:
+    reg_field = (modrm >> 3) & 0x07
+    reg_text = '%' + REGISTERS[reg][reg_field]
+    if writes_to == 'reg':
+      input, output = rm_text, reg_text
+    else: # rm, both
+      input, output = reg_text, rm_text
+    replacement.extend([input, output])
+  return input, output
+
+
+def ModRMRegisterReplacements(rm, reg=None, writes_to='rm', opcode_bits=0,
+                              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)
+    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
+  """
+  # Reg field can be used either as reg or as opcode extension, but not both
+  assert reg is None or opcode_bits == 0
+
+  output_key = (options.bitness, reg, rm, writes_to, opcode_bits,
+                register_write)
+  if output_key in ModRMRegisterReplacements.replacements:
+    return ModRMRegisterReplacements.replacements[output_key]
+
+  replacements = []
+
+  # Two upper bits of ModR/M byte (mod field) must be equal to 11
+  # This gives us range from 0xc0 to 0xff but we are going from the
+  # end to make rejection faster (%r15 is equal to 0x7 and %rbp is 0x5).
+  if reg is None:
+    # reg field is used as opcode extension
+    byte_range = [byte
+                  for byte in range(0xff, 0xbf, -1)
+                  if (byte >> 3) & 0x7 == opcode_bits]
+  else:
+    byte_range = range(0xff, 0xbf, -1)
+
+  for modrm in byte_range:
+    rm_field  = (modrm & 0x07)
+    rm_text = '%' + REGISTERS[rm][rm_field]
+    byte_text = '{:02x}'.format(modrm)
+    replacement = [byte_text]
+    input, output = AppendOperandsReplacement(
+        replacement, rm_text, reg, modrm, writes_to)
+    if options.bitness == 64:
+      replacement.append('any_nonspecial') # input_rr
+      replacement.append(output if register_write == 'sandbox' else None)
+      if InstructionIsDangerous(input, output, register_write, writes_to):
+        continue
+    replacements.append(tuple(replacement))
+  ModRMRegisterReplacements.replacements[output_key] = tuple(replacements)
+  return ModRMRegisterReplacements.replacements[output_key]
+ModRMRegisterReplacements.replacements = {}
+
+
+def BaseOnlyMemoryOperand(modrm, base):
+  """Creates replacement tuples list for register-to-memory instructions
+     (base only, no SIB)
+
+  Args:
+    modrm: modrm byte
+    base: register kind for base
+  Returns:
+    bytes_text: replacement for "bytes" group
+    rm_text: textual representation of "rm" argument
+    base_text: textual representation of "base" register
+  """
+  mod_field = (modrm >> 6) & 0x03
+  rm_field  = (modrm & 0x07)
+  base_text = '%' + REGISTERS[base][rm_field]
+  # If RM field == %rbp and MOD field is zero then it's absolute address
+  # in 32-bit mode and %rip-based address in 64-bit mode
+  if mod_field == 0 and rm_field == validator.REG_RBP:
+    bytes_text = '{:02x} 00 00 00 00'.format(modrm)
+    rm_text = '0x0' if options.bitness == 32 else '0x0(%rip)'
+    base_text = '%eiz' if options.bitness == 32 else '%rip'
+  # Memory access with just a base register
+  elif mod_field == 0:
+    bytes_text = '{:02x}'.format(modrm)
+    rm_text = '({})'.format(base_text)
+  # Memory access with base and 8bit offset
+  elif mod_field == 1:
+    bytes_text = '{:02x} 00'.format(modrm)
+    rm_text = '0x0({})'.format(base_text)
+  # Memory access with base and 32bit offset
+  else: # mod_field == 2
+    bytes_text = '{:02x} 00 00 00 00'.format(modrm)
+    rm_text = '0x0({})'.format(base_text)
+  return bytes_text, rm_text, base_text
+
+
+def SIBMemoryOperand(modrm, sib, base, index):
+  """Creates replacement tuples list for register-to-memory instructions
+     (base only, no SIB)
+
+  Args:
+    modrm: modrm byte
+    base: register kind for base
+  Returns:
+    bytes_text: replacement for "bytes" group
+    rm_text: textual representation of "rm" argument
+    base_text: textual representation of "base" register
+    index_text: textual representation of "index" register
+  """
+  mod_field = (modrm >> 6) & 0x03
+  scale_field = (sib >> 6) & 0x03
+  index_field = (sib >> 3) & 0x07
+  base_field  = (sib & 0x07)
+  index_text = '%' + INDEXES[index][index_field]
+  base_text = '%' + REGISTERS[base][base_field]
+  scale_text = str(1 << scale_field)
+  # 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_text = '{:02x} {:02x} 00 00 00 00'.format(modrm, sib)
+    if (options.bitness == 64 and
+        index_text == '%riz' and
+        scale_text == '1'):
+      rm_text = '0x0'
+    else:
+      rm_text = '0x0(,{},{})'.format(index_text, scale_text)
+    # There are no base in this case
+    base_text = '%eiz' if options.bitness == 32 else '%riz'
+  # Memory access with base and index (no offset)
+  elif mod_field == 0:
+    bytes_text = '{: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_text = '{: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_text = '{: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 (or %r12)
+  if (base_field == validator.REG_RSP and
+      index_text in ('%eiz', '%riz') and
+      scale_text == '1'):
+    if mod_field == 0: # no offset
+      rm_text = '({})'.format(base_text)
+    else: # 8-bit or 32-bit offset
+      rm_text = '0x0({})'.format(base_text)
+  return bytes_text, rm_text, base_text, index_text
+
+
+def ModRMMemoryReplacements(reg=None, writes_to='rm', opcode_bits=0,
+                            memory_accessed=True, register_write='ignore',
+                            base_r8=False, index_r8=False):
+  """Creates replacement tuples list for register-to-memory instructions
+
+  Args:
+    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
+  """
+  # Reg field can be used either as reg or as opcode extension, but not both
+  assert reg is None or opcode_bits == 0
+
+  output_key = (options.bitness, reg, writes_to, opcode_bits,
+                base_r8, 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 base_r8 else 'rax'
+    index = 'r8' if index_r8 else 'rax'
+
+  replacements = []
+
+  # Two upper bits of ModR/M byte (mod field) must be equal to 00, 01, or 10
+  # This gives us range from 0x00 to 0xbf but we are going from the end to make
+  # rejection faster (%r15 is equal to 0x7 and %rbp is 0x5).
+  if reg is None:
+    # reg field is used as opcode extension
+    byte_range = [byte
+                  for byte in range(0xbf, -1, -1)
+                  if (byte >> 3) & 0x7 == opcode_bits]
+  else:
+    byte_range = range(0xbf, -1, -1)
+
+  for modrm in byte_range:
+    # If RM field != %rsp then there are no SIB byte
+    if (modrm & 0x07) != validator.REG_RSP:
+      bytes_text, rm_text, base_text = BaseOnlyMemoryOperand(modrm, base)
+      replacement = [bytes_text]
+      input, output = AppendOperandsReplacement(
+          replacement, rm_text, reg, modrm, writes_to)
+      if options.bitness == 64:
+        replacement.append('any_nonspecial')
+        # If writes_to is equal to 'reg' then output is register
+        if writes_to == 'reg' and register_write == 'sandbox':
+          replacement.append(output)
+        else:
+          # Note that instruction like xchg could write to another register:
+          # it's "input"!  But validator currently does not support this case
+          # thus we are ignoring it here and writing "None" in this case, too.
+          replacement.append(None)
+        if InstructionIsDangerous(input, output, register_write, writes_to,
+                                  memory_accessed, base_text):
+          continue
+      replacements.append(tuple(replacement))
+    else:
+      # If RM field == %rsp then we have SIB byte
+      for sib in xrange(0x100):
+        bytes_text, rm_text, base_text, index_text = SIBMemoryOperand(
+            modrm, sib, base, index)
+        replacement = [bytes_text]
+        input, output = AppendOperandsReplacement(
+            replacement, rm_text, reg, modrm, writes_to)
+        if options.bitness == 64:
+          if not memory_accessed or index_text == '%riz':
+            replacement.append('any_nonspecial')
+          else:
+            if index_r8:
+              # Convert %r8 to %r8d, %r9 to %r9d, etc
+              replacement.append(index_text + 'd')
+            else:
+              # Convert %rax to %eax, %rsp to %esp, etc
+              replacement.append('%e' + index_text[2:])
+          # If writes_to is equal to 'reg' then output is register
+          if writes_to == 'reg' and register_write == 'sandbox':
+            replacement.append(output)
+          else:
+            # Note that instruction like xchg could write to another register:
+            # it's "input"!  But validator currently does not support this case
+            # thus we are ignoring it here and writing "None" in this case, too.
+            replacement.append(None)
+          if InstructionIsDangerous(input, output, register_write, writes_to,
+                                    memory_accessed, base_text, index_text):
+            continue
+        replacements.append(tuple(replacement))
+  ModRMMemoryReplacements.replacements[output_key] = tuple(replacements)
+  return ModRMMemoryReplacements.replacements[output_key]
+ModRMMemoryReplacements.replacements = {}
+
+
+# Map from "REX bit off" group of registers to "REX bit on" group of registers
+r8 = {
+  'al': 'r8b',
+  'ax': 'r8w',
+  'eax': 'r8d',
+  'rax': 'r8',
+  'mm0': 'mmalt',
+  'xmm0': 'xmm8',
+  'ymm0': 'ymm8'
+}
+
+
+def RegisterKinds():
+  """ Return list of register kinds we process with register compressors """
+
+  if options.bitness == 32:
+    return ('al', 'ax', 'eax', 'mm0', 'xmm0', 'ymm0')
+  else:
+    return ('al', 'spl', 'ax', 'eax', 'rax', 'mm0', 'xmm0', 'ymm0',
+            'r8b', 'r8w', 'r8d', 'r8', 'mmalt', 'xmm8', 'ymm8')
+
+
+def RegisterKindPairs():
+  """ Return hand-picked pairs which we must consider in compressors """
+
+  if options.bitness == 32:
+    return (
+      (  'al',   'al'),
+      (  'ax',   'al'),
+      (  'al',   'ax'),
+      (  'ax',   'ax'),
+      ( 'eax',   'al'),
+      (  'al',  'eax'),
+      ( 'eax',   'ax'),
+      (  'ax',  'eax'),
+      ( '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:
+    return (
+      (  'al',   'al'),
+      ( 'spl',  'spl'), ( 'spl',  'r8b'), ( 'r8b',  'spl'), ( 'r8b',   'r8b'),
+      (  'ax',   'al'),
+      (  'ax',  'spl'), (  'ax',  'r8b'), ( 'r8w',  'spl'), ( 'r8w',   'r8b'),
+      (  'al',   'ax'),
+      ( 'spl',   'ax'), ( 'spl',  'r8w'), ( 'r8b',   'ax'), ( 'r8b',   'r8w'),
+      (  'ax',   'ax'), (  'ax',  'r8w'), ( 'r8w',   'ax'), ( 'r8w',   'r8w'),
+      ( 'eax',   'al'),
+      ( 'eax',  'spl'), ( 'eax',  'r8b'), ( 'r8d',  'spl'), ( 'r8d',   'r8b'),
+      ( 'al',   'eax'),
+      ( 'spl',  'eax'), ( 'spl',  'r8d'), ( 'r8b',  'eax'), ( 'r8b',   'r8d'),
+      ( 'eax',   'ax'), ( 'eax',  'r8w'), ( 'r8d',   'ax'), ( 'r8d',   'r8w'),
+      (  'ax',  'eax'), (  'ax',  'r8d'), ( 'r8w',  'eax'), ( 'r8w',   'r8d'),
+      ( 'eax',  'eax'), ( 'eax',  'r8d'), ( 'r8d',  'eax'), ( 'r8d',   'r8d'),
+      ( 'rax',   'al'),
+      ( 'rax',  'spl'), ( 'rax',  'r8b'), (  'r8',  'spl'), (  'r8',   'r8b'),
+      (  'al',  'rax'),
+      ( 'spl',  'rax'), ( 'spl',   'r8'), ( 'r8b',  'rax'), ( 'r8b',   'r8'),
+      ( 'rax',   'ax'), ( 'rax',  'r8w'), (  'r8',   'ax'), (  'r8',   'r8w'),
+      (  'ax',  'rax'), (  'ax',   'r8'), ( 'r8w',  'rax'), (  'r8w',   'r8'),
+      ( 'rax',  'eax'), ( 'rax',  'r8d'), (  'r8',  'eax'), (  'r8',   'r8d'),
+      ( 'eax',  'rax'), ( 'eax',   'r8'), ( 'r8d',  'rax'), (  'r8d',   'r8'),
+      ( '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')
+    )
+
+
+def MemRegex(opcode_bits = 0):
+  """ Returns three regexes: two for bytes and one textual representation.  """
+
+  modrm_regex = '^.*?({:02x})'.format(0xc0 + opcode_bits * 8)
+  # We only need to process ModR/M+SIB '04 04' or '04 07' here.
+  modrm_sib_regex = '^.*?({:02x} 0[47])'.format(0x04 + opcode_bits * 8)
+  if options.bitness == 32:

[halyavin, 2013/12/07 17:27:15]

# We only match memory operands without offset, so we don't need to add zeros to
the end of modrm_regex and modrm_sib_regex regular expressions.

[khim, 2013/12/08 23:22:31]

Done.

+    regex_mem = '\\(%esp,%eax,1\\)'

[halyavin, 2013/12/07 17:27:15]

regex_mem->mem_regex for consistency.

[khim, 2013/12/08 23:22:31]

Actually it makes more sense to put _mem as suffix. Changes other *_regex
variables instead.

+  else:
+    regex_mem = '\\((?:%rsp|%r15),(?:%rax|%r8),1\\)'
+  return modrm_regex, modrm_sib_regex, regex_mem
+
+
+def RegToRmCompressors(rm, reg, writes_to, memory_accessed=True,

[halyavin, 2013/12/07 19:51:15]

Big refactoring (and so it is better to make it in a separate patchset so that
we can roll it back).

I don't like us maintaining several variables in parallel. I think it is better
to complicate enumeration but simplify Compressor creation. We will need to
introduce 2 new parameters: rm_compression which is 3-state ('register',
'memory', 'register_or_memory') and index_r8 which is 3 state (None, False,
True).

The enumeration will be changed as follows:

for instruction_kind in instruction_kinds:
  for rm_compression in ('register', 'memory', 'register_or_memory'):
    if rm_compression == 'register' and instruction_kind.get('memory_accessed'):
      continue
    if options.bitness == 64 and rm_compression != 'register':
      for index_r8 in (False, True):
        compressors.extends(RegToRmCompressors(reg=reg, rm=rm,
rm_compression=rm_compression, index_r8=index_r8, **instruction_kind)
    else:
      compressors.extends(RegToRmCompressors(reg=reg, rm=rm,
rm_compression=rm_compression, **instruction_kind)

This transformation will allow us to ensure that regex is exactly what is needed
by compressor. Currently we make regex more general so that it matches all 5
variants.

[khim, 2013/12/08 20:13:04]

Done.

+                       register_write='ignore', is_3Dnow=False, notes=''):
+  """Returns a list of reg <-> rm compressors for a given set of parameters.
+
+  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
+    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)
+    is_3DNow - True if instruction is 3DNow! style (opcode in immidiate)
+    notes - Notes to add to the description
+
+  Returns:
+    List of compressors
+  """
+
+  compressors = []
+
+  start_reg = REGISTERS[reg][0]
+  end_reg = REGISTERS[reg][-1]
+  # Exclude r15 from the interval, if instruction can write to reg.
+  if (end_reg.startswith('r15') and register_write != 'ignore' and
+      writes_to in ('reg', 'both')):
+    end_reg = REGISTERS[reg][-2]
+  start_rm = REGISTERS[rm][0]
+  end_rm = REGISTERS[rm][-1]
+  # Exclude r15 from the interval, if instruction can write to rm.
+  if (end_rm.startswith('r15') and register_write != 'ignore' and
+      writes_to in ('rm', 'both')):
+    end_rm = REGISTERS[rm][-2]
+
+  # Regex here matches everything AFTER the ModR/M (+ SIB) bytes.
+  if is_3Dnow:
+    # Immediate byte is opcode extension with 3DNow! instructions.
+    regex = ' [0-9a-fA-F][0-9a-fA-F]'
+  else:
+    # Accept immediate (which is always zeros in our case).
+    regex = '(?: 00)*'
+  # 2 spaces separate byte code from instruction name.
+  regex += '  '
+  # Optional "lock" prefix.
+  regex += '(?:lock )?'
+  # Instruction name.
+  regex += '\\w* '
+  # Immediate or implicit operand that can precede reg/rm pair.
+  regex += '(?:\\$0x0,|\\$0x0,\\$0x0,|%cl,|%xmm0,)?'
+  modrm_regex, modrm_sib_regex, regex_mem = MemRegex()
+  output = None

[halyavin, 2013/12/07 17:27:15]

rename to output_rr_regex

[khim, 2013/12/08 23:22:31]

regex_output_rr

+  output_note = None

[halyavin, 2013/12/07 17:27:15]

rename to output_rr_subst

[khim, 2013/12/08 23:22:31]

subst_output_rr

+  if writes_to == 'reg':
+    regex += '(%' + REGISTERS[rm][0] + '|' + regex_mem + ')'
+    regex += ',(%' + REGISTERS[reg][0] + ')'
+    if register_write == 'sandbox':
+      assert reg in ('eax', 'r8d')
+      output = '%' + reg + '|None'

[halyavin, 2013/12/07 17:27:15]

We need to either remove None from here or explain how it could happen.

[khim, 2013/12/08 23:22:31]

Removed.

+      output_note = '[%eax..%edi]' if reg == 'eax' else '[%r8d..%r14d]'
+    subst = (
+        'XX', '[%{}..%{} or memory]'.format(start_rm, end_rm),
+        '[%{}..%{}]'.format(start_reg, end_reg))
+    subst_register = (
+        'XX', '[%{}..%{}]'.format(start_rm, end_rm),
+        '[%{}..%{}]'.format(start_reg, end_reg))
+    subst_memory = (
+        'XX', '[memory]',
+        '[%{}..%{}]'.format(start_reg, end_reg))
+  else:
+    regex += '(%' + REGISTERS[reg][0] + ')'
+    regex += ',(%' + REGISTERS[rm][0] + '|' + regex_mem + ')'
+    if register_write == 'sandbox':
+      assert rm in ('eax', 'r8d')
+      output = '%' + rm + '|None'

[halyavin, 2013/12/07 17:27:15]

We need to add comment of why we are doing such slightly incorrect compression.

[khim, 2013/12/08 23:22:31]

Done.

+      output_note = '[%eax..%edi]' if rm == 'eax' else '[%r8d..%r14d]'
+    subst = (
+        'XX', '[%{}..%{}]'.format(start_reg, end_reg),
+        '[%{}..%{} or memory]'.format(start_rm, end_rm))
+    subst_register = (
+        'XX', '[%{}..%{}]'.format(start_reg, end_reg),
+        '[%{}..%{}]'.format(start_rm, end_rm))
+    subst_memory = (
+        'XX', '[%{}..%{}]'.format(start_reg, end_reg),
+        '[memory]')
+  # Skip implicit arguments (if any)
+  regex += '.*'
+  if options.bitness == 64:

[halyavin, 2013/12/07 17:49:32]

# We generate 2 variants of compressors with memory operands to enumerate 2
possible values of index_r8 property.

[khim, 2013/12/08 23:22:31]

Done.

+    regex += '; input_rr=(%eax|%r8d|any_nonspecial)'
+    regex += '; output_rr=({})'.format(output)
+    if memory_accessed:

[halyavin, 2013/12/07 17:27:15]

Can we move regex += '; input_rr=(%eax|%r8d)' here and
regex += '; input_rr = (any_nonspecial)' to the else clause?

[khim, 2013/12/08 23:22:31]

Done.

+      input_note = '[%eax..%edi]'

[halyavin, 2013/12/07 17:27:15]

input_note->input_rr_subst

[khim, 2013/12/08 23:22:31]

subst_input_rr

+      input_note_r8 = '[%r8d..%r15d]'

[halyavin, 2013/12/07 17:27:15]

input_note_r8->input_rr_subst_r8

[khim, 2013/12/08 23:22:31]

Removed.

+    else:
+      input_note = 'any_nonspecial'
+      input_note_r8 = 'any_nonspecial'

[halyavin, 2013/12/07 17:49:32]

r8->index8

[khim, 2013/12/08 23:22:31]

Removed

+    subst_r8 = subst + (input_note_r8, output_note)
+    subst = subst + (input_note, output_note)
+    subst_memory_r8 = subst_memory + (input_note_r8, output_note)
+    subst_memory = subst_memory + (input_note, output_note)
+    subst_register = subst_register + ('any_nonspecial', output_note)
+  # With "or memory" or "memory" compressors we always can see where is
+  # reg and where is rm, but with reg to rm or rm to reg it's impossible.
+  # Add the appropriate comment
+  if writes_to == 'reg':
+    notes_register = ' # rm to reg'

[halyavin, 2013/12/07 17:27:15]

notes_register->notes_register_subst

[khim, 2013/12/08 23:22:31]

N/A: Changed (and hopefully simplified) logic differently instead.

+  else:
+    notes_register = ' # reg to rm'
+  if notes != '':
+    notes_register += '; ' + notes
+    notes = ' # ' + notes

[halyavin, 2013/12/07 17:27:15]

notes_subst = '# ' + notes

[khim, 2013/12/08 23:22:31]

N/A: Changed (and hopefully simplified) logic differently instead.

+  subst += (notes, )
+  subst_memory += (notes, )
+  subst_register += (notes_register, )
+  if options.bitness == 64:
+    subst_r8 += (notes, )
+    subst_memory_r8 += (notes, )
+  regex += '()$'
+  base_r8 = rm in r8.values()
+  memory_replacement = ModRMMemoryReplacements(
+      reg=reg, base_r8=base_r8, writes_to=writes_to,
+      memory_accessed=memory_accessed, register_write=register_write)
+  compressors.append(Compressor(
+      modrm_sib_regex + regex, subst_memory, memory_replacement))
+  if options.bitness == 64:
+    memory_replacement_r8 = ModRMMemoryReplacements(
+        reg=reg, base_r8=base_r8, index_r8=True, writes_to=writes_to,
+        memory_accessed=memory_accessed, register_write=register_write)
+    compressors.append(Compressor(
+        modrm_sib_regex + regex, subst_memory_r8, memory_replacement_r8))
+  # Instructions with no memory access are instructions which are doing
+  # something with memory address (e.g. lea) and as such they don't have
+  # non-memory forms.
+  if memory_accessed:
+    register_replacement = ModRMRegisterReplacements(
+         reg=reg, rm=rm, writes_to=writes_to, register_write=register_write)
+    compressors.append(Compressor(
+        modrm_regex + regex, subst_register, register_replacement))
+    main_replacement = register_replacement + memory_replacement
+    compressors.append(Compressor(
+        modrm_sib_regex + regex, subst, main_replacement))
+    if options.bitness == 64:
+      main_replacement_r8 = register_replacement + memory_replacement_r8
+      compressors.append(Compressor(
+          modrm_sib_regex + regex, subst_r8, main_replacement_r8))
+  return compressors
+
+
+def AllRegToRmCompressors():
+  """ Return list of all Reg to RM (and RM to Reg) compressors.  """
+
+  compressors = []
+
+  for reg, rm in RegisterKindPairs():
+    instruction_kinds = [
+      # Normal instructions with two operands (rm to reg)
+      {'writes_to': 'reg'},
+      # Normal instructions with two operands (reg to rm)
+      {'writes_to': 'rm'}
+    ]
+    # In 64 bit mode we have many different types of instructions depending
+    # on whether we are accessing memory or whether we are writing to registers.
+    if options.bitness == 64:
+      # Lea in 64 bit mode is truly unique instruction for now
+      if reg in ('ax', 'r8w', 'eax', 'r8d', 'rax', 'r8'):
+        register_write = 'sandbox' if reg in ('eax', 'r8d') else 'protect'
+        instruction_kinds.append(
+            {'writes_to': 'reg',
+             'memory_accessed': False,
+             'register_write': register_write,
+             'notes': 'lea'})
+      # There are few more forms in 64 bit case (rm to reg)
+      if reg in ('eax', 'r8d'):
+        # Zero-extending version.
+        instruction_kinds.append(
+            {'writes_to': 'reg',
+             'register_write': 'sandbox'})
+      # More forms in 64 bit case (reg to rm)
+      if rm in ('eax', 'r8d'):
+        # Zero-extending version.
+        instruction_kinds.append(
+            {'writes_to': 'rm',
+             'register_write': 'sandbox'})
+        # Zero-extending xchg/xadd
+        instruction_kinds.append(
+            {'writes_to': 'both',
+             'register_write': 'sandbox',
+             'notes': 'write to both'})
+      # Still more forms for 64 bit case (rm to reg).
+      if 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'})
+      # Still more forms for 64 bit case (reg to rm)
+      if 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'})
+        # Dangerous xchg/xadd
+        instruction_kinds.append(
+            {'writes_to': 'both',
+             'register_write': 'protect',
+             'notes': 'write to both'})
+    # 3DNow! instructions
+    if reg in ('mm0', 'mmalt') or rm in ('mm0', 'mmalt'):
+      instruction_kinds.append(
+          {'writes_to': 'reg',
+           'is_3Dnow': True})
+    for instruction_kind in instruction_kinds:
+      compressors.extend(RegToRmCompressors(reg=reg, rm=rm, **instruction_kind))
+  return compressors
+
+
+def RmCompressors(rm, opcode_bits,
+                  memory_accessed=True, register_write='ignore'):
+  """Returns a list of rm compressors for a given set of parameters.
+
+  Args:
+    rm: rm operand kind (see REGISTERS array)
+    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)
+
+  Returns:
+    List of compressors
+  """
+  compressors = []
+
+  start_rm = REGISTERS[rm][0]
+  end_rm = REGISTERS[rm][-1]
+  # Exclude r15 from the interval, if instruction can write to rm.
+  if end_rm.startswith('r15') and register_write != 'ignore':
+    end_rm = REGISTERS[rm][-2]
+  byte_mark = 'XX/' + str(opcode_bits)
+
+  subst = (byte_mark, '[%{}..%{} or memory]'.format(start_rm, end_rm))
+  subst_register = (byte_mark, '[%{}..%{}]'.format(start_rm, end_rm))
+  subst_memory = (byte_mark, '[memory]')
+
+  # Regex here matches everything AFTER the ModR/M (+ SIB) bytes.
+  regex = '(?: 00)*'
+  # 2 spaces separate byte code from instruction name.
+  regex += '  '
+  # Optional "lock" prefix.
+  regex += '(?:lock )?'
+  # Instruction name.
+  regex += '\\w* '
+  # Immediate or implicit operand that can precede rm argument.
+  regex += '(?:\\$0x0,|%cl,)?'
+  modrm_regex, modrm_sib_regex, regex_mem = MemRegex(opcode_bits)
+  # First register or memory access
+  regex += '(%' + REGISTERS[rm][0] + '|' + regex_mem + ').*'
+  output = None
+  output_note = None
+  if options.bitness == 32:
+    subst += ('', )
+    subst_memory += ('', )
+    subst_register += ('', )
+  else:
+    if 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:
+      input_note = '[%eax..%edi]'
+      input_note_r8 = '[%r8d..%r15d]'
+    else:
+      input_note = 'any_nonspecial'
+      input_note_r8 = 'any_nonspecial'
+    subst_r8 = subst + (input_note_r8, output_note, '')
+    subst = subst + (input_note, output_note, '')
+    subst_memory_r8 = subst_memory + (input_note_r8, output_note, '')
+    subst_memory = subst_memory + (input_note, output_note, '')
+    subst_register = subst_register + ('any_nonspecial', output_note, '')
+  regex += '()'
+  base_r8 = rm in r8.values()
+  memory_replacement = ModRMMemoryReplacements(
+      reg=None, base_r8=base_r8, opcode_bits=opcode_bits,
+      memory_accessed=memory_accessed, register_write=register_write)
+  compressors.append(Compressor(
+      modrm_sib_regex + regex, subst_memory, memory_replacement))
+  if options.bitness == 64:
+    memory_replacement_r8 = ModRMMemoryReplacements(
+        reg=None, base_r8=base_r8, index_r8=True, opcode_bits=opcode_bits,
+        memory_accessed=memory_accessed, register_write=register_write)
+    compressors.append(Compressor(
+        modrm_sib_regex + regex, subst_memory_r8, memory_replacement_r8))
+  # Instructions with no memory access are instructions which are doing
+  # something with memory address (e.g. prefetch) and as such they don't
+  # have non-memory forms.
+  if memory_accessed:
+    register_replacement = ModRMRegisterReplacements(
+        reg=None, rm=rm, opcode_bits=opcode_bits, register_write=register_write)
+    compressors.append(Compressor(
+        modrm_regex + regex, subst_register, register_replacement))
+    main_replacement = register_replacement + memory_replacement
+    compressors.append(Compressor(
+        modrm_sib_regex + regex, subst, main_replacement))
+    if options.bitness == 64:
+      main_replacement_r8 = register_replacement + memory_replacement_r8
+      compressors.append(Compressor(
+          modrm_sib_regex + regex, subst_r8, main_replacement_r8))
+  return compressors
+
+
+def AllRmCompressors():
+  """ Return list of all RM (with reg as opcode extension) compressors.  """
+  compressors = []
+
+  for rm in RegisterKinds():
+    for opcode_bits in xrange(8):
+      instruction_kinds = [
+        # The most basic form
+        {}
+      ]
+      # In 64 bit mode we have many different types of instructions depending
+      # on whether we are accessing memory or whether we are writing to
+      # registers.
+      if options.bitness == 64:
+        # No memory access (e.g. prefetch)
+        instruction_kinds.append(
+          {'memory_accessed':False})
+        # More forms in 64 bit case.
+        if rm in ('eax', 'r8d'):
+          # Zero-extending version.
+          instruction_kinds.append(
+              {'register_write':'sandbox'})
+        # Still more forms for 64 bit case (reg to rm).
+        if rm in ('al', 'spl', 'ax', 'eax', 'rax',
+                  'r8b', 'r8w', 'r8d', 'r8'):
+          # Dangerous instructions.
+          instruction_kinds.append(
+              {'register_write':'protect'})
+      for instruction_kind in instruction_kinds:
+        compressors.extend(RmCompressors(
+            rm=rm, opcode_bits=opcode_bits, **instruction_kind))
+  return compressors
+
+
+def AllOpcodeCompressors():
+  """ Return "register in opcode" compressors.   """
+  compressors = []
+
+  for reg in RegisterKinds() + ('st(0)',):
+    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))
+      ):
+        start_reg = REGISTERS[reg][0]
+        end_reg = REGISTERS[reg][-1 if 7 in nibble else -2]
+        subst_regs = '[%{}..%{}]'.format(start_reg, end_reg)
+        # Note that we use instruction with 1st register, not 0th register
+        # here to avoid ambiguity when opcode is 0x00
+        compressors.append(Compressor(
+          '.*?[0-9a-fA-F](1)(?: 00)*'
+          '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+          '(%' + REGISTERS_RE[reg][1] + ').*()',
+          (text1, subst_regs, ''),
+          tuple(('{:x}'.format(n), '%' + REGISTERS[reg][n])
+                for n in nibble)))
+        compressors.append(Compressor(
+          '.*?[0-9a-fA-F](8)(?: 00)*'
+          '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+          '(%' + REGISTERS_RE[reg][0] + ').*()',
+          (text2, subst_regs, ''),
+          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'):
+          compressors.append(Compressor(
+            '.*?[0-9a-fA-F](1)(?: 00)*'
+            '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+            '(%' + REGISTERS_RE[reg][1] + ').*'
+            'output_rr=(%'+ REGISTERS_RE[reg][1] + ').*()',
+            (text1, subst_regs, subst_regs, ''),
+            tuple(['{:x}'.format(n)] + ['%' + REGISTERS[reg][n]] * 2
+                   for n in nibble)))
+          compressors.append(Compressor(
+            '.*?[0-9a-fA-F](8)(?: 00)*'
+            '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+            '(%' + REGISTERS_RE[reg][0] + ').*'
+            'output_rr=(%'+ REGISTERS_RE[reg][0] + ').*()',
+            (text2, subst_regs, subst_regs, ''),
+            tuple(['{:x}'.format(n + 8)] + ['%' + REGISTERS[reg][n]] * 2
+                   for n in nibble)))
+  return compressors
+
+
+def AllMemoryNonMemoryCompressors():
+  """ Return memory/nonmemory compressors.  """
+
+  compressors = []
+
+  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]
+    if reg[0:2] == 'r8':
+      end_regs = (REGISTERS[reg][-2], REGISTERS[reg][-1])
+    else:
+      end_regs = (REGISTERS[reg][-1], )
+    for end_reg in end_regs:
+      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[1] if output_rrs[0] is None else output_rrs[0],
+                   '', ''),
+                  ((letter, '[memory]', index_regs, output_rrs[0], ''),
+                   ('', all_regs, 'any_nonspecial', output_rrs[1], notes))))
+  return compressors
+
+
+def RexCompressor(rm, rmR15, reg, regR15, rexw, input_rr, output_rr, rm_to_reg):
+  """ Return REX compressor (or nothing) for a given set of paramenters.
+
+  Args:
+    rm: rm operand kind (see REGISTERS array) or None if rm is not used
+    reg: reg operand kind (see REGISTERS array) or None if reg is not used
+    rmR15: True if R15 register is included
+    regR15: True if R15 register is included
+    rexw: True if REX.W should be set
+    input_rr: True if input_rr is used
+    output_rr: true if output_rr is used
+    rm_to_reg: True if direction is rm to reg
+  """
+
+  # reg and rm can be of three different possible intervals
+  #   start_reg/rm to end_reg/rm (e.g. from %al to %bh)
+  #   start_reg/rm to end_reg0/rm0 (e.g from %al to %dil)
+  #   start_reg8/rm8 to end_reg8/rm8 (e.g. from %r8b to %r15b)
+  # First form can be observed if there are not REX, second form
+  # if REX.R/REX.B is not set and third form is where it's set.
+  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]][-1 if regR15 else -2]
+    if rexw:
+      reg_regex = '\\[(%' + start_reg + '\\.\\.%' + end_reg0 + ')]'
+    else:
+      reg_regex = '\\[(%' + start_reg + '\\.\\.%' + end_reg + ')]'
+  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]][-1 if rmR15 else -2]
+    if rexw:
+      rm_regex = ('\\[(%' + start_rm + '\\.\\.%' + end_rm0 + ')'
+                  '(?: or memory)?]')
+    else:
+      rm_regex = ('\\[(%' + start_rm + '\\.\\.%' + end_rm + ')'
+                  '(?: or memory)?]')
+
+  # 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:
+    regex += rm_regex + '.*'
+    replacement_tuple += (replacement_rms, )
+  elif reg and not rm:
+    regex += reg_regex + '.*'
+    replacement_tuple += (replacement_regs, )
+  elif rm_to_reg:
+    regex += rm_regex + ',' + reg_regex + '.*'
+    replacement_tuple += (replacement_rms, replacement_regs)
+  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) + [0]):
+    replacement_case = (' {:02x}'.format(byte) if byte else '', )
+    if rm:
+      if byte & 0x1:
+        replacement_rms = '%{}..%{}'.format(start_rm8, end_rm8)
+      elif byte:
+        replacement_rms = '%{}..%{}'.format(start_rm, end_rm0)
+      else:
+        replacement_rms = '%{}..%{}'.format(start_rm, end_rm)
+    if byte & 0x2:
+      replacement_index = '%r8d..%r15d'
+    else:
+      replacement_index = '%eax..%edi'
+    if reg:
+      if byte & 0x4:
+        replacement_regs = '%{}..%{}'.format(start_reg8, end_reg8)
+      elif byte:
+        replacement_regs = '%{}..%{}'.format(start_reg, end_reg0)
+      else:
+        replacement_regs = '%{}..%{}'.format(start_reg, end_reg)
+    if not reg and not rm:
+      pass
+    elif not reg and rm:
+      replacement_case += (replacement_rms, )
+      final_rr = '%r8d..%r14d' if byte & 0x1 else '%eax..%edi'
+    elif reg and not rm:
+      replacement_case += (replacement_regs, )
+      final_rr = '%r8d..%r14d' if byte & 0x4 else '%eax..%edi'
+    elif rm_to_reg:
+      replacement_case += (replacement_rms, replacement_regs)
+      final_rr = '%r8d..%r14d' if byte & 0x4 else '%eax..%edi'
+    else:
+      replacement_case += (replacement_regs, replacement_rms)
+      final_rr = '%r8d..%r14d' if byte & 0x1 else '%eax..%edi'
+    if input_rr: replacement_case += (replacement_index, )
+    if output_rr: replacement_case += (final_rr, )
+    replacement_tuples += (replacement_case, )
+  return Compressor(regex, replacement_tuple, replacement_tuples)
+
+
+def AllRexCompressors():
+  """ Return "REX" compressors which combine different REX prefixes.  """
+
+  if options.bitness != 64:
+    return []
+
+  compressors = []
+
+  # 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'),
+  )
+  for reg, rm in register_kind_pairs:
+    for regR15 in (True, False):
+      for rmR15 in (True, False):
+        for rexw in (True, False):
+          for input_rr in (True, False):
+            for output_rr in (True, False):
+              for rm_to_reg in (True, False):
+                # These combinations will just produce useless duplicates
+                if not reg and not regR15: continue
+                if not rm and not rmR15: continue
+                if not reg and not rm and (output_rr or rm_to_reg): continue
+                compressors.append(RexCompressor(
+                    rm=rm, rmR15=rmR15, reg=reg, regR15=regR15,
+                    rexw=rexw, input_rr=input_rr, output_rr=output_rr,
+                    rm_to_reg=rm_to_reg))
+
+  # 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]', ))))
+  return compressors
+
+
+def AllSpecialCompressors():
+  """ Return all "special" compressors. """
+
+  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)]))
+  return compressors
+
+
+def PrepareCompressors():
+  """ Return list of all compressors sorted from bigger ones to smaller ones """
+
+  return tuple(sorted(
+    AllRegToRmCompressors() +
+    AllRmCompressors() +
+    AllOpcodeCompressors() +
+    AllMemoryNonMemoryCompressors() +
+    AllRexCompressors() +
+    AllSpecialCompressors(),
+    key=lambda compressor: -len(compressor.replacements)))
+
+
+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)
+  global compressors
+  compressors = 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()