GRUB Graphical Menu Development Journal

Author: Colin D. Bennett <colin@gibibit.com>

29 November 2009

Finally! Graphical menu in GRUB experimental

The graphical menu feature is now finally being merged into mainline GRUB, thanks in large part to Vladimir “phcoder” Serbinenko since I have not had the time to do the needed work.

GRUB has switched to Bazaar for its own version control system, which I am very exited about. This makes distributed development much easier than it is with Subversion (although bzr-svn helps a lot compared to plain Subversion).

The graphical menu is now available in GRUB's experimental branch.

Note

GRUB experimental branch.

# readonly access
bzr branch http://bzr.savannah.gnu.org/r/grub/branches/experimental/

# member access
bzr branch sftp://<username>@bzr.savannah.gnu.org/srv/bzr/grub/branches/experimental

Note

My development branches and snapshots are very much outdated.

The GRUB experimental branch should be used instead.

Users of Debian experimental and Ubuntu 9.10 users have easy access to GRUB's experimental branch containing the graphical menu system, as this email from Debian maintainer and GRUB developer Felix Zielcke describes:

From: Felix Zielcke
To: The development of GNU GRUB <grub-devel@gnu.org>
Subject: Re: gfxmenu available in experimental
Date: Fri, 27 Nov 2009 12:42:31 +0100

Am Freitag, den 20.11.2009, 23:17 +0100 schrieb Vladimir
'φ-coder/phcoder' Serbinenko:
> Hello, all. After various delays with various cause I'm proud to
> announce the availability of Colin's gfxmenu into experimental branch
> of
> grub2.

I'm proud to announce it's finally avaible in Debian experimental
(Thanks Robert) and in my Ubuntu ppa for the karmic users with all the
Ubuntu changes merged in this time.

There is some work to do on the graphical menu before it's complete, but Vladimir “phcoder” has already done some significant performance optimizations.

12 June 2009

Progress update

I'm continuing to get closer to committing the graphical menu code to GRUB mainline. I have made changes in the error handling of the code to increase its robustness, and I am currently trying to track down a bug that is manifested when one switching between themes repeatedly: eventually it appears that GRUB runs out of memory.

Bazaar branch changes

If you've been using the Bazaar branches, then you should know that I had to rebase the branches when I upgraded to bzr-svn 0.5. The new graphical menu code is available in the gfxmenu branch.

19 January 2009

Graphical menu support progressing

I finally merged the gfxmenu code into my stack of patches that have been reworked for submission to GRUB mainline. Besides this being a large step toward getting gfxmenu into GRUB's mainline, this also gives some Unicode support to gfxmenu, due to my addition of UTF-8 support to the font engine.

I have not had a chance to test the graphical menu with UTF-8 text yet, but there may still be issues, for instance in theme file parser, that will need to be ironed out.

Some of the still outstanding issues with the graphical menu are:

  • After running a command such as videotest basic which changes the video mode (?) from the graphical menu, the graphical menu system does not return. The interaction between the gfxmenu module, the gfxterm module, and users of the output terminal needs to be defined properly an implementated.
  • A usable and flexible way of letting the user select a theme must be added. I envision this as a popup menu brought up with a hotkey.

Updated source tarball with graphical menu

Here is a new source tarball of the GSoC'08 changes (r876) which you can use to build GRUB 2. Follow the instructions given on 19 December 2008 to build it. Note that the kludge of appending |class=foo,bar to menu entry titles to specify the class attribute has been replaced with a proper --class=foo option to the menuentry command in grub.cfg. This means that the menuentry command should now look something like

menuentry "Gentoo Linux" --class gentoo --class linux --class os {
  ...
}

You may want to use the new test overlay containing the updated grub.cfg that uses --class=X, together with the themes and fonts.

19 December 2008

This is just a quick update to say that while I have been very busy with life lately, GRUB and the gfxmenu feature are still moving along. I am still in the process of reworking some of the code to suit the desires of the core GRUB developers.

I have posted a source tarball to make it easy to build GRUB 2 with gfxmenu support on your own if you want to install it on a real machine instead of just testing with the premade ISO image that I created.

To build and install GRUB 2, the following commands should suffice:

tar -xjf cdbmain_r867.tar.bz2
cd cdbmain_r867
mkdir build
cd build
sh ../configure --prefix=YOUR_PREFIX_DIR
make
make install  (or sudo make install, depending on the prefix)

Some people have tried to extract the files from the premade gfxmenu demo ISO I provide on the download page, and either insert new files into the ISO image or install the files to a hard drive device. This usually does not work, so I recommend building GRUB 2 with gfxmenu from the source tarball yourself if you want to boot your machine with it or customize it.

30 October 2008

Added UTF-8 support to the new font engine. I enhanced the video test command to demonstrate the rendering of UTF-8 strings containing non-ASCII characters, as well as showing how the new smart glyph substitution works. Smart glyph substitution occurs when the font you request to use for drawing a string does not contain one of the characters in the string. In this case, the other loaded fonts are scanned for the glyph, and the glyph from the most similar font is used.

