2013-12-12

2013-12-12 Benchmarking Doom

I have put some benchmarking code into the Doom engine to count the number of ticks (each tick being 1/100th of a second currently) that it takes to render 20 frames and then writes it to the stdout.  It provides me with a way of getting a good FPS reading without needing to worry about floating point arithmetic.  Even though the screen is running in mode 0x12, I have wired up the kernel stdout to Bochs' "Port 0xE9 Hack" so that any text written by the kernel also appears in Bochs' separate console window.  This provides console output that works alongside the graphical output of Doom so I can get the benchmarks out without affecting the render code.

At Rich's suggestion, I also tested running Doom without the Parrot Dithering in the VGA driver, the results are:

Average with dithering is 158 ticks per frame = 1.58 seconds per frame = 0.6 FPS
Average without dithering is 115 ticks per frame = 0.87 FPS.

In order to try to work out where I can save time, I have tested a function which just pushes data into the VGA memory as fast as it can so I can see how fast this part can be (bearing in mind that it's a planar Mode 0x12 screen).  Using 32-bit writes (which may not work on all hardware) seems to allow me to paint all the planes in under one tick, so that's reasonable.

Moving on from this, I've created a planar back buffer in memory to store the data ready to be pushed to the VGA memory.  The plot and drawing routines now write to this buffer (which is faster because it can access all the planes without having to change any registers), and I've added a function to update the front buffer (the VGA hardware) from the back buffer.

All of these changes, and Doom now runs at a blistering ... 0.95 FPS ... Oh :(

It may be that the VGA card is not the slowdown here, I'll have to do some proper benchmarking ... maybe after Christmas.

2013-12-03

2013-12-03 DoomVideo

A quick screen capture video to show just how bad the frame rate is (still awesome to watch though).

The intro screen lasts for about 40 seconds, so you may want to skip past it.


I'm searching through my copy of Programmer's Guide to the EGA, VGA, and Super VGA Cards by Richard F. Ferraro (very good book) to find a better way to get the data into the VGA memory.

I tested writing all of each plane at a time using 32-bit writes, and that filled the screen in under 1/100th of a second, so fast enough for double-buffering, which is what I'm investigating.

2013-12-01

The Biggest Letters in the Whole Wide World

So, I was watching TV with my daughter the other day and a character in one of the kids programs said they were trying to make "the biggest '9' in the whole wide world".  This got me to thinking, where is the biggest '9' in the world?  For that matter, what about all the other letters?

I'd say the only ground rules are that the letter has to be a physical structure, and that the structure was intended to represent that letter (so an American Football goalpost doesn't count as a 'Y').  For the moment, I'll restrict this to the Latin alphabet

I guess most of them are going to be found on buildings or perhaps ships.  The "HOLLYWOOD" sign might scoop six of the letters, but where are the others?  Some of them may actually be quite small.  Suggestions in the comments ...


  • A
    • "READYMIX[5] 240 metres tall.
    • "BISMARK[10] 87 metres tall (estimated).
    • "CASAS BAHIA 1[7] 71 metres tall (estimated).
    • "Coca Cola[3] 15.5 metres tall (estimated).
    • "PADDY POWER[1] 15.2 metres tall.
  • B
    • "BISMARK" [10] 87 metres tall (estimated).
    • "CASAS BAHIA 1" [7] 71 metres tall (estimated).
  • C
    • "LUECKE[4] 950 metres tall (estimated).
    • "JOSTWINE.COM[6] 75 metres (estimated).
    • "Coca Cola" [3] 32 metres tall (estimated)
  • D
    • "READYMIX[5] 240 metres tall.
    • "GOD'S WISDOM[9] 28 metres tall (estimated).
    • "PADDY POWER[1] 15.2 metres tall.
    • "HOLLYWOOD[2] 14 metres tall.
  • E
    • "LUECKE[4] 950 metres tall (estimated).
    • "READYMIX[5] 240 metres tall.
    • "JOSTWINE.COM[6] 75 metres (estimated).
    • "PADDY POWER[1] 15.2 metres tall.
  • F
    • "FOWL[11] 55 metres tall (estimated).
  • G
    • "GOD'S WISDOM[9] 28 metres tall (estimated).
  • H
    • "CASAS BAHIA 1[7] 71 metres tall (estimated).
    • "HOLLYWOOD[2] 14 metres tall.
    • Pink suggested a Helipad somewhere?
  • I
    • "READYMIX[5] 240 metres tall.
    • "BISMARK[10] 87 metres tall (estimated).
    • "JOSTWINE.COM[6] 75 metres (estimated).
    • "CASAS BAHIA 1[7] 71 metres tall (estimated).
  • J
    • "JOSTWINE.COM" [6] 75 metres (estimated).
  • K
    • "LUECKE[4] 950 metres tall (estimated).
    • "BISMARK[10] 87 metres tall (estimated).
    • "FOWL[11] 55 metres tall (estimated).
  • L
    • "LUECKE[4] 950 metres tall (estimated).
    • "Coca Cola[3] 32 metres tall (estimated).
    • "HOLLYWOOD[2] - 14 metres tall.
  • M
    • "READYMIX[5] 240 metres tall.
    • "BISMARK[10] 87 metres tall (estimated).
    • "JOSTWINE.COM[6] 75 metres (estimated).
    • "Platte Mound M" - 73 metres tall.
  • N
    • "JOSTWINE.COM[6] 75 metres (estimated).
  • O
    • "JOSTWINE.COM[6] 75 metres (estimated).
    • "FOWL[11] 55 metres tall (estimated).
    • "GOD'S WISDOM[9] 28 metres tall (estimated).
    • "Coca Cola[3] 15.5 metres tall (estimated).
    • "PADDY POWER[1] 15.2 metres tall.
    • "HOLLYWOOD[2] 14 metres tall.
  • P
    • "PADDY POWER" [1] 15.2 metres tall.
    • "PLAZA MAYOR[8] 14 metres tall (estimated).
    • "P&O" Cruise Ships 8 metres tall (estimated)
  • Q
  • R
    • "READYMIX[5] 240 metres tall.
    • "BISMARK[10] 87 metres tall (estimated).
    • "PADDY POWER[1] 15.2 metres tall.
    • "PLAZA MAYOR[8] 14 metres tall (estimated).
  • S
    • "BISMARK[10] 87 metres tall (estimated).
    • "JOSTWINE.COM[6] 75 metres (estimated).
    • "GOD'S WISDOM[9] 28 metres tall (estimated).
  • T
    • "JOSTWINE.COM[6] 75 metres (estimated).
  • U
    • "LUECKE[4] 950 metres tall (estimated).
    • "Block U" 30 metres tall.
  • V
  • W
    • "JOSTWINE.COM[6] 75 metres (estimated).
    • "FOWL[11] 55 metres tall (estimated).
    • "GOD'S WISDOM[9] 28 metres tall (estimated).
    • "PADDY POWER[1] 15.2 metres tall.
    • "HOLLYWOOD[2] 14 metres tall.
  • X
    • "READYMIX" [5] 240 metres tall.
  • Y
    • "READYMIX[5] 240 metres tall.
    • "PADDY POWER[1] 15.2 metres tall.
    • "HOLLYWOOD[2] 14 metres tall.
    • "PLAZA MAYOR[8] 14 metres tall (estimated).
  • Z
    • "PLAZA MAYOR[8] 14 metres tall (estimated).
  • 0
  • 1
    • "CASAS BAHIA 1[7] 71 metres tall (estimated).
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9



  • [1]  "PADDY POWER" http://www.telegraph.co.uk/advertising/news/7465528/Worlds-biggest-advertising-sign-built-overlooking-Cheltenham-Racecourse.html

    [2]  "HOLLYWOOD" https://maps.google.com/maps?ll=34.134029,-118.321611&spn=0.001039,0.002064&sll=34.092809,-118.328661&sspn=0.06653,0.132093&t=h&z=20

    [3]  "Coca Cola" https://maps.google.co.uk/maps?ll=-18.529371,-70.249503&spn=0.00238,0.004128&sll=-18.481898,-70.250197&sspn=0.019049,0.033023&t=h&z=19

    [4]  "LUECKE" https://maps.google.co.uk/maps?ll=30.081684,-97.140995&spn=0.00869,0.016512&sll=52.8382,-2.327815&sspn=12.439947,33.815918&t=h&z=20

    [5]  "READYMIX" https://maps.google.co.uk/maps?ll=-32.21714,125.361149&spn=0.016992,0.033023&sll=52.8382,-2.327815&sspn=12.439947,33.815918&t=h&z=16

    [6]  "JOSTWINE.COM" https://maps.google.co.uk/maps?ll=45.800234,-63.381817&spn=0.003501,0.008256&sll=52.8382,-2.327815&sspn=12.439947,33.815918&t=h&z=18

    [7]  "CASAS BAHIA 1" https://maps.google.com/maps?ll=-23.23482,-46.862687&spn=0.004614,0.008256&t=h&z=18

    [8]  "PLAZA MAYOR" https://maps.google.com/maps?ll=36.655336,-4.47956&spn=0.001007,0.002064&sll=36.655314,-4.479591&sspn=0.001007,0.002064&t=h&z=20

    [9]  "GOD'S WISDOM" https://maps.google.com/maps?ll=42.46578,-72.08783&spn=0.001852,0.004128&sll=42.465956,-72.089957&sspn=0.014816,0.033023&t=h&z=19

    [10]  "BISMARK" https://maps.google.com/maps?ll=46.815614,-100.722774&spn=0.001718,0.004128&sll=46.81627,-100.720757&sspn=0.003436,0.008256&t=h&z=19

    [11]  "FOWL" https://maps.google.com/maps?ll=44.829679,-87.905474&spn=0.00178,0.004128&t=h&z=19



    2013-11-30

    2013-11-30 Doom Demo

    Not too much time to investigate things today, but I thought I'd briefly look into the problem with the demo not playing in Doom.

    Turns out the demo was for version 1.09 and the game is version 1.10.  Also turns out if you callously comment out the version check and pretend it's all ok, it works  :)


    The frame rate is currently about 0.9 frames per second, but almost all of that time is my video routine drawing the 24-bit bitmap to the screen, plenty of room for improvement.  I'll probably make a video benchmarking function to maybe count the time it takes to render 50 frames so that I can clearly test each modification I make.  Maybe over Christmas ...

    2013-11-30 Doom Progress Continued

    So last night I cleared a few more bugs in my kernel and libraries, and got Doom to the point where it stopped outputting text to the console because it gone into its main loop ...

    Loading Operating System ...
    Kernel Initialised
    Loading ELF library
    
                                DOOM Registered Startup v1.10
    V_Init: allocate screens.
    M_LoadDefaults: Load system defaults.
    dos_openFile: Opening "devdatadefault.cfg".
    Could not find the device.
    Z_Init: Init zone memory allocation daemon.
    W_Init: Init WADfiles.
    dos_openFile: Opening "DH1:Doom/base/doom.wad".
     adding DH1:Doom/base/doom.wad
    ===========================================================================
                     Commercial product - do not distribute!
             Please report software piracy to the SPA: 1-800-388-PIR8
    ===========================================================================
    M_Init: Init miscellaneous info.
    R_Init: Init DOOM refresh daemon - [.....                     ]
    InitTextures
    InitFlats............
    InitSprites
    InitColormaps
    R_InitData
    R_InitPointToAngle
    R_InitTables
    R_InitPlanes
    R_InitLightTables
    R_InitSkyMap
    R_InitTranslationsTables
    P_Init: Init Playloop state.
    I_Init: Setting up machine state.
    D_CheckNetGame: Checking network game status.
    startskill 2  deathmatch: 0  startmap: 1  startepisode: 1
    player 1 of 1 (1 nodes)
    S_Init: Setting up sound.
    S_Init: default sfx volume 8
    HU_Init: Setting up heads up display.
    ST_Init: Init status bar.
    

    My original plan was then to design and write the device management subsystem, migrate the vga driver code, implement the graphics library, then get Doom to open the graphics library in order to output to the screen.

    Unfortunately (fortunately?), my impatience got the better of me and I thought I might just try a quick 'n' dirty system call to get the bitmap that Doom had generated onto the screen.  I pulled much of the code from the VGA driver that I used in the 16 colour image article, and called the initialise() function to switch from the mode 3h VGA text screen to the mode 12h VGA graphics screen, with 640x480 pixels by 16 colours.

    Doom's bitmap uses 8 bits per pixel, each pixel's byte is used as an index into a colour mapping array to get a new byte, which is then used as an index into a palette array to get three bytes for red, green, and blue.  People familiar with the VGA hardware will recognise these two levels of translation as features that VGA provides natively.  I guess that's why the original Doom was written that way.  In any case, I figured I could get something recognisable if I just took the bitmap array and drew it directly, so the initial bitmap gave the value 0-255 for the blue component of each pixel.

    I wrote a system call which accepted the bitmap pointer, width and height, and used a quick function to call the plot() function in the VGA driver, which gave me a quarter screen blue image, but one which bore a passing resemblance to the Doom intro screen.

    This image only filled quarter of the screen, so a few tweaks had it full-screen.  Doom was designed to run a 320x200 mode 13h screen with 256 colours, so it needed enlarging.


    After spending some time investigating the format of the Doom bitmap and finding out about the palette, I modified the Doom render routine.  I wanted to give the 24-bit bitmap to the system call, rather than worrying about passing it the colour map and palette.  I allocated a second screen buffer that was 3 bytes per pixel for the doom screen and added a loop to copy each pixel, translating it for the colour map and palette, and wrote the 24-bit colour to the second buffer.

    I used the same bitmap drawing routine that was used for the parrot, and draw the image without dithering.  This was the first of the images that I posted yesterday.  Turned on the dithering and posted the second image.  My brain told me the image was a little "off", but I wasn't sure how.  I looked for a comparison image on Google and then spotted that red and blue were reversed.  Behold!


    The vertical cyan lines are left-overs because I didn't clear the screen buffer after switching to Mode 12h, and the bitmap drawing routine supports transparency, which is why they show through the black areas.


    Bugs fixed


    These are the bugs I fixed in order to get Doom to its main loop.  We don't need to go into details ...

    • strncasecmp() was checking one more character than it should have been, so it couldn't find "SW1BRCOM".
    • I had stripped all of the netcode from Doom because I don't have my network stack in this kernel yet, but apparently some of it's required, so I had to put some of it back in.
    • I hadn't implemented the precision parameter of sprintf() so it didn't construct the font texture names correctly.  It was looking for "STCFN33" rather than "STCFN033".
    • sprintf() also wasn't writing a null-terminator, which apparently it needs (who knew?), so it was looking for "STTNUM10" rather than "STTNUM1".

    Next Steps

    When I next get time on this, I plan to address the following:

    • "Demo is for a different version of the game".  This well-known Doom error is causing the game to exit shortly after it starts.  If I can fix this, Doom should go into playing its opening demo.
    • Keyboard input.  I haven't looked into how Doom accesses the keyboard, but it will need at least key-up and key-down events which is more than the C library provides.  I'll need to think about this some more, but I'll probably create some form of message queue and port which Doom can open and listen for events.  This will be akin to how it will work under a window manager anyway.
    • Implement access().  Doom uses the access() function to determine which wad files it has available.  If I finish the implementation of this, I could upload an archive of the emulator and the game (without the wad file, maybe with a shareware wad), for people to toy with.
    • Write the device manager.  Not specifically for Doom, but the full implementation of the vga driver needs the device manager.
    • Write the proper vga driver (not the hacky one that's there now)
    • Write a sound library.  This'll probably need the device manager, and is the one big thing I don't have a pre-existing kernel for testing.
    • Make it faster!  It's not fast, we need to go faster, more speed!

    2013-11-29

    2013-11-29 Doom Progress


    ... and with a bit of parrot-based dithering ...


    Oops, of course red and blue were backwards.



    2013-11-24

    2013-11-24 Doom Progress

    Continuing my work on porting Doom ... actually, that isn't really fair.  I'm not making Doom work with my OS, I'm writing my OS to work for Doom, semantics.

    Continuing my work on my OS, Doom is locating and opening the wad file now.  It uses the effectively finished path of Program -> C Library -> Kernel API -> DOS Layer -> File-system -> Block Device to locate the file and open it.  Still happy with that set-up.

    Doom is, however, complaining that the wad file doesn't have the correct signature.  That may have something to do with not having connected the read() function into the DOS layer ... there, fixed.

    The kernel is now exploding (technical term), screen gibberish and inconsistent results.  After an hour or so of debugging, I've tracked down the two causes:

    1. Doom was allocating 36k of memory on the stack ... the stack is only 16k in size.  The rest of the space was overwriting the kernel ... d'oh!  (Makes stack bigger ... shhhh!)
    2. It appears as if all the remaining memory in the memory allocator is being used suddenly, causing an out-of-memory situation.
    Another hour of debugging later and I've found the problem.  Every allocation of memory has a header and a footer.  They both include information such as the length of the block, a magic number (to help detect overflows), and a flag which indicates if the block is currently used or free.


    When freeing a block, the memory allocator looks to see if the block being freed and the preceding block can be combined to make a bigger free block, then does the same for the following block.  It examines the footer of the preceding block (which is immediately before the header of the block being freed, obviously) to see if that block is free.  If so, it uses the length stored in the tail of the preceding block to find the header of the preceding block, then updates everything to combine them.  The bug was that in one circumstance, the tail pointer free flag was not being set which created a block where one flag said it was free and the other said it wasn't.  :(

    The allocator looked at the previous tail flag and it said the block was free, so it dutifully added the length of the block being freed onto the previous block.  Seeing that the following block was also free (the following block being all the remaining free memory on the system), it added that in as well to make one big contiguous free block ... except that the previous block wasn't free.  The tail flag said it was free, the head flag said it was in use.  In a flash, freeing a block of memory had consumed every available byte of memory  :(

    Easy to fix, I'm glad that it happened now, and I'm glad that my memory allocator has one fewer bug in it.

    Doom approves of my fix:

    Loading Operating System ...
    Kernel Initialised
    Loading ELF library
    
                                DOOM Registered Startup v1.10
    
    V_Init: allocate screens.
    M_LoadDefaults: Load system defaults.
    dos_openFile: Opening "devdatadefault.cfg".
    Could not find the device.
    Z_Init: Init zone memory allocation daemon.
    W_Init: Init WADfiles.
    dos_openFile: Opening "DH1:Doom/base/doom.wad".
     adding DH1:Doom/base/doom.wad
    ===========================================================================
                     Commercial product - do not distribute!
             Please report software piracy to the SPA: 1-800-388-PIR8
    ===========================================================================
    M_Init: Init miscellaneous info.
    R_Init: Init DOOM refresh daemon - Error: W_GetNumForName: PNAMES not found!
    Exited!
    

    Next time:  Investigating what PNAMES is and why it wasn't found.