Learning Rust: Run-Length Encoding

11 min readAug 4, 2023

Curious about how our computing ancestors managed to compress the earliest images? Let’s explore the naïve technique they used, akin to the ‘byte-squeezing’ methods of a bygone era.

Images and computers have had a longstanding relationship. We’ve grown fond of storing and showcasing these images on our devices such as phones or computers. Numerous services have evolved around them to monetize their exchange and storage. Ultimately, an image is merely a series of pixels arranged in a precise order, producing beauty discernible by humans and, as of today, machines too.

Images demand a certain amount of storage space and network bandwidth for their transmission. In response to this, a variety of compression algorithms have been developed to decrease storage and transfer costs, albeit at the expense of some CPU processing power or slight degradation in image quality.

In this article, I’m set to delve into the simplest and most fundamental compression algorithm, one that was used in the early image format known as BMP. This piece will focus primarily on basic decryption and handling such a now-obsolete format.

The BMP format, as documented in the Microsoft Documentation and Wikipedia, supports multiple pixel encoding methods. However, this text will focus solely on BI_RLE8, a simple implementation of the Run-Length Encoding algorithm.

The RLE algorithm is built on the premise that some pixels repeat multiple times. For instance, rather than writing [255, 255, 255, 255, 255] to indicate five white pixels, you could simplify it to two bytes, [5, 255], indicating the repetition. In data containing numerous repetitions, this can significantly reduce the size.

According to the documentation, the BMP file start with the file header, followed by the info header. Both contain fundamental information such as height, width, pixel data offset and the compression method. To make this clearer, let’s take a look at these Rust structures:

use byteorder::{ByteOrder, LittleEndian};

#[derive(Debug)]
pub struct BitmapFileHeader {
    pub bf_type: u16,
    pub bf_size: u32,
    pub bf_reserved1: u16,
    pub bf_reserved2: u16,
    pub bf_off_bits: u32,
}

impl BitmapFileHeader {
    pub fn parse(data: &[u8]) -> Self {
        Self {
            bf_type: LittleEndian::read_u16(&data[0..2]),
            bf_size: LittleEndian::read_u32(&data[2..6]),
            bf_reserved1: LittleEndian::read_u16(&data[6..8]),
            bf_reserved2: LittleEndian::read_u16(&data[8..10]),
            bf_off_bits: LittleEndian::read_u32(&data[10..14]),
        }
    }
}

#[derive(Debug)]
pub struct BitmapInfoHeader {
    pub bi_size: u32,
    pub bi_width: i32,
    pub bi_height: i32,
    pub bi_planes: u16,
    pub bi_bit_count: u16,
    pub bi_compression: u32,
    pub bi_size_image: u32,
    pub bi_x_pels_per_meter: i32,
    pub bi_y_pels_per_meter: i32,
    pub bi_clr_used: u32,
    pub bi_clr_important: u32,
}

impl BitmapInfoHeader {
    pub fn parse(data: &[u8]) -> Self {
        BitmapInfoHeader {
            bi_size: LittleEndian::read_u32(&data[0..4]),
            bi_width: LittleEndian::read_i32(&data[4..8]),
            bi_height: LittleEndian::read_i32(&data[8..12]),
            bi_planes: LittleEndian::read_u16(&data[12..14]),
            bi_bit_count: LittleEndian::read_u16(&data[14..16]),
            bi_compression: LittleEndian::read_u32(&data[16..20]),
            bi_size_image: LittleEndian::read_u32(&data[20..24]),
            bi_x_pels_per_meter: LittleEndian::read_i32(&data[24..28]),
            bi_y_pels_per_meter: LittleEndian::read_i32(&data[28..32]),
            bi_clr_used: LittleEndian::read_u32(&data[32..36]),
            bi_clr_important: LittleEndian::read_u32(&data[36..40]),
        }
    }
}

In languages like C/C++, we could map memory directly to certain structs. In Rust, we may use the byteorder crate for LittleEndian processing. Both structures may be read directly from the file, as in the following code snippet:

