Image Blending in Windows – an Assembly Language Approach
[Once again, the code snippets in this article refuse to format correctly. When entering the article text, the scroll bars appear and all is well. When the article is submitted, the scroll bars disappear and all the code snippets suddenly form a fanatical devotion to a right margin that's too narrow, and unwanted line breaks begin appearing all over the snippets. The problem has reared its ugly head in other articles I've written, and better minds than mine have worked on it - all to no avail. The problem has not gone unnoticed, and is not the result of lazy indifference.]
[Worse, the article editor appears to be forcing the image URL references to https:// after they're entered as http://. It's not known why this occurs but as the author I know of no way I can fix it. Images display fine in the editor; URL's are auto-modified to https:// against my will after I submit the article. To counter this as best I can, each image caption includes the full URL where the image lives.]
To C, or Not to C?
Quality code from a C++ perspective could well be horribly wasteful and inefficient from the CPU’s viewpoint. If you’re not playing directly in the CPU’s arena, you’re not likely to come anywhere near maximizing its potential. With high-demand tasks such as image blending, you can’t rely on the Windows API – especially GDI functions – to get the job done efficiently. Windows is designed to be all things to all developers; it places ritual far ahead of performance. If you’re going to eliminate bottlenecks efficiently, you can’t go wrong by turning to assembly language.
The caveat here is that intrinsics are not a safe alternative. To squeeze every last iota of performance out of the CPU, you can’t write generic code that doesn’t know or care whether it’s running on a lightspeed hundredth generation i9 or a clunky lightweight ARM processor. In short, you can’t milk quality out of shortcuts. To get the best performance, sometimes you have to work for it: you must tailor your work to the hardware it’s running on. In the end, that work pays off in spades.
The Pitfalls of BitBlt
The first thing to note is that when you create a bitmap with CreateCompatibleBitmap, the very limited kernel memory is used to store that image. If Microsoft documents this fact at all, that discussion is well hidden from prying eyes. If such documentation exists, I never saw it. (And it may well exist; maybe I have no excuse for never having seen it!) When creating bitmaps on the fly, I’ve hit the “insufficient memory” wall exactly once; that experience was what led me to begin scouring development forums to track down where I was going wrong. That was when I learned about which bitmaps go into which memory areas, and in the course of adjusting for it, that particular problem never returned.
CreateDIBSection uses memory off the current process’ heap; making that switch solved my resource problem once and for all. I developed my own local function, CreateLocalBitmap, which takes the same parameters as CreateCompatibleBitmap (with one extra added) but creates a DIB section instead – and its functionality includes returning the location of the bitmap data. That little data pointer is worked with directly, across the board, in the image blending process discussed in this article. If you load an image from a resource, you can also use GetDIBits to retrieve a bitmap's data. (The documentation for GetBitmapBits says that function is deprecated; use GetDIBits instead.)
My locally declared function CreateLocalBitmap always creates a 32-bit bitmap. This is done because 4 bytes per pixel work exceedingly well for processing through XMM registers. With a 24-bit format, you just can’t do it. You’ll have to convert the 24-bit format to a 32-bit layout first – a taxing process that is wholly unnecessary, given a little preparation that creates 32-bit bitmaps from the outset.
[NOTE: the following two paragraphs were accurate at the time they were written. They were inserted as a direct result of experiencing a forced change from 32 to 24 bits in a bitmap I was working with. However in the course of creating the sample images for this article, the effect appears to have vanished. I used BitBlt to copy from a LoadImage 24-bit format to a CreateDIBSection 32-bit format, and the 32-bit format remained. So take the following two paragraphs with a grain of salt - in true Windows tradition, it could happen but doesn't always. Let your own experience guide you.]
BitBlt likes 24-bit formats, and it’s quite aggressive about forcing its views on every bitmap passing through it. Even if you’re blitting to a bitmap or DIB section that was explicitly created as a 32-bit image, BitBlt will overwrite the 32-bit data with 24-bit values. The amount of allocated bitmap memory remains unchanged from its initial size, but the expected 32-bit data format does not survive a call to BitBlt. The function is completely unware of alpha channels and will not hesitate to perform genocide on every byte of bitmap data referring to one.
Instead, AlphaBlend, designed to process alpha channels, respects the sovereignty of alpha channel bytes and leaves bitmaps formatted as 32-bit entities. Ideally, if you can get the function to work at all under Windows 10, it’s called with an opacity value of 255 (fully opaque) to emulate BitBlt without destroying the format of the bitmap data. What happens when a 24-bit image is AlphaBlended onto a 32-bit destination is a question I can’t answer – my last attempt to use that function resulted in an error that cannot and should not occur, and that was the end of my toying with it. After 22 years of developing under Windows (almost exclusively in assembly language), my intolerance for Windows API failures has grown to the point where I will no longer research most bugs and inexcusably recalcitrant functions – I simply go straight to a workaround. For example, in the case of filling a bitmap with a solid color, the silly and quite stupid (my opinion) process of creating a brush, calling FillRect, and deleting the brush, not to mention creating a memory DC to hold the bitmap while this is done, selecting the bitmap into it, then deselecting the bitmap and finally deleting the DC – is all so far over the line of sheer insanity that I couldn’t even begin to explain the thinking behind it. Instead, seven simple assembly language instructions fill the bitmap. No DC is required, no brush, no objects to select, deselect, or delete. As long as you have that bitmap data pointer, all is well.
lea rdi, BitmapData
mov rax, BitmapWidth
mov rcx, BitmapHeight
mul rcx
mov rcx, rax
mov rax, FillColor
rep stosd
Done … and … done. It’s just that simple. There’s no reason to make it any more complicated than that.
Blending
This article outlines a process for blending two bitmaps of 32-bit format. Alpha values are not used (premultiplied or otherwise); the blend is the final result of merging two images. The source opacity is passed as an integer percent value times one hundred, which is converted within the blend function to a single-precision float; the destination opacity is presumed to be one minus that value. For example, declaring a 20% opacity for the source bitmap would place the destination opacity at 80%. I have not found a way to do this with GDI (everything seems to be additive), and I won’t go beyond that to get the job done. DirectX requires a relatively enormous setup time that I find difficult to justify in most apps that I create. Moving beyond that to something like DirectComposition or Direct2D is for me unthinkable – I liken it to bringing a full-sized aircraft carrier to the grocery store just to haul your groceries home, when a little red wagon would do just as well. That doesn’t mean those API’s are that powerful – they’re just that needlessly complex (and embarrassingly bloated).
For the process outlined here, the focus is on speed, and to maximize speed, two main rules must be followed:
- Avoid memory access.
- Use XMM registers to process all color component values in parallel – this results in one multiplication per pixel, not three.
YMM registers don’t make sense in this kind of application because they use 64-bit values. For the process of blending images, 32-bit values are ultimately moved down to 8 bits for each color channel, and four 32-bit values processed by XMM registers is the low limit of SSE/AVX granularity.
Thinking it Through
Forethought is the precursor of performance. The impact of tailoring the task at hand for the specifics of the processor that task will run on cannot be overstated. A little analysis and planning can go a long way in creating unprecedented speed improvements; customizing code for the hardware it will run on has no parallel in its virtue.
In the actual blend loop, for optimal performance, there should be only three occasions when memory is accessed: to read each pixel from image 1, to read each pixel from image 2, and to write the final blended result. Complicating the process is the inherent need to separate each pixel into color channels before performing the blend. After the blend is complete, the data again needs to be converted back from float values, reassembled into a single 32-bit value, and stored at its destination.
Logically, the process is so simple that most developers (if they don’t hand the task off to Windows) simply run a loop to execute it. The problem is that in C++ or any other language, the simplicity of the algorithm is usually mistaken as equating to speed in execution, with the particulars of actual implementation not being worth much attention.
The function created in this article will take two incoming bitmaps – one and two – and write the final blend data over the first bitmap’s incoming data. Since everything transpires across the CPU’s registers, no memory needs to be allocated (or subsequently freed) to achieve the blend.
The real key to the process lies in breaking up the pixel data into color channels, then getting that data into an XMM register where the required multiplications can be executed.
The multiplier values will not change across the life of the loop, so they should be placed into XMM registers directly from the registers they’re passed to the blend function in, then left alone.
On entry into the function:
RCX > bitmap one bits
RDX > bitmap two bits
R8 = bitmap one blend %, multiplied by one hundred to allow an integer value to be passed
R9 = bitmap width
[rsp+40] = bitmap height
The reason for passing the blend % as an integer is that 64-bit calling convention becomes confusing and convoluted when trying to pass a float. It can certainly be done (most languages do it as a matter of course), but being the only float value, the blend factor will come into the function in XMM0. You can do it if you want to; the code in this article won’t. As a general rule, I’ve found that a lot of mistakes and debugging time are saved by utilizing XMM registers in some kind of sensible order where they’re not so easily lost track of. There are sixteen of the things and it’s quite easy to forget who’s doing what and why if you implement them at random. In the end, the entire issue is purely aesthetic, but I personally find it far preferable to doing things any other way: parameter 3, R8, holds the source bitmap blend percent times a hundred - allowing an integer value to be passed in a general purpose register.
For reasons discussed shortly, there is no danger of overflowing any 8-bit color channel anywhere in the blend process.
On entry to the function, immediately point RDI at the first bitmap’s data, and RSI at the second. The assembly STOSD instruction writes to the location where RDI is pointing, and bitmap one is where the blended output is written. So it may as well be set up as the first order of business.
mov rdi, rcx
mov rsi, rdx
With this done, it’s time to decide on XMM register usage. XMM 0 will get data from bitmap one; XMM1 will hold the blend factor for bitmap one. XMM2 will get data from bitmap two, and XMM3 will hold bitmap two’s blend factor.
There’s little left to do beyond setting up XMM1 and XMM3 with the blend factor values before diving into the process loop. Of critical importance is one final note: it would be insane to divide every output pixel by 100.0. After moving the incoming R8 into XMM0, it’s divided by 100.0 immediately so that the division – the slowest instruction on Earth – only needs to be performed once.
The following variables are declared as data:
align 16
one_hundred real4 4 dup ( 100.0 )
Then the entry code for the function:
mov rdi, rcx
mov rsi, rdx
movd xmm1, r8
cvtdq2ps xmm1, xmm1
divss xmm1, real4 ptr one_hundred
shufps xmm1, xmm1, 0
Setting XMM3 to (1 - XMM1) requires just a little creativity. There are no instructions for moving immediate data (data that’s encoded with an instruction) into an XMM register, and loading 1.0 from memory is last choice.
The CMPPS instruction compares whatever random data is in XMM3 with itself, checking for XMM3 = XMM3. The result must be true, regardless of what the register holds. All bits in XMM3 will then be set, as is done when a compare is true. Shifting those bits right by 31 bits will leave a value of 1.0 in each 32-bit division of XMM3.
cmpps xmm3, xmm3, 0
psrld xmm3, 31
cvtdq2ps xmm3, xmm3
subps xmm3, xmm1
The blend factors are now correctly set as packed (present and repeated in all four 32-bit sections) floating point values in XMM1 for image one, and XMM3 for image two.
Breaking Down and Building Up
The next parts of the process needing special attention are separating and recombining the color channel values. Fortunately, SSE will handle most of this for you, at least on the uptake. Curiously, there is no such convenience when writing each final blended pixel.
Things would be much simpler if the blend factor didn’t come into play. All operations could be performed with SSE integer instructions, and there would be no need for ever converting values to and from floating point. But the blend factor is the entire reason for the function, and it has to be stored as a floating point value since within the function it’s always <= 1.0. So there’s little choice in the matter but to convert the color data to floats before multiplying.
The following instruction loads the source data into XMM0 (bitmap one) and XMM2 (bitmap two):
pmovzxbd xmm0, dword ptr [ rdi ]
cvtdq2ps xmm0, xmm0
pmovzxbd xmm2, dword ptr [ rsi ]
cvtdq2ps xmm2, xmm2
The above instructions separate each byte from the dword value loaded and conveniently place the data into consecutive dword locations within an XMM register. This saves oodles of execution time over having to do it manually.
Next, the multiplication occurs:
mulps xmm0, xmm1
mulps xmm2, xmm3
Add the two values together:
addps xmm0, xmm2
Finally, build the output dword, store it, and advance both bitmap data pointers.
cvtps2dq xmm0, xmm0
shufps xmm0, xmm0, 4Eh
movd ebx, xmm0
shufps xmm0, xmm0, 93h
movd eax, xmm0
shl ebx, 8
mov bl, al
shufps xmm0, xmm0, 93h
movd eax, xmm0
shl ebx, 8
or eax, ebx
stosd
The above code comprises the entirety of the merging process.
No memory access occurs inside the loop, other than to load the source values and store the merged result. The only math performed is the multiplication of each color channel by the blend factor, and even this operation is performed simultaneously on all color channels via the XMM registers.
The complete function is shown below. Note that the images passed to this function are assumed to be the same size, and are merged in their entirety. A more sophisticated function that allowed specified areas to be selected out of each image would be considerably more complicated as far as loop controls – individual rows would need to be looped through, then columns within each row, while properly tracking the data pointers through both loops. For simplicity, this article merges the entire incoming set of bitmap data - its intent is to focus on utilizing assembly language, particularly XMM registers, to perform the actual blend.
The required data for the function:
align 16 ; Required for XMM access
one_hundred real4 4 dup ( 100.0 ) ; Divisor of 100
Finally, the entire function:
BlendImages proc
mov rdi, rcx
mov rsi, rdx
movd xmm1, r8
cvtdq2ps xmm1, xmm1
divss xmm1, real4 ptr one_hundred
shufps xmm1, xmm1, 0
cmpps xmm3, xmm3, 0
psrld xmm3, 31
cvtdq2ps xmm3, xmm3
subps xmm3, xmm1
mov rax, [ rsp + 40 ]
mul r9
mov rcx, rax
BlendLoop: pmovzxbd xmm0, dword ptr [ rdi ]
cvtdq2ps xmm0, xmm0
pmovzxbd xmm2, dword ptr [ rsi ]
cvtdq2ps xmm2, xmm2
mulps xmm0, xmm1
mulps xmm2, xmm3
addps xmm0, xmm2
cvtps2dq xmm0, xmm0
shufps xmm0, xmm0, 4Eh
movd ebx, xmm0
shufps xmm0, xmm0, 93h
movd eax, xmm0
shl ebx, 8
mov bl, al
shufps xmm0, xmm0, 93h
movd eax, xmm0
shl ebx, 8
or eax, ebx
stosd
add rsi, 4
loop BlendLoop
xor rax, rax
ret
BlendImages endp
The function conforms to the 64-bit calling convention, allowing it to be exported from a DLL and called from any language that allows calling external functions.
Limit checking is not required because the nature of the blend process makes an overflow impossible – with 8 bit color channels, no pixel can have a value greater than 255. Even if a blend factor > 1 were passed, such as 1.25, the bitmap two blend factor would be 1 - 1.25 or -0.25. Worst case, both pixels being blended would be 255. The Bitmap 1 pixel would factor in as 255 * 1.25 or 319 (rounded up); the bitmap 2 pixel would weigh in at 255 * -0.25 or -64 (rounded up). Summing the two values would yield 255. So no limit checking is required with the implementation shown.
Certified Runnable
The code in this article has actually been compiled and executed, blending the following images at 45% image 1 (the sunset) and 55% image 2 (the forest); the third (blended) image was captured from actual output generated by this article's source code:
Conclusion
This article demonstrated how drastically custom tailoring code for the hardware it’s running on can speed up an operation. Garbage in, garbage out; shortcuts are the fast path to the next bottleneck.
The function outlined here is hardly made up of thousands of lines of code, and it’s almost completely self-contained. In most (if not all) modern languages, the attendant declarations, includes, and endless compiler instructions far outweigh any savings of time in the coding process. To use an analogy, every day, more and more workers are replaced with dead weight managers. The workers (actual functions) may or may not get the job done faster, but the explosion of dead weight management makes the company as a whole larger and larger each year, while producing less and less – and what’s produced is slower and slower to execute.
A forthcoming article covers a much more complex subject: implementing Gaussian blur in assembly language. The article's code will use an 11x11 convolution kernel and will run a single pass. The speed improvement in that code is nothing short of staggering, resulting from the application of the same logic that was presented in this article: customizing code to maximize what the CPU has to offer.
