info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Efficient exclusive OR
88 views
Skip to first unread message
Martin Eberhard
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
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
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
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
> CLL CMA IAC RAL / **this is the order these microinstructions will execute**
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
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.
> (We're going to miss CJL.)
He had a tremendous wealth of knowledge.
Rob Doyle.
Vincent Slyngstad
Apr 13, 2020, 2:41:46 AM4/13/20
to
https://groups.google.com/forum/#!topic/pidp-8/_nsf30zSTHo
Vince
Robert
Apr 13, 2020, 9:12:01 AM4/13/20
to
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
Apr 13, 2020, 11:00:23 AM4/13/20
to
Andy Valencia
Apr 13, 2020, 1:29:27 PM4/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 always begged him--implored him--to open source it, package it to make it
> A shame - I have been waiting to try it out for more years than I care
> to remember.
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
Apr 13, 2020, 1:59:25 PM4/13/20
to
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
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.
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
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
>> This is incorrect.
>
> Actually, what I said IS correct.
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.)
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
Apr 13, 2020, 5:33:04 PM4/13/20
to
disagreement with his opinions well.
Ian Schofield
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.
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.
0 new messages