pub async fn extract_metadata(file: &mut File) -> Result<(BitmapFileHeader, BitmapInfoHeader), std::io::Error> {
    let mut buffer: [u8; 2048] = [0; 2048];

    file.seek(SeekFrom::Start(0)).await?;
    file.read(&mut buffer).await?;

    let file_header = BitmapFileHeader::parse(&buffer[..]);
    let info_header = BitmapInfoHeader::parse(&buffer[0x0e..]);

    file.seek(SeekFrom::Start(file_header.bf_off_bits as u64)).await?;
    Ok((file_header, info_header))
}

Armed with the metadata, we can move directly to the pixels. For the purposes of this discussion, let’s assume we are dealing solely with BI_RLE8 compression and that all pixels are mapped directly, without the need for an intermediate color table. This assumption should typically hold true for grayscale images.

The metadata provides several crucial pieces of information:

bi_height and bi_width: these could theoretically take negative values
bi_compression: this should be set to BI_RLE8
bf_off_bits: this indicates the absolute position in the file where pixel data can be found

Once we load some pixel data from the specified offset, we can begin decoding RLE packets. In the simplified BI_RLE8, we can distinguish four types of packets:

Encoded: two bytes [x, y], where ‘x’ indicates the number of repetitions and ‘y’ specifies the value being repeated
Absolute: multiple bytes [0, n, b1..bn], where ’n’ reveals the number of bytes to be written without any encoding
EndOfLine: two bytes [0, 0], indicating that one row of data is complete and subsequent packets will represent a new row
EndOfBitmap: two bytes [0, 1], signaling that the entire dataset has been exhausted and no further data should be anticipated

Sounds simple, right? Not exactly. I also need to mention that each packet size must be a multiple of DWORD and additional padding might be introduced. This detail, alluded to rather indirectly in the documentation, took me a few hours to troubleshoot and confirm.

Another ambiguous aspect is the bottom-up encoding of rows. In other words, you’ll first see the last row, then the penultimate one, and so on, with the first row showing up last. This arrangement can make the processing of large images somewhat challenging. We will address this issue towards the end of this piece.

Decoding packets is not overly complex; it merely requires adherence to certain predefined rules. The implementation example in the following listing is designed for clarity. I purposely created an intermediate struct for demonstration and troubleshooting. If this were written in C/C++, you might see less abstraction and more of a buffer-to-buffer approach.

#[derive(Debug)]
pub enum RlePacket<'a> {
    Encoded { count: usize, value: u8 },
    Absolute { data: Cow<'a, [u8]> },
    EndOfLine,
    EndOfBitmap,
}

impl<'a> RlePacket<'a> {
    pub fn decode<'b>(source: &'b [u8]) -> Option<RlePacket<'b>> {
        if source.len() < 2 {
            return None;
        }

        if source[0] > 0 {
            return Some(RlePacket::Encoded {
                count: source[0] as usize,
                value: source[1],
            });
        }

        if source[1] == 0 {
            return Some(RlePacket::EndOfLine);
        }

        if source[1] == 1 {
            return Some(RlePacket::EndOfBitmap);
        }

        if source[1] > 0 && source.len() >= 2 + source[1] as usize {
            return Some(RlePacket::Absolute {
                data: Cow::Borrowed(&source[2..2 + source[1] as usize]),
            });
        }

        None
    }
}

The code decodes a single packet in the byte slice. If the slice is too small or incomplete, it returns None. The Absolute variant holds the values using the Cow (Copy on Write) pattern. This pattern is generally used when data may be borrowed or owned, depending on the context. We borrow the data in this first listing, which is a more efficient operation than copying it right away.

We can add some helper functions to facilitate operations on the struct, such as determining the length of the packet size or the size of the data within the packet. We can also create an owned version of the packet or decompress it to a buffer.

impl<'a> RlePacket<'a> {
    fn from<'b>(packet: &RlePacket<'a>) -> RlePacket<'b> {
        match packet {
            Self::Encoded { count, value } => RlePacket::Encoded {
                count: *count,
                value: *value,
            },
            Self::Absolute { data } => RlePacket::Absolute {
                data: Cow::Owned(data.to_vec()),
            },
            Self::EndOfLine => RlePacket::EndOfLine,
            Self::EndOfBitmap => RlePacket::EndOfBitmap,
        }
    }

    pub fn data_size(&self) -> usize {
        match self {
            Self::Encoded { count, value: _value } => *count,
            Self::Absolute { data } => data.len(),
            _ => 0,
        }
    }

    pub fn packet_size(&self) -> usize {
        match self {
            Self::Absolute { data } => 2 + data.len() + (data.len() % 2),
            _ => 2,
        }
    }

    pub fn write(&'a self, buf: &mut ReadBuf<'_>) -> Option<usize> {
        match self {
            Self::Absolute { data } if buf.remaining() >= data.len() => {
                match data {
                    Cow::Borrowed(data) => buf.put_slice(data),
                    Cow::Owned(data) => buf.put_slice(&data),
                }
                Some(data.len())
            }
            Self::Encoded { count, value } if buf.remaining() >= *count => {
                let data = vec![*value; *count];
                buf.put_slice(&data);
                Some(*count)
            }
            Self::EndOfLine | Self::EndOfBitmap => Some(0),
            _ => None,
        }
    }
}

