| // Copyright (c) 2018 Google LLC |
| // |
| // 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 "source/comp/markv_encoder.h" |
| |
| #include "source/binary.h" |
| #include "source/opcode.h" |
| #include "spirv-tools/libspirv.hpp" |
| |
| namespace spvtools { |
| namespace comp { |
| namespace { |
| |
| const size_t kCommentNumWhitespaces = 2; |
| |
| } // namespace |
| |
| spv_result_t MarkvEncoder::EncodeNonIdWord(uint32_t word) { |
| auto* codec = model_->GetNonIdWordHuffmanCodec(inst_.opcode, operand_index_); |
| |
| if (codec) { |
| uint64_t bits = 0; |
| size_t num_bits = 0; |
| if (codec->Encode(word, &bits, &num_bits)) { |
| // Encoding successful. |
| writer_.WriteBits(bits, num_bits); |
| return SPV_SUCCESS; |
| } else { |
| // Encoding failed, write kMarkvNoneOfTheAbove flag. |
| if (!codec->Encode(MarkvModel::GetMarkvNoneOfTheAbove(), &bits, |
| &num_bits)) |
| return Diag(SPV_ERROR_INTERNAL) |
| << "Non-id word Huffman table for " |
| << spvOpcodeString(SpvOp(inst_.opcode)) << " operand index " |
| << operand_index_ << " is missing kMarkvNoneOfTheAbove"; |
| writer_.WriteBits(bits, num_bits); |
| } |
| } |
| |
| // Fallback encoding. |
| const size_t chunk_length = |
| model_->GetOperandVariableWidthChunkLength(operand_.type); |
| if (chunk_length) { |
| writer_.WriteVariableWidthU32(word, chunk_length); |
| } else { |
| writer_.WriteUnencoded(word); |
| } |
| return SPV_SUCCESS; |
| } |
| |
| spv_result_t MarkvEncoder::EncodeOpcodeAndNumOperands(uint32_t opcode, |
| uint32_t num_operands) { |
| uint64_t bits = 0; |
| size_t num_bits = 0; |
| |
| const uint32_t word = opcode | (num_operands << 16); |
| |
| // First try to use the Markov chain codec. |
| auto* codec = |
| model_->GetOpcodeAndNumOperandsMarkovHuffmanCodec(GetPrevOpcode()); |
| if (codec) { |
| if (codec->Encode(word, &bits, &num_bits)) { |
| // The word was successfully encoded into bits/num_bits. |
| writer_.WriteBits(bits, num_bits); |
| return SPV_SUCCESS; |
| } else { |
| // The word is not in the Huffman table. Write kMarkvNoneOfTheAbove |
| // and use fallback encoding. |
| if (!codec->Encode(MarkvModel::GetMarkvNoneOfTheAbove(), &bits, |
| &num_bits)) |
| return Diag(SPV_ERROR_INTERNAL) |
| << "opcode_and_num_operands Huffman table for " |
| << spvOpcodeString(GetPrevOpcode()) |
| << "is missing kMarkvNoneOfTheAbove"; |
| writer_.WriteBits(bits, num_bits); |
| } |
| } |
| |
| // Fallback to base-rate codec. |
| codec = model_->GetOpcodeAndNumOperandsMarkovHuffmanCodec(SpvOpNop); |
| assert(codec); |
| if (codec->Encode(word, &bits, &num_bits)) { |
| // The word was successfully encoded into bits/num_bits. |
| writer_.WriteBits(bits, num_bits); |
| return SPV_SUCCESS; |
| } else { |
| // The word is not in the Huffman table. Write kMarkvNoneOfTheAbove |
| // and return false. |
| if (!codec->Encode(MarkvModel::GetMarkvNoneOfTheAbove(), &bits, &num_bits)) |
| return Diag(SPV_ERROR_INTERNAL) |
| << "Global opcode_and_num_operands Huffman table is missing " |
| << "kMarkvNoneOfTheAbove"; |
| writer_.WriteBits(bits, num_bits); |
| return SPV_UNSUPPORTED; |
| } |
| } |
| |
| spv_result_t MarkvEncoder::EncodeMtfRankHuffman(uint32_t rank, uint64_t mtf, |
| uint64_t fallback_method) { |
| const auto* codec = GetMtfHuffmanCodec(mtf); |
| if (!codec) { |
| assert(fallback_method != kMtfNone); |
| codec = GetMtfHuffmanCodec(fallback_method); |
| } |
| |
| if (!codec) return Diag(SPV_ERROR_INTERNAL) << "No codec to encode MTF rank"; |
| |
| uint64_t bits = 0; |
| size_t num_bits = 0; |
| if (rank < MarkvCodec::kMtfSmallestRankEncodedByValue) { |
| // Encode using Huffman coding. |
| if (!codec->Encode(rank, &bits, &num_bits)) |
| return Diag(SPV_ERROR_INTERNAL) |
| << "Failed to encode MTF rank with Huffman"; |
| |
| writer_.WriteBits(bits, num_bits); |
| } else { |
| // Encode by value. |
| if (!codec->Encode(MarkvCodec::kMtfRankEncodedByValueSignal, &bits, |
| &num_bits)) |
| return Diag(SPV_ERROR_INTERNAL) |
| << "Failed to encode kMtfRankEncodedByValueSignal"; |
| |
| writer_.WriteBits(bits, num_bits); |
| writer_.WriteVariableWidthU32( |
| rank - MarkvCodec::kMtfSmallestRankEncodedByValue, |
| model_->mtf_rank_chunk_length()); |
| } |
| return SPV_SUCCESS; |
| } |
| |
| spv_result_t MarkvEncoder::EncodeIdWithDescriptor(uint32_t id) { |
| // Get the descriptor for id. |
| const uint32_t long_descriptor = long_id_descriptors_.GetDescriptor(id); |
| auto* codec = |
| model_->GetIdDescriptorHuffmanCodec(inst_.opcode, operand_index_); |
| uint64_t bits = 0; |
| size_t num_bits = 0; |
| uint64_t mtf = kMtfNone; |
| if (long_descriptor && codec && |
| codec->Encode(long_descriptor, &bits, &num_bits)) { |
| // If the descriptor exists and is in the table, write the descriptor and |
| // proceed to encoding the rank. |
| writer_.WriteBits(bits, num_bits); |
| mtf = GetMtfLongIdDescriptor(long_descriptor); |
| } else { |
| if (codec) { |
| // The descriptor doesn't exist or we have no coding for it. Write |
| // kMarkvNoneOfTheAbove and go to fallback method. |
| if (!codec->Encode(MarkvModel::GetMarkvNoneOfTheAbove(), &bits, |
| &num_bits)) |
| return Diag(SPV_ERROR_INTERNAL) |
| << "Descriptor Huffman table for " |
| << spvOpcodeString(SpvOp(inst_.opcode)) << " operand index " |
| << operand_index_ << " is missing kMarkvNoneOfTheAbove"; |
| |
| writer_.WriteBits(bits, num_bits); |
| } |
| |
| if (model_->id_fallback_strategy() != |
| MarkvModel::IdFallbackStrategy::kShortDescriptor) { |
| return SPV_UNSUPPORTED; |
| } |
| |
| const uint32_t short_descriptor = short_id_descriptors_.GetDescriptor(id); |
| writer_.WriteBits(short_descriptor, MarkvCodec::kShortDescriptorNumBits); |
| |
| if (short_descriptor == 0) { |
| // Forward declared id. |
| return SPV_UNSUPPORTED; |
| } |
| |
| mtf = GetMtfShortIdDescriptor(short_descriptor); |
| } |
| |
| // Descriptor has been encoded. Now encode the rank of the id in the |
| // associated mtf sequence. |
| return EncodeExistingId(mtf, id); |
| } |
| |
| spv_result_t MarkvEncoder::EncodeExistingId(uint64_t mtf, uint32_t id) { |
| assert(multi_mtf_.GetSize(mtf) > 0); |
| if (multi_mtf_.GetSize(mtf) == 1) { |
| // If the sequence has only one element no need to write rank, the decoder |
| // would make the same decision. |
| return SPV_SUCCESS; |
| } |
| |
| uint32_t rank = 0; |
| if (!multi_mtf_.RankFromValue(mtf, id, &rank)) |
| return Diag(SPV_ERROR_INTERNAL) << "Id is not in the MTF sequence"; |
| |
| return EncodeMtfRankHuffman(rank, mtf, kMtfGenericNonZeroRank); |
| } |
| |
| spv_result_t MarkvEncoder::EncodeRefId(uint32_t id) { |
| { |
| // Try to encode using id descriptor mtfs. |
| const spv_result_t result = EncodeIdWithDescriptor(id); |
| if (result != SPV_UNSUPPORTED) return result; |
| // If can't be done continue with other methods. |
| } |
| |
| const bool can_forward_declare = spvOperandCanBeForwardDeclaredFunction( |
| SpvOp(inst_.opcode))(operand_index_); |
| uint32_t rank = 0; |
| |
| if (model_->id_fallback_strategy() == |
| MarkvModel::IdFallbackStrategy::kRuleBased) { |
| // Encode using rule-based mtf. |
| uint64_t mtf = GetRuleBasedMtf(); |
| |
| if (mtf != kMtfNone && !can_forward_declare) { |
| assert(multi_mtf_.HasValue(kMtfAll, id)); |
| return EncodeExistingId(mtf, id); |
| } |
| |
| if (mtf == kMtfNone) mtf = kMtfAll; |
| |
| if (!multi_mtf_.RankFromValue(mtf, id, &rank)) { |
| // This is the first occurrence of a forward declared id. |
| multi_mtf_.Insert(kMtfAll, id); |
| multi_mtf_.Insert(kMtfForwardDeclared, id); |
| if (mtf != kMtfAll) multi_mtf_.Insert(mtf, id); |
| rank = 0; |
| } |
| |
| return EncodeMtfRankHuffman(rank, mtf, kMtfAll); |
| } else { |
| assert(can_forward_declare); |
| |
| if (!multi_mtf_.RankFromValue(kMtfForwardDeclared, id, &rank)) { |
| // This is the first occurrence of a forward declared id. |
| multi_mtf_.Insert(kMtfForwardDeclared, id); |
| rank = 0; |
| } |
| |
| writer_.WriteVariableWidthU32(rank, model_->mtf_rank_chunk_length()); |
| return SPV_SUCCESS; |
| } |
| } |
| |
| spv_result_t MarkvEncoder::EncodeTypeId() { |
| if (inst_.opcode == SpvOpFunctionParameter) { |
| assert(!remaining_function_parameter_types_.empty()); |
| assert(inst_.type_id == remaining_function_parameter_types_.front()); |
| remaining_function_parameter_types_.pop_front(); |
| return SPV_SUCCESS; |
| } |
| |
| { |
| // Try to encode using id descriptor mtfs. |
| const spv_result_t result = EncodeIdWithDescriptor(inst_.type_id); |
| if (result != SPV_UNSUPPORTED) return result; |
| // If can't be done continue with other methods. |
| } |
| |
| assert(model_->id_fallback_strategy() == |
| MarkvModel::IdFallbackStrategy::kRuleBased); |
| |
| uint64_t mtf = GetRuleBasedMtf(); |
| assert(!spvOperandCanBeForwardDeclaredFunction(SpvOp(inst_.opcode))( |
| operand_index_)); |
| |
| if (mtf == kMtfNone) { |
| mtf = kMtfTypeNonFunction; |
| // Function types should have been handled by GetRuleBasedMtf. |
| assert(inst_.opcode != SpvOpFunction); |
| } |
| |
| return EncodeExistingId(mtf, inst_.type_id); |
| } |
| |
| spv_result_t MarkvEncoder::EncodeResultId() { |
| uint32_t rank = 0; |
| |
| const uint64_t num_still_forward_declared = |
| multi_mtf_.GetSize(kMtfForwardDeclared); |
| |
| if (num_still_forward_declared) { |
| // We write the rank only if kMtfForwardDeclared is not empty. If it is |
| // empty the decoder knows that there are no forward declared ids to expect. |
| if (multi_mtf_.RankFromValue(kMtfForwardDeclared, inst_.result_id, &rank)) { |
| // This is a definition of a forward declared id. We can remove the id |
| // from kMtfForwardDeclared. |
| if (!multi_mtf_.Remove(kMtfForwardDeclared, inst_.result_id)) |
| return Diag(SPV_ERROR_INTERNAL) |
| << "Failed to remove id from kMtfForwardDeclared"; |
| writer_.WriteBits(1, 1); |
| writer_.WriteVariableWidthU32(rank, model_->mtf_rank_chunk_length()); |
| } else { |
| rank = 0; |
| writer_.WriteBits(0, 1); |
| } |
| } |
| |
| if (model_->id_fallback_strategy() == |
| MarkvModel::IdFallbackStrategy::kRuleBased) { |
| if (!rank) { |
| multi_mtf_.Insert(kMtfAll, inst_.result_id); |
| } |
| } |
| |
| return SPV_SUCCESS; |
| } |
| |
| spv_result_t MarkvEncoder::EncodeLiteralNumber( |
| const spv_parsed_operand_t& operand) { |
| if (operand.number_bit_width <= 32) { |
| const uint32_t word = inst_.words[operand.offset]; |
| return EncodeNonIdWord(word); |
| } else { |
| assert(operand.number_bit_width <= 64); |
| const uint64_t word = uint64_t(inst_.words[operand.offset]) | |
| (uint64_t(inst_.words[operand.offset + 1]) << 32); |
| if (operand.number_kind == SPV_NUMBER_UNSIGNED_INT) { |
| writer_.WriteVariableWidthU64(word, model_->u64_chunk_length()); |
| } else if (operand.number_kind == SPV_NUMBER_SIGNED_INT) { |
| int64_t val = 0; |
| std::memcpy(&val, &word, 8); |
| writer_.WriteVariableWidthS64(val, model_->s64_chunk_length(), |
| model_->s64_block_exponent()); |
| } else if (operand.number_kind == SPV_NUMBER_FLOATING) { |
| writer_.WriteUnencoded(word); |
| } else { |
| return Diag(SPV_ERROR_INTERNAL) << "Unsupported bit length"; |
| } |
| } |
| return SPV_SUCCESS; |
| } |
| |
| void MarkvEncoder::AddByteBreak(size_t byte_break_if_less_than) { |
| const size_t num_bits_to_next_byte = |
| GetNumBitsToNextByte(writer_.GetNumBits()); |
| if (num_bits_to_next_byte == 0 || |
| num_bits_to_next_byte > byte_break_if_less_than) |
| return; |
| |
| if (logger_) { |
| logger_->AppendWhitespaces(kCommentNumWhitespaces); |
| logger_->AppendText("<byte break>"); |
| } |
| |
| writer_.WriteBits(0, num_bits_to_next_byte); |
| } |
| |
| spv_result_t MarkvEncoder::EncodeInstruction( |
| const spv_parsed_instruction_t& inst) { |
| SpvOp opcode = SpvOp(inst.opcode); |
| inst_ = inst; |
| |
| LogDisassemblyInstruction(); |
| |
| const spv_result_t opcode_encodig_result = |
| EncodeOpcodeAndNumOperands(opcode, inst.num_operands); |
| if (opcode_encodig_result < 0) return opcode_encodig_result; |
| |
| if (opcode_encodig_result != SPV_SUCCESS) { |
| // Fallback encoding for opcode and num_operands. |
| writer_.WriteVariableWidthU32(opcode, model_->opcode_chunk_length()); |
| |
| if (!OpcodeHasFixedNumberOfOperands(opcode)) { |
| // If the opcode has a variable number of operands, encode the number of |
| // operands with the instruction. |
| |
| if (logger_) logger_->AppendWhitespaces(kCommentNumWhitespaces); |
| |
| writer_.WriteVariableWidthU16(inst.num_operands, |
| model_->num_operands_chunk_length()); |
| } |
| } |
| |
| // Write operands. |
| const uint32_t num_operands = inst_.num_operands; |
| for (operand_index_ = 0; operand_index_ < num_operands; ++operand_index_) { |
| operand_ = inst_.operands[operand_index_]; |
| |
| if (logger_) { |
| logger_->AppendWhitespaces(kCommentNumWhitespaces); |
| logger_->AppendText("<"); |
| logger_->AppendText(spvOperandTypeStr(operand_.type)); |
| logger_->AppendText(">"); |
| } |
| |
| switch (operand_.type) { |
| case SPV_OPERAND_TYPE_RESULT_ID: |
| case SPV_OPERAND_TYPE_TYPE_ID: |
| case SPV_OPERAND_TYPE_ID: |
| case SPV_OPERAND_TYPE_OPTIONAL_ID: |
| case SPV_OPERAND_TYPE_SCOPE_ID: |
| case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID: { |
| const uint32_t id = inst_.words[operand_.offset]; |
| if (operand_.type == SPV_OPERAND_TYPE_TYPE_ID) { |
| const spv_result_t result = EncodeTypeId(); |
| if (result != SPV_SUCCESS) return result; |
| } else if (operand_.type == SPV_OPERAND_TYPE_RESULT_ID) { |
| const spv_result_t result = EncodeResultId(); |
| if (result != SPV_SUCCESS) return result; |
| } else { |
| const spv_result_t result = EncodeRefId(id); |
| if (result != SPV_SUCCESS) return result; |
| } |
| |
| PromoteIfNeeded(id); |
| break; |
| } |
| |
| case SPV_OPERAND_TYPE_LITERAL_INTEGER: { |
| const spv_result_t result = |
| EncodeNonIdWord(inst_.words[operand_.offset]); |
| if (result != SPV_SUCCESS) return result; |
| break; |
| } |
| |
| case SPV_OPERAND_TYPE_TYPED_LITERAL_NUMBER: { |
| const spv_result_t result = EncodeLiteralNumber(operand_); |
| if (result != SPV_SUCCESS) return result; |
| break; |
| } |
| |
| case SPV_OPERAND_TYPE_LITERAL_STRING: { |
| const char* src = |
| reinterpret_cast<const char*>(&inst_.words[operand_.offset]); |
| |
| auto* codec = model_->GetLiteralStringHuffmanCodec(opcode); |
| if (codec) { |
| uint64_t bits = 0; |
| size_t num_bits = 0; |
| const std::string str = src; |
| if (codec->Encode(str, &bits, &num_bits)) { |
| writer_.WriteBits(bits, num_bits); |
| break; |
| } else { |
| bool result = |
| codec->Encode("kMarkvNoneOfTheAbove", &bits, &num_bits); |
| (void)result; |
| assert(result); |
| writer_.WriteBits(bits, num_bits); |
| } |
| } |
| |
| const size_t length = spv_strnlen_s(src, operand_.num_words * 4); |
| if (length == operand_.num_words * 4) |
| return Diag(SPV_ERROR_INVALID_BINARY) |
| << "Failed to find terminal character of literal string"; |
| for (size_t i = 0; i < length + 1; ++i) writer_.WriteUnencoded(src[i]); |
| break; |
| } |
| |
| default: { |
| for (int i = 0; i < operand_.num_words; ++i) { |
| const uint32_t word = inst_.words[operand_.offset + i]; |
| const spv_result_t result = EncodeNonIdWord(word); |
| if (result != SPV_SUCCESS) return result; |
| } |
| break; |
| } |
| } |
| } |
| |
| AddByteBreak(MarkvCodec::kByteBreakAfterInstIfLessThanUntilNextByte); |
| |
| if (logger_) { |
| logger_->NewLine(); |
| logger_->NewLine(); |
| if (!logger_->DebugInstruction(inst_)) return SPV_REQUESTED_TERMINATION; |
| } |
| |
| ProcessCurInstruction(); |
| |
| return SPV_SUCCESS; |
| } |
| |
| } // namespace comp |
| } // namespace spvtools |
