0-5999 to 0-99h:59m

Log in or register to post comments
Go To Last Post
15 posts / 0 new
Author
Message
KerimF
KerimF's picture
Level: Hangaround
Joined: Mon. Jan 26, 2015
Posts: 304 View posts
Location: Aleppo-Syria
#1
Posted by KerimF: Sat. Jul 21, 2018 - 12:24 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

Lately, I needed to convert 0-5999 to 0-99h:59m.

The operation requires a division by 60; the dividend in minutes, the result in hours and the remainder in minutes.

Instead of using the conventional algorithm of division (2 bytes divided by 1 byte), I try using the following code for speed:

 

; r20       ; temporary
; r19       ; temporary
; r18       ; remainder
; r17       ; dividend, high
; r16       ; dividend, low

; r15       ; temporary
; r14       ; result

; r13       ; temporary
; r12       ; temporary

D16b_60:
    MOV   r19, r17    ;1, A=   r17      r16    carry
    MOV   r18, r16    ;1,    87654321 hgfedcba   ?
    LSL   r18         ;1,    87654321 gfedcba0   h
    ROL   r19         ;1,    7654321h gfedcba0   8
    ROL   r18         ;1,    7654321h fedcba08   g
    ROL   r19         ;1,    654321hg fedcba08   7
    ROL   r18         ;1,    654321hg edcba087   f
    ANDI  r18, 0x03   ;1,    654321hg 00000087
    MOV   r15, r18    ;1
    MOV   r14, r19    ;1, B= r15:r14 = A/64

    MOV   r19, r17    ;1     87654321   ?
    LSR   r19         ;1     08765432   1
    LSR   r19         ;1, C= 00876543 = r19 = B/16

    ADD   r14, r19    ;1
    CLR   r19         ;1
    ADC   r15, r19    ;1, D= r15:r14 = B+C

    LDI   r19,60      ;1
    MUL   r14,r19     ;2
    MOV   r12,r0      ;1
    MOV   r13,r1      ;1
    MUL   r15,r19     ;2
    ADD   r13,r0      ;1, E= r13:r12 = D*60

    MOV   r19, r17    ;1
    MOV   r18, r16    ;1
    SUB   r18,r12     ;1
    SBC   r19,r13     ;1, F= r13:r12 = A-E

    SER   r20         ;1
loop:
    INC   r20         ;1
    SUBI  r18,60      ;1 
    BREQ  cnt         ;2,1

    BRCC  loop        ;2,1 , 6*3=18 max

    LDI   r19,60      ;1, G= r20 = F/60
    ADD   r18,r19     ;1, restore remainder (minutes)
    ADD   r14,r20     ;1, hours= r15:r14 = D+G
    RET               ;2

cnt:
    SEC               ;1
    ADC   r14,r20     ;1, hours= r15:r14 = D+G
    RET               ;2

 

I tested it for various entries; the maximum number of cycles seemed to be 41 (without rcall and ret).

I use ATmega8 and I wonder if there is a better code to achieve this special division in term of speed.

Thank you.

 

Added:

The above code is based on the following formula:

 

M = N/60 = N/(64-4) = N/64/(1+1/16) =~ N/64 * (1 – 1/16) = (N/64) – (N/64)/16

 

The result M is usually less than the right one, say H.

To find the difference:

 

D = N – M*60

 

The maximum number of D happens to be 139.

So D/60 needs at most just 3 passes of subtraction. This gives E (how many times of 60 are in D) and the remainder (in minutes).

 

H = M + E  

 

Tags:

AVR Microcontrollers, megaAVR and tinyAVR
Last Edited: Sat. Jul 21, 2018 - 01:14 AM
Top
avr-mike
avr-mike's picture
Level: Resident
Joined: Sat. Jul 21, 2018
Posts: 865 View posts
Location: U.S. Pacific
Posted by avr-mike: Sat. Jul 21, 2018 - 06:12 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You can often use multiplication followed by a shift to achieve a division, though this is obviously complicated by the 8-bit architecture.

 

In your example, 1/60 is very close to 17/1024 (within about 0.4%) so you could try writing a routine which multiplies by 17 followed by a shift of 10 bits to determine the hours.  Multiply this by 60 and subtract from the input to get minutes.

 

You might have to adjust the hours by one and the minutes by 60 if you hit a corner case due to the error margin.

 

Since this multiplication puts you beyond 16 bits for the result anyway, you can try multiplying by 1092 which puts the number of hours in the third byte of the result - no shifting needed (and accuracy improves to 0.025% as well).

 

--Mike

 

Top
KerimF
KerimF's picture
Level: Hangaround
Joined: Mon. Jan 26, 2015
Posts: 304 View posts
Location: Aleppo-Syria
Posted by KerimF: Sat. Jul 21, 2018 - 06:57 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thank you Mike.

 

Multiplying by 1092 seems good since 16x16 Bit unsigned multiplication takes 17 cycles only (without rcall and ret).

 

Kerim

 

Top
KerimF
KerimF's picture
Level: Hangaround
Joined: Mon. Jan 26, 2015
Posts: 304 View posts
Location: Aleppo-Syria
Posted by KerimF: Sat. Jul 21, 2018 - 10:33 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The following new code (thanks to Mike) takes 28 cycles (29 cycles if the remainder is 0).

 

; r19  multiplier high
; r18  multiplier low , remainder (minutes)
; r17  multiplicand (minutes), high
; r16  multiplicand (minutes), low 
; r15  result (hours)
; r14  temporary
; r13  temporary
; r12  temporary

D16u_60:
    LDI   r19, high(1092)       ;1
    LDI   r18,  low(1092)       ;1
                                ;   x= r17:r16 = minutes (0-5999) 
    MUL   r17, r19              ;2
    MOVW  r14, r0               ;1
    MUL   r16, r18              ;2
    MOVW  r12, r0               ;1
    MUL   r17, r18              ;2
    CLR	  r18                   ;1
    ADD	  r13, r0               ;1
    ADC	  r14, r1               ;1
    ADC	  r15, r18              ;1
    MUL	  r19, r16              ;2
    ADD	  r13, r0               ;1
    ADC	  r14, r1               ;1
    ADC	  r15, r14              ;1, y= r15 = x*1092/256/256 = hours

    LDI   r18, 60               ;1
    MUL   r15, r18              ;2, u= r1:r0 = y*60

    MOV   r19, r17              ;1
    MOV   r18, r16              ;1
    SUB   r18 , r0              ;1, v= r18 = x-u (remainder in minutes)

    CPI   r18, 60               ;1
    BRLO  end                   ;2,1

    SUBI  r18, 60               ;1, remainder adjusted
    INC   r15                   ;1, hours     adjusted
end:
    RET

 

Top
clawson
clawson's picture
Level: Moderator
Joined: Mon. Jul 18, 2005
Posts: 96500 View posts
Location: (using avr-gcc in) Finchingfield, Essex, England
Posted by clawson: Sat. Jul 21, 2018 - 12:33 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

Why not hold time as "unixtime" then a divide by 60 really is just an integer divide by 60. The only complication is that at the final point of interpretation you need to make a conversion to yymmdd hhmmss. But there's already well established functions for doing that because almost every computer system in the world dealing in dates/times is using unixtime.

Top
theusch
theusch's picture
Level: 10k+ Postman
Joined: Mon. Feb 19, 2001
Posts: 39459 View posts
Location: Wisconsin USA
Posted by theusch: Sat. Jul 21, 2018 - 12:39 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 2

As the minute value only changes --wait for it-- once a minute, what difference does it make in your application if the conversion for display takes 10 microseconds or 20?  If this situation is so painful, then keep time in hours and minutes, and you never need to perform the described operations; no multiplies or divides involved, only the rollover of the minutes byte.  8-bit INC and one cycle CPI.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

Top
the_real_seebs
the_real_seebs's picture
Level: Hangaround
Joined: Sun. Dec 3, 2017
Posts: 189 View posts
Posted by the_real_seebs: Sat. Jul 21, 2018 - 04:53 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

That's a very good point:

++minutes;
if (minutes == 60) {
    minutes = 0;
    ++hours;
}

This is almost certainly a lot faster than division on AVR.

Top
sparrow2
sparrow2's picture
Level: Raving Lunatic
Joined: Mon. Oct 7, 2002
Posts: 6385 View posts
Location: Denmark
Posted by sparrow2: Sat. Jul 21, 2018 - 05:51 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

perhaps it's a help that 60 can be divided with 4. (so numbers can be 4 times smaller)

and #6 #7  assume that this is a timer I don't think it solves OP's problem.

 

but I don't think it can be done much faster than the solution in #4 about 20 clk would be my guess.

Top
kk6gm
kk6gm's picture
Level: Raving Lunatic
Joined: Fri. Sep 11, 2009
Posts: 3698 View posts
Location: Sacramento, CA
Posted by kk6gm: Sat. Jul 21, 2018 - 06:01 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

theusch wrote:

As the minute value only changes --wait for it-- once a minute, what difference does it make in your application if the conversion for display takes 10 microseconds or 20?

Good question.  Maybe it matters, but 1 minute is 60,000,000 microseconds.  Is this really where one should spend time optimizing?  It's easy to get caught up in optimizing fever and forget to look at the bigger picture.  I do it myself, sometimes just for the intellectual pleasure of it.

Last Edited: Sat. Jul 21, 2018 - 06:02 PM
Top
theusch
theusch's picture
Level: 10k+ Postman
Joined: Mon. Feb 19, 2001
Posts: 39459 View posts
Location: Wisconsin USA
Posted by theusch: Sat. Jul 21, 2018 - 09:25 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

kk6gm wrote:
Good question. Maybe it matters, but 1 minute is 60,000,000 microseconds. Is this really where one should spend time optimizing?

I gave one suggestion about "speeding it up".  Another is to keep the time in a fraction of minutes that is a power of two, and then the whole minutes are had by just dropping low bits.  As a further possible line of investigation, one can keep time in fractional hours that is a power of two.  Get out your pencil and paper and start noodling.  Or, you can continue railing about the crappy toolchain you have chosen.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

Top
digitalDan
digitalDan's picture
Level: Hangaround
Joined: Sat. Nov 1, 2008
Posts: 461 View posts
Posted by digitalDan: Sat. Jul 21, 2018 - 11:02 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

theusch wrote:
Or, you can continue railing

 

I don't see anything here I would consider "railing".  Or was it just that voice inside your head? devil

Letting the smoke out since 1978

 

 

 

 

Last Edited: Sat. Jul 21, 2018 - 11:03 PM
Top
sparrow2
sparrow2's picture
Level: Raving Lunatic
Joined: Mon. Oct 7, 2002
Posts: 6385 View posts
Location: Denmark
Posted by sparrow2: Sat. Jul 21, 2018 - 11:32 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

you use 19 clk to get to hours with MUL 17 it could be like this:

LDI r19,17
LDI r18,0
MUL r19,r17
MOVW r14,r0
MUL r19,r16
ADD r15,r1  ; only high byte needed
ADC r16,r18 ; 4*hours 0..399
LSR r16
ROR r15     ; 2*hours 0..199
LSR r15     ; hours

that is 12 clk (11 if you have a zero reg).

like your code it could be one off

(not tested)

Last Edited: Sat. Jul 21, 2018 - 11:36 PM
Top
theusch
theusch's picture
Level: 10k+ Postman
Joined: Mon. Feb 19, 2001
Posts: 39459 View posts
Location: Wisconsin USA
Posted by theusch: Sun. Jul 22, 2018 - 12:41 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

digitalDan wrote:
Or was it just that voice inside your head?

I only do what the voices in my spouse's head tell her to tell me to do.

 

Railing is in the eye of the beholder.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

Top
meslomp
meslomp's picture
Level: Raving Lunatic
Joined: Wed. May 2, 2007
Posts: 5750 View posts
Location: Nieuwegein, Netherlands
Posted by meslomp: Mon. Jul 23, 2018 - 07:54 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

as said why not split the hours and minutes. for the 6000 number you will be needing a 16bit number. if you take two 8 bit numbers you can keep track of both minutes and hours individually. even do it nibble wise from 0-9 so 59 can be 0x59...... all you then need to do is keep track of the nibbles. but that is even a very simple roll over structure with if statements put inside eachother to say that when the first digit changes check if it over flows, then reset first digit and increment digit 2 then check that on overflow......

Top
KerimF
KerimF's picture
Level: Hangaround
Joined: Mon. Jan 26, 2015
Posts: 304 View posts
Location: Aleppo-Syria
Posted by KerimF: Mon. Jul 23, 2018 - 10:11 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The following new code (now thanks to sparrow2) takes 22 cycles (23 cycles if the first remainder > 59 minutes):

 

; r19  multiplier high
; r18  multiplier low , remainder (minutes)
; r17  multiplicand (minutes), high
; r16  multiplicand (minutes), low
; r15  result (hours)
; r14  temporary
; r1   temporary
; r0   temporary

BIN2hhmm:
    LDI   r19,17                ;1
    LDI   r18,0                 ;1

    MUL   r17, r19              ;2
    MOV   r15, r0               ;1
    MOV   r14, r1               ;1
    MUL   r16, r19              ;2
    ADD   r15, r1               ;1
    ADC   r14, r18              ;1, r14:r15 = 4 * hours 

    LSR   r14                   ;1
    ROR   r15                   ;1
    LSR   r15                   ;1, hours

    LDI   r18, 60               ;1
    MUL   r15, r18              ;2, hours * 60

    MOV   r19, r17              ;1
    MOV   r18, r16              ;1
    SUB   r18 , r0              ;1, remainder in minutes

    CPI   r18, 60               ;1
    BRLO  end                   ;2\1

    SUBI  r18, 60               ;1, remainder adjusted
    INC   r15                   ;1, hours     adjusted
end:
    RET

 

For instance, in some of my applications, I have many timers (running in seconds and minutes) and some of them need to be displayed on 7-seg LED displays on request (hence binary to BCD as hh:mm). Many user entries related to time are usually as hh:mm too. they has to be converted to binary for various calculations (and control) before some of the results will be converted back to hh:mm.

 

Anyway, though the highest speed may not be important in many situations, I just thought how fast this special division (conversion from binary to 99h:59m) could be done. So far it seems it can be done in 23 cycles (without call and ret).

 

Thank you for the other interesting ideas.

 

Last Edited: Mon. Jul 23, 2018 - 10:30 AM
Top