The next layer of abstraction is the RLE Decoder. This struct maintains an asynchronous data stream and both headers. It keeps an internal buffer and can fetch more data, decoding all the packets from the buffer, subsequently emptying the buffer and advancing all the pointers.

#[derive(Debug)]
pub struct RleDecoder<TSource: AsyncRead + Sized + Unpin> {
    source: TSource,
    file_header: BitmapFileHeader,
    info_header: BitmapInfoHeader,
    buffer: Vec<u8>,
    position: usize,
    start: usize,
    end: usize,
}

impl<TSource: AsyncRead + Unpin> RleDecoder<TSource> {
    async fn fetch(&mut self) -> Result<(), RleDecoderError> {
        if self.start > self.buffer.len() / 2 {
            self.buffer.copy_within(self.start..self.end, 0);
            self.end -= self.start;
            self.start = 0;
        }

        self.end += match self.source.read(&mut self.buffer[self.end..]).await {
            Ok(count) => count,
            Err(error) => return Err(RleDecoderError::IO(error)),
        };

        Ok(())
    }

    async fn fill<'a>(&'a mut self, packets: &mut Vec<RlePacket<'a>>) {
        loop {
            let buffer = &self.buffer[self.start..self.end];
            let packet = RlePacket::decode(buffer);

            if let Some(packet) = packet {
                self.start += packet.packet_size();
                self.position += packet.data_size();

                packets.push(packet);
                continue;
            }

            break;
        }
    }

    pub async fn next_packets<'a>(&'a mut self) -> Result<Vec<RlePacket<'a>>, RleDecoderError> {
        let mut packets = Vec::new();

        self.fetch().await?;
        self.fill(&mut packets).await;

        Ok(packets)
    }
}

Currently, we’ll only work with asynchronous files. Let’s add more code to facilitate this:

impl RleDecoder<File> {
    fn from(source: File, file_header: BitmapFileHeader, info_header: BitmapInfoHeader) -> Self {
        Self {
            source: source,
            buffer: vec![0; 65536],
            file_header: file_header,
            info_header: info_header,
            position: 0,
            start: 0,
            end: 0,
        }
    }

    pub async fn file(name: &str) -> Result<Self, std::io::Error> {
        let mut file = File::open(name).await?;
        let (file_header, info_header) = extract_metadata(&mut file).await?;

        Ok(RleDecoder::from(file, file_header, info_header))
    }

    pub async fn seek(&mut self, offset: usize) -> Result<(), std::io::Error> {
        self.source.seek(SeekFrom::Start(offset as u64)).await?;
        self.position = offset - self.file_header.bf_off_bits as usize;

        self.start = 0;
        self.end = 0;

        Ok(())
    }
}

Now, let’s put the code into action. Consider a simple BMP image, encoded with RLE, comprised solely of 25 black or white pixels.

Our task is to traverse through each pixel’s data and decode it. The following code snippet accomplishes this:

use futures::stream::{unfold, StreamExt};

pub async fn decode_packets<'a>(
    decoder: &'a mut RleDecoder<File>,
) -> Result<Pin<Box<impl futures::Stream<Item = RlePacket>>>, RleDecoderError> {
    let data = unfold(decoder, |decoder| async {
        let packets = decoder.next_packets().await.unwrap();
        let mut cloned = Vec::with_capacity(packets.len());

        for packet in &packets {
            cloned.push(RlePacket::from(packet));
        }

        if packets.is_empty() {
            None
        } else {
            Some((cloned, decoder))
        }
    });

    Ok(Box::pin(data.flat_map(|packets| futures::stream::iter(packets))))
}

