Commit | Line | Data |
---|---|---|
920dae64 AT |
1 | /* |
2 | * ========== Copyright Header Begin ========================================== | |
3 | * | |
4 | * OpenSPARC T2 Processor File: rz3_bitarray.h | |
5 | * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved. | |
6 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES. | |
7 | * | |
8 | * The above named program is free software; you can redistribute it and/or | |
9 | * modify it under the terms of the GNU General Public | |
10 | * License version 2 as published by the Free Software Foundation. | |
11 | * | |
12 | * The above named program is distributed in the hope that it will be | |
13 | * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | * General Public License for more details. | |
16 | * | |
17 | * You should have received a copy of the GNU General Public | |
18 | * License along with this work; if not, write to the Free Software | |
19 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. | |
20 | * | |
21 | * ========== Copyright Header End ============================================ | |
22 | */ | |
23 | /* new rz3_bitarray.h | |
24 | * utility code for rstzip3 | |
25 | * | |
26 | * Copyright (C) 2003 Sun Microsystems, Inc. | |
27 | * All Rights Reserved | |
28 | */ | |
29 | ||
30 | ||
31 | #ifndef _rz3_bitarray_h_ | |
32 | #define _rz3_bitarray_h_ | |
33 | ||
34 | #include <stdio.h> | |
35 | #include <sys/types.h> | |
36 | #include <strings.h> | |
37 | ||
38 | #if defined(ARCH_AMD64) | |
39 | #include "rstf/byteswap.h" | |
40 | #endif | |
41 | ||
42 | // set this to 1 for debugging - outputs every update to each bitarray | |
43 | const int rz3_bitarray_debug = 0; | |
44 | ||
45 | // class rz3_bitarray_base { | |
46 | class rz3_bitarray { | |
47 | public: | |
48 | ||
49 | // rz3_bitarray_base(const char * arg_name, int arg_nbits, int size_hint) { | |
50 | rz3_bitarray(const char * arg_name, int arg_nbits, int size_hint) { | |
51 | name = strdup(arg_name); | |
52 | ||
53 | elemsize = arg_nbits; | |
54 | ||
55 | elem_mask = (~0ull) >> (64-elemsize); | |
56 | ||
57 | maxcount = 0; | |
58 | u64 = NULL; | |
59 | ||
60 | int desired_count; | |
61 | if (size_hint) { | |
62 | desired_count = size_hint; | |
63 | } else { | |
64 | desired_count = (1024*64/elemsize); | |
65 | } | |
66 | ||
67 | reallocate(desired_count); | |
68 | ||
69 | clear(); | |
70 | ||
71 | straddle = ((64%elemsize) != 0); | |
72 | } | |
73 | ||
74 | ||
75 | // ~rz3_bitarray_base() { | |
76 | ~rz3_bitarray() { | |
77 | if(u64 != NULL) { | |
78 | delete [] u64; | |
79 | } | |
80 | free(name); | |
81 | } | |
82 | ||
83 | virtual void clear() { | |
84 | count = 0; | |
85 | nextidx = 0; | |
86 | sum = 0; | |
87 | nbits = 0; | |
88 | } | |
89 | ||
90 | virtual void Push(uint64_t data_nbits) { | |
91 | data_nbits &= elem_mask; | |
92 | ||
93 | if (rz3_bitarray_debug) { printf("rz3_bitarray %s [%d] <= %llx\n", name, count, data_nbits); fflush(stdout); } | |
94 | ||
95 | if (count >= maxcount) { // we havent written u64[count] yet. cannot write if count>=maxcount | |
96 | reallocate(count+1); | |
97 | } | |
98 | ||
99 | int u64idx = nbits/64; | |
100 | int offs = nbits%64; | |
101 | if (straddle && ((64-offs) < elemsize)) { | |
102 | // low-order bits | |
103 | int lbits = (64-offs); | |
104 | uint64_t lmask = (1ull << lbits) - 1; | |
105 | uint64_t lowbits = data_nbits & lmask; | |
106 | u64[u64idx] &= ~(lmask << offs); | |
107 | u64[u64idx] |= (lowbits << offs); | |
108 | u64[u64idx+1] = data_nbits >> lbits; | |
109 | } else { | |
110 | u64[u64idx] &= ~(elem_mask << offs); | |
111 | u64[u64idx] |= (data_nbits << offs); | |
112 | } | |
113 | count++; | |
114 | nbits += elemsize; | |
115 | sum += data_nbits; | |
116 | } | |
117 | ||
118 | ||
119 | virtual bool Get(int key, uint64_t & value) | |
120 | { | |
121 | if (key >= count) { | |
122 | if (rz3_bitarray_debug) fprintf(stderr, "rz3_bitarray %s: Error: Get(%d) - count is %d\n", name, key, count); | |
123 | return false; | |
124 | } | |
125 | ||
126 | value = 0x0; | |
127 | int u64idx = (key*elemsize)/64; | |
128 | int offs = (key*elemsize)%64; | |
129 | if (straddle && ((offs+elemsize)>64)) { | |
130 | int hbits = (offs+elemsize)-64; | |
131 | int lbits = elemsize-hbits; | |
132 | value = u64[u64idx] >> offs; | |
133 | uint64_t hmask = (1ull << hbits)-1; | |
134 | uint64_t hval = u64[u64idx+1] & hmask; | |
135 | value |= (hval << lbits); | |
136 | } else { | |
137 | value = (u64[u64idx] >> offs) & elem_mask; | |
138 | } | |
139 | return true; | |
140 | } | |
141 | ||
142 | // GetNext() is a stateful function that returns elements in the order they were inserted | |
143 | virtual bool GetNext(uint64_t & value) | |
144 | { | |
145 | bool rv = Get(nextidx, value); | |
146 | if (rz3_bitarray_debug) { printf("rz3_bitarray %s [%d] <= %llx\n", name, nextidx, value); fflush(stdout); } | |
147 | nextidx++; | |
148 | return rv; | |
149 | } | |
150 | ||
151 | virtual int Count() { | |
152 | return count; | |
153 | } | |
154 | ||
155 | virtual uint64_t ComputeMemBufSize(int n_elements) | |
156 | { | |
157 | int n_u64 = (n_elements * elemsize + 63)/64; | |
158 | return n_u64 * sizeof(uint64_t); | |
159 | } | |
160 | ||
161 | virtual uint64_t GetMemBufSize() { | |
162 | return ComputeMemBufSize(count); | |
163 | } | |
164 | ||
165 | virtual uint64_t CopyTo(unsigned char * membuf) | |
166 | { | |
167 | int n_u64 = (nbits+63)/64; | |
168 | uint64_t sz = n_u64*sizeof(uint64_t); | |
169 | #if defined(ARCH_AMD64) | |
170 | for (int i=0; i<n_u64; i++) { | |
171 | u64[i] = byteswap64(u64[i]); | |
172 | } | |
173 | #endif | |
174 | memcpy(membuf, u64, sz); | |
175 | return sz; | |
176 | } | |
177 | ||
178 | virtual uint64_t CopyFrom(unsigned char * membuf, int arg_count) | |
179 | { | |
180 | if (arg_count > maxcount) { | |
181 | reallocate(arg_count); | |
182 | } | |
183 | count = arg_count; | |
184 | nbits = count * elemsize; | |
185 | int n_u64 = (nbits + 63)/64; | |
186 | int sz = n_u64 * sizeof(uint64_t); | |
187 | memcpy(u64, membuf, sz); | |
188 | #if defined(ARCH_AMD64) | |
189 | for (int i=0; i<n_u64; i++) { | |
190 | u64[i] = byteswap64(u64[i]); | |
191 | } | |
192 | #endif | |
193 | return sz; | |
194 | } | |
195 | ||
196 | // GetSum only returns a valid value if elements are Push()'ed. Not if the are CopyFrom()'ed. | |
197 | virtual uint64_t GetSum() { | |
198 | return sum; | |
199 | } | |
200 | ||
201 | ||
202 | protected: | |
203 | ||
204 | void reallocate(int desired_size) { | |
205 | if (desired_size <= maxcount) return; | |
206 | ||
207 | if (desired_size < (2*maxcount)) { | |
208 | desired_size = 2*maxcount; | |
209 | } | |
210 | ||
211 | int new_u64_count = (desired_size * elemsize + 63)/64; | |
212 | uint64_t * new_u64 = new uint64_t [new_u64_count]; | |
213 | if (u64 != NULL) { | |
214 | memcpy(new_u64, u64, u64_count*sizeof(uint64_t)); | |
215 | delete [] u64; | |
216 | } | |
217 | ||
218 | u64 = new_u64; | |
219 | u64_count = new_u64_count; | |
220 | ||
221 | maxcount = desired_size; | |
222 | ||
223 | } | |
224 | ||
225 | char * name; | |
226 | ||
227 | int elemsize; | |
228 | uint64_t elem_mask; | |
229 | ||
230 | int count; // count of valid elements in the array | |
231 | int maxcount; // the most number of elements that can exist in the array | |
232 | ||
233 | int nbits; | |
234 | ||
235 | int nextidx; | |
236 | ||
237 | int u64_count; | |
238 | ||
239 | uint64_t * u64; | |
240 | ||
241 | uint64_t sum; | |
242 | ||
243 | bool straddle; | |
244 | ||
245 | }; // class rz3_bitarray_base | |
246 | ||
247 | ||
248 | #if 0 | |
249 | ||
250 | // the rz3_bitarray is a space-efficient way to | |
251 | // maintain lists of items whose size is not necessarily 8/16/32/64 bits. | |
252 | // We try to balance memory usage and speed requirements. | |
253 | // To this end, we implement 2 types of bit-arrays: fixed and growable. | |
254 | // Fixed arrays are fast but can waste space. | |
255 | // Growable arrays allocate space only as required | |
256 | ||
257 | class rz3_bitarray { | |
258 | public: | |
259 | // nbits is the size of the array element. Must be <= 64 | |
260 | rz3_bitarray(const char * arg_name, int nbits, int size_hint) | |
261 | { | |
262 | impl = new rz3_bitarray_base(arg_name, nbits, size_hint); | |
263 | } | |
264 | ||
265 | ~rz3_bitarray() { | |
266 | delete impl; | |
267 | } | |
268 | ||
269 | void clear() { | |
270 | impl->clear(); | |
271 | } | |
272 | ||
273 | void Push(uint64_t data_nbits) { | |
274 | impl->Push(data_nbits); | |
275 | } | |
276 | ||
277 | bool Get(int key, uint64_t & value) { | |
278 | return impl->Get(key, value); | |
279 | } | |
280 | ||
281 | // GetNext() is a stateful function that returns elements in the order they were inserted | |
282 | bool GetNext(uint64_t & value) | |
283 | { | |
284 | return impl->GetNext(value); | |
285 | } | |
286 | ||
287 | ||
288 | int Count() { | |
289 | return impl->Count(); | |
290 | } | |
291 | ||
292 | ||
293 | uint64_t ComputeMemBufSize(int n_elements) { | |
294 | return impl->ComputeMemBufSize(n_elements); | |
295 | } | |
296 | ||
297 | ||
298 | uint64_t GetMemBufSize() { | |
299 | return impl->GetMemBufSize(); | |
300 | } | |
301 | ||
302 | ||
303 | uint64_t CopyTo(unsigned char * membuf) { | |
304 | return impl->CopyTo(membuf); | |
305 | } | |
306 | ||
307 | ||
308 | uint64_t CopyFrom(unsigned char * membuf, int arg_count) { | |
309 | return impl->CopyFrom(membuf, arg_count); | |
310 | } | |
311 | ||
312 | uint64_t GetSum() { | |
313 | return impl->GetSum(); | |
314 | } | |
315 | ||
316 | protected: | |
317 | rz3_bitarray_base * impl; | |
318 | }; // class rz3_bitarray | |
319 | ||
320 | #endif | |
321 | ||
322 | ||
323 | #endif // _rz3_bitarray_h_ |