UEFI News and Commentary

Saturday, December 03, 2016

The UEFI Maze Game, Part 3

This is the third part in a series of posts about a simple game written as a UEFI Shell application. It consists of generating a random graphical maze and navigating a little man through that maze from entrance to exit.

This post gets to the actual maze generation, which is actually a recursive function. Pick a random position. Then pick a random direction and, if that cell is completely surrounded, then mark the cell as a path. If there is no such cell in any direction, then back up. This algorithm generates that there are no circular paths through the maze.

Figure 10.40  Maze generation main function, part 1 in Game.c
Lines 272-280
This function gets called once for each grid cell. The coordinates of the current cell are X and Y.
Lines 282-288
The local variables keep track of which neighbors to the current cell. The number of valid neighbors and then the direction from the current cell. 
Lines 293-299
If the neighboring cell to the left is surrounded by walls, then it is a possible cell that we could go to next. So record the cell’s coordinates and increment the number of valid neighbors.
Lines 301-307
If the neighboring cell above is surrounded by walls, then it is a possible cell that we could go to next. So record the cell’s coordinates and increment the number of valid neighbors.

Figure 10.41 Maze generation main function, part 2 in Game.c
Lines 310-315
If the neighboring cell down is surrounded by walls, then it is a possible cell that we could go to next. So record the cell’s coordinates and increment the number of valid neighbors.
Lines 301-307
If the neighboring cell to the right is surrounded by walls, then it is a possible cell that we could go to next. So record the cell’s coordinates and increment the number of valid neighbors.
Lines 328-331
If there are no valid neighbors then we need to back track to the last valid position and try again.

Figure 10.42 Maze generation main function, part 3 in Game.c

Lines 336-340
Pick a random direction and update the coordinates in that direction.
Lines 343-345
Save the coordinates in the backtrack list.
Lines 349-357
Mark the maze in that direction as a path and increment the number of cells visited.
Lines 361
Now recursively call this function, but this time start at the next location.

Next Steps

Now the finish line is nearly in sight. We have the environment, we have the bitmaps, and we have the maze. Now we just need to draw it and move the man around.

Oh, wait. We haven't seen how to read the bitmap files or draw them with transparency. These functions are not provided within UEFI itself, so we will add them in a single post!

Tuesday, November 22, 2016

The UEFI Maze Game, Part 2

This is the second article in a series describing a simple UEFI Shell game that generates a random maze and lets you navigate a character through that maze to the exit. The goal is to show how to use graphics and the UEFI Shell together, line by line.

The next step is to initialize the grid and the maze. The maze uses two-by-two sections of the grid. These sections can have one of the following configurations

Notice that in each chase, the lower-right cell is always a rock, and the upper-right cell is always empty. The only question is whether there is a pathway to the right, to the bottom, or both.

Figure 35

Lines 407-423
This function divides up the screen into cells based on the size of the loaded bitmap images. If there aren’t e

nough cells to make a reasonable maze then the function exits with an error. The maze uses a two by two section for each part of the maze. In addition, the first row and first column must be all walls. This means that the number of rows and columns must be odd. 
Lines 425-434
The function creates the buffer for the maze bitmap.
Lines 436-441
The function creates the buffer for the maze grid contents.

Figure 36
Lines 443-448
Initialize every cell in the grid to a background image.
Lines 450-451
Display the empty background grid. This is important, because the other images (rock and player) need to be drawn on to another color besides black.
Lines 454-460
Initialize the maze generation data structures, create the random maze, copy that maze over to the grid and then free up the allocated data structures.
Lines 462-469
The entrance is at a random location on the top edge. The exit is at a random location on the bottom edge.
Lines 471-475
Now move the character to the entrance and draw it on the bitmap. 

During maze initialization, we create a temporary grid.

Figure 37
Lines 231-242
The temporary two-dimensional array mMaze holds either PATH or WALL for every location.
Lines 245-259
The backtrack arrays are used so that when we get to a dead end, the maze generator can back up to the last place where a decision was made.
Lines 261-269
Since in every 2x2 section of the maze, the bottom right cell is a rock wall, set that now.

These utility functions simply make it easier.

Figure 38

Lines 195-200
These global variables hold the maze and the backtrack data structures. The maze (mMaze) is a two-dimensional array where each element is set to either a path (PATH) or wall (WALL). The backtrack arrays contain the coordinates in the maze of the last point where a decision was made.
Lines 202-207
Utility function to return what is at a specific set of coordinates in the maze.
Lines 209-214
Utility function to change what is at a specific set of coordinates in the maze.
Lines 216-226
Utility function that returns whether there are walls in all four directions.

Now there are the two functions to generate the maze and shutdown the maze.

Figure 39

Lines 380-385
This function calls the maze generation function, starting at the upper-left hand cornder of the maze. Since each maze cell requires a 2x2 section of the grid, we divide both the height and width of the grid by 2. We subtract 1 because we leave one extra for the wall on the top and left of the grid.
Lines 389-394
Free up all of the resources used by the maze generation.
Next Steps
Now we have all of the pieces we need to generate the maze and all the parts to draw it. In the next article, we'll dig in to the heart of the maze generation function.

Sunday, November 13, 2016

The UEFI Maze Game, Part 1

