Shift!

Shift! That's one overrated actor if I've ever heard of one. His movie was the first to crossover, he still has an acting career (but only in bad movies like From Dusk To Dawn), and he got all the women. His soundtrack even got an Academy Award -- what, is Oscar too good for Curtis Mayes? No, wait, that's Shaft! Shift is one of my favorite ALU units. Never mind -- just keep reading.
The shifter handles 7 different types of 8-bit shifts and rotates. Specifically, these are:
  1. Shift left; move in "0" (SL0)
  2. Shift left; move in "1" (SL1)
  3. Rotate left (RL)
  4. Shift right; move in "0" (SR0)
  5. Shift right; move in "1" (SR1)
  6. Arithmetic shift right (ASR)
  7. Rotate right (RR)
The shifter takes two external inputs: an 8-bit datum to be shifted, and a 3-bit shift count (ranges from 0-7). Although a larger shift count could theoretically be supported, there is no clear reason for doing so; all larger shifts would entail a total loss of data, whereas all larger rotates could be expressed modulo 8 and still give the same answer.

The shift unit conists of three parts:

  1. the barrel-shifter core
  2. glue logic to set the inputs of the barrel shifter
  3. glue logic to select the appropriate line of the barrel shifter

The Barrel-Shifter core

The gate-level layout of the barrel-shifter core is as follows:

Shifter Inputs

When taken at face value, the barrel-shifter can only accomplish 15-bit right shifts, and take the low-order eight bits of those. Specifically, if S0 is asserted, inputs D7-D0 pass to outputs O7-O0. If S7 is asserted, inputs D14-D7 pass to outputs O7-O0. In general,

O[7..0] = D[7+x..0+x]

where x is the number of the select (S) line asserted. If more than one select line is asserted, the outputs will be shorted; if zero select lines are asserted, the outputs will be high-impedance.

However, we quickly notice that we can do 15-bit left shifts also (taking only the high-order 8-bits), so long as the shift count is flipped (ones-complemented). As we are not interested in doing fifteen-bit shifts of either kind, we now must map our 8-bit shifts into these inputs.

TypeD14D13D12D11D10D9D8D7D6D5D4D3D2D1D0Flip S?
SL0A7A6A5A4A3A2A1A00000000Yes
SL1A7A6A5A4A3A2A1A01111111Yes
RLA7A6A5A4A3A2A1A0A7A6A5A4A3A2A1Yes
RRA6A5A4A3A2A1A0A7A6A5A4A3A2A1A0No
ASRA7A7A7A7A7A7A7A7A6A5A4A3A2A1A0No
SR00000000A7A6A5A4A3A2A1A0No
SR11111111A7A6A5A4A3A2A1A0No
A trivial implementation would attach a 7-to-1 mux on each D input of the barrel shifter in order to choose which shift operation to use. This layout provides ease of wiring; however, it is not compact, as it does not exploit the similarities in the input patterns for each of the D inputs.

We therefore split the D inputs into three classes: D14-D8, D7, and D6-D0. In the first class, each D input can have up to five possible values (two constant). In the second class, D7 can have two possible values, whereas in the third class, each D input can have four possible values (two constant). Thus, we can use smaller multiplexers for each input. These multiplexers are described in greater detail in the circuit layout section.

The Select input

The appropriate S input is asserted by doing a 3-to-8 decode on the lowest three bits of the ALU's B input. Here we take advantage of the fact that the B input is already inverted for subtract; we use this inverted B input for each of the left shifts and rotates in order to avoid separately flipping the S input for this unit.