src/native_client/src/trusted/validator_arm/address_set.cc

   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 be
   4  * found in the LICENSE file.
   5  * Copyright 2009, Google Inc.
   6  */
   7
   8 #include "native_client/src/trusted/validator_arm/address_set.h"
   9 #include <stdio.h>
  10 #include <string.h>
  11
  12 namespace nacl_arm_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