Post by thread:Parity Challenge

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

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

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 <.....sdattaloKILLspam@spam@unix.sri.com> To: PICLISTKILLspamMITVMA.MIT.EDU <.....PICLISTKILLspam.....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

Scott Dattalo <EraseMEsdattalospam_OUTTakeThisOuTunix.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 - fastfwdspam_OUTix.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 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@fastfwdKILLspamix.netcom.com === Fast Forward Engineering - Vista, California === http://www.geocities.com/SiliconValley/2499