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 {
IllegalInstructionException(String msg)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 
Opcodes(int value)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 
ExtendedOpcodes(int value)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 
Register(int value)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 beginning of this program. Set by {@link ApfGenerator#generate}.
112         int offset;
113 
Instruction(Opcodes opcode, Register register)114         Instruction(Opcodes opcode, Register register) {
115             mOpcode = (byte)opcode.value;
116             mRegister = (byte)register.value;
117         }
118 
Instruction(Opcodes opcode)119         Instruction(Opcodes opcode) {
120             this(opcode, Register.R0);
121         }
122 
setImm(int imm, boolean signed)123         void setImm(int imm, boolean signed) {
124             mHasImm = true;
125             mImm = imm;
126             mImmSigned = signed;
127             mImmSize = calculateImmSize(imm, signed);
128         }
129 
setUnsignedImm(int imm)130         void setUnsignedImm(int imm) {
131             setImm(imm, false);
132         }
133 
setSignedImm(int imm)134         void setSignedImm(int imm) {
135             setImm(imm, true);
136         }
137 
setLabel(String label)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 
setTargetLabel(String label)149         void setTargetLabel(String label) {
150             mTargetLabel = label;
151             mTargetLabelSize = 4; // May shrink later on in generate().
152         }
153 
setCompareBytes(byte[] bytes)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          */
size()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          */
shrink()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          */
generateImmSizeField()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          */
generateInstructionByte()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          */
writeValue(int value, byte[] bytecode, int writingOffset)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          */
generate(byte[] bytecode)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          */
generatedImmSize()265         private byte generatedImmSize() {
266             return mImmSize > mTargetLabelSize ? mImmSize : mTargetLabelSize;
267         }
268 
calculateTargetLabelOffset()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 
calculateImmSize(int imm, boolean signed)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      */
ApfGenerator(int version)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      */
supportsVersion(int version)383     public static boolean supportsVersion(int version) {
384         return version >= MIN_APF_VERSION;
385     }
386 
requireApfVersion(int minimumVersion)387     private void requireApfVersion(int minimumVersion) throws IllegalInstructionException {
388         if (mVersion < minimumVersion) {
389             throw new IllegalInstructionException("Requires APF >= " + minimumVersion);
390         }
391     }
392 
addInstruction(Instruction instruction)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      */
defineLabel(String name)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      */
addJump(String target)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 beginning of the packet into {@code register}.
435      */
addLoad8(Register register, int offset)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 beginning of the packet into {@code register}.
446      */
addLoad16(Register register, int offset)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 beginning of the packet into {@code register}.
457      */
addLoad32(Register register, int offset)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 beginning of the packet is
468      * the sum of {@code offset} and the value in register R1.
469      */
addLoad8Indexed(Register register, int offset)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 beginning of the packet is
480      * the sum of {@code offset} and the value in register R1.
481      */
addLoad16Indexed(Register register, int offset)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 beginning of the packet is
492      * the sum of {@code offset} and the value in register R1.
493      */
addLoad32Indexed(Register register, int offset)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      */
addAdd(int value)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      */
addMul(int value)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      */
addDiv(int value)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      */
addAnd(int value)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      */
addOr(int value)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      */
addLeftShift(int value)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      */
addRightShift(int value)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      */
addAddR1()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      */
addMulR1()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      */
addDivR1()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      */
addAndR1()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      */
addOrR1()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      */
addLeftShiftR1()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      */
addLoadImmediate(Register register, int value)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      */
addJumpIfR0Equals(int value, String target)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      */
addJumpIfR0NotEquals(int value, String target)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      */
addJumpIfR0GreaterThan(int value, String target)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      */
addJumpIfR0LessThan(int value, String target)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      */
addJumpIfR0AnyBitsSet(int value, String target)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      */
addJumpIfR0EqualsR1(String target)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      */
addJumpIfR0NotEqualsR1(String target)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      */
addJumpIfR0GreaterThanR1(String target)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      */
addJumpIfR0LessThanR1(String target)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      */
addJumpIfR0AnyBitsSetR1(String target)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      */
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