Barrel Shifter

A Barrel shifter performs the operation v << s (or v >> s with flipped bits) where s is not constant. An elegant implementation is the approach via cascaded multiplexer elements.

This cshift primitive is later instanced procedurally, iterating through the variable i

Shifter element in MyHDL

In [1]:
import sys
sys.path.insert(0, "../..")
In [2]:
from myirl.emulation.myhdl import *

@block
def cshift(q : Signal.Output, a : Signal, b : Signal, sbit : Signal, 
           msb : Signal,
           # These can take a signal or a fixed bool:
           asr, rotate,
           WRAP : bool):
    carry = Signal(bool()) # Carry bit
    u, v = [ Signal(bool()) for i in range(2) ]
    
    @always_comb
    def assign_carry():
        if asr: # arithmetic shift right
            carry.next = sbit & msb
        else:
            carry.next = 0

    @always_comb
    def assign():
        u.next = a & ~sbit
        
        if rotate == False:         
            if WRAP:
                v.next = carry
            else:
                v.next = b & sbit
        else:
            v.next = b & sbit
            
    @always_comb
    def assign_q():    
        q.next = u | v
        
    return instances()

Shifter stage

In [3]:
@block
def shifter_stage(
    shifter,
    w_in : Signal,
    w_out : Signal.Output,
    msb : Signal,
    nmux : int, sbit : Signal, DATA_WIDTH : int, W_POWER : int, asr : bool, rotate : bool
):
    inst = []

    # Create signal array
    w = [ Signal(bool()) for i in range(DATA_WIDTH) ]
    wo = concat(*reversed(w))
    wi = [ w_in[i] for i in range(DATA_WIDTH) ]

    MUX_W = DATA_WIDTH // nmux

    for imux in range(nmux):
        tmp = imux * MUX_W
        # print(imux)
        for i in range(tmp, tmp + MUX_W):
            j = i + MUX_W//2
            m = j % DATA_WIDTH
            inst.append(shifter(w[m], wi[m], wi[i], sbit, msb, asr, rotate,
                         j >= DATA_WIDTH ))

    @always_comb
    def assign():
        w_out.next = wo

    return instances()

The barrel shifter implementation

In [4]:
@block
def barrel_shifter(shifter, clk : ClkSignal, ce : Signal, val : Signal, s : Signal, result : Signal.Output, \
                   rotate = False, W_POWER = 5 ):
    
    DATA_WIDTH = 2 ** W_POWER
    print("DATA WIDTH", DATA_WIDTH, "ROTATE", rotate)
        
    worker = [ val ]
    worker = worker + [ Signal(intbv()[DATA_WIDTH:]) for i in range(W_POWER) ]
    msb = val[DATA_WIDTH-1]

    sbit = [ s[i] for i in range(len(s))]
    
    shifter_stages = []
    for stage in range(W_POWER):
        K = W_POWER - stage - 1
        print("Stage %d" % stage)
        shifter_stages.append( \
                shifter_stage(shifter, worker[stage], worker[stage + 1], msb, 2 ** stage, sbit[K], \
                            DATA_WIDTH, W_POWER, False, rotate) \
                             )
        
    @always(clk.posedge)
    def assign():
        if ce == True:
            result.next = worker[W_POWER]
        
    return instances()

Translate and test

The translation into the target RTL or HDL takes place via a test bench factory function. This allows us to switch between different simulator back end methods. Here, we can choose between GHDL and CXXRTL.

In [9]:
from simulation import *

from myirl.simulation import print_
from myirl.emulation.factory_class import factory
from myirl.targets import pyosys

class example_design(factory.Module):
    def __init__(self, name, simclass, *args, **kwargs):
        super().__init__(name, simclass, *args, **kwargs)
        self.W_POWER = 4
        self.debug = False

        # Top level signal set
        self.clk = self.ClkSignal(name="clk")
        self.ce = self.Signal(bool())
        self.val, self.result = [ self.Signal(intbv(0xaa00)[2 ** self.W_POWER:]) for i in range(2) ]
        self.result.rename("result")
        self.s = self.Signal(intbv()[self.W_POWER:])
    
    def build(self):
        return barrel_shifter(cshift,
            clk = self.clk,
            ce = self.ce,
            val = self.val,
            s = self.s,
            result = self.result,
            rotate = False,
            W_POWER = self.W_POWER
        )
    
    def emit_rtlil(self, fileprefix):
        tgt = pyosys.RTLIL("barrel_shifter")
        inst = self.build()
        d = inst.elab(tgt)
        d[0].write_rtlil(fileprefix)

    @factory.testbench('ns')
    def tb_rtl(self):
        
        inst = self.build()

        clk = self.clk
        ce = self.ce
        val = self.val
        result = self.result
        s = self.s
        
        @self.always(delay(2))
        def clkgen():
            clk.next = ~clk

        TEST_VALUES = [
            (0xdead, 8, 0xad00),
            (0x8f01, 15, 0x8000),
        ]

        @self.sequence
        def stim():
            for item in TEST_VALUES:
                ce.next = False
                s.next = item[1]
                val.next = item[0]
                yield(clk.posedge)
                ce.next = True
                yield(clk.posedge)
                yield(clk.posedge)

                print(result, type(result))
                assert result == item[2]

            raise StopSimulation

        return instances()    
