EASy68K  
It is currently Fri Apr 10, 2020 3:07 am

All times are UTC




Post new topic Reply to topic  [ 21 posts ]  Go to page Previous  1, 2
Author Message
 Post subject:
PostPosted: Fri Feb 03, 2006 8:10 pm 
Offline

Joined: Mon Jan 16, 2006 3:04 pm
Posts: 7
ok, i misunderstood your scheme then
i thought that word A was that highest 0000 and that it shouldn't be included when dividing, but rather combine that FFFD as the highest word and then put the middle word from 48 bit as the low word in that 32 register which would then be FFFD 0002

thanks again for it, you're the man lee, now i can finally give that assignment :)


Top
 Profile  
 
 Post subject:
PostPosted: Sat Feb 04, 2006 12:32 pm 
Offline

Joined: Mon Dec 27, 2004 11:40 pm
Posts: 318
The first divide you do in this sort of routine should always be small enough to never overflow a 16 bit result. The easiest way to ensure that is to make the first divide into $0000xxxx where xxxx is the highest 16 bits of your number.

Ok last bit of huge ASCII art on this, this is to divide a 48 bit number by 10 leaving a 48 bit result and a 0 to 9 remainder (which is the next digit).

Code:
         |       64 bit very long word       |
                  |                 |
                  V                 V
         | 32 bit longword | 32 bit longword |
             |        |        |        |
             V        V        V        V
         | word A | word B | word C | word D |   word A always $0000
                      |        |        | 
                      V        |        |
         |  $0000 | word B |   |        |
divide by         |     10 |   |        |
         -------------------   |        |
         | remain |result h|   |        |
swap words                     |        |
         |result h| remain |   |        |
             |        |        |        |
             |        V        V        |
             |    | remain | word C |   |
divide by    |             |     10 |   |
             |    -------------------   |
             |    | remain | result |   |
swap words   |                          |
             |    |result m| remain |   |
             |        |        |        |
             |        |        V        V
             |        |    | remain | word D |
divide by    |        |             |     10 |
             |        |    -------------------
             |        |    | remain |result l|
swap words   |        |
             |        |    |result l| remain | -> remainder is digit
             |        |        |
             V        V        V
         |result h|result m|result l|
             |        |        |
             V        V        V
| word A | word B | word C | word D |   for next divide

Lee.


Last edited by lee on Sun Feb 05, 2006 4:37 pm, edited 4 times in total.

Top
 Profile  
 
 Post subject:
PostPosted: Sun Feb 05, 2006 4:39 pm 
Offline

Joined: Mon Dec 27, 2004 11:40 pm
Posts: 318
There were more corrections to do than that but, as I was having a very hard time connecting, I gave up.

All fixed now, I think.

Lee.


Top
 Profile  
 
 Post subject:
PostPosted: Thu Feb 09, 2006 3:01 am 
Offline

Joined: Thu Feb 09, 2006 2:57 am
Posts: 1
I only registered to thank you all. I had the same assignment as Velorien.
And this thread helped me a lot.

And I guess you're going to have lots of Croats around here in the near future. :)

Thanks again!

Dino


Top
 Profile  
 
 Post subject:
PostPosted: Sat Mar 19, 2011 10:31 pm 
Offline

Joined: Mon Jul 26, 2010 11:43 pm
Posts: 198
Location: Aurora, IL
Code:
*------------------------------------
* Decimal conversion and 64-bit division example
*  clive@tbcnet.com  cturvey@gmail.com
*------------------------------------

           org     $400

* Program starts here

start

        move.l  #12345,d0
        lea     buffer,a0
        bsr     dec16
        bsr     puts

        move.l  #1234567890,d0
        lea     buffer,a0
        bsr     dec32
        bsr     puts

        move.l  #$FFFFFFFF,d0 ; d1:d0 = 64-bit
        move.l  #$FFFFFFFF,d1
        lea     buffer,a0
        bsr     dec64
        bsr     puts

        MOVE.L  #9,D0
        TRAP    #15     ; halt simulator

*------------------------------------
* Convert 16-bit binary to decimal

; D0=binary number (0-65,535), Assume High Order Zero, Real Limit (0-655,359)
; A0=string output address

