Searching \ for 'Parity Challenge' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: techref.massmind.org/techref/index.htm?key=parity+challenge
Search entire site for: 'Parity Challenge'.

Truncated match.
PICList Thread
'Parity Challenge'
1998\03\13@201914 by sdattalo

face
flavicon
face
It's been a while since there's been a challenge. And since there's
been a bunch talk about RS232 stuff, I thought it might be appropriate
if we had a really fast parity generator for those software bit-banging
UARTs.

So here's the challenge:
Given the variable X, write a routine that computes the odd-parity
of X.

Here's a routine that's slow/looped:

       CLRF    parity
LOOP:
       CLRC
       RRF     X,F             ;Get LSB and put it in the carry
       SKPNC                   ;If LSB (i.e. C) is set
         INCF  parity,F        ;then count it
       MOVF    X,F
       SKPZ
         GOTO    LOOP

The least significant bit of 'parity' contains the parity of X.

The best I could do executes in 7 cycles and trashes X.

Scott

1998\03\13@202739 by William Chops Westfield

face picon face
No fair.  I'm pretty sure we already had a challenge to count the one's
bits in a byte.  calculating parity is the same thing...

BillW

1998\03\13@204035 by sdattalo

face
flavicon
face
William Chops Westfield wrote:
>
> No fair.  I'm pretty sure we already had a challenge to count the one's
> bits in a byte.  calculating parity is the same thing...
>
> BillW

Only the LSB is the same. The sample I posted is a bit-counter, but
even/odd parity generator produces only a single bit. For example,
here's another slow way to do it:


     CLRW

LOOP:
     CLRC
     XORWF  X,W
     RRF    X,F
     MOVF   X,F
     SKPZ
      goto  LOOP

In this case, the bits are 'added together' with XORs.

Scott

1998\03\13@204452 by Mauro, Chuck

flavicon
face
This may seem rather obvious to some of you, but the fastest way I know
to compute parity is to XORWF Parity,F inline with my serial output
routine (assuming a firmware bit-bang engine).  Since the data to be
output is being shifted to the right in my code loop, Bit 0 of Parity
contains the desired result of all N bits when all data bits have been
shifted out (generates odd parity).  I then shift Bit 0 of Parity out as
the final bit before the stop bit.  Since the XORWF is inline, it takes
only 1 cycle  to compute parity per bit.  Ya can't do it any faster than
that.

