Josef “Jeff” Sipek

2015-06-11

O(n) binary search for when O(log n) is just too fast.

A Constructive Look At TempleOS

D3 gallery — chock full of neat visualizations.

The Apollo Guidance Computer: Architecture and Operation seems to be a nice book.

Detecting In-Flight Page Changes with Web Tripwires

Count, Compare, Skip

I just remembered a fun fact about the Wikipedia article: Apollo Guidance Computer (AGC).

A few years ago, I was tinkering with emulating one. It kind of worked, but that’s not important.

The AGC was an accumulator architecture, with 15-bit words (the accumulator (A) and few other “registers” were 16 bits), and 1’s complement arithmetic.

Now, the fun fact. There was an instruction called ’CCS’. It took an address, loaded the accumulator with the value at the address, and then performed a 4-way branch. The easiest way to explain it is with a some code that demonstrates what happened with some C-style pseudocode (A = accumulator, Z = program counter):

Z = Z + 1;
A = mem[operand];

switch(A) {
        case POSITIVE:
        	A = A - 1;
        	/* Z is already incremented */
        	break;
        case POS_ZERO:
        	/* A is already a zero */
        	Z = Z + 1;
        	break;
        case NEGATIVE:
        	A = (~A) - 1;
        	Z = Z + 2;
        	break;
        case NEG_ZERO:
        	/* A is already a zero */
        	Z = Z + 3;
        	break;
}

So, in a program, you could see something like:

CCS addr1
TC  addr2
TC  addr3
TC  addr4
TC  addr5

So, data from addr1 was loaded, and then one of the TC instructions (TC = Transfer Control = a branch instruction) was jumped to depending on the value, then when the TC got executed, it unconditionally branched to some other address.

Of course, you didn’t have to use TC, you could use any valid instruction and CCS would happily jump to it.

My understanding is that sometimes when CCS was used, some of the 4 possible targets were impossible. Not to waste memory, a committee was organized to keep track of these holes, and fill them in with useful constants.

Powered by blahgd