pub async fn handle_packets(name: &str) -> Result<(), Box<dyn std::error::Error>> {
    let mut decoder: RleDecoder<File> = RleDecoder::file(name).await?;
    let mut packets = decode_packets(&mut decoder).await?;
    let mut packets = packets.as_mut();

    while let Some(packet) = packets.next().await {
        println!("{:?}", packet);
    }

    Ok(())
}

This code generates a stream of packets from the decoder we created earlier. Due to the returned packets being tied to the mutable decoder’s buffer slice, we need to convert them into an owned version. This conversion enables us to pass the decoder to the next state of the unfold function without any hindrance.

Get Adrian Macal’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Upon executing this code, we expect an output similar to:

Encoded { count: 5, value: 0 }
EndOfLine
Encoded { count: 4, value: 255 }
Encoded { count: 1, value: 0 }
EndOfLine
Encoded { count: 3, value: 255 }
Encoded { count: 1, value: 0 }
Encoded { count: 1, value: 255 }
EndOfLine
Absolute { data: [255, 255, 0, 255, 255] }
EndOfLine
Encoded { count: 1, value: 255 }
Encoded { count: 1, value: 0 }
Encoded { count: 3, value: 255 }
EndOfBitmap

This output adheres to the specified format in the documentation. Importantly, please note that the lines are encoded from the bottom, moving upwards. The specific representation is as follows:

1st line: 5 black pixels
2nd line: 4 white and 1 black
3rd line: 3 white, 1 black, and 1 white
4th line: 2 white, 1 black, and 2 white
5th line: 1 white, 1 black, and 3 white

Our next test is to exclusively output row information. This addresses the bottom-up encoding problem inherent in bitmap images. The upcoming code introduces a structure that holds an index within the BMP file, indicating where a line starts, and another index within the output matrix, signifying where the binary line should be placed.

#[derive(Debug, Default, Clone)]
pub struct BitmapRow {
    pub bitmap_line: usize,
    pub source_offset: usize,
    pub target_offset: usize,
}

pub async fn decode_rows(decoder: &mut RleDecoder<File>) -> Result<Vec<BitmapRow>, RleDecoderError> {
    let mut counter = 0;
    let mut offset = decoder.file_header.bf_off_bits as usize;

    let mut prev = decoder.file_header.bf_off_bits as usize;
    let mut indices = vec![BitmapRow::default(); decoder.info_header.bi_height as usize];

    let mut streaming = true;
    let height = decoder.info_header.bi_height as usize;
    let width = decoder.info_header.bi_width as usize;

    while streaming  {
        for packet in decoder.next_packets().await? {
            offset += packet.packet_size();

            if let RlePacket::EndOfLine | RlePacket::EndOfBitmap = packet {
                counter += 1;
                indices[height - counter] = BitmapRow {
                    source_offset: prev,
                    bitmap_line: height - counter,
                    target_offset: (height - counter) * width,
                };
                prev = offset;
            }

            if let RlePacket::EndOfBitmap = packet {
                streaming = false;
            }
        }
    }

    Ok(indices)
}

pub async fn handle_rows(name: &str) -> Result<(), Box<dyn std::error::Error>> {
    let mut decoder: RleDecoder<File> = RleDecoder::file(name).await?;
    let rows = decode_rows(&mut decoder).await?;

    for row in &rows {
        println!("{:?}", row);
    }

    Ok(())
}

The function streams all packets and, when it encounters an EndOfLine or EndOfBitmap marker, it generates an output in the vector at the correct position. The final function simply prints this output.

When you run this, you should see something similar to the following:

BitmapRow { bitmap_line: 0, source_offset: 1190, target_offset: 0 }
BitmapRow { bitmap_line: 1, source_offset: 1180, target_offset: 5 }
BitmapRow { bitmap_line: 2, source_offset: 1172, target_offset: 10 }
BitmapRow { bitmap_line: 3, source_offset: 1166, target_offset: 15 }
BitmapRow { bitmap_line: 4, source_offset: 1162, target_offset: 20 }

Why do we care about these lines? The next step in our exploration is to output all pixels in a raw format that can be opened by software like GIMP. The raw format we’re interested in has a .data extension and contains only pixel data, devoid of any metadata. The pixels need to be arranged as a human would view them: from top to bottom, and left to right.

