1/*	$NetBSD: bitstring.h,v 1.14 2016/03/17 02:25:32 christos Exp $	*/
  2
  3/*
  4 * Copyright (c) 1989, 1993
  5 *	The Regents of the University of California.  All rights reserved.
  6 *
  7 * This code is derived from software contributed to Berkeley by
  8 * Paul Vixie.
  9 *
 10 * Redistribution and use in source and binary forms, with or without
 11 * modification, are permitted provided that the following conditions
 12 * are met:
 13 * 1. Redistributions of source code must retain the above copyright
 14 *    notice, this list of conditions and the following disclaimer.
 15 * 2. Redistributions in binary form must reproduce the above copyright
 16 *    notice, this list of conditions and the following disclaimer in the
 17 *    documentation and/or other materials provided with the distribution.
 18 * 3. Neither the name of the University nor the names of its contributors
 19 *    may be used to endorse or promote products derived from this software
 20 *    without specific prior written permission.
 21 *
 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 25 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 32 * SUCH DAMAGE.
 33 *
 34 *	@(#)bitstring.h	8.1 (Berkeley) 7/19/93
 35 */
 36
 37#ifndef _BITSTRING_H_
 38#define	_BITSTRING_H_
 39
 40/* modified for SV/AT and bitstring bugfix by M.R.Murphy, 11oct91
 41 * bitstr_size changed gratuitously, but shorter
 42 * bit_alloc   spelling error fixed
 43 * the following were efficient, but didn't work, they've been made to
 44 * work, but are no longer as efficient :-)
 45 * bit_nclear, bit_nset, bit_ffc, bit_ffs
 46 */
 47/*
 48 * The comment above may or may not bear any resemblance to reality.
 49 * This code has been maintained in a confusing way, with little
 50 * information available on the provenance of much of it. "At least it
 51 * works."
 52 *  /s/ Perry E. Metzger, 2 Feb 98
 53 */
 54typedef	unsigned char bitstr_t;
 55
 56/* internal macros */
 57				/* byte of the bitstring bit is in */
 58#define	_bit_byte(bit) \
 59	(uint32_t)((bit) >> 3)
 60
 61				/* mask for the bit within its byte */
 62#define	_bit_mask(bit) \
 63	(uint32_t)((1 << (uint32_t)((bit)&0x7)))
 64
 65/* external macros */
 66				/* bytes in a bitstring of nbits bits */
 67#define	bitstr_size(nbits) \
 68	(size_t)((uint32_t)((nbits) + 7) >> 3)
 69
 70				/* allocate a bitstring */
 71#define	bit_alloc(nbits) \
 72	calloc(bitstr_size(nbits), sizeof(bitstr_t))
 73
 74				/* allocate a bitstring on the stack */
 75#define	bit_decl(name, nbits) \
 76	((name)[bitstr_size(nbits)])
 77
 78				/* is bit N of bitstring name set? */
 79#define	bit_test(name, bit) \
 80	/*LINTED bitwise on signed*/((name)[_bit_byte(bit)] & _bit_mask(bit))
 81
 82				/* set bit N of bitstring name */
 83#define	bit_set(name, bit) \
 84	/*LINTED bitwise on signed*/ \
 85	((name)[_bit_byte(bit)] = \
 86	(unsigned char)(_bit_mask(bit) | (name)[_bit_byte(bit)]))
 87
 88				/* clear bit N of bitstring name */
 89#define	bit_clear(name, bit) \
 90	/*LINTED bitwise on signed*/ \
 91	((name)[_bit_byte(bit)] &= (unsigned char)~_bit_mask(bit))
 92
 93				/* clear bits start ... stop in bitstring */
 94#define	bit_nclear(name, start, stop) do { \
 95	bitstr_t *_name = name; \
 96	size_t _start = start, _stop = stop; \
 97	while (_start <= _stop) { \
 98		bit_clear(_name, _start); \
 99		_start++; \
100	} \
101} while(/*CONSTCOND*/0)
102
103				/* set bits start ... stop in bitstring */
104#define	bit_nset(name, start, stop) do { \
105	bitstr_t *_name = name; \
106	size_t _start = start, _stop = stop; \
107	while (_start <= _stop) { \
108		bit_set(_name, _start); \
109		_start++; \
110	} \
111} while(/*CONSTCOND*/0)
112
113				/* find first bit clear in name */
114#define	bit_ffc(name, nbits, value) do { \
115	const bitstr_t *_name = name; \
116	size_t _bit, _nbits = nbits; \
117	int _value = -1; \
118	for (_bit = 0; _bit < _nbits; ++_bit) \
119		if (!bit_test(_name, _bit)) { \
120			_value = _bit; \
121			break; \
122		} \
123	*(value) = _value; \
124} while(/*CONSTCOND*/0)
125
126				/* find first bit set in name */
127#define	bit_ffs(name, nbits, value) do { \
128	const bitstr_t *_name = name; \
129	size_t _bit, _nbits = nbits; \
130	int _value = -1; \
131	for (_bit = 0; _bit < _nbits; ++_bit) \
132		if (bit_test(_name, _bit)) { \
133			_value = _bit; \
134			break; \
135		} \
136	*(value) = _value; \
137} while(/*CONSTCOND*/0)
138
139#endif /* !_BITSTRING_H_ */