dec16   movem.l d0-d1/a0,-(a7)  ; Save D0,D1,A0
        move.w  #0,-(a7)        ; Push NUL End-Of-Stack marker
loop1   divu    #10,d0          ; D0:LOW = D0/10, D0:HIGH = D0%10
        move.l  d0,d1           ; Copy to split quotient and remainder
        swap    d1              ; Get remainder in D1:LOW
        add.w   #$30,d1         ; Add ASCII '0' to 0-9 digit
        move.w  d1,-(a7)        ; Push Digit, number built backward
        and.l   #$FFFF,d0       ; D0:HIGH = 0
        bne     loop1           ; until D0 = 0

; Now unstack reverse decimal built on stack

loop2   move.w  (a7)+,d1        ; unstack next digit
        move.b  d1,(a0)+        ; copy into output string buffer
        bne     loop2           ; Until NUL unstacked

        movem.l (a7)+,d0-d1/a0  ; Restore D0,D1,A0
        rts

*------------------------------------
* Convert 32-bit binary to decimal

; D0=binary number (0-4,294,967,295)
; A0=string output address

dec32   cmp.l   #655360,d0      ; Use 16-bit routine if in range
        bcs     dec16           ; unsigned less than 655,360

        ; At least 6 significant digits

        movem.l d0-d3/a0,-(a7)  ; Save D0,D1,D2,D3,A0

        move.w  #0,-(a7)        ; Push NUL End-Of-Stack marker

        move.l  d0,d2           ; Save original D0 for remainder computation

        ; Improve 68K efficiency by using 16-bit divides, beware
        ;  the student that blindly copies this code. It was written
        ;  by someone who knows what they are doing.

        lsr.l   #1,d0           ; / 2
        move.w  #50000,d1       ;   50000
        divu    d1,d0           ; / 100000, ie (50000 * 2)
        and.l   #$FFFF,d0       ; Mask quotient
        mulu    d0,d1           ; D1 = D0 * 50000
        sub.l   d1,d2           ; back out quotient twice for remainder
        sub.l   d1,d2           ; D2 -= D0 * 100000

        ; The preceeding sequence effectively performs a divide
        ;  beyond the scope of a single 16-bit hardware divide.

        ; D0 = D0 / 100000, D2 = D0 % 100000

        move.l   #5-2,d3        ; D3 = 5 Least significant digits

loop3   divu    #10,d2          ; D2:LOW = D2/10, D2:HIGH = D2%10
        move.l  d2,d1           ; Copy to split quotient and remainder
        swap    d1              ; Get remainder in D1:LOW
        add.w   #$30,d1         ; Add ASCII '0' to 0-9 digit
        move.w  d1,-(a7)        ; Push Digit, number built backward
        and.l   #$FFFF,d2       ; D2:HIGH = 0
        dbra    d3,loop3        ; until 5 digits
        add.w   #$30,d2         ; Add ASCII '0' to 0-9 digit
        move.w  d2,-(a7)        ; Push Digit, number built backward

        ; Most significant 1-5 digits

loop4   divu    #10,d0          ; D0:LOW = D0/10, D0:HIGH = D0%10
        move.l  d0,d1           ; Copy to split quotient and remainder
        swap    d1              ; Get remainder in D1:LOW
        add.w   #$30,d1         ; Add ASCII '0' to 0-9 digit
        move.w  d1,-(a7)        ; Push Digit, number built backward
        and.l   #$FFFF,d0       ; D0:HIGH = 0
        bne     loop4           ; until D0 = 0

loop5   move.w  (a7)+,d1        ; unstack next digit
        move.b  d1,(a0)+        ; copy into output string buffer
        bne     loop5           ; Until NUL unstacked

        movem.l (a7)+,d0-d3/a0  ; Restore D0,D1,D2,D3,A0
        rts

*------------------------------------
* Convert 64-bit binary to decimal

; D1:D0=binary number (0-18,446,744,073,709,551,615)
; A0=string output address

dec64   or.l    d1,d1           ; Use 32-bit routine if in range
        beq     dec32           ; unsigned less than 4,294,967,296

        movem.l d0-d5/a0,-(a7)  ; Save

        move.l  d1,d2           ; Map to registers used by the 64-bit divides
        move.l  d0,d1           ; D2:D1 - 64-bit number

        move.l  #10000,d3       ; Divisor constant for 16-bit 4-digit multiples

        move.w  #0,-(a7)        ; Push NUL End-Of-Stack marker
loop6
        bsr     div6416         ; D2:D1 = D2:D1 / 10000, D0 = D2:D1 % 10000
        move.l  d1,d4           ; 64-bit quotient test
        or.l    d2,d4
        beq     loop8           ; quotient zero, final digits

        move.w  #4-2,d4         ; 4 digits (final /10 not required)
loop7   divu    #10,d0          ; D0:LOW = D0/10, D0:HIGH = D0%10
        move.l  d0,d5           ; Copy to split quotient and remainder
        swap    d5              ; Get remainder in D5:LOW
        add.w   #$30,d5         ; Add ASCII '0' to 0-9 digit
        move.w  d5,-(a7)        ; Push Digit, number built backward
        and.l   #$FFFF,d0       ; D0:HIGH = 0
        dbra    d4, loop7
        add.w   #$30,d0         ; Add ASCII '0' to 0-9 digit
        move.w  d0,-(a7)        ; Push Digit, number built backward
        or.l    d2,d2           ; High order empty?
        bne     loop6           ; Still 64-bit wide
        bsr     div3216         ; Otherwise 32-bit, D1 = D1 / 10000, D0 = D1 % 10000
        move.w  #4-2,d4         ; 4 digits
        or.l    d1,d1           ; 32-bit quotient test
        bne     loop7           ; Non-zero quotient, another group

        ; Most significant 1-4 digits

loop8   divu    #10,d0          ; D0:LOW = D0/10, D0:HIGH = D0%10
        move.l  d0,d5           ; Copy to split quotient and remainder
        swap    d5              ; Get remainder in D5:LOW
        add.w   #$30,d5         ; Add ASCII '0' to 0-9 digit
        move.w  d5,-(a7)        ; Push Digit, number built backward
        and.l   #$FFFF,d0       ; D0:HIGH = 0
        bne     loop8           ; While any digits remain

loop9   move.w  (a7)+,d1        ; unstack next digit
        move.b  d1,(a0)+        ; copy into output string buffer
        bne     loop9           ; Until NUL unstacked

        movem.l (a7)+,d0-d5/a0  ; Restore
        rts

*------------------------------------
; Divide 64-bit by 16-bit
;
; D1[32] = D1[32] / D3[16]
; D0[16] = D1[32] % D3[16]
; D3 Preserved
;
; Algorithm
;
; A B / X = C D, and A B % X = d (each digit is 16-bit word)
;
; The remainder cascades down the chain of divides
;
; Where C = A / X, c = A % X
;       D = ((c << 16) + B) / X, d = ((c << 16) + B) % X
;
; The final remainder is that for the entire division chain

div3216 move.l  d4,-(a7)        ; Save D4
        move.w  d1,d4           ; D1 = A:B, D4:LOW = B
        clr.w   d1              ; D1:LOW = 0
        swap    d1              ; D1:LOW = A, D1:HIGH = 0
        divu.w  d3,d1           ; D1:LOW = 0:A/X (C), D1:HIGH = 0:A%X (c)
        move.l  d1,d0           ; D0:LOW = C, D0:HIGH = c
        swap    d1              ; D1:LOW = c, D1:HIGH = C
        move.w  d4,d0           ; D0:LOW = B (D0:HIGH = c)
        divu.w  d3,d0           ; D0:LOW = c:B/X (D), D0:HIGH = c:B%X (d)
        move.w  d0,d1           ; D1:LOW = D (D1:HIGH = C) - Final C:D
        clr.w   d0              ; D0:LOW = 0
        swap    d0              ; D0:LOW = c:B%X (d), D0:HIGH = 0 - Remainder 0:d
        move.l  (a7)+,d4        ; Restore D4
        rts

