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               0 :     : base_(base), size_(size), bits_(new uint32_t[(size + 3) / 4]) {
      16               0 :   memset(bits_, 0, sizeof(uint32_t) * ((size + 3) / 4));
      17               0 : }
      18                 : 
      19               0 : AddressSet::~AddressSet() {
      20               0 :   delete[] bits_;
      21               0 : }
      22                 : 
      23               0 : void AddressSet::add(uint32_t address) {
      24               0 :   if ((address - base_) < size_) {
      25               0 :     uint32_t word_address = (address - base_) / sizeof(uint32_t);
      26                 : 
      27               0 :     bits_[word_address / 32] |= 1 << (word_address % 32);
      28                 :   }
      29               0 : }
      30                 : 
      31               0 : bool AddressSet::contains(uint32_t address) const {
      32               0 :   if ((address - base_) < size_) {
      33               0 :     uint32_t word_address = (address - base_) / sizeof(uint32_t);
      34                 : 
      35               0 :     return bits_[word_address / 32] & (1 << (word_address % 32));
      36                 :   } else {
      37               0 :     return false;
      38                 :   }
      39               0 : }
      40                 : 
      41               0 : AddressSet::Iterator AddressSet::begin() const {
      42               0 :   return Iterator(*this, 0, 0);
      43               0 : }
      44                 : 
      45               0 : AddressSet::Iterator AddressSet::end() const {
      46               0 :   return Iterator(*this, (size_ + 3) / 4, 0);
      47               0 : }
      48                 : 
      49                 : AddressSet::Iterator::Iterator(const AddressSet &parent,
      50                 :                                uint32_t index,
      51                 :                                uint32_t shift)
      52               0 :     : parent_(parent), index_(index), shift_(shift) {
      53               0 :   advance();
      54               0 : }
      55                 : 
      56               0 : AddressSet::Iterator &AddressSet::Iterator::operator++() {
      57               0 :   shift_++;   // Skip the current bit, if any, and
      58               0 :   advance();  // seek to the next 1 bit.
      59               0 :   return *this;
      60               0 : }
      61                 : 
      62               0 : bool AddressSet::Iterator::operator!=(const AddressSet::Iterator &other) const {
      63               0 :   return index_ != other.index_ || shift_ != other.shift_;
      64               0 : }
      65                 : 
      66               0 : uint32_t AddressSet::Iterator::operator*() const {
      67               0 :   return parent_.base_ + 4 * ((index_ * 32) + shift_);
      68               0 : }
      69                 : 
      70               0 : void AddressSet::Iterator::advance() {
      71               0 :   uint32_t max_index = (parent_.size_ + 3) / 4;
      72                 : 
      73               0 :   for (; index_ < max_index; index_++) {
      74               0 :     uint32_t word = (shift_ > 31)? 0 : parent_.bits_[index_] >> shift_;
      75               0 :     while (word) {
      76               0 :       if (word & 1) return;
      77                 : 
      78                 :       // A meager optimization for sparse words
      79               0 :       if (!(word & 0xFFFF)) {
      80               0 :         word >>= 16;
      81               0 :         shift_ += 16;
      82               0 :       } else if (!(word & 0xFF)) {
      83               0 :         word >>= 8;
      84               0 :         shift_ += 8;
      85               0 :       } else {
      86               0 :         word >>= 1;
      87               0 :         shift_++;
      88                 :       }
      89               0 :     }
      90               0 :     shift_ = 0;
      91                 :   }
      92               0 : }
      93                 : 
      94                 : }  // namespace