1// Copyright (c) 2009 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "net/disk_cache/blockfile/bitmap.h"
6
7#include <algorithm>
8
9#include "base/logging.h"
10
11namespace {
12
13// Returns the number of trailing zeros.
14int FindLSBSetNonZero(uint32 word) {
15  // Get the LSB, put it on the exponent of a 32 bit float and remove the
16  // mantisa and the bias. This code requires IEEE 32 bit float compliance.
17  float f = static_cast<float>(word & -static_cast<int>(word));
18
19  // We use a union to go around strict-aliasing complains.
20  union {
21    float ieee_float;
22    uint32 as_uint;
23  } x;
24
25  x.ieee_float = f;
26  return (x.as_uint >> 23) - 0x7f;
27}
28
29// Returns the index of the first bit set to |value| from |word|. This code
30// assumes that we'll be able to find that bit.
31int FindLSBNonEmpty(uint32 word, bool value) {
32  // If we are looking for 0, negate |word| and look for 1.
33  if (!value)
34    word = ~word;
35
36  return FindLSBSetNonZero(word);
37}
38
39}  // namespace
40
41namespace disk_cache {
42
43Bitmap::Bitmap(int num_bits, bool clear_bits)
44    : num_bits_(num_bits),
45      array_size_(RequiredArraySize(num_bits)),
46      alloc_(true) {
47  map_ = new uint32[array_size_];
48
49  // Initialize all of the bits.
50  if (clear_bits)
51    Clear();
52}
53
54Bitmap::Bitmap(uint32* map, int num_bits, int num_words)
55    : map_(map),
56      num_bits_(num_bits),
57      // If size is larger than necessary, trim because array_size_ is used
58      // as a bound by various methods.
59      array_size_(std::min(RequiredArraySize(num_bits), num_words)),
60      alloc_(false) {
61}
62
63Bitmap::~Bitmap() {
64  if (alloc_)
65    delete [] map_;
66}
67
68void Bitmap::Resize(int num_bits, bool clear_bits) {
69  DCHECK(alloc_ || !map_);
70  const int old_maxsize = num_bits_;
71  const int old_array_size = array_size_;
72  array_size_ = RequiredArraySize(num_bits);
73
74  if (array_size_ != old_array_size) {
75    uint32* new_map = new uint32[array_size_];
76    // Always clear the unused bits in the last word.
77    new_map[array_size_ - 1] = 0;
78    memcpy(new_map, map_,
79           sizeof(*map_) * std::min(array_size_, old_array_size));
80    if (alloc_)
81      delete[] map_;  // No need to check for NULL.
82    map_ = new_map;
83    alloc_ = true;
84  }
85
86  num_bits_ = num_bits;
87  if (old_maxsize < num_bits_ && clear_bits) {
88    SetRange(old_maxsize, num_bits_, false);
89  }
90}
91
92void Bitmap::Set(int index, bool value) {
93  DCHECK_LT(index, num_bits_);
94  DCHECK_GE(index, 0);
95  const int i = index & (kIntBits - 1);
96  const int j = index / kIntBits;
97  if (value)
98    map_[j] |= (1 << i);
99  else
100    map_[j] &= ~(1 << i);
101}
102
103bool Bitmap::Get(int index) const {
104  DCHECK_LT(index, num_bits_);
105  DCHECK_GE(index, 0);
106  const int i = index & (kIntBits-1);
107  const int j = index / kIntBits;
108  return ((map_[j] & (1 << i)) != 0);
109}
110
111void Bitmap::Toggle(int index) {
112  DCHECK_LT(index, num_bits_);
113  DCHECK_GE(index, 0);
114  const int i = index & (kIntBits - 1);
115  const int j = index / kIntBits;
116  map_[j] ^= (1 << i);
117}
118
119void Bitmap::SetMapElement(int array_index, uint32 value) {
120  DCHECK_LT(array_index, array_size_);
121  DCHECK_GE(array_index, 0);
122  map_[array_index] = value;
123}
124
125uint32 Bitmap::GetMapElement(int array_index) const {
126  DCHECK_LT(array_index, array_size_);
127  DCHECK_GE(array_index, 0);
128  return map_[array_index];
129}
130
131void Bitmap::SetMap(const uint32* map, int size) {
132  memcpy(map_, map, std::min(size, array_size_) * sizeof(*map_));
133}
134
135void Bitmap::SetRange(int begin, int end, bool value) {
136  DCHECK_LE(begin, end);
137  int start_offset = begin & (kIntBits - 1);
138  if (start_offset) {
139    // Set the bits in the first word.
140    int len = std::min(end - begin, kIntBits - start_offset);
141    SetWordBits(begin, len, value);
142    begin += len;
143  }
144
145  if (begin == end)
146    return;
147
148  // Now set the bits in the last word.
149  int end_offset = end & (kIntBits - 1);
150  end -= end_offset;
151  SetWordBits(end, end_offset, value);
152
153  // Set all the words in the middle.
154  memset(map_ + (begin / kIntBits), (value ? 0xFF : 0x00),
155         ((end / kIntBits) - (begin / kIntBits)) * sizeof(*map_));
156}
157
158// Return true if any bit between begin inclusive and end exclusive
159// is set.  0 <= begin <= end <= bits() is required.
160bool Bitmap::TestRange(int begin, int end, bool value) const {
161  DCHECK_LT(begin, num_bits_);
162  DCHECK_LE(end, num_bits_);
163  DCHECK_LE(begin, end);
164  DCHECK_GE(begin, 0);
165  DCHECK_GE(end, 0);
166
167  // Return false immediately if the range is empty.
168  if (begin >= end || end <= 0)
169    return false;
170
171  // Calculate the indices of the words containing the first and last bits,
172  // along with the positions of the bits within those words.
173  int word = begin / kIntBits;
174  int offset = begin & (kIntBits - 1);
175  int last_word = (end - 1) / kIntBits;
176  int last_offset = (end - 1) & (kIntBits - 1);
177
178  // If we are looking for zeros, negate the data from the map.
179  uint32 this_word = map_[word];
180  if (!value)
181    this_word = ~this_word;
182
183  // If the range spans multiple words, discard the extraneous bits of the
184  // first word by shifting to the right, and then test the remaining bits.
185  if (word < last_word) {
186    if (this_word >> offset)
187      return true;
188    offset = 0;
189
190    word++;
191    // Test each of the "middle" words that lies completely within the range.
192    while (word < last_word) {
193      this_word = map_[word++];
194      if (!value)
195        this_word = ~this_word;
196      if (this_word)
197        return true;
198    }
199  }
200
201  // Test the portion of the last word that lies within the range. (This logic
202  // also handles the case where the entire range lies within a single word.)
203  const uint32 mask = ((2 << (last_offset - offset)) - 1) << offset;
204
205  this_word = map_[last_word];
206  if (!value)
207    this_word = ~this_word;
208
209  return (this_word & mask) != 0;
210}
211
212bool Bitmap::FindNextBit(int* index, int limit, bool value) const {
213  DCHECK_LT(*index, num_bits_);
214  DCHECK_LE(limit, num_bits_);
215  DCHECK_LE(*index, limit);
216  DCHECK_GE(*index, 0);
217  DCHECK_GE(limit, 0);
218
219  const int bit_index = *index;
220  if (bit_index >= limit || limit <= 0)
221    return false;
222
223  // From now on limit != 0, since if it was we would have returned false.
224  int word_index = bit_index >> kLogIntBits;
225  uint32 one_word = map_[word_index];
226
227  // Simple optimization where we can immediately return true if the first
228  // bit is set.  This helps for cases where many bits are set, and doesn't
229  // hurt too much if not.
230  if (Get(bit_index) == value)
231    return true;
232
233  const int first_bit_offset = bit_index & (kIntBits - 1);
234
235  // First word is special - we need to mask off leading bits.
236  uint32 mask = 0xFFFFFFFF << first_bit_offset;
237  if (value) {
238    one_word &= mask;
239  } else {
240    one_word |= ~mask;
241  }
242
243  uint32 empty_value = value ? 0 : 0xFFFFFFFF;
244
245  // Loop through all but the last word.  Note that 'limit' is one
246  // past the last bit we want to check, and we don't want to read
247  // past the end of "words".  E.g. if num_bits_ == 32 only words[0] is
248  // valid, so we want to avoid reading words[1] when limit == 32.
249  const int last_word_index = (limit - 1) >> kLogIntBits;
250  while (word_index < last_word_index) {
251    if (one_word != empty_value) {
252      *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value);
253      return true;
254    }
255    one_word = map_[++word_index];
256  }
257
258  // Last word is special - we may need to mask off trailing bits.  Note that
259  // 'limit' is one past the last bit we want to check, and if limit is a
260  // multiple of 32 we want to check all bits in this word.
261  const int last_bit_offset = (limit - 1) & (kIntBits - 1);
262  mask = 0xFFFFFFFE << last_bit_offset;
263  if (value) {
264    one_word &= ~mask;
265  } else {
266    one_word |= mask;
267  }
268  if (one_word != empty_value) {
269    *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value);
270    return true;
271  }
272  return false;
273}
274
275int Bitmap::FindBits(int* index, int limit, bool value) const {
276  DCHECK_LT(*index, num_bits_);
277  DCHECK_LE(limit, num_bits_);
278  DCHECK_LE(*index, limit);
279  DCHECK_GE(*index, 0);
280  DCHECK_GE(limit, 0);
281
282  if (!FindNextBit(index, limit, value))
283    return false;
284
285  // Now see how many bits have the same value.
286  int end = *index;
287  if (!FindNextBit(&end, limit, !value))
288    return limit - *index;
289
290  return end - *index;
291}
292
293void Bitmap::SetWordBits(int start, int len, bool value) {
294  DCHECK_LT(len, kIntBits);
295  DCHECK_GE(len, 0);
296  if (!len)
297    return;
298
299  int word = start / kIntBits;
300  int offset = start % kIntBits;
301
302  uint32 to_add = 0xffffffff << len;
303  to_add = (~to_add) << offset;
304  if (value) {
305    map_[word] |= to_add;
306  } else {
307    map_[word] &= ~to_add;
308  }
309}
310
311}  // namespace disk_cache
312