bsd/sys/bitstring.h

   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_ */