Re: Re: Efficiently determining the number of bits set in the contents of, a VARBIT field

Thank you TJ and everyone else for the advise and the c code. Today I
did finally return to the 'number of bits set challenge' and managed to
compile and link the nbits c function which went smoothly. However the
function does crash my postgres server installation (8.3.3) with a
segmentation fault each time I call it for example SELECT
nbits_set(B'1101');
My C skills are very sparse and am unable to debug the function, I have
included the C code of this function. Is there something I may have left
out?

#include "postgres.h"
#include "utils/varbit.h"
#include "fmgr.h"
#ifdef PG_MODULE_MAGIC
PG_MODULE_MAGIC;
#endif

PG_FUNCTION_INFO_V1(nbits_set);
Datum
nbits_set(PG_FUNCTION_ARGS)
{
/* how many bits are set in a bitstring? */
VarBit *a = PG_GETARG_VARBIT_P(0);
int n=0;
int i;
unsigned char *ap = VARBITS(a);
unsigned char aval;
for (i=0; i < VARBITBYTES(a); ++i) {
aval = *ap; ++ap;
if (aval == 0) continue;
if (aval & 1) ++n;
if (aval & 2) ++n;
if (aval & 4) ++n;
if (aval & 8) ++n;
if (aval & 16) ++n;
if (aval & 32) ++n;
if (aval & 64) ++n;
if (aval & 128) ++n;
}
PG_RETURN_INT32(n);
}

Allan

Bruce Momjian wrote:
> Jean-David Beyer wrote:
>
>> TJ O'Donnell wrote:
>>
>>> I use a c function, nbits_set that will do what you need.
>>> I've posted the code in this email.
>>>
>>> TJ O'Donnell
>>> http://www.gnova.com
>>>
>>> #include "postgres.h"
>>> #include "utils/varbit.h"
>>>
>>> Datum nbits_set(PG_FUNCTION_ARGS);
>>> PG_FUNCTION_INFO_V1(nbits_set);
>>> Datum
>>> nbits_set(PG_FUNCTION_ARGS)
>>> {
>>> /* how many bits are set in a bitstring? */
>>>
>>> VarBit *a = PG_GETARG_VARBIT_P(0);
>>> int n=0;
>>> int i;
>>> unsigned char *ap = VARBITS(a);
>>> unsigned char aval;
>>> for (i=0; i < VARBITBYTES(a); ++i) {
>>> aval = *ap; ++ap;
>>> if (aval == 0) continue;
>>> if (aval & 1) ++n;
>>> if (aval & 2) ++n;
>>> if (aval & 4) ++n;
>>> if (aval & 8) ++n;
>>> if (aval & 16) ++n;
>>> if (aval & 32) ++n;
>>> if (aval & 64) ++n;
>>> if (aval & 128) ++n;
>>> }
>>> PG_RETURN_INT32(n);
>>> }
>>>
>>>
>>>
>>>
>>>> Hi all,
>>>> Am looking for a fast and efficient way to count the number of bits set
>>>> (to 1) in a VARBIT field. I am currently using
>>>> "LENGTH(REGEXP_REPLACE(CAST(a.somefield_bit_code AS TEXT),'0','','g'))".
>>>>
>>>> Allan.
>>>>
>>>
>> When I had to do that, in days with smaller amounts of RAM, but very long
>> bit-vectors, I used a faster function sort-of like this:
>>
>> static char table[256] = {
>> 0,1,1,2,1,2,2,3,1,.....
>> };
>>
>> Then like above, but instead of the loop,
>>
>> n+= table[aval];
>>
>>
>> You get the idea.
>>
>
> Uh, I was kind of confused by this, even when I saw a full
> implementation:
>
> http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable
>
> Actually, this looks even better:
>
> http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
>
>