Bit manipulation generally consists of six activities: setting bits, clearing bits, inverting bits, testing and comparing bits, extracting bits from a bit string, and inserting bits into a bit string. By now you should be familiar with most of the instructions we'll use to perform these operations; their introduction started way back in the earliest chapters of this text. Nevertheless, it's worthwhile to review the old instructions here as well as present the few bit-manipulation instructions we've yet to consider.
The most basic bit-manipulation instructions are the and, or, xor, not, test, and shift and rotate instructions. Indeed, on the earliest 80x86 processors, these were the only instructions available for bit manipulation. The following paragraphs review these instructions, concentrating on how you could use them to manipulate bits in memory or registers.
The and instruction provides the ability to strip away unwanted bits from some bit sequence, replacing the unwanted bits with zeros. This instruction is especially useful for isolating a bit string or a bit set that is merged with other, unrelated data (or, at least, data that is not part of the bit string or bit set). For example, suppose that a bit string consumes bit positions 12 through 24 of the EAX register; we can isolate this bit string by setting all other bits in EAX to 0 by using the following instruction:
and( %1_1111_1111_1111_0000_0000_0000, eax );
Most programs use the and instruction to clear bits that are not part of the desired bit string. In theory, you could use the or instruction to mask all unwanted bits to ones rather than zeros, but later comparisons and operations are often easier if the unneeded bit positions contain 0 (see Figure 10-1).
Once you've cleared the unneeded bits in a set of bits, you can often operate on the bit set in place. For example, to see if the string of bits in positions 12 through 24 of EAX contains $12F3, you could use the following code:
and( %1_1111_1111_1111_0000_0000_0000, eax ); cmp( eax, %1_0010_1111_0011_0000_0000_0000 );
Here's another solution, using constant expressions, that's a little easier to digest:
and( %1_1111_1111_1111_0000_0000_0000, eax ); cmp( eax, $12F3 << 12 ); // "<<12" shifts $12F3 to the left 12 bits.
Most of the time, however, you'll want (or need) the bit string aligned with bit 0 in EAX prior to any operations you would want to perform. Of course, you can use the shr instruction to properly align the value after you've masked it, like this:
and( %1_1111_1111_1111_0000_0000_0000, eax );
shr( 12, eax );
cmp( eax, $12F3 );
<< Other operations that require the bit string at bit #0 >>Now that the bit string is aligned to bit 0, the constants and other values you use in conjunction with this value are easier to deal with.
You can also use the or instruction to mask unwanted bits. However, the or instruction does not let you clear bits; it allows you to set bits to ones. In some instances setting all the bits around your bit set may be desirable; most software, however, is easier to write if you clear the surrounding bits rather than set them.
The or instruction is especially useful for inserting a bit set into some other bit string. To do this, there are several steps you must go through:
Clear all the bits surrounding your bit set in the source operand.
Clear all the bits in the destination operand where you wish to insert the bit set.
orthe bit set and destination operand together.
For example, suppose you have a value in bits 0..12 of EAX that you wish to insert into bits 12..24 of EBX without affecting any of the other bits in EBX. You would begin by stripping out bits 13 and above from EAX; then you would strip out bits 12..24 in EBX. Next, you would shift the bits in EAX so the bit string occupies bits 12..24 of EAX. Finally, you would or the value in EAX into EBX (see Figure 10-2), as shown here:
and( $1FFF, eax ); // Strip all but bits 0..12 from eax.
and( $FE00_0FFF, ebx ); // Clear bits 12..24 in ebx.
shl( 12, eax ); // Move bits 0..12 to 12..24 in eax.
or( eax, ebx ); // Merge the bits into ebx.
In this figure the desired bits (AAAAAAAAAAAAA) formed a bit string. However, this algorithm still works fine even if you're manipulating a noncontiguous set of bits. All you have to do is to create an appropriate bit mask you can use for anding that has ones in the appropriate places.
When working with bit masks, it is incredibly poor programming style to use literal numeric constants as in the past few examples. You should always create symbolic constants in the HLA const (or val) section for your bit masks. Combined with some constant expressions, you can produce code that is much easier to read and maintain. The current example code is more properly written as the following:
const
StartPosn := 12;
BitMask: dword := $1FFF << StartPosn; // Mask occupies bits 12..24.
.
.
.
shl( StartPosn, eax ); // Move into position.
and( BitMask, eax ); // Strip all but bits 12..24 from eax.
and( !BitMask, ebx ); // Clear bits 12..24 in ebx.
or( eax, ebx ); // Merge the bits into ebx.Notice the use of the compile time not operator (!) to invert the bit mask in order to clear the bit positions in EBX where the code inserts the bits from EAX. This saves having to create another constant in the program that has to be changed anytime you modify the BitMask constant. Having to maintain two separate symbols whose values are dependent on one another is not a good thing in a program.
Of course, in addition to merging one bit set with another, the or instruction is also useful for forcing bits to 1 in a bit string. By setting various bits in a source operand to 1, you can force the corresponding bits in the destination operand to 1 by using the or instruction.
The xor instruction allows you to invert selected bits in a bit set. Although inverting bits isn't as common as setting or clearing them, the xor instruction often appears in bit-manipulation programs. Of course, if you want to invert all the bits in some destination operand, the not instruction is probably more appropriate than the xor instruction; however, to invert selected bits while not affecting others, the xor is the way to go.
One interesting fact about xor's operation is that it lets you manipulate known data in just about any way imaginable. For example, if you know that a field contains %1010, you can force that field to 0 by xoring it with %1010. Similarly, you can force it to %1111 by xoring it with %0101. Although this might seem like a waste, because you can easily force this 4-bit string to 0 or all ones using and/or, the xor instruction has two advantages: (1) You are not limited to forcing the field to all zeros or all ones; you can actually set these bits to any of the 16 valid combinations via xor; and (2) if you need to manipulate other bits in the destination operand at the same time, and/or may not be able to accommodate you. For example, suppose that you know that one field contains %1010 that you want to force to 0 and another field contains %1000 and you wish to increment that field by 1 (i.e., set the field to %1001). You cannot accomplish both operations with a single and or or instruction, but you can do this with a single xor instruction; just xor the first field with %1010 and the second field with %0001. Remember, however, that this trick works only if you know the current value of a bit set within the destination operand. Of course, while you're adjusting the values of bit fields containing known values, you can invert bits in other fields simultaneously.
In addition to setting, clearing, and inverting bits in some destination operand, the and, or, and xor instructions also affect various condition codes in the flags register. These instructions affect the flags as follows:
These instructions always clear the carry and overflow flags.
These instructions set the sign flag if the result has a 1 in the H.O. bit; they clear it otherwise. That is, these instructions copy the H.O. bit of the result into the sign flag.
These instructions set/clear the zero flag if the result is 0.
These instructions set the parity flag if there is an even number of set bits in the L.O. byte of the destination operand; they clear the parity flag if there is an odd number of 1 bits in the L.O. byte of the destination operand.
The first thing to note is that these instructions always clear the carry and overflow flags. This means that you cannot expect the system to preserve the state of these two flags across the execution of these instructions. A very common mistake in many assembly language programs is the assumption that these instructions do not affect the carry flag. Many people will execute an instruction that sets/clears the carry flag, execute an and/or/xor instruction, and then attempt to test the state of the carry from the previous instruction. This simply will not work.
One of the more interesting aspects to these instructions is that they copy the H.O. bit of their result into the sign flag. This means that you can easily test the setting of the H.O. bit of the result by testing the sign flag (using sets/setns or js/jns instructions, or using the @s/@ns flags in a boolean expression). For this reason, many assembly language programmers will often place an important boolean variable in the H.O. bit of some operand so they can easily test the state of that bit using the sign flag after a logical operation.
We haven't talked much about the parity flag in this text. We're not going to get into a big discussion of this flag and what you use it for because the primary purpose for this flag has been taken over by hardware.[126] However, because this is a chapter on bit manipulation, and parity computation is a bit-manipulation operation, it seems only fitting to provide a brief discussion of the parity flag at this time.
Parity is a very simple error-detection scheme originally employed by telegraphs and other serial communication protocols. The idea was to count the number of set bits in a character and include an extra bit in the transmission to indicate whether that character contained an even or odd number of set bits. The receiving end of the transmission would also count the bits and verify that the extra "parity" bit indicated a successful transmission. We're not going to explore the information-theory aspects of this error-checking scheme at this point other than to point out that the purpose of the parity flag is to help compute the value of this extra bit.
The 80x86 and, or, and xor instructions set the parity bit if the L.O. byte of their operand contains an even number of set bits. An important fact bears repeating here: The parity flag reflects only the number of set bits in the L.O. byte of the destination operand; it does not include the H.O. bytes in a word, double-word, or other-sized operand. The instruction set uses the L.O. byte only to compute the parity because communication programs that use parity are typically character-oriented transmission systems (there are better error-checking schemes if you transmit more than 8 bits at a time).
The zero flag setting is one of the more important results the and/or/xor instructions produce. Indeed, programs reference this flag so often after the and instruction that Intel added a separate instruction, test, whose main purpose is to logically and two results and set the flags without otherwise affecting either instruction operand.
There are three main uses of the zero flag after the execution of an and or test instruction: (1) checking to see if a particular bit in an operand is set, (2) checking to see if at least one of several bits in a bit set is 1, and (3) checking to see if an operand is 0. Using (1) is actually a special case of (2) in which the bit set contains only a single bit. We'll explore each of these uses in the following paragraphs.
A common use for the and instruction, and also the original reason for the inclusion of the test instruction in the 80x86 instruction set, is to test to see if a particular bit is set in a given operand. To perform this type of test, you would normally and/test a constant value containing a single set bit with the operand you wish to test. This clears all the other bits in the second operand, leaving a 0 in the bit position under test if the operand contains a 0 in that bit position. anding with a 1 leaves a 1 in that position if it originally contained a 1. Because all of the other bits in the result are 0, the entire result will be 0 if that particular bit is 0; the entire result will be nonzero if that bit position contains a 1. The 80x86 reflects this status in the zero flag (Z = 1 indicates a 0 bit; Z = 0 indicates a 1 bit). The following instruction sequence demonstrates how to test to see if bit 4 is set in EAX:
test( %1_0000, eax ); // Check bit #4 to see if it is 0/1.
if( @nz ) then
<< Do this if the bit is set. >>
else
<< Do this if the bit is clear. >>
endif;You can also use the and/test instructions to see if any one of several bits is set. Simply supply a constant that has a 1 in all the positions you want to test (and zeros everywhere else). anding such a value with an unknown quantity will produce a nonzero value if one or more of the bits in the operand under test contain a 1. The following example tests to see if the value in EAX contains a 1 in bit positions 1, 2, 4, and 7:
test( %1001_0110, eax );
if( @nz ) then // At least one of the bits is set.
<< Do whatever needs to be done if one of the bits is set. >>
endif;Note that you cannot use a single and or test instruction to see if all the corresponding bits in the bit set are equal to 1. To accomplish this, you must first mask out the bits that are not in the set and then compare the result against the mask itself. If the result is equal to the mask, then all the bits in the bit set contain ones. You must use the and instruction for this operation because the test instruction does not mask out any bits. The following example checks to see if all the bits in a bit set (bitMask) are equal to 1:
and( bitMask, eax );
cmp( eax, bitMask );
if( @e ) then
// All the bit positions in eax corresponding to the set
// bits in bitMask are equal to 1 if we get here.
<< Do whatever needs to be done if the bits match. >>
endif;Of course, once we stick the cmp instruction in there, we don't really have to check to see if all the bits in the bit set contain ones. We can check for any combination of values by specifying the appropriate value as the operand to the cmp instruction.
Note that the test/and instructions will set the zero flag in the above code sequences only if all the bits in EAX (or other destination operand) have zeros in the positions where ones appear in the constant operand. This suggests another way to check for all ones in the bit set: Invert the value in EAX prior to using the and or test instruction. Then if the zero flag is set, you know that there were all ones in the (original) bit set. For example:
not( eax ); test( bitMask, eax ); if( @z ) then // At this point, eax contained all ones in the bit positions // occupied by ones in the bitMask constant. << Do whatever needs to be done at this point. >> endif;
The previous paragraphs all suggest that the bitMask (the source operand) is a constant. This was for purposes of example only. In fact, you can use a variable or other register here, if you prefer. Simply load that variable or register with the appropriate bit mask before you execute the test, and, or cmp instructions in the examples above.
Another set of instructions we've already seen that we can use to manipulate bits are the bit test instructions. These instructions include bt (bit test), bts (bit test and set), btc (bit test and complement), and btr (bit test and reset). We've used these instructions to manipulate bits in HLA character-set variables; we can also use them to manipulate bits in general. The btx instructions allow the following syntactical forms:
btx(BitNumber,BitsToTest); btx(reg16,reg16); btx(reg32,reg32); btx(constant,reg16); btx(constant,reg32); btx(reg16,mem16); btx(reg32,mem32); btx(constant,mem16); btx(constant,mem32);
The btx instruction's first operand is a bit number that specifies which bit to check in the second operand. If the second operand is a register, then the first operand must contain a value between 0 and the size of the register (in bits) minus 1; because the 80x86's largest registers are 32 bits, this value has the maximum value 31 (for 32-bit registers). If the second operand is a memory location, then the bit count is not limited to values in the range 0..31. If the first operand is a constant, it can be any 8-bit value in the range 0..255. If the first operand is a register, it has no limitation.
The bt instruction copies the specified bit from the second operand into the carry flag. For example, the bt( 8, eax ); instruction copies bit 8 of the EAX register into the carry flag. You can test the carry flag after this instruction to determine whether bit 8 was set or clear in EAX.
The bts, btc, and btr instructions manipulate the bit they test while they are testing it. These instructions may be slow (depending on the processor you're using), and you should avoid them if performance is your primary concern and you're using an older CPU. If performance (versus convenience) is an issue, you should always try two different algorithms—one that uses these instructions, one that uses and/or instructions—and measure the performance difference; then choose the best of the two approaches.
The shift and rotate instructions are another group of instructions you can use to manipulate and test bits. These instructions move the H.O. (left shift/rotate) or L.O. (right shift/rotate) bits into the carry flag. Therefore, you can test the carry flag after you execute one of these instructions to determine the original setting of the operand's H.O. or L.O. bit. The shift and rotate instructions are invaluable for aligning bit strings and packing and unpacking data. Chapter 2 has several examples of this, and some earlier examples in this chapter also use the shift instructions for this purpose.
[126] Serial communications chips and other communications hardware that use parity for error checking normally compute the parity in hardware; you don't have to use software for this purpose.