Index: src/trusted/validator_ragel/compress_regular_instructions.py |
=================================================================== |
--- src/trusted/validator_ragel/compress_regular_instructions.py (revision 0) |
+++ src/trusted/validator_ragel/compress_regular_instructions.py (revision 0) |
@@ -0,0 +1,1636 @@ |
+# 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 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']): |
+ 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 two memory regexes: for bytes and textual representation. """ |
halyavin
2013/12/06 16:17:58
It is 3 regex now.
khim
2013/12/06 16:28:50
Done.
|
+ |
+ 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: |
+ regex_mem = '\\(%esp,%eax,1\\)' |
+ 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, |
+ 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. |
+ regex = '(?: 00)*' |
+ # Additional byte is opcode extension with 3DNow! instructions. |
+ if is_3Dnow: |
halyavin
2013/12/06 16:05:47
Write it as if else and replace "Additional byte"
khim
2013/12/06 16:28:50
Done.
|
+ regex = ' [0-9a-fA-F][0-9a-fA-F]' |
+ # 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 |
+ output_note = None |
+ 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' |
+ 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' |
+ 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: |
+ 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) |
+ # 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' |
+ else: |
+ notes_register = ' # reg to rm' |
+ if notes != '': |
+ notes_register += '; ' + notes |
+ notes = ' # ' + notes |
+ subst = subst + (notes, ) |
+ subst_memory = subst_memory + (notes, ) |
+ subst_register = subst_register + (notes_register, ) |
+ if options.bitness == 64: |
+ subst_r8 = subst_r8 + (notes, ) |
+ subst_memory_r8 = 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 reg/rm pair. |
+ regex += '(?:\\$0x0,|\\$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 == 64: |
+ 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[0:-1] + (input_note_r8, output_note) + subst[-1:] |
+ subst = subst[0:-1] + (input_note, output_note) + subst[-1:] |
+ subst_memory_r8 = subst_memory[0:-1] + ( |
+ input_note_r8, output_note) + subst_memory[-1:] |
+ subst_memory = subst_memory[0:-1] + ( |
+ input_note, output_note) + subst_memory[-1:] |
+ subst_register = subst_register[0:-1] + ( |
+ 'any_nonspecial', output_note) + subst_register[-1:] |
+ 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( |
+ '.*?({:02x} 0[47])'.format(0x04 + opcode_bits * 8) + 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,)?' |
halyavin
2013/12/06 16:30:38
Use raw literals when you are escaping '\\'
khim
2013/12/08 23:23:05
Done.
|
+ '(%' + 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() |