1 : /*
2 : * Copyright (c) 2012 The Native Client Authors. All rights reserved.
3 : * Use of this source code is governed by a BSD-style license that can be
4 : * found in the LICENSE file.
5 : */
6 :
7 : #include "native_client/src/trusted/validator_mips/address_set.h"
8 : #include <assert.h>
9 : #include <stdio.h>
10 : #include <string.h>
11 :
12 : namespace nacl_mips_val {
13 :
14 : #if !defined(NDEBUG)
15 : static const int kInstrAlignment = 4;
16 : #endif
17 : static const int kInstrSize = 4;
18 : static const int kWordSize = 32;
19 : static const int kInstrPerWord = 4 * kWordSize;
20 :
21 : #define UP_ALLIGN(x) (kInstrSize * ((x + kInstrSize - 1) / kInstrSize))
22 :
23 91 : AddressSet::AddressSet(uint32_t base, uint32_t size)
24 : : base_(base), size_(size), end_(base + UP_ALLIGN(size) - kInstrSize),
25 91 : bits_(new uint32_t[(end_ - base_) / kInstrPerWord + 1]) {
26 91 : assert(((base % kInstrAlignment) == 0) && (size > 0));
27 91 : memset(bits_, 0, sizeof(uint32_t) * ((end_ - base_) / kInstrPerWord + 1));
28 91 : }
29 :
30 91 : AddressSet::~AddressSet() {
31 91 : delete[] bits_;
32 91 : }
33 :
34 26 : void AddressSet::Add(uint32_t address) {
35 26 : if ((address - base_) < size_) {
36 22 : uint32_t word_address = (address - base_) / sizeof(uint32_t);
37 22 : bits_[word_address / kWordSize] |= 1 << (word_address % kWordSize);
38 : }
39 26 : }
40 :
41 16 : bool AddressSet::Contains(uint32_t address) const {
42 16 : if ((address - base_) < size_) {
43 12 : uint32_t word_address = (address - base_) / sizeof(uint32_t);
44 :
45 12 : return bits_[word_address / kWordSize] & (1 << (word_address % kWordSize));
46 : } else {
47 4 : return false;
48 : }
49 : }
50 :
51 61 : AddressSet::Iterator AddressSet::Begin() const {
52 61 : return Iterator(*this, 0, 0);
53 : }
54 :
55 73 : AddressSet::Iterator AddressSet::End() const {
56 73 : uint32_t end_index = (end_ - base_) / kInstrPerWord;
57 73 : uint32_t end_shift = ((end_ - base_) / kInstrSize) % kWordSize;
58 73 : return Iterator(*this, end_index, end_shift);
59 : }
60 :
61 134 : AddressSet::Iterator::Iterator(const AddressSet &parent,
62 : uint32_t index,
63 : uint32_t shift)
64 134 : : parent_(parent), index_(index), shift_(shift) {
65 134 : Advance();
66 134 : }
67 :
68 12 : AddressSet::Iterator &AddressSet::Iterator::Next() {
69 12 : shift_++; // Skip the current bit, if any, and
70 12 : Advance(); // seek to the next 1 bit.
71 12 : return *this;
72 : }
73 :
74 73 : bool AddressSet::Iterator::Equals(const AddressSet::Iterator &other) const {
75 73 : return index_ == other.index_ && shift_ == other.shift_;
76 : }
77 :
78 12 : uint32_t AddressSet::Iterator::GetAddress() const {
79 12 : return parent_.base_ + kInstrSize * ((index_ * kWordSize) + shift_);
80 : }
81 :
82 146 : void AddressSet::Iterator::Advance() {
83 146 : uint32_t max_index = (parent_.size_ / kInstrPerWord) + 1;
84 :
85 291 : for (; index_ < max_index; index_++) {
86 185 : uint32_t word = (shift_ > 31) ? 0 : parent_.bits_[index_] >> shift_;
87 479 : while (word) {
88 295 : if (word & 1) return;
89 :
90 : // A meager optimization for sparse words. Check if the first 16 slots are
91 : // empty, and if they are, skip them. Repeat the same check for 8 slots.
92 : // Otherwise, we will check bit by bit, to reach the next valid one.
93 109 : if (!(word & 0xFFFF)) {
94 3 : word >>= 16;
95 3 : shift_ += 16;
96 106 : } else if (!(word & 0xFF)) {
97 1 : word >>= 8;
98 1 : shift_ += 8;
99 : } else {
100 105 : word >>= 1;
101 105 : shift_++;
102 : }
103 : }
104 145 : shift_ = 0;
105 : }
106 :
107 : // If we have moved too far, we should limit the address to
108 : // the last valid address.
109 106 : if (index_ == max_index) {
110 106 : index_ = (parent_.end_ - parent_.base_) / kInstrPerWord;
111 106 : shift_ = ((parent_.end_ - parent_.base_) / kInstrSize) % kWordSize;
112 : }
113 : }
114 :
115 : } // namespace nacl_mips_val
|
