OLD | NEW |
(Empty) | |
| 1 /* |
| 2 * Copyright 2009 The Native Client Authors. All rights reserved. |
| 3 * Use of this source code is governed by a BSD-style license that can |
| 4 * be found in the LICENSE file. |
| 5 * Copyright 2009, Google Inc. |
| 6 */ |
| 7 |
| 8 #include "native_client/src/trusted/validator_mips/address_set.h" |
| 9 #include <stdio.h> |
| 10 #include <string.h> |
| 11 |
| 12 namespace nacl_mips_val { |
| 13 |
| 14 AddressSet::AddressSet(uint32_t base, uint32_t size) |
| 15 : base_(base), size_(size), bits_(new uint32_t[(size + 3) / 4]) { |
| 16 memset(bits_, 0, sizeof(uint32_t) * ((size + 3) / 4)); |
| 17 } |
| 18 |
| 19 AddressSet::~AddressSet() { |
| 20 delete[] bits_; |
| 21 } |
| 22 |
| 23 void AddressSet::add(uint32_t address) { |
| 24 if ((address - base_) < size_) { |
| 25 uint32_t word_address = (address - base_) / sizeof(uint32_t); |
| 26 |
| 27 bits_[word_address / 32] |= 1 << (word_address % 32); |
| 28 } |
| 29 } |
| 30 |
| 31 bool AddressSet::contains(uint32_t address) const { |
| 32 if ((address - base_) < size_) { |
| 33 uint32_t word_address = (address - base_) / sizeof(uint32_t); |
| 34 |
| 35 return bits_[word_address / 32] & (1 << (word_address % 32)); |
| 36 } else { |
| 37 return false; |
| 38 } |
| 39 } |
| 40 |
| 41 AddressSet::Iterator AddressSet::begin() const { |
| 42 return Iterator(*this, 0, 0); |
| 43 } |
| 44 |
| 45 AddressSet::Iterator AddressSet::end() const { |
| 46 return Iterator(*this, (size_ + 3) / 4, 0); |
| 47 } |
| 48 |
| 49 AddressSet::Iterator::Iterator(const AddressSet &parent, |
| 50 uint32_t index, |
| 51 uint32_t shift) |
| 52 : parent_(parent), index_(index), shift_(shift) { |
| 53 advance(); |
| 54 } |
| 55 |
| 56 AddressSet::Iterator &AddressSet::Iterator::operator++() { |
| 57 shift_++; // Skip the current bit, if any, and |
| 58 advance(); // seek to the next 1 bit. |
| 59 return *this; |
| 60 } |
| 61 |
| 62 bool AddressSet::Iterator::operator!=(const AddressSet::Iterator &other) const { |
| 63 return index_ != other.index_ || shift_ != other.shift_; |
| 64 } |
| 65 |
| 66 uint32_t AddressSet::Iterator::operator*() const { |
| 67 return parent_.base_ + 4 * ((index_ * 32) + shift_); |
| 68 } |
| 69 |
| 70 void AddressSet::Iterator::advance() { |
| 71 uint32_t max_index = (parent_.size_ + 3) / 4; |
| 72 |
| 73 for (; index_ < max_index; index_++) { |
| 74 uint32_t word = (shift_ > 31)? 0 : parent_.bits_[index_] >> shift_; |
| 75 while (word) { |
| 76 if (word & 1) return; |
| 77 |
| 78 // A meager optimization for sparse words |
| 79 if (!(word & 0xFFFF)) { |
| 80 word >>= 16; |
| 81 shift_ += 16; |
| 82 } else if (!(word & 0xFF)) { |
| 83 word >>= 8; |
| 84 shift_ += 8; |
| 85 } else { |
| 86 word >>= 1; |
| 87 shift_++; |
| 88 } |
| 89 } |
| 90 shift_ = 0; |
| 91 } |
| 92 } |
| 93 |
| 94 } // namespace |
OLD | NEW |