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,
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
* 512 instructions with one 15-bit address and one 3-bit register
* 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
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
* 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
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