оптимизированный sha1

Тема в разделе "WASM.CRYPTO", создана пользователем zss, 26 дек 2007.

  1. zss

    zss New Member

    Публикаций:
    0
    Регистрация:
    11 июл 2004
    Сообщения:
    40
    Адрес:
    Чехов-2
    помогите пожалуйста найти оптимизированное решение.

    НАшел под MMX
    Код (Text):
    1. // SHA-1 MMX implementation, (C) 2005 Simon Marechal
    2.  
    3. // This code computes two SHA-1 digests at the same time. It
    4. // doesn't take care of padding (0x80 and size << 3), so make
    5. // sure the last input block is properly padded. Both 64-byte
    6. // input blocks must be (four bytes) interleaved.
    7.  
    8. #ifdef __i386__
    9.  
    10. .globl  shammx_init
    11. .globl  shammx_ends;
    12. .globl  shammx_data;
    13.  
    14. .globl _shammx_init;
    15. .globl _shammx_ends;
    16. .globl _shammx_data;
    17.  
    18. .data
    19. .align(16)
    20. const_init_a:
    21. .long 0x67452301
    22. .long 0x67452301
    23. const_init_b:
    24. .long 0xEFCDAB89
    25. .long 0xEFCDAB89
    26. const_init_c:
    27. .long 0x98BADCFE
    28. .long 0x98BADCFE
    29. const_init_d:
    30. .long 0x10325476
    31. .long 0x10325476
    32. const_init_e:
    33. .long 0xC3D2E1F0
    34. .long 0xC3D2E1F0
    35. const_stage0:
    36. .long 0x5A827999
    37. .long 0x5A827999
    38. const_stage1:
    39. .long 0x6ED9EBA1
    40. .long 0x6ED9EBA1
    41. const_stage2:
    42. .long 0x8F1BBCDC
    43. .long 0x8F1BBCDC
    44. const_stage3:
    45. .long 0xCA62C1D6
    46. .long 0xCA62C1D6
    47. const_ff00:
    48. .long 0xFF00FF00
    49. .long 0xFF00FF00
    50. const_00ff:
    51. .long 0x00FF00FF
    52. .long 0x00FF00FF
    53.  
    54. #define ctxa %mm0
    55. #define ctxb %mm1
    56. #define ctxc %mm2
    57. #define ctxd %mm3
    58. #define ctxe %mm4
    59. #define tmp1 %mm5
    60. #define tmp2 %mm6
    61. #define tmp3 %mm7
    62. #define tmp4 ctxa
    63. #define tmp5 ctxb
    64.  
    65. #define F0(x,y,z)       \
    66.         movq   x, tmp2; \
    67.         movq   x, tmp1; \
    68.         pand   y, tmp2; \
    69.         pandn  z, tmp1; \
    70.         por    tmp2, tmp1;
    71.  
    72. #define F1(x,y,z)       \
    73.         movq   z, tmp1; \
    74.         pxor   y, tmp1; \
    75.         pxor   x, tmp1
    76.  
    77. #define F2(x,y,z)       \
    78.         movq   x, tmp1; \
    79.         movq   x, tmp2; \
    80.         pand   y, tmp1; \
    81.         por    y, tmp2; \
    82.         pand   z, tmp2; \
    83.         por    tmp2, tmp1;
    84.        
    85. #define subRoundX(a, b, c, d, e, f, k, data)    \
    86.         f(b,c,d);                               \
    87.         movq   a, tmp2;                         \
    88.         movq   a, tmp3;                         \
    89.         paddd  tmp1, e;                         \
    90.         pslld    $5, tmp2;                      \
    91.         psrld   $27, tmp3;                      \
    92.         por    tmp3, tmp2;                      \
    93.         paddd  tmp2, e;                         \
    94.         movq   b, tmp2;                         \
    95.         pslld  $30, b;                          \
    96.         paddd  k, e;                            \
    97.         psrld  $2, tmp2;                        \
    98.         por    tmp2, b;                         \
    99.         movq   (data*8)(%edx), tmp1;            \
    100.         movq   tmp1, tmp2;                      \
    101.         pand   const_ff00, tmp1;                \
    102.         pand   const_00ff, tmp2;                \
    103.         psrld  $8, tmp1;                        \
    104.         pslld  $8, tmp2;                        \
    105.         por    tmp2, tmp1;                      \
    106.         movq   tmp1, tmp2;                      \
    107.         psrld  $16, tmp1;                       \
    108.         pslld  $16, tmp2;                       \
    109.         por    tmp2, tmp1;                      \
    110.         movq   tmp1, (data*8)(%ecx);            \
    111.         paddd  tmp1, e;
    112.  
    113. #define subRoundY(a, b, c, d, e, f, k, data)    \
    114.         movq   ((data- 3)*8)(%ecx), tmp1;       \
    115.         pxor   ((data- 8)*8)(%ecx), tmp1;       \
    116.         pxor   ((data-14)*8)(%ecx), tmp1;       \
    117.         pxor   ((data-16)*8)(%ecx), tmp1;       \
    118.         movq   tmp1, tmp2;                      \
    119.         pslld    $1, tmp1;                      \
    120.         psrld   $31, tmp2;                      \
    121.         por    tmp2, tmp1;                      \
    122.         movq   tmp1, (data*8)(%ecx);            \
    123.         paddd  tmp1, e;                         \
    124.         f(b,c,d);                               \
    125.         movq   a, tmp2;                         \
    126.         movq   a, tmp3;                         \
    127.         paddd  tmp1, e;                         \
    128.         pslld    $5, tmp2;                      \
    129.         psrld   $27, tmp3;                      \
    130.         por    tmp3, tmp2;                      \
    131.         paddd  tmp2, e;                         \
    132.         movq   b, tmp2;                         \
    133.         pslld  $30, b;                          \
    134.         paddd  k, e;                            \
    135.         psrld  $2, tmp2;                        \
    136.         por    tmp2, b;
    137.  
    138. .text
    139.  
    140. // arg 1 (eax): context (40 bytes)
    141.  
    142.  shammx_init:
    143. _shammx_init:
    144.  
    145.         movq   const_init_a, ctxa
    146.         movq   const_init_b, ctxb
    147.         movq   const_init_c, ctxc
    148.         movq   const_init_d, ctxd
    149.         movq   const_init_e, ctxe
    150.  
    151.         movq   ctxa,  0(%eax)
    152.         movq   ctxb,  8(%eax)
    153.         movq   ctxc, 16(%eax)
    154.         movq   ctxd, 24(%eax)
    155.         movq   ctxe, 32(%eax)
    156.  
    157.         ret
    158.  
    159. // arg 1 (eax): context (40 bytes)
    160. // arg 2 (edx): digests (40 bytes)
    161.  
    162.  shammx_ends:
    163. _shammx_ends:
    164.  
    165.         movq    0(%eax), ctxa
    166.         movq    8(%eax), ctxb
    167.         movq   16(%eax), ctxc
    168.         movq   24(%eax), ctxd
    169.         movq   32(%eax), ctxe
    170.  
    171.         movq   const_ff00, tmp3
    172.         movq   ctxa, tmp1
    173.         movq   ctxb, tmp2
    174.         pand   tmp3, ctxa
    175.         pand   tmp3, ctxb
    176.         movq   const_00ff, tmp3
    177.         pand   tmp3, tmp1
    178.         pand   tmp3, tmp2
    179.         psrld  $8, ctxa
    180.         psrld  $8, ctxb
    181.         pslld  $8, tmp1
    182.         pslld  $8, tmp2
    183.         por    tmp1, ctxa
    184.         por    tmp2, ctxb
    185.         movq   ctxa, tmp1
    186.         movq   ctxb, tmp2
    187.         psrld  $16, ctxa
    188.         psrld  $16, ctxb
    189.         pslld  $16, tmp1
    190.         pslld  $16, tmp2
    191.         por    tmp1, ctxa
    192.         por    tmp2, ctxb
    193.         movq   ctxa,  0(%edx)
    194.         movq   ctxb,  8(%edx)
    195.  
    196.         movq   const_ff00, tmp5
    197.         movq   ctxc, tmp1
    198.         movq   ctxd, tmp2
    199.         movq   ctxe, tmp3
    200.         pand   tmp5, ctxc
    201.         pand   tmp5, ctxd
    202.         pand   tmp5, ctxe
    203.         movq   const_00ff, tmp5
    204.         pand   tmp5, tmp1
    205.         pand   tmp5, tmp2
    206.         pand   tmp5, tmp3
    207.         psrld  $8, ctxc
    208.         psrld  $8, ctxd
    209.         psrld  $8, ctxe
    210.         pslld  $8, tmp1
    211.         pslld  $8, tmp2
    212.         pslld  $8, tmp3
    213.         por    tmp1, ctxc
    214.         por    tmp2, ctxd
    215.         por    tmp3, ctxe
    216.         movq   ctxc, tmp1
    217.         movq   ctxd, tmp2
    218.         movq   ctxe, tmp3
    219.         psrld  $16, ctxc
    220.         psrld  $16, ctxd
    221.         psrld  $16, ctxe
    222.         pslld  $16, tmp1
    223.         pslld  $16, tmp2
    224.         pslld  $16, tmp3
    225.         por    tmp1, ctxc
    226.         por    tmp2, ctxd
    227.         por    tmp3, ctxe
    228.  
    229.         movq   ctxc, 16(%edx)
    230.         movq   ctxd, 24(%edx)
    231.         movq   ctxe, 32(%edx)
    232.  
    233.         ret
    234.  
    235. // arg 1 (eax): context     (40 bytes)
    236. // arg 2 (edx): input data (128 bytes)
    237. // arg 3 (ecx): workspace  (640 bytes)
    238.  
    239.  shammx_data:
    240. _shammx_data:
    241.  
    242.         movq    0(%eax), ctxa
    243.         movq    8(%eax), ctxb
    244.         movq   16(%eax), ctxc
    245.         movq   24(%eax), ctxd
    246.         movq   32(%eax), ctxe
    247.  
    248. round0:
    249.  
    250.         prefetchnta (%edx)
    251.  
    252.         subRoundX( ctxa, ctxb, ctxc, ctxd, ctxe, F0, const_stage0,  0 );
    253.         subRoundX( ctxe, ctxa, ctxb, ctxc, ctxd, F0, const_stage0,  1 );
    254.         subRoundX( ctxd, ctxe, ctxa, ctxb, ctxc, F0, const_stage0,  2 );
    255.         subRoundX( ctxc, ctxd, ctxe, ctxa, ctxb, F0, const_stage0,  3 );
    256.         subRoundX( ctxb, ctxc, ctxd, ctxe, ctxa, F0, const_stage0,  4 );
    257.         subRoundX( ctxa, ctxb, ctxc, ctxd, ctxe, F0, const_stage0,  5 );
    258.         subRoundX( ctxe, ctxa, ctxb, ctxc, ctxd, F0, const_stage0,  6 );
    259.         subRoundX( ctxd, ctxe, ctxa, ctxb, ctxc, F0, const_stage0,  7 );
    260.         subRoundX( ctxc, ctxd, ctxe, ctxa, ctxb, F0, const_stage0,  8 );
    261.         subRoundX( ctxb, ctxc, ctxd, ctxe, ctxa, F0, const_stage0,  9 );
    262.         subRoundX( ctxa, ctxb, ctxc, ctxd, ctxe, F0, const_stage0, 10 );
    263.         subRoundX( ctxe, ctxa, ctxb, ctxc, ctxd, F0, const_stage0, 11 );
    264.         subRoundX( ctxd, ctxe, ctxa, ctxb, ctxc, F0, const_stage0, 12 );
    265.         subRoundX( ctxc, ctxd, ctxe, ctxa, ctxb, F0, const_stage0, 13 );
    266.         subRoundX( ctxb, ctxc, ctxd, ctxe, ctxa, F0, const_stage0, 14 );
    267.         subRoundX( ctxa, ctxb, ctxc, ctxd, ctxe, F0, const_stage0, 15 );
    268.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F0, const_stage0, 16 );
    269.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F0, const_stage0, 17 );
    270.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F0, const_stage0, 18 );
    271.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F0, const_stage0, 19 );
    272.  
    273. round1:
    274.  
    275.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F1, const_stage1, 20 );
    276.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F1, const_stage1, 21 );
    277.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F1, const_stage1, 22 );
    278.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F1, const_stage1, 23 );
    279.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F1, const_stage1, 24 );
    280.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F1, const_stage1, 25 );
    281.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F1, const_stage1, 26 );
    282.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F1, const_stage1, 27 );
    283.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F1, const_stage1, 28 );
    284.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F1, const_stage1, 29 );
    285.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F1, const_stage1, 30 );
    286.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F1, const_stage1, 31 );
    287.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F1, const_stage1, 32 );
    288.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F1, const_stage1, 33 );
    289.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F1, const_stage1, 34 );
    290.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F1, const_stage1, 35 );
    291.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F1, const_stage1, 36 );
    292.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F1, const_stage1, 37 );
    293.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F1, const_stage1, 38 );
    294.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F1, const_stage1, 39 );
    295.  
    296. round2:
    297.  
    298.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F2, const_stage2, 40 );
    299.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F2, const_stage2, 41 );
    300.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F2, const_stage2, 42 );
    301.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F2, const_stage2, 43 );
    302.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F2, const_stage2, 44 );
    303.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F2, const_stage2, 45 );
    304.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F2, const_stage2, 46 );
    305.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F2, const_stage2, 47 );
    306.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F2, const_stage2, 48 );
    307.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F2, const_stage2, 49 );
    308.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F2, const_stage2, 50 );
    309.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F2, const_stage2, 51 );
    310.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F2, const_stage2, 52 );
    311.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F2, const_stage2, 53 );
    312.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F2, const_stage2, 54 );
    313.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F2, const_stage2, 55 );
    314.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F2, const_stage2, 56 );
    315.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F2, const_stage2, 57 );
    316.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F2, const_stage2, 58 );
    317.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F2, const_stage2, 59 );
    318.  
    319. round3:
    320.  
    321.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F1, const_stage3, 60 );
    322.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F1, const_stage3, 61 );
    323.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F1, const_stage3, 62 );
    324.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F1, const_stage3, 63 );
    325.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F1, const_stage3, 64 );
    326.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F1, const_stage3, 65 );
    327.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F1, const_stage3, 66 );
    328.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F1, const_stage3, 67 );
    329.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F1, const_stage3, 68 );
    330.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F1, const_stage3, 69 );
    331.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F1, const_stage3, 70 );
    332.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F1, const_stage3, 71 );
    333.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F1, const_stage3, 72 );
    334.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F1, const_stage3, 73 );
    335.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F1, const_stage3, 74 );
    336.         subRoundY( ctxa, ctxb, ctxc, ctxd, ctxe, F1, const_stage3, 75 );
    337.         subRoundY( ctxe, ctxa, ctxb, ctxc, ctxd, F1, const_stage3, 76 );
    338.         subRoundY( ctxd, ctxe, ctxa, ctxb, ctxc, F1, const_stage3, 77 );
    339.         subRoundY( ctxc, ctxd, ctxe, ctxa, ctxb, F1, const_stage3, 78 );
    340.         subRoundY( ctxb, ctxc, ctxd, ctxe, ctxa, F1, const_stage3, 79 );
    341.  
    342.         paddd    0(%eax), ctxa
    343.         paddd    8(%eax), ctxb
    344.         paddd   16(%eax), ctxc
    345.         paddd   24(%eax), ctxd
    346.         paddd   32(%eax), ctxe
    347.  
    348.         movq    ctxa,  0(%eax)
    349.         movq    ctxb,  8(%eax)
    350.         movq    ctxc, 16(%eax)
    351.         movq    ctxd, 24(%eax)
    352.         movq    ctxe, 32(%eax)
    353.  
    354.         ret
    355.  
    356. #endif
    выигрыш - 2 порядка, но что-то я такого синтаксиса не знаю.
    Можно ли его переписать как под Intel?

    P.S. Хочу использовать как asm вставку для VC
     
  2. Av0id

    Av0id New Member

    Публикаций:
    0
    Регистрация:
    21 окт 2004
    Сообщения:
    87
    синтаксис AT&T, местами операнды меняем, добавляем скобочки где нужно и юзаем

    ps. и где-то я уже видел приведенный в человеческий вид исходник
     
  3. zss

    zss New Member

    Публикаций:
    0
    Регистрация:
    11 июл 2004
    Сообщения:
    40
    Адрес:
    Чехов-2
    Av0id, буду признателен, если найдешь ссылочку :)
     
  4. zss

    zss New Member

    Публикаций:
    0
    Регистрация:
    11 июл 2004
    Сообщения:
    40
    Адрес:
    Чехов-2
    Av0id, поменял, но что-то не все инструкции проглатывает :dntknw:
     
  5. flankerx

    flankerx New Member

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

    yasm понимает AT&T'шный синтаксис, но сначала файлик нужно будет прогнать через сишный препроцессор. Также в сети можно найти конверторы из этого синтаксиса в нормальный NASMовский или MASMовский.
     
  6. Av0id

    Av0id New Member

    Публикаций:
    0
    Регистрация:
    21 окт 2004
    Сообщения:
    87
    ссылку не нашел, но я обычно обхожусь вручную, если очень нужно могу заняться
     
  7. zss

    zss New Member

    Публикаций:
    0
    Регистрация:
    11 июл 2004
    Сообщения:
    40
    Адрес:
    Чехов-2
    Av0id, буду очень признателен :)
     
  8. Av0id

    Av0id New Member

    Публикаций:
    0
    Регистрация:
    21 окт 2004
    Сообщения:
    87
    нашел время и помучал это чудище, тупо скомпилил gcc, рипнул идой, компильнул masm'ом и собрал либу, т.е. код даже не трогал руками, только вот хэши оно выдает неправильные или что-то я не так понял, если кто-нибудь ещё глянет будет замечательно

    в аттаче проект msvs80 + sha1 mmx + sha1 x86 [пишет результат через MessageBox]

    http://slil.ru/25413113
     
  9. Dmit

    Dmit New Member

    Публикаций:
    0
    Регистрация:
    24 окт 2004
    Сообщения:
    17
    Адрес:
    Russia
    "It doesn't take care of padding (0x80 and size << 3), so make sure the last input block is properly padded."
     
  10. Av0id

    Av0id New Member

    Публикаций:
    0
    Регистрация:
    21 окт 2004
    Сообщения:
    87
    dmit, оно уже properly padded если вы не заметили или это не properly по вашему?
     
  11. Dmit

    Dmit New Member

    Публикаций:
    0
    Регистрация:
    24 окт 2004
    Сообщения:
    17
    Адрес:
    Russia
    Это отнюдь не properly.

    Ассемблерный код shammx_data обрабатывает блоки данных размером 64 байта. Так же делает и функция sha_transform(), которая вызывается из sha_update() (через sha_block()) и из sha_final(). Создание properly padded-блока занимает собственно почти всю функцию sha_final(). После хешируемых даных помещается байт со значением 0x80, далее блок дополняется нулями, кроме последних 8 байт, в которые записывается число хешированных бит как 64-битовое значение.

    Таким образом,
    Код (Text):
    1.     sha_init(&sctx);
    2.     sha_update(&sctx,(mutils_word8 *)szVector,128);
    3.     sha_final(&sctx);
    приведет к трем вызовам sha_transform(). В первом и втором обработаются два 64-байтовых блока с символами '0', а в третьем - padding. Стало быть и вызовов shammx_data должно быть три.

    И что-то мне подсказывает, что shammx_data вычисляет два хеша параллельно, а не хеш от двух последовательных блоков. Просто sha_transform(), насколько мне известно, устроена так, что до окончания обработки i-ого блока не получится начать обрабатывать i+1-ый...

    И, кстати, стоит проверить, что там с Byte Ordering - вроде традиционная реализация MD5 байты в каждом DWORD-е переворачивает, про SHA не уверен, но наверняка в нем то же самое. Фраза "Both 64-byte input blocks must be (four bytes) interleaved" как раз про это. Для блоков, заполненных одинаковыми байтами, это не влияет на результат, а padding скорее всего придется переворачивать.
     
  12. Av0id

    Av0id New Member

    Публикаций:
    0
    Регистрация:
    21 окт 2004
    Сообщения:
    87
    мды, а я так надеялся... так надеялся, что все таки properly :) фактически в этом mmx коде не хватает процедуры sha_transform()