Project

General

Profile

Statistics
| Branch: | Tag: | Revision:

birq / bit_array.c @ master

History | View | Annotate | Download (81.1 KB)

1
/*
2
 bit_array.c
3
 project: bit array C library
4
 url: https://github.com/noporpoise/BitArray/
5
 maintainer: Isaac Turner <turner.isaac@gmail.com>
6
 license: Public Domain, no warranty
7
 date: Aug 2014
8
*/
9

    
10
// 64 bit words
11
// Array length can be zero
12
// Unused top bits must be zero
13

    
14
#include <stdlib.h>
15
#include <stdarg.h>
16
#include <stdio.h>
17
#include <limits.h> // ULONG_MAX
18
#include <errno.h>
19
#include <signal.h> // needed for abort()
20
#include <string.h> // memset()
21
#include <assert.h>
22
#include <time.h> // needed for seeding rand()
23
#include <unistd.h>  // need for getpid() for seeding rand number
24
#include <ctype.h>  // need for tolower()
25
#include <errno.h>  // perror()
26
#include <sys/time.h> // for seeding random
27

    
28
// Windows includes
29
#if defined(_WIN32)
30
#include <intrin.h>
31
#endif
32

    
33
#include "bit_array.h"
34
#include "bit_macros.h"
35

    
36
//
37
// Tables of constants
38
//
39

    
40
// byte reverse look up table
41
static const word_t reverse_table[256] =
42
{
43
  0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0,
44
  0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
45
  0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8,
46
  0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
47
  0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4,
48
  0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
49
  0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC,
50
  0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
51
  0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2,
52
  0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
53
  0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA,
54
  0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
55
  0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6,
56
  0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
57
  0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE,
58
  0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
59
  0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1,
60
  0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
61
  0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9,
62
  0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
63
  0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5,
64
  0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
65
  0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED,
66
  0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
67
  0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3,
68
  0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
69
  0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB,
70
  0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
71
  0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7,
72
  0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
73
  0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF,
74
  0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF,
75
};
76

    
77
// Morton table for interleaving bytes
78
static const word_t morton_table0[256] =
79
{
80
  0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015,
81
  0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055,
82
  0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115,
83
  0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155,
84
  0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415,
85
  0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455,
86
  0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515,
87
  0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555,
88
  0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015,
89
  0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055,
90
  0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115,
91
  0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155,
92
  0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415,
93
  0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455,
94
  0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515,
95
  0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555,
96
  0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015,
97
  0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055,
98
  0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115,
99
  0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155,
100
  0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415,
101
  0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455,
102
  0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515,
103
  0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555,
104
  0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015,
105
  0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055,
106
  0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115,
107
  0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155,
108
  0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415,
109
  0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455,
110
  0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515,
111
  0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555,
112
};
113

    
114
// Morton table for interleaving bytes, shifted left 1 bit
115
static const word_t morton_table1[256] =
116
{
117
  0x0000, 0x0002, 0x0008, 0x000A, 0x0020, 0x0022, 0x0028, 0x002A,
118
  0x0080, 0x0082, 0x0088, 0x008A, 0x00A0, 0x00A2, 0x00A8, 0x00AA,
119
  0x0200, 0x0202, 0x0208, 0x020A, 0x0220, 0x0222, 0x0228, 0x022A,
120
  0x0280, 0x0282, 0x0288, 0x028A, 0x02A0, 0x02A2, 0x02A8, 0x02AA,
121
  0x0800, 0x0802, 0x0808, 0x080A, 0x0820, 0x0822, 0x0828, 0x082A,
122
  0x0880, 0x0882, 0x0888, 0x088A, 0x08A0, 0x08A2, 0x08A8, 0x08AA,
123
  0x0A00, 0x0A02, 0x0A08, 0x0A0A, 0x0A20, 0x0A22, 0x0A28, 0x0A2A,
124
  0x0A80, 0x0A82, 0x0A88, 0x0A8A, 0x0AA0, 0x0AA2, 0x0AA8, 0x0AAA,
125
  0x2000, 0x2002, 0x2008, 0x200A, 0x2020, 0x2022, 0x2028, 0x202A,
126
  0x2080, 0x2082, 0x2088, 0x208A, 0x20A0, 0x20A2, 0x20A8, 0x20AA,
127
  0x2200, 0x2202, 0x2208, 0x220A, 0x2220, 0x2222, 0x2228, 0x222A,
128
  0x2280, 0x2282, 0x2288, 0x228A, 0x22A0, 0x22A2, 0x22A8, 0x22AA,
129
  0x2800, 0x2802, 0x2808, 0x280A, 0x2820, 0x2822, 0x2828, 0x282A,
130
  0x2880, 0x2882, 0x2888, 0x288A, 0x28A0, 0x28A2, 0x28A8, 0x28AA,
131
  0x2A00, 0x2A02, 0x2A08, 0x2A0A, 0x2A20, 0x2A22, 0x2A28, 0x2A2A,
132
  0x2A80, 0x2A82, 0x2A88, 0x2A8A, 0x2AA0, 0x2AA2, 0x2AA8, 0x2AAA,
133
  0x8000, 0x8002, 0x8008, 0x800A, 0x8020, 0x8022, 0x8028, 0x802A,
134
  0x8080, 0x8082, 0x8088, 0x808A, 0x80A0, 0x80A2, 0x80A8, 0x80AA,
135
  0x8200, 0x8202, 0x8208, 0x820A, 0x8220, 0x8222, 0x8228, 0x822A,
136
  0x8280, 0x8282, 0x8288, 0x828A, 0x82A0, 0x82A2, 0x82A8, 0x82AA,
137
  0x8800, 0x8802, 0x8808, 0x880A, 0x8820, 0x8822, 0x8828, 0x882A,
138
  0x8880, 0x8882, 0x8888, 0x888A, 0x88A0, 0x88A2, 0x88A8, 0x88AA,
139
  0x8A00, 0x8A02, 0x8A08, 0x8A0A, 0x8A20, 0x8A22, 0x8A28, 0x8A2A,
140
  0x8A80, 0x8A82, 0x8A88, 0x8A8A, 0x8AA0, 0x8AA2, 0x8AA8, 0x8AAA,
141
  0xA000, 0xA002, 0xA008, 0xA00A, 0xA020, 0xA022, 0xA028, 0xA02A,
142
  0xA080, 0xA082, 0xA088, 0xA08A, 0xA0A0, 0xA0A2, 0xA0A8, 0xA0AA,
143
  0xA200, 0xA202, 0xA208, 0xA20A, 0xA220, 0xA222, 0xA228, 0xA22A,
144
  0xA280, 0xA282, 0xA288, 0xA28A, 0xA2A0, 0xA2A2, 0xA2A8, 0xA2AA,
145
  0xA800, 0xA802, 0xA808, 0xA80A, 0xA820, 0xA822, 0xA828, 0xA82A,
146
  0xA880, 0xA882, 0xA888, 0xA88A, 0xA8A0, 0xA8A2, 0xA8A8, 0xA8AA,
147
  0xAA00, 0xAA02, 0xAA08, 0xAA0A, 0xAA20, 0xAA22, 0xAA28, 0xAA2A,
148
  0xAA80, 0xAA82, 0xAA88, 0xAA8A, 0xAAA0, 0xAAA2, 0xAAA8, 0xAAAA,
149
};
150

    
151
//
152
// Macros
153
//
154

    
155
// WORD_SIZE is the number of bits per word
156
// sizeof gives size in bytes (8 bits per byte)
157
#define WORD_SIZE 64
158
// #define WORD_SIZE (sizeof(word_t) * 8)
159

    
160
// POPCOUNT is number of bits set
161

    
162
#if defined(_WIN32)
163

    
164
// See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
165
static word_t __inline windows_popcount(word_t w)
166
{
167
  w = w - ((w >> 1) & (word_t)~(word_t)0/3);
168
  w = (w & (word_t)~(word_t)0/15*3) + ((w >> 2) & (word_t)~(word_t)0/15*3);
169
  w = (w + (w >> 4)) & (word_t)~(word_t)0/255*15;
170
  c = (word_t)(w * ((word_t)~(word_t)0/255)) >> (sizeof(word_t) - 1) * 8;
171
}
172

    
173
static word_t __inline windows_parity(word_t w)
174
{
175
  w ^= w >> 1;
176
  w ^= w >> 2;
177
  w = (w & 0x1111111111111111UL) * 0x1111111111111111UL;
178
  return (w >> 60) & 1;
179
}
180

    
181
#define POPCOUNT(x) windows_popcountl(x)
182
#define PARITY(x) windows_parity(x)
183
#else
184
#define POPCOUNT(x) (unsigned)__builtin_popcountll(x)
185
#define PARITY(x) (unsigned)__builtin_parityll(x)
186
#endif
187

    
188
#define MIN(a, b)  (((a) <= (b)) ? (a) : (b))
189
#define MAX(a, b)  (((a) >= (b)) ? (a) : (b))
190

    
191
// Make this a power of two
192
#define INIT_CAPACITY_WORDS 2
193

    
194
// word of all 1s
195
#define WORD_MAX  (~(word_t)0)
196

    
197
#define SET_REGION(arr,start,len)    _set_region((arr),(start),(len),FILL_REGION)
198
#define CLEAR_REGION(arr,start,len)  _set_region((arr),(start),(len),ZERO_REGION)
199
#define TOGGLE_REGION(arr,start,len) _set_region((arr),(start),(len),SWAP_REGION)
200

    
201
// Have we initialised with srand() ?
202
static char rand_initiated = 0;
203

    
204
static void _seed_rand()
205
{
206
  if(!rand_initiated)
207
  {
208
    // Initialise random number generator
209
    struct timeval time;
210
    gettimeofday(&time, NULL);
211
    srand((((time.tv_sec ^ getpid()) * 1000001) + time.tv_usec));
212
    rand_initiated = 1;
213
  }
214
}
215

    
216
//
217
// Common internal functions
218
//
219

    
220
#define bits_in_top_word(nbits) ((nbits) ? bitset64_idx((nbits) - 1) + 1 : 0)
221

    
222
// Mostly used for debugging
223
static inline void _print_word(word_t word, FILE* out)
224
{
225
  word_offset_t i;
226
  for(i = 0; i < WORD_SIZE; i++)
227
  {
228
    fprintf(out, "%c", ((word >> i) & (word_t)0x1) == 0 ? '0' : '1');
229
  }
230
}
231

    
232
// prints right to left
233
static inline char* _word_to_str(word_t word, char str[WORD_SIZE+1])
234
  __attribute__((unused));
235

    
236
static inline char* _word_to_str(word_t word, char str[WORD_SIZE+1])
237
{
238
  word_offset_t i;
239
  for(i = 0; i < WORD_SIZE; i++)
240
  {
241
    str[WORD_SIZE-i-1] = ((word >> i) & (word_t)0x1) == 0 ? '0' : '1';
242
  }
243
  str[WORD_SIZE] = '\0';
244
  return str;
245
}
246

    
247
// Used in debugging
248
#ifdef DEBUG
249
  #define DEBUG_PRINT(msg,...) printf("[%s:%i] "msg, __FILE__, __LINE__, ##__VA_ARGS__);
250
  #define DEBUG_VALIDATE(a) validate_bitarr((a), __FILE__, __LINE__)
251
#else
252
  #define DEBUG_PRINT(msg,...)
253
  #define DEBUG_VALIDATE(a)
254
#endif
255

    
256
void validate_bitarr(BIT_ARRAY *arr, const char *file, int lineno)
257
{
258
  // Check top word is masked
259
  word_addr_t tw = arr->num_of_words == 0 ? 0 : arr->num_of_words - 1;
260
  bit_index_t top_bits = bits_in_top_word(arr->num_of_bits);
261
  int err = 0;
262

    
263
  if(arr->words[tw] > bitmask64(top_bits))
264
  {
265
    _print_word(arr->words[tw], stderr);
266
    fprintf(stderr, "\n[%s:%i] Expected %i bits in top word[%i]\n",
267
            file, lineno, (int)top_bits, (int)tw);
268
    err = 1;
269
  }
270

    
271
  // Check num of words is correct
272
  word_addr_t num_words = roundup_bits2words64(arr->num_of_bits);
273
  if(num_words != arr->num_of_words)
274
  {
275
    fprintf(stderr, "\n[%s:%i] num of words wrong "
276
                    "[bits: %i, word: %i, actual words: %i]\n", file, lineno,
277
            (int)arr->num_of_bits, (int)num_words, (int)arr->num_of_words);
278
    err = 1;
279
  }
280

    
281
  if(err) abort();
282
}
283

    
284
// Reverse a word
285
static inline word_t _reverse_word(word_t word)
286
{
287
  word_t reverse = (reverse_table[(word)       & 0xff] << 56) |
288
                   (reverse_table[(word >>  8) & 0xff] << 48) |
289
                   (reverse_table[(word >> 16) & 0xff] << 40) |
290
                   (reverse_table[(word >> 24) & 0xff] << 32) |
291
                   (reverse_table[(word >> 32) & 0xff] << 24) |
292
                   (reverse_table[(word >> 40) & 0xff] << 16) |
293
                   (reverse_table[(word >> 48) & 0xff] << 8) |
294
                   (reverse_table[(word >> 56) & 0xff]);
295

    
296
  return reverse;
297
}
298

    
299
static inline void _mask_top_word(BIT_ARRAY* bitarr)
300
{
301
  // Mask top word
302
  word_addr_t num_of_words = MAX(1, bitarr->num_of_words);
303
  word_offset_t bits_active = bits_in_top_word(bitarr->num_of_bits);
304
  bitarr->words[num_of_words-1] &= bitmask64(bits_active);
305
}
306

    
307
//
308
// Get and set words (internal use only -- no bounds checking)
309
//
310

    
311
static inline word_t _get_word(const BIT_ARRAY* bitarr, bit_index_t start)
312
{
313
  word_addr_t word_index = bitset64_wrd(start);
314
  word_offset_t word_offset = bitset64_idx(start);
315

    
316
  word_t result = bitarr->words[word_index] >> word_offset;
317

    
318
  word_offset_t bits_taken = WORD_SIZE - word_offset;
319

    
320
  // word_offset is now the number of bits we need from the next word
321
  // Check the next word has at least some bits
322
  if(word_offset > 0 && start + bits_taken < bitarr->num_of_bits)
323
  {
324
    result |= bitarr->words[word_index+1] << (WORD_SIZE - word_offset);
325
  }
326

    
327
  return result;
328
}
329

    
330
// Set 64 bits from a particular start position
331
// Doesn't extend bit array
332
static inline void _set_word(BIT_ARRAY* bitarr, bit_index_t start, word_t word)
333
{
334
  word_addr_t word_index = bitset64_wrd(start);
335
  word_offset_t word_offset = bitset64_idx(start);
336

    
337
  if(word_offset == 0)
338
  {
339
    bitarr->words[word_index] = word;
340
  }
341
  else
342
  {
343
    bitarr->words[word_index]
344
      = (word << word_offset) |
345
        (bitarr->words[word_index] & bitmask64(word_offset));
346

    
347
    if(word_index+1 < bitarr->num_of_words)
348
    {
349
      bitarr->words[word_index+1]
350
        = (word >> (WORD_SIZE - word_offset)) |
351
          (bitarr->words[word_index+1] & (WORD_MAX << word_offset));
352
    }
353
  }
354

    
355
  // Mask top word
356
  _mask_top_word(bitarr);
357
  DEBUG_VALIDATE(bitarr);
358
}
359

    
360
static inline void _set_byte(BIT_ARRAY *bitarr, bit_index_t start, uint8_t byte)
361
{
362
  word_t w = _get_word(bitarr, start);
363
  _set_word(bitarr, start, (w & ~(word_t)0xff) | byte);
364
}
365

    
366
// 4 bits
367
static inline void _set_nibble(BIT_ARRAY *bitarr, bit_index_t start,
368
                               uint8_t nibble)
