I've added more stuff to responsive-os. It's now running faster. For some reason gcc's optimizer flags were slowing things down in that context. But switching to clang and optimization is taking in the 32 bit context.

My drawing methods are now faster now that I have some bulk memory functions like memset and memcpy. Images are now drawing with the right color channels. "Raw images" are now 3 channel instead of 4, but that may change back.

I've added support for keyboards. Random number generation. Random tensors. A juicy in-place quicksort algorithm. I don't know why I'd never thought about how to do quicksort in place before. Likely because modern languages and environments have always spoiled me.

I'm sure others have solved in-place quicksort before, but I can share the rational and the code for people who want to learn how the thought process for this kind of stuff works.

So what is quicksort? Quicksort can colloquially be called the pivot sort. Though don't call it that because offical pivotsort is a variant of quicksort with a tuned pivot.

The way it works is you pick an element from the list at random. You then organize the list into buckets. One bucket is for values that are less than or equal to the pivot. The other bucket is for values that are greater. You then perform quicksort on the smaller buckets. Merge all the lists together and you have a sorted list.

It's one of the fastest algorithms. But in a modern language there is a lot of opportunity to do things that aren't the most efficient. Things like initializing new lists to act as your buckets. Using a bucket who's size isn't pre-determined so you could end up re-allocating or worse, using some kind of a linked-list based structure that might ship with your language of choice. And then you might find yourself copying values into a final list.

Even when you do all of those things, quick sort can still perform pretty well.

Two layers of realizations can get us a better result.

The first realization is that if we added a working space of equal size we could fill less than or equal values from the front, and greater than values from the back. We can then pass a slice from the first part of the array as the source to quicksort again and use part of our initial input array as the working space memory.

There a few reasons why this doesn't work though. Different parts of the algorthm will hit their base case at different depths. Specifically even or odd depths. Meaning, which array holds the real end result is a mixed bag. Solving this would force us to copy results between lists to assemble the end product. Yuck.

Better, is the exact same concept except you use your input list as your working space. You can assign a value either to the front or the back, and if you are about to overwrite data that you haven't compared yet, you simply make that the next value to compare.

At first I feared there are going to be a lot of indexes to keep track of. Which values are we reading, where are we writing to in both the front and back, how many values in both the front and back have been pulled and are safe to overwrite, where is the hole we made when we selected the pivot element. Then all the logic for managing those indexes. We don't know how complicated it might get until we solve it.

But it turns out we can wrangle this. The first thing to note is that picking a random pivot value outperforms just selecting the first value in practice. If you just chose the first value as the pivot value on an already sorted list, this isn't going to go well. This is an ironic case you don't want. Taking longer to sort an already sorted list.

So the first step to get rid of one of these indexes to think about is to pick a random index, assign it's value as our pivot value, and then insert the first value of the list where the pivot value was. Essentially we've swapped the first value and a random index and then used the first value as the pivot. This means the hole created by the pivot select is in a predictable spot and we don't need to account for it later. At the very least we won't come across it randomly.

Next we start our loop reading from the second position in the list, index 1, the first non-pivot value. If it is less than or equal we write it to index 0. If it is greater than then we write it to the end, but not before reading that value as our next compare value. It wasn't as critical to do it in that order for the other case because index 0 had nothing of value in it. It's value was already copied to our pivot hole in the center.

If we write to the front we read from the front. If we write to the back we read from the back ahead.

We continue until the next write index for the front equals the write index for the back. In that case there is only one place to write to. And that place is for writing our pivot value.

We then just call quicksort on the two wings.

Here is the code:

void quicksort(u32 *list,u32 size,Random *r) {
 if(r==0) {
  r = (Random*)malloc(sizeof(Random));
  random_seed(r,0);
  quicksort(list,size,r);
  return;
 }
 u32 pivIdx = random_range(r,0,size-1);
 u32 pivVal = list[pivIdx];
 list[pivIdx]=list[0];
 u32 frontIdx=0;
 u32 backIdx=size-1;
 u32 checkValue=list[frontIdx+1];
 while(frontIdx!=backIdx) { //Break at the right time
  if(checkValue>=pivVal) {
   u32 temp=list[backIdx];
   list[backIdx]=checkValue;
   checkValue=temp;
   --backIdx;
  }
  else {
   //Cleaner logic because of the hole made at the start
   list[frontIdx]=checkValue;
   ++frontIdx;
   checkValue=list[frontIdx];
  }
 }
 list[frontIdx]=pivVal;
 if(frontIdx>1) quicksort(list,frontIdx,r);
 if(size-frontIdx-1 > 1) quicksort(list+frontIdx+1,size-frontIdx-1,r);
}

It really is more simple once the solution is known. But I wanted to share some of the micro-stress that makes the game of coming up with an algorithm. You start off with all of the complexity of what you might have to consider with the 60% assumption that some or a lot of it will simplify out. But you can't discover the ways things will simplify until you start asking questions about how some of the things that might have to exist might interact with each other.

With the age of AI on us, fewer and fewer people will be maintaining the skills of problem solving. Especially when even the problems that have elegant solutions often don't have elegant beginnings in how to start thinking about them.

---

I'm slowly working my way up to making an editor. That's why I put in keyboard support today. But I still need a lot of things beyond that. The keyboard code is short so I might as well share that too.

//Work with ports
// Write a byte to a hardware port
void outb(unsigned short port, unsigned char val) {
 // "a" means use EAX/AL register
 // "Nd" means use a constant or the DX register
 asm volatile ("outb %0, %1" : : "a"(val), "Nd"(port));
}

// Read a byte from a hardware port
unsigned char inb(unsigned short port) {
 unsigned char ret;
 // "a" means store the result in AL
 // "Nd" means use a constant or the DX register
 asm volatile ("inb %1, %0" : "=a"(ret) : "Nd"(port));
 return ret;
}

// kdb_US is a copy-paste lookup table that's kind of long.
char scancode2ascii(unsigned char scancode) {
 return kbd_US[scancode];
}

char check_keyboard() {
 //Measure if the buffer has content with the fist bit of 0x64
 if(!(inb(0x64)&1)) return 0;
 unsigned char scancode = inb(0x60); //Read it from 0x60
 if(scancode>0x80) return 0;
 return scancode2ascii(scancode);
}

void kernel_main(struct mutliboot_info *info) {
 //...Some init code here...
 Random r;
 random_seed(&r,0);
 drawimage(info,10,10);
 Offset *offsets = randoffsets(info,10);
 //Random jitter the position of an image as proof of life;
 for(int i=0;i<100;++i) { 
  i%=10;
  int prev=(i+11)%10;
  drawimage(info,offsets[i].x,offsets[i].y);
  char press=check_keyboard();
  if(press) backgroundColor = random_next(&r);
 }
 //Halt code we'll never reach
}

---

But a few other things will likely come in before an editor. Even things like porting a game and adding a basic language will likely happen quicker.