
;*******************************************************
;*                   PICMATH32.ASM                     *
;*                                                     *
;*   A SET OF 32 BIT MATH ROUTINES AND MATH TUTORIAL   *
;*           For MicroChip PIC Microcontrollers        *
;*            Converted to SX by James Newton          *
;*                                                     *
;*   Add32/Subtract32/Multiply32 handle both + and -   *
;*          Divide32 handles only + numbers            *
;*          Divide32x handles both + and -             *
;*-----------------------------------------------------*
;*                    Written By                       *
;*                Fr. Thomas McGahee                   *
;*            tom_mcgahee@mailsnare.com                *
;*                                                     *
;* Permission granted for anyone to use these routines *
;*          for personal or commercial use             *
;*         as long as author is given credit           *
;*           by including this credit block            *
;*                                                     *
;*    Users may modify routines to fit their needs     *
;*******************************************************
;*              Last Updated: April, 2004              *
;*******************************************************

;*******************************************************
;* If you find this tutorial and programs useful, you  *
;*       can let me know by sending an email to:       *
;*              tom_mcgahee@mailsnare.com              *
;*******************************************************

;*******************************************************
;* I have used long descriptive names for my variables *
;* and routines. I have done this to make the programs *
;* easier to understand. Once you understand how the   *
;* programs work, you might want to make the variable  *
;* names and program names smaller. You might also     *
;* choose to eliminate the comments.                   *
;*                                                     *
;* I suggest that if you plan on doing this, you make  *
;* a COPY of this assembly file and make changes only  *
;* to the copy.                                        *
;*******************************************************

;*******************************************************
;* Most material is repeated in various places.        *
;* I wrote this not only as a program, but also as a   *
;* tutorial. I have found that it is better to repeat  *
;* certain information than to force the user to look  *
;* all over the place in order to find it.             *
;*                                                     *
;* I hope that you find this information useful.       *
;* I have tried to include enough comments to make the *
;* logic behind the program understandable.            *
;*                                                     *
;* These routines were all written from scratch by     *
;* myself without reference to any programs written by *
;* anyone else. I refrained from including             *
;* optimizations except in those cases where it would  *
;* be easy to follow the logic. As such, you may find  *
;* a more highly optimized 32 bit divide program, for  *
;* example, but chances are you won't be able to       *
;* understand how it functions.                        *
;*                                                     *
;* Multiply32 & divide32 are fairly complex, so I have *
;* prefaced them with a quick explanation of the       *
;* math process for those who are interested in        *
;* how it is performed. In addition, divide32 also has *
;* a pseudo-code example so you can follow the logic   *
;* of the program more readily.                        *
;*******************************************************

;*********************************************************************
;BEGIN GENERAL INFO GENERAL INFO GENERAL INFO GENERAL INFO GENERAL INFO

;*********************************************************************
;* 32 BIT MATH ROUTINES FOR PIC MICROCONTROLLERS
;*            GENERAL INFORMATION
;*
;---------------------------------------------------------------------
;* BINARY REPRESENTATION
;* In the base ten number system each digit has one of ten states.
;* These ten states are: 0 1 2 3 4 5 6 7 8 9
;* The value of a base ten digit depends on it's state and its power.
;* 10^0=1  10^1=10  10^2=100  10^3=1,000  10^4=10,000 etc.
;* In the number 123, the 3 has a value of 3*10^0 which is 3*1=3
;* The 2 has a value of 2*10^1 which is 2*10=20
;* The 1 has a value of 1*10^2 which is 1*100=100
;* The value of the entire number 123 is the sum of the parts. This
;* gives us 100+20+3 which we call "one hundred and twenty three".
;*
;* Binary numbers work in the same way. HOWEVER:
;* Binary bits have only two states. The states are 0 and 1.
;* This simplifies the math tremendously. The rules for addition
;* are: 0+0=0  0+1=1  1+0=1 and 1+1=10 (note the carry).
;* The rules for multiplication are even simpler:
;* 0*0=0  0*1=0  1*0=0  1*1=1
;*
;* Just as in base ten numbers, the value of a binary bit is a
;* function of it's state and it's power.
;* The powers of two are: 2^0=1  2^1=2  2^2=4  2^3=8  2^4=16  2^5=32
;* 2^6=64  2^7=128 (and 2^8=256, etc.)
;* If a bit is 0, then it's VALUE is also 0, regardless of its power.
;* If a bit is a 1, then it's VALUE is equal to it's power.
;* To determine the value of a binary number, add up the values of all
;* it's parts. For example, 00000101 is 4+1=5
;*
;* In binary, 1111 is 8+4+2+1=15. Since a 4 bit binary number can have
;* 16 possible states (0,1,2,....,14,15), these groupings of four
;* bits are referred to as hexadecimal numbers, or hex digits.
;* Since our "usual" counting numerals are 0 1 2 3 4 5 6 7 8 9
;* hex numerals build on this and become:
;* 0 1 2 3 4 5 6 7 8 9 A B C D E F.
;* Thus A=10  B=11  C=12  D=13  E=14  F=15. At first, hex notation may
;* seem a little strange, but it is a very useful form of notation.
;*
;* The basic binary "word" length is 8 bits. We call 8 bits a byte.
;* 4 bits is half of a byte. Because the words "byte" and "bite" sound
;* the same, engineers began to playfully call 4 bits a "nibble", and
;* the name has stuck. 4 bits is a nibble. Two nibbles make up a byte.
;* Hex bytes consist of two hex nibbles, and so take on the form
;* XX such as 2B, which is 2*16+11=43
;*
;* To avoid confusion, MPASM uses base specifiers when dealing with
;* numbers. Let's look at how the base ten number 266 might be shown:
;* In decimal it is d'266'
;* In binary it is b'100001010' which is 256+8+2=266
;* In hex it is h'010A' because 01=1*256=256. 0A=10*1=10.
;* The sum is 256+10=266
;*
;* By the way, MPASM allows several variations on how the radix
;* can be specified. Note also that leading zeros can be left out.
;* Hex notation allows both upper and lower case for A thru F.
;*
;* Here are the radix notations available for numbers:
;* Decimal: d'266' or D'266' or .266  (.266 is confusing. Avoid it).
;* Binary: b'100001010' or B'100001010'
;* Hex: h'010A  or  H'010A'  or  0x010A
;* Although MPASM allows you to choose a default radix, it is usually
;* best to always specify the radix using one of the above notations.
;* A specified radix will always over-ride the selected default radix.
;*
;* To specify a negative number in any radix, specify 0-number.
;* For example, 0-d'266' would yield -266. (Since 0 is the same in
;* any radix, you do not have to specify it's radix explicitly.)
;*
;* Long strings of binary digits become difficult to read. In base
;* ten we use commas every 3 places to the left of the decimal point to
;* help us deal with large numbers like 23,452,751.
;* Binary numbers are sometimes broken up into sets of 8 bits,
;* called bytes.

;* In binary we do not use commas, and MPASM does not allow spaces
;* within numbers. However, when working with binary on PAPER, I
;* have always found it useful to break large binary numbers into
;* bytes and separate them with a space. I also separate
;* hex numbers with a space between each byte. I find that this makes
;* it easier to work with. For example, the 32 bit binary number
;* 01110010100110010101001110101011 looks very intimidating, whereas
;* 01110010 10011001 01010011 10101011 is a bit easier to handle, and
;* 72 99 53 AB (which is the same binary number written in hex) seems
;* almost friendly by comparison.
;*
;---------------------------------------------------------------------
;* UNSIGNED REPRESENTATION and SIGNED TWOS COMPLEMENT REPRESENTATION:
;*
;*	32 bits can be used to represent a value up to 4,294,967,295.
;*	That is (256*256*256*256)-1
;*	In this case only positive values can be represented. That is
;*	just fine in the case of addition and multiplication, but
;*	cannot work if you also want to use negative numbers.
;*
;*	Note that subtraction and division involve the use of negative
;*	numbers, so to perform THESE operations you HAVE to have a way
;*	of representing negative numbers.
;*
;---------------------------------------------------------------------
;* SIGNED BINARY TWOS COMPLEMENT REPRESENTATION
;*	A binary number can be converted into it's negative form by first
;*	complementing the number (make all 1's 0's, and all 0's 1's) and
;*	then adding 1 to the result. Complementing it puts it into
;*	what is called "one's complement notation". After you add one to
;*	THAT, you have what is called "two's complement notation".
;*
;*	One of the features of two's complement notation is that the
;*	MSB (Most Significant Bit) of a negative number is ALWAYS 1.
;*	In the case of a 32 bit representation, that means 1 bit is
;*	allocated to sign duty, and the other 31 bits can hold value
;*	information. That is why we have to restrict the input and
;*	output VALUE of our numbers to 31 bits in a 32 bit system.
;*
;*	Please note that the MSB being 1 is NOT the same thing as the
;*	MSB being a negative sign.
;*
;*	Take the number 2 in 32 bit binary. It would be represented as:
;*	00000000 00000000 00000000 00000010. When we complement it we get
;*      11111111 11111111 11111111 11111101  adding 1 to this we get
;*      11111111 11111111 11111111 11111110 which represents -2.
;*
;*	00000000 00000000 00000000 00000010 if we add 2
;*      11111111 11111111 11111111 11111110 and -2, we get
;*	-----------------------------------
;*   (1)00000000 00000000 00000000 00000000 The (1) represents a carry
;*	out from the MSB (Most Significant Bit). Note that the value of
;*	the result (ignoring the carry) is 0.  2-2=0.
;*
;*	To represent negative numbers in a 32 bit system we use
;*	twos complement notation where a negative number will always
;*	have a 1 at the MSB position. You will hopefully have noticed
;*	that in twos complement notation we can perform subtraction
;*	through the addition of negative numbers. Twos complement
;*	notation allows both positive and negative numbers to be
;*	represented and mathematically manipulated. Twos complement
;*	notation is sometimes referred to as twos complement
;*	representation, or signed binary.
;*
;*	With SIGNED binary, 32 bits can represent +/- 2,147,483,647
;*
;*	You might be wondering why I didn't say +/- 2,147,483,648.
;*	It turns out that 2,147,483,648 and -2,147,483,648 in a 32 bit
;*	representation end up having the same representation. For this
;*	reason this value is disallowed in 32 bit representation.
;*
;*	Let's look at why this is so. Convert to signed binary form:
;*	10000000 00000000 00000000 00000000 is complemented to become
;*	01111111 11111111 11111111 11111111. Add 1 to this and you get
;*	10000000 00000000 00000000 00000000 which is exactly the same
;*	as the original.
;*
;*	An easy way to help you remember what the disallowed
;*	value is in any binary system is to make only the MSB a 1.
;*	For example, in a 24 bit binary system the disallowed value will
;*	be 10000000 0000000 0000000. In a 16 bit system the disallowed
;*	value will be 10000000 00000000. In an 8 bit system the
;*	disallowed value will be 10000000.
;*
;*	By the way, if you use the two's complement method to find the
;*	negative of 0 you get 0. But here there is no problem,
;*	because 0 - 0 = 0 so the result is always correct. Another way
;*	to look at this is to realize that 0 is neither positive nor
;*	negative. Cool!
;*
;*	The really nice thing about two's complement notation is that
;*	when you add numbers in this notation you always get the right
;*	answer. Add 123 and -125 and you get -2. In binary we perform
;*	subtraction through the addition of negative numbers. It
;*	works beautifully.
;*
;*	All 32 bits can be used for addition and multiplication (only)
;*	if the user chooses to *interpret* ALL numbers as positive.
;*
;*	Obviously, subtraction REQUIRES twos complement notation
;*	to allow negative numbers to be used. Subtraction is restricted
;*	to handling 31 bits of input and output for positive values
;*	when the total bit length is 32 bits.
;*
;*	Division involves a subtraction process, so intermediate
;*	results at certain stages may go negative. This means
;*	that numerators, multipliers, and quotients are restricted
;*	to a 31 bit maximum length, and may ONLY be positive.
;*
;*	It is the 31 bit restriction to allow subtraction that dictates
;*	the use of only POSITIVE input and output values for the
;*	divide32 routine.
;*
;*	32 bit binary values are used in sets that each contain 4 bytes.
;*	MSB is leftmost bit of <set>_4, and LSB is rightmost bit
;*	of <set>_1.
;*
;*	For example: <accumulator> is the general specifier for a
;*	particular 32 bit set that is comprised of 4 bytes named
;*	accumulator_4  accumulator_3  accumulator_2  accumulator_1
;*
;*	Bits within a byte are specified with a comma and a value from
;*	0 to 7. For example, "accumulator_1,0" would specify the LSB.
;*
;*
;*	It is easy to decode the value of a binary number. Each bit
;*	represents a power value. Just add up all the power values
;*	where there is a 1. For example, in the byte 01101001
;*	we get 1 + 8 + 32 + 64 = 105
;*
;---------------------------------------------------------------------
;* MAXIMUM INPUT VALUE:
;*	Maximum twos complement input value to any math function is
;*	therefore limited to +/- 2,147,483,647
;*	This is 31 bits for positive numbers.
;*	BE CAREFUL! The REAL limit is a function of the RESULT!
;*	For example, 2,147,483,647 + 3 would violate max RESULT!
;*	In this example the result would APPEAR to be negative!
;*
;*	Note that the math32 routines will not catch that kind
;*	of error, because they do not know whether you are
;*	treating the result as a positive or negative number.
;*	If treating it as a positive number, the answer would be
;*	correct. If treating the answer as a negative number,
;*	the answer would be incorrect.
;*
;*	!!! In the case of add32 and multiply32, you may
;*	raise the bit limit to 32 if you are *interpreting*
;*	ALL numbers as positive. Make sure RESULT does not
;*	exceed 32 bit size limit! Maximum value in this
;*	case is raised to 4,294,967,295
;*
;---------------------------------------------------------------------
;* MAXIMUM RESULT:
;*	MAXIMUM result of any operation is limited
;*	to +/- 2,147,483,647.
;*
;*	!!! In the case of add32 and multiply32, you may
;*	raise the bit limit to 32 if you are interpreting
;*	ALL numbers as positive. Make sure ANSWER does not
;*	exceed 32 bit size limit! Maximum answer is then
;*	raised to 4,294,967,295
;*
;*	For multiplication, the SUM of the BITS must be less than 32.
;*	For example, a 16 bit number times a 15 bit number
;*	will yield a 31 bit result. This is OK. But a 16 bit number
;*	times a 16 bit number yields a 32 bit result that
;*	would have lost any sign information. This is OK if
;*	you are working only with positive numbers, but is
;*	disastrous if working with negative numbers!
;*
;*	When I refer to a number as being a 15 bit number, I mean
;*	that from the LSB to the left-most "1" there are 15 bits.
;*	Example: 10000000 00000000 is a 16 bit number in 16 bit field.
;*		 01000000 00000000 is a 15 bit number in 16 bit field.
;*		 00000000 00000101 is a 3 bit number in 16 bit field.
;*		 00000000 00000001 is a 1 bit number in 16 bit field.
;*
;*	Bits within a byte are given bit identifiers where 0 is the
;*	LSB, and 7 is the MSB. For example: in the byte accumulator_1
;*	containing 00001000, the "1" bit is accumulator_1,3.
;*
;*	          Shown visually:
;*	76543210  are the bit identifiers
;*	00001000  is the accumulator_1 contents.
;*	    ^     the "1" bit is at position "3"
;---------------------------------------------------------------------
;* 32 BIT OVERFLOW and ERROR FLAGS:
;*
;*	Certain attempted operations will exceed the 32 bits!
;*
;*	OVERFLOW is detected by the add32 routine, and returned
;*	in _mflag_overflow. Since add32 is called by
;*	subtract32/multiply32, these will also
;*	pass along (and possibly act upon) _mflag_overflow.
;*
;*	Upon entry, multiply32 and divide32 both clear ALL
;*	math error flags by clearing the mflag register.
;*
;*	!!! Direct calls by the user to add32 and subtract32
;*	require the user to CLEAR at least _mflag_overflow
;*	before calling the routines IF they want to make use of
;*	_mflag_overflow to report an overflow condition.
;*
;*	!!!Divide32 ALWAYS returns _mflag_overflow cleared, since
;*	it specifically restricts input values to 31 bit
;*	positive values. Thus overflow is logically impossible.
;*	Divide32 provides some additional error checking.
;*
;.....................................................................
;* OVERFLOW IN GENERAL:
;*
;*	!!! User calls to add32 and subtract32 must clear the
;*	_mflag_overflow before calling the routines if they wish
;*	to make use of this feature.
;*
;*	_mflag_overflow reports:
;*		OVERFLOW from any 32 bit operation.
;*		this includes add32/subtract32/multiply32
;*
;*	BE AWARE of the fact that adding two unsigned
;*	32 bit numbers can generate a 33 bit result,
;*	which CANNOT be contained in a 32 bit number.
;*	Overflow will result and be flagged.
;*
;*	BE AWARE that adding two 31 bit negative numbers
;*	can result in a 32 bit negative result that then
;*	LOOKS like a positive number because the sign bit
;*	got shifted out into the carry and got lost!
;*	Overflow will result and be flagged.
;*
;*	BE AWARE that multiplying two 32 bit unsigned
;*	numbers could result in a 64 bit answer!
;*	Overflow will result and be flagged.
;*	Carry from the 32nd bit will cause an overflow, and the
;*	program will report the error via _mflag_overflow!
;*	It is YOUR responsibility to check this flag after
;*	add32/subtract32/multiply32
;*
;*	BE AWARE that multiplying two 32 bit signed numbers
;*	can result in a 33rd bit overlow, and the
;*	remaining 32 bit result is not what you think it is!
;*	_mflag_overflow will report the error.
;*
;.....................................................................
;* SPECIAL ERROR REPORTING FOR CALLS TO DIVIDE32/DIVIDE32X:
;*
;*	divide32 will never return _mflag_overflow set to 1,
;*		so you can ignore it completely.
;*
;*	_mflag_derror reports:
;*		ANY fatal error in divide32. (_dneg and _dzero).
;*		Test this flag first.
;*
;*	_mflag_dneg reports:
;*		Attempt to use negative numbers in divide32.
;*		It will flag this for <numerator> and <denominator>.
;*		(NOT used in divide32x)
;*
;*	_mflag_dzero reports:
;*		Attempt to divide by 0 in divide32.
;*
;*	These flags are automatically cleared upon entry to
;*	divide32. The user does not have to clear them.
;*
;*
;*	BE AWARE that divide32 allows only POSITIVE values,
;*	and their size cannot exceed 31 bits. This is the
;*	bad news. The good news is that the answer is then
;*	forced to be 31 bits or less and cannot cause
;*	an overflow error.
;*
;---------------------------------------------------------------------
;* VARIABLE DATA SETS USED FOR MATH OPERATIONS:
;*
;* <ACCUMULATOR>:
;*	primary use: 		<accumulator> for add32.
;*	 add32:			<accumulator> = <accumulator> + <operand>
;*
;*	add32 called by:
;*	 subtract32:		<accumulator> = <accumulator> +
;*						negated <operand>
;*	 multiply32: 		<accumulator> = <multiplier> * <operand>
;*	 multiply32plus: 	<accumulator2> = <accumulator1> +
;*						 (<multiplier2> * <operand2>)
;*
;*	<accumulator>:
;*	 aliased as: 		<numerator> for divide32
;*	 aliased as: 		<remainder> AFTER divide32 is done
;*
;*	used as INPUT to:	add32/subtract32/multiply32/*divide32
;*					*aliased as <numerator>
;*	used as OUTPUT from:	add32/subtract32/multiply32/*divide32
;*					*aliased as <remainder>
;*	holds ANSWER for:	add32/subtract32/multiply32
;*	holds <remainder>:	after divide32. (Leftover from division).
;*
;* <OPERAND>:
;*	primary use: 		<operand> for add32
;*	 add32:			<accumulator> = <accumulator> + <operand>
;*
;*	add32 called by:
;*	 neg32:			<operand> = negated<operand>
;*	 subtract32:		<accumulator> = <accumulator> +
;*						negated<operand>
;*	 multiply32		<accumulator> = <multiplier> * <operand>
;*	 divide32:		<operand> is aliased as <denominator>
;*				<quotient> = <numerator> / <denominator>
;*	<operand>:
;*	aliased as: 		<denominator> for divide32
;*
;*	used as INPUT to:	add32/negate32/subtract32/multiply32/*divide32
;*					*aliased as <denominator>
;*	used as OUTPUT from:	negate32
;*	holds ANSWER for:	negate32
;*
;* <MULTIPLIER>:
;*	primary use:		<multiplier> in multiply32
;*	 multiply32: 		<accumulator> = <multiplier> * <operand>
;*
;*	<multiplier>:
;*	aliased as: 		<quotient> for divide32
;*
;*	used as INPUT to:	multiply32
;*	used as OUTPUT from:	*divide32
;*					*aliased as <quotient>
;*
;* <NUMERATOR>:
;*	primary use:		<numerator> in divide32
;*	 divide32:		<quotient> = <numerator> / <denominator>
;*
;*	alias of:		<accumulator>
;*
;*	aliased as:		<remainder> (at end of division it holds remainder)
;*
;*	used as INPUT to:	*add32/*subtract32/*multiply32/divide32
;*					*aliased as <accumulator>
;*	used as OUTPUT from:	*add32/*subtract32/*multiply32/divide32
;*					*aliased as <accumulator>
;*	holds <remainder>:	after divide32. (Leftover from divide operation).
;*
;* <DENOMINATOR>:
;*	primary use: 		<denominator> in divide32
;*	 divide32:		<quotient> = <numerator> / <denominator>
;*
;*	alias of:		<operand>
;*
;*	used as INPUT to:	*add32/*negate32/*subtract32/*multiply32/divide32
;*					*aliased as <operand>
;*	used as OUTPUT from:	*negate32
;*					*aliased as <operand>
;*
;* <QUOTIENT>:
;*	primary use:		<quotient> in divide32
;*	 divide32:		<quotient> = <numerator> / <denominator>
;*
;*	alias of:		<multiplier>
;*
;*	used as INPUT to:	divide32/*multiply32
;*					*aliased as <multiplier>
;*	used as OUTPUT from:	divide32
;*
;---------------------------------------------------------------------
;* QUICK LOOK AT MATH FUNCTIONS
;*
;* In general, answers are limited to +/- 2,147,483,647.
;* In this implementation, only the divide32 routine is
;* restricted to the use of POSITIVE numbers. All else
;* may freely use a mix of positive and negative numbers
;*
;* Number notation is twos complement for negative numbers.
;* This restricts positive numbers in general to 31 bits
;* so we can allow 31 bit positive numbers to be negated
;* to 32 bit wide twos complement form.
;*
;* add32
;* Addition:	<accumulator> = <accumulator> + <operand>
;*
;* neg32
;* Negation:	<operand> = negative of <operand>
;*		Negating a negative number makes it positive.
;*		(uses twos complement notation)
;*
;* subtract32
;* Subtraction:	<accumulator> = <accumulator> - <operand>
;*
;* multiply32
;* Multiplication: <accumulator> = <multiplier> * <operand>
;*	Upon entry the <accumulator> is cleared.
;*	(See multiply32plus for multiply that does NOT clear
;*	the <accumulator>).
;*	NOTE that SUM of input BITS (+ form) must be LESS than 32.
;*	For example, a 22 bit positive number times an
;*	11 bit positive number will yield a 33 bit positive
;*	result. Overflow flag will be set.
;*
;* multiply32plus
;* Multiplication with Addition:
;* <accumulator> = <accumulator1> + (<multiplier2> * <operand2>)
;*	This is included as an added convenience to the basic
;*	math routines. Requires no additional code.
;*
;* divide32
;* Division:	<quotient> = <numerator> / <denominator>
;*		(remainder is returned in numerator>
;*	In this implementation, input values are RESTRICTED to only
;*	POSITIVE numbers. Max positive size of input(s) is 31 bits.
;*	Max positive result is 31 bit number 2,147,483,647
;*
;*
;* divide32x
;* Division:	<quotient> = <numerator> / <denominator>
;*		(remainder is returned in numerator>
;*	In this implementation, input values are within the range
;*	+/- 2,147,483,647. Result has range +/- 2,147,483,647.
;*
;*	The tradeoff is that there is some additional overhead.
;*	Divide32x determines the correct output polarity,
;*	converts inputs to positive only values, calls divide32,
;*	and then converts the <quotient> to a negative form if
;*	the previously determined polarity demands a negative
;*	output value.
;*
;*	(The only possible error is attempted division by zero.)
;*
;*  *******************************************************
;*  * Any remarks made about multiply32 apply also to     *
;*  * multiply32plus. The only difference is that         *
;*  * multiply32 begins by clearing the <accumulator>,    *
;*  * but multiply32plus keeps the current <accumulator>  *
;*  * contents and adds into the existing contents.       *
;*  *******************************************************
;*
;***********************************************************************

;END GENERAL INFO GENERAL INFO GENERAL INFO GENERAL INFO GENERAL INFO
;***********************************************************************
;BEGIN DIRECTIVES DIRECTIVES DIRECTIVES DIRECTIVES DIRECTIVES DIRECTIVES

;===================================================================
;= THE FOLLOWING SECTION CONTAINS DIRECTIVES, DEFINITIONS, AND     =
;= ASSIGNMENTS THAT ALLOW THE 32 BIT MATH ROUTINES TO WORK.        =
;= SOME OF THIS STUFF YOU WILL NEED TO MERGE INTO YOUR OWN PROGRAM =
;= IN ORDER TO USE THE MATH ROUTINES. SOME OF THIS STUFF IS HERE   =
;= TO ALLOW YOU TO TEST THE MATH ROUTINES IN A STAND-ALONE MODE    =
;= THAT YOU CAN LOAD INTO MPLAB AND PLAY WITH.                     =
;= REMEMBER TO REMOVE THE "EXTRA" CODE WHEN YOU INTEGRATE THE MATH =
;= ROUTINES INTO YOUR OWN PROGRAMS!                                =
;===================================================================

; First, some directives to allow for testing of the math functions

	DEVICE SX28	;this directive MUST come first
				;!!! set this to the version of
				;!!! SX that you will be using.

	IRC_CAL IRC_SLOW
    FREQ 50
;END DIRECTIVES DIRECTIVES DIRECTIVES DIRECTIVES DIRECTIVES
;*****************************************************
;BEGIN RAM RAM RAM RAM RAM RAM RAM RAM RAM RAM RAM RAM

;**************************************************
;* Declare RAM Variable usage using CBLOCK method *
;**************************************************

		ORG	$20	;bank 0  h'20' to h'6f'.
	;80 locations (+16 Globals)
	;!!! You may place variables elsewhere
	;if desired.

mflag           DS	1	;8 bit math flag register (see bit definitions below)
isitneg         DS	1	;a byte used to indicate polarity DURING divide32x

scancounter     DS	1	;used by divide32 to keep track of bit position

	;*** 32 bit SETS ***

	;NOTE: I refer to SETS of bytes such as accumulator_1 thru
	;accumulator_4 by placing BASE name inside angle brackets.
	;Thus, <accumulator> refers to the entire accumulator SET.

	;NOTE: The ORDER in which sets like <accumulator> are
	;declared is significant, as they are sometimes referenced
	;referenced in the routines using indirect addressing via
	;fsr/indf method.
	;Do NOT rearrange the order within a set.
	;MSB is leftmost bit of _4 member of set

accumulator_4   DS	1	;32 bit <accumulator> for
accumulator_3   DS	1	;add32/subtract32/multiply32.
accumulator_2   DS	1	; aliased as <numerator> when doing divide32.
accumulator_1   DS	1	; aliased as <remainder> after divide32

goback_4        DS	1	;32 bit copy used to speed things up
goback_3        DS	1	;when divide32 routine has to back-track.
goback_2        DS	1	; !!! these can also be used by other routines
goback_1        DS	1	; !!! for temporary storage if they don't use
						; !!! the divide32 routine.

operand_4       DS	1	;32 bit operand for
operand_3       DS	1	;add32/neg32/subtract32/lshift32/multiply32
operand_2       DS	1	;
operand_1       DS	1	; aliased as <denominator> for divide32

multiplier_4    DS	1	;32 bit multiplier.
multiplier_3    DS	1	;<accumulator> = <multiplier> * <operand>
multiplier_2    DS	1	;
multiplier_1    DS	1	; aliased as <quotient> for division

	;END OF CBLOCK VARIABLE DECLARATIONS

;address of last item should be a max value of 6fh.
;if address exceeds 6fh, then we would have to move to another
;ram block. Then we would have to keep track of bank useage.
;It is always nice when you can keep all variables in ram bank 0

;END RAM RAM RAM RAM RAM RAM RAM RAM RAM RAM RAM RAM RAM RAM
;***********************************************************
;BEGIN ALIASES ALIASES ALIASES ALIASES ALIASES ALIASES ALIASES

;*******************************
; SHARED RESOURCES AND ALIASES *
;*******************************

;These shared resources have different names to reflect their different
;uses within the math routines. This makes the routines easier to
;understand, and at the same time keeps resource usage smaller by
;sharing the RAM resources.
;THE USE OF AN ALIAS REQUIRES NO ADDITIONAL RAM!

;NOTE: When using SXKey to experiment with the program, be aware
;that the variable WATCH window can only be loaded with the
;variable names declared in cblock above.
;This means, for example, that to watch the aliased set
;<numerator> you would have to "watch" <accumulator>
;in the watch window.

numerator_4 = accumulator_4	;32 bit <numerator>
numerator_3	= accumulator_3	;for divide32
numerator_2	= accumulator_2
numerator_1	= accumulator_1

remainder_4	= accumulator_4	;32 bit <remainder>
remainder_3	= accumulator_3	;at end of divide32
remainder_2	= accumulator_2
remainder_1	= accumulator_1

denominator_4 = operand_4	;32 bit <denominator>
denominator_3 = operand_3	;for divide32
denominator_2 = operand_2
denominator_1 = operand_1

quotient_4 = multiplier_4	;32 bit <quotient> returned
quotient_3 = multiplier_3	;by divide32
quotient_2 = multiplier_2
quotient_1 = multiplier_1

;*************************
;* mflag bit definitions *
;*************************

			;I use a leading underscore to indicate that
			;we are dealing with a single BIT.
			;Flags below are arranged as they are
			;just for ease of viewing in MPLAB

			;A 1 means the flag is asserted for that error.

_mflag_0 		=	mflag,0	;not used
_mflag_dzero	=	mflag,1	;divide by zero in divide32/x
_mflag_2 		=	mflag,2	;not used
_mflag_dneg		=	mflag,3	;negative input to divide32
_mflag_4 		=	mflag,4	;not used
_mflag_derror	=	mflag,5	;general error in divide32/x routine
_mflag_6 		=	mflag,6	;not used
_mflag_overflow	=	mflag,7	;overflow occured in add/sub/mult32



_z 		=  	status,2	;I prefer letters to numbers,
_dc  	= 	status,1	; since they are easier to
_c  	= 	status,0	; relate to the function

;END ALIASES ALIASES ALIASES ALIASES ALIASES ALIASES ALIASES ALIASES
;*********************************************************************
;BEGIN TESTING TESTING TESTING TESTING TESTING TESTING TESTING TESTING

;!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
;!!! TEST PROGRAM TO VERIFY MATH ROUTINES !!!
;!!!   USED *ONLY* FOR TESTING PURPOSES   !!!
;!!!   USER SHOULD REMOVE AFTER TESTING   !!!
;!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

	org	0	;Every SX has its prime origin at 0
RESET init
	nop
	nop
	nop		;This nop is required by my ICD1 In Circuit
			;Debugger, so here it is. You may leave it
			;out with impunity if you don't use an ICD1.

	jmp	init	;You have to jump past the interrupt
				;vector at 0004.
				;I usually have an initialization routine that I
				;always	call "init" that I jump to...

	org	4	;Interrupt Service Routine (ISR) vector address.

;this is where vector interrupt would go.
;for testing purposes we do not need an interrupt routine.
;So I am only including a return from interrupt code.

interrupt_service_routine

;*** WARNING: SX saves/restores W, STATUS, and FSR automatically.
	reti	;Even an "empty" isr should have a return from interrupt.
			;Better Safe than Sorry!

	org	$	;It is always good to explicitly declare things
		  	;like the origin... even if not required by law.
		  	;$ means "current program counter value"

init

;!!! This is where I would usually have my initialization
;!!! routine(s) that would set up the hardware such as port
;!!! usage, setting up timers, counters, and all that
;!!! nitty-gritty stuff that you just gotta do.

;!!! since testing of pure software with no hardware requirements
;!!! doesn't use any i/o, and interrupt defaults to it's off state,
;!!! we can skip all the usual init stuff and get right to work.

;Allow Testing of Math Functions HERE.
;This example can be used to test Divide32x
;load <numerator> and <denominator> with 31 bit max size numbers
;(in a 32 bit field, of course)

;Adjust testing routine to test whatever function you want.

	mov	W, #%01000000
	mov	numerator_4, W
	mov	W, #%00000000
	mov	numerator_3, W
	mov	W, #%00000000
	mov	numerator_2, W
	mov	W, #%00000000
	mov	numerator_1, W

	mov	W, #%00000000
	mov	denominator_4, W
	mov	W, #%00000000
	mov	denominator_3, W
	mov	W, #%00000000
	mov	denominator_2, W
	mov	W, #%00000010
	mov	denominator_1, W


	call	divide32x	; answer will be found in <quotient>,

endlessloop
	jmp	endlessloop	;set breakpoint here for testing.

		;endless loop is used for testing only.
		;Once this point is reached the program
		;STAYS here. I usually set a BREAKPOINT
		;in MPLAB at endlessloop when doing testing.

		;Use MPLAB to examine results.
		;Remember that WATCH window in MPLAB can only
		;display PRIMARY RAM variable names, NOT
		;the ALIASED names.
		;For your convenience, here are the ALIASES:
		;<numerator> is <accumulator>
		;<denominator> is <operand>
		;<quotient> is <multiplier>
		;<remainder> is <numerator> is <accumulator>
		;You should also watch mflag for the
		;error bits.

		;The MAX number of cycles to do a complete
		;division in divide32 is about 2,800 cycles.
		;With a 20 Mhz clock this is 560 microseconds.

		;Minimum divide time is about 78 cycles due
		;to short-circuit evaluation of division
		;by 1 (which would otherwise have taken more
		;that 5,000 cycles!)

		;The larger the denominator, the shorter
		;the time it takes to determine the <quotient>.



;!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
;!!!   END OF TEST PROGRAM SECTION   !!!
;!!! REMOVE ONCE TESTING IS FINISHED !!!
;!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

;The following are the actual MATH routines. This is what you will
;eventually end up copying into your own program. But don't forget
;to also copy over the RAM declarations and the Alias Definitions
;and merge them into your own declaration section.

;END TESTING TESTING TESTING TESTING TESTING TESTING TESTING TESTING
;*******************************************************************

;*******************************************************************
;BEGIN MATH MATH MATH MATH MATH MATH MATH MATH MATH MATH MATH MATH

;*******************************************************************
;BEGIN NEG32 NEG32 NEG32 NEG32 NEG32 NEG32 NEG32 NEG32 NEG32 NEG32

;NAME:		neg32

;FUNCTION:	<operand> = negative of <operand>.

;ENTER WITH:	<operand>

;RETURNS:	<operand> = negative of <operand>.

;CHANGED:	<operand> is now negative of original <operand>

;NOTES:		If <operand> comes in positive, it returns negative
;		If <operand> comes in negative, it returns positive
;		Uses twos complement method

;---------------------------------------------------------------
;Twos complement of a number is generated by first complementing
;the number and then adding 1 to the result. It makes a positive
;number negative, and a negative number positive.

neg32	;make twos complement of operand

	not	operand_1	;ones complement of operand:
	not	operand_2	;4 bytes to get 32 bits...
	not	operand_3
	not	operand_4

	inc	operand_1	;twos complement of operand
	sb	Z	;If result is 0 we need ripple carry
	ret	;return if no more carries needed

	inc	operand_2	;perform carry by incrementing
	sb	Z	;If result is 0 we need ripple carry
	ret	;return if no more carries needed

	inc	operand_3	;perform carry by incrementing
	sb	Z	;If result is 0 we need ripple carry
	ret	;return if no more carries needed
	inc	operand_4	;perform carry by incrementing
				;Ignore any carry out from MSB
	ret	;All 4 bytes ripple carried,
				;so return.

;---------------------------------------------------------------
;END NEG32 NEG32 NEG32 NEG32 NEG32 NEG32 NEG32 NEG32 NEG32 NEG32
;***************************************************************

;***************************************************************
;BEGIN LSHIFT32 LSHIFT32 LSHIFT32 LSHIFT32 LSHIFT32 LSHIFT32

;NAME:		lshift32

;FUNCTION:	single shift left of 32 bit <operand> with zero
;		fill at LSB. If overflow of MSB occurs, carry
;		flag is set to 1.
;		This operation effectively multiplies <operand> by 2.
;		<operand> = <operand> * 2

;ENTER WITH:	<operand>.

;RETURNS:	<operand> = <operand> * 2
;		Overflow is returned in carry flag.

;CHANGED:	<operand>

;CALLED BY:	multiply32/divide32

;---------------------------------------------------------------

;Clear Carry and Shift 32 bits in <operand> once to the LEFT.
;	ret

lshift32
	clrb	C	;clear the carry bit to be shifted into LSB.
	rl	operand_1	;_c lshifts into _1. _1 MSB lshifts into _c.
	rl	operand_2	;_c lshifts into _2. _2 MSB lshifts into _c.
	rl	operand_3	;_c lshifts into _3. _3 MSB lshifts into _c.
	rl	operand_4	;_c lshifts into _4. _4 MSB lshifts into _c.
	ret	;return with possible overflow in _c

;END LSHIFT32 LSHIFT32 LSHIFT32 LSHIFT32 LSHIFT32 LSHIFT32
;***************************************************************
;BEGIN ADD32 ADD32 ADD32 ADD32 ADD32 ADD32 ADD32 ADD32 ADD32

;NAME:		add32

;FUNCTION:	<accumulator> = <operand> + <accumulator>.
;		basic addition of positive and negative numbers.

;ENTER WITH:	<operand> and <accumulator> loaded.
;		(Calling program must clear _mflag_overflow)
;		(But only if INTERESTED in the overflow condition)

;RETURNS:	<accumulator> = <accumulator> + <operand>
;		<operand> is unchanged.
;		_mflag_overflow is SET if there is an
;		overflow of the MSB.
;		(Calling program should CLEAR _mflag_overflow to 0)
;		(But only if it is INTERESTED in the
;		overflow condition)


;NOTES:		This routine allows "sequential adds/subtracts"
;		to the accumulator from the <operand> set.
;	example: <accumulator> = (((A + B) + C) + D)
;		also, since result of multiply32 is
;		returned in <accumulator>,
;		you can do things like
;		<accumulator> = (((A * B) + C ) + D)

;		Calling program is responsible for first clearing
;		_mflag_overflow if the overflow detection feature
;		is to be used.
;		(For example, multiply32 routine does
;		this automatically).
;		If you call add32 directly, YOU must
;		clear _mflag_overflow.
;		The same applies if you call subtract32.

;CALLED BY:	subtract32/multiply32/divide32

;---------------------------------------------------------------
;Perform 32 bit add by adding 4 bytes. Implements ripple-carry of bits.

add32
	mov	W, operand_1	;get low part of <operand>
	add	accumulator_1, W	;into w and add to accumulator
	snb	C	;was there a carry?
	call	accumulator_ripple_2	;if so, do ripple carry

	mov	W, operand_2	;get next part of <operand>
	add	accumulator_2, W	;into w and add to accumulator
	snb	C	;was there a carry?
	call	accumulator_ripple_3	;if so, do ripple carry


	mov	W, operand_3	;get next part of <operand>
	add	accumulator_3, W	;into w and add to accumulator
	snb	C	;was there a carry?
	call	accumulator_ripple_4	;if so, do ripple carry

	mov	W, operand_4	;get next part of <operand>
	add	accumulator_4, W	;into w and add to accumulator
	snb	C
	setb	_mflag_overflow	;flag overflow!
	ret

;called ripple-carry functions used by add32.
;Sets _mflag_overflow on overflow of MSB

accumulator_ripple_2		;do ripple carry
	inc	accumulator_2	;via increment
	sb	Z	;if result is NOT zero
	ret	;then ripple carry is done.

accumulator_ripple_3		;otherwise ripply carry next...
	inc	accumulator_3
	sb	Z
	ret	;on non-zero result we are done.

accumulator_ripple_4		;otherwise do last ripple carry...
	inc	accumulator_4
	snb	Z
	setb	_mflag_overflow	;Set _mflag_overflow if accumulator_4
	ret	;wrapped around to zero because of
				;increment. This reports overflow

;END ADD32 ADD32 ADD32 ADD32 ADD32 ADD32 ADD32 ADD32 ADD32 ADD32
;***************************************************************

;***************************************************************
;BEGIN SUBTRACT32 SUBTRACT32 SUBTRACT32 SUBTRACT32 SUBTRACT32


;NAME:		subtract32

;FUNCTION:	<accumulator> = <accumulator> - <operand>.

;ENTER WITH:	<operand> and  <accumulator> loaded.

;RETURNS:	<accumulator> = <accumulator> - <operand>.
;		_mflag_overflow is SET if there is
;		<accumulator> overflow.

;CHANGED:	<operand> is now negative of original <operand>

;NOTES:		divide32 does NOT call this routine

;		This routine allows "sequential adds/subtracts"
;		to the <accumulator> from the <operand> set.
;	example: <accumulator> = (((A + B) - C) + D)
;		also, since result of multiply32 is returned
;		in <accumulator>, you can do things like
;		<accumulator> = (((A * B) - C ) + D)
;		Calling program is responsible for first clearing
;		_mflag_overflow if the overflow detection feature is
;		to be used. (For example, multiply32 routine
;		does this automatically).
;		If you call subtract32 directly, YOU must clear
;		_mflag_overflow. The same applies if you call add32.

;CALLS:		neg32/add32

;---------------------------------------------------------------

subtract32	;subtraction is done via addition of
		;negative number in <operand>

	call	neg32	;create twos complement of operand
	call	add32	;now add negative number to accumulator
	ret	;return
				;(with _mflag_overflow set on overflow).

;END  SUBTRACT32 SUBTRACT32 SUBTRACT32 SUBTRACT32 SUBTRACT32
;***************************************************************

;***************************************************************
;BEGIN MULTIPLY32 MULTIPLY32 MULTIPLY32 MULTIPLY32 MULTIPLY32

;---------------------------------------------------------------
;BEGINNING OF EXPLANATION OF MULTIPLY ALGORITHM

;Multiplication is actually a set of repeated additions. In school
;you were probably taught to multiply the operand (the top number)
;by the multiplier (the bottom number) starting with the rightmost
;digit of the multiplier. Then underneath that result line you wrote
;down a place holding zero and then multiplied the operand by the
;second digit of the multiplier. For the third digit of the multiplier
;you put down two place holding zeros and then multiplied the third
;digit times the operand. You repeated this process for each digit
;in the multiplier. When done, you added up all the result lines to
;obtain the final answer.
;
;When multiplying in binary we make a few simplifications. First, the
;only digits involved are 0 and 1. So, the ONLY possible combinations
;are: 0*0=0  0*1=0  1*0=0  1*1=1  which is all very simple stuff.

;Assume that the first digit is the multiplier digit. You will notice
;that whenever the multiplier is 0 the result is 0. Further,
;whenever the multiplier is 1 the result is the same as the operand.
;SUPER Simple stuff.

;Instead of shifting the result, we can shift the operand. It has the
;same effect, but simplifies things for us. So, when multiplying
;we first shift the operand left once (EXCEPT on the FIRST multiply
;bit!), then, IF the multiplier bit is "1", we ADD the current
;operand to the accumulator. (It is called the accumulator because
;it accumulates the result). By doing the addition immediately we
;simplify the addition of the multiple lines that would normally
;pile up (especially with 32 bit numbers!)

;If the current multiplier bit was a zero we skip the addition part,
;because 0 * anything = 0.

;Once we have done this process for each multiplier bit, we will have
;the product (<multiplier> * <operand>) in the accumulator.

;Note that the largest product you are allowed to generate is 31 bits
;wide. A product's bit width is equal to the sum of the multiplier
;bit width and the operand bit width. If you multiplied a 20 bit
;multiplier times a 15 bit operand you would get a 35 bit product
;which would NOT fit in the alloted 32 bits! By the way, the 31 bit
;limitation is so we can process negative numbers as well as positive
;numbers. If you are only dealing with positive numbers, then you
;can handle full 32 bit numbers.


;END OF EXPLANATION OF MULTIPLY ALGORITHM
;---------------------------------------------------------------

;NAME:		multiply32

;FUNCTION:	<accumulator> = <multiplier> * <operand>

;ENTER WITH:	<multiplier> and <operand> loaded.
;		(<accumulator> is cleared upon entry so there are
;		no suprises). (See note below on multiply32plus if
;		you do NOT want <accumulator> cleared)

;LIMITATIONS:	Largest accumulator and operand value is
;		+/- 2,147,483,647 (31 bits), OR + 4,294,967,295
;		(32 bits) if using unsigned binary numbers.

;		Note that the sum of the bits in multiplier and operand
;		must be 31 or less when using signed math, and 32 or
;		less when using unsigned math. For example,
;		multiplying an 8 bit multiplier times a 30 bit operand
;		would require a 38 bit register set. Since our register
;		sets are fixed at 32 bits, the _flag_overflow bit
;		would be set.

;		If using multiply32plus, you must also ensure that
;		the additionof the entry value in <accumulator>
;		does not cause the final answer to overflow.
;		_flag_overflow will report such errors.

;RETURNS:	<accumulator> =  <multiplier> * <operand>
;		_mflag_overflow is SET if there is <accumulator>
;		overflow.

;CHANGED:	<accumulator> and _mflag_overflow

;TRASHED:	<operand>/<multiplier>

;MULTIPLY32PLUS
;to allow the added functionality of being able to do
;<accumulator2> = <accumulator1> + (<multiplier2> * <operand2>)
;I have included an alternate entry point to the multiply32
;function that does NOT clear the prior contents of the <accumulator>
;before performing the multiplication. This function is called
;multiply32plus. This allows you to effectively ADD the
;multiplication resultto the PREVIOUS contents of the <accumulator>.

;For example:
;<accumulator2> = (<operand1>+<accumulator1>) * <multiplier2>
;We get this "extra" function for free, by simply skipping the first
;part of multiply32 that clears <accumulator>.

;Note that you can also do a multiply32 or multiply32plus and FOLLOW
;it with add32 or subtract32 and only have to enter the <operand>
;for the second operation.

;For example:
;<accumulator2> = (<multiplier1> * <operand1>) + <operand2>

;------------------------------------------------------------
;BEGINNING OF PIC CODE TO IMPLEMENT MULTIPLY32 ALGORITHM



;CALLS:		lshift32/add32

multiply32
	;Entering HERE will give you the simple multiplication function:
	;<accumulator> = <multiplier> * <operand>

	clr	accumulator_4	;Start with a clean <accumulator>
	clr	accumulator_3
	clr	accumulator_2
	clr	accumulator_1	;Now <old accumulator> is all zeros.

multiply32plus
	;Entering HERE will give you the expanded multiplication function:
	;<accumulator2> = <accumulator1> + (<multiplier2> * <operand2>)
	;where <accumulator1> is a value you pre-loaded into
	;the <accumulator>, or the result of a previous function that
	;left a result in the <accumulator>. For example,
	;add32/subtract32/multiply32 all place result in <accumulator>.

	;overflow is indicated by _mflag_overflow being set to 1

	clr	mflag	;clear all math flags
				;(especially _mflag_overflow)
				;flag gets SET in add32 on overflow

	mov	W, #multiplier_1	;SET UP INDIRECT ADDRESSING
	mov	fsr, W	;to handle 4 multiplier bytes

	jmp	skipshift_bit0	;NO shift on bit0 of multiplier,
				;because bit 0 represents
				;multiplication by 1. SPECIAL CASE!

multiply32_loop
				;do 8 bits for EACH multiplier byte,
				;so we handle all 32 bytes eventually.

	call	lshift32	;left shift 32 bit <operand>
				;(with carry in/out at each byte)
				;(except NO initial lshift on
				;multiplier_1,0)
skipshift_bit0
	snb 	indf.0		;handle bit 0 of THIS <multiplier> bit
	call	add32		; if 1 then add to accumulator

	call	lshift32	;lshift 32 bit operand with carry in/out
	snb 	indf.1		;handle bit 1
	call	add32		; if 1 then add to accumulator

	call	lshift32	;lshift 32 bit operand with carry in/out
	snb 	indf.2		;handle bit 2
	call	add32		; if 1 then add to accumulator

	call	lshift32	;lshift 32 bit operand with carry in/out
	snb 	indf.3		;handle bit 3
	call	add32		; if 1 then add to accumulator

	call	lshift32	;lshift 32 bit operand with carry in/out
	snb 	indf.4		;handle bit 4
	call	add32		; if 1 then add to accumulator

	call	lshift32	;lshift 32 bit operand with carry in/out
	snb 	indf.5		;handle bit 5
	call	add32		; if 1 then add to accumulator

	call	lshift32	;lshift 32 bit operand with carry in/out
	snb 	indf.6		;handle bit 6
	call	add32		; if 1 then add to accumulator

	call	lshift32	;lshift 32 bit operand with carry in/out
	snb		indf.7		;handle bit 7
	call	add32		; if 1 then add to accumulator

	dec		fsr			;update fsr to point to next BYTE
	mov		W, --fsr	;need it in w, too for endloop test
;*** WARNING: Manual replacement required for "SUBLW k" instruction (w = k - w). Check if previous instruction is a skip instruction. 
	xor		W, #multiplier_4-1	;done all 4 multiplier bytes?
	sb		Z	; examine _z flag to find out.
	jmp		multiply32_loop	;if not, do next multiplier set

	ret			;when last byte was multiplier_4,
				;we are done! _mflag_overflow
				;reports any overflow.


;END MULTIPLY32 MULTIPLY32 MULTIPLY32 MULTIPLY32 MULTIPLY32
;***********************************************************

;***********************************************************
;BEGIN DIVIDE32 DIVIDE32 DIVIDE32 DIVIDE32 DIVIDE32 DIVIDE32

;-----------------------------------------------------------
;BEGINNING OF VERBOSE DESCRIPTION OF DIVISION ALGORITHM


;Because of the relative complexity of the divide32 routine I am
;first going to run through the basic division algorithm in
;simple English. Then I will present the actual code I devised
;to implement the division algorithm.

;Division is actually a set of repeated subtractions. The denominator
;is subtracted from the numerator. The process can be speeded up
;considerably if we begin by subtracting the BIGGEST binary multiple
;of the denominator possible, and then continue attempting to
;subtract the next biggest binary multiple possible. We repeat
;these actions until the numerator is smaller than the denominator.
;What is left is the remainder.

;In binary math a number can be divided by two simply by shifting
;it to the right once. It can be multiplied by two simply by
;shifting it to the left once.

;The division algorithm that I came up with begins by clearing all
;error flags and clearing the quotient to zero. I then check for
;certain special entry conditions such as entry of negative values
;or values that are 32 bits instead of 31 bit maximum length. I
;also check for division by zero, which is not allowed. If I find
;division by 1 I short circuit the process to speed things up.
;On any error I set a error flags and return with quotient
;holding zero value.

;If there were no input error conditions then we proceed.
;Denominator is made negative (so it can be used to perform
;subtractions)

;I then enter a scanloop that shifts the entire denominator left
;one bit at a time. scancounter keeps track of how many shifts
;were necessary to bring the most significant "0" to bit position 31.

;Upon exit from scanloop, scancounter contains the number of
;passes that were made through scanloop..

;A subtractloop is now entered. At the top of the loop a
;copy of the current numerator is saved in case we subtract when
;we shouldn't. I add the negated form denominator to the
;numerator (which is actually a subtraction). If result
;in numerator goes negative I recover the copy (that undoes
;the subtraction). If subtraction was successful then a "1" is
;placed at scancounter bit of quotient. That is how we generate
;the quotient bit-by-bit. I mentioned the phrase "is placed
;at scancounter bit of quotient." I use the fsr to
;indirectly address the proper byte of the 4 byte (32 bit)
;quotient. The scancounter is used to generate a COMPUTED GOTO
;via a jump table to process the proper byte/bit combination
;of the quotient. Each iteration of the loop I shift the
;denominator to the right and update the scancounter so we "move"
;to the next "bit" to be processed. When scancounter rolls over
;to 0xff we are all done. (rolling over here means zero
;is decremented and the byte value becomed b'11111111' or hex 0xff).


;END OF VERBOSE DESCRIPTION OF DIVISION ALGORITHM
;----------------------------------------------------------
;----------------------------------------------------------
;BEGINNING OF PSEUDO-CODE DESCRIPTION OF DIVISION ALGORITHM

;DIVIDE32
;CALLING PROGRAM details:

;Load 32 bit NUMERATOR into <numerator> set.
;Load 32 bit denominator into <denominator> set.
;	call	divide32
;answer is returned in <quotient> set.
;User can check error flags if necessary.


;DIVIDE32 short form algorithm:
;Clear all error flags.
;Clear quotient.

;If MSB of <numerator> is 1
;	then set negative_derror flag and return (must be positive).
;Endif
;
;Convert <denominator> in operand to negative form and
;keep in <denominator>.
;
;If MSB of <denominator> is 0
;	set error flag and return (div by 0 undefined!).
;	(This also catches attempt to divide by a
;	negative denominator)
;Endif
;
;Clear error flag set.
;
;If <denominator> is 00000000 00000000 00000000 00000001 (1)
;	copy <numerator> to <quotient>
;	clear <numerator> so <remainder> is 0
;	ret
;Endif
;
;Clear <scancounter> (It will hold bit position).
;
;SCANLOOP:
;	If MSB-1 of <denominator>is 0
;		break out of loop and goto SUBTRACTLOOP
;	Endif
;	Increment <scancounter>.
;	clear carry and left-shift <denominator>.
;	jmp	SCANLOOP.
;END SCANLOOP
;
;(We now have MSB-1 of <denominator> aligned so it is largest
;binary multiple of NEGATIVE value of original
;denominator possible). (We want to subtract BIG pieces FIRST!)
;
;SUBTRACTLOOP:
;	Copy <numerator> into <goback>
;	(allows recovery from bad subtraction)
;	Add (negform) <denominator> to <numerator>.
;	(subtract multiple of denominator)
;
;	If MSB of <numerator> is 1, result was negative, so
;		copy <goback> back into <numerator>.
;		(Back where we were).
;	Endif
;
;	If MSB of <numerator> was 0
;		place 1 at <scanpointer> bit of <quotient>.
;		(This records multiple of denominator).
;	Endif
;
;	Then set carry. Shift <denominator> right.
;	(This shifts negative denominator)
;	Decrement <scancounter>.
;	If <scancounter>=0xff (Test scancounter bit 7 for 1)
;		then DONE, so RETURN.
;	Endif
;	jmp	SUBTRACTLOOP
;END SUBTRACTLOOP
;
;
;END OF PSEUDO-CODE DESCRIPTION OF DIVISION ALGORITHM
;-----------------------------------------------------------
;-----------------------------------------------------------


;NAME:		divide32

;FUNCTION:	<quotient> = <numerator> / <denominator>
		;divide32 ONLY handles POSITIVE 31 bit values!

;ENTER WITH:	<numerator> and  <denominator> loaded.
;		BOTH must be POSITIVE. 31 bit max (MSB must be 0)
;		!!!(see divide32x for version that
;		handles +/- numbers)

;RETURNS:	<quotient> = <numerator> / <denominator>
;		remainder is in <remainder>
;		(remainder> is alias for <numerator>)
;		(See ERROR REPORTING for results when an
;		error occurred)
;
;LIMITATIONS:
;		Largest input or result value is +2,147,483,647.
		;They MUST be positive!
		;!!!(see divide32x for extension to divide32
		;that allows negative numbers)
;
;		Since routine uses a form of subtraction,
;		numbers are limited to 31 bits maximum.

;ERROR REPORTING:
;		!!! you can ignore _mflag_overflow! It is never
;		set by divide32. _mflag_derror flags ALL div errors.
;		(Test this flag first). _mflag_dneg is set if negative
;		<numerator> or <denominator> entered._mflag_dzero is
;		set if <denominator> was 0 on entry. On any
;		_mflag_derror, <quotient> returns as 0.

;		On an error, input values MAY be changed.
;		ALWAYS check the _mflag_derror flag. If it is set,
;		then you can check _mflag_dneg and _mflag_dzero to
;		determine the exact kind of error detected.
;

;CHANGED:	<quotient> contains answer.
;		<numerator> contains remainder
;		(numerator is aliased as <remainder> for convenience)
;		mflag bits may have been changed to reflect
;		errors encountered.
;
;TRASHED:	<operand>/<denominator>/<goback>

;ALIASES:	Aliases are used to make routine easier to follow.
;		<denominator> is alias for <operand>
;		<numerator> is alias for <accumulator>
;		<remainder> is also alias for <numerator>/<accumulator>
;		AFTER division.

;CALLS:		add32/lshift32/neg32

		;The MAX number of cycles to do a complete
		;division in divide32 is about 2,800 cycles.
		;With a 20 Mhz clock this is 560 microseconds.

		;Minimum divide time is about 78 cycles due
		;to short-circuit evaluation of division
		;by 1 (which would otherwise have taken more
		;that 5,000 cycles!)

		;The larger the denominator, the shorter
		;the time it takes to determine the <quotient>.


;----------------------------------------------------------------

;BEGINNING OF PIC CODE THAT IMPLEMENTS DIVISION32

;Here begins the actual divide32 for positive unsigned 31 bit values.

divide32

;Clear error flags.

	clr	mflag	;clear ALL math flags.
	setb	_mflag_derror	;assume there will be general_derror...

;Clear <quotient>

	clr	quotient_4	;clear 4 bytes that comprise <quotient>
	clr	quotient_3
	clr	quotient_2
	clr	quotient_1


;If MSB of <numerator> is 1, then set _mflag_dneg and return.
;(numerator> must be positive).

	sb	numerator_4.7	;bit 7 of numerator_4 is MSB of <numerator>
	jmp	testfornegdiv	; if bit was 0 continue to testfornegdiv
	setb	_mflag_dneg	; if bit was 1 then numerator was negative!
	ret	;Report error! _mflag_derror is ALSO set.

testfornegdiv
;If MSB of <denominator> is 1, then set _mflag_dneg and return
;(<denominator> must be positive).

	sb	denominator_4.7	;bit 7 of denominator_4 is MSB
	jmp	chkdivby1	; if bit was 0 continue to negatediv
	setb	_mflag_dneg
	ret	;_mflag_derror is ALSO set.



chkdivby1
	mov	W, denominator_4	;this section short circuits division by 1
	sb	Z
	jmp	negateit
	mov	W, denominator_3
	sb	Z
	jmp	negateit
	mov	W, denominator_2
	sb	Z
	jmp	negateit
	mov	W, denominator_1
;*** WARNING: Manual replacement required for "SUBLW k" instruction (w = k - w). Check if previous instruction is a skip instruction. 
	xor w,	#1
	sb	Z
	jmp	negateit

;if attempting to divide by 1, just copy <numerator> into <quotient>
;and then clear <numerator>, since <numerator> on exit should
;contain the remainder (which in the case of x/1 is always 0)
;This helps speed up division by 1 tremendously.
divby1
	mov	W, numerator_4	;copy numerator into w
	mov	quotient_4, W	;copy w (numerator) into quotient
	clr	numerator_4	;clear numerator (which is now remainder)
	mov	W, numerator_3	;REPEAT for all 4 bytes (32 bits)
	mov	quotient_3, W
	clr	numerator_3
	mov	W, numerator_2
	mov	quotient_2, W
	clr	numerator_2
	mov	W, numerator_1
	mov	quotient_1, W
	clr	numerator_1
	clr	mflag	;this is NOT an error.
	ret	;short-circuit divide by one done. Return.

;Convert <denominator> (in operand) to negative form and
;keep in <denominator>.

negateit
	call	neg32	;negate <denominator>

;Note: the negative of 0 is 0. So, if MSB is 0 after negation, then
;original value was 0. If MSB of <denominator> is 0,
;set _mflag_dzero and return (div by 0 undefined!).

	snb	denominator_4.7	;MSB of <denominator> 0?
	jmp	clear_scan	; if MSB was 1 then all is OK so far...
	setb	_mflag_dzero	; if MSB was 0 it is divide by zero error.
	ret	;_mflag_derror is ALSO set.


;Clear <scancounter> (It will hold bit position).

clear_scan
	clr	mflag
	clr	scancounter	;initialize scancounter.

;SCANLOOP:

scanloop

;If MSB-1 of <denominator>is 0, break out of scanloop.
;(since denominator is now in negative form, first bit that is 0
;indicates that previous bit was last 1 indicating negative value)

	sb	denominator_4.6	;is MSB-1 (still) 1?
	jmp	subtractloop	; if not, we do subtractloop!

;	Increment <scancounter>.

	inc	scancounter	;MSB-1 (still) 1; update scancounter
	clrb	C	;clear carry for left shift
	call	lshift32	;left shift denominator (again).

;	jmp	LOOP.

	jmp	scanloop	;continue scanning until done.


;(We now have MSB-1 of <denominator> aligned so it is largest
;binary multiple of negative value of original denominator possible)
;(We want to subtract BIGGEST pieces FIRST!)

;
;SUBTRACTLOOP:

subtractloop


;Copy <numerator> into <goback> (allows recovery from bad subtraction)
setgoback
	mov	W, numerator_4	;copy <numerator> into <goback>
	mov	goback_4, W

	mov	W, numerator_3
	mov	goback_3, W

	mov	W, numerator_2
	mov	goback_2, W

	mov	W, numerator_1
	mov	goback_1, W

;Add (negform) <denominator> to <numerator>.
;(subtract multiple of denominator)

	call	add32	;effectively "subtract" current
				;denominator multiple from numerator.

;	If MSB of <numerator> is 1, result was negative, so
;		copy <goback> back into <numerator>. (Back where we were).

	sb	numerator_4.7	;If MSB is 1, GOBACK! (undo subtraction!)
	jmp	msbwas0	;otherwise continue...
msbwas1
	mov	W, goback_4	;perform GOBACK.
	mov	numerator_4, W

	mov	W, goback_3
	mov	numerator_3, W

	mov	W, goback_2
	mov	numerator_2, W

	mov	W, goback_1
	mov	numerator_1, W

	jmp	divshift	;if we did GOBACK, then no bit to set.
				;skip to bottom of loop

msbwas0

;	Otherwise, if MSB of <numerator> was 0, place 1 at
;		<scancounter> bit of <quotient>.
;	(This records multiple of denominator).

;	(first determine if quotient_4,_3,_2, or _1. Set fsr accordingly)
;	if scancounter 0 to 7, then quotient_1 is used, etc.

wasquotient_1
	mov	W, #-7			;Load negative 7
	add W, scancounter	;add positive scancounter
						;the end result is scancounter-7
	sb	C				;_c set when scancounter :lte: 7
	jmp	wasquotient_2	;try next
	mov	W, #quotient_1	;it is quotient_1
	jmp	divsetbit		;bits 2,1,0 of scancounter
						;reveal bit position
wasquotient_2
	mov	W, #-15			;Load negative 15
	add	W, scancounter	;add positive scancounter
						;the end result is scancounter-15
	sb	C				;_c set when scancounter :lte: 15
	jmp	wasquotient_3	;try next
	mov	W, #quotient_2	;it is quotient_2
	jmp	divsetbit		;bits 2,1,0 of scancounter
						;reveal bit position
wasquotient_3
	mov	W, #-23			;Load negative 23
	add	W, scancounter	;add positive scancounter
						;the end result is scancounter-23
	sb	C				;_c set when scancounter :lte: 23
	jmp	wasquotient_4	;try next
	mov	W, #quotient_3	;it is quotient_3
	jmp	divsetbit		;bits 2,1,0 of scancounter
						;reveal bit position
wasquotient_4
	mov	W, #quotient_4	;it MUST be quotient_4 if we got here.

split MACRO 
 REPT \0
  expand
  temp = ?\%
  noexpand
  if ?\% == '+'
    expand
    ;add
    noexpand
    ENDIF
  ENDR
 ENDM

split A,+,B,/,2

ListCount_Count = 0
ListCount MACRO 
 ListCount_Count = \0
 ENDM
;ListCount 1,2,3

TblIfAt MACRO inst, addr, table
 noexpand
;This macro takes any instruction, and an address, and a list {table}
;then it expands the instruction (no matter what) and checkes the 
;address against the current program entry. If the table would be
;alligned to the address, then it assembles a jump around the table
;and defines the table.
;See LupW8 for an example of its use.
 IF ($+1) == addr
  ListCount table
  expand
 jmp $ + ListCount_Count + 1
 DW table
  noexpand
  ENDIF
 expand
 inst
 noexpand
 ENDM

;TableIfAt $+1, {1,2}

LupW8 MACRO register, table
; local _LookupWTableBegin ;can't be local if we pass it to other macros.
 noexpand
;Defines an in-line DW/IREAD lookup table up to 8 words long
;returns the 12 bit value indexed by W in M:W.
;must call with table in curly brackets: e.g.
;LupW8 fr, {1, 2, 4, 8, 16, 32, 64, 128}
;Affects M and W.
 ListCount table
 LupW8_TblLen = ListCount_Count
 LupW8_TblBgn = ($ | 7) + 1
 LupW8_reg = register
 TblIfAt {page LupW8_TblBgn+LupW8_TblLen},	LupW8_TblBgn, {table}
 TblIfAt {mov w,LupW8_reg				},	LupW8_TblBgn, {table}
 TblIfAt {and w,#%00000111				},	LupW8_TblBgn, {table}
 TblIfAt {or w,#LupW8_TblBgn			},	LupW8_TblBgn, {table}
 TblIfAt {mov m,#LupW8_TblBgn>>8		},	LupW8_TblBgn, {table}
 TblIfAt {iread							},	LupW8_TblBgn, {table}
 IF LupW8_TblBgn >= $
  expand
 jmp LupW8_TblBgn + ListCount_Count
 org LupW8_TblBgn	;wasted space to align table.
 DW table
  noexpand
  ENDIF
 ENDM


divsetbit
	mov ind, W 				;load lower byte of address plus index
    LupW8 scancounter, {1, 2, 4, 8, 16, 32, 64, 128}
	;look up an appropriate mask to turn on the bit indicated by the 
	;lower 3 bits of scancounter.
	or indf,w	;set that bit in the register 
;	Then set carry. Shift <denominator> right.
;	(This shifts negative denominator)

divshift			;(skip to here on GOBACK)

	setb	C	;set carry and then shift
	rr	denominator_4	;denominator right 4 bytes
	rr	denominator_3
	rr	denominator_2
	rr	denominator_1

;	Decrement <scancounter>.

	dec	scancounter

;	If <scancounter> wrapped to 0xff we are done, so return.

	sb	scancounter.7	;check for bit 7 is adequate.
	jmp	subtractloop	;If not all done, get back to work!
	clrb	_mflag_overflow	;clear any misleading overflow
				;error flag. True overflow in this
				;routine never happens.
				;Calling routine can totally
				;ignore flag.

	ret

;	Otherwise	jmp	SUBTRACTLOOP


;END OF PIC CODE THAT IMPLEMENTS THE DIVISION ALGORITHM
;-------------------------------------------------------

;END DIVIDE32 DIVIDE32 DIVIDE32 DIVIDE32 DIVIDE32 DIVIDE32
;*******************************************************
;*******************************************************
;BEGIN DIVIDE32X DIVIDE32X DIVIDE32X DIVIDE32X DIVIDE32X

;DIVIDE32X:
;This is a routine that allows the use of 31 bit NEGATIVE numbers
;as input and output to the divide32 routine (as well as positive
;31 bit numbers, of course). (31 value bits, 1 sign bit,
;twos complement form).
;
;It first determines what the sign of the quotient should be,
;based on the signs of the <numerator> and <denominator>.
;
;Then it converts any negative inputs to a 31 bit positive
;form. Then it calls the regular divide32 program that only
;handles positive 31 bit numbers, and determines the
;positive-value <quotient>. Then if the <quotient> needs to
;be negative, it replaces <quotient> with the negative of
;the <quotient>. The remainder is returned in <remainder>.
;<remainder> is ALWAYS returned as a positive number.

;If you are absolutely sure that you are using only positive
;<numerator> and <denominator> values, then divide32 is a
;better routine to use. THIS routine has an additional overhead
;associated with it that divide32 does not have.
;This makes divide32 faster.

;In fact, if you ALWAYS deal with division of positive
;numbers, then you can leave this divide32x program out
;entirely and save the code space.

;-----------------------------------------------------------------

;NAME:		divide32x

;FUNCTION:	<quotient> = <numerator> / <denominator>
		;it allows both positive and NEGATIVE input and output!

;ENTER WITH:	<numerator> and  <denominator> loaded.
;		Both must be 32 bit signed numbers
		;(MSB handles sign, which limits VALUE to 31 bits)

;RETURNS:	<quotient> = <numerator> / <denominator>
		;<quotient> is negative when signs require it to be so.
;		remainder is in <remainder> (alias for <numerator>)
		;<remainder> is always in positive form
;		(See ERROR REPORTING for more info)
;
;LIMITATIONS:
;		Largest input or result value is +/- 2,147,483,647.
;
;		Since routine uses a form of subtraction, numbers
;		are limited to 31 bits maximum plus sign bit.

;ERROR REPORTING:
;		!!! you can ignore _mflag_overflow! It is never
;		set by divide32. _mflag_derror is set if ANY error
;		occured. (Test this flag first).
;		_mflag_dzero is set if <denominator> was 0 on entry.
;
;		On any _mflag_derror, <quotient> returns as 0.
;		On an error, input values MAY be changed.
;		You can check the _mflag_derror flag -or- _mflag_dzero
;		to determine if there was a divide by zero error.
;
;		No other types of error are possible, since this routine
;		specifically allows 32 bit SIGNED binary +/- numbers.
;		It is up to the user to enforce entry of numbers in 32
;		bit twos complement notation.
;

;CHANGED:	<quotient> contains answer.
;		<numerator> contains remainder if operation was successful.
;		(numerator is also aliased as <remainder> for convenience)
;		mflag bits may have been changed to reflect
;		errors encountered.
;
;TRASHED:	<operand>/<denominator>/<goback>

;ALIASES:	Aliases are used to make routine easier to follow.
;		<denominator> is alias for <operand>
;		<numerator> is alias for <accumulator>
;		<remainder> is alias for <numerator>/<accumulator>
;		AFTER division.

;CALLS:		add32/lshift32/neg32/divide32
;-----------------------------------------------------------------

divide32x	;eXtended form of divide32 that allows
		;31 bit signed numbers.
		;Largest input or result value is +/- 2,147,483,647.

		;clear isitneg, which is used for polarity
		;determination

	clr	isitneg

negdenominator			;if <denominator> is negative,
	sb	denominator_4.7
	jmp	negnumerator	;(if not negative. skip to next check)
				; increment isitneg
	inc	isitneg
				; negate <denominator>
	call	neg32
				;endif
negnumerator
				;if <numerator> is negative,
	sb	numerator_4.7
	jmp	dodivide32
				; copy <denominator> to <goback>
	mov	W, denominator_4
	mov	goback_4, W
	mov	W, denominator_3
	mov	goback_3, W
	mov	W, denominator_2
	mov	goback_2, W
	mov	W, denominator_1
	mov	goback_1, W
				; copy <numerator> to <denominator>
	mov	W, numerator_4
	mov	denominator_4, W
	mov	W, numerator_3
	mov	denominator_3, W
	mov	W, numerator_2
	mov	denominator_2, W
	mov	W, numerator_1
	mov	denominator_1, W
				; increment isitneg
	inc	isitneg
				; negate <denominator>
	call	neg32
				; copy <denominator> to <numerator>
	mov	W, denominator_4
	mov	numerator_4, W
	mov	W, denominator_3
	mov	numerator_3, W
	mov	W, denominator_2
	mov	numerator_2, W
	mov	W, denominator_1
	mov	numerator_1, W
				; copy <goback> to <denominator>
	mov	W, goback_4
	mov	denominator_4, W
	mov	W, goback_3
	mov	denominator_3, W
	mov	W, goback_2
	mov	denominator_2, W
	mov	W, goback_1
	mov	denominator_1, W
				;endif
dodivide32
;	call	divide32
	call	divide32

				;if isitneg,0 = 1
	sb	isitneg.0
	ret
				; copy <quotient> to <denominator>
	mov	W, quotient_4
	mov	denominator_4, W
	mov	W, quotient_3
	mov	denominator_3, W
	mov	W, quotient_2
	mov	denominator_2, W
	mov	W, quotient_1
	mov	denominator_1, W
				; negate <denominator>
	call	neg32
				; copy <denominator> to <quotient>
	mov	W, denominator_4
	mov	quotient_4, W
	mov	W, denominator_3
	mov	quotient_3, W
	mov	W, denominator_2
	mov	quotient_2, W
	mov	W, denominator_1
	mov	quotient_1, W
			;endif
	ret
;	ret
		;<quotient> is in standard twos complement form.
;	ret
		;(quotient_4,7 will be 1 if <quotient> is negative.)

;END DIVIDE32X DIVIDE32X DIVIDE32X DIVIDE32X DIVIDE32X
;******************************************************

;END MATH MATH MATH MATH MATH MATH MATH MATH MATH MATH
;*****************************************************

	end	;END statement is here so program can be run
		;in stand-alone mode for testing purposes.
		;!!! REMOVE "end" statement when inserting
		;math module into your program


