1 /* bits.h -*- mode:c; coding:utf-8; -*-
2 *
3 * Copyright (c) 2010-2021 Takashi Kato <ktakashi@ymail.com>
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
22 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
23 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
24 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * $Id: $
29 */
30 #ifndef SAGITTARIUS_PRIVATE_BITS_H_
31 #define SAGITTARIUS_PRIVATE_BITS_H_
32
33 #include "sagittariusdefs.h"
34
35 #define SG_BITS_MASK(s, e) \
36 (((e) ? (1UL<<(e)) - 1 : -1) & ~((1UL<<(s)) - 1))
37
38
39 #ifndef NO_NLZ
40 /* should these be macro? */
nlz32(uint32_t x)41 static inline int nlz32(uint32_t x)
42 {
43 uint32_t t;
44 int n = 32;
45 t = x >> 16; if (t) { n -= 16 ; x = t; }
46 t = x >> 8; if (t) { n -= 8 ; x = t; }
47 t = x >> 4; if (t) { n -= 4 ; x = t; }
48 t = x >> 2; if (t) { n -= 2 ; x = t; }
49 t = x >> 1; if (t) { return n - 2; }
50 return n - x;
51 }
52
nlz64(uint64_t x)53 static inline int nlz64(uint64_t x)
54 {
55 uint64_t t;
56 int n = 64;
57 t = x >> 32; if (t) { n -= 32 ; x = t; }
58 t = x >> 16; if (t) { n -= 16 ; x = t; }
59 t = x >> 8; if (t) { n -= 8 ; x = t; }
60 t = x >> 4; if (t) { n -= 4 ; x = t; }
61 t = x >> 2; if (t) { n -= 2 ; x = t; }
62 t = x >> 1; if (t) { return n - 2; }
63 return n - (int)x;
64 }
65
nlz(long x)66 static inline int nlz(long x) {
67 if (sizeof(long) == sizeof(uint32_t)) return nlz32((uint32_t)x);
68 return nlz64((uint64_t)x);
69 }
70 #endif
71
72 #if !defined(NO_NBITS) || !defined(NO_NTZ)
nbits32(uint32_t x)73 static inline int nbits32(uint32_t x)
74 {
75 uint32_t t;
76 x = x - ((x >> 1) & 0x55555555);
77 t = ((x >> 2) & 0x33333333);
78 x = (x & 0x33333333) + t;
79 x = (x + (x >> 4)) & 0x0F0F0F0F;
80 x = x * 0x01010101;
81 return x >> 24;
82 }
83
nbits64(uint64_t x)84 static inline int nbits64(uint64_t x)
85 {
86 const uint64_t c1 = 0x5555555555555555LL;
87 const uint64_t c2 = 0x3333333333333333LL;
88 const uint64_t c3 = 0x0F0F0F0F0F0F0F0FLL;
89 const uint64_t c4 = 0x0101010101010101LL;
90 uint64_t t;
91 x = x - ((x >> 1) & c1);
92 t = ((x >> 2) & c2);
93 x = (x & c2) + t;
94 x = (x + (x >> 4)) & c3;
95 x = x * c4;
96 return x >> 56;
97 }
98 #endif
99
100 #ifndef NO_NTZ
ntz32(uint32_t x)101 static inline int ntz32(uint32_t x)
102 {
103 return nbits32(~x & (x - 1));
104 }
105
ntz64(uint64_t x)106 static inline int ntz64(uint64_t x)
107 {
108 return nbits64(~x & (x - 1));
109 }
110
ntz(intptr_t x)111 static inline int ntz(intptr_t x) {
112 if (sizeof(intptr_t) == sizeof(uint32_t)) return ntz32((uint32_t)x);
113 return ntz64((uint64_t)x);
114 }
115 #endif
116
117 #ifndef NO_NBITS
nbits(long x)118 static inline int nbits(long x)
119 {
120 if (sizeof(long) == sizeof(uint32_t)) return nbits32((uint32_t)x);
121 return nbits64((uint64_t)x);
122 }
123 #endif
124
125 SG_CDECL_BEGIN
126
127 SG_EXTERN long Sg_BitsCount0(const unsigned long *bits, long start, long end);
128 SG_EXTERN long Sg_BitsCount1(const unsigned long *bits, long start, long end);
129
130 SG_CDECL_END
131
132 #endif /* SAGITTARIUS_BITS_H_ */
133