My GUI... check, optimization, hints...

Greetings fellow programmers... On Wed, Oct 2nd I started coding my GUI for my operating system. I did this every school day since then in my spare time in Period 3 of 4 (In my peer-tutoring class - I help Grade 10's program in Turing). Because I have to help people, I get about 30 mins a day...

Stats about the GUI:
- Compiled with the PowerC Compiler (email me for it)
- Can handle a current MAX of 64 windows. (can be
changed to whatever with 1 line)
- Enables the user to move, select, deselect
windows to make them active or what not.
- 500 lines of C Code...
- 2D engine allows clipped rectangles and pixels
EVENTUALLY I WILL ADD A DOUBLE BUFFER TO REMOVE FLICKERING

Controls(will change to mouse soon): Arrow keys to move the cursor (a pixel) and space bar to select windows for making active, once more to select to move, and once more to deselct. Currently I have tons of other squares and such drawn... the GUI itself is the group of 3 windows. Here is a search loop:

Code:

---

unsigned char inwhatwin(int x, int y)
{
    unsigned int tz;
    unsigned char i;

    for (tz = 0; tz < MAXWINDOWS; tz++)
    {
        for (i = 0; i < MAXWINDOWS; i++)
        {
            if (wm_elements[i].zorder == tz)
            {
                if (wm_elements[i].flags & WMFLAGS_ACTIVE)
                {       
                    if ((x >= wm_elements[i].x) && (x < (wm_elements[i].x + wm_elements[i].width)))
                        if ((y >= wm_elements[i].y) && (y < (wm_elements[i].y + wm_elements[i].height)))
                            return i;
                }
            }
        }
    }

    return 255;
}

---

That will start at the top(most visible) active window and search if (x,y) is in it. If not, it'll check the next top most, next top most, etc... wm_elements are the windows. MAXWINDOWS is 64. Returns the handle of the window that the (x,y) point is in of 255 if in none... All of my search and redraw loops look pretty much the same as that. I don't want to give out my actual source file...

I am wondering if ANY one could optimize this loop to make it run faster.

for (tz = 0; tz < MAXWINDOWS; tz++)
{
for (i = 0; i < MAXWINDOWS; i++)
{


those are basically the same loop, just twice...possibly you can make it 1 loop, but handle i using an if statement using mod?

not sure how much it would help, but its just a though

btw looks really cool :cool:

The first loop is for checking the zorder, the second loop is for going through all windows to check if that temp zorder (tz) exists... check the code to see what I mean...

Thanks for the compliment... This is what it'll become in like a year... :rolleyes: :) When you see the pic, it'll be one heck of a transformation... But it'll be nice...

just what Im saying is they both go from 0 to MAXWINDOWS, seemed kind of redundant to me, but I've never really done much in optimizing. :)

Thats a really cool interface! Im sure you'll be able to get there :cool:

Yeah, they are the exact same loop, but they each are used for something different... Last night I managed to do some slight modifications for speed. The speed is not noticable, but it could with only 3 windows up, it could save 61 ifs because of a sooner check if the window exists... I could do this for 2 functions, saving a max of 122 ifs (with 3 windows, supporting 64). Basically all I did was change the order in which I did my if check... it used to be check zorder then check active, now it's check active and then check zorder...

I talked about this optimization on another forum ( http://www.mega-tokyo.com/forum ), and someone said to change the width and height of each window into an x2, y2 coord. with 64x64 checks, this could save 4096 additions per double-loop... But, doing this COULD make it hard for the programmers... When I have my GUI able to support titlebars and buttons, then I will do this... I should be able to support buttons and titlebars in possibly 2 weeks, maybe 1... But right now, I really need to optimize...

Maybe use a different data structure? A resortable balanced tree or something like that?
Because this would enable you to sort them after z-order, so you only need 1 for loop.
Or maybe just sort the array using quicksort, then some fast algorithm if you change the z-order (shouldn't be too hard).


How does the drawing code work? Direct hardware access? It runs on Win2k, so I'm really wondering...

Drawing is VGA mode 13h (320x200x256colors) doing direct video memory access (address 0xA0000000)... so yes, direct hardware access... It runs on my Windows XP as well... why are you wondering?

The person on the other forum said to sort them this way as well... I'll have to see what I can do... How would I go about doing the sort algorhythm?

I wonder because WinNT derived OSs should block direct hardware access...

Just take some CRT and look at the quick sort (qsort) in case it ever gets REALLY messed up.

For all other purposes you would just have it like this (with z=0 being the front)

This is how the sorted array should look like:
z=highest, ..., z=1, z=0
Empty space is behind z=0
Now if a window should be brought to front:
make a copy of the window info.
do a memmove of all windows with lower z values one position to the front
increment the z values of those windows
add the temp window at the end and set it's z to 0

Or in code (using CRT):

Code:

---

// sorted array
struct WIN arWins[MAX_WINDOWS];
// current number of windows
int iNumWins;

// iWin is the index of the window that
// is to be brought to front
void BringToFront(int iWin)
{
  struct WIN temp = arWins[iWin];
  struct WIN *p;
  // memmove is a variation of memcpy
  // that works even if the src and dest
  // overlap, it doesn't destroy data there
  p=arWins+iWin;
  memmove(p+1, p, iNumWins-iWin);
  for(;p<arWins+iNumWins;++p) {
    ++(p->z);
  }
  temp.z = 0;
  arWins[iNumWins-1] = temp;
}

---

The window creation code would need something similar.

I think using a relative z-order would prove most efficient, if you're only moving windows to front, a list to loop trough from top to bottom zordering would be constant time and searching linear.

I have had no earlier experience with linked lists and sorting and such... I have no idea how it's done... I did a try and made a function called void winzsort(); and I tried it. It didn't mess up the array, but when I changed the drawing function by deleting a loop and an if(), it wouldn't draw correctly... messed up big... I reverted back to a previous save...

I have included my entire GUI source... Yes it's small, yes it's somewhat ugly, but it works... It would be much appreciated if someone were to help me optimize this...

Your code seems a little bit inflexible to me. Yet I don't know how to change that.

I've changed the code to use a linked list instead of an array. I also pointed out a few minor problems. You have to adapt the code to your compiler, but it should work (compiles without syntax errors, don't know about logical errors).
The number of windows is now only limited by available memory.

The program runs, but it seems to be stuck in the draw loop... (doesn't draw anything, keys don't work)

If you want, I can send you the PowerC compiler... It's 558KBytes zipped up. Corned Bee, thanks alot... There is one thing wrong with this code... it will not support MDI windows until we add a "parent" window pointer in the window struct. Someone in another forum modified the GUI as well... It allows easy addition of MDI windows(assigning a parent window to each window struct - the desktop would be a parent to all main windows... and some main windows would be parents to child windows... Very odd code - the window struct looks like:

struct WINDOW
{
unsigned short x;
unsigned short y;
unsigned short width;
unsigned short height;
unsigned char *caption;
unsigned long flags;

struct WINDOW *prev, *next;
struct WINDOW *first_child, *last_child;
struct WINDOW *parent;
}

Now... What I think I should do is pool both of the ideas together and redo my GUI. What I think looks good so far is:

list
{
struct WINDOW *prev, *next;
struct WINDOW *first_child, *last_child;
struct WINDOW *parent;
};

window
{
unsigned short x;
unsigned short y;
unsigned short width;
unsigned short height;
unsigned char *caption;
unsigned long flags;
list *da_list;
};

CornedBee, do you have MSN Messenger or AIM? I may need your help while rebuilding this entire thing... Thanks alot!
P.S. I am learning about Linked Lists and Binary Trees from http://www.cprogramming.com

MSN UserID: [email protected]
AOL Screen: Warmaster199

Yes, send me the PowerC compiler, it looks interesting. My email is [email protected] .

I only have ICQ #70788560, no other messenger. But I'd be glad to help you. You can contact me also by PM or email.

The window struct this guy gave you is actually something very interesting. It's data, linked list node and linked list container in one while maintaining a pointer to the parent. Yes, it's probably the best how you want to do it (which is the idea of this guy, but with improved readability).

Another question (because of the far keyword): is this just the stupid compiler or is does this actually run in 16-bit mode?

And wouldn't it be better to make the window position and size signed 32-bit variables? Think about it: by the time your OS has gained some market share we might have 4 parallel monitors with resolutions of 16000 pixels or more (resulting in a total width of about your 2^16). And if you look at Windows you can actually move the windows off the left side of the screen: negative positions.
Think about it.

You shouldn't really code for 16-bit mode any more. I'm sure you know how to boot up and switch to protected mode, though (I don't, never needed it. Might try though someday).

That's why I was wondering. I'm pretty sure this OS is protected mode (you know the OS thread in ASMF, parksie).

I thought he was doing it 32-bit as well, that's why I got confused.

No, I didn't read the thread. Don't go in the asm forum that much. I probably will soon, though, we start doing assembler in a couple of terms' time.

Yeah, PowerC is a 16-bit compiler... It's also command line. I can bring it anywhere and get work done... So I guess it's not the compiler, but the fact that it makes 16-bit code...

My O.S. definitely will be a 32-bit protected mode kernel, but for now, the GUI is ok to run in a 16-bit real mode environment(aka DOS)... Only for testing purposes. As soon as I can get my O.S. WORKING(as in not generating General Protection Faults and Invalid Opcodes(exceptions - pay attention to window's blue screens of death - They are mainly General Protection Faults)) enough that it has paging memory management support and a simple mouse and video driver (it has a keyboard driver already - although buggy), I will add the GUI... Then, at least the system will die with beautiful windows popping up and no more screen floods(lol). HA! Right now this OS of mine doesn't sound that great... bugs and crashes... But as soon as I get my Interrupt handler running(That's the damned thing thats making the GPFs and IOEs), everything should go nice and smooth with no crashes!

As for signed positions and using the "long" datatype, I figured I wouldn't need long because monitors don't display that kind of res. But I forgot that I wanted a VDesk in there(Check the picture in a zip I posted near top)... long might be good after all(but not for window widths/heights)... Sure there are negative values... good point(No need to think) - forgot that!

Today I started recoding the GUI in class(I got 2 structures and some defines done :( ), and I also started designing the list algorhythms (CornedBee, you already did that, but I wanted to see if I could do it now with the new-found knowledge - I wrote my design on paper[well, the switchtofront(); function])... Its a rough writing, so I forgot 2 if() statements... I realized after writing.

I really don't like ICQ, but I think I might d/l it because lots of people have it and I can get lots of help/contacts that way...

You see, I don't have an AOL connection so I don't have AOL messenger, and I refuse to use a MS product when there's an equivalent free other product around. And I try to delay signing up to a .NET passport as long as possible.

The long will pay off in the long run. Think of it as an investment in the future. Just think of the problems and restrictions that Win98 suffers from, they are all because the whole thing is still based on the old Win16 base, because of that damn backwards compatibility. Design your OS for the future!


parksie: I'll be happy to answer any questions I can.

I have Bell Sympatico High speed, and I downloaded AOL Messenger seperate... it's like a totally different thing... http://www.aol.ca/aim/index_eng.adp and click on "New users click here"

I am trying to design for the future, but I also want to have my OS support DOS programs so that you can at least run something on my OS right off the bat... like OS/2... I also plan to implement the Windows API. As you seen in my GUI code, I wanted some of the code to be compatible to make it easy to support this... but that's another project... I will create the basic functionality of my OS first(specifically including memory management, GUI and possibly my tasker), before I implement the DOS code... Windows API emulation will come later... Before I can do DOS emulation, I have to code a simple Video BIOS, so that I can draw DOS apps in a small box and even run Graphical Mode programs in a DOS box. I think this OS will end up great (it will look good with the GUI).

I totally agree that the long will pay off. Good thinking :)

You're doing in many ways the same thing as I am playing around with in my dreams. Just my idea goes even farther:

The OS should:
* support as many filesystems as possible
* implement the programming interfaces of both linux and windows
* be able to use both windows and it's own device drivers (for compatibility: just look at the graphics card hardware acceleration support driver problems in linux: nVidia won't give away it's hardware specs, yet it doesn't write Linux drivers either)
* provide babysitting for apps: the user would need to give each app eplicit permission to access important APIs (like file operations). This needs some mechanism to make program trust groups and it should remember the user's choice. Programs should also be able to mark "unsafe areas" where they could for example execute scripts in any language in a sandbox provided by the OS.
* many more things that would make the OS totally superior to any other

Hehe. Sweet dreams are made of this.

Oh, right. The kernel would be open source and modular, but the native GUI would be proprietary. Why? Don't know, just like the idea.