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

#define ALLOC_MINBITS           3       /* smallest chunk size is 8 bytes */
#define ALLOCSET_NUM_FREELISTS  11
#define BITS_PER_BYTE 8

/* ----------
 * AllocSetFreeIndex -
 *
 *              Depending on the size of an allocation compute which freechunk
 *              list of the alloc set it belongs to.  Caller must have verified
 *              that size <= ALLOC_CHUNK_LIMIT.
 * ----------
 */
int
AllocSetFreeIndex_clz(size_t size)
{
	int                     idx = 0;

	if (size > (1 << ALLOC_MINBITS))
	{
		size = (size - 1) >> ALLOC_MINBITS;

		idx = sizeof(unsigned int) * BITS_PER_BYTE -
			__builtin_clz((unsigned int)size);

	}

	return idx;
}

int
AllocSetFreeIndex_fh(size_t size)
{
	int                     idx = 0;

	if (size > (1 << ALLOC_MINBITS))
	{
		size = (size - 1) >> ALLOC_MINBITS;


		union { unsigned int u[2]; double d; } t; // temp

		t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
		t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = size;
		t.d -= 4503599627370496.0;
		idx = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FE;
	       
	}

	return idx;
}

int
AllocSetFreeIndex_lt(size_t size)
{
	int                     idx = 0;

	if (size > (1 << ALLOC_MINBITS))
	{
		size = (size - 1) >> ALLOC_MINBITS;


#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n

		static const char LogTable256[256] = 
			{
				0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
				LT(5), LT(6), LT(6), LT(7), LT(7), LT(7), LT(7),
				LT(8), LT(8), LT(8), LT(8), LT(8), LT(8), LT(8), LT(8)
			};

		unsigned int t, tt; // temporaries

		if (tt = size >> 16)
		{
			idx = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
		}
		else 
		{
			idx = (t = size >> 8) ? 8 + LogTable256[t] : LogTable256[size];
		}

	}

	return idx;
}

int
AllocSetFreeIndex_ur(size_t size)
{
	int                     idx = 0;

	if (size > (1 << ALLOC_MINBITS))
	{
		size = (size - 1) >> ALLOC_MINBITS;


		idx++;
		size >>= 1;
		if (size != 0)
		{
			idx++;
			size >>= 1;
			if (size != 0)
			{
				idx++;
				size >>= 1;
				if (size != 0)
				{
					idx++;
					size >>= 1;
					while (size != 0)
					{
						idx++;
						size >>= 1;
					}
				}
			}
		}
	}

	return idx;
}

int
AllocSetFreeIndex(size_t size)
{
	int                     idx = 0;

	if (size > (1 << ALLOC_MINBITS))
	{
		size = (size - 1) >> ALLOC_MINBITS;

		do
		{
			idx++;
			size >>= 1;
		}
		while (size != 0);
	}

	return idx;
}