* Execute the ASMap bytecode to find the ASN for an IP * * This function interprets the asmap bytecode and uses bits from the IP * address to navigate through the encoded trie structure, ultimately * returning an ASN value. */
| 178 | * returning an ASN value. |
| 179 | */ |
| 180 | uint32_t Interpret(const std::span<const std::byte> asmap, const std::span<const std::byte> ip) |
| 181 | { |
| 182 | size_t pos{0}; |
| 183 | const size_t endpos{asmap.size() * 8}; |
| 184 | uint8_t ip_bit{0}; |
| 185 | const uint8_t ip_bits_end = ip.size() * 8; |
| 186 | uint32_t default_asn = 0; |
| 187 | while (pos < endpos) { |
| 188 | Instruction opcode = DecodeType(pos, asmap); |
| 189 | if (opcode == Instruction::RETURN) { |
| 190 | // Found leaf node - return the ASN |
| 191 | uint32_t asn = DecodeASN(pos, asmap); |
| 192 | if (asn == INVALID) break; // ASN straddles EOF |
| 193 | return asn; |
| 194 | } else if (opcode == Instruction::JUMP) { |
| 195 | // Binary branch: if IP bit is 1, jump forward; else continue |
| 196 | uint32_t jump = DecodeJump(pos, asmap); |
| 197 | if (jump == INVALID) break; // Jump offset straddles EOF |
| 198 | if (ip_bit == ip_bits_end) break; // No input bits left |
| 199 | if (int64_t{jump} >= static_cast<int64_t>(endpos - pos)) break; // Jumping past EOF |
| 200 | if (ConsumeBitBE(ip_bit, ip)) { // Check next IP bit (big-endian) |
| 201 | pos += jump; // Bit = 1: skip to right subtree |
| 202 | } |
| 203 | // Bit = 0: fall through to left subtree |
| 204 | } else if (opcode == Instruction::MATCH) { |
| 205 | // Compare multiple IP bits against a pattern |
| 206 | // The match value encodes both length and pattern: |
| 207 | // - highest set bit position determines length (bit_width - 1) |
| 208 | // - lower bits contain the pattern to compare |
| 209 | uint32_t match = DecodeMatch(pos, asmap); |
| 210 | if (match == INVALID) break; // Match bits straddle EOF |
| 211 | int matchlen = std::bit_width(match) - 1; // An n-bit value matches n-1 input bits |
| 212 | if ((ip_bits_end - ip_bit) < matchlen) break; // Not enough input bits |
| 213 | for (int bit = 0; bit < matchlen; bit++) { |
| 214 | if (ConsumeBitBE(ip_bit, ip) != ((match >> (matchlen - 1 - bit)) & 1)) { |
| 215 | return default_asn; // Pattern mismatch - use default |
| 216 | } |
| 217 | } |
| 218 | // Pattern matched - continue execution |
| 219 | } else if (opcode == Instruction::DEFAULT) { |
| 220 | // Update the default ASN for subsequent MATCH failures |
| 221 | default_asn = DecodeASN(pos, asmap); |
| 222 | if (default_asn == INVALID) break; // ASN straddles EOF |
| 223 | } else { |
| 224 | break; // Instruction straddles EOF |
| 225 | } |
| 226 | } |
| 227 | // Reached EOF without RETURN, or aborted (see any of the breaks above) |
| 228 | // - should have been caught by SanityCheckAsmap below |
| 229 | assert(false); |
| 230 | return 0; // 0 is not a valid ASN |
| 231 | } |
| 232 | |
| 233 | /** |
| 234 | * Validates ASMap structure by simulating all possible execution paths. |