The NEW 512 Byte Contest -- Quok Style

[quok]

The goal of this 512 byte contest isn't to see who can do the fanciest thing with the least amount of asm code. Instead, it's rather practical. It's a real bootsector, and it's meant to be used by the osdev community. It also isn't being run the same as these competitions have been in the past.

THE GOALS

• Implement in no more than 512 bytes a bootsector that will work on BOTH FAT12 and FAT16 formatted media. The bootsector must detect at runtime which filesystem type it is running on and act appropriately. This bootsector must be self contained; for example, it cannot load an additional sector to handle FAT16 operations.
• Scan for a file named "OSLOADER " in the root directory.
• OSLOADER is a statically linked 32 bit ELF file. Parse the headers and load the file accordingly. Several sample files will be provided at a later date to test your bootsector against. None of these files will have load addresses above the first megabyte.
• Jump to the ELF entry point.
• Use only instructions available on the i386.
• The bootsector must of course work on REAL HARDWARE as well as ALL major emulators (bochs, qemu, virtual pc, virtualbox, vmware). I know someone that happens to have a very very picky i486 laptop that refuses to boot most modern bootsectors.
• You may make NO assumptions about the filesystem (beyond that it is either FAT12 or FAT16), the boot media (beyond that it will be no larger than 8GB), the hardware, or the OSLOADER, with one further exception. The size of the OSLOADER is guaranteed to be no more than 128K.

ADDITIONAL GOAL

• Be able to load and execute a 32-bit ELF file of any size that is also linked above the first megabyte.

CONTEST RULES

• The contest entry deadline is 23:59 April 30 2010 UTC. To be fair to everyone involved, and to give everyone a chance to see this contest announcement, no entries will be accepted before 23:59 Jan 30 2010 UTC. Sample files to be used to test your bootsector will be posted after this date. At this time, a list of hardware used to test entries will be made available.
• All entries MUST be ISC licensed. This is because "public domain" does not exist in all countries, and the ISC license is about as close as you can get to public domain.
• Entries must compile with either nasm (version 2.05 or later) or GNU binutils (version 2.15 or later). Include in your entry the proper command line to compile the source code. Both AT&T and Intel syntaxes are allowed.
• All entries MUST be liberally commented. Highly optimized assembly, as these entries are expected to be, can be quite hard to follow. Just because you understand it, doesn't mean anyone else will. An entry that accomplishes all the goals but is not commented will be disqualified.
• All entries MUST be original works. Collaborations are allowed.
• After the contest deadline passes, all submitted entries will be voted on by the OSDev community to select a winner. This vote will be based on the cleanliness of the code, ease of understanding, and code size. Voting will be open for 1 week after the contest deadline passes. Voting will close at 23:59 May 7 2010 UTC.

THE TWIST

• The FIRST entry submitted that accomplishes goals 1 through 7 and passes all tests will be declared the winner. A submitted entry that does not pass all tests may be modified and resubmitted.
• There are TWO winners! The first winner is as mentioned above, and the second winner will be announced after community voting has closed. So if someone has already claimed the first prize, you should still submit your entry. It is also possible for the same entry to win twice.

THE PRIZE
That's right, there's a real prize! Two of them, actually.

• First prize is a $50 gift certificate to amazon.com. The winner will be announced upon submission of a validated working bootsector.
• Second prize is a $25 gift certificate to amazon.com. The winner will be the entry with the most votes at the end of the community voting period.
• In lieu of amazon.com gift certificates, each winner may elect to have a donation made to the Peer Directed Projects Center (the organization behind freenode) in their name.
• Prizes will be awarded within 30 days of each winner being announced.
• In case a winning entry is a collaboration, the prize money will be equally distributed amongst all collaborators.

HOW TO ENTER
Publicly reply to this post with your entry as an attachment. Do not send your entry privately (via PM or email), or provide a link to another site that hosts your entry. Make sure your entry contains compilation instructions as well as a means of contacting you if your entry should be a winner.

