1 /* $OpenBSD: bitmap.h,v 1.8 2024/03/20 22:52:44 bluhm Exp $ */ 2 /* 3 * Copyright (c) 2013, 2014, 2015 Mark Kettenis 4 * 5 * Permission to use, copy, modify, and distribute this software for any 6 * purpose with or without fee is hereby granted, provided that the above 7 * copyright notice and this permission notice appear in all copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18 #ifndef _LINUX_BITMAP_H 19 #define _LINUX_BITMAP_H 20 21 #include <linux/align.h> 22 #include <linux/bitops.h> 23 #include <linux/string.h> 24 25 #define bitmap_empty(p, n) (find_first_bit(p, n) == n) 26 27 static inline void 28 bitmap_set(void *p, int b, u_int n) 29 { 30 u_int end = b + n; 31 32 for (; b < end; b++) 33 __set_bit(b, p); 34 } 35 36 static inline void 37 bitmap_clear(void *p, int b, u_int n) 38 { 39 u_int end = b + n; 40 41 for (; b < end; b++) 42 __clear_bit(b, p); 43 } 44 45 static inline void 46 bitmap_zero(void *p, u_int n) 47 { 48 u_int *ptr = p; 49 u_int b; 50 51 for (b = 0; b < n; b += 32) 52 ptr[b >> 5] = 0; 53 } 54 55 static inline void 56 bitmap_fill(void *p, u_int n) 57 { 58 u_int *ptr = p; 59 u_int b; 60 61 for (b = 0; b < n; b += 32) 62 ptr[b >> 5] = 0xffffffff; 63 } 64 65 static inline void 66 bitmap_or(void *d, void *s1, void *s2, u_int n) 67 { 68 u_int *dst = d; 69 u_int *src1 = s1; 70 u_int *src2 = s2; 71 u_int b; 72 73 for (b = 0; b < n; b += 32) 74 dst[b >> 5] = src1[b >> 5] | src2[b >> 5]; 75 } 76 77 static inline void 78 bitmap_andnot(void *d, void *s1, void *s2, u_int n) 79 { 80 u_int *dst = d; 81 u_int *src1 = s1; 82 u_int *src2 = s2; 83 u_int b; 84 85 for (b = 0; b < n; b += 32) 86 dst[b >> 5] = src1[b >> 5] & ~src2[b >> 5]; 87 } 88 89 static inline void 90 bitmap_complement(void *d, void *s, u_int n) 91 { 92 u_int *dst = d; 93 u_int *src = s; 94 u_int b; 95 96 for (b = 0; b < n; b += 32) 97 dst[b >> 5] = ~src[b >> 5]; 98 } 99 100 static inline bool 101 bitmap_intersects(const void *s1, const void *s2, u_int n) 102 { 103 const u_int *b1 = s1; 104 const u_int *b2 = s2; 105 u_int b; 106 107 for (b = 0; b < n; b += 32) 108 if (b1[b >> 5] & b2[b >> 5]) 109 return true; 110 if ((n % 32) != 0) 111 if ((b1[n >> 5] & b2[b >> 5]) & (0xffffffff >> (32 - (n % 32)))) 112 return true; 113 114 return false; 115 } 116 117 static inline void 118 bitmap_copy(void *d, const void *s, u_int n) 119 { 120 u_int *dst = d; 121 const u_int *src = s; 122 u_int b; 123 124 for (b = 0; b < n; b += 32) 125 dst[b >> 5] = src[b >> 5]; 126 } 127 128 static inline void 129 bitmap_to_arr32(void *d, const unsigned long *src, u_int n) 130 { 131 u_int *dst = d; 132 u_int b; 133 134 #ifdef __LP64__ 135 for (b = 0; b < n; b += 32) { 136 dst[b >> 5] = src[b >> 6] & 0xffffffff; 137 b += 32; 138 if (b < n) 139 dst[b >> 5] = src[b >> 6] >> 32; 140 } 141 #else 142 bitmap_copy(d, src, n); 143 #endif 144 if ((n % 32) != 0) 145 dst[n >> 5] &= (0xffffffff >> (32 - (n % 32))); 146 } 147 148 static inline void 149 bitmap_from_arr32(unsigned long *dst, const void *s, u_int n) 150 { 151 const u_int *src = s; 152 u_int b; 153 154 #ifdef __LP64__ 155 for (b = 0; b < n; b += 32) { 156 dst[b >> 6] = src[b >> 5]; 157 b += 32; 158 if (b < n) 159 dst[b >> 6] |= ((unsigned long)src[b >> 5]) << 32; 160 } 161 if ((n % 64) != 0) 162 dst[n >> 6] &= (0xffffffffffffffffUL >> (64 - (n % 64))); 163 #else 164 bitmap_copy(dst, s, n); 165 if ((n % 32) != 0) 166 dst[n >> 5] &= (0xffffffff >> (32 - (n % 32))); 167 #endif 168 } 169 170 static inline int 171 bitmap_weight(const void *p, u_int n) 172 { 173 const u_int *ptr = p; 174 u_int b; 175 int sum = 0; 176 177 for (b = 0; b < n; b += 32) 178 sum += hweight32(ptr[b >> 5]); 179 return sum; 180 } 181 182 static inline int 183 bitmap_find_free_region(void *p, u_int n, int o) 184 { 185 int b; 186 187 KASSERT(o == 0); 188 b = find_first_zero_bit(p, n); 189 if (b == n) 190 return -ENOMEM; 191 __set_bit(b, p); 192 return b; 193 } 194 195 static inline void 196 bitmap_release_region(void *p, u_int b, int o) 197 { 198 KASSERT(o == 0); 199 __clear_bit(b, p); 200 } 201 202 void *bitmap_zalloc(u_int, gfp_t); 203 void bitmap_free(void *); 204 205 #endif 206