Step 1 - Get the length of the instruction

The first step is the easiest one. We want to know how long is our instruction and, in order to do that we have to know how many operations are inside it. But not only how many operations but also how many format bits and extension bytes. All this information is provided by the format bits themselves.

In the second part of the series we saw there is a table that gives us information about all the possible combinations format bits may have:

By reading this table, we get exactly the amount of bits required for each operation and the extension bytes. We already know that the format bits are located at the beginning of the instruction thus we have to get them and process them.

As I already mentioned, the execution flow in the TriMedia ASM is indicated by a dtree and the bytes representing the dtree are used also as the only uncompressed instruction (branch):

Format bytes: 0x02AA -> binary form: 0000 0010 1010 1010
Issue slot no: 0

Every time you start disassembling a TriMedia stream, you have to remember the dtree bytes because you must start by processing them. They are implicitly taken as the first group of format bits for the first instruction. Then, the format bits at the beginning of the first instruction are used as format bits for the next instruction. Let's try to explain it better with a picture:

At this point, we already have 16 bits due to the first format field, but not all the bits are used, just 10 bits. Let's keep that in mind for the final calculation.

The astute reader will surely have noticed that, as the dtree always starts with 0x02AA, then the first instruction is always 224 bits long. Why? because the format bits are {01, 01, 01, 01, 01}, let's show them again:

Format bytes: 0x02AA -> binary form: 00 00 00 10 10 10 10 10 (read it from right to left, we are working with little endianess, we have to swap the bytes)
                                              ^^ ^^ ^^ ^^ ^^

If we pay attention to the previous table, we can infer that the combination of 0 (lsb) and 1 (msb) means:

Issue slot i is used and an operation for it is available in the instruction.
The operation size is 42 bits.
The size of the extension is 2 bytes.

At the moment, we know that the instruction contains 5 operations with 42 bits each.

One remark: the specs says that if the instruction contains more than three operations, we have to add 8 bits for the format field of the second group of operations (2 operations). By doing some calculation, we infer that the 224 bits are formed by the first 16 bits, 5 operations with 40 bits each (the 2 bits left in each operation, which are the formats bits, are included in the first 16 bits) and the final 8 bits for the second format field as a consequence of the additional 2 operations.

To get a clearer idea of what I'm talking about, look at the following code extracted from the disassembler:

uint16_t instructionlength(uint16_t formatbits) {
        uint32_t i;
        uint16_t len = 0, instrcount = 0;

        len = 16;           // add the two bytes for the 1st format field
        for(i=0;i<5;i++)
        switch(formatbits >> (2 * i) & 3) {
                case 0  :   len += 24;  // 26-bit operation
                                        instrcount++;
                                        break;
                case 1  :   len += 32;  // 34-bit
                                        instrcount++;
                                        break;
                case 2  :   len += 40;  // 42-bit operation
                                        instrcount++;
                                        break;
                case 3  :   break;      // 0-bit operation (NOP)
                default   : fprintf(stderr, "encoding error  (* -1 bits *)\n");
                                        return -1;
                }
        if(instrcount >3)
                len += 8;       // add eight bits for the format field of the 2nd group
        return len;
}

Please, note that until now, we didn't bother to talk about the bytes in the binary and we don't actually need the instruction length to strictly disassemble the instruction. However, we need it to calculate the amount of bytes we have to get from the binary.

Step 2 - Get the operation size

Getting the size of each operation is really simple. If you put attention to the previous step, you'd have noted that we have fixed sizes for operations (26, 34 and 42 bit operations). This information is provided, again, by the format bits, so the only thing we need to do is to read the bit fields corresponding to the current operation. Simple as that.

From Step 1, we know that all the operations inside the instruction are 42 bits long thus we'll have 2 extension bytes. We need to get the offset of those extension bytes and the bytes representing the operation itself with the parameters. This is what we are going to see in the next step.

7C 47 81 43 60 21 60 A0 85 50 80 30 03 C1 08 00 40 E0 60 45 60 11 40 0F 80 00 57 01

format bytes 0x7C47 -> swap_bytes(0x7C47) -> 0x477C -> binary form -> ‭‭01 00 01 11 01 11 11 00‬
                                                                               ^^ ^^ ^^ ^^ ^^

Step 3 - Unpack the operation

So far we have the following information:

1. the instruction length;
2. the size of each operation inside the instruction.

To continue disassembling the instruction, we need to know the offset of each operation inside the bit stream and, when relevant, the offset of the extension bytes.

For a better explanation, I'll use part of the code of tm32disassembler to show you how both offsets are calculated.

uint16_t operationoffset(uint16_t formatbits, uint8_t slotnumber) {
        uint16_t i, offset = 0, oplen = 0, opcount = 0;

        if (operationsize(formatbits, slotnumber) == 0) // a NOP in slotnumber, so operation size for that is zero
                return 0;

        for(i=0;i<slotnumber;i++) {
                oplen = operationsize(formatbits, i);
                if(oplen>0) {
                        opcount++;
                        offset+=24;
                }
        }
        if(opcount > 2)
                offset+=8;          // add the formatbits byte for the 2nd operations group, if used

        return offset;
}

7C 47 81 43 60 21 60 A0 85 50 80 30 03 C1 08 00 40 E0 60 45 60 11 40 0F 80 00 57 01

7c 47       - 81 43 60 21 60
^^ ^^         ^^ ^^ ^^ ^^ ^^
(fb n ins)  -   (op bytes)

219 uint16_t extensionoffset(uint16_t formatbits, uint8_t slotnumber) {
220    uint32_t i;
221    uint16_t extbegin = 0, extoffset = 0,oplen = 0, opcount = 0;
222
223    if(operationsize(formatbits,slotnumber) <= 24)      // operation has no extension
224        return 0;
225
226    for(i=0;i<MAXSLOT;i++) { // count the number of non-NOP operations in the instruction.
227        oplen = operationsize(formatbits, i); // (count * 24) + format bytes is a pointer to the extension bytes
228        if(oplen>0)
229            opcount++;
230    }
231    extbegin+=(opcount*24);
232
233    if(opcount >3) //
234        extbegin+=8; // add format byte to ext. offset for 2nd operations group, if used
235
236    extoffset = extbegin;
237
238    for(i=0;i<slotnumber;i++) {
239        oplen = operationsize(formatbits, i);
240        if(oplen>0)
241            extoffset+= oplen - 24;
242    }
243    return extoffset;
244 }

7C 47 81 43 60 21 60 A0 85 50 80 30 03 C1 08 00 40 E0 60 45 60 11 40 0F 80 00 57 01
^^                                                    ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^
offset no. 0                                          extension bytes starting at offset 18

Step 4 - Decode operation

The work of the decode operation is to get the byte array returned by the unpack operation and parse the bit fields which hold the operation code, operands, parameters, predicates, etc. I won't show each single case for each single operation type because it makes no sense to go through all of them but I'll use the first operation to show you some of the basic cases you can find. This will give you a basic idea of the whole process and if you are interested in the other cases, you'll just need to look at the code of the disassembler or the datasheet/US Patent mentioned in the posts.

Please, remember the following considerations about a TriMedia operation:

• the length of each instruction varies depending on the size of each operation;
• operations:
  • size can be 26, 34 or 42 bits;
  • can be guarded or unguarded;
  • can be zeroary, unary or binary (0, 1 or 2 operands);
  • can be resultless;
  • may contain immediate parameters (7 or 32 bits);
  • are all compressed except for the branch op.

Each item mentioned above is configured by a bit or set of bits that are located at specific offsets of the operation bytes. Basically, we'll need to do a lot of shifting and bit masking in order to get the specific bit field. As I said before, we are going to see just an example but if you want more details about the position of each bit on each type of operation, please, take a look at the following documents [1] [2].

One thing I didn't mention about the unpack operation part is that the format bits and the extension bytes for the current operation (in case of a 34 or 42 bits operation) are packed in the same byte array. The author of the tm32disassembler uses a 64 bit unsigned integer (opint64) to pack all the operation data and simplify the bitwise operations. This is more of an implementation detail and doesn't modify the explanation, but I mention it because I spent some time figuring out the details between the specs and the specific implementation in the tm32disassembler.

Before continuing with our practical example, I would like to show you some snippets of code from the tm32disassembler in order for you to have an idea on how the decoding is done. As I said, there are many cases to consider so we will have a lot of switch..case sentences with if..else in between. Just to give you an idea, the code should look like this:

uint64_t decode(unpacked_bytestream, operation_size)
{

        switch (operation_size)
        {
                case 24:
                        switch(decode_bits(unpacked_bytestream))
                        {
                                case 1: break;
                                case n: break;
                                default: break;
                        }
                        break;
                case 32:
                        switch(decode_bits(unpacked_bytestream))
                        {
                                case 1: break;
                                case n: break;
                                default: break;
                        }
                        break;
                case 40:
                        switch(decode_bits(unpacked_bytestream))
                        {
                                case 1: break;
                                case n: break;
                                default: break;
                        }
                        break;
                default: break;

        }
}

