Demilade Sonuga's blog

All posts

Drawing Bitmaps III

2022-12-18

Onto our final steps to draw block.bmp:

  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.

Before we can get to looping over the pixel array, we first need to get a slice to those bytes starting at the pixel array's offset into the bitmap file, to the end of the file.

Now, why exactly do we need a slice and not something else? To understand why we need a slice, let's first understand slices and how they work.

Slices

Here is an array:

fn main() {
    let an_array: [u8; 5] = [3, 4, 5, 6, 7];
}

When this code is run, during main's execution, an_array, will look like this in memory:

Address Stack
1004    3
1003    4
1002    5
1001    6
1000    7

That is, the array's values are all initialized on the stack when the function gets executed. If you don't know what the stack is, let's just say it's an area in memory that functions can use to store their local variables. The thing about the stack is that the size of anything that will be kept on the stack must be known beforehand. This is because when Rust code is compiled, the first instruction in a function is always space allocation on the stack for local variables.

For a clearer understanding of what I'm talking about, consider the disassembly of the function:

0000000000007b30 <_ZN1x4main17h8a77269bb7464175E>:
    7b30:       48 83 ec 05             sub    $0x5,%rsp
    7b34:       c6 04 24 03             movb   $0x3,(%rsp)
    7b38:       c6 44 24 01 04          movb   $0x4,0x1(%rsp)
    7b3d:       c6 44 24 02 05          movb   $0x5,0x2(%rsp)
    7b42:       c6 44 24 03 06          movb   $0x6,0x3(%rsp)
    7b47:       c6 44 24 04 07          movb   $0x7,0x4(%rsp)
    7b4c:       48 83 c4 05             add    $0x5,%rsp
    7b50:       c3                      ret    
    7b51:       66 2e 0f 1f 84 00 00    cs nopw 0x0(%rax,%rax,1)
    7b58:       00 00 00 
    7b5b:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)

This is the disassembly of the array initialization function. The numbers on the far left with columns in front of them are addresses. The numbers that come after them are hexadecimal equivalents of the instructions and the text on the far right are the instructions in x86_64 assembly.

Following this is not hard. This is just another language with a lot more detail. The %rsp up there identifies a register, which is just high-speed memory. This register has the special purpose of keeping the address of the stack's top. The $0x5 is the number 5.

The sub $0x5,%rsp instruction subtracts 5 from %rsp. This is done because the function needs 5 bytes of space on the stack to store all the local variables used in the function. The an_array is an array value of 5 u8s which are 1-byte integers. 5 * 1 byte == 5 bytes, hence the need for 5 bytes of space on the stack.

The subsequent movb num, location instructions after the sub move the number num to the location in memory location. The movb $0x3,(%rsp) moves the integer 3 into the location just reserved for it on the stack. The same is done for integers 4, 5, 6, and 7. These numbers taken together then constitute the array an_array.

Immediately after all this initialization is add $0x5,%rsp. This instruction returns the stack pointer to the state it was in before the function began executing. Now, when another function wants to execute, it will overwrite whatever was put in that area of memory with its own local variables. The ret instruction transfers CPU control back to the function caller.

Slices are like arrays in the sense that you can index into them, like slice[9]. The thing about them is that the values that you get from a slice when you index into them like slice[9] are not owned by the slice, but rather are referenced from some other sequence. In other words, a slice is just a sort of reference to another sequence, which allows you to view some elements of that sequence.

fn main() {
    let an_array: [i32; 5] = [3, 4, 5, 6, 7];
    let a_slice: &[i32] = &an_array[1..=3];
}

In the above, a_slice[0] will be 4, a_slice[1] will be 5, a_slice[2] will be 6 and a_slice.len() will be 3. The a_slice itself has no values of its own, but rather, it references an_array and provides a view into a subsequence of an_array's elements.

At runtime, main's stack will look like this:

Address Stack
1004    3       (`an_array`'s items)
1003    4
1002    5
1001    6
1000    7
999     1003    (`a_slice`'s pointer to the first array element it's referencing)
998     3       (The number of elements `a_slices` can view from `an_array` )

The above has some errors in it, for simplicity. For example, the address 1003 can't possibly fit in a single byte, but the above shows it fitting easily into the byte at address 999. Ignore that. I think the point I'm trying to pass across should be clear.

Getting On With The Next Steps

Now, armed with some knowledge of slices, let's get our pixel array.

In an earlier post, it was mentioned that include_bytes! retrieves the bytes in a file, hardcodes those bytes into the binary and returns a slice referencing those bytes which will be in memory when the binary is loaded.

The pixel array will be just a slice, too, referencing a contiguous sequence of bitmap bytes that contain the desired array.

What we need now is the offset of the pixel array's bytes into the bitmap which is given by the FileHeader:

#[repr(C, packed)]
pub struct FileHeader {
    pub bmp_id: [u8; 2],
    pub file_size: u32,
    reserved: [u8; 4],
    pub pixel_array_offset: u32 // Just what we're looking for
}

In our efi_main:

#[no_mangle]
extern "efiapi" fn efi_main(
    handle: *const core::ffi::c_void,
    sys_table: *mut SystemTable,
) -> usize {
    const DIB_HEADER_SIZE: usize = core::mem::size_of::<DIBHeader>();
    const COLOR_TABLE_OFFSET: isize = (FILE_HEADER_SIZE + DIB_HEADER_SIZE) as isize;
    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");
    }
    */

    // Get a slice to the bitmap's pixel array 
    let pixel_array = &block_bytes[file_header.pixel_array_offset as usize..];

    0
}

The &block_bytes[file_header.pixel_array_offset..] gets a slice to the underlying bytes in the binary starting from the offset file_header.pixel_array_offset till the end of the bitmap.

Step 2 tells us that we need to iterate over the pixel array, image width at a time, from the last bytes upwards. Before proceeding, think about how you'll do this yourself.

First, we need to remember that the pixel array is a 2D array. So, if a pixel array [3, 4, 5, 6, 2, 3, 4, 5, 4, 9, 2, 1] has a width of 3, then on screen, it will look like this:

Screen
9 2 1
4 5 4
6 2 3
3 4 5

In this illustration, the numbers stand in place of the colors. This is equivalent to having an array [[3, 4, 5], [6, 2, 3], [4, 5, 4], [9, 2, 1] drawn from the bottom up.

The procedure to draw such a 2D array will look like this:

Draw-2D-Pixel-Array(screen, image)
    for row in 0..image.height
        for col in 0..image.width
            inverted_row = image.height - row - 1
            color_table_index = image.pixel_array[inverted_row][col]
            color = image.color_table[color_table_index]
            screen[screen.curr_row + row][screen.curr_col + col] = To-Pixel(color)

The above iterates over each row from the top of the image to the bottom. Since the image's rows are inverted in the pixel array, the correct row index will be image.height - row - 1, because this will ensure the rows are considered from bottom to top. For example, row, for the 2D array described, will go through the values 0, 1, 2, and 3, in that order and inverted_row will go through the values 4 - 0 - 1 == 3, 4 - 1 - 1 == 2, 4 - 2 - 1 == 1, and 4 - 3 - 1 == 0, or, less verbosely, 3, 2, 1, and 0, which is the inverted order we're looking for. The image's width is the number of columns in the image. This is clear from the structure of the 2D pixel array above. Since the image width is 3, there are only 3 columns to put colors in before moving to the next row. Since, each value in the pixel array is an index in the color table, when the value for the current row and column is retrieved, it's used to index the color table to get the actual color value. This color value is then converted to the pixel structure expected by the screen and it's placed on the screen.

But our pixel array is just a slice of bytes, so we have to make up the 2D-ness ourselves.

To do this, the actual procedure will look like this instead:

Draw-Pixel-Array(screen, image)
    for row in 0..image.height
        for col in 0..image.width
            inverted_row = image.height - row - 1
            color_table_index = image.pixel_array[inverted_row*image.width + col] // Changed to emulate 2D-ness
            color = image.color_table[color_table_index]
            screen[screen.curr_row + row][screen.curr_col + col] = To-Pixel(color)

With this change, our procedure will now work with our actual pixel array. To understand how this change works, consider this same pixel array [3, 4, 5, 6, 2, 3, 4, 5, 4, 9, 2, 1] of an image with a width of 3 and a height of 4. To draw this, the first value of row == 0 and inverted_row will be height - row - 1 == 4 - 0 - 1 == 3. So, for column 0, pixel_array[inverted_row*width + col] == pixel_array[3 * 3 + 0] == pixel_array[9] == 9, the first value that ought to be on screen. When col is increased by 1, the next value will be pixel_array[3*3 + 1] == pixel_array[10] == 2. The next will be pixel_array[3*3 + 2] == pixel_array[11] == 1, giving the first row on the screen: 9 2 1.

row will increase by 1 and become 1. col will reset to 0 again since it's drawing on a new row. inverted_row will now be 4 - 1 - 1 == 2. The next value from the pixel array will then be pixel_array[2 * 3 + 0] == pixel_array[6] == 4, the first value of the second row. This will continue until all the values in all the rows have their pixel equivalents on screen.

For a better understanding of how this works, consider the following execution of the procedure for this pixel array [4, 5, 4, 9, 2, 1] of an image with a height of 2 and a width of 3 (And assuming that the screen's current row and column are 0):

Initially, our screen is blank:

Screen
    0  1  2
0
1

Our procedure begins:

  1. row is initialized to 0
  2. col is initialized to 0
  3. inverted_row is set to image.height - row - 1 == 4 - 0 - 1 == 3
  4. color_table_index is set to image.pixel_array[inverted_row * image.width + col] == image.pixel_array[1 * 3 + 0] == image.pixel_array[3] == 9
  5. The color is then retrieved from the color table and placed on the screen at screen[screen.curr_row + row][screen.curr_col + col] == screen[0 + 0][0 + 0] == screen[0][0], the first position on the screen. The screen will now look like this:
Screen
    0  1  2
0   9
1
  1. col is increased to 1 to become 1
  2. inverted_row remains the same since row hasn't changed yet
  3. color_table_index is set to image.pixel_array[inverted_row * image.width + col] == image.pixel_array[1 * 3 + 1] == image.pixel_array[4] == 2
  4. The color indexed by 2 in the color table is retrieved and placed in the screen at screen[screen.curr_row + row][screen.curr_col + col] == screen[0 + 0][0 + 1] == screen[0][1] The screen now looks like this:
Screen
    0  1  2
0   9  2
1
  1. col is increased by 1 to become 2
  2. row hasn't changed; inverted_row remains the same
  3. color_table_index is set to image.pixel_array[inverted_row * image.width + col] == image.pixel_array[1 * 3 + 2] == image.pixel_array[5] == 1
  4. The color indexed by 1 in the color table is retrieved and placed in the screen at screen[screen.curr_row + row][screen.curr_col + col] == screen[0 + 0][0 + 2] == screen[0][2] The screen now looks like this:
Screen
    0  1  2
0   9  2  1
1
  1. Since the col has reached its max, we've drawn the first row of the bitmap. row is now increased by 1 to become 1
  2. col is set to 0
  3. inverted_row is set to image.height - row - 1 == 2 - 1 - 1 == 0. So, it's the first row in the pixel array we're looking at now. This is correct because the rows in the pixel array are upside down
  4. color_table_index is set to image.pixel_array[inverted_row * image.width + col] == image.pixel_array[0 * 3 + 0] == image.pixel_array[0] == 4
  5. The color indexed by 4 in the color table is retrieved and placed in the screen at screen[screen.curr_row + row][screen.curr_col + col] == screen[0 + 1][0 + 0] == screen[1][0] The screen now looks like this:
Screen
    0  1  2
0   9  2  1
1   4
  1. col is increased by 1 to become 1
  2. row hasn't changed; inverted_row remains the same
  3. color_table_index is set to image.pixel_array[inverted_row * image.width + col] == image.pixel_array[0 * 3 + 1] == image.pixel_array[1] == 5
  4. The color indexed by 5 in the color table is retrieved and placed in the screen at screen[screen.curr_row + row][screen.curr_col + col] == screen[0 + 1][0 + 1] == screen[1][1] The screen now looks like this:
Screen
    0  1  2
0   9  2  1
1   4  5
  1. col is increased by 1 to become 2
  2. row hasn't changed; inverted_row remains the same
  3. color_table_index is set to image.pixel_array[inverted_row * image.width + col] == image.pixel_array[0 * 3 + 2] == image.pixel_array[2] == 4
  4. The color indexed by 4 in the color table is retrieved and placed in the screen at screen[screen.curr_row + row][screen.curr_col + col] == screen[0 + 1][0 + 2] == screen[1][2] The screen now looks like this:
Screen
    0  1  2
0   9  2  1
1   4  5  4
  1. At this point, both row and col have reached their max, so all the color values of the bitmap have been drawn on the screen

Translating this to our Rust code:

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

    let pixel_array = &block_bytes[file_header.pixel_array_offset as usize..];
    
    // Retrieving the image height from the DIB header
    // Casting it as a usize so that it can be used to index into arrays and slices
    let image_height = dib_header.image_height as usize;
    // Retrieving the image width from the DIB header
    // Casting it as a usize so that it can be used to index into arrays and slices
    let image_width = dib_header.image_width as usize;
    // Drawing the bitmap on screen
    for row in 0..image_height {
        for col in 0..image_width {
            // The image is upside down in the pixel array,
            // so the pixel array's rows have to retrieved from the bottom up
            let inverted_row = image_height - row - 1;
            let color_table_index = pixel_array[inverted_row * image_width + col];
            let color = color_table.0[color_table_index as usize];
            screen.pixels[row][col] = Pixel {
                red: color.red,
                green: color.green,
                blue: color.blue,
                reserved: 0
            };
        }
    }

    0
}

If you try building the project now, you'll get some errors concerning the privacy of Screen's pixels field. To rectify this:

In uefi.rs

pub struct Screen {
    // DELETED: pixels: [[Pixel; NO_OF_PIXELS_IN_A_ROW]; NO_OF_PIXELS_IN_A_COLUMN],
    pub pixels: [[Pixel; NO_OF_PIXELS_IN_A_ROW]; NO_OF_PIXELS_IN_A_COLUMN], // NEW
}

We just make the pixels field public. There is actually a better way of doing this, but we'll just stick to this for now.

We also have to import the Pixel struct in our main.rs:

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

mod font;
use font::FONT;

mod uefi;
// DELETED: use uefi::{SystemTable, Screen, PixelFormat, pre_graphics_print_str, print_str, printint};
use uefi::{SystemTable, Screen, PixelFormat, Pixel, pre_graphics_print_str, print_str, printint}; // NEW

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

Building again will result in ownership concerning moving Color. This is because Color doesn't implement Copy. To rectify:

In bitmap.rs

#[derive(Clone, Copy)] // NEW
#[repr(C)]
pub struct Color {
    pub blue: u8,
    pub green: u8,
    pub red: u8,
    pub reserved: u8
}

Building and running now should give you:

Block On The Screen

  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.

Take Away

  • Slices are a sort of references to other contiguous sequences

For the full code, go to the repo

In the Next Post

We'll be thinking through our code and refactoring, again.

References

  • https://doc.rust-lang.org/rust-by-example/primitives/array.html
  • https://doc.rust-lang.org/book/ch04-03-slices.html
  • https://doc.rust-lang.org/std/primitive.slice.html