Index: src/trusted/validator_mips/address_set.h |
diff --git a/src/trusted/validator_mips/address_set.h b/src/trusted/validator_mips/address_set.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..d36c7c8e5597bd8899d6a8dec199bc70974283f5 |
--- /dev/null |
+++ b/src/trusted/validator_mips/address_set.h |
@@ -0,0 +1,81 @@ |
+/* |
+ * Copyright 2012 The Native Client Authors. All rights reserved. |
+ * Use of this source code is governed by a BSD-style license that can |
+ * be found in the LICENSE file. |
+ * Copyright 2012, Google Inc. |
+ */ |
+ |
+#ifndef NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_MIPS_ADDRESS_SET_H |
+#define NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_MIPS_ADDRESS_SET_H |
+ |
+#include <stdint.h> |
+ |
+namespace nacl_mips_val { |
+ |
+/* |
+ * A set of word addresses, implemented as a dense bitset. |
+ * |
+ * An AddressSet has a base address and a size, in bytes, of the space to |
+ * describe. Describing N bytes costs N/32 bytes here, since we only record |
+ * word addresses (4-byte alignment) and pack 8 per byte. |
+ * |
+ * Thus, an AddressSet covering the entire 256MB code region costs 8MB, plus |
+ * a small constant overhead (~16 bytes). |
+ */ |
+class AddressSet { |
+ public: |
+ /* |
+ * Creates an AddressSet describing 'size' bytes starting at 'base'. |
+ */ |
+ AddressSet(uint32_t base, uint32_t size); |
+ ~AddressSet(); |
+ |
+ /* |
+ * Adds an address to the set. |
+ * - If the address is already in the set, nothing changes. |
+ * - If the address is outside of this set's range (delimited by base and size |
+ * provided at construction), nothing changes. |
+ * - If the address is not 4-byte aligned, the address of the 4-byte word |
+ * containing the address is added instead. |
+ */ |
+ void Add(uint32_t address); |
+ |
+ /* |
+ * Checks whether the AddressSet contains an address. If the address is not |
+ * 4-byte aligned, the address of the 4-byte word containing the address is |
+ * checked instead. |
+ */ |
+ bool Contains(uint32_t address) const; |
+ |
+ class Iterator { |
+ public: |
+ Iterator(const AddressSet &, uint32_t index, uint32_t shift); |
+ Iterator& Next(); |
+ bool Equals(const Iterator &) const; |
+ uint32_t GetAddress() const; |
+ |
+ private: |
+ void Advance(); |
+ |
+ const AddressSet &parent_; |
+ uint32_t index_; |
+ uint32_t shift_; |
+ }; |
+ |
+ Iterator Begin() const; |
+ Iterator End() const; |
+ |
+ private: |
+ const uint32_t base_; |
+ const uint32_t size_; |
+ const uint32_t end_; |
+ uint32_t * const bits_; |
+ |
+ // Disallow copies - we don't need them, and don't want to refcount bits_. |
+ AddressSet(const AddressSet &); |
+ AddressSet &operator=(const AddressSet &); |
+}; |
+ |
+} // namespace |
+ |
+#endif // NATIVE_CLIENT_SRC_TRUSTED_VALIDATOR_MIPS_ADDRESS_SET_H |