Мелкие задачки для крупных мозгов №24

Дано:

номер года Y от 0 до 9999

номер месяца M от 1 (январь) до 12(декабрь).

Если ((Y mod 4 = 0) и (Y mod 100 <>0)) или ((Y mod 400)=0), то год считается високосным, и в феврале такого года 29 дней.



Задача:

оптимизировать по размеру код, который определит сколько дней D в месяце M года Y (28,29,30 или 31).

Например:

Y=1700,M=2, D=28

Y=1999,M=5, D=31

Y=2000,M=2, D=29

Y=2005,M=11, D=30



Дополнительная задача:

сделать то же самое без переходов.



M,Y и результат D должны находиться в 32х разрядных регистрах, которые можно выбрать произвольно.

 

Версия "навскидку", без бранчей, 36 байт, простор для оптимизации. Пока придержу.

MD5 hash: A7 10 CC 5B 66 F1 6D 57 13 71 85 DE 02 AB C2 2D

 

Для начала предложу половину кода.

Ту половину, которая отвечает за код если месяц не февраль.

Обратим внимание, что у половины месяцев с (января до июля) 31 день в нечётные месяцы, а у половины - в чётные.

Обратим внимание что номера тех что чётные номера месяцев >= 8 а значит будут содержать 1 в 3ем бите т.е. иметь форму бинарную 01xxx.

используем это для определения 31 или 30 дней без бранча.

Код (Text):

1.  
2. ;eax = номер месяца
3. cmp al,2
4. je @febr ;обработка февраля
5. mov ecx,eax
6. shr ecx,3
7. xor eax,ecx
8. and eax,1
9. add eax,30
10.  

 

The Svin

Хороший код.



Вот моя частичка.

; eax = год

; ecx = номер месяца

............

; eax = 0 для простого и 10h для для високосного

; ecx = номер месяца

add eax, 03BBEECCh

shl ecx, 1

shr eax, cl

and eax, 3

add al, 28



уже 14 байт.

интересно, через флаг попробовать... не, не катит.

 

half doesn't count, only the whole thing do.

Половина -- сильно сказано, имхо третья часть. Я бы задачу разделил на 3 части: определить, високосен ли год, затем определить число дней в месяце. Третья часть -- это связывание (не)високосности только с февралем.



The Svin

Число дней в месяце без учета февраля можно в 8 байт посчитать... это самое неинтересное. Если тянет на матем. оптимизацию -- самый простор в определении високосности.

 

Чую-чую что с

div 64h

начать надо...

 

AlB80

Я делал на этом принципе: если 2 младшие десятичные цифры числа делятся на 4, то и всё число делится на 4 без остатка.

num % 4 == (num % 100) % 4

Перельман хоть и еврей был, но книжки писал классные.

 

_BC_

Вот и я чую, что две младшие десятичные цифры есть 64h.

 

AlB80

Странно, а я наоборот, 2х-битовые смещения забраковал сразу же, и сделал однобитовые (т.е. под флаг).

