Aloha everyone,
   I have a quandry; I'm attempting to understand expanding opcodes, but 
Tannenbaum doesn't adequately explain it, at least for my understanding. 
  When it is presented in the text book, it has 2^k operations and 2^n 
operands.  That much I understand.  What I can't figure out how to do is to

"determine if it is possible to design an expanding opcode for the 
following to be encoded in a x-bit instruction:
xxx instructions with yyy registers
xxxx instructions with yy registers
xx instructions with yyyy registers
a register is xxx bits"
(using whatever numbers you wish for the x's and y's)

Can anyone help me out with this?  I asked my instructor, but he kind of 
just glossed over it and I never got an adequate explanation.

Thanks in advance for any assistance,

William Jones

William Jones wrote:
> Aloha everyone,
>   I have a quandry; I'm attempting to understand expanding opcodes, but 
> Tannenbaum doesn't adequately explain it, at least for my understanding. 
>  When it is presented in the text book, it has 2^k operations and 2^n 
> operands.  That much I understand.  What I can't figure out how to do is to
> 
> "determine if it is possible to design an expanding opcode for the 
> following to be encoded in a x-bit instruction:
> xxx instructions with yyy registers
> xxxx instructions with yy registers
> xx instructions with yyyy registers
> a register is xxx bits"
> (using whatever numbers you wish for the x's and y's)
> 
> Can anyone help me out with this?  I asked my instructor, but he kind of 
> just glossed over it and I never got an adequate explanation.
> 
> Thanks in advance for any assistance,
> 
> William Jones


A specific example might illustrate.

The Z80 has a load instruction that can transfer data from any of 8 
sources to any of 8 destinations.  The sources and destinations can each 
be 8-bit registers a,b,c,d,e,h,l or the byte held at the address in 
16-bit register hl (it can't do ld (hl),(hl) though; that would be 0x76 
which is HALT).  The load instruction is 01 sss ddd, and sss and ddd 
represent b,c,d,e,h,l,(hl),a as 0-7.  So for instance ld a,(hl) is 0x7e 
which is 01 111 110, and the general form is 01 ddd sss (d=destination, 
s=source).

In effect this is a two bit opcode.

It can also load a single byte from the program into a register, for 
which the opcode is 00 rrr 110, and the complete instruction is two bytes.

In effect this is a five bit opcode.

You can also add to the 16 bit register hl the contents of other 16 bit 
registers bc, de, hl, sp.  The opcode for that is 00 rr 1001.

In effect this is a six bit opcode.

I don't remember using the term "expanding opcodes" when I did a lot of 
Z80 programming, so it could be terminology used either academically or 
in some other processor.


A quick google revealed the following:

Design an expanding opcode (i.e., give the opcodes) to allow all the 
following to be encoded in a 36 bit instruction:

     * 7 instructions with two 15-bit addresses and one 3-bit register 
number
     * 512 instructions with one 15-bit address and one 3-bit register 
number
     * 64 instructions with no address or registers

Taking the first, we could represent the first, using i for the 7 
instructions, a,b for the addresses and r for the registers:
iiia aaaa aaaa aaaa aabb bbbb bbbb bbbb brrr

At least one of the 8 values for iii cannot be used in this form 
otherwise no other operations are possible.  This is the case, so the 
rest of the operands can be encoded iff they can be fully expressed in 
33 bits.


The same page asks: Is it possible to design an expanding opcode to 
allow the following to be encoded in a 12-bit instruction? A register is 
3 bits.

     * 4 instructions with 3 registers
     * 255 instructions with one register
     * 16 instructions with zero registers

Using i for instruction and p/q/r for registers we can see the answer to 
this is no.

Four instructions with three registers requires two bits for the opcodes 
and nine for the registers, this leaves one bit spare:

0iip ppqq qrrr

All combinations of ii are used, so we cannot use 0xxxxxxxxxxx for any 
other instruction.

We can represent 255 instructions on 1 register as follows:

1iii iiii ippp

If all combinations of iiiiiiii are used, then no further instructions 
are possible.  However, one combination is free as there are only 255 
instructions of this form, so let's say 0000 0000 is unused; this leaves 
the following form for the remaining 16 instructions:

1000 0000 0iii

16 instructions cannot be encoded in only 3 bits.

However, this assumes there are 8 registers.  If there are only 7 
possibilities for just one of p,q,r, then we can fit in the extra 
instructions; if for example we decide not to allow r=111, then we have 
the following available for another 256 instructions:

0xxx xxxx x111


Dave.