Навеяло сокетами. Спеслистам по сокетам, сервлетам ...

[vg]

Иногда, при решении сетевых задач, необходимо уметь работать или с сырыми сокетами, или уметь анализировать входящий поток байт на сетевом интерфейсе. Один из вопросов, который на мой взгляд не нашёл освещения в инете – это достаточно внятное объяснение сути алгоритма, используемого при подсчёте контрольных сумм в заголовках ip, tcp (а в настоящее время и udp). RCF - дают только вербальные определения. Интересно здесь само определение и мат. обоснование алгоритмов. Насколько этот правильно с мат. точки зрения? Где опубликованы статьи, может тех. отчёты? Кто придумал эти алгоритмы? Может откуда-то взаимствовали? Может там и нет математики вовсе, а есть некое обоснование, которое было, например, у Беллмана для задач динамического программирования? Т.е. обоснования нет – а всё работает;))))

Почему я задаю, эти вопросы? Потому, что понимание алгоритма позволяет программировать ЭТО в любых ситуациях, извините за банальность. Может показаться, что существующих реализаций уже достаточно, чтобы не учитывать особенности алгоритма вовсе. Это не так.
Например, вот одна из профессиональных реализаций (кстати, она не работает;))))). Привожу её потому, что это пропостил один из буржуйских гуру.

Код: Выделить всё

u_short checksum(u_short * data,u_short length)
{
        register long value;
        u_short i;

        for(i=0;i<(length>>1);i++)
                value+=data[i];

        if((length&1)==1)
                value+=(data[i]<<8);

        value=(value&65535)+(value>>16);

        return(~value);
}

Вот другая реализация от *никсов

Код: Выделить всё

/*
* in_cksum --
* Checksum routine for Internet Protocol family headers (C Version)
*/
int
in_cksum(addr, len)
u_short *addr;
int len;
{
int nleft = len;
u_short *w = addr;
int sum = 0;
u_short answer = 0;
/*
* Our algorithm is simple, using a 32 bit accumulator (sum), we add
* sequential 16 bit words to it, and at the end, fold back all the
* carry bits from the top 16 bits into the lower 16 bits.
*/
while (nleft > 1) {
sum += *w++;
nleft -= 2;
}
/* mop up an odd byte, if necessary */
if (nleft == 1) {
*(u_char *)(&answer) = *(u_char *)w ;
sum += answer;
}
/* add back carry outs from top 16 bits to low 16 bits */
sum = (sum >> 16) + (sum & 0xffff); /* add hi 16 to low 16 */
sum += (sum >> 16); /* add carry */
answer = ~sum; /* truncate to 16 bits */
return(answer);
}

Вот реализация, которую использую я, и которая, как не странно работает и для 16- и для 32-битных компиллеров (здесь мне немного смешно, т.к. творчески переделав код одного из программера – добавил #ifdef _32BIT_ и далее …., написав и протестировав когда-то ЭТО, я сам до конца так и не понял – как это работает;))) ).

Код: Выделить всё

ushort net_checksum( void *data, size_t len )
{
ulong sum = 0;
int words = len >> 1;
#ifdef _32BIT_
  unsigned short int * dp =  ( unsigned short int *) data;
  unsigned short int sum_s;
#else
  ushort *dp =  (ushort *) data;
  ushort sum_s;
#endif

while( words -- )
  sum += * dp ++;

if( len & 1 )
sum += *(uchar*) dp;

#ifdef  _32BIT_
  sum   = (unsigned short int) sum + (sum >> 16) & 0xffff;
  sum_s = (unsigned short int) sum + (unsigned short int)(sum >> 16);
#else
  sum   = (ushort) sum + (sum >> 16) & 0xffff;
  sum_s = (ushort) sum + (ushort)(sum >> 16);
#endif

return sum_s != 0xffff ? ~sum_s : sum_s;
}

С вопросом об алгоритме здесь надо б определиться. Это важно, поскольку используется ОНО и сетевыми протоколами и сетевым транспортом. Да и для кругозора пользительно.

ПС.
Если кто может объяснить суть алгоритма, дать ссылки на его обоснование – будет полезно и спасибо.
А ну-ка гуру - покажись!!!

[Marmot]

А что, sources Linuxa или BSD там у вас в Мухосранске взять негде?

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

А примерчик таких задач можно?

ЗЫ Я не гуру в этом вопросе, и поэтому ну совсем не могу понять нафига это надо в случае обычного application-a.
Я так понимаю, не firewall же вы там пишите...

[vg]

2Marmot,
про внимательность и невнимательность.

Думаю, что в других Мухосрансках (конечно, это не про тебя), в том числе зарубежных, не очень внимательно читают постинги. Ибо желание отметить Мухосранск таковым - всегда преобладает.
Пережитки совка....да и только.
К чему это? К тому, что выше я пропостил и юниховую реализацию, которая кочует от версии к версии (так говорят Мухосранские гуру). Внимательным надо б быть.

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

[Marmot]

2Marmot,
про внимательность и невнимательность.

Думаю, что в других Мухосрансках (конечно, это не про тебя), в том числе зарубежных, не очень внимательно читают постинги. Ибо желание отметить Мухосранск таковым - всегда преобладает.
Пережитки совка....да и только.
К чему это? К тому, что выше я пропостил и юниховую реализацию, которая кочует от версии к версии (так говорят Мухосранские гуру). Внимательным надо б быть.

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

Согласен, был неправ, каюсь...
Поспешил, людей насмешил