HOG2
NBitArray.h
Go to the documentation of this file.
1 //
2 // NBitArray.h
3 // hog2 glut
4 //
5 // Created by Nathan Sturtevant on 9/29/15.
6 // Copyright (c) 2015 University of Denver. All rights reserved.
7 //
8 
9 #ifndef hog2_glut_NBitArray_h
10 #define hog2_glut_NBitArray_h
11 
12 #include <stdint.h>
13 #include <string.h>
14 #include <algorithm>
15 #include <cinttypes>
16 
22 template <uint64_t numBits>
23 class NBitArray
24 {
25 public:
26  NBitArray(uint64_t numEntries = 0);
27  NBitArray(const char *);
28  NBitArray(const NBitArray &copyMe);
29  ~NBitArray();
30  NBitArray &operator=(const NBitArray &copyMe);
31  bool Equal(const NBitArray &compare) const;
32  void FillMax();
33  void Clear();
34  void Resize(uint64_t newMaxEntries);
35  uint64_t Size() const;
36  uint64_t Get(uint64_t index) const;
37  void Set(uint64_t index, uint64_t val);
38  uint64_t GetMaxValue() const { uint64_t v = 1; return (v<<numBits)-1;}
39 
40  bool Write(FILE *);
41  bool Read(FILE *);
42  bool Write(const char *);
43  bool Read(const char *);
44 private:
45  uint64_t *mem;
46  uint64_t entries;
47  uint64_t memorySize;
48 };
49 
50 
51 template <uint64_t numBits>
52 bool operator==(const NBitArray<numBits>& l, const NBitArray<numBits>& r)
53 {
54  return l.Equal(r);
55 }
56 
57 template <uint64_t numBits>
58 NBitArray<numBits>::NBitArray(uint64_t numEntries)
59 :entries(numEntries), memorySize(((entries*numBits+63)/64))
60 {
61  static_assert(numBits >= 1 && numBits <= 64, "numBits out of bounds!");
62 
63  mem = new uint64_t[memorySize];
64 }
65 
66 template <uint64_t numBits>
67 NBitArray<numBits>::NBitArray(const char *file)
68 :mem(0)
69 {
70  static_assert(numBits >= 1 && numBits <= 64, "numBits out of bounds!");
71  Read(file);
72 }
73 
74 template <uint64_t numBits>
75 NBitArray<numBits>::NBitArray(const NBitArray &copyMe)
76 {
77  entries = copyMe.entries;
78  memorySize = copyMe.memorySize;
79  mem = new uint64_t[memorySize];
80  memcpy(mem, copyMe.mem, memorySize*sizeof(mem[0]));
81 }
82 
83 
84 template <uint64_t numBits>
85 NBitArray<numBits>::~NBitArray()
86 {
87  delete [] mem;
88 }
89 
90 template <uint64_t numBits>
91 NBitArray<numBits> &NBitArray<numBits>::operator=(const NBitArray &copyMe)
92 {
93  if (this == &copyMe)
94  return *this;
95  delete mem;
96  entries = copyMe.entries;
97  memorySize = copyMe.memorySize;
98  mem = new uint64_t[memorySize];
99  memcpy(mem, copyMe.mem, memorySize*sizeof(mem[0]));
100  return *this;
101 }
102 
103 template <uint64_t numBits>
104 bool NBitArray<numBits>::Equal(const NBitArray &compare) const
105 {
106  if (this == &compare)
107  return true;
108  if (entries != compare.entries)
109  return false;
110  for (size_t x = 0; x < memorySize; x++)
111  {
112  if (mem[x] != compare.mem[x])
113  return false;
114  }
115 #pragma message("Last bits are not being tested properly")
116  // TODO: figure out how many remaining entries are left, and
117  // only compare relevant bits
118  return true;
119 }
120 
121 
122 template <uint64_t numBits>
123 void NBitArray<numBits>::FillMax()
124 {
125  memset(mem, 0xFF, memorySize*8);
126 }
127 
128 template <uint64_t numBits>
129 void NBitArray<numBits>::Clear()
130 {
131  memset(mem, 0, memorySize*8);
132 }
133 
134 template <uint64_t numBits>
135 void NBitArray<numBits>::Resize(uint64_t newMaxEntries)
136 {
137  entries = newMaxEntries;
138  memorySize = ((entries*numBits+63)/64);
139  delete [] mem;
140  mem = new uint64_t[memorySize];
141 }
142 
143 template <uint64_t numBits>
144 uint64_t NBitArray<numBits>::Size() const
145 {
146  return entries;
147 }
148 
149 template <uint64_t numBits>
150 bool NBitArray<numBits>::Write(FILE *f)
151 {
152  if (fwrite(&entries, sizeof(uint64_t), 1, f) != 1)
153  return false;
154  if (fwrite(&memorySize, sizeof(uint64_t), 1, f) != 1)
155  return false;
156  if (fwrite(mem, sizeof(uint64_t), memorySize, f) != memorySize)
157  return false;
158  printf("Wrote %" PRId64 " bytes to disk\n", memorySize*sizeof(uint64_t));
159  return true;
160 }
161 
162 template <uint64_t numBits>
163 bool NBitArray<numBits>::Read(FILE *f)
164 {
165  bool success = true;
166  uint64_t e1, m1;
167  success = success&&(fread(&e1, sizeof(uint64_t), 1, f) == 1);
168  success = success&&(fread(&m1, sizeof(uint64_t), 1, f) == 1);
169  if (success)
170  {
171  entries = e1;
172  memorySize = m1;
173  delete [] mem;
174  mem = new uint64_t[memorySize];
175  success = success&&(fread(mem, sizeof(uint64_t), memorySize, f) == memorySize);
176  }
177  return success;
178 }
179 
180 template <uint64_t numBits>
181 bool NBitArray<numBits>::Write(const char *file)
182 {
183  FILE *f = fopen(file, "w+b");
184  if (f == 0)
185  {
186  perror("Could not open file for writing in NBitArray");
187  return false;
188  }
189  bool result = Write(f);
190  fclose(f);
191  return result;
192 }
193 
194 template <uint64_t numBits>
195 bool NBitArray<numBits>::Read(const char *file)
196 {
197  FILE *f = fopen(file, "rb");
198  if (f == 0)
199  {
200  perror("Could not open file for reading in NBitArray");
201  return false;
202  }
203  bool result = Read(f);
204  fclose(f);
205  return result;
206 }
207 
208 template <uint64_t numBits>
209 uint64_t NBitArray<numBits>::Get(uint64_t index) const
210 {
211  uint64_t startingBit = index*numBits;
212  uint64_t offset1 = startingBit/64;
213  uint64_t bitOffset1 = startingBit&0x3F; // same as mod 64
214  uint64_t bitCount1 = std::min(64-bitOffset1, numBits);
215  uint64_t bitCount2 = numBits - bitCount1;
216  uint64_t bitMask1 = (1ull<<bitCount1)-1;
217  uint64_t bitMask2 = (1ull<<bitCount2)-1;
218  uint64_t result = (mem[offset1]>>bitOffset1)&bitMask1;
219  result = ((mem[offset1+1]&bitMask2)<<bitCount1) | result;
220  return result;
221 }
222 
223 template <uint64_t numBits>
224 void NBitArray<numBits>::Set(uint64_t index, uint64_t val)
225 {
226  uint64_t startingBit = index*numBits;
227  uint64_t offset1 = startingBit/64;
228  uint64_t bitOffset1 = startingBit&0x3F; // same as mod 64
229  uint64_t bitCount1 = std::min(64-bitOffset1, (uint64_t)numBits);
230  uint64_t bitCount2 = numBits - bitCount1;
231  uint64_t bitMask1 = (1ull<<bitCount1)-1;
232  uint64_t bitMask2 = (1ull<<bitCount2)-1;
233  mem[offset1] = (mem[offset1]&(~(bitMask1<<bitOffset1))) | ((val&bitMask1)<<bitOffset1);
234  mem[offset1+1] = (mem[offset1+1]&(~(bitMask2))) | ((val>>bitCount1)&bitMask2);
235  // uint64_t result = (mem[offset1]>>bitOffset1)&bitMask1;
236  // result = ((mem[offset1+1]&bitMask2)<<bitCount2) | result;
237 }
238 
239 template <>
240 uint64_t NBitArray<64>::Get(uint64_t index) const;
241 template <>
242 uint64_t NBitArray<32>::Get(uint64_t index) const;
243 template <>
244 uint64_t NBitArray<16>::Get(uint64_t index) const;
245 template <>
246 uint64_t NBitArray<8>::Get(uint64_t index) const;
247 template <>
248 uint64_t NBitArray<4>::Get(uint64_t index) const;
249 template <>
250 uint64_t NBitArray<2>::Get(uint64_t index) const;
251 template <>
252 uint64_t NBitArray<1>::Get(uint64_t index) const;
253 template <>
254 void NBitArray<64>::Set(uint64_t index, uint64_t val);
255 template <>
256 void NBitArray<32>::Set(uint64_t index, uint64_t val);
257 template <>
258 void NBitArray<16>::Set(uint64_t index, uint64_t val);
259 template <>
260 void NBitArray<8>::Set(uint64_t index, uint64_t val);
261 template <>
262 void NBitArray<4>::Set(uint64_t index, uint64_t val);
263 template <>
264 void NBitArray<2>::Set(uint64_t index, uint64_t val);
265 template <>
266 void NBitArray<1>::Set(uint64_t index, uint64_t val);
267 
268 
269 
270 #endif
NBitArray
This class supports compact n-bit arrays.
Definition: NBitArray.h:23
NBitArray::memorySize
uint64_t memorySize
Definition: NBitArray.h:47
min
double min(double a, double b)
Definition: FPUtil.h:35
NBitArray::~NBitArray
~NBitArray()
Definition: NBitArray.h:85
NBitArray::mem
uint64_t * mem
Definition: NBitArray.h:45
NBitArray::FillMax
void FillMax()
Definition: NBitArray.h:123
NBitArray::Set
void Set(uint64_t index, uint64_t val)
Definition: NBitArray.h:224
NBitArray::Resize
void Resize(uint64_t newMaxEntries)
Definition: NBitArray.h:135
NBitArray::Get
uint64_t Get(uint64_t index) const
Definition: NBitArray.h:209
NBitArray::entries
uint64_t entries
Definition: NBitArray.h:46
NBitArray::Write
bool Write(FILE *)
Definition: NBitArray.h:150
NBitArray::Clear
void Clear()
Definition: NBitArray.h:129
NBitArray::Size
uint64_t Size() const
Definition: NBitArray.h:144
NBitArray::NBitArray
NBitArray(uint64_t numEntries=0)
Definition: NBitArray.h:58
NBitArray::Equal
bool Equal(const NBitArray &compare) const
Definition: NBitArray.h:104
NBitArray::Read
bool Read(FILE *)
Definition: NBitArray.h:163
NBitArray::GetMaxValue
uint64_t GetMaxValue() const
Definition: NBitArray.h:38
operator==
bool operator==(const NBitArray< numBits > &l, const NBitArray< numBits > &r)
Definition: NBitArray.h:52
NBitArray::operator=
NBitArray & operator=(const NBitArray &copyMe)
Definition: NBitArray.h:91
Generated by   doxygen 1.8.17