123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487 |
- // 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
|