369
{
370
  word_t w = _get_word(bitarr, start);
371
  _set_word(bitarr, start, (w & ~(word_t)0xf) | nibble);
372
}
373

    
374
// Wrap around
375
static inline word_t _get_word_cyclic(const BIT_ARRAY* bitarr, bit_index_t start)
376
{
377
  word_t word = _get_word(bitarr, start);
378

    
379
  bit_index_t bits_taken = bitarr->num_of_bits - start;
380

    
381
  if(bits_taken < WORD_SIZE)
382
  {
383
    word |= (bitarr->words[0] << bits_taken);
384

    
385
    if(bitarr->num_of_bits < (bit_index_t)WORD_SIZE)
386
    {
387
      // Mask word to prevent repetition of the same bits
388
      word = word & bitmask64(bitarr->num_of_bits);
389
    }
390
  }
391

    
392
  return word;
393
}
394

    
395
// Wrap around
396
static inline void _set_word_cyclic(BIT_ARRAY* bitarr,
397
                                    bit_index_t start, word_t word)
398
{
399
  _set_word(bitarr, start, word);
400

    
401
  bit_index_t bits_set = bitarr->num_of_bits - start;
402

    
403
  if(bits_set < WORD_SIZE && start > 0)
404
  {
405
    word >>= bits_set;
406

    
407
    // Prevent overwriting the bits we've just set
408
    // by setting 'start' as the upper bound for the number of bits to write
409
    word_offset_t bits_remaining = MIN(WORD_SIZE - bits_set, start);
410
    word_t mask = bitmask64(bits_remaining);
411

    
412
    bitarr->words[0] = bitmask_merge(word, bitarr->words[0], mask);
413
  }
414
}
415

    
416
//
417
// Fill a region (internal use only)
418
//
419

    
420
// FillAction is fill with 0 or 1 or toggle
421
typedef enum {ZERO_REGION, FILL_REGION, SWAP_REGION} FillAction;
422

    
423
static inline void _set_region(BIT_ARRAY* bitarr, bit_index_t start,
424
                               bit_index_t length, FillAction action)
425
{
426
  if(length == 0) return;
427

    
428
  word_addr_t first_word = bitset64_wrd(start);
429
  word_addr_t last_word = bitset64_wrd(start+length-1);
430
  word_offset_t foffset = bitset64_idx(start);
431
  word_offset_t loffset = bitset64_idx(start+length-1);
432

    
433
  if(first_word == last_word)
434
  {
435
    word_t mask = bitmask64(length) << foffset;
436

    
437
    switch(action)
438
    {
439
      case ZERO_REGION: bitarr->words[first_word] &= ~mask; break;
440
      case FILL_REGION: bitarr->words[first_word] |=  mask; break;
441
      case SWAP_REGION: bitarr->words[first_word] ^=  mask; break;
442
    }
443
  }
444
  else
445
  {
446
    // Set first word
447
    switch(action)
448
    {
449
      case ZERO_REGION: bitarr->words[first_word] &=  bitmask64(foffset); break;
450
      case FILL_REGION: bitarr->words[first_word] |= ~bitmask64(foffset); break;
451
      case SWAP_REGION: bitarr->words[first_word] ^= ~bitmask64(foffset); break;
452
    }
453

    
454
    word_addr_t i;
455

    
456
    // Set whole words
457
    switch(action)
458
    {
459
      case ZERO_REGION:
460
        for(i = first_word + 1; i < last_word; i++)
461
          bitarr->words[i] = (word_t)0;
462
        break;
463
      case FILL_REGION:
464
        for(i = first_word + 1; i < last_word; i++)
465
          bitarr->words[i] = WORD_MAX;
466
        break;
467
      case SWAP_REGION:
468
        for(i = first_word + 1; i < last_word; i++)
469
          bitarr->words[i] ^= WORD_MAX;
470
        break;
471
    }
472

    
473
    // Set last word
474
    switch(action)
475
    {
476
      case ZERO_REGION: bitarr->words[last_word] &= ~bitmask64(loffset+1); break;
477
      case FILL_REGION: bitarr->words[last_word] |=  bitmask64(loffset+1); break;
478
      case SWAP_REGION: bitarr->words[last_word] ^=  bitmask64(loffset+1); break;
479
    }
480
  }
481
}
482

    
483

    
484

    
485
//
486
// Constructor
487
//
488

    
489
// If cannot allocate memory, set errno to ENOMEM, return NULL
490
BIT_ARRAY* bit_array_alloc(BIT_ARRAY* bitarr, bit_index_t nbits)
491
{
492
  bitarr->num_of_bits = nbits;
493
  bitarr->num_of_words = roundup_bits2words64(nbits);
494
  bitarr->capacity_in_words = MAX(8, roundup2pow(bitarr->num_of_words));
495
  bitarr->words = (word_t*)calloc(bitarr->capacity_in_words, sizeof(word_t));
496
  if(bitarr->words == NULL) {
497
    errno = ENOMEM;
498
    return NULL;
499
  }
500
  return bitarr;
501
}
502

    
503
void bit_array_dealloc(BIT_ARRAY* bitarr)
504
{
505
  free(bitarr->words);
506
  memset(bitarr, 0, sizeof(BIT_ARRAY));
507
}
508

    
509
// If cannot allocate memory, set errno to ENOMEM, return NULL
510
BIT_ARRAY* bit_array_create(bit_index_t nbits)
511
{
512
  BIT_ARRAY* bitarr = (BIT_ARRAY*)malloc(sizeof(BIT_ARRAY));
513

    
514
  // error if could not allocate enough memory
515
  if(bitarr == NULL || bit_array_alloc(bitarr, nbits) == NULL)
516
  {
517
    if(bitarr != NULL) free(bitarr);
518
    errno = ENOMEM;
519
    return NULL;
520
  }
521

    
522
  DEBUG_PRINT("Creating BIT_ARRAY (bits: %lu; allocated words: %lu; "
523
              "using words: %lu; WORD_SIZE: %i)\n",
524
              (unsigned long)nbits, (unsigned long)bitarr->capacity_in_words,
525
              (unsigned long)roundup_bits2words64(nbits), (int)WORD_SIZE);
526

    
527
  DEBUG_VALIDATE(bitarr);
528

    
529
  return bitarr;
530
}
531

    
532
//
533
// Destructor
534
//
535
void bit_array_free(BIT_ARRAY* bitarr)
536
{
537
  if(bitarr->words != NULL)
538
    free(bitarr->words);
539

    
540
  free(bitarr);
541
}
542

    
543
bit_index_t bit_array_length(const BIT_ARRAY* bit_arr)
544
{
545
  return bit_arr->num_of_bits;
546
}
547

    
548
// Change the size of a bit array. Enlarging an array will add zeros
549
// to the end of it. Returns 1 on success, 0 on failure (e.g. not enough memory)
550
char bit_array_resize(BIT_ARRAY* bitarr, bit_index_t new_num_of_bits)
551
{
552
  word_addr_t old_num_of_words = bitarr->num_of_words;
553
  word_addr_t new_num_of_words = roundup_bits2words64(new_num_of_bits);
554

    
555
  bitarr->num_of_bits = new_num_of_bits;
556
  bitarr->num_of_words = new_num_of_words;
557

    
558
  DEBUG_PRINT("Resize: old_num_of_words: %i; new_num_of_words: %i capacity: %i\n",
559
              (int)old_num_of_words, (int)new_num_of_words,
560
              (int)bitarr->capacity_in_words);
561

    
562
  if(new_num_of_words > bitarr->capacity_in_words)
563
  {
564
    // Need to change the amount of memory used
565
    word_addr_t old_capacity_in_words = bitarr->capacity_in_words;
566
    size_t old_capacity_in_bytes = old_capacity_in_words * sizeof(word_t);
567

    
568
    bitarr->capacity_in_words = roundup2pow(new_num_of_words);
569
    bitarr->capacity_in_words = MAX(8, bitarr->capacity_in_words);
570

    
571
    size_t new_capacity_in_bytes = bitarr->capacity_in_words * sizeof(word_t);
572
    bitarr->words = (word_t*)realloc(bitarr->words, new_capacity_in_bytes);
573

    
574
    if(bitarr->words == NULL)
575
    {
576
      // error - could not allocate enough memory
577
      perror("resize realloc");
578
      errno = ENOMEM;
579
      return 0;
580
    }
581

    
582
    // Need to zero new memory
583
    size_t num_bytes_to_zero = new_capacity_in_bytes - old_capacity_in_bytes;
584
    memset(bitarr->words + old_capacity_in_words, 0, num_bytes_to_zero);
585

    
586
    DEBUG_PRINT("zeroing from word %i for %i bytes\n", (int)old_capacity_in_words,
587
                (int)num_bytes_to_zero);
588
  }
589
  else if(new_num_of_words < old_num_of_words)
590
  {
591
    // Shrunk -- need to zero old memory
592
    size_t num_bytes_to_zero = (old_num_of_words - new_num_of_words)*sizeof(word_t);
593

    
594
    memset(bitarr->words + new_num_of_words, 0, num_bytes_to_zero);
595
  }
596

    
597
  // Mask top word
598
  _mask_top_word(bitarr);
599
  DEBUG_VALIDATE(bitarr);
600
  return 1;
601
}
602

    
603
void bit_array_resize_critical(BIT_ARRAY* bitarr, bit_index_t num_of_bits)
604
{
605
  bit_index_t old_num_of_bits = bitarr->num_of_bits;
606

    
607
  if(!bit_array_resize(bitarr, num_of_bits))
608
  {
609
    fprintf(stderr, "Ran out of memory resizing [%lu -> %lu]",
610
            (unsigned long)old_num_of_bits, (unsigned long)num_of_bits);
611
    abort();
612
  }
613
}
614

    
615
// If bitarr length < num_bits, resizes to num_bits
616
char bit_array_ensure_size(BIT_ARRAY* bitarr, bit_index_t ensure_num_of_bits)
617
{
618
  if(bitarr->num_of_bits < ensure_num_of_bits)
619
  {
620
    return bit_array_resize(bitarr, ensure_num_of_bits);
621
  }
622

    
623
  return 1;
624
}
625

    
626
void bit_array_ensure_size_critical(BIT_ARRAY* bitarr, bit_index_t num_of_bits)
627
{
628
  if(num_of_bits > bitarr->num_of_bits)
629
  {
630
    bit_array_resize_critical(bitarr, num_of_bits);
631
  }
632
}
633

    
634
static inline
635
void _bit_array_ensure_nwords(BIT_ARRAY* bitarr, word_addr_t nwords,
636
                              const char *file, int lineno, const char *func)
637
{
638
  size_t newmem, oldmem;
639
  if(bitarr->capacity_in_words < nwords) {
640
    oldmem = bitarr->capacity_in_words * sizeof(word_t);
641
    bitarr->capacity_in_words = roundup2pow(nwords);
642
    newmem = bitarr->capacity_in_words * sizeof(word_t);
643
    bitarr->words = (word_t*)realloc(bitarr->words, newmem);
644

    
645
    if(bitarr->words == NULL) {
646
      fprintf(stderr, "[%s:%i:%s()] Ran out of memory resizing [%zu -> %zu]",
647
              file, lineno, func, oldmem, newmem);
648
      abort();
649
    }
650

    
651
    DEBUG_PRINT("Ensure nwords realloc %zu -> %zu\n", oldmem, newmem);
652
  }
653
}
654

    
655

    
656
//
657
// Get, set, clear, assign and toggle individual bits
658
//
659

    
660
// Get the value of a bit (returns 0 or 1)
661
char bit_array_get_bit(const BIT_ARRAY* bitarr, bit_index_t b)
662
{
663
  assert(b < bitarr->num_of_bits);
664
  return bit_array_get(bitarr, b);
665
}
666

    
667
// set a bit (to 1) at position b
668
void bit_array_set_bit(BIT_ARRAY* bitarr, bit_index_t b)
669
{
670
  assert(b < bitarr->num_of_bits);
671
  bit_array_set(bitarr,b);
672
  DEBUG_VALIDATE(bitarr);
673
}
674

    
675
// clear a bit (to 0) at position b
676
void bit_array_clear_bit(BIT_ARRAY* bitarr, bit_index_t b)
677
{
678
  assert(b < bitarr->num_of_bits);
679
  bit_array_clear(bitarr, b);
680
  DEBUG_VALIDATE(bitarr);
681
}
682

    
683
// If bit is 0 -> 1, if bit is 1 -> 0.  AKA 'flip'
684
void bit_array_toggle_bit(BIT_ARRAY* bitarr, bit_index_t b)
685
{
686
  assert(b < bitarr->num_of_bits);
687
  bit_array_toggle(bitarr, b);
688
  DEBUG_VALIDATE(bitarr);
689
}
690

    
691
// If char c != 0, set bit; otherwise clear bit
692
void bit_array_assign_bit(BIT_ARRAY* bitarr, bit_index_t b, char c)
693
{
694
  assert(b < bitarr->num_of_bits);
695
  bit_array_assign(bitarr, b, c ? 1 : 0);
696
  DEBUG_VALIDATE(bitarr);
697
}
698

    
699
//
700
// Get, set etc with resize
701
//
702

    
703
// Get the value of a bit (returns 0 or 1)
704
char bit_array_rget(BIT_ARRAY* bitarr, bit_index_t b)
705
{
706
  bit_array_ensure_size_critical(bitarr, b+1);
707
  return bit_array_get(bitarr, b);
708
}
709

    
710
// set a bit (to 1) at position b
711
void bit_array_rset(BIT_ARRAY* bitarr, bit_index_t b)
712
{
713
  bit_array_ensure_size_critical(bitarr, b+1);
714
  bit_array_set(bitarr,b);
715
  DEBUG_VALIDATE(bitarr);
716
}
717

    
718
// clear a bit (to 0) at position b
719
void bit_array_rclear(BIT_ARRAY* bitarr, bit_index_t b)
720
{
721
  bit_array_ensure_size_critical(bitarr, b+1);
722
  bit_array_clear(bitarr, b);
723
  DEBUG_VALIDATE(bitarr);
724
}
725

    
726
// If bit is 0 -> 1, if bit is 1 -> 0.  AKA 'flip'
727
void bit_array_rtoggle(BIT_ARRAY* bitarr, bit_index_t b)
728
{
729
  bit_array_ensure_size_critical(bitarr, b+1);
730
  bit_array_toggle(bitarr, b);
731
  DEBUG_VALIDATE(bitarr);
732
}
733

    
734
// If char c != 0, set bit; otherwise clear bit
735
void bit_array_rassign(BIT_ARRAY* bitarr, bit_index_t b, char c)
736
{
737
  bit_array_ensure_size_critical(bitarr, b+1);
738
  bit_array_assign(bitarr, b, c ? 1 : 0);
739
  DEBUG_VALIDATE(bitarr);
740
}
741

    
742
//
743
// Set, clear and toggle several bits at once
744
//
745

    
746
// Set multiple bits at once.
747
// e.g. set bits 1, 20 & 31: bit_array_set_bits(bitarr, 3, 1,20,31);
748
void bit_array_set_bits(BIT_ARRAY* bitarr, size_t n, ...)
749
{
750
  size_t i;
751
  va_list argptr;
752
  va_start(argptr, n);
753

    
754
  for(i = 0; i < n; i++)
755
  {
756
    unsigned int bit_index = va_arg(argptr, unsigned int);
757
    bit_array_set_bit(bitarr, bit_index);
758
  }
759

    
760
  va_end(argptr);
761
  DEBUG_VALIDATE(bitarr);
762
}
763

    
764
// Clear multiple bits at once.
765
// e.g. clear bits 1, 20 & 31: bit_array_clear_bits(bitarr, 3, 1,20,31);
766
void bit_array_clear_bits(BIT_ARRAY* bitarr, size_t n, ...)
767
{
768
  size_t i;
769
  va_list argptr;
770
  va_start(argptr, n);
771

    
772
  for(i = 0; i < n; i++)
773
  {
774
    unsigned int bit_index = va_arg(argptr, unsigned int);
775
    bit_array_clear_bit(bitarr, bit_index);
776
  }
777

    
778
  va_end(argptr);
779
  DEBUG_VALIDATE(bitarr);
780
}
781

    
782
// Toggle multiple bits at once
783
// e.g. toggle bits 1, 20 & 31: bit_array_toggle_bits(bitarr, 3, 1,20,31);
784
void bit_array_toggle_bits(BIT_ARRAY* bitarr, size_t n, ...)
785
{
786
  size_t i;
787
  va_list argptr;
788
  va_start(argptr, n);
789

    
790
  for(i = 0; i < n; i++)
791
  {
792
    unsigned int bit_index = va_arg(argptr, unsigned int);
793
    bit_array_toggle_bit(bitarr, bit_index);
794
  }
795

    
796
  va_end(argptr);
797
  DEBUG_VALIDATE(bitarr);
798
}
799

    
800

    
801
//
802
// Set, clear and toggle all bits in a region
803
//
804

    
805
// Set all the bits in a region
806
void bit_array_set_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len)
807
{
808
  assert(start + len <= bitarr->num_of_bits);
809
  SET_REGION(bitarr, start, len);
810
  DEBUG_VALIDATE(bitarr);
811
}
812

    
813

    
814
// Clear all the bits in a region
815
void bit_array_clear_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len)
816
{
817
  assert(start + len <= bitarr->num_of_bits);
818
  CLEAR_REGION(bitarr, start, len);
819
  DEBUG_VALIDATE(bitarr);
820
}
821

    
822
// Toggle all the bits in a region
823
void bit_array_toggle_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len)
824
{
825
  assert(start + len <= bitarr->num_of_bits);
826
  TOGGLE_REGION(bitarr, start, len);
827
  DEBUG_VALIDATE(bitarr);
828
}
829

    
830

    
831
//
832
// Set, clear and toggle all bits at once
833
//
834

    
835
// set all elements of data to one
836
void bit_array_set_all(BIT_ARRAY* bitarr)
837
{
838
  bit_index_t num_of_bytes = bitarr->num_of_words * sizeof(word_t);
839
  memset(bitarr->words, 0xFF, num_of_bytes);
840
  _mask_top_word(bitarr);
841
  DEBUG_VALIDATE(bitarr);
842
}
843

    
844
// set all elements of data to zero
845
void bit_array_clear_all(BIT_ARRAY* bitarr)
846
{
847
  memset(bitarr->words, 0, bitarr->num_of_words * sizeof(word_t));
848
  DEBUG_VALIDATE(bitarr);
849
}
850

    
851
// Set all 1 bits to 0, and all 0 bits to 1. AKA flip
852
void bit_array_toggle_all(BIT_ARRAY* bitarr)
853
{
854
  word_addr_t i;
855
  for(i = 0; i < bitarr->num_of_words; i++)
856
  {
857
    bitarr->words[i] ^= WORD_MAX;
858
  }
859

    
860
  _mask_top_word(bitarr);
861
  DEBUG_VALIDATE(bitarr);
862
}
863

    
864
//
865
// Get a word at a time
866
//
867

    
868
uint64_t bit_array_get_word64(const BIT_ARRAY* bitarr, bit_index_t start)
869
{
870
  assert(start < bitarr->num_of_bits);
871
  return (uint64_t)_get_word(bitarr, start);
872
}
873

    
874
uint32_t bit_array_get_word32(const BIT_ARRAY* bitarr, bit_index_t start)
875
{
876
  assert(start < bitarr->num_of_bits);
877
  return (uint32_t)_get_word(bitarr, start);
878
}
879

    
880
uint16_t bit_array_get_word16(const BIT_ARRAY* bitarr, bit_index_t start)
881
{
882
  assert(start < bitarr->num_of_bits);
883
  return (uint16_t)_get_word(bitarr, start);
884
}
885

    
886
uint8_t bit_array_get_word8(const BIT_ARRAY* bitarr, bit_index_t start)
887
{
888
  assert(start < bitarr->num_of_bits);
889
  return (uint8_t)_get_word(bitarr, start);
890
}
891

    
892
uint64_t bit_array_get_wordn(const BIT_ARRAY* bitarr, bit_index_t start, int n)
893
{
894
  assert(start < bitarr->num_of_bits);
895
  assert(n <= 64);
896
  return (uint64_t)(_get_word(bitarr, start) & bitmask64(n));
897
}
898

    
899
//
900
// Set a word at a time
901
//
902

    
903
void bit_array_set_word64(BIT_ARRAY* bitarr, bit_index_t start, uint64_t word)
904
{
905
  assert(start < bitarr->num_of_bits);
906
  _set_word(bitarr, start, (word_t)word);
907
}
908

    
909
void bit_array_set_word32(BIT_ARRAY* bitarr, bit_index_t start, uint32_t word)
910
{
911
  assert(start < bitarr->num_of_bits);
912
  word_t w = _get_word(bitarr, start);
913
  _set_word(bitarr, start, (w & ~(word_t)0xffffffff) | word);
914
}
915

    
916
void bit_array_set_word16(BIT_ARRAY* bitarr, bit_index_t start, uint16_t word)
917
{
918
  assert(start < bitarr->num_of_bits);
919
  word_t w = _get_word(bitarr, start);
920
  _set_word(bitarr, start, (w & ~(word_t)0xffff) | word);
921
}
922

    
923
void bit_array_set_word8(BIT_ARRAY* bitarr, bit_index_t start, uint8_t byte)
924
{
925
  assert(start < bitarr->num_of_bits);
926
  _set_byte(bitarr, start, byte);
927
}
928

    
929
void bit_array_set_wordn(BIT_ARRAY* bitarr, bit_index_t start, uint64_t word, int n)
930
{
931
  assert(start < bitarr->num_of_bits);
932
  assert(n <= 64);
933
  word_t w = _get_word(bitarr, start), m = bitmask64(n);
934
  _set_word(bitarr, start, bitmask_merge(word,w,m));
935
}
936

    
937
//
938
// Number of bits set
939
//
940

    
941
// Get the number of bits set (hamming weight)
942
bit_index_t bit_array_num_bits_set(const BIT_ARRAY* bitarr)
943
{
944
  word_addr_t i;
945

    
946
  bit_index_t num_of_bits_set = 0;
947

    
948
  for(i = 0; i < bitarr->num_of_words; i++)
949
  {
950
    if(bitarr->words[i] > 0)
951
    {
952
      num_of_bits_set += POPCOUNT(bitarr->words[i]);
953
    }
954
  }
955

    
956
  return num_of_bits_set;
957
}
958

    
959
// Get the number of bits not set (1 - hamming weight)
960
bit_index_t bit_array_num_bits_cleared(const BIT_ARRAY* bitarr)
961
{
962
  return bitarr->num_of_bits - bit_array_num_bits_set(bitarr);
963
}
964

    
965

    
966
// Get the number of bits set in on array and not the other.  This is equivalent
967
// to hamming weight of the XOR when the two arrays are the same length.
968
// e.g. 10101 vs 00111 => hamming distance 2 (XOR is 10010)
969
bit_index_t bit_array_hamming_distance(const BIT_ARRAY* arr1,
970
                                       const BIT_ARRAY* arr2)
971
{
972
  word_addr_t min_words = MIN(arr1->num_of_words, arr2->num_of_words);
973
  word_addr_t max_words = MAX(arr1->num_of_words, arr2->num_of_words);
974

    
975
  bit_index_t hamming_distance = 0;
976
  word_addr_t i;
977

    
978
  for(i = 0; i < min_words; i++)
979
  {
980
    hamming_distance += POPCOUNT(arr1->words[i] ^ arr2->words[i]);
981
  }
982

    
983
  if(min_words != max_words)
984
  {
985
    const BIT_ARRAY* long_arr
986
      = (arr1->num_of_words > arr2->num_of_words ? arr1 : arr2);
987

    
988
    for(i = min_words; i < max_words; i++)
989
    {
990
      hamming_distance += POPCOUNT(long_arr->words[i]);
991
    }
992
  }
993

    
994
  return hamming_distance;
995
}
996

    
997
// Parity - returns 1 if odd number of bits set, 0 if even
998
char bit_array_parity(const BIT_ARRAY* bitarr)
999
{
1000
  word_addr_t w;
1001
  unsigned int parity = 0;
1002

    
1003
  for(w = 0; w < bitarr->num_of_words; w++)
1004
  {
1005
    parity ^= PARITY(bitarr->words[w]);
1006
  }
1007

    
1008
  return (char)parity;
1009
}
1010

    
1011
//
1012
// Find indices of set/clear bits
1013
//
1014

    
1015
// Find the index of the next bit that is set/clear, at or after `offset`
1016
// Returns 1 if such a bit is found, otherwise 0
1017
// Index is stored in the integer pointed to by `result`
1018
// If no such bit is found, value at `result` is not changed
1019
#define _next_bit_func_def(FUNC,GET) \
1020
char FUNC(const BIT_ARRAY* bitarr, bit_index_t offset, bit_index_t* result) \
1021
{ \
1022
  assert(offset < bitarr->num_of_bits); \
1023
  if(bitarr->num_of_bits == 0 || offset >= bitarr->num_of_bits) { return 0; } \
1024
 \
1025
  /* Find first word that is greater than zero */ \
1026
  word_addr_t i = bitset64_wrd(offset); \
1027
  word_t w = GET(bitarr->words[i]) & ~bitmask64(bitset64_idx(offset)); \
1028
 \
1029
  while(1) { \
1030
    if(w > 0) { \
1031
      bit_index_t pos = i * WORD_SIZE + trailing_zeros(w); \
1032
      if(pos < bitarr->num_of_bits) { *result = pos; return 1; } \
1033
      else { return 0; } \
1034
    } \
1035
    i++; \
1036
    if(i >= bitarr->num_of_words) break; \
1037
    w = GET(bitarr->words[i]); \
1038
  } \
1039
 \
1040
  return 0; \
1041
}
1042

    
1043
// Find the index of the previous bit that is set/clear, before `offset`.
1044
// Returns 1 if such a bit is found, otherwise 0
1045
// Index is stored in the integer pointed to by `result`
1046
// If no such bit is found, value at `result` is not changed
1047
#define _prev_bit_func_def(FUNC,GET) \
1048
char FUNC(const BIT_ARRAY* bitarr, bit_index_t offset, bit_index_t* result) \
1049
{ \
1050
  assert(offset <= bitarr->num_of_bits); \
1051
  if(bitarr->num_of_bits == 0 || offset == 0) { return 0; } \
1052
 \
1053
  /* Find prev word that is greater than zero */ \
1054
  word_addr_t i = bitset64_wrd(offset-1); \
1055
  word_t w = GET(bitarr->words[i]) & bitmask64(bitset64_idx(offset-1)+1); \
1056
 \
1057
  if(w > 0) { *result = (i+1) * WORD_SIZE - leading_zeros(w) - 1; return 1; } \
1058
 \
1059
  /* i is unsigned so have to use break when i == 0 */ \
1060
  for(--i; i != BIT_INDEX_MAX; i--) { \
1061
    w = GET(bitarr->words[i]); \
1062
    if(w > 0) { \
1063
      *result = (i+1) * WORD_SIZE - leading_zeros(w) - 1; \
1064
      return 1; \
1065
    } \
1066
  } \
1067
 \
1068
  return 0; \
1069
}
1070

    
1071
#define GET_WORD(x) (x)
1072
#define NEG_WORD(x) (~(x))
1073
_next_bit_func_def(bit_array_find_next_set_bit,  GET_WORD);
1074
_next_bit_func_def(bit_array_find_next_clear_bit,NEG_WORD);
1075
_prev_bit_func_def(bit_array_find_prev_set_bit,  GET_WORD);
1076
_prev_bit_func_def(bit_array_find_prev_clear_bit,NEG_WORD);
1077

    
1078
// Find the index of the first bit that is set.
1079
// Returns 1 if a bit is set, otherwise 0
1080
// Index of first set bit is stored in the integer pointed to by result
1081
// If no bits are set, value at `result` is not changed
1082
char bit_array_find_first_set_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
1083
{
1084
  return bit_array_find_next_set_bit(bitarr, 0, result);
1085
}
1086

    
1087
// same same
1088
char bit_array_find_first_clear_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
1089
{
1090
  return bit_array_find_next_clear_bit(bitarr, 0, result);
1091
}
1092

    
1093
// Find the index of the last bit that is set.
1094
// Returns 1 if a bit is set, otherwise 0
1095
// Index of last set bit is stored in the integer pointed to by `result`
1096
// If no bits are set, value at `result` is not changed
1097
char bit_array_find_last_set_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
1098
{
1099
  return bit_array_find_prev_set_bit(bitarr, bitarr->num_of_bits, result);
1100
}
1101

    
1102
// same same
1103
char bit_array_find_last_clear_bit(const BIT_ARRAY* bitarr, bit_index_t* result)
1104
{
1105
  return bit_array_find_prev_clear_bit(bitarr, bitarr->num_of_bits, result);
1106
}
1107

    
1108
//
1109
// "Sorting" bits
1110
//
1111

    
1112
// Put all the 0s before all the 1s
1113
void bit_array_sort_bits(BIT_ARRAY* bitarr)
1114
{
1115
  bit_index_t num_of_bits_set = bit_array_num_bits_set(bitarr);
1116
  bit_index_t num_of_bits_cleared = bitarr->num_of_bits - num_of_bits_set;
1117
  bit_array_set_all(bitarr);
1118
  CLEAR_REGION(bitarr, 0, num_of_bits_cleared);
1119
  DEBUG_VALIDATE(bitarr);
1120
}
1121

    
1122
// Put all the 1s before all the 0s
1123
void bit_array_sort_bits_rev(BIT_ARRAY* bitarr)
1124
{
1125
  bit_index_t num_of_bits_set = bit_array_num_bits_set(bitarr);
1126
  bit_array_clear_all(bitarr);
1127
  SET_REGION(bitarr, 0, num_of_bits_set);
1128
  DEBUG_VALIDATE(bitarr);
1129
}
1130

    
1131

    
1132
//
1133
// Strings and printing
1134
//
1135

    
1136
// Construct a BIT_ARRAY from a substring with given on and off characters.
1137
void bit_array_from_substr(BIT_ARRAY* bitarr, bit_index_t offset,
1138
                           const char *str, size_t len,
1139
                           const char *on, const char *off,
1140
                           char left_to_right)
1141
{
1142
  bit_array_ensure_size(bitarr, offset + len);
1143
  bit_array_clear_region(bitarr, offset, len);
1144

    
1145
  // BitArray region is now all 0s -- just set the 1s
1146
  size_t i;
1147
  bit_index_t j;
1148

    
1149
  for(i = 0; i < len; i++)
1150
  {
1151
    if(strchr(on, str[i]) != NULL)
1152
    {
1153
      j = offset + (left_to_right ? i : len - i - 1);
1154
      bit_array_set(bitarr, j);
1155
    }
1156
    else { assert(strchr(off, str[i]) != NULL); }
1157
  }
1158

    
1159
  DEBUG_VALIDATE(bitarr);
1160
}
1161

    
1162
// From string method
1163
void bit_array_from_str(BIT_ARRAY* bitarr, const char* str)
1164
{
1165
  bit_array_from_substr(bitarr, 0, str, strlen(str), "1", "0", 1);
1166
}
1167

    
1168
// Takes a char array to write to.  `str` must be bitarr->num_of_bits+1 in length
1169
// Terminates string with '\0'
1170
char* bit_array_to_str(const BIT_ARRAY* bitarr, char* str)
1171
{
1172
  bit_index_t i;
1173

    
1174
  for(i = 0; i < bitarr->num_of_bits; i++)
1175
  {
1176
    str[i] = bit_array_get(bitarr, i) ? '1' : '0';
1177
  }
1178

    
1179
  str[bitarr->num_of_bits] = '\0';
1180

    
1181
  return str;
1182
}
1183

    
1184
char* bit_array_to_str_rev(const BIT_ARRAY* bitarr, char* str)
1185
{
1186
  bit_index_t i;
1187

    
1188
  for(i = 0; i < bitarr->num_of_bits; i++)
1189
  {
1190
    str[i] = bit_array_get(bitarr, bitarr->num_of_bits-i-1) ? '1' : '0';
1191
  }
1192

    
1193
  str[bitarr->num_of_bits] = '\0';
1194

    
1195
  return str;
1196
}
1197

    
1198

    
1199
// Get a string representations for a given region, using given on/off characters.
1200
// Note: does not null-terminate
1201
void bit_array_to_substr(const BIT_ARRAY* bitarr,
1202
                         bit_index_t start, bit_index_t length,
1203
                         char* str, char on, char off,
1204
                         char left_to_right)
1205
{
1206
  assert(start + length <= bitarr->num_of_bits);
1207

    
1208
  bit_index_t i, j;
1209
  bit_index_t end = start + length - 1;
1210

    
1211
  for(i = 0; i < length; i++)
1212
  {
1213
    j = (left_to_right ? start + i : end - i);
1214
    str[i] = bit_array_get(bitarr, j) ? on : off;
1215
  }
1216

    
1217
//  str[length] = '\0';
1218
}
1219

    
1220
// Print this array to a file stream.  Prints '0's and '1'.  Doesn't print newline.
1221
void bit_array_print(const BIT_ARRAY* bitarr, FILE* fout)
1222
{
1223
  bit_index_t i;
1224

    
1225
  for(i = 0; i < bitarr->num_of_bits; i++)
1226
  {
1227
    fprintf(fout, "%c", bit_array_get(bitarr, i) ? '1' : '0');
1228
  }
1229
}
1230

    
1231
// Print a string representations for a given region, using given on/off characters.
1232
void bit_array_print_substr(const BIT_ARRAY* bitarr,
1233
                            bit_index_t start, bit_index_t length,
1234
                            FILE* fout, char on, char off,
1235
                            char left_to_right)
1236
{
1237
  assert(start + length <= bitarr->num_of_bits);
1238

    
1239
  bit_index_t i, j;
1240
  bit_index_t end = start + length - 1;
1241

    
1242
  for(i = 0; i < length; i++)
1243
  {
1244
    j = (left_to_right ? start + i : end - i);
1245
    fprintf(fout, "%c", bit_array_get(bitarr, j) ? on : off);
1246
  }
1247
}
1248

    
1249
//
1250
// Decimal
1251
//
1252

    
1253
// Get bit array as decimal str (e.g. 0b1101 -> "13")
1254
// len is the length of str char array -- will write at most len-1 chars
1255
// returns the number of characters needed
1256
// return is the same as strlen(str)
1257
size_t bit_array_to_decimal(const BIT_ARRAY *bitarr, char *str, size_t len)
1258
{
1259
  size_t i = 0;
1260

    
1261
  if(bit_array_cmp_uint64(bitarr, 0) == 0)
1262
  {
1263
    if(len >= 2)
1264
    {
1265
      *str = '0';
1266
      *(str+1) = '\0';
1267
    }
1268

    
1269
    return 1;
1270
  }
1271

    
1272
  BIT_ARRAY *tmp = bit_array_clone(bitarr);
1273
  uint64_t rem;
1274

    
1275
  str[len-1] = '\0';
1276

    
1277
  while(bit_array_cmp_uint64(tmp, 0) != 0)
1278
  {
1279
    bit_array_div_uint64(tmp, 10, &rem);
1280

    
1281
    if(i < len-1)
1282
    {
1283
      str[len-2-i] = '0' + rem;
1284
    }
1285

    
1286
    i++;
1287
  }
1288

    
1289
  if(i < len-1)
1290
  {
1291
    // Moves null-terminator as well
1292
    memmove(str, str+len-i-1, i+1);
1293
  }
1294

    
1295
  bit_array_free(tmp);
1296

    
1297
  return i;
1298
}
1299

    
1300
// Get bit array from decimal str (e.g. "13" -> 0b1101)
1301
// Returns number of characters used
1302
size_t bit_array_from_decimal(BIT_ARRAY *bitarr, const char* decimal)
1303
{
1304
  bit_array_clear_all(bitarr);
1305
  size_t i = 0;
1306

    
1307
  if(decimal[0] == '\0' || decimal[0] < '0' || decimal[0] > '9')
1308
  {
1309
    return 0;
1310
  }
1311

    
1312
  bit_array_add_uint64(bitarr, decimal[i] - '0');
1313
  i++;
1314

    
1315
  while(decimal[i] != '\0' && decimal[i] >= '0' && decimal[i] <= '9')
1316
  {
1317
    bit_array_mul_uint64(bitarr, 10);
1318
    bit_array_add_uint64(bitarr, decimal[i] - '0');
1319
    i++;
1320
  }
1321

    
1322
  return i;
1323
}
1324

    
1325
//
1326
// Hexidecimal
1327
//
1328

    
1329
char bit_array_hex_to_nibble(char c, uint8_t *b)
1330
{
1331
  c = tolower(c);
1332

    
1333
  if(c >= '0' && c <= '9')
1334
  {
1335
    *b = c - '0';
1336
    return 1;
1337
  }
1338
  else if(c >= 'a' && c <= 'f')
1339
  {
1340
    *b = 0xa + (c - 'a');
1341
    return 1;
1342
  }
1343
  else
1344
  {
1345
    return 0;
1346
  }
1347
}
1348

    
1349
char bit_array_nibble_to_hex(uint8_t b, char uppercase)
1350
{
1351
  if(b <= 9)
1352
  {
1353
    return '0' + b;
1354
  }
1355
  else
1356
  {
1357
    return (uppercase ? 'A' : 'a') + (b - 0xa);
1358
  }
1359
}
1360

    
1361
// Loads array from hex string
1362
// Returns the number of bits loaded (will be chars rounded up to multiple of 4)
1363
// (0 on failure)
1364
bit_index_t bit_array_from_hex(BIT_ARRAY* bitarr, bit_index_t offset,
1365
                               const char* str, size_t len)
1366
{
1367
  if(str[0] == '0' && tolower(str[1]) == 'x')
1368
  {
1369
    str += 2;
1370
    len -= 2;
1371
  }
1372

    
1373
  size_t i;
1374
  for(i = 0; i < len; i++, offset += 4)
1375
  {
1376
    uint8_t b;
1377
    if(bit_array_hex_to_nibble(str[i], &b))
1378
    {
1379
      bit_array_ensure_size(bitarr, offset + 4);
1380
      _set_nibble(bitarr, offset, b);
1381
    }
1382
    else
1383
    {
1384
      break;
1385
    }
1386
  }
1387

    
1388
  return 4 * i;
1389
}
1390

    
1391
// Returns number of characters written
1392
size_t bit_array_to_hex(const BIT_ARRAY* bitarr,
1393
                        bit_index_t start, bit_index_t length,
1394
                        char* str, char uppercase)
1395
{
1396
  assert(start + length <= bitarr->num_of_bits);
1397

    
1398
  size_t k = 0;
1399
  bit_index_t offset, end = start + length;
1400

    
1401
  for(offset = start; offset + WORD_SIZE <= end; offset += WORD_SIZE)
1402
  {
1403
    word_t w = _get_word(bitarr, offset);
1404

    
1405
    word_offset_t j;
1406
    for(j = 0; j < 64; j += 4)
1407
    {
1408
      str[k++] = bit_array_nibble_to_hex((w>>j) & 0xf, uppercase);
1409
    }
1410
  }
1411

    
1412
  if(offset < end)
1413
  {
1414
    // Remaining full nibbles (4 bits)
1415
    word_t w = _get_word(bitarr, offset);
1416

    
1417
    for(; offset + 4 <= end; offset += 4)
1418
    {
1419
      str[k++] = bit_array_nibble_to_hex(w & 0xf, uppercase);
1420
      w >>= 4;
1421
    }
1422

    
1423
    if(offset < end)
1424
    {
1425
      // Remaining bits
1426
      str[k++] = bit_array_nibble_to_hex(w & bitmask64(end - offset), uppercase);
1427
    }
1428
  }
1429

    
1430
  str[k] = '\0';
1431

    
1432
  // Return number of characters written
1433
  return k;
1434
}
1435

    
1436
// Print bit array as hex
1437
size_t bit_array_print_hex(const BIT_ARRAY* bitarr,
1438
                           bit_index_t start, bit_index_t length,
1439
                           FILE* fout, char uppercase)
1440
{
1441
  assert(start + length <= bitarr->num_of_bits);
1442

    
1443
  size_t k = 0;
1444
  bit_index_t offset, end = start + length;
1445

    
1446
  for(offset = start; offset + WORD_SIZE <= end; offset += WORD_SIZE)
1447
  {
1448
    word_t w = _get_word(bitarr, offset);
1449

    
1450
    word_offset_t j;
1451
    for(j = 0; j < 64; j += 4)
1452
    {
1453
      fprintf(fout, "%c", bit_array_nibble_to_hex((w>>j) & 0xf, uppercase));
1454
      k++;
1455
    }
1456
  }
1457

    
1458
  if(offset < end)
1459
  {
1460
    // Remaining full nibbles (4 bits)
1461
    word_t w = _get_word(bitarr, offset);
1462

    
1463
    for(; offset + 4 <= end; offset += 4)
1464
    {
1465
      fprintf(fout, "%c", bit_array_nibble_to_hex(w & 0xf, uppercase));
1466
      w >>= 4;
1467
      k++;
1468
    }
1469

    
1470
    if(offset < end)
1471
    {
1472
      // Remaining bits
1473
      char hex = bit_array_nibble_to_hex(w & bitmask64(end - offset), uppercase);
1474
      fprintf(fout, "%c", hex);
1475
      k++;
1476
    }
1477
  }
1478

    
1479
  return k;
1480
}
1481

    
1482
//
1483
// Clone and copy
1484
//
1485

    
1486
// Returns NULL if cannot malloc
1487
BIT_ARRAY* bit_array_clone(const BIT_ARRAY* bitarr)
1488
{
1489
  BIT_ARRAY* cpy = bit_array_create(bitarr->num_of_bits);
1490

    
1491
  if(cpy == NULL)
1492
  {
1493
    return NULL;
1494
  }
1495

    
1496
  // Copy across bits
1497
  memcpy(cpy->words, bitarr->words, bitarr->num_of_words * sizeof(word_t));
1498

    
1499
  DEBUG_VALIDATE(cpy);
1500
  return cpy;
1501
}
1502

    
1503
// destination and source may be the same bit_array
1504
// and src/dst regions may overlap
1505
static void _array_copy(BIT_ARRAY* dst, bit_index_t dstindx,
1506
                        const BIT_ARRAY* src, bit_index_t srcindx,
1507
                        bit_index_t length)
1508
{
1509
  DEBUG_PRINT("bit_array_copy(dst: %zu, src: %zu, length: %zu)\n",
1510
              (size_t)dstindx, (size_t)srcindx, (size_t)length);
1511

    
1512
  // Num of full words to copy
1513
  word_addr_t num_of_full_words = length / WORD_SIZE;
1514
  word_addr_t i;
1515

    
1516
  word_offset_t bits_in_last_word = bits_in_top_word(length);
1517

    
1518
  if(dst == src && srcindx > dstindx)
1519
  {
1520
    // Work left to right
1521
    DEBUG_PRINT("work left to right\n");
1522

    
1523
    for(i = 0; i < num_of_full_words; i++)
1524
    {
1525
      word_t word = _get_word(src, srcindx+i*WORD_SIZE);
1526
      _set_word(dst, dstindx+i*WORD_SIZE, word);
1527
    }
1528

    
1529
    if(bits_in_last_word > 0)
1530
    {
1531
      word_t src_word = _get_word(src, srcindx+i*WORD_SIZE);
1532
      word_t dst_word = _get_word(dst, dstindx+i*WORD_SIZE);
1533

    
1534
      word_t mask = bitmask64(bits_in_last_word);
1535
      word_t word = bitmask_merge(src_word, dst_word, mask);
1536

    
1537
      _set_word(dst, dstindx+num_of_full_words*WORD_SIZE, word);
1538
    }
1539
  }
1540
  else
1541
  {
1542
    // Work right to left
1543
    DEBUG_PRINT("work right to left\n");
1544

    
1545
    for(i = 0; i < num_of_full_words; i++)
1546
    {
1547
      word_t word = _get_word(src, srcindx+length-(i+1)*WORD_SIZE);
1548
      _set_word(dst, dstindx+length-(i+1)*WORD_SIZE, word);
1549
    }
1550

    
1551
    DEBUG_PRINT("Copy %i,%i to %i\n", (int)srcindx, (int)bits_in_last_word,
1552
                                      (int)dstindx);
1553

    
1554
    if(bits_in_last_word > 0)
1555
    {
1556
      word_t src_word = _get_word(src, srcindx);
1557
      word_t dst_word = _get_word(dst, dstindx);
1558

    
1559
      word_t mask = bitmask64(bits_in_last_word);
1560
      word_t word = bitmask_merge(src_word, dst_word, mask);
1561
      _set_word(dst, dstindx, word);
1562
    }
1563
  }
1564

    
1565
  _mask_top_word(dst);
1566
}
1567

    
1568
// destination and source may be the same bit_array
1569
// and src/dst regions may overlap
1570
void bit_array_copy(BIT_ARRAY* dst, bit_index_t dstindx,
1571
                    const BIT_ARRAY* src, bit_index_t srcindx,
1572
                    bit_index_t length)
