Подсчёт контрольной суммы UDP

Тема в разделе "WASM.NETWORKS", создана пользователем PavPS, 14 сен 2006.

  1. PavPS

    PavPS New Member

    Публикаций:
    0
    Регистрация:
    24 фев 2004
    Сообщения:
    109
    Адрес:
    Russia
    Здравствуйте уважаемые!

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

    Нужен именно оптимизированный по скорости алгоритм. Если на ассемблере, то просто супер!!!

    С огромным уважением и заранее благодарен, PavPS.
     
  2. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    На атлонеХР для блоков 1-64 Кб получается примерно 0.55-0.6 такта/байт:
    Код (Text):
    1. sum:;(ptr +4, len +8)
    2.     mov esi,[esp+4] ;ptr
    3.     mov ecx,[esp+8] ;len
    4.     xor eax,eax
    5.     shr ecx,1
    6.     jnc .l0
    7.     add al,[esi+ecx*2]
    8.   .l0:
    9.     shr ecx,1
    10.     jnc .l2
    11.     add ax,[esi+ecx*4]
    12.     adc ax,0
    13.   .l2:
    14.     shr ecx,1
    15.     jnc .l3
    16.     add eax,[esi+ecx*8]
    17.     adc eax,0
    18.   .l3:
    19.     jecxz .exit
    20.   .l1:
    21.     adc eax,[esi+ecx*8-8]
    22.     adc eax,[esi+ecx*8-4]
    23.     loop .l1
    24.     adc eax,0
    25.   .exit: ; метка должна быть здесь!!!
    26.     mov edx,eax
    27.     shr eax,16
    28.     add ax,dx
    29.     adc ax,0
    30. ;   .exit: а не здесь
    31.     ret 8
    Еще есть MMX вариант, но он в два с половиной раза хуже:
    Код (Text):
    1. summmx:
    2.     mov esi,[esp+4]
    3.     mov ecx,[esp+8]
    4.     pxor mm0,mm0
    5.     pxor mm1,mm1
    6.     pxor mm7,mm7
    7.     shr ecx,2
    8.   .l0:
    9.     paddd mm0,mm1
    10.     movd mm1,[esi]
    11.     add esi,4
    12.     punpcklwd mm1,mm7
    13.     loop .l0
    14.     paddd mm0,mm1
    15.     sub esp,8
    16.     movq [esp],mm0
    17.     pop edx
    18.     pop eax
    19.     add eax,edx
    20.     mov edx,eax
    21.     shr eax,16
    22.     add ax,dx
    23.     adc ax,0
    24.     ret 8
    Работает только с блоками кратными двойному слову размером не более 65535 двойных слов. Если переписать для SSE2 и малость развернуть цикл, то может он и догонит первый вариант.

    Исправлено: первый вариант не правильно обрабатывал блоки длиной 4-7 байт.
     
  3. PavPS

    PavPS New Member

    Публикаций:
    0
    Регистрация:
    24 фев 2004
    Сообщения:
    109
    Адрес:
    Russia
    Огромное спасибо!
     
  4. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Теперь MMX вариант стал самым быстрым - 0.46-0.5 тактов/байт:
    Код (Text):
    1. summmx:
    2.     mov esi,[esp+4]
    3.     mov ecx,[esp+8]
    4.     shr ecx,4
    5.     movq mm7,qword [.c8000]
    6.     movq mm0,mm7
    7.     movq mm2,mm7
    8.     .l0:
    9.     movq mm1,[esi]
    10.     movq mm3,[esi+8]
    11.     paddw mm0,mm1
    12.     paddw mm2,mm3
    13.     pxor mm1,mm7
    14.     pxor mm3,mm7
    15.     pcmpgtw mm1,mm0
    16.     pcmpgtw mm3,mm2
    17.     psubw mm0,mm1
    18.     psubw mm2,mm3
    19.     add esi,16
    20.     loop .l0
    21.     pxor mm2,mm7
    22.     paddw mm0,mm2
    23.     pxor mm2,mm7
    24.     pcmpgtw mm2,mm0
    25.     psubw mm0,mm2
    26.     pxor mm0,mm7
    27.  
    28.     sub esp,8
    29.     movq [esp],mm0
    30.     pop edx
    31.     pop eax
    32.     add eax,edx
    33.     adc eax,0
    34.     mov edx,eax
    35.     shr eax,16
    36.     add ax,dx
    37.     adc ax,0
    38.     ret 8
    39. .c8000  dw $8000,$8000,$8000,$8000
    Если переписать под SSE2, то ускорение будет еще в два раза.
     
  5. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    SSE2 позволил удвоить скорость на больших массивах помещающихся в кеш:
    Код (Text):
    1. sumsse2:;(buf +4, len +8)
    2.         mov edx,[esp+4]
    3.         mov eax,31
    4.         sub eax,[esp+8]
    5.         mov ecx,eax
    6.         and eax,31
    7.         sub ecx,eax
    8.         movdqu xmm0,[.mask+eax]
    9.         movdqu xmm2,[.mask+eax+16]
    10.         sub edx,ecx
    11.         pand xmm0,[edx]
    12.         pand xmm2,[edx+16]
    13.         jecxz .exit
    14.         movdqu xmm7,dqword [.hbit]
    15.         pxor xmm0,xmm7
    16.         pxor xmm2,xmm7
    17.     .loop:
    18.         movdqa xmm1,[edx+ecx]
    19.         movdqa xmm3,[edx+ecx+16]
    20.         paddd xmm0,xmm1
    21.         paddd xmm2,xmm3
    22.         pxor xmm1,xmm7
    23.         pxor xmm3,xmm7
    24.         pcmpgtd xmm1,xmm0
    25.         pcmpgtd xmm3,xmm2
    26.         psubd xmm0,xmm1
    27.         psubd xmm2,xmm3
    28.         add ecx,32
    29.         jnz .loop
    30.         pxor xmm0,xmm7
    31.         pxor xmm2,xmm7
    32.     .exit:
    33.         sub esp,32
    34.         movdqu [esp],xmm0
    35.         movdqu [esp+16],xmm2
    36.         pop eax
    37.         mov ecx,7
    38.     .add:
    39.         pop edx
    40.         adc eax,edx
    41.         loop .add
    42.         adc eax,0
    43.         shld edx,eax,16
    44.         add ax,dx
    45.         adc ax,0
    46.         movzx eax,ax
    47.         ret 8
    48.  
    49.     .hbit dd 80000000h,80000000h,80000000h,80000000h
    50.        
    51.     .mask: times 31 db -1
    52.         times 32 db 0
     
  6. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    Этого к щастью хватит. Длина udp описывается двумя байтами. Больше 65535 не влезет))