shithub: femtolisp

ref: 85e6759db8e1fd064efc3cf04716b15e84ca089f
dir: /llt/bitvector.c/

/*
  bit vector primitives

  todo:
  * reverse
  * nreverse
 (- rotate left/right)
  * shl_to
  * not
  - shr_row, shl_row

  These routines are the back end supporting bit matrices. Many operations
  on bit matrices are slow (such as accessing or setting a single element!)
  but certain operations are privileged and lend themselves to extremely
  efficient implementation due to the bit-vector nature of machine integers.
  These are:
  done:
	&  |  $  ~  copy  reverse  fill  sum  prod
  todo:
	shift  trans  rowswap
  would be nice:
	channel  interleave

  Important note:
  Out-of-place functions always assume dest and source have the same amount
  of space available.

  shr_to, shl_to, not_to, and reverse_to assume source and dest don't overlap
  and_to, or_to, and xor_to allow overlap.
*/

#include "llt.h"

uint32_t *
bitvector_resize(uint32_t *b, uint64_t oldsz, uint64_t newsz, int initzero)
{
	uint32_t *p;
	size_t sz = ((newsz+31)>>5) * sizeof(uint32_t);
	p = LLT_REALLOC(b, sz);
	if(p == nil)
		return nil;
	if(initzero && newsz>oldsz){
		size_t osz = ((oldsz+31)>>5) * sizeof(uint32_t);
		memset(&p[osz/sizeof(uint32_t)], 0, sz-osz);
	}
	return p;
}

uint32_t *
bitvector_new(uint64_t n, int initzero)
{
	return bitvector_resize(nil, 0, n, initzero);
}

size_t
bitvector_nwords(uint64_t nbits)
{
	return (nbits+31)>>5;
}

void
bitvector_set(uint32_t *b, uint64_t n, uint32_t c)
{
	if(c)
		b[n>>5] |= 1<<(n&31);
	else
		b[n>>5] &= ~(1<<(n&31));
}

uint32_t
bitvector_get(uint32_t *b, uint64_t n)
{
	return b[n>>5] & (1<<(n&31));
}

static int
ntz(uint32_t x)
{
	int n;

	if(x == 0)
		return 32;
	n = 1;
	if((x & 0x0000FFFF) == 0){
		n = n +16;
		x = x >>16;
	}
	if((x & 0x000000FF) == 0){
		n = n + 8;
		x = x >> 8;
	}
	if((x & 0x0000000F) == 0){
		n = n + 4;
		x = x >> 4;
	}
	if((x & 0x00000003) == 0){
		n = n + 2;
		x = x >> 2;
	}
	return n - (x & 1);
}

// given a bitvector of n bits, starting at bit n0 find the next
// set bit, including n0.
// returns n if no set bits.
uint32_t
bitvector_next(uint32_t *b, uint64_t n0, uint64_t n)
{
	if(n0 >= n)
		return n;

	uint32_t i = n0>>5;
	uint32_t nb = n0&31;
	uint32_t nw = (n+31)>>5;
	uint32_t w;

	if(i < nw-1 || (n&31) == 0)
		w = b[i]>>nb;
	else
		w = (b[i]&lomask(n&31)) >> nb;
	if(w != 0)
		return ntz(w) + n0;
	if(i == nw-1)
		return n;
	i++;
	while(i < nw-1){
		w = b[i];
		if(w != 0)
			return ntz(w) + (i<<5);
		i++;
	}
	w = b[i];
	nb = n&31;
	i = ntz(w);
	if(nb == 0)
		return i + (n-32);
	if(i >= nb)
		return n;
	return i + (n-nb);
}