Searching \ for 'Parity Challenge' in subject line. ()
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.
'Parity Challenge'
1998\03\13@201914 by

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
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
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
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}
Scott Dattalo <sdattaloUNIX.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
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.

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
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 <sdattalounix.sri.com>
To: PICLISTMITVMA.MIT.EDU <PICLISTMITVMA.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
Scott Dattalo <sdattalounix.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 - fastfwdix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499
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
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

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 - fastfwdix.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...