Алгоритм Евклида

Тема в разделе "WASM.A&O", создана пользователем volodya, 16 авг 2004.

  1. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Гм, на С пишется просто:


    Код (Text):
    1.  
    2. /* a must be >= b */
    3. unsigned gcd(unsigned a, unsigned b)
    4. {
    5.     while(b)
    6.     {
    7.         unsigned r = a % b;
    8.         a = b;
    9.         b = r;
    10.     }
    11.  
    12.     return a;
    13. }
    14.  




    Компилятор в режиме самой офуительной оптимизации выдал мне сие:


    Код (Text):
    1.  
    2. ; _a$ = eax
    3. ; _b$ = ecx
    4.  
    5. ; 8    :    while(b)
    6.  
    7.     test    ecx, ecx
    8.     je  SHORT $L8421
    9. $L8420:
    10.  
    11. ; 9    :    {
    12. ; 10   :        unsigned r = a % b;
    13.  
    14.     xor edx, edx
    15.     div ecx
    16.  
    17. ; 11   :        a = b;
    18.  
    19.     mov eax, ecx
    20.     test    edx, edx
    21.  
    22. ; 12   :        b = r;
    23.  
    24.     mov ecx, edx
    25.     jne SHORT $L8420
    26. $L8421:
    27.  




    Как по мне, так в test edx, edx/jne SHORT $L8420 нужды нет. Можно было бы просто заменить это jmp. Плоды моих усилий вымучались в:


    Код (Text):
    1.  
    2. unsigned gcd(unsigned a, unsigned b)
    3. {
    4.     unsigned r = 0;
    5.  
    6.     __asm
    7.     {
    8.         mov eax, a
    9.         mov ecx, b
    10. again:
    11.         test ecx, ecx
    12.         je  SHORT end
    13.         xor edx, edx
    14.         div ecx
    15.         mov eax, ecx
    16.         mov ecx, edx
    17.         jmp SHORT again
    18. end:
    19.         mov r, eax
    20.     }
    21.  
    22.     return r;
    23.  
    24. }
    25.  




    Теперь, собственно, упражнение - максимально оптимизировать скорость. Как по мне, так уже больше некуда, но, может, я ошибаюсь?
     
  2. green

    green New Member

    Публикаций:
    0
    Регистрация:
    15 июл 2003
    Сообщения:
    1.217
    Адрес:
    Ukraine
    imho, вот так будет быстрее:
    Код (Text):
    1.  
    2. __declspec(naked)
    3. unsigned int __fastcall gcd(unsigned int a, unsigned int b)
    4. {
    5.     __asm
    6.     {
    7.         mov eax, ecx
    8.      l1:
    9.         cmp eax, edx
    10.         jae l2
    11.         xchg eax, edx
    12.      l2:
    13.         sub eax, edx
    14.         jnz l1
    15.         retn
    16.     }
    17. }
     
  3. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Может и быстрее, но алгоритм не работает :dntknw:

    И первая же инструкция мне не понравилась - ты перетираешь значение а!
     
  4. green

    green New Member

    Публикаций:
    0
    Регистрация:
    15 июл 2003
    Сообщения:
    1.217
    Адрес:
    Ukraine
    прошу прощения, не протестил :)



    Вот так у меня вроде работает:




    Код (Text):
    1.  
    2. __declspec(naked)
    3. unsigned int __fastcall gcd(unsigned int a, unsigned int b)
    4. {
    5.     __asm
    6.     {
    7.         xchg eax, ecx
    8.      l1:
    9.         cmp edx, eax
    10.         jae l2
    11.         xchg edx, eax
    12.      l2:
    13.         sub edx, eax
    14.         jnz l1
    15.         retn
    16.     }
    17. }
     
  5. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    Проверил для 777 и 629, получается 37.

    Медоленные команды не используются.
    Код (Text):
    1.         mov eax, a
    2.         mov ecx, b
    3.  
    4. @@:     mov edx, eax
    5.         sub eax, ecx
    6.         jnc @b
    7.  
    8.         mov eax, ecx
    9.         mov ecx, edx
    10.         jnz @b
    11.  
    12.         mov r, eax
     
  6. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    S_T_A_S_



    Два вопроса.

    1) Чей алгоритм быстрее? Твой или green'a?

    2) Что это за метка "@@"? И где метка "@b"? Ты пользуешься синтаксисом, которого я не знаю :dntknw:
     
  7. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    Сам алгоритм вроде одинаковый, заменили деление вычитанием.



    У меня не используется xchg, которая довольно медленна и не спаривается с другими командами.

    Одна команда проверки условия вместо 2х.

    Нет зависимости по данным, кроме как jnc сразу после sub (зато jnz должен быть предсказан одновременно с jnc).





    "@@" - это просто анонимная локальная метка, "@b" - значит переход на ближайшую "@@" назад (если "@f" - это вперёд).

    Я и забыл, что С регается на символы @ :)
     
  8. Asterix

    Asterix New Member

    Публикаций:
    0
    Регистрация:
    25 фев 2003
    Сообщения:
    3.576
    volodya

    > 2) Что это за метка "@@"? И где метка "@b"? Ты пользуешься синтаксисом, которого я не знаю :dntknw:



    jmp @B или jmp @b - это прыжок назад на ближайшую метку @@:

    jmp @F или jmp @f - тоже самое, но вперед :derisive:



    ЗЫ: нормальный ассемблерный синтаксис.
     
  9. Asterix

    Asterix New Member

    Публикаций:
    0
    Регистрация:
    25 фев 2003
    Сообщения:
    3.576
    Пока писал в оффлайне S_T_A_S_ меня уже опередил :derisive:
     
  10. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Все, понял. Всем спасибо :)
     
  11. cresta

    cresta Active Member

    Публикаций:
    0
    Регистрация:
    13 июн 2004
    Сообщения:
    2.257
    S_T_A_S_



    Твой алгоритм вычисляет наибольший общий делитель, но зацикливается после его нахождения. Вот так работает, правда две команды плюс:
    Код (Text):
    1.     mov eax, 10557
    2.     mov ecx, 1530
    3.  
    4. @@: cmp eax,ecx
    5.     je short Exit
    6.     mov edx, eax
    7.     sub eax, ecx
    8.     jnc @B
    9.  
    10.     mov eax, ecx
    11.     mov ecx, edx
    12.     jnz @B
    13. Exit:
     
  12. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    cresta



    Мог бы и добавить, что ответ в eax :|>



    А от
    Код (Text):
    1.  
    2. @@: cmp eax,ecx
    3.     je short Exit
    4.  


    избавиться нельзя? Мне не нравится.
     
  13. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    Ой млин.. точно, спасибо :)

    косячный вариант запостил :dntknw:



    Правильно так:
    Код (Text):
    1.         mov eax, a
    2.         mov ecx, b
    3.  
    4. @@:     mov edx, eax
    5.         sub eax, ecx
    6.         ja  @b
    7.  
    8.         mov eax, ecx
    9.         mov ecx, edx
    10.         jnz @b
    11.  
    12.         mov r, eax
     
  14. cresta

    cresta Active Member

    Публикаций:
    0
    Регистрация:
    13 июн 2004
    Сообщения:
    2.257
    А алгоритм green'a для некоторых пар чисел выдаёт ошибочный результат. Я так понял, это зависит от содержимого edx. Если его обнулить перед циклом, то вообще зацикливается. Нельзя ли уточнить, что должно быть в регистре edx перед выполнением цикла?
     
  15. green

    green New Member

    Публикаций:
    0
    Регистрация:
    15 июл 2003
    Сообщения:
    1.217
    Адрес:
    Ukraine
    а вот так алгоритм S_T_A_S_

    можно в С-код впаять:


    Код (Text):
    1. __declspec(naked)
    2. unsigned int __fastcall gcd(unsigned int a, unsigned int b)
    3. {
    4.     __asm
    5.     {
    6.     l:
    7.             mov eax, edx
    8.             sub edx, ecx
    9.             ja l
    10.  
    11.             mov edx, ecx
    12.             mov ecx, eax
    13.             jnz l
    14.             ret
    15.     }
    16. }
     
  16. green

    green New Member

    Публикаций:
    0
    Регистрация:
    15 июл 2003
    Сообщения:
    1.217
    Адрес:
    Ukraine
    cresta

    через регистры ecx и edx передаются значения a и b
     
  17. cresta

    cresta Active Member

    Публикаций:
    0
    Регистрация:
    13 июн 2004
    Сообщения:
    2.257
    green



    Да теперь всё стало на место. Просто volodya изначально передавал через eax/ecx, поэтому подумал, что и у тебя тоже. Усё работает.
     
  18. volodya

    volodya wasm.ru

    Публикаций:
    0
    Регистрация:
    22 апр 2003
    Сообщения:
    1.169
    Единственное что, я слабо понимаю


    Код (Text):
    1. __declspec(naked) unsigned int __fastcall




    Зачем использовать ДВЕ конвенции о вызовах? Мало fastcall? А вообще (и правильнее!) заменять это на


    Код (Text):
    1. static inline




    inline - ежику понятно. static - это то, что надо линкеру, чтобы не искал внешних ссылок. Глянь в коды линухи - там все функции через static.
     
  19. green

    green New Member

    Публикаций:
    0
    Регистрация:
    15 июл 2003
    Сообщения:
    1.217
    Адрес:
    Ukraine
    volodya

    1) __declspec(naked) - это фича компилятора MS.

    Она указывает, что компилятор не должен генерировать никакой отсебятины для ф-ции -- всякие прологи/эпилоги т.е. В данном случае они (прологи/эпилоги) не нужны, и задача ставилась - оптимизировать по скорости.



    2) __fastcall - конвенция передачи параметров в ф-цию:

    первые 2 параметра передаются через ecx и edx, остальные - через стек.

    С __declspec(naked) это не связано.



    Да, на данном этапе оптимизации возможно уже есть смысл сделать это ф-цию inline. Тогда в самом деле и naked и __fastcall лишние.
     
  20. dmit10

    dmit10 New Member

    Публикаций:
    0
    Регистрация:
    25 окт 2004
    Сообщения:
    37
    Адрес:
    Russia
    Вы Кнута читали? Там что-то, вроде нечто:



    Вход eax,ebx

    Выход eax



    mov ecx,1



    next_step:

    test eax,eax

    jz end_loop



    test ebx,ebx

    jz end_loop



    test eax,1

    jnz eax_nechet

    shr eax,1



    test ebx,1

    jnz next_step

    shr ebx,1

    shl ecx,1

    jmp next_step



    eax_nechet:

    test ebx,1

    jnz ebx_nechet

    shr ebx,1

    jmp next_step

    ebx_nechet:

    sub eax,ebx

    jns next_step

    neg eax

    jmp next_step

    end_loop:



    sub eax,ebx

    mul ecx