BitBlt raster opcodes calculated?
Commenter R P asks what the low-order 16 bits of the
BitBlt raster opcodes mean.
The documentation explains that the high-order 16 bits of the raster opcode are the zero-extended 8-bit value that represents the result of the raster operation given the 8 combinations of three binary inputs (pattern, source, and destination). This is the easy part to understand.
The documentation also says that the low-order 16 bits are an operation code, but gives no information as to how the operation code is determined.
Okay, let’s dig through the history.
BitBlt raster opcodes were only 16-bit values, consisting of the operation codes. The higher-order 16 bits were added later because it turns out that people preferred table lookups to parsing operation codes.
Okay, that’s enough beating around the bush. How do I parse the operation codes?
The operation code is interpreted as follows:
Operations 1 through 5 select one of the following logical operations:
Operation 6 encodes an optional final not operation.
The operations imply the number of input parameters required. Each binary operation pops two arguments off the stack and pushes the result back onto the stack, for a net reduction of one. The unary not operation pops one argument off the stack and pushes the result back onto the stack, for no net change. And when we’re finished, we want one final result on the stack. Therefore, the number of items that need to be placed onto the stack is one more than the number of binary operations.
The template and bias tell you what those parameters are. First, the template selects one of the following sequences of elements.
Two of the templates are not currently used and are reserved for future expansion.
The bias specifies how many initial template elements to ignore. After that, take the template elements until you have consumed one more than the number of binary operations. Also take the asterisk, if you encounter one. And if you run out of template elements, then start over from the beginning.
Okay, now we put all the pieces together.
- For each template element:
- If it is a letter, then push that input onto the stack.
- If it is an asterisk, then perform the next operation.
- After you have used up all the template elements, perform all of the remaining operations.
- When you’re done, there should be one value left on the stack. That is the result of the
Consider the raster opcode
0x00010289. The operation index is 1, which decodes as follows:
The operation code is
0x0289, which decodes as follows:
There are two binary operation codes (the two or operations), so we will need three parameters.
- The bias tells us to skip the first template element, so we skip the S.
- The next element in the template is a D, so we push the destination.
- The next element in the template is a P, so we push the pattern.
- We have run out of template elements, so we wrap around and see that we have an S, so we push the source.
- Now to use up the remaining operations, in order:
- Operation 1 tells us to pop the top two values from the stack, or them together, and push the result back onto the stack.
- Operation 2 tells us to pop the top two values from the stack, or them together, and push the result back onto the stack.
- Operation 3 tells us to pop the top value from the stack, bitwise-not it, and push the result back onto the stack.
- Operation 4 tells us to pop the top value from the stack, bitwise-not it, and push the result back onto the stack.
- Operation 5 tells us to pop the top value from the stack, bitwise-not it, and push the result back onto the stack.
- Operation 6 tells us to do nothing.
- The final value on the stack is the result of the
In RPN, this encodes compactly as
It looks like a lot of work, but that’s because I spelled it out in painstaking detail. A shorter version would be
- The template says SDP, and the bias is 1, so we start at the D and take three parameters (wrapping around if necessary), which gives us
- Then we append the operations, which is
nn bitwise-negates the top item on the stack, and then bitwise-negates it again. The two operations cancel out, which means that any
nn sequence can be optimized out. In practice, these
nn operations will appear at the end. If you’re encoding operations, and you have an even number of leftover operation slots, then you pad out the unused operations with not. If you have an odd number of leftover operation slots, then you put not in all but the last slot. (Operation 6 is the only one that can be left empty.)
Removing the redundant nn leaves us with
DPSoon, which matches the value given in the table.
Let’s try one of the more complicated operations. Operation index
0x00D41D78. The operation code is
There are four binary operations, so we need five parameters. There is no bias, so we start at the beginning with
SSP. Next is an asterisk, so we replace it with the first operation, which is
x. Then we continue with the template, which gives us
PD. And then we perform the leftover operations, which are
xaxnn. The resulting RPN is
SSPxPDxaxnn, which after canceling out the
SSPxPDxax. And this matches the value in the table.
If you write a program to apply this algorithm to all of the raster operations, you’ll find that decoding the operation code results in the published RPN, with the exception of operation indices 0 and 255.
Let’s decode operation index 0, whose operation code is
This decodes as
DDxnnnn, which simplifies to
DDx, but the published RPN is just
0. Aha, but we also know that anything xor‘d with itself is zero, so
DDx simplifies further to
Similarly, operation index 255 has operation code
0x0062 which decodes as follows:
This decodes as
DDxnnnnn, which simplifies to
DDxn, and since we learned that
0, this gives us
0n, which simplifies further to just
1, which matches the published RPN.
Back to history: As I noted earlier, the raster opcodes were initially 16-bit values, and the idea was that
BitBlt implementations would parse and execute the expressions encoded in the operation code. In practice, people just looked up the value in a table of precomputed operation codes and used that to decide how to perform the operation. As a result, the operation index was added to the raster opcode, so that implementations who want to use a table lookup have a single byte to look up instead of having to do a binary search on the 16-bit operation code. Both the operation index and operation code are present so that the values work both with drivers that use lookup tables and drivers which parse the operation code and execute the miniature expression language.
Over time, the drivers that executed the miniature expression language died out. All anybody cares about nowadays is the operation index.