; maxsum.asm				Celio Guimaraes	15 Nov 2001
;	Given a vector of random signed 8 bit inegers,
;	obtain a subvector of consecutive elements whose sum is maximum;
;	translated to PIC assembly language from the following
;	linear time algorithm, written in C:
;int main() 
;{ 
; int i,j,start,end,csum,maxsum; 
; char tab[TMAX]; 
; rand8(tab,TMAX);   /*initialize vector with random signed 8 bit integers*/ 
; csum=maxsum=start=0; end=-1; 
; for (i=0, j=0; j < TMAX; j++){ 
;   csum= csum + tab[j]; 
;   if (csum> maxsum){ 
;   maxsum=csum; 
;   start= i; 
;   end=j; 
;   }else if (csum < 0){ 
; 	i= j+1; 
; 	csum=0; 
;   } 
;} 

	list      p=16F84	   ; list directive to define processor
	errorlevel 1, -305   ; suppress message that takes f as default destination operand
#include <mymacros.inc>	   ; macros mov, movl, add, sub, decbnz
TMAX	equ	d'16'	   ; 0< TMAX <= 256
PCL		equ 02
STATUS	equ 3
CY		equ 0
Z		equ 2
PCLATH	equ 0xA
#define ch csumh		   ; just to use shorter names in cmpcsummaxsum
#define cl csuml
#define dh maxsumh
#define dl maxsuml
	
 cblock 0x10
   i,j,start,endv,csumh,csuml,maxsumh,maxsuml,htab,wsave
 endc
 
 ORG 0x0000
	goto init
sum:				; computes csum + tab[j] => csum (with 16 bit precision) 
 	clrf	htab		; use htab to extend tab[j] to a signed 16 bit value
 	mov j,w
 	call tab		; will return with "tab[j]" in W
 	mov	w,wsave	; save it
 	rlf	wsave,w		; tab[j] < 0?
 	btfsc	STATUS, CY
 	decf	htab		; yes, extend sign bit thru htab
 	mov	wsave, w	; put back in W
 	add	csuml,f	; tab[j] + csuml => csuml, may have Carry,
 	btfsc	STATUS,CY 	; if we had a Carry from previous sum,
 	incf	htab		; add it to most significant byte (htab)
 	mov	htab,w	; prepare most significant byte
 	add	csumh,f	; add it to csumh (if there is a Cy we are in trouble!)
	return

cmpcsummaxsum:		; compares two 16 bit signed integers c and d,
				; where d is always >=0 !
				; if c > d return 1
				; if c = d return 0
				; if c < d return -1
				; c=(ch, cl) d=(dh, dl)
	rlf ch,w		; c < 0?
	bc 	less		; yes, return -1
	mov	dh,w		; no,
	sub	ch,w		; ch - dh; don't change ch!
	bz	tzero		; can not be made before next test!(see PIC manual)
	bnc	less		; that's how two's complement subtraction works!
	retlw	1		; c > d
tzero:			; ch=dh here; now compare least significant bytes
	mov	dl,w
	sub	cl,w		; cl - dl
	btfsc STATUS,Z	; if Zero
	retlw	0		; cl = dl, return 0
	bnc		less	; else, if no CY, c < d return -1
	retlw	1		; c > d

less:
	retlw	-1		; c < d

;***** end of subroutines ********************************************* 

init:
    	movlw HIGH (tab+1); get most significant address bits of tab+1
    	mov w, PCLATH	; move to SFR PCLATH, to use later in call to tab
	clrf i		; 0=>i
 	clrf j		; 0 => j
 	clrf start		; 0 => start	
 	clrf endv		
 	decf endv		; -1 => end
 	clrf csumh
 	clrf csuml		; 0 => csum
 	clrf maxsumh
 	clrf maxsuml	; 0 => maxsum
 	goto	firsttime	; trick to allow a 256 entry table
loop:
  	mov j, w		
  	sublw	TMAX		; TMAX = j ?
  	bz done		; yes, done 
firsttime:
  	call sum		; compute csum + tab[j] => csum
  	call cmpcsummaxsum ; compare csum with maxsum, result in W
  	sublw	1		; if 1
  	bz	csumgtmaxsum; then csum > maxsum
  	rlf	csumh,w	;else, check csumh most significant bit
  	bnc	continue	; csum >=0, continue with next j
csumlt0:			; csum < 0 here
	incf j,w		; j+1 => w
	mov	w,i		; j+1 => i
	clrf	csumh
	clrf	csuml		; 0 => csum
    b	continue
csumgtmaxsum:		; csum > maxsum here
  	mov	csumh, maxsumh
 	mov	csuml,maxsuml	; csum => maxsum
  	mov	i,start		; i => start
  	mov	j, endv		; j => endv
continue:
  	incf j			; j+1 => j
  	b	loop
done: 	
  		sleep
 org 0xFF			; our first table entry will be on a page boundary (100h)
tab:				; implements a table of constants via a "jump table"
	addwf	PCL		; adds W to PCL,  moves (PCL,PCLATH) to PC!
	retlw	-d'58'	; if W is 0 return -58
	retlw	-d'18'	; W= 1, return -18 
	retlw	-d'90'	; and so on...
	retlw	-d'93'
	retlw	d'104'
	retlw	d'75'
	retlw	-d'10'
	retlw	-d'98'
	retlw	d'51'
	retlw	d'66'
	retlw	d'14'
	retlw	d'50'
	retlw	d'02'
	retlw	-d'02'
	retlw	-d'104'
	retlw	d'102'
			; for this table one should get the results:
			; start=04 endv=0C maxsum=00FE
	END