The fonts used in the Unicode test are fixed 10x20 and Helvetica. The fixed 10x20 font contains all the Unicode characters used in the test. The Helvetica font is missing many of the non-ASCII characters, and so they are being substituted from other fonts. Notice how the smallest Helvetica text, 8 point size, gets a glyphs substituted from a smaller font than the Helvetica 14 point text above it does.

Journal_2008-10-30_utf8_test.png

A portion of the videotest text screen showing the rendering of non-ASCII Unicode characters from a UTF-8 string.

16 August 2008

Added named color support in gfxmenu themes. The Lua branch (gfxmenu-lua) supports Lua GUI components, although only the paint() and destroy() functions are implemented yet. It would be great to have full Lua integration with the GUI component system, but it will take a little more work, since to make it smoothly integrated, both Lua->C and C->Lua component access will need to be possible (for example, if we created a Lua container, it would need to be able to contain and manage child components which were C components).

15 August 2008

Removed status bar since it can now be created with components. Added a pixmap-styled progress bar. Add circular progress indicator.

14 August 2008

Improved theme component layout functionality. Added scrolling boot menu and theme scrollbar support.

11 August 2008

Added progress_bar component, which is now used for GRUB default boot timeout status. Updates to demo themes.

10 August 2008

Added align property to label, and added preferred_size property to box, canvas, and label components.

9 August 2008

I have uploaded a new ISO showing off the enhanced theme support, which allows themes to lay out custom components on the screen. Currently text labels and images can be freely placed, and there are two types of containers available to automatically manage the layout of their child components: a horizontal box ("hbox") and a vertical box ("vbox"). The winter theme offers a demonstration of these features.

27 July 2008

Backed out my file readahead buffering patch that modified grub_file_read() to do buffering. Then I applied Bean's patch that added the bufio module. Bean's patch is far superior since it is implemented as a decorator around a grub_file_t object. Thus, only code that opens files with grub_buffile_open(const char *) or grub_bufio_open(grub_file_t) will be affected by the buffered I/O feature. This is good since I found that my patch caused GRUB to crash early in the boot process when my buffering code was enabled before grub_main().

26 July 2008

Implemented runtime theme switching. Currently it is a hardcoded hack: press 1 to load the proto theme, or press 2 to load the winter theme. Complete theme switching support by presenting a menu to the user is probably a good idea, so that users can try the available themes to select one. However, they will still have to manually edit the grub.cfg file to set the theme persistently (with set theme="/path/to/theme.txt"). Probably the best way for general users to choose a theme is simply by looking at screen shots provided with the theme.

Theme_winter_menu.jpg

Screen shot of the winter theme showing the boot menu.

I created a new theme, winter, inspired by the image Without Leafs in Winter. As I created the theme, it helped to define some of the things the graphical menu must do. I have uploaded some screen shots of the themes winter and proto.

I enhanced the theme format and the gfxmenu GUI by including more configurable properties, by adding a themed box type for the terminal window.

I added default entry booting after a timeout, with fallback support, to gfxmenu. Since I'm trying to stay in the GUI to give feedback to the user, I am running into the nasty problem where commands that switch to text mode (with grub_video_restore()) make GRUB crash after the command returns. I am actually not certain of the root cause, but after many hours of tedious and unfruitful debugging, I need to move on for now.

25 July 2008

Enhanced the theme file format to allow relative paths to images. If relative paths are specified, they are interpreted relative to the directory containing the theme file itself. Use of . and .. is supported.

24 July 2008

Did some initial work to support gfxmenu executing a default item after the timeout is elapsed as well as enhancing the existing fallback functionality to support multiple fallback entries.

23 July 2008

Today I split the graphical menu code into model-view-controller (MVC) components. This makes it more modular and limits the responsibilities of each part of the menu system. The view is by far the most complex part.

I also implemented very simple theme file loading support as a step toward flexible customization features. An example theme file in this simple format:

# Sample GRUB gfxmenu theme.

title-font: "Helvetica Bold 24"
item-font: "Helvetica Bold 12"
status-font: "Helvetica 12"
title-color: "255, 255, 0"
item-color: "0, 0, 255"
status-color: "255, 128, 128"
status-bg-color: "64, 64, 64"
desktop-image: "/boot/images/bg-protomenu1.tga"
desktop-color: "0, 0, 128"
menu-box: "/boot/images/menubox_*.tga"
selected-item-box: "/boot/images/select_blue_*.tga"

Currently, gfxmenu is hard coded to use the file /boot/theme.txt, which in turn must specify the absolute paths to the image files it uses. I plan to add a way for the user to choose these on the fly from the gfxmenu interface. Also, I plan to eventually make paths in the theme file relative to the theme file's location. This will make installing themes much easier for users.

As a drive-by fix, I also removed the menu selection wrap-around behavior to be consistent with the text mode GRUB menu interface.

19 July 2008

Journal_2008-07-19_gfxterm.jpg

The gfxmenu graphical menu showing a gfxterm terminal window in use.

Supported double buffering for the gfxterm terminal window in the graphical menu. It is rather slow since it is very unoptimized at this point.

It is hard to make things work properly when the menu entries that are executed (or commands executed in the terminal window) change the graphics mode. Generally Bad Things happen. My current strategy is to revert to the console terminal before executing menu entries, and restore the gfxterm terminal after a menu entry returns. However, if you execute a command that switches video modes such as videotest basic in the command line terminal window, the screen will not be properly restored when the command completes.

Next, I created a new branch off of cdbmain called gfxmenu, took all the work up to this point from the menu-proto branch, and integrated it into the new gfxmenu branch while changing the name of the menu system to "gfxmenu" instead of "protomenu".

I tried to optimize the gfxterm performance in a gfxmenu window by caching the rendered menu screen and blitting that each time a gfxterm refresh is needed instead of re-drawing the whole screen piece by piece, but I ran into problems where text is not being drawn on offscreen RGB or RGBA render targets.

To try out the gfxmenu graphical menu, the following files are available:

  • An ISO image which is ready to run in VMware or QEMU.
  • A GRUB overlay if you want to build it yourself from the gfxmenu branch sources, and use these images, fonts, and grub.cfg as an overlay to grub-mkimage.

18 July 2008

Implemented a nested gfxterm terminal in the graphical menu. It doesn't work with double buffering enabled yet, so set protomenu_nodoublebuf=y and press 'g' at the protomenu to test it.

17 July 2008

Worked on the gfxterm module to add support for using only a portion of the screen. Once this is done, it will be usable within the graphical menu as a terminal window.

11 July 2008

Added functionality to the graphical menu prototype:

  • Press Enter to execute a menu item.
  • Press t to switch to the original character terminal menu.
  • Press c to access a command line. Currently just switches to text mode, but it needs to be changed to use the gfxterm terminal.

To try out the new menu, you can download the 2008-07-11 graphical menu prototype ISO and run it with QEMU (slower) or VMware (faster).

Alternately, you can get the source from the menu-proto bzr branch (with bzr branch http://grub.gibibit.com/bzr/menu-proto) and build it. Use grub-mkimage to overlay the contents of this overlay, which contains the images, fonts, and grub.cfg to demo the graphical menu.

Journal_2008-07-11_protomenu.jpg

Screen shot of the graphical menu prototype.

10 July 2008

Introduced a menu_viewer interface to allow the original character terminal-based menu and the new graphical menu to be both easily used. The menu_viewer interface provides a way for the 'normal' module to initiate the presentation of a menu to the user while allowing for a variety of presentation methods. The plain character terminal-oriented menu UI from normal.mod is called 'terminal', since it uses the grub 'terminal' interface to present the menu.

9 July 2008

Optimized RGBA->BGR alpha-blended blitting. This makes graphics much faster in QEMU.

I'm studying the GRUB menu handling code in the normal module. I'm trying to determine how to make use of the menu data in the graphical menu. I think I'll initially have to duplicate some of the functionality in the normal module, but at least I want to be able to show the list of menu items, and allow executing an item.

My new font engine seems to have broken the gfxterm menu. I don't know what's going on yet. Everything works when gfxterm is used as the shell terminal, but when I try to switch to the gfxterm terminal from the GRUB menu, it crashes. I tried to debug GRUB with the instructions on Debugging GRUB 2 with GDB, but I haven't been able to get it working yet.

8 July 2008

Multiple double buffering methods: page flipping, blitting, and null strategy. If double buffering is requested, then page flipping is tried first, then if that is not successful, blitting from an offscreen buffer is attempted. If even that fails, then no double buffering is done (the null strategy).

Since VMware does not support VBE page flipping, the blit strategy is very useful to make screen updates smooth.

I should add a check to the page flipping code for the amount of available video memory. QEMU seemed to have issues with page flipping at 1024x768 and I wonder if it was because there was not enough video RAM for 2 pages.

7 July 2008

Implemented pixmap-stylized components for the graphical menu prototype.

5 July 2008

Created prototype graphical menu. Check out the graphical menu prototype ISO to see what it looks like so far. I still am working on adding pixmap-styled widgets. If you build from the source, you can use my GRUB overlay files, which include fonts and images to support the prototype menu.

4 July 2008

Responded to Marco Gerards' comments on my TSC patch. I have prepared a new patch based on the current svn trunk.

If we want to support running GRUB on 386 and 486 machines, I'll have to make the TSC support selectable at run time. It would mean significant re-structuring in the patch, since we'd have to link in multiple implementations of the time functions and then have grub_machine_init() set up function pointers to the best available functions at run time.

3 July 2008

After several hours of applying all my patches to the new svn-based trunk, I have completed the transition to using the new official GRUB Subversion trunk.

Important

bzr repository has been re-created.

Since the switch to Subversion for the GRUB project, I had to re-base all my work off of the new svn branch instead of the CVS branch. Since bzr-svn, the tool I am using, provides full svn history, my old Tailor-generated CVS revision history is no longer valid. Therefore I had to essentially start over with a fresh repository and apply my changes to it.

If you have an existing checkout of my old bzr repository, you will need to get a new, fresh copy, since the revision history is completely different.

2 July 2008

Image scaling

I've looked at image scaling algorithms, and haven't found a simple snippet of Free Software code that I can use. I think the GIMP code would be too complex, as is the gdk-pixbuf image scaling in gtk+. I will start by implementing a simple nearest-neighbor scaling algorithm as a starting point. Its use could later be replaced by a better algorithm such as bilinear or bicubic.

This morning and afternoon I implemented bitmap scaling supporting both nearest-neighbor and bilinear interpolation. I added a new video test, videotest scale to demonstrate the scaling functionality.

Conversion to using Subversion

Since the GRUB project has switched to using Subversion, I now need to switch to using Subversion as my upstream base. I could try to use the bzr-rebase plugin to replay my history on the bzr-svn branch, but I don't know if it would be worth it. I might just try to manually apply all my changes as patches to branches of the new bzr-svn branch.

1 July 2008

I am now working on the design for the menu system itself. Use of pixmaps to stylize the user interface will be fully supported from the start, to maximize the customizability.

An image-scaling algorithm will be needed in order to scale background images to fit, and to stretch style elements such as title bars to fit. I need to find a fast and Free image scaling algorithm, preferably ready to plug and go, since I have a lot of other work to do.

30 June 2008

Vesa helped me solve my problem where I broke the GRUB build with my changes yesterday. It turns out I was misusing the EXPORT_FUNC() macro. It is only to be used for symbols that the kernel exports. I actually had tried removing the EXPORT_FUNC() macro from the font.h declarations, but I did not wipe the build directory and do a clean build, so it still failed me that time.

29 June 2008

Most font system functions now accept a grub_font_t parameter, which makes possible the use of multiple fonts simultaneously.

Important changes:

  • The font/manager.c file has been split into font/loader.c, font/font_cmd.c, and font/font.c.
  • Font functions such as grub_font_get_glyph() now require a grub_font_t as the first parameter.
  • The gfxterm module now uses the environment variable gfxterm_font to select the font to use.
  • The font command has become loadfont, and a new lsfonts command has been added.
  • The glyph blitting function now puts the text baseline on the specified y coordinate.
  • A new videotest text (in the cdbmain branch)/fonttest in the font2 branch) has been added to exercise the font system.

I have made available some fonts for testing. To use the fonts, use grub-mkrescue with the --overlay=DIR option, specifying the overlay directory from overlay.tgz as DIR. The grub.cfg file automatically loads all the fonts (takes about 1 second), so they are all available for testing. You wouldn't normally need to load this many fonts when really using GRUB.

28 June 2008

Added font information such as family, point size, weight, and slant style to the PFF2 file format. This way, GRUB can select fonts by name regardless of the requirement to use, for instance, short file names, or what the user has named the font file.

The struct font is now separated from the global linked list of fonts, which is a step toward allowing users of the font module to operate on fonts as objects, and use multiple fonts for rendering.

27 June 2008

Font loading and rendering

This morning, I rewrote the glyph blitting to iterate over the glyph pixels and use set_pixel() to write to the render target. This helped me to track down where the problems were. It turned out that my font loading code had some silly bugs in it, including some (probably copy-and-paste bugs!) where I called grub_file_read() and took a return value of 0 to indicate success, instead of the number of bytes that were required to be read.

Once I got the font loading code working with my 'dumb' font rendering using set_pixel(), I changed it to use grub_video_vbe_blit_bitmap() to do the glyph drawing.

  • Changed the structure of the video mode_info->mode_type field to add a new mode type, GRUB_VIDEO_MODE_TYPE_1BIT_BITMAP. Also added a new blit format, GRUB_VIDEO_BLIT_FORMAT_1BIT_PACKED.
  • Made the unmapping of 1-bit color values work. It uses the background and foreground colors set in the source mode_info structure
  • Blit the glyph as a bitmap. Uses BLIT_REPLACE right now. Should it use BLEND?

Actually, I think that iterating over the glyph's pixels and using set_pixel() to write to the render target would perform better than blitting it as a bitmap if the 1-bit packed blit format does not have an optimized blit function for the render target. At least if the loop is implemented in the blit_glyph function, accessing the glyph's pixels is optimized. Therefore, I will definitely want to write optimized 1-bit -> BGR/BGRA functions when I merge this font code with my vbeopt changes that add the BGR/BGRA blit formats.

Making font files

Having implemented the ability to use the new font file format, we next need to have some nice fonts. The fonts I'm currently using are the X Window System bitmap fonts. Dr. Markus Kuhn also has some information on Unicode fonts and tools for X11 that may be useful.

The unifont font apparently covers the Unicode character space well, but it only comes in a single size and style, so it will probably not prove very useful in practice.

I'm thinking of using xmbdfed, a GUI program, or writing a new program using FreeType to convert outline fonts (TrueType, etc.) to bitmap fonts at various sizes. This will greatly expand the selection of available fonts. However, the results may not be great. Perhaps there are other bitmap fonts available at decent sizes (16 to 48 points).

Font API

The font API should be updated to support multiple fonts.

First, the functions accessing a font need to be passed the desired font as a parameter. For instance, grub_font_get_glyph(grub_uint32_t code) should become grub_font_get_glyph(grub_font_t font, grub_uint32_t code).

Besides supporting multiple fonts, font "sets" or "families" should be supported, where a font set is set of fonts that can be used to render text by falling back on other fonts in the set when the first does not contain a requested character.

Themes requesting fonts by name should also ask for fonts by specifying a list of allowable fonts in the same way the CSS does. For instance, in CSS, the expression font-family: Georgia, Times, serif requests the use of the Georgia font, but if it is not available, then the Times font is used, and if neither of the first two is available, then whatever font the alias serif points to is used.

I think that the font file format should include the font name as well. This way if a font file is renamed, or stored on a file system that truncates its name, the font is still usable. The font size should be taken as the maximum character height from the MAXW header value.

26 June 2008

Implemented reading the new PFF2 file format in GRUB. I attempted to render glyphs using bitmap blitting, but it took me all day long to get to the point of testing the code, I didn't have time to debug it when it didn't work... I had trouble keeping my eyes open by that point.

25 June 2008

Modified the PFF2 font format and updated the converter utility and Java viewer to support it. Basically all the header information that needs to be loaded when the font is loaded is stored at the beginning of the font file, before all the character definition data. The end of the header information is indicated by a section start marker called "DATA", after which the rest of the file contents are accessed only through the character index. This should make reading the file simpler and eliminate the need to seek through the whole file when it is opened.

Now I need to implement using the new font format in GRUB. I'm reading the font manager code now and looking at users of fonts such as gfxterm to see how fonts are used.

23 June 2008

Today I refined the TSC patch and posted it for review to GRUB devel mailing list. I propagated the TSC changes through my branches. I did run into a weird merge problem where the TSC changes were merged into one branch through two different paths. The default bzr three-way merge did not handle this ("criss-cross") merge. I tried merge --lca and merge --weave, which worked better. I wonder when weave and lca merge algorithms are superior to the three way merge.

22 June 2008

Worked more on the font converter. Also implemented PFF2 font loading in Java, which I used in a font viewer application.

I am looking into how to compress the font data for use in GRUB. It looks like io/gzio.c only supports reading from files that include a gzip header, not from plain DEFLATE data.

Journal_2008-06-22_fonttools.png

The new font converter tool and viewer tool. Note the difference in size between the BDF file and the PFF2 file for the same font, even though the PFF2 is uncompressed.

21 June 2008

Added instructions to the Bazaar repository page on how to update local branches with changes from the online repository branch here—both for cloned branches (with bzr pull) and for lightweight checkouts (with bzr update).

Added a branch relationship diagram to help communicate how my GRUB branches are related. I tried to follow the basic branch diagram idea used by Streamed Lines by Brad Appleton et al, though mine are not as complete or as nice.

Created a new cdbmain branch off of upstream and merged my main feature branches into it. I'll periodically merge new feature updates into this branch.


I implemented a BDF -> PFF2 font converter in Java, and in the process I firmed up the file format.

20 June 2008

Having implemented routines to support filling and blitting to BGRA and BGR formats, the performance increase is a huge benefit. On my 2.4 GHz Core 2 Duo system running VMware, the following table illustrates the performance boost provided by the optimized blit and fill routines. Similar gains were observed for the VIA Nehemiah M10000.

Operation Fill 1024x768 Blit RGB->1024x768 Blit RGBA->1024x768 videotest clock
Unoptimized 55.8 19.3 19.7 2493.2
Optimized BGRA/BGR 519.0 111.0 91.0 18420.0
Improvement 830% 475% 362% 639%

19 June 2008

I was excited to discover today why graphics seemed so much slower than I thought they should be! It turns out that every video adapter I have tested on so far (nVidia 7600GT graphics, VIA Unichrome, VMware, QEMU) has supported BGRA (32 bpp) or BGR (24 bpp) but not RGBA or RGB. Without optimized graphics routines for the video format, the extremely slow color-format-independent general blit and fill routines are used.

I determined the supported video mode color formats by enhancing the vbeinfo command to display color field and mask information.

The terminology for BGR, BGRA, RGB, RGB, ARGB, and so on, felt a bit unclear to me. Information from the post ARGB, BGRA, RGBA mess by Bill Spitzak on the Cairo mailing list, helped to clear up the confusion by defining the distinguishing characteristics of RGBA versus ABGR and others.

Note that even though Spitzak says, "BGRA - Seen even less, but should be supported if ARGB is", in my testing, BGRA (32bpp with blue shift 0, green shift 8, red shift 16, alpha not used) is the format that I see supported on all the machines I've tested on except for QEMU which only supports the 24 bpp format BGR.

18 June 2008

I implemented double buffering for the VBE module using page flipping. However, VMware doesn't seem to support the VBE set display start operation, at least in the video mode that GRUB uses (for the basic video test, which uses indexed color 1024x768 mode). The existing GRUB VBE BIOS call uses VBE function 07h BX=80h, which is the set display start during vertical retrace operation. It takes a pixel row/column location to set as the display start. The return code from VBE function 07h/80h is 0x024F, where the high byte 02h indicates that the operation is not supported in the current video mode. From VBE 3 specification on function 07h:

Note that functions 02h, 03h, 82h and 83h take the display start address as a byte offset in video memory, whereas the VBE 1.2 compatible functions 00h and 80h take an (x,y) pixel coordinate as the starting address in the frame buffer. Functions 02h and 82h are preferable because they allow for correct page flipping operation in all color depths. Functions 00h and 80h have problems in 24bpp modes where each pixel is represented as three bytes, since there are some combinations of (x,y) starting addresses that may not map

After implementing a function using subfunction BL=82h, I observed that VMware fails with AX=014Fh this time.

