#include <limits.h>
#include <stdio.h>
#include <assert.h>
#include <sys/time.h>
#include <time.h>

struct ref {
	void *p;
};

#define EXPORT_SYMBOL(x)	static struct ref __ref__##x = { .p = (x) }
#define BITS_TO_LONGS(bits) \
        (((bits)+BITS_PER_LONG-1)/BITS_PER_LONG)
#define DECLARE_BITMAP(name,bits) \
        unsigned long name[BITS_TO_LONGS(bits)]
#define CLEAR_BITMAP(name,bits) \
        memset(name, 0, BITS_TO_LONGS(bits)*sizeof(unsigned long))
#define TYPEBITS(t)	(CHAR_BIT*sizeof(t))
#define BITS_PER_LONG	TYPEBITS(unsigned long)

#define MAX_BITMAP_BITS	512

#define BUG_ON(p)	assert(!(p))

static inline void bitmap_clear(unsigned long *bitmap, int bits)
{
        CLEAR_BITMAP((unsigned long *)bitmap, bits);
}

static inline void bitmap_fill(unsigned long *bitmap, int bits)
{
        memset(bitmap, 0xff, BITS_TO_LONGS(bits)*sizeof(unsigned long));
}

static inline void bitmap_copy(unsigned long *dst,
                        const unsigned long *src, int bits)
{
        memcpy(dst, src, BITS_TO_LONGS(bits)*sizeof(unsigned long));
}

static inline int set_bit(int nr, unsigned long *addr)
{
	int	mask, retval;

	addr += nr >> 5;
	mask = 1 << (nr & 0x1f);
	retval = (mask & *addr) != 0;
	*addr |= mask;
	return retval;
}

static inline int clear_bit(int nr, unsigned long *addr)
{
	int	mask, retval;

	addr += nr >> 5;
	mask = 1 << (nr & 0x1f);
	retval = (mask & *addr) != 0;
	*addr &= ~mask;
	return retval;
}

static inline int test_bit(int nr, const unsigned long *addr)
{
	int	mask;

	addr += nr >> 5;
	mask = 1 << (nr & 0x1f);
	return ((mask & *addr) != 0);
}

int bitmap_empty(const unsigned long *bitmap, int bits)
{
	int k, lim = bits/BITS_PER_LONG;
	for (k = 0; k < lim; ++k)
		if (bitmap[k])
			return 0;

	if (bits % BITS_PER_LONG)
		if (bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1))
			return 0;

	return 1;
}
EXPORT_SYMBOL(bitmap_empty);

int bitmap_full(const unsigned long *bitmap, int bits)
{
	int k, lim = bits/BITS_PER_LONG;
	for (k = 0; k < lim; ++k)
		if (~bitmap[k])
			return 0;

	if (bits % BITS_PER_LONG)
		if (~bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1))
			return 0;

	return 1;
}
EXPORT_SYMBOL(bitmap_full);

int bitmap_equal(const unsigned long *bitmap1,
		unsigned long *bitmap2, int bits)
{
	int k, lim = bits/BITS_PER_LONG;;
	for (k = 0; k < lim; ++k)
		if (bitmap1[k] != bitmap2[k])
			return 0;

	if (bits % BITS_PER_LONG)
		if ((bitmap1[k] ^ bitmap2[k]) &
				((1UL << (bits % BITS_PER_LONG)) - 1))
			return 0;

	return 1;
}
EXPORT_SYMBOL(bitmap_equal);

void bitmap_complement(unsigned long *bitmap, int bits)
{
	int k;
	int nr = BITS_TO_LONGS(bits);

	for (k = 0; k < nr; ++k)
		bitmap[k] = ~bitmap[k];
}
EXPORT_SYMBOL(bitmap_complement);

/*
 * bitmap_shift_right - logical right shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting right (dividing) means moving bits in the MS -> LS bit
 * direction.  Zeros are fed into the vacated MS positions and the
 * LS bits shifted off the bottom are lost.
 */
void bitmap_shift_right(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k, lim = BITS_TO_LONGS(bits);
	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
	unsigned long mask = (1UL << rem) - 1;
	for (k = 0; off + k < lim; ++k) {
		unsigned long upper;

		/*
		 * If shift is not word aligned, take lower rem bits of
		 * word above and make them the top rem bits of result.
		 */
		if (rem && off + k + 1 < lim)
			upper = src[off + k + 1] & mask;
		else
			upper = 0;
		dst[k] = upper << (BITS_PER_LONG - rem) | src[off + k] >> rem;
	}
	if (off)
		memset(&dst[lim - off], 0, off*sizeof(unsigned long));
}
EXPORT_SYMBOL(bitmap_shift_right);

/*
 * bitmap_shift_left - logical left shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting left (multiplying) means moving bits in the LS -> MS
 * direction.  Zeros are fed into the vacated LS bit positions
 * and those MS bits shifted off the top are lost.
 */