Вот мой первый вариант (eax = год, ecx = месяц:

Код (Text):

1.         cdq
2.         push    100
3.         pop ebx
4.         div ebx
5.         test    edx, edx
6.         cmovnz  eax, edx
7.         and al, 3
8.         setnz   al
9.         cmp cl, 2
10.         setz    bl
11.         and eax, ebx
12.         add eax, ebx
13.         neg al
14.         mov dx, 0AD5h
15.         shr edx, cl
16.         adc al, 30

Если украсть твою концовку, то можно сделать в 32 байта:

Код (Text):

1.         cdq
2.         push    100
3.         pop ebx
4.         div ebx
5.         test    edx, edx
6.         cmovnz  eax, edx
7.         and al, 3
8.         setz    ah
9.         db  0D5h, 10h   ; aad 16
10.         add eax, 3BBEECCh
11.         shr eax, cl
12.         shr eax, cl
13.         and eax, 3
14.         add al, 28

_2102853904__hashme.txt

 

_BC_

Не думал что без переходов можно уложиться в 32 байта, видимо опыта использования setxx и cmovxx у людей маловато. Нужно будет включить их в следующие задачки.



А мой первый вариант с переходами долго мутировал, но как был 37 байт, так и остался, но зато какая в нём появилась табличка!



eax-год, ecx-месяц, edx-число дней

Код (Text):

1.     xor cl,2
2.     jz .feb
3.     imul ecx,$FFFFFF90
4.     shr cl,7;незаметил что можно rol cl,1 поставить 8(
5.     inc ecx
6.     .feb:;(cl=0 - февраль, cl=1 - 30 дней,cl=2 - 31 день)
7.     mov dl,1111100b ;табличка
8.     mov ch,100
9.     div ch
10.     test ah,3
11.     jnz .l28
12.     test ah,ah
13.     jnz .l29
14.     and al,3
15.     jnz .l28
16.     .l29:
17.     inc edx  ;правим табличку
18.     .l28:
19.     ror dl,cl ;извлекаем
20.     and edx,31;значение
21.  

 

а rol будет лучше? Чем, если не секрет? Быстрее потому, что 1, а не 7, или как?

 

r90

rol cl,1 на 1 байт меньше чем shr cl,7

 

Black_mirror

не знал. заглянул в доки, заодно так полистал: вот, блин, ребята из intel постарались, чтоб оптимизаторам было чем заняться. поражён глубиной мысли. надо будет поизучать на досуге.

 

r90

ror чуть медленнее чем shr, особенно на P1 и PMMX. Подозреваю, что сказывается реализация barrel shifter'а. Правда для P4 в Агнере Фоге производительность обоих инструкций имеет одинаковые коэффициенты. Кстати, в отличии от ROL, для SHR не имеет значения количество сдвигов.

 

Quantum

А ты не путаешь rol\ror с rcr\rcl ?

Вроде как rol\ror на константу не отличаются по латентности от shl\shr и не зависят от числа сдвигов

 

eax = год, edx = месяц, bl = день, 37 байт:

Код (Text):

1.  
2.         mov bl, 31
3.  
4.         mov cx, 0001010110101010b
5.         bt ecx, edx
6.         jb _day_31
7.  
8.         mov cl, 2
9.         cmp cl, dl
10.         jnz _day_30
11.  
12.         inc ecx
13.         test al, cl
14.         jnz _day_28
15.  
16.         mov ch, 100
17.         div ch
18.         test ah, ah
19.         jnz _day_28
20.  
21.         test al, cl
22.         jz _day_29
23.  
24. _day_28:
25.         dec ebx
26.  
27. _day_29:
28.         dec ebx
29.  
30. _day_30:
31.         dec ebx
32.  
33. _day_31:    
34.  

Для 32-разрядного результата еще xor ebx, ebx в начале, итого 39 байт.

 

leo

Нет, ротацию через C я вообще боюсь использовать, т.к. там в плане производительнсоти дела обстоят ещё хуже.

Фог считает иначе, а я сам не проверял, т.к. разница очень маленькая. ror/rol с константой 1 обретает статус спариваемой инструкции на старых моделях, а про новые внятно ничего не сказано, но латентность всё равно выше, чем shl/shr.

 

У меня 40 байт получилось, больше не смотрел.

Меньше тоже.



mov dl, 64h

div dl

xor ax, 0303h

rol ah, 6

shl al, 6

add ax, 3F40h

adc al, 0

shl al, 4

movzx eax, al

add eax, 03BBEECC

shl cl, 1

shr eax, cl

and eax, 3

adc al, 28

 

переделанный вариант _monday_morning 30 байт



mov bl,31

mov cx,1010110101010b

bt ecx,edx

jb day_31



xor dl,2

jnz day_30



mov cx,400

div cx

or edx,edx

jz day_29

dec ebx

day_29:

dec ebx

day_30:

dec ebx

day_31:



А почему условие такое mod 400, а не просто mod 4.

 

asd

20 объяснений по поводу того, что такое високосный год