ASM и компиляторы

Вот тут у меня с человеком возник большой спор. Он как и многие сейчас делают утверждает что компилятор с оптимизацией делает оптимизацию лучше человека.

Сразу скажу что для меня это утверждение полный маразм. Хорошего! кодера никакой оптимизатор обогнать не сможет. Единственная вещь с которой он выигрывает это скорость оптмизации. Даже если вопрос не касается алгоритма. На языке всегда видно как лучше оптимизировать сам алгоритм.



Поэтому поступило предложение посоревноваться немного. Я

реализую решение любой задачи на асме, а он на Си или ещё чём (с опимизацей алгоритма и всё как полагается), но без вставок. И пускай она его обгонит хотя бы в два раза (можно больше). Вот здесь и воникает проблема.

Лично я исправленный перевод Генри Уоррена читал на одном дыхании и каких либо усилий находил в кучу ошибок (некоторые из которых сделаны даже не по вине переводчика). И на асме я пишу достаточно давно, чтобы быть более чем уверенным в своих силах. Но с другой стороны сейчас я по уши завален работой (и горой хороших книг которые мне некогда даже полистать) и у меня нет никакого желания тратить время на глупый спор. Даже один день стал бы роскошью.



Поэтому вот что. Если у кого-нибудь хорошо оптимизированный исходник который мог бы выступить в такой роли ?? (желательно по криптографии)...



ICQ: ...

 

Дык давай пусть он реализует на сях дешифрование RC4 (ключ 128 бит), а мы попробуем обогнать, сравним например на файле порядочного размера или замерим (кстати тестовая машина какая будет?) я уже даже чуть начал , это генерация таблицы в RC4 (ещё есть куда оптимизировать)

Код (Text):

1. ;=========================================================
2. table:      times   256 db %-1
3. key         db      1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
4. ;=========================================================
5.             mov     ebx,table
6.             mov     ebp,0-256
7.             xor     ecx,ecx
8.             xor     eax,eax
9. align 16                                      ; PIII
10. @@:         movzx   edx,byte [ebx+ebp+256]    ; p2
11.             and     ecx,0Fh                   ; p01
12.             add     al,dl                     ; p01
13.             add     al,byte [key+ecx]         ; p01\p2
14.             movzx   ecx,byte [ebx+eax]        ; p2
15.             mov     byte [ebx+ebp+256],cl     ; p3\p4
16.             mov     byte [ebx+eax],dl         ; p3\p4
17.             inc     ebp                       ; p01
18.             mov     ecx,ebp                   ; p01
19.             jnz     @B                        ; p1
20. ;=========================================================

 

В аттаче исходник (фасм), проверяющий корректность таблицы

_1572332567__rc4table.asm

 

После создания таблицы, происходит дешифровка, вот её код после C\C++ (из виндовс кстати)

Код (Text):

1.             xor     ecx,ecx
2.             xor     edx,edx
3.             mov     esi,table
4.             mov     ebp,size
5.             mov     edi,encrypted
6.             mov     cl,byte [esi+100]
7.             mov     dl,byte [esi+101]
8.             test    ebp,ebp
9.             je      exit
10. @@:         inc     ecx
11.             mov     ebx,0FFh
12.             and     ecx,ebx
13.             xor     eax,eax
14.             mov     al,byte [esi+ecx]
15.             add     edx,eax
16.             and     edx,ebx
17.             xor     ebx,ebx
18.             mov     bl,byte [esi+edx]
19.             mov     byte [esi+ecx],bl
20.             mov     byte [esi+edx],al
21.             add     al,bl
22.             mov     bl,byte [edi]
23.             mov     al,byte [esi+eax]
24.             xor     bl,al
25.             mov     byte [edi],bl
26.             inc     edi
27.             dec     ebp
28.             jnz     @B

 

