Subject: Divide instruction.

From: Charles Esson <[email-masked]>
Date: Wed, 25 Jun 1997 09:22:13 +1000

I am in trouble the strong arm is getting canned because of the lack of
a divide ( well I can't find it anyway) and the best I can do is 96
instructions. 

Has anyone done better.

---

From: Phil Norman <[email-masked]>
Date: Wed, 25 Jun 1997 13:37:31 +0100 (BST)

> a divide ( well I can't find it anyway) and the best I can do is 96

I think so.  I posted a fast ARM assembler DIV routine (also does MOD as 
a side-effect) to c.s.a.programmer a while back.  I'm afraid I can't find 
it in my sent-mail - dunno what pine did to it - but I will get a copy of 
it next time I'm home and will post it here when I'm next in the computer 
lab.  It does about 1,000,000,000,000 (1<<40 to be exact) DIVs in about 
1.41s on a StrongARM at 202MHz.

See ya,
Phil

-- 

=============================================
= Phil Norman  -  [email-masked] =
= http://newton.ex.ac.uk/general/ug/norman  =
=    Acorn fanatic and physics student      =
=============================================

---

From: Andy Armstrong <[email-masked]>
Date: Wed, 25 Jun 1997 13:12:08 +0100

In article <[email-masked]>, Charles Esson
<[email-masked]> writes
>a divide ( well I can't find it anyway) and the best I can do is 96

96! :-)

Have a look at ARM's web site (www.arm.com). I'm sure they have some
quite snappy divide routines there.

-- 
http://www.wonderworks.co.uk --> Free RISC OS software
Andy Armstrong, WonderWorks

---

From: Matthew Wilcox <[email-masked]>
Date: Wed, 25 Jun 1997 14:08:15 +0100 (BST)

> a divide ( well I can't find it anyway) and the best I can do is 96

Yes.  For all your arm code needs..
http://www.comlab.ox.ac.uk/oucl/users/robin.watts/Docs/

---

From: Phil Norman <[email-masked]>
Date: Wed, 25 Jun 1997 17:08:23 +0100 (BST)

> a divide ( well I can't find it anyway) and the best I can do is 96

I posted just a few hours ago about a DIV routine I've done.  I'm back in 
the computer lab now, so here it is.  This is exactly the posting I sent 
to c.s.a.programmer.

The reason I couldn't find it in my sent-mail in pine was because I sent 
it from home while dialing up :-)

Hope it's useful.

Hello!

While writing the slider bar for my (soon to be released) music CD application,
Duet, I found need of an integer division routine.  Since Duet is written
entirely in ARM assembler, and I was far from any internet connection, I had to
write my own.

I haven't speed tested it, but I think it's fairly optimal.  I'm posting it
firstly in case anyone wants to use it, and secondly in case anyone knows of a
faster routine.  If you do, please let me know about it.  By the way, I think
the FPE is probably the type of thing where the new StrongARM instruction, MULL
IIRC, could be used to speed things up a bit.  Is anyone planning a Strong-ARM
optimised FPE?

Here's the code...

Actually, just now I realised how it could be further optimised.  I've put the
extra bit of code in, tested it, and found that on my StrongARM, the time taken
for (1<<40) divisions, (1<<20) each of each of the numbers from (1<<20) to 0,
was 313cs for the first version, and 141cs for the second, improved version.

;******************************************************************************
.Divide
; Phil's Astounding Divider.  Integer division routine, slightly optimised
; for StrongARM (but there wasn't much space for optimisation).
; If you wish this routine to return the remainder too, just don't bother to
; preserve r2 on the stack - it will return as the remainder.
; On entry:
;       r2  =   Numerator
;       r3  =   Denominator
; On exit:
;       r0  =   Result
; During routine:
;       r0  =   Result build-up
;       r1  =   Accumulator
;       r2  =   Numerator (continuously lowered)
;       r3  =   Denominator (const)
;       r14 =   Shift counter
;==============================================================================
        STMFD   r13!,{r1,r2,r14}
        MOV     r0,#0           ; Initialise result
        CMP     r2,r3           ; Is numerator less than denominator?
        BLT     $Exit           ; If so, exit with result
        MOV     r1,r3           ; Initialise accumulator
        MOV     r14,#1          ; Initialise shift counter

$UpwardLoop
        CMP     r2,r1,LSL #1    ; Check accumulator*2 against numerator
        MOV     r4,r4,LSL #1    ; Shift shift counter
        MOV     r1,r1,LSL #1    ; Shift accumulator up
        BGT     $UpwardLoop     ; Branch back
;==============================================================================
; The accumulator now contains the highest shift of the denominator which is
; still less than the numerator.  Take this away from the numerator, and add
; the shift value to the result build-up.
;------------------------------------------------------------------------------
$DownwardLoop
        CMP     r1,r2           ; Is numerator greater than accumulator?
        SUBLE   r2,r2,r1        ; Take accumulator away from numerator
        ADDLE   r0,r0,r4        ; Add shift counter to result build-up
        BEQ     $Exit           ; Exit if finished division (no remainder left)
        MOV     r1,r1,LSR #1    ; Lower accumulator
        MOVS    r4,r4,LSR #1    ; Lower shift counter
        BGT     $DownwardLoop   ; Go again if there are more positive shifts

$Exit
        LDMFD   r13!,{r1,r2,pc}^
;******************************************************************************

It's in JFPatch format.  JFPatch provides loads of really lovely add-ons to ARM
assembler, but the only one used here is the local labels.  Any label starting
with an $ character only exists between two normal (.labelname) labels.

Anyway, that's about it.  Thanks for your time, and I hope this code is useful
to someone.  See ya, 

Phil Norman.

--

---

From: Philip Blundell <[email-masked]>
Date: Wed, 25 Jun 1997 19:37:26 +0100 (BST)

> I posted just a few hours ago about a DIV routine I've done.  I'm back in 

BTW, the gcc sources have a division routine in (look at lib1funcs.asm). 
This is needed because gcc can't open code division for the ARM and so it
has to compile into a library call. 

p.

---

From: Andy Armstrong <[email-masked]>
Date: Wed, 25 Jun 1997 17:56:36 +0100

In article <Pine.SGI.3.91.970625170545.18786B-100000@newman>, Phil
Norman <[email-masked]> writes

[snip]
>was 313cs for the first version, and 141cs for the second, improved version.

This is completely bonkers Phil. 1 << 40 is about 1e12. To do that many
divides in 141cs each divide would have to take 0.128 picoseconds.

---

From: Alan Cox <[email-masked]>
Date: Thu, 26 Jun 1997 17:48:24 +0100 (BST)

> a divide ( well I can't find it anyway) and the best I can do is 96

That is normal for risc CPU's

> Has anyone done better.

I don't know for ARM but look at the Linux kernel bits for the sparc
and alpha CPU's. Remember it takes a pentium about 35 clocks to do a divide

Alan

---

From: Andy Armstrong <[email-masked]>
Date: Wed, 25 Jun 1997 14:24:37 +0100

In article <Pine.SGI.3.91.970625133317.12063B-100000@newman>, Phil
Norman <[email-masked]> writes
>1.41s on a StrongARM at 202MHz.

Impressive. More than the number of single instructions a StrongARM
could do in that time. Are you sure you haven't got something wrong
somewhere? I don't believe you were doing 3860 divides every clock cycle
:-)

---

From: Alan Cox <[email-masked]>
Date: Fri, 27 Jun 1997 09:47:52 +0100 (BST)

> divides in 141cs each divide would have to take 0.128 picoseconds.

Thats pushing it somewhat 8) - even the 16bit divide in about 2 clocks
(64K lookup table) is slow by comparison