Parity calculation

Ken Peterson · 2007-08-28 17:02

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!·

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

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

Paul Baker · 2007-08-28 17:09

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
Propeller Applications Engineer

Parallax, Inc.

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

Ken Peterson · 2007-08-28 17:29

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 · 2007-08-28 18:09

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

Beau Schwabe · 2007-08-28 19:12

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

IC Layout Engineer
Parallax, Inc.

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

Ken Peterson · 2007-08-28 21:10

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 · 2007-08-28 21:42

@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 · 2007-08-28 22:32

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

Ken Peterson · 2007-08-28 23:30

@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 [noparse]:)[/noparse]

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

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

deSilva · 2007-08-29 05:36

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 · 2007-08-29 12:32

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 · 2007-08-29 17:56

Tracy Allen said...
... This is from Hacker's Delight

Looks like a tacit rave review of this book.

deSilva · 2007-08-29 18:08

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 · 2007-08-29 18:19

Fred,

Yes, this is the Amazon link to Hacker's Delight. All reviews give it 5 stars. I purchased it on a recommendation here, from Cliff Biffle.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

Fred Hawkins · 2007-08-29 20:30

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

Parity calculation

Comments