;; ;; stack-math.asm, a PIC 12C509 stack based math package. ;; Copyright (C) 1999, 2000, 2001 James Cameron (quozl@us.netrek.org) ;; ;; This program is free software; you can redistribute it and/or modify ;; it under the terms of the GNU General Public License as published by ;; the Free Software Foundation; either version 2 of the License, or ;; (at your option) any later version. ;; ;; This program is distributed in the hope that it will be useful, ;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;; GNU General Public License for more details. ;; ;; You should have received a copy of the GNU General Public License ;; along with this program; if not, write to the Free Software ;; Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA ;; ;; 1.0 Introduction ;; This file contains addition, subtraction, multiplication ;; and division code for 16-bit signed integers on the PIC 12C509 ;; processor, using a first in last out data stack based on ;; the FSR and INDF registers. It aims for efficiency of file ;; register space rather than code space efficiency. ;; 2.0 The Data Stack Implementation ;; FSR points to the top element in the stack. The stack ;; grows downward in memory addresses, which is the same as ;; upward on paper. The initial value of FSR is set by the main ;; program initialisation, usually to the last free register ;; address plus one. ;; When a 16-bit value is on the stack, it is stored with the ;; most significant byte uppermost, to comply with FORTH ;; standards. ;; 3.0 Comment Formatting Comments ;; Note that there are comments on this code that declare the ;; position of the stack and the current value of the stack ;; pointer. These stack comments are pretty much like the FORTH ;; standard. ;; Example; ( a b -- a+b ) means that the function expects two ;; values on the stack, adds them, and returns with the first ;; value replaced by the answer. The stack will have shrunk. ;; If stack comments contain a ^ character, then this ;; represents the current top of stack. The value immediately to ;; the left of ^ is the one pointed to by FSR. ;; Also, most stack comments are at byte level but some are ;; expressed in terms of 16-bit values. The context should ;; be clear as to which is which. ;; During lengthy FSR manipulations, an alternate commenting ;; strategy has also been used. A comment of "->fred" means that ;; at the end of the instruction the FSR is pointing at the stack ;; contents so named. ;; Each function has a comment block that describes the ;; purpose, effects on the data stack, and effects on the ;; CALL/RETLW stack. The data stack effect may also describe the ;; peak stack consumption. ;; 4.0 Stack Macros ;; The following macros are primitive stack operations. They ;; are used extensively through the code in order to simplify the ;; concepts. The macros build on each other. pushw macro ; push from w to stack decf fsr,f movwf indf endm popw macro ; pop to w from stack movf indf,w incf fsr,f endm pushl macro m_literal ; push literal to stack movlw m_literal pushw endm popl macro ; pop literal (aka drop) from stack incf fsr,f endm pushf macro m_from ; push from file address (uses w) movf m_from,w pushw endm popf macro m_to ; pop to file addresss (uses w) popw movwf m_to endm pushf16 macro m_from ; push 16-bit value pushf m_from pushf m_from+1 endm popf16 macro m_to ; pop 16-bit value popf m_to+1 popf m_to endm pushl16 macro m_literal ; push literal to stack pushl low(literal) pushl high(literal) endm popl16 macro ; pop literal (aka 2drop) popl popl endm ;; 5.0 Static Register Allocation ;; The math functions have the right to use two general ;; purpose registers in order to simplify the stack manipulation ;; logic. However, not all of them do this. Some code could be ;; reduced if they did, but when I was writing them the whole ;; point was to achieve zero usage of non-stack registers. cblock r_ephemeral r_temporary endc ;; 6.0 Vector Table ;; Since the 12C509 cannot CALL to an address in the upper ;; half of each code page, a vector table is required in low ;; memory. This is included here. sb_add goto sb_add_ sb_subtract goto sb_subtract_ sb_abs goto sb_abs_ sb_negate goto sb_negate_ sb_nip goto sb_nip_ sb_over goto sb_over_ sb_multiply goto sb_multiply_ sb_divide goto sb_divide_ ;; 7.0 Math Functions ;;; ;;; sb_add, sixteen bit addition ;;; ;;; data stack: ( a b -- a+b ) [total 4] ;;; stack: none ;;; sb_add_ ; ( lsb1 msb1 lsb2 msb2 -- lsb3 msb3 ) movf indf,w ; msb2 incf fsr,f ; ( lsb1 msb1 lsb2 ^ msb2 ) incf fsr,f ; ( lsb1 msb1 ^ lsb2 msb2 ) addwf indf,f ; msb3 = msb1 + msb2 decf fsr,f ; ( lsb1 msb3 lsb2 ^ msb2 ) movf indf,w ; lsb2 incf fsr,f ; ( lsb1 msb3 ^ lsb2 msb2 ) incf fsr,f ; ( lsb1 ^ msb3 lsb2 msb2 ) addwf indf,f ; lsb3 = lsb1 + lsb2 decf fsr,f ; ( lsb3 msb3 ^ lsb2 msb2 ) btfsc status,c ; carry? incf indf,f ; msb3 retlw 0 ; ( lsb3 msb3 ) ;;; ;;; sb_subtract, sixteen bit subtraction ;;; ;;; data stack: ( a b -- a-b ) [total 4] ;;; stack: none ;;; sb_subtract_ ; ( lsb1 msb1 lsb2 msb2 -- lsb3 msb3 ) movf indf,w ; msb2 incf fsr,f ; ( lsb1 msb1 lsb2 ^ msb2 ) incf fsr,f ; ( lsb1 msb1 ^ lsb2 msb2 ) subwf indf,f ; msb3 = msb1 - msb2 decf fsr,f ; ( lsb1 msb3 lsb2 ^ msb2 ) movf indf,w ; lsb2 incf fsr,f ; ( lsb1 msb3 ^ lsb2 msb2 ) incf fsr,f ; ( lsb1 ^ msb3 lsb2 msb2 ) subwf indf,f ; lsb3 = lsb1 - lsb2 decf fsr,f ; ( lsb3 msb3 ^ lsb2 msb2 ) btfss status,c ; underflow? decf indf,f ; msb3 retlw 0 ;;; ;;; sb_abs, sixteen bit absolute value ;;; ;;; data stack: ( a -- |a| ) [total 2] ;;; stack: none ;;; sb_abs_ btfss indf,7 ; is it negative? retlw 0 ; no, so return ; fall through to negate ;;; ;;; sb_negate, sixteen bit negate ;;; ;;; data stack: ( a -- 0-a ) [total 2] ;;; stack: none ;;; sb_negate_ ; ( lsb msb -- lsb msb ) incf fsr,f ; ( lsb ^ msb ) comf indf,f ; lsb incf indf,f ; lsb decfsz fsr,f ; ( lsb msb ^ ) nop ; [decrement without losing z] btfsc status,z decf indf,f ; msb comf indf,f ; msb retlw 0 ; ( lsb msb ) ;;; ;;; sb_nip, sixteen bit nip, remove item under current item ;;; ;;; data stack: ( x y -- y ) [total 4] ;;; stack: none ;;; sb_nip_ ; ( a b c d -- c d ) movf indf,w ; d @ incf fsr,f ; ->c incf fsr,f ; ->b movwf indf ; b ! decf fsr,f ; ->c movf indf,w ; c @ incf fsr,f ; ->b incf fsr,f ; ->a movwf indf ; a ! decf fsr,f ; ->b retlw 0 ;;; ;;; sb_over, sixteen bit over, copy item under current item ;;; ;;; data stack: ( x y -- x y x ) [total 6] ;;; stack: none ;;; sb_over_ ; ( a b c d -- a b c d a b ) incf fsr,f ; ( a b c ^ d ) incf fsr,f ; ( a b ^ c d ) incf fsr,f ; ( a ^ b c d ) movf indf,w ; a decf fsr,f ; ( a b ^ c d ) decf fsr,f ; ( a b c ^ d ) decf fsr,f ; ( a b c d ^ ) decf fsr,f ; ( a b c d ? ^ ) movwf indf ; a incf fsr,f ; ( a b c d ^ a ) incf fsr,f ; ( a b c ^ d a ) incf fsr,f ; ( a b ^ c d a ) movf indf,w ; b decf fsr,f ; ( a b c ^ d a ) decf fsr,f ; ( a b c d ^ a ) decf fsr,f ; ( a b c d a ^ ) decf fsr,f ; ( a b c d a ? ^ ) movwf indf ; b retlw 0 ;;; ;;; sb_multiply, sixteen bit multiply ;;; ;;; data stack: ( multiplicand multiplier -- product ) [total 7] ;;; stack: calls others that do not call ;;; sb_multiply_ ; ( al ah bl bh -- cl ch ) pushl16 d'0' ; clear product ;; ( al ah bl bh cl ch ) pushl d'16' ; count of bits to process ;; ( al ah bl bh cl ch count ) sb_multiply_loop ; for each bit ;; ( al ah bl bh cl ch count ) ;; shift multiplier down by one movlw 5 addwf fsr,f ; ->ah rrf indf,f incf fsr,f ; ->al rrf indf,f decf fsr,f ; ->ah decf fsr,f ; ->bl ;; ( al ah bl ^ bh cl ch count ) ;; if the bit is set ... btfss status,c goto sb_multiply_skip ;; add the multiplicand to the product decf fsr,f ; ->bh movf indf,w decf fsr,f ; ->cl decf fsr,f ; ->ch addwf indf,f movlw 3 addwf fsr,f ; ->bl movf indf,w decf fsr,f ; ->bh decf fsr,f ; ->cl addwf indf,f decf fsr,f ; ->ch btfsc status,c incf indf,f movlw 3 addwf fsr,f ; ->bl sb_multiply_skip ;; ( al ah bl ^ bh cl ch count ) ;; shift up multiplicand bcf status,c rlf indf,f decf fsr,f ; ->bh rlf indf,f ;; ( al ah bl bh ^ cl ch count ) ;; and loop for remainder of bits movlw 3 subwf fsr,f ; ->count decfsz indf,f goto sb_multiply_loop ;; ( al ah bl bh cl ch count ) popl ; count call sb_nip ; bl bh goto sb_nip ; al ah ;;; ;;; sb_divide, sixteen bit divide ;;; ;;; data stack: ( numerator denominator -- remainder quotient ) [total 10] ;;; stack: calls others that do not call ;;; sb_divide_ ;; ( nl nh dl dh -- rl rh ql qh ) ;; prepare stack for results ;; ( nl nh dl dh ) call sb_over ;; ( nl nh dl dh nl nh ) call sb_over ;; ( nl nh dl dh nl nh dl dh ) ;; ( rl rh ql qh nl nh dl dh ) movlw d'4' addwf fsr,f ; ->qh clrf indf ; qh incf fsr,f ; ->ql clrf indf ; ql incf fsr,f ; ->rh clrf indf ; rh incf fsr,f ; ->rl clrf indf ; rl movlw d'7' subwf fsr,f ; ->dh ;; ( rl rh ql qh nl nh dl dh ) ;; save effective sign difference ;; sign = xor(nh,dh) ;; ( nl nh dl dh ) movf indf,w ; dh incf fsr,f ; incf fsr,f ; ->nh xorwf indf,w ; nh decf fsr,f ; decf fsr,f ; ->dh pushw ;; ( nl nh dl dh sign ) ;; force arguments to positive ;; n = abs (n) ;; ( nl nh dl dh sign ) movlw d'3' addwf fsr,f ; ->nh call sb_abs decf fsr,f ; ->dl decf fsr,f ; ->dh ;; d = abs (d) ;; ( nl nh dl dh ^ sign ) call sb_abs decf fsr,f ; ->sign ;; set the bit counter pushl d'16' ; for 16 shifts ;; ( nl nh dl dh sign count ) ;; ( rl rh ql qh nl nh dl dh sign count ) sb_divide_loop ;; ( rl rh ql qh nl nh dl dh sign count ) ;; shift bits left from numerator to remainder movlw d'5' addwf fsr,f ; ->nl bcf status,c ; clear status.c rlf indf,f ; nl decf fsr,f ; ->nh rlf indf,f ; nh incf fsr,f ; (must keep status.c) incf fsr,f ; incf fsr,f ; incf fsr,f ; incf fsr,f ; ->rl rlf indf,f ; rl decf fsr,f ; ->rh rlf indf,f ; rh ;; ( rl rh ^ ql qh nl nh dl dh sign count ) ;; check if remainder is greater than denominator movlw d'6' subwf fsr,f ; ->dh movf indf,w ; dh movwf r_ephemeral movlw d'6' addwf fsr,f ; ->rh movf r_ephemeral,w subwf indf,w ; rh btfss status,z goto sb_divide_skip_1 ;; ( rl rh ^ ql qh nl nh dl dh sign count ) ;; msb equal, so check lsb movlw d'5' subwf fsr,f ; ->dl movf indf,w ; dl movwf r_ephemeral movlw d'6' addwf fsr,f ; ->rl movf r_ephemeral,w subwf indf,w ; rl decf fsr,f ; ->rh ;; ( rl rh ^ ql qh nl nh dl dh sign count ) sb_divide_skip_1 btfss status,c goto sb_divide_skip_2 ; remainder is less ;; ( rl rh ^ ql qh nl nh dl dh sign count ) ;; carry set, remainder is greater than denominator ;; subtract denominator from remainder and save in remainder movlw d'5' subwf fsr,f ; ->dl movf indf,w ; dl movwf r_ephemeral movlw d'6' addwf fsr,f ; ->rl movf r_ephemeral,w subwf indf,f ; rl decf fsr,f ; ->rh btfss status,c decf indf,f ; rh movlw d'6' subwf fsr,f ; ->dh movf indf,w ; dh movwf r_ephemeral movlw d'6' addwf fsr,f ; ->rh movf r_ephemeral,w subwf indf,f ; rh bsf status,c ; shift a 1 into quotient ;; ( rl rh ^ ql qh nl nh dl dh sign count ) sb_divide_skip_2 ;; shift the quotient left decf fsr,f ; ->ql rlf indf,f ; ql decf fsr,f ; ->qh rlf indf,f ; qh ;; loop until all bits checked movlw d'6' subwf fsr,f ; ->count decfsz indf,f ; count goto sb_divide_loop popl ; drop count ;; ( rl rh ql qh nl nh dl dh sign ) ;; adjust stack popf r_ephemeral movlw d'4' addwf fsr,f ; drop nl nh dl dh ;; ( rl rh ql qh ) ;; check effective sign difference and adjust quotient btfss r_ephemeral,7 retlw 0 ; signs were same ;; signs different, negate quotient goto sb_negate ;; end of stack-math.asm