| 128 | } |
| 129 | |
| 130 | bool SanityCheckASMap(const std::vector<bool>& asmap, int bits) |
| 131 | { |
| 132 | const std::vector<bool>::const_iterator begin = asmap.begin(), endpos = asmap.end(); |
| 133 | std::vector<bool>::const_iterator pos = begin; |
| 134 | std::vector<std::pair<uint32_t, int>> jumps; // All future positions we may jump to (bit offset in asmap -> bits to consume left) |
| 135 | jumps.reserve(bits); |
| 136 | Instruction prevopcode = Instruction::JUMP; |
| 137 | bool had_incomplete_match = false; |
| 138 | while (pos != endpos) { |
| 139 | uint32_t offset = pos - begin; |
| 140 | if (!jumps.empty() && offset >= jumps.back().first) return false; // There was a jump into the middle of the previous instruction |
| 141 | Instruction opcode = DecodeType(pos, endpos); |
| 142 | if (opcode == Instruction::RETURN) { |
| 143 | if (prevopcode == Instruction::DEFAULT) return false; // There should not be any RETURN immediately after a DEFAULT (could be combined into just RETURN) |
| 144 | uint32_t asn = DecodeASN(pos, endpos); |
| 145 | if (asn == INVALID) return false; // ASN straddles EOF |
| 146 | if (jumps.empty()) { |
| 147 | // Nothing to execute anymore |
| 148 | if (endpos - pos > 7) return false; // Excessive padding |
| 149 | while (pos != endpos) { |
| 150 | if (*pos) return false; // Nonzero padding bit |
| 151 | ++pos; |
| 152 | } |
| 153 | return true; // Sanely reached EOF |
| 154 | } else { |
| 155 | // Continue by pretending we jumped to the next instruction |
| 156 | offset = pos - begin; |
| 157 | if (offset != jumps.back().first) return false; // Unreachable code |
| 158 | bits = jumps.back().second; // Restore the number of bits we would have had left after this jump |
| 159 | jumps.pop_back(); |
| 160 | prevopcode = Instruction::JUMP; |
| 161 | } |
| 162 | } else if (opcode == Instruction::JUMP) { |
| 163 | uint32_t jump = DecodeJump(pos, endpos); |
| 164 | if (jump == INVALID) return false; // Jump offset straddles EOF |
| 165 | if (int64_t{jump} > int64_t{endpos - pos}) return false; // Jump out of range |
| 166 | if (bits == 0) return false; // Consuming bits past the end of the input |
| 167 | --bits; |
| 168 | uint32_t jump_offset = pos - begin + jump; |
| 169 | if (!jumps.empty() && jump_offset >= jumps.back().first) return false; // Intersecting jumps |
| 170 | jumps.emplace_back(jump_offset, bits); |
| 171 | prevopcode = Instruction::JUMP; |
| 172 | } else if (opcode == Instruction::MATCH) { |
| 173 | uint32_t match = DecodeMatch(pos, endpos); |
| 174 | if (match == INVALID) return false; // Match bits straddle EOF |
| 175 | int matchlen = CountBits(match) - 1; |
| 176 | if (prevopcode != Instruction::MATCH) had_incomplete_match = false; |
| 177 | if (matchlen < 8 && had_incomplete_match) return false; // Within a sequence of matches only at most one should be incomplete |
| 178 | had_incomplete_match = (matchlen < 8); |
| 179 | if (bits < matchlen) return false; // Consuming bits past the end of the input |
| 180 | bits -= matchlen; |
| 181 | prevopcode = Instruction::MATCH; |
| 182 | } else if (opcode == Instruction::DEFAULT) { |
| 183 | if (prevopcode == Instruction::DEFAULT) return false; // There should not be two successive DEFAULTs (they could be combined into one) |
| 184 | uint32_t asn = DecodeASN(pos, endpos); |
| 185 | if (asn == INVALID) return false; // ASN straddles EOF |
| 186 | prevopcode = Instruction::DEFAULT; |
| 187 | } else { |