Shifts/Rotates: (cobweb-ridded) terminology clarification

[sur-behoffski <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