1 | /* |
---|
2 | Copyright (C) 1994-2001 Digitool, Inc |
---|
3 | This file is part of OpenMCL. |
---|
4 | |
---|
5 | OpenMCL is licensed under the terms of the Lisp Lesser GNU Public |
---|
6 | License , known as the LLGPL and distributed with OpenMCL as the |
---|
7 | file "LICENSE". The LLGPL consists of a preamble and the LGPL, |
---|
8 | which is distributed with OpenMCL as the file "LGPL". Where these |
---|
9 | conflict, the preamble takes precedence. |
---|
10 | |
---|
11 | OpenMCL is referenced in the preamble as the "LIBRARY." |
---|
12 | |
---|
13 | The LLGPL is also available online at |
---|
14 | http://opensource.franz.com/preamble.html |
---|
15 | */ |
---|
16 | |
---|
17 | |
---|
18 | |
---|
19 | #ifndef __bits_h__ |
---|
20 | #define __bits_h__ 1 |
---|
21 | |
---|
22 | #include <string.h> |
---|
23 | |
---|
24 | typedef natural *bitvector; |
---|
25 | |
---|
26 | #if WORD_SIZE == 64 |
---|
27 | #define bitmap_shift 6 |
---|
28 | #define BIT0_MASK 0x8000000000000000ULL |
---|
29 | #define ALL_ONES 0xffffffffffffffffULL |
---|
30 | #else |
---|
31 | #define bitmap_shift 5 |
---|
32 | #define BIT0_MASK 0x80000000U |
---|
33 | #define ALL_ONES 0xFFFFFFFFU |
---|
34 | #endif |
---|
35 | |
---|
36 | #define bitmap_shift_count_mask ((1<<bitmap_shift)-1) |
---|
37 | |
---|
38 | static inline int |
---|
39 | set_bit(bitvector bits,natural bitnum) __attribute__((always_inline)); |
---|
40 | |
---|
41 | static inline int |
---|
42 | set_bit(bitvector bits,natural bitnum) |
---|
43 | { |
---|
44 | natural |
---|
45 | windex = bitnum>>bitmap_shift, |
---|
46 | old = bits[windex], |
---|
47 | new = old | (BIT0_MASK >> (bitnum & bitmap_shift_count_mask)); |
---|
48 | if (new == old) { |
---|
49 | return 1; /* Was set */ |
---|
50 | } else { |
---|
51 | bits[windex] = new; |
---|
52 | return 0; /* Was clear */ |
---|
53 | } |
---|
54 | } |
---|
55 | |
---|
56 | static inline int |
---|
57 | atomic_set_bit(bitvector bits ,natural bitnum) |
---|
58 | { |
---|
59 | extern natural atomic_ior(bitvector, natural); |
---|
60 | natural |
---|
61 | windex = bitnum>>bitmap_shift, |
---|
62 | mask = (BIT0_MASK >> (bitnum & bitmap_shift_count_mask)); |
---|
63 | |
---|
64 | return atomic_ior(bits + windex, mask); |
---|
65 | } |
---|
66 | |
---|
67 | void set_n_bits(bitvector,natural,natural); |
---|
68 | |
---|
69 | static inline int |
---|
70 | clr_bit(bitvector bits, natural bitnum) |
---|
71 | { |
---|
72 | unsigned |
---|
73 | windex = bitnum>>bitmap_shift, |
---|
74 | old = bits[windex], |
---|
75 | new = old & ~(BIT0_MASK >> (bitnum & bitmap_shift_count_mask)); |
---|
76 | if (new == old) { |
---|
77 | return 0; /* Was clear */ |
---|
78 | } else { |
---|
79 | bits[windex] = new; |
---|
80 | return 1; /* Was set */ |
---|
81 | } |
---|
82 | } |
---|
83 | |
---|
84 | |
---|
85 | static inline unsigned |
---|
86 | ref_bit(bitvector bits,natural bitnum) __attribute__((always_inline)); |
---|
87 | |
---|
88 | static inline unsigned |
---|
89 | ref_bit(bitvector bits,natural bitnum) |
---|
90 | { |
---|
91 | return ((bits[bitnum>>bitmap_shift] & (BIT0_MASK >> (bitnum & bitmap_shift_count_mask))) != 0); |
---|
92 | } |
---|
93 | |
---|
94 | void zero_bits(bitvector, natural); |
---|
95 | void ior_bits(bitvector,bitvector,natural); |
---|
96 | |
---|
97 | #define bits_word_index(bitnum) (((natural)(bitnum)) >> bitmap_shift) |
---|
98 | #define bits_bit_index(bitnum) (((natural)(bitnum)) & bitmap_shift_count_mask) |
---|
99 | #define bits_word_ptr(bits,bitnum) \ |
---|
100 | ((natural*) (((natural*) bits) + ((natural) (bits_word_index(bitnum))))) |
---|
101 | #define bits_word_mask(bitnum) ((BIT0_MASK) >> bits_bit_index(bitnum)) |
---|
102 | #define bits_indexed_word(bitv,indexw) ((((natural*)(bitv))[indexw])) |
---|
103 | #define bits_word(bitv,bitnum) bits_indexed_word(bits,bits_word_index(bitnum)) |
---|
104 | |
---|
105 | /* Evaluates some arguments twice */ |
---|
106 | |
---|
107 | #define set_bits_vars(BITVvar,BITNUMvar,BITPvar,BITWvar,MASKvar) \ |
---|
108 | { BITPvar = bits_word_ptr(BITVvar,BITNUMvar); BITWvar = *BITPvar; MASKvar = bits_word_mask(BITNUMvar); } |
---|
109 | |
---|
110 | #define set_bitidx_vars(BITVvar,BITNUMvar,BITPvar,BITWvar,BITIDXvar) \ |
---|
111 | { BITPvar = bits_word_ptr(BITVvar,BITNUMvar); BITIDXvar = bits_bit_index(BITNUMvar); \ |
---|
112 | BITWvar = (*BITPvar << BITIDXvar) >> BITIDXvar; } |
---|
113 | |
---|
114 | #ifdef __GNUC__ |
---|
115 | static __inline__ natural |
---|
116 | current_stack_pointer(void) __attribute__((always_inline)); |
---|
117 | |
---|
118 | static __inline__ natural |
---|
119 | current_stack_pointer(void) |
---|
120 | { |
---|
121 | #ifdef PPC |
---|
122 | register natural _sp __asm__("r1"); |
---|
123 | #endif |
---|
124 | #ifdef X8664 |
---|
125 | register natural _sp __asm__("%rsp"); |
---|
126 | #endif |
---|
127 | return _sp; |
---|
128 | } |
---|
129 | #else |
---|
130 | natural |
---|
131 | current_stack_pointer(void); |
---|
132 | #endif |
---|
133 | |
---|
134 | #ifdef __GNUC__ |
---|
135 | static __inline__ unsigned |
---|
136 | count_leading_zeros(natural w) __attribute__((always_inline)); |
---|
137 | |
---|
138 | static __inline__ unsigned |
---|
139 | count_leading_zeros(natural w) |
---|
140 | { |
---|
141 | #if __GNUC__ >= 4 |
---|
142 | #if WORD_SIZE == 64 |
---|
143 | return __builtin_clzll(w); |
---|
144 | #else |
---|
145 | return __builtin_clz(w); |
---|
146 | #endif |
---|
147 | #else /* __GNUC__ < 4 */ |
---|
148 | natural lz; |
---|
149 | #ifdef PPC |
---|
150 | #ifdef PPC64 |
---|
151 | __asm__ ("cntlzd %0,%1" : "=r" (lz) : "r" (w)); |
---|
152 | #else |
---|
153 | __asm__ ("cntlzw %0,%1" : "=r" (lz) : "r" (w)); |
---|
154 | #endif |
---|
155 | #endif /* PPC */ |
---|
156 | #ifdef X86 |
---|
157 | #ifdef X8664 |
---|
158 | __asm__ ("bsr %1,%0" : "=r" (lz) : "r" (w)); |
---|
159 | __asm__ ("xor $63,%0" : "=r" (lz)); |
---|
160 | #else |
---|
161 | __asm__ ("bsr %1,%0" : "=r" (lz) : "r" (w)); |
---|
162 | __asm__ ("xor $31,%0" : "=r" (lz)); |
---|
163 | #endif |
---|
164 | #endif |
---|
165 | return lz; |
---|
166 | #endif |
---|
167 | } |
---|
168 | #else /* not __GNUC__ */ |
---|
169 | unsigned |
---|
170 | count_leading_zeros(natural); |
---|
171 | #endif |
---|
172 | |
---|
173 | #endif /* __bits_h__ */ |
---|