Re: remove bitmap_shift_*() bitmap length limits

[Paul Jackson <pj@sgi.com>]

There was one bug in my untested code for simple bitmap shifts,
the left shift needs to scan downwards, not upwards, so as to
avoid clobbering the input if shifting inplace.

The total text size of my user level test program is actually
made smaller with this per-bit simple implementation, as compared
to the implementation currently in the kernel, by 80 bytes.

Bill Irwin's more sophisticated version grows the text size,
over the current implementation, by 304 bytes.  This is on
Pentium pc, gcc version 3.3.2, compiled -O2.

Given the very rare usage this bitmap shift routines receive,
I cast my vote for small and simple.

The more sophisticated logic of Bill's implementation is
impressive, but unjustified in this situation, in my view.

My fixed shift functions are:

lib/bitmap.c:
=============

    static void _setbitval(unsigned long *dst,
			    unsigned int n, int val, unsigned int nbits)
    {
	    if (n >= nbits)
		    return;
	    if (val)
		    set_bit(n, dst);
	    else
		    clear_bit(n, dst);
    }

    static int _getbitval(const unsigned long *src,
			    unsigned int n, unsigned int nbits)
    {
	    if (n >= nbits)
		    return 0;
	    return test_bit(n, src) ? 1 : 0;
    }

    void bitmap_shift_right(unsigned long *dst,
			    const unsigned long *src, int shift, int bits)
    {
	    int k;
	    for (k = 0; k < bits; k++)
		    _setbitval(dst, k, _getbitval(src, k+shift, bits), bits);
    }
    EXPORT_SYMBOL(bitmap_shift_right);

    void bitmap_shift_left(unsigned long *dst,
			    const unsigned long *src, int shift, int bits)
    {
	    int k;
	    for (k = bits-1; k >= 0; k--)
		    _setbitval(dst, k, _getbitval(src, k-shift, bits), bits);
    }
    EXPORT_SYMBOL(bitmap_shift_left);


-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373