Bitmap.cpp   [plain text]


/*
 * Copyright (c) 2011 Apple Inc. All rights reserved.
 *
 * @APPLE_APACHE_LICENSE_HEADER_START@
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *     http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * 
 * @APPLE_APACHE_LICENSE_HEADER_END@
 */
/*
    Bitmap.cpp
    High Performance Bitmap
    Copyright (c) 2004-2011 Apple Inc. All rights reserved.
 */

#include "Definitions.h"
#include "Bitmap.h"


namespace Auto {

    //----- Bitmap -----//

    //
    // Bitmaps (bit vectors) are a fast and lightweight means of showing set
    // representation.  A single bit is used to indicate membership in the set; 1
    // indicating membership and 0 indicating exclusion.  In this representation we use
    // an array of unsigned long words. Each word represents a unit of bits_per_word members
    // numbered from the least significant bit (endian representation is not
    // important.)  Thus for any member k its word index would be equal to (k / bits_per_word) or
    // (k >> ilog2(bits_per_word)) and its bit position would be equal to (k % bits_per_word).
    //
    

    //
    // set_bits_large
    //
    // Set n bits in the bit map to 1 spanning more than one word.
    // Assumes that range spans more than one word.
    //
    void Bitmap::set_bits_large(const usword_t bp, const usword_t n) const {
        usword_t *cursor = bp_cursor(bp);                   // address of first word
        const usword_t sh = shift(bp);                      // bit shift
        
        // set first word bits
        *cursor++ |= (all_ones << sh);
        
        // calculate overflow
        signed spill = sh + n - bits_per_word;
        
        // fill in full words
        for ( ; spill >= (sword_t)bits_per_word; spill -= bits_per_word) *cursor++ = all_ones;
        
        // remaining bits
        if (spill > 0) *cursor |= (all_ones >> (bits_per_word - spill));
    }
        
    
    //
    // clear_bits_large
    //
    // Set n bits in the bit map to 0 spanning more than one word.
    // Assumes that range spans more than one word.
    //
    void Bitmap::clear_bits_large(const usword_t bp, const usword_t n) const {
        usword_t *cursor = bp_cursor(bp);                   // address of first word
        const usword_t sh = shift(bp);                      // bit shift
        
        // set first word bits
        *cursor++ &= ~(all_ones << sh);
        
        // calculate overflow
        signed spill = sh + n - bits_per_word;
        
        // fill in full words
        for ( ; spill >= (sword_t)bits_per_word; spill -= bits_per_word) *cursor++ = all_zeros;
        
        // remaining bits
        if (spill > 0) *cursor &= ~(all_ones >> (bits_per_word - spill));
    }        
    
    
    bool Bitmap::bits_are_clear_large(const usword_t bp, const usword_t n) const {
        usword_t *cursor = bp_cursor(bp);                   // address of first word
        const usword_t sh = shift(bp);                      // bit shift
        
        // check first word bits
        if (*cursor++ & (all_ones << sh)) return false;
        
        // calculate overflow
        signed spill = sh + n - bits_per_word;
        
        // fill in full words
        for ( ; spill >= (sword_t)bits_per_word; spill -= bits_per_word)
            if (*cursor++) return false;
        
        // check remaining bits
        if (spill > 0) {
            if (*cursor & (all_ones >> (bits_per_word - spill)))
                return false;
        }
        
        return true;
    }        
    
    
    //
    // count_set
    //
    // Returns the number of bits set (one) in the bit map using
    // a standard bit population algoirithm (ref. Hacker's Delight.)
    // in 64 bit word treat bits array as 32 bit array.
    //
    usword_t Bitmap::count_set() const {
        register const unsigned fives = 0x55555555;
        register const unsigned threes = 0x33333333;
        register const unsigned nibbles = 0x0f0f0f0f;
        register const unsigned bytes = 0x00ff00ff;
        register const unsigned shorts = 0x0000ffff;
        register usword_t   count = 0;
        register usword_t   size = this->size() >> sizeof(unsigned);
        register unsigned   *bits = (unsigned *)address();
        
         for (usword_t i = 0; i < size; i += 31)  {
            usword_t lim = min(size, i + 31);
            usword_t sum8 = 0;
            
            for (usword_t j = i; j < lim; j++) {
                usword_t x = bits[j];
                x = x - ((x >> 1) & fives);
                x = (x & threes) + ((x >> 2) & threes);
                x = (x + (x >> 4)) & nibbles;
                sum8 = sum8 + x;
            }
            
            usword_t y = (sum8 & bytes) + ((sum8 >> 8) & bytes);
            y = (y & shorts) + (y >> 16);
            count += y;
        }
        
        return count;
    }

    
    //
    // previous_set
    //
    // Return the bit postion of the 1 that comes at or prior to the bit position 'bp'.
    //
    usword_t Bitmap::previous_set(const usword_t bp) const {
        usword_t *cursor = bp_cursor(bp);                   // address of bit map data
        usword_t *first = bp_cursor(0);                     // first address
        usword_t sh = shift(bp);                            // bit shift
        usword_t word = 0;                                  // bit map word
        
        // read first word and eliminate following 1s if not first position
        if (sh) word = *cursor & mask(sh);

        // skip backward looking for set bit
        if (is_all_zeros(word)) {
            // skip through zeroes quickly
            cursor = skip_backward_all_zeros(cursor - 1, first);
            
            // get word if at end make sure 
            if ( cursor >= first)  word = *cursor;
            else                   return not_found;
        }
        
        // return bit position of 1
        return cursor_bp(cursor) + ilog2(word);
    }
    
    
    //
    // next_set
    //
    // Return the bit postion of the 1 that comes at or after to the bit position 'bp'.
    //
    usword_t Bitmap::next_set(const usword_t bp) const {
        usword_t *cursor = bp_cursor(bp);                   // address of bit map data
        usword_t *end = end_cursor();                       // end address
        usword_t sh = shift(bp);                            // bit shift
        
        // may be at the last word
        if (cursor >= end) return not_found;
        
        // read first bit map word
        usword_t word = *cursor;                            

        // eliminate prior 1s if not first position
        if (sh) word &= ~mask(sh);
        
        // do we need to skip some words
        if (is_all_zeros(word)) {
            // skip through zeroes quickly
            cursor = skip_all_zeros(cursor + 1, end);
            
            // get next word
            word = cursor < end ? *cursor : all_ones;
        }
        
        // return bit position of 1 (not_found if not found)
        return cursor < end ? cursor_bp(cursor) + count_trailing_zeros(word) : not_found;
    }
            
