Demilade Sonuga's blog

All posts

Drawing Bitmaps II

2022-12-15

The bitmaps we're going to be working with consist of 4 sections:

  1. The bitmap file header
  2. The DIB header
  3. The color table, and
  4. The pixel array

At this point, we have our block.bmp file as a slice of bytes in our code. But it's not just a slice of bytes; bytes at specific positions have a definite meaning. We encode this meaning with the type system.

We start with the first section of the BMP file: the bitmap file header. In a previous post, we looked at the structure of the BMP file and the meaning of the bytes at different offsets. For the bitmap file header, the bytes 0..2 (0 and 1) are always the numbers 0x42 and 0x4d which means "BM" in ASCII.

To start pinning this down in our code, create a new file bitmap.rs and throw this in:

// The first section of a file in the BMP file format
#[repr(C)]
pub struct FileHeader {
    // The first 2 bytes in the file which are always 0x42 and 0x4d, "BM" in ASCII
    pub bmp_id: [u8; 2],
}

We add the #[repr(C)] at the top there so the compiler won't reorder the fields (for a reminder of why go to this post). The pub keyword is used to make items visible outside the module. We're doing this because we're only going to be using them outside.

The bmp_id field itself is just an array of 2 unsigned 8-bit integers (1 byte == 8 bits).

The bytes at offset 2..6 (2, 3, 4, and 5) are defined by the BMP format to be the size of the whole BMP file in bytes. This is a 4-byte number and 4 bytes == 4 * 8 bits == 32 bits. So, this is a 32-bit number. The size of the file can't possibly be negative, so this must be an unsigned 32-bit integer.

#[repr(C)]
pub struct FileHeader {
    pub bmp_id: [u8; 2],
    // The size of the whole BMP file in bytes
    pub file_size: u32,
}

Next on the list are bytes 6..10 (6, 7, 8, and 9 (4 bytes)). These bytes are reserved:

#[repr(C)]
pub struct FileHeader {
    pub bmp_id: [u8; 2],
    pub file_size: u32,
    // These bytes are reserved
    reserved: [u8; 4],
}

The reserved field isn't public because we know for sure that we'll never need to use it outside.

The last field in the bitmap file header is the pixel array's offset into the file. These are the bytes 10..14 (10, 11, 12, and 13). This is a 4-byte number and far as I know, I don't think this number can be negative. So, this must be an unsigned 32-bit integer:

#[repr(C)]
pub struct FileHeader {
    pub bmp_id: [u8; 2],
    pub file_size: u32,
    pub reserved: [u8; 4],
    // The offset into the file of the starting byte of the bitmap pixel array
    pub pixel_array_offset: u32
}

Now, we have a complete model of the bitmap file header in code which we can use to interpret the first 14 bytes of block.bmp's bits.

Next on the list, we have the DIB header.

// Gives some information about the BMP file
#[repr(C)]
pub struct DIBHeader {
    
}

The first field in the header is the size of the DIB header itself in bytes. It's at offset 0..4 (0, 1, 2, and 3). It's 4 bytes in size and the value can't be negative, so it must be an unsigned 32-bit integer.

// Gives some information about the BMP file
#[repr(C)]
pub struct DIBHeader {
    // The size of the DIB header itself
    pub size_of_self: u32,
}

The next is the width of the image. This is also a 4-byte value, which can't be negative.

#[repr(C)]
pub struct DIBHeader {
    pub size_of_self: u32,
    // The width of the image
    pub image_width: u32,
}

Another 4-byte value; the image height:

#[repr(C)]
pub struct DIBHeader {
    pub size_of_self: u32,
    pub image_width: u32,
    // The height of the image
    pub image_height: u32,
}

The next on the list is a "number that is always 1". The bytes: 12..14 (12 and 13). This is a 2-byte value and 2 * 8 == 16. So, this is a 16-bit value. The number is always 1, so it's unsigned.

#[repr(C)]
pub struct DIBHeader {
    pub size_of_self: u32,
    pub image_width: u32,
    pub image_height: u32,
    // A number that is always 1
    pub always_1: u16,
}

The bytes 14..16 (14 and 15) represent the number of bits used to define a single pixel. The possible values are 1, 4, 8, 16, 24, and 32. But in our code, we'll be assuming that it will always be 8.

#[repr(C)]
pub struct DIBHeader {
    pub size_of_self: u32,
    pub image_width: u32,
    pub image_height: u32,
    pub always_1: u16,
    // The number of bits used to define a single pixel in the
    // bitmap's pixel array.
    // This representation of the bitmap assumes that the value is always 8
    pub bits_per_pixel: u16,
}

Bytes 16..120 (104 bytes) are a bunch of fields we aren't going to use and immediately after that are 4 reserved bytes:

#[repr(C)]
pub struct DIBHeader {
    pub size_of_self: u32,
    pub image_width: u32,
    pub image_height: u32,
    pub always_1: u16,
    pub bits_per_pixel: u16,
    // We aren't going to use these fields
    pub unneeded1: [u8; 104],
    // These bytes are reserved
    reserved: [u8; 4]
}

That's it for our DIB header. The color table is the next section in the file. This color table is simply an array of colors. The length is at most 2^n, where n == the number of bits per pixel. So, if the number of bits per pixel is 1, then there can only be 2 colors (because 1 bit can have only one of 2 values). In this project, the number of bits per pixel is assumed to always be 8, and the color table length -- 2^8 == 256.

Each color is a 32-bit value, whose first 8 bits represent the blue color intensity, the second 8 bits represent the green color intensity, the third 8 bits represent the red color intensity and the last 8 bits are reserved. In other words:

// A color in the color table
#[repr(C)]
pub struct Color {
    // The blue intensity of the color
    pub blue: u8,
    // The green intensity of the color
    pub green: u8,
    // The red intensity of the color
    pub red: u8,
    // These bits are reserved
    reserved: u8
}

The color table, in our case, is just an array of 256 of these colors:

#[repr(transparent)]
pub struct ColorTable(pub [Color; 256]);

If you can't remember, the #[repr(transparent)] attribute tells the compiler that the way a struct is represented in memory is the way its sole field is represented. This was mentioned in the 5th Graphics Output Protocol post when we were modeling the screen.

After the color table comes the pixel array. It's this array that contains the data which describes the colors of the image row by row. Some bitmaps, rather than using a color table, put the colors used directly into the pixel array, so the pixel array will be an array of Colors. But in this project, we'll be assuming that the pixel array will always be an array of 8-bit values which are indexes into the color table. So color_table[pixel_array[0]] will be the color of the 0th element in the pixel array.

The pixel array is actually a 2D array because it describes the colors of the image in a row-by-row manner. So, its definition is supposed to be something like [[u8; image width]; image height]. But the problem is, we don't know the width or height (okay, we do but hardcoding it will be a bad idea) of the image until runtime when we read it from the DIBHeader, so we have to leave it as just a bunch of bytes.

In the previous post, we outlined 2 steps to get our bitmap on screen:

  1. Get the block's bits into our code.
  2. Get the colors described by the pixel array on the screen.

With our new models for interpreting bits, step 2 should be a lot easier now. To proceed from this point, we ask ourselves a few questions. How exactly do we get the colors described by the pixel array on the screen? Well, the pixel array is a sequence of bytes and this sequence of bytes describes the colors of the image row by row, from the bottom to the top. And from the bottom to the top, I mean the first row of the image is the last row described in the pixel array and the second row of the image is the second to the last row described in the pixel array, and so on.

Okay, but how exactly does this pixel array describe the colors? Well, each byte is an index in the color table and each value in this color table describes the red, blue, and green intensity of a color.

Okay, but how do we know when a row in the pixel array has ended, since the pixel array itself is just a sequence of bytes? Well, the pixel array describes the colors of the image in a row-by-row manner. But just what exactly is a row? What exactly do I mean by "in a row-by-row manner"? Okay, well, the image can be divided into tiny squares of colors -- pixels. The image itself has a width and a height. And the width of an image is just the number of these pixels, or color values, which fit in one row of the image and the height is the number of these color values that fit in a single column of the image. So, "row-by-row manner" means that the pixel array, taken image width bytes at a time, describes a single row of the image, from the image's last row to the image's first row. Or in other words:

Pixel array:

[0, 2, 3, 4, 5, 6, 1, 23]

If the above is the pixel array for some image and this image has an image width of 4, then the bytes [5, 6, 1, 23] describe the first row of the image and the bytes [0, 2, 3, 4] describe the last row of the image. The image also has a height of 2, which is apparent from the fact that there are only 2 rows.

From this information, a definite procedure of how to draw the bitmap on screen is becoming clear. You should think about this yourself and how you'll pin it down in code before reading on.

