Writing My Own DEFLATE From Scratch to Embed Data in a PNG

A one line project rule: no zlib, no third party compression libraries, turned into writing CRC32, Adler32, a bitstream packer, canonical Huffman coding, LZ77, and a full RFC 1951 DEFLATE encoder/decoder pair by hand, then using all of it to hide messages inside real PNG files. And how validating against a real zlib_decompress(). By Iman Atarof (imaarov).

Iman Atarof • imaarov

Computer Engineering student focused on systems programming, Linux, data compression, binary file formats and software written in C.

Updated July 27, 2026
54 views

Table of Contents

How It Started

A while back I got curious about something most people never think twice about: how sound turns into numbers. That curiosity led me down the PCM rabbit hole, and I ended up writing about it here: PCM: The DNA of Sound in Computers. Once I understood how ADC and DAC turn analog signals into bits and back, I wanted the next project to sit somewhere close to that same "how is this actually stored" territory.

That's how I landed on steganography. Not encryption, not compression, but the idea of hiding data inside other data so well that the file still looks and behaves completely normal. The concept alone was enough to hook me, and once I saw how simple the core trick is, I knew I wanted to build my own version in C, without leaning on any third-party library to do the heavy lifting for me.

What Is Steganography, Really

At its core, steganography is about hiding a message inside a file in a way that doesn't noticeably change the file. Unlike encryption, which scrambles data so it can't be read, steganography hides the fact that a secret exists at all. A photo with a hidden text message inside it still opens fine, still looks the same to the eye, and gives no visual clue that anything is different.

The technique I used across this project is called LSB steganography, short for Least Significant Bit. Every byte of raw data in a file, whether it's a pixel value or an audio sample, has a bit that matters the least to how that byte is perceived. Flip that one bit and a pixel's color shifts by a value so small the human eye can't tell. Flip it across thousands of bytes in sequence and you can smuggle an entire message through, one bit at a time.

The part I had to solve for every format was the same question: where exactly does the raw, embeddable data live in the file, and how do I get to it without corrupting the structure around it?

BMP: The Easy One

BMP was the natural starting point because it stores pixel data uncompressed. No algorithm sits between the raw bytes and the file, which made it the perfect first target to prove the LSB idea actually works.

#define BMP_HEADER_SIZE                   2
#define BMP_HEADER_SIGNATURE              0x424d
#define BMP_PIXEL_DATA_OFFSET_ADDRESS     10
#define BMP_PIXEL_DATA_ADDRESS_FIELD_SIZE 4
#define BMP_STEG_HEADER_SIZE              32
#define BMP_FILE_SIZE_FIELD_SIZE          4

bool encode_bmp(FILE *file, const char *secret_message);
char *decode_bmp(FILE *file);

Every file format follows a blueprint, a fixed structure that any valid file of that type must respect. BMP's blueprint starts with a two-byte signature that should always read 0x424d. Reading that first and comparing it against BMP_HEADER_SIGNATURE is the first sanity check: if it doesn't match, the file isn't a real BMP, or it's already corrupted, and there's no point going further.

A few bytes later, at a fixed offset, BMP stores a pointer of its own: BMP_PIXEL_DATA_OFFSET_ADDRESS tells you exactly where in the file the raw pixel bytes begin, and BMP_PIXEL_DATA_ADDRESS_FIELD_SIZE tells you how many bytes that pointer itself takes up. Read that value, jump to it, and you're standing right at the start of the raw pixel data with nothing but bytes ahead of you.

From there, embedding is mechanical: take each byte of the secret message, break it into 8 bits, and write one bit into the least significant bit of one pixel byte at a time. Decoding just reverses the process, but it needs one extra agreement between encoder and decoder: how do you know when to stop reading? My solution was to reserve a fixed-size field right after the starting point to store the length of the hidden message. Decoding means jumping to that same starting point, reading the length field first, then pulling exactly that many bytes worth of bits out of the pixel data.

WAV: Same Idea, Different Bytes

WAV followed the same logic as BMP with one meaningful difference: audio samples are usually stored as 16-bit values, meaning two bytes per sample, instead of the single byte per pixel channel that BMP uses.

That extra byte introduces endianness into the picture. Endianness is just the order in which a multi-byte value is stored in memory. In little-endian, the least significant byte comes first; in big-endian, it comes last. WAV samples are stored little-endian, so the byte that actually matters for LSB embedding, the one that changes the sample value the least when modified, is the first byte of every two-byte pair, not the second.

Once that detail is handled correctly, the rest is identical to BMP: locate the raw sample data, walk through it two bytes at a time, touch only the least significant byte of each sample, and move on to the next pair.

PNG: The Wall

After BMP and WAV, I assumed every format would follow the same pattern: find the raw data section, twiddle some bits, done. PNG broke that assumption completely.

Instead of a flat block of pixel bytes sitting in the file, PNG stores its pixel data inside one or more IDAT chunks, and that data is compressed using DEFLATE. On top of that, each chunk carries its own CRC32 checksum for integrity, and the compressed stream itself is wrapped in a zlib container that ends with an Adler-32 checksum over the decompressed data. There's no raw pixel byte to touch directly, only a compressed blob guarded by two different checksums.

That was the point where the project stopped being "find the bytes, flip a bit" and turned into something much closer to reverse-engineering a real compression format.

Deciding To Write DEFLATE From Scratch

The obvious move at that point was to link against zlib and let it handle compression and decompression. I decided against it on purpose. Using zlib would have reduced PNG to the same kind of exercise as BMP and WAV, and any future format I added later would follow the same shortcut. That felt like it defeated the point of the whole project, which was to actually understand these formats rather than just consume them through a library.

So I set out to implement DEFLATE myself, following RFC 1951, and Adler-32 as specified in RFC 1950, the zlib format. This turned out to be the hardest part of the entire project, by a wide margin. I went in thinking DEFLATE was one algorithm. It's actually three things working together: LZ77 for finding repeated sequences, canonical Huffman coding for compressing the symbols efficiently, and a bitstream layer that packs everything into a tight sequence of bits rather than clean byte boundaries. All three have to follow the RFC exactly, because the decoder on the other end, whether it's mine or a real PNG viewer, expects the encoded stream to obey the specification down to the bit.

Inside DEFLATE: Blocks, BTYPE and BFINAL

DEFLATE splits data into one or more blocks, and every block starts with a tiny three-bit header. The first bit is BFINAL: it tells the decoder whether this is the last block in the stream or whether more blocks follow. The next two bits are BTYPE, which describes how this particular block is encoded. There are three possibilities: stored with no compression at all, compressed with a fixed Huffman table that both encoder and decoder already agree on in advance, or compressed with a dynamic Huffman table that gets built and transmitted specifically for this block's data.

bitstream_write_bits_lsb(
    stream,
    process_bytes + block_size >= data_len ? BFINAL_LAST_BLOCK : BFINAL_NOT_LAST_BLOCK, 1);
bitstream_write_bits_lsb(stream, BTYPE_NO_COMPRESSION, 2);

The stored block type is the simplest and it's what I implemented first, mostly as a way to get a full, correct pipeline working end to end before worrying about actual compression. A stored block writes its length as a 16-bit value called LEN, immediately followed by the one's complement of that same value, called NLEN. The decoder reads both and checks that NLEN is really the bitwise inverse of LEN. If it isn't, something got corrupted or misaligned, and the decoder can catch that immediately instead of silently reading garbage.

One detail that's easy to miss on a first read of the RFC: after writing the three-bit block header, a stored block has to skip forward to the next byte boundary before writing LEN and NLEN, since those fields are always byte-aligned even though the header itself isn't. Miss that padding step and every stored block you write will be unreadable by any real DEFLATE decoder.

LZ77: Finding Repetition