For example, the iadd operation takes two parameters, it sums them, produces a result and stores it in another parameter. What can we say about the iadd operation then?

• it's a binary operation;
• it has a result;
• operands can be signed or unsigned;
• it can be guarded.

But we have a variation for this operation, the iaddi operation. The iaddi operation is similar to the iadd but it only takes one operand and an immediate value with 7 bits. All this means that if we want to decode an operation we need to take a look at the instruction set in order to know what type of properties it has.

Regarding what I said previously about shifting bits to get the operation properties, the following are the C macros that the tm32disassembler uses:

#define OPBITS6_0(x)    (uint32_t)(x & 0x7f)            //   src1[6:0]   | param[13:7]
#define OPBITS13_7(x)   (uint32_t)((x >> 7) & 0x7f)     //   src2[6:0]   | param[6:0]   | dst[6:0]
#define OPBITS20_14(x)  (uint32_t)((x >> 14) & 0x7f)    //   dst[6:0]    | param[6:0]   | guard[6:0] | dst[6:0]
#define OPBITS23_21(x)  (uint32_t)((x >> 21) & 7)       //   opcode[2:0] | param[16:14]
#define OPBITS25_24(x)  (uint32_t)((x >> 24) & 3)       //   opcode[4:3] | param[18:17]
#define OPBITS25_21(x)  (uint32_t)((x >> 21) & 0x1f)    //   opcode[4:0]
#define OPBITS28_26(x)  (uint32_t)((x >> 26) & 7)       //   opcode[7:5]
#define OPBITS28_21(x)  (uint32_t)((x >> 21) & 0xff)    //   opcode[7:0]
#define OPBITS30_21(x)  (uint32_t)((x >> 21) & 0x3ff)   //   param[23:14]
#define OPBITS30_26(x)  (uint32_t)((x >> 26) & 0x1f)    //   param[23:19]
#define OPBITS32_26(x)  (uint32_t)((x >> 26) & 0x7f)    //   dst[6:0]    | param[6:0]
#define OPBITS33_26(x)  (uint32_t)((x >> 26) & 0x1f)    //   param[23:19]
#define OPBITS41_34(x)  (uint32_t)((x >> 34) & 0xff)    //   param[31:24]
#define OPBITS41_35(x)  (uint32_t)((x >> 35) & 0x7f)    //   param[6:0]  | dst[6:0]
#define OPBITS41_26(x)  (uint32_t)((x >> 26) & 0xffff)  //   both extension bytes

#define OPBITS33(x)     (uint32_t)((x >> 33) & 1)       //   used to encode type for 42-bit operations
#define OPBITS32(x)     (uint32_t)((x >> 32) & 1)       //
#define OPBITS31(x)     (uint32_t)((x >> 31) & 1)       //
#define OPBITS32_31(x)  (uint32_t)((x >> 31) & 3)       //
#define OPBITS29(x)     (uint32_t)((x >> 29) & 1)       //   sign flag for 7-bit parameteric operations

#define PARAM32BITS(x)  (uint32_t)(((x>>7) & 0x7f) | ((x<<7) & 0x7f<<7) | ((x>>7) & 0x3ff<<14) | ((x>>10) & 0xff<<24))

As you can read, there is a small comment about the meaning of each bit but, in some cases, depending on the size of the operation, the same bit has a different interpretation. For example, in a 34 bit operation, bit 33 gives the operation code (opcode) but in a 42 bits operation, bit 33 corresponds to some special cases and you have to look at bits 21 to 28 to get the real opcode (look from the line 152 onwards in the tm32decode.c file). Pretty homogeneous, uh? ;p

In our case, our first instruction is composed of 5 operations with 40 bits each. When dealing with 32 and 40 bit operations, there are two types of opcodes: with 4 bits (short opcodes) or 7 bits (long opcodes). In the case of 40 bits operations, there is one more thing to handle, uncompressed jumps.

For 24 bits operations, the opcode is given by bits 21 to 25.

For 32 bits operations, bit 33 is used as a flag to determine if there is a short or long opcode. If false, then opcode is short, otherwise it's a long opcode. In the case of a short opcode, you have to look at bits 21 to 25. In the case of a long opcode, you have to look at bits 21 to 28.

