Oldskooler Ramblings

the unlikely child born of the home computer wars

Archive for the ‘Programming’ Category

Hump Algorithms

Posted by Trixter on August 27, 2013

I have the dumbest first-world problems. The current one: I’ve come up with new ideas for a retroprogramming/demoscene project, ideas that nobody on my platform (4.77MHz 8088) has ever attempted. They’re pretty radical, and on par with 8088 Corruption in terms of code cleverness and impact, except this time, I actually know what I’m doing (as opposed to stumbling into it somewhat by accident with Corruption). Every time I think about what is possible, I get really excited and obsess over implementation details. In my head, it’s all coded and running beautifully, bringing shocks of laughter to other retroprogrammers and demosceners alike.

The problem is, even after weeks of design, it’s still in my head.

What I have planned relies heavily on same tricks as the 8-bit democoding scene, namely lots of tables. Generation of those tables, compared to how they are used, is a highly asymmetric process: It can take hours or days to create the table, whereas using it only costs a few cycles for a memory lookup. This very similar to the process of vector quantization, where coming up with the codebook is an NP-hard problem that there is no universal solution for. To bring my ideas to life, I need to write programs that take advantage of gigs of memory and multiple cores to come up with the tables I need. So why not just write them? What’s stopping me is the dumbest of dumb problems: I simply haven’t written any large, modern, multithreaded applications before. All of my programming over the last 30 years has been either in Pascal, or assembler, using dialects and architectures that aren’t applicable to modern resources any more.

“So pick up a new language, ya moron!” is what all of you just screamed at me. I know, I know. But this is what kills me: It would take me at least a month to pick up a new language, learn its IDE, learn its visual form/component system, and the inevitable learning of how to debug my code when it all goes pants. I’ve been putting it off for at least a decade.  I can do it… but it would take at least a month to ramp up to full speed! And (said in Veruca Salt cadence) I want to code up my idea NOW!

I’m frozen. What a stupid, stupid first-world problem.

I need an algorithm for getting over the hump that can be solved in polynomial time.

Posted in Demoscene, Programming, Vintage Computing | 17 Comments »

World Firsts and Happy Accidents

Posted by Trixter on July 20, 2013

(Impatient?  Scroll down to the end of this post if you just want to watch the videos or download the programs.)

The demoscene used to be based almost completely on “world firsts”, which are bonus levels of street cred given when you are the first in the world to produce a living, working example of some new technological marvel.  In the early days it was as simple as “most sprites onscreen at once” (impressive because you were exceeding the hardware’s published limitations for that kind of thing) or “first example of texture mapping on PC” or similar.  Nowadays the “world first”, as a pure concept, as been boiled down to “first demo for a platform”.  So for modern hardware, this will likely translate into something like the very first demo for the XBone or the PS4.

But what of old hardware?  Just about every single old personal computer has had a demo made for it.  Pouet lists over 25,000 demos for over 90 platforms from the Acorn to the ZX Spectrum.  There are demos for the TI-86 calculator, for old nokia cell phones… even a goddamn typewriter.  Linus Åkesson even created his own hardware platform out of a microcontroller when nothing else seemed interesting.  It is pretty hard to find something that hasn’t had a proper demoscene demo made for it.

Luckily, my obsession with the IBM PCjr’s 30th anniversary pays off in this area.  Around the beginning of the year, I noted that there have been a few demos that supported the Tandy 1000′s 16-color graphics and 3-voice sound, but nothing that was specifically designed for the PCjr, which made it a “virgin platform”.  Since I had intimate knowledge of the CPU and had a decent development toolchain, and with @party 2013 coming up, I realized this was probably my last chance to achieve a world first, so I starting writing code around April.

To qualify as a “world first” for the platform, I felt it was appropriate to perform one or more effects that specifically required a PCjr to run, and for good measure, that nobody had ever seen before so that DOSBox or any other emulator would not be able to run the code properly.  One of my favorite features of the PCjr is a real vertical retrace interrupt that you can use to perform display operations “behind the scenes” so that any tricks you’re pulling remain invisible.  Coding to use that went very well, and no emulator or clones (save for a few early Tandy 1000 models) provided it, so I started off on a proper little demo for the platform.

Along the way, I found that my ideas to use the vertical retrace interrupt broke down because I needed to do more operations than I had time for in the blanking interval, so I wrote my own interrupt sync’d to the interval I wanted using the system timer instead.  I also discovered that the PCjr’s legendary lack of speed (it’s the slowest PC clone ever made) meant I couldn’t use the 320x200x16 mode I originally wanted to — there’s just too many bits to move around in a reasonable amount of time.  To maintain world-first status, I pondered creating a PCjr cartridge-based demo — a ton of work I wasn’t really prepared for — when I discovered that some poor coding on my part had resulted in some odd graphical properties in the 160x200x16 mode.  The wrong values had configured the PCjr’s video gate array to double each line.  Completely by accident, I had created a lower-res 160x100x16 mode with a true linear chunky organization!  (This is not the same as CGA “lowres” mode, which is based on text mode and is slow to work with.)

That mode was a great match for the slower speed of the PCjr, and I proceeded to write the entire demo and all its effects to use that mode.  I had already started a silly joke game for the PCjr, and when I discovered the 160×100 mode, I retrofitted the game to use it as well!  Both of these productions won 2nd and 1st place in their respective categories at @party 2013 (and Phoenix doing the graphics and sound for the demo was a big help; check the video below for his tiny Charlie Chaplin).

But more important than winning competitions… world first, y’all.  I’m part of an elite group of less than 100 people in the entire world.  Which I know just about nobody cares about, but I care, and that’s what makes me smile.  :-)

To view the demo, watch INTROjr on Youtube.  Regrettably, the demo is not shown at the full framerate because Youtube doesn’t support 60fps video and has no plans to in the near future (of course, they support near useless 4K resolution video, but whatever).  Download links for the software can be found on INTROjr’s Pouet page.  .

To view the game with a silly theme attached, watch HARLEM SHAKEjr  on Youtube.  Download links for the software can be found on SHAKEjr’s Pouet page.

PS: If you want source code to the PCjr-specific bits, such as the music player, the vertical retrace interrupt, setting the special graphics mode up, using multiple graphics pages, reading the joystick, etc., drop me a line.

Posted in Demoscene, Programming, Vintage Computing | 1 Comment »

Upcoming Trixter Sighting + Retroprogramming

Posted by Trixter on May 15, 2013

June 14-16 you should be able to see me at @party in Boston.  (If anyone is looking to share a hotel room, drop me a line!)  I am scheduled to give a 30-minute version of the PCjr presentation I had worked on for NOTACON, and hopefully enter a compo or two with some oldskool hardware I will be shipping to arrive ahead of me.

Speaking of entering a compo: I really, really dig retroprogramming.  The cool part is, after 10 years of retroprogramming in spare time, my kung fu is getting advanced enough where I not only know how to do what I want in assembly, but I know the fastest possible method to getting it done on the target hardware. For example, I recently implemented a vertical-retrace interrupt in software because the hardware one wasn’t good enough. It’s sick that I know how to do that, but sicker that I know why I need to do that.

I still get a kick out of impressing Jim-of-20-years-ago.

Posted in Demoscene, Programming | 7 Comments »

LZ4 on the 8088: One small drop

Posted by Trixter on February 9, 2013

I thought I had squeezed every drop of blood from the stone that is LZ4 decompression on the 8088, but with some help from Peter Ferrie and Terje Mathisen, we’ve managed to improve the decompression speed by another 1%.  1% may seem laughable, but believe me, it’s quite an accomplishment if you followed my previous 3-part series on optimizing for the 8088.

In addition to even faster code, I thought it would be interesting to see how small an LZ4 decompressor could get, so with Peter’s help we managed to come up with a version of the code that trades speed for size.  It’s 30% slower on average, but it compiles to only 78 bytes.

The downloads section of the LZ4_8088 website has been updated to contain both versions in the single .zip file.

Posted in Programming, Vintage Computing | Tagged: | Leave a Comment »

Optimizing for the 8088 and 8086 CPU, Part 3: A Case Study In Speed

Posted by Trixter on January 18, 2013

In this final part of 8088 optimization posts, I present a case study for 8088 optimization. Specifically, I’ll cover a problem that I needed to solve, how I solved it, how long it took to optimize my solution for 8088, and what the performance benefit was from that optimization.

For the TL;DR crowd who will likely skip to the end of the article: Through clever 8088 optimization and a thorough understanding of our problem, a decompression routine was created that not only beats all known methods previously created for 8088, but can actually exceed the speed of a memcopy given the right input. But to see how this was achieved, you’ll have to grab a snack and settle down for 10 minutes.

Now, on with our case study.

Read the rest of this entry »

Posted in Programming, Vintage Computing | 20 Comments »

Optimizing for the 8088 and 8086 CPU: Part 2

Posted by Trixter on January 11, 2013

Welcome back to our little crash course on how to optimize code for maximum speed on the 8088 and 8086 CPU. Let’s jump right back in with a quick way to transmogrify the contents of a buffer.

Read the rest of this entry »

Posted in Programming, Vintage Computing | 9 Comments »

Optimizing for the 8088 and 8086 CPU: Part 1

Posted by Trixter on January 10, 2013

There is a small but slowly growing hobby around retroprogramming for old PCs and compatibles. This hobby has existed for decades for other platforms, as evidenced by the active demoscenes on each retro platform, but the IBM PC (and other 4.77MHz 8088 compatibles) has only recently started to gain that same sort of attention. As a public service to the 8088 retroprogramming community — “All four of you, huh?” — I’ve decided to write a crash-course on optimizing your code for maximum speed on the 8088. This information is targeted to people who already know either modern x86 assembly or assembly for other CPUs, and are programming for the 8088 or 8086 for the first time (or the first time in a long while).

Read the rest of this entry »

Posted in Programming, Vintage Computing | 26 Comments »

