A Decoding Algorithm and Its Optimization for Mixed-Length Instruction Sets with Non-Uniform Encoding

Abstract

The software decoding algorithm of instruction sets is widely applied in simulators, debuggers and reverse engineering. Current research predominantly focuses on fixed-length instruction sets and variable-length instruction sets, with limited studies addressing non-uniformly encoded mixed-length instruction sets. This paper introduces a two-level reading strategy for machine instructions. With the help of a decoding framework, the instruction boundaries of mixed-length instruction sets are identified and machine instructions in executable files are parsed. Following this, a three-stage decoding algorithm is proposed. In the first stage, preliminary decoding identifies all matching pattern sets of instructions. The second stage determines the optimal matching pattern and corresponding instruction length. The third stage resolves encoding conflicts specific to 32-bit instructions. To further enhance the algorithm, a priority-based optimization method is designed and applied for the above algorithm. The proposed approach is tested on common algorithms and standard library functions of DSP. The experimental results demonstrate that the optimization method effectively improves efficiency.