On Sun, 28 Dec 1997 09:24:30 -0600 John Payson <supercat@MCS.NET> writes:

>> Another variant.
>>
>>         movfw   scanbit
>>         addwf   scanbit,f
>>         skpnz
>>         bsf     scanbit,0
>>
>Hmm... this has the same problem that the first four-cycler given
>before
>had: if scanbit holds something other than a power of two, running the
>routine repeatedly won't fix that.

This version should work.  Adding a number to itself is exactly the same
as shifting it left 1 bit and putting a 0 into the LSB (The AVR's 'shift
left' instruction is actually an add to itself, though shifting to the
right is apparently done with a dedicated unit.).  After 8 or fewer such
operations, any initial value is certain to become 0, at which time the
BSF is executed to reset the value to 00000001.

Note this will not work with a RLF instruction because RLF doesn't affect
the Z flag (as well as requiring the proper initial value in C).

A somewhat faster recovery may be possible by additionally testing for
the first 1 bit to come out:

        movfw   scanbit
        addwf   scanbit,f       ;Shift 'scanbit' left 1.
        skpnc
        clrf    scanbit         ;Immediately go to 0 if 1 came
out.
        skpnz                   ;If result 00000000,
        bsf     scanbit,0       ; restart to 00000001

The C test can't be used alone because then it won't detect if the value
was 0 at first.  The BSF always executes if the CLRF did because CLRF
always sets the Z bit.

I think the worst-case recovery for this routine is if scanbit is
00000011, in which case 7 iterations would be required to get a valid
value.  So the extra 2 instructions aren't worth that much.

What's the best way to guarantee a valid output with only one execution
of the update routine?  Maybe changing the whole approach to use a
counter that counts from 0 to 7, then generating ths scan mask from it
(Most likely any real application will require both a count and a mask
anyway).  The counter can be guaranteed valid just by ANDing it with 7.

Or some method that finds the first '1' bit in the result and sets the
other 7 bits all to 0?

It appears that XORing n with n-1 produces a result having zeros on the
left and at least 1 one on the right.  The position of the rightmost 0 in
the result is one left of the position of the rightmost 1 in n.

Now take these results (r) and convert them to a form having one 1 and 7
zeros with z = (((r << 1)+1) ^ r).  The special case of r = 11111111
(actually can test 1XXXXXXX since we know all the LSBs will be 1 anyway)
needs to generate z = 00000001.

    n        n-1         r         z
00001100, 00001011 -> 00000111 -> 00001000
00001101, 00001100 -> 00000001 -> 00000010
00000000, 11111111 -> 11111111 -> 00000001 *
11111111, 11111110 -> 00000001 -> 00000010
00010000, 00001111 -> 00011111 -> 00100000
10000000, 01111111 -> 11111111 -> 00000001 *
10001000, 10000111 -> 00001111 -> 00010000
etc.

Writing this in PIC code:
        decf    scanbit,w
        xorwf   scanbit,w       ;W = r.
        movwf   tmp             ;Prepare to compute z.
        rlf     tmp,f
        bsf     tmp,0           ;tmp = r<<1 + 1
        xorwf   tmp,w           ;W = z (exc. special case)
        skpnz                   ;z is OK.
        movlw   1               ;Special case resulting if r = 0xFF
        movwf   scanbit         ;New scan mask, guaranteed
legal.

Obscure? Yes.  Useful?  Maybe.  Functional?  Not sure.