1/* 2 * Copyright (c) 1999, 2000, 2003, 2005, 2008, 2012 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23// 24// bitarray.c 25// bitarray 26// 27// Created by Bertrand Serlet on 9/26/10. 28// Copyright (c) 2010 Apple. All rights reserved. 29// 30 31#include "bitarray.h" 32#define NDEBUG 1 33#include <assert.h> 34 35/******************************** Utilities ***************************/ 36 37#define STATIC_INLINE static __inline 38 39STATIC_INLINE unsigned __ffsll(uint64_t xx) { 40#if defined(__LP64__) 41 return __builtin_ffsl(xx); 42#else 43 return __builtin_ffsll(xx); 44#endif 45} 46 47#define BIT_SET(old,bit) ((old) | (1ULL << (bit))) 48#define BIT_GET(old,bit) ((old) & (1ULL << (bit))) 49#define BIT_ZAP(old,bit) ((old) & ~ (1ULL << (bit))) 50 51// several variants below of bit setting or zapping to generate minimal code 52// All these do 1 memory read and (maybe) 1 memory write 53STATIC_INLINE bool word_get_bit_simple(uint64_t *word, unsigned bit) { 54 uint64_t old = *word; 55 return BIT_GET(old, bit) != 0; 56} 57 58STATIC_INLINE void word_set_bit_simple(uint64_t *word, unsigned bit) { 59 uint64_t old = *word; 60 *word = BIT_SET(old, bit); 61} 62 63STATIC_INLINE bool word_set_bit_changed(uint64_t *word, unsigned bit) { 64 // returns 1 iff word has changed 65 uint64_t old = *word; 66 uint64_t new = BIT_SET(old, bit); 67 if (old == new) return 0; 68 *word = new; 69 return 1; 70} 71 72STATIC_INLINE bool word_set_bit_changed_go_down(uint64_t *word, unsigned bit, bool *was_non_zero) { 73 // returns 1 iff word changed 74 // sets was_non_zero (when something changed) 75 uint64_t old = *word; 76 uint64_t new = BIT_SET(old, bit); 77 if (old == new) return 0; 78 *word = new; 79 *was_non_zero = old != 0; 80 return 1; 81} 82 83STATIC_INLINE bool word_set_bit_go_down(uint64_t *word, unsigned bit) { 84 // returns 1 iff level below should be set too 85 uint64_t old = *word; 86 uint64_t new = BIT_SET(old, bit); 87 if (old == new) return 0; 88 *word = new; 89 return !old; 90} 91 92STATIC_INLINE void word_zap_bit_simple(uint64_t *word, unsigned bit) { 93 uint64_t old = *word; 94 *word = BIT_ZAP(old, bit); 95} 96 97STATIC_INLINE bool word_zap_bit_changed(uint64_t *word, unsigned bit) { 98 // returns 1 iff word changed 99 uint64_t old = *word; 100 uint64_t new = BIT_ZAP(old, bit); 101 if (old == new) return 0; 102 *word = new; 103 return 1; 104} 105 106STATIC_INLINE bool word_zap_bit_changed_go_down(uint64_t *word, unsigned bit, bool *is_now_zero) { 107 // returns 1 iff word changed 108 // sets is_now_zero (when something changed) 109 uint64_t old = *word; 110 uint64_t new = BIT_ZAP(old, bit); 111 if (old == new) return 0; 112 *word = new; 113 *is_now_zero = ! new; 114 return 1; 115} 116 117STATIC_INLINE bool word_zap_bit_go_down(uint64_t *word, unsigned bit) { 118 // returns 1 iff level below might require a bit-zeroing 119 uint64_t old = *word; 120 uint64_t new = BIT_ZAP(old, bit); 121 if (old == new) return 0; 122 *word = new; 123 return !new; 124} 125 126/******************************** Helpers ***************************/ 127 128#define NB 9 // number of bits we process at once 129// must be at least 6 (64-bit) and 9 seems the best on x86 130#define MASKNB ((1 << NB) - 1) // to just keep these bits 131#define NUM_64b (1 << (NB - 6)) // number of 64-bit words we process at once 132 133// number of uint64_t of summaries 134#define LEVEL0 (NUM_64b) 135#define LEVEL1 (LEVEL0 + (1 << NB)*NUM_64b) 136#define LEVEL2 (LEVEL1 + (1 << (NB+NB))*NUM_64b) 137#define LEVEL3 (LEVEL2 + (1 << (NB+NB+NB))*NUM_64b) 138 139#define MAX_LEVEL 5 140 141static const unsigned levels_num_words[] = {LEVEL0, LEVEL1, LEVEL2, LEVEL3}; // this encodes the number of words reserved for the bitmap summaries at various levels 142 143STATIC_INLINE bool GET_SIMPLE(uint64_t *word, unsigned bit) { 144 return word_get_bit_simple(word + (bit >> 6), bit & 63); 145} 146 147STATIC_INLINE void SET_SIMPLE(uint64_t *word, unsigned bit) { 148 word_set_bit_simple(word + (bit >> 6), bit & 63); 149} 150 151STATIC_INLINE bool SET_CHANGED(uint64_t *word, unsigned bit) { 152 // returns 1 iff word changed 153 return word_set_bit_changed(word + (bit >> 6), bit & 63); 154} 155 156STATIC_INLINE bool SET_CHANGED_GO_DOWN(uint64_t *word, unsigned bit, bool *was_non_zero) { 157 // returns 1 iff word changed 158 // sets was_non_zero (when something changed) 159 return word_set_bit_changed_go_down(word + (bit >> 6), bit & 63, was_non_zero); 160} 161 162STATIC_INLINE bool SET_GO_DOWN(uint64_t *word, unsigned bit) { 163 // returns 1 iff level below should be set too 164 return word_set_bit_go_down(word + (bit >> 6), bit & 63); 165} 166 167STATIC_INLINE void ZAP_SIMPLE(uint64_t *word, unsigned bit) { 168 return word_zap_bit_simple(word + (bit >> 6), bit & 63); 169} 170 171STATIC_INLINE bool ZAP_CHANGED(uint64_t *word, unsigned bit) { 172 // returns 1 iff word changed 173 return word_zap_bit_changed(word + (bit >> 6), bit & 63); 174} 175 176STATIC_INLINE bool all_zeros(uint64_t *words) { 177 for (unsigned w = 0; w < NUM_64b; w++) { 178 if (words[w]) return 0; 179 } 180 return 1; 181} 182 183STATIC_INLINE bool ZAP_CHANGED_GO_DOWN(uint64_t *word, unsigned bit, bool *is_now_zero) { 184 // returns 1 iff word changed 185 // sets is_now_zero (when something changed) 186 bool changed = word_zap_bit_changed_go_down(word + (bit >> 6), bit & 63, is_now_zero); 187 if (changed && (NUM_64b != 1)) { 188 // One component went entirely zero, now examine all components in the level 189 if (!all_zeros(word)) *is_now_zero = 0; 190 } 191 return changed; 192} 193 194STATIC_INLINE bool ZAP_GO_DOWN(uint64_t *word, unsigned bit) { 195 // returns 1 iff level below should be changed too 196 bool changed = word_zap_bit_go_down(word + (bit >> 6), bit & 63); 197 if (changed && (NUM_64b != 1)) { 198 // One component went entirely zero, now examine all components in the level 199 if (!all_zeros(word)) return 0; 200 } 201 return changed; 202} 203 204STATIC_INLINE unsigned FFS(uint64_t *word) { 205 // does NUM_64b memory reads, at most 206#if NB==6 207 return __ffsll(*word); 208#else 209 for (unsigned w = 0; w < NUM_64b; w++) { 210 unsigned f = __ffsll(word[w]); 211 if (f) return f + (w << 6); 212 } 213 return 0; 214#endif 215} 216 217/******************************** Entry Points ***************************/ 218 219size_t bitarray_size(unsigned log_size) { 220 assert(log_size <= MAX_LEVEL * NB); 221 unsigned num = NUM_64b; 222 if (log_size > NB) { 223 unsigned level = (log_size - NB - 1) / NB; 224 num = levels_num_words[level] + (1 << (log_size - 6)); 225 } 226 return num * sizeof(uint64_t); 227} 228 229bitarray_t bitarray_create(unsigned log_size) { 230 return calloc(1, bitarray_size(log_size)); 231} 232 233bool bitarray_get(bitarray_t bits, unsigned log_size, index_t index) { 234 assert(log_size <= MAX_LEVEL * NB); 235 assert(index < (1 << log_size)); 236 if (log_size <= NB) return GET_SIMPLE(bits, index); 237 unsigned level = (log_size - NB - 1) / NB; 238 unsigned bit; 239 bit = index & MASKNB; index >>= NB; 240 return GET_SIMPLE(bits + levels_num_words[level] + index*NUM_64b, bit); 241} 242 243bool bitarray_set(bitarray_t bits, unsigned log_size, index_t index) { 244 // returns whether changed 245 assert(log_size <= MAX_LEVEL * NB); 246 assert(index < (1 << log_size)); 247 if (log_size <= NB) return SET_CHANGED(bits, index); 248 unsigned level = (log_size - NB - 1) / NB; 249 bool was_non_zero; 250 unsigned bit; 251 bit = index & MASKNB; index >>= NB; 252 // printf("SET_CHANGED_GO_DOWN(bits + %d, %d,…)\n", levels_num_words[level] + index, bit); 253 if (!SET_CHANGED_GO_DOWN(bits + levels_num_words[level] + index*NUM_64b, bit, &was_non_zero)) return 0; 254 if (was_non_zero) return 1; 255 switch (level) { 256 case 3: 257 bit = index & MASKNB; index >>= NB; 258 if (!SET_GO_DOWN(bits + LEVEL2 + index*NUM_64b, bit)) return 1; 259 /* no break */ 260 case 2: 261 bit = index & MASKNB; index >>= NB; 262 if (!SET_GO_DOWN(bits + LEVEL1 + index*NUM_64b, bit)) return 1; 263 /* no break */ 264 case 1: 265 bit = index & MASKNB; index >>= NB; 266 if (!SET_GO_DOWN(bits + LEVEL0 + index*NUM_64b, bit)) return 1; 267 /* no break */ 268 case 0: 269 SET_SIMPLE(bits, index & MASKNB); 270 return 1; 271 default: abort(); 272 } 273} 274 275bool bitarray_zap(bitarray_t bits, unsigned log_size, index_t index) { 276 assert(log_size <= MAX_LEVEL * NB); 277 assert(index < (1 << log_size)); 278 if (log_size <= NB) return ZAP_CHANGED(bits, index); 279 unsigned level = (log_size - NB - 1) / NB; 280 bool is_now_zero; 281 unsigned bit; 282 bit = index & MASKNB; index >>= NB; 283 if (!ZAP_CHANGED_GO_DOWN(bits + levels_num_words[level] + index*NUM_64b, bit, &is_now_zero)) return 0; 284 if (!is_now_zero) return 1; 285 switch (level) { 286 case 3: 287 bit = index & MASKNB; index >>= NB; 288 if (!ZAP_GO_DOWN(bits + LEVEL2 + index*NUM_64b, bit)) return 1; 289 /* no break */ 290 case 2: 291 bit = index & MASKNB; index >>= NB; 292 if (!ZAP_GO_DOWN(bits + LEVEL1 + index*NUM_64b, bit)) return 1; 293 /* no break */ 294 case 1: 295 bit = index & MASKNB; index >>= NB; 296 if (!ZAP_GO_DOWN(bits + LEVEL0 + index*NUM_64b, bit)) return 1; 297 /* no break */ 298 case 0: 299 ZAP_SIMPLE(bits, index & MASKNB); 300 return 1; 301 default: abort(); 302 } 303} 304 305// Note in the following macro that "words" and "base" are variables being written 306#define ADJUST_OFFSET_FOR_FFS(words, base, current_level) { \ 307words += (1 << (NB * current_level)) * NUM_64b; \ 308base = (base << NB) + FFS(words + base*NUM_64b) - 1; \ 309} 310 311// Note in the following macro that "words" and "base" are variables being written 312#define ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level) {\ 313switch (level) { \ 314case 4: \ 315ADJUST_OFFSET_FOR_FFS(words, base, 0); \ 316ADJUST_OFFSET_FOR_FFS(words, base, 1); \ 317ADJUST_OFFSET_FOR_FFS(words, base, 2); \ 318break; \ 319case 3: \ 320ADJUST_OFFSET_FOR_FFS(words, base, 0); \ 321ADJUST_OFFSET_FOR_FFS(words, base, 1); \ 322break; \ 323case 2: \ 324ADJUST_OFFSET_FOR_FFS(words, base, 0); \ 325break; \ 326case 1: \ 327break; \ 328default: abort(); \ 329} \ 330} 331 332// Note in the following macro that "ix" and "bit" are variables being written 333#define ZAP_SUMMARIES(bits, ix, level) {\ 334unsigned bit; \ 335switch (level) { \ 336case 3: \ 337bit = ix & MASKNB; ix >>= NB; \ 338if (!ZAP_GO_DOWN(bits + LEVEL2 + ix*NUM_64b, bit)) break; \ 339case 2: \ 340bit = ix & MASKNB; ix >>= NB; \ 341if (!ZAP_GO_DOWN(bits + LEVEL1 + ix*NUM_64b, bit)) break; \ 342case 1: \ 343bit = ix & MASKNB; ix >>= NB; \ 344if (!ZAP_GO_DOWN(bits + LEVEL0 + ix*NUM_64b, bit)) break; \ 345case 0: \ 346ZAP_SIMPLE(bits, ix & MASKNB); \ 347break; \ 348default: abort(); \ 349} \ 350} 351 352index_t bitarray_first_set(const bitarray_t bits, unsigned log_size) { 353 // return 0 if none set 354 assert(log_size <= MAX_LEVEL * NB); 355 uint64_t *words = bits; 356 unsigned bit = FFS(words); 357 if (log_size <= NB) return bit; 358 if (!bit) return 0; 359 unsigned level = (log_size - 1) / NB; 360 index_t base = bit - 1; // offset, in number of uin64_t words 361 ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level); 362 words += (1 << (NB * (level-1))) * NUM_64b; 363 base = (base << NB) + FFS(words + base*NUM_64b) - 1; 364 return base+1; //+1 because bit N is encoded as N+1 365} 366 367bool bitarray_zap_first_set(bitarray_t bits, unsigned log_size, index_t *index) { 368 assert(log_size <= MAX_LEVEL * NB); 369 uint64_t *words = bits; 370 index_t ix = FFS(words); 371 if (!ix) return 0; 372 unsigned level = (log_size - 1) / NB; 373 if (! level) { 374 ix--; 375 *index = ix; 376 ZAP_SIMPLE(bits, ix); 377 return 1; 378 } 379 index_t base = ix - 1; // offset, in number of uin64_t words 380 ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level); 381 words += (1 << (NB * (level-1))) * NUM_64b; 382 base = (base << NB) + FFS(words + base*NUM_64b) - 1; 383 ix = base; 384 *index = ix; 385 assert(ix < (1 << log_size)); 386 level--; 387 bool is_now_zero; 388 unsigned bit; 389 bit = ix & MASKNB; ix >>= NB; 390 if (!ZAP_CHANGED_GO_DOWN(bits + levels_num_words[level] + ix*NUM_64b, bit, &is_now_zero)) return 1; 391 if (!is_now_zero) return 1; 392 ZAP_SUMMARIES(bits, ix, level); 393 return 1; 394} 395 396static unsigned FFS_and_zap_word(uint64_t *words, unsigned max, index_t *indices, index_t to_be_added) { 397 // returns the number of bits zapped 398 unsigned zapped = 0; 399 for (unsigned w = 0; w < NUM_64b; w++) { 400 uint64_t word = words[w]; 401 if (!word) continue; 402 while (1) { 403 unsigned f = __ffsll(word); 404 assert(f); 405 f--; 406 // printf("%d ", f); 407 indices[zapped++] = f + (w << 6) + to_be_added; 408 word = BIT_ZAP(word, f); 409 if (!word) break; 410 if (zapped >= max) break; 411 } 412 words[w] = word; 413 // printf("word=%lld \n", word); 414 if (zapped >= max) break; 415 } 416 return zapped; 417} 418 419unsigned bitarray_zap_first_set_multiple(bitarray_t bits, unsigned log_size, unsigned max, index_t *indices) { 420 assert(log_size <= MAX_LEVEL * NB); 421 if (log_size <= NB) return FFS_and_zap_word(bits, max, indices, 0); 422 unsigned zapped = 0; 423 unsigned level = (log_size - 1) / NB; 424 while (zapped < max) { 425 /* the lines in loop could be written just as: 426 // if (! bitarray_zap_first_set(bits, log_size, indices + zapped)) break; 427 // zapped++; 428 but the code is faster because it wont go up and down in the summaries */ 429 uint64_t *words = bits; 430 index_t ix = FFS(words); 431 if (!ix) return zapped; // if the top level summary is 0, no bit is set 432 index_t base = ix - 1; // offset, in number of uin64_t words 433 ADJUST_OFFSET_FOR_FFS_ACROSS_SUMMARIES(words, base, level); 434 words += (1 << (NB * (level-1))) * NUM_64b; // the beginning of the non-summarized bitarray 435 uint64_t *word = words + base*NUM_64b; // the first non-zero word 436 ix = base; 437 // the idea here is that we zap a whole bunch of bits at once 438 unsigned z = FFS_and_zap_word(word, max - zapped, indices + zapped, base << NB); 439 assert(z); 440 zapped += z; 441 if ((zapped < max) /* entire word was zapped */ || all_zeros(word) /* partial zap, a priori */) { 442 // adjust summaries to reflect all zeros in the bitarray 443 ZAP_SUMMARIES(bits, ix, level-1); 444 } 445 } 446 return zapped; 447} 448 449#if 0 450/******************************** Test and debug utilities ***************************/ 451 452static void print_ones(const uint64_t *bits, unsigned num_big_words) { 453 unsigned base = 0; 454 unsigned num = num_big_words * NUM_64b; 455 // printf("In print_ones; num=%d, num_big=%d \n", num, num_big_words); 456 while (num--) { 457 uint64_t word = *(bits++); 458 if (word) { 459 for (unsigned bit = 0; bit < 64; bit++) { 460 if (word & (1ULL << bit)) printf("%d ", base + bit); 461 } 462 } 463 base += 64; 464 } 465} 466 467void bitarray_print(bitarray_t bits, unsigned log_size) { 468 assert(log_size <= MAX_LEVEL * NB); 469 printf("bitarray %p log_size=%d\n", bits, log_size); 470 if (log_size > 4*NB) { 471 printf("Level 4: "); print_ones(bits, 1); printf("\n"); 472 printf("Level 3: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n"); 473 printf("Level 2: "); print_ones(bits + LEVEL1, 1 << NB); printf("\n"); 474 printf("Level 1: "); print_ones(bits + LEVEL2, 1 << NB); printf("\n"); 475 printf("Level 0: "); print_ones(bits + LEVEL3, 1 << (log_size - NB)); printf("\n"); 476 } else if (log_size > 3*NB) { 477 printf("Level 3: "); print_ones(bits, 1); printf("\n"); 478 printf("Level 2: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n"); 479 printf("Level 1: "); print_ones(bits + LEVEL1, 1 << NB); printf("\n"); 480 printf("Level 0: "); print_ones(bits + LEVEL2, 1 << (log_size - NB)); printf("\n"); 481 } else if (log_size > 2*NB) { 482 printf("Level 2: "); print_ones(bits, 1); printf("\n"); 483 printf("Level 1: "); print_ones(bits + LEVEL0, 1 << NB); printf("\n"); 484 printf("Level 0: "); print_ones(bits + LEVEL1, 1 << (log_size - NB)); printf("\n"); 485 } else if (log_size > NB) { 486 printf("Level 1: "); print_ones(bits, 1); printf("\n"); 487 printf("Level 0: "); print_ones(bits + LEVEL0, 1 << (log_size - NB)); printf("\n"); 488 } else { 489 printf("Level 0: "); print_ones(bits, 1); printf("\n"); 490 } 491} 492 493bool compare_to_truth(bitarray_t bits, unsigned nbits, const bool *truth) { 494 uint64_t *start = bits; 495 if (nbits > NB) { 496 unsigned level = (nbits - NB - 1) / NB; 497 start += levels_num_words[level]; 498 } 499 bool ok = 1; 500 for (unsigned bit = 0; bit < (1 << nbits); bit++) { 501 bool expected = truth[bit]; 502 uint64_t word = start[bit >> 6]; 503 bool actual = (word >> (bit & 63)) & 1; 504 if (actual != expected) { 505 printf("*** # for bit %d, expected=%d actual=%d\n", bit, expected, actual); 506 ok = 0; 507 } 508 } 509 return ok; 510} 511 512unsigned first_set_in_truth(const bool *truth, unsigned log_size) { 513 for (unsigned bit = 0; bit < (1 << log_size); bit++) { 514 if (truth[bit]) return bit+1; 515 } 516 return 0; 517} 518 519void truth_print(const bool *truth, unsigned log_size) { 520 printf("Truth: "); 521 for (unsigned bit = 0; bit < (1 << log_size); bit++) { 522 if (truth[bit]) printf("%d ", bit); 523 } 524 printf("\n"); 525} 526#endif 527 528/* vim: set noet:ts=4:sw=4:cindent: */ 529