libdexfile/dex/type_lookup_table.cc - platform/art - Git at Google

 /*
  * Copyright (C) 2015 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "type_lookup_table.h"

 #include <cstring>
 #include <memory>

 #include "base/bit_utils.h"
 #include "base/leb128.h"
 #include "dex/dex_file-inl.h"
 #include "dex/utf-inl.h"

 namespace art {

 static inline bool ModifiedUtf8StringEquals(const char* lhs, const char* rhs) {
   return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(lhs, rhs) == 0;
 }

 TypeLookupTable TypeLookupTable::Create(const DexFile& dex_file) {
   uint32_t num_class_defs = dex_file.NumClassDefs();
   if (UNLIKELY(!SupportedSize(num_class_defs))) {
     return TypeLookupTable();
   }
   size_t mask_bits = CalculateMaskBits(num_class_defs);
   size_t size = 1u << mask_bits;
   std::unique_ptr<Entry[]> owned_entries(new Entry[size]);
   Entry* entries = owned_entries.get();

   static_assert(alignof(Entry) == 4u, "Expecting Entry to be 4-byte aligned.");
   const uint32_t mask = Entry::GetMask(mask_bits);
   std::vector<uint16_t> conflict_class_defs;
   // The first stage. Put elements on their initial positions. If an initial position is already
   // occupied then delay the insertion of the element to the second stage to reduce probing
   // distance.
   for (size_t class_def_idx = 0; class_def_idx < dex_file.NumClassDefs(); ++class_def_idx) {
     const dex::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
     const dex::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
     const dex::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
     const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
     const uint32_t pos = hash & mask;
     if (entries[pos].IsEmpty()) {
       entries[pos] = Entry(str_id.string_data_off_, hash, class_def_idx, mask_bits);
       DCHECK(entries[pos].IsLast(mask_bits));
     } else {
       conflict_class_defs.push_back(class_def_idx);
     }
   }
   // The second stage. The initial position of these elements had a collision. Put these elements
   // into the nearest free cells and link them together by updating next_pos_delta.
   for (uint16_t class_def_idx : conflict_class_defs) {
     const dex::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
     const dex::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
     const dex::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
     const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
     // Find the last entry in the chain.
     uint32_t tail_pos = hash & mask;
     DCHECK(!entries[tail_pos].IsEmpty());
     while (!entries[tail_pos].IsLast(mask_bits)) {
       tail_pos = (tail_pos + entries[tail_pos].GetNextPosDelta(mask_bits)) & mask;
       DCHECK(!entries[tail_pos].IsEmpty());
     }
     // Find an empty entry for insertion.
     uint32_t insert_pos = tail_pos;
     do {
       insert_pos = (insert_pos + 1) & mask;
     } while (!entries[insert_pos].IsEmpty());
     // Insert and chain the new entry.
     entries[insert_pos] = Entry(str_id.string_data_off_, hash, class_def_idx, mask_bits);
     entries[tail_pos].SetNextPosDelta((insert_pos - tail_pos) & mask, mask_bits);
     DCHECK(entries[insert_pos].IsLast(mask_bits));
     DCHECK(!entries[tail_pos].IsLast(mask_bits));
   }

   return TypeLookupTable(dex_file.DataBegin(), mask_bits, entries, std::move(owned_entries));
 }

 TypeLookupTable TypeLookupTable::Open(const uint8_t* dex_data_pointer,
                                       const uint8_t* raw_data,
                                       uint32_t num_class_defs) {
   DCHECK_ALIGNED(raw_data, alignof(Entry));
   const Entry* entries = reinterpret_cast<const Entry*>(raw_data);
   size_t mask_bits = CalculateMaskBits(num_class_defs);
   return TypeLookupTable(dex_data_pointer, mask_bits, entries, /* owned_entries= */ nullptr);
 }

 uint32_t TypeLookupTable::Lookup(const char* str, uint32_t hash) const {
   uint32_t mask = Entry::GetMask(mask_bits_);
   uint32_t pos = hash & mask;
   // Thanks to special insertion algorithm, the element at position pos can be empty
   // or start of the right bucket, or anywhere in the wrong bucket's chain.
   const Entry* entry = &entries_[pos];
   if (entry->IsEmpty()) {
     return dex::kDexNoIndex;
   }
   // Look for the partial hash match first, even if traversing the wrong bucket's chain.
   uint32_t compared_hash_bits = (hash << mask_bits_) >> (2 * mask_bits_);
   while (compared_hash_bits != entry->GetHashBits(mask_bits_)) {
     if (entry->IsLast(mask_bits_)) {
       return dex::kDexNoIndex;
     }
     pos = (pos + entry->GetNextPosDelta(mask_bits_)) & mask;
     entry = &entries_[pos];
     DCHECK(!entry->IsEmpty());
   }
   // Found partial hash match, compare strings (expecting this to succeed).
   const char* first_checked_str = GetStringData(*entry);
   if (ModifiedUtf8StringEquals(str, first_checked_str)) {
     return entry->GetClassDefIdx(mask_bits_);
   }
   // If we're at the end of the chain, return before doing further expensive work.
   if (entry->IsLast(mask_bits_)) {
     return dex::kDexNoIndex;
   }
   // Check if we're traversing the right bucket. This is important if the compared
   // partial hash has only a few bits (i.e. it can match frequently).
   if (((ComputeModifiedUtf8Hash(first_checked_str) ^ hash) & mask) != 0u) {
     return dex::kDexNoIndex;  // Low hash bits mismatch.
   }
   // Continue looking for the string in the rest of the chain.
   do {
     pos = (pos + entry->GetNextPosDelta(mask_bits_)) & mask;
     entry = &entries_[pos];
     DCHECK(!entry->IsEmpty());
     if (compared_hash_bits == entry->GetHashBits(mask_bits_) &&
         ModifiedUtf8StringEquals(str, GetStringData(*entry))) {
       return entry->GetClassDefIdx(mask_bits_);
     }
   } while (!entry->IsLast(mask_bits_));
   // Not found.
   return dex::kDexNoIndex;
 }

 uint32_t TypeLookupTable::RawDataLength(uint32_t num_class_defs) {
   return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) * sizeof(Entry) : 0u;
 }

 uint32_t TypeLookupTable::CalculateMaskBits(uint32_t num_class_defs) {
   return SupportedSize(num_class_defs) ? MinimumBitsToStore(num_class_defs - 1u) : 0u;
 }

 bool TypeLookupTable::SupportedSize(uint32_t num_class_defs) {
   return num_class_defs != 0u && num_class_defs <= std::numeric_limits<uint16_t>::max();
 }

 TypeLookupTable::TypeLookupTable(const uint8_t* dex_data_pointer,
                                  uint32_t mask_bits,
                                  const Entry* entries,
                                  std::unique_ptr<Entry[]> owned_entries)
     : dex_data_begin_(dex_data_pointer),
       mask_bits_(mask_bits),
       entries_(entries),
       owned_entries_(std::move(owned_entries)) {}

 const char* TypeLookupTable::GetStringData(const Entry& entry) const {
   DCHECK(dex_data_begin_ != nullptr);
   const uint8_t* ptr = dex_data_begin_ + entry.GetStringOffset();
   // Skip string length.
   DecodeUnsignedLeb128(&ptr);
   return reinterpret_cast<const char*>(ptr);
 }

 }  // namespace art
	/*
	* Copyright (C) 2015 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "type_lookup_table.h"

	#include <cstring>
	#include <memory>

	#include "base/bit_utils.h"
	#include "base/leb128.h"
	#include "dex/dex_file-inl.h"
	#include "dex/utf-inl.h"

	namespace art {

	static inline bool ModifiedUtf8StringEquals(const char* lhs, const char* rhs) {
	return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(lhs, rhs) == 0;
	}

	TypeLookupTable TypeLookupTable::Create(const DexFile& dex_file) {
	uint32_t num_class_defs = dex_file.NumClassDefs();
	if (UNLIKELY(!SupportedSize(num_class_defs))) {
	return TypeLookupTable();
	}
	size_t mask_bits = CalculateMaskBits(num_class_defs);
	size_t size = 1u << mask_bits;
	std::unique_ptr<Entry[]> owned_entries(new Entry[size]);
	Entry* entries = owned_entries.get();

	static_assert(alignof(Entry) == 4u, "Expecting Entry to be 4-byte aligned.");
	const uint32_t mask = Entry::GetMask(mask_bits);
	std::vector<uint16_t> conflict_class_defs;
	// The first stage. Put elements on their initial positions. If an initial position is already
	// occupied then delay the insertion of the element to the second stage to reduce probing
	// distance.
	for (size_t class_def_idx = 0; class_def_idx < dex_file.NumClassDefs(); ++class_def_idx) {
	const dex::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
	const dex::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
	const dex::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
	const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
	const uint32_t pos = hash & mask;
	if (entries[pos].IsEmpty()) {
	entries[pos] = Entry(str_id.string_data_off_, hash, class_def_idx, mask_bits);
	DCHECK(entries[pos].IsLast(mask_bits));
	} else {
	conflict_class_defs.push_back(class_def_idx);
	}
	}
	// The second stage. The initial position of these elements had a collision. Put these elements
	// into the nearest free cells and link them together by updating next_pos_delta.
	for (uint16_t class_def_idx : conflict_class_defs) {
	const dex::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
	const dex::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
	const dex::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
	const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
	// Find the last entry in the chain.
	uint32_t tail_pos = hash & mask;
	DCHECK(!entries[tail_pos].IsEmpty());
	while (!entries[tail_pos].IsLast(mask_bits)) {
	tail_pos = (tail_pos + entries[tail_pos].GetNextPosDelta(mask_bits)) & mask;
	DCHECK(!entries[tail_pos].IsEmpty());
	}
	// Find an empty entry for insertion.
	uint32_t insert_pos = tail_pos;
	do {
	insert_pos = (insert_pos + 1) & mask;
	} while (!entries[insert_pos].IsEmpty());
	// Insert and chain the new entry.
	entries[insert_pos] = Entry(str_id.string_data_off_, hash, class_def_idx, mask_bits);
	entries[tail_pos].SetNextPosDelta((insert_pos - tail_pos) & mask, mask_bits);
	DCHECK(entries[insert_pos].IsLast(mask_bits));
	DCHECK(!entries[tail_pos].IsLast(mask_bits));
	}

	return TypeLookupTable(dex_file.DataBegin(), mask_bits, entries, std::move(owned_entries));
	}

	TypeLookupTable TypeLookupTable::Open(const uint8_t* dex_data_pointer,
	const uint8_t* raw_data,
	uint32_t num_class_defs) {
	DCHECK_ALIGNED(raw_data, alignof(Entry));
	const Entry* entries = reinterpret_cast<const Entry*>(raw_data);
	size_t mask_bits = CalculateMaskBits(num_class_defs);
	return TypeLookupTable(dex_data_pointer, mask_bits, entries, /* owned_entries= */ nullptr);
	}

	uint32_t TypeLookupTable::Lookup(const char* str, uint32_t hash) const {
	uint32_t mask = Entry::GetMask(mask_bits_);
	uint32_t pos = hash & mask;
	// Thanks to special insertion algorithm, the element at position pos can be empty
	// or start of the right bucket, or anywhere in the wrong bucket's chain.
	const Entry* entry = &entries_[pos];
	if (entry->IsEmpty()) {
	return dex::kDexNoIndex;
	}
	// Look for the partial hash match first, even if traversing the wrong bucket's chain.
	uint32_t compared_hash_bits = (hash << mask_bits_) >> (2 * mask_bits_);
	while (compared_hash_bits != entry->GetHashBits(mask_bits_)) {
	if (entry->IsLast(mask_bits_)) {
	return dex::kDexNoIndex;
	}
	pos = (pos + entry->GetNextPosDelta(mask_bits_)) & mask;
	entry = &entries_[pos];
	DCHECK(!entry->IsEmpty());
	}
	// Found partial hash match, compare strings (expecting this to succeed).
	const char* first_checked_str = GetStringData(*entry);
	if (ModifiedUtf8StringEquals(str, first_checked_str)) {
	return entry->GetClassDefIdx(mask_bits_);
	}
	// If we're at the end of the chain, return before doing further expensive work.
	if (entry->IsLast(mask_bits_)) {
	return dex::kDexNoIndex;
	}
	// Check if we're traversing the right bucket. This is important if the compared
	// partial hash has only a few bits (i.e. it can match frequently).
	if (((ComputeModifiedUtf8Hash(first_checked_str) ^ hash) & mask) != 0u) {
	return dex::kDexNoIndex; // Low hash bits mismatch.
	}
	// Continue looking for the string in the rest of the chain.
	do {
	pos = (pos + entry->GetNextPosDelta(mask_bits_)) & mask;
	entry = &entries_[pos];
	DCHECK(!entry->IsEmpty());
	if (compared_hash_bits == entry->GetHashBits(mask_bits_) &&
	ModifiedUtf8StringEquals(str, GetStringData(*entry))) {
	return entry->GetClassDefIdx(mask_bits_);
	}
	} while (!entry->IsLast(mask_bits_));
	// Not found.
	return dex::kDexNoIndex;
	}

	uint32_t TypeLookupTable::RawDataLength(uint32_t num_class_defs) {
	return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) * sizeof(Entry) : 0u;
	}

	uint32_t TypeLookupTable::CalculateMaskBits(uint32_t num_class_defs) {
	return SupportedSize(num_class_defs) ? MinimumBitsToStore(num_class_defs - 1u) : 0u;
	}

	bool TypeLookupTable::SupportedSize(uint32_t num_class_defs) {
	return num_class_defs != 0u && num_class_defs <= std::numeric_limits<uint16_t>::max();
	}

	TypeLookupTable::TypeLookupTable(const uint8_t* dex_data_pointer,
	uint32_t mask_bits,
	const Entry* entries,
	std::unique_ptr<Entry[]> owned_entries)
	: dex_data_begin_(dex_data_pointer),
	mask_bits_(mask_bits),
	entries_(entries),
	owned_entries_(std::move(owned_entries)) {}

	const char* TypeLookupTable::GetStringData(const Entry& entry) const {
	DCHECK(dex_data_begin_ != nullptr);
	const uint8_t* ptr = dex_data_begin_ + entry.GetStringOffset();
	// Skip string length.
	DecodeUnsignedLeb128(&ptr);
	return reinterpret_cast<const char*>(ptr);
	}

	} // namespace art