piclist 2006\08\03\065022a >
Thread: 16 bit Mod 7 Math
techref.massmind.org/techref/microchip/math/index.htm?key=math
BY : Scott Dattalo email (remove spam text)

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

{Quote hidden}

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

bc      Mod7Byte_L2
Mod7Byte_L1:
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
<62424.71.139.28.43.1154585257.squirrel@ruckus.brouhaha.com> 7bit