lkml.org 
[lkml]   [2004]   [Apr]   [4]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: remove bitmap_shift_*() bitmap length limits
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 14:02    [W:0.041 / U:0.364 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site