1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* bit search implementation 3 * 4 * Copied from lib/find_bit.c to tools/lib/find_bit.c 5 * 6 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. 7 * Written by David Howells (dhowells@redhat.com) 8 * 9 * Copyright (C) 2008 IBM Corporation 10 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au> 11 * (Inspired by David Howell's find_next_bit implementation) 12 * 13 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease 14 * size and improve performance, 2015. 15 */ 16 17 #include <linux/bitops.h> 18 #include <linux/bitmap.h> 19 #include <linux/kernel.h> 20 21 #if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ 22 !defined(find_next_and_bit) 23 24 /* 25 * This is a common helper function for find_next_bit, find_next_zero_bit, and 26 * find_next_and_bit. The differences are: 27 * - The "invert" argument, which is XORed with each fetched word before 28 * searching it for one bits. 29 * - The optional "addr2", which is anded with "addr1" if present. 30 */ 31 unsigned long _find_next_bit(const unsigned long *addr1, 32 const unsigned long *addr2, unsigned long nbits, 33 unsigned long start, unsigned long invert, unsigned long le) 34 { 35 unsigned long tmp, mask; 36 (void) le; 37 38 if (unlikely(start >= nbits)) 39 return nbits; 40 41 tmp = addr1[start / BITS_PER_LONG]; 42 if (addr2) 43 tmp &= addr2[start / BITS_PER_LONG]; 44 tmp ^= invert; 45 46 /* Handle 1st word. */ 47 mask = BITMAP_FIRST_WORD_MASK(start); 48 49 /* 50 * Due to the lack of swab() in tools, and the fact that it doesn't 51 * need little-endian support, just comment it out 52 */ 53 #if (0) 54 if (le) 55 mask = swab(mask); 56 #endif 57 58 tmp &= mask; 59 60 start = round_down(start, BITS_PER_LONG); 61 62 while (!tmp) { 63 start += BITS_PER_LONG; 64 if (start >= nbits) 65 return nbits; 66 67 tmp = addr1[start / BITS_PER_LONG]; 68 if (addr2) 69 tmp &= addr2[start / BITS_PER_LONG]; 70 tmp ^= invert; 71 } 72 73 #if (0) 74 if (le) 75 tmp = swab(tmp); 76 #endif 77 78 return min(start + __ffs(tmp), nbits); 79 } 80 #endif 81 82 #ifndef find_first_bit 83 /* 84 * Find the first set bit in a memory region. 85 */ 86 unsigned long _find_first_bit(const unsigned long *addr, unsigned long size) 87 { 88 unsigned long idx; 89 90 for (idx = 0; idx * BITS_PER_LONG < size; idx++) { 91 if (addr[idx]) 92 return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); 93 } 94 95 return size; 96 } 97 #endif 98 99 #ifndef find_first_and_bit 100 /* 101 * Find the first set bit in two memory regions. 102 */ 103 unsigned long _find_first_and_bit(const unsigned long *addr1, 104 const unsigned long *addr2, 105 unsigned long size) 106 { 107 unsigned long idx, val; 108 109 for (idx = 0; idx * BITS_PER_LONG < size; idx++) { 110 val = addr1[idx] & addr2[idx]; 111 if (val) 112 return min(idx * BITS_PER_LONG + __ffs(val), size); 113 } 114 115 return size; 116 } 117 #endif 118 119 #ifndef find_first_zero_bit 120 /* 121 * Find the first cleared bit in a memory region. 122 */ 123 unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size) 124 { 125 unsigned long idx; 126 127 for (idx = 0; idx * BITS_PER_LONG < size; idx++) { 128 if (addr[idx] != ~0UL) 129 return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); 130 } 131 132 return size; 133 } 134 #endif 135