Subversion Repositories myblaze

# -*- coding: utf-8 -*-

"""

    LUTs.py

    =============

    Lookup tables for sinus and division calculation

    :copyright: Copyright (c) 2010 Jian Luo

    :author-email: jian.luo.cn(at_)gmail.com

    :license: LGPL, see LICENSE for details

    :revision: $Id: lut.py 5 2010-11-21 10:59:30Z rockee $

"""

from numpy import *

from myhdl import *

from fixed_point import fxintbv,fxint

__all__ = ['ROM', 'LZD', 'GS_R0_Gen',

           'get_lzd_width', 'get_gs_entry_shape']

def my_bin(x, w=16):

    l = len(bin(x))

    return ''.join(['0'*(w-l), bin(x)])

###########

# General #

###########

def ROM(dout, addr, CONTENT):

    """

    General ROM implementation

    """

    @always_comb

    def read():

        dout.next = CONTENT[int(addr)]

    return instances()

##########################

# Leading Zero Detection #

##########################

def count_l_zeros(x, width=8):

    """

    Helper for count leading zeros

    x:      input digit

    width:  bitwidth of x

    """

    count = 0

    for i in downrange(width):

        y = (x>>i) & 1

        if y:

            break

        else:

            count += 1

    return count

def get_lzd_width(width):

    """

    Get word length of counter for leading zero detector

    """

    return int(ceil(log2(width)))

def LZD(dout, index, width=16, depth=1, top=None, offset=0):

    """

    Higher-half LUT of leading zeros for 16bit digits

    """

    if not top:

        top=width

    if depth == 0:  # Leaf LUT

        # Prepare contents

        LZeros = tuple([(count_l_zeros(x, width=width)+offset)%top for x in range(2**width)])

        lut = ROM(dout, index, LZeros)

    else:           # Recursive create 2 half LUTs

        half_width = width / 2

        assert half_width * 2 == width, (

            "Word length of %s can't be evenly divided into 2 parts." % width

        )

        # Glue signals

        index_h = Signal(intbv(0)[half_width:])

        index_l = Signal(intbv(0)[half_width:])

        dout_h = Signal(intbv(0)[len(dout):])

        dout_l = Signal(intbv(0)[len(dout):])

        high = LZD(dout_h, index_h, width=half_width,

                    offset=offset, depth=depth-1, top=top)

        low = LZD(dout_l, index_l, width=half_width, top=top,

                    offset=offset+half_width, depth=depth-1)

        @always_comb

        def input():

            index_h.next = index[:half_width]

            index_l.next = index[half_width:]

        @always_comb

        def output():

            if index_h == 0:

                dout.next = dout_l

            else:

                dout.next = dout_h

    return instances()

##############################

# R0 of Goldschmidt Division #

##############################

def get_gs_entry_shape(width, index_width):

    w = index_width

    ww = width

    r_wl = around(w*1.5)                # Word length of table entry

    r_iwl = ceil(log2(1.0*ww/w))        # Integer word length

    return (int(r_iwl), int(r_wl-r_iwl))

def gen_GSDiv_R0(width=16, index_width=8, debug=0, roundMode='round_even'):

    """

    Generates table of R0 for Goldschmidt division

    width -- Bitwidth of divisor

    index_width -- Number of leading bits for indexing lut.

                   While the first bit of divisor is always 1, so actually only

                   index_width - 1 bits will be used for indexing.

    R_Q -- Representation of entry in the table

    """

    R0=[]

    w = index_width

    ww = width

    r_Q = get_gs_entry_shape(ww, w) # Shape of entries

    for ii in range(2**(w-1), 2**w):

        try:

            val = (ii<<(w)) + (1<<(w-1))

            d0 = fxint(val/(2.0**(ww)), Q=(0,ww), roundMode=roundMode)

            #R0.append(fxint(2.0**(ww)/d0, Q=r_Q, roundMode='round'))

            r = fxint(1./d0.fValue, Q=r_Q, roundMode=roundMode)

            R0.append(r[r_Q[0]+r_Q[1]:])# roundMode='round'))

        except:

            print ii

            raise

    # Check if the table fulfills our requirements:

    #   generate "index_width" bits of leading '1's or '0's

    if debug:

        # Do tests

        for i in range(2**(w-1)):

            ii = (1<<(w-1)) | i

            if debug > 1:

                print '\ndh=%3d' % ii

            dh = ii<<w

            r0 = fxint(int(R0[i]), Q=r_Q, roundMode=roundMode)

            for dl in range(2**(w-1)):

                d = fxint((dh + dl)/2.0**(ww), Q=(0,ww), roundMode=roundMode)

                q = d*r0

                q.Q = (1,ww)

                bs = bin(q)

                if bs.startswith('10'):

                    c = bs[1:].find('1')

                else:

                    c = bs.find('0')

                if c<0:

                    c = q.fwl

                if debug > 1:

                    print '%s(%-8f) x %s(%-8f) = %s(%-14s):%s c=%2d' % (

                                d.Bit(), d.fValue, r0.Bit(), r0.fValue,

                                q.Bit(), q.fValue, q.rep, c

                            )

                if c < w:

                    raise

    return map(int, R0)