DISCLAIMER
By submitting an entry, you hereby agree to all contest goals and rules. Contest rules are subject to change without notice, so check back often. In the event of major conflicts between the goals and/or the rules, the contest deadlines may be extended. Clarification of the goals and/or rules will not automatically change any contest deadlines. Under no circumstances will contest deadlines be shortened. By participating in this contest and agreeing to the contest goals and rules, you hereby waive any and all legal rights you may have to challenge, change, sway, or otherwise intimidate the outcome of the contest.

Questions and comments welcome. Reply here, via PM, or hit me up on freenode (where I go by, you guessed it, quok).

[~]

I think that there are FAT16 for CHS and also for LBA.

Also, if the bootsector only will boot the same media it is in, wouldn't adding support for 3 variations of filesystems be wasting some space in each case since the filesystem can only be one at the time?

But I see your point: being able to use the same unmodified 512-byte MBR with no modifications would prove useful once the full documentation for the tweaks and the code in question is clear and available.

[quok]

I think that there are FAT16 for CHS and also for LBA.

Yes, there are. However for the purposes of this contest, I'll add one other assumption: the boot media will not be bigger than 8GB.

Also, if the bootsector only will boot the same media it is in, wouldn't adding support for 3 variations of filesystems be wasting some space in each case since the filesystem can only be one at the time?

Well, it's 2 variations now, and it very well may waste some space in each case, but in contests like this one, people generally try to pack as many features as possible in the space provided. And believe me, the differences in how you handle FAT12 vs FAT16 don't amount to much

But I see your point: being able to use the same unmodified 512-byte MBR with no modifications would prove useful once the full documentation for the tweaks and the code in question is clear and available.

Yes, using the same bootsector code for either FAT12 or FAT16 is quite useful. I'm currently doing it myself and it certainly makes things a lot easier. I was going to post my code as a reference implementation (since it does nearly everything in this competition already), but I didn't want to see a bunch of entries that are just reworked versions of the bootsector code that bewing and I worked on (and has already been posted to the forums elsewhere).

Also, don't think of it as a MBR. FAT12 and FAT16 formatted media may be partitioned, after all.

[XanClic]

Entries must compile with either nasm (version 2.05 or later) or GNU binutils (version 2.15 or later).

Why not FASM?

[quok]

Entries must compile with either nasm (version 2.05 or later) or GNU binutils (version 2.15 or later).

Why not FASM?

Mostly because I'm not willing to install every assembler ever created to support this contest. nasm is quite popular and used by many forum members for their projects. I'm sure it's way more popular around here than GNU AS is. FASM may even be more popular than GNU AS, but I had to draw a line somewhere

[a427]

Interesting contest..

But it seems like the major challenge is first to recover a damaged FAT12/16 filesystem, whose BPB sector has been completely overwritten, and thus, can't tell about its properties ? (cluster size, number of fat, etc...)

