/*
 * Small testprogram to test the page masking algoritm
 */

#include <assert.h>

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

#define N_PAGES 0x1000000
#define printk printf

/* test-page allocation table */
char pages0[(N_PAGES>>3) + 1];
char pages[(N_PAGES>>3) + 1];
unsigned long memsize;

void map_alloc(unsigned long page_nr, int _)
{
	assert(!allocated_in_map(page_nr));
	assert(page_nr<memsize);
	pages[page_nr>>3] |= 1<<(page_nr&0x7);
}

int allocated_in_map(unsigned long page_nr)
{
	return pages[page_nr>>3] & (1<<(page_nr&0x7));
}

/* function to be tested */
void mask_iterate_simple(unsigned long bad_pfn, unsigned long bad_mask,
                         unsigned long max_page)
{
	unsigned long i;

	bad_pfn &= bad_mask;
/*--- BEGIN CODE FROM THE PATCH -------------------------------------*/
	for ( i=0; (bad_pfn|i) < max_page; i++)
	{
		if ( !(i&bad_mask) )
		{
			if ( !allocated_in_map(bad_pfn|i) )
				map_alloc(i|bad_pfn, 1);
			else
				printk("Warning, bad page %lx in use\n", bad_pfn|i);
		}
	}
/*--- END CODE FROM THE PATCH ---------------------------------------*/
}

/* alternative, faster, but more complex algorithm */
void mask_iterate_quick(unsigned long bad_pfn, unsigned long bad_mask,
                        unsigned long max_page)
{
	unsigned long i=0, step;

	bad_pfn &= bad_mask; /* bad_masked bits in the page address should be ignored */

	/* iterates over the bad_mask */
	while ( (bad_pfn|i) < max_page )
	{
		if ( !allocated_in_map(bad_pfn|i) )
			map_alloc(i|bad_pfn, 1);
		else
			printk("Warning, bad page %lx in use\n", bad_pfn|i);

		step = 1;

		if ( i == ~bad_mask ) /* break before integer overflow */
			break;

		/* the following lines are an inc() operation, skipping masked bits */
		while ( step & (bad_mask|i) )
			step <<= 1;

		i |= step;
		i &= ~(step-1);
	}
}

/* functions to compare against */
void range_iterate(unsigned long bad_psfn, unsigned long bad_pefn,
                   unsigned long max_page)
{
	unsigned long i;

	for ( i = bad_psfn; i <= bad_pefn; i++ )
		if ( (i < max_page) && !allocated_in_map(i) )
			map_alloc(i, 1);
}


/* tests and testroutines */
static struct
{
	unsigned long page_nr;
	unsigned long mask;
	unsigned long memsize;
} tests[] =
{
	{0x1c46, 0xff02, 0x10000},
	{0x1c46, 0xff02, N_PAGES},
	{0x2a000, 0xef000, 0x3c000}, /* my badram problem */
	{0x2a000, 0xef000, 0x40000},
	{0x00000, 0x00000, 0x00001},
	{0x10000, 0x11111, 0x00001},
	{0x10000, 0x11111, 0x11111},
	{0x11111, 0x11111, 0x11111},
	{0x11111, 0x00000, 0x11111},
	{0x10101, 0x01010, 0x11111},
/* 
from random import randint

for i in range(200):
    print "\t{0x%x, 0x%x, 0x%x}," % tuple([ randint(0, 0xffffff) for i in range(3) ])

 */
	/* 190 lines of random data snipped */
	{0x160dba, 0xfd810a, 0xc325c},
	{0xcf2c46, 0xa485e7, 0x4803},
	{0x32b0d7, 0xcb17e, 0x873b6f},
	{0xbce68, 0xa3e2aa, 0x92a7a1},
	{0x7bb8ee, 0xab048, 0xa937a6},
	{0x443e64, 0xaf1a17, 0xdcac7c},
	{0xdc6f8e, 0x4f894f, 0xc5a1c8},
	{0x7f620, 0x22bf9f, 0xa83a56},
	{0x22173, 0xf04ffe, 0xa78071},
	{0x5ea795, 0xe303cf, 0x55b54b},
	{0,0,0}
};

static struct
{
	unsigned long page_nr;
	unsigned long mask;
	unsigned long memsize;
	unsigned long start_range;
	unsigned long end_range;
} range_tests[] =
{
	{0x2a000, 0xff000, 0x3c000, 0x2a000, 0x2afff},
	{0x3a000, 0xff000, 0x3c000, 0x3a000, 0x3afff},
	{0x00000, 0x00000, 0xfffff, 0x00000, 0xfffff},
	{0x00000, 0xf0000, 0xfffff, 0x00000, 0x0ffff},
	{0,0,0,0,0}
};

static struct
{
	void (*test)(unsigned long,unsigned long,unsigned long);
	char *name;
} routine[] =
{
	{mask_iterate_simple, "mask_iterate_simple"},
	{mask_iterate_quick, "mask_iterate_quick"},
	{0,0}
};

void test_compare(void)
{
	int i, j;

	for (i=0; tests[i].memsize; i++)
	{
		printf("TEST %d: ", i); fflush(stdout);
		memsize=tests[i].memsize;
		memset(pages, 0, (tests[i].memsize>>3)+1);

		routine[0].test(tests[i].page_nr, tests[i].mask, tests[i].memsize);
		memcpy(pages0, pages, (tests[i].memsize>>3)+1);
	
		for (j=1; routine[j].test; j++)
		{
			memset(pages, 0, (tests[i].memsize>>3)+1);
			routine[j].test(tests[i].page_nr, tests[i].mask, tests[i].memsize);

			printf(bcmp(pages0, pages, (tests[i].memsize>>3)+1)?"fail\n":"pass\n");
		}
	}
}

void test_against_range(void)
{
	int i, j;

	for (i=0; range_tests[i].memsize; i++)
	{
		printf("TEST %d: ", i); fflush(stdout);
		memsize=range_tests[i].memsize;
		memset(pages, 0, (range_tests[i].memsize>>3)+1);

		range_iterate(range_tests[i].start_range,range_tests[i].end_range,
		              range_tests[i].memsize);
		
		memcpy(pages0, pages, (range_tests[i].memsize>>3)+1);
	
		for (j=0; routine[j].test; j++)
		{
			memset(pages, 0, (range_tests[i].memsize>>3)+1);
			routine[j].test(range_tests[i].page_nr, range_tests[i].mask,
			                range_tests[i].memsize);

			printf(bcmp(pages0, pages, (range_tests[i].memsize>>3)+1)?
			                           "fail ":"pass ");
		}
		printf("\n");
	}
}

int main(int argc, char **argv)
{

	printf("---test against range----\n");
	test_against_range();
	printf("---test eachother----\n");
	test_compare();
}