17 June 2008

Updated the TSC patch based on input from Vesa (TSC patch 2008-06-17). I redesigned the TSC implementation to be more maintainable and flexible:

  • Extracted generic implementations of grub_get_time_ms() and grub_millisleep() into kern/generic/get_time_ms.c and kern/generic/millisleep.c so the generic code doesn't get pulled into the kernel image when a platform has a more specialized implementation.
  • Instead of having each platform define, for instance, grub_get_time_ms() to call grub_get_time_ms_generic(), we just link in kern/generic/get_time_ms.c, which defines a generic get_time_ms().
  • TSC initialization occurs by GRUB main() calling grub_time_init(), which each platform defines to do the necessary time initialization. For i386 platforms, grub_time_init() is defined in kern/i386/tsc.c to call grub_tsc_calibrate().

16 June 2008

Wrote and submitted my weekly report.

15 June 2008

Updated videotest bench to support specifying what color depth to use for each test configuration. Running in VMware, only 32 bits/pixel direct color modes are supported, not 24 bits/pixel. I have not checked the supported modes on my Mini-ITX board yet.

I added a --time/-t option to the videotest command. This sets the time limit for tests such as bench, bitmaps, and clock in seconds. The bench test also allows skipping tests by pressing any key. The bitmaps test uses the millisecond precision timer (grub_get_time_ms()) instead of the RTC for frames/s calculations. I hope that TSC calibration is accurate; it seems to be close based on my wall-time comparison for the clock operation, but perhaps some tests are in order to ensure that the performance numbers I record are accurate.

13 June 2008

Added support to videotest bench for displaying the color depth in bits per pixel. This is useful for diagnostic and optimization purposes.

I started working on the VBE page flipping implementation.

I implemented an optimization to the VBE fill utility functions so that instead of calculating the address of each row the full way, we just add the proper offset to the last pixel address of the previous row. This results in the data pointer advancing to the first pixel address of the next row. Only a single addition is necessary, instead of a multiplication and an addition. However, no performance changes was apparent on my workstation with VMware. Integer multiplication must be so fast that it is dwarfed by the memory access time. If that is the case, then even less performance is to be gained by implementing this same optimization for bitmap blitting, but it still may be worth doing since it is a very simple change.

I'd like to find out what is causing bitmap blitting to be so slow. Certainly it is more complex than filling a rectangle, but I think that for nice graphical effects, it would be important to be able to achieve screen update rates of at least 30 frames/s.

I need to post the benchmark results for other machines, including my Mini-ITX system, which I consider to be a minimum performing system. If I can make graphical effects look decent on the Mini-ITX system, then it should look fabulous on more powerful machines (any normal desktop > 1 GHz).

12 June 2008

Today I updated videotest clock to use grub_get_time_ms() instead of grub_get_rtc() in order to use the higher resolution x86 TSC. This makes the progress bar in the clock test scroll much more smoothly. Instead of making the one second scroll process in about 18 visual steps, it now makes one visual step for each pixel.

The exact semantics of the grub_video_swap_buffers() operation needs to be defined. My understanding is as follows:

The front buffer render target (GRUB_VIDEO_RENDER_TARGET_FRONT_BUFFER) always refers to the page of video memory that is currently displayed on the screen. The back buffer render target (GRUB_VIDEO_RENDER_TARGET_BACK_BUFFER) refers to another buffer that is not visible on screen. When grub_video_swap_buffers() is called, the pages referred to by the front buffer and back buffer render targets are swapped, and the page previously referred to by the back buffer is made visible.

To implement the buffer swap function, we will want to keep track of the video pages associated the front and back bufers. When drawing to the front or back buffer render target, the drawing must occur within the proper page. Then the buffer swap function itself will need to tell the video adapter to switch the displayed page, and then update the front and back buffer render targets so that subsequent drawing operations take place on the approriate video page.

For the sake of simplicity, the video pages will be implemented as vertically stacked instead of horizontally stacked, since the latter would require a different row access pitch, and might be less efficient (?) due to cache issues. The start address of the page (for effiency, since it will probably be referred to much more often than the pages will flipped), along with the page number (0 or 1) could be stored in the render target structure for the front and back buffers.

11 June 2008

Did research into what it will take to do VESA page flipping, to implement grub_video_vbe_swap_buffers().

