From e9878e809c68dfcad90153810d211fc6e590390c Mon Sep 17 00:00:00 2001 From: Aaron Taylor Date: Mon, 12 Jul 2021 18:58:33 -0700 Subject: [PATCH] Added 'long division' as new embedded program for NEDsim. --- hacks/NEDsim/NEDsim.c | 5 + .../NEDsim/ned_programs/long_division.ned_asm | 274 ++++++++++++++++++ 2 files changed, 279 insertions(+) create mode 100644 hacks/NEDsim/ned_programs/long_division.ned_asm diff --git a/hacks/NEDsim/NEDsim.c b/hacks/NEDsim/NEDsim.c index 9b5ceef..31327da 100644 --- a/hacks/NEDsim/NEDsim.c +++ b/hacks/NEDsim/NEDsim.c @@ -203,6 +203,11 @@ static struct ned_program ned_programs[] = { integer_stack, &integer_stack_size, 0x20000000 + }, + { + long_division, + &long_division_size, + 0x20000000 } }; diff --git a/hacks/NEDsim/ned_programs/long_division.ned_asm b/hacks/NEDsim/ned_programs/long_division.ned_asm new file mode 100644 index 0000000..fa9cf2c --- /dev/null +++ b/hacks/NEDsim/ned_programs/long_division.ned_asm @@ -0,0 +1,274 @@ +# (c) 2021 Aaron Taylor +# 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 + -- 2.20.1