1/* 2 * Copyright (c) 2011 Apple Inc. All rights reserved. 3 * 4 * @APPLE_APACHE_LICENSE_HEADER_START@ 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 * 18 * @APPLE_APACHE_LICENSE_HEADER_END@ 19 */ 20/* 21 Bitmap.cpp 22 High Performance Bitmap 23 Copyright (c) 2004-2011 Apple Inc. All rights reserved. 24 */ 25 26#include "Definitions.h" 27#include "Bitmap.h" 28 29 30namespace Auto { 31 32 //----- Bitmap -----// 33 34 // 35 // Bitmaps (bit vectors) are a fast and lightweight means of showing set 36 // representation. A single bit is used to indicate membership in the set; 1 37 // indicating membership and 0 indicating exclusion. In this representation we use 38 // an array of unsigned long words. Each word represents a unit of bits_per_word members 39 // numbered from the least significant bit (endian representation is not 40 // important.) Thus for any member k its word index would be equal to (k / bits_per_word) or 41 // (k >> ilog2(bits_per_word)) and its bit position would be equal to (k % bits_per_word). 42 // 43 44 45 // 46 // set_bits_large 47 // 48 // Set n bits in the bit map to 1 spanning more than one word. 49 // Assumes that range spans more than one word. 50 // 51 void Bitmap::set_bits_large(const usword_t bp, const usword_t n) const { 52 usword_t *cursor = bp_cursor(bp); // address of first word 53 const usword_t sh = shift(bp); // bit shift 54 55 // set first word bits 56 *cursor++ |= (all_ones << sh); 57 58 // calculate overflow 59 signed spill = sh + n - bits_per_word; 60 61 // fill in full words 62 for ( ; spill >= (sword_t)bits_per_word; spill -= bits_per_word) *cursor++ = all_ones; 63 64 // remaining bits 65 if (spill > 0) *cursor |= (all_ones >> (bits_per_word - spill)); 66 } 67 68 69 // 70 // clear_bits_large 71 // 72 // Set n bits in the bit map to 0 spanning more than one word. 73 // Assumes that range spans more than one word. 74 // 75 void Bitmap::clear_bits_large(const usword_t bp, const usword_t n) const { 76 usword_t *cursor = bp_cursor(bp); // address of first word 77 const usword_t sh = shift(bp); // bit shift 78 79 // set first word bits 80 *cursor++ &= ~(all_ones << sh); 81 82 // calculate overflow 83 signed spill = sh + n - bits_per_word; 84 85 // fill in full words 86 for ( ; spill >= (sword_t)bits_per_word; spill -= bits_per_word) *cursor++ = all_zeros; 87 88 // remaining bits 89 if (spill > 0) *cursor &= ~(all_ones >> (bits_per_word - spill)); 90 } 91 92 93 bool Bitmap::bits_are_clear_large(const usword_t bp, const usword_t n) const { 94 usword_t *cursor = bp_cursor(bp); // address of first word 95 const usword_t sh = shift(bp); // bit shift 96 97 // check first word bits 98 if (*cursor++ & (all_ones << sh)) return false; 99 100 // calculate overflow 101 signed spill = sh + n - bits_per_word; 102 103 // fill in full words 104 for ( ; spill >= (sword_t)bits_per_word; spill -= bits_per_word) 105 if (*cursor++) return false; 106 107 // check remaining bits 108 if (spill > 0) { 109 if (*cursor & (all_ones >> (bits_per_word - spill))) 110 return false; 111 } 112 113 return true; 114 } 115 116 117 // 118 // count_set 119 // 120 // Returns the number of bits set (one) in the bit map using 121 // a standard bit population algoirithm (ref. Hacker's Delight.) 122 // in 64 bit word treat bits array as 32 bit array. 123 // 124 usword_t Bitmap::count_set() const { 125 register const unsigned fives = 0x55555555; 126 register const unsigned threes = 0x33333333; 127 register const unsigned nibbles = 0x0f0f0f0f; 128 register const unsigned bytes = 0x00ff00ff; 129 register const unsigned shorts = 0x0000ffff; 130 register usword_t count = 0; 131 register usword_t size = this->size() >> sizeof(unsigned); 132 register unsigned *bits = (unsigned *)address(); 133 134 for (usword_t i = 0; i < size; i += 31) { 135 usword_t lim = min(size, i + 31); 136 usword_t sum8 = 0; 137 138 for (usword_t j = i; j < lim; j++) { 139 usword_t x = bits[j]; 140 x = x - ((x >> 1) & fives); 141 x = (x & threes) + ((x >> 2) & threes); 142 x = (x + (x >> 4)) & nibbles; 143 sum8 = sum8 + x; 144 } 145 146 usword_t y = (sum8 & bytes) + ((sum8 >> 8) & bytes); 147 y = (y & shorts) + (y >> 16); 148 count += y; 149 } 150 151 return count; 152 } 153 154 155 // 156 // previous_set 157 // 158 // Return the bit postion of the 1 that comes at or prior to the bit position 'bp'. 159 // 160 usword_t Bitmap::previous_set(const usword_t bp) const { 161 usword_t *cursor = bp_cursor(bp); // address of bit map data 162 usword_t *first = bp_cursor(0); // first address 163 usword_t sh = shift(bp); // bit shift 164 usword_t word = 0; // bit map word 165 166 // read first word and eliminate following 1s if not first position 167 if (sh) word = *cursor & mask(sh); 168 169 // skip backward looking for set bit 170 if (is_all_zeros(word)) { 171 // skip through zeroes quickly 172 cursor = skip_backward_all_zeros(cursor - 1, first); 173 174 // get word if at end make sure 175 if ( cursor >= first) word = *cursor; 176 else return not_found; 177 } 178 179 // return bit position of 1 180 return cursor_bp(cursor) + ilog2(word); 181 } 182 183 184 // 185 // next_set 186 // 187 // Return the bit postion of the 1 that comes at or after to the bit position 'bp'. 188 // 189 usword_t Bitmap::next_set(const usword_t bp) const { 190 usword_t *cursor = bp_cursor(bp); // address of bit map data 191 usword_t *end = end_cursor(); // end address 192 usword_t sh = shift(bp); // bit shift 193 194 // may be at the last word 195 if (cursor >= end) return not_found; 196 197 // read first bit map word 198 usword_t word = *cursor; 199 200 // eliminate prior 1s if not first position 201 if (sh) word &= ~mask(sh); 202 203 // do we need to skip some words 204 if (is_all_zeros(word)) { 205 // skip through zeroes quickly 206 cursor = skip_all_zeros(cursor + 1, end); 207 208 // get next word 209 word = cursor < end ? *cursor : all_ones; 210 } 211 212 // return bit position of 1 (not_found if not found) 213 return cursor < end ? cursor_bp(cursor) + count_trailing_zeros(word) : not_found; 214 } 215 216 // 217 // fetch_clear_bits_atomic 218 // 219 // fetch and clear multiple bits at a time 220 // bp is the index of the first bit to fetch, max is the first index *not* to be fetched 221 // returns a word containing the fetched bits, and by reference in count the number of valid bits in the return 222 // returned bits start at bit 0, and bits higher than count are zeroed 223 // 224 usword_t Bitmap::AtomicCursor::fetch_clear_bits_atomic(const usword_t bp, const usword_t max, usword_t &count) { 225 usword_t result_shift = bp & mask(bits_per_word_log2); 226 count = bits_per_word - result_shift; 227 if (count > max - bp) 228 count = max - bp; 229 usword_t result_mask = mask(count); 230 usword_t result = _bitmap.atomic_and_return_orig(~(result_mask << result_shift), _bitmap.bp_cursor(bp)); 231 result = (result >> result_shift) & result_mask; 232 return result; 233 } 234 235 // 236 // next_set_bit 237 // 238 // Returns the index of a set bit from the bitmap range. If no bits are set, returns -1. 239 // The returned value is the offset from the start index passed to the constructor. 240 // So if 5 is passed as the start bit to the constructor and bit 8 is the first set bit in the bitmap, 241 // the first callto next_set_bit() will return 3. (This is done because the cursor is used 242 // to enumerate subzone quanta, which are zero based.) 243 // 244 usword_t Bitmap::AtomicCursor::next_set_bit() { 245 usword_t result; 246 247 // May still have some valid bits from the last time. If they are zero then adjust index. 248 if (_copied_bits == 0) { 249 _index += _valid_bits; 250 } 251 252 // if there are no nonzero _copied_bits, this loop scans a word at a time until some nonzero bits are found 253 if (_copied_bits == 0 && _index < _max_index) { 254 ASSERTION((_index % bits_per_word) == 0); 255 usword_t *start = _bitmap.bp_cursor(_index); 256 usword_t *end = _bitmap.bp_cursor(_max_index); 257 usword_t *cursor = _bitmap.skip_all_zeros(start, end); 258 _index = _bitmap.cursor_bp(cursor); 259 if (_index < _max_index) { 260 // at this point we fetch either some nonzero bits or a partial word at the end of the range 261 _copied_bits = fetch_clear_bits_atomic(_index, _max_index, _valid_bits); 262 } 263 } 264 265 // there are either nonzero bits in _copied_bits or we are done 266 if (_copied_bits != 0) { 267 usword_t shift = count_trailing_zeros(_copied_bits); 268 result = _index + shift - _offset; 269 // Need to shift _copied_bits by (shift+1). But if shift+1 == bits_per_word then the bitwise shift is undefined. 270 // So just shift by shift and again by 1 rather than introduce a test/branch. 271 _copied_bits >>= shift; 272 _copied_bits >>= 1; 273 shift++; 274 _index += shift; 275 _valid_bits -= shift; 276 } else { 277 // no nonzero bits, so we are done 278 result = (usword_t)-1; 279 _index = _max_index; 280 } 281 return result; 282 } 283}; 284 285