In [10]:
from yosys.simulator import CXXRTL

d = example_design("rtlil_bs", CXXRTL)
d.emit_rtlil("test")
 Module rtlil_bs: Existing instance barrel_shifter, rename to barrel_shifter_3 
DATA WIDTH 16 ROTATE False
Stage 0
 Module rtlil_bs: Existing instance shifter_stage, rename to shifter_stage_12 
 Module rtlil_bs: Existing instance cshift, rename to cshift_6 
 Module rtlil_bs: Existing instance cshift, rename to cshift_7 
Stage 1
 Module rtlil_bs: Existing instance shifter_stage, rename to shifter_stage_13 
Stage 2
 Module rtlil_bs: Existing instance shifter_stage, rename to shifter_stage_14 
Stage 3
 Module rtlil_bs: Existing instance shifter_stage, rename to shifter_stage_15 
Creating process 'barrel_shifter/assign' with sensitivity (clk'rising,)
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_8_s1_16_4_0_0 
 Adding module with name `shifter_stage_15` 
 DEBUG: SKIP NON-SIGNAL ARGUMENT `shifter` : <class 'myirl.emulation.myhdl.wrapped_wrapper'> 
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_4_s1_16_4_0_0 
 Adding module with name `shifter_stage_14` 
 DEBUG: SKIP NON-SIGNAL ARGUMENT `shifter` : <class 'myirl.emulation.myhdl.wrapped_wrapper'> 
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_2_s1_16_4_0_0 
 Adding module with name `shifter_stage_13` 
 DEBUG: SKIP NON-SIGNAL ARGUMENT `shifter` : <class 'myirl.emulation.myhdl.wrapped_wrapper'> 
 Elaborating component cshift_s1_s1_s1_s1_s1_0_0_1 
 Adding module with name `cshift_7` 
 Elaborating component cshift_s1_s1_s1_s1_s1_0_0_0 
 Adding module with name `cshift_6` 
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_1_s1_16_4_0_0 
 Adding module with name `shifter_stage_12` 
 DEBUG: SKIP NON-SIGNAL ARGUMENT `shifter` : <class 'myirl.emulation.myhdl.wrapped_wrapper'> 
 Adding module with name `barrel_shifter_3` 
 DEBUG: SKIP NON-SIGNAL ARGUMENT `shifter` : <class 'myirl.emulation.myhdl.wrapped_wrapper'> 
 FINALIZE implementation `barrel_shifter_3` of `barrel_shifter` 
Output filename: test.il

-- Running command `tee -q hierarchy -top \barrel_shifter_1' --

-- Running command `tee -q write_cxxrtl -namespace barrel_shifter_1_2922  -header /tmp/barrel_shifter_1_2922_rtl.cpp' --

-- Running command `tee -q hierarchy -top \barrel_shifter_3' --

-- Running command `write_rtlil test.il' --

6. Executing RTLIL backend.
In [11]:
from myirl.test.ghdl import GHDL

# XXX Note: we must carry out the simulation backend sequence in this order. Otherwise,
# a yet undetermined sticky effect will report a combinatorial loop error.
for sim in CXXRTL, GHDL:
    d = example_design("testbench", sim)
    tb = d.tb_rtl()
    print(76 * '=')
    tb.run(60)
 Module testbench: Existing instance barrel_shifter, rename to barrel_shifter_4 
DATA WIDTH 16 ROTATE False
Stage 0
 Module testbench: Existing instance shifter_stage, rename to shifter_stage_16 
 Module testbench: Existing instance cshift, rename to cshift_8 
 Module testbench: Existing instance cshift, rename to cshift_9 
Stage 1
 Module testbench: Existing instance shifter_stage, rename to shifter_stage_17 
Stage 2
 Module testbench: Existing instance shifter_stage, rename to shifter_stage_18 
Stage 3
 Module testbench: Existing instance shifter_stage, rename to shifter_stage_19 
Creating process 'barrel_shifter/assign' with sensitivity (clk'rising,)
DEBUG: Skip non-simulation type <class '__main__.example_design'>
DEBUG: Skip non-simulation type <class 'list'>
============================================================================
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_8_s1_16_4_0_0 
 Adding module with name `shifter_stage_19` 
 DEBUG: SKIP NON-SIGNAL ARGUMENT `shifter` : <class 'myirl.emulation.myhdl.wrapped_wrapper'> 
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_4_s1_16_4_0_0 
 Adding module with name `shifter_stage_18` 
 DEBUG: SKIP NON-SIGNAL ARGUMENT `shifter` : <class 'myirl.emulation.myhdl.wrapped_wrapper'> 
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_2_s1_16_4_0_0 
 Adding module with name `shifter_stage_17` 
 DEBUG: SKIP NON-SIGNAL ARGUMENT `shifter` : <class 'myirl.emulation.myhdl.wrapped_wrapper'> 
 Elaborating component cshift_s1_s1_s1_s1_s1_0_0_1 
 Adding module with name `cshift_9` 
 Elaborating component cshift_s1_s1_s1_s1_s1_0_0_0 
 Adding module with name `cshift_8` 
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_1_s1_16_4_0_0 
 Adding module with name `shifter_stage_16` 
 DEBUG: SKIP NON-SIGNAL ARGUMENT `shifter` : <class 'myirl.emulation.myhdl.wrapped_wrapper'> 
 Adding module with name `barrel_shifter_4` 
 DEBUG: SKIP NON-SIGNAL ARGUMENT `shifter` : <class 'myirl.emulation.myhdl.wrapped_wrapper'> 
 FINALIZE implementation `barrel_shifter_4` of `barrel_shifter` 
Compiling /tmp/barrel_shifter_4_25ee.pyx because it changed.
[1/1] Cythonizing /tmp/barrel_shifter_4_25ee.pyx
running build_ext
building 'barrel_shifter_4_25ee' extension
x86_64-linux-gnu-gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O2 -Wall -g -ffile-prefix-map=/build/python3.9-RNBry6/python3.9-3.9.2=. -fstack-protector-strong -Wformat -Werror=format-security -g -fwrapv -O2 -g -ffile-prefix-map=/build/python3.9-RNBry6/python3.9-3.9.2=. -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -fPIC -DCOSIM_NAMESPACE=barrel_shifter_4_25ee -I../../myirl/../ -I/tmp/ -I/usr/share/yosys/include -I/usr/include/python3.9 -c /tmp/barrel_shifter_4_25ee.cpp -o build/temp.linux-x86_64-3.9/tmp/barrel_shifter_4_25ee.o
x86_64-linux-gnu-gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O2 -Wall -g -ffile-prefix-map=/build/python3.9-RNBry6/python3.9-3.9.2=. -fstack-protector-strong -Wformat -Werror=format-security -g -fwrapv -O2 -g -ffile-prefix-map=/build/python3.9-RNBry6/python3.9-3.9.2=. -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -fPIC -DCOSIM_NAMESPACE=barrel_shifter_4_25ee -I../../myirl/../ -I/tmp/ -I/usr/share/yosys/include -I/usr/include/python3.9 -c /tmp/barrel_shifter_4_25ee_rtl.cpp -o build/temp.linux-x86_64-3.9/tmp/barrel_shifter_4_25ee_rtl.o
x86_64-linux-gnu-g++ -pthread -shared -Wl,-O1 -Wl,-Bsymbolic-functions -Wl,-z,relro -g -fwrapv -O2 -Wl,-z,relro -g -fwrapv -O2 -g -ffile-prefix-map=/build/python3.9-RNBry6/python3.9-3.9.2=. -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 build/temp.linux-x86_64-3.9/tmp/barrel_shifter_4_25ee.o build/temp.linux-x86_64-3.9/tmp/barrel_shifter_4_25ee_rtl.o -o build/lib.linux-x86_64-3.9/barrel_shifter_4_25ee.cpython-39-x86_64-linux-gnu.so
copying build/lib.linux-x86_64-3.9/barrel_shifter_4_25ee.cpython-39-x86_64-linux-gnu.so -> 
Open for writing: tb_rtl.vcd
 CXXRTL context: SKIP INTERFACE ITEM `shifter` 
 CXXRTL context: SKIP INTERFACE ITEM `rotate` 
 CXXRTL context: SKIP INTERFACE ITEM `W_POWER` 
<result> : 0xad00 <class 'simulation.Signal'>
<result> : 0x8000 <class 'simulation.Signal'>
STOP SIMULATION @22 
 Declare obj 'tb_rtl' in context '(example_design 'testbench')' 
 Module testbench: Existing instance barrel_shifter, rename to barrel_shifter_5 
DATA WIDTH 16 ROTATE False
Stage 0
 Module testbench: Existing instance shifter_stage, rename to shifter_stage_20 
 Module testbench: Existing instance cshift, rename to cshift_10 
 Module testbench: Existing instance cshift, rename to cshift_11 
Stage 1
 Module testbench: Existing instance shifter_stage, rename to shifter_stage_21 
Stage 2
 Module testbench: Existing instance shifter_stage, rename to shifter_stage_22 
Stage 3
 Module testbench: Existing instance shifter_stage, rename to shifter_stage_23 
Creating process 'barrel_shifter/assign' with sensitivity (clk'rising,)
Creating process 'tb_rtl/clkgen' with sensitivity ([ DeltaT 2 ns ],)
Creating sequential 'sequence/stim' 
============================================================================
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_8_s1_16_4_0_0 
 Writing 'shifter_stage_23' to file /tmp/shifter_stage_23.vhdl 
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_4_s1_16_4_0_0 
 Writing 'shifter_stage_22' to file /tmp/shifter_stage_22.vhdl 
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_2_s1_16_4_0_0 
 Writing 'shifter_stage_21' to file /tmp/shifter_stage_21.vhdl 
 Elaborating component cshift_s1_s1_s1_s1_s1_0_0_1 
 Writing 'cshift_11' to file /tmp/cshift_11.vhdl 
 Elaborating component cshift_s1_s1_s1_s1_s1_0_0_0 
 Writing 'cshift_10' to file /tmp/cshift_10.vhdl 
 Elaborating component shifter_stage__wrapped_wrapper_s16_s16_s1_1_s1_16_4_0_0 
 Writing 'shifter_stage_20' to file /tmp/shifter_stage_20.vhdl 
 Elaborating component barrel_shifter__wrapped_wrapper_s1_s1_s16_s4_s16_0_4 
 Writing 'barrel_shifter_5' to file /tmp/barrel_shifter_5.vhdl 
 Elaborating component tb_rtl__example_design 
 Writing 'tb_rtl' to file /tmp/tb_rtl.vhdl 
 Creating library file /tmp/myirl_module_defs_ut1dtcmv/module_defs.vhdl 
==== COSIM stdout ====

==== COSIM stderr ====
/tmp/myirl_module_defs_ut1dtcmv/module_defs.vhdl:6:1:warning: package "module_defs" was also defined in file "/tmp/myirl_module_defs_p9ib8f4e/module_defs.vhdl" [-Wlibrary]
/home/testing/src/myhdl2/myirl/targets/libmyirl.vhdl:1:1:warning: package "myirl_conversion" was also defined in file "/home/testing/.local/lib/python3.9/site-packages/myirl-0.0.0-py3.9-linux-x86_64.egg/myirl/targets/libmyirl.vhdl" [-Wlibrary]
/home/testing/src/myhdl2/myirl/targets/../test/vhdl/txt_util.vhdl:42:1:warning: package "txt_util" was also defined in file "/home/testing/.local/lib/python3.9/site-packages/myirl-0.0.0-py3.9-linux-x86_64.egg/myirl/targets/../test/vhdl/txt_util.vhdl" [-Wlibrary]

==== COSIM stdout ====
analyze /home/testing/src/myhdl2/myirl/targets/../test/vhdl/txt_util.vhdl
analyze /home/testing/src/myhdl2/myirl/targets/libmyirl.vhdl
analyze /tmp/cshift_10.vhdl
analyze /tmp/cshift_11.vhdl
analyze /tmp/shifter_stage_20.vhdl
analyze /tmp/shifter_stage_21.vhdl
analyze /tmp/shifter_stage_22.vhdl
analyze /tmp/shifter_stage_23.vhdl
analyze /tmp/barrel_shifter_5.vhdl
analyze /tmp/tb_rtl.vhdl
elaborate tb_rtl

==== COSIM stderr ====

==== COSIM stdout ====
0xAD00 <class 'myirl.emulation.signals.Signal'>
0x8000 <class 'myirl.emulation.signals.Signal'>
/tmp/tb_rtl.vhdl:69:9:@22ns:(assertion failure): Stop Simulation
/tmp/tb_rtl:error: assertion failed
in process .tb_rtl(myirl).stim
/tmp/tb_rtl:error: simulation failed

==== COSIM stderr ====

Further Optimization

A bit more optimization can be done by moving the code into a cythonizeable library. See Cythonized barrel shifter

This primitive approach however is not very compact and this design should not be mass-instanced using CXXRTL due to issues with combinatorial logic.

See Compact barrel shifter implementation for an improved version.