#!/usr/bin/env python3

# MIT License, Witold Baryluk, 2022

# double dabble algorithm for convering binary numbers to decimal notation.
# This is program is not for speed, but just for ilustration and education.
# It works, and could be starting point to trying to understand
# how it works, and implement it for example on a microcontroller without
# division.

# x = 243
x = 65244
# x = 4294967185
# x = 348199535390660743


digits = len(str(x))
width = len(bin(x)) - 2


scratch = [0] * (digits * 4)

word_size = 8  # for computing shift_count
shift_count = 0  # number of word-bit shifts

x0 = x

print(
    f"Will convert {width}-bit value 0b{x:b} to decimal (expecting end result: {x0} with {digits} digits)"
)
print()


def shift_scratch(new_lsb=0):
    global scratch, shift_count
    print("shift")
    shift_count += (len(scratch) + 4) // word_size
    scratch = scratch[1:] + [new_lsb]


def scratch_digit_read(j):
    return (
        (scratch[4 * j] << 3)
        + (scratch[4 * j + 1] << 2)
        + (scratch[4 * j + 2] << 1)
        + (scratch[4 * j + 3])
    )


def scratch_digit_write(j, x):
    global scratch
    assert 0 <= x and x <= 0xF
    # assert 0 <= x and x <= 9
    scratch[4 * j + 0] = x >> 3
    scratch[4 * j + 1] = (x >> 2) & 1
    scratch[4 * j + 2] = (x >> 1) & 1
    scratch[4 * j + 3] = x & 1


def extract_msb(x):
    return (x >> (width - 1)) & 1


def shift_x():
    global x, shift_count
    shift_count += (width + 7) // word_size
    x = (x << 1) & ((1 << width) - 1)


def dump(show_ups=False, end=" "):
    print("Bin:", end="")
    for i in range(digits):
        print(f" {scratch_digit_read(i):04b}", end="")
    print(f"  {x:0{width}b}")
    print("Dec:", end="")
    for i in range(digits):
        print(f" {scratch_digit_read(i):4d}", end="")
    print()
    print("    ", end="")
    if show_ups:
        for i in range(digits):
            if scratch_digit_read(i) >= 5:
                print(f"    ^", end="")
            else:
                print(f"     ", end="")
    print()


def dd():
    global x
    dump()

    for i in range(3):
        shift_scratch(extract_msb(x))
        print(shift_count)
        shift_x()
        print(shift_count)
        dump(show_ups=(i == 2))

    for i in range(width - 3):
        print("checking if need to add")
        for j in range(digits):
            digit = scratch_digit_read(j)
            power = f"10^{digits-j-1}"
            print(f"digit at position {j:2d} ({power:5}): {digit:2}", end=" : ")
            if digit >= 5:
                digit += 3
                print(f"need to add,    result:  {digit:2d}")
                # assert 0 <= digit and digit <= 9
                scratch_digit_write(j, digit)
            else:
                print(f"no need to add, keeping: {digit:2d}")
        dump(show_ups=False)
        shift_scratch(extract_msb(x))
        print(shift_count)
        shift_x()
        print(shift_count)
        dump(show_ups=(i < width - 4))

    print("Final decimal result:", end="")
    got = 0
    for i in range(digits):
        digit = scratch_digit_read(i)
        print(f" {digit:d}", end="")
        got = 10 * got + digit
    print()
    assert got == x0
    print(f"Final result is same as expected from the start ({x0})")


if __name__ == "__main__":
    dd()
    print(f"Total number of {word_size}-bit shifts:", shift_count)