1 /* 2 * Copyright (c) 1989 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Paul Vixie. 7 * 8 * Redistribution and use in source and binary forms are permitted 9 * provided that the above copyright notice and this paragraph are 10 * duplicated in all such forms and that any documentation, 11 * advertising materials, and other materials related to such 12 * distribution and use acknowledge that the software was developed 13 * by the University of California, Berkeley. The name of the 14 * University may not be used to endorse or promote products derived 15 * from this software without specific prior written permission. 16 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 17 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 19 * 20 * @(#)bitstring.h 5.3 (Berkeley) 05/30/90 21 */ 22 23 typedef unsigned char bitstr_t; 24 25 /* internal macros */ 26 /* byte of the bitstring bit is in */ 27 #define _bit_byte(bit) \ 28 ((bit) >> 3) 29 30 /* mask for the bit within its byte */ 31 #define _bit_mask(bit) \ 32 (1 << ((bit)&0x7)) 33 34 /* external macros */ 35 /* bytes in a bitstring of nbits bits */ 36 #define bitstr_size(nbits) \ 37 ((((nbits) - 1) >> 3) + 1) 38 39 /* allocate a bitstring */ 40 #define bit_alloc(nbits) \ 41 (bitstr_t *)calloc(1, \ 42 (unsigned int)_bitstr_size(nbits) * sizeof(bitstr_t)) 43 44 /* allocate a bitstring on the stack */ 45 #define bit_decl(name, nbits) \ 46 (name)[bitstr_size(nbits)] 47 48 /* is bit N of bitstring name set? */ 49 #define bit_test(name, bit) \ 50 ((name)[_bit_byte(bit)] & _bit_mask(bit)) 51 52 /* set bit N of bitstring name */ 53 #define bit_set(name, bit) \ 54 (name)[_bit_byte(bit)] |= _bit_mask(bit) 55 56 /* clear bit N of bitstring name */ 57 #define bit_clear(name, bit) \ 58 (name)[_bit_byte(bit)] &= ~_bit_mask(bit) 59 60 /* clear bits start ... stop in bitstring */ 61 #define bit_nclear(name, start, stop) { \ 62 register bitstr_t *_name = name; \ 63 register int _start = start, _stop = stop; \ 64 register int _startbyte = _bit_byte(_start); \ 65 register int _stopbyte = _bit_byte(_stop); \ 66 _name[_startbyte] &= 0xff >> (8 - (_start&0x7)); \ 67 while (++_startbyte < _stopbyte) \ 68 _name[_startbyte] = 0; \ 69 _name[_stopbyte] &= 0xff << ((_stop&0x7) + 1); \ 70 } 71 72 /* set bits start ... stop in bitstring */ 73 #define bit_nset(name, start, stop) { \ 74 register bitstr_t *_name = name; \ 75 register int _start = start, _stop = stop; \ 76 register int _startbyte = _bit_byte(_start); \ 77 register int _stopbyte = _bit_byte(_stop); \ 78 _name[_startbyte] |= 0xff << ((start)&0x7); \ 79 while (++_startbyte < _stopbyte) \ 80 _name[_startbyte] = 0xff; \ 81 _name[_stopbyte] |= 0xff >> (7 - (_stop&0x7)); \ 82 } 83 84 /* find first bit clear in name */ 85 #define bit_ffc(name, nbits, value) { \ 86 register bitstr_t *_name = name; \ 87 register int _byte, _nbits = nbits; \ 88 register int _stopbyte = _bit_byte(_nbits), _value = -1; \ 89 for (_byte = 0; _byte <= _stopbyte; ++_byte) \ 90 if (_name[_byte] != 0xff) { \ 91 _value = _byte << 3; \ 92 for (_stopbyte = _name[_byte]; (_stopbyte&0x1); \ 93 ++_value, _stopbyte >>= 1); \ 94 break; \ 95 } \ 96 *(value) = _value; \ 97 } 98 99 /* find first bit set in name */ 100 #define bit_ffs(name, nbits, value) { \ 101 register bitstr_t *_name = name; \ 102 register int _byte, _nbits = nbits; \ 103 register int _stopbyte = _bit_byte(_nbits), _value = -1; \ 104 for (_byte = 0; _byte <= _stopbyte; ++_byte) \ 105 if (_name[_byte]) { \ 106 _value = _byte << 3; \ 107 for (_stopbyte = _name[_byte]; !(_stopbyte&0x1); \ 108 ++_value, _stopbyte >>= 1); \ 109 break; \ 110 } \ 111 *(value) = _value; \ 112 } 113