Is it really intended ? If yes, does it mean that after having actually replaced the original BPB by an actual 512 byte contest entry, then the filesystem is no more readable/mountable by another OS (eg: we can't mount the floppy/partition under say, linux in order to browse it/ modify the OSLOADER elf file) -- without first restoring the original BPB ?

Can you confirm that ?

[quok]

Seems like there are some FAQs that need answering, so here goes!

...it seems like the major challenge is first to recover a damaged FAT12/16 filesystem, whose BPB sector has been completely overwritten, and thus, can't tell about its properties ? (cluster size, number of fat, etc...)
The filesystem's BPB will not be corrupted. You can safely assume that the cluster size and number of FATs as listed in the BPB are valid. But of course, there are some values that you'll need to calculate for yourself. All bootsector entries will be tested on fat12 and fat16 filesystems of varying size, however the BPB itself will not be changed at all aside from the geometry information as written by mtools. When I create the base images, I will use mtools to do so. Before testing a bootsector entry, I'll copy the base ("clean") image to a testing image, and will use the mformat command to update the bootsector on the testing image.

Who decides the winner? Quok?
For round 1 of the competition, if you want to call it that, yes. I'll be the primary judge for first prize. That being said, if anyone else would like to judge this part of the contest as well, then please PM me. But note that if you elect to act as a judge, you cannot also enter a bootsector. To do so would create a conflict of interest, and certainly wouldn't put this contest in a good light. Unfortunately, I cannot provide payment to anyone that assists with the judging. In my opinion, to do so would also compromise the integrity of the contest.

The second prize winner will be voted on by the osdev.org community. More specifically, by those community members that are interested and willing to vote. It'll be a simple forum based poll, open to everyone, and set to expire 1 week from when I open it.

About the prize money
I'm including prize money because it was suggested in this thread about the 4th 512 byte OS contest. Some people liked it, some people didn't. If you, as the winner of the prize money, would rather not accept any prize money, then as stated in the contest rules, the winner may elect to have a donation made in their name to the PDPC. I selected the PDPC specifically because they promote free and open source software in general, and are not specific to any one project or agenda. Disclaimer: I am a freenode staff member.

The prize money is coming out of my own pocket. There is no organization sponsoring this contest. It's just one individual with a couple of dollars to spare. I'm certainly no millionaire CEO of a company that is farming out development of an OS to a rather large, vague, and fluid community.

I'm located in the US, so the prize money at stated is in USD. If you as the winner elect to have your prize money donated to the PDPC, $50 USD is approximately £30, and $25 USD is approximately £15. That's enough for the professional and active donor level cloaks, respectively, as stated here. I know many people here are from outside the US, so I'm checking with Amazon to see if a gift certificate purchased through amazon.com may also be used at amazon.co.uk (for example). If this is not the case, then something else will need to be worked out.

The contest rules state that prize money will be awarded within 30 days of a winner being announced in order to provide adequate time to inform the winner, and allow the winner to elect to receive the gift certificate or have the donation made.

Why was FAT chosen? It's old and obsolete.
FAT12 and FAT16 may be old and quite nearly obsolete, perhaps even boring, but the FAT family of filesystems are still the de-facto standard filesystems used on removable media. When's the last time you bought a USB flash drive that came pre-formatted as ext4?

Why are you only allowing NASM or GNU AS?
As I stated in another post, mostly because I don't want to install all kinds of assemblers to support this contest. Please keep in mind that as of now, I'm the only judge for first prize. I completely understand that FASM may compile your entry to 511 bytes, but with NASM you can only get it down to 513 bytes. If this happens to you, I'm sorry. I'm sure you'll be able to find some place to save a byte.

I'm not entering because...
I'm sorry that you're not interested in entering the contest. I did my best to appeal to a large audience of potential participants. Unfortunately, you can't please everybody. I respect your decision to not enter the contest, so please respect my request to not clog up this thread with posts about why you won't be entering.

I'm offended by...
I'm sorry you're offended by whatever it is that offends you. Keep in mind all contests have rules and restrictions. Most contests have far more rules and restrictions than this one does. Feel free to start a contest that is more to your liking. Otherwise, kindly sod off.

What happened to my posts that were in this thread?
I apologize, but those posts were split off to another topic and are hidden away in a secret vault for all of eternity. The posts that were split were all related to a flamewar over the terms of this contest. For fair warning, any new posts of that nature will also be split off and locked away. Let's please keep things friendly here, and follow the forum rules. Thanks!

Waaaah! My whine isn't covered here!
Would you like some cheese to go with that whine[sic]? Perhaps some brie? Or would you rather Camembert? If you'd like the brie, I can suggest a nice Merlot to go with that. For the Camembert, I have about 30 bottles of a very very nice (homemade) Cabernet in my basement.

Seriously though, if there is anything about the contest that needs more clarification, don't be afraid to ask. I'll do my best to clarify whatever it is as much as possible.

[a427]

Ok, thanks for the first answers.

Nevertheless, there's one point I still don't get :
I started writing my own 'boot sector' entry, that is supposed to be written inside the fat12/fat16 you just created.
The problem is : if I write my boot sector in place of the BPB of such filesystem (like say, on the sector 0 of a floppy, to make it bootable, and to load the elf file that is present on it)
then by definition, there will not be a valid BPB anymore on it !

Or else, when you said that the BPB will still be present, then how, or where do I write my boot sector ?

Or maybe I missed the point that your were assuming we have to deal only with hard disk images, where there can be multiple MBR, PBR, BPB ?

[01000101]

Ok, thanks for the first answers.

Nevertheless, there's one point I still don't get :
I started writing my own 'boot sector' entry, that is supposed to be written inside the fat12/fat16 you just created.
The problem is : if I write my boot sector in place of the BPB of such filesystem (like say, on the sector 0 of a floppy, to make it bootable, and to load the elf file that is present on it)
then by definition, there will not be a valid BPB anymore on it !

Or else, when you said that the BPB will still be present, then how, or where do I write my boot sector ?

Or maybe I missed the point that your were assuming we have to deal only with hard disk images, where there can be multiple MBR, PBR, BPB ?

Ok, for FAT12/16/32, you allocate free space to hold the BPB. When you run a formatting utility like "mformat" (part of mtools package) or "mkdosfs", it will overwrite the free space with appropriate geometry values that you can use at run-time. For instance, you can format a floppy image and a BPB will be setup in sector zero 3 bytes from the start (just like the specs, and infinitely more important, the wiki, says). Then you will overwrite everywhere else BUT the BPB with your own code and use the geometry appropriately.

So, your custom bootloader only needs to reserve some space. Look through the wiki for the FAT12/16 article, it's very helpful, or look through the forum for some example bootloader code (which does exist, I was looking at some earlier as a refresher).

[a427]

Ok, for FAT12/16/32, you allocate free space to hold the BPB. When you run a formatting utility like "mformat" (part of mtools package) or "mkdosfs", it will overwrite the free space with appropriate geometry values that you can use at run-time. For instance, you can format a floppy image and a BPB will be setup in sector zero 3 bytes from the start (just like the specs, and infinitely more important, the wiki, says). Then you will overwrite everywhere else BUT the BPB with your own code and use the geometry appropriately.

So, your custom bootloader only needs to reserve some space. Look through the wiki for the FAT12/16 article, it's very helpful, or look through the forum for some example bootloader code (which does exist, I was looking at some earlier as a refresher).

Ah, OK I didn't get the point that the actual "installation" of the competing entry's boot code would be done via a parameter given to such tools like mkdosfs or mformat..
I thought we'd do that the brute way, like dd if=boot of=fd.img bs=512 count=1
Hence my worry about missing BPB, or a BPB not reflecting the rest of the fd.img...

And yes you're right I have thus to reserve the BPB bytes _within_ my boot sector, to make it BPB-patchable...
The cool thing is then that whatever geometry is chosen by the "installer", the boot sector will then be able identify the remaining sectors, plus the resulting media will still be mountable..

Thanks for the clarification..

[Love4Boobies]

(just like the specs, and infinitely more important, the wiki, says)

Oh, come on... Seriously?

[technik3k]

Hi guys!

You are pushing it! I guess this is the goal of this contest

However, if you make no assumptions about any of the following it will be impossible to do it in 448 bytes (512 - BPB size) :

BIOS / MBR:
Initial entry address for boot code: standard 0:7C00h vs non-compliant 07C0h:0000
Validity of initial DL value as a disk number versus BPB disk number value
CHS / LBA (int 13h/4xh) availability

FAT:
Sector size: {512, 1024, 2048, 4096} vs {1..64k-1}
Cluster size: {1..64} sectors vs {1..255}
Reserved sectors at the beginning: 1..64k-1 ?
Number of FAT copies: {1,2} vs {1..255}
Short number of sectors versus long number of sectors availability
Validity of the FileSystem ID field vs deriving it from sector number

ELF:
There are too many fields to list. Which ones do you expect boot sector to interpret?

Please, provide reasonable ranges for those variables and, ideally, pseudo-code for ELF header interpretation. This will make it easier for everyone and make an even playing field.

Thanks,
technik3k

[01000101]

Initial entry address for boot code: standard 0:7C00h vs non-compliant 07C0h:0000

A whopping one instruction... "jmp 0x0000:somelabel"

Validity of initial DL value as a disk number versus BPB disk number value

iirc, the value in the BPB, is the disk number from the host and thus should be ignored (in favor of DL).

CHS / LBA (int 13h/4xh) availability

It's up to you if you want to use EDD. Just know that it's not available on all computers that may have your code tested on.

There are too many fields to list. Which ones do you expect boot sector to interpret?

It's very easy to parse ELF files and load sections into memory. It can be done with very little space.

Please, provide reasonable ranges for those variables and, ideally, pseudo-code for ELF header interpretation. This will make it easier for everyone and make an even playing field.

These are very reasonable requirements given the target group. If you've written a bootloader before, this shouldn't be all that complicated to do.

I did skip some of your questions as I'm honestly quite lazy, but you can see the point being made (hopefully).

Thanks,
technik3k

You're very welcome.

[XanClic]

However, if you make no assumptions about any of the following it will be impossible to do it in 448 bytes (512 - BPB size) :

I have to say that I already got something working (though it still makes a lot of assumptions) and I can say that it is possible. Yeah, it'll be very hard. But this is a contest with a big price, isn't it?
So don't call it to be too hard.

And, btw:

Please, provide reasonable ranges for those variables and, ideally, pseudo-code for ELF header interpretation. This will make it easier for everyone and make an even playing field.

Sorry, but in my opinion it's like that: If you don't know how to parse an ELF you'll have to learn it on your own or you may not participate in this contest. This is no test, nobody beats you if you don't compete.
Of course I plan to participate and deep in my mind I try to keep the number of competitors as low as possible ( )—but I really believe that there should be no "manual" on how to do it, because it's the goal of contests like this to go "new ways", that are as small as possible. So if you think there are too many fields in the ELF header—then you are not able to create a valid entry and I don't know why we should help you in doing so. Should I post my "proposal" here and all of you help me in minimizing it and hence help me to win? (Of course, if nobody makes it until May, we can do it that way, because it would then simply be interesting how that code would look like.)

[technik3k]

And, btw:

Please, provide reasonable ranges for those variables and, ideally, pseudo-code for ELF header interpretation. This will make it easier for everyone and make an even playing field.

Sorry, but in my opinion it's like that: If you don't know how to parse an ELF you'll have to learn it on your own or you may not participate in this contest. This is no test, nobody beats you if you don't compete.
Of course I plan to participate and deep in my mind I try to keep the number of competitors as low as possible ( )—but I really believe that there should be no "manual" on how to do it, because it's the goal of contests like this to go "new ways", that are as small as possible. So if you think there are too many fields in the ELF header—then you are not able to create a valid entry and I don't know why we should help you in doing so. Should I post my "proposal" here and all of you help me in minimizing it and hence help me to win? (Of course, if nobody makes it until May, we can do it that way, because it would then simply be interesting how that code would look like.)

OK. This makes sense, lets compete.

Still, as I am not that fluent in ELFish, would it be safe to assume that static ELF needed to be supported is like the hello.asm from fasm for linux examples, where the file doesn't have any section headers and only two program headers (one for each code and data segments)?
What is the linking alignment? Do we expect to relocate data section relative to the code section or they are already properly spaced?
Do you want a long jump to e_entry or to the first p_vaddr?
Do you guarantee that is is going to be paragraph aligned?

Also, please, correct me if any of these assumptions are not correct:

BIOS/MBR calls this boot sector code at 0:7C00h with correct boot drive number passed in DL
BIOS int 13h CHS calls should be used when Cyl<1024 and LBA calls should be used otherwise

This boot code needs to support real floppies and therefore needs to do a reset operation.

FAT BPB has correct sector size (for this media) and it is one of the following values: {512, 1024, 2048, 4096}
FAT cluster size has one of the following values: { 1, 2, 4, 8, 16, 32, 64 }
Number of FAT copies is either 1 or 2 and they have reasonable size (i.e. cluster#2 is within 64k sectors from the beginning of the partition, so 32-bit arithmetic is not necessary there)
FileSystemID field is correct and could only be either "FAT12 " or "FAT16 "

Finally, since you didn't mention anything about error messages I am going to assume that calling "int 18h" in case of an error is good enough to meet the official rules.

Thanks,
technik3k