Навеяло сокетами. Спеслистам по сокетам, сервлетам ...
Добавлено: 10 ноя 2003, 14:57
Иногда, при решении сетевых задач, необходимо уметь работать или с сырыми сокетами, или уметь анализировать входящий поток байт на сетевом интерфейсе. Один из вопросов, который на мой взгляд не нашёл освещения в инете – это достаточно внятное объяснение сути алгоритма, используемого при подсчёте контрольных сумм в заголовках ip, tcp (а в настоящее время и udp). RCF - дают только вербальные определения. Интересно здесь само определение и мат. обоснование алгоритмов. Насколько этот правильно с мат. точки зрения? Где опубликованы статьи, может тех. отчёты? Кто придумал эти алгоритмы? Может откуда-то взаимствовали? Может там и нет математики вовсе, а есть некое обоснование, которое было, например, у Беллмана для задач динамического программирования? Т.е. обоснования нет – а всё работает;))))
Почему я задаю, эти вопросы? Потому, что понимание алгоритма позволяет программировать ЭТО в любых ситуациях, извините за банальность. Может показаться, что существующих реализаций уже достаточно, чтобы не учитывать особенности алгоритма вовсе. Это не так.
Например, вот одна из профессиональных реализаций (кстати, она не работает;))))). Привожу её потому, что это пропостил один из буржуйских гуру.
Вот другая реализация от *никсов
Вот реализация, которую использую я, и которая, как не странно работает и для 16- и для 32-битных компиллеров (здесь мне немного смешно, т.к. творчески переделав код одного из программера – добавил #ifdef _32BIT_ и далее …., написав и протестировав когда-то ЭТО, я сам до конца так и не понял – как это работает;))) ).
С вопросом об алгоритме здесь надо б определиться. Это важно, поскольку используется ОНО и сетевыми протоколами и сетевым транспортом. Да и для кругозора пользительно.
ПС.
Если кто может объяснить суть алгоритма, дать ссылки на его обоснование – будет полезно и спасибо.
А ну-ка гуру - покажись!!!
Почему я задаю, эти вопросы? Потому, что понимание алгоритма позволяет программировать ЭТО в любых ситуациях, извините за банальность. Может показаться, что существующих реализаций уже достаточно, чтобы не учитывать особенности алгоритма вовсе. Это не так.
Например, вот одна из профессиональных реализаций (кстати, она не работает;))))). Привожу её потому, что это пропостил один из буржуйских гуру.
Код: Выделить всё
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);
}Код: Выделить всё
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;
}ПС.
Если кто может объяснить суть алгоритма, дать ссылки на его обоснование – будет полезно и спасибо.
А ну-ка гуру - покажись!!!
Ибо желание отметить Мухосранск таковым - всегда преобладает.
