1/* 2 Title: Bitmap. Generally used by the garbage collector to indicate allocated words 3 4 Copyright (c) 2006, 2012 David C.J. Matthews 5 Based on original code in garbage_collect.c. 6 7 This library is free software; you can redistribute it and/or 8 modify it under the terms of the GNU Lesser General Public 9 License as published by the Free Software Foundation; either 10 version 2.1 of the License, or (at your option) any later version. 11 12 This library is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 Lesser General Public License for more details. 16 17 You should have received a copy of the GNU Lesser General Public 18 License along with this library; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 20 21*/ 22 23/* 24 Bitmaps are used particularly in the garbage collector to indicate allocated 25 words. The efficiency of this code is crucial for the speed of the garbage 26 collector. 27*/ 28 29#ifdef HAVE_CONFIG_H 30#include "config.h" 31#elif defined(_WIN32) 32#include "winconfig.h" 33#else 34#error "No configuration file" 35#endif 36 37#ifdef HAVE_ASSERT_H 38#include <assert.h> 39#define ASSERT(h) assert(h) 40#else 41#define ASSERT(h) 42#endif 43 44#ifdef HAVE_STDLIB_H 45#include <stdlib.h> 46#endif 47 48#ifdef HAVE_MALLOC_H 49#include <malloc.h> 50#endif 51 52#ifdef HAVE_STRING_H 53#include <string.h> 54#endif 55 56#include "bitmap.h" 57#include "globals.h" 58 59bool Bitmap::Create(POLYUNSIGNED bits) 60{ 61 free(m_bits); // Any previous data 62 size_t bytes = (bits+7) >> 3; 63 m_bits = (unsigned char*)calloc(bytes, sizeof(unsigned char)); 64 return m_bits != 0; 65} 66 67void Bitmap::Destroy() 68{ 69 free(m_bits); 70 m_bits = 0; 71} 72 73Bitmap::~Bitmap() 74{ 75 Destroy(); 76} 77 78// Set a range of bits in a bitmap. This checks that the bits are not already set. 79void Bitmap::SetBits(POLYUNSIGNED bitno, POLYUNSIGNED length) 80{ 81 POLYUNSIGNED byte_index = bitno >> 3; 82 83 ASSERT (0 < length); // Strictly positive 84 85 /* Set the first part byte */ 86 POLYUNSIGNED start_bit_index = bitno & 7; 87 POLYUNSIGNED stop_bit_index = start_bit_index + length; 88 /* Do we need to change more than one byte? */ 89 if (stop_bit_index < 8) 90 { 91 const unsigned mask1 = 0xff << start_bit_index; 92 const unsigned mask2 = 0xff << stop_bit_index; 93 const unsigned mask = mask1 & ~mask2; 94 95// ASSERT((m_bits[byte_index] & mask) == 0); 96 m_bits[byte_index] |= mask; 97 return; 98 } 99 else /* Set all the bits we can in the first byte */ 100 { 101 const unsigned mask = 0xff << start_bit_index; 102 103// ASSERT((m_bits[byte_index] & mask) == 0); 104 m_bits[byte_index] |= mask; 105 106 /* length = length - (8 - start_bit_index); */ 107 length = stop_bit_index - 8; 108 } 109 110 /* Set as many full bytes as possible */ 111 if (8 <= length) 112 { 113 memset(m_bits + byte_index + 1, 0xff, length >> 3); 114 byte_index += length >> 3; 115 length &= 7; 116 } 117 118 /* Invariant: 0 <= length < 8 */ 119 ASSERT(length < 8); 120 if (length == 0) return; 121 122 /* Invariant: 0 < length < 8 */ 123 124 /* Set the final part byte */ 125 byte_index ++; 126 const unsigned mask = 0xff & ~(0xff << length); 127// ASSERT((m_bits[byte_index] & mask) == 0); 128 m_bits[byte_index] |= mask; 129} 130 131// Clear a range of bits. This is only used to clear the bitmap so 132// it does not need to be exact so long as at least the range specified 133// is zero. 134void Bitmap::ClearBits(POLYUNSIGNED bitno, POLYUNSIGNED length) 135{ 136 POLYUNSIGNED byte_index = bitno >> 3; 137 length += bitno & 7; 138 size_t bytes = length >> 3; 139 if (length & 7) bytes++; 140 memset(m_bits+byte_index, 0, bytes); 141} 142 143// How many zero bits (maximum n) are there in the bitmap, starting at location start? */ 144POLYUNSIGNED Bitmap::CountZeroBits(POLYUNSIGNED bitno, POLYUNSIGNED n) const 145{ 146 POLYUNSIGNED byte_index = bitno >> 3; 147 unsigned bit_index = bitno & 7; 148 unsigned mask = 1 << bit_index; 149 POLYUNSIGNED zero_bits = 0; 150 ASSERT (0 < n); // Strictly positive 151 152 /* Check the first part byte */ 153 while (mask != 0) 154 { 155 /* zero_bits < n */ 156 if ((m_bits[byte_index] & mask) != 0) return zero_bits; 157 zero_bits ++; 158 if (zero_bits == n) return zero_bits; 159 mask = (mask << 1) & 0xff; 160 /* zero_bits < n */ 161 } 162 163 /* zero_bits < n */ 164 165 /* Check as many bytes as possible */ 166 byte_index ++; 167 while (zero_bits < n && m_bits[byte_index] == 0) 168 { 169 zero_bits += 8; 170 byte_index ++; 171 } 172 173 /* Check the final part byte */ 174 mask = 1; 175 while (zero_bits < n && (m_bits[byte_index] & mask) == 0) 176 { 177 zero_bits ++; 178 mask = (mask << 1) & 0xff; 179 } 180 181 return zero_bits; 182} 183 184 185// Search the bitmap from the high end down looking for n contiguous zeros 186// Returns the value of "bitno" on failure. . 187POLYUNSIGNED Bitmap::FindFree 188( 189 POLYUNSIGNED limit, /* The highest numbered bit that's too small to use */ 190 POLYUNSIGNED start, /* The lowest numbered bit that's too large to use */ 191 POLYUNSIGNED n /* The number of consecutive zero bits required */ 192) const 193{ 194 if (limit + n >= start) 195 return start; // Failure 196 197 POLYUNSIGNED candidate = start - n; 198 ASSERT (start > limit); 199 200 while (1) 201 { 202 POLYUNSIGNED bits_free = CountZeroBits(candidate, n); 203 204 if (n <= bits_free) 205 return candidate; 206 207 if (candidate < n - bits_free + limit) 208 return start; // Failure 209 210 candidate -= (n - bits_free); 211 } 212} 213 214// Count the number of set bits in the bitmap. 215POLYUNSIGNED Bitmap::CountSetBits(POLYUNSIGNED size) const 216{ 217 size_t bytes = (size+7) >> 3; 218 POLYUNSIGNED count = 0; 219 for (size_t i = 0; i < bytes; i++) 220 { 221 unsigned char byte = m_bits[i]; 222 if (byte == 0xff) // Common case 223 count += 8; 224 else 225 { 226 while (byte != 0) 227 { 228 unsigned char b = byte & (-byte); 229 count++; 230 byte -= b; 231 } 232 } 233 } 234 return count; 235} 236 237// Find the last set bit before here. Used to find the start of a code cell. 238// Returns zero if no bit is set. 239POLYUNSIGNED Bitmap::FindLastSet(POLYUNSIGNED bitno) const 240{ 241 size_t byteno = bitno >> 3; 242 // Code cells are quite long so most of the bitmap will be zero. 243 if (m_bits[byteno] == 0) 244 { 245 do { 246 if (byteno == 0) return 0; 247 byteno--; 248 } while (m_bits[byteno] == 0); 249 bitno = (byteno << 3) + 7; // Set it to the last bit 250 } 251 while (bitno > 0 && ! TestBit(bitno)) bitno--; 252 return bitno; 253}