1573
{
1574
  assert(srcindx + length <= src->num_of_bits);
1575
  assert(dstindx <= dst->num_of_bits);
1576
  _array_copy(dst, dstindx, src, srcindx, length);
1577
  DEBUG_VALIDATE(dst);
1578
}
1579

    
1580
// Clone `src` into `dst`. Resizes `dst`.
1581
void bit_array_copy_all(BIT_ARRAY* dst, const BIT_ARRAY* src)
1582
{
1583
  bit_array_resize_critical(dst, src->num_of_bits);
1584
  memmove(dst->words, src->words, src->num_of_words * sizeof(word_t));
1585
  DEBUG_VALIDATE(dst);
1586
}
1587

    
1588

    
1589
//
1590
// Logic operators
1591
//
1592

    
1593
// Destination can be the same as one or both of the sources
1594
void bit_array_and(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2)
1595
{
1596
  // Ensure dst array is big enough
1597
  word_addr_t max_bits = MAX(src1->num_of_bits, src2->num_of_bits);
1598
  bit_array_ensure_size_critical(dst, max_bits);
1599

    
1600
  word_addr_t min_words = MIN(src1->num_of_words, src2->num_of_words);
1601

    
1602
  word_addr_t i;
1603

    
1604
  for(i = 0; i < min_words; i++)
1605
  {
1606
    dst->words[i] = src1->words[i] & src2->words[i];
1607
  }
1608

    
1609
  // Set remaining bits to zero
1610
  for(i = min_words; i < dst->num_of_words; i++)
1611
  {
1612
    dst->words[i] = (word_t)0;
1613
  }
1614

    
1615
  DEBUG_VALIDATE(dst);
1616
}
1617

    
1618
// Destination can be the same as one or both of the sources
1619
static void _logical_or_xor(BIT_ARRAY* dst,
1620
                            const BIT_ARRAY* src1,
1621
                            const BIT_ARRAY* src2,
1622
                            char use_xor)
1623
{
1624
  // Ensure dst array is big enough
1625
  bit_array_ensure_size_critical(dst, MAX(src1->num_of_bits, src2->num_of_bits));
1626

    
1627
  word_addr_t min_words = MIN(src1->num_of_words, src2->num_of_words);
1628
  word_addr_t max_words = MAX(src1->num_of_words, src2->num_of_words);
1629

    
1630
  word_addr_t i;
1631

    
1632
  if(use_xor)
1633
  {
1634
    for(i = 0; i < min_words; i++)
1635
      dst->words[i] = src1->words[i] ^ src2->words[i];
1636
  }
1637
  else
1638
  {
1639
    for(i = 0; i < min_words; i++)
1640
      dst->words[i] = src1->words[i] | src2->words[i];
1641
  }
1642

    
1643
  // Copy remaining bits from longer src array
1644
  if(min_words != max_words)
1645
  {
1646
    const BIT_ARRAY* longer = src1->num_of_words > src2->num_of_words ? src1 : src2;
1647

    
1648
    for(i = min_words; i < max_words; i++)
1649
    {
1650
      dst->words[i] = longer->words[i];
1651
    }
1652
  }
1653

    
1654
  // Set remaining bits to zero
1655
  size_t size = (dst->num_of_words - max_words) * sizeof(word_t);
1656
  memset(dst->words + max_words, 0, size);
1657

    
1658
  DEBUG_VALIDATE(dst);
1659
}
1660

    
1661
void bit_array_or(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2)
1662
{
1663
  _logical_or_xor(dst, src1, src2, 0);
1664
}
1665

    
1666
// Destination can be the same as one or both of the sources
1667
void bit_array_xor(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2)
1668
{
1669
  _logical_or_xor(dst, src1, src2, 1);
1670
}
1671

    
1672
// If dst is longer than src, top bits are set to 1
1673
void bit_array_not(BIT_ARRAY* dst, const BIT_ARRAY* src)
1674
{
1675
  bit_array_ensure_size_critical(dst, src->num_of_bits);
1676

    
1677
  word_addr_t i;
1678

    
1679
  for(i = 0; i < src->num_of_words; i++)
1680
  {
1681
    dst->words[i] = ~(src->words[i]);
1682
  }
1683

    
1684
  // Set remaining words to 1s
1685
  for(i = src->num_of_words; i < dst->num_of_words; i++)
1686
  {
1687
    dst->words[i] = WORD_MAX;
1688
  }
1689

    
1690
  _mask_top_word(dst);
1691

    
1692
  DEBUG_VALIDATE(dst);
1693
}
1694

    
1695
//
1696
// Comparisons
1697
//
1698

    
1699
// Compare two bit arrays by value stored, with index 0 being the Least
1700
// Significant Bit (LSB). Arrays do not have to be the same length.
1701
// Example: ..0101 (5) > ...0011 (3) [index 0 is LSB at right hand side]
1702
// Sorts on length if all zeros: (0,0) < (0,0,0)
1703
// returns:
1704
//  >0 iff bitarr1 > bitarr2
1705
//   0 iff bitarr1 == bitarr2
1706
//  <0 iff bitarr1 < bitarr2
1707
int bit_array_cmp(const BIT_ARRAY* bitarr1, const BIT_ARRAY* bitarr2)
1708
{
1709
  word_addr_t i;
1710
  word_t word1, word2;
1711
  word_addr_t min_words = bitarr1->num_of_words;
1712

    
1713
  // i is unsigned so break when i == 0
1714
  if(bitarr1->num_of_words > bitarr2->num_of_words) {
1715
    min_words = bitarr2->num_of_words;
1716
    for(i = bitarr1->num_of_words-1; ; i--) {
1717
      if(bitarr1->words[i]) return 1;
1718
      if(i == bitarr2->num_of_words) break;
1719
    }
1720
  }
1721
  else if(bitarr1->num_of_words < bitarr2->num_of_words) {
1722
    for(i = bitarr2->num_of_words-1; ; i--) {
1723
      if(bitarr2->words[i]) return 1;
1724
      if(i == bitarr1->num_of_words) break;
1725
    }
1726
  }
1727

    
1728
  if(min_words == 0) return 0;
1729

    
1730
  for(i = min_words-1; ; i--)
1731
  {
1732
    word1 = bitarr1->words[i];
1733
    word2 = bitarr2->words[i];
1734
    if(word1 != word2) return (word1 > word2 ? 1 : -1);
1735
    if(i == 0) break;
1736
  }
1737

    
1738
  if(bitarr1->num_of_bits == bitarr2->num_of_bits) return 0;
1739
  return bitarr1->num_of_bits > bitarr2->num_of_bits ? 1 : -1;
1740
}
1741

    
1742
// Compare two bit arrays by value stored, with index 0 being the Most
1743
// Significant Bit (MSB). Arrays do not have to be the same length.
1744
// Example: 10.. > 01.. [index 0 is MSB at left hand side]
1745
// Sorts on length if all zeros: (0,0) < (0,0,0)
1746
// returns:
1747
//  >0 iff bitarr1 > bitarr2
1748
//   0 iff bitarr1 == bitarr2
1749
//  <0 iff bitarr1 < bitarr2
1750
int bit_array_cmp_big_endian(const BIT_ARRAY* bitarr1, const BIT_ARRAY* bitarr2)
1751
{
1752
  word_addr_t min_words = MAX(bitarr1->num_of_words, bitarr2->num_of_words);
1753

    
1754
  word_addr_t i;
1755
  word_t word1, word2;
1756

    
1757
  for(i = 0; i < min_words; i++) {
1758
    word1 = _reverse_word(bitarr1->words[i]);
1759
    word2 = _reverse_word(bitarr2->words[i]);
1760
    if(word1 != word2) return (word1 > word2 ? 1 : -1);
1761
  }
1762

    
1763
  // Check remaining words. Only one of these loops will execute
1764
  for(; i < bitarr1->num_of_words; i++)
1765
    if(bitarr1->words[i]) return 1;
1766
  for(; i < bitarr2->num_of_words; i++)
1767
    if(bitarr2->words[i]) return -1;
1768

    
1769
  if(bitarr1->num_of_bits == bitarr2->num_of_bits) return 0;
1770
  return bitarr1->num_of_bits > bitarr2->num_of_bits ? 1 : -1;
1771
}
1772

    
1773
// compare bitarr with (bitarr2 << pos)
1774
// bit_array_cmp(bitarr1, bitarr2<<pos)
1775
// returns:
1776
//  >0 iff bitarr1 > bitarr2
1777
//   0 iff bitarr1 == bitarr2
1778
//  <0 iff bitarr1 < bitarr2
1779
int bit_array_cmp_words(const BIT_ARRAY *arr1,
1780
                        bit_index_t pos, const BIT_ARRAY *arr2)
1781
{
1782
  if(arr1->num_of_bits == 0 && arr2->num_of_bits == 0)
1783
  {
1784
    return 0;
1785
  }
1786

    
1787
  bit_index_t top_bit1 = 0, top_bit2 = 0;
1788

    
1789
  char arr1_zero = !bit_array_find_last_set_bit(arr1, &top_bit1);
1790
  char arr2_zero = !bit_array_find_last_set_bit(arr2, &top_bit2);
1791

    
1792
  if(arr1_zero && arr2_zero) return 0;
1793
  if(arr1_zero) return -1;
1794
  if(arr2_zero) return 1;
1795

    
1796
  bit_index_t top_bit2_offset = top_bit2 + pos;
1797

    
1798
  if(top_bit1 != top_bit2_offset) {
1799
    return top_bit1 > top_bit2_offset ? 1 : -1;
1800
  }
1801

    
1802
  word_addr_t i;
1803
  word_t word1, word2;
1804

    
1805
  for(i = top_bit2 / WORD_SIZE; i > 0; i--)
1806
  {
1807
    word1 = _get_word(arr1, pos + i * WORD_SIZE);
1808
    word2 = arr2->words[i];
1809

    
1810
    if(word1 > word2) return 1;
1811
    if(word1 < word2) return -1;
1812
  }
1813

    
1814
  word1 = _get_word(arr1, pos);
1815
  word2 = arr2->words[0];
1816

    
1817
  if(word1 > word2) return 1;
1818
  if(word1 < word2) return -1;
1819

    
1820
  // return 1 if arr1[0..pos] != 0, 0 otherwise
1821

    
1822
  // Whole words
1823
  word_addr_t num_words = pos / WORD_SIZE;
1824

    
1825
  for(i = 0; i < num_words; i++)
1826
  {
1827
    if(arr1->words[i] > 0)
1828
    {
1829
      return 1;
1830
    }
1831
  }
1832

    
1833
  word_offset_t bits_remaining = pos - num_words * WORD_SIZE;
1834

    
1835
  if(arr1->words[num_words] & bitmask64(bits_remaining))
1836
  {
1837
    return 1;
1838
  }
1839

    
1840
  return 0;
1841
}
1842

    
1843

    
1844
//
1845
// Reverse -- coords may wrap around
1846
//
1847

    
1848
// No bounds checking
1849
// length cannot be zero
1850
static void _reverse_region(BIT_ARRAY* bitarr,
1851
                            bit_index_t start,
1852
                            bit_index_t length)
1853
{
1854
  bit_index_t left = start;
1855
  bit_index_t right = (start + length - WORD_SIZE) % bitarr->num_of_bits;
1856

    
1857
  while(length >= 2 * WORD_SIZE)
1858
  {
1859
    // Swap entire words
1860
    word_t left_word = _get_word_cyclic(bitarr, left);
1861
    word_t right_word = _get_word_cyclic(bitarr, right);
1862

    
1863
    // reverse words individually
1864
    left_word = _reverse_word(left_word);
1865
    right_word = _reverse_word(right_word);
1866

    
1867
    // Swap
1868
    _set_word_cyclic(bitarr, left, right_word);
1869
    _set_word_cyclic(bitarr, right, left_word);
1870

    
1871
    // Update
1872
    left = (left + WORD_SIZE) % bitarr->num_of_bits;
1873
    right = (right < WORD_SIZE ? right + bitarr->num_of_bits : right) - WORD_SIZE;
1874
    length -= 2 * WORD_SIZE;
1875
  }
1876

    
1877
  word_t word, rev;
1878

    
1879
  if(length == 0)
1880
  {
1881
    return;
1882
  }
1883
  else if(length > WORD_SIZE)
1884
  {
1885
    // Words overlap
1886
    word_t left_word = _get_word_cyclic(bitarr, left);
1887
    word_t right_word = _get_word_cyclic(bitarr, right);
1888

    
1889
    rev = _reverse_word(left_word);
1890
    right_word = _reverse_word(right_word);
1891

    
1892
    // fill left 64 bits with right word rev
1893
    _set_word_cyclic(bitarr, left, right_word);
1894

    
1895
    // Now do remaining bits (length is between 1 and 64 bits)
1896
    left += WORD_SIZE;
1897
    length -= WORD_SIZE;
1898

    
1899
    word = _get_word_cyclic(bitarr, left);
1900
  }
1901
  else
1902
  {
1903
    word = _get_word_cyclic(bitarr, left);
1904
    rev = _reverse_word(word);
1905
  }
1906

    
1907
  rev >>= WORD_SIZE - length;
1908
  word_t mask = bitmask64(length);
1909

    
1910
  word = bitmask_merge(rev, word, mask);
1911

    
1912
  _set_word_cyclic(bitarr, left, word);
1913
}
1914

    
1915
void bit_array_reverse_region(BIT_ARRAY* bitarr, bit_index_t start, bit_index_t len)
1916
{
1917
  assert(start + len <= bitarr->num_of_bits);
1918
  if(len > 0) _reverse_region(bitarr, start, len);
1919
  DEBUG_VALIDATE(bitarr);
1920
}
1921

    
1922
void bit_array_reverse(BIT_ARRAY* bitarr)
1923
{
1924
  if(bitarr->num_of_bits > 0) _reverse_region(bitarr, 0, bitarr->num_of_bits);
1925
  DEBUG_VALIDATE(bitarr);
1926
}
1927

    
1928
//
1929
// Shift left / right
1930
//
1931

    
1932
// Shift towards MSB / higher index
1933
void bit_array_shift_left(BIT_ARRAY* bitarr, bit_index_t shift_dist, char fill)
1934
{
1935
  if(shift_dist >= bitarr->num_of_bits)
1936
  {
1937
    fill ? bit_array_set_all(bitarr) : bit_array_clear_all(bitarr);
1938
    return;
1939
  }
1940
  else if(shift_dist == 0)
1941
  {
1942
    return;
1943
  }
1944

    
1945
  FillAction action = fill ? FILL_REGION : ZERO_REGION;
1946

    
1947
  bit_index_t cpy_length = bitarr->num_of_bits - shift_dist;
1948
  _array_copy(bitarr, shift_dist, bitarr, 0, cpy_length);
1949
  _set_region(bitarr, 0, shift_dist, action);
1950
}
1951

    
1952
// shift left extend - don't truncate bits when shifting UP, instead
1953
// make room for them.
1954
void bit_array_shift_left_extend(BIT_ARRAY* bitarr, bit_index_t shift_dist,
1955
                                 char fill)
