Shifts, Rotates, Barrel Shifters and Streaming
Predict what each shift operator puts in the empty bits. Know what a shift, a rotate and a streaming operator cost in gates.
You Will Be Able To
- Predict when
>>>fills with the sign bit and when it fills with zeros. - Explain why a constant shift is free and a variable shift is a barrel shifter.
- Write a variable rotate from one shift of a double-width vector.
- Choose a streaming operator to reverse the bits or the bytes of a bus.
- Lesson
- R10.3
- Time
- 30 min
- Runs on
- Your browser
- Check
- 5 questions
A volume control divided each audio sample by 4. Quiet passages were fine. Every negative sample came out as a large positive one, and the speaker clicked.
The operand is declared unsigned
input logic [7:0] sample; // -128 to 127
...
assign y = sample >>> sh;
Icarus 12 for a sample of -64 and sh = 2: y= 48 (00110000). Two zeros came in at the top.
The operand is signed
input logic [7:0] sample; // -128 to 127
...
assign y = $signed(sample) >>> sh;
Icarus 12: y= -16 (11110000). Two copies of the sign bit came in. Lint is silent on both versions.
Three Shifts and What Fills the Gap
A shift moves every bit of a vector left or right. Bits that leave the vector are lost. The operator decides what enters at the other end.
| Expression | Operand 1100_0101 | Result | What came in |
|---|---|---|---|
u << 2 | unsigned | 0001_0100 | zeros at the bottom |
u >> 2 | unsigned | 0011_0001 | zeros at the top |
u >>> 2 | unsigned | 0011_0001 | zeros: the operand is not signed |
s >> 2 | signed | 0011_0001 | zeros: >> never looks at the sign |
s >>> 2 | signed | 1111_0001 | copies of the sign bit |
s <<< 2 | signed | 0001_0100 | zeros: the same as << |
u >> 9, u << 8 | unsigned | 0000_0000 | every bit left the vector |
s >>> 9 | signed | 1111_1111 | only sign bits are left |
Icarus 12 and Verilator 5.052 print the same eight rows.
>>> is the arithmetic right shift. It keeps the sign only when the expression it shifts is signed. Lesson R1.4 gives the rule: an expression is signed only if every operand is.
Assigned to an 8-bit y, with s = 1100_0101 | Result | Why |
|---|---|---|
y = s >>> 2; | 1111_0001 | the operand is signed |
y = $signed(u) >>> 2; | 1111_0001 | the cast makes it signed |
y = s[7:0] >>> 2; | 0011_0001 | a part-select is unsigned |
y = (s >>> 2) + 8'd0; | 0011_0001 | 8'd0 is unsigned, so the whole expression is |
y = (s >>> 2) + 0; | 1111_0001 | a plain 0 is signed |
y = pick ? s >>> 2 : u; | 0011_0001 | the other arm is unsigned |
Measured on both simulators. One unsigned operand anywhere in the expression turns the shift into a zero fill.
A Constant Shift Is Wiring
When the amount is a constant, each output bit is one fixed input bit or a 0. Synthesis connects wires and builds nothing.
| Design (8 bits) | Cells | Levels |
|---|---|---|
a << 3, a >> 1 and a signed sa >>> 2 together | 0 | 0 |
{a[4:0], 3'b000}, the same left shift as a concatenation | 0 | 0 |
Measured on this flow. Multiplying or dividing by a constant power of two is free.
The width still matters. A shift is done at the width of its left operand and its context. With n at 9, 8'd1 << n printed 0 in $display, where nothing widens it. Assigned to a 16-bit mask it gave 512. A plain 1 << n is 32 bits wide and printed 512.
A Variable Shift Is a Barrel Shifter
When the amount is a signal, every output bit can come from several input bits. The circuit is a barrel shifter: one row of muxes for each bit of the amount.
s.- I/O
- Datapath
- Data
- Control
- One stage
Stage 1 is eight muxes. Each picks its own bit or the bit one place to the right, as
s[0]says. - Powers of two
Stage 2 moves by two places and stage 4 by four. Any amount from 0 to 7 is a sum of 1, 2 and 4.
- The cost
Three rows of muxes, so three levels of logic. A 32-bit shifter has five rows.
Read the diagram as text
- a[7:0]: the word
- s[2:0]: the amount, 0 to 7
- Stage 1: shift by 1 if s[0]
- Stage 2: shift by 2 if s[1]
- Stage 4: shift by 4 if s[2]
- y[7:0]: a << s
- a[7:0] → Stage 1: 8 bits
- Stage 1 → Stage 2
- Stage 2 → Stage 4
- Stage 4 → y[7:0]
- s[2:0] → Stage 1: s[0]
- s[2:0] → Stage 2: s[1]
- s[2:0] → Stage 4: s[2]
You do not write the stages. a << s builds them. The count is one level for each bit of the amount.
| Width | a << s | signed a >>> s | rotate left (next section) |
|---|---|---|---|
| 8 | 26 cells, 3 levels | 21 cells, 3 levels | 24 cells, 3 levels |
| 16 | 67 cells, 4 levels | 60 cells, 4 levels | 64 cells, 4 levels |
| 32 | 164 cells, 5 levels | 155 cells, 5 levels | 160 cells, 5 levels |
| 64 | 429 cells, 8 levels | 382 cells, 8 levels | 384 cells, 6 levels |
Measured on this flow. The rotate is exactly W muxes per stage: 8 times 3, 16 times 4, 32 times 5, 64 times 6. At 64 bits the two shifts came out deeper than their six stages.
Rotates
A rotate is a shift whose lost bits come back in at the other end. SystemVerilog has no rotate operator.
A rotate by a constant is a concatenation, and so it is wiring: {a[5:0], a[7:6]} rotates left by 2. A rotate by a signal needs one trick.
Two shifts and an OR
assign y = (a << s) | (a >> (4'd8 - s));
Correct for every amount. 74 cells and 7 levels on this flow: two shifters and a subtract.
One shift of a double-width vector
module rol8 (
input logic [7:0] a,
input logic [2:0] s,
output logic [7:0] y
);
logic [15:0] d;
assign d = {a, a} << s; // a joined to itself, then one shift
assign y = d[15:8]; // the top half is a rotated left by s
endmodule
The same results. 24 cells and 3 levels: eight muxes in each of three stages.
Join the vector to itself and shift the pair left. The bits that leave the top copy are replaced by the same bits from the bottom copy. For a right rotate, shift the pair right and take the bottom half.
Streaming: Reorder with No Gates
The streaming operator {<<N{x}} cuts x into blocks of N bits and writes the blocks in the opposite order. With no N the blocks are single bits.
rev=01001011 swp=cdab3412 nib=dcba4321 same=1234abcd c=5ad2.module tb;
logic [31:0] a = 32'h1234_abcd, swp, nib, same;
logic [7:0] b = 8'b1101_0010, rev;
logic [15:0] c;
initial begin
rev = {<<{b}}; // 1-bit blocks: reverse the bits
swp = {<<8{a}}; // 8-bit blocks: reverse the bytes
nib = {<<4{a}}; // 4-bit blocks: reverse the nibbles
same = {>>{a}}; // left to right: the same order
c = {<<8{b, 8'h5a}}; // several items: joined first, then reordered
$display("rev=%b swp=%h nib=%h same=%h c=%h", rev, swp, nib, same, c);
$finish(0);
end
endmodule| Form | What it does | A use |
|---|---|---|
{<<{x}} | reverses the bits | a CRC or a serial port that sends the low bit first |
{<<8{x}} | reverses the bytes; bits inside a byte keep their order | an endian swap between a bus and a network header |
{>>{x}} | keeps the order | packing an array or a struct into a vector |
{>>8{lane}} = word; | on the left side: unpacks word into the bytes of an array | splitting a bus into lanes; lane[0] got the top byte |
Synthesize a module with the bit reverse, the byte swap and the nibble swap of a 32-bit word. It reports 0 cells and 0 levels. The unpack into four byte lanes is 0 cells too. All of it is wiring.
The Lab: The Sample That Changed Sign
| Port | Direction | Width | Meaning |
|---|---|---|---|
| sample | input | [7:0] | a two's complement sample, -128 to 127 |
| sh | input | [1:0] | the scale: divide by 1, 2, 4 or 8 |
| y | output | [7:0] | sample / 2**sh, rounded toward minus infinity |
- Latency
- combinational
- Corner cases
- negative samples, and
shat 0. Done when: Run printsy= -16for -64 withsh2 andy= -2for -3 withsh1, and Synthesize reports 14 cells
Run as shipped
Line 1 is right: 100 with
sh2 gives 25. Line 2 is right, because a shift by 0 moves nothing. Lines 3 to 5 show 48, 126 and 16 for negative samples.Find the unsigned operand
sampleis declaredlogic [7:0], which is unsigned.>>>on it fills with zeros. Lint prints nothing: the code is legal.Try a fix that fails
Write
assign y = (sh == 2'd0) ? sample : $signed(sample) >>> sh;and Run. The lines do not change. The unsigned arm makes the whole ternary unsigned.Fix the expression
Write
assign y = $signed(sample) >>> sh;and Run: -64, -16, -2, -16. Synthesize reports 14 cells and 2 levels, all$_MUX_. The shipped version was 17 cells.
Asked in interviews
What is the difference between
>>and>>>?>>always fills with zeros.>>>fills with the sign bit, but only when the expression it shifts is signed. On an unsigned operand the two are the same.What does a shift cost in hardware?
A shift by a constant is wiring and costs nothing. A shift by a signal is a barrel shifter. It has one row of muxes and one level of logic for each bit of the amount.
How do you rotate a vector by a variable amount?
Join the vector to itself, shift the pair by the amount and take one half. It costs one barrel shifter. Two shifts and an OR also work, and cost about three times as much on this flow.
Try It
The bench applies five samples and prints y as a signed number and in binary. The first two lines are right. A positive sample has a 0 sign bit, and a shift by 0 moves nothing.
In the last three lines zeros came in at the top, because sample is unsigned. With $signed(sample) the lines read -16, -2 and -16.
Synthesize reports 17 cells and 2 levels for the shipped design: 13 $_MUX_ and 4 gates. The fixed design is 14 cells, all $_MUX_, and 2 levels.
Synthesize the design to measure its cells and inspect the mapped gates.
sample= 100 sh=2 | y= 25 (00011001) sample= -64 sh=0 | y= -64 (11000000) sample= -64 sh=2 | y= 48 (00110000) sample= -3 sh=1 | y= 126 (01111110) sample=-128 sh=3 | y= 16 (00010000)Original design · 17 cells · 0 flip-flops · 0 latches · 2 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
module tb;
logic [7:0] sample = 0, y;
logic [1:0] sh = 0;
level_scale dut (.*);
task automatic show(input int v, input int s);
sample = 8'(v); sh = 2'(s); #1;
$display("sample=%4d sh=%0d | y=%4d (%b)", $signed(sample), sh, $signed(y), y);
endtask
initial begin
show(100, 2);
show(-64, 0);
show(-64, 2);
show(-3, 1);
show(-128, 3);
$finish(0);
end
endmodule
Check Yourself
Common Mistakes
Wrong Build a one-hot mask as {8'd1 << n} inside braces when n can be 8 or more.
Inside braces nothing widens the shift. It is done at the width of its left operand, so the 1 falls off the top and the mask is 0.
Fix Give the left operand the width of the result you need. In a plain 16-bit assignment the target widens the shift, but a sized operand is clear anywhere.
logic [3:0] n; // 0 to 15
logic [15:0] mask;
assign mask = {8'd1 << n}; // 0 for n = 8 to 15logic [3:0] n; // 0 to 15
logic [15:0] mask;
assign mask = 16'd1 << n;Wrong Write a variable rotate as two shifts joined by an OR.
The second shift needs a subtract for its amount, and the flow built 74 cells where one shift builds 24.
Fix Shift the vector joined to itself, {a, a} << s, and take the top half.
Wrong Use x >>> 1 in place of a signed divide by 2.
The shift rounds toward minus infinity and the divide rounds toward zero, so they differ on odd negative values.
Fix Decide the rounding from the brief first. Lesson R1.6 measures both on -3.
Wrong Pass a streaming operator straight to $display or into a larger expression.
A streaming operator has no width of its own, and Verilator stops with "cannot be used in an implicitly cast context".
Fix Assign it to a variable of the width you want, then use the variable.
Remember
<<and>>fill with zeros.>>>fills with the sign bit only when the whole expression is signed.- One unsigned operand, a part-select or an unsigned ternary arm turns
>>>into a zero fill. - A shift by a constant is wiring: 0 cells. A shift by a signal is a barrel shifter with one mux level per amount bit.
- Rotate by shifting the vector joined to itself: 24 cells at 8 bits, against 74 for two shifts and an OR.
- Streaming operators reverse bits or bytes for 0 cells. Assign the result to a sized variable.