#include <linux/module.h>

__u8 bitmaps[20][27] = {
		{1, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{2, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{4, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{8, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{16, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 1,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{32, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{64, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 1, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 2, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 4, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 8, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 1, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 1,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 1, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 1,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 1, 0, 0, 0,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 1,
		 0, 0, 0, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 1, 0, 0, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 1, 0},
		{0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 0, 0,
		 0, 0, 0, 0, 0, 1}
		};

uint64_t rdtsc(void) {
uint32_t lo, hi;
__asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
return (uint64_t)hi << 32 | lo;
}

static void test_bit_search_speed(void)
{
	unsigned long flags;
	uint64_t tsc_s, tsc_diff;
	int i, j, pos;
	const void *bit_addr;

	local_irq_save(flags);
	preempt_disable();

	for (i = 0; i < 20; i++) {
		printk("Test bitmap %d... \n", i);

		bit_addr = &bitmaps[i];

		tsc_s = rdtsc();

		for (j = 0; j < 1000; j++)
			find_next_bit_le(bit_addr, 216, 0);

		tsc_diff = (rdtsc() - tsc_s)/1000;

		printk("find_next_bit_le: %llu \n", tsc_diff);

		pos = 0;
		tsc_s = rdtsc();

		for (j = 0; j < 1000; j++)
			while (!test_bit_le(pos++, bit_addr));

		tsc_diff = (rdtsc() - tsc_s)/1000;

		printk("test_bit_le     : %llu \n", tsc_diff);
	}

	preempt_enable();
	local_irq_restore(flags);
}

static int __init start_test(void) {
	test_bit_search_speed();
	return 0;
}

static void __exit exit_test(void) {

}

module_init(start_test);
module_exit(exit_test);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Gu Zheng");