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