On Wed, 2006-08-02 at 13:35 -0700, Brooke Clarke wrote:

> In order to calculate the Zeller Congruence the math needs to be 16 bit
> to handle the 4 digit Year so the Modulo 7 calculation needs to start
> with a two byte unsigned integer and output 0 to 6, but so far it's
> escaped me how to calculate it and there's not even a mention of modulo
> calculations on the piclist.com source code pages.  The start of the
> loop may be something like:
>
>     movlw    7 ; addwf with a -7 does not work
> Mod7_Loop
>     subwf    Z_DowLo,F
>     btfsc    STATUS,C    ; for subtraction the sense of carry is inverted
>     goto Mod7_Loop ; keep subtracting 7 until there's a carry
>
> but the next part has me stumped.


Maybe a better way to think about the problem is in terms of number
bases and modulo arithmetic. For example, your goal is to compute DOW
mod 7 where DOW is the 16-bit representation of the day of the
week. You can write this as:

  DOW = DOW_HI*256 + DOW_LO

  DOW%7 = (DOW_HI*256 + DOW_LO) % 7
        = ((DOW_HI*256)%7  + (DOW_LO % 7)) %7
        = ((DOW_HI%7 * 256%7)  + (DOW_LO%7)) %7
        = ((DOW_HI%7 * 4)  + (DOW_LO%7)) %7

Expressed in this manner, you can separately compute the modulo 7
result for the high and low bytes. Multiply the result for the high by
4 and add it to the low and then finally compute result modulo 7.

Computing the mod 7 result of an 8-bit number can be performed in a
similar fashion. You can write an 8-bit number in octal like so:

   X = a*64 + b*8 + c

Where a, b, and c are 3-bit numbers.

   X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
       = (a%7 + b%7 + c%7) % 7
       = (a + b + c) % 7

since 64%7 = 8%7 = 1

Of course, a, b, and c are

   c = X & 7
   b = (X>>3) & 7
   a = (X>>6) & 7  (actually, a is only 2-bits).

The largest possible value for a+b+c is 7+7+3 = 17. So, you'll need
one more octal step. The complete (untested) C version could be
written like:

unsigned char Mod7Byte(unsigned char X)
{
  X = (X&7) + ((X>>3)&7) + (X>>6);
  X = (X&7) + (X>>3);

  return X==7 ? 0 : X;
}

I spent a few moments writing a PIC version. The actual implementation
is slightly different than described above



Mod7Byte:
	movwf	temp1	;
	andlw	7	;W=c
	movwf	temp2	;temp2=c
	rlncf   temp1,F	;
	swapf	temp1,W ;W= a*8+b
	andlw   0x1F
	addwf	temp2,W ;W= a*8+b+c
	movwf	temp2   ;temp2 is now a 6-bit number
	andlw   0x38    ;get the high 3 bits == a'
	xorwf	temp2,F ;temp2 now has the 3 low bits == b'
	rlncf   WREG,F  ;shift the high bits right 4
	swapf   WREG,F  ;
	addwf	temp2,W ;W = a' + b'

  ; at this point, W is between 0 and 10


	addlw	-7
	bc      Mod7Byte_L2
Mod7Byte_L1:
	addlw	7
Mod7Byte_L2:
	return



Here's a liitle routine to test the algorithm


        clrf    x
        clrf    count

TestLoop:
	movf	x,W
	RCALL   Mod7Byte
	cpfseq count
         bra    fail

	incf	count,W
	xorlw   7
	skpz
         xorlw	7
	movwf   count

	incfsz	x,F
	bra	TestLoop
passed:


Finally, for the 16-bit result (which I have not tested), you could
write:

uint16 Mod7Word(uint16 X)
{
  return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}


Scott
-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist