Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #4017 > unrolled thread

Fast counting of 1-bits of arbitrarily long bit sequences

Back to article view | Back to comp.programming

Contents

  Fast counting of 1-bits of arbitrarily long bit sequences Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-12-02 19:17 +0100
    Re: Fast counting of 1-bits of arbitrarily long bit sequences Robert Wessel <robertwessel2@yahoo.com> - 2013-12-03 03:44 -0600
      Re: Fast counting of 1-bits of arbitrarily long bit sequences "osmium" <r124c4u102@comcast.net> - 2013-12-03 10:16 -0600
        Re: Fast counting of 1-bits of arbitrarily long bit sequences Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-12-03 21:35 +0000
        Re: Fast counting of 1-bits of arbitrarily long bit sequences Robert Wessel <robertwessel2@yahoo.com> - 2013-12-03 15:47 -0600
      Re: Fast counting of 1-bits of arbitrarily long bit sequences Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-12-03 17:31 +0100
        Re: Fast counting of 1-bits of arbitrarily long bit sequences Robert Wessel <robertwessel2@yahoo.com> - 2013-12-03 15:50 -0600
          Re: Fast counting of 1-bits of arbitrarily long bit sequences Mok-Kong Shen <mok-kong.shen@t-online.de> - 2013-12-04 16:03 +0100

#4017 — Fast counting of 1-bits of arbitrarily long bit sequences

Given a n-bit sequence, one may be interested to determine the number
of 1-bits in it. Decades ago, some computers, e.g. those from CDC, had
an instruction delivering the bit count of a computer word, which was
commonly believed to have been specially provided to facilitate some
crypto studies. A fast software bit counting algorithm for n=32 in C is
well-known. In the following is a Python code for arbitrary large
values of n, based on the same idea. Hopefully it could be useful for
some readers.

jdege has converted that to a class, available at:
http://http://s13.zetaboards.com/Crypto/topic/7129099/1/

M. K. Shen

-----------------------------------------------------------------------------------

# Fast counting of 1-bits of variables of n bits (n = 2**logn).
# M. K. Shen, 01.12.2013.

def initbitcount():
   global logn,byten,tpwi,mk
   assert(logn>=4)
   byten=2**logn//8
   tpwi=[2**i for i in range(logn)]
   b55=0x55
   b33=0x33
   b00=0x00
   b0f=0x0f
   bff=0xff
   mk=[]
   mk.append(bm(1,b55,b55))
   mk.append(bm(1,b33,b33))
   mk.append(bm(1,b0f,b0f))
   for i in range(logn-3):
     mk.append(bm(tpwi[i],b00,bff))
   return

def bm(nb,b1,b2):
   global logn,byten,tpwi,mk
   u=0
   for i in range(nb):
     u<<=8
     u|=b1
   for i in range(nb):
     u<<=8
     u|=b2
   c=byten//(2*nb)
   h=2*nb*8
   v=0
   for i in range(c):
     v<<=h
     v|=u
   return(v)

# Delivers number of 1-bits of a n-bit variable x (n=2**logn).
# logn (>= 4) is to be defined and initbitcount() invoked before first
# use of bitcount().

def bitcount(x):
   global logn,byten,tpwi,mk
   for i in range(logn):
     x=(x&mk[i])+((x>>tpwi[i])&mk[i])
   return(x)

# Example:
logn=7
initbitcount()
x=0x4a27a1e3cb477398d804530bce3d9460
print(bitcount(x))

[toc] | [next] | [standalone]

#4018

On Mon, 02 Dec 2013 19:17:55 +0100, Mok-Kong Shen
<mok-kong.shen@t-online.de> wrote:

>
>Given a n-bit sequence, one may be interested to determine the number
>of 1-bits in it. Decades ago, some computers, e.g. those from CDC, had
>an instruction delivering the bit count of a computer word, which was
>commonly believed to have been specially provided to facilitate some
>crypto studies. A fast software bit counting algorithm for n=32 in C is
>well-known. In the following is a Python code for arbitrary large
>values of n, based on the same idea. Hopefully it could be useful for
>some readers.


Many current machines have population count instructions, including
x86, zSeries, PPC/POWER, ARM...  (Not all versions, of course).

[toc] | [prev] | [next] | [standalone]

#4021

"Robert Wessel" wrote:

> On Mon, 02 Dec 2013 19:17:55 +0100, Mok-Kong Shen
> <mok-kong.shen@t-online.de> wrote:
>
>>
>>Given a n-bit sequence, one may be interested to determine the number
>>of 1-bits in it. Decades ago, some computers, e.g. those from CDC, had
>>an instruction delivering the bit count of a computer word, which was
>>commonly believed to have been specially provided to facilitate some
>>crypto studies. A fast software bit counting algorithm for n=32 in C is
>>well-known. In the following is a Python code for arbitrary large
>>values of n, based on the same idea. Hopefully it could be useful for
>>some readers.
>
>
> Many current machines have population count instructions, including
> x86, zSeries, PPC/POWER, ARM...  (Not all versions, of course).

Is there any way to use those instructions in a high-level language such as 
C without resorting to assembly language? 

[toc] | [prev] | [next] | [standalone]

#4023

"osmium" <r124c4u102@comcast.net> writes:

> "Robert Wessel" wrote:

>> Many current machines have population count instructions, including
>> x86, zSeries, PPC/POWER, ARM...  (Not all versions, of course).
>
> Is there any way to use those instructions in a high-level language such as 
> C without resorting to assembly language? 

gcc has many __builtin_xxx functions that get converted to instructions
if the target has them, but which remain as function calls if not.

For example, a call to __builtin_popcount will turn into an Intel
popcntl instruction if I specify -msse4 on the gcc command line.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#4024

On Tue, 3 Dec 2013 10:16:22 -0600, "osmium" <r124c4u102@comcast.net>
wrote:

>"Robert Wessel" wrote:
>
>> On Mon, 02 Dec 2013 19:17:55 +0100, Mok-Kong Shen
>> <mok-kong.shen@t-online.de> wrote:
>>
>>>
>>>Given a n-bit sequence, one may be interested to determine the number
>>>of 1-bits in it. Decades ago, some computers, e.g. those from CDC, had
>>>an instruction delivering the bit count of a computer word, which was
>>>commonly believed to have been specially provided to facilitate some
>>>crypto studies. A fast software bit counting algorithm for n=32 in C is
>>>well-known. In the following is a Python code for arbitrary large
>>>values of n, based on the same idea. Hopefully it could be useful for
>>>some readers.
>>
>>
>> Many current machines have population count instructions, including
>> x86, zSeries, PPC/POWER, ARM...  (Not all versions, of course).
>
>Is there any way to use those instructions in a high-level language such as 
>C without resorting to assembly language? 


Some compilers for those platforms have intrinsics which let you
access those sorts of things.  For example __popcnt64, __popcnt and
__popcnt16 in MSVC/x86.  There's an intrinsic for MSVC/ARM too
(_CountOneBits).  GCC has similar intrinsics on most platforms it
supports (__builtin_popcount, etc. for x86, the _vcnt_xx group for
ARM/Neon).

[toc] | [prev] | [next] | [standalone]

#4022

Am 03.12.2013 10:44, schrieb Robert Wessel:

> Many current machines have population count instructions, including
> x86, zSeries, PPC/POWER, ARM...  (Not all versions, of course).

I don't remember from reading a couple of books on x86 assembly 
programming in the past that there was such an instruction. Could
you please provide a pointer?

M. K. Shen

[toc] | [prev] | [next] | [standalone]

#4025

On Tue, 03 Dec 2013 17:31:10 +0100, Mok-Kong Shen
<mok-kong.shen@t-online.de> wrote:

>Am 03.12.2013 10:44, schrieb Robert Wessel:
>
>> Many current machines have population count instructions, including
>> x86, zSeries, PPC/POWER, ARM...  (Not all versions, of course).
>
>I don't remember from reading a couple of books on x86 assembly 
>programming in the past that there was such an instruction. Could
>you please provide a pointer?


The instruction is POPCNT, takes 16/32/64 bit operands.  See the usual
Intel x86 manuals.  IIRC, it's normally part of the SSE4.2 group,
although it has its own feature bit.

[toc] | [prev] | [next] | [standalone]

#4030

Am 03.12.2013 22:50, schrieb Robert Wessel:
> On Tue, 03 Dec 2013 17:31:10 +0100, Mok-Kong Shen
> <mok-kong.shen@t-online.de> wrote:

>> I don't remember from reading a couple of books on x86 assembly
>> programming in the past that there was such an instruction. Could
>> you please provide a pointer?
>
> The instruction is POPCNT, takes 16/32/64 bit operands.  See the usual
> Intel x86 manuals.  IIRC, it's normally part of the SSE4.2 group,
> although it has its own feature bit.

Thanks. I now read from Internet:

     Intel Core processors introduced a POPCNT instruction with the
     SSE4.2 instruction set extension, first available in a
     Nehalem-based Core i7 processor, released in November 2008.

M. K. Shen

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web