The dynamic Huffman path is where actual compression happens, and it starts with LZ77. The idea behind LZ77 is straightforward: scan through the data looking for sequences that already appeared earlier, and instead of writing those bytes again, write a short reference back to where they occurred and how long the repeated run is. A literal byte gets encoded as itself, but a repeated run gets encoded as a length and a distance pointing backward into the data already processed.

This is why the decoder has to reconstruct output as it goes rather than decode everything and rearrange it afterward: a match's distance points into output that the decoder itself already produced a moment earlier.

if (distance > *out_size) {
    FATAL("back-reference distance exceeds decoded output so far");
    return false;
}
uint32_t start = *out_size - distance;
for (uint32_t k = 0; k < length; k++)
    if (!out_push(out, out_size, out_cap, (*out)[start + k]))
        return false;

That check matters more than it looks. A match distance that reaches further back than any data the decoder has produced so far is a sign of a corrupted or malformed stream, and trying to copy from it anyway would mean reading uninitialized memory.

Canonical Huffman and the Header Nobody Warns You About

Once LZ77 has turned the data into a sequence of literals and length/distance matches, those symbols still need to be encoded efficiently, and that's where Huffman coding comes in. DEFLATE specifically requires canonical Huffman codes, meaning the codes aren't built freely from a tree the way a textbook Huffman example usually shows them. Instead, codes are assigned in a fixed, predictable order based purely on code length and symbol value. This matters because it means the decoder can rebuild the exact same code table just from a list of code lengths, without needing the encoder to transmit the tree shape itself.

That's the part I underestimated going in. I assumed once I had LZ77 and a working Huffman implementation, I could just chain them together and call it done. What I hadn't accounted for is that a dynamic Huffman block has to carry its own header describing the code lengths it used, and that header has a structure of its own defined by the RFC:

  • HLIT tells the decoder how many literal and length codes are present, encoded as a 5-bit value offset by 257.
  • HDIST tells the decoder how many distance codes are present, encoded as a 5-bit value offset by 1.
  • HCLEN tells the decoder how many of the special code-length codes follow, encoded as a 4-bit value offset by 4.

The code-length codes are themselves compressed with a small Huffman table of their own, transmitted in a fixed, oddly-ordered sequence defined in the RFC rather than sequential order. On top of that, runs of identical or zero-length codes get run-length encoded using three special symbols, 16, 17 and 18, so a block of a hundred unused symbols doesn't need a hundred individual length entries.

bitstream_write_bits_lsb(stream, hlit_count - 257, 5);
bitstream_write_bits_lsb(stream, hdist_count > 0 ? hdist_count - 1 : 0, 5);
bitstream_write_bits_lsb(stream, hclen_count - 4, 4);

It's a header describing a header describing the actual codes, and every layer of it has to match the RFC exactly, or a real decoder somewhere else will read complete nonsense from a stream that looks perfectly valid to a casual glance.

Putting It Back Together: Decoding

Decoding walks the same structure in reverse. Read BFINAL and BTYPE, branch based on the block type, and if it's a dynamic block, read HLIT, HDIST and HCLEN first, then rebuild the code-length Huffman table, use it to decode the actual literal/length and distance code lengths, and finally reconstruct the canonical codes needed to read the real data.

int32_t hlit_raw  = bitstream_read_bits_lsb(reader, 5);
int32_t hdist_raw = bitstream_read_bits_lsb(reader, 5);
int32_t hclen_raw = bitstream_read_bits_lsb(reader, 4);

Once both code tables exist, decoding the body is a loop: read one Huffman symbol at a time. If it's a literal, push that byte to the output. If it's the end-of-block symbol, the block is finished. If it's a length code, read the extra bits that refine the exact match length, then read the paired distance code the same way, and copy that many bytes from earlier in the already-decoded output. This continues, block after block, until a block arrives with BFINAL set, at which point the whole stream is fully reconstructed.

Back To PNG: Chunks, CRC32 and Hiding the Message