Our procedure:

  1. Interpret the image bytes using the structs we laid down.
  2. Loop over the pixel array image width at a time, from the last bytes upwards.
  3. In each iteration of step 2, retrieve the index values in a row, convert them to the pixel values the screen is expecting and put them on screen.

First, we import the structs from bitmap.rs in main.rs:

#![no_std]
#![no_main]
#![feature(abi_efiapi)]

mod font;
use font::FONT;

mod uefi;
use uefi::{SystemTable, Screen, PixelFormat, pre_graphics_print_str, print_str};

// NEW:
mod bitmap;
use bitmap::{FileHeader, DIBHeader, ColorTable, Color};

We begin with step 1:

#[no_mangle]
extern "efiapi" fn efi_main(
    handle: *const core::ffi::c_void,
    sys_table: *mut SystemTable,
) -> usize {
    // ... Others

    let screen = framebuffer_base as *mut Screen;
    
    let screen = unsafe { &mut *screen };

    let block_bytes = include_bytes!("./block.bmp");

    // Retrieving a pointer to the block.bmp's bytes
    let block_bytes_ptr: *const u8 = block_bytes.as_ptr();

    // Reinterpreting a pointer to bytes as a pointer to a FileHeader instance
    let file_header_ptr = block_bytes_ptr as *const FileHeader;

    // Interpreting the first section of the bitmap as the file header
    let file_header = unsafe { &(*file_header_ptr) };

    // The number of bytes that make up the FileHeader
    const FILE_HEADER_SIZE: usize = core::mem::size_of::<FileHeader>();

    // The DIB header comes immediately after the file header
    const DIB_HEADER_OFFSET: isize = FILE_HEADER_SIZE as isize;

    // Reinterpreting a pointer to the bytes at offset DIB_HEADER_OFFSET
    // as a pointer to the DIB header
    let dib_header_ptr = unsafe { block_bytes_ptr.offset(DIB_HEADER_OFFSET) as *const DIBHeader };

    // Interpreting the second section of the bitmap as the DIB header
    let dib_header = unsafe { &(*dib_header_ptr) };

    // The number of bytes that make up the DIB header
    const DIB_HEADER_SIZE: usize = core::mem::size_of::<DIBHeader>();

    // The color table comes immediately after the file header and the DIB header
    const COLOR_TABLE_OFFSET: isize = (FILE_HEADER_SIZE + DIB_HEADER_SIZE) as isize;

    // Reinterpreting a pointer to the bytes at offset COLOR_TABLE_OFFSET as a pointer
    // to the color table
    let color_table_ptr = unsafe { block_bytes_ptr.offset(COLOR_TABLE_OFFSET) as *const ColorTable };

    // Interpreting the bytes at `COLOR_TABLE_OFFSET` as the color table
    let color_table = unsafe { &(*color_table_ptr) };

    0
}