1956
{
1957
   bit_index_t newlen = bitarr->num_of_bits + shift_dist;
1958
   bit_index_t cpy_length = bitarr->num_of_bits;
1959

    
1960
  if(shift_dist == 0)
1961
  {
1962
    return;
1963
  }
1964

    
1965
  bit_array_resize_critical(bitarr, newlen);
1966

    
1967
  FillAction action = fill ? FILL_REGION : ZERO_REGION;
1968
  _array_copy(bitarr, shift_dist, bitarr, 0, cpy_length);
1969
  _set_region(bitarr, 0, shift_dist, action);
1970
}
1971

    
1972
// Shift towards LSB / lower index
1973
void bit_array_shift_right(BIT_ARRAY* bitarr, bit_index_t shift_dist, char fill)
1974
{
1975
  if(shift_dist >= bitarr->num_of_bits)
1976
  {
1977
    fill ? bit_array_set_all(bitarr) : bit_array_clear_all(bitarr);
1978
    return;
1979
  }
1980
  else if(shift_dist == 0)
1981
  {
1982
    return;
1983
  }
1984

    
1985
  FillAction action = fill ? FILL_REGION : ZERO_REGION;
1986

    
1987
  bit_index_t cpy_length = bitarr->num_of_bits - shift_dist;
1988
  bit_array_copy(bitarr, 0, bitarr, shift_dist, cpy_length);
1989

    
1990
  _set_region(bitarr, cpy_length, shift_dist, action);
1991
}
1992

    
1993
//
1994
// Cycle
1995
//
1996

    
1997
// Cycle towards index 0
1998
void bit_array_cycle_right(BIT_ARRAY* bitarr, bit_index_t cycle_dist)
1999
{
2000
  if(bitarr->num_of_bits == 0)
2001
  {
2002
    return;
2003
  }
2004

    
2005
  cycle_dist = cycle_dist % bitarr->num_of_bits;
2006

    
2007
  if(cycle_dist == 0)
2008
  {
2009
    return;
2010
  }
2011

    
2012
  bit_index_t len1 = cycle_dist;
2013
  bit_index_t len2 = bitarr->num_of_bits - cycle_dist;
2014

    
2015
  _reverse_region(bitarr, 0, len1);
2016
  _reverse_region(bitarr, len1, len2);
2017
  bit_array_reverse(bitarr);
2018
}
2019

    
2020
// Cycle away from index 0
2021
void bit_array_cycle_left(BIT_ARRAY* bitarr, bit_index_t cycle_dist)
2022
{
2023
  if(bitarr->num_of_bits == 0)
2024
  {
2025
    return;
2026
  }
2027

    
2028
  cycle_dist = cycle_dist % bitarr->num_of_bits;
2029

    
2030
  if(cycle_dist == 0)
2031
  {
2032
    return;
2033
  }
2034

    
2035
  bit_index_t len1 = bitarr->num_of_bits - cycle_dist;
2036
  bit_index_t len2 = cycle_dist;
2037

    
2038
  _reverse_region(bitarr, 0, len1);
2039
  _reverse_region(bitarr, len1, len2);
2040
  bit_array_reverse(bitarr);
2041
}
2042

    
2043
//
2044
// Next permutation
2045
//
2046

    
2047
static word_t _next_permutation(word_t v)
2048
{
2049
  // From http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
2050
  word_t t = v | (v - 1); // t gets v's least significant 0 bits set to 1
2051
  // Next set to 1 the most significant bit to change,
2052
  // set to 0 the least significant ones, and add the necessary 1 bits.
2053
  return (t+1) | (((~t & (t+1)) - 1) >> (trailing_zeros(v) + 1));
2054
}
2055

    
2056
// Get the next permutation of an array with a fixed size and given number of
2057
// bits set.  Also known as next lexicographic permutation.
2058
// Given a bit array find the next lexicographic orginisation of the bits
2059
// Number of possible combinations given by (size choose bits_set) i.e. nCk
2060
// 00011 -> 00101 -> 00110 -> 01001 -> 01010 ->
2061
// 01100 -> 10001 -> 10010 -> 10100 -> 11000 -> 00011 (back to start)
2062
void bit_array_next_permutation(BIT_ARRAY* bitarr)
2063
{
2064
  if(bitarr->num_of_bits == 0)
2065
  {
2066
    return;
2067
  }
2068

    
2069
  word_addr_t w;
2070

    
2071
  char carry = 0;
2072
  word_offset_t top_bits = bitset64_idx(bitarr->num_of_bits);
2073

    
2074
  for(w = 0; w < bitarr->num_of_words; w++)
2075
  {
2076
    word_t mask
2077
      = (w < bitarr->num_of_words - 1 || top_bits == 0) ? WORD_MAX
2078
                                                        : bitmask64(top_bits);
2079

    
2080
    if(bitarr->words[w] > 0 &&
2081
       (bitarr->words[w] | (bitarr->words[w]-1)) == mask)
2082
    {
2083
      // Bits in this word cannot be moved forward
2084
      carry = 1;
2085
    }
2086
    else if(carry)
2087
    {
2088
      // 0111 -> 1000, 1000 -> 1001
2089
      word_t tmp = bitarr->words[w] + 1;
2090

    
2091
      // Count bits previously set
2092
      bit_index_t bits_previously_set = POPCOUNT(bitarr->words[w]);
2093

    
2094
      // set new word
2095
      bitarr->words[w] = tmp;
2096

    
2097
      // note: w is unsigned
2098
      // Zero words while counting bits set
2099
      while(w > 0)
2100
      {
2101
        bits_previously_set += POPCOUNT(bitarr->words[w-1]);
2102
        bitarr->words[w-1] = 0;
2103
        w--;
2104
      }
2105

    
2106
      // Set bits at the beginning
2107
      SET_REGION(bitarr, 0, bits_previously_set - POPCOUNT(tmp));
2108

    
2109
      carry = 0;
2110
      break;
2111
    }
2112
    else if(bitarr->words[w] > 0)
2113
    {
2114
      bitarr->words[w] = _next_permutation(bitarr->words[w]);
2115
      break;
2116
    }
2117
  }
2118

    
2119
  if(carry)
2120
  {
2121
    // Loop around
2122
    bit_index_t num_bits_set = bit_array_num_bits_set(bitarr);
2123
    bit_array_clear_all(bitarr);
2124
    SET_REGION(bitarr, 0, num_bits_set);
2125
  }
2126

    
2127
  DEBUG_VALIDATE(bitarr);
2128
}
2129

    
2130

    
2131
//
2132
// Interleave
2133
//
2134

    
2135
// dst cannot point to the same bit array as src1 or src2
2136
// src1, src2 may point to the same bit array
2137
// abcd 1234 -> a1b2c3d4
2138
// 0011 0000 -> 00001010
2139
// 1111 0000 -> 10101010
2140
// 0101 1010 -> 01100110
2141
void bit_array_interleave(BIT_ARRAY* dst,
2142
                          const BIT_ARRAY* src1,
2143
                          const BIT_ARRAY* src2)
2144
{
2145
  // dst cannot be either src1 or src2
2146
  assert(dst != src1 && dst != src2);
2147
  // Behaviour undefined when src1 length != src2 length",
2148
  assert(src1->num_of_bits == src2->num_of_bits);
2149

    
2150
  // Need at least src1->num_of_words + src2->num_of_words
2151
  size_t nwords = MIN(src1->num_of_words + src2->num_of_words, 2);
2152
  _bit_array_ensure_nwords(dst, nwords, __FILE__, __LINE__, __func__);
2153
  dst->num_of_bits = src1->num_of_bits + src2->num_of_bits;
2154
  dst->num_of_words = roundup_bits2words64(dst->num_of_bits);
2155

    
2156
  word_addr_t i, j;
2157

    
2158
  for(i = 0, j = 0; i < src1->num_of_words; i++)
2159
  {
2160
    word_t a = src1->words[i];
2161
    word_t b = src2->words[i];
2162

    
2163
    dst->words[j++] =  morton_table0[(a      ) & 0xff] |
2164
                       morton_table1[(b      ) & 0xff] |
2165
                      (morton_table0[(a >>  8) & 0xff] << 16) |
2166
                      (morton_table1[(b >>  8) & 0xff] << 16) |
2167
                      (morton_table0[(a >> 16) & 0xff] << 32) |
2168
                      (morton_table1[(b >> 16) & 0xff] << 32) |
2169
                      (morton_table0[(a >> 24) & 0xff] << 48) |
2170
                      (morton_table1[(b >> 24) & 0xff] << 48);
2171

    
2172
    dst->words[j++] =  morton_table0[(a >> 32) & 0xff] |
2173
                       morton_table1[(b >> 32) & 0xff] |
2174
                      (morton_table0[(a >> 40) & 0xff] << 16) |
2175
                      (morton_table1[(b >> 40) & 0xff] << 16) |
2176
                      (morton_table0[(a >> 48) & 0xff] << 32) |
2177
                      (morton_table1[(b >> 48) & 0xff] << 32) |
2178
                      (morton_table0[(a >> 56)       ] << 48) |
2179
                      (morton_table1[(b >> 56)       ] << 48);
2180
  }
2181

    
2182
  DEBUG_VALIDATE(dst);
2183
}
2184

    
2185
//
2186
// Random
2187
//
2188

    
2189
// Set bits randomly with probability prob : 0 <= prob <= 1
2190
void bit_array_random(BIT_ARRAY* bitarr, float prob)
2191
{
2192
  assert(prob >= 0 && prob <= 1);
2193

    
2194
  if(bitarr->num_of_bits == 0)
2195
  {
2196
    return;
2197
  }
2198
  else if(prob == 1)
2199
  {
2200
    bit_array_set_all(bitarr);
2201
    return;
2202
  }
2203

    
2204
  // rand() generates number between 0 and RAND_MAX inclusive
2205
  // therefore we want to check if rand() <= p
2206
  long p = RAND_MAX * prob;
2207

    
2208
  _seed_rand();
2209

    
2210
  word_addr_t w;
2211
  word_offset_t o;
2212

    
2213
  // Initialise to zero
2214
  memset(bitarr->words, 0, bitarr->num_of_words * sizeof(word_t));
2215

    
2216
  for(w = 0; w < bitarr->num_of_words - 1; w++)
2217
  {
2218
    for(o = 0; o < WORD_SIZE; o++)
2219
    {
2220
      if(rand() <= p)
2221
      {
2222
        bitarr->words[w] |= ((word_t)0x1 << o);
2223
      }
2224
    }
2225
  }
2226

    
2227
  // Top word
2228
  word_offset_t bits_in_last_word = bits_in_top_word(bitarr->num_of_bits);
2229
  w = bitarr->num_of_words - 1;
2230

    
2231
  for(o = 0; o < bits_in_last_word; o++)
2232
  {
2233
    if(rand() <= p)
2234
    {
2235
      bitarr->words[w] |= ((word_t)0x1 << o);
2236
    }
2237
  }
2238

    
2239
  DEBUG_VALIDATE(bitarr);
2240
}
2241

    
2242
// Shuffle the bits in an array randomly
2243
void bit_array_shuffle(BIT_ARRAY* bitarr)
2244
{
2245
  if(bitarr->num_of_bits == 0)
2246
    return;
2247

    
2248
  _seed_rand();
2249

    
2250
  bit_index_t i, j;
2251

    
2252
  for(i = bitarr->num_of_bits - 1; i > 0; i--)
2253
  {
2254
    j = (bit_index_t)rand() % i;
2255

    
2256
    // Swap i and j
2257
    char x = (bitarr->words[bitset64_wrd(i)] >> bitset64_idx(i)) & 0x1;
2258
    char y = (bitarr->words[bitset64_wrd(j)] >> bitset64_idx(j)) & 0x1;
2259

    
2260
    if(!y)
2261
      bitarr->words[bitset64_wrd(i)] &= ~((word_t)0x1 << bitset64_idx(i));
2262
    else
2263
      bitarr->words[bitset64_wrd(i)] |= (word_t)0x1 << bitset64_idx(i);
2264

    
2265
    if(!x)
2266
      bitarr->words[bitset64_wrd(j)] &= ~((word_t)0x1 << bitset64_idx(j));
2267
    else
2268
      bitarr->words[bitset64_wrd(j)] |= (word_t)0x1 << bitset64_idx(j);
2269
  }
2270

    
2271
  DEBUG_VALIDATE(bitarr);
2272
}
2273

    
2274
//
2275
// Arithmetic
2276
//
2277

    
2278
// Returns 1 on sucess, 0 if value in array is too big
2279
char bit_array_as_num(const BIT_ARRAY* bitarr, uint64_t* result)
2280
{
2281
  if(bitarr->num_of_bits == 0)
2282
  {
2283
    *result = 0;
2284
    return 1;
2285
  }
2286

    
2287
  word_addr_t w;
2288

    
2289
  for(w = bitarr->num_of_words-1; w > 0; w--)
2290
  {
2291
    if(bitarr->words[w] > 0)
2292
    {
2293
      return 0;
2294
    }
2295
  }
2296

    
2297
  *result = bitarr->words[0];
2298
  return 1;
2299
}
2300

    
2301

    
2302
// 1 iff bitarr > value
2303
// 0 iff bitarr == value
2304
// -1 iff bitarr < value
2305
int bit_array_cmp_uint64(const BIT_ARRAY* bitarr, uint64_t value)
2306
{
2307
  uint64_t arr_num = 0;
2308

    
2309
  // If cannot put bitarr in uint64, it is > value
2310
  if(!bit_array_as_num(bitarr, &arr_num)) return 1;
2311

    
2312
  if(arr_num > value)      return  1;
2313
  else if(arr_num < value) return -1;
2314
  else                     return  0;
2315
}
2316

    
2317
// If value is zero, no change is made
2318
void bit_array_add_uint64(BIT_ARRAY* bitarr, uint64_t value)
2319
{
2320
  if(value == 0)
2321
  {
2322
    return;
2323
  }
2324
  else if(bitarr->num_of_bits == 0)
2325
  {
2326
    bit_array_resize_critical(bitarr, WORD_SIZE - leading_zeros(value));
2327
    bitarr->words[0] = (word_t)value;
2328
    return;
2329
  }
2330

    
2331
  char carry = 0;
2332
  word_addr_t i;
2333

    
2334
  for(i = 0; i < bitarr->num_of_words; i++)
2335
  {
2336
    if(WORD_MAX - bitarr->words[i] < value)
2337
    {
2338
      carry = 1;
2339
      bitarr->words[i] += value;
2340
    }
2341
    else
2342
    {
2343
      // Carry is absorbed
2344
      bitarr->words[i] += value;
2345
      carry = 0;
2346
      break;
2347
    }
2348
  }
2349

    
2350
  if(carry)
2351
  {
2352
    // Bit array full, need another bit after all words filled
2353
    bit_array_resize_critical(bitarr, bitarr->num_of_words * WORD_SIZE + 1);
2354

    
2355
    // Set top word to 1
2356
    bitarr->words[bitarr->num_of_words-1] = 1;
2357
  }
2358
  else
2359
  {
2360
    word_t final_word = bitarr->words[bitarr->num_of_words-1];
2361
    word_offset_t expected_bits = bits_in_top_word(bitarr->num_of_bits);
2362
    word_offset_t actual_bits = WORD_SIZE - leading_zeros(final_word);
2363

    
2364
    if(actual_bits > expected_bits)
2365
    {
2366
      // num_of_bits has increased -- num_of_words has not
2367
      bitarr->num_of_bits += (actual_bits - expected_bits);
2368
    }
2369
  }
2370
}
2371

    
2372
// If value is greater than bitarr, bitarr is not changed and 0 is returned
2373
// Returns 1 on success, 0 if value > bitarr
2374
char bit_array_sub_uint64(BIT_ARRAY* bitarr, uint64_t value)
2375
{
2376
  if(value == 0)
2377
  {
2378
    return 1;
2379
  }
2380
  else if(bitarr->words[0] >= value)
2381
  {
2382
    bitarr->words[0] -= value;
2383
    return 1;
2384
  }
2385

    
2386
  value -= bitarr->words[0];
2387

    
2388
  word_addr_t i;
2389

    
2390
  for(i = 1; i < bitarr->num_of_words; i++)
2391
  {
2392
    if(bitarr->words[i] > 0)
2393
    {
2394
      // deduct one
2395
      bitarr->words[i]--;
2396

    
2397
      for(; i > 0; i--)
2398
      {
2399
        bitarr->words[i] = WORD_MAX;
2400
      }
2401

    
2402
      // -1 since we've already deducted 1
2403
      bitarr->words[0] = WORD_MAX - value - 1;
2404

    
2405
      return 1;
2406
    }
2407
  }
2408

    
2409
  // subtract value is greater than array
2410
  return 0;
2411
}
2412

    
2413
//
2414
// Arithmetic between bit arrays
2415
//
2416

    
2417
// src1, src2 and dst can all be the same BIT_ARRAY
2418
static void _arithmetic(BIT_ARRAY* dst,
2419
                        const BIT_ARRAY* src1,
2420
                        const BIT_ARRAY* src2,
2421
                        char subtract)