void bitmap_shift_left(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k, lim = BITS_TO_LONGS(bits);
	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
	for (k = lim - off - 1; k >= 0; --k) {
		unsigned long lower;

		/*
		 * If shift is not word aligned, take upper rem bits of
		 * word below and make them the bottom rem bits of result.
		 */
		if (rem && k > 0)
			lower = src[k - 1] >> (BITS_PER_LONG - rem);
		else
			lower = 0;
		dst[k + off] = lower | src[k] << rem;
	}
	if (off)
		memset(dst, 0, off*sizeof(unsigned long));
}
EXPORT_SYMBOL(bitmap_shift_left);

void bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
				const unsigned long *bitmap2, int bits)
{
	int k;
	int nr = BITS_TO_LONGS(bits);

	for (k = 0; k < nr; k++)
		dst[k] = bitmap1[k] & bitmap2[k];
}
EXPORT_SYMBOL(bitmap_and);

void bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
				const unsigned long *bitmap2, int bits)
{
	int k;
	int nr = BITS_TO_LONGS(bits);

	for (k = 0; k < nr; k++)
		dst[k] = bitmap1[k] | bitmap2[k];
}
EXPORT_SYMBOL(bitmap_or);


/*
 * bitmap_shift_right - logical right shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting right (dividing) means moving bits in the MS -> LS bit
 * direction.  Zeros are fed into the vacated MS positions and the
 * LS bits shifted off the bottom are lost.
 */
void old_bitmap_shift_right(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k;
	DECLARE_BITMAP(__shr_tmp, MAX_BITMAP_BITS);

	BUG_ON(bits > MAX_BITMAP_BITS);
	bitmap_clear(__shr_tmp, bits);
	for (k = 0; k < bits - shift; ++k)
		if (test_bit(k + shift, src))
			set_bit(k, __shr_tmp);
	bitmap_copy(dst, __shr_tmp, bits);
}
EXPORT_SYMBOL(old_bitmap_shift_right);

/*
 * bitmap_shift_left - logical left shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting left (multiplying) means moving bits in the LS -> MS
 * direction.  Zeros are fed into the vacated LS bit positions
 * and those MS bits shifted off the top are lost.
 */
void old_bitmap_shift_left(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k;
	DECLARE_BITMAP(__shl_tmp, MAX_BITMAP_BITS);

	BUG_ON(bits > MAX_BITMAP_BITS);
	bitmap_clear(__shl_tmp, bits);
	for (k = bits; k >= shift; --k)
		if (test_bit(k - shift, src))
			set_bit(k, __shl_tmp);
	bitmap_copy(dst, __shl_tmp, bits);
}
EXPORT_SYMBOL(old_bitmap_shift_left);

int main(void)
{
	int n;
	struct timeval tv;
	unsigned short seed[3];
	unsigned long bitmap1[BITS_TO_LONGS(MAX_BITMAP_BITS)],
			bitmap2[BITS_TO_LONGS(MAX_BITMAP_BITS)],
			bitmap3[BITS_TO_LONGS(MAX_BITMAP_BITS)];

	gettimeofday(&tv, NULL);
	seed[0] = (unsigned short)tv.tv_usec;
	seed[1] = (unsigned short)getpid();
	seed[2] = (unsigned short)0;

	while (1) {
		int k, shift;
		++n;
		for (k = 0; k < BITS_TO_LONGS(MAX_BITMAP_BITS); ++k)
			bitmap1[k] = (unsigned long)nrand48(seed);
		shift = (unsigned long)nrand48(seed) & (MAX_BITMAP_BITS - 1);
		/* shift = (shift + 31) & ~0x31UL; */
		memcpy(bitmap2, bitmap1, sizeof(bitmap1));
		memcpy(bitmap3, bitmap1, sizeof(bitmap1));
		if (n & 1) {
			old_bitmap_shift_left(bitmap1, bitmap1, shift, MAX_BITMAP_BITS);
			bitmap_shift_left(bitmap2, bitmap2, shift, MAX_BITMAP_BITS);
		} else {
			old_bitmap_shift_right(bitmap1, bitmap1, shift, MAX_BITMAP_BITS);
			bitmap_shift_right(bitmap2, bitmap2, shift, MAX_BITMAP_BITS);
		}
		if (memcmp(bitmap1, bitmap2, sizeof(bitmap1))) {
			printf("problem %s/%d!!!\n", (n&1) ? "left" : "right", shift);
			for (k = 0; k < BITS_TO_LONGS(MAX_BITMAP_BITS); ++k) {
				printf("orig/old/new = 0x%0*lx/0x%0*lx/0x%0*lx\n",
					2*sizeof(bitmap3[k]), bitmap3[k],
					2*sizeof(bitmap1[k]), bitmap1[k],
					2*sizeof(bitmap2[k]), bitmap2[k]);
			}
			exit(1);
		}
	}
	return 0;
}