1 | /* |
2 | * Copyright (c) 2013-2016 Apple Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | |
29 | /*- |
30 | * Copyright (c) 1989, 1993 |
31 | * The Regents of the University of California. All rights reserved. |
32 | * |
33 | * This code is derived from software contributed to Berkeley by |
34 | * Paul Vixie. |
35 | * |
36 | * Redistribution and use in source and binary forms, with or without |
37 | * modification, are permitted provided that the following conditions |
38 | * are met: |
39 | * 1. Redistributions of source code must retain the above copyright |
40 | * notice, this list of conditions and the following disclaimer. |
41 | * 2. Redistributions in binary form must reproduce the above copyright |
42 | * notice, this list of conditions and the following disclaimer in the |
43 | * documentation and/or other materials provided with the distribution. |
44 | * 4. Neither the name of the University nor the names of its contributors |
45 | * may be used to endorse or promote products derived from this software |
46 | * without specific prior written permission. |
47 | * |
48 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
49 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
50 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
51 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
52 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
53 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
54 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
55 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
56 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
57 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
58 | * SUCH DAMAGE. |
59 | */ |
60 | |
61 | #ifndef _SYS_BITSTRING_H_ |
62 | #define _SYS_BITSTRING_H_ |
63 | |
64 | #ifdef XNU_KERNEL_PRIVATE |
65 | #include <sys/mcache.h> |
66 | |
67 | typedef uint8_t bitstr_t; |
68 | |
69 | /* internal macros */ |
70 | /* byte of the bitstring bit is in */ |
71 | #define _bitstr_byte(bit) \ |
72 | ((bit) >> 3) |
73 | |
74 | /* mask for the bit within its byte */ |
75 | #define _bitstr_mask(bit) \ |
76 | (1 << ((bit) & 0x7)) |
77 | |
78 | /* external macros */ |
79 | /* bytes in a bitstring of nbits bits */ |
80 | #define bitstr_size(nbits) \ |
81 | (((nbits) + 7) >> 3) |
82 | |
83 | /* allocate a bitstring on the stack */ |
84 | #define bit_decl(name, nbits) \ |
85 | ((name)[bitstr_size(nbits)]) |
86 | |
87 | /* is bit N of bitstring name set? */ |
88 | #define bitstr_test(name, bit) \ |
89 | ((name)[_bitstr_byte(bit)] & _bitstr_mask(bit)) |
90 | |
91 | /* set bit N of bitstring name */ |
92 | #define bitstr_set(name, bit) \ |
93 | ((name)[_bitstr_byte(bit)] |= _bitstr_mask(bit)) |
94 | |
95 | /* set bit N of bitstring name (atomic) */ |
96 | #define bitstr_set_atomic(name, bit) \ |
97 | (void)os_atomic_or(&((name)[_bitstr_byte(bit)]), _bitstr_mask(bit), relaxed) |
98 | |
99 | /* clear bit N of bitstring name */ |
100 | #define bitstr_clear(name, bit) \ |
101 | ((name)[_bitstr_byte(bit)] &= ~_bitstr_mask(bit)) |
102 | |
103 | /* clear bit N of bitstring name (atomic) */ |
104 | #define bitstr_clear_atomic(name, bit) \ |
105 | (void)os_atomic_andnot(&((name)[_bitstr_byte(bit)]), _bitstr_mask(bit), relaxed) |
106 | |
107 | /* clear bits start ... stop in bitstring */ |
108 | #define bitstr_nclear(name, start, stop) do { \ |
109 | bitstr_t *_name = (name); \ |
110 | int _start = (start), _stop = (stop); \ |
111 | int _startbyte = _bitstr_byte(_start); \ |
112 | int _stopbyte = _bitstr_byte(_stop); \ |
113 | if (_startbyte == _stopbyte) { \ |
114 | _name[_startbyte] &= ((0xff >> (8 - (_start & 0x7))) | \ |
115 | (0xff << ((_stop & 0x7) + 1))); \ |
116 | } else { \ |
117 | _name[_startbyte] &= 0xff >> (8 - (_start & 0x7)); \ |
118 | while (++_startbyte < _stopbyte) \ |
119 | _name[_startbyte] = 0; \ |
120 | _name[_stopbyte] &= 0xff << ((_stop & 0x7) + 1); \ |
121 | } \ |
122 | } while (0) |
123 | |
124 | /* set bits start ... stop in bitstring */ |
125 | #define bitstr_nset(name, start, stop) do { \ |
126 | bitstr_t *_name = (name); \ |
127 | int _start = (start), _stop = (stop); \ |
128 | int _startbyte = _bitstr_byte(_start); \ |
129 | int _stopbyte = _bitstr_byte(_stop); \ |
130 | if (_startbyte == _stopbyte) { \ |
131 | _name[_startbyte] |= ((0xff << (_start & 0x7)) & \ |
132 | (0xff >> (7 - (_stop & 0x7)))); \ |
133 | } else { \ |
134 | _name[_startbyte] |= 0xff << ((_start) & 0x7); \ |
135 | while (++_startbyte < _stopbyte) \ |
136 | _name[_startbyte] = 0xff; \ |
137 | _name[_stopbyte] |= 0xff >> (7 - (_stop & 0x7)); \ |
138 | } \ |
139 | } while (0) |
140 | |
141 | /* find first bit clear in name */ |
142 | #define bitstr_ffc(name, nbits, value) do { \ |
143 | bitstr_t *_name = (name); \ |
144 | int _byte, _nbits = (nbits); \ |
145 | int _stopbyte = _bitstr_byte(_nbits - 1), _value = -1; \ |
146 | if (_nbits > 0) \ |
147 | for (_byte = 0; _byte <= _stopbyte; ++_byte) \ |
148 | if (_name[_byte] != 0xff) { \ |
149 | bitstr_t _lb; \ |
150 | _value = _byte << 3; \ |
151 | for (_lb = _name[_byte]; (_lb & 0x1); \ |
152 | ++_value, _lb >>= 1); \ |
153 | break; \ |
154 | } \ |
155 | if (_value >= nbits) \ |
156 | _value = -1; \ |
157 | *(value) = _value; \ |
158 | } while (0) |
159 | |
160 | /* find first bit set in name */ |
161 | #define bitstr_ffs(name, nbits, value) do { \ |
162 | bitstr_t *_name = (name); \ |
163 | int _byte, _nbits = (nbits); \ |
164 | int _stopbyte = _bitstr_byte(_nbits - 1), _value = -1; \ |
165 | if (_nbits > 0) \ |
166 | for (_byte = 0; _byte <= _stopbyte; ++_byte) \ |
167 | if (_name[_byte]) { \ |
168 | bitstr_t _lb; \ |
169 | _value = _byte << 3; \ |
170 | for (_lb = _name[_byte]; !(_lb & 0x1); \ |
171 | ++_value, _lb >>= 1); \ |
172 | break; \ |
173 | } \ |
174 | if (_value >= nbits) \ |
175 | _value = -1; \ |
176 | *(value) = _value; \ |
177 | } while (0) |
178 | |
179 | #endif /* XNU_KERNEL_PRIVATE */ |
180 | #endif /* !_SYS_BITSTRING_H_ */ |
181 | |