Binary logic: masks, flags, and tst
prerequisite
The logic instructions treat a register as a row of separate bits. Bit 5 of the result depends only on bit 5 of each operand, and nothing carries from one position to the next the way it does in addition. That makes them the tool for changing or checking chosen bits while leaving the others alone.
And, or, exclusive or, not
Each logic operation takes one bit from each operand and gives one bit back:
| a | b | a AND b | a OR b | a XOR b |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
AND is 1 only in the rows where a and b are both 1. OR is 1 whenever at least one of them is. Exclusive or (XOR) gives 1 where the two bits differ. NOT takes a single bit and flips it. Applied to whole registers, 1100 AND 1010 is 1000, OR is 1110, and XOR is 0110.
AArch64 spells these as instructions, each working on all 32 bits of a w register or all 64 bits of an x register at once:
| instruction | result |
|---|---|
and d, n, m | n AND m |
orr d, n, m | n OR m |
eor d, n, m | n XOR m |
bic d, n, m | n AND (NOT m), called bit clear |
orn d, n, m | n OR (NOT m) |
eon d, n, m | n XOR (NOT m) |
mvn d, m | NOT m |
Two familiar instructions are logic instructions underneath: mov x19, x20 is orr x19, xzr, x20 (OR with zero changes nothing), and mvn is orn with the zero register as its first source.
Masks
A mask is a value whose 1 bits mark the positions you want to work on. Each instruction does one job with it:
orrwith a mask sets those bits to 1, because x OR 1 is 1 and x OR 0 is x.bicwith a mask clears those bits to 0.eorwith a mask flips (toggles) those bits, because x XOR 1 is NOT x and x XOR 0 is x.andwith a mask keeps those bits and clears all the others.and w1, w0, 0xffkeeps the low byte ofw0.
A flag is one bit used as a yes-or-no answer. The N, Z, C and V condition flags that cmp sets are flags in exactly this sense. A program can pack its own flags into one register, which saves space and lets one instruction change several at once.
Status effects as flags
A game might keep a character's status effects as four flags in one word:
| bit | mask | effect |
|---|---|---|
| 0 | 0x1 | poisoned |
| 1 | 0x2 | invisible |
| 2 | 0x4 | flying |
| 3 | 0x8 | shielded |
The program below names each mask with define, so the code says POISONED instead of 0x1. In FLYING | SHIELDED, the | means OR, worked out by the assembler before the program runs, so that operand is the constant 0xc. bic takes its mask from a register here, so the mask goes into w9 first.
The status word has to survive every printf call, so it lives in w19. This main uses w19 without saving it first, as the programs in these lessons do. A subroutine you write yourself has to save any of x19 to x28 that it changes.
The status goes 0x0, 0x1, 0xd, 0xf, 0xe, 0xc. In binary that is 0000, 0001, 1101, 1111, 1110, 1100: each step changes one bit, except the third, where one mask sets two bits at once.
The two eor lines use the same mask, so the second one undoes the first: flipping a bit twice puts it back. bic is safe to repeat as well: clearing a bit that is already 0 leaves it at 0.
pitfall
A logic instruction cannot take just any constant. The immediate in and, orr, eor, ands and tst has to be a bitmask immediate: one run of consecutive 1s, which may be rotated and repeated across the register. 0xc (1100), 0xff and 0xfffffffe qualify. 0x5 (0101) does not, so orr w19, w19, POISONED | FLYING fails to assemble. Put a mask like that in a register with mov first and use the register form. Zero and all ones are never allowed as a bitmask immediate either.
Testing bits with tst
tst ANDs its two operands, throws the result away, and keeps only the condition flags, the same way cmp is a subs that throws its result away. If none of the mask's bits are 1 in the register, the AND is zero and the Z flag is set. So after a tst:
b.eqbranches when every masked bit is 0.b.nebranches when at least one masked bit is 1.
ands does the same AND but also writes the result to its destination. Both set N from the top bit of the result and Z when the result is zero, and both clear C and V.
The program below starts from a status value and prints the name of each effect that is on. Each test branches past its message with b.eq when the bit is clear, the same shape as an if with no else. Before the four single-bit tests, one tst with the mask 0xf checks all four bits at once, and prints no effects when none is set.
With the starting value 0xa it prints status = 0xa, then invisible and shielded: 0xa is 1010, so bits 1 and 3 are on. Change START to 0x0 to see the no effects line, or to 0xf to see all four names.
Check yourself
w0holds0110andw1holds0011. What doand,orrandeorof the two give?- Which instruction turns bit 4 of
w19off and leaves every other bit as it was, with the mask0x10inw9? - After
tst w19, 0x4, which branch jumps when bit 2 ofw19is 1? - Why does
eor w19, w19, 0x3done twice leavew19unchanged?
answers
show answers
0010,0111and0101.bic w19, w19, w9.b.ne: the AND is not zero when the bit is 1.- Each
eorflips bits 0 and 1, and flipping a bit twice puts it back.
Practice
- Basic quiz: binary logic and Intermediate quiz: binary logic: what each logic instruction does,
bicandtstincluded. - Fill in the blank: binary logic (core): write the instruction for a described change, such as clearing the bits set in a mask.
- Predict: binary logic (challenge): what short instruction sequences leave in a register.
- Power of two, or not?: one
andof n with n - 1 answers it. - The secret handshake: test one bit at a time with
tstand a mask. - Bit population census and Advanced quiz: binary logic: both lean on Shifts, sign extension, and bitfields, the next lesson.
- Basic quiz: bit manipulation: masks that set, clear and test one bit, and the AND of n with n - 1. Its shift and rotate questions lean on the next lesson too.