I had some ideas for possible optimizations as well that I would like to evaluate:

  • Video performance: try inlining the get_data_ptr() function in vbeutil, possibly get_pixel(), set_pixel() too... first determine if a significant amount of time is spent there: try eliminating the call with a NOP and see if performance improves.
  • Eliminating calls to get_data_ptr for each row in the vbeblit functions by simply using mode_info->pitch to skip the right number of bytes to get to the right place within the next row. As above, first determine if the the time spent there is significant by comparing with a NOP.
  • Move grub_memmove() an inline function. This way the compiler may be able to make optimizations based on the specific circumstances for the invocation. It would be interesting to examine the generated assembly code for some common uses of grub_memmove() such as bitmap blitting to see what kind of optimizations were done (loop unrolling, conditional expression elimination, etc.).
  • Implement grub_memcpy() in addition to grub_memmove(). Since in many (if not most) cases, it is known that memory does not overlap, using memcpy instead of memmove will result in simpler, faster code that might be more efficient with CPU cache prefetching policies (since grub_memmove() copied in order of decreasing addresses in certain cases.

videotest bench should be used to determine whether these optimizations have significant performance benefits.

10 June 2008

Today I implemented a higher resolution timer for GRUB using the x86 RDTSC instruction. The TSC ticks are synchronized to the CPU clock, so at GRUB startup, the RTC is used to calibrate the TSC rate value and reference it to real time. (TSC patch)

I also fixed grub-install so it can function when installed to a prefix other than /usr/local. (grub-install patch)

To make the output of make easier to parse by eye as it scrolls by, I added support for "pretty" output for make. It replaces the full gcc commands like

gcc -Iutil -I../util -I. -Iinclude -I../include -Wall -W -DGRUB_LIBDIR=\"/usr/local/lib/`echo grub/i386-pc | sed 's,x,x,'`\" -g -O2 -DGRUB_UTIL=1  -MD -c -o grub_setup-util_getroot.o ../util/getroot.c
gcc -Ikern -I../kern -I. -Iinclude -I../include -Wall -W -DGRUB_LIBDIR=\"/usr/local/lib/`echo grub/i386-pc | sed 's,x,x,'`\" -g -O2 -DGRUB_UTIL=1  -MD -c -o grub_setup-kern_device.o ../kern/device.c
../kern/device.c: In function 'grub_device_iterate':
../kern/device.c:84: warning: generating trampoline in object (requires executable stack)
../kern/device.c:84: warning: generating trampoline in object (requires executable stack)
gcc -Ikern -I../kern -I. -Iinclude -I../include -Wall -W -DGRUB_LIBDIR=\"/usr/local/lib/`echo grub/i386-pc | sed 's,x,x,'`\" -g -O2 -DGRUB_UTIL=1  -MD -c -o grub_setup-kern_disk.o ../kern/disk.c
gcc -Ikern -I../kern -I. -Iinclude -I../include -Wall -W -DGRUB_LIBDIR=\"/usr/local/lib/`echo grub/i386-pc | sed 's,x,x,'`\" -g -O2 -DGRUB_UTIL=1  -MD -c -o grub_setup-kern_err.o ../kern/err.c
gcc -Ikern -I../kern -I. -Iinclude -I../include -Wall -W -DGRUB_LIBDIR=\"/usr/local/lib/`echo grub/i386-pc | sed 's,x,x,'`\" -g -O2 -DGRUB_UTIL=1  -MD -c -o grub_setup-kern_misc.o ../kern/misc.c

with output that, in my opinion, makes it easier to see warnings and errors:

COMPILE         ../util/getroot.c
COMPILE         ../kern/device.c
../kern/device.c: In function 'grub_device_iterate':
../kern/device.c:84: warning: generating trampoline in object (requires executable stack)
../kern/device.c:84: warning: generating trampoline in object (requires executable stack)
COMPILE         ../kern/disk.c
COMPILE         ../kern/err.c
COMPILE         ../kern/misc.c

If the variable V (for verbose) is set to 1, then the traditional full output is displayed. This is useful when you need to see which compiler flags are being used or which source files are being linked into an object file. Just run

make V=1

to get the full output. (pretty make output patch)

6 June 2008

Added Bazaar branches so anyone interested can easily track my changes. Just install Bazaar and then you can view the log for the last 5 revisions with

bzr log -r -10.. http://grub.gibibit.com/bzr/cdbmain

If you want to get the code, you can create a local copy of the branch with

bzr branch http://grub.gibibit.com/bzr/cdbmain

This will create a cdbmain directory on your local machine containing the branch. This branch will contain the full branch history. If you don't want a full branch but just a working tree, you can do a lightweight checkout instead with the command

bzr co --lightweight http://grub.gibibit.com/bzr/cdbmain

5 June 2008

This week I've been working on a video benchmark feature for GRUB. I've added it to the videotest command, which now accepts parameters indicating which test to run. At first I created a new videodemo command, but then realized that there were probably going to be more test variations such as a font test, and it seemed logical to make an easy way to see the available video tests in one place (run videotest list or just run videotest with no arguments).

The new videotest bench command runs the benchmark test for a variety of display resolutions and mode variants. The indexed color modes are commented out because they were excrutiatingly slow when blitting the RGB bitmap—on the order of several seconds per frame! The test measures the frame rate achieved when filling the screen (grub_video_fill_rect()) and when blitting a full screen bitmap (grub_video_blit_bitmap()).

Today I posted a patch implementing a video benchmark for the videotest command. (The patch also contains a Bazaar bundle and merge directive created by the bzr send command, but patch happily ignores this.)

Journal_2008-06-05_benchmark_results.png

Results of a videotest bench run.

31 May 2008

After yesterday afternoon, I felt like I needed to produce some real code, since most of the week has been just research, reading code, etc. I decided to implement a more comprehensive video test in the videodemo command. So far I have implemented code to generate a true color offscreen bitmap and fill it with an interesting pattern, then do some tests blitting it to the screen. One of the blitting tests is animated and bounces the bitmap around the screen until a key is pressed.

It is worthwhile noting the potential perils of unsigned types in C (and C++). I spent a lot of time trying to figure out why my apparently simple code was not working. It turns out that I had expressions that combined signed and unsigned integral types. The unsigned types were the viewport origin/size, which GRUB defines to be unsigned, and one of the signed types was an offset that was added to the bitmap position during the animation. This offset had to be signed since it could be either positive or negative, depending on the present direction of the bitmap's movement. The final solution was to use signed types only. I read some discussions on signed vs. unsigned types and found this quote from Bjarne Stroustrup, which in my experience is wise advice:

The unsigned integer types are ideal for uses that treat storage as a bit array. Using an unsigned instead of an int to gain one more bit to represent positive integers is almost never a good idea. Attempts to ensure that some values are positive by declaring variables unsigned will typically be defeated by the implicit conversion rules.

30 May 2008

Spent the afternoon working on the font file format, specifically trying to determine what metrics should be stored about the font. I looked at the BDF font format specification and examined some BDF font files to see what it uses. I think BDF will be the most useful intermediate format to convert from, since there are good tools that support it natively (e.g., xmbdfed), it is relatively simple to parse, and the GNU Unifont is already available in that format. xmbdfed can be used to convert other bitmap font formats into BDF format.

29 May 2008

Working on a document describing a new font file format for GRUB. I'm still in school for the spring session, so I haven't been able to dedicate as much time to GRUB as I'd like yet, but I only have a couple of weeks of classes left.

28 May 2008

I realized that the current font system will need to be updated to support multiple fonts being used concurrently, since right now the font manager (manager.c) uses whichever loaded font it first finds the requested character in. The cleanest option will be to roll the font command into the gfxterm module, since that is the only thing that uses it (except videotest, but that can easily change). Then the users of fonts will specify which font (or set of fonts) to use for rendering. Perhaps borrowing the concept of specifying preferred fonts and fallback fonts from CSS, as in

body { font-family: Georgia, "Times New Roman", Times, serif; }

would be helpful in making the font usage flexible and robust. This would need some more though, but at least for now I will need to make it possible to render text in different fonts on the screen at once. I will use the videotest module to test this work as it goes along. It would be nice to also have a way to pop up a menu of the available fonts and show a sample of each one.

I began sketching requirements for a new font file format. I will create a tool to convert .bdf and hopefully other bitmap font formats into the new GRUB format so we can make use of the many free bitmap fonts out there (GNU unifont, Proggy programming fonts, Artwiz, etc.). Started coding an addition to the videotest module to do some further tests, such as rendering whole strings of text and doing animation and image blitting. I may start with a basic pixel-pushing demo like munching squares or my good old fire demo to see what kind of graphics performance is possible with the GRUB video subsystem.

There's a good page on Wikipedia on Free software unicode typefaces.

27 May 2008

Continued looking into what changes should be made to support larger font sizes in GRUB. I think I will avoid altering the glyph caching behavior for now (as well as putting off the optimization of caching glyphs as bitmaps suitable for blitting to the video device) since it's not immediately required for me to proceed with developing the menu system. These optimizations can always be added later down the road if they seem worthwhile.

I am thinking of updating the videotest command to support graphics benchmarking and demonstrations of more complex tasks such as simple animation and rendering full strings of text.

At first I considered creating a new module to do my testing with. I looked through the GRUB build system to see what it would take to create a new module. Unfortunately, it looks really nasty, based on conf/i386-pc.mk. Just looking at the simple videotest command, there is a whole slew of rules in i386-pc.mk that pertain to videotest. After scanning through the nearly 3000 lines of makefile rules in this file alone, I feel rather disoriented. I may try to copy and paste all the rules related to videotest.mod and create my own video test module to make sure I know how to create a module successfully. If these files are completely written by hand, it seems like a lot of repetitive and tedious work to produce such a brittle thing as this huge makefile. Since various commands are written for each module scattered throughout this multi-thousand-line file, if one wanted to improve or otherwise change the build process, it would be a monumental task. The makefile rule files in the conf/ directory consist of over 15000 lines!

Based on my minimal knowledge of GRUB's build system, I expect that each module has only a few essential data associated with it such as the source files comprising it, the modules it depends on, the commands it provides, and some other details, every module has essentially the same form. Therefore I find it nearly unbearable to deal with this 15000 line beast.

26 May 2008

Official first day of GSoC coding phase! Today began documenting the GRUB font file format on the GRUB wiki. (Yay! MoinMoin supports reStructuredText!) The file format is called either PFF or PPF: GRUB uses both names so I'm not sure which is correct.

I'm looking at adding support for font sizes larger than 16x16 pixels to GRUB. This would entail an incompatible change to the file format, and I would like to make sure that the new format is flexible enough to do important tasks like provide text baseline information. Glyph bitmaps should not waste space padding to 32-bit boundaries, and within a particular glyph bitmap, should not waste space padding to 8-bit byte boundaries.

I need to look into how glyph caching is currently done. I seem to recall that the video layer does glyph caching, but it might make more sense to have the font cache its own glyphs. Then again, at the video layer, glyphs can be cached in the output device's native format. Perhaps this will require more thought before a course of action is determined. Will probably postpone this, but will keep it in mind as other work proceeds.