какая Машина не знаю. И как всё это сравнивать тоже. Думаю обычная машина. Т.е. наши компы. Какой-нибудь P3-P4 (или что там сейчас люди покупают). Вообще мне просто обидно что я позволил ввязать в себя в эту глупость. Но раз уж так получилось. Хотелось бы знать насколько быстрее это работает. Если быстро и на Си это сделать трудно, то я не поленюсь оторвать немного времени от работы и написать оболочку...

 

Вообще впечатляет. Но иницилизацию ключа оптимизировать не нужно, она на скорость не влияет. И сам цикл шифра больно уж просто должен выглядеть. Нету так сказать простора для фантазии....

И вот это радует

@@: inc ecx

mov ebx,0FFh

and ecx,ebx



только 7-й вижал Си себя уже гораздо умнее ведёт..

 

Это подтасовка!

Современные криптоалгоритмы _создаются_ с учётом возможности их быстрой реализации на HLL.



Возьмите лучше задачу, гда HLL заведомо слабы - обработку битовых потоков данных, вроде некотороых алгоритмов коспресии

 

<font color="gray][ Вот тут у меня с человеком возник большой спор. ]</font><!--color-->



А я знаю origin.

 

Интересный origin,

видно от кого _изначально_

В этих спорах часто пропускают довольно важный момент: скорость зависит не только от языков и алгоритмов и т.п - понимание архитектуры тоже очень важно, например предвыборка для больших объёмов памяти...



К слову об архитектуре, не просветите человека из тундры (меня), кто-нибудь сделал на Спеке скроллинг _всего_ экрана вверх за 1/50 сек? Физически это не возможно, а вот практически...

 

Скролинг делал )

Не то что скроллинг ... Экран этот вращать умудрялись хотя на 1/50 это не тянуло (но было где-то близко). Вообще спектрум эту другая тема, проц. не конвеерный вся оптимизация сводиться к тому чтобы размахать программу в памяти и не тратить время на циклы, таблиц всяких в памяти понашлёпать чтобы вычислять поменьше. У меня вообще есть спектрумкие дизасемблеры почти всех программ с E96. Тока я не знаю как их достать с 5 дюймовых дискет. Там есть что почитать. Мне вообще обидно что я в такую глупость вязался. У меня была года два назад прога которая unix-des ломала. На оптимизацию неделю, может больше угрохал. Как миниум в 5 раз лучше оригинала работало. Но винт у меня слишком часто ломается (потёрлось).



Между делом, автор SamInside утверждает что ни один компилятор не сможет упростить (((x)&(y))|((~x)&(z))), до вида ((((y)^(z))&(x))^(z)). Я по правде не поверял что с кодом 7 вижул делает (знаю те кто 6 писал, с асмом местами вообще не дружат). А но мне самому до сих пор не приходилось видеть компилятор, который может изменять формулы с логикой. Даже программы навроде Maple не смогут это сделать правильно (кое что они делают, но немного не то что надо)

 

<font color="gray][ Хорошего! кодера никакой оптимизатор обогнать не сможет. ]</font><!--color-->



Интересно, как это понимать?

Возможно ли задачу оптимизации формализовать, математически поставить, и автоматически решить? Если нет, то почему?



<font color="gray][ с другой стороны сейчас я по уши завален работой ]</font><!--color-->



Ручной оптимизацией программ на ассемблере?



<font color="gray][ ...но мне самому до сих пор не приходилось видеть компилятор, который может... ]</font><!--color-->



А сколько компиляторов было просмотрено?

И каким образом они выбирались?

 

Proteus



Кто там что умудрялся вращать - это другой разговор,

ты на самом деле можешь обработать на 3.5MHz Z80 12Кб за 69888 тактов ???



Интересно, что по этому поводу скажет captain cobalt...





А что до формулы (((x)&(y))|((~x)&(z))) (между делом, зачем так много скобок? imho это говорит о незнании приоритетов операций), дык какой смысл? Ну уберём лишнее действие, зато получим зависимость по данным, а в первоночальном варианте можно параллелить вычисления. (вообще, этот код слишком мал, что бы что-то оценивать, много времени тратится на работу с памятью)

Код (Text):

