View Full Version : Parity calculation

Ken Peterson

08-29-2007, 12:02 AM

Anybody know of a really efficient parity bit calculation routine in SPIN?· I have an application that needs ODD parity and I was wondering if there is a more elegant way than shifting and XORing.

Thankyou!· http://forums.parallax.com/images/smilies/smile.gif

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

The more I know, the more I know I don't know.· Is this what they call Wisdom?

Paul Baker

08-29-2007, 12:09 AM

The fastest way hands down is using assembly language, an AND of the value with $FFFF_FFFF and the C flag holds the parity, a single instruction parity operation. This efficient means of computing parity has no analog in Spin.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

Paul Baker (mailto:pbaker@parallax.com)

Propeller Applications Engineer

[/url][url=http://www.parallax.com] (http://www.parallax.com)

Parallax, Inc. (http://www.parallax.com)

Post Edited (Paul Baker (Parallax)) : 8/28/2007 5:17:29 PM GMT

Ken Peterson

08-29-2007, 12:29 AM

Oh well...the rest of my routine is in SPIN and I'm trying to avoid using another cog just for one operation.

Thanks!

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

The more I know, the more I know I don't know.· Is this what they call Wisdom?

Tracy Allen

08-29-2007, 01:09 AM

Well, shift and XOR but faster than one bit at a time... This is from Hacker's Delight

PUB Parity(x)

result := x ^ (x >> 1)

result := result ^ (result >> 2)

result := result ^ (result >> 4)

result := result ^ (result >> 8)

result := result ^ (result >> 16)

result := result & 1 ' 1=odd, 0=even

That might be compressible to one line using intermediate assignments

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

Tracy Allen

www.emesystems.com (http://www.emesystems.com)

Beau Schwabe

08-29-2007, 02:12 AM

Tracy,

you beat me to it... (grin)

PUB Parity(x)

x ^= x >> 16 'if x equals a LONG you can start here

x ^= x >> 8 'if x equals a WORD you can start here

x ^= x >> 4 'if x equals a BYTE you can start here

x ^= x >> 2 'if x equals a NIBBLE you can start here

x ^= x >> 1

result := x & 1 ' 1=odd, 0=even

In other words, if Ken is only using BYTE variables all he needs in his routine is...

PUB Parity(x)

x ^= x >> 4

x ^= x >> 2

x ^= x >> 1

result := x & 1 ' 1=odd, 0=even

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

Beau Schwabe (mailto:bschwabe@parallax.com)

IC Layout Engineer

Parallax, Inc.

Post Edited (Beau Schwabe (Parallax)) : 8/28/2007 10:06:56 PM GMT

Ken Peterson

08-29-2007, 04:10 AM

That's pretty cool. Thanks guys. I knew there had to be a quicker way than brute force. Yes, I'm only doing a byte at a time.

I'm visualizing it. You have four XOR gates, feeding into two XOR gates, feeding into one XOR gate.

or.... ((b7 ^ b6) ^ (b5 ^ b4)) ^ ((b3 ^ b2)^(b1 ^ b0))

Ken

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

The more I know, the more I know I don't know.· Is this what they call Wisdom?

deSilva

08-29-2007, 04:42 AM

@Ken: Your formula shows that the result is correct, as XOR is an associative and commutative operation, so you can ommit ALL parentheses!

However there is a "by product" of many more results, as always 32 bits are XORed. This a why the last &1 is needed.

Tracy Allen

08-29-2007, 05:32 AM

How about this? I'm not confident with the assignment operators.

PUB parity8(x) : p

p := x

p ^= (p >>= 1) ^ (p >>= 2) ^ (p >>= 4) & 1 ' 1=odd, 0=even

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

Tracy Allen

www.emesystems.com (http://www.emesystems.com)

Ken Peterson

08-29-2007, 06:30 AM

@deSilva: The parentheses are for illustration purposes. If I had done a rotate/Xor method, then the parentheses can be left out. Just in case someone else is reading and they don't quite understand what happens.

Thanks again, Gentlemen. It's nice to have some brainstorming going on :)

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

The more I know, the more I know I don't know.· Is this what they call Wisdom?

deSilva

08-29-2007, 12:36 PM

Ken Peterson said...

@deSilva: The parentheses are for illustration purposes.

What I wanted to say - and it is not always easy as a furiner - is:

(1) YOU gave the STRUCTURE of the process using the parentheses.

(2) The XOR operation is associative and communicative, therefor you can ommit all parantheses

(3) So it becomes obvious that the process is correct, as anyone can see.

(4) You did not describe the process absolutely correctly, as there is more going on in the program than your formula shows.

Ken Peterson

08-29-2007, 07:32 PM

I guess I did show things in the wrong order. Perhaps it's more like this:

b0 := ((b7 ^ b3) ^ (b5 ^ b1)) ^ ((b2 ^ b6) ^ (b4 ^ b0))

Like I said before, the parentheses were to show the order of computation. For instance, b7 ^ b3 in the first operation. I realize that each operation is calculating a full 32 bits, but we don't care what the result is for anything above b3 after the first XOR, or anything above b1 after the second XOR, or anything above b0 after the third XOR. Hence the "& 1" at the end - it just cleans up the result.

Am I still missing something?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

The more I know, the more I know I don't know.· Is this what they call Wisdom?

Fred Hawkins

08-30-2007, 12:56 AM

Tracy Allen said...

... This is from Hacker's Delight

Looks like a tacit rave review of this book.

deSilva

08-30-2007, 01:08 AM

Ken Peterson said...

I guess I did show things in the wrong order.

Perhaps it's more like this:

b0 := ((b7 ^ b3) ^ (b5 ^ b1)) ^ ((b2 ^ b6) ^ (b4 ^ b0))

Right! So your first approach describes this program, which will also work:

PUB Parity(x)

x ^= x >> 1

x ^= x >> 2

x ^= x >> 4

return (x & 1) ' 1=odd, 0=even

Tracy Allen

08-30-2007, 01:19 AM

Fred,

Yes, this is the Amazon link to Hacker's Delight (http://www.amazon.com/Hackers-Delight-Henry-Warren-Jr/dp/0201914654/ref=pd_bbs_sr_1/103-4972897-3351065?ie=UTF8&s=books&qid=1188411318&sr=8-1). All reviews give it 5 stars. I purchased it on a recommendation here, from Cliff Biffle.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

Tracy Allen

www.emesystems.com (http://www.emesystems.com)

Fred Hawkins

08-30-2007, 03:30 AM

Tracy,

Alas that lob softball pitch for hoped for pithy paragraph was whiffed, but I did order it last night on the basis of the first reviewer's opinion of Donald Knuth. I am looking forward to curling up with it and the prop ide and reading it through. Just as soon as I get something other than led's to show a program is doing something. (Lazy much?)

Fred