This UEFI Shell application features a very simple maze game that uses UEFI’s Graphics Output protocol to draw a random maze and direct a character from entrance to exit using a keyboard. It will be added to the SVN repository after the last article in this series is published.

This application features a few nifty touches, including converting bitmap (.bmp) files to HII, merging bitmaps using transparency and a nifty maze generation algorithm. This application uses both the standard C library, as well as UEFI-specific libraries.

This game doesn’t have any villains or time limits, yet. Originally, I planned to integrate the thermometer application previously discussed so that the main character got hotter and hotter and little ice cubs in the maze would cool him down. You can add villains in the maze, or the animation could move smoothly from cell to cell or there could be some sort of time limit.

The source is spread over two .C files. It also uses three bitmap files, which are included in the online source code. These bitmaps are: a rock, a player, and a solid green background.

The First Source File: Game.c
Figure 1: Global Variables in Game.c
Lines 1-13
These are the include files for the standard C library, basic UEFI services and, surprise(!) bitmaps. The MdePkg\Include\IndustryStandard contains constants, data structures and file formats from many popular industry standards, including PCI, ACPI and USB.
Lines 15-41
These are the key function declarations from the other source file, Bitmap.c. Rather than create a separate header file, they are just listed here.
Figure 2: Game State Data in Game.c

Next we move on the various global variables that maintain the game state.

Lines 46-47
DisplayImageStack is the global function that refreshes the screen from the internal buffer that holds the game’s bitmap image.
Lines 50-51, 64-65
These globals hold the width of the loaded background images and other images. These should be the same.
Lines 52-54
These point to the three bitmaps used in the game: the rock, the background and the player. Each is 50 x 50 pixels.
Lines 56-58
The game maintains a pixel-for-pixel copy of what is actually going to be displayed on the maze portion of the screen.  All of the player actions are updated here before they are copied to the screen. 
Lines 60-62
The game also maintains a cell-by-cell copy of what is in each part of the grid. The array mGrid contains a two dimensional array, mGridWidth cells wide by mGridHeight cells tall. Each element in the array points to one of the bitmaps: rock, background or player. The size of the array is calculated based on the screen resolution.
Lines 67-74
These mark the coordinates (within mGrid) of the character’s position, the entrance position and the exit position. Initially, the character’s position is at the entrance position. The game ends when the character reaches the exit position.
Figure 3 Game entry point in Game.c

Now that you are thoroughly bored with the global definitions, we finally reach the entry point of the game. 

Lines 590-596
This uses the standard C-style entry point. But there are no command-line options parsed.
Line 598
The srand() function is used to initialize the random number generator with a seed value. In this case, the seed value is derived from the system time. When debugging the maze generation algorithm, it was useful to set this to a fixed value so that the maze would be the same each time, facilitation easier debugging of issues.
Line 600
Reset the console so that the screen is empty.
Lines 602-606
Load all of the bitmap images and convert them into the format used by the UEFI graphics output functions. If there is an error, it means that not all of the images could be loaded or (less likely) the system cannot switch to graphics mode.
Line 608
Initialize the game data structures, including the maze.
Line 610-614
Display the maze for the first time.
Line 616
Enter the main game loop. This loop continues until the user indicates they are finished or they have reached the maze exit.
Line 619-621
Clear the screen and exit.

Figure 4 Setup bitmap images and Graphics Output Protocol in Game.c

The first step for the game is to load all of the bitmaps out of the files.

Lines 108-110
Find the instance of the UEFI Graphics Output protocol.
Lines 112-127
Load each of the three bitmaps from external files. Each of the files is formatted using the industry standard .bmp file format. 

Next Time
In the next installment, we'll look at exactly how to initialize UEFI's Graphics Output Protocol and load a bitmap.

Wednesday, October 26, 2016

Intel and Insyde Embedded White Paper

Stephen Gentile, my colleague at Insyde Software, and I wrote a white paper with several Intel IoTG folks that describes how our UEFI-based embedded solution, BlinkBoot®, solves real-world business and technical challenges. You can find the paper here. BlinkBoot includes a unique add-on technology model, called Lenses, and a dedicated suite of tools: BlinkDebug, BlinkFlash and BlinkShell.

Thursday, October 20, 2016

PI 1.5 Released

This is late news, but you should head on over to the UEFI web site and pick up the PI 1.5 specification (here). Here are the highlights:

  1. Change the term System Management Mode (SMM) to Management Mode (MM)
  2. Provide a Management Mode infrastructure on ARM systems by using TrustZone.
  3. Allow initialization of Management Mode, as early as SEC or PEI. Also introduced a new class of MM drivers that launch natively within MM.
  4. Improved I2C support.
  5. Allow SEC to pass HOBs to PEI.
  6. New multi-processor protocol 
  7. Updated Disk Info to support SD/MMC
  8. and more...
As you can see, SMM (or rather MM) was a big part of this update. I started this, but my efforts were dwarfed by others. Part of the reason was that the ARM 64-bit folks had already started down a standardization path for TrustZone and it required some diligent technical and consensus-building work to create an environment that both ARM and x86 architecture firmware could share. We didn't just include Aarch64 systems. We made IA32 and X64 systems more robust and flexible as well. A shout out to Charles Garcia-Tobin (ARM) and Vincent Zimmer (Intel) on this.