On Tue, 13 Mar 2001, Nikolai Golovchenko wrote:

> Just thought that once we have only 15 bits in divisor, the routine
> can be optimized quite a bit:

And there's another trick to optimize it further. But before going there,
I have a question. Why do you want to add the divisor (b) to the dividend
(a) when the msb of the dividend is set? In other words, when you shift the
dividend left and the carry get set, then yes, you unconditionally want to
perform the subtraction. However, if the carry doesn't get set then you need to
perform a comparison to see if dividend is less than the divisor. This
comparison can be a subtraction, but if it turns out that the dividend is not
greater than the subtraction has to be restored. Or am I'm missing something?

Let's assume that I don't undertand the algorithm and that what's below is
correct. Here's a cute trick to save a few cycles (I learned this one from Andy
Warren):

>
> ;-----------------------------------------------------------------------------
> ; Input:
> ;  a1:a0 - 10 bit dividend   (a0 - lower byte)
> ;  b1:b0 - 15 bit divisor in 7Q8 format (b1 is integer, b0 is
> ;          fractional)
> ; Output:
> ;  c1:c0 - 15 bit quotient in 7Q8 format
> ;
> ; Temporary:
> ;  count - counter
> ;
> ;-----------------------------------------------------------------------------
> div_uint10_fxp7q8_fxp7q8
>
> ;left align the dividend
> ; (shift accumulator left 1 bit to get the first result bit weight
> ;  equal to 128)
>         clrc
>         rlf     a0, f
>         rlf     a1, f              ;carry is cleared here
> ;initialize registers

Don't need a count register:

;>         movlw 15                   ;15 iterations
;>         movwf count

>         clrf c0                    ;clear result - it will be used
>         clrf c1                    ;to shift zeroes to dividend

          bsf  c1,2   ; use c0:c1 as the counter after 15 shifts, this
                      ; bit will go to the carry.

> div_loop

move the c0:c1<<1 down below
;>         rlf c0, f                  ;shift in next result bit
;>         rlf c1, f

>         rlf a0, f                  ;and shift out next bit of dividend
>         rlf a1, f                  ;to remainder
>
>         movf b0, w                 ;load w with lower divisor byte
>         skpnc                      ;if remainder positive - subtract,
>          goto div_add              ;if negative - add
>         ;subract
>         subwf a0, f
>         movf b1, w
>         skpc
>          incfsz b1, w
>           subwf a1, f
>         goto div_next
> div_add
>         ;add
>         addwf a0, f
>         movf b1, w
>         skpnc
>          incfsz b1, w
>           addwf a1, f
> div_next
> ;here carry has a new result bit

         rlf c0, f                  ;shift in next result bit
         rlf c1, f

Don't need this counter anymore:
>         decfsz count, f
>          goto div_loop

        skpc                      ;did the "count" bit pop out?
         goto  div_loop

        return

don't need this any more:
> ;shift in last result bit
>         rlf c0, f
>         rlf c1, f
>         return
> ;-----------------------------------------------------------------------------


Scott

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics