1 // SPDX-License-Identifier: GPL-2.0-only
32  * endian architectures.  See the big-endian headers
33  * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
82  * __bitmap_shift_right - logical right shift of the bits in a bitmap
88  * Shifting right (dividing) means moving bits in the MS -> LS bit
90  * LS bits shifted off the bottom are lost.
96 	unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;  in __bitmap_shift_right()  local
98 	for (k = 0; off + k < lim; ++k) {  in __bitmap_shift_right()
105 		if (!rem || off + k + 1 >= lim)  in __bitmap_shift_right()
108 			upper = src[off + k + 1];  in __bitmap_shift_right()
109 			if (off + k + 1 == lim - 1)  in __bitmap_shift_right()
111 			upper <<= (BITS_PER_LONG - rem);  in __bitmap_shift_right()
113 		lower = src[off + k];  in __bitmap_shift_right()
114 		if (off + k == lim - 1)  in __bitmap_shift_right()
119 	if (off)  in __bitmap_shift_right()
120 		memset(&dst[lim - off], 0, off*sizeof(unsigned long));  in __bitmap_shift_right()
126  * __bitmap_shift_left - logical left shift of the bits in a bitmap
132  * Shifting left (multiplying) means moving bits in the LS -> MS
134  * and those MS bits shifted off the top are lost.
142 	unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;  in __bitmap_shift_left()  local
143 	for (k = lim - off - 1; k >= 0; --k) {  in __bitmap_shift_left()
151 			lower = src[k - 1] >> (BITS_PER_LONG - rem);  in __bitmap_shift_left()
155 		dst[k + off] = lower | upper;  in __bitmap_shift_left()
157 	if (off)  in __bitmap_shift_left()
158 		memset(dst, 0, off*sizeof(unsigned long));  in __bitmap_shift_left()
163  * bitmap_cut() - remove bit region from bitmap and right shift remaining bits
170  * Set the n-th bit of @dst iff the n-th bit of @src is set and
171  * n is less than @first, or the m-th bit of @src is set for any
174  * In pictures, example for a big-endian 32-bit architecture:
184  * if @cut is 3, and @first is 14, bits 14-16 in @src are cut and @dst is::
208 		       (~0UL >> (BITS_PER_LONG - first % BITS_PER_LONG));  in bitmap_cut()
213 	while (cut--) {  in bitmap_cut()
215 			if (i < len - 1)  in bitmap_cut()
220 			dst[i] = (dst[i] >> 1) | (carry << (BITS_PER_LONG - 1));  in bitmap_cut()
362 	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);  in __bitmap_set()
365 	while (len - bits_to_set >= 0) {  in __bitmap_set()
367 		len -= bits_to_set;  in __bitmap_set()
383 	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);  in __bitmap_clear()
386 	while (len - bits_to_clear >= 0) {  in __bitmap_clear()
388 		len -= bits_to_clear;  in __bitmap_clear()
401  * bitmap_find_next_zero_area_off - find a contiguous aligned zero area
425 	index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;  in bitmap_find_next_zero_area_off()
440  * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
447  * is not a valid bit position, map to -1.
451  * and other @pos values will get mapped to -1.  When @pos value 7
460 		return -1;  in bitmap_pos_to_ord()
466  * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
474  * whatever position is held by the n-th set bit in @old is mapped
475  * to the n-th set bit in @new.  In the more general case, allowing
477  * weight of @old, map the position of the n-th set bit in @old to
478  * the position of the m-th set bit in @new, where m == n % w.
520  * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
527  * whatever position is held by the n-th set bit in @old is mapped
528  * to the n-th set bit in @new.  In the more general case, allowing
530  * weight of @old, map the position of the n-th set bit in @old to
531  * the position of the m-th set bit in @new, where m == n % w.
559  * bitmap_onto - translate one bitmap relative to another
565  * Set the n-th bit of @dst iff there exists some m such that the
566  * n-th bit of @relmap is set, the m-th bit of @orig is set, and
567  * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
572  * using the map { <n, m> | the n-th bit of @relmap is the
573  * m-th set bit of @relmap }.
586  *  Let's say @relmap has bits 30-39 set, and @orig has bits
592  *  that is turned on in @relmap.  Since bit 0 was off in the
593  *  above example, we leave off that bit (bit 30) in @dst.
597  *  is the second bit that is turned on in @relmap.  The second
598  *  bit in @relmap that was turned on in the above example was
599  *  bit 31, so we turned on bit 31 in @dst.
601  *  Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
608  *  turned on in @relmap.  In the above example, there were
609  *  only ten bits turned on in @relmap (30..39), so that bit
630  *  various @orig's.  I list the zero-based positions of each set bit.
693  * bitmap_fold - fold larger bitmap into smaller, modulo specified size
783  * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
801 		bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);  in bitmap_from_arr32()
806  * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
824 		buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));  in bitmap_to_arr32()
831  * bitmap_from_arr64 - copy the contents of u64 array of bits to bitmap
840 	for (n = nbits; n > 0; n -= 64) {  in bitmap_from_arr64()
856 		bitmap[-1] &= BITMAP_LAST_WORD_MASK(nbits);  in bitmap_from_arr64()
861  * bitmap_to_arr64 - copy the contents of bitmap to a u64 array of bits
879 		buf[-1] &= GENMASK_ULL((nbits - 1) % 64, 0);  in bitmap_to_arr64()