#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define MAX_WORDS 10

#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)

typedef unsigned int bitmapword;		/* must be an unsigned type */

typedef struct Bitmapset
{
	int			nwords;			/* number of words in array */
	bitmapword	words[MAX_WORDS];	/* really [nwords] */
} Bitmapset;

#define BITS_PER_BITMAPWORD 32
#define WORDNUM(x)	((x) / BITS_PER_BITMAPWORD)
#define BITNUM(x)	((x) % BITS_PER_BITMAPWORD)


void
printbits(bitmapword b)
{
	int x = BITS_PER_BITMAPWORD - 1;
	while (x >= 0)
	{
		putchar((b >> x) & 1 ? '1' : '0');
		x--;
	}
	putchar('\n');
}

void printbitmapset(Bitmapset *a)
{
	int x;
	
	for (x = 0; x < MAX_WORDS; x++)
	{
		printbits(a->words[x]);
	}
}


Bitmapset *
bms_add_range(Bitmapset *a, int lower, int upper)
{
	int			lwordnum,
				lbitnum,
				uwordnum,
				ubitnum,
				wordnum;

	uwordnum = WORDNUM(upper);

	wordnum = lwordnum = WORDNUM(lower);
	
	/*
	 * Starting at lower's wordnum, loop over each word up to upper's wordnum.
	 * Along the way set all bits inclusively between lower and upper to 1. We
	 * only need to handle the lwordnum and uwordnum specially so we don't set
	 * any bits outside of the range.
	 */
	while (wordnum <= uwordnum)
	{
		bitmapword mask = ~(bitmapword) 0;

		/* If working on the lower word, zero out bits below 'lower'. */
		if (wordnum == lwordnum)
		{
			//mask &= ~(bitmapword)((1 << BITNUM(lower)) - 1);			
			int lbitnum = BITNUM(lower);
			mask >>= lbitnum;
			mask <<= lbitnum;
		}

		/* Likewise, if working on the upper word, zero bits above 'upper' */
		if (wordnum == uwordnum)
		{
			int ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
			mask <<= ushiftbits;
			mask >>= ushiftbits;
			//mask &= (~(bitmapword) 0) >> (BITS_PER_BITMAPWORD - (BITNUM(upper) + 1));
		}

		a->words[wordnum++] |= mask;
	}

	return a;
}

Bitmapset *
bms_add_range2(Bitmapset *a, int lower, int upper)
{
	int			lwordnum,
				lbitnum,
				uwordnum,
				ushiftbits,
				wordnum;

	uwordnum = WORDNUM(upper);

	wordnum = lwordnum = WORDNUM(lower);

	lbitnum = BITNUM(lower);
	ushiftbits = BITS_PER_BITMAPWORD - (BITNUM(upper) + 1);
	
	/*
	 * Special case when lwordnum is the same as uwordnum we must perform the
	 * upper and lower masking on the word.
	 */
	if (lwordnum == uwordnum)
	{
		a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
							  & (~(bitmapword) 0) >> ushiftbits;
	}
	else
	{
		/* turn on lbitnum and all bits left of it */
		a->words[wordnum++] |= ~(bitmapword)(((bitmapword) 1 << lbitnum) - 1);
		
		/* turn on all bits for any intermediate words */
		while (wordnum < uwordnum)
			a->words[wordnum++] = ~(bitmapword) 0;
		
		/* turn on upper's bit and all bits right of it. */
		a->words[uwordnum] |= (~(bitmapword) 0) >> ushiftbits;
	}

	return a;
}

#define LOOPS 100000000

int main(void)
{
	Bitmapset a, b;
	clock_t start, end;
	int loop;

	int lower = 1;
	//int upper = 65;
#define upper loop % (MAX_WORDS * BITS_PER_BITMAPWORD)
	
	memset(&a, 0, sizeof(a));
	memset(&b, 0, sizeof(b));


	start = clock();
	for (loop = LOOPS; loop >= 0; loop--)
		bms_add_range(&a,lower, upper);

	end = clock();

	printf("bms_add_range in %g (%g ns per loop)\n", (double) (end - start) / CLOCKS_PER_SEC, (double) (end - start) / CLOCKS_PER_SEC / LOOPS * 1000000000);

	start = clock();
	for (loop = LOOPS; loop >= 0; loop--)
		bms_add_range2(&b,lower, upper);

	end = clock();

	printf("bms_add_range2 in %g (%g ns per loop)\n", (double) (end - start) / CLOCKS_PER_SEC, (double) (end - start) / CLOCKS_PER_SEC / LOOPS * 1000000000);


	printbitmapset(&a);
	printf("-------------\n");
	printbitmapset(&b);

	return 0;
}