We have designed an efficient algorithm as given in figure 11. This algorithm is based on an observation that instruction set of a processor uses some fixed number of bits for opcode in any instruction. By looking at these bits, all the instructions can be divided uniquely into different categories. All instructions will have same bit values for the opcode in each category. In each category, again some fixed number of bits differentiate among the instructions. We call these bits as subcode. Most of the processors use this two-level of hierarchy in assignment of the opcode to the instruction.
Figure 11 : Algorithm for Calculating More Mask Values
In the algorithm, a binary string named general-mask is calculated to identify the instruction category. We call these category as different buckets. The general-mask will have 1 at bit positions used for opcodes. For example, we will get the general-mask value as 0xFC 0x00 0x00 0x00 for PowerPC603 processor[19] that has 32 bit long instruction with first 6 bits as an opcode. The instructions are grouped in buckets. Each bucket is assigned a bucket-value which is the binary string resultant from the bit-wise anding of the binary string image of the instruction and the general-mask. Each bucket is assigned a bucket-mask to identify a instruction among the instructions stored in each bucket. The bucket-mask has bit value 1 at all those positions which are used for the opcode and the subcode. All buckets and the instructions within each bucket are sorted with respect to the bucket-value and the binary string image respectively to reduce the searching time.
Now the instruction matching algorithm is described as follows.
