PDP-8 signed overflow detection

[mike]

Kyle and Vince, thanks for the education. Not sure I can use this right now,
but it is always helpful to see how others attack a problem. 

Mike Zahorik
(414) 254-6768
-----Original Message-----
From: cctalk [mailto:cctalk-bounces at classiccmp.org] On Behalf Of Kyle Owen
via cctalk
Sent: Monday, March 25, 2019 12:26 AM
To: General Discussion: On-Topic and Off-Topic Posts
Subject: Re: PDP-8 signed overflow detection

Overflow can be summarized in a few ways, such as: (sign of arg_a XOR sign
of arg_b == 0) AND (sign of arg XOR sign of result == 1)
or, less intuitively, the carry into the sign != the carry out of the sign.

My first inclination was to try the XOR approach, as that was most
intuitive to me. Using the "traditional" XOR macro on a PDP-8 is rather
inefficient, as you don't really care if you're XORing the rest of the
bits; only the sign bit. Since the sign bit is the high bit of the AC,
ignoring the link bit, simply adding the signs together results in an XOR
of the signs. However, you can't simply add the arguments, as you need to
ensure there are no carries into the sign bit; hence, ANDing one argument
with 04000 prevents any potential carries in.

I then realized that, when performing the addition with the link cleared,
the parity (i.e. XOR) of the link bit and the three sign bits will also
indicate overflow.

So, all this to say, here's my implementation:
/KYLE'S IMPLEMENTATION
SATADD, 0
CLA CLL
TAD ARGA
TAD ARGB
DCA SUM /NORMAL SUM
RAR /LINK TO SIGN BIT
TAD ARGA /SIGN OF LINK XOR SIGN OF ARGA
AND (4000
TAD ARGB /XOR SIGN OF ARGB
AND (4000
TAD SUM /XOR SIGN OF SUM
SMA CLA /OVERFLOW?
JMP NOPROB
TAD SUM /YES, GENERATE CORRECT CONSTANT
SPA CLA
CMA
TAD (4000
JMP I SATADD
NOPROB, TAD SUM /NO OVERFLOW, RETURN
JMP I SATADD
ARGA, 0
ARGB, 0
SUM, 0

Vince Slyngstad and I worked on this puzzle at VCF PNW this weekend quite a
bit, and I feel very compelled in declaring Vince the winner! Here's his
very elegant solution:
/
/ Saturation add
/
/ Add ARGA and ARGB, returning the sum in AC.  If integer overflow
/ occurs, return 3777 or 4000, depending on the sign,
/
SATADD, .-.
TAD ARGA / Get first operand
CLL RAL / Remember the sign
CLA / ...but not the magnitude
TAD ARGB / Get the second operand
SPA / Is it negative?
CML / Yes, add to sign(ARGA)
TAD ARGA / Add the rest of ARGA
SMA SNL / Link == sign == 0?
JMP I SATADD / Yes, we are done
TAD (4000 / Complement sign, also carry into L
SMA SNL / 00 => was 11
JMP RESTOR / No overflow, go restore sum and return
SMA CLA / Overflow.  Is the sum to be positive?
CMA / Yes, get -1
RESTOR, TAD (4000 / Form the correct result
JMP I SATADD / ...and return it
ARGA, .-.
ARGB, .-.

Vince's solution is 20 total locations; mine is 24. Excellent work, Vince!

All this to fix a ~45 year old bug in Spacewar! where a ship's velocity
overflows, causing the ship to "bounce" off of nothing.

Kyle