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