8 ms·
Pacman in 512 bytes of x86 boot sector machine code
- remlov 7y agoVideo of this in action: https://www.youtube.com/watch?v=ALBgsXOq11o https://www.youtube.com/watch?v=ALBgsXOq11o
- Nextgrid 7y agoDoes anyone know what are the artifacts at the bottom left corner of the video? Is it just an issue with the video capture or is he doing something clever like storing data in these pixels?
- moron4hire 7y agoStoring data in pixels, so it only has one memory segment and can write direct to memory to do the graphics.
- nanochess 7y agoTo save 3 bytes I had to use the address in DI after drawing the maze (just below the last tile row), it contains the positions of the player and ghosts.
- kazinator 7y agohttps://en.wikipedia.org/wiki/Blinkenlights https://en.wikipedia.org/wiki/Blinkenlights For debugging.
- sukilot 7y agoYou say "save 3 bytes", we say "visualizing dynamic game state, for debugging and educational purposes, and highlighting how small the dynamic state is compared to the static art asserts"
- farmerbb 7y agoReminds me of CRAM dots on the Sega Genesis: https://segaretro.org/Sega_Mega_Drive/Palettes_and_CRAM#CRAM_mid-frame_changes https://segaretro.org/Sega_Mega_Drive/Palettes_and_CRAM#CRAM...
- moron4hire 7y agoWhat's incredible is that there really aren't any special "tricks" here. The code is pretty easy to follow.
- thrwaway4137 7y agojust to put into perspective how little 512 bytes is, here is 512 ascii bytes (including 8 newlines) pacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacman pacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacman pacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacman pacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacman pacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacman pacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacman pacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacman pacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacmanpacman pacmanpacmanpacmanpacman that's it. That's 512 characters/ascii bytes.
- tenebrisalietum 7y ago4 times more RAM than the Atari 2600 has.
- mysterydip 7y agoThe 2600 was such an interesting machine for its lack of video RAM. Developers "raced the beam" to draw things just in time for them to be displayed, changing colors and sprites partway through a line to make all the cool (for the time) effects.
- anyfoo 7y agoTrue, but let’s not forget that the game code is usually in much bigger ROM on the Atari 2600 (and I forgot whether bank switching hardware and similar cartridge extension hardware was common there). Still mind boggling how little RAM you had for game state. And that you actually did not have a framebuffer at all, meaning that you essentially had to draw each pixel (or scanline?) when it came up!
- ktpsns 7y ago> It can be run as a COM file or put into a boot sector of a floppy disk to be run. Isn't "COM file" something specific to DOS? How does it differ from a machine binary file, i.e. what GCC (or a linker) would spit out of the ASM code? (The makefile uses nasm, thought)
- dalf 7y agoFrom https://en.m.wikipedia.org/wiki/COM_file https://en.m.wikipedia.org/wiki/COM_file > Since it lacks relocation information, it is loaded by the operating system at a pre-set address, at offset 0100h immediately following the PSP, where it is executed (hence the limitation of the executable's size): the entry point is fixed at 0100h.
- nanochess 7y agoIt's a plain 16-bit executable without headers or linking information. Specific to DOS.
- johannes1234321 7y agoWhich essentially is equal to a raw machine binary, except that the MBR's boot loader is mapped to 0x7c00, while DOS's COM loader maps the start at 0x1000. Of course the pure MBR version has no access to DOS interrupt handlers for IO access or similar. (Interrupt 0x21)
- farmerbb 7y agoInteresting that, when you compare the MBR and COM versions side-by-side in a hex editor, the only changes (apart from the required few bytes at the end of the MBR version) are in what I assume are memory addresses: a 7D byte in the MBR version ends up being 02 in the COM version. One higher than 7C and 01 in the respective starting addresses.
- johannes1234321 7y agoYou can also easily see this in the (really nice) code, where the only difference is the starting address set at https://github.com/nanochess/Pillman/blob/master/pillman.asm#L50 https://github.com/nanochess/Pillman/blob/master/pillman.asm... and the MBR magic bytes in the very bottom. If you now wonder what the difference between a .com and a .exe file is: A .com file has a single page which is loaded in that specific location, with all addresses in the code assuming absolute addresses. The .exe (MZ file) allows DOS to put the program anywhere into memory and the rewrite address references (or rather segments) according the relocation table from the program header. With MZ files DOS also sets up space for the stack and sets registers accordingly.
- jchw 7y agoReflection: - Machine code is very dense. Really, this is not an accident, although maybe it’s not entirely on purpose either, more just common sense at the time. In the end, there were probably many platforms using this or predecessor CPUs with very little RAM/ROM and bytes still counted even on IBM PC. - Assembly code is still very readable. The trouble is not that machine code isn’t readable, and it probably never really was. It just doesn’t offer ways to build abstraction beyond what the machine supported (like routines, sw interrupts, etc.) Only gets worse as hardware gets more complicated. Imagine avoiding VGA and instead attempting to support initializing a modern graphics card all the way through! It would probably be quite ridiculous even with documentation. This is part of what bugs me about a lot of non-x86 platforms, since that’s kind of the environment you’re dropped into in many of them. - Speaking of compatibility, one must wonder how many new layers have been introduced on top of things like VGA since the original VGA.
- derefr 7y ago> Machine code is very dense. It's intriguingly dense. If you're writing an emulator or a bytecode VM, and you can't just slap a JIT in (because you need to ensure that e.g. data races resolve the same way they did on the original machine), it's very hard to come up with a data structure to represent "decoded" code, that is more performant than just keeping the original code around in memory in its packed-stream-of-opcodes form. One would think, for example, that it would make sense to do the "instruction decode" pass ahead of time, to end up with an array of pointers-to-instructions plus literal-values... but the resulting representation of the code is usually much larger in memory, and so less of it will fit in cache (and it'll also fight the VM interpreter itself for cache-lines.) You might gain from your instruction impls not having to trampoline back to the interpreter (https://en.wikipedia.org/wiki/Threaded_code https://en.wikipedia.org/wiki/Threaded_code, basically), but you'll lose in cache coherence. Really, the best you can do in such a situation is to translate the stream of opcodes to another stream of opcodes, just ones that you can execute more efficiently (i.e. create your own "microcode" ISA for your VM.) Either way, "a loop that walks/jumps through an in-memory buffer of variable-length CISC opcodes using a byte-granular program-counter pointer register" seems to be an optimum somehow in design space.
- JoeAltmaier 7y agoMy older brother bought an 8086 kit in the 80's. He could afford 128B (bytes) of RAM which cost $50. It had a front panel with switches for toggling in a program (MITS 8800) and a serial display port. So I wrote a little game in 128 bytes that took one key input and you guided a little 'X' around the screen, trying to avoid the obstacles or going off the screen.
- hermitdev 7y agoWhen I wad in college, we had something similar in lab. This was around early 2000s, and we had Motorola 68K minicomputers with around 512k RAM, IIRC. They were hand built, with wirewrapped connections between the various DIPs. To debug supervisor mode assembler, we had a clock toggle switch that could switch from normal running at 1 Mhz, I think, to a single clock cycle push button. We had a 2 character hex display that showed the 16-bit raw data on the databus. Spent so much time staring at those 16-bit hex values, I was able decode most of the instructions from memory (spent a LOT of time with the 68K ASM programmer manual - still have it on my shell). Couldn't even see the register state. Had to keep track of that in your mind or on paper. I think we had some dipswitches to toggle memory values, as well. Helped save time for trivial changes because downloading a decently sized ASM program could take 15-20 mins over a 1200 baud serial connection. Got in the habit of inserting NOPs in the code so we'd have room to insert a handful of instruxtions here and there. When I say decently sized, I mean around a couple 10ks bytes of machine code. We were working on a supervisor program to load user code, execute it in user mode and debug user code. Some other misc stuff, like commands to act like a calculator, sort arbitrary men locations, etc. It was a really fun class. Still can't believe how much we got done in 1 semester. Lots of late hours, sleeping on lab stools. Beer and sandwiches in lab while we worked. Made some new friends, strengthened bonds with others, lost a few friends that weren't pulling their weight. The lot of us later made an MP3 player around an Atmel AVR chip (forget the model) and a dedicated decoder chip with some wire wrapping and soldering and a crap ton of wiring. For expediency, we streamed the data over a serial port from a PC. Also a fun project. Discovered a lot of engineering stuff we'd been taught, but didn't really understand the relevance, was extremely important (like travelling wave theory and the importance of terminating a bus properly). It was a lot of fun building things in a constrained environment. Can't say I don't miss the college years, when you couldn't just "throw more hardware at it".
- basementcat 7y agoWhile still very impressive, this does make use of BIOS routines for VGA, I/O and timekeeping.
- userbinator 7y ago...as opposed to something much bigger that also eventually uses the same "library" of functionality.
- basementcat 7y agoI would be interested in seeing if an EFI version of this would also fit in 512 bytes. One may have to overlap some fields in the binary format.
- nineteen999 7y agoDoes EFI even have the same 512 byte restriction though?
- NieDzejkob 7y agoNo, it doesn't.
- einr 7y agoAs for VGA, it only uses one BIOS call to set the graphics mode, then never again. After that, it just throws bytes directly at VGA memory.
- sukilot 7y agoHN Title is misleading. The github author correctly calls it Pillman / yellow-thing-eats-pills-and-chased-by-ghosts . Even ignoring trademark issues; it's not Pac-Man -- there are no power pills, no teleporter/torus holes, no ghost house, no fruits, no score, etc.
- deleted 7y ago[deleted]
- SmellyGeekBoy 7y ago> It's compatible with 8088 (the original IBM PC). So you now have to look for a 8-bit compatible VGA card if you want to run it in original hardware ;) I'd be interested in the thoughts behind this decision. CGA would have been more period correct and more compatible with the "real" hardware that's out there (I say this as an IBM 5150 owner). Not wanting to criticise the author of course - this is still a very cool project and, being open source, I'm sure we'll see new variations popping up before too long. I might even have a go myself.
- einr 7y agoThe CGA 320x200 graphics mode is horrible to program for and would have made a 512 byte implementation much harder to accomplish. Even and odd rows of pixels on screen are separated in memory by 8k bytes, for instance. VGA mode 0x13, on the other hand, is widely known as the easiest graphics mode to program for -- all you do is throw bytes one after the other into 0x8000 + 64K and you're immediately putting 256-color graphics on the screen. 8-bit compatible VGA cards are somewhat of a rarity to find nowadays but it wasn't entirely uncommon to see 8088 or 8086 systems paired with VGA cards in the late 80's, although generally they were more common and useful with a 286 and up.
- parkertomatoes 7y agoPlayable link: https://parkertomatoes.github.io/v86/?type=mbr&content=uBMAzRD8uACgjtiOwL54fb8gFC6tkbvwANHhuBg3cwO4OALooAEB34PrEHIK6JYBKd%2BD7wjr4oHHiAmB%2FqJ9ddKxBbgCAC6lq%2BL7tADNGjsWBPp09okWBPq0Ac0WtAB0As0WiOAsSHIMPAlzCLusfS7Xov75viDmrZetkzHA6CwAgDb%2F%2BYC4KA54B6Ai5rED0uDoMQG3IegbAbcu6BYBtyjoEQG3NOgMAeugdAPoFgGJ%2BDHSuUAB9%2FGI1AjEgOQHdVu1Nzht%2FxDkOK0AChDkOG0IEOQ4rcD%2BEOSE%2F3Qt9sMFdAw7FgD6sAJyDrAI6wo6BgL6sARyArABhMR1IojYhMR1HNDodfiwCOv0iRYA%2BqIC%2BqD%2B%2BYTEdQYg3HQaiNiIRP6oBbuA%2FXUDuwIAqAx0AvfbAd%2BJfPzDAELn5%2F%2F%2Ffjw8fvzw8Px%2BPP%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FPH7%2F%2F%2BfnQgA8fv%2F%2F%2F%2F9%2BPDx%2B29v%2F%2F%2F%2BlAAAAGBgAAAA8fj8PDz9%2BPAAA%2Fn8CQgJC%2F39AQn5%2BAgJ%2FAsADQAJ%2FAkAC%2Fn8CQv97QAp%2BfgJA%2F38AAJiqkFCYZKA8qFABAAAIAAIAAAStl62E5JOwMFDGRP8C6Ob%2BWFBTUVdQuzB9LteTuQgAiPjQ43ICMcCA%2FxByCoA9DnUD6Rf%2BMgWq4uaBxzgBWECoB3XSX1lbWMNPVao%3D https://parkertomatoes.github.io/v86/?type=mbr&content=uBMAz...
- nanochess 7y agoStandby for my upcoming 8088 programming book ;)