[Libre-soc-isa] [Bug 937] New: instructions for bigint shift and prefix-code encode

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=937

            Bug ID: 937
           Summary: instructions for bigint shift and prefix-code encode
           Product: Libre-SOC's first SoC
           Version: unspecified
          Hardware: Other
                OS: Linux
            Status: CONFIRMED
          Severity: enhancement
          Priority: ---
         Component: Specification
          Assignee: lkcl at lkcl.net
          Reporter: programmerjake at gmail.com
                CC: libre-soc-isa at lists.libre-soc.org
            Blocks: 817, 933
   NLnet milestone: ---

untested code for 3-in 1-out unsigned shift by signed instructions (dshlsd and
dshrsd in code, we'll also want 3-in 1-out signed shift for handling sign
extension for the MSB end of some bigint formats, and for signed 128-bit
integers)

def u64(v):
    """convert to u64"""
    return int(v) % 2 ** 64

def i64(v):
    """convert to i64"""
    v = u64(v)
    if v >> 63:
        v -= 2 ** 64
    return v

def dshlsd(RA, RB, RC):
    """double-width unsigned-shift-left signed-shift dword"""
    RA = u64(RA)
    RB = u64(RB)
    RC = i64(RC)
    v = (RA << 64) | RB
    if RC <= -64 or RC >= 128:
        return 0
    elif RC < 0:
        v >>= -RC
    else:
        v <<= RC
    return u64(v >> 64)  # return high 64-bits

def dshrsd(RA, RB, RC):
    """double-width unsigned-shift-right signed-shift dword"""
    RA = u64(RA)
    RB = u64(RB)
    RC = i64(RC)
    v = (RA << 64) | RB
    if RC <= -64 or RC >= 128:
        return 0
    elif RC < 0:
        v <<= -RC
    else:
        v >>= RC
    return u64(v)  # return low 64-bits

def bigint_shl(inp, out, shift):
    if shift < 0:
        return bigint_shr(inp, out, -shift)
    offset = shift // 64
    shift %= 64
    for i in range(len(out)):
        out[i] = dshlsd(inp[i - offset], inp[i - offset - 1], shift)

def bigint_shr(inp, out, shift):
    if shift < 0:
        return bigint_shl(inp, out, -shift)
    offset = shift // 64
    shift %= 64
    for i in range(len(out)):
        out[i] = dshrsd(inp[i + offset + 1], inp[i + offset], shift)

def pcenc(symbols, start, symbol_table):
    """ prefix-codes encode
    symbols: list[int]
        symbol indexes
    start: int
        LSB0 bit-index to start encoding at, must be < 64
    symbol_table: list[tuple[int, int]]
        pairs of bits and bit lengths for symbols
    Returns: tuple[list[int], int]
        the output 64-bit words, and the LSB0 bit-index in the last word
        where trailing zero-padding starts.
    """
    out = [0]
    while len(symbols):
        for i in range(len(symbols)):
            # gather-load and shifts and ands to extract fields:
            sym_bits, sym_len = symbol_table[symbols[i]]
            # prefix-sum:
            cur_start = start
            start += sym_len
            # shift then or-reduce:
            out[-1] |= dshlsd(sym_bits[i], 0, cur_start)
            # data-dependent fail-first:
            if start >= 64:
                # part of outer loop
                carry = dshlsd(0, sym_bits[i], cur_start)
                start -= 64
                out.append(carry)
                symbols = symbols[i + 1:]
                break
     return out, start


Referenced Bugs:

https://bugs.libre-soc.org/show_bug.cgi?id=817
[Bug 817] Big Integer Math (sv.adde, sv.subfe, sv.madded, 128 by 64-bit ->
64-bit div/rem, maybe more...)
https://bugs.libre-soc.org/show_bug.cgi?id=933
[Bug 933] prefix-code (like huffman code) decode/encode instructions
-- 
You are receiving this mail because:
You are on the CC list for the bug.