PureBasic Forumhttp://forums.purebasic.com/english/ Population counthttp://forums.purebasic.com/english/viewtopic.php?f=35&t=62235 Page 2 of 3

 Author: wilbert [ Fri May 15, 2015 10:34 am ] Post subject: Re: Population count davido wrote:I've chosen the PB version of the method described by idle; it runs at 210%.I present it, just in case it can be improved uponCode:Procedure popcount9(i.l)  i - (i >> 1) & \$55555555  i = (i & \$33333333) + ((i >> 2) & \$33333333)  ProcedureReturn (((i + i >> 4) & \$0f0f0f0f) * \$01010101) >> 24 & \$ffEndProcedure

 Author: davido [ Fri May 15, 2015 12:21 pm ] Post subject: Re: Population count @wilbert,Well squeezed! Thank you very much.

 Author: luis [ Fri May 15, 2015 12:36 pm ] Post subject: Re: Population count @davidoDid you miss the link I posted above ?Code:int swar(uint32_t i) {  i = i - ((i >> 1) & 0x55555555);  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;}It was already there. Don't tell me "but it's in C !"

 Author: wilbert [ Fri May 15, 2015 12:49 pm ] Post subject: Re: Population count luis wrote:It was already there. Don't tell me "but it's in C !" I know, but it didn't work when I tried it exactly like that in PureBasic x64.It turned out that the result of the multiplication instruction on x64 is a 64 bit value and that 64 bit value is shifted 24 bits to the right resulting in a wrong output.A lot of the brackets aren't required due to operator priority Code:Procedure popcount9(i.l)  i - i >> 1 & \$55555555  i = i & \$33333333 + i >> 2 & \$33333333  ProcedureReturn ((i + i >> 4) & \$0f0f0f0f * \$01010101) >> 24 & \$ffEndProcedurebut it might make less sense this way.

 Author: BasicallyPure [ Fri May 15, 2015 6:14 pm ] Post subject: Re: Population count Here is one I came up with.It yields about 285% against wilbert's assembly code.Code:Procedure PopCount_10(k.l) ; BasicallyPure   Macro AaS : result + k & 1 : k >> 1 : EndMacro   Protected result   AaS : AaS : AaS : AaS : AaS : AaS : AaS : AaS : AaS : AaS   AaS : AaS : AaS : AaS : AaS : AaS : AaS : AaS : AaS : AaS   AaS : AaS : AaS : AaS : AaS : AaS : AaS : AaS : AaS : AaS   AaS : AaS   ProcedureReturn resultEndProcedureThis is all very interesting but I don't have any idea what it can be used for.It's obviously very useful or there wouldn't be an assembly instruction for it.edit: Never mind, a little research on 'PopCnt' or 'PopCount' told me more than I ever wanted to know. It's probably a safe bet that I'll never use it.

 Author: davido [ Sat May 16, 2015 12:46 am ] Post subject: Re: Population count @luis,My apologies, I did get the code from the link you posted.Thank you.

 Author: wilbert [ Sat May 16, 2015 5:01 am ] Post subject: Re: Population count Seems indeed to scale up to 64 bits as well Code:Procedure PopCount64(x.q)  !mov rax, [p.v_x]  !mov rdx, rax  !shr rdx, 1  !and rdx, [popcount64_v55]   !sub rax, rdx   ;x = (x & \$3333333333333333) + ((x >> 2) & \$3333333333333333)  !mov rdx, rax       ;x   !and rax, [popcount64_v33]   !shr rdx, 2   !and rdx, [popcount64_v33]  !add rax, rdx  ;x = (x + (x >> 4)) & \$0f0f0f0f0f0f0f0f0f0f  !mov rdx, rax   !shr rdx, 4   !add rax, rdx   !and rax, [popcount64_v0f]  ;x * \$0101010101010101 >> 56  !imul rax, [popcount64_v01]  !shr rax, 56  ProcedureReturn  !popcount64_v01: dq 0x0101010101010101  !popcount64_v0f: dq 0x0f0f0f0f0f0f0f0f  !popcount64_v33: dq 0x3333333333333333  !popcount64_v55: dq 0x5555555555555555EndProcedure x = Random(\$FFFFFFFF)Debug Bin(x)Debug Popcount64(x) Code:Procedure PopCount64(x.q); SSE2 (both x86 and x64)  !movd xmm0, [p.v_x]  !movd xmm1, [p.v_x + 4]  !movq xmm2, [popcount64_v55]  !movq xmm3, [popcount64_v33]  !movq xmm4, [popcount64_v0f]  !punpckldq xmm0, xmm1  !movdqa xmm1, xmm0  !psrlq xmm1, 1  !pand xmm1, xmm2  !psubb xmm0, xmm1   !movdqa xmm1, xmm0   !pand xmm0, xmm3  !psrlq xmm1, 2   !pand xmm1, xmm3  !paddb xmm0, xmm1  !movdqa xmm1, xmm0  !psrlq xmm1, 4  !paddb xmm0, xmm1  !pand xmm0, xmm4  !pxor xmm1, xmm1  !psadbw xmm0, xmm1  !movd eax, xmm0  ProcedureReturn  !popcount64_v0f: dq 0x0f0f0f0f0f0f0f0f  !popcount64_v33: dq 0x3333333333333333  !popcount64_v55: dq 0x5555555555555555EndProcedureUsing twice 32 bitsCode:Procedure Popcount64(x.q)  !mov eax, [p.v_x]  !mov ecx, [p.v_x + 4]  !mov edx, ecx  !shr edx, 1  !jz popcount64_l0  !and edx, 0x55555555  !sub ecx, edx  !mov edx, ecx  !and ecx, 0x33333333  !shr edx, 2  !and edx, 0x33333333  !add ecx, edx  !mov edx, ecx  !shr edx, 4  !add ecx, edx  !and ecx, 0x0f0f0f0f  !popcount64_l0:  !mov edx, eax  !shr edx, 1  !and edx, 0x55555555  !sub eax, edx  !mov edx, eax  !and eax, 0x33333333  !shr edx, 2  !and edx, 0x33333333  !add eax, edx  !mov edx, eax  !shr edx, 4  !add eax, edx  !and eax, 0x0f0f0f0f  !add eax, ecx  !imul eax, 0x01010101  !shr eax, 24  ProcedureReturn EndProcedureA basic version should look like thisCode:Procedure PopCount64b1(i.q)  i - i >> 1 & \$5555555555555555  i = i & \$3333333333333333 + i >> 2 & \$3333333333333333  ProcedureReturn ((i + i >> 4) & \$0f0f0f0f0f0f0f0f * \$0101010101010101) >> 56EndProcedureBut this fails on x64. This code howeverCode:Procedure PopCount64b2(i.q)  Protected m.q = \$0101010101010101  i - i >> 1 & \$5555555555555555  i = i & \$3333333333333333 + i >> 2 & \$3333333333333333  i = (i + i >> 4) & \$0f0f0f0f0f0f0f0f  ProcedureReturn (i * m) >> 56EndProcedureworks fine on x64.PB bug?

 Author: idle [ Sat May 16, 2015 7:24 am ] Post subject: Re: Population count Wilbert do you know why x64 can't use immediates for the constants? In my x64 version above I had to load them into a register Code:...!mov r15, 0x5555555555555555!and rdx, r15...

 Author: wilbert [ Sat May 16, 2015 7:38 am ] Post subject: Re: Population count I completely overlooked your 64 bit version post Idle I ran into the same problem with immediate values. After some searching I found the answer ...64bit mode allows only signed 32bit immediates. The only instruction that can take a 64bit immediate is mov .

 Author: idle [ Sat May 16, 2015 8:54 am ] Post subject: Re: Population count wilbert wrote::oops: I completely overlooked your 64 bit version post Idle I ran into the same problem with immediate values. After some searching I found the answer ...64bit mode allows only signed 32bit immediates. The only instruction that can take a 64bit immediate is mov .That's good to know, I didn't expect it'd be an issue and couldn't understand why it only worked via mov.