def GS_R0_Gen(dout, index, width=16, index_width=8, debug=0, roundMode='round_even'):

    """

    Generator of R0 for GoldSchmidt division, implemented as a lookup table

    width -- Word width

    index_width -- index width

    """

    addr_width = index_width - 1 # msb is always 1, while index >= 0.5

    msb = width - 1

    lsb = msb - addr_width

    R0 = tuple(gen_GSDiv_R0(width=width, index_width=index_width, debug=debug, roundMode=roundMode))

    # Only index_width - 1 bits are needed for indexing

    addr = Signal(intbv(0)[addr_width:])

    lut = ROM(dout, addr, R0)

    @always_comb

    def decode():

        #addr_i = intbv(0)[index_width-1:]

        #addr_i = index[:index_width]

        #addr.next = addr_i[addr_width:]

        addr.next = index[msb:lsb]

    return instances()

#############

# unit test #

#############

def tb_lzd():

    width = 16

    clk = Signal(False)

    d = Signal(intbv(0)[width:])

    lzeros = Signal(intbv(0)[get_lzd_width(width):])

    lzd = LZD(lzeros, d, width=width, depth=1)

    @always(delay(10))

    def clkgen():

        clk.next = not clk

    @instance

    def stim():

        yield delay(1)

        while 1:

            print 'd=%17s lzd=%d' % (my_bin(d,16), lzeros)

            if d >= 256:

                d.next = (d+(1 << 8)) % 65536

            else:

                d.next = d + 1

            yield clk.posedge

    #@always(clk.negedge)

    #def monitor():

        ## moniting on negedge 

    return instances()

def tb_gs_r0():

    width = 16

    iw = 8

    clk = Signal(False)

    d = Signal(fxintbv(0.5, Q=(0,width)))

    qt = get_gs_entry_shape(width, iw)

    r = Signal(fxintbv(0, Q=qt))

    q = Signal(fxintbv(0, Q=(qt[0],width)))

    gsr0 = GS_R0_Gen(r, d, index_width=iw)

    print qt

    @always(delay(10))

    def clkgen():

        clk.next = not clk

    @instance

    def stim():

        yield delay(1) # load r

        while d.fValue < 1:

            q.next = intbv(d.value*r.value)[:qt[0]+qt[1]-1].signed()

            yield delay(1)

            print 'd=%s(%f) * r=%s(%f) == q=%s(%f) %f' % (

                d.Bit(), d.fValue, r.Bit(), r.fValue,

                q.Bit(), q.fValue, 1.0/d.fValue)

            d.next = d.value + 1

            yield clk.posedge

    return instances()

def test_conv():

    rQ = get_gs_entry_shape(16, 8)

    addr = Signal(intbv(0)[16:])

    dout = Signal(intbv(0)[4:])

    rout = Signal(fxintbv(0, Q=rQ))

    toVHDL(LZD, dout, addr)

    toVHDL(GS_R0_Gen, rout, addr, debug=0)

    #gen_GSDiv_R0(debug=True)

if __name__ == '__main__':

    test_conv()

    tb = tb_gs_r0()

    #tb = tb_lzd()

    #gen_GSDiv_R0(debug=2)

    ##tb = traceSignals(tb_reciprocal)

    Simulation(tb).run()

### EOF ###

# vim:smarttab:sts=4:ts=4:sw=4:et:ai: