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

#define BITS_PER_LONG 32
#define PAGE_SHIFT 12
#define EXPORT_SYMBOL(x)
#define BUG_ON(x)						\
do {								\
	if ((x)) {						\
		fprintf(stderr, "BUG at %ld\n", __LINE__);	\
		exit(-1);					\
	}							\
} while (0)

static inline const int get_order(unsigned long size)
{
        int order;

        size = (size - 1) >> (PAGE_SHIFT - 1);
        order = -1;
        do {
                size >>= 1;
                order++;
        } while (size);
        return order;
}
static int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
{
	unsigned long mask;
	int pages = 1 << order;
	int i;
	int span = (pages + (BITS_PER_LONG - 1)) / BITS_PER_LONG;

	if (pages > BITS_PER_LONG)
		pages = BITS_PER_LONG;

	/* make a mask of the order */
	mask = (1ul << (pages - 1));
	mask += mask - 1;

	for (i = 0; i < bits; i += pages) {
		int index = i/BITS_PER_LONG;
		int offset = i - (index * BITS_PER_LONG);
		int j, room = 1;

		/* Find room in the bitmap */
		for (j = 0; j < span; j++)
			if ((bitmap[index+j] & (mask << offset)) != 0) {
				room = 0;
				break;
			}

		if (!room)
			continue;

		for (j = 0; j < span; j++)
			bitmap[index+j] |= (mask << offset);

		return i;
	}
#else
	/* run up the bitmap pages bits at a time */
	for (i = 0; i < bitsz; i += pages) {
		int index = i/BITS_PER_LONG;
		int offset = i - (index * BITS_PER_LONG);

		printf("index: %d, offset %d\n", index, offset);
		if((bitmap[index] & (mask << offset)) == 0) {
			/* set region in bimap */
			bitmap[index] |= (mask << offset);
			return i;
		}
	}
#endif
	return -ENOMEM;
}
EXPORT_SYMBOL(bitmap_find_free_region);

/**
 *	bitmap_release_region - release allocated bitmap region
 *	@bitmap: a pointer to the bitmap
 *	@pos: the beginning of the region
 *	@order: the order of the bits to release (number is 1<<order)
 *
 * This is the complement to __bitmap_find_free_region and releases
 * the found region (by clearing it in the bitmap).
 */
static void bitmap_release_region(unsigned long *bitmap, int pos, int order)
{
	int pages = 1 << order;
	unsigned long mask = (1ul << (pages - 1));
	int index = pos/BITS_PER_LONG;
	int offset = pos - (index * BITS_PER_LONG);
	mask += mask - 1;
	bitmap[index] &= ~(mask << offset);
}
EXPORT_SYMBOL(bitmap_release_region);

int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
{
	int pages = 1 << order;
	unsigned long mask = (1ul << (pages - 1));
	int index = pos/BITS_PER_LONG;
	int offset = pos - (index * BITS_PER_LONG);

	/* We don't do regions of pages > BITS_PER_LONG.  The
	 * algorithm would be a simple look for multiple zeros in the
	 * array, but there's no driver today that needs this.  If you
	 * trip this BUG(), you get to code it... */
	BUG_ON(pages > BITS_PER_LONG);
	mask += mask - 1;
	if (bitmap[index] & (mask << offset))
		return -EBUSY;
	bitmap[index] |= (mask << offset);
	return 0;
}
EXPORT_SYMBOL(bitmap_allocate_region);

static unsigned long *bitmap;

static inline void bitmap_search(unsigned int order)
{
	unsigned int nr_pages = (1 << order);
	int page;

	page = bitmap_find_free_region(bitmap, 0x04000000, order);
	if (page < 0) {
		printf("Failed to find space for order %d\n", order);
		return;
	}

	printf("%4d %spage%s (0x%08lx) at page %4d, offset 0x%08lx-0x%08lx\n",
	       nr_pages, nr_pages > 1 ? "" : " ", nr_pages > 1 ? "s" : "",
	       nr_pages << PAGE_SHIFT, page, page << PAGE_SHIFT,
	       (page << PAGE_SHIFT) + (nr_pages << PAGE_SHIFT));
}

int main(int argc, char **argv)
{
	unsigned int nr_pages;
	unsigned int bitmap_size;

	nr_pages = (64 << 20) >> PAGE_SHIFT;
	bitmap_size = (nr_pages + (BITS_PER_LONG - 1)) / BITS_PER_LONG;

	bitmap = malloc(bitmap_size);
	if (!bitmap)
		return -ENOMEM;

	memset(bitmap, 0, bitmap_size);

	bitmap_search(get_order(0x1000));
	bitmap_search(get_order(0x2000));
#if 1
	bitmap_search(get_order(0x4000));
	bitmap_search(get_order(0x10000));
	bitmap_search(get_order(0x20000));
	bitmap_search(get_order(0x40000));
	bitmap_search(get_order(0x100000));
	bitmap_search(get_order(0x1000));
	bitmap_search(get_order(0x1000));
#endif
	free(bitmap);
	return 0;
}