* ========== Copyright Header Begin ==========================================
* OpenSPARC T2 Processor File: rz3_bitarray.h
* Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES.
* The above named program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public
* License version 2 as published by the Free Software Foundation.
* The above named program is distributed in the hope that it will be
* useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
* You should have received a copy of the GNU General Public
* License along with this work; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
* ========== Copyright Header End ============================================
* utility code for rstzip3
* Copyright (C) 2003 Sun Microsystems, Inc.
#include "rstf/byteswap.h"
// set this to 1 for debugging - outputs every update to each bitarray
const int rz3_bitarray_debug
= 0;
// class rz3_bitarray_base {
// rz3_bitarray_base(const char * arg_name, int arg_nbits, int size_hint) {
rz3_bitarray(const char * arg_name
, int arg_nbits
, int size_hint
) {
elem_mask
= (~0ull) >> (64-elemsize
);
desired_count
= size_hint
;
desired_count
= (1024*64/elemsize
);
reallocate(desired_count
);
straddle
= ((64%elemsize
) != 0);
// ~rz3_bitarray_base() {
virtual void Push(uint64_t data_nbits
) {
if (rz3_bitarray_debug
) { printf("rz3_bitarray %s [%d] <= %llx\n", name
, count
, data_nbits
); fflush(stdout
); }
if (count
>= maxcount
) { // we havent written u64[count] yet. cannot write if count>=maxcount
if (straddle
&& ((64-offs
) < elemsize
)) {
uint64_t lmask
= (1ull << lbits
) - 1;
uint64_t lowbits
= data_nbits
& lmask
;
u64
[u64idx
] &= ~(lmask
<< offs
);
u64
[u64idx
] |= (lowbits
<< offs
);
u64
[u64idx
+1] = data_nbits
>> lbits
;
u64
[u64idx
] &= ~(elem_mask
<< offs
);
u64
[u64idx
] |= (data_nbits
<< offs
);
virtual bool Get(int key
, uint64_t & value
)
if (rz3_bitarray_debug
) fprintf(stderr
, "rz3_bitarray %s: Error: Get(%d) - count is %d\n", name
, key
, count
);
int u64idx
= (key
*elemsize
)/64;
int offs
= (key
*elemsize
)%64;
if (straddle
&& ((offs
+elemsize
)>64)) {
int hbits
= (offs
+elemsize
)-64;
int lbits
= elemsize
-hbits
;
value
= u64
[u64idx
] >> offs
;
uint64_t hmask
= (1ull << hbits
)-1;
uint64_t hval
= u64
[u64idx
+1] & hmask
;
value
|= (hval
<< lbits
);
value
= (u64
[u64idx
] >> offs
) & elem_mask
;
// GetNext() is a stateful function that returns elements in the order they were inserted
virtual bool GetNext(uint64_t & value
)
bool rv
= Get(nextidx
, value
);
if (rz3_bitarray_debug
) { printf("rz3_bitarray %s [%d] <= %llx\n", name
, nextidx
, value
); fflush(stdout
); }
virtual uint64_t ComputeMemBufSize(int n_elements
)
int n_u64
= (n_elements
* elemsize
+ 63)/64;
return n_u64
* sizeof(uint64_t);
virtual uint64_t GetMemBufSize() {
return ComputeMemBufSize(count
);
virtual uint64_t CopyTo(unsigned char * membuf
)
int n_u64
= (nbits
+63)/64;
uint64_t sz
= n_u64
*sizeof(uint64_t);
for (int i
=0; i
<n_u64
; i
++) {
u64
[i
] = byteswap64(u64
[i
]);
virtual uint64_t CopyFrom(unsigned char * membuf
, int arg_count
)
if (arg_count
> maxcount
) {
nbits
= count
* elemsize
;
int n_u64
= (nbits
+ 63)/64;
int sz
= n_u64
* sizeof(uint64_t);
for (int i
=0; i
<n_u64
; i
++) {
u64
[i
] = byteswap64(u64
[i
]);
// GetSum only returns a valid value if elements are Push()'ed. Not if the are CopyFrom()'ed.
virtual uint64_t GetSum() {
void reallocate(int desired_size
) {
if (desired_size
<= maxcount
) return;
if (desired_size
< (2*maxcount
)) {
desired_size
= 2*maxcount
;
int new_u64_count
= (desired_size
* elemsize
+ 63)/64;
uint64_t * new_u64
= new uint64_t [new_u64_count
];
memcpy(new_u64
, u64
, u64_count
*sizeof(uint64_t));
u64_count
= new_u64_count
;
int count
; // count of valid elements in the array
int maxcount
; // the most number of elements that can exist in the array
}; // class rz3_bitarray_base
// the rz3_bitarray is a space-efficient way to
// maintain lists of items whose size is not necessarily 8/16/32/64 bits.
// We try to balance memory usage and speed requirements.
// To this end, we implement 2 types of bit-arrays: fixed and growable.
// Fixed arrays are fast but can waste space.
// Growable arrays allocate space only as required
// nbits is the size of the array element. Must be <= 64
rz3_bitarray(const char * arg_name
, int nbits
, int size_hint
)
impl
= new rz3_bitarray_base(arg_name
, nbits
, size_hint
);
void Push(uint64_t data_nbits
) {
bool Get(int key
, uint64_t & value
) {
return impl
->Get(key
, value
);
// GetNext() is a stateful function that returns elements in the order they were inserted
bool GetNext(uint64_t & value
)
return impl
->GetNext(value
);
uint64_t ComputeMemBufSize(int n_elements
) {
return impl
->ComputeMemBufSize(n_elements
);
uint64_t GetMemBufSize() {
return impl
->GetMemBufSize();
uint64_t CopyTo(unsigned char * membuf
) {
return impl
->CopyTo(membuf
);
uint64_t CopyFrom(unsigned char * membuf
, int arg_count
) {
return impl
->CopyFrom(membuf
, arg_count
);
rz3_bitarray_base
* impl
;
#endif // _rz3_bitarray_h_