Re: combinations of 4

[Valdis.Kletnieks () vt edu]

On Sat, 06 Apr 2002 17:01:59 PST, KF <dotslash () snosoft com>  said:
> I am in the process of archiving power pc instructions that do not 
> contain null... I have come to the decision that if I could generate a 
> list of all possible unique 4 char combinations for a given list of 
> alpha numeric chars then I could quickly sort the rest out in gdb...

Many people have posted various nested-for-loop solutions, without
actually *thinking* here.  Note the following:

1) "do not contain null" - that's *different* than "A..Z".  There's
a *lot* of instructions that contain non-printable non-null characters.
Most of them, in fact.  For a 32-bit instruction, there are 2^32 (or
4,294,967,296, of which 4,228,250,625 (or 255^4) do *not* contain nulls.
Only 66,716,671 (or about 1.5%) of all possible 32-bit instructions *DO*
contain a null.

2) However, for the *vast* majority of the other 4 billion options, the
instruction will have no null bits, but not do anything useful/desirable.
For instance, the chances that a "branch" or "call" opcode will go anyplace
useful are almost zero unless it happens to specify a valid target (on most
RISC-based systems, this involves loading the target address into a register
beforehand).

3) Turn it around, and work as follows:

A) On the Power architectures, all instructions are 32 bits long.

B) The first 8 bits can never be all zero (since bits 0-5 are the
primary opcode, and are never all zero for a valid opcode).

C) The *next* 24 bits are instruction-format dependent - for example,
for a D-format, bits 6-10 are RT/RS/FRT/TO/BF/FRS, and 11-15 are RA,
and 16-31 are D/SI/UI.  So for the second byte, you just have to make
sure that *one* of those 2 5-bit register specifications is non-zero,
and for the last 2 bytes, you have to make sure that the D, SI, or UI
field (as appropriate for that instruction) is non-zero.

D) A similar analysis applies to the B, I, X, XL and other format
instructions as well - in fact, for *all* instruction formats I see
listed with the exception of SC, bits 8-15 are *NOT* opcode bits, but
are *operand* specifiers (registers, condition code fields, and so
on).  For the SC format, bits 6-15 are reserved (and should probably
be zero) - this shouldn't pose a problem for actual code.

E) For X and XL format, you  can use the 'extended opcode' field to
trim out non-zero values for the 3rd and 4th byte.  Fortunately,
you can often be clever here.  For instance, 'compare' is an X-format
instruction with opcode 31 and XO of 0.  However, in actual practice,
this can be worked around, by not using R0 as the RA field (if the value
you care about is in R0, specify it as the RB field and reverse the
sense of the compare), which will make the 3rd byte non-zero - and
the 4th byte you can set the Rc bit (make sure you're not using the
CR0 for something else if so. ;)

In general, trying to write PPC code that doesn't contain nulls
will be more a matter of being careful in choice of *operands* rather
than *opcodes*.

-- 
                                Valdis Kletnieks
                                Computer Systems Senior Engineer
                                Virginia Tech

Attachment: _bin
Description: