1-D Huffman encoding #1

New Issue

claunia · 2026-01-29T20:29:57Z

claunia commented

2026-01-29 20:29:57 +00:00

Originally created by @rupertwh on GitHub (Oct 29, 2024).

1-D Huffman-encoded BMPs

While v1.6.0 introduced reading Huffman encoded BMPs, I would consider it only a first crude draft.

It does work with the Huffman sample BMP from BMP Suite, but that also seems to be the only Huffman encoded BMP in the whole wide world. (Which kind of questions the utility of supporting the format in the first place).
Anyway, it exists and I want to support it. But information about the format is very scarce.

I will abuse this issue as a general information hub about Huffman-encoded BMPs.

The codes. Where are the codes?

Searching for the actual bit-sequences that make up the Huffman codes, you'll eventually end up on an archived version of a publication by Luong Chi Mai. Unfortunately, those tables contain a couple of typos. I assembled a corrected human-readable version of the codes in gen-huffman-codes.h
EDIT: Duh! They are available as part of ITU-T Rec. T.4 (Group 3 Fax specification)

Name and differentiation

Huffman, 1-D Huffman, Modified Huffman, 1-D Modified Huffman, CCITT Group 3, Fax g3, ... Are they all identical, similar, related?

Still not sure.

EOL, RTC

You might expect EOL ('000000000001') to end each scan line, but it doesn't. It starts each scan line.

RTC (return to control) is a series of 6 consecutive EOLs and marks the end of the image. Actually, it marks the end of the image transmission in the Group 3 Fax protocol. The sample BMP includes those 6 EOLs, but it seems unnecessary and according to FileFormat.Info it is not needed when saving the image data in a file (opposed to transmitting it to a fax machine).

The same article describes "TIFF Compression Type 2" as variant that stores neither EOLs nor RTC.

filler bits

filler 0's may be inserted immediately after a scan line before the EOL.

How long is EOL? Or, how short can it be?

EOL is a 12-bit code consisting of 11 zero-bits followed by a 1-bit. With additional filler-bits, it can essentially be any length.
But what about 8, 9, or 10 zeros followed by a one? 8/9/10 zeros can only be part of EOL; the otherwise longest run of zeros is 7.

What to make of it.

With all that said, it remains unclear what the actual file format for Huffman encoded BMPs should be.
For reading them, it's ok. What we currently do is:

Ignore EOL at the beginning of a line
consider any run of 8 or more zeros followed by a 1 as EOL
Ignore RTC

But for writing? Unclear.

Originally created by @rupertwh on GitHub (Oct 29, 2024). # 1-D Huffman-encoded BMPs While v1.6.0 introduced reading Huffman encoded BMPs, I would consider it only a first crude draft. It does work with the Huffman sample BMP from [BMP Suite](https://entropymine.com/jason/bmpsuite/), but that also seems to be the only Huffman encoded BMP in the whole wide world. (Which kind of questions the utility of supporting the format in the first place). Anyway, it exists and I want to support it. But information about the format is very scarce. I will abuse this issue as a general information hub about Huffman-encoded BMPs. ### The codes. Where are the codes? Searching for the actual bit-sequences that make up the Huffman codes, you'll eventually end up on an archived version of a publication by Luong Chi Mai. Unfortunately, those tables contain a couple of typos. I assembled a corrected human-readable version of the codes in [gen-huffman-codes.h](https://github.com/rupertwh/bmplib/blob/main/gen-huffman-codes.h) EDIT: Duh! They are available as part of [ITU-T Rec. T.4](https://www.itu.int/rec/dologin_pub.asp?lang=e&id=T-REC-T.4-200307-I!!PDF-E&type=items) (Group 3 Fax specification) ### Name and differentiation Huffman, 1-D Huffman, Modified Huffman, 1-D Modified Huffman, CCITT Group 3, Fax g3, ... Are they all identical, similar, related? Still not sure. ### EOL, RTC You might expect EOL ('000000000001') to end each scan line, but it doesn't. It starts each scan line. RTC (return to control) is a series of 6 consecutive EOLs and marks the end of the image. Actually, it marks the end of the image transmission in the Group 3 Fax protocol. The sample BMP includes those 6 EOLs, but it seems unnecessary and according to [FileFormat.Info](https://www.fileformat.info/mirror/egff/ch09_05.htm) it is not needed when saving the image data in a file (opposed to transmitting it to a fax machine). The same article describes "TIFF Compression Type 2" as variant that stores neither EOLs nor RTC. ### filler bits filler 0's may be inserted immediately after a scan line before the EOL. ### How long is EOL? Or, how short can it be? EOL is a 12-bit code consisting of 11 zero-bits followed by a 1-bit. With additional filler-bits, it can essentially be any length. But what about 8, 9, or 10 zeros followed by a one? 8/9/10 zeros can only be part of EOL; the otherwise longest run of zeros is 7. ## What to make of it. With all that said, it remains unclear what the actual file format for Huffman encoded BMPs should be. For reading them, it's ok. What we currently do is: - Ignore EOL at the beginning of a line - consider any run of 8 or more zeros followed by a 1 as EOL - Ignore RTC But for writing? Unclear.

claunia commented

2026-01-29 20:30:00 +00:00

@rupertwh commented on GitHub (Oct 30, 2024):

Makeup codes and terminating codes

There are four groups of codes: black / white terminating codes and black / white makeup codes.

A scanline always starts with a white code (of length 0 in case the first pixel actually has to be black) and then alternates black / white. Runs of up to 63 pixels are encoded with a single terminating code. Runs longer than that are encoded with a makeup code (with a value between 64 and 2560) preceding the terminating code.

Of course, it wasn't until after I was done with the first implementation that I discovered that for very long runs, there can be several makeup codes followed by one terminating code, which are all added up. (I had expected several makeup+terminating codes, interjected with 0-length runs of the other color.)

Result is the obvious afterthought of the "callagain" flag in huff_decode(), which was needed because the codes for one run don't necessarily fit into 32 bits anymore. So this will have to be redesigned. huff_decode() needs to be able to refill the bit buffer for long chains of makeup codes.

@rupertwh commented on GitHub (Oct 30, 2024): ### Makeup codes and terminating codes There are four groups of codes: black / white terminating codes and black / white makeup codes. A scanline always starts with a white code (of length 0 in case the first pixel actually has to be black) and then alternates black / white. Runs of up to 63 pixels are encoded with a single terminating code. Runs longer than that are encoded with a makeup code (with a value between 64 and 2560) preceding the terminating code. Of course, it wasn't until after I was done with the first implementation that I discovered that for very long runs, there can be several makeup codes followed by one terminating code, which are all added up. (I had expected several makeup+terminating codes, interjected with 0-length runs of the other color.) Result is the obvious afterthought of the "callagain" flag in huff_decode(), which was needed because the codes for one run don't necessarily fit into 32 bits anymore. So this will have to be redesigned. huff_decode() needs to be able to refill the bit buffer for long chains of makeup codes.

claunia commented

2026-01-29 20:30:04 +00:00

@peteroupc commented on GitHub (Nov 17, 2024):

Modified Huffman compression is a feature of OS/2 bitmaps (and icons and pointers), bitmaps which are largely based on the Windows format (compression code is BCA_HUFFMAN1D = 3).

I also suspect the meaning of "black" and "white" in this compression mode is reversed when OS/2 displays a bitmap or icon that uses this compression mode.

EDIT: But that may be because black is 0 and white is 1 in this compression scheme, rather than vice versa as is the convention I was thinking of. This was after I read the file format document you linked to.

@peteroupc commented on GitHub (Nov 17, 2024): Modified Huffman compression is a feature of OS/2 bitmaps (and [icons and pointers](https://github.com/peteroupc/classic-wallpaper/blob/main/desktopwallpaper.py#L1836)), bitmaps which are largely based on the Windows format (compression code is `BCA_HUFFMAN1D = 3`). I also suspect the meaning of "black" and "white" in this compression mode is reversed when OS/2 displays a bitmap or icon that uses this compression mode. EDIT: But that may be because black is 0 and white is 1 in this compression scheme, rather than vice versa as is the convention I was thinking of. This was after I read the file format document you linked to.

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: starred/bmplib#1