Shifts/Rotates: (cobweb-ridded) terminology clarification

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Shifts/Rotates: (cobweb-ridded) terminology clarification

sur-behoffski
This is a long message, so TL;DR:

      * Be careful to distinguish between LOGICAL shift right and ARITHMETIC
        shift right (assuming a twos-complement architecture).

      * Some of these machine-level operations are not natively available in
        "C89" (ANSI X3.159-1989) at the coder's level, although the compiler,
        the OS, and quite a number of associated libraries are likely to use
        them quite extensively internally.  My understanding is that they can
        be emulated in Lua, although not as cheaply as directly executing
        native machine code.

---------------------------------

Digging back through my assembly experience, I've generally seen several
instructions, perhaps more common in the pre-RISC and pre-SIMD days:

These all come from my early days, assuming a bit layout for bits 15
to bit 0 of a register, with the highest-value bit on the left:

+-------------------------------------------------------------------------------+
| 15 | 14 | 13 | 12 | 11 | 10 |  9 |  8 |  7 |  6 |  5 |  4 |  3 |  2 |  1 |  0 |
+-------------------------------------------------------------------------------+

Bit 0 is 2^0, i.e. 1, bit 1 is 2^1, (2) bit 2 is 2^2 (4), bit 3 is 2^4 (8), etc.
Bit 15 is 2^15, i.e. 32768.  where such a register is either:
       Unsigned:  Bit 15 is added to bits 0..14, to allow values [0..65535]; or
       Signed:    Bit 15 is a sign bit, with value 0 meaning "positive, and
                  value "1" meaning "negative".  This allows values [-32768..32767].

Okay, we have a 16-bit register, with one bit having two different possible
meanings (the differentiation is spread through other instructions, such as
"unsigned multiply" versus "signed multiply").

So, for number of bits "n", we have the main shift/rotate instructions:
[I'll assume n = 3 in the following examples in the interests of brevity.]

1. Shift Left "n" bits.

       - Superficially the same as "multiply by 2^n", except for:
           1. "n=3" high bits, e.g. 15, 14 and 13, are lost; and
           2. Zeroes are shifted in from the left;
           2. Some lower bit becomes bit 15 (e.g. bit 12 for n=3).  If the
            register is a signed value, its sign may change.
           3. If n is greater than 15, then the register becomes all zeroes.

2. LOGICAL Shift Right "n" bits.

      +-------------------------------------------------------------------------------+
0 -> | 15 | 14 | 13 | 12 | 11 | 10 |  9 |  8 |  7 |  6 |  5 |  4 |  3 |  2 |  1 |  0 | -> (lost)
      +-------------------------------------------------------------------------------+

       NOTE the term of the use "logical" to qualify "shift".

       - Mostly similar to the shift left case, except that zeroes are shifted
         in from the right, and lowest "n" bits are lost (shifted out to the
         right).

3. ARITHMETIC Shift Right "n" bits.

      +-------------------------------------------------------------------------------+
/--> | 15 | 14 | 13 | 12 | 11 | 10 |  9 |  8 |  7 |  6 |  5 |  4 |  3 |  2 |  1 |  0 | -> (lost)
|    +-------------------------------------------------------------------------------+
|       |
|       v
\-------/

      - The ARITHMETIC is *almost* the same as the logical shift right... except for
        a crucial change:  Instead of zeroes being shifted into bit 15, each
        shift step (for 1..n steps) sees bit 15 copied into bit 14.  This means
        that positive values will remain positive, and negative values will
        remain negative.  This is roughly equal an integer division by 2^n,
        although I'm not certain of the actual or desirable rounding
        properties (round to zero? to even? to odd?).

4. Rotate Left "n" bits.

        The rotate instructions differ from the the shifts, in that the shifts
        either insert zeroes at the "dominant" end of each step, or, in the case
        of the arithmetic shift right, insert a copy of bit 15 into bit 14 at
        each step.

        Rotates, however, simply take the value that would have been "bumped
        out" by the rotate (bit 15 in the Rotate Left case), and re-insert it
        in the lowest position (bit 0 in the Rotate Left case), and keeps doing
        this procedure n times.

5 Rotate Right "n" bits.

        Similar to Rotate Left, except that bit 0 is bumped out, and is
        re-inserted in bit 15, and this is repeated for n steps.

Here's a schematic representation of "rotate right 1 bit":

+-------------------------------------------------------------------------------+
| 15 | 14 | 13 | 12 | 11 | 10 |  9 |  8 |  7 |  6 |  5 |  4 |  3 |  2 |  1 |  0 | --\
+-------------------------------------------------------------------------------+   |
    ^                                                                                |
    |                                                                                v
    \--------------------------------------------------------------------------------/


------------------------------------------------

Hope that I haven't bored you guys too much.  Three variations on the above notes:


1. I've used a 16-bit register, but the same can be used on other register sizes,
depending on the architecture.  Microcontrollers and smaller CPUs will have
8-bit registers; many machines will have 32-bit registers, and larger machines
will have 64-bit or even 128-bit registers.  The same general principles apply.


2. A slightly more tricky case comes along when you want to string together a
series of individual registers into one "mega-register".  In this case, the CPU
has a "Carry" flag that indicates e.g. for an addition, when the result exceeds
the size of the register (but the carry, posing as the highest bit, together with
the register, gives the correct result).

Since carry-inclusive functions are so common, instructions sets tend to cater to
them specifically with a separate set of commands, e.g. "add with carry", "rotate
right through carry", etc.

Here's a schematic representation of "rotate left through carry, 1 bit":

+-------------------------------------------------------------------------------+     +---+
| 15 | 14 | 13 | 12 | 11 | 10 |  9 |  8 |  7 |  6 |  5 |  4 |  3 |  2 |  1 |  0 | <-- | C | --\
+-------------------------------------------------------------------------------+     +---|   ^
    |                                                                                          |
    v                                                                                          |
    \------------------------------------------------------------------------------------------/



3. Newer DSP, SIMD machines, with more sophisticated integer hardware, offer
"saturation" arithmetic modes, where, if a result would exceed the maximum possible
value for the register size, the register is instead set to its maximum value.



-----------------------

Hope this helps,

sur-behoffski (Brenton Hoff)
Programmer, Grouse Software

Reply | Threaded
Open this post in threaded view
|

Re: Shifts/Rotates: (cobweb-ridded) terminology clarification

Martin
On 05/15/2017 03:31 AM, sur-behoffski wrote:

> This is a long message, so TL;DR:
>
>      * Be careful to distinguish between LOGICAL shift right and ARITHMETIC
>        shift right (assuming a twos-complement architecture).
>
>      * Some of these machine-level operations are not natively available in
>        "C89" (ANSI X3.159-1989) at the coder's level, although the
> compiler,
>        the OS, and quite a number of associated libraries are likely to use
>        them quite extensively internally.  My understanding is that they
> can
>        be emulated in Lua, although not as cheaply as directly executing
>        native machine code.
>

Good post!

I think it'll benefit from mentioning related Intel microprocessor
instructions:

    operation | left | right
   -----------+------+-------
    shift     | SHL  | SHR
    .arithm   | SAL  | SAR
    rotate    | ROL  | ROR
    .via_carry| RCL  | RCR

-- Martin