Wednesday, 3 July 2013

A neat trick

Usually, no idea in Computing is completely new. Trick bits of coding, like the xor swap algorithm (swap 2 values without an intermediate store) are well known by most people and occasionally rediscovered by rookies.

Yesterday evening, pondering the software for this thing, I came up with something that might actually be original.

It's this:

aisc 14
aisc 14
aisc 15
aisc 5
aisc 8

aisc is add immediate and skip on carry, i.e. aisc 14 adds 14 to the (4 bit) accumulator and skips the next instruction if the result is more than 15 (the largest value in a 4 bit accumulator).

It looks like gibberish. You add 5 numbers in a row. 

But it doesn't do that, because different values skip different instructions. So if  you start with 1 you do the first 2 and skip the third (1->15->13) instructions, but if you start with 2 you do the first and third and skip the second (2->0->15)

What it actually does is to map 0,1,2,3 -> 1,2,4,8 - it converts a bit number to a bit mask. (the results are 0001 0010 0100 1000 in binary). This is going to be very useful in the system routines which access hardware by ID (e.g. LEDs are accessed using two 2-bit values in a nibble, the L line to set to '1' and the D line to set to '0').

I figured it out more or less by trial and error by hand having wondered if it were possible to do this sequence this way (an index lookup or loop would be bigger and slower). Having done that I then wrote a Java program to search for these sort of aisc sequences (combined with comp, the 1's complement instruction) for other useful mappings (e.g. 0,1,2,3 -> 14,13,11,7, the 1's complement of the above). But it didn't turn up anything much of any use.

It's one of the things I like about coding for a 4-bit processor. It makes you think. I learnt to code (on a real machine) on an SC/MP Introkit (basically the same as Sinclair's MK14) and it taught  you about things like efficiency.

When I worked as a pro developer I quite often came up against outrageous wastes of either CPU time or Memory space by other coders that were quite unnecessary. On their own these don't cause a problem, but if you have lots of them in the same system then it drags the whole thing down.

The trick is to get the balance right - don't spend hours optimising every cycle out (unless it is something like an Atari 2600 - or this where space/time is important) versus a quick and lazy solution.

I think this basic fault is why Windows 3.11 (for example) worked on a 386-20 very nicely, but the prettier 32 bit versions are slower on a machine which is umpteen times faster and has thousands of times more memory and much of the drawing work done by a graphics card (I'm old enough to have developed using 32Mb Hard Disk partitions on Windows 3.1). If you read the book "Showstopper" about the development of Windows NT David Cutler (the lead) has one of this as his main premises.