Added 'long division' as new embedded program for NEDsim.

[screensavers] / hacks / NEDsim / ned_programs / long_division.ned_asm

# (c) 2021 Aaron Taylor <ataylor at subgeniuskitty dot com>
# See LICENSE.txt file for copyright and license details.

# This program performs binary long division, halting when complete.

# Dividend, chosen for alternating bit pattern to make it easily identifiable
# whenever it appears somewhere on the stack.
WORD_715827882

# Divisor, also chosen for a unique, visually recognizable bit pattern.
WORD_65534
IM_1
ADD

# The stack is initialized. Time to run the program.
JSR>divide
HALT

##########################################################################################
generatesignflag
##########################################################################################
# Description:
#   Given a pair of twos-complement signed integers X and Y, generates a sign flag.
#   Flag is non-zero if the product of X and Y would be negative, otherwise flag is zero.
# Call Stack:
#   Y Operand
#   X Operand
#   Return PC <-- TOS
# Return Stack:
#   Sign Flag <-- TOS
##########################################################################################
    # Place Return PC at bottom of stack.
    LDSP+2
    LDSP+1
    STSP+3
    STSP+0
    
    # Stack now looks like:
    #   Return PC
    #   X Operand
    #   Y Operand <-- TOS

    IM_4
    LOAD
    AND
    SWAP
    IM_4
    LOAD
    AND
    XOR
    SWAP
    RTS
    
##########################################################################################
negate
##########################################################################################
# Description:
#   Returns the additive inverse of a twos-complement operand.
# Call Stack:
#   Operand
#   Return PC <-- TOS
# Return Stack:
#   Result <-- TOS
##########################################################################################
    SWAP
    NOT
    IM_1
    ADD
    SWAP
    RTS

##########################################################################################
absolutevalue
##########################################################################################
# Description:
#   Returns the absolute value of a twos-complement operand.
# Call Stack:
#   Operand
#   Return PC <-- TOS
# Return Stack:
#   Result <-- TOS
##########################################################################################
    SWAP
    LDSP+0
    IM_4
    LOAD
    AND
    BRZ>absolutevaluereturn
        JSR>negate
    absolutevaluereturn
        SWAP
        RTS

##########################################################################################
subtract
##########################################################################################
# Description:
#   Performs X-Y and returns result on TOS.
# Call Stack:
#   Y Operand
#   X Operand
#   Return PC <-- TOS
# Return Stack:
#   Result <-- TOS
##########################################################################################
    # Place Return PC at bottom of stack.
    LDSP+2
    LDSP+1
    STSP+3
    STSP+0
    # Stack now looks like:
    #   Return PC
    #   X Operand
    #   Y Operand <-- TOS

    JSR>negate
    ADD
    SWAP
    RTS

##########################################################################################
divide
##########################################################################################
# Description:
#   Division with remainder.
#   Halts on zero divisor.
# Call Stack:
#   Dividend
#   Divisor
#   Return PC <-- TOS
# Return Stack:
#   Quotient
#   Remainder <-- TOS
##########################################################################################
    # Move Return PC to bottom of stack.
    LDSP+2
    SWAP
    STSP+2
    SWAP

    # Stack now looks like:
    #   Return PC
    #   Dividend
    #   Divisor <-- TOS

    # Check for zero divisor
    LDSP+0
    BRZ>divideexception

    # Generate a sign flag and store it behind the operands.
    LDSP+1
    LDSP+1
    JSR>generatesignflag
    LDSP+2
    SWAP
    STSP+2

    # Stack now looks like:
    #   Return PC
    #   Sign flag (nonzero for negative result, 0 for positive result)
    #   Divisor
    #   Dividend <-- TOS

    # Convert both Dividend and Divisor to absolute value.
    JSR>absolutevalue
    SWAP
    JSR>absolutevalue

    # Stack now looks like:
    #   Return PC
    #   Sign flag (nonzero for negative result, 0 for positive result)
    #   ABS(Dividend)
    #   ABS(Divisor) <-- TOS

    # Prepare stack for division algorithm.
    IM_31           # Cycle Counter - Loop from n-1 -> 0 where n = 32 bits.
    IM_0            # Quotient
    IM_0            # Remainder

    # Binary long division
    divisionloop
        # Check Cycle Counter for end-of-loop condition (CC = -1).
        LDSP+2 # Cycle Counter
        IM_1
        ADD
        BRZ>divisionloopend

            # While Cycle Counter >= 0

            # Left-shift Remainder by 1 bit.
            IM_1
            IM_4 # Address of 0x80000000 register
            LOAD
            OR
            SHIFT
    
            # Set LSB of Remainder equal to bit (Cycle Counter) of Dividend.
            LDSP+4 # Dividend
            LDSP+3 # Cycle Counter
            SHIFT
            IM_1
            AND
            OR
    
            # Check if Remainder >= Divisor
            LDSP+0 # Remainder
            LDSP+4 # Divisor
            BLT>divisionsubloopend

                # If Remainder >= Divisor

                # Set Remainder = Remainder - Divisor
                LDSP+3 # Divisor
                SWAP
                JSR>subtract

                # Set bit (Cycle Counter) of Quotient equal to 1.
                SWAP
                IM_1
                LDSP+3 # Cycle Counter
                IM_4
                LOAD
                OR
                SHIFT
                OR
                SWAP

            divisionsubloopend

            # Decrement Cycle Counter
            IM_1
            LDSP+3 # Cycle Counter
            JSR>subtract
            STSP+2

            # Loop over next division cycle
            JMP>divisionloop

        divisionloopend

        # Stack cleanup
        STSP+1
        STSP+1
        STSP+1

    # Stack now looks like:
    #   Return PC
    #   Sign flag (nonzero for negative result, 0 for positive result)
    #   Remainder
    #   Quotient <-- TOS

    # Set sign of results.
    LDSP+2 # Sign flag
    BRZ>divisioncleanup
        JSR>negate
        SWAP
        JSR>negate
        SWAP

    divisioncleanup

    # Clean up and return
    SWAP
    LDSP+3 # Return PC
    SWAP
    STSP+2
    SWAP
    STSP+2
    RTS

    # For now we can only HALT on errors and let the PC inform our debugging.
    divideexception
        HALT