1 /* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.net.apf; 18 19 import com.android.internal.annotations.VisibleForTesting; 20 21 import java.util.ArrayList; 22 import java.util.HashMap; 23 24 /** 25 * APF assembler/generator. A tool for generating an APF program. 26 * 27 * Call add*() functions to add instructions to the program, then call 28 * {@link generate} to get the APF bytecode for the program. 29 * 30 * @hide 31 */ 32 public class ApfGenerator { 33 /** 34 * This exception is thrown when an attempt is made to generate an illegal instruction. 35 */ 36 public static class IllegalInstructionException extends Exception { IllegalInstructionException(String msg)37 IllegalInstructionException(String msg) { 38 super(msg); 39 } 40 } 41 private enum Opcodes { 42 LABEL(-1), 43 LDB(1), // Load 1 byte from immediate offset, e.g. "ldb R0, [5]" 44 LDH(2), // Load 2 bytes from immediate offset, e.g. "ldh R0, [5]" 45 LDW(3), // Load 4 bytes from immediate offset, e.g. "ldw R0, [5]" 46 LDBX(4), // Load 1 byte from immediate offset plus register, e.g. "ldbx R0, [5]R0" 47 LDHX(5), // Load 2 byte from immediate offset plus register, e.g. "ldhx R0, [5]R0" 48 LDWX(6), // Load 4 byte from immediate offset plus register, e.g. "ldwx R0, [5]R0" 49 ADD(7), // Add, e.g. "add R0,5" 50 MUL(8), // Multiply, e.g. "mul R0,5" 51 DIV(9), // Divide, e.g. "div R0,5" 52 AND(10), // And, e.g. "and R0,5" 53 OR(11), // Or, e.g. "or R0,5" 54 SH(12), // Left shift, e.g, "sh R0, 5" or "sh R0, -5" (shifts right) 55 LI(13), // Load immediate, e.g. "li R0,5" (immediate encoded as signed value) 56 JMP(14), // Jump, e.g. "jmp label" 57 JEQ(15), // Compare equal and branch, e.g. "jeq R0,5,label" 58 JNE(16), // Compare not equal and branch, e.g. "jne R0,5,label" 59 JGT(17), // Compare greater than and branch, e.g. "jgt R0,5,label" 60 JLT(18), // Compare less than and branch, e.g. "jlt R0,5,label" 61 JSET(19), // Compare any bits set and branch, e.g. "jset R0,5,label" 62 JNEBS(20), // Compare not equal byte sequence, e.g. "jnebs R0,5,label,0x1122334455" 63 EXT(21), // Followed by immediate indicating ExtendedOpcodes. 64 LDDW(22), // Load 4 bytes from data memory address (register + immediate): "lddw R0, [5]R1" 65 STDW(23); // Store 4 bytes to data memory address (register + immediate): "stdw R0, [5]R1" 66 67 final int value; 68 Opcodes(int value)69 private Opcodes(int value) { 70 this.value = value; 71 } 72 } 73 // Extended opcodes. Primary opcode is Opcodes.EXT. ExtendedOpcodes are encoded in the immediate 74 // field. 75 private enum ExtendedOpcodes { 76 LDM(0), // Load from memory, e.g. "ldm R0,5" 77 STM(16), // Store to memory, e.g. "stm R0,5" 78 NOT(32), // Not, e.g. "not R0" 79 NEG(33), // Negate, e.g. "neg R0" 80 SWAP(34), // Swap, e.g. "swap R0,R1" 81 MOVE(35); // Move, e.g. "move R0,R1" 82 83 final int value; 84 ExtendedOpcodes(int value)85 private ExtendedOpcodes(int value) { 86 this.value = value; 87 } 88 } 89 public enum Register { 90 R0(0), 91 R1(1); 92 93 final int value; 94 Register(int value)95 private Register(int value) { 96 this.value = value; 97 } 98 } 99 private class Instruction { 100 private final byte mOpcode; // A "Opcode" value. 101 private final byte mRegister; // A "Register" value. 102 private boolean mHasImm; 103 private byte mImmSize; 104 private boolean mImmSigned; 105 private int mImm; 106 // When mOpcode is a jump: 107 private byte mTargetLabelSize; 108 private String mTargetLabel; 109 // When mOpcode == Opcodes.LABEL: 110 private String mLabel; 111 // When mOpcode == Opcodes.JNEBS: 112 private byte[] mCompareBytes; 113 // Offset in bytes from the beginning of this program. Set by {@link ApfGenerator#generate}. 114 int offset; 115 Instruction(Opcodes opcode, Register register)116 Instruction(Opcodes opcode, Register register) { 117 mOpcode = (byte)opcode.value; 118 mRegister = (byte)register.value; 119 } 120 Instruction(Opcodes opcode)121 Instruction(Opcodes opcode) { 122 this(opcode, Register.R0); 123 } 124 setImm(int imm, boolean signed)125 void setImm(int imm, boolean signed) { 126 mHasImm = true; 127 mImm = imm; 128 mImmSigned = signed; 129 mImmSize = calculateImmSize(imm, signed); 130 } 131 setUnsignedImm(int imm)132 void setUnsignedImm(int imm) { 133 setImm(imm, false); 134 } 135 setSignedImm(int imm)136 void setSignedImm(int imm) { 137 setImm(imm, true); 138 } 139 setLabel(String label)140 void setLabel(String label) throws IllegalInstructionException { 141 if (mLabels.containsKey(label)) { 142 throw new IllegalInstructionException("duplicate label " + label); 143 } 144 if (mOpcode != Opcodes.LABEL.value) { 145 throw new IllegalStateException("adding label to non-label instruction"); 146 } 147 mLabel = label; 148 mLabels.put(label, this); 149 } 150 setTargetLabel(String label)151 void setTargetLabel(String label) { 152 mTargetLabel = label; 153 mTargetLabelSize = 4; // May shrink later on in generate(). 154 } 155 setCompareBytes(byte[] bytes)156 void setCompareBytes(byte[] bytes) { 157 if (mOpcode != Opcodes.JNEBS.value) { 158 throw new IllegalStateException("adding compare bytes to non-JNEBS instruction"); 159 } 160 mCompareBytes = bytes; 161 } 162 163 /** 164 * @return size of instruction in bytes. 165 */ size()166 int size() { 167 if (mOpcode == Opcodes.LABEL.value) { 168 return 0; 169 } 170 int size = 1; 171 if (mHasImm) { 172 size += generatedImmSize(); 173 } 174 if (mTargetLabel != null) { 175 size += generatedImmSize(); 176 } 177 if (mCompareBytes != null) { 178 size += mCompareBytes.length; 179 } 180 return size; 181 } 182 183 /** 184 * Resize immediate value field so that it's only as big as required to 185 * contain the offset of the jump destination. 186 * @return {@code true} if shrunk. 187 */ shrink()188 boolean shrink() throws IllegalInstructionException { 189 if (mTargetLabel == null) { 190 return false; 191 } 192 int oldSize = size(); 193 int oldTargetLabelSize = mTargetLabelSize; 194 mTargetLabelSize = calculateImmSize(calculateTargetLabelOffset(), false); 195 if (mTargetLabelSize > oldTargetLabelSize) { 196 throw new IllegalStateException("instruction grew"); 197 } 198 return size() < oldSize; 199 } 200 201 /** 202 * Assemble value for instruction size field. 203 */ generateImmSizeField()204 private byte generateImmSizeField() { 205 byte immSize = generatedImmSize(); 206 // Encode size field to fit in 2 bits: 0->0, 1->1, 2->2, 3->4. 207 return immSize == 4 ? 3 : immSize; 208 } 209 210 /** 211 * Assemble first byte of generated instruction. 212 */ generateInstructionByte()213 private byte generateInstructionByte() { 214 byte sizeField = generateImmSizeField(); 215 return (byte)((mOpcode << 3) | (sizeField << 1) | mRegister); 216 } 217 218 /** 219 * Write {@code value} at offset {@code writingOffset} into {@code bytecode}. 220 * {@link generatedImmSize} bytes are written. {@code value} is truncated to 221 * {@code generatedImmSize} bytes. {@code value} is treated simply as a 222 * 32-bit value, so unsigned values should be zero extended and the truncation 223 * should simply throw away their zero-ed upper bits, and signed values should 224 * be sign extended and the truncation should simply throw away their signed 225 * upper bits. 226 */ writeValue(int value, byte[] bytecode, int writingOffset)227 private int writeValue(int value, byte[] bytecode, int writingOffset) { 228 for (int i = generatedImmSize() - 1; i >= 0; i--) { 229 bytecode[writingOffset++] = (byte)((value >> (i * 8)) & 255); 230 } 231 return writingOffset; 232 } 233 234 /** 235 * Generate bytecode for this instruction at offset {@link offset}. 236 */ generate(byte[] bytecode)237 void generate(byte[] bytecode) throws IllegalInstructionException { 238 if (mOpcode == Opcodes.LABEL.value) { 239 return; 240 } 241 int writingOffset = offset; 242 bytecode[writingOffset++] = generateInstructionByte(); 243 if (mTargetLabel != null) { 244 writingOffset = writeValue(calculateTargetLabelOffset(), bytecode, writingOffset); 245 } 246 if (mHasImm) { 247 writingOffset = writeValue(mImm, bytecode, writingOffset); 248 } 249 if (mCompareBytes != null) { 250 System.arraycopy(mCompareBytes, 0, bytecode, writingOffset, mCompareBytes.length); 251 writingOffset += mCompareBytes.length; 252 } 253 if ((writingOffset - offset) != size()) { 254 throw new IllegalStateException("wrote " + (writingOffset - offset) + 255 " but should have written " + size()); 256 } 257 } 258 259 /** 260 * Calculate the size of either the immediate field or the target label field, if either is 261 * present. Most instructions have either an immediate or a target label field, but for the 262 * instructions that have both, the size of the target label field must be the same as the 263 * size of the immediate field, because there is only one length field in the instruction 264 * byte, hence why this function simply takes the maximum of the two sizes, so neither is 265 * truncated. 266 */ generatedImmSize()267 private byte generatedImmSize() { 268 return mImmSize > mTargetLabelSize ? mImmSize : mTargetLabelSize; 269 } 270 calculateTargetLabelOffset()271 private int calculateTargetLabelOffset() throws IllegalInstructionException { 272 Instruction targetLabelInstruction; 273 if (mTargetLabel == DROP_LABEL) { 274 targetLabelInstruction = mDropLabel; 275 } else if (mTargetLabel == PASS_LABEL) { 276 targetLabelInstruction = mPassLabel; 277 } else { 278 targetLabelInstruction = mLabels.get(mTargetLabel); 279 } 280 if (targetLabelInstruction == null) { 281 throw new IllegalInstructionException("label not found: " + mTargetLabel); 282 } 283 // Calculate distance from end of this instruction to instruction.offset. 284 final int targetLabelOffset = targetLabelInstruction.offset - (offset + size()); 285 return targetLabelOffset; 286 } 287 calculateImmSize(int imm, boolean signed)288 private byte calculateImmSize(int imm, boolean signed) { 289 if (imm == 0) { 290 return 0; 291 } 292 if (signed && (imm >= -128 && imm <= 127) || 293 !signed && (imm >= 0 && imm <= 255)) { 294 return 1; 295 } 296 if (signed && (imm >= -32768 && imm <= 32767) || 297 !signed && (imm >= 0 && imm <= 65535)) { 298 return 2; 299 } 300 return 4; 301 } 302 } 303 304 /** 305 * Jump to this label to terminate the program and indicate the packet 306 * should be dropped. 307 */ 308 public static final String DROP_LABEL = "__DROP__"; 309 310 /** 311 * Jump to this label to terminate the program and indicate the packet 312 * should be passed to the AP. 313 */ 314 public static final String PASS_LABEL = "__PASS__"; 315 316 /** 317 * Number of memory slots available for access via APF stores to memory and loads from memory. 318 * The memory slots are numbered 0 to {@code MEMORY_SLOTS} - 1. This must be kept in sync with 319 * the APF interpreter. 320 */ 321 public static final int MEMORY_SLOTS = 16; 322 323 /** 324 * Memory slot number that is prefilled with the IPv4 header length. 325 * Note that this memory slot may be overwritten by a program that 326 * executes stores to this memory slot. This must be kept in sync with 327 * the APF interpreter. 328 */ 329 public static final int IPV4_HEADER_SIZE_MEMORY_SLOT = 13; 330 331 /** 332 * Memory slot number that is prefilled with the size of the packet being filtered in bytes. 333 * Note that this memory slot may be overwritten by a program that 334 * executes stores to this memory slot. This must be kept in sync with the APF interpreter. 335 */ 336 public static final int PACKET_SIZE_MEMORY_SLOT = 14; 337 338 /** 339 * Memory slot number that is prefilled with the age of the filter in seconds. The age of the 340 * filter is the time since the filter was installed until now. 341 * Note that this memory slot may be overwritten by a program that 342 * executes stores to this memory slot. This must be kept in sync with the APF interpreter. 343 */ 344 public static final int FILTER_AGE_MEMORY_SLOT = 15; 345 346 /** 347 * First memory slot containing prefilled values. Can be used in range comparisons to determine 348 * if memory slot index is within prefilled slots. 349 */ 350 public static final int FIRST_PREFILLED_MEMORY_SLOT = IPV4_HEADER_SIZE_MEMORY_SLOT; 351 352 /** 353 * Last memory slot containing prefilled values. Can be used in range comparisons to determine 354 * if memory slot index is within prefilled slots. 355 */ 356 public static final int LAST_PREFILLED_MEMORY_SLOT = FILTER_AGE_MEMORY_SLOT; 357 358 // This version number syncs up with APF_VERSION in hardware/google/apf/apf_interpreter.h 359 private static final int MIN_APF_VERSION = 2; 360 361 private final ArrayList<Instruction> mInstructions = new ArrayList<Instruction>(); 362 private final HashMap<String, Instruction> mLabels = new HashMap<String, Instruction>(); 363 private final Instruction mDropLabel = new Instruction(Opcodes.LABEL); 364 private final Instruction mPassLabel = new Instruction(Opcodes.LABEL); 365 private final int mVersion; 366 private boolean mGenerated; 367 368 /** 369 * Creates an ApfGenerator instance which is able to emit instructions for the specified 370 * {@code version} of the APF interpreter. Throws {@code IllegalInstructionException} if 371 * the requested version is unsupported. 372 */ 373 @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE) ApfGenerator(int version)374 public ApfGenerator(int version) throws IllegalInstructionException { 375 mVersion = version; 376 requireApfVersion(MIN_APF_VERSION); 377 } 378 379 /** 380 * Returns true if the ApfGenerator supports the specified {@code version}, otherwise false. 381 */ supportsVersion(int version)382 public static boolean supportsVersion(int version) { 383 return version >= MIN_APF_VERSION; 384 } 385 requireApfVersion(int minimumVersion)386 private void requireApfVersion(int minimumVersion) throws IllegalInstructionException { 387 if (mVersion < minimumVersion) { 388 throw new IllegalInstructionException("Requires APF >= " + minimumVersion); 389 } 390 } 391 addInstruction(Instruction instruction)392 private void addInstruction(Instruction instruction) { 393 if (mGenerated) { 394 throw new IllegalStateException("Program already generated"); 395 } 396 mInstructions.add(instruction); 397 } 398 399 /** 400 * Define a label at the current end of the program. Jumps can jump to this label. Labels are 401 * their own separate instructions, though with size 0. This facilitates having labels with 402 * no corresponding code to execute, for example a label at the end of a program. For example 403 * an {@link ApfGenerator} might be passed to a function that adds a filter like so: 404 * <pre> 405 * load from packet 406 * compare loaded data, jump if not equal to "next_filter" 407 * load from packet 408 * compare loaded data, jump if not equal to "next_filter" 409 * jump to drop label 410 * define "next_filter" here 411 * </pre> 412 * In this case "next_filter" may not have any generated code associated with it. 413 */ defineLabel(String name)414 public ApfGenerator defineLabel(String name) throws IllegalInstructionException { 415 Instruction instruction = new Instruction(Opcodes.LABEL); 416 instruction.setLabel(name); 417 addInstruction(instruction); 418 return this; 419 } 420 421 /** 422 * Add an unconditional jump instruction to the end of the program. 423 */ addJump(String target)424 public ApfGenerator addJump(String target) { 425 Instruction instruction = new Instruction(Opcodes.JMP); 426 instruction.setTargetLabel(target); 427 addInstruction(instruction); 428 return this; 429 } 430 431 /** 432 * Add an instruction to the end of the program to load the byte at offset {@code offset} 433 * bytes from the beginning of the packet into {@code register}. 434 */ addLoad8(Register register, int offset)435 public ApfGenerator addLoad8(Register register, int offset) { 436 Instruction instruction = new Instruction(Opcodes.LDB, register); 437 instruction.setUnsignedImm(offset); 438 addInstruction(instruction); 439 return this; 440 } 441 442 /** 443 * Add an instruction to the end of the program to load 16-bits at offset {@code offset} 444 * bytes from the beginning of the packet into {@code register}. 445 */ addLoad16(Register register, int offset)446 public ApfGenerator addLoad16(Register register, int offset) { 447 Instruction instruction = new Instruction(Opcodes.LDH, register); 448 instruction.setUnsignedImm(offset); 449 addInstruction(instruction); 450 return this; 451 } 452 453 /** 454 * Add an instruction to the end of the program to load 32-bits at offset {@code offset} 455 * bytes from the beginning of the packet into {@code register}. 456 */ addLoad32(Register register, int offset)457 public ApfGenerator addLoad32(Register register, int offset) { 458 Instruction instruction = new Instruction(Opcodes.LDW, register); 459 instruction.setUnsignedImm(offset); 460 addInstruction(instruction); 461 return this; 462 } 463 464 /** 465 * Add an instruction to the end of the program to load a byte from the packet into 466 * {@code register}. The offset of the loaded byte from the beginning of the packet is 467 * the sum of {@code offset} and the value in register R1. 468 */ addLoad8Indexed(Register register, int offset)469 public ApfGenerator addLoad8Indexed(Register register, int offset) { 470 Instruction instruction = new Instruction(Opcodes.LDBX, register); 471 instruction.setUnsignedImm(offset); 472 addInstruction(instruction); 473 return this; 474 } 475 476 /** 477 * Add an instruction to the end of the program to load 16-bits from the packet into 478 * {@code register}. The offset of the loaded 16-bits from the beginning of the packet is 479 * the sum of {@code offset} and the value in register R1. 480 */ addLoad16Indexed(Register register, int offset)481 public ApfGenerator addLoad16Indexed(Register register, int offset) { 482 Instruction instruction = new Instruction(Opcodes.LDHX, register); 483 instruction.setUnsignedImm(offset); 484 addInstruction(instruction); 485 return this; 486 } 487 488 /** 489 * Add an instruction to the end of the program to load 32-bits from the packet into 490 * {@code register}. The offset of the loaded 32-bits from the beginning of the packet is 491 * the sum of {@code offset} and the value in register R1. 492 */ addLoad32Indexed(Register register, int offset)493 public ApfGenerator addLoad32Indexed(Register register, int offset) { 494 Instruction instruction = new Instruction(Opcodes.LDWX, register); 495 instruction.setUnsignedImm(offset); 496 addInstruction(instruction); 497 return this; 498 } 499 500 /** 501 * Add an instruction to the end of the program to add {@code value} to register R0. 502 */ addAdd(int value)503 public ApfGenerator addAdd(int value) { 504 Instruction instruction = new Instruction(Opcodes.ADD); 505 instruction.setSignedImm(value); 506 addInstruction(instruction); 507 return this; 508 } 509 510 /** 511 * Add an instruction to the end of the program to multiply register R0 by {@code value}. 512 */ addMul(int value)513 public ApfGenerator addMul(int value) { 514 Instruction instruction = new Instruction(Opcodes.MUL); 515 instruction.setSignedImm(value); 516 addInstruction(instruction); 517 return this; 518 } 519 520 /** 521 * Add an instruction to the end of the program to divide register R0 by {@code value}. 522 */ addDiv(int value)523 public ApfGenerator addDiv(int value) { 524 Instruction instruction = new Instruction(Opcodes.DIV); 525 instruction.setSignedImm(value); 526 addInstruction(instruction); 527 return this; 528 } 529 530 /** 531 * Add an instruction to the end of the program to logically and register R0 with {@code value}. 532 */ addAnd(int value)533 public ApfGenerator addAnd(int value) { 534 Instruction instruction = new Instruction(Opcodes.AND); 535 instruction.setUnsignedImm(value); 536 addInstruction(instruction); 537 return this; 538 } 539 540 /** 541 * Add an instruction to the end of the program to logically or register R0 with {@code value}. 542 */ addOr(int value)543 public ApfGenerator addOr(int value) { 544 Instruction instruction = new Instruction(Opcodes.OR); 545 instruction.setUnsignedImm(value); 546 addInstruction(instruction); 547 return this; 548 } 549 550 /** 551 * Add an instruction to the end of the program to shift left register R0 by {@code value} bits. 552 */ addLeftShift(int value)553 public ApfGenerator addLeftShift(int value) { 554 Instruction instruction = new Instruction(Opcodes.SH); 555 instruction.setSignedImm(value); 556 addInstruction(instruction); 557 return this; 558 } 559 560 /** 561 * Add an instruction to the end of the program to shift right register R0 by {@code value} 562 * bits. 563 */ addRightShift(int value)564 public ApfGenerator addRightShift(int value) { 565 Instruction instruction = new Instruction(Opcodes.SH); 566 instruction.setSignedImm(-value); 567 addInstruction(instruction); 568 return this; 569 } 570 571 /** 572 * Add an instruction to the end of the program to add register R1 to register R0. 573 */ addAddR1()574 public ApfGenerator addAddR1() { 575 Instruction instruction = new Instruction(Opcodes.ADD, Register.R1); 576 addInstruction(instruction); 577 return this; 578 } 579 580 /** 581 * Add an instruction to the end of the program to multiply register R0 by register R1. 582 */ addMulR1()583 public ApfGenerator addMulR1() { 584 Instruction instruction = new Instruction(Opcodes.MUL, Register.R1); 585 addInstruction(instruction); 586 return this; 587 } 588 589 /** 590 * Add an instruction to the end of the program to divide register R0 by register R1. 591 */ addDivR1()592 public ApfGenerator addDivR1() { 593 Instruction instruction = new Instruction(Opcodes.DIV, Register.R1); 594 addInstruction(instruction); 595 return this; 596 } 597 598 /** 599 * Add an instruction to the end of the program to logically and register R0 with register R1 600 * and store the result back into register R0. 601 */ addAndR1()602 public ApfGenerator addAndR1() { 603 Instruction instruction = new Instruction(Opcodes.AND, Register.R1); 604 addInstruction(instruction); 605 return this; 606 } 607 608 /** 609 * Add an instruction to the end of the program to logically or register R0 with register R1 610 * and store the result back into register R0. 611 */ addOrR1()612 public ApfGenerator addOrR1() { 613 Instruction instruction = new Instruction(Opcodes.OR, Register.R1); 614 addInstruction(instruction); 615 return this; 616 } 617 618 /** 619 * Add an instruction to the end of the program to shift register R0 left by the value in 620 * register R1. 621 */ addLeftShiftR1()622 public ApfGenerator addLeftShiftR1() { 623 Instruction instruction = new Instruction(Opcodes.SH, Register.R1); 624 addInstruction(instruction); 625 return this; 626 } 627 628 /** 629 * Add an instruction to the end of the program to move {@code value} into {@code register}. 630 */ addLoadImmediate(Register register, int value)631 public ApfGenerator addLoadImmediate(Register register, int value) { 632 Instruction instruction = new Instruction(Opcodes.LI, register); 633 instruction.setSignedImm(value); 634 addInstruction(instruction); 635 return this; 636 } 637 638 /** 639 * Add an instruction to the end of the program to jump to {@code target} if register R0's 640 * value equals {@code value}. 641 */ addJumpIfR0Equals(int value, String target)642 public ApfGenerator addJumpIfR0Equals(int value, String target) { 643 Instruction instruction = new Instruction(Opcodes.JEQ); 644 instruction.setUnsignedImm(value); 645 instruction.setTargetLabel(target); 646 addInstruction(instruction); 647 return this; 648 } 649 650 /** 651 * Add an instruction to the end of the program to jump to {@code target} if register R0's 652 * value does not equal {@code value}. 653 */ addJumpIfR0NotEquals(int value, String target)654 public ApfGenerator addJumpIfR0NotEquals(int value, String target) { 655 Instruction instruction = new Instruction(Opcodes.JNE); 656 instruction.setUnsignedImm(value); 657 instruction.setTargetLabel(target); 658 addInstruction(instruction); 659 return this; 660 } 661 662 /** 663 * Add an instruction to the end of the program to jump to {@code target} if register R0's 664 * value is greater than {@code value}. 665 */ addJumpIfR0GreaterThan(int value, String target)666 public ApfGenerator addJumpIfR0GreaterThan(int value, String target) { 667 Instruction instruction = new Instruction(Opcodes.JGT); 668 instruction.setUnsignedImm(value); 669 instruction.setTargetLabel(target); 670 addInstruction(instruction); 671 return this; 672 } 673 674 /** 675 * Add an instruction to the end of the program to jump to {@code target} if register R0's 676 * value is less than {@code value}. 677 */ addJumpIfR0LessThan(int value, String target)678 public ApfGenerator addJumpIfR0LessThan(int value, String target) { 679 Instruction instruction = new Instruction(Opcodes.JLT); 680 instruction.setUnsignedImm(value); 681 instruction.setTargetLabel(target); 682 addInstruction(instruction); 683 return this; 684 } 685 686 /** 687 * Add an instruction to the end of the program to jump to {@code target} if register R0's 688 * value has any bits set that are also set in {@code value}. 689 */ addJumpIfR0AnyBitsSet(int value, String target)690 public ApfGenerator addJumpIfR0AnyBitsSet(int value, String target) { 691 Instruction instruction = new Instruction(Opcodes.JSET); 692 instruction.setUnsignedImm(value); 693 instruction.setTargetLabel(target); 694 addInstruction(instruction); 695 return this; 696 } 697 /** 698 * Add an instruction to the end of the program to jump to {@code target} if register R0's 699 * value equals register R1's value. 700 */ addJumpIfR0EqualsR1(String target)701 public ApfGenerator addJumpIfR0EqualsR1(String target) { 702 Instruction instruction = new Instruction(Opcodes.JEQ, Register.R1); 703 instruction.setTargetLabel(target); 704 addInstruction(instruction); 705 return this; 706 } 707 708 /** 709 * Add an instruction to the end of the program to jump to {@code target} if register R0's 710 * value does not equal register R1's value. 711 */ addJumpIfR0NotEqualsR1(String target)712 public ApfGenerator addJumpIfR0NotEqualsR1(String target) { 713 Instruction instruction = new Instruction(Opcodes.JNE, Register.R1); 714 instruction.setTargetLabel(target); 715 addInstruction(instruction); 716 return this; 717 } 718 719 /** 720 * Add an instruction to the end of the program to jump to {@code target} if register R0's 721 * value is greater than register R1's value. 722 */ addJumpIfR0GreaterThanR1(String target)723 public ApfGenerator addJumpIfR0GreaterThanR1(String target) { 724 Instruction instruction = new Instruction(Opcodes.JGT, Register.R1); 725 instruction.setTargetLabel(target); 726 addInstruction(instruction); 727 return this; 728 } 729 730 /** 731 * Add an instruction to the end of the program to jump to {@code target} if register R0's 732 * value is less than register R1's value. 733 */ addJumpIfR0LessThanR1(String target)734 public ApfGenerator addJumpIfR0LessThanR1(String target) { 735 Instruction instruction = new Instruction(Opcodes.JLT, Register.R1); 736 instruction.setTargetLabel(target); 737 addInstruction(instruction); 738 return this; 739 } 740 741 /** 742 * Add an instruction to the end of the program to jump to {@code target} if register R0's 743 * value has any bits set that are also set in R1's value. 744 */ addJumpIfR0AnyBitsSetR1(String target)745 public ApfGenerator addJumpIfR0AnyBitsSetR1(String target) { 746 Instruction instruction = new Instruction(Opcodes.JSET, Register.R1); 747 instruction.setTargetLabel(target); 748 addInstruction(instruction); 749 return this; 750 } 751 752 /** 753 * Add an instruction to the end of the program to jump to {@code target} if the bytes of the 754 * packet at an offset specified by {@code register} don't match {@code bytes}, {@code register} 755 * must be R0. 756 */ addJumpIfBytesNotEqual(Register register, byte[] bytes, String target)757 public ApfGenerator addJumpIfBytesNotEqual(Register register, byte[] bytes, String target) 758 throws IllegalInstructionException { 759 if (register == Register.R1) { 760 throw new IllegalInstructionException("JNEBS fails with R1"); 761 } 762 Instruction instruction = new Instruction(Opcodes.JNEBS, register); 763 instruction.setUnsignedImm(bytes.length); 764 instruction.setTargetLabel(target); 765 instruction.setCompareBytes(bytes); 766 addInstruction(instruction); 767 return this; 768 } 769 770 /** 771 * Add an instruction to the end of the program to load memory slot {@code slot} into 772 * {@code register}. 773 */ addLoadFromMemory(Register register, int slot)774 public ApfGenerator addLoadFromMemory(Register register, int slot) 775 throws IllegalInstructionException { 776 if (slot < 0 || slot > (MEMORY_SLOTS - 1)) { 777 throw new IllegalInstructionException("illegal memory slot number: " + slot); 778 } 779 Instruction instruction = new Instruction(Opcodes.EXT, register); 780 instruction.setUnsignedImm(ExtendedOpcodes.LDM.value + slot); 781 addInstruction(instruction); 782 return this; 783 } 784 785 /** 786 * Add an instruction to the end of the program to store {@code register} into memory slot 787 * {@code slot}. 788 */ addStoreToMemory(Register register, int slot)789 public ApfGenerator addStoreToMemory(Register register, int slot) 790 throws IllegalInstructionException { 791 if (slot < 0 || slot > (MEMORY_SLOTS - 1)) { 792 throw new IllegalInstructionException("illegal memory slot number: " + slot); 793 } 794 Instruction instruction = new Instruction(Opcodes.EXT, register); 795 instruction.setUnsignedImm(ExtendedOpcodes.STM.value + slot); 796 addInstruction(instruction); 797 return this; 798 } 799 800 /** 801 * Add an instruction to the end of the program to logically not {@code register}. 802 */ addNot(Register register)803 public ApfGenerator addNot(Register register) { 804 Instruction instruction = new Instruction(Opcodes.EXT, register); 805 instruction.setUnsignedImm(ExtendedOpcodes.NOT.value); 806 addInstruction(instruction); 807 return this; 808 } 809 810 /** 811 * Add an instruction to the end of the program to negate {@code register}. 812 */ addNeg(Register register)813 public ApfGenerator addNeg(Register register) { 814 Instruction instruction = new Instruction(Opcodes.EXT, register); 815 instruction.setUnsignedImm(ExtendedOpcodes.NEG.value); 816 addInstruction(instruction); 817 return this; 818 } 819 820 /** 821 * Add an instruction to swap the values in register R0 and register R1. 822 */ addSwap()823 public ApfGenerator addSwap() { 824 Instruction instruction = new Instruction(Opcodes.EXT); 825 instruction.setUnsignedImm(ExtendedOpcodes.SWAP.value); 826 addInstruction(instruction); 827 return this; 828 } 829 830 /** 831 * Add an instruction to the end of the program to move the value into 832 * {@code register} from the other register. 833 */ addMove(Register register)834 public ApfGenerator addMove(Register register) { 835 Instruction instruction = new Instruction(Opcodes.EXT, register); 836 instruction.setUnsignedImm(ExtendedOpcodes.MOVE.value); 837 addInstruction(instruction); 838 return this; 839 } 840 841 /** 842 * Add an instruction to the end of the program to load 32 bits from the data memory into 843 * {@code register}. The source address is computed by adding the signed immediate 844 * @{code offset} to the other register. 845 * Requires APF v3 or greater. 846 */ addLoadData(Register destinationRegister, int offset)847 public ApfGenerator addLoadData(Register destinationRegister, int offset) 848 throws IllegalInstructionException { 849 requireApfVersion(3); 850 Instruction instruction = new Instruction(Opcodes.LDDW, destinationRegister); 851 instruction.setSignedImm(offset); 852 addInstruction(instruction); 853 return this; 854 } 855 856 /** 857 * Add an instruction to the end of the program to store 32 bits from {@code register} into the 858 * data memory. The destination address is computed by adding the signed immediate 859 * @{code offset} to the other register. 860 * Requires APF v3 or greater. 861 */ addStoreData(Register sourceRegister, int offset)862 public ApfGenerator addStoreData(Register sourceRegister, int offset) 863 throws IllegalInstructionException { 864 requireApfVersion(3); 865 Instruction instruction = new Instruction(Opcodes.STDW, sourceRegister); 866 instruction.setSignedImm(offset); 867 addInstruction(instruction); 868 return this; 869 } 870 871 /** 872 * Updates instruction offset fields using latest instruction sizes. 873 * @return current program length in bytes. 874 */ updateInstructionOffsets()875 private int updateInstructionOffsets() { 876 int offset = 0; 877 for (Instruction instruction : mInstructions) { 878 instruction.offset = offset; 879 offset += instruction.size(); 880 } 881 return offset; 882 } 883 884 /** 885 * Returns an overestimate of the size of the generated program. {@link #generate} may return 886 * a program that is smaller. 887 */ programLengthOverEstimate()888 public int programLengthOverEstimate() { 889 return updateInstructionOffsets(); 890 } 891 892 /** 893 * Generate the bytecode for the APF program. 894 * @return the bytecode. 895 * @throws IllegalStateException if a label is referenced but not defined. 896 */ generate()897 public byte[] generate() throws IllegalInstructionException { 898 // Enforce that we can only generate once because we cannot unshrink instructions and 899 // PASS/DROP labels may move further away requiring unshrinking if we add further 900 // instructions. 901 if (mGenerated) { 902 throw new IllegalStateException("Can only generate() once!"); 903 } 904 mGenerated = true; 905 int total_size; 906 boolean shrunk; 907 // Shrink the immediate value fields of instructions. 908 // As we shrink the instructions some branch offset 909 // fields may shrink also, thereby shrinking the 910 // instructions further. Loop until we've reached the 911 // minimum size. Rarely will this loop more than a few times. 912 // Limit iterations to avoid O(n^2) behavior. 913 int iterations_remaining = 10; 914 do { 915 total_size = updateInstructionOffsets(); 916 // Update drop and pass label offsets. 917 mDropLabel.offset = total_size + 1; 918 mPassLabel.offset = total_size; 919 // Limit run-time in aberant circumstances. 920 if (iterations_remaining-- == 0) break; 921 // Attempt to shrink instructions. 922 shrunk = false; 923 for (Instruction instruction : mInstructions) { 924 if (instruction.shrink()) { 925 shrunk = true; 926 } 927 } 928 } while (shrunk); 929 // Generate bytecode for instructions. 930 byte[] bytecode = new byte[total_size]; 931 for (Instruction instruction : mInstructions) { 932 instruction.generate(bytecode); 933 } 934 return bytecode; 935 } 936 } 937 938