shithub: femtolisp

ref: aaa5cd4ca48ace29538f59436063544f3124535e
dir: /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));
}