In the above code, we first retrieve a pointer to the image's bytes by using the slice's as_ptr function. This pointer is then cast as a pointer to FileHeader, telling the compiler "The values behind this pointer aren't just bytes; they're FileHeaders". The pointer is then dereferenced (which is an unsafe operation because it's a raw pointer), and a reference is taken to the underlying bytes. So, file_header now holds a reference to FileHeader which can be used safely.

The DIB_HEADER_OFFSET is just the size of the file header because it comes immediately after the file header in the BMP file format. The raw pointer's offset function is used to retrieve a pointer to the bytes at DIB_HEADER_OFFSET from the bitmap's starting address. This function is marked as an unsafe function, so we have to use an unsafe block to call it. This pointer, too, is then cast as a pointer to DIBHeader and a reference is taken.

The same is done again with the color table. Since the color table comes immediately after the DIB header, its starting address will be at an offset of file header size + DIB header size into the file.

All that's left now is the pixel array, but before we get to that, let's first do some sanity checks.

According to the BMP file format, the first 2 bytes in the file header are always 0x42 and 0x4d. Let's make sure we're on the right track.

#[no_mangle]
extern "efiapi" fn efi_main(
    handle: *const core::ffi::c_void,
    sys_table: *mut SystemTable,
) -> usize {
    // ... Others
    let color_table_ptr = unsafe { block_bytes_ptr.offset(COLOR_TABLE_OFFSET) as *const ColorTable };
    let color_table = unsafe { &(*color_table_ptr) };

    // NEW:
    print_str(screen, "The first 2 bytes in the file header:");
    printint(file_header.bmp_id[0] as u32); // THIS DOESN'T EXIST
    print_str(screen, " ");
    printint(file_header.bmp_id[1] as u32); // THIS DOESN'T EXIST

    0
}

To run this, we need a printint function. If you can remember, we have already created such a function, but that function makes use of the Simple Text Output's output_string, which we can no longer use because we're in a graphic mode. To print out numbers on the screen now, we need a new printint function and we need to add descriptions of numbers to our font.

We can go on and do this now, but that's not warranted (at the moment). Right now, we just want to check if the first 2 bytes of the file header are what we expect them to be. Now, modify your code like so:

#[no_mangle]
extern "efiapi" fn efi_main(
    handle: *const core::ffi::c_void,
    sys_table: *mut SystemTable,
) -> usize {
    // ... Others
    let color_table_ptr = unsafe { block_bytes_ptr.offset(COLOR_TABLE_OFFSET) as *const ColorTable };
    let color_table = unsafe { &(*color_table_ptr) };

    /* DELETED:
    print_str(screen, "The first 2 bytes in the file header:");
    printint(file_header.bmp_id[0] as u32);
    print_str(screen, " ");
    printint(file_header.bmp_id[1] as u32);
    */

    // NEW:
    if file_header.bmp_id[0] == 0x42 && file_header.bmp_id[1] == 0x4d {
        print_str(screen, "The first two bytes are as expected");
    } else {
        print_str(screen, "Something is wrong somewhere");
    }

    0
}

Notice that the first print_str is taking "The first two bytes are as expected" and not "The first 2 bytes are as expected". This is, again, because we don't have descriptions of numbers in our font.

Upon building and running, we have:

First Two Bytes as Expected

Okay. Those two bytes are what we expected. Now, let's do another check: the width of the block is 36 and the height is 16. Let's see if our DIB header has what we expect.

#[no_mangle]
extern "efiapi" fn efi_main(
    handle: *const core::ffi::c_void,
    sys_table: *mut SystemTable,
) -> usize {
    // ... Others
    let color_table_ptr = unsafe { block_bytes_ptr.offset(COLOR_TABLE_OFFSET) as *const ColorTable };
    let color_table = unsafe { &(*color_table_ptr) };

    /* DELETED:
    if file_header.bmp_id[0] == 0x42 && file_header.bmp_id[1] == 0x4d {
        print_str(screen, "The first two bytes are as expected");
    } else {
        print_str(screen, "Something is wrong somewhere");
    }
    */

    // NEW:
    if dib_header.image_width == 36 && dib_header.image_height == 16 {
        print_str(screen, "Width and height as expected");
    } else {
        print_str(screen, "Something wrong somewhere");
    }

    0
}

Upon building and running you should get:

Something Wrong Somewhere

The image width and height are not as expected. To understand why we need to go back to the topic of data layout. You can revisit this post for a refresher. The #[repr(C)] attribute is used on the struct to indicate that the compiler should handle the struct the way C does. We've been using this attribute because C doesn't reorder struct fields, meanwhile, Rust does, and the order of the fields matters here because the file formats and the specs we've used so far have dictated that certain fields should be at specific offsets.

One more thing we didn't cover about the way C handles structs is that while C doesn't reorder fields, it still stuffs padding where needed for alignment.

Take a look at the FileHeader definition:

#[repr(C)]
pub struct FileHeader {
    pub bmp_id: [u8; 2],
    pub file_size: u32,
    reserved: [u8; 4],
    pub pixel_array_offset: u32
}

According to the alignment rules, file_size's address must be a multiple of 4, because file_size's alignment is 4. Because of this requirement, 2 bytes of padding are added after bmp_id to ensure the alignment requirements are satisfied. The pixel_array_offset, too, has an alignment of 4, but the padding isn't added before it because, with the insertion of the first padding, its offset from the struct's starting position is already a multiple of 4.

After these padding modifications, our struct ends up looking like this:

#[repr(C)]
pub struct FileHeader {
    pub bmp_id: [u8; 2],
    _pad: [u8; 2],
    pub file_size: u32,
    reserved: [u8; 4],
    pub pixel_array_offset: u32
}

The file header is supposed to be 14 bytes in size and the DIB header, coming immediately after the file header is supposed to be at an offset of 14 bytes (the file header size) into the BMP file. But because of the padding, the FileHeader size is 16 bytes. So, the bytes we're interpreting as our DIB header are 2 bytes off the mark.

To verify what's been said here, let's do a little experiment:

#[no_mangle]
extern "efiapi" fn efi_main(
    handle: *const core::ffi::c_void,
    sys_table: *mut SystemTable,
) -> usize {
    // ... Others
    let color_table_ptr = unsafe { block_bytes_ptr.offset(COLOR_TABLE_OFFSET) as *const ColorTable };
    let color_table = unsafe { &(*color_table_ptr) };

    /* DELETED:
    if dib_header.image_width == 36 && dib_header.image_height == 16 {
        print_str(screen, "Width and height as expected");
    } else {
        print_str(screen, "Something wrong somewhere");
    }
    */

    if FILE_HEADER_SIZE == 16 {
        print_str(screen, "The padding has inflated our file header");
    } else {
        print_str(screen, "So we are wrong");
    }

    0
}

Upon building and running, you should have:

The Padding Did It

To fix this situation, we have to make use of another attribute: #[repr(packed)]. This attribute tells the compiler that padding should not be inserted. Combined with #[repr(C)], the fields won't be reordered and padding won't be inserted, which is exactly what we want.

// DELETED: #[repr(C)]
#[repr(C, packed)] // NEW
pub struct FileHeader { /* OTHERS */ }

// DELETED: #[repr(C)]
#[repr(C, packed)] // NEW
pub struct DIBHeader { /* OTHERS */ }

You might be wondering why we didn't add the packed attribute to Color and ColorTable. This wasn't done because all the fields in Color are u8s, so their alignments are 1. This means that they can be placed at any address, so the compiler won't insert any padding in Color. As for ColorTable, this is just an array of Colors, and array values are always packed together with no padding.

The file header size should be 14 now, as it was always supposed to be.

#[no_mangle]
extern "efiapi" fn efi_main(
    handle: *const core::ffi::c_void,
    sys_table: *mut SystemTable,
) -> usize {
    // ... Others
    let color_table_ptr = unsafe { block_bytes_ptr.offset(COLOR_TABLE_OFFSET) as *const ColorTable };
    let color_table = unsafe { &(*color_table_ptr) };

    // DELETED: if FILE_HEADER_SIZE == 16 {
    if FILE_HEADER_SIZE == 14 {
        print_str(screen, "The file header is okay now");
    } else {
        print_str(screen, "So we are wrong");
    }

    0
}

Building and running:

Now 14

Now, let's check if the DIB header has the correct image width and height again.

#[no_mangle]
extern "efiapi" fn efi_main(
    handle: *const core::ffi::c_void,
    sys_table: *mut SystemTable,
) -> usize {
    // ... Others
    let color_table_ptr = unsafe { block_bytes_ptr.offset(COLOR_TABLE_OFFSET) as *const ColorTable };
    let color_table = unsafe { &(*color_table_ptr) };

    /* DELETED:
    if FILE_HEADER_SIZE == 14 {
        print_str(screen, "The file header is okay now");
    } else {
        print_str(screen, "So we are wrong");
    }
    */

    // NEW:
    if dib_header.image_width == 36 && dib_header.image_height == 16 {
        print_str(screen, "Width and height as expected");
    } else {
        print_str(screen, "Something wrong somewhere");
    }

    0
}

Building and running:

Correct Width and Height

The width and height are now as expected.

Back to our procedure for drawing:

  1. Interpret the image bytes using the structs we laid down.
  2. Loop over the pixel array image width at a time, from the last bytes upwards.
  3. In each iteration of step 2, retrieve the index values in a row, convert them to the pixel values the screen is expecting and put them on screen.

We'll continue with steps 2 and 3 in the next post.

A Little Ending Note

There are a few things about bitmaps that I did not mention, mainly because we didn't need them. For example, numeric fields in bitmaps are little-endian. If you don't know what this means, that's not a problem. Endianness just has to do with how the bytes of some value are ordered in memory. I won't go into the specifics right now because we don't need to worry about it in this project. Endianness and its role in the bitmap format will feature in a future detour post.

Take Away

  • #[repr(packed)] is an attribute used to stop the compiler from inserting padding into a struct.

Code till now:

Directory view:

blasterball/
| .cargo/
| | config.toml
| src/
| | bitmap.rs
| | block.bmp
| | font.rs
| | main.rs
| | uefi.rs
| .gitignore
| Cargo.lock
| Cargo.toml

For the full code, go to the repo

In the Next Post

We'll get on with the next steps to get block.bmp on the screen