Subversion Repositories Kolibri OS

/*

 * lib/bitmap.c

 * Helper functions for bitmap.h.

 *

 * This source code is licensed under the GNU General Public License,

 * Version 2.  See the file COPYING for more details.

 */

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

//#include 

/*

 * bitmaps provide an array of bits, implemented using an an

 * array of unsigned longs.  The number of valid bits in a

 * given bitmap does _not_ need to be an exact multiple of

 * BITS_PER_LONG.

 *

 * The possible unused bits in the last, partially used word

 * of a bitmap are 'don't care'.  The implementation makes

 * no particular effort to keep them zero.  It ensures that

 * their value will not affect the results of any operation.

 * The bitmap operations that return Boolean (bitmap_empty,

 * for example) or scalar (bitmap_weight, for example) results

 * carefully filter out these unused bits from impacting their

 * results.

 *

 * These operations actually hold to a slightly stronger rule:

 * if you don't input any bitmaps to these ops that have some

 * unused bits set, then they won't output any set unused bits

 * in output bitmaps.

 *

 * The byte ordering of bitmaps is more natural on little

 * endian architectures.  See the big-endian headers

 * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h

 * for the best explanations of this ordering.

 */

int __bitmap_equal(const unsigned long *bitmap1,

		const unsigned long *bitmap2, unsigned int bits)

{

	unsigned 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]) & BITMAP_LAST_WORD_MASK(bits))

			return 0;

	return 1;

}

EXPORT_SYMBOL(__bitmap_equal);

void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)

{

	unsigned int k, lim = bits/BITS_PER_LONG;

	for (k = 0; k < lim; ++k)

		dst[k] = ~src[k];

	if (bits % BITS_PER_LONG)

		dst[k] = ~src[k];

}

EXPORT_SYMBOL(__bitmap_complement);

/**

 * __bitmap_shift_right - logical right shift of the bits in a bitmap

 *   @dst : destination bitmap

 *   @src : source bitmap

 *   @shift : shift by this many bits

 *   @nbits : 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,

			unsigned shift, unsigned nbits)

{

	unsigned k, lim = BITS_TO_LONGS(nbits);

	unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;

	unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);

	for (k = 0; off + k < lim; ++k) {

		unsigned long upper, lower;

		/*

		 * 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 = 0;

		else {

			upper = src[off + k + 1];

			if (off + k + 1 == lim - 1)

				upper &= mask;

			upper <<= (BITS_PER_LONG - rem);

		}

		lower = src[off + k];

		if (off + k == lim - 1)

			lower &= mask;

		lower >>= rem;

		dst[k] = lower | upper;

	}

	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

 *   @shift : shift by this many bits

 *   @nbits : 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,

			unsigned int shift, unsigned int nbits)

{

	int k;

	unsigned int lim = BITS_TO_LONGS(nbits);

	unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;

	for (k = lim - off - 1; k >= 0; --k) {

		unsigned long upper, 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;

		upper = src[k] << rem;

		dst[k + off] = lower | upper;

	}

	if (off)

		memset(dst, 0, off*sizeof(unsigned long));

}

EXPORT_SYMBOL(__bitmap_shift_left);

int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,

				const unsigned long *bitmap2, unsigned int bits)

{

	unsigned int k;

	unsigned int lim = bits/BITS_PER_LONG;

	unsigned long result = 0;

	for (k = 0; k < lim; k++)

		result |= (dst[k] = bitmap1[k] & bitmap2[k]);

	if (bits % BITS_PER_LONG)

		result |= (dst[k] = bitmap1[k] & bitmap2[k] &

			   BITMAP_LAST_WORD_MASK(bits));

	return result != 0;

}

EXPORT_SYMBOL(__bitmap_and);

void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,

				const unsigned long *bitmap2, unsigned int bits)

{

	unsigned int k;

	unsigned int nr = BITS_TO_LONGS(bits);

	for (k = 0; k < nr; k++)

		dst[k] = bitmap1[k] | bitmap2[k];

}

EXPORT_SYMBOL(__bitmap_or);

void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,

				const unsigned long *bitmap2, unsigned int bits)

{

	unsigned int k;

	unsigned int nr = BITS_TO_LONGS(bits);

	for (k = 0; k < nr; k++)

		dst[k] = bitmap1[k] ^ bitmap2[k];

}

EXPORT_SYMBOL(__bitmap_xor);

int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,

				const unsigned long *bitmap2, unsigned int bits)

{

	unsigned int k;

	unsigned int lim = bits/BITS_PER_LONG;

	unsigned long result = 0;

	for (k = 0; k < lim; k++)

		result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);

	if (bits % BITS_PER_LONG)

		result |= (dst[k] = bitmap1[k] & ~bitmap2[k] &

			   BITMAP_LAST_WORD_MASK(bits));

	return result != 0;

}

EXPORT_SYMBOL(__bitmap_andnot);

int __bitmap_intersects(const unsigned long *bitmap1,

			const unsigned long *bitmap2, unsigned int bits)

{

	unsigned int k, lim = bits/BITS_PER_LONG;

	for (k = 0; k < lim; ++k)

		if (bitmap1[k] & bitmap2[k])

			return 1;

	if (bits % BITS_PER_LONG)