Re: [fpc-pascal] Bitcounting

[David W Noon]

On Sat, 5 Mar 2016 19:03:24 +0100, Bart (bartjun...@gmail.com) wrote
about "[fpc-pascal] Bitcounting" (in
<camye31xhge_egouaqk7hegk7by0steko5en11dkg3dmjyxd...@mail.gmail.com>):

> Does FreePascal have a routine for counting bits?
[snip]
> Surely this can be done better?

If you don't mind a bit of C, attached is what I use. It is blazingly
fast compared to examining each bit.

It uses ASCIIZ strings, but can easily be converted to Pascal and
AnsiStrings (or whatever). However, I'll leave that to you.
-- 
Regards,

Dave  [RLU #314465]
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
david.w.n...@googlemail.com (David W Noon)
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
#ifndef BIT_COUNT_H_INCLUDED
#define BIT_COUNT_H_INCLUDED

/* Functions to count how many 1-bits or 0-bits are in a buffer area.
 *
 * Copyright (C) 2015, David W. Noon.  All rights reserved.
 * This code is released under the Berkeley License.
 *
 */

#ifdef __cplusplus
#include 
#include  /* Requires C++11 or later. */
#else
#include 
#include  /* Requires C99 or later. */
#endif

/* Function to count the number of 1 bits in a buffer. */
static uint32_t count_ones(const void * buffer, size_t bytes_count)
{
	static const uint8_t ONES[256] = {
			0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
			1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
			1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
			2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
			1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
			2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
			2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
			3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
			1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
			2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
			2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
			3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
			2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
			3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
			3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
			4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };
	uint32_t result = 0U;
#ifdef __cplusplus
	const uint8_t * byte_ptr = reinterpret_cast(buffer);
#else
	const uint8_t * byte_ptr = (const uint8_t *) buffer;
#endif

	for (size_t ctr = bytes_count; ctr > 0; --ctr)
	{
		result += ONES[*byte_ptr];
		++byte_ptr;
	}

	return result;
}

/* Function to count the number of 0 bits in a buffer. */
static uint32_t count_zeroes(const void * buffer, size_t bytes_count)
{
	static const uint8_t ZEROES[256] = {
			8, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
			7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
			7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
			6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
			7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
			6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
			6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
			5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
			7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
			6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
			6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
			5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
			6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
			5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
			5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
			4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0 };
	uint32_t result = 0U;
#ifdef __cplusplus
	const uint8_t * byte_ptr = reinterpret_cast(buffer);
#else
	const uint8_t * byte_ptr = (const uint8_t *) buffer;
#endif

	for (size_t ctr = bytes_count; ctr > 0; --ctr)
	{
		result += ZEROES[*byte_ptr];
		++byte_ptr;
	}

	return result;
}
#endif /* BIT_COUNT_H_INCLUDED */
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] Bitcounting

[Jesus Reyes A.]

En Sat, 05 Mar 2016 12:03:24 -0600, Bart  escribió:


Hi,

Does FreePascal have a routine for counting bits?
So that e.g. BitCount(%100110011) gives 5 (number of bits that are  
1)?


I came up with (extracted from IntToBin()):

function BitCount(N: Int64): Integer;
var
  Q: QWord;
  i: Integer;
begin
  Result := 0;
  Q := QWord(N);
  for i := 0 to (8 * SizeOf(N) - 1) do
  begin
if ((Q and 1) = 1) then Inc(Result);
Q := Q shr 1;
  end;
end;

Surely this can be done better?

Bart



function BitCount(N: Int64): Integer;
var
  i: Integer;
begin
  Result := 0;
  if N=0 then
exit;
  for i := 0 to (8 * SizeOf(N) - 1) do
  begin
if (N and (1 shl i)) <> 0 then Inc(result);
  end;
end;

not tested :D

Jesus Reyes A.
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] Bitcounting

[Bart]

On 3/5/16, Jonas Maebe  wrote:


> The "compilerproc" modifier does not influence code generation other
> than symbol mangling. You can just look at the implementation in the
> system unit like for any other routine.

Lazarus code-tools didn't get me there ;-)
Found it in compilerproc.inc.

Thanks.

Bart
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] Bitcounting

[Jonas Maebe]

On 05/03/16 23:12, Bart wrote:

On 3/5/16, Jonas Maebe  wrote:


>FPC 3.x has system.popcnt

Thanks.
I see it's a compilerproc.
How can I see how it'simplemented?


The "compilerproc" modifier does not influence code generation other 
than symbol mangling. You can just look at the implementation in the 
system unit like for any other routine.


It's however not just a compilerproc, but also an intrinsic. This means 
that the compiler knows about this routine, and may substitute it with 
more efficient code on some platforms. To know whether it does so in 
your case with your particular compiler version and compiler settings, 
you have to look at the generated assembler code.



Jonas
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] Bitcounting

[Bart]

On 3/5/16, Jonas Maebe  wrote:

> FPC 3.x has system.popcnt

Thanks.
I see it's a compilerproc.
How can I see how it'simplemented?

Bart
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] Bitcounting

[Santiago A.]

El 05/03/16 a las 19:03, Bart escribió:
> Hi,
>
> Does FreePascal have a routine for counting bits?
> So that e.g. BitCount(%100110011) gives 5 (number of bits that are 1)?
>
> I came up with (extracted from IntToBin()):
>
> function BitCount(N: Int64): Integer;
> var
>   Q: QWord;
>   i: Integer;
> begin
>   Result := 0;
>   Q := QWord(N);
>   for i := 0 to (8 * SizeOf(N) - 1) do
>   begin
> if ((Q and 1) = 1) then Inc(Result);
> Q := Q shr 1;
>   end;
> end;
>
> Surely this can be done better?

function BitCount_for(N: Int64): Integer;
var
  Q: QWord;
  i: Integer;
begin
  Result := 0;
  Q := QWord(N);
  for i := 0 to (8 * SizeOf(N) - 1) do
  begin
inc(result,(Q and 1));
Q := Q shr 1;
  end;
end;

function BitCount_while(N: Int64): Integer;
var
  Q: QWord;
  i: Integer;
begin
  Result := 0;
  Q := QWord(N);
  While Q>0 do begin
inc(result,(Q and 1));
Q := Q shr 1;
  end;
end;

The while version is slower if the first bit is 1


>
> Bart
> ___
> fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
> http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal


-- 
Santiago A.
s...@ciberpiula.net

___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] Bitcounting

[Jonas Maebe]

On 05/03/16 19:03, Bart wrote:

Does FreePascal have a routine for counting bits?
So that e.g. BitCount(%100110011) gives 5 (number of bits that are 1)?


FPC 3.x has system.popcnt


Jonas
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] Bitcounting

[Jeppe Johansen]

The PopCount functions do exactly that.

On 03/05/2016 07:03 PM, Bart wrote:

Hi,

Does FreePascal have a routine for counting bits?
So that e.g. BitCount(%100110011) gives 5 (number of bits that are 1)?

I came up with (extracted from IntToBin()):

function BitCount(N: Int64): Integer;
var
   Q: QWord;
   i: Integer;
begin
   Result := 0;
   Q := QWord(N);
   for i := 0 to (8 * SizeOf(N) - 1) do
   begin
 if ((Q and 1) = 1) then Inc(Result);
 Q := Q shr 1;
   end;
end;

Surely this can be done better?

Bart
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal



___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] Bitcounting

[Martin]

On 05/03/2016 18:03, Bart wrote:

Hi,

Does FreePascal have a routine for counting bits?
So that e.g. BitCount(%100110011) gives 5 (number of bits that are 1)?

I came up with (extracted from IntToBin()):


Have a look at
http://stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] Bitcounting

[Philippe Lévi]

sorry ... need change intToStr in my suggestion by something like intToStrBin
length( strChange( intToStrBin( N, '0', ''));

but it is just for fun! 


De: fpc-pascal-boun...@lists.freepascal.org 
<fpc-pascal-boun...@lists.freepascal.org> em nome de Bart <bartjun...@gmail.com>
Enviado: sábado, 5 de março de 2016 15:03
Para: FPC-Pascal users discussions
Assunto: [fpc-pascal] Bitcounting

Hi,

Does FreePascal have a routine for counting bits?
So that e.g. BitCount(%100110011) gives 5 (number of bits that are 1)?

I came up with (extracted from IntToBin()):

function BitCount(N: Int64): Integer;
var
  Q: QWord;
  i: Integer;
begin
  Result := 0;
  Q := QWord(N);
  for i := 0 to (8 * SizeOf(N) - 1) do
  begin
if ((Q and 1) = 1) then Inc(Result);
Q := Q shr 1;
  end;
end;

Surely this can be done better?

Bart
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

[fpc-pascal] Bitcounting

[Bart]

Hi,

Does FreePascal have a routine for counting bits?
So that e.g. BitCount(%100110011) gives 5 (number of bits that are 1)?

I came up with (extracted from IntToBin()):

function BitCount(N: Int64): Integer;
var
  Q: QWord;
  i: Integer;
begin
  Result := 0;
  Q := QWord(N);
  for i := 0 to (8 * SizeOf(N) - 1) do
  begin
if ((Q and 1) = 1) then Inc(Result);
Q := Q shr 1;
  end;
end;

Surely this can be done better?

Bart
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal