Chapter 13: Logical Operations
Logical Operation Instructions are Instructions that compute a result using Binary/Bit operation. Logical Operations are done on a bit-by-bit basis! It's important to understand this. To keep things simple let's just focus on the non-extended registers for this Chapter as handling 64-bits in entirety can be a pain.
Anyway, let's say we have a value in w3 and we preform a logical operation with the value in w27. Bit 0 of w3 will have a logical operation done in reference to bit 0 of w27. Bit 1 of w3 will have an operation done in reference to bit 1 of w27. Bit 2 of w3 will have a logical operation done in reference to bit 3 of w27, and so on and so on.
There are a 6 main types of Logical Operations, they are...
The ARM64 instruction set doesn't include instructions for all 6 main types (example: There is no ARM64 instruction for NAND). Here are the 7 different ARM64 logical operation instructions...
NOTE: Complements will be explained sometime below.
The orr, and, & eor instructions use the following format..
wD, wA, wB
wD, wA, bimm32*
xD, xD, xB
xD, xA, bimm64*
The bic, orn, & eon instructions prohibit Immediate Value usage. Format is as follows..
wD, wA, wB
xD, xA, xB
*For bimm32/64, the Immediate Value is not a standard range, it must follow a simple "string" rule. String meaning a single chain of 1 (high) bits. Any single chain of high-bits can exist...
Example of valid "Stringed" Immediate Values
0xFFFFE000
0x00001800
0x00000001
0x0003F80000000000
0xC00000000000007F
When there are 2 or more high bits in any Immediate Value, they must be consecutive high bits. If there are any low bits in between, the Immediate value cannot be used.
Example of invalid "Stringed" Immediate Values
0xFF700010
0x00011000
0x002FFFFFFFFFFFFF
0xABCD000000000000
Not only that, for Extended register use, you cannot use a 64-bit Immediate value that has *all* high bits (Hex; 0xFFFFFFFFFFFFFFFF). This same concept/rule also applies to non-extended use in regards to 32-bit Immediate Values. The value of 0xFFFFFFFF cannot be used.
We need to cover some basic terminology with Logical Operations.
The term "high" or "true" refers to a bit being the value of 1.
The term "low" or "false" refers to a bit being the value of 0.
The easiest way to understand each Logical Operation is with its corresponding truth table. A truth table is a table/list of the results of all 4 combinations of possible bit operations for a Logical Operation. Each Logical Operation has a unique truth table. They are actually not too hard to remember. You simply need to remember or, and, & xor.
Before we can go over each truth table, we need to understand how bits are "labeled". Fyi, this has nothing to do with branch labels. For example, the leading (far left) bit of any value, regardless of the value's size/length is known as the "Most Significant Bit' or MSB. The trailing (far right) is the "Least Significant" bit aka LSB.
The MSB (for Little Endian CPUs) is always known as bit 31 (far left bit). Moving right, you *decrease* the bit's label number. So the bit to the right of bit 31 is bit 30. Continue left, you hit bit 29, then bit 28, etc etc. In a double-word value, the MSB (far left) is bit 63. In a word value, the MSB is bit 31. LSB (regardless of data/value lenght) is always bit 0 (far right bit). This concept of Bit Labeling (numbers that decrease going from left to right) is only applicable to Little Endian. Big Endian is opposite, fyi.
Confused? Here's a pic of a word value broken up into 32 slots for 32 total bits. Observe how the bit numbering system starts at Bit 31 and ends at Bit 0...
Logical OR (orr)
Truth Table:
| Input | Input | Result |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
With orr, if any of the bits are high, the result is always true.
Scaling up from binary to a hex word value, if w3 has a value of 0x00000001, and w27 has a value of 0x80000001, and these two values are OR'd together, it would produce a result of 0x80000001. Confused by this? let's break it down in binary view...
r3 - 0000 0000 0000 0000 0000 0000 0000 0001
r27 - 1000 0000 0000 0000 0000 0000 0000 0001
Remember Logical Operations are done on a per-bit basis. What occurs is this....
Every bit in the Source Register will have the Logical Operation done with its corresponding bit in the other Source Register/Immediate Value. Okay let's look at the full result in Binary view...
1000 0000 0000 0000 0000 0000 0000 0001
Convert that to Hex and you get 0x80000001.
Logical ORing is the great way to set a bit high while leaving all other bits alone. For example. We can load a value from memory, set a specific bit high, then store the value back. Remember that if the bit was high beforehand, it stays high.
Example code:
ldr w0, [x1] //Load value from memory
orr w0, w0, #0x00008000 //Make sure bit 15 is set high and leave all other bits alone
str w0, [x1] //Store back new modified value to memory
Logical AND (and)
Truth Table:
| Input | Input | Result |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
With and, both bits must be high for the result to be true. Otherwise, result is always false.
Logical ANDing is a great way to check if a value in a register is even or odd.
Example code:
ands w0, w13, #0x00000001 // This will wipe all other bits while leaving bit 0 (LSB) intact. w0 is being used as a scratch register. If you don't care about preserving the GPR being AND'd, then you can set the Destination Register as same as the Source Register.
beq odd // Jump to spot in source for handling the situation of when w0 is odd. Ofc you can swap this for a "bne even"
*NOTICE* how the above and instruction has an 's' appended to it. Back in Chapter 12, you've learned that this gives us a 'free' usage of 'cmp w0, #0'. It's *IMPORTANT* to note that only the and & bic instructions are able to do this. All other logical operation instructions cannot use this feature.
You can also use Logical ANDing for a task that checks the alignment of a Memory Address that's residing in a register.
Example code of checking if Memory Address in w23 is 64-byte aligned. 64-BYTE, not bit.
ands w0, w23, #0x3F // This will wipe all bits values except the lower 6 bits of w23 and use w0 as a result scratch register. If an address if 64-byte aligned (divisible by 0x40), it's lower 6 bits will be low (null).
bne unaligned // Jump to spot in source for handling situation if Address isn't aligned
Example code of checking if Memory Address in w23 is 32-byte aligned.
ands w0, w23, #0x1F // This will wipe all bit values except the lower 5 bits of w23 and use w0 as a result scratch register. If an address if 32-byte aligned (divisible by 0x20), it's lower 5 bits will be low (null).
bne unaligned
Example code of checking if Memory Address in w23 is 16-byte aligned.
ands w0, w23, #0xF // This will wipe all bit values except the lower 6 bits of w23 and use w0 as a result scratch register. If an address if 16-byte aligned (divisible by 0x10), it's lower 6 bits will be low (null).
bne unaligned
Logical XOR (eor)
Truth Table:
| Input | Input | Result |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
With eor, as long as the two bits are opposite values, the result will be true.
Logical XORing is a great way to flip a bit (high to low, or low to high) without effecting other bits. For example...
ldr w0, [x1] // Load Value from Memory
eor w0, w0, #0x0008 // XOR bit 3. Its value will be flipped (high to low; low to high)
str w0, [x1] // Store Value back to Memory
If you Logical XOR a value with itself, the result is always 0. XORing is used by pretty much all encryption and hashing algorithms.
What is a Complement? A Complement is just another term for the Bitwise Negation of a Value. Or better yet, it's taking a Value and applying a Logical NOT to it. A Logical NOT is actually a value that is Logically NOR'd with itself. Simply put, the binary value of 0 becomes 1, and the value of 1 becomes 0.
For example, the value of 0x0000FFFF becomes 0xFFFF0000. The value of 0x8000FFF2 becomes 0x7FFF000E. You may be thinking... the ARM64 instruction set doesn't come with a Logical NOR instruction, but we can XOR a value with 0xFFFFFFFF to apply a Logical NOT. Yes this is true, but remember the String Immediate Value rules. 0xFFFFFFFF/0xFFFFFFFFFFFFFFFF cannot be used. However, there is the mvn instruction...
The mvn (Move with Bitwise Negate) instruction applies a basic Logical NOT and nothing else.
Examples...
mvn x4, x7 //Logical NOT of x7 is placed into x4
mvn w0, w0 //Do Logical NOT on w0.
mvn w7, 0xFF //Do Logical NOT of 0xFF (which is 0xFFFFFF00), and place that value into w7
Now that you understand what a Complement is. Let's dive into bic, orn, and eon.
Bit Instruction Clear (bic) is the instruction for AND w/ Complement. It's not named something like "andc" because usually when this type of operation is done, its for the purpose of clearing selected bits in a register. Like this....
mov w8, 0x0010 //Needed because bic can't use Immediate Values
bic w7, w7, w8
This will set bit 4 low in w7 and leave all other bits alone. What this bic instruction actually does is this....
Simply put, the secondary source register or IMM gets Logical NOT'd before the Logical AND operation is performed.
OR w/ Complement (ORN) follows this same concept. Example...
orn w16, w2, w14
XOR w/ Complement (EON) follows the same concept as well. Example..
eon w5, w0, w27
What's unique about XOR w/ Complement is that it produces the exact same bit results as Logical XNOR aka Logical EQV. Here's the truth table for XNOR/EQV....
| Input | Input | Result |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
HOWEVER, bic (AND w/ Complement) does NOT produce the same bit results as Logical NAND. Not only that, orn (OR W/ Complement) does NOT produce the same bit results as Logical NOR. You may be asking yourself, why doesn't the ARM64 instruction set include these 2 instructions? Well, they are simply not needed. The instructions of and, orr, eor, bic, orn, eon, and mvn cover any logical situation/circumstance that would ever need to be addressed realistically within in a program.
ANDing vs TESTing
If you have been browsing around at various ARM64 code on the internet, you may have seen the tst (Test) instruction. This instruction performs a Logical AND and updates the condition flags for any subsequent conditional branch, but it discards the result. This allows you to not have to use a scratch register.
Example (check if w13 is odd or even)
tst w13, #0x00000001
beq odd
We can optimize this even further. Testing + branching can be combined into four different possible instructions...
//Test then Branch if Zero
tbz wD, imm, label
tbz xD, imm label
//Test then Branch if not Zero
tbnz wD, imm, label
tbnz xD, imm, label
There is a "catch" with tbz and tbnz. You can only test for a specific bit. For non-extended versions imm is anything from 0 thru 31. For extended versions imm is 0 thru 63. So if you wanted to test bit 45 of xD, imm would be 45. If you wanted to test bit 2 of wD, imm would be 2.
Here's the earlier example now fully optimized.
tbnz w13, 0, odd //Test bit 0 (lsb). This bit tells us if w13 is even or odd.
Final NOTE:
Sometimes it's easier for Coders/Devs to write out Immediate Values of Logical Operation Instructions in binary form. You can do that by prepending the binary value with "0b".
Example (Logically AND w26 with 2, result is placed back into w26)
and w26, w26, 0b10