Home | History | Annotate | Line # | Download | only in linux
bitops.h revision 1.4 
      1 /*	$NetBSD: bitops.h,v 1.4 2018/08/27 07:04:32 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 hweight16(uint16_t n)
     77 {
     78 	return popcount32(n);
     79 }
     80 
     81 static inline unsigned int
     82 hweight32(uint32_t n)
     83 {
     84 	return popcount32(n);
     85 }
     86 
     87 static inline unsigned int
     88 hweight64(uint64_t n)
     89 {
     90 	return popcount64(n);
     91 }
     92 
     93 /*
     94  * XXX Don't define BITS_PER_LONG as sizeof(unsigned long)*CHAR_BIT
     95  * because that won't work in preprocessor conditionals, where it often
     96  * turns up.
     97  */
     98 
     99 #define	BITS_TO_LONGS(n)						\
    100 	roundup2((n), (sizeof(unsigned long) * CHAR_BIT))
    101 
    102 #define	BIT(n)	((uintmax_t)1 << (n))
    103 #define	GENMASK(h,l)	__BITS(h,l)
    104 
    105 static inline int
    106 test_bit(unsigned int n, const volatile unsigned long *p)
    107 {
    108 	const unsigned units = (sizeof(unsigned long) * CHAR_BIT);
    109 
    110 	return ((p[n / units] & (1UL << (n % units))) != 0);
    111 }
    112 
    113 static inline void
    114 __set_bit(unsigned int n, volatile unsigned long *p)
    115 {
    116 	const unsigned units = (sizeof(unsigned long) * CHAR_BIT);
    117 
    118 	p[n / units] |= (1UL << (n % units));
    119 }
    120 
    121 static inline void
    122 __clear_bit(unsigned int n, volatile unsigned long *p)
    123 {
    124 	const unsigned units = (sizeof(unsigned long) * CHAR_BIT);
    125 
    126 	p[n / units] &= ~(1UL << (n % units));
    127 }
    128 
    129 static inline void
    130 __change_bit(unsigned int n, volatile unsigned long *p)
    131 {
    132 	const unsigned units = (sizeof(unsigned long) * CHAR_BIT);
    133 
    134 	p[n / units] ^= (1UL << (n % units));
    135 }
    136 
    137 static inline unsigned long
    138 __test_and_set_bit(unsigned int bit, volatile unsigned long *ptr)
    139 {
    140 	const unsigned int units = (sizeof(*ptr) * CHAR_BIT);
    141 	volatile unsigned long *const p = &ptr[bit / units];
    142 	const unsigned long mask = (1UL << (bit % units));
    143 	unsigned long v;
    144 
    145 	v = *p;
    146 	*p |= mask;
    147 
    148 	return ((v & mask) != 0);
    149 }
    150 
    151 static inline unsigned long
    152 __test_and_clear_bit(unsigned int bit, volatile unsigned long *ptr)
    153 {
    154 	const unsigned int units = (sizeof(*ptr) * CHAR_BIT);
    155 	volatile unsigned long *const p = &ptr[bit / units];
    156 	const unsigned long mask = (1UL << (bit % units));
    157 	unsigned long v;
    158 
    159 	v = *p;
    160 	*p &= ~mask;
    161 
    162 	return ((v & mask) != 0);
    163 }
    164 
    165 static inline unsigned long
    166 __test_and_change_bit(unsigned int bit, volatile unsigned long *ptr)
    167 {
    168 	const unsigned int units = (sizeof(*ptr) * CHAR_BIT);
    169 	volatile unsigned long *const p = &ptr[bit / units];
    170 	const unsigned long mask = (1UL << (bit % units));
    171 	unsigned long v;
    172 
    173 	v = *p;
    174 	*p ^= mask;
    175 
    176 	return ((v & mask) != 0);
    177 }
    178 
    179 static inline unsigned long
    180 find_first_zero_bit(const unsigned long *ptr, unsigned long nbits)
    181 {
    182 	const size_t bpl = (CHAR_BIT * sizeof(*ptr));
    183 	const unsigned long *p;
    184 	unsigned long result = 0;
    185 
    186 	for (p = ptr; bpl < nbits; nbits -= bpl, p++, result += bpl) {
    187 		if (~*p)
    188 			break;
    189 	}
    190 
    191 	CTASSERT(sizeof(unsigned long) <= sizeof(uint64_t));
    192 	result += ffs64(~(uint64_t)*p | (~0UL << MIN(nbits, bpl)));
    193 	return result;
    194 }
    195 
    196 static inline unsigned
    197 hweight8(unsigned w)
    198 {
    199 
    200 	return popcount(w & 0xff);
    201 }
    202 
    203 #endif  /* _LINUX_BITOPS_H_ */
    204