1 /* 2 * gauche/bits.h - Bit manipulation utilities 3 * 4 * Copyright (c) 2007-2020 Shiro Kawai <shiro@acm.org> 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * 3. Neither the name of the authors nor the names of its contributors 18 * may be used to endorse or promote products derived from this 19 * software without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 #ifndef GAUCHE_BITS_H 35 #define GAUCHE_BITS_H 36 37 /*============================================================ 38 * Bits 39 */ 40 41 /* ScmBits utilities are to manage bit array in an array of u_longs. 42 43 The LSB of the first word is the bit #0. The MSB of the first 44 word is the bit #31 or #63, and the LSB of the second word is the 45 bit #32 or #64, and so on. 46 The user can use ScmBits as opaque structure and don't need to 47 worry about the bit ordering. For internal hackers: ScmBits are 48 also used in bignum.c, and it must maintain this bit ordering. 49 It is important that ScmBignum->values can be casted to ScmBits*. 50 */ 51 52 typedef u_long ScmBits; 53 54 /* Allocates and returns a bitmap that can hold NUMBITS. Zero-cleared. */ 55 SCM_EXTERN ScmBits *Scm_MakeBits(int numbits); 56 57 #define SCM_BITS_NUM_WORDS(size) \ 58 (((size)+SCM_WORD_BITS-1)/SCM_WORD_BITS) 59 60 #define SCM_BITS_TEST_IN_WORD(word, ind_w) (0!=((word) & (1UL<<(ind_w)))) 61 #define SCM_BITS_SET_IN_WORD(word, ind_w) ((word) |= (1UL<<(ind_w))) 62 #define SCM_BITS_RESET_IN_WORD(word, ind_w) ((word) &= ~(1UL<<(ind_w))) 63 64 #define SCM_BITS_TEST(bits, index) \ 65 SCM_BITS_TEST_IN_WORD((bits)[(index)/SCM_WORD_BITS], (index)%SCM_WORD_BITS) 66 67 #define SCM_BITS_SET(bits, index) \ 68 SCM_BITS_SET_IN_WORD((bits)[(index)/SCM_WORD_BITS], (index)%SCM_WORD_BITS) 69 70 #define SCM_BITS_RESET(bits, index) \ 71 SCM_BITS_RESET_IN_WORD((bits)[(index)/SCM_WORD_BITS], (index)%SCM_WORD_BITS) 72 73 /* calculates a mask to extract bits between s (inclusive) and e (exclusive) 74 from a word. e==0 means e is just left of the word (i.e. bits up to 75 the word boundary. Assume 0 <= s < e' <= SCM_WORD_BITS, where e' = e 76 for 1 <= e < SCM_WORD_BITS, and e' = SCM_WORD_BITS if e == 0. */ 77 #define SCM_BITS_MASK(s, e) \ 78 (((e)? (1UL<<(e)) - 1 : (u_long)-1) & ~((1UL<<(s)) - 1)) 79 80 /* works on the range of bits, from start (inclusive) to end (exclusive) */ 81 82 SCM_EXTERN void Scm_BitsFill(ScmBits *bits, int start, int end, int b); 83 84 SCM_EXTERN void Scm_BitsCopyX(ScmBits *target, int tstart, 85 ScmBits *src, int sstart, int send); 86 87 typedef enum { 88 SCM_BIT_AND, /* r = a & b */ 89 SCM_BIT_IOR, /* r = a | b */ 90 SCM_BIT_XOR, /* r = a ^ b */ 91 SCM_BIT_EQV, /* r = ~(a ^ b) */ 92 SCM_BIT_NAND, /* r = ~(a & b) */ 93 SCM_BIT_NOR, /* r = ~(a | b) */ 94 SCM_BIT_ANDC1, /* r = ~a & b */ 95 SCM_BIT_ANDC2, /* r = a & ~b */ 96 SCM_BIT_IORC1, /* r = ~a | b */ 97 SCM_BIT_IORC2, /* r = a | ~b */ 98 SCM_BIT_XORC1, /* r = ~a ^ b */ 99 SCM_BIT_XORC2, /* r = a ^ ~b */ 100 SCM_BIT_SRC1, /* r = a */ 101 SCM_BIT_SRC2, /* r = b */ 102 SCM_BIT_NOT1, /* r = ~a */ 103 SCM_BIT_NOT2, /* r = ~b */ 104 } ScmBitOp; 105 106 SCM_EXTERN void Scm_BitsOperate(ScmBits *r, ScmBitOp op, 107 const ScmBits *a, const ScmBits *b, 108 int start, int end); 109 110 SCM_EXTERN int Scm_BitsEqual(const ScmBits *a, const ScmBits *b, 111 int start, int end); 112 SCM_EXTERN int Scm_BitsIncludes(const ScmBits *a, const ScmBits *b, 113 int start, int end); 114 115 SCM_EXTERN int Scm_BitsCount0(const ScmBits *bits, int start, int end); 116 SCM_EXTERN int Scm_BitsCount1(const ScmBits *bits, int start, int end); 117 118 SCM_EXTERN int Scm_BitsLowest1(const ScmBits *bits, int start, int end); 119 SCM_EXTERN int Scm_BitsLowest0(const ScmBits *bits, int start, int end); 120 SCM_EXTERN int Scm_BitsHighest1(const ScmBits *bits, int start, int end); 121 SCM_EXTERN int Scm_BitsHighest0(const ScmBits *bits, int start, int end); 122 123 #endif /*GAUCHE_BITS_H*/ 124