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]
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
mitchi, if you want to understand the principle :
http://www.asmcommunity.net/board/index.php?topic=21308.0
Lingo, nice...
lingo,
Returned the correct result for every date I threw at it. Nice and fast too. :thumbu
mitchi,
There is a calculator on this (http://win32assembly.online.fr/source.html) page called MagicNumber by The Svin, it's handy for finding the 'magic numbers'.
Haha, that magicnumber tool is awesome !
:cheekygreen: :cheekygreen: :cheekygreen: :cheekygreen:
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)
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!!!
"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
Do C and other HLL compilers do these optimization ?
@ Lingo
Please make a better magic tool. Name it BlackMagicTool :toothy
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.
Now, you just need to replace the MUL/IMUL instruction with a register shifter
You can start here,
http://en.wikipedia.org/wiki/Julian_day..
and it gets messy according to which calandar you use.
:8)
Quote from: BlackVortex on April 07, 2009, 05:48:03 PM
Do C and other HLL compilers do these optimization ?
Yes. I've seen even VC++ 6.0 emitting magic numbers.
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:
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]
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
Well, the original code "should" have been written this way:
unsigned dayOfWeek(unsigned day, unsigned month, unsigned year)
{
static unsigned t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
unsigned x = year;
if(month < 3)
--x;
return (x + x/4 - x/100 + x/400 + t[month-1] + day) % 7;
}
It should generate more efficient code.
QuoteIt should generate more efficient code.
It did. Running on my P3, the improved code was 5 cycles faster compiled with Visual C++ Toolkit 2003 and 7 cycles faster compiled with GCC. I have updated the attachment and the results.
Apparently, more recent versions do an even better job; here's the assembler output from my FreeBSD's GCC:
.file "dayOfWeek.c"
.text
.p2align 4,,15
.globl dayOfWeek
.type dayOfWeek, @function
dayOfWeek:
pushl %ebp
movl %esp, %ebp
movl 12(%ebp), %ecx
movl 16(%ebp), %edx
movl 8(%ebp), %eax
pushl %ebx
cmpl $3, %ecx
sbbl $0, %edx
addl t.1543-4(,%ecx,4), %eax
movl %edx, %ecx
shrl $2, %ecx
addl %edx, %eax
leal (%eax,%ecx), %ebx
movl $1374389535, %ecx
movl %edx, %eax
mull %ecx
movl %edx, %ecx
shrl $7, %ecx
addl %ecx, %ebx
shrl $5, %edx
subl %edx, %ebx
movl $613566757, %edx
movl %ebx, %eax
movl %ebx, %ecx
mull %edx
subl %edx, %ecx
shrl %ecx
addl %ecx, %edx
shrl $2, %edx
leal 0(,%edx,8), %ecx
subl %edx, %ecx
subl %ecx, %ebx
movl %ebx, %eax
popl %ebx
popl %ebp
ret
.size dayOfWeek, .-dayOfWeek
.section .rodata
.align 32
.type t.1543, @object
.size t.1543, 48
t.1543:
.long 0
.long 3
.long 2
.long 5
.long 0
.long 3
.long 5
.long 1
.long 4
.long 6
.long 2
.long 4
.ident "GCC: (GNU) 4.2.1 20070719 [FreeBSD]"
On my soon to be posted new moonphase program it allows you to enter a date to see different astronomical positions. but you can not enter the dates october 5-14 in the year 1582 since this is the commonly used dates of transition from Julian to Gregorian calendar, oct. 4, 1582 julian calendar followed by the next day of oct. 15, 1582 gregorian calendar.
Regards, Darrel
I could say enough uncomplements to inventors of calendar magic numbers as oct. 4, 1582 julian :bdg, insted of using original formule from it's papa and no chance if not to understand astronomers :
including 4000 years correlation, Grigorian calendar repeating on (((365*4+1)*25-1)*4+1)*10-1 = 1460969 days, so formule of week day is :
dayOfWeek = (total_days(day, month, year) - 1) % 7;