1 /* $NetBSD: bitmap.h,v 1.8 2018/08/27 14:52:16 riastradh Exp $ */ 2 3 /*- 4 * Copyright (c) 2018 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_BITMAP_H_ 33 #define _LINUX_BITMAP_H_ 34 35 #include <sys/param.h> 36 #include <sys/types.h> 37 #include <sys/systm.h> 38 39 /* 40 * bitmap_zero(bitmap, nbits) 41 * 42 * Zero a bitmap that was allocated to have nbits bits. Yes, this 43 * zeros bits past nbits. 44 */ 45 static inline void 46 bitmap_zero(unsigned long *bitmap, size_t nbits) 47 { 48 const size_t bpl = NBBY * sizeof(*bitmap); 49 size_t n = howmany(nbits, bpl); 50 51 memset(bitmap, 0, n * sizeof(*bitmap)); 52 } 53 54 /* 55 * bitmap_empty(bitmap, nbits) 56 * 57 * Return true if all bits at 0, 1, 2, ..., nbits-2, nbits-1 are 58 * 0, or false if any of them is 1. 59 */ 60 static inline bool 61 bitmap_empty(const unsigned long *bitmap, size_t nbits) 62 { 63 const size_t bpl = NBBY * sizeof(*bitmap); 64 65 for (; nbits >= bpl; nbits -= bpl) { 66 if (*bitmap++) 67 return false; 68 } 69 70 if (nbits) { 71 if (*bitmap & ~(~0UL << nbits)) 72 return false; 73 } 74 75 return true; 76 } 77 78 /* 79 * bitmap_weight(bitmap, nbits) 80 * 81 * Compute the number of 1 bits at 0, 1, 2, ..., nbits-2, nbits-1. 82 */ 83 static inline int 84 bitmap_weight(const unsigned long *bitmap, size_t nbits) 85 { 86 const size_t bpl = NBBY * sizeof(*bitmap); 87 int weight = 0; 88 89 for (; nbits >= bpl; nbits -= bpl) 90 weight += popcountl(*bitmap++); 91 if (nbits) 92 weight += popcountl(*bitmap & ~(~0UL << nbits)); 93 94 return weight; 95 } 96 97 /* 98 * bitmap_set(bitmap, startbit, nbits) 99 * 100 * Set bits at startbit, startbit+1, ..., startbit+nbits-2, 101 * startbit+nbits-1 to 1. 102 */ 103 static inline void 104 bitmap_set(unsigned long *bitmap, size_t startbit, size_t nbits) 105 { 106 const size_t bpl = NBBY * sizeof(*bitmap); 107 unsigned long *p = bitmap + startbit/bpl; 108 unsigned initial = startbit%bpl; 109 110 /* Handle an initial odd word if any. */ 111 if (initial) { 112 /* Does the whole thing fit in a single word? */ 113 if (nbits <= bpl - initial) { 114 /* Yes: just set nbits starting at initial. */ 115 *p |= ~(~0ULL << nbits) << initial; 116 return; 117 } 118 /* Nope: set all bits above initial, and advance. */ 119 *p++ |= ~0ULL << initial; 120 nbits -= bpl - initial; 121 } 122 123 /* Set the middle part to all bits 1. */ 124 for (; nbits >= bpl; nbits -= bpl) 125 *p++ = ~0UL; 126 127 /* Handle a final odd word if any by setting its low nbits. */ 128 if (nbits) 129 *p |= ~(~0ULL << nbits); 130 } 131 132 /* 133 * bitmap_clear(bitmap, startbit, nbits) 134 * 135 * Clear bits at startbit, startbit+1, ..., startbit+nbits-2, 136 * startbit+nbits-1, replacing them by 0. 137 */ 138 static inline void 139 bitmap_clear(unsigned long *bitmap, size_t startbit, size_t nbits) 140 { 141 const size_t bpl = NBBY * sizeof(*bitmap); 142 unsigned long *p = bitmap + startbit/bpl; 143 unsigned initial = startbit%bpl; 144 145 /* Handle an initial odd word if any. */ 146 if (initial) { 147 /* Does the whole thing fit in a single word? */ 148 if (nbits <= bpl - initial) { 149 /* Yes: just clear nbits starting at initial. */ 150 *p &= ~(~(~0ULL << nbits) << initial); 151 return; 152 } 153 /* Nope: clear all bits above initial, and advance. */ 154 *p++ &= ~(~0ULL << initial); 155 nbits -= bpl - initial; 156 } 157 158 /* Zero the middle part. */ 159 for (; nbits >= bpl; nbits -= bpl) 160 *p++ = 0UL; 161 162 /* Handle a final odd word if any by clearing its low nbits. */ 163 if (nbits) 164 *p &= ~0ULL << nbits; 165 } 166 167 /* 168 * bitmap_and(dst, src1, src2, nbits) 169 * 170 * Set dst to be the bitwise AND of src1 and src2, all bitmaps 171 * allocated to have nbits bits. Yes, this modifies bits past 172 * nbits. Any pair of {dst, src1, src2} may be aliases. 173 */ 174 static inline void 175 bitmap_and(unsigned long *dst, const unsigned long *src1, 176 const unsigned long *src2, size_t nbits) 177 { 178 const size_t bpl = NBBY * sizeof(unsigned long); 179 size_t n = howmany(nbits, bpl); 180 181 while (n --> 0) 182 *dst++ = *src1++ & *src2++; 183 } 184 185 /* 186 * bitmap_or(dst, src1, src2, nbits) 187 * 188 * Set dst to be the bitwise inclusive-OR of src1 and src2, all 189 * bitmaps allocated to have nbits bits. Yes, this modifies bits 190 * past nbits. Any pair of {dst, src1, src2} may be aliases. 191 */ 192 static inline void 193 bitmap_or(unsigned long *dst, const unsigned long *src1, 194 const unsigned long *src2, size_t nbits) 195 { 196 const size_t bpl = NBBY * sizeof(unsigned long); 197 size_t n = howmany(nbits, bpl); 198 199 while (n --> 0) 200 *dst++ = *src1++ | *src2++; 201 } 202 203 #endif /* _LINUX_BITMAP_H_ */ 204