Efficient exclusive OR

82 views
Skip to first unread message

Martin Eberhard

unread,
Apr 11, 2020, 8:33:45 PM4/11/20
to

I keep seeing variations of the following as the efficient PDP8 XOR routine:

CLA / clear accumulator (AC) since all we have is add!
TAD ArgOne / add (TAD) ArgOne to the just-zeroed AC
AND ArgTwo / AND ArgTwo to determine where the carrys will be
CLL RAL / clear the LINK (CLL) and rotate the accumulator left (RAL)
CMA IAC / compliment (CMA) & increment (IAC) the accumulator (negate)
TAD ArgOne / add the first argument to the negated accumulator
TAD ArgTwo / and add the second argument as well
/ the accumulator now contains the XOR of ArgOne & ArgTwo

But it seems to me that the two OP instructions can be combined:

CLA / clear accumulator (AC) since all we have is add!
TAD ArgOne / add (TAD) ArgOne to the just-zeroed AC
AND ArgTwo / AND ArgTwo to determine where the carrys will be
CLL CMA IAC RAL / **this is the order these microinstructions will execute**
TAD ArgOne / add the first argument to the negated accumulator
TAD ArgTwo / and add the second argument as well
/ the accumulator now contains the XOR of ArgOne & ArgTwo

Of course, the micro-instructions are performed in a different order. But as far as I can see, the result is still the same.

Fundamentally, the sequence
CLL RAL /times 2
CMA IAC /2's complement

first multiplies by 2, and then takes the two's complement, for the result of multiplying by -2.

whereas the sequence
CLL /just getting ready
CMA IAC /2's complement
RAL /times 2 (L is already 0)

first takes the 2's complement and then multiplies by 2, which is the same thing!

And according to the Small Computer Handbook, if you pile all of these into one OP instruction (CLL CMA IAC RAL), it will execute in the order I have written them and produce the correct result.

Right??? So why does everyone write it as 2 OP instructions? What am I missing?


Martin Eberhard

unread,
Apr 11, 2020, 8:38:12 PM4/11/20
to
...does the IAC set the link bit if it overflows? That would be a the reason.

Martin Eberhard

unread,
Apr 11, 2020, 8:53:43 PM4/11/20
to
> ...does the IAC set the link bit if it overflows? That would be a the reason.

IAC does indeed set the link bit, so this explains why you need 2 OP instructions. <still learning!>

Vincent Slyngstad

unread,
Apr 11, 2020, 11:14:32 PM4/11/20
to
On 4/11/2020 5:33 PM, Martin Eberhard wrote:
> CLL CMA IAC RAL / **this is the order these microinstructions will execute**

This is incorrect. On some PDP-8 models IAC and rotates cannot be
combined. I believe that is the real reason two instructions were used.
(Have a look at page 103 of the 1967 edition of the small computer
handbook.)

Vince

(We're going to miss CJL.)

Rob Doyle

unread,
Apr 12, 2020, 11:43:36 PM4/12/20
to
On 4/11/2020 8:14 PM, Vincent Slyngstad wrote:

> (We're going to miss CJL.)

I must have missed that announcement.

He had a tremendous wealth of knowledge.

Rob Doyle.

Vincent Slyngstad

unread,
Apr 13, 2020, 2:41:46 AM4/13/20
to
I think the only place I'd seen mentioned previously is here:
https://groups.google.com/forum/#!topic/pidp-8/_nsf30zSTHo

Vince

Robert

unread,
Apr 13, 2020, 9:12:01 AM4/13/20
to
And rather sadly I suppose this consigns P?S/8 to history.
A shame - I have been waiting to try it out for more years than I care
to remember.
I expect there are a few copies floating around from friends and
acquaintances so I hope to see it someday but of course the essential
documentation will be sparse.
RIP Charles.

Scott Lurndal

unread,
Apr 13, 2020, 11:00:23 AM4/13/20
to
Along with an abrasive personality...

Andy Valencia

unread,
Apr 13, 2020, 1:29:27 PM4/13/20
to
Robert <n...@displaying.it> writes:
> >>> (We're going to miss CJL.)
> And rather sadly I suppose this consigns P?S/8 to history.
> A shame - I have been waiting to try it out for more years than I care
> to remember.

I always begged him--implored him--to open source it, package it to make it
easy for the public to try it. Let people learn from it. It just wasn't how
he saw its place in the world; I suspect that people from his generation
just didn't accept that a Magnum Opus should ever be given away.

He wrote great tomes of information, and yet I'm sure there are still entire
branches of comp sci history which have just been lost to the world.

Thank you for mentioning this here,
Andy Valencia

Rob Doyle

unread,
Apr 13, 2020, 1:59:25 PM4/13/20
to
Maybe.

There were several times when I asked what I thought was a simple
question related to a PDP8. He followed-up with several voluminous
emails privately providing a more nuanced explanation of how things
really were. He obviously spent hours doing that. I didn't know him and
he didn't owe me that.

Rob Doyle

Martin Eberhard

unread,
Apr 13, 2020, 2:48:40 PM4/13/20
to
> This is incorrect.

Actually, what I said IS correct.

Try this experiment, either on the pdp8/e simulator or on a real pdp8e. (I have done both.)

*200
7604 LOOP, LAS

7145 CLL CMA IAC RAL

7421 MQL
5200 JMP LOOP

Now set the rotary switch to MQ.
Now try entering values on the switch register, and see the result of the combined OP instruction on the lights.

All values on the switch register produce the correct value in MQ *except* 0000. When the switch register is 0000, MQ is 0001, which is incorrect, and is the result of the IAC instruction setting the LINK bit when 7777 is incremented to 0000. the subsequent RAL pulls that bit into bit position 11, resulting in 0001, instead of 0000, which would have been the correct value.

Vincent Slyngstad

unread,
Apr 13, 2020, 3:46:52 PM4/13/20
to
On 4/13/2020 11:48 AM, Martin Eberhard wrote:
>> This is incorrect.
>
> Actually, what I said IS correct.

Only for some values of PDP-8. The reference page I pointed you in the
Small Computer Handbook clearly states that for some PDP-8's, it is
incorrect.

> Try this experiment, either on the pdp8/e simulator or on a real pdp8e. (I have done both.)

I believe you. I knew it worked as you described on the 8/E, and SIMH
correctly simulates that.

Your original query in no way implied that you wanted your program to
work only on PDP-8's nearly as new as yours :-). And, I think I have
given an answer (perhaps not the only one) to your original question
about why various sources for XOR routines use two instructions instead
of one.

Vince

Scott Lurndal

unread,
Apr 13, 2020, 5:33:04 PM4/13/20
to
He seemed always happy to teach and instruct. He didn't handle
disagreement with his opinions well.

Ian Schofield

unread,
May 30, 2020, 2:03:00 PM5/30/20
to
Dear All,

I agree, CJL was really good for an opinion but not so for a discussion.
Not unusual for some of my medical colleagues!

Anyway, thanks for the XOR info. Just sent a note in to the PiDP8I group
about a c compiler update. This is the only missing function as it is
slightly tricky optimizing it for the PDP8. Might put it in.

Regards, Ian.
Reply all
Reply to author
Forward
0 new messages