2014-06-09 Animated GIFs

While I was working through some of the significant changes to the windowing system to get input events and window painting working, I thought it might be useful to have something a bit more light-weight than Doom to be able to test some things (not that Doom takes long to load anyway).  I decided that getting images to load and display might be interesting, and I thought what better place to start than with animated GIFs (pronounced with a soft 'G' apparently, as in "Jug").

Examining all the GIF89a specifications, I was surprised to find that GIF files can easily have more than 256 colours per frame, and the fact that most graphics tools limit files to 256 colours is because they're poor implementations of the standard.  That said, there is a question on how many programs could correctly read and display such a GIF (mental note: test major browsers for support).

Opening the files and working through the general container format for the GIF files was no different to any other graphics file format, the two really interesting parts are the multiple images per frame (how you get more than 256 colours per file and optimise animations) and the LZW encoding for the images.

When dealing with GIF files, each file contains a number of logical "screens" which are animation frames (one for a static GIF, multiple for an animated GIF), then each "screen" is built up of one or more "images".  Each image provides a part of the screen image, so you could tile multiple images to make up each screen (each frame of animation).  Each image has a palette limit of 256 colours, so by tiling as many "images" as you need to make up each "screen" you can easily get more than 256 colour GIF files.  Most files, however, only use a single "image" per "screen" and are therefore limited to 256 colours.

The LZW encoding is more intricate, and there is a lot of conflicting and incomplete information on exactly how you go about interpreting the data.  Because of this, I'm not going to go into detail on this until my implementation is complete to the point of working with all of my test images.  Be aware that a lot of code posted on the internet under the heading of "LZW Decoding" is actually the GIF-specific variant of LZW coding.

Because the graphics output is the same window-system method as Doom is using, all the output is already in-place and tested, as long as I can build an appropriate Bitmap structure from the image data, and I get dithering for free if required.

Such poking and frustration later ...

Yes it does animate, but you'll have to take my word on that for now.  I could create an animated GIF of my OS playing an animated GIF for you all to enjoy, but not today (Yo dawg, I heard you like animated GIFs ...).  You can still see the section of border to the left of the graphic is still being overwritten, that's the VGA driver blitting routing still not supporting masking correctly.

I have a host of other animated GIF images, including some simple ones that Leah made for testing, but not all of them work.  Some of them run the system out of memory (it only has a few meg for the memory manager at the moment), some of them have LZW coded data that causes my LZW decoder to fail (still need to find out why).

At some point, the code for loading the GIF files (currently incorporated into the Hello World test app) will be extracted out and built into a class to be loaded by the codec system, a part of the OS I'm really looking forward to writing  :)

One of the benefits of writing all your own window manager code, including the routine to draw the window chrome, is that I get to do things like this:

The Amiga Kickstart 1.3 window chrome faithfully reproduced, loading a GIF of the boot screen.  I also coded in another font that's closer to the Workbench standard.  It isn't Topaz, but it's close.

I'm very happy with that :)

(I think that's the last article I had to publish from before my three month break from development, hopefully I get to do some new stuff now.)

2014-06-02 More Windowing Progress

Good progress today, fixed a lot of the smaller bugs which were obvious from the last couple of days, and also got two big blocks of functionality into the VGA driver to make things better.

One of the things I'll call a "small bug" is that I've thrown some hacky code in to the current keyboard handler to gather the key up and key down events for the important keys and push them into the window manager, which then adds the events into the event queue for the "active" window.  Because I can't currently select the "active" window, I have added a pointer to the "last opened window" (effectively the tail of the window list) to mimic this for now.  I've removed the test code which pushed input events into new windows, and Doom is actually now playable.

Completed:
- Added the ability to blit bitmap objects onto the screen via the VGA driver.  This means Doom is a lot faster again and has dithering back.
- Added an efficient DrawLine() function to the VGA driver.  This greatly speeds up the window drawing.
- Fixed the KeyUp and Keydown events being reversed.
- Fixed the window title text being drawn in the wrong place.
- Added backspace handling to the window console mode.

Next steps:
- Fix the console scrolling.
- Identify the bug in the keyboard handling.
- Get all drawing routines to use the back buffer to re-enable double-buffering.
- Add the masking support to the Plot8() function (Doom left border problem)
- Identify why the Mode 12h code doesn't work on the Netbook.
- Investigate sound.

2014-06-01 Input Events

Recently, I've been thinking about the minimal required implementation for getting input events wired into the windowing system as well.  This is going to be a good step forward as I may actually be able to play Doom, rather than just watching the demos.  I also had a call with +Pi nk for assistance and support with working this through, many thanks  :)

The plan is to add a structure which represents a single input event which contains the event type (key down and key up to start with) and some data (which key), add a List to the window to store the input events, add a function to dequeue the next input event from a specific window and return it, and the window manager will need some method of getting keyboard events into the queue.

Reviewing how the Linux Doom source code processes input, it seems to fetch XWindow events in a similar manner, converts them into Doom input events, then calls a Doom function to push them into a queue.  I'll reinstate a version of this code, but wired to get the event using my new function and modified to convert from my event structure into the Doom event.

One note here is that the XWindows GetEvent() function blocks if there are no events to serve, and the Doom code calls a separate function to determine if there are events ready so that the game doesn't stop every frame waiting for input.  My function will return NULL if there are no events, so I'll need to adjust the code in Doom to account for this.

Having modified Doom to read and process the input events, I need to get some events into the queue.  Whilst I do have a PS/2 keyboard handler in the kernel, it's wired up to output ASCII values from key down events only, where as we need key up and key down events for all the keys, even non-ASCII ones.  In order to test the event pipeline and the event handling code in Doom, I've put some code into the OpenWindow() function to push some key presses into the event queue of the Doom window, specifically 'Escape', 'Enter', 'Enter', 'Enter' which should bring up the menu, select 'New Game', select the episode, then select the difficulty to start the game.

All this in place and it works a treat.  Doom loads, then goes into the menu, and starts the game, leaving the character standing at the beginning of level 1.  \ o /

(The screenshot is from a slightly later test where some keyboard events are wired in ... spoliers)

2014-05-31 Doom Windowing

Found some time today to look at some things.  First thing to address is that since putting in the windowing code, Doom has failed to load and caused a recursive crash.  While I haven't actually tracked the cause of this, it only happens if I compile using my Debug_Map configuration (a build configuration in the project which outputs the link map during the build, useful for debugging).  It's probably something related to output directories or something, but I can work around it for now.

Before now, I had a special routine in the kernel library which accepted the kind of bitmap that Doom outputted and drew it to the screen.  With the windowing system progressed, this has been slightly modified to accept a pointer to the window structure as well.  Now, Doom calls OpenWindow() to create a window,  then calls this DrawBitmap() function each frame to actually put the bitmap onto it.  This new version of the DrawBitmap() function currently uses SetPixel() to draw each pixel on the screen one-at-a-time, which isn't fast, but should allow me to get things running and debugged more easily.

At the moment, the windowing system doesn't handle windows overlapping one another, or moving them, but there's plenty to do before worrying about minor things like that.  I also broke the USB Mass Storage driver at some point, so I had to track two small bugs in this before I could test this on real hardware.  I hadn't reset the USB port before calling SetAddress() against device 0, and I hadn't reset the transfer descriptor CurrentPage property between calls.

With these bits in place, Doom is running in a window on the screen, and is outputting the console text to the console window.

It's not fast, and it's not dithered currently, but it's working and running the Doom demos (I nearly know the demos off by heart now).

A few things stand out from this image which aren't quite correct

1. The window title text for the Doom window is actually drawing over the Console window for some reason.
2. The console text doesn't scroll, so when it gets to the bottom, it just overwrites the last line.
3. Many other things :)

2014-05-16 Graphics and Windowing

I've been working through putting in a skeleton windowing system in, although this has required a large rework of the graphics system.  This hasn't actually been a bad thing as it has given me opportunity to add a "Bitmap" structure.

So, what's so special about the bitmap structure?  Well, it starts off being the header of a generic, in-memory bitmap.  In this form, it has a width and height, it has optional palette information, it has details of the layout, format of the pixels and the "pitch" of the bitmap (the number of bytes per pixel row, including padding), and a pointer to start of the actual bitmap data.

Alongside the bitmap structure, we have graphics functions which accept a pointer to a bitmap structure and perform some operation on them.  The basic functions are:

bitmap_t* allocateBitmap( uint16 pWidth, uint16 pHeight, uint16 pPaletteSize, colourType_t pPaletteType );
void freeBitmap( bitmap_t* pBitmap );
uint32 getNearestPaletteEntry( bitmap_t* pBitmap, colour_t pColour );
void setPaletteEntry( bitmap_t* pBitmap, uint32 pPaletteEntry, colour_t pColour );
colour_t getPixel( bitmap_t* pBitmap, uint16 pX, uint16 pY );
void setPixel( bitmap_t* pBitmap, uint16 pX, uint16 pY, colour_t pColour );
void drawLine( bitmap_t* pBitmap, bitmap_t* pMask, int32 pX1, int32 pY1, int32 pX2, int32 pY2, colour_t pColour );
void drawRectangle( bitmap_t* pBitmap, bitmap_t* pMask, int32 pX1, int32 pY1, int32 pX2, int32 pY2, colour_t pColour );
void fillRectangle( bitmap_t* pBitmap, bitmap_t* pMask, int32 pX1, int32 pY1, int32 pX2, int32 pY2, int32 pColour );
void placeChar( bitmap_t* pBitmap, bitmap_t* pMask, font_t pFont, int pCharacter, int32 pX, int32 pY, int32 pColour );
void blitLocal( bitmap_t* pBitmap, bitmap_t* pMask, uint32 pSourceX, uint32 pSourceY, uint32 pWidth, uint32 pHeight, uint32 pDestinationX, uint32 pDestinationY);
void blitRemote( bitmap_t* pSourceBitmap, uint32 pSourceX, uint32 pSourceY, uint32 pWidth, uint32 pHeight, bitmap_t* pDestinationBitmap, bitmap_t* pMask, uint32 pDestinationX, uint32 pDestinationY);

I won't explain all of these in detail, but the non-self-explanatory parts ...

• The mask is a binary bitmap the same size as the bitmap object, but the drawing routine can only alter a pixel in the given bitmap if the corresponding pixel in the mask bitmap is on.  Often though, the mask will be null, which means that no masking is to be performed.
• The "nearest colour" functionality from the Displaying Images in 16 Colours article is also incorporated into the graphics function with the mapping table stored as part of the bitmap structure itself.
• BlitLocal is for copying ("Block Transferring") a rectangle of bitmap to somewhere else in the same bitmap.
• BlitRemote is for copying from one bitmap to another bitmap.

So, all very boring, why am I that happy with it?  Well, the bitmap structure also contains a series of function pointers for the same graphics operations and if these pointers are non-null, the graphics functions above will just call the given function (this is similar to the operations structure in the FILE structure in C).  These functions allow it to integrate very well with the windowing functions.

Still not getting it, okay, how about "every graphics device is represented by a bitmap structure"?  That do anything for ya?  It's polymorphism, Holmes!

Yes, each monitor / screen / graphics device is represented by a bitmap structure that is known to the windowing system, so drawing to the screen is as easy as drawing to any in-memory bitmap, and uses the same functions to do it.  If you want to draw a line on the screen, no problem.  If you want to "block transfer" (known as Blitting) a window bitmap to the screen, you call the graphics blitting routines.  If you want to read a section of the screen, you blit from the screen to a bitmap.

A graphics device which is using a memory-mapped framebuffer needs nothing more than the bitmap structure which defines the structure and location of the framebuffer.  If the graphics device is more complicated, or offers some form of hardware acceleration, it has a bitmap structure which provides functions for the various function pointers which the graphics routines call.  This is the case for the VGA Mode 12h driver because of its planar structure and requirement to use a windowing function to access the entire bitmap.

Each window in the system can have a bitmap to act as a back-buffer, but it doesn't need one.  If a program tries to draw to its window and it has a bitmap, the drawing routines draw to the bitmap, then if that area of the window is visible on-screen, the window bitmap is "blitted" (with a mask) onto the screen (or screens) with which it intersects.  If the window doesn't have a bitmap, the graphics routines are translated directly to the screen(s) with the mask bitmap set to account for the window being partially or wholly obscured by other windows.

A future enhancement for this whole caboodle is to incorporate the ability to add a 2D transform matrix to into the system at some point (not worked out where yet) so that bitmaps, windows, and even screens can be scaled, rotated, sheared, translated and whatnot to no end of amusement.  :D

Anyway, I'll leave you with a picture of what is currently the system console window with my beautifully hand-crafted window border design ...

(Did I mention the library system was working?)

2014-03-29 Library Memory Mapping

I haven't posted anything for a while, there's a big project on at work which is taking up a lot of my time.

I've been thinking about libraries and how they will work, mainly in how the memory management will work in such a way that it will work for the library and the whatever the program is doing.

Having considered and investigated various approaches, I think I've come up with the best solution.

At the point the program starts executing, the kernel has set up an address space, and loaded the program text (the code) at address 0, followed by the data and bss (uninitialised data) as set by the executable file.  The stack of the program will have been set at some arbitrarily high address, such as the top of the address space.  The kernel will have set and be keeping track of the "stack break" value, which is the top of the heap.  This state is shown in A below.

Note that because this program was written in C, it has the appropriate C library has been linked into the program executable, and includes the malloc() function and memory management functions.  It's also possible that this program may have been written purely in assembly in which case it won't have a C library and will have some other form of memory management.

The first time that the program calls the malloc() function (or during the C library initialisation, depending on the library), the memory allocator in the program's C library will make a call to the kernel function sbrk() to move the break value up by a certain amount, maybe a few megabytes, as shown in B.  The memory allocator in the program will then use this space for any allocations needed by the program.  When this space has all been allocated, the memory allocator makes another call to sbrk() to get another part of the address space.

Imagine that the program now wants to load a maths library.  It calls the kernel function openLibrary(), requesting the library.  The kernel locates the library, and moves the break value of the process up again to secure an area of the address space for the new library, and loads it.  This is shown in C.

Note again that this library has also been written in C and linked to its C library, but this C library may be different to the one in the program in such a way as to be incompatible.  This would prevent the maths library from using the malloc() implementation that is in the C library of the program.

If the newly-loaded Maths library now wants to allocate some memory for itself, it will make a separate call to the kernel sbrk() function.  This returns another area of the address space, which the memory allocator in the Library then uses for allocations.  This is shown in D.

So, if the program now more space to use for more allocations, it can make another call to sbrk() which will return another slice of the address space pie.  This new space won't be contiguous with the previously allocated program memory space, but that's OK because the memory allocator in the program's C library won't worry about that.

All right, I think that's enough for now, I think it all makes sense and should work for any combination of programs and libraries, regardless of whether they're using the standard C library, a non-standard C library, or just some custom assembly for memory management, as long as they all behave and use sbrk() and openLibrary() correctly.  I know I haven't mentioned mmap() but it should follow the same rules.

2014-02-01 Further Tweaks

I gave a short demo of Doom running on the Revo to a few friends (because the video was so poor) and came away with a number of suggestions:

• Fixing the VSync issue
• USB Keyboard Device and Input Queue to make the game playable
• Sound and Music
• Finding out the actual frame rate
• USB Serial interface for streaming console output
• USB Flash Drive performance
• Doing happy dance

I've been looking into fixing the smaller items on this list.  The vertical sync was the easiest one, it was 3 lines of code.  In the function to update the front buffer from the back buffer, I put in a spin-lock to wait for the VGA device to be in the vertical retrace period before it started the swap.

I found that the VGA emulation in Bochs doesn't actually support the vertical retrace register, which was a bit disappointing as this means Doom now freezes before the first frame in this spinlock waiting for a VSync that will never come.  I mitigated this by adding code to the VGA initialise() routine to test to see if the vertical retrace register changes value in 100 milliseconds.  There should be 6 vertical retraces in this time (assuming 60Hz), so if the value never changes I assume the register isn't supported and clear the "Enable VSync" flag.

I also investigated why the "wipe" in Doom wasn't working.  The wipe is used when the game is transitioning to the game from the menu or vice versa.  The problem was easily resolved.  When I had removed the code from the I_Video.c file to get Doom to compile without the Linux specific video code, I had removed the content of the I_ReadScreen() function which is used to perform this wipe.  It just returns data from Doom's own internal buffer, so I didn't need to change it and shouldn't have removed it.  With the code reinstated, the wipe now works and as an added benefit, the background for the HUD now appears correctly.

Next I have looked into the load time issue because it really shouldn't take five minutes to load.  My first plan is to increase the amount of data that I transfer from the USB device in each transfer.  Currently I transfer one block at a time as required and cache it in the block device driver in case it gets accessed again next time.  If I increase this to load 8 blocks at a time (aligned to an 8 block boundary), this shouldn't take any more time to load from the USB (I figure I can transfer just over 100 blocks in a 1ms frame assuming USB2 speeds and no bus contention) and should improve reading from subsequent blocks.  With this change in place, the load time is now a respectable 38 seconds.

Still not happy with that though.  The next target is the delay I have while I wait for the USB bus to transfer the data.  Because my OS has the Programmable Interrupt Timer set to 100Hz, my delay function has a maximum granularity of 10ms and I'm using two such delays in the block loading (one after issuing the request, one while waiting for the response).  To replace these, I've written a helper function which will examine the status flags on the USB Transfer Descriptors and will spinlock until they are processed with whatever result.  As the USB transfer should complete in under 1ms, this should save 19ms per 8 blocks loaded.

With all that debugged, The OS goes from the Grub screen to the Doom splash screen in 3 seconds ... boom!