Oh look at the time. I should probably write an entry before I bust the deadline.
I spent much of today working on a small library in QuickBASIC that I call FilePak as part of my preparatory work for the LED2-20 retro-programming project. Previously I had talked about how I might want to use CHAIN and COMMON as mechanisms to create overlays of the code that generates the sprites from DATA statements from the code that runs the main event-loop. It was an interesting idea, but after thinking about it while working on my design document, I realised that I probably didn't want to pursue it.
If the intent was just to refactor/rewrite the old LED(II), then the mechanism works well, since all the sprites are pre-determined and are really of the same shape, and thus it is straightforward in laying out the module flow for CHAIN and COMMON to be effective.
The problem was that as I sat down to work on the design document to flesh out my vision on how LED2-20 should work out, I have changed the calculus by quite a bit. Gone was the simplistic 32×16 enemy sprites repeated over several waves---I wanted each wave to mean something more than just a change of sprite with the same behaviour. I wanted some form of procedurally generated level layout for the waves, I wanted boss fights. I wanted terrain tiles, I wanted background tiles, I wanted parallax where meaningful.
Essentially, I would be creating an intricate call chain with the CHAIN command and associated sources just to get all these done. It is not sound engineering---it is crazy mad scientist levels of cranky engineering. I could still use a program to generate the sprites, but I can no longer use it actively in the intricate dance that I was about to choreograph.
Which meant that I would have to follow Hung's Dynamite Man concept, or Lianne in... The Dark Crown by DarkDread/Dark Dreams, which was to use lots of small files (sub-500 bytes each) to store the binary data for the image and masks. As mentioned before, in the era where each cluster size is 4 kiB as opposed to 512 bytes, storing each of these files as-is is very inefficient and can cause heavy external fragmentation. It's also an ugly mess when it comes to distribution since it's really hard to keep track of all these many files.
The solution has always been to create some kind of package file to store all these assets and provide APIs to retrieve their contents during run-time. These days, the game-engine that one purchases a license to use would have this built-in, but since I'm working retro, it's time to go retro.
Enter FilePak. It's a really dumb format. What passes as a header is just a 15-bit integer on the number of records in the File Allocation Table (FAT), with the sign bit used to mark if the FilePak is read-only and optimised. This is followed by however many entries are there of the FAT. Each FAT entry is a 12-character space-padded Latin-1 string representing the old 8.3 file name, two 32-bit signed integers representing the absolute byte position for the start and end of the real file that acts as the container, with the sign bit for the start position used as an indicator of a deleted entry since QuickBASIC only handles file positions of less than 231 anyway. Immediately after the FAT just comes the data themselves.
It's really dumb because there is no compression, no checksum, and is not even a ``real'' file system since it doesn't free up space when an existing FAT entry is marked as deleted.
How I envision myself using it will be to generate the sprites from sketch into the correct binary format for the screen mode I am using (mode 7h, or EGA's 320×200 with 16 colours (and 8 pages)) and saving them into the FilePak using the API I wrote up. Subsequently, I will just retrieve the binary data directly into the binary buffers (represented as 16-bit integer arrays in QuickBASIC) for use later on.
The programming for the binary I/O into memory was interesting. It seemed that the 16-bit integer arrays were more stable in terms of their location---their segment:offset didn't change between when they were called and when they were used. This is in opposition to the character strings (or the STRING type)---these change in between QuickBASIC statements, and had to be ``fixed'' by poking their values directly into an integer array.
It was relatively easy to write these memory-related functions in QuickBASIC because their variables are all passed by reference. So I could just pass the array (say a()) directly into the sub-routine, and call VARSEG(a(LBOUND(a))) and VARPTR(a(UBOUND(a))) respectively to get the desired segment:offset.
While trying to support multi-segment arrays (i.e. arrays larger than 64 kiB), I ran into an interesting compiler problem---it yelled at me for ``Math Overflow'' when it saw my supposed 32-bit long integer constant of 65535. I was confused for quite a while---why would it bitch about that when I could run it in the interpreter with no problems? Then it dawned upon me: I had always used DEFINT A-Z as a default for all my programs (that and the '$DYNAMIC metacommand for dynamically-sized arrays). The reason for that was subtle: by using DEFINT A-Z, I was telling the interpreter/compiler to emit 16-bit integer opcodes when running/compiling. For those who are confused, computer processors generally run optimally when the data they are operating on is of the same size as the so-called ``machine word''. The QuickBASIC compiler existed during the time where 16-bit processors ruled supreme, and thus the 16-bit operations tended to work the fastest. Back then also, 32-bit ``long'' integers were abnormal, and tended to be slower. Floating point performance is also abysmal.
So, for the fastest opcodes generated, one would want 16-bit integer arithmetic to be used as much as possible, especally in real mode. That same property that I had been using forever had bitten me in the ass for that particular chunk of code, because in 16-bit integer land, 65535 is a bogus number. Yes, it can be represented in 16 bits, but only when it was unsigned, a particular version of integers that has always remained little used and has usually been the main source for the strangest of bugs, security or otherwise. I had to convince the compiler to not do that for that chunk of code, and so for that sub-routine only, I switched to DEFLNG A-Z instead.
And it compiled and it worked. Yay.
One last thing that I added to FilePak was a simple tool that would optimise it for reading. The FAT was always loaded into memory by the module, and it was usually referred to by the file name. Unfortunately, the sprite generation process is likely to be more programmer friendly in terms of ordering, and so the FAT had to rely on a linear search to find the correct entry. There was also the problem about handling the internal fragmentation from file deletion and file overwrite through reusing an older FAT entry---leaving these artefacts alone meant that the FilePak was just going to keep expanding with useless data, and a long time to find anything.
The optimise for reading tool simply loaded the existing FAT, sorted it by file name order, discarded all FAT entries that were unused or soft-deleted, before finally writing out the adjusted FAT with updated byte positions to a new file, thus compacting it. The sorting was important because it could then allow binary search to be applied in the look up for the FAT entry, which was much faster.
Unfortunately, QuickBASIC didn't have a built-in sort routine like C/C++/every other modern language, and so the old faithfuls had to come out. I started with a simple bubble sort, but quickly converted it to comb sort instead. For what I had in mind, trying to build a quicksort for this was just not worth it. However, I will write quicksort for the rendering pipeline: that's one place where having a fast sort is super important, since it can occur quite frequently while trying to compute collisions among the objects as part of the associated computational geometry.
Anyway, that's that. Till the next update, I suppose.
No comments:
Post a Comment