Restoring and nonrestoring binary division

divide.py

#!/usr/bin/python3

# Per's code
def sw_binary_divide2(n, d, num_bits):
    q = 0
    r = n
    d2 = d << (num_bits - 1)
    for i in range(num_bits):
        q <<= 1
        if r >= d2:
            q |= 1
            r -= d2
        r <<= 1
    return q

# Modified variant 1
def sw_binary_divide3(n, d, num_bits):
    q = 0
    r = n
    d2 = d << num_bits
    for i in range(num_bits):
        q <<= 1
        r <<= 1
        if r >= d2:
            q |= 1
            r -= d2
    return q

# Modified variant 2
def sw_binary_divide4(n, d, num_bits):
    q = 0
    r = n
    for i in range(num_bits):
        q <<= 1
        r <<= 1
        if (r >> num_bits) >= d:
            q |= 1
            r -= d << num_bits
    return q

# Modified variant 3 (one shift register only)
def sw_binary_divide5(n, d, num_bits):
    qr = n
    low_mask = (1 << num_bits) - 1
    for i in range(num_bits):
        qr <<= 1
        hi_diff = (qr >> num_bits) - d
        if hi_diff >= 0:
            qr = (hi_diff << num_bits) | (qr & low_mask) | 1
    return qr & low_mask

def nonrestoring_divide(n, d, num_bits):
    qr = n
    ds = d << num_bits
    for i in range(num_bits):
        qr <<= 1
        # NOTE only actually need an adder in the high half of qr
        # the low half never changes
        if qr >= 0:
            qr = (qr | 1) - ds
        else:
            qr += ds

    # final complement step
    q = (qr << 1) & ((1 << num_bits) - 1)
    r = qr >> num_bits
    if r < 0:
        r += d
    else:
        q += 1

    assert n == q*d + r
    return q

# More hardware-y!
def nonrestoring_divide2(n, d, num_bits):
    qr = n
    ds = d << num_bits
    for i in range(num_bits):
        ispos = 1 if qr >= 0 else 0
        # NOTE only actually need an adder in the high half of qr
        # the low half never changes
        qr = ((qr << 1) | ispos) + (ds ^ -ispos) + ispos

    # final complement step
    q = (qr << 1) & ((1 << num_bits) - 1)
    r = qr >> num_bits
    if r < 0:
        r += d
    else:
        q += 1

    assert n == q*d + r
    assert 0 <= r < d
    return q

# Clean up final step
def nonrestoring_divide3(n, d, num_bits):
    qr = n
    ds = d << num_bits
    for i in range(num_bits):
        ispos = 1 if qr >= 0 else 0
        # NOTE only actually need an adder in the high half of qr
        # the low half never changes
        qr = ((qr << 1) | ispos) + (ds ^ -ispos) + ispos

    # final complement step
    lomask = (1 << num_bits) - 1

    # note q - ~q = q + ~(~q) + 1 = q+q+1 = (q<<1) + 1
    # instead of adding 1 to q always then subtracting 1 if r<0,
    # add ispos, same as in the main iteration.
    ispos = 1 if qr >= 0 else 0
    q = ((qr << 1) | ispos) & lomask
    # d & (ispos-1) <=> d if !ispos, 0 otherwise
    r = (qr >> num_bits) + (d & (ispos - 1))

    assert n == q*d + r
    assert 0 <= r < d
    return q

def test_divide(division_alg, N):
    for a in range(1 << N):
        for b in range(1, 1 << N):
            q = division_alg(a, b, N)
            assert q == a // b

#test_divide(sw_binary_divide2, 8)
test_divide(sw_binary_divide5, 8)
#test_divide(nonrestoring_divide, 8)
#test_divide(nonrestoring_divide2, 8)
test_divide(nonrestoring_divide3, 8)