2011-12-28

2011-12-28 - Structure Changes

I've added the Libs, list and DOS elements back into the kernel, and wired them in.  I've also changed the way that the standard C library features are structured into the kernel.  They now have their own virtual directory courtesy of NetBeans.  I've also changed the naming convention for the standard function to remove the prefix which I had been using before.

2011-12-05

2011-12-05 - NetBeans and Subversion

Recovering from the flu, I decided to have a look at NetBeans.  I have it installed on this new machine, along with MinGW and MSYS, but I haven't gotten around to doing any OS dev work yet.

I looked at NetBeans and poked around with a few test projects, trying to figure out how best to get my structure of OS to work through the IDE.  I've come up with the idea that creating a C/C++ Static Library is the best approach, and putting 99% of the OS code into it.  That seems to use the ar tool to create a .a file which contains all the .o files.  I have then added post-build steps into the project makefile to take this .a file and link it in with my existing start.o to create the binary kernel files as I have before.  The makefile also compiles the bootblock.  I have set the Project run command to run the Bochs bxrc file (via a batch file) to then fire up Bochs with my OS loaded.

A "quick" install of Apache and Subversion later, and NetBeans is happy to push the code into the source control repository, and I can keep track of changes.  All looks good.

Currently, this set of code only contains a few of the previous files, it sets 32-bit protected mode, clears the VGA Mode 3 screen, and displays a title.  It's more of a test for the environment.  In any case, if this approach works, it will make a very good starting point to re-integrate all of the code and create the modular kernel that should have been working ages ago.

I have sent a copy of the project to Pink to test on his Linux install.  He reports that he has been able to get it to build by adding a Debug-Linux configuration into the project and tweaking some settings.  We may be able to get a Subversion repository exposed so that it can become a collaborative project, at least from the point of view of being able to get the code and run the progress so far.

2011-07-13

2011-07-13 - Threads and Processes

A few more tweaks to the Process subsystem today.  I've taken an old set of code that I was working on before this issue with Bochs not working came up, and I applied the fixes to make it work in Bochs to it.  After a little tweaking, it started to work and tick along correctly.

Tested a few threads as well (the character generator program that I developed previously) and it all seemed to work.  There is a slight issue with the display when scrolling which the semaphore should have fixed, but I think it's actually a render issue with Bochs.  The semaphore itself tested correctly.

The next step from here is to remove the Sleep(Time) code from the process system and implement a GetPid() function, Sleep(Pid) and Wake(Pid) to allow threads to control one another.  The Sleep(Time) will be reimplemented as a separate subsystem which will use its own thread (or even an interrupt handler) to wake a thread up once its timer has expired.

This should then give me the following functions:

  • GetPid(): Returns the current Pid
  • Sleep(Pid): Sets the given Pid to sleep
  • Wake(Pid): Sets the given Pid to waiting
  • Sleep(Time): Sleeps the thread for some time
  • TickHandler(): Checks for threads needing waking and wakes them.


The Top command would be modified to display the Pid in the table, and command versions of Sleep() and Wake() will be added to allow thread control for testing and lolz.

2011-07-12

2011-07-12 - Bochs and Threads

Recently I have been looking into Bochs to try to figure out why the multitasking code (which works on physical machines) fails under Bochs.

The discovery was made yesterday that the reason it was failing under Bochs specifically is because Bochs does not start with zero-initialised memory, and that the initialisation code for my multitasking did not clear its variables.  What's more is that the compiler assumed that the BSS would be zeroed, and even refused my explicit zero initialisation.  This was fixed up and the code got further before crashing.

Last night and today, I was looking into the Bochs debugger and trying to figure out why it seemed that the code compiled on my laptop was causing it to fail even after fixing the above issue.  After hours of stepping and deleting code and stepping and disassembling, I could not figure how the EBP register was being overwritten by the EIP value.
Finally, I spotted it.  The code I was using (modified from some tutorial code) set up the tasking jump using unnamed registers, and the GCC compiler was choosing its own registers to use.  Unfortunately, one of it's choices conflicted with a register I was using.  A few tweaks later and the code compiled correctly.  Also setting the "clobber" registers to the call made it compile reliably.

This was a particularly difficult issue to track down as each time the code was changed and recompiled, it could have compiled differently, and some changes would "fix" the problem, even though they did not directly affect it.  This made the problem intermittent at best.

2011-05-04

2011-05-04 - Delays and Sleep

So, I need to create some form of Timer_Sleep() function that works in a similar manner to my Timer_Delay().

Timer_Delay() currently spinlocks until the designated time ... functional, but not advisable.

Timer_Sleep() has to instead suspend the thread until the allotted time, then wake it up again.

2011-05-03

2011-05-03 - Semaphores

