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 java.util.ArrayList; 20 import java.util.HashMap; 21 22 /** 23 * APF assembler/generator. A tool for generating an APF program. 24 * 25 * Call add*() functions to add instructions to the program, then call 26 * {@link generate} to get the APF bytecode for the program. 27 * 28 * @hide 29 */ 30 public class ApfGenerator { 31 /** 32 * This exception is thrown when an attempt is made to generate an illegal instruction. 33 */ 34 public static class IllegalInstructionException extends Exception { 35 IllegalInstructionException(String msg) { 36 super(msg); 37 } 38 } 39 private enum Opcodes { 40 LABEL(-1), 41 LDB(1), // Load 1 byte from immediate offset, e.g. "ldb R0, [5]" 42 LDH(2), // Load 2 bytes from immediate offset, e.g. "ldh R0, [5]" 43 LDW(3), // Load 4 bytes from immediate offset, e.g. "ldw R0, [5]" 44 LDBX(4), // Load 1 byte from immediate offset plus register, e.g. "ldbx R0, [5]R0" 45 LDHX(5), // Load 2 byte from immediate offset plus register, e.g. "ldhx R0, [5]R0" 46 LDWX(6), // Load 4 byte from immediate offset plus register, e.g. "ldwx R0, [5]R0" 47 ADD(7), // Add, e.g. "add R0,5" 48 MUL(8), // Multiply, e.g. "mul R0,5" 49 DIV(9), // Divide, e.g. "div R0,5" 50 AND(10), // And, e.g. "and R0,5" 51 OR(11), // Or, e.g. "or R0,5" 52 SH(12), // Left shift, e.g, "sh R0, 5" or "sh R0, -5" (shifts right) 53 LI(13), // Load immediate, e.g. "li R0,5" (immediate encoded as signed value) 54 JMP(14), // Jump, e.g. "jmp label" 55 JEQ(15), // Compare equal and branch, e.g. "jeq R0,5,label" 56 JNE(16), // Compare not equal and branch, e.g. "jne R0,5,label" 57 JGT(17), // Compare greater than and branch, e.g. "jgt R0,5,label" 58 JLT(18), // Compare less than and branch, e.g. "jlt R0,5,label" 59 JSET(19), // Compare any bits set and branch, e.g. "jset R0,5,label" 60 JNEBS(20), // Compare not equal byte sequence, e.g. "jnebs R0,5,label,0x1122334455" 61 EXT(21), // Followed by immediate indicating ExtendedOpcodes. 62 LDDW(22), // Load 4 bytes from data memory address (register + immediate): "lddw R0, [5]R1" 63 STDW(23); // Store 4 bytes to data memory address (register + immediate): "stdw R0, [5]R1" 64 65 final int value; 66 67 private Opcodes(int value) { 68 this.value = value; 69 } 70 } 71 // Extended opcodes. Primary opcode is Opcodes.EXT. ExtendedOpcodes are encoded in the immediate 72 // field. 73 private enum ExtendedOpcodes { 74 LDM(0), // Load from memory, e.g. "ldm R0,5" 75 STM(16), // Store to memory, e.g. "stm R0,5" 76 NOT(32), // Not, e.g. "not R0" 77 NEG(33), // Negate, e.g. "neg R0" 78 SWAP(34), // Swap, e.g. "swap R0,R1" 79 MOVE(35); // Move, e.g. "move R0,R1" 80 81 final int value; 82 83 private ExtendedOpcodes(int value) { 84 this.value = value; 85 } 86 } 87 public enum Register { 88 R0(0), 89 R1(1); 90 91 final int value; 92 93 private Register(int value) { 94 this.value = value; 95 } 96 } 97 private class Instruction { 98 private final byte mOpcode; // A "Opcode" value. 99 private final byte mRegister; // A "Register" value. 100 private boolean mHasImm; 101 private byte mImmSize; 102 private boolean mImmSigned; 103 private int mImm; 104 // When mOpcode is a jump: 105 private byte mTargetLabelSize; 106 private String mTargetLabel; 107 // When mOpcode == Opcodes.LABEL: 108 private String mLabel; 109 // When mOpcode == Opcodes.JNEBS: 110 private byte[] mCompareBytes; 111 // Offset in bytes from the begining of this program. Set by {@link ApfGenerator#generate}. 112 int offset; 113 114 Instruction(Opcodes opcode, Register register) { 115 mOpcode = (byte)opcode.value; 116 mRegister = (byte)register.value; 117 } 118 119 Instruction(Opcodes opcode) { 120 this(opcode, Register.R0); 121 } 122 123 void setImm(int imm, boolean signed) { 124 mHasImm = true; 125 mImm = imm; 126 mImmSigned = signed; 127 mImmSize = calculateImmSize(imm, signed); 128 } 129 130 void setUnsignedImm(int imm) { 131 setImm(imm, false); 132 } 133 134 void setSignedImm(int imm) { 135 setImm(imm, true); 136 } 137 138 void setLabel(String label) throws IllegalInstructionException { 139 if (mLabels.containsKey(label)) { 140 throw new IllegalInstructionException("duplicate label " + label); 141 } 142 if (mOpcode != Opcodes.LABEL.value) { 143 throw new IllegalStateException("adding label to non-label instruction"); 144 } 145 mLabel = label; 146 mLabels.put(label, this); 147 } 148 149 void setTargetLabel(String label) { 150 mTargetLabel = label; 151 mTargetLabelSize = 4; // May shrink later on in generate(). 152 } 153 154 void setCompareBytes(byte[] bytes) { 155 if (mOpcode != Opcodes.JNEBS.value) { 156 throw new IllegalStateException("adding compare bytes to non-JNEBS instruction"); 157 } 158 mCompareBytes = bytes; 159 } 160 161 /** 162 * @return size of instruction in bytes. 163 */ 164 int size() { 165 if (mOpcode == Opcodes.LABEL.value) { 166 return 0; 167 } 168 int size = 1; 169 if (mHasImm) { 170 size += generatedImmSize(); 171 } 172 if (mTargetLabel != null) { 173 size += generatedImmSize(); 174 } 175 if (mCompareBytes != null) { 176 size += mCompareBytes.length; 177 } 178 return size; 179 } 180 181 /** 182 * Resize immediate value field so that it's only as big as required to 183 * contain the offset of the jump destination. 184 * @return {@code true} if shrunk. 185 */ 186 boolean shrink() throws IllegalInstructionException { 187 if (mTargetLabel == null) { 188 return false; 189 } 190 int oldSize = size(); 191 int oldTargetLabelSize = mTargetLabelSize; 192 mTargetLabelSize = calculateImmSize(calculateTargetLabelOffset(), false); 193 if (mTargetLabelSize > oldTargetLabelSize) { 194 throw new IllegalStateException("instruction grew"); 195 } 196 return size() < oldSize; 197 } 198 199 /** 200 * Assemble value for instruction size field. 201 */ 202 private byte generateImmSizeField() { 203 byte immSize = generatedImmSize(); 204 // Encode size field to fit in 2 bits: 0->0, 1->1, 2->2, 3->4. 205 return immSize == 4 ? 3 : immSize; 206 } 207 208 /** 209 * Assemble first byte of generated instruction. 210 */ 211 private byte generateInstructionByte() { 212 byte sizeField = generateImmSizeField(); 213 return (byte)((mOpcode << 3) | (sizeField << 1) | mRegister); 214 } 215 216 /** 217 * Write {@code value} at offset {@code writingOffset} into {@code bytecode}. 218 * {@link generatedImmSize} bytes are written. {@code value} is truncated to 219 * {@code generatedImmSize} bytes. {@code value} is treated simply as a 220 * 32-bit value, so unsigned values should be zero extended and the truncation 221 * should simply throw away their zero-ed upper bits, and signed values should 222 * be sign extended and the truncation should simply throw away their signed 223 * upper bits. 224 */ 225 private int writeValue(int value, byte[] bytecode, int writingOffset) { 226 for (int i = generatedImmSize() - 1; i >= 0; i--) { 227 bytecode[writingOffset++] = (byte)((value >> (i * 8)) & 255); 228 } 229 return writingOffset; 230 } 231 232 /** 233 * Generate bytecode for this instruction at offset {@link offset}. 234 */ 235 void generate(byte[] bytecode) throws IllegalInstructionException { 236 if (mOpcode == Opcodes.LABEL.value) { 237 return; 238 } 239 int writingOffset = offset; 240 bytecode[writingOffset++] = generateInstructionByte(); 241 if (mTargetLabel != null) { 242 writingOffset = writeValue(calculateTargetLabelOffset(), bytecode, writingOffset); 243 } 244 if (mHasImm) { 245 writingOffset = writeValue(mImm, bytecode, writingOffset); 246 } 247 if (mCompareBytes != null) { 248 System.arraycopy(mCompareBytes, 0, bytecode, writingOffset, mCompareBytes.length); 249 writingOffset += mCompareBytes.length; 250 } 251 if ((writingOffset - offset) != size()) { 252 throw new IllegalStateException("wrote " + (writingOffset - offset) + 253 " but should have written " + size()); 254 } 255 } 256 257 /** 258 * Calculate the size of either the immediate field or the target label field, if either is 259 * present. Most instructions have either an immediate or a target label field, but for the 260 * instructions that have both, the size of the target label field must be the same as the 261 * size of the immediate field, because there is only one length field in the instruction 262 * byte, hence why this function simply takes the maximum of the two sizes, so neither is 263 * truncated. 264 */ 265 private byte generatedImmSize() { 266 return mImmSize > mTargetLabelSize ? mImmSize : mTargetLabelSize; 267 } 268 269 private int calculateTargetLabelOffset() throws IllegalInstructionException { 270 Instruction targetLabelInstruction; 271 if (mTargetLabel == DROP_LABEL) { 272 targetLabelInstruction = mDropLabel; 273 } else if (mTargetLabel == PASS_LABEL) { 274 targetLabelInstruction = mPassLabel; 275 } else { 276 targetLabelInstruction = mLabels.get(mTargetLabel); 277 } 278 if (targetLabelInstruction == null) { 279 throw new IllegalInstructionException("label not found: " + mTargetLabel); 280 } 281 // Calculate distance from end of this instruction to instruction.offset. 282 final int targetLabelOffset = targetLabelInstruction.offset - (offset + size()); 283 if (targetLabelOffset < 0) { 284 throw new IllegalInstructionException("backward branches disallowed; label: " + 285 mTargetLabel); 286 } 287 return targetLabelOffset; 288 } 289 290 private byte calculateImmSize(int imm, boolean signed) { 291 if (imm == 0) { 292 return 0; 293 } 294 if (signed && (imm >= -128 && imm <= 127) || 295 !signed && (imm >= 0 && imm <= 255)) { 296 return 1; 297 } 298 if (signed && (imm >= -32768 && imm <= 32767) || 299 !signed && (imm >= 0 && imm <= 65535)) { 300 return 2; 301 } 302 return 4; 303 } 304 } 305 306 /** 307 * Jump to this label to terminate the program and indicate the packet 308 * should be dropped. 309 */ 310 public static final String DROP_LABEL = "__DROP__"; 311 312 /** 313 * Jump to this label to terminate the program and indicate the packet 314 * should be passed to the AP. 315 */ 316 public static final String PASS_LABEL = "__PASS__"; 317 318 /** 319 * Number of memory slots available for access via APF stores to memory and loads from memory. 320 * The memory slots are numbered 0 to {@code MEMORY_SLOTS} - 1. This must be kept in sync with 321 * the APF interpreter. 322 */ 323 public static final int MEMORY_SLOTS = 16; 324 325 /** 326 * Memory slot number that is prefilled with the IPv4 header length. 327 * Note that this memory slot may be overwritten by a program that 328 * executes stores to this memory slot. This must be kept in sync with 329 * the APF interpreter. 330 */ 331 public static final int IPV4_HEADER_SIZE_MEMORY_SLOT = 13; 332 333 /** 334 * Memory slot number that is prefilled with the size of the packet being filtered in bytes. 335 * Note that this memory slot may be overwritten by a program that 336 * executes stores to this memory slot. This must be kept in sync with the APF interpreter. 337 */ 338 public static final int PACKET_SIZE_MEMORY_SLOT = 14; 339 340 /** 341 * Memory slot number that is prefilled with the age of the filter in seconds. The age of the 342 * filter is the time since the filter was installed until now. 343 * Note that this memory slot may be overwritten by a program that 344 * executes stores to this memory slot. This must be kept in sync with the APF interpreter. 345 */ 346 public static final int FILTER_AGE_MEMORY_SLOT = 15; 347 348 /** 349 * First memory slot containing prefilled values. Can be used in range comparisons to determine 350 * if memory slot index is within prefilled slots. 351 */ 352 public static final int FIRST_PREFILLED_MEMORY_SLOT = IPV4_HEADER_SIZE_MEMORY_SLOT; 353 354 /** 355 * Last memory slot containing prefilled values. Can be used in range comparisons to determine 356 * if memory slot index is within prefilled slots. 357 */ 358 public static final int LAST_PREFILLED_MEMORY_SLOT = FILTER_AGE_MEMORY_SLOT; 359 360 // This version number syncs up with APF_VERSION in hardware/google/apf/apf_interpreter.h 361 private static final int MIN_APF_VERSION = 2; 362 363 private final ArrayList<Instruction> mInstructions = new ArrayList<Instruction>(); 364 private final HashMap<String, Instruction> mLabels = new HashMap<String, Instruction>(); 365 private final Instruction mDropLabel = new Instruction(Opcodes.LABEL); 366 private final Instruction mPassLabel = new Instruction(Opcodes.LABEL); 367 private final int mVersion; 368 private boolean mGenerated; 369 370 /** 371 * Creates an ApfGenerator instance which is able to emit instructions for the specified 372 * {@code version} of the APF interpreter. Throws {@code IllegalInstructionException} if 373 * the requested version is unsupported. 374 */ 375 ApfGenerator(int version) throws IllegalInstructionException { 376 mVersion = version; 377 requireApfVersion(MIN_APF_VERSION); 378 } 379 380 /** 381 * Returns true if the ApfGenerator supports the specified {@code version}, otherwise false. 382 */ 383 public static boolean supportsVersion(int version) { 384 return version >= MIN_APF_VERSION; 385 } 386 387 private void requireApfVersion(int minimumVersion) throws IllegalInstructionException { 388 if (mVersion < minimumVersion) { 389 throw new IllegalInstructionException("Requires APF >= " + minimumVersion); 390 } 391 } 392 393 private void addInstruction(Instruction instruction) { 394 if (mGenerated) { 395 throw new IllegalStateException("Program already generated"); 396 } 397 mInstructions.add(instruction); 398 } 399 400 /** 401 * Define a label at the current end of the program. Jumps can jump to this label. Labels are 402 * their own separate instructions, though with size 0. This facilitates having labels with 403 * no corresponding code to execute, for example a label at the end of a program. For example 404 * an {@link ApfGenerator} might be passed to a function that adds a filter like so: 405 * <pre> 406 * load from packet 407 * compare loaded data, jump if not equal to "next_filter" 408 * load from packet 409 * compare loaded data, jump if not equal to "next_filter" 410 * jump to drop label 411 * define "next_filter" here 412 * </pre> 413 * In this case "next_filter" may not have any generated code associated with it. 414 */ 415 public ApfGenerator defineLabel(String name) throws IllegalInstructionException { 416 Instruction instruction = new Instruction(Opcodes.LABEL); 417 instruction.setLabel(name); 418 addInstruction(instruction); 419 return this; 420 } 421 422 /** 423 * Add an unconditional jump instruction to the end of the program. 424 */ 425 public ApfGenerator addJump(String target) { 426 Instruction instruction = new Instruction(Opcodes.JMP); 427 instruction.setTargetLabel(target); 428 addInstruction(instruction); 429 return this; 430 } 431 432 /** 433 * Add an instruction to the end of the program to load the byte at offset {@code offset} 434 * bytes from the begining of the packet into {@code register}. 435 */ 436 public ApfGenerator addLoad8(Register register, int offset) { 437 Instruction instruction = new Instruction(Opcodes.LDB, register); 438 instruction.setUnsignedImm(offset); 439 addInstruction(instruction); 440 return this; 441 } 442 443 /** 444 * Add an instruction to the end of the program to load 16-bits at offset {@code offset} 445 * bytes from the begining of the packet into {@code register}. 446 */ 447 public ApfGenerator addLoad16(Register register, int offset) { 448 Instruction instruction = new Instruction(Opcodes.LDH, register); 449 instruction.setUnsignedImm(offset); 450 addInstruction(instruction); 451 return this; 452 } 453 454 /** 455 * Add an instruction to the end of the program to load 32-bits at offset {@code offset} 456 * bytes from the begining of the packet into {@code register}. 457 */ 458 public ApfGenerator addLoad32(Register register, int offset) { 459 Instruction instruction = new Instruction(Opcodes.LDW, register); 460 instruction.setUnsignedImm(offset); 461 addInstruction(instruction); 462 return this; 463 } 464 465 /** 466 * Add an instruction to the end of the program to load a byte from the packet into 467 * {@code register}. The offset of the loaded byte from the begining of the packet is 468 * the sum of {@code offset} and the value in register R1. 469 */ 470 public ApfGenerator addLoad8Indexed(Register register, int offset) { 471 Instruction instruction = new Instruction(Opcodes.LDBX, register); 472 instruction.setUnsignedImm(offset); 473 addInstruction(instruction); 474 return this; 475 } 476 477 /** 478 * Add an instruction to the end of the program to load 16-bits from the packet into 479 * {@code register}. The offset of the loaded 16-bits from the begining of the packet is 480 * the sum of {@code offset} and the value in register R1. 481 */ 482 public ApfGenerator addLoad16Indexed(Register register, int offset) { 483 Instruction instruction = new Instruction(Opcodes.LDHX, register); 484 instruction.setUnsignedImm(offset); 485 addInstruction(instruction); 486 return this; 487 } 488 489 /** 490 * Add an instruction to the end of the program to load 32-bits from the packet into 491 * {@code register}. The offset of the loaded 32-bits from the begining of the packet is 492 * the sum of {@code offset} and the value in register R1. 493 */ 494 public ApfGenerator addLoad32Indexed(Register register, int offset) { 495 Instruction instruction = new Instruction(Opcodes.LDWX, register); 496 instruction.setUnsignedImm(offset); 497 addInstruction(instruction); 498 return this; 499 } 500 501 /** 502 * Add an instruction to the end of the program to add {@code value} to register R0. 503 */ 504 public ApfGenerator addAdd(int value) { 505 Instruction instruction = new Instruction(Opcodes.ADD); 506 instruction.setSignedImm(value); 507 addInstruction(instruction); 508 return this; 509 } 510 511 /** 512 * Add an instruction to the end of the program to multiply register R0 by {@code value}. 513 */ 514 public ApfGenerator addMul(int value) { 515 Instruction instruction = new Instruction(Opcodes.MUL); 516 instruction.setSignedImm(value); 517 addInstruction(instruction); 518 return this; 519 } 520 521 /** 522 * Add an instruction to the end of the program to divide register R0 by {@code value}. 523 */ 524 public ApfGenerator addDiv(int value) { 525 Instruction instruction = new Instruction(Opcodes.DIV); 526 instruction.setSignedImm(value); 527 addInstruction(instruction); 528 return this; 529 } 530 531 /** 532 * Add an instruction to the end of the program to logically and register R0 with {@code value}. 533 */ 534 public ApfGenerator addAnd(int value) { 535 Instruction instruction = new Instruction(Opcodes.AND); 536 instruction.setUnsignedImm(value); 537 addInstruction(instruction); 538 return this; 539 } 540 541 /** 542 * Add an instruction to the end of the program to logically or register R0 with {@code value}. 543 */ 544 public ApfGenerator addOr(int value) { 545 Instruction instruction = new Instruction(Opcodes.OR); 546 instruction.setUnsignedImm(value); 547 addInstruction(instruction); 548 return this; 549 } 550 551 /** 552 * Add an instruction to the end of the program to shift left register R0 by {@code value} bits. 553 */ 554 public ApfGenerator addLeftShift(int value) { 555 Instruction instruction = new Instruction(Opcodes.SH); 556 instruction.setSignedImm(value); 557 addInstruction(instruction); 558 return this; 559 } 560 561 /** 562 * Add an instruction to the end of the program to shift right register R0 by {@code value} 563 * bits. 564 */ 565 public ApfGenerator addRightShift(int value) { 566 Instruction instruction = new Instruction(Opcodes.SH); 567 instruction.setSignedImm(-value); 568 addInstruction(instruction); 569 return this; 570 } 571 572 /** 573 * Add an instruction to the end of the program to add register R1 to register R0. 574 */ 575 public ApfGenerator addAddR1() { 576 Instruction instruction = new Instruction(Opcodes.ADD, Register.R1); 577 addInstruction(instruction); 578 return this; 579 } 580 581 /** 582 * Add an instruction to the end of the program to multiply register R0 by register R1. 583 */ 584 public ApfGenerator addMulR1() { 585 Instruction instruction = new Instruction(Opcodes.MUL, Register.R1); 586 addInstruction(instruction); 587 return this; 588 } 589 590 /** 591 * Add an instruction to the end of the program to divide register R0 by register R1. 592 */ 593 public ApfGenerator addDivR1() { 594 Instruction instruction = new Instruction(Opcodes.DIV, Register.R1); 595 addInstruction(instruction); 596 return this; 597 } 598 599 /** 600 * Add an instruction to the end of the program to logically and register R0 with register R1 601 * and store the result back into register R0. 602 */ 603 public ApfGenerator addAndR1() { 604 Instruction instruction = new Instruction(Opcodes.AND, Register.R1); 605 addInstruction(instruction); 606 return this; 607 } 608 609 /** 610 * Add an instruction to the end of the program to logically or register R0 with register R1 611 * and store the result back into register R0. 612 */ 613 public ApfGenerator addOrR1() { 614 Instruction instruction = new Instruction(Opcodes.OR, Register.R1); 615 addInstruction(instruction); 616 return this; 617 } 618 619 /** 620 * Add an instruction to the end of the program to shift register R0 left by the value in 621 * register R1. 622 */ 623 public ApfGenerator addLeftShiftR1() { 624 Instruction instruction = new Instruction(Opcodes.SH, Register.R1); 625 addInstruction(instruction); 626 return this; 627 } 628 629 /** 630 * Add an instruction to the end of the program to move {@code value} into {@code register}. 631 */ 632 public ApfGenerator addLoadImmediate(Register register, int value) { 633 Instruction instruction = new Instruction(Opcodes.LI, register); 634 instruction.setSignedImm(value); 635 addInstruction(instruction); 636 return this; 637 } 638 639 /** 640 * Add an instruction to the end of the program to jump to {@code target} if register R0's 641 * value equals {@code value}. 642 */ 643 public ApfGenerator addJumpIfR0Equals(int value, String target) { 644 Instruction instruction = new Instruction(Opcodes.JEQ); 645 instruction.setUnsignedImm(value); 646 instruction.setTargetLabel(target); 647 addInstruction(instruction); 648 return this; 649 } 650 651 /** 652 * Add an instruction to the end of the program to jump to {@code target} if register R0's 653 * value does not equal {@code value}. 654 */ 655 public ApfGenerator addJumpIfR0NotEquals(int value, String target) { 656 Instruction instruction = new Instruction(Opcodes.JNE); 657 instruction.setUnsignedImm(value); 658 instruction.setTargetLabel(target); 659 addInstruction(instruction); 660 return this; 661 } 662 663 /** 664 * Add an instruction to the end of the program to jump to {@code target} if register R0's 665 * value is greater than {@code value}. 666 */ 667 public ApfGenerator addJumpIfR0GreaterThan(int value, String target) { 668 Instruction instruction = new Instruction(Opcodes.JGT); 669 instruction.setUnsignedImm(value); 670 instruction.setTargetLabel(target); 671 addInstruction(instruction); 672 return this; 673 } 674 675 /** 676 * Add an instruction to the end of the program to jump to {@code target} if register R0's 677 * value is less than {@code value}. 678 */ 679 public ApfGenerator addJumpIfR0LessThan(int value, String target) { 680 Instruction instruction = new Instruction(Opcodes.JLT); 681 instruction.setUnsignedImm(value); 682 instruction.setTargetLabel(target); 683 addInstruction(instruction); 684 return this; 685 } 686 687 /** 688 * Add an instruction to the end of the program to jump to {@code target} if register R0's 689 * value has any bits set that are also set in {@code value}. 690 */ 691 public ApfGenerator addJumpIfR0AnyBitsSet(int value, String target) { 692 Instruction instruction = new Instruction(Opcodes.JSET); 693 instruction.setUnsignedImm(value); 694 instruction.setTargetLabel(target); 695 addInstruction(instruction); 696 return this; 697 } 698 /** 699 * Add an instruction to the end of the program to jump to {@code target} if register R0's 700 * value equals register R1's value. 701 */ 702 public ApfGenerator addJumpIfR0EqualsR1(String target) { 703 Instruction instruction = new Instruction(Opcodes.JEQ, Register.R1); 704 instruction.setTargetLabel(target); 705 addInstruction(instruction); 706 return this; 707 } 708 709 /** 710 * Add an instruction to the end of the program to jump to {@code target} if register R0's 711 * value does not equal register R1's value. 712 */ 713 public ApfGenerator addJumpIfR0NotEqualsR1(String target) { 714 Instruction instruction = new Instruction(Opcodes.JNE, Register.R1); 715 instruction.setTargetLabel(target); 716 addInstruction(instruction); 717 return this; 718 } 719 720 /** 721 * Add an instruction to the end of the program to jump to {@code target} if register R0's 722 * value is greater than register R1's value. 723 */ 724 public ApfGenerator addJumpIfR0GreaterThanR1(String target) { 725 Instruction instruction = new Instruction(Opcodes.JGT, Register.R1); 726 instruction.setTargetLabel(target); 727 addInstruction(instruction); 728 return this; 729 } 730 731 /** 732 * Add an instruction to the end of the program to jump to {@code target} if register R0's 733 * value is less than register R1's value. 734 */ 735 public ApfGenerator addJumpIfR0LessThanR1(String target) { 736 Instruction instruction = new Instruction(Opcodes.JLT, Register.R1); 737 instruction.setTargetLabel(target); 738 addInstruction(instruction); 739 return this; 740 } 741 742 /** 743 * Add an instruction to the end of the program to jump to {@code target} if register R0's 744 * value has any bits set that are also set in R1's value. 745 */ 746 public ApfGenerator addJumpIfR0AnyBitsSetR1(String target) { 747 Instruction instruction = new Instruction(Opcodes.JSET, Register.R1); 748 instruction.setTargetLabel(target); 749 addInstruction(instruction); 750 return this; 751 } 752 753 /** 754 * Add an instruction to the end of the program to jump to {@code target} if the bytes of the 755 * packet at an offset specified by {@code register} match {@code bytes}. 756 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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
