Day Of The Week Algo

[lingo]

option   prologue:none
option   epilogue:none
; Work out what the day of the week is for a given date
; C Algorithm by Tomohiko Sakamoto
; int dayofweek(int d, int m, int y) {
;   static int t[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
;   y -= m < 3;
;   return ( y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
; }
; year  = [1, 9999+]
; month = [1, 12]
; day   = [1, 31]
; MASM algo by Lingo - 7 clocks
; Return: eax=0(Su) or 1(Mo) or 2(Tu) or 3 (We) or 4 (Th) or 5(Fr) or 6(Sa)

align 16
monthdata    dd 0,0,3,2,5,0,3,5,1,4,6,2,4,0,1,2
DayOfTheWeek proc year:DWORD, month:DWORD, day:DWORD

pop  eax                      ; return address
pop  edx                      ; edx->years
pop  eax                      ; eax->month
cmp  eax, 3                   ; test if month is < 3
pop  ecx                      ; ecx->day
sbb  edx, 0                   ; if month < 3 then dec edx->years
add  ecx, [monthdata + eax*4] ; ecx-> monthdata[month-1] +day
mov  eax, edx                 ; eax=edx=years
shr  eax, 2                   ; eax= years/4
add  ecx, edx                 ; ecx-> monthdata[month-1] +day+years
imul edx, 0A3D8h              ; dividing edx=years by 100 == imul edx, 0A3D8h / shr edx, 22
add  eax, ecx                 ; eax= monthdata[month-1] +day+years+ years/4
shr  edx, 22                  ; end of dividing ; edx=years/100
sub  eax, edx                 ; eax= monthdata[month-1] +day+years+ years/4- years/100
shr  edx, 2                   ; edx=years/400
add  eax, edx                 ; eax= monthdata[month-1] +day+years+ years/4-years/100+years/400

mov  edx, 24924925h           ; dividing eax by 7 == mul edx, eax ; 24924925h=dword (1/7 * 2^35)
mov  ecx, eax                 ; ecx=eax=monthdata[month-1]  + day+years+years/4-years/100+years/400[/u]
mul  edx                      ; dividing eax by 7 ->result in edx
add  ecx, edx                 ; add n/7 to ecx(n)
neg  edx                      ; edx-> -n/7 ;-> ecx+ ecx/7 - 8*ecx/7 = ecx -  7*ecx/7 = ecx  % 7 [/u]
lea  eax, [ecx+edx*8]         ; eax= (monthdata[month-1] + day + years + years/4 - years/100 + years/400) % 7
jmp  dword ptr [esp-4*4]      ; jmp to return address[/list]
DayOfTheWeek  endp
option   prologue:prologuedef
option   epilogue:epiloguedef
Notes:
- Dividing by 100 -> imul edx, 0A3D8h / shr edx, 22 works for all edx in range 0 to AAB2h(43 698)
- Dividing by 7 -> mov edx, 24924925h / mul edx works for all eax in range 0 to 55555559h(1 431 655 769)
[/font][/size][/pre]

[mitchi]

Lingo, you have godlike control of your code. I read your code and It's like everything is planned in advance and optimized fully. I'm proud that I can understand most of it. I still don't understand how you manage to manage to dodge divisions like that by using mul and other magic numbers. They never taught me stuff like that in math class ! What's happening here ?  :green

[NightWare]

mitchi, if you want to understand the principle :
http://www.asmcommunity.net/board/index.php?topic=21308.0

Lingo, nice...

[GregL]

lingo,

  Returned the correct result for every date I threw at it.  Nice and fast too.  :thumbu


mitchi,

  There is a calculator on this page called MagicNumber by The Svin, it's handy for finding the 'magic numbers'.

[BlackVortex]

Haha, that magicnumber tool is awesome ! 

:cheekygreen:               :cheekygreen:                :cheekygreen:               :cheekygreen:

[mitchi]

Wahooo, I'm impressed by the might of maths sometimes !
Thank you very much Greg, I had a wonderful time looking at this with much curiosity   :bg

But to come back to the subject, that Lingo really doesn't waste a single cycle. I have a long way to go  :8)

[lingo]

Thank you guys,  :wink
I used Terje Mathisen's (before A.Fog and Svin) way to dividing by a constant  by multiplying with the reciprocal.
This method needs some refinement in order to compensate for rounding errors and we must test the range of numbers ALLWAYS before to use it!!!

[lingo]

"Haha, that magicnumber tool is awesome"

I know Svin but don't use his MagicNumber tool. Why? :wink
Example:

Svin's MagicNumber tool
Divider:  7
Result:
MagicNumber = 2454267026
mov eax,X
mov edx, MagicNumber
inc eax
mul edx
SHR edx, 2

Against my smaller and faster MagicNumber:
mov eax, X
mov edx, 24924925h  ; My MagicNumber for Divider 7
mul edx

[BlackVortex]

Do C and other HLL compilers do these optimization ?

@ Lingo
Please make a better magic tool. Name it BlackMagicTool    :toothy

[FORTRANS]

Hi,

   Using a fixed point to decimal converter it is easy to verify
that 24924925h is a good approximation to 1/7.  I posted
one in another multiply to divide thread.  It was for 16.16
calculations.  I've since written a 32.32 tool.

Regards,

Steve N.

[dedndave]

Now, you just need to replace the MUL/IMUL instruction with a register shifter

[vanjast]

You can start here,
http://en.wikipedia.org/wiki/Julian_day..

and it gets messy according to which calandar you use.
  :8)

[xmetal]

Do C and other HLL compilers do these optimization ?

Yes. I've seen even VC++ 6.0 emitting magic numbers.

[MichaelW]

The attachment is a comparison of lingo's code to the original C code compiled with Visual C++ Toolkit 2003 and with GCC 3.2.3 (MinGW). The file dayofweek_gcc_o2.asm shows what GCC created for the -O2 optimization level instead of -O3 (on my P3 the -O3 was faster by one cycle).
Results on my P3:

Code Select Expand


18 cycles, DayOfTheWeek
60 cycles, dayofweek
55 cycles, dayofweek2
62 cycles, dayofweek_gcc
54 cycles, dayofweek2_gcc


Edit: New results and new attachment after 5 downloads.


[attachment deleted by admin]

[daydreamer]

great code Lingo
it would be possible to improve it even more, by have Gregorian/Julian Calendar calculated in parallel, and from a lookuptable on when different Nations changed from Julian Calendar to Gregorian Calendar to choose to display right result