1 /* $NetBSD: bitops.h,v 1.9 2019/12/05 20:03:09 maya Exp $ */ 2 3 /*- 4 * Copyright (c) 2013 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Taylor R. Campbell. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #ifndef _LINUX_BITOPS_H_ 33 #define _LINUX_BITOPS_H_ 34 35 #include <sys/cdefs.h> 36 #include <sys/types.h> 37 #include <sys/param.h> 38 #include <sys/atomic.h> 39 #include <sys/bitops.h> 40 41 #include <machine/limits.h> 42 43 #include <lib/libkern/libkern.h> 44 45 /* 46 * Linux __ffs/__ffs64 is zero-based; zero input is undefined. Our 47 * ffs/ffs64 is one-based; zero input yields zero. 48 */ 49 static inline unsigned long 50 __ffs(unsigned long x) 51 { 52 53 KASSERT(x != 0); 54 return ffs64(x) - 1; 55 } 56 57 static inline unsigned long 58 __ffs64(uint64_t x) 59 { 60 61 KASSERT(x != 0); 62 return ffs64(x) - 1; 63 } 64 65 /* 66 * Linux fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32, so it matches 67 * our fls semantics. 68 */ 69 static inline int 70 fls(int x) 71 { 72 return fls32(x); 73 } 74 75 static inline unsigned int 76 hweight8(uint8_t w) 77 { 78 return popcount(w & 0xff); 79 } 80 81 static inline unsigned int 82 hweight16(uint16_t n) 83 { 84 return popcount32(n); 85 } 86 87 static inline unsigned int 88 hweight32(uint32_t n) 89 { 90 return popcount32(n); 91 } 92 93 static inline unsigned int 94 hweight64(uint64_t n) 95 { 96 return popcount64(n); 97 } 98 99 /* 100 * XXX Don't define BITS_PER_LONG as sizeof(unsigned long)*CHAR_BIT 101 * because that won't work in preprocessor conditionals, where it often 102 * turns up. 103 */ 104 105 #define BITS_PER_BYTE 8 106 #define BITS_TO_LONGS(n) \ 107 roundup2((n), (sizeof(unsigned long) * CHAR_BIT)) 108 109 #define BIT(n) ((uintmax_t)1 << (n)) 110 #define GENMASK(h,l) __BITS(h,l) 111 112 static inline int 113 test_bit(unsigned int n, const volatile unsigned long *p) 114 { 115 const unsigned units = (sizeof(unsigned long) * CHAR_BIT); 116 117 return ((p[n / units] & (1UL << (n % units))) != 0); 118 } 119 120 static inline void 121 __set_bit(unsigned int n, volatile unsigned long *p) 122 { 123 const unsigned units = (sizeof(unsigned long) * CHAR_BIT); 124 125 p[n / units] |= (1UL << (n % units)); 126 } 127 128 static inline void 129 __clear_bit(unsigned int n, volatile unsigned long *p) 130 { 131 const unsigned units = (sizeof(unsigned long) * CHAR_BIT); 132 133 p[n / units] &= ~(1UL << (n % units)); 134 } 135 136 static inline void 137 __change_bit(unsigned int n, volatile unsigned long *p) 138 { 139 const unsigned units = (sizeof(unsigned long) * CHAR_BIT); 140 141 p[n / units] ^= (1UL << (n % units)); 142 } 143 144 static inline unsigned long 145 __test_and_set_bit(unsigned int bit, volatile unsigned long *ptr) 146 { 147 const unsigned int units = (sizeof(*ptr) * CHAR_BIT); 148 volatile unsigned long *const p = &ptr[bit / units]; 149 const unsigned long mask = (1UL << (bit % units)); 150 unsigned long v; 151 152 v = *p; 153 *p |= mask; 154 155 return ((v & mask) != 0); 156 } 157 158 static inline unsigned long 159 __test_and_clear_bit(unsigned int bit, volatile unsigned long *ptr) 160 { 161 const unsigned int units = (sizeof(*ptr) * CHAR_BIT); 162 volatile unsigned long *const p = &ptr[bit / units]; 163 const unsigned long mask = (1UL << (bit % units)); 164 unsigned long v; 165 166 v = *p; 167 *p &= ~mask; 168 169 return ((v & mask) != 0); 170 } 171 172 static inline unsigned long 173 __test_and_change_bit(unsigned int bit, volatile unsigned long *ptr) 174 { 175 const unsigned int units = (sizeof(*ptr) * CHAR_BIT); 176 volatile unsigned long *const p = &ptr[bit / units]; 177 const unsigned long mask = (1UL << (bit % units)); 178 unsigned long v; 179 180 v = *p; 181 *p ^= mask; 182 183 return ((v & mask) != 0); 184 } 185 186 static inline unsigned long 187 __find_next_bit(const unsigned long *ptr, unsigned long nbits, 188 unsigned long startbit, unsigned long toggle) 189 { 190 const size_t bpl = (CHAR_BIT * sizeof(*ptr)); 191 const unsigned long *p = ptr + startbit/bpl; 192 size_t n = howmany(nbits, bpl); 193 unsigned long result; 194 uint64_t word; 195 196 /* 197 * We use ffs64 because NetBSD doesn't have a handy ffsl that 198 * works on unsigned long. This is a waste on 32-bit systems 199 * but I'd rather not maintain multiple copies of this -- the 200 * first version had enough bugs already. 201 */ 202 203 /* Do we need to examine a partial starting word? */ 204 if (startbit % bpl) { 205 /* Toggle the bits and convert to 64 bits for ffs64. */ 206 word = *p ^ toggle; 207 208 /* Clear the low startbit%bpl bits. */ 209 word &= (~0UL << (startbit % bpl)); 210 211 /* Are any of these bits set now? */ 212 if (word) 213 goto out; 214 215 /* Move past it. */ 216 p++; 217 n--; 218 } 219 220 /* Find the first word with any bits set. */ 221 for (; n --> 0; p++) { 222 /* Toggle the bits and convert to 64 bits for ffs64. */ 223 word = *p ^ toggle; 224 225 /* Are any of these bits set now? */ 226 if (word) 227 goto out; 228 } 229 230 /* Nada. */ 231 return nbits; 232 233 out: 234 /* Count how many words we've skipped. */ 235 result = bpl*(p - ptr); 236 237 /* Find the first set bit in this word, zero-based. */ 238 result += ffs64(word) - 1; 239 240 /* We may have overshot, so clamp down to at most nbits. */ 241 return MIN(result, nbits); 242 } 243 244 static inline unsigned long 245 find_next_bit(const unsigned long *ptr, unsigned long nbits, 246 unsigned long startbit) 247 { 248 return __find_next_bit(ptr, nbits, startbit, 0); 249 } 250 251 static inline unsigned long 252 find_first_bit(const unsigned long *ptr, unsigned long nbits) 253 { 254 return find_next_bit(ptr, nbits, 0); 255 } 256 257 static inline unsigned long 258 find_next_zero_bit(const unsigned long *ptr, unsigned long nbits, 259 unsigned long startbit) 260 { 261 return __find_next_bit(ptr, nbits, startbit, ~0UL); 262 } 263 264 static inline unsigned long 265 find_first_zero_bit(const unsigned long *ptr, unsigned long nbits) 266 { 267 return find_next_zero_bit(ptr, nbits, 0); 268 } 269 270 #define for_each_set_bit(BIT, PTR, NBITS) \ 271 for ((BIT) = find_first_bit((PTR), (NBITS)); \ 272 (BIT) < (NBITS); \ 273 (BIT) = find_next_bit((PTR), (NBITS), (BIT) + 1)) 274 275 #endif /* _LINUX_BITOPS_H_ */ 276