So my first foray into Semaphores didn't work first time.  I've implemented a test&set function, and I've created the GetSemaphore() and ReleaseSemaphore() functions which take a pointer to a semaphore and spinlock until it can be gained, and then to release it.  I tied this into the String_kprintf() function so that only one thread could be in the function at a time.  Instead of a proper lock, the system just locked when it first performed a printf, and presumably infinitely looped.

Ah ha!  In copying the code sample for the Intel implementation of test_and_set, I neglected to reverse the operands to the mov instructions, so the stack was being loaded with the values from the registers, not the other way around.  Why that would screw up the printing, I don't know.

2011-05-02

2011-05-02 - Multitasking on the Revo

Gotten the new Aspire Revo 3700 wired up in place of the thin client, nice little piece of kit with an integral hard drive amongst other things.  I'm ignoring the Linpus Linux for now and have it set to network boot, and it fired up the TFTP branch first time.

Been looking at the multitasking code using the Revo (not that it's any better in this regard than the T61) and trying to track down the problem.  Having spent ages sticking in various bits of debugging code and trying to make sense of the results, the solution ends up being stupidly simple ... the stack I was assigning to each thread was too small.  One stack would overwrite part of another, then cause it's Interrupt frame to be corrupt, crashing when that thread was next invoked.

With that 'fixed', the threads are ticking over happily.  It's currently running maybe 30 character generator threads with a quanta of 10ms to test it.  So far no problems except the video routines aren't multi-thread safe.

2011-01-15

2011-01-15 - More Dithering

Moving on from the success of Parrot dithering, I decided to run a few more tests on the quantising/dithering engine to see what kind of effects I could get out of it.  I modified the drawing routine to allow a half-dithered option where the error value is divided by two so that only half the error is applied to the following pixel.  Also adjusted the calling code to then draw three parrots with the three forms of dithering, none, half and full.  The half-dithered approach did work to soften some of the artefacts from the crude dithering in some cases, but also ruined the effect in others.

The next thing I wanted to do was to see what effect changing the palette would have on the quantiser/ditherer.  First thing I tried was a grey scale of 0x000000, 0x111111 up to 0xFFFFFF.  This worked well and gave a very striking result, except for the anticipated fact that the greens looked dark and the blues looked bright.  Also of note was that the non-dithered version looked considerably better than the dithered version as the dithering artefacts destroyed the image.  It's possible that a Floyd-Steinberg dithering will improve this as each row will influence the following one.

Following on from this, I used a commercial paint package to calculate a 16-colour palette from the source image so that I could set the VGA palette to this.  With the optimised palette in hand, I couldn't resist setting only the red colour into the palette ... the result was impressive.  Most of the parrot was highlighted in red, with the entire background in shades of grey, very satisfying.

I implemented the full optimised palette, but the result didn't seem much better than my original palette, probably because the original palette was chosen to give a wide spread of colours in the available depth.

I then tried some different images, the OS logo (not released yet :P ), and two random images from the internet.  All the images worked really well, especially the colourful logo.

2011-01-07

2011-01-07 - VGA Graphics over Christmas

Lots to catch up on here over the last two weeks, so here goes ...

Over the Christmas break, I began reading some more of the "Programmers guide to the EGA, VGA and Super VGA" book.  Taking a few ideas and information from here, I decided to revisit some of the graphics VGA elements I have in place.

First things first, I took a copy of my base OS, stripped out various bits and pieces, and ended up with a kernel that booted, and set up Mode 12h.  I also rewired the keyboard handler to reboot the machine so I didn't need to keep power cycling it.  (Idea: Use the interrupt handler to reboot the machine on the escape key always, which should prevent infinite loops blocking the soft reset.)

With that in place, my OS boots to a black, 640 by 480 by 16 colour screen, and does nothing other than reboot when I press any key.

First thing I did was got something drawn to the screen.  This was mainly so that I could see that it worked and this blank screen was, in fact, "A Good  Thing"(TM).  This was done using the the same method as before by setting the Plane Write and then writing to the memory.

This worked, so I quickly moved on to reimplementing the Plot routine to draw pixels to the screen.  Instead of the previous method of looping each plane in turn, reading the byte, masking the old byte with the new one, then writing the new byte back, the new method uses VGA Write Mode 2, sets the Bit Mask register, and writes to the memory once.  This should be significantly faster than before.

I then rewrote the DrawHorizontal() routine.  This routine draws a horizontal line on the screen in one colour, and is optimised to take advantage of the screen's memory configuration.  With this routine, I created a set of function calls to this routine so that I could verify that all the combinations of starting and ending pixels worked correctly as the calculation for this involves lots of bit shifting and boolean logic.

I knew I would also need control of the palette, so I pulled up a copy of some old code which set the palette and set about updating it.  I added a global array of sixteen 24-bit colours to the file and made a routine to read this array, and set the equivalent 18-bit colour to the palette using the old routine.  Curiously, the 16 EGA palette registers actually refer to colours in the 256 colour VGA palette, but they don't map to 0 to 15 as you might expect, so I remapped these into the 0 to 15 range for convenience.  This was all tested to ensure that I could influence the palette as required.

With all of these things working, I had a fairly boring screen with some test elements on it.  Time to throw in some Win!

When I was first toying with the Mode 12h screen, one of the things I did was to take a 640x480 picture on the PC, convert it down into 16 colours (which used a palette not far from the VGA standard) and then append the bitmap file onto the end of a kernel.  I then wrote a function to read the bitmap header, find the palette and map it to the nearest displayable colour, and then draw the bitmap to the screen.  It wasn't pretty code, and it certainly wasn't fast, but it worked and displayed the full-screen image.  One of the things I always regretted about this implementation was that I have to convert the image to 16 colours using the PC.

This time around (and using the information on Colour Quantisation and Dithering that I had been subconsciously processing since) I decided that I would not only improve the nearest colour system, but also throw in some dithering as well.  To start this off, I went to the OS Dev wiki and searched around for articles on either ... nothing, so I set about to write them.

A short while later, I had an article on Colour Quantisation that detailed how to extend or contract colours, talked about the Euclidean distance algorithm, and I have also come up with what should be a very fast method of pre-calculating Euclidean distances to greatly improve the speed of the GetNearestColour().  I had also finished an article on Dithering which covered some very basic Error Diffusion algorithms.

The main outcome from writing these articles was not the dissemination of information to help others (which is a side-benefit), but to help focus my thoughts and to allow me to write my own plan in the form of a guide to others.

I found a colourful picture from the web, specifically a 24-bit bitmap of a parrot, saved it to a file, and extracted 24-bit bitmap data from the file and placed it into a byte array inside my OS.  This would be the image data that I would use to test the routines as I wrote them.

The first step for this part was to create a routine that was able to plot 8 neighbouring pixels at the same time because this is how the Mode 12h memory is organised.  I threw this together fairly quickly, so that it accepted X and Y coordinates, a bitmask, and an array of eight palette indices to draw, and then draw them.

I then wrote the colour quantiser.  I already had the Euclidean-based nearest colour algorithm from before, and from writing the article I had worked out that a pre-calculated table of 512 entries would enough for what I needed, so I created the table, and wrote a routine to populate it based on the colours in the global palette array.

Following on from this, I wrote the routine to read the bitmap data of the parrot, use the quantiser to map each pixel in turn, and write eight pixels at a time to the screen using the Plot8() function.  Booting this up, it looked nothing like a parrot.  Onoes!

Onto the familiar task of debugging.  The first problem was easy to track down.  Bitmap (.bmp) files align each row to a 4-byte boundary, and as my image was 150 pixels wide, I needed to advance the pointer by 2 bytes at the end of each row.  The result of this problem was that the 3-byte pixels were falling out of alignment, so RGB on the first row was becoming BRG on the second, and GBR on the third, resulting in bands of colour.  This was easily corrected, and things looked a little better.

The second issue was that the GetNearestColour() wasn't correctly contracting the 24-bit colour into the 9-bit colour required to access the precalculated table of colours.  This just needed some bitmask corrections.

The display now definitely looked like a parrot, but a parrot behind a bathroom window, where each vertical stripe of the parrot looked backwards.  Was this the Plot8() routine being wrong, or the data being passed to the Plot8() routine.  Adding in a quick call to Plot8() to display a pattern of white pixels followed by purple pixels quickly revealed that the Plot8() routine was at fault and backwards.  This was quickly fixed.

Recompiling and rebooting the test machine and, tada.wav, it works.  One nearest colour parrot displayed from 24-bit bitmap data.

The quantiser was working perfectly, and the image display was fast.  Well, I think it was fast, it displayed the image before the monitor had adjusted to the Mode 12h screen, so I'm happy to consider that fast for now.  Unfortunately, nearest colour just wasn't good enough.

Turns out that to implemented my simple dithering algorithm was amazingly easy.  Create a unioned structure so that I could access the red, green and blue components of the colour easily, and create a second one that used signed integers for the three components.  This is needed of course because the error could be either positive or negative.  I added the code to calculate the error, and the code to add the error into the bitmap colour before it was quantised.  Recompiled and rebooted.

Sufficed to say, the first test was not successful, nor was the second, third or fourth.  The problem with each attempt was that I got overflow errors every time, so a high red value plus a positive red error wrapped around to a low red value and vice-versa.  For the fifth attempt, I wrote a separate function to add the colour error to the colour in a very careful manner.

Once more, tada.wav, and not just any tada.wav, but a really big tada.wav!  The dithering, whilst being simple, was amazing and worked perfectly.  One very well dithered parrot, even if it was only in 16 colours.

One more minor modification was to make the dithering enable an option to the drawing routine, along with an X coordinate start, so that I could draw two parrots side-by-side, one with nearest colour and the other dithered to see the difference.  Took photos to show people.  Big win!