Most efficient way to sum the 1's in a byte

Lucky

I am trying to find the number of ones in a byte so that I can determine the parity bit. I have some code, but I am unsatisfied with it because I know there is a better way. Right now I'm having·a brain fart, and can't come up with anything. This is what I have:

·· index := %0000_0001
·· repeat rep from 0 to 7
····· if(KeySig &·index == 1)
········ ++parity
····· index <<= 1

·· if(parity // 2 == 1)······· 'odd parity
····· parity := 0
·· else
····· parity := 1

Is there a better way?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
"You do not really understand something unless you can explain it to your grandmother."


-Lucky[size=-1][/size]

Post Edited (Lucky) : 4/3/2010 12:57:58 AM GMT

kuroneko

I don't know about most efficient (it's too early here) but try this:

CON
  pattern = %0110_1001_1001_0110
  
PRI parity(b)
  return (pattern >> (b & $F) ^ pattern >> (b >> 4)) & 1 ^ 1

Edit: minor improvement

PRI parity(b)
  return !(pattern >> (b & $F) ^ pattern >> (b >> 4)) & 1

Edit: and one more

CON
  pattern08 = %1001_0110
  pattern32 = %1001_0110_0110_1001_0110_1001_1001_0110
  
PRI parity(b)
  return !(pattern32 >> b ^ pattern08 >> (b >> 5)) & 1

Post Edited (kuroneko) : 4/3/2010 4:35:39 AM GMT

Lucky

Wow, can you explain what is going on because I have no clue what you just did

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
"You do not really understand something unless you can explain it to your grandmother."


-Lucky[size=-1][/size]

Peter Jakacki

I know you can use the carry in PASM to test for parity but that Spin method is a very cute method indeed, it encapsulates what is essentially a twin table lookup in a one line'r of 22 byte tokens.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
*Peter*

kuroneko

First I split the byte into two nibbles (which can have values from 0..15). That value is used as a bit index on a 16bit constant (pattern). Said constant has a 1 in places where the bit count of the index is odd, e.g. %0111 (7) is odd meaning bit 7 in pattern is set. That bit is also shifted into position 0 (>>). This is done for both nibbles. Now we combine them (e?e=e, e?o=o, o?e=o, o?o=e) which is done by xor'ing them. What remains to be done is extract the bit 0 of the result (& 1) and change parity to even (^ 1).

Does that make sense?

pjv

Hello Lucky;

In assembler the carry holds the parity value when ANDing the long with $FFFF_FFFF. That of course is the same as the slightly more convenient form of ANDN Long, #0 ..... so a single instruction.

But that's assembly..... unfortunately I don't (yet) know or understand SPIN, and can't help you there.

Cheers,

Peter (pjv)

JonnyMac

I don't know if this is the *most* efficient, but it's simple:

pub ones(value)

  result~
  repeat 8
    result += value & 1
    value >> 1

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Jon McPhalen
Hollywood, CA

Lucky

@kuroneko: yes that makes much more sense, thank you

@pjv: how do you know assy but not spin, I thought every program on the prop needed some spin

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
"You do not really understand something unless you can explain it to your grandmother."


-Lucky[size=-1][/size]

James Newman

Well, it only takes a bit of spin to start the asm code for the prop. I too started with quite a few (some quite large and intricate) pasm programs before I had a project that was easier to do some stuff in spin. That was mainly interface using vga_text, floating math, keyboard, etc...

Beau Schwabe

Lucky,

I ran some benchmark speed test on the suggested methods...

Your original code came in at...  268.4us

kuroneko code version 1           43.4us       'return (pattern >> (b & $F) ^ pattern >> (b >> 4)) & 1 ^ 1'
kuroneko code version 2           41.4us       'return !(pattern >> (b & $F) ^ pattern >> (b >> 4)) & 1'
kuroneko code version 3           36.4us       'return !(pattern32 >> b ^ pattern08 >> (b >> 5)) & 1'

JonnyMac's code                   200.4us

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

kuroneko

It's surprising what a walk outside can do for you [noparse]:)[/noparse] One last improvement for today ...

CON
  pattern32 = %1001_0110_0110_1001_0110_1001_1001_0110

PRI parity(b)
  return !(pattern32 >> (b ^ (b >> 5))) & 1

Andrey Demenev

And moving the negation to constant saves another instruction

CON
 {pattern32 = %1001_0110_0110_1001_0110_1001_1001_0110}
  pattern32 = %0110_1001_1001_0110_1001_0110_0110_1001

PRI parity(b)
  return (pattern32 >> (b ^ (b >> 5))) & 1

kuroneko

Nice one!

wjsteele

Ok, Beau, we need a couple more speeds tests, please.

Bill

Dave Hein

Actually it seems to generate the complement of the parity.· The ! operator shouldn't be used with the original pattern32.

kuroneko

Dave Hein said...
Actually it seems to generate the complement of the parity.

As per OP, even parity is reported as 1 (not judging whether that was intended).

Beau Schwabe

wjsteele,

For speed testing, just set up the routine to be timed in a repeat loop that toggles a pin !outa[noparse][[/noparse]0]


Use this routine as a baseline time, use a scope to measure the width of the pulse.

dira[noparse][[/noparse]0]~~
repeat
  !outa[noparse][[/noparse]0]     'toggle pin 0

Now, do the same thing by adding the code you want to time and use a scope to measure the width of that pulse.

dira[noparse][[/noparse]0]~~
repeat
  !outa[noparse][[/noparse]0]     'toggle pin 0
  {place the code you want to time here} 

To isolate just how long the timed routine requires, subtract the baseline amount of time from the time with the added code.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

Roger Lee

Beau,

I like the way you think. Teach a man to fish...

Roger

Dave Hein

If you don't have a scope, but do have an LED and a resistor you can measure the time by looping the test code many times as follows:

dira[noparse][[/noparse]0]~~
repeat
  !outa[noparse][[/noparse]0]     'toggle pin 0
    repeat 10000
      {place the code you want to time here} 

Use a convenient loop count that you can easily measure with a watch.

Tracy Allen

The following uses the Spin decode/encode operators to knock down one bit at a time, so it is fastest when 1's are sparse, and easily extends to longs.

PRI ones(tbd)
  repeat until tbd==0
    tbd := tbd - |< ( >| y - 1 )     ' knock down set bits, msb first
    result++

Hacker's Delight devotes 25 pages to functions based on counting 1s.

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

MagIO2

Why would you use a scope or an LED to measure the time???? Everybody has a serial interface and every propeller has the CNT. Isn't it precise enough for you?? ;o)