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
109 			if (off + k + 1 == lim - 1)  in __bitmap_shift_right()
111 			upper <<= (BITS_PER_LONG - rem);  in __bitmap_shift_right()
114 		if (off + k == lim - 1)  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
133  * direction.  Zeros are fed into the vacated LS bit positions
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()
163  * bitmap_cut() - remove bit region from bitmap and right shift remaining bits
166  * @first: start bit of region to be removed
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::
190  *                      14 (bit 17     0                                   32
196  * step for each moved bit. Optimisation is left as an exercise
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
410  * the bit offset of all zero areas this function finds plus @align_offset
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
442  *	@pos: a bit position in @buf (0 <= @pos < @nbits)
443  *	@nbits: number of valid bit positions in @buf
445  * Map the bit at position @pos in @buf (of length @nbits) to the
446  * ordinal of which set bit it is.  If it is not set or if @pos
447  * is not a valid bit position, map to -1.
451  * and other @pos values will get mapped to -1.  When @pos value 7
453  * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
455  * The bit positions 0 through @bits are valid positions in @buf.
460 		return -1;  in bitmap_pos_to_ord()
466  * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
473  * Let @old and @new define a mapping of bit positions, such that
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.
491  * @new has bits 12 through 15 set.  This defines the mapping of bit
493  * bit positions unchanged.  So if say @src comes into this routine
520  * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
521  *	@oldbit: bit position to be mapped
526  * Let @old and @new define a mapping of bit positions, such that
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.
536  * Apply the above specified mapping to bit position @oldbit, returning
537  * the new bit position.
540  * @new has bits 12 through 15 set.  This defines the mapping of bit
542  * bit positions unchanged.  So if say @oldbit is 5, then this routine
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 }.
575  * Any set bits in @orig above bit number W, where W is the
583  * setting the bit (m % W) in @dst, for each bit (m) set in @orig.
586  *  Let's say @relmap has bits 30-39 set, and @orig has bits
590  *  When bit 0 is set in @orig, it means turn on the bit in
591  *  @dst corresponding to whatever is the first bit (if any)
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.
595  *  When bit 1 is set in @orig (as in the above example), it
596  *  means turn on the bit in @dst corresponding to whatever
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.
606  *  When bit 11 is set in @orig, it means turn on the bit in
607  *  @dst corresponding to whatever is the twelfth bit that is
609  *  only ten bits turned on in @relmap (30..39), so that bit
615  *		40 41 42 43 45 48 53 61 74 95
617  *  (for the curious, that's 40 plus the first ten terms of the
630  *  various @orig's.  I list the zero-based positions of each set bit.
637  *      0                0             40
640  *      10               0             40 [#f1]_
642  *      0 1 2 3 4        0 1 2 3 4     40 41 42 43 45
643  *      0 9 18 27        0 9 8 7       40 61 74 95
644  *      0 10 20 30       0             40
645  *      0 11 22 33       0 1 2 3       40 41 42 43
646  *      0 12 24 36       0 2 4 6       40 42 45 53
693  * bitmap_fold - fold larger bitmap into smaller, modulo specified size
699  * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst.
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()