How are 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.

Initially, the 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:

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
op5		op4		op3		op2		op1		op6	template			bias

Operations 1 through 5 select one of the following logical operations:

Value	Operation	Abbreviation
0	not	n
1	exclusive or	x
2	or	o
3	and	a

Operation 6 encodes an optional final not operation.

Value	Operation	Abbreviation
0	no operation
1	not	n

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.

Value	Template
0	SPDD
1	SPD
2	SDP
3	(not used)
4	(not used)
5	SSP*DS
6	SSP*PDS
7	SSD*PDS

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 BitBlt operation.

Consider the raster opcode 0x00010289. The operation index is 1, which decodes as follows:

P	1	1	1	1	0	0	0	0
S	1	1	0	0	1	1	0	0
D	1	0	1	0	1	0	1	0
Result	0	0	0	0	0	0	0	1

The operation code is 0x0289, which decodes as follows:

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
op5		op4		op3		op2		op1		op6	template			bias
0	0	0	0	0	0	1	0	1	0	0	0	1	0	0	1
0		0		0		2		2		0	2			1
n		n		n		o		o			SDP			1

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 BitBlt operation.

In RPN, this encodes compactly as DPSoonnn

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 DPS.
• Then we append the operations, which is oonnn.

Observe that 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 0xD4 is 0x00D41D78. The operation code is 0x1D78:

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
op5		op4		op3		op2		op1		op6	template			bias
0	0	0	1	1	1	0	1	0	1	1	1	1	0	0	0
0		1		3		1		1		1	6			0
n		x		a		x		x		n	SSP*PD			0

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 nn leaves 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 0x0042.

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
op5		op4		op3		op2		op1		op6	template			bias
0	0	0	0	0	0	0	0	0	1	0	0	0	0	1	0
0		0		0		0		1		0	0			2
n		n		n		n		x			SPDD			2

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 0.

Similarly, operation index 255 has operation code 0x0062 which decodes as follows:

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
op5		op4		op3		op2		op1		op6	template			bias
0	0	0	0	0	0	0	0	0	1	1	0	0	0	1	0
0		0		0		0		1		1	0			2
n		n		n		n		x		n	SPDD			2

This decodes as DDxnnnnn, which simplifies to DDxn, and since we learned that DDx is 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.