2422
{
2423
  word_addr_t max_words = MAX(src1->num_of_words, src2->num_of_words);
2424

    
2425
  // Adding: dst_words >= max(src1 words, src2 words)
2426
  // Subtracting: dst_words is >= src1->num_of_words
2427

    
2428
  char carry = subtract ? 1 : 0;
2429

    
2430
  word_addr_t i;
2431
  word_t word1, word2;
2432

    
2433
  for(i = 0; i < max_words; i++)
2434
  {
2435
    word1 = (i < src1->num_of_words ? src1->words[i] : 0);
2436
    word2 = (i < src2->num_of_words ? src2->words[i] : 0);
2437

    
2438
    if(subtract)
2439
      word2 = ~word2;
2440

    
2441
    dst->words[i] = word1 + word2 + carry;
2442
    // Update carry
2443
    carry = WORD_MAX - word1 < word2 || WORD_MAX - word1 - word2 < (word_t)carry;
2444
  }
2445

    
2446
  if(subtract)
2447
  {
2448
    carry = 0;
2449
  }
2450
  else
2451
  {
2452
    // Check last word
2453
    word_offset_t bits_on_last_word = bits_in_top_word(dst->num_of_bits);
2454

    
2455
    if(bits_on_last_word < WORD_SIZE)
2456
    {
2457
      word_t mask = bitmask64(bits_on_last_word);
2458

    
2459
      if(dst->words[max_words-1] > mask)
2460
      {
2461
        // Array has overflowed, increase size
2462
        dst->num_of_bits++;
2463
      }
2464
    }
2465
    else if(carry)
2466
    {
2467
      // Carry onto a new word
2468
      if(dst->num_of_words == max_words)
2469
      {
2470
        // Need to resize for the carry bit
2471
        bit_array_resize_critical(dst, dst->num_of_bits+1);
2472
      }
2473

    
2474
      dst->words[max_words] = (word_t)1;
2475
    }
2476
  }
2477

    
2478
  // Zero the rest of dst array
2479
  for(i = max_words+carry; i < dst->num_of_words; i++)
2480
  {
2481
    dst->words[i] = (word_t)0;
2482
  }
2483

    
2484
  DEBUG_VALIDATE(dst);
2485
}
2486

    
2487
// src1, src2 and dst can all be the same BIT_ARRAY
2488
// If dst is shorter than either of src1, src2, it is enlarged
2489
void bit_array_add(BIT_ARRAY* dst, const BIT_ARRAY* src1, const BIT_ARRAY* src2)
2490
{
2491
  bit_array_ensure_size_critical(dst, MAX(src1->num_of_bits, src2->num_of_bits));
2492
  _arithmetic(dst, src1, src2, 0);
2493
}
2494

    
2495
// dst = src1 - src2
2496
// src1, src2 and dst can all be the same BIT_ARRAY
2497
// If dst is shorter than src1, it will be extended to be as long as src1
2498
// src1 must be greater than or equal to src2 (src1 >= src2)
2499
void bit_array_subtract(BIT_ARRAY* dst,
2500
                          const BIT_ARRAY* src1, const BIT_ARRAY* src2)
2501
{
2502
  // subtraction by method of complements:
2503
  // a - b = a + ~b + 1 = src1 + ~src2 +1
2504

    
2505
  assert(bit_array_cmp(src1, src2) >= 0); // Require src1 >= src2
2506

    
2507
  bit_array_ensure_size_critical(dst, src1->num_of_bits);
2508
  _arithmetic(dst, src1, src2, 1);
2509
}
2510

    
2511

    
2512
// Add `add` to `bitarr` at `pos`
2513
// Bounds checking not needed as out of bounds is valid
2514
void bit_array_add_word(BIT_ARRAY *bitarr, bit_index_t pos, uint64_t add)
2515
{
2516
  DEBUG_VALIDATE(bitarr);
2517

    
2518
  if(add == 0)
2519
  {
2520
    return;
2521
  }
2522
  else if(pos >= bitarr->num_of_bits)
2523
  {
2524
    // Resize and add!
2525
    bit_index_t num_bits_required = pos + (WORD_SIZE - leading_zeros(add));
2526
    bit_array_resize_critical(bitarr, num_bits_required);
2527
    _set_word(bitarr, pos, (word_t)add);
2528
    return;
2529
  }
2530

    
2531
  /*
2532
  char str[1000];
2533
  printf(" add_word: %s\n", bit_array_to_str_rev(bitarr, str));
2534
  printf("     word: %s [pos: %i]\n", _word_to_str(add, str), (int)pos);
2535
  */
2536

    
2537
  word_t w = _get_word(bitarr, pos);
2538
  word_t sum = w + add;
2539
  char carry = WORD_MAX - w < add;
2540

    
2541
  // Ensure array is big enough
2542
  bit_index_t num_bits_required = pos + (carry ? WORD_SIZE + 1
2543
                                               : (WORD_SIZE - leading_zeros(sum)));
2544

    
2545
  bit_array_ensure_size(bitarr, num_bits_required);
2546

    
2547
  _set_word(bitarr, pos, sum);
2548
  pos += WORD_SIZE;
2549

    
2550
  if(carry)
2551
  {
2552
    word_offset_t offset = pos % WORD_SIZE;
2553
    word_addr_t addr = bitset64_wrd(pos);
2554

    
2555
    add = (word_t)0x1 << offset;
2556
    carry = (WORD_MAX - bitarr->words[addr] < add);
2557
    sum = bitarr->words[addr] + add;
2558

    
2559
    num_bits_required = addr * WORD_SIZE +
2560
                        (carry ? WORD_SIZE + 1 : (WORD_SIZE - leading_zeros(sum)));
2561

    
2562
    bit_array_ensure_size(bitarr, num_bits_required);
2563

    
2564
    bitarr->words[addr++] = sum;
2565

    
2566
    if(carry)
2567
    {
2568
      while(addr < bitarr->num_of_words && bitarr->words[addr] == WORD_MAX)
2569
      {
2570
        bitarr->words[addr++] = 0;
2571
      }
2572

    
2573
      if(addr == bitarr->num_of_words)
2574
      {
2575
        bit_array_resize_critical(bitarr, addr * WORD_SIZE + 1);
2576
      }
2577
      else if(addr == bitarr->num_of_words-1 &&
2578
              bitarr->words[addr] == bitmask64(bits_in_top_word(bitarr->num_of_bits)))
2579
      {
2580
        bit_array_resize_critical(bitarr, bitarr->num_of_bits + 1);
2581
      }
2582

    
2583
      bitarr->words[addr]++;
2584
    }
2585
  }
2586

    
2587
  DEBUG_VALIDATE(bitarr);
2588
}
2589

    
2590
// Add `add` to `bitarr` at `pos`
2591
// Bounds checking not needed as out of bounds is valid
2592
void bit_array_add_words(BIT_ARRAY *bitarr, bit_index_t pos, const BIT_ARRAY *add)
2593
{
2594
  assert(bitarr != add); // bitarr and add cannot point to the same bit array
2595

    
2596
  bit_index_t add_top_bit_set;
2597

    
2598
  if(!bit_array_find_last_set_bit(add, &add_top_bit_set))
2599
  {
2600
    // No bits set in add
2601
    return;
2602
  }
2603
  else if(pos >= bitarr->num_of_bits)
2604
  {
2605
    // Just resize and copy!
2606
    bit_index_t num_bits_required = pos + add_top_bit_set + 1;
2607
    bit_array_resize_critical(bitarr, num_bits_required);
2608
    _array_copy(bitarr, pos, add, 0, add->num_of_bits);
2609
    return;
2610
  }
2611
  else if(pos == 0)
2612
  {
2613
    bit_array_add(bitarr, bitarr, add);
2614
    return;
2615
  }
2616

    
2617
  /*
2618
  char str[1000];
2619
  printf(" add_words1: %s\n", bit_array_to_str_rev(bitarr, str));
2620
  printf(" add_words2: %s\n", bit_array_to_str_rev(add, str));
2621
  printf(" [pos: %i]\n", (int)pos);
2622
  */
2623

    
2624
  bit_index_t num_bits_required = pos + add_top_bit_set + 1;
2625
  bit_array_ensure_size(bitarr, num_bits_required);
2626

    
2627
  word_addr_t first_word = bitset64_wrd(pos);
2628
  word_offset_t first_offset = bitset64_idx(pos);
2629

    
2630
  word_t w = add->words[0] << first_offset;
2631
  unsigned char carry = (WORD_MAX - bitarr->words[first_word] < w);
2632

    
2633
  bitarr->words[first_word] += w;
2634

    
2635
  word_addr_t i = first_word + 1;
2636
  bit_index_t offset = WORD_SIZE - first_offset;
2637

    
2638
  for(; carry || offset <= add_top_bit_set; i++, offset += WORD_SIZE)
2639
  {
2640
    w = offset < add->num_of_bits ? _get_word(add, offset) : (word_t)0;
2641

    
2642
    if(i >= bitarr->num_of_words)
2643
    {
2644
      // Extend by a word
2645
      bit_array_resize_critical(bitarr, (bit_index_t)(i+1)*WORD_SIZE+1);
2646
    }
2647

    
2648
    word_t prev = bitarr->words[i];
2649

    
2650
    bitarr->words[i] += w + carry;
2651

    
2652
    carry = (WORD_MAX - prev < w || (carry && prev + w == WORD_MAX)) ? 1 : 0;
2653
  }
2654

    
2655
  word_offset_t top_bits
2656
    = WORD_SIZE - leading_zeros(bitarr->words[bitarr->num_of_words-1]);
2657

    
2658
  bit_index_t min_bits = (bitarr->num_of_words-1)*WORD_SIZE + top_bits;
2659

    
2660
  if(bitarr->num_of_bits < min_bits)
2661
  {
2662
    // Extend within the last word
2663
    bitarr->num_of_bits = min_bits;
2664
  }
2665

    
2666
  DEBUG_VALIDATE(bitarr);
2667
}
2668

    
2669
char bit_array_sub_word(BIT_ARRAY* bitarr, bit_index_t pos, word_t minus)
2670
{
2671
  DEBUG_VALIDATE(bitarr);
2672

    
2673
  if(minus == 0)
2674
  {
2675
    return 1;
2676
  }
2677

    
2678
  word_t w = _get_word(bitarr, pos);
2679

    
2680
  if(w >= minus)
2681
  {
2682
    _set_word(bitarr, pos, w - minus);
2683
    DEBUG_VALIDATE(bitarr);
2684
    return 1;
2685
  }
2686

    
2687
  minus -= w;
2688

    
2689
  bit_index_t offset;
2690
  for(offset = pos + WORD_SIZE; offset < bitarr->num_of_bits; offset += WORD_SIZE)
2691
  {
2692
    w = _get_word(bitarr, offset);
2693

    
2694
    if(w > 0)
2695
    {
2696
      // deduct one
2697
      _set_word(bitarr, offset, w - 1);
2698

    
2699
      SET_REGION(bitarr, pos, offset-pos);
2700

    
2701
      // -1 since we've already deducted 1
2702
      minus--;
2703

    
2704
      _set_word(bitarr, pos, WORD_MAX - minus);
2705

    
2706
      DEBUG_VALIDATE(bitarr);
2707
      return 1;
2708
    }
2709
  }
2710

    
2711
  DEBUG_VALIDATE(bitarr);
2712

    
2713
  return 0;
2714
}
2715

    
2716
char bit_array_sub_words(BIT_ARRAY* bitarr, bit_index_t pos, BIT_ARRAY* minus)
2717
{
2718
  assert(bitarr != minus); // bitarr and minus cannot point to the same bit array
2719

    
2720
  int cmp = bit_array_cmp_words(bitarr, pos, minus);
2721

    
2722
  if(cmp == 0)
2723
  {
2724
    bit_array_clear_all(bitarr);
2725
    return 1;
2726
  }
2727
  else if(cmp < 0)
2728
  {
2729
    return 0;
2730
  }
2731

    
2732
  bit_index_t bitarr_length = bitarr->num_of_bits;
2733

    
2734
  bit_index_t bitarr_top_bit_set;
2735
  bit_array_find_last_set_bit(bitarr, &bitarr_top_bit_set);
2736

    
2737
  // subtraction by method of complements:
2738
  // a - b = a + ~b + 1 = src1 + ~src2 +1
2739

    
2740
  bit_array_not(minus, minus);
2741

    
2742
  bit_array_add_words(bitarr, pos, minus);
2743
  bit_array_add_word(bitarr, pos, (word_t)1);
2744

    
2745
  bit_array_sub_word(bitarr, pos+minus->num_of_bits, 1);
2746
  bit_array_resize(bitarr, bitarr_length);
2747

    
2748
  bit_array_not(minus, minus);
2749

    
2750
  DEBUG_VALIDATE(bitarr);
2751

    
2752
  return 1;
2753
}
2754

    
2755
void bit_array_mul_uint64(BIT_ARRAY *bitarr, uint64_t multiplier)
2756
{
2757
  if(bitarr->num_of_bits == 0 || multiplier == 1)
2758
  {
2759
    return;
2760
  }
2761
  else if(multiplier == 0)
2762
  {
2763
    bit_array_clear_all(bitarr);
2764
    return;
2765
  }
2766

    
2767
  bit_index_t i;
2768

    
2769
  for(i = bitarr->num_of_bits; i > 0; i--)
2770
  {
2771
    if(bit_array_get(bitarr, i-1))
2772
    {
2773
      bit_array_clear(bitarr, i-1);
2774
      bit_array_add_word(bitarr, i-1, multiplier);
2775
    }
2776
  }
2777

    
2778
  DEBUG_VALIDATE(bitarr);
2779
}
2780

    
2781
void bit_array_multiply(BIT_ARRAY *dst, BIT_ARRAY *src1, BIT_ARRAY *src2)
2782
{
2783
  if(src1->num_of_bits == 0 || src2->num_of_bits == 0)
2784
  {
2785
    bit_array_clear_all(dst);
2786
    return;
2787
  }
2788

    
2789
  // Cannot pass the same array as dst, src1 AND src2
2790
  assert(dst != src1 || dst != src2);
2791

    
2792
  // Dev: multiplier == 1?
2793

    
2794
  BIT_ARRAY *read_arr, *add_arr;
2795

    
2796
  if(src1 == dst)
2797
  {
2798
    read_arr = src1;
2799
    add_arr = src2;
2800
  }
2801
  else
2802
  {
2803
    read_arr = src2;
2804
    add_arr = src1;
2805
  }
2806

    
2807
  if(dst != src1 && dst != src2)
2808
  {
2809
    bit_array_clear_all(dst);
2810
  }
2811

    
2812
  bit_index_t i;
2813

    
2814
  for(i = read_arr->num_of_bits; i > 0; i--)
2815
  {
2816
    if(bit_array_get(read_arr, i-1))
2817
    {
2818
      bit_array_clear(dst, i-1);
2819
      bit_array_add_words(dst, i-1, add_arr);
2820
    }
2821
  }
2822

    
2823
  DEBUG_VALIDATE(dst);
2824
}
2825

    
2826
// bitarr = round_down(bitarr / divisor)
2827
// rem = bitarr % divisor
2828
void bit_array_div_uint64(BIT_ARRAY *bitarr, uint64_t divisor, uint64_t *rem)
2829
{
2830
  assert(divisor != 0); // cannot divide by zero
2831

    
2832
  bit_index_t div_top_bit = 63 - leading_zeros(divisor);
2833
  bit_index_t bitarr_top_bit;
2834

    
2835
  if(!bit_array_find_last_set_bit(bitarr, &bitarr_top_bit))
2836
  {
2837
    *rem = 0;
2838
    return;
2839
  }
2840

    
2841
  if(bitarr_top_bit < div_top_bit)
2842
  {
2843
    *rem = bitarr->words[0];
2844
    bit_array_clear_all(bitarr);
2845
    return;
2846
  }
2847

    
2848
  // When div is shifted by offset, their top set bits are aligned
2849
  bit_index_t offset = bitarr_top_bit - div_top_bit;
2850

    
2851
  uint64_t tmp = _get_word(bitarr, offset);
2852
  _set_word(bitarr, offset, (word_t)0);
2853

    
2854
  // Carry if 1 if the top bit was set before left shift
2855
  char carry = 0;
2856

    
2857
  // offset unsigned so break when offset == 0
2858
  while(1)
2859
  {
2860
    if(carry)
2861
    {
2862
      // (carry:tmp) - divisor = (WORD_MAX+1+tmp)-divisor
2863
      tmp = WORD_MAX - divisor + tmp + 1;
2864
      bit_array_set(bitarr, offset);
2865
    }
2866
    else if(tmp >= divisor)
2867
    {
2868
      tmp -= divisor;
2869
      bit_array_set(bitarr, offset);
2870
    }
2871
    else
2872
    {
2873
      bit_array_clear(bitarr, offset);
2874
    }
2875

    
2876
    if(offset == 0)
2877
      break;
2878

    
2879
    offset--;
2880

    
2881
    // Is the top bit set (that we're about to shift off)?
2882
    carry = tmp & 0x8000000000000000;
2883

    
2884
    tmp <<= 1;
2885
    tmp |= bit_array_get(bitarr, offset);
2886
  }
2887

    
2888
  *rem = tmp;
2889
}
2890

    
2891
// Results in:
2892
//   quotient = dividend / divisor
2893
//   dividend = dividend % divisor
2894
// (dividend is used to return the remainder)
2895
void bit_array_divide(BIT_ARRAY *dividend, BIT_ARRAY *quotient, BIT_ARRAY *divisor)
2896
{
2897
  assert(bit_array_cmp_uint64(divisor, 0) != 0); // Cannot divide by zero
2898

    
2899
  bit_array_clear_all(quotient);
2900

    
2901
  int cmp = bit_array_cmp(dividend, divisor);
2902

    
2903
  if(cmp == 0)
2904
  {
2905
    bit_array_ensure_size(quotient, 1);
2906
    bit_array_set(quotient, 0);
2907
    bit_array_clear_all(dividend);
2908
    return;
2909
  }
2910
  else if(cmp < 0)
2911
  {
2912
    // dividend is < divisor, quotient is zero -- done
2913
    return;
2914
  }
2915

    
2916
  // now we know: dividend > divisor, quotient is zero'd,
2917
  //              dividend != 0, divisor != 0
2918
  bit_index_t dividend_top_bit = 0, div_top_bit = 0;
2919

    
2920
  bit_array_find_last_set_bit(dividend, &dividend_top_bit);
2921
  bit_array_find_last_set_bit(divisor, &div_top_bit);
2922

    
2923
  // When divisor is shifted by offset, their top set bits are aligned
2924
  bit_index_t offset = dividend_top_bit - div_top_bit;
2925

    
2926
  // offset unsigned so break when offset == 0
2927
  for(; ; offset--)
2928
  {
2929
    if(bit_array_cmp_words(dividend, offset, divisor) >= 0)
2930
    {
2931
      bit_array_sub_words(dividend, offset, divisor);
2932
      bit_array_ensure_size(quotient, offset+1);
2933
      bit_array_set(quotient, offset);
2934
    }
2935

    
2936
    if(offset == 0)
2937
      break;
2938
  }
2939
}
2940

    
2941
//
2942
// Read/Write from files
2943
//
2944
// file format is [8 bytes: for number of elements in array][data]
2945
// data is written in little endian order (least sig byte first)
2946
//
2947

    
2948
// Saves bit array to a file. Returns the number of bytes written
2949
// number of bytes returned should be 8+(bitarr->num_of_bits+7)/8
2950
bit_index_t bit_array_save(const BIT_ARRAY* bitarr, FILE* f)
2951
{
2952
  bit_index_t num_of_bytes = roundup_bits2bytes(bitarr->num_of_bits);
2953
  bit_index_t bytes_written = 0;
2954

    
2955
  const int endian = 1;
2956
  if(*(uint8_t*)&endian == 1)
2957
  {
2958
    // Little endian machine
2959
    // Write 8 bytes to store the number of bits in the array
2960
    bytes_written += fwrite(&bitarr->num_of_bits, 1, 8, f);
2961

    
2962
    // Write the array
2963
    bytes_written += fwrite(bitarr->words, 1, num_of_bytes, f);
2964
  }
2965
  else
2966
  {
2967
    // Big endian machine
2968
    uint64_t i, w, whole_words = num_of_bytes/sizeof(word_t);
2969
    uint64_t rem_bytes = num_of_bytes - whole_words*sizeof(word_t);
2970
    uint64_t n_bits = byteswap64(bitarr->num_of_bits);
2971

    
2972
    // Write 8 bytes to store the number of bits in the array
2973
    bytes_written += fwrite(&n_bits, 1, 8, f);
2974

    
2975
    // Write the array
2976
    for(i = 0; i < whole_words; i++) {
2977
      w = byteswap64(bitarr->words[i]);
2978
      bytes_written += fwrite(&w, 1, 8, f);
2979
    }
2980

    
2981
    if(rem_bytes > 0) {
2982
      w = byteswap64(bitarr->words[whole_words]);
2983
      bytes_written += fwrite(&w, 1, rem_bytes, f);
2984
    }
2985
  }
2986

    
2987
  return bytes_written;
2988
}
2989

    
2990
// Load a uint64 from little endian format.
2991
// Works for both big and little endian architectures
2992
static inline uint64_t le64_to_cpu(const uint8_t *x)
2993
{
2994
  return (((uint64_t)(x[0]))       | ((uint64_t)(x[1]) << 8)  |
2995
          ((uint64_t)(x[2]) << 16) | ((uint64_t)(x[3]) << 24) |
2996
          ((uint64_t)(x[4]) << 32) | ((uint64_t)(x[5]) << 40) |
2997
          ((uint64_t)(x[6]) << 48) | ((uint64_t)(x[7]) << 56));
2998
}
2999

    
3000
// Reads bit array from a file. bitarr is resized and filled.
3001
// Returns 1 on success, 0 on failure
3002
char bit_array_load(BIT_ARRAY* bitarr, FILE* f)
3003
{
3004
  // Read in number of bits, return 0 if we can't read in
3005
  bit_index_t num_bits;
3006
  if(fread(&num_bits, 1, 8, f) != 8) return 0;
3007
  num_bits = le64_to_cpu((uint8_t*)&num_bits);
3008

    
3009
  // Resize
3010
  bit_array_resize_critical(bitarr, num_bits);
3011

    
3012
  // Have to calculate how many bytes are needed for the file
3013
  // (Note: this may be different from num_of_words * sizeof(word_t))
3014
  bit_index_t num_of_bytes = roundup_bits2bytes(bitarr->num_of_bits);
3015
  if(fread(bitarr->words, 1, num_of_bytes, f) != num_of_bytes) return 0;
3016

    
3017
  // Fix endianness
3018
  word_addr_t i;
3019
  for(i = 0; i < bitarr->num_of_words; i++)
3020
    bitarr->words[i] = le64_to_cpu((uint8_t*)&bitarr->words[i]);
3021

    
3022
  // Mask top word
3023
  _mask_top_word(bitarr);
3024
  DEBUG_VALIDATE(bitarr);
3025
  return 1;
3026
}
3027

    
3028
//
3029
// Hash function
3030
//
3031

    
3032
/* From: lookup3.c, by Bob Jenkins, May 2006, Public Domain. */
3033
#define hashsize(n) ((uint32_t)1<<(n))
3034
#define hashmask(n) (hashsize(n)-1)
3035
#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
3036

    
3037
/* From: lookup3.c, by Bob Jenkins, May 2006, Public Domain. */
3038
#define mix(a,b,c) \
3039
{ \
3040
  a -= c;  a ^= rot(c, 4);  c += b; \
3041
  b -= a;  b ^= rot(a, 6);  a += c; \
3042
  c -= b;  c ^= rot(b, 8);  b += a; \
3043
  a -= c;  a ^= rot(c,16);  c += b; \
3044
  b -= a;  b ^= rot(a,19);  a += c; \
3045
  c -= b;  c ^= rot(b, 4);  b += a; \
3046
}
3047

    
3048
/* From: lookup3.c, by Bob Jenkins, May 2006, Public Domain. */
3049
#define final(a,b,c) \
3050
{ \
3051
  c ^= b; c -= rot(b,14); \
3052
  a ^= c; a -= rot(c,11); \
3053
  b ^= a; b -= rot(a,25); \
3054
  c ^= b; c -= rot(b,16); \
3055
  a ^= c; a -= rot(c,4);  \
3056
  b ^= a; b -= rot(a,14); \
3057
  c ^= b; c -= rot(b,24); \
3058
}
3059

    
3060
/*
3061
From: lookup3.c, by Bob Jenkins, May 2006, Public Domain.
3062
--------------------------------------------------------------------
3063
hashword2() -- same as hashword(), but take two seeds and return two
3064
32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
3065
both be initialized with seeds.  If you pass in (*pb)==0, the output
3066
(*pc) will be the same as the return value from hashword().
3067
--------------------------------------------------------------------
3068
*/
3069
static void hashword2 (
3070
const uint32_t *k,                   /* the key, an array of uint32_t values */
3071
size_t          length,               /* the length of the key, in uint32_ts */
3072
uint32_t       *pc,                      /* IN: seed OUT: primary hash value */
3073
uint32_t       *pb)               /* IN: more seed OUT: secondary hash value */
3074
{
3075
  uint32_t a,b,c;
3076

    
3077
  /* Set up the internal state */
3078
  a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
3079
  c += *pb;
3080

    
3081
  /*------------------------------------------------- handle most of the key */
3082
  while (length > 3)
3083
  {
3084
    a += k[0];
3085
    b += k[1];
3086
    c += k[2];
3087
    mix(a,b,c);
3088
    length -= 3;
3089
    k += 3;
3090
  }
3091

    
3092
  /*------------------------------------------- handle the last 3 uint32_t's */
3093
  switch(length)                     /* all the case statements fall through */
3094
  {
3095
  case 3 : c+=k[2];
3096
  case 2 : b+=k[1];
3097
  case 1 : a+=k[0];
3098
    final(a,b,c);
3099
  case 0:     /* case 0: nothing left to add */
3100
    break;
3101
  }
3102
  /*------------------------------------------------------ report the result */
3103
  *pc=c; *pb=b;
3104
}
3105

    
3106
// Pass seed as 0 on first call, pass previous hash value if rehashing due
3107
// to a collision
3108
// Using bob jenkins hash lookup3
3109
uint64_t bit_array_hash(const BIT_ARRAY* bitarr, uint64_t seed)
3110
{
3111
  uint32_t seed32[2];
3112
  memcpy(seed32, &seed, sizeof(uint32_t)*2);
3113

    
3114
  // Round up length to number 32bit words
3115
  hashword2((uint32_t*)bitarr->words, (bitarr->num_of_bits + 31) / 32,
3116
            &seed32[0], &seed32[1]);
3117

    
3118
  // XOR with array length. This ensures arrays with different length but same
3119
  // contents have different hash values
3120
  seed ^= bitarr->num_of_bits;
3121

    
3122
  return seed;
3123
}
3124

    
3125

    
3126
//
3127
// Generally useful functions
3128
//
3129

    
3130
// Generalised 'binary to string' function
3131
// Adds bits to the string in order of lsb to msb
3132
// e.g. 0b11010 (26 in decimal) would come out as "01011"
3133
char* bit_array_word2str(const void *ptr, size_t num_of_bits, char *str)
3134
{
3135
  const uint8_t* d = (const uint8_t*)ptr;
3136

    
3137
  size_t i;
3138
  for(i = 0; i < num_of_bits; i++)
3139
  {
3140
    uint8_t bit = (d[i/8] >> (i % 8)) & 0x1;
3141
    str[i] = bit ? '1' : '0';
3142
  }
3143
  str[num_of_bits] = '\0';
3144
  return str;
3145
}
3146

    
3147
char* bit_array_word2str_rev(const void *ptr, size_t num_of_bits, char *str)
3148
{
3149
  const uint8_t* d = (const uint8_t*)ptr;
3150

    
3151
  size_t i;
3152
  for(i = 0; i < num_of_bits; i++)
3153
  {
3154
    uint8_t bit = (d[i/8] >> (i % 8)) & 0x1;
3155
    str[num_of_bits-1-i] = bit ? '1' : '0';
3156
  }
3157
  str[num_of_bits] = '\0';
3158
  return str;
3159
}