1 // Copyright (c) 2017 Google Inc. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "id_descriptor.h" 16 17 #include <cassert> 18 #include <iostream> 19 20 #include "opcode.h" 21 #include "operand.h" 22 23 namespace libspirv { 24 25 namespace { 26 27 // Hashes an array of words. Order of words is important. 28 uint32_t HashU32Array(const std::vector<uint32_t>& words) { 29 // The hash function is a sum of hashes of each word seeded by word index. 30 // Knuth's multiplicative hash is used to hash the words. 31 const uint32_t kKnuthMulHash = 2654435761; 32 uint32_t val = 0; 33 for (uint32_t i = 0; i < words.size(); ++i) { 34 val += (words[i] + i + 123) * kKnuthMulHash; 35 } 36 return val; 37 } 38 39 } // namespace 40 41 uint32_t IdDescriptorCollection::ProcessInstruction( 42 const spv_parsed_instruction_t& inst) { 43 if (!inst.result_id) 44 return 0; 45 46 assert(words_.empty()); 47 words_.push_back(inst.words[0]); 48 49 for (size_t operand_index = 0; operand_index < inst.num_operands; 50 ++operand_index) { 51 const auto &operand = inst.operands[operand_index]; 52 if (spvIsIdType(operand.type)) { 53 const uint32_t id = inst.words[operand.offset]; 54 const auto it = id_to_descriptor_.find(id); 55 // Forward declared ids are not hashed. 56 if (it != id_to_descriptor_.end()) { 57 words_.push_back(it->second); 58 } 59 } else { 60 for (size_t operand_word_index = 0; 61 operand_word_index < operand.num_words; ++operand_word_index) { 62 words_.push_back(inst.words[operand.offset + operand_word_index]); 63 } 64 } 65 } 66 67 const uint32_t descriptor = HashU32Array(words_); 68 assert(descriptor); 69 70 words_.clear(); 71 72 const auto result = id_to_descriptor_.emplace(inst.result_id, descriptor); 73 assert(result.second); 74 (void)result; 75 return descriptor; 76 } 77 78 } // namespace libspirv 79