*------------------------------------
; Divide 64-bit by 16-bit
;
; D2:D1[64] = D2:D1[64] / D3[16]
; D0[16]    = D2:D1[64] % D3[16]
; D3 Preserved
;
; Algorithm
;
; A B C D / X = E F G H, and A B C D % X = h (each digit is 16-bit word)
;
; The remainder cascades down the chain of divides
;
; Where E = A / X, e = A % X
;       F = ((e << 16) + B) / X, f = ((e << 16) + B) % X
;       G = ((f << 16) + C) / X, g = ((f << 16) + C) % X
;       H = ((g << 16) + D) / X, h = ((g << 16) + D) % X
;
; The final remainder is that for the entire division chain
;
; The observation is that (((V % X) << 16) + W) / X will always fit in 16-bits
;  and the cascades can be extended to 128-bits, or whatever extent required.
; On the 68020 you could evolve the divides to 32-bit longs.
;
; The 16-bit divisor works well for decimals, specifically 10 (1 digit) or 10000 (4 digits)
;  The remainder from a 10000 divide, permits 4 digits to be printed with intrinsic DIVU's

div6416 move.l  d4,-(a7)        ; Save D4
        move.w  d2,d4           ; D2 = A:B, D4:LOW = B
        clr.w   d2              ; D2:LOW = 0
        swap    d2              ; D2:LOW = A, D2:HIGH = 0
        divu.w  d3,d2           ; D2:LOW = 0:A/X (E), D2:HIGH = 0:A%X (e)
        move.l  d2,d0           ; D0:HIGH = e, D0:HIGH = E
        swap    d2              ; D2:HIGH = E - Save
        move.w  d4,d0           ; D0:LOW = B (D0:HIGH = e)
        divu.w  d3,d0           ; D0:LOW = e:B/X (F), D0:HIGH = e:B%X (f)
        move.w  d0,d2           ; D2:LOW = F (D2:HIGH = E) - Final E:F
        swap    d0              ; D0:HIGH = F, D0:LOW = f
        move.w  d1,d4           ; D1 = C:D, D4:LOW  = D
        move.w  d0,d1           ; D1:LOW = f (D1:HIGH = C)
        swap    d1              ; D1:HIGH = f, D1:LOW = C
        divu.w  d3,d1           ; D1:LOW = f:C/X (G), D1:HIGH = f:C%X (g)
        move.l  d1,d0           ; D0:HIGH = g, D0:LOW = G
        swap    d1              ; D1:HIGH = G - Save
        move.w  d4,d0           ; D0:LOW = D, D0:HIGH g
        divu.w  d3,d0           ; D0:LOW = g:D/X (H), D0:HIGH = g:D%X (h)
        move.w  d0,d1           ; D1:LOW = H (D1:HIGH = G) - Final G:H
        clr.w   d0              ; D0:LOW = 0
        swap    d0              ; D0:LOW = g:D%X (h), D0:HIGH = 0 - Remainder 0:h
        move.l  (a7)+,d4        ; Restore D4
        rts

*------------------------------------
* Subroutine to display NUL terminated string

outstr  movem.l d0/a0-a1,-(a7)
        move    #14,d0          ; task number into D0
        move    a0,a1
        trap    #15             ; display string
        movem.l (a7)+,d0/a0-a1
        rts

*------------------------------------

puts    movem.l d0/a0-a1,-(a7)
        move    #14,d0          ; task number into D0
        move    a0,a1
        trap    #15             ; display string
        lea     crlf,a1
        trap    #15
        movem.l (a7)+,d0/a0-a1
        rts

crlf    dc.b    13,10,0,0

*------------------------------------

buffer  ds.b    30

        end start


Top
 Profile  
 
PostPosted: Wed Jan 15, 2014 4:37 am 
Offline

Joined: Tue Nov 15, 2005 7:58 am
Posts: 129
Location: Oregon, USA
Lee (or anybody) -- can you point me to any methods to divide by arbitrary numbers bigger than a word and that make good use of 68000 hardware? Ones possibly that don't require trial divisors?
I'm familiar with one-bit-per-iteration methods, but I'm hoping for something more efficient, but not as complex as say FFTs, elliptic curves, or other exotica.

Thanks much.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 21 posts ]  Go to page Previous  1, 2

All times are UTC


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group