Commit | Line | Data |
---|---|---|
920dae64 AT |
1 | /* |
2 | * ========== Copyright Header Begin ========================================== | |
3 | * | |
4 | * OpenSPARC T2 Processor File: rz3_bitarray.v3.14b.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 | /* rz3_bitarray.h | |
24 | * utility code for rstzip3 | |
25 | * | |
26 | * Copyright (C) 2003 Sun Microsystems, Inc. | |
27 | * All Rights Reserved | |
28 | */ | |
29 | ||
30 | #ifndef _rz3_bitarray_h_ | |
31 | #define _rz3_bitarray_h_ | |
32 | ||
33 | #include <stdio.h> | |
34 | #include <sys/types.h> | |
35 | #include <strings.h> | |
36 | ||
37 | #define rz3_bitarray_debug 0 | |
38 | ||
39 | // the rz3_bitarray is a space-efficient way to | |
40 | // maintain lists of items whose size is not necessarily 8/16/32/64 bits. | |
41 | // Access time is kept low by allocating a static array of size <maxsize_hint>. | |
42 | // Exceeding this size involves memory reallocation() which may slow things down | |
43 | // It is cheaper to specify a large maxsize_hint than to reallocate memory | |
44 | struct rz3_bitarray { | |
45 | ||
46 | enum consts_e { u64_per_line = 128 }; | |
47 | ||
48 | // nbits is the size of the array element. Must be <= 64 | |
49 | rz3_bitarray(const char * arg_name, int nbits, int maxsize_hint) { | |
50 | if (nbits > 64) { | |
51 | fprintf(stderr, "ERROR: rz3_bitarray: nbits cannot be > 64. Specified = %d\n", nbits); | |
52 | exit(1); | |
53 | } | |
54 | ||
55 | name = strdup(arg_name); | |
56 | ||
57 | elemsize = nbits; | |
58 | ||
59 | elems_per_line = u64_per_line*64/elemsize; | |
60 | ||
61 | elem_mask = (~0ull) >> (64-elemsize); | |
62 | ||
63 | can_straddle = ((64 % elemsize) != 0); | |
64 | ||
65 | if (maxsize_hint == 0) { | |
66 | nlines = 1; | |
67 | } else { | |
68 | nlines = (maxsize_hint + elems_per_line - 1)/elems_per_line; | |
69 | } | |
70 | ||
71 | lines = new uint64_t * [nlines]; | |
72 | int i; | |
73 | for (i=0; i<nlines; i++) { | |
74 | lines[i] = NULL; | |
75 | } | |
76 | ||
77 | count = 0; | |
78 | nextidx = 0; | |
79 | ||
80 | sum = 0; | |
81 | } | |
82 | ||
83 | ~rz3_bitarray() { | |
84 | int i; | |
85 | for (i=0; i<nlines; i++) { | |
86 | if (lines[i] != NULL) { | |
87 | delete [] lines[i]; | |
88 | lines[i] = NULL; | |
89 | } | |
90 | } | |
91 | delete [] lines; | |
92 | free(name); | |
93 | } | |
94 | ||
95 | void clear() { | |
96 | count = 0; | |
97 | nextidx = 0; | |
98 | sum = 0; | |
99 | } | |
100 | ||
101 | void Push(uint64_t data_nbits) { | |
102 | data_nbits &= elem_mask; // zero-out upper bits of local copy of input arg | |
103 | ||
104 | if (rz3_bitarray_debug) { printf("rz3_bitarray %s [%d] <= %llx\n", name, count, data_nbits); fflush(stdout); } | |
105 | ||
106 | sum += data_nbits; | |
107 | ||
108 | // printf("rz3_bitarray::Push: count %d data %llx\n", count, data_nbits); | |
109 | int idx = count / elems_per_line; | |
110 | if (idx >= nlines) { | |
111 | // realloc lines | |
112 | nlines = (nlines + 1) * 1.5; | |
113 | uint64_t* * newlines = new uint64_t* [nlines]; | |
114 | int i; | |
115 | for (i=0; i<idx; i++) { | |
116 | newlines[i] = lines[i]; | |
117 | } | |
118 | for(i=idx; i<nlines; i++) { | |
119 | newlines[i] = NULL; | |
120 | } | |
121 | delete [] lines; | |
122 | lines = newlines; | |
123 | } | |
124 | if(lines[idx] == NULL) { | |
125 | lines[idx] = new uint64_t[u64_per_line]; | |
126 | } // add new line | |
127 | ||
128 | int offset = count % elems_per_line; | |
129 | int u64_idx = (offset * elemsize) >> 6; | |
130 | int u64_offset = (offset * elemsize) & 0x3f; | |
131 | if (can_straddle && ((u64_offset + elemsize) > 64)) { | |
132 | // low-order bits | |
133 | int lbits = (64-u64_offset); | |
134 | uint64_t lmask = (1ull << lbits) - 1; | |
135 | uint64_t lowbits = data_nbits & lmask; | |
136 | lines[idx][u64_idx] &= ~(lmask << u64_offset); | |
137 | lines[idx][u64_idx] |= (lowbits << u64_offset); | |
138 | lines[idx][u64_idx+1] = data_nbits >> lbits; | |
139 | // printf(" lines[%d][%d] = %016llx, lines[%d][%d] = %016llx\n", idx, u64_idx, lines[idx][u64_idx], idx, u64_idx+1, lines[idx][u64_idx+1]); | |
140 | } else { | |
141 | lines[idx][u64_idx] &= ~(elem_mask << u64_offset); // zero out elem bits | |
142 | lines[idx][u64_idx] |= (data_nbits << u64_offset); | |
143 | // printf(" lines[%d][%d] = %016llx\n", idx, u64_idx, lines[idx][u64_idx]); | |
144 | } | |
145 | count++; | |
146 | } // Push() | |
147 | ||
148 | bool Get(int key, uint64_t & value) { | |
149 | if (key >= count) { | |
150 | return false; | |
151 | } | |
152 | ||
153 | value = 0x0; | |
154 | int idx = key/elems_per_line; | |
155 | int offset = key % elems_per_line; | |
156 | int u64_idx = (offset * elemsize) >> 6; | |
157 | int u64_offset = (offset * elemsize) & 0x3f; | |
158 | ||
159 | if (can_straddle && ((u64_offset+elemsize) > 64)) { | |
160 | int lbits = 64-u64_offset; | |
161 | value = lines[idx][u64_idx] >> u64_offset; | |
162 | int hbits = (u64_offset+elemsize-64); | |
163 | uint64_t hmask = (1ull << hbits) - 1; | |
164 | uint64_t hval = (lines[idx][u64_idx+1] & hmask); | |
165 | value |= (hval << lbits); | |
166 | } else { | |
167 | value = (lines[idx][u64_idx] >> u64_offset) & elem_mask; | |
168 | } | |
169 | ||
170 | return true; | |
171 | } | |
172 | ||
173 | // GetNext() is a stateful function that returns elements in the order they were inserted | |
174 | bool GetNext(uint64_t & value) | |
175 | { | |
176 | bool rv = Get(nextidx, value); | |
177 | if (rz3_bitarray_debug) { printf("rz3_bitarray %s [%d] <= %llx\n", name, nextidx, value); fflush(stdout); } | |
178 | nextidx++; | |
179 | return rv; | |
180 | } | |
181 | ||
182 | int Count() { | |
183 | return count; | |
184 | } | |
185 | ||
186 | uint64_t ComputeMemBufSize(int n_elements) { | |
187 | uint64_t full_lines = (n_elements/elems_per_line); | |
188 | uint64_t partial_line_bits = (n_elements % elems_per_line) * elemsize; | |
189 | uint64_t partial_line_u64_count = (partial_line_bits + 63)/64; | |
190 | return (full_lines * u64_per_line + partial_line_u64_count) * sizeof(uint64_t); | |
191 | } | |
192 | ||
193 | uint64_t GetMemBufSize() { | |
194 | return ComputeMemBufSize(count); | |
195 | } | |
196 | ||
197 | ||
198 | // returns number of bytes copied out - should be equal to SizeInBytes() | |
199 | uint64_t CopyTo(unsigned char * membuf) { | |
200 | int full_lines = (count/elems_per_line); | |
201 | int partial_line_bits = (count % elems_per_line) * elemsize; | |
202 | int partial_line_u64_count = (partial_line_bits + 63)/64; | |
203 | int i; | |
204 | uint64_t bytes_copied = 0; | |
205 | // copy full lines | |
206 | int full_line_size = u64_per_line * sizeof(uint64_t); | |
207 | for (i=0; i<full_lines; i++) { | |
208 | memcpy(membuf+bytes_copied, lines[i], full_line_size); | |
209 | bytes_copied += full_line_size; | |
210 | } | |
211 | ||
212 | // copy partial line | |
213 | memcpy(membuf+bytes_copied, lines[i], partial_line_u64_count*sizeof(uint64_t)); | |
214 | bytes_copied += (partial_line_u64_count * sizeof(uint64_t)); | |
215 | return bytes_copied; | |
216 | } | |
217 | ||
218 | // returns number of bytes copied in - should be equal to GetMemBufSIze() | |
219 | uint64_t CopyFrom(unsigned char * membuf, int arg_count) { | |
220 | ||
221 | count = arg_count; | |
222 | ||
223 | int full_lines = (count/elems_per_line); | |
224 | int partial_line_bits = (count % elems_per_line) * elemsize; | |
225 | int partial_line_u64_count = (partial_line_bits + 63)/64; | |
226 | ||
227 | int i; | |
228 | ||
229 | // do we have enough lines available? | |
230 | int lines_needed = full_lines; | |
231 | if (partial_line_u64_count) { | |
232 | lines_needed++; | |
233 | } | |
234 | ||
235 | if (lines_needed > nlines) { | |
236 | // allocate more line pointers. 1.5X current count or needed count, whichever larger | |
237 | int new_nlines = (nlines+1)*1.5; | |
238 | if (lines_needed > new_nlines) { | |
239 | new_nlines = lines_needed; | |
240 | } | |
241 | ||
242 | uint64_t ** newlines = new uint64_t * [new_nlines]; | |
243 | ||
244 | // copy over <nlines> pointers> | |
245 | memcpy(newlines, lines, nlines * sizeof(uint64_t *)); | |
246 | ||
247 | // zero pointers past nlines | |
248 | bzero(newlines+nlines, (new_nlines-nlines)*sizeof(uint64_t *)); | |
249 | ||
250 | nlines = new_nlines; | |
251 | delete [] lines; | |
252 | lines = newlines; | |
253 | } | |
254 | ||
255 | uint64_t bytes_copied = 0; | |
256 | for (i=0; i<full_lines; i++) { | |
257 | if (lines[i] == NULL) { | |
258 | lines[i] = new uint64_t [u64_per_line]; | |
259 | } | |
260 | int nbytes = u64_per_line*sizeof(uint64_t); | |
261 | memcpy(lines[i], membuf+bytes_copied, nbytes); | |
262 | bytes_copied += nbytes; | |
263 | } | |
264 | ||
265 | // partial line | |
266 | if (partial_line_u64_count) { | |
267 | if (lines[i] == NULL) { | |
268 | lines[i] = new uint64_t [u64_per_line]; | |
269 | } | |
270 | int nbytes = partial_line_u64_count*sizeof(uint64_t); | |
271 | memcpy(lines[i], membuf+bytes_copied, nbytes); | |
272 | bytes_copied += nbytes; | |
273 | } | |
274 | ||
275 | return bytes_copied; | |
276 | } // CopyFrom() | |
277 | ||
278 | ||
279 | uint64_t GetSum() { | |
280 | return sum; | |
281 | } | |
282 | ||
283 | char * name; | |
284 | int elemsize; | |
285 | int elems_per_line; | |
286 | uint64_t elem_mask; // shift u64 then AND with this mask to extract element | |
287 | ||
288 | bool can_straddle; | |
289 | ||
290 | int nlines; | |
291 | int count; | |
292 | int nextidx; | |
293 | uint64_t* *lines; | |
294 | ||
295 | uint64_t sum; // useful for generating prediction efficiency stats for elemsize=1. (may also be useful in other situations) | |
296 | }; // rz3_bitarray | |
297 | ||
298 | ||
299 | #endif // _rz3_bitarray_h_ |