Sorry, but the code is part of a commercial product - and I don't have
authorization to disclose the actual serial bit-bang routine here.  But
jeez, you get the gist of it: the concept couldn't be simpler.
(Ceeeeripes Man!  It's 1 lousy instruction in your output loop! ;-)

Cheers,

Chuck

> {Original Message removed}

1998\03\13@210126 by Eric Smith

flavicon
face
Scott Dattalo <spam_OUTsdattaloTakeThisOuTspamUNIX.SRI.COM> wrote:
> It's been a while since there's been a challenge. And since there's
> been a bunch talk about RS232 stuff, I thought it might be appropriate
> if we had a really fast parity generator for those software bit-banging
> UARTs.

I've found that if I need to compute parity when I'm bit-banging a serial
protocol, it is easiest if I just compute the parity a single bit at a time,
as that bit is transmitted or received.  This works quite nicely since the
transmit or receive code usually already has the code to loop through all the
bits, and shifts them all into the same bit position.

Before the loop, I do
       clrf    parity

The loop just needs one extra instruction,
       xorwf   parity

At the end of the loop, the resultant parity is in the LSB or MSB of
'parity', depending on which way the bits get shifted.

So my "solution" takes a total of 9 cycles (two more than Scott's), but only
two instructions.

However, my best solution that doesn't "cheat" takes 8 instructions, 8
cycles, trashes X and W, and leaves the result in the LSB of either X or
W (your choice).  I'll have to think about it some more to figure out how
Scott shaved it down to 7 cycles.

Cheers,
Eric

1998\03\13@213709 by sdattalo

face
flavicon
face
Eric Smith wrote:
>

> I've found that if I need to compute parity when I'm bit-banging a serial
> protocol, it is easiest if I just compute the parity a single bit at a time,
> as that bit is transmitted or received.

Hmm, giving away Chuck's trade secrets? There's no doubt about it,
this certainly the most 'practical' way. However consider this
'impractical' application:

;PORT B, bit0 is the data output bit. All other port bits are
;configured as outputs, but are otherwise wasted

; pre-calculate the parity.

 RRF   parity,W ;Put Parity into Carry
 MOVF  data_byte,W

 CLRF  PORTB    ;start bit

 MOVWF PORTB    ;d0
 RRF   PORTB,F  ;d1 and pick up the parity bit
 RRF   PORTB,F
 RRF   PORTB,F
 RRF   PORTB,F
 RRF   PORTB,F
 RRF   PORTB,F
 RRF   PORTB,F

 RRF   PORTB,F  ;parity
 BSF   PORTB,0  ;stop bit

Single-cycle execution.



> However, my best solution that doesn't "cheat" takes 8 instructions, 8
> cycles, trashes X and W, and leaves the result in the LSB of either X or
> W (your choice).  I'll have to think about it some more to figure out how
> Scott shaved it down to 7 cycles.

Hint: My solution leaves the parity bit in two 'convenient'
places: bit1 and bit5 of 'X'. It trashes W too.

Scott

1998\03\13@221413 by Brian Schousek

picon face
Here's a hint for you Scott: with the addition of one instruction to what I
suspect is your algorithm, you can leave X untrashed. One caveat: it will
only leave the parity in bit 1 for 12c508's, but will leave it in bit 1 and
5 for 16c84's.
Brian
-----Original Message-----
From: Scott Dattalo <.....sdattaloKILLspamspam@spam@unix.sri.com>
To: PICLISTspamKILLspamMITVMA.MIT.EDU <.....PICLISTKILLspamspam.....MITVMA.MIT.EDU>
Date: Friday, March 13, 1998 9:36 PM
Subject: Re: Parity Challenge


<snip>
>Hint: My solution leaves the parity bit in two 'convenient'
>places: bit1 and bit5 of 'X'. It trashes W too.
>
>Scott

1998\03\13@224336 by Andrew Warren

face
flavicon
face
Scott Dattalo <EraseMEsdattalospam_OUTspamTakeThisOuTunix.sri.com> wrote:

> Given the variable X, write a routine that computes the odd-parity
> of X.

Scott:

                   ; X:              W:
                   ; ------------    ------------
   SWAPF   X,W     ;     ABCDEFGH        EFGHABCD
                   ;
   XORWF   X       ;     ABCDEFGH        EFGHABCD
                   ; xor EFGHABCD
                   ;
   RRF     X,W     ;                     -ABCDEFG
                   ;                 xor -EFGHABC
                   ;
   XORWF   X       ;     ABCDEFGH
                   ; xor EFGHABCD
                   ; xor -ABCDEFG
                   ; xor -EFGHABC
                   ;
   RRF     X,W     ;                     -ABCDEFG
                   ;                 xor -EFGHABC
                   ;                 xor --ABCDEF
                   ;                 xor --EFGHAB
                   ;
   RLF     X       ;     BCDEFGH-
                   ; xor FGHABCD-
                   ; xor ABCDEFG-
                   ; xor EFGHABC-
                   ;
   XORWF   X       ;     BCDEFGH-
                   ; xor FGHABCD-
                   ; xor ABCDEFG-
                   ; xor EFGHABC-
                   ; xor -ABCDEFG
                   ; xor -EFGHABC
                   ; xor --ABCDEF
                   ; xor --EFGHAB

Seven words, seven cycles; even parity is in bits 1, 2, 3, 4, and 5
of "X".

-Andy

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

1998\03\13@232021 by Brian Schousek

picon face
Andy, Scott-
8 cycles, even parity in bits 0-4, X not trashed. Lucky thing I emailed to
Scott to establish priority on the algorithm. :-)
But in all fairness, taking into account the amount of time it takes to type
in the Warren-style documentation it was probably a pretty even heat.
Note that you can bring it down to 7 cycles by working in X instead of fsr,
but who wants to roach their data?

Brian


swapf X,W     ;   fsr:           W:
xorwf X,W     ;-----------    -----------
movwf   fsr     ;   ABCDEFGH    ABCDEFGH
                       ;xorEFGHABCD    xorEFGHABCD
                       ;
rrf     fsr,F   ;   -ABCDEFG       ABCDEFGH
                       ;xor-EFGHABC    xorEFGHABCD
                       ;
rrf     fsr,F   ;   --ABCDEF       ABCDEFGH
                       ;xor--EFGHAB    xorEFGHABCD
                       ;
xorwf   fsr,F   ;   --ABCDEF       ABCDEFGH
                       ;xor--EFGHAB    xorEFGHABCD
                       ;xorABCDEFGH
                       ;xorEFGHABCD
                       ;
rrf     fsr,W   ;   --ABCDEF       ---ABCDE
                       ;xor--EFGHAB    xor---EFGHA
                       ;xorABCDEFGH    xor-ABCDEFG
                       ;xorEFGHABCD    xor-EFGHABC
                       ;
xorwf   fsr,F   ;   --ABCDEF       ---ABCDE
                       ;xor--EFGHAB    xor---EFGHA
                       ;xorABCDEFGH    xor-ABCDEFG
                       ;xorEFGHABCD    xor-EFGHABC
                       ;xor---ABCDE
                       ;xor---EFGHA
                       ;xor-ABCDEFG
                       ;xor-EFGHABC

1998\03\14@002123 by Andrew Warren

face
flavicon
face
Here's one more... This one takes 19 words, but executes in either 5
or 7 cycles, INCLUDING the test-and-branch at the end of the routine
that all the previously-posted solutions have ignored.

Oh... And this one doesn't affect X, either.

       SWAPF   X,W
       XORWF   X,W
       ANDLW   00001111B

       ADDWF   PC
       GOTO    ZERO
       GOTO    ONE
       GOTO    ONE
       GOTO    ZERO
       GOTO    ONE
       GOTO    ZERO
       GOTO    ZERO
       GOTO    ONE
       GOTO    ONE
       GOTO    ZERO
       GOTO    ZERO
       GOTO    ONE
       GOTO    ZERO
       GOTO    ONE
       GOTO    ONE

   ZERO:
       ....

   ONE:
       ....

-Andy

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

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