In the case of a 40 bits operation, you start by looking at bit 33 of the operation stream. If this bit is set, it means you have an operation identified as zeroary_param32, which is, basically, an operation with 0 operands, e.g. iimm/uimm (load signed/unsigned 32 bit immediate). If the bit is not set, you have an operation identified as zeroary_param32_resultless, this is an operation with 0 operands and no result, for example, a jmpi. In the particular case of a jmpi/ijmpi operation, bit 32 must be false too. If bit 31 is true, then it's a jmpi otherwise is a ijmpi.

When bit 33 or bit 32 are false in a 40 bits operation, then we have a long opcode operation. If this is the case, the operation code is located at bits 21 to 28.

Now that we know all these things, let's try to decode our unpacked instruction bytes.

From the previous section, we know what our operations bytes are and what their extension bytes are.

The number representing these bytes is packed as an uint64_t integer. In the case of our first operation, the number is 1191876510593 (11581604381h). If you pay attention to this number (in hex), you will note that the last six digits, from right to left, represent the operation bytes. The remaining bytes contain format bits and extension bytes but are packed in a different way. In order to make it fit in the 64 bit integer and to ease the decoding operation, tm32disassembler performs some operations over those bytes as swap, shift left and logical or. If you want more details about these operations, let us look at lines between #78 and #125 of the tm32unpack.c file from the tm32disassembler project.

In order to continue, please, take a look at our number in binary:

0000 0000 0000 0000 0000 0001 0001 0101 1000 0001 0110 0000 0100 0011 1000 0001

We know that the size of our first operation is 40 so we have to look at bit 33 to see if it's a zeroary_param32 or a zeroary_param32_resultless. In this case, bit 33 is 0 thus we are in the zeroary_param32_resultless way. Then, as bit 32 is 1, we know that our operation is not a jmpi/ijmpi but a long opcode operation so we have to look at bits 21 to 28. In order to do so, just shift left 21 positions and get the 8 bits from there with a logical and with 0xFF. This is the output from a Python interpreter:

>>> 1191876510593>>21
568331L
>>> hex(1191876510593>>21)
'0x8ac0bL'
>>> 0x8ac0b & 0xff
11

In binary:

0000 1011

Now we know the operation code (opcode) for our first operation: 11. This opcode corresponds to the asli operation, an arithmetic shift left immediate which takes a single argument in rsrc1 and an immediate modifier n and produces a result in rdest equal to rsrc1 arithmetically shifted left by n bits. This operation is defined as UNARY_PARAM7_SHORT (because of the immediate value with 7 bits), it can be guarded, it has one argument (rsrc1) and one immediate value (n) and a result that's stored in another register (rdest). It means we have to get all those operation parameters in order to fully disassemble it. All these parameters vary depending on the type of operation. It's not the same to have an operation defined as UNARY_PARAM7_SHORT or as UNARY_PARAM7_UNGUARDED (this is true only when speaking about 40 bits operations).

In the case of a UNARY_PARAM7_SHORT operation, the guard is taken from bits 14 to 20, the immediate value is taken from bits 7 to 13, the only argument is taken from bits 0 to 6 and, finally, bits 35 to 41 indicate the rdest register (result). The process to get all these parameters is simple: just left shift the bits to the corresponding offset and perform a logical and with the necessary bitmask in order to get the amount of bits that are needed:

• guarded register (bits 14 to 20): 000001 (1);
• rsrc1 register (bits 0 to 6): 000001 (1);
• immediate value (bits 7 to 13): 0000111 (7);
• rdest register (bits 35 to 41): 0100010 (34).

In the case of the parameters indicating registers (rsrc1, rdest and the guarded register), the resulting number indicates the number of registers involved in the operation. In the case of an immediate value, the resulting number indicates the number itself.

Please, note that r1 is used as a guarded register. This is a special register which always contains the value 1 (by definition in the datasheet), so it makes no sense to guard the instruction because the condition will always be TRUE, so it is always executed. However, tm32disassmebler explicitly shows these cases, probably to indicate that the operation is guarded.

In our case, the first operation can be constructed like this asli(7) r1 -> r34 or, if you prefer to be more compliant with the explicit form, if r1 asli(7) r1 -> r34.

Now that we know the required steps to disassemble an operation, we can repeat all the steps mentioned before in order to continue disassembling the rest of the operations in the instruction.

If you want more details about the decoding process, please, take a look at the tm32decode.c file from the tm32disassembler project.