With DEFLATE working, PNG itself became a matter of chunk bookkeeping. Every PNG chunk has the same four-part shape: a 4-byte length, a 4-byte type identifier like IHDR or IDAT, the chunk's data, and a 4-byte CRC32 checksum computed over the type and data together.

uint32_t crc_input_len = PNG_CHUNK_ID_SIZE + data_len;
byte *crc_input        = malloc(crc_input_len);
memcpy(crc_input, type, PNG_CHUNK_ID_SIZE);
if (data_len > 0)
    memcpy(crc_input + PNG_CHUNK_ID_SIZE, data, data_len);
uint32_t crc = crc32_calculate(crc_input, crc_input_len);

The IHDR chunk, which comes right after the signature, describes the image itself: width, height, color type, compression method, and so on. Reading it first and verifying its CRC is a good early check that the file is intact before doing anything more expensive like decompression.

The actual pixel data can be split across several IDAT chunks, so decoding means walking every chunk in the file, concatenating the payload of every IDAT chunk into one buffer, and skipping past everything else using the length field until the terminating IEND chunk is reached.

if (0 == strncmp(PNG_IDAT_CHUNK_ID, (char *)chunk_id, PNG_CHUNK_ID_SIZE)) {
    byte *grown = realloc(idat_data, idat_size + chunk_size);
    idat_data = grown;
    fread(idat_data + idat_size, sizeof(byte), chunk_size, file);
    idat_size += chunk_size;
    fseek(file, PNG_CRC_FIELD_SIZE, SEEK_CUR);
    continue;
}

Once every IDAT chunk has been collected, that combined buffer is what gets handed to the DEFLATE decoder, which unwraps the zlib container, verifies Adler-32 over the result, and hands back the raw, decompressed scanline data. That decompressed buffer is where the actual pixel bytes finally live, and it's exactly the kind of raw data that BMP handed over immediately, just several layers deeper.

Embedding a message follows the same LSB approach as before: flip the least significant bit of enough decompressed bytes to store the message length followed by the message itself. The one thing I flagged honestly in the code rather than pretending it wasn't there is that PNG scanlines are usually filtered, meaning each row of pixel data can be encoded relative to the row above it or the pixel before it, and my current implementation embeds directly into the filtered bytes rather than unfiltering first. It works because the LSB embedding survives the round trip, but it's on my list to fix properly since unfiltered data is the more correct place to hide bits without any risk of visibly disturbing a filtered row.

After the message is embedded, the modified data gets compressed again through my own DEFLATE encoder, wrapped back into a fresh zlib stream, and written out as a brand-new IDAT chunk with a freshly computed CRC32. Every other chunk in the original file gets copied through untouched, so the final PNG is byte-for-byte identical to the original except for the one chunk that now quietly carries a hidden message.

What I Took Away From This

Going in, I thought this project was about steganography. By the end, most of the actual work turned out to be about respecting file format specifications down to the last bit. BMP and WAV taught me how to navigate a file's structure. PNG taught me that "compressed" is doing a lot of hiding in that one word, and that a format described in a few pages of an RFC can take weeks to implement correctly once you refuse to shortcut it with an existing library.

The version of me that started this project thought LSB steganography was the hard part. It turned out to be the easiest five percent. The real difficulty was earning the right to reach the raw bytes in the first place, which meant building a working LZ77 matcher, a canonical Huffman encoder and decoder, a bit-level stream reader and writer, and a CRC32 and Adler-32 implementation, all cross-checked against RFC 1950 and RFC 1951 until real PNG viewers would open the files without complaint.

If you want to see how all of it fits together, or you're working through the same RFCs yourself and want another reference implementation to compare against, the full source is here: github.com/imaarov/steganov. There's still more to do, PNG filtering being the next thing on the list, and other formats I'd like to add once this foundation is solid. But for now, a message can travel inside a BMP, a WAV, or a PNG that I compressed myself, bit by bit, following the spec instead of a library, and that's exactly the kind of project I wanted this to be.