jcs.org
jcs's openbsd hax
openbsd
1/* $OpenBSD: bitmap.h,v 1.9 2025/09/09 10:11:41 jsg 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
27static inline void
28bitmap_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
36static inline void
37bitmap_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
45static inline void
46bitmap_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
55static inline void
56bitmap_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
65static inline void
66bitmap_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
77static inline void
78bitmap_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
89static inline void
90bitmap_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
100static inline bool
101bitmap_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
117static inline void
118bitmap_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
128static inline void
129bitmap_to_arr32(void *d, const unsigned long *src, u_int n)
130{
131 u_int *dst = d;
132#ifdef __LP64__
133 u_int b;
134
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
148static inline void
149bitmap_from_arr32(unsigned long *dst, const void *s, u_int n)
150{
151#ifdef __LP64__
152 const u_int *src = s;
153 u_int b;
154
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
170static inline int
171bitmap_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
182static inline int
183bitmap_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
195static inline void
196bitmap_release_region(void *p, u_int b, int o)
197{
198 KASSERT(o == 0);
199 __clear_bit(b, p);
200}
201
202void *bitmap_zalloc(u_int, gfp_t);
203void bitmap_free(void *);
204
205#endif