# auto_bitmaps.c   [plain text]

```/*
*
*
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
*
* Unless required by applicable law or agreed to in writing, software
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
*
*/

#import "auto_impl_utilities.h"
#import "auto_bitmaps.h"

#import <libc.h>
#import <objc/malloc.h>

/*********  32-bit-at-a-time bitmaps ***************/

//
// FIND BIT SEQUENCE ALGORITHM
//
// The algorithm used here takes advantage of fast bit count available on the PowerPC
//
// The find bit sequence algorithm iterates through each word in the bitmap examining
// consecutive runs of 0s or 1s.
//
// We start by setting up a mask of N one bits (least significant end.)  This will
// be used to detect the run of 0s we need.
//
// Iterating through each word we look to see if the least significant bits are 0.
// 'trailing_zeroes' returns a consecutive run of 1s for each 0 in the least
// significant end of the word.  If this run is >= than our mask then we can return
// our result.
//
// To look at the next run of 0s in the word we need to skip the current run of 0s
// and the adjacent run of 1s.  We can do this by merging the run we just
// constructed (1s for 0s) from 'trailing_zeroes' and the original word.  We can
// then generate a run of trailing 1s and count the bits in this.  This count can
// be used to shift the word to the next run of 0s.  We also track the bit position
// in the word ('bit'.)
//
// If the original word has a run of 0s in the most significant bits then we need
// to set up a barrier of 1s to get an accurate count of 0s.  We can do this by
// inverting the previous run and shifting by the current bit position.
//
// If the original word has a run of 0s in the most significant bits we may need to
// carry forward those 0s to append the end of the next word.  We do this by
// setting 'bit' to the negative of the number of 0s left over.  This has two
// advantages.  It gives us an indicator of the carry forward ('bit' < 0) and the
// calculation of overall bit position naturally corrects against the next word.
//
// If we encounter a word of all 0s the we have an immediate result.  If we
// encounter a word of all 1s then we need to reset and skip the word.
//
// This process continues until we either return or reach the end of the bitmap.
//
// Example: Find a sequence of seven 0 bits.
//
//   bitmap[] = {
//     0b0000_1111_1111_1111_1111_1111_1110_0000,
//     0b0000_0000_0000_0000_0000_0000_1111_1000,
//     ... };
//
//
//   Setup:
//
//     index = 0;
//     bit = 0;               // bit position 0 (least significant bit)
//     word = bitmap[index];  // get the first word
//
//
//   Isolate the trailing 0s:
//
//     run      = trailing_zeros(word);
//     0b1_1111 = trailing_zeros(0b0000_1111_1111_1111_1111_1111_1110_0000);
//
//
//   Check to see if the run is greater or equal to our mask:
//
//     run      >= mask is not true so we continue.
//     0b1_1111 >= 0b111_1111
//
//
//   Merge the run with the original word:
//
//     run                                       = word                                      | run;
//     0b0000_1111_1111_1111_1111_1111_1111_1111 = 0b0000_1111_1111_1111_1111_1111_1110_0000 | 0b1_1111
//
//
//   Isolate the trailing 1s:
//
//     run                                       = trailing_ones(run);
//     0b0000_1111_1111_1111_1111_1111_1111_1111 = trailing_ones(0b0000_1111_1111_1111_1111_1111_1111_1111);
//
//
//   Count the trailing 1s:
//
//     count = bitmap_count(run);
//     28    = bitmap_count(0b0000_1111_1111_1111_1111_1111_1111_1111);
//
//
//   Shift word and increment bit position:
//
//     word                                      = word                                      >> count;
//     0b0000_0000_0000_0000_0000_0000_0000_0000 = 0b0000_1111_1111_1111_1111_1111_1110_0000 >> 28;
//
//     bit += count;
//     28
//
//
//   Word is zero so we need to check to see if there were enough bits left:
//
//     run                                       = ~run;
//     0b1111_0000_0000_0000_0000_0000_0000_0000 = 0b0000_1111_1111_1111_1111_1111_1111_1111;
//
//     run     = run                                       >> count;
//     0xb1111 = 0b1111_0000_0000_0000_0000_0000_0000_0000 >> 28;
//
//     run     >= mask is not true so we continue.
//     0xb1111 >= 0b111_1111
//
//
//   To indicate carry word we set bit negative:
//
//     bit = bit - 32;
//     -4  = 28  - 32;
//
//
//   We get the next word and adjust it to pretend there were extra 0s from the previous word.
//
//     next = bitmap[++index];
//     word                                      = next                                      << -bit;
//     0b0000_0000_0000_0000_0000_1111_1000_0000 = 0b0000_0000_0000_0000_0000_0000_1111_1000 << -(-4);
//
//
//   The process is repeated but this time we have a match:
//
//     run      >= mask  so we have a match
//     0b111_1111 >= 0b111_1111
//
//
//   If it didn't match, bit < 0 indicates that we need to correct from the carry forward.
//

//
// Return the longest sequence of 0 bits in the bitmap (maximum 'MAX_SEQ'.)
//
// Using the Find Bit Sequence Algorithm (see above) we search for a sequence of MAX_SEQ 0s.
// Along the way we track the longest run of 0s we encounter.  The result is the longest
// run found.
//
unsigned bitmap_max_seq(const auto_bitmap_t bitmap, unsigned num_words) {
unsigned    max_seq = 0;            // maximum seq found
unsigned    index = 0;              // index of 32 bit word in bitmap
unsigned    word = bitmap[0];       // current word from bitmap
signed      bit = 0;                // current bit in word, if bit < 0 then word spans from previous word
unsigned    next = 0;               // next word from bitmap

if (!num_words) return 0;           // exit early if empty bitmap

while (1) {
unsigned    run;                // mask of consecutive bits
unsigned    shift;              // required shift

// exit early if word is all clear
if (!word) return MAX_SEQ;

// get the run (mask) of trailing zeros
run = trailing_zeroes(word);

// if there is a run update the maximum
if (run) {
// if the run exceeds or equals mask then we have enough (note: bit may be carry over from previous word)
if (run >= mask) return MAX_SEQ;

unsigned    lng = bitmap_count(run);
max_seq = lng > max_seq ? lng : max_seq;
}

// get the run (mask) of ones including the previous run of zeroes
run = trailing_ones(word | run);

// if we span from previous word then correct for rest of word
if (bit < 0) {
run >>= -bit;
word = next;
bit = 0;
}

// compute the shift we need to get the previous ones and zeroes out of the way
shift = bitmap_count(run);

// get the previous ones and zeroes out of the way
word >>= shift;

// update the bit position
bit += shift;

// if the rest of the word is zero
if (!word) {
run = ~run >> bit;

if (run) {
// check to see if what is left is big enough
if (run >= mask) return MAX_SEQ;

unsigned    lng = bitmap_count(run);
max_seq = lng > max_seq ? lng : max_seq;
}

while (1) {
// if there are no more words we are out of luck
if (++index >= num_words) return max_seq;

// get the next word
next = bitmap[index];

// continue if some bits clear
if (~next) break;

// need to reset bit position and try again
bit = 32;
}

// set up a negative bit value if there are bits left over from previous word, otherwise start at zero
bit = bit < 32 ? bit - 32 : 0;

// make adjustment if zeroes in previous word
word = next << -bit;
}
}

return max_seq;
}

//
// Return the bit position of the first sequence of 0 bits with length >= 'seq'.  If no sequence is
// found the result is NOT_FOUND.
//
// Using the Find Bit Sequence Algorithm (see above) we search for a sequence of 'seq' 0s.
// When we find a match then we return the result of (index * BITSPERWORD + bit).  Note: if 'bit' < 0
// then the result is still correct since index has been advanced to the next word.
//
unsigned bitmap_find_clear_sequence(const auto_bitmap_t bitmap, unsigned num_words, const unsigned seq) {
// finds the first sequence in the bitmap with seq (1..MAX_SEQ) bits free (zero)
// may read up to num_words of bitmap
// returns bit position
unsigned    index = 0;              // index of 32 bit word in bitmap
unsigned    word = bitmap[0];       // current word from bitmap
signed      bit = 0;                // current bit in word, if bit < 0 then word spans from previous word
unsigned    next = 0;               // next word from bitmap

if (!num_words) return NOT_FOUND;   // exit early if empty bitmap

while (1) {
unsigned    run;                // mask of consecutive bits
unsigned    shift;              // required shift

// exit early if word is all clear
if (!word) return index * BITSPERWORD + bit;

// get the run (mask) of trailing zeros
run = trailing_zeroes(word);

// if the run exceeds or equals mask then we have enough (note: bit may be carry over from previous word)
if (run >= mask) return index * BITSPERWORD + bit;

// get the run (mask) of ones including the previous run of zeroes
run = trailing_ones(word | run);

// if we span from previous word then correct for rest of word
if (bit < 0) {
run >>= -bit;
word = next;
bit = 0;
}

// compute the shift we need to get the previous ones and zeroes out of the way
shift = bitmap_count(run);

// get the previous ones and zeroes out of the way
word >>= shift;

// update the bit position
bit += shift;

// if the rest of the word is zero
if (!word) {
// remaining zeros
run = ~run >> bit;

// check to see if what is left is big enough
if (run >= mask) return index * BITSPERWORD + bit;

while (1) {
// if there are no more words we are out of luck
if (++index >= num_words) return NOT_FOUND;

// get the next word
next = bitmap[index];

// continue if some bits clear
if (~next) break;

// need to reset bit position and try again
bit = 32;
}

// set up a negative bit value if there are bits left over from previous word, otherwise start at zero
bit = bit < 32 ? bit - 32 : 0;

// make adjustment if zeroes in previous word
word = next << -bit;
}
}

// out of luck
return NOT_FOUND;
}

//
// Return the number of contiguous 1 bits found in the bitmap 'in_use' starting at 'bit' and bounded by 1 bits
// found in the bitmap 'ptr_start'.
//
// The bitmap 'in_use' represents block availability; a 1 indicating the block is in use and 0 indicating
// the block is free.
//
// The bitmap 'ptr_start' represents the set of first blocks.  A 1 indicates that the block begins a new block.
//
// Example:
//
//   in_use[] = {
//     0b0000_0000_0000_0000_0000_1111_1111_1111,
//     ... };
//
//   ptr_start[] = {
//     0b0000_0000_0000_0000_0000_0000_1001_0001,
//     ... };
//
//   bit = 4;
//
//
// Setup:
//
//   index = bit >> BITSPERWORDLOG2;
//   0     = 4   >> 5;
//
//   shift = bit & BITSPERWORDMASK;
//   4     = 4   & 31;
//
//
// Get first words and position to bit (spanning words are not necessary in this example):
//   in_use_bits                               = in_use[index]                             >> shift;
//   0b0000_0000_0000_0000_0000_0000_1111_1111 = 0b0000_0000_0000_0000_0000_1111_1111_1111 >> 4;
//
//   ptr_start_bits                            = ptr_start[index]                          >> shift;
//   0b0000_0000_0000_0000_0000_0000_0000_1001 = 0b0000_0000_0000_0000_0000_0000_1001_0001 >> 4;
//
//
// Clear out starts:
//
//   in_use_bits                               = in_use_bits                               & ~ptr_start_bits;
//   0b0000_0000_0000_0000_0000_0000_1111_0110 = 0b0000_0000_0000_0000_0000_0000_1111_1111 & ~0b0000_0000_0000_0000_0000_0000_0000_1001;
//
//
// Add first block back in:
//
//   in_use_bits                               = in_use_bits                               | 1;
//   0b0000_0000_0000_0000_0000_0000_1111_0111 = 0b0000_0000_0000_0000_0000_0000_1111_0110 | 1;
//
//
// Isolate trailing 1s:
//
//   in_use_bits                               = trailing_ones(in_use_bits);
//   0b0000_0000_0000_0000_0000_0000_0000_0111 = trailing_ones(0b0000_0000_0000_0000_0000_0000_1111_0111);
//
//
// Count trailing 1s:
//
//   return bitmap_count(in_use_bits);
//   3      bitmap_count(0b0000_0000_0000_0000_0000_0000_0000_0111;
//
unsigned bitmap_blocks_used(const auto_bitmap_t in_use, const auto_bitmap_t ptr_start, const unsigned bit) {
unsigned    index = bit >> BITSPERWORDLOG2;     // index of 32 bit word in bitmap holding bit
unsigned    shift = bit & BITSPERWORDMASK;      // shift to extract bit

// extract portion from first word
unsigned in_use_bits = in_use[index] >> shift;
unsigned ptr_start_bits = ptr_start[index] >> shift;

if ((shift + 7) > BITSPERWORD) {
// extract spanning part if necessary
unsigned inverse_shift = 32 - shift;
in_use_bits |= in_use[index + 1] << inverse_shift;
ptr_start_bits |= ptr_start[index + 1] << inverse_shift;
}

// clear starting bits (beginning of next)
in_use_bits &= ~ptr_start_bits;

// add back in this block's first
in_use_bits |= 1;

// count the in use bits
return bitmap_count(trailing_ones(in_use_bits));
}

//
// Return the number of 1 bits in the set.
//
// Looking a word at a time we count the run of 1s in the least significant portion
// of the word.  Then we skip over the 1s and the adjacent 0s. repeat until the
// word is zero.
//
unsigned bitmap_count_set(const auto_bitmap_t bitmap, unsigned num_words) {
unsigned    num_bits = 0;       // running count of set bits

// while there are words
while (num_words--) {
// get the next word (last to first)
unsigned    word = bitmap[num_words];

// while the word has bits set
while (word) {
// get the run of trailing ones
unsigned    run = trailing_ones(word);

// count those bits
num_bits += bitmap_count(run);

// clear those bits
word &= ~run;

// shift up to the next sequence of ones
word >>= bitmap_count(trailing_zeroes(word));
}
}

// return the number of bits
return num_bits;
}

//
// Returns the bit position of the first and last 1 bits in the set.  If *first > *last the the set is empty
//
// Starting form the beginning we look for a non-zero word in the bitmap.  We then count the trailing 0s to
// find the first bit position.
//
// Then starting from the end look for a the last non-zero word.   Then we count leading 0s (more or less) to
// find the last bit position.
//
void bitmap_range_set(const auto_bitmap_t bitmap, unsigned num_words, unsigned *first, unsigned *last) {
unsigned    lo = 0, hi = num_words;     // index range to look
unsigned    word;                       // current word

// skip zero words from the first
for ( word = bitmap[0]; !word && lo < hi; word = bitmap[++lo]) {}

// if no non zero words found
if (lo >= hi) {
*first = UNLIMITED;
*last = 0;
}

// set up the first bit
*first = (lo * BITSPERWORD) + bitmap_count(trailing_zeroes(word));

// skip zero words from the last
for (word = bitmap[--hi]; !word && lo <= hi; word = bitmap[--hi]) {}

// set up the last bit
*last = (hi * BITSPERWORD) + bitmap_count(word);
}

//
// Diagnositic printing of the bitmap.
//
void bitmap_print(auto_bitmap_t bitmap, unsigned num_words) {
unsigned    num_all_0 = 0;
unsigned    num_all_1 = 0;
while (num_words--) {
unsigned    word = *bitmap++;
if (!word) {
if (num_all_1) { printf("1*%d ", num_all_1); num_all_1 = 0; }
num_all_0++;
} else if (!~word) {
if (num_all_0) { printf("0*%d ", num_all_0); num_all_0 = 0; }
num_all_1++;
} else {
if (num_all_0) { printf("0*%d ", num_all_0); num_all_0 = 0; }
if (num_all_1) { printf("1*%d ", num_all_1); num_all_1 = 0; }
unsigned    bit = 0;
while (bit < 32) {
printf("%d", bitmap_bit(&word, bit));
bit++;
}
printf(" ");
}
}
if (num_all_0) { printf("0*%d ", num_all_0); num_all_0 = 0; }
if (num_all_1) { printf("1*%d ", num_all_1); num_all_1 = 0; }
printf("\n");
}
```