1. int opt(int x, int y, int z)
2. {
3.     return x & y | ~x & z;// (((x)&(y))|((~x)&(z)));
4. }
5.  
6. ;cl.exe /O2 (MSVC 7.1 / 13.10)
7. mov     edx, [esp]
8. push    esi
9. mov     esi, [esp+8]
10. mov     ecx, [esp+C]
11. mov     eax, ecx
12. not     eax
13. and     ecx, esi
14. and     eax, edx
15. or      eax, ecx
16. pop     esi
17.  
18. ;icl.exe /O2 (intel C++ 8.1)
19. mov     edx, [esp+4]
20. mov     eax, [esp+8]
21. and     eax, edx
22. not     edx
23. and     edx, [esp+C]
24. or      eax, edx

Интересно, что icl в этот же код компилирует и выражение

~(~x | ~y) | ~x & z

 

Да там было что-то такое. Экран перебрасывали. Т.е. они как бы его перебрасывали ))) но в тоже время нет...

Какой-то фокус с развёрткой был... мне сейчас слом подробности искать...

 

Я не знаю зачем так много скобок. Я цитирую как есть. Мало того что помойму он в RFC так и записан со скобками. Да и без разницы, любой даже самый тупейший компилятор скобки замечать не должен. А за листинг вообще спасибо...

Тут насколько я заметил - 4 операци в то время (x&z)^(y&z) это три операции... И вот эту формулу насколько я помню ещё даже спеструмиты в 90-x годах использовади при работе с картиками.



p.s. Хотя интелу я готов простить всё.. Если он работу с массвами умеет переводить в mmx

 

> Ручной оптимизацией программ на ассемблере?



Неа.. на КПК проги. Ассеблировать времени щас вообще нет.



> А сколько компиляторов было просмотрено?

> И каким образом они выбирались?



Вообще мало. Watcom, VC++, GNU и т.д... ты в слова вдумайся. Я не говорю что видел все на свете компиляторы. А говорю что те что попадались, те смотрел.

(но вот товарищи с Inside наверняка видели больше)...

 

ОК.



А как насчёт чисто математической постановки задачи оптимизации и затем её автоматического решения?



Есть какие-нибудь причины, по которым задача может быть "не доступна" для математики?



S_T_A_S_

<font color="gray][ ты на самом деле можешь обработать на 3.5MHz Z80 12Кб за 69888 тактов ???

Интересно, что по этому поводу скажет captain cobalt... ]</font><!--color-->



Если это то, о чём я думаю, то там лишь шесть Кб. Да, фреймовый скролл возможен.

 

Я сейчас точно не помню, но на попытки вывода экрана меньше чем за цикл я потратил много-много часов

Неужели кому-то удалось?



Кстати, как портировать с 5 дюймовых дискет проги на PC?

(вроде прога hobeta должна быть, чтоб дискету переформатнуть)

А то есть своя игрушка, хотел бы показать.

 

Не знаю. У меня впринципе мало что осталось от того творчества. В принципе в любом эмуляторе прочитать. Я короче пробовал что-то достать, не получается. У меня BIOS такой дисковод не переваривает. Надо где-то пятидюймовый на 1.2 мега откапывать..

 

yureckor



Ну... это не совсем то

Как написал captain cobalt,

- то есть на самом деле обрабатыается только половина данных (по 3 кб на чтение и запись) хотя внешне кажется, что все. даже остаётся время на оцифрованную музыку.

Компилятор до такого врядли додумается



Это к слову об оптимизации. Дело вот в чём - даже такая (не совсем честная) техника даёт прирост в всего лишь в 2 раза, но никак не:



Proteus >

 

Попробуй на Си написать шифровальник, который хотя бы в 10 раз медленее SamInside работает.... Или на спектруме экран на большой шарик намотать и повертеть...

Конешно если взять какой-нибудь Anti-Grain Geometry, то работает он быстро. Но всё таки на так быстро как могбы, и то за счёт сильного усложения алгоритмов.



А что там с экраном было я тебе по аське могу рассказать. Фокус на самом деле очень гнустный...