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
67typedef 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