Let GDI do your RLE compression for you


This is another trick along the lines of using DIB sections to perform bulk color mapping. GDI will do it for you; you just have to know how to ask. Today's mission is to take a 4bpp bitmap and compress it in BI_RLE4 format. Now, sure, there are programs out there which already do this conversion, but the lesson is in the journey, not in the destination.

The secret is the GetDIBits function. You give this function a bitmap and a bitmap format, and out come the bits in the format you requested; GDI will convert as necessary.

Note: I'm going to take a risk and write "sloppy" code. This is code that is not production quality but is enough to get the point across, so put your nitpicking notepads away.

void ConvertToRLE4(LPCTSTR pszSrc, LPCTSTR pszDst)
{
    // error checking elided for expository purposes
    HBITMAP hbm = (HBITMAP)LoadImage(NULL, pszSrc, IMAGE_BITMAP,
                                     0, 0,
                                     LR_LOADFROMFILE |
                                     LR_CREATEDIBSECTION);

    DIBSECTION ds;

    // error checking elided for expository purposes
    GetObject(hbm, sizeof(ds), &ds);

    if (ds.dsBmih.biBitCount != 4) {
        // error - source bitmap is not 4bpp
    }

    struct BITMAPINFO16COLOR {
        BITMAPINFOHEADER bmih;
        RGBQUAD rgrgb[16];
    } bmi16;
    bmi16.bmih = ds.dsBmih;

    bmi16.bmih.biCompression = BI_RLE4;

    BYTE *rgbPixels = new BYTE[bmi16.bmih.biSizeImage];
    HDC hdc = GetDC(NULL);
    if (GetDIBits(hdc, hbm, 0, bmi16.bmih.biHeight, rgbPixels,
                  (LPBITMAPINFO)&bmi16, DIB_RGB_COLORS)
        != bmi16.bmih.biHeight) {
        // error - bitmap not compressible
    }
    ReleaseDC(NULL, hdc);

    BITMAPFILEHEADER bfh = { 0 };
    bfh.bfType = MAKEWORD('B', 'M');
    bfh.bfOffBits = sizeof(BITMAPFILEHEADER) + sizeof(bmi16);
    bfh.bfSize = bfh.bfOffBits + bmi16.bmih.biSizeImage;

    // error checking elided for expository purposes
    HANDLE h = CreateFile(pszDst, GENERIC_WRITE, 0, NULL,
                          CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL);
    DWORD dwWritten;
    WriteFile(h, &bfh, sizeof(bfh), &dwWritten, NULL);
    WriteFile(h, &bmi16, sizeof(bmi16), &dwWritten, NULL);
    WriteFile(h, rgbPixels, bmi16.bmih.biSizeImage, &dwWritten, NULL);
    CloseHandle(h);
    delete[] rgbPixels;
}

Let's start from the top. After loading the bitmap and verifying that it is a 4bpp bitmap, we declare a BITMAPINFO16COLOR structure that is just a BITMAPINFO structure that holds 16 colors instead of just one. We copy the BITMAPINFOHEADER from the DIBSECTION to our structure for two reasons:

  1. We want to make some changes, and
  2. GDI expects the color table to come immediately after the BITMAPINFOHEADER.

The second reason is the more important one. We can't use the BITMAPINFOHEADER that is part of the DIBSECTION structure because the DIBSECTION structure puts dsBitfields after the BITMAPINFOHEADER instead of a color table.

After copying the BITMAPINFOHEADER, we make the key change: Changing the compression type to BI_RLE4. We allocate a pixel buffer of a size equal to the uncompressed size of the original bitmap and use GetDIBits to fill it with compressed data. Key points:

  • Before calling the GetDIBits function, we must set the biSizeImage member of the BITMAPINFO structure to the size of the buffer we passed as rgbPixels. In our case, this happened implicitly since we allocated rgbPixels based on the value of bmi16.bmih.biSizeImage.

  • On successful exit from the GetDIBits function, the GetDIBits function sets the biSizeImage member of the BITMAPINFO structure to the number of bytes actually written to the buffer.

  • On successful exit from the GetDIBits function, the GetDIBits function fills the color table if you're using a bitmap format that requires a color table. It's important that you allocate enough memory to hold the color table; if you forget, then you have a buffer overflow bug.

Since the GetDIBits function returns the number of scan lines successfully read, if the value is different from the value we requested, then something went wrong. In our case, the most likely reason is that the bitmap is not compressible according to the BI_RLE4 algorithm.

Now that we have the compressed bits, it's just grunt work to turn it into a BMP file. The BMP file format specifies that the file begins with a BITMAPFILEHEADER, followed by the BITMAPINFOHEADER, the color table, and the pixels. So we write them out in that order.

Easy peasy.

Comments (25)
  1. Neil (SM) says:

    Even with the note about sloppy non-production code, the first commenter just couldn’t resist.

  2. Adrian says:

    Cool trick.

    One thing that always puzzles me about some of the GDI functions like GetDIBits is what is the HDC parameter used for?  MSDN is a pretty vague, and I don’t see an obvious need for it in this case.  Can you pass any old DC in?  Can you pass NULL?

    I have similar confusion about functions like SetStretchBltMode.  Do you use it on the source or the destination DC?

  3. Xepol says:

    While a handy example in how to save a bitmap, I am struck by a few things.

    1. This would have been more relevant about 10 years ago.
    2. The Windows API has always struck me as surprisingly deficient when it comes to working with graphics files.  Having to hand craft file sections strikes me a tedious make work when 99.9% of situations could just as easily be handled by single loadbitmap savebitmap calls.  This isn’t the only area where the winapis seem to fall short of doing the job properly.

    3. I understand why GIF isn’t supported by the winapi (patent issues with a brain dead patent owner), but I’m less clear on why JPG and PNG support are not native parts of the GDI.

    I suppose you could argue that point 3 is covered under the whole reverse compatibility issue, but I suspect the problem is larger.  I think it is a symptom that MS has already collapsed under its own size, entrenched in a culture that serves only to defeat innovation rather than embrace it.

    Every time I hear about a "it isn’t right but if we fix it, other people’s stuff breaks" problem on this blog, I just get more and more convinced that MS is heading for a monumental failure unless someone comes in and serious cleans house.

    I am not even certain that the change in corporate attitude required to avoid certain dissaster is even possible at this point.

    Sad, really.

  4. zila says:

    You can load it using Ole, and get the bitmap out of the IPicture extremely easily.

    Or better yet you can use GdiPlus.

    http://msdn.microsoft.com/en-us/library/ms533971(VS.85).aspx

    Both native parts of the OS no?

  5. acq says:

    Xepol, you’re very, very wrong.

    The biggest success for MSFT  is when the old programs just work or work faster.

    The worst MSFT does is when it listens to advices like yours (also from the inside of the company) and produces something where not all programs work perfectly or are slower than before because of new features.

    I can guarantee you that a lot of big companies will reject switching to 64-bit versions of OS even once there’s enough memory on the computers they use only because some existing Win16 programs won’t work on 64-bit OS.

  6. Leo Davidson says:

    When writing code to read/write BMP files it’s difficult not to be sloppy.

    For such a simple format getting the code right is incredibly complex due to all the different rules (which interact with each other), overloaded structure flags/members and possible formats.

    As a result of the complexity, and how few manage to get their writers right, the are a lot of malformed BMP files out there which people making readers have to cope with (or at least safely reject without your program going ape). That’s on top of the well-formed but incredibly uncommon image types you’ll eventually come across after someone sends you something that won’t display. :)

    With that in mind, the article presents a good tip: Let GDI compress (and decompress) RLE data for you. The BMP format is complex enough as it is without trying to get RLE right as well.

    Also, properly implementing RLE decompression — let alone compresion — yourself is more complex than it might seem. It’s like BMP in that some simple rules can combine into a complex set of states, some of which you’re likely to miss. Let GDI (or a higher level library) do the work!

  7. Mike says:

    Adrian, the DC passed to GetDIBits is needed in case there are palette or color management conversion that needs to be done.

  8. Aardvark says:

    I prefer this:

    bfh.bfType = ‘MB’;

    to your:

    bfh.bfType = MAKEWORD(‘B’, ‘M’);

    Two characters in a single quoted string is just to strange to resist! Google "Multi-character constants" for more info (not MUCH more however…).

  9. Adrian says:

    Thanks Mike for your insight on the purpose of the HDC parameter.

    But that still leaves me with questions.  Since this is a 4-bit to 4-bit compression, there should be no conversion of the color table at all.  So do you really need a DC?  If my screen were in some weird color format, could that affect the result of this compression?  (I’d hope not!)

  10. johnb says:

    Xepol: GDI can already decode JPEG and PNG data for you.  See the documentation of the StretchDIBits function (which says, "Windows 98/Me, Windows 2000/XP: StretchDIBits has been extended to allow a JPEG or PNG image to be passed as the source image." right up at the top in the synopsis of the function)

  11. You’re still vulnerable to a buffer overflow — allocating bmi16.bmih.biSizeImage bytes for the compressed data is not enough, since some images may get larger upon "compression".

    According to http://www.fourcc.org/rgb.php , you should need 130 bytes (00 FF plus the pixel data) for every 256 pixels in the worst case, which comes out to a maximum image size of

    (130 * bmi16.bmih.biWidth * bmi16.bmih.biWidth + 255) / 256

    Also, not all programs properly set the biSizeImage field properly, so you may end up allocating 0 (!) bytes.

  12. Err, that should be 130 bytes for every _255_ pixels, so the maximum compressed size is

    (130 * bmi16.bmih.biWidth * bmi16.bmHeight + 254) / 255

  13. Alexandre Grigoriev says:

    johnb,

    JPEG and PNG in GDI: only for printer DC, sorry, not for display.

  14. davidlmorris says:

    Raymond, you said "This is code that is not production quality but is enough to get the point across".  I understand why you would do this, and I probably wouldn’t want the detail to get in the way of the point in any event.  

    But.  

    For the future, I would be interested in seeing an example like this taken all the way to full production code (perhaps over several entries). I think that exercise could be very instructional. And, I just can’t imagine not learning something from it – even if that thing was that most of my code was OK.

  15. Lio says:

    "the lesson is in the journey, not in the destination."

    OT: Are you subscribed to ChinesePod by any chance?

  16. Dude says:

    Does anyone actually use RLE? Our customers are constantly asking us to support formats like JPG, PNG and TIF, but never about RLE.

    As a matter of fact, when we tell them we support RLE, we usually just get a blank stare back.

  17. Falcon says:

    "Alas, there’s probably some idiot out there that’s gonna use Raymond’s code as-is without making it production ready in a real live system…"

    Yeah, wouldn’t surprise me. They’d probably even leave this bit in:

           != bmi16.bmih.biHeight) {

           // error – bitmap not compressible

       }

    Stranger things have happened…

  18. Worf says:

    @davidlmorris: I’m not sure why you’d want to see it, since full production quality would make it 10 times longer. Mostly in the error checking – there are many spots that Raymond skipped error checking on for conciseness.

    But if you must:

    * Check the return value of every API call, and decide how best to handle it

    * Validate that the buffer is big enough – the first post illustrates this – RLE encoding can make files larger, so all buffers have to be big enough. (I wouldn’t call it a nitpick, but a vital point when adapting the method for production).

    * Check the side effects of each API – does it modify some global/system state? If so, must you save/restore it?

    * Check parameters – anything that might get you in trouble like going up a directory tree inadvertently? Or sizes that don’t make sense? Or maybe unterminated strings?

    Alas, there’s probably some idiot out there that’s gonna use Raymond’s code as-is without making it production ready in a real live system…

  19. Me says:

    @Semi Essessi:

    "It’s clearly not one of those ‘we could fix it but it would break something else’ features either…"

    You know you’re just asking for a bracketed explanation for why it IS just such a feature to appear at the bottom of your comment, right? ;)

  20. Semi Essessi says:

    Thanks for taking the time to make this post, but it does seem out of date. A tutorial on how to use .png/.jpg compression with GDIPlus would be more useful today. libpng/jpeg can be daunting to newbies… I can remember. :)

    Still, this is a lot better than the X bad tutorials out there which show you how to load a subset of bitmap files yourself, the hard way.

    Like Xepol, I’ve always wondered why GDI didn’t come with a function like DWORD* LoadAnyFreakingBitmapIWant(LPSTR* path), returning an uncompressed RGB0/BGR0 array… as a rule you don’t want to read/store any headers or data which deviate from the standard for bitmpa files, so having the seperate functions is almost always of no benefit. If anything it just introduces more potential for error by the programmer and a steeper learning curve. It’s clearly not one of those "we could fix it but it would break something else" features either…

  21. Xepol says:

    @@acq -> I believe you miss the full scope of the problem.  Another 2 or 3 major releases of Windows following in the current trend will lead to a totally useless product so mired in past mistakes and compatibility fixes that forward movement will become near impossible.

    I do see a glimmer of hope from MS with attempts to virtualize compatibiltiy with older OS versions already.  MS needs to make the a major feature standard in all their OSes.  Want to run an XP/Vista/Win7/Win8 app?  Rather than being limited by Win#’s design and mistakes, the current OS fires up a virtualization layer that provides that environment.  This would free any current version of the OS to truely to improve and evolve.

    Personally, I can see a day when ALL apps run inside a virutalized sandbox regardless of whether they are targeted for a previous version of the OS or the current version.  Security, system stability, even cost of ownership can greatly benefit.

    A full transition would doubtlessly be very painful, but the benefits could be dramatic.

  22. streuth says:

    I probably ought to add that I’m just adding the last function to the median cut and error diffusion code. (Including I might add, the proper nth element algorithm, for median cut)

    Although it’s the natural progression from having a big pile of image readers, that’s not open source.

    Nevertheless it’d be nice if Microsoft offered such capabilities without the "COM" development overhead. (As Win32).

  23. streuth says:

    Oh man!

    This is the blog post from me, I’ve just *had* to do all this.

    Getting GDI to do compression for you is fine. Doing decompression is fine also. (or at least so it seems) The problem I had was that if I started with an optimal palette RLE bitmap, passed it into, and then back out of the DC, then I ended up with a functional RLE, but with a suboptimal palette.

    Getting control of that darned palette is the trouble.

    In the end I coded my own RLE algorithm, only took an hour!! (more like a day and a half with debug) :))

    Anyway, I’ve also integrated JPEG, PNG, and GIF into the shebang and made a DLL out of it. Being as the whole thing is open source I’m going to have to post the source anyhow.

    Am I allowed to post links here?

    No doubt there is a "Raymond" that you can do which makes it all work in ten seconds flat!!

    :slaps forehead:

  24. Alexandre Grigoriev says:

    @Semi Essessi:

    LoadImage/LR_LOADFROMFILE?

  25. Yuhong Bao says:

    "Our customers are constantly asking us to support formats like JPG, PNG and TIF, but never about RLE.

    As a matter of fact, when we tell them we support RLE, we usually just get a blank stare back."

    That is because RLE is not itself a file format, it is a compression algorithm used with other file formats like BMP.

Comments are closed.