1 // SPDX-License-Identifier: GPL-2.0-only
43  * endian architectures.  See the big-endian headers
44  * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
93  * __bitmap_shift_right - logical right shift of the bits in a bitmap
99  * Shifting right (dividing) means moving bits in the MS -> LS bit
120 			if (off + k + 1 == lim - 1)  in __bitmap_shift_right()
122 			upper <<= (BITS_PER_LONG - rem);  in __bitmap_shift_right()
125 		if (off + k == lim - 1)  in __bitmap_shift_right()
131 		memset(&dst[lim - off], 0, off*sizeof(unsigned long));  in __bitmap_shift_right()
137  * __bitmap_shift_left - logical left shift of the bits in a bitmap
143  * Shifting left (multiplying) means moving bits in the LS -> MS
154 	for (k = lim - off - 1; k >= 0; --k) {  in __bitmap_shift_left()
162 			lower = src[k - 1] >> (BITS_PER_LONG - rem);  in __bitmap_shift_left()
174  * bitmap_cut() - remove bit region from bitmap and right shift remaining bits
181  * Set the n-th bit of @dst iff the n-th bit of @src is set and
182  * n is less than @first, or the m-th bit of @src is set for any
185  * In pictures, example for a big-endian 32-bit architecture:
195  * if @cut is 3, and @first is 14, bits 14-16 in @src are cut and @dst is::
206  * This is implemented in the obvious way, with a shift and carry
214 	unsigned long keep = 0, carry;  in bitmap_cut()  local
219 		       (~0UL >> (BITS_PER_LONG - first % BITS_PER_LONG));  in bitmap_cut()
224 	while (cut--) {  in bitmap_cut()
226 			if (i < len - 1)  in bitmap_cut()
227 				carry = dst[i + 1] & 1UL;  in bitmap_cut()
229 				carry = 0;  in bitmap_cut()
231 			dst[i] = (dst[i] >> 1) | (carry << (BITS_PER_LONG - 1));  in bitmap_cut()
366 	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);  in __bitmap_set()
369 	while (len - bits_to_set >= 0) {  in __bitmap_set()
371 		len -= bits_to_set;  in __bitmap_set()
387 	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);  in __bitmap_clear()
390 	while (len - bits_to_clear >= 0) {  in __bitmap_clear()
392 		len -= bits_to_clear;  in __bitmap_clear()
405  * bitmap_find_next_zero_area_off - find a contiguous aligned zero area
413  * The @align_mask should be one less than a power of 2; the effect is that
429 	index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;  in bitmap_find_next_zero_area_off()
449  * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
476  * bitmap_print_to_pagebuf - convert bitmap to list or hex format ASCII string
482  * Output format is a comma-separated list of decimal numbers and
483  * ranges if list is specified or hex digits grouped into comma-separated
486  * It is assumed that @buf is a pointer into a PAGE_SIZE, page-aligned
494 	ptrdiff_t len = PAGE_SIZE - offset_in_page(buf);  in bitmap_print_to_pagebuf()
502  * bitmap_print_to_buf  - convert bitmap to list or hex format ASCII string
521 		return -ENOMEM;  in bitmap_print_to_buf()
530  * bitmap_print_bitmask_to_buf  - convert bitmap to hex bitmask format ASCII string
598  *  - Time complexity is O(nbits^2/count), comparing to O(nbits) for snprintf().
599  *  - Memory complexity is O(nbits), comparing to O(1) for snprintf().
600  *  - @off and @count are NOT offset and number of bits to print.
601  *  - If printing part of bitmap as list, the resulting string is not a correct
604  *    may be broken, so bitmap_parselist-like parser may fail parsing it.
605  *  - If printing the whole bitmap as list by parts, user must ensure the order
607  *  - If printing the whole bitmap as list by parts, user must keep bitmap
621  * bitmap_print_list_to_buf  - convert bitmap to decimal list format ASCII string
639  * Region 9-38:4/10 describes the following bitmap structure:
657 	for (start = r->start; start <= r->end; start += r->group_len)  in bitmap_set_region()
658 		bitmap_set(bitmap, start, min(r->end - start + 1, r->off));  in bitmap_set_region()
663 	if (r->start > r->end || r->group_len == 0 || r->off > r->group_len)  in bitmap_check_region()
664 		return -EINVAL;  in bitmap_check_region()
666 	if (r->end >= r->nbits)  in bitmap_check_region()
667 		return -ERANGE;  in bitmap_check_region()
685 		return ERR_PTR(-EINVAL);  in bitmap_getnum()
687 		return ERR_PTR(-EOVERFLOW);  in bitmap_getnum()
723 		end--;  in bitmap_find_region_reverse()
730 	unsigned int lastbit = r->nbits - 1;  in bitmap_parse_region()
733 		r->start = 0;  in bitmap_parse_region()
734 		r->end = lastbit;  in bitmap_parse_region()
740 	str = bitmap_getnum(str, &r->start, lastbit);  in bitmap_parse_region()
747 	if (*str != '-')  in bitmap_parse_region()
748 		return ERR_PTR(-EINVAL);  in bitmap_parse_region()
750 	str = bitmap_getnum(str + 1, &r->end, lastbit);  in bitmap_parse_region()
759 		return ERR_PTR(-EINVAL);  in bitmap_parse_region()
761 	str = bitmap_getnum(str + 1, &r->off, lastbit);  in bitmap_parse_region()
766 		return ERR_PTR(-EINVAL);  in bitmap_parse_region()
768 	return bitmap_getnum(str + 1, &r->group_len, lastbit);  in bitmap_parse_region()
771 	r->end = r->start;  in bitmap_parse_region()
773 	r->off = r->end + 1;  in bitmap_parse_region()
774 	r->group_len = r->end + 1;  in bitmap_parse_region()
780  * bitmap_parselist - convert list format ASCII string to bitmap
786  * Input format is a comma-separated list of decimal numbers and
787  * ranges.  Consecutively set bits are shown as two hyphen-separated
794  * Example: 0-1023:2/256 ==> 0,1,256,257,512,513,768,769
796  * maximum allowed value; i.e (nmaskbits - 1).  Keep in mind that it is
800  * Returns: 0 on success, -errno on invalid input strings. Error values:
802  *   - ``-EINVAL``: wrong region format
803  *   - ``-EINVAL``: invalid character in string
804  *   - ``-ERANGE``: bit number specified too large for mask
805  *   - ``-EOVERFLOW``: integer overflow in the input parameters
837  * bitmap_parselist_user() - convert user buffer's list format ASCII
873 		c = hex_to_bin(*end--);  in bitmap_get_x32_reverse()
875 			return ERR_PTR(-EINVAL);  in bitmap_get_x32_reverse()
883 	if (hex_to_bin(*end--) >= 0)  in bitmap_get_x32_reverse()
884 		return ERR_PTR(-EOVERFLOW);  in bitmap_get_x32_reverse()
891  * bitmap_parse - convert an ASCII hex string into a bitmap.
901  * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
902  * then leading 0-bits are prepended.  %-EINVAL is returned for illegal
909 	const char *end = strnchrnul(start, buflen, '\n') - 1;  in bitmap_parse()
920 		if (!chunks--)  in bitmap_parse()
921 			return -EOVERFLOW;  in bitmap_parse()
932 	unset_bit = (BITS_TO_U32(nmaskbits) - chunks) * 32;  in bitmap_parse()
934 		bitmap_clear(maskp, unset_bit, nmaskbits - unset_bit);  in bitmap_parse()
939 		return -EOVERFLOW;  in bitmap_parse()
946  * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
953  * is not a valid bit position, map to -1.
957  * and other @pos values will get mapped to -1.  When @pos value 7
966 		return -1;  in bitmap_pos_to_ord()
972  * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
980  * whatever position is held by the n-th set bit in @old is mapped
981  * to the n-th set bit in @new.  In the more general case, allowing
982  * for the possibility that the weight 'w' of @new is less than the
983  * weight of @old, map the position of the n-th set bit in @old to
984  * the position of the m-th set bit in @new, where m == n % w.
1026  * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
1033  * whatever position is held by the n-th set bit in @old is mapped
1034  * to the n-th set bit in @new.  In the more general case, allowing
1035  * for the possibility that the weight 'w' of @new is less than the
1036  * weight of @old, map the position of the n-th set bit in @old to
1037  * the position of the m-th set bit in @new, where m == n % w.
1065  * bitmap_onto - translate one bitmap relative to another
1071  * Set the n-th bit of @dst iff there exists some m such that the
1072  * n-th bit of @relmap is set, the m-th bit of @orig is set, and
1073  * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
1078  * using the map { <n, m> | the n-th bit of @relmap is the
1079  * m-th set bit of @relmap }.
1092  *  Let's say @relmap has bits 30-39 set, and @orig has bits
1136  *  various @orig's.  I list the zero-based positions of each set bit.
1180 	 * The following code is a more efficient, but less  in bitmap_onto()
1199  * bitmap_fold - fold larger bitmap into smaller, modulo specified size
1264 	offset = pos - (index * BITS_PER_LONG);  in __reg_op()
1269 	 * Can't do "mask = (1UL << nbitsinlong) - 1", as that  in __reg_op()
1272 	mask = (1UL << (nbitsinlong - 1));  in __reg_op()
1273 	mask += mask - 1;  in __reg_op()
1300  * bitmap_find_free_region - find a contiguous aligned mem region
1311  * or -errno on failure.
1323 	return -ENOMEM;  in bitmap_find_free_region()
1328  * bitmap_release_region - release allocated bitmap region
1345  * bitmap_allocate_region - allocate bitmap region
1352  * Return 0 on success, or %-EBUSY if specified region wasn't
1358 		return -EBUSY;  in bitmap_allocate_region()
1364  * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
1452  * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
1470 		bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);  in bitmap_from_arr32()
1475  * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
1493 		buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));  in bitmap_to_arr32()
1500  * bitmap_from_arr64 - copy the contents of u64 array of bits to bitmap
1509 	for (n = nbits; n > 0; n -= 64) {  in bitmap_from_arr64()
1525 		bitmap[-1] &= BITMAP_LAST_WORD_MASK(nbits);  in bitmap_from_arr64()
1530  * bitmap_to_arr64 - copy the contents of bitmap to a u64 array of bits
1548 		buf[-1] &= GENMASK_ULL((nbits - 1) % 64, 0);  in bitmap_to_arr64()