    //
    // fetch_clear_bits_atomic
    //
    // fetch and clear multiple bits at a time
    // bp is the index of the first bit to fetch, max is the first index *not* to be fetched
    // returns a word containing the fetched bits, and by reference in count the number of valid bits in the return
    // returned bits start at bit 0, and bits higher than count are zeroed
    //
    usword_t Bitmap::AtomicCursor::fetch_clear_bits_atomic(const usword_t bp, const usword_t max, usword_t &count) {            
        usword_t result_shift = bp & mask(bits_per_word_log2);
        count = bits_per_word - result_shift;
        if (count > max - bp)
            count = max - bp;
        usword_t result_mask = mask(count);
        usword_t result = _bitmap.atomic_and_return_orig(~(result_mask << result_shift), _bitmap.bp_cursor(bp));
        result = (result >> result_shift) & result_mask;
        return result;
    }
    
    //
    // next_set_bit
    //
    // Returns the index of a set bit from the bitmap range. If no bits are set, returns -1.
    // The returned value is the offset from the start index passed to the constructor.
    // So if 5 is passed as the start bit to the constructor and bit 8 is the first set bit in the bitmap,
    // the first callto next_set_bit() will return 3. (This is done because the cursor is used
    // to enumerate subzone quanta, which are zero based.)
    //
    usword_t Bitmap::AtomicCursor::next_set_bit() {
        usword_t result;
        
        // May still have some valid bits from the last time. If they are zero then adjust index.
        if (_copied_bits == 0) {
            _index += _valid_bits;
        }
        
        // if there are no nonzero _copied_bits, this loop scans a word at a time until some nonzero bits are found
        if (_copied_bits == 0 && _index < _max_index) {
            ASSERTION((_index % bits_per_word) == 0);
            usword_t *start = _bitmap.bp_cursor(_index);
            usword_t *end = _bitmap.bp_cursor(_max_index);
            usword_t *cursor = _bitmap.skip_all_zeros(start, end);
            _index = _bitmap.cursor_bp(cursor);
            if (_index < _max_index) {
                // at this point we fetch either some nonzero bits or a partial word at the end of the range
                _copied_bits = fetch_clear_bits_atomic(_index, _max_index, _valid_bits);
            }
        }
        
        // there are either nonzero bits in _copied_bits or we are done
        if (_copied_bits != 0) {
            usword_t shift = count_trailing_zeros(_copied_bits);
            result = _index + shift - _offset;
            // Need to shift _copied_bits by (shift+1). But if shift+1 == bits_per_word then the bitwise shift is undefined.
            // So just shift by shift and again by 1 rather than introduce a test/branch.
            _copied_bits >>= shift;
            _copied_bits >>= 1;
            shift++;
            _index += shift;
            _valid_bits -= shift;
        } else {
            // no nonzero bits, so we are done
            result = (usword_t)-1;
            _index = _max_index;
        }
        return result;
    }
};