1 /* $NetBSD: bitops.h,v 1.8 2018/08/27 14:46:23 riastradh 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_TO_LONGS(n) \ 106 roundup2((n), (sizeof(unsigned long) * CHAR_BIT)) 107 108 #define BIT(n) ((uintmax_t)1 << (n)) 109 #define GENMASK(h,l) __BITS(h,l) 110 111 static inline int 112 test_bit(unsigned int n, const volatile unsigned long *p) 113 { 114 const unsigned units = (sizeof(unsigned long) * CHAR_BIT); 115 116 return ((p[n / units] & (1UL << (n % units))) != 0); 117 } 118 119 static inline void 120 __set_bit(unsigned int n, volatile unsigned long *p) 121 { 122 const unsigned units = (sizeof(unsigned long) * CHAR_BIT); 123 124 p[n / units] |= (1UL << (n % units)); 125 } 126 127 static inline void 128 __clear_bit(unsigned int n, volatile unsigned long *p) 129 { 130 const unsigned units = (sizeof(unsigned long) * CHAR_BIT); 131 132 p[n / units] &= ~(1UL << (n % units)); 133 } 134 135 static inline void 136 __change_bit(unsigned int n, volatile unsigned long *p) 137 { 138 const unsigned units = (sizeof(unsigned long) * CHAR_BIT); 139 140 p[n / units] ^= (1UL << (n % units)); 141 } 142 143 static inline unsigned long 144 __test_and_set_bit(unsigned int bit, volatile unsigned long *ptr) 145 { 146 const unsigned int units = (sizeof(*ptr) * CHAR_BIT); 147 volatile unsigned long *const p = &ptr[bit / units]; 148 const unsigned long mask = (1UL << (bit % units)); 149 unsigned long v; 150 151 v = *p; 152 *p |= mask; 153 154 return ((v & mask) != 0); 155 } 156 157 static inline unsigned long 158 __test_and_clear_bit(unsigned int bit, volatile unsigned long *ptr) 159 { 160 const unsigned int units = (sizeof(*ptr) * CHAR_BIT); 161 volatile unsigned long *const p = &ptr[bit / units]; 162 const unsigned long mask = (1UL << (bit % units)); 163 unsigned long v; 164 165 v = *p; 166 *p &= ~mask; 167 168 return ((v & mask) != 0); 169 } 170 171 static inline unsigned long 172 __test_and_change_bit(unsigned int bit, volatile unsigned long *ptr) 173 { 174 const unsigned int units = (sizeof(*ptr) * CHAR_BIT); 175 volatile unsigned long *const p = &ptr[bit / units]; 176 const unsigned long mask = (1UL << (bit % units)); 177 unsigned long v; 178 179 v = *p; 180 *p ^= mask; 181 182 return ((v & mask) != 0); 183 } 184 185 static inline unsigned long 186 __find_next_bit(const unsigned long *ptr, unsigned long nbits, 187 unsigned long startbit, unsigned long toggle) 188 { 189 const size_t bpl = (CHAR_BIT * sizeof(*ptr)); 190 const unsigned long *p = ptr + startbit/bpl; 191 size_t n = howmany(nbits, bpl); 192 unsigned long result; 193 uint64_t word; 194 195 /* 196 * We use ffs64 because NetBSD doesn't have a handy ffsl that 197 * works on unsigned long. This is a waste on 32-bit systems 198 * but I'd rather not maintain multiple copies of this -- the 199 * first version had enough bugs already. 200 */ 201 202 /* Do we need to examine a partial starting word? */ 203 if (startbit % bpl) { 204 /* Toggle the bits and convert to 64 bits for ffs64. */ 205 word = *p ^ toggle; 206 207 /* Clear the low startbit%bpl bits. */ 208 word &= (~0UL << (startbit % bpl)); 209 210 /* Are any of these bits set now? */ 211 if (word) 212 goto out; 213 214 /* Move past it. */ 215 p++; 216 n--; 217 } 218 219 /* Find the first word with any bits set. */ 220 for (; n --> 0; p++) { 221 /* Toggle the bits and convert to 64 bits for ffs64. */ 222 word = *p ^ toggle; 223 224 /* Are any of these bits set now? */ 225 if (word) 226 goto out; 227 } 228 229 /* Nada. */ 230 return nbits; 231 232 out: 233 /* Count how many words we've skipped. */ 234 result = bpl*(p - ptr); 235 236 /* Find the first set bit in this word, zero-based. */ 237 result += ffs64(word) - 1; 238 239 /* We may have overshot, so clamp down to at most nbits. */ 240 return MIN(result, nbits); 241 } 242 243 static inline unsigned long 244 find_next_bit(const unsigned long *ptr, unsigned long nbits, 245 unsigned long startbit) 246 { 247 return __find_next_bit(ptr, nbits, startbit, 0); 248 } 249 250 static inline unsigned long 251 find_first_bit(const unsigned long *ptr, unsigned long nbits) 252 { 253 return find_next_bit(ptr, nbits, 0); 254 } 255 256 static inline unsigned long 257 find_next_zero_bit(const unsigned long *ptr, unsigned long nbits, 258 unsigned long startbit) 259 { 260 return __find_next_bit(ptr, nbits, startbit, ~0UL); 261 } 262 263 static inline unsigned long 264 find_first_zero_bit(const unsigned long *ptr, unsigned long nbits) 265 { 266 return find_next_zero_bit(ptr, nbits, 0); 267 } 268 269 #define for_each_set_bit(BIT, PTR, NBITS) \ 270 for ((BIT) = find_first_bit((PTR), (NBITS)); \ 271 (BIT) < (NBITS); \ 272 (BIT) = find_next_bit((PTR), (NBITS), (BIT) + 1)) 273 274 #endif /* _LINUX_BITOPS_H_ */ 275