With a small image, one could load it into memory and simply copy the appropriate slices. But for the sake of a challenge, let’s try to avoid unnecessary memory usage. Instead, let’s aim to process even large images, such as a NASA image converted to a size of 14559 x 848 and 125MB, using only a fixed amount of memory. The ideal solution should utilize just a few megabytes.

To achieve this, we’ll employ a two-pass approach. The first pass reads the image and extracts line ending markers, just like in our earlier example, resulting in a small vector. The second pass sequentially creates a file, jumping to the correct offsets in the source file as it writes. Simple, isn’t it?

Here’s the code to implement this:

pub async fn handle_data(name: &str, outcome: &str) -> Result<(), Box<dyn std::error::Error>> {
    let mut decoder: RleDecoder<File> = RleDecoder::file(name).await?;
    let rows = decode_rows(&mut decoder).await?;

    let mut buffer = vec![0; decoder.info_header.bi_width as usize];
    let mut buffer = ReadBuf::new(&mut buffer);

    let mut streaming;
    let mut outcome = File::create(outcome).await?;

    for row in &rows {
        streaming = true;
        decoder.seek(row.source_offset).await?;

        println!("{:?}", row);

        while streaming {
            for packet in decoder.next_packets().await? {
                if let RlePacket::EndOfLine | RlePacket::EndOfBitmap = packet {
                    streaming = false;
                    break;
                }

                packet.write(&mut buffer);
            }
        }

        outcome.write_all(buffer.filled()).await?;
        buffer.clear();
    }

    Ok(())
}

The code performs as expected. An interesting observation during this exercise was that all images I worked with took up roughly the same storage space post-decompression as they did when compressed. This implies that RLE compression didn’t add significant storage efficiency in these instances.

I’m not sure about you, but I had a great time unraveling the intricacies of RLE. The journey started with understanding what RLE actually is and where it finds practical application. The initial phase involved getting to grips with how packets are encoded. Plenty of hours went into figuring out why certain things didn’t work as expected. The documentation had the answers, albeit not as explicitly as one might hope.

In the end, we successfully wrote Rust code to delve into these concepts in detail, examining various aspects and even creating a converter that can decode an entire BMP file into another one.

If you’re interested in seeing the working code, feel free to visit the following link: https://github.com/amacal/learning-rust/tree/bmp-rle

Level Up Coding

Learning Rust: Run-Length Encoding

Get Adrian Macal’s stories in your inbox

Level Up Coding

Written by Adrian Macal

Published in Level Up Coding

No responses yet

More from Adrian Macal and Level Up Coding

Dev Containers in CI/CD

Is your CI/CD pipeline running exactly the same code as your local environment? See what you can do to avoid CI/CD drift.

Did Stanford Just Kill ChatGPT? I Looked. Here’s the Truth.

Did Stanford just release something that destroys ChatGPT, Claude and Gemini? Because that’s what I’m seeing everywhere online.

The Collapse Of Software Engineering And The Beginning Of Something New

“It was never about coding” is a lie

Learning Rust: Parsing big XML files

Cracking the XML Giant: How to Explore Large XML Files in Seconds, Not Hours.

Recommended from Medium

AWS Just Put DuckDB Inside PostgreSQL. Data Engineers Have Some Rethinking to Do.

If you’ve built more than a couple of data pipelines, you’ve built this one before. Your orders live in Postgres. Three years of history…

Prompting Is Now the Slowest, Buggiest Way to Code with AI. Here’s the Fast, Clean One

Forget clever prompts. Here’s the ultimate hands-on guide to AI coding productivity, with insights you won’t find anywhere else

Understanding Rust’s memory ownership, references, borrowing and lifetimes

Learning about how Rust manages memory

Rust Is Building a New Foundation for Local AI Inference

Local AI is becoming more than a way to avoid cloud subscriptions. Rust projects are exploring how to make model inference more efficient…

Learning Rust #2 — My Code Works, So Why Is Rust Still Complaining?

How a small naming warning led me to Rust’s lint system, compiler diagnostics, and the strange fact that a warning can become an error.

6 Rust Changes That Could Make the Compiler Feel Like a Teammate

Smarter borrowing, clearer ownership, and faster builds: what is coming, what is only an experiment, and what to watch