1# Copyright (c) 2013 The Native Client Authors. All rights reserved.
2# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4
5import spec
6
7
8class Validator(object):
9
10  BITNESS = None
11  MAX_SUPERINSTRUCTION_LENGTH = None
12
13  def ValidateSuperinstruction(self, superinstruction):
14    raise NotImplementedError()
15
16  def FitsWithinBundle(self, insns):
17    offset = insns[0].address
18    last_byte_offset = offset + sum(len(insn.bytes) for insn in insns) - 1
19    return offset // spec.BUNDLE_SIZE == last_byte_offset // spec.BUNDLE_SIZE
20
21  def CheckConditions(
22      self, insns, precondition, postcondition):
23    raise NotImplementedError()
24
25  def CheckFinalCondition(self, end_offset):
26    raise NotImplementedError()
27
28  def Validate(self, insns):
29    self.messages = []
30    self.valid_jump_targets = set()
31    self.jumps = {}
32    self.condition = spec.Condition()
33
34    i = 0
35
36    while i < len(insns):
37      offset = insns[i].address
38      self.valid_jump_targets.add(offset)
39      try:
40        # Greedy: try to match longest superinstructions first.
41        for n in range(self.MAX_SUPERINSTRUCTION_LENGTH, 1, -1):
42          if i + n > len(insns):
43            continue
44          try:
45            self.ValidateSuperinstruction(insns[i:i+n])
46            if not self.FitsWithinBundle(insns[i:i+n]):
47              self.messages.append(
48                  (offset, 'superinstruction crosses bundle boundary'))
49            self.CheckConditions(
50                insns[i:i+n],
51                precondition=spec.Condition(),
52                postcondition=spec.Condition())
53            i += n
54            break
55          except spec.DoNotMatchError:
56            continue
57        else:
58          try:
59            jump_destination, precondition, postcondition = (
60                spec.ValidateDirectJumpOrRegularInstruction(
61                    insns[i],
62                    self.BITNESS))
63            if not self.FitsWithinBundle(insns[i:i+1]):
64              self.messages.append(
65                  (offset, 'instruction crosses bundle boundary'))
66            self.CheckConditions(
67                insns[i:i+1], precondition, postcondition)
68            if jump_destination is not None:
69              self.jumps[insns[i].address] = jump_destination
70            i += 1
71          except spec.DoNotMatchError:
72            self.messages.append(
73                (offset, 'unrecognized instruction %r' % insns[i].disasm))
74            i += 1
75
76      except spec.SandboxingError as e:
77        self.messages.append((offset, str(e)))
78        i += 1
79        self.condition = spec.Condition()
80
81    assert i == len(insns)
82
83    end_offset = insns[-1].address + len(insns[-1].bytes)
84    self.valid_jump_targets.add(end_offset)
85    self.CheckFinalCondition(end_offset)
86
87    for source, destination in sorted(self.jumps.items()):
88      if (destination % spec.BUNDLE_SIZE != 0 and
89          destination not in self.valid_jump_targets):
90        self.messages.append(
91            (source, 'jump into a middle of instruction (0x%x)' % destination))
92
93    return self.messages
94
95
96class Validator32(Validator):
97
98  BITNESS = 32
99  MAX_SUPERINSTRUCTION_LENGTH = 2
100
101  def ValidateSuperinstruction(self, superinstruction):
102    spec.ValidateSuperinstruction32(superinstruction)
103
104  def CheckConditions(
105      self, insns, precondition, postcondition):
106    assert precondition == postcondition == spec.Condition()
107
108  def CheckFinalCondition(self, end_offset):
109    assert self.condition == spec.Condition()
110
111
112class Validator64(Validator):
113
114  BITNESS = 64
115  MAX_SUPERINSTRUCTION_LENGTH = 5
116
117  def ValidateSuperinstruction(self, superinstruction):
118    spec.ValidateSuperinstruction64(superinstruction)
119
120  def CheckConditions(
121      self, insns, precondition, postcondition):
122    offset = insns[0].address
123    if not self.condition.Implies(precondition):
124      self.messages.append((offset, self.condition.WhyNotImplies(precondition)))
125
126    if not spec.Condition().Implies(precondition):
127      self.valid_jump_targets.remove(offset)
128
129    self.condition = postcondition
130
131    end_offset = offset + sum(len(insn.bytes) for insn in insns)
132    if end_offset % spec.BUNDLE_SIZE == 0:
133      # At the end of bundle we reset condition to default value
134      # (because anybody can jump to this point), so we have to check
135      # that it's safe to do so.
136      if not self.condition.Implies(spec.Condition()):
137        self.messages.append((
138            end_offset,
139            '%s at the end of bundle'
140            % self.condition.WhyNotImplies(spec.Condition())))
141      self.condition = spec.Condition()
142
143  def CheckFinalCondition(self, end_offset):
144    # If chunk ends mid-bundle, we have to check final condition separately.
145    if end_offset % spec.BUNDLE_SIZE != 0:
146      if not self.condition.Implies(spec.Condition()):
147        self.messages.append((
148            end_offset,
149            '%s at the end of chunk'
150            % self.condition.WhyNotImplies(spec.Condition())))
151