#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <sys/time.h>


#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))

#define mix(a,b,c) \
{ \
  a -= c;  a ^= rot(c, 4);	c += b; \
  b -= a;  b ^= rot(a, 6);	a += c; \
  c -= b;  c ^= rot(b, 8);	b += a; \
  a -= c;  a ^= rot(c,16);	c += b; \
  b -= a;  b ^= rot(a,19);	a += c; \
  c -= b;  c ^= rot(b, 4);	b += a; \
}

#define final(a,b,c) \
{ \
  c ^= b; c -= rot(b,14); \
  a ^= c; a -= rot(c,11); \
  b ^= a; b -= rot(a,25); \
  c ^= b; c -= rot(b,16); \
  a ^= c; a -= rot(c, 4); \
  b ^= a; b -= rot(a,14); \
  c ^= b; c -= rot(b,24); \
}

typedef unsigned long Size;

unsigned int
hash_int4(unsigned int k)
{
	register unsigned int a,
				b,
				c;

	a = b = c = 0x9e3779b9 + (unsigned int) sizeof(unsigned int) + 3923095;
	a += k;

	final(a, b, c);

	return c;
}

unsigned int
hash_int8(long unsigned int k)
{
	long int val = k;
	unsigned int lohalf = (unsigned int) val;
	unsigned int hihalf = (unsigned int) (val >> 32);

	lohalf ^= (val >= 0) ? hihalf : ~hihalf;

	return hash_int4(lohalf);
}

void main()
{
	long unsigned int i;
	long unsigned int max_hash = 1048576;
	Size len = max_hash / 8;
	unsigned char *bitmap;
	int	search = 500;
	int nset = 0;
	long unsigned int start;
	int	r = 0;
	char str[17];

	bitmap = malloc(len);
	memset(bitmap, 0, len);

	for (i = 0; i < ULONG_MAX; i++)
	{
		unsigned int h;
		int byte;
		int bit;

		h = hash_int8(i);

		if ((i > 0) && (i % 1000000000 == 0))
			printf("i=%lu nset=%d\n", i, nset);

		if (h >= max_hash)
			continue;

		byte = h / 8;
		bit = h % 8;

		if ((bitmap[byte] & (0x01 << bit)) != 0)
			continue;

		bitmap[byte] |= (0x01 << bit);
		nset++;
	}
}
