please dont rip this site

November 2003 MassMind newsletter

Yes, I know I skipped September, it is still in the works but having digital camera issues. I can't seem to get good closeups. Does anyone know how to adapt a macro lens to a Photosmart 435?

A SET OF 32 BIT MATH ROUTINES AND MATH TUTORIAL
For Microcontrollers

Written By
Fr. Thomas McGahee
tom_mcgahee@mailsnare.com

Converted for Ubicom SX by James Newton

Last Updated: April, 2004

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

If you find this tutorial and programs useful, you can let me know by sending an email to: tom_mcgahee at mailsnare,com. If you find a bug, it is the fault of JamesNewton at sxlist.com

Users may modify routines to fit their needs:

Add32/Subtract32/Multiply32 handle both + and -
Divide32 handles only + numbers
Divide32x handles both + and -

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.

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 310^0 which is 31=3. The 2 has a value of 210^1 which is 210=20. The 1 has a value of 110^2 which is 1100=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: 00=0 01=0 10=0 11=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 216+11=43

To avoid confusion, we use base specifiers when dealing with numbers. Let's look at how the base ten number 266 might be shown:

The sum is 256+10=266

By the way, assemblers allow 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:

Although most assemblers allow 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 (256256256256)-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

MULTIPLICATION:

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.

DIVISION:

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).

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.

And so on to the actual code:


;*******************************************************
;*                   FrTOMath32.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              *
;*******************************************************

		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 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 SXKey In Circuit
			;Debugger, so here it is. You may leave it
			;out with impunity if you don't use an SXKey.


	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
		;at endlessloop when doing testing.


		;Use a WATCH to examine results.
		;Remember that WATCH window 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

;---------------------------------------------------------------
;SEE THE EXPLANATION ABOVE:

;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 by James for "SUBLW k" instruction (w = k - w).
	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

;-----------------------------------------------------------
;SEE ABOVE FOR 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 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 by James for "SUBLW k" instruction (w = k - w). 
	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
;*** WARNING: Manual replacement by James for "SUBLW k" instruction (w = k - w). 
	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
;*** WARNING: Manual replacement by James for "SUBLW k" instruction (w = k - w). 
	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
;*** WARNING: Manual replacement by James for "SUBLW k" instruction (w = k - w). 
	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.

;*** WARNING: Manual replacement by James Of the entire table lookup
; And he used some FUNKY macros which will be explained next month.

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





file: /Techref/new/letter/news0311.htm, 69KB, , updated: 2005/2/9 12:48, local time: 2024/12/24 18:18,
TOP NEW HELP FIND: 
3.148.144.139:LOG IN

 ©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?
Please DO link to this page! Digg it! / MAKE!

<A HREF="http://sxlist.com/techref/new/letter/news0311.htm"> November 2003 MassMind newsletter</A>

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type a nice message (short messages are blocked as spam) in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.


Link? Put it here: 
if you want a response, please enter your email address: 
Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
Did you find what you needed?

 

Welcome to sxlist.com!


Site supported by
sales, advertizing,
& kind contributors
just like you!

Please don't rip/copy
(here's why

Copies of the site on CD
are available at minimal cost.
 

Welcome to sxlist.com!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  .