Searching \ for 'Speedily Executing XOR' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=speedily+executing
Search entire site for: 'Speedily Executing XOR'.

Truncated match.
PICList Thread
'Speedily Executing XOR'
1997\09\23@184447 by sdattalo

face
flavicon
face
Since the piclist is back down to only 50 messages or so a day,
I figured it was time to throw another bit-banging challenge out
there. This is very similar to the the bit-ANDing one I threw out
a few weeks ago.

This time the goal is to exclusive-or two bits.

Given:
bit_a  of register A
bit_b  of register B
bit_c  of register C

The goal in C parlance is:

 C.bit_c = A.bit_a ^ B.bit_b;

 A.bit_a   B.bit_b  | C.bit_C
---------------------+---------
   0          0     |   0
   0          1     |   1
   1          0     |   1
   1          1     |   0



Here's a reasonably slow version to get you started:

     CLRW             ;and set Z (i.e. result is zero)
     BTFSC   A,bit_a  ;If A.bit_a is high
      XORLW  1        ; then W=1 and clear Z

     BTFSC   B,bit_b
      XORLW  1

     SKPZ             ;If the above was non-zero
      BSF    C,bit_c  ; then set C accordingly
     SKPNZ            ;otherwise
      BCF    C,bit_c  ; clear C



Let's optimize the speed vector:

 points = 9 - max execution cycles

My best version scores 3 points.



Scott

PS. Andy, I'll give you back the beer if you can score
4 points or buy you a bud lite if you score 3.

1997\09\23@214217 by Andrew Warren

face
flavicon
face
Scott Dattalo <spam_OUTsdattaloTakeThisOuTspamunix.SRI.COM> wrote:

{Quote hidden}

Scott:

   BSF     C,bit_c
   BTFSS   A,bit_a
   BCF     C,bit_c

   MOVLW   1 << bit_c      ; This is legal because bit_c is a
                           ; literal.

   BTFSC   B,bit_b
   XORWF   C

Points = 9 - 6 = 3.  Looks like you owe me a Bud Lite...

-Andy

=== Meet other PICLIST members at the Embedded Systems Conference:
=== 6:30 pm on Wednesday, 1 October, at Bytecraft Limited's booth.
===
=== For more information on the Embedded Systems Conference,
=== see: http://www.embedsyscon.com/

=== Andrew Warren - .....fastfwdKILLspamspam@spam@ix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499

1997\09\23@225922 by John Payson

picon face
[My solutions to A^B -> C follow...

 Skip this message if you still want to try

 solving this puzzle for yourself.

















> Points = 9 - 6 = 3.  Looks like you owe me a Bud Lite...

Well, if either A or B is in the same bit-spot as C, and the other is either
1 or 4 bits away, then it's possible to do it in 5 instructions:

       movf    A,w     ; or "rlf", "rrf", or "swapf"
       xorwf   B,w
       xorwf   C,w
       andlw   1<<bit_c        ; See note above code snippet
       xorwf   C,f

Another 5-cycle special-case variant would be if A and B are in bit 7 and
C is in bit zero

       movf    A,w
       xorwf   B,w
       rrf     C
       addlw   128     ; Bit 7 of W into C
       rlf     C       ; Ta da!

This is, of course, not a general solution but it's faster when it works.
Alternatively, my submission for the more general case would be

       movlw   1 << bit_c
       iorwf   C,f
       btfss   A
        xorwf  C,f
       btfsc   B
        xorwf  C,f

or for a somewhat broader set of cases than the 5-cycle version above (either
A or B must be 1 or 4 bits removed from bit_c, while the other can be any bit)

       movf    A,w
       btfsc   B,bit_b
        xorlw  1 << bit_c
       xorwf   C,w
       andlw   1 << bit_c
       xorwf   C,f

This version is no shorter than the general version above, but it has the
advantage that the output will be glitch-free (it's still important that
bit C not change during the algorithm though other bits of that byte will
not be corrupted).

1997\09\24@044537 by Mal Goris

flavicon
face
Andrew Warren writes:
> Scott Dattalo <sdattalospamKILLspamunix.SRI.COM> wrote:
>
> > PS. Andy, I'll give you back the beer if you can score
> > 4 points or buy you a bud lite if you score 3.
>
> Scott:
>
>     BSF     C,bit_c
>     BTFSS   A,bit_a
>     BCF     C,bit_c
>
>     MOVLW   1 << bit_c      ; This is legal because bit_c is a
>                             ; literal.
>
>     BTFSC   B,bit_b
>     XORWF   C
>
> Points = 9 - 6 = 3.  Looks like you owe me a Bud Lite...

You know, I deserve half of that Bud Lite because I independently came
up with the same solution as Andy (except I had the movlw instruction
first). You can keep my half cold and fizzy till I have a chance to
come to the States.

Mal
--
http://www.nfra.nl/~mgoris/

1997\09\24@131847 by sdattalo

face
flavicon
face
Andrew Warren wrote:
>
> Scott Dattalo <.....sdattaloKILLspamspam.....unix.SRI.COM> wrote:
>
> > PS. Andy, I'll give you back the beer if you can score
> > 4 points or buy you a bud lite if you score 3.
>
> Scott:
>
>     BSF     C,bit_c
>     BTFSS   A,bit_a
>     BCF     C,bit_c
>
>     MOVLW   1 << bit_c      ; This is legal because bit_c is a
>                             ; literal.
>
>     BTFSC   B,bit_b
>     XORWF   C
>
> Points = 9 - 6 = 3.  Looks like you owe me a Bud Lite...

Sure does. BTW, this is the exact complement of my solution.
In other words, the BCF's are BSF's, etc.

And then Mal Goris wrote:
> You know, I deserve half of that Bud Lite because I independently came
> up with the same solution as Andy (except I had the movlw instruction
> first). You can keep my half cold and fizzy till I have a chance to
> come to the States.

Sorry Mal, the early worm gets the Bud. But if it's that important,
I'll save the other 5 for you.


Then Eric Smith, Dmitry, and Tony Nixon sent me (presumably
unintentionally) their solutions.

TONY NIXON, taking into account the unwise single-letter variable
names, wrote:
>
> Assuming W reg has bit number of C before call is made
>
>  bcf Cee,bitc
>  btfsc Bee,bitb
>  bsf Cee,bitc
>
>  btfsc Aye,bita
>  xorwf Cee

Well, replace the assumption with a MOVLW 1<<bitc and you more or
less have Andy's solution.

Dmitry Kiryashov wrote:
>
> Hello Scott ! You act like a terrorist ;)

Oh yeah, I forgot to mention Dmitry, if you don't have the fastest
solution that I'm going to shoot you.

{Quote hidden}

A variation of the theme. And finally,

Eric Smith wrote:
>
> Scott Dattalo <EraseMEsdattalospam_OUTspamTakeThisOuTunix.SRI.COM> wrote:
>
> > PS. Andy, I'll give you back the beer if you can score
> > 4 points or buy you a bud lite if you score 3.
>
> Is that offer open to others?

You can have what Mal can't stand to finish.

{Quote hidden}

Now to add to John's alternative solutions, here's one more that's
slow and stringy, but has some otherwise interesting features:


   BTFSC   A,bit_a
    goto   A_is_set

   BTFSC   B,bit_b
    goto   set_n_exit

   goto    $+1

clear
   BCF     C,bit_c
   goto    exit       ;Or RETURN

A_is_set
   BTFSC   B
    goto   clear

set_n_exit
   NOP
   BSF     C,bit_c
   goto    $+1       ;Or RETURN
exit

Features:
1) Doesn't modify W or the flags
2) Isosynchronous at 9 cycles
3) Glitch free- register C is accessed only once
4) The new state of bit_c is changed at the same
  relative point on all passes. This is useful for
  phase sensitive operations like a software PLL
  for example.


Scott

More... (looser matching)
- Last day of these posts
- In 1997 , 1998 only
- Today
- New search...