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
