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

[Allan Kamau <allank(at)sanbi(dot)ac(dot)za>]

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
>
>