Scott Dattalo <PICLIST@MITVMA.MIT.EDU> wrote:

> Here's the code that will do it.
>
> DIVBY3: CLRF    t1         ;Temporary variable to keep track of
>                            ;the sum of digits
> a1      MOVF    test,W     ;Get the test pattern
>         SKPNZ              ;If it is zero, then all bits have
>         goto  a2           ; been shifted out
>
>         ANDLW   3          ;Get the two lsb's
>         ADDWF   t1,F       ;Sum of digits  (note C=0 after this
>                            ;inst)
>         RRF     test,F     ;Get rid of the two lsb's: first one
>         CLRC               ;CYA
>         RRF     test,F     ;                          second one
>         goto    a1         ;See if there are any more bits
>
> a2      MOVF    t1,W       ;Get the sum of digits
>         MOVWF   test       ;Save in case we have to loop some more
>         ANDLW   0xfc       ;Is the sum >= 4? SKPZ
>         goto    DIVBY3     ;Yes, loop some more
>
>         RRF     test,W     ;Move b1 to b0
>         XORWF   test,F     ;b0 = b0 ^ b1
>         BTFSC   test,0     ;If b0 is set then sum of digits is 01b
>                            ;or 10b
>         RETLW 0            ;Not divisble by three
>         RETLW   1          ;Sum of digits is either 00b or 11b
>                            ;note that 00b is possible only if test
>                            ;equal zero upon entry.
>
> Best case execution is 15 cycles, worst case is 71. I don't know the
> average. It doesn't beat Andy's original posting in either
> performance or code length, but it is a slightly different
> implementation.
>
> Guess we'll have to split a lite Beer, Erik.

Scott:

Yeah, I guess so, unless someone comes up with an even better way.

Here's a faster implementation of the "Erik & Scott" algorithm:

    DIVBY3: MOVF    TEST,W
            ANDLW   00110011B
            MOVWF   T1

            RRF     TEST
            RRF     TEST,W
            ANDLW   00110011B
            ADDWF   T1

            SWAPF   T1,W
            ADDWF   T1,W

            ANDLW   00001111B

            SKPNZ
            RETLW   1

            XORLW   3
            SKPNZ
            RETLW   1

            XORLW   6^3
            SKPNZ
            RETLW   1

            XORLW   9^6
            SKPNZ
            RETLW   1

            XORLW   12^9
            SKPNZ
            RETLW   1

            RETLW   0

This code executes in 13-26 cycles, significantly faster than the
code I originally posted.  I haven't profiled it to see what the
average execution time is, or whether that average can be lowered by
rearranging the order of the final XORLWs (it probably can).

If the above code is rewritten using a table, it takes even less
code space AND it executes faster... Only 14 cycles per input:

    DIVBY3: MOVF    TEST,W
            ANDLW   00110011B
            MOVWF   T1

            RRF     TEST
            RRF     TEST,W
            ANDLW   00110011B
            ADDWF   T1

            SWAPF   T1,W
            ADDWF   T1,W

            ANDLW   00001111B

            ADDWF       PC

            RETLW   1
            RETLW   0
            RETLW   0
            RETLW   1
            RETLW   0
            RETLW   0
            RETLW   1
            RETLW   0
            RETLW   0
            RETLW   1
            RETLW   0
            RETLW   0
            RETLW   1

Can anyone do better than THIS?

-Andy

P.S.  The above code was written on-line... I haven't tested it yet,
      so if you find any errors, please let me know.

Andrew Warren - fastfwd@ix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499