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}