Maze Generation In Thirteen Bytes

Posted by Trixter on December 17, 2012

Update 12/7/2012 @ 13:46: Peter Ferrie smashed my record by a single byte, so the record is now held by him at 12 bytes.  Congrats, and I feel like a fool for missing it :-)  I’ve tacked on his optimization to the end of my original post.

Update 1/7/2013: herm1t further smashed the record, down to 11 bytes!

Update 1/7/2013 @ 18:00: Peter bounces back and reclaims the record with 10 bytes! It kind-of breaks my target platform (uses an undocumented opcode that only works on Intel processors) but hey, a record’s a record! I’ve updated the article below.

In the past, when I’ve had a democoding breakthrough, I kept quiet and either used my discovery in a production, or just bragged to my demoscene friends privately.  However, my opportunities to achieve democoding “world firsts” are just about gone, and size coding compos seem to be dead, so I’ve decided to just write a blog post about what I’ve done instead: I’ve written a maze generator in only 13 bytes of x86 machine code.

Read the rest of this entry »

Posted in Demoscene, Programming, Vintage Computing | 20 Comments »

Reverse-engineering an old wound

Posted by Trixter on November 8, 2012

Nearly two decades ago on the usenet newsgroups comp.sys.ibm.pc.demos and comp.sys.ibm.pc.soundcard, there were some accusations flung around that Josh Jensen (Cyberstrike of Renaissance, for those who still remember the PC demoscene) had copied entire chunks of Mark J. Cox‘s MODPLAY to use in his own modplayer SuperProPlay (and later MASI sound system). Just as time has a way of healing old wounds, advances in technology has a way of ripping them open again, and a chance encounter with some familiar assembly code in October got me thinking about the accusations against Jensen all those years ago. I didn’t give it much attention back then, but I’m a different person now, with much more skill than I had 20 years ago. With decades of x86 assembler, reverse-engineering, and programming skills under my belt, I decided to take another look at this issue to see if it could be answered definitively. I armed myself with much better RE tools (IDA) as well as Josh’s released Protracker Playing Source (PPS) v1.10 source code (PPS110.ZIP) and spent about an hour looking at them both.

My verdict: Josh quite absolutely copied entire chunks of MODPLAY for use in his own code.

Read the rest of this entry »

Posted in Demoscene, Programming | 2 Comments »

Family Computing

Posted by Trixter on November 22, 2011

Today’s post over on Vintage Computing and Gaming’s Retro Scan Of The Week covered the magazine Family Computing, one of the lesser-known personal computing magazines of the 1980s, which brought back a memory that I think is important to share.  Normally I’d write a lot of historical info about Family Computing Magazine itself, but not today.  This post is less about Family Computing and more about how a simple choice my father made shaped my life.

In 1983, having started using the Apple IIs at my school for word processing and simple programming with LOGO, I became quite interested in computers and really wanted one, but our family didn’t have a lot of money at the time and couldn’t afford one, even a C64. My father was sympathetic to how I felt, and as a small consolation bought me a subscription to Family Computing Magazine. It turned out that the magazine subscription was just as valuable a gift as the computer I wanted. Whenever it arrived, I read it cover to cover in 2-3 hours, absorbing everything in that magazine and learning about every system on the market as well as what kinds of software and hardware were available for them.  More importantly, I also learned what other people were using their computers to accomplish, far beyond a simple checkbook balance or playing a game.  And for those specialized tasks, they were often writing their own software in BASIC.

That’s a nice memory, but not a life-changing one.  What changed my life, specifically, was the combination of three things:  My desire to use a computer + not actually owning one + the BASIC listings in every Family Computing magazine.  Every mag had a few BASIC programs that did various things, usually a utility program, a simple game, and some “mystery” program that displayed or printed some graphic or message and you had to run the code to see what it was.  They were written in Applesoft BASIC, with diffs for other computers of the time (usually Atari 8-bit, C64, TRS-80, and TI 99/4A were represented, with later diffs for Spectrum and PCjr’s sound and graphics).  Because we didn’t own a computer, I would spend hours tracing through the BASIC listings in my head to “run” them to see what they did.  Sometimes I had a pad next to me to jot down notes, as I couldn’t juggle more than 5-6 variables at a time. For the “mystery” programs that output graphics, I would plot the output on graph paper.  Each program was a puzzle to solve.  My brain became an emulator.

Dad saw me spend hours reading each magazine, and going over older ones, so he found a way to save monthly for a computer.  A little over a year later, he surprised the family with an AT&T PC 6300, which he was able to get at a discount because he worked at AT&T at the time. I nearly exploded, and barreled through that machine with a purpose.  I used that computer just as long as I read Family Computing, both until roughly 1989.

Today, I program in 8088 assembler for fun.  It calms me down.

Thank you, Joey Latimer, for writing all those BASIC programs, and thank you Dad, for a simple act of empathy.

Posted in Programming, Vintage Computing | 1 Comment »

 
Follow

Get every new post delivered to your Inbox.

Join 229 other followers