Оптимизация перестановки бит по таблице

Тема в разделе "WASM.A&O", создана пользователем SteelRat, 17 дек 2004.

  1. SteelRat

    SteelRat New Member

    Публикаций:
    0
    Регистрация:
    26 авг 2004
    Сообщения:
    409
    В алгоритме DES есть перестановка бит по таблице (1 блок 64 бита)
    Код (Text):
    1.  
    2.     ;
    3.     ; Ф-ция берет бит в блоке и возвращает 0 или 1 в eax
    4.     ;
    5. DesGetBit proc uses ecx edx pBlock:PVOID, Pos:DWORD
    6.     ;
    7.     mov edx, pBlock
    8.     .if Pos<=32
    9.         mov eax, (_LARGE_INTEGER PTR [edx]).LowPart
    10.     .else
    11.         mov eax, (_LARGE_INTEGER PTR [edx]).HighPart
    12.         sub Pos, 32
    13.     .endif
    14.     mov ecx, Pos
    15.     clc
    16.     shr eax, cl
    17.     jnc dgbNotSet
    18.     mov eax, 1
    19.     jmp dgbContinue
    20. dgbNotSet:
    21.     xor eax, eax
    22. dgbContinue:
    23.     ;
    24.     ret
    25.     ;
    26. DesGetBit endp
    27.  


    Это слишком долго :dntknw: У кого есть соображения как позицию бита вычислить быстрее ?
     
  2. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    SteelRat

    В приведенном коде явно лишнее:

    1) clc не нужно (на P4 очень медленная)

    2) после shr никакие переходы не нужны, если Pos в диапазоне 0..63 (если нет, нужно сделать декремент)
    Код (Text):
    1.     shr eax,cl
    2.     and eax,1
    В первой проверке для исключения переходов можно использовать SETcc и\или CMOVcc (условный мув только для PII и выше). Вот только сходу у меня "изящного" варианта не получается - надо помозговать.



    А вот вариант с MMX без переходов:
    Код (Text):
    1.     ;edx - pBlock
    2.     ;ecx - Pos=0..63, если же 1..64, то нужно dec ecx
    3.     movq mm0,[edx]
    4.     movd mm1,ecx
    5.     psrlq mm0,mm1
    6.     movd eax,mm0
    7.     and eax,1
     
  3. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    3) вычисление бита может произойти быстрее, чем "один push и pop", т.ч. оформление этого кода в виде процедуры с переходами признак плохой реализации хорошего криптоалгоритма
     
  4. SteelRat

    SteelRat New Member

    Публикаций:
    0
    Регистрация:
    26 авг 2004
    Сообщения:
    409
    Да, это круто почему-то я все время забываю про MMX...

    Спасибо :)
     
  5. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    Вот такой вариантик с SETcc пришел на ум (Pos = 0..63)
    Код (Text):
    1.     delta: dd 0, 32
    2. ..................................
    3.     xor eax,eax
    4.     cmp ecx,32
    5.     setge al
    6.     sub ecx,[delta+eax*4]
    7.     mov eax,[edx+eax*4]
    8.     shr eax,cl
    9.     and eax,1
     
  6. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    В последнем варианте можно BT и SETC AL использовать вместо последних 2х команд. Не знаю только, что на PIV быстрее будет.. на athlon для скорости нужно из памяти в регистр операнд BT считывать, иначе можно было бы совсем 2мя командами обойтись.
     
  7. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    Ну вот, помозговал малость. Вычитание ecx-32 по условию это излишество, т.к. SHR берет CL по модулю 32.

    Вот еще несколько вариантов как обойти переходы (мож кому пригодиться "для коллекции"):

    (edx - указатель на число Int64, ecx - Pos=0..63)

    1) SETcc:
    Код (Text):
    1.     xor eax,eax
    2.     test cl,32
    3.     setne al
    4.     <font color="gray];and cl,31 - это лишнее</font><!--color-->
    5.     mov eax,[edx+eax*4]
    6.     shr eax,cl
    7.     and eax,1
    2) CMOVcc (только для PII и выше)
    Код (Text):
    1.     mov eax,[edx]
    2.     test cl,32
    3.     cmovne eax,[edx+4]
    4.     <font color="gray];and cl,31 - это лишнее</font><!--color-->
    5.     shr eax,cl
    6.     and eax,1
    3) MOVZX
    Код (Text):
    1.     add ecx,0E0h  ;если >= 32 будет перенос в CH
    2.     movzx eax,ch
    3.     <font color="gray];and cl,31 - это лишнее</font><!--color-->
    4.     mov eax,[edx+eax*4]
    5.     shr eax,cl
    6.     and eax,1
    4) СDQ - проигрывает всем предыдущим как на P6 family, так и на P4, а посему не приводится



    Приблизительный рейтинг:
    Код (Text):
    1. Метод  PIII        PIV     PIV без and cl,31
    2. -----   ----        ----        ---------------
    3. MMX 58      136     136
    4. SETcc   78      160     164
    5. CMOVcc  76      148<font color="gray];184</font><!--color-->        148
    6. MOVZX   66<font color="gray] ;124</font><!--color-->        148     144
    7. CDQ 132     196


    ПОПРАВИЛ: AND cl,31 не нужно, т.к. это делается автоматом в SHR. Теперь в табличке результаты без AND, а через точку с запятой с AND. Цифры это примерное число тактов на цикл из 16.
     
  8. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    0...63
    Код (Text):
    1. mov     eax,dword [edx]
    2. shr     eax,cl
    3. mov     edx,dword [edx+4]
    4. shr     edx,cl
    5. shr     ecx,5
    6. and     eax,1
    7. and     edx,ecx
    8. or      eax,edx
    RDTSC говорит 4 такта на PIII, твои примерно тоже, а ммх 3 такта
     
  9. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    Народ! Есть же спец.тулзы, зачем измерять всё "в попугаях" ?!

    Вот картина для athlon XP



    Кстати, видно, что BT вполне неплоха без всякой обвязки.





    [​IMG] 296696783__get_bit.PNG
     
  10. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
  11. Asterix

    Asterix New Member

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

    > зачем измерять всё "в попугаях"



    А я вот что-то "в pipeline'ах" ничего не понял, и описалово не помогло %)
     
  12. Broken Sword

    Broken Sword Robert

    Публикаций:
    0
    Регистрация:
    30 авг 2002
    Сообщения:
    433
    мне просто интересно - где ты нашел в DES-е перестановку по P-блокам с 64-битовым входом, всегда был 32 бита (?)
     
  13. n0p

    n0p 10010000b

    Публикаций:
    0
    Регистрация:
    7 май 2003
    Сообщения:
    256
    Адрес:
    Новосиbeerск
    S_T_A_S_





    Так нормально?
     
  14. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    Я конечно в очередной раз "тормознул" и насовал во все варианты and cl,31, хотя все это делается автоматом в SHR. Пришлось подправить предыдущий пост.



    bogrus

    Твой вариант на P4 (модель 2 Northwood) получается довольно тормозным (280 попугаев по приведенной мной табличке). На 3й модели (Prescott) возможно будет лучше (там якобы SHR за 1 такт, зато ALU тоже 1 такт вместо 0.5).



    S_T_A_S_

    1) Честно, говоря BT давно не пользовался и у меня из головы вылетело, что BT m,r может работать с любыми смещениями. Код конечно простой из двух строчек BT+SETcc, но на P4 это получается очень тормозной вариант (в моих попугаях 300 против ~150 -160).



    2) Сочетание BT r,r + SETcc на P4 получается по задержке на 1-2 такта хуже SHR (1 если убрать and eax,1 хотя по условию результат д.б. в EAX, а не AL). Кстати на твоих диаграммах эти инструкции вообще идут в параллель без смещения - это что-то типа слияния (fusion) инструкций на Pentium M ?.



    3) Диаграмы это "весчь". Но возникает пара вопросов (это особенности атлона или ???):

    a) получается что cpuid может переставляться с другими инструкциями - ее выполнение может начинаться раньше других (интелы уверяют нечто обратное или я их неверно понимаю) - тогда wintest-ы Агнера и bogrus могут сильно ошибаться ?

    b) почему так сравнительно долго выполняются MMX инструкции ? Как это объяснить - особенностью атлона или мы с bogrus неверно попугаи подсчитываем ? Даже если смотреть по началу cpuid, то на диаграмме все-равно MMX получается хуже остальных. А наши попугаи на пеньках показывают обратное.



    n0p > "Так нормально?"

    Пойдет, хотя пока речь идет не о перестановке по таблице, а только о BitTest для Int64.
     
  15. SteelRat

    SteelRat New Member

    Публикаций:
    0
    Регистрация:
    26 авг 2004
    Сообщения:
    409
    Broken Sword

    В DES стандарте перестановка в 64-битовом блоке
    Код (Text):
    1.  
    2. IP  db  58, 50, 42, 34, 26, 18, 10, 02
    3.     db  60, 52, 44, 36, 28, 20, 12, 04
    4.     db  62, 54, 46, 38, 30, 22, 14, 06
    5.     db  64, 56, 48, 40, 32, 24, 16, 08
    6.     db  57, 49, 41, 33, 25, 17, 09, 01
    7.     db  59, 51, 43, 35, 27, 19, 11, 03
    8.     db  61, 53, 45, 37, 29, 21, 13, 05
    9.     db  63, 55, 47, 39, 31, 23, 15, 07
    10.  


    А потом делтся пополам :) по 32 бита
     
  16. Broken Sword

    Broken Sword Robert

    Публикаций:
    0
    Регистрация:
    30 авг 2002
    Сообщения:
    433
    а ты это хочешь оптимизировать? :) так бы сразу и сказал. могу предложить тебе лучший вариант оптимизации этого куска: выкинь его к чертям собачим. Начальная (и конечная) перестановки НИКАК не влияют на стойкость DES, и нужна была она для реализации в аппаратуре образца 80х годов, которую уже 15 лет не выпускают
     
  17. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    Asterix >




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

    Потом можно переставлять команды местами и сравнивать.





    Видно, что наиболее быстрые из протестированных - вариант bogrus и использование BT + "обвязка".





    leo >




    Это не мои, а AMD CodeAnalyst'а диаграммы :)

    Хто его знает, что это такое - факт имеет место быть на практике, зачем тут теории..



    >




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



    >




    А почему нет? Если замерить время выполнения 20000 nop'ов, и поделить на 20000, то будет ли результат временем ваполнения одной команды ?



    >




    У AMD инструкции вида MOVD mmreg, reg32 относятся к категории VectorPatch, т.е. они не могут выполняться одновременно с другими. Хотя Execute Latency - 3 такта. К тому же попугаи показывают время ваполнения таких команд в цикле.





    В дополнение - не только
    , но ещё и оформление этого кода в виде отдельной (не inline) процедуры - то же, поскольку call / ret - тяжёлые команды.
     
  18. SteelRat

    SteelRat New Member

    Публикаций:
    0
    Регистрация:
    26 авг 2004
    Сообщения:
    409
    S_T_A_S_ но ещё и оформление этого кода в виде отдельной (не inline) процедуры - то же, поскольку call / ret - тяжёлые команды.

    Просто предпочитаю сначала написАть черновик, потом оптимизировать, согласно одной из статей на WASM :)

    Broken Sword

    Буду благодарен, а по перестановке заметил, что если одинаковые байты напимер 04141414141414141h, то получаем 0FF0000FF00000000h :) наш ГОСТ в этом плане намного практичнее, там нет работы с битами, думаю на IA64 платформе его реализовать - "читый мёд"
     
  19. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine




    Вот с MMX ничерта не пойму, написано, что почти каждая занимает по такту, rdtsc тоже подтверждает, а на картинке (get_bit.PNG) так тормозные?
     
  20. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    если интересует _только_ перстановка для DES, то её можно выполнить проще и без MMXов.



    Выдержка из одного из OpenSSLовских заголовков:


    Код (Text):
    1.  
    2. /*
    3. The main trick is to remember that
    4. t=((l>>size)^r)&(mask);
    5. r^=t;
    6. l^=(t<<size);
    7. can be used to swap and move bits between words.
    8.  
    9. Thanks for hints from Richard Outerbridge - he told me IP&FP could be done in 15 xor, 10 shifts and 5 ands.
    10. When I finally started to think of the problem in 2D I first got ~42 operations without xors.  When I emembered
    11. how to use xors :-) I got it to its final state.
    12. */
    13.  
    14. #define PERM_OP(a,b,t,n,m) ((t)=((((a)>>(n))^(b))&(m)),\
    15.     (b)^=(t),\
    16.     (a)^=((t)<<(n)))
    17.  
    18. #define IP(l,r) \
    19.     { \
    20.     register DES_LONG tt; \
    21.     PERM_OP(r,l,tt, 4,0x0f0f0f0fL); \
    22.     PERM_OP(l,r,tt,16,0x0000ffffL); \
    23.     PERM_OP(r,l,tt, 2,0x33333333L); \
    24.     PERM_OP(l,r,tt, 8,0x00ff00ffL); \
    25.     PERM_OP(r,l,tt, 1,0x55555555L); \
    26.     }
    27.  
    28. #define FP(l,r) \
    29.     { \
    30.     register DES_LONG tt; \
    31.     PERM_OP(l,r,tt, 1,0x55555555L); \
    32.     PERM_OP(r,l,tt, 8,0x00ff00ffL); \
    33.     PERM_OP(l,r,tt, 2,0x33333333L); \
    34.     PERM_OP(r,l,tt,16,0x0000ffffL); \
    35.     PERM_OP(l,r,tt, 4,0x0f0f0f0fL); \
    36.     }
    37.