Date: Wed, 15 Nov 2000 17:40:31 +0200 From: Ruslan Ermilov <ru@FreeBSD.ORG> To: Julian Elischer <julian@elischer.org>, Charles Mott <cmott@scientech.com>, Archie Cobbs <archie@dellroad.org>, net@FreeBSD.ORG, Ari Suutari <ari@suutari.iki.fi> Subject: Re: libalias: Incremental Update of Internet Checksum Message-ID: <20001115174031.A10161@sunbay.com> In-Reply-To: <20001115162615.A3145@sunbay.com>; from ru@FreeBSD.ORG on Wed, Nov 15, 2000 at 04:26:15PM %2B0200 References: <Pine.BSF.4.21.0011122254240.50684-100000@carcassonne.scientech.com> <Pine.BSF.4.21.0011130015100.50906-100000@carcassonne.scientech.com> <20001113103852.E34671@sunbay.com> <3A126F63.8EB0D49@elischer.org> <20001115150433.A98014@sunbay.com> <3A1295DE.6930D125@elischer.org> <20001115162615.A3145@sunbay.com>
next in thread | previous in thread | raw e-mail | index | archive | help
--fdj2RfSjLxBAspz7 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline On Wed, Nov 15, 2000 at 04:26:15PM +0200, Ruslan Ermilov wrote: [...] > > I went further, and wrote another test program that demonstrates that > both implementation for formula 4 I posted at the very beginning, and > the current version in libalias(3) produce wrong results in some cases. > By "wrong" here I mean really wrong results, not the 0 -> 0xffff case. > See my next posting... > The attached program demonstrates problems with both my implementation of RFC1624's equation 4 (see the original message in this thread), and the current implementation of incremental checksum update in libalias. This program takes 11 seconds on my 500MHz Celeron. You may also want to remove the `break' statements to see the whole story. Basically, what it does, is: 1. Constructs two fake IP packets (old and new) 2. Computes the checksum of the old packet (old checksum) 3. Computes the checksum of the new packet (new checksum) 4. Computes new checksum using one or more differential update procedure 5. Compares the checksums obtained in steps 3 and 4. Have fun, -- Ruslan Ermilov Oracle Developer/DBA, ru@sunbay.com Sunbay Software AG, ru@FreeBSD.org FreeBSD committer, +380.652.512.251 Simferopol, Ukraine http://www.FreeBSD.org The Power To Serve http://www.oracle.com Enabling The Information Age --fdj2RfSjLxBAspz7 Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename=Makefile PROG= inc_cksum NOMAN= YES CFLAGS+=${BDECFLAGS} .if ${MACHINE_ARCH} == i386 CFLAGS+=-O3 .endif CFLAGS+=-DLIBALIAS CFLAGS+=-DRFC1624_3 CFLAGS+=-DRFC1624_4 .include <bsd.prog.mk> --fdj2RfSjLxBAspz7 Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="inc_cksum.c" #include <sys/types.h> #include <stdio.h> #include <stdlib.h> u_short PacketAliasInternetChecksum(u_short *, int nbytes); void test(int, int); #ifdef LIBALIAS void DifferentialChecksum_libalias(u_short *, u_short *, u_short *, int); #endif #ifdef RFC1624_3 void DifferentialChecksum_RFC1624_3(u_short *, u_short *, u_short *, int); #endif #ifdef RFC1624_4 void DifferentialChecksum_RFC1624_4(u_short *, u_short *, u_short *, int); #endif u_short PacketAliasInternetChecksum(u_short *ptr, int nbytes) { int sum, oddbyte; sum = 0; while (nbytes > 1) { sum += *ptr++; nbytes -= 2; } if (nbytes == 1) { oddbyte = 0; ((u_char *) &oddbyte)[0] = *(u_char *) ptr; ((u_char *) &oddbyte)[1] = 0; sum += oddbyte; } sum = (sum >> 16) + (sum & 0xffff); sum += (sum >> 16); return(~sum); } #ifdef LIBALIAS void DifferentialChecksum_libalias(u_short *cksum, u_short *new, u_short *old, int n) { int i; int accumulate; accumulate = *cksum; for (i=0; i<n; i++) { accumulate += (u_short)~*new++; accumulate += *old++; } if (accumulate < 0) { accumulate = -accumulate; accumulate = (accumulate >> 16) + (accumulate & 0xffff); accumulate += accumulate >> 16; *cksum = (u_short) ~accumulate; } else { accumulate = (accumulate >> 16) + (accumulate & 0xffff); accumulate += accumulate >> 16; *cksum = (u_short) accumulate; } } #endif #ifdef RFC1624_3 /* * Incremental Update of Internet Checksum with [Eqn. 3] from RFC 1624. */ void DifferentialChecksum_RFC1624_3(u_short *cksum, u_short *new, u_short *old, int n) { int i; u_int acc; acc = (u_short)~*cksum; for (i = 0; i < n; i++) { acc += *new++; acc += (u_short)~*old++; } acc = (acc >> 16) + (acc & 0xffff); acc += acc >> 16; *cksum = (u_short)~acc; } #endif #ifdef RFC1624_4 /* * Incremental Update of Internet Checksum with [Eqn. 4] from RFC 1624. */ void DifferentialChecksum_RFC1624_4(u_short *cksum, u_short *new, u_short *old, int n) { int i; int acc; /* should be `signed' */ acc = *cksum; for (i = 0; i < n; i++) { acc -= *new++; acc -= (u_short)~*old++; } acc = (acc >> 16) + (acc & 0xffff); acc += acc >> 16; *cksum = (u_short)acc; } #endif void test(int oldword, int newword) { #define MAXWORDS 32767 u_short old[MAXWORDS], new[MAXWORDS]; int i, nbytes, nwords; u_short oldcksum, newcksum; u_short cksum_libalias, cksum_rfc1624_3, cksum_rfc1624_4; /* Construct the fake packets. */ for (i = 0; i < MAXWORDS; i++) { old[i] = oldword; new[i] = newword; } /* Make sure the sum will be non-zero. */ old[0] = new[0] = 1; /* Try the different lengths. */ for (nwords = 1; nwords <= MAXWORDS; nwords++) { nbytes = nwords << 1; /* Calculate the checksums from scratch. */ oldcksum = cksum_libalias = cksum_rfc1624_3 = cksum_rfc1624_4 = PacketAliasInternetChecksum(old, nbytes); newcksum = PacketAliasInternetChecksum(new, nbytes); /* Calculate the checksums incrementally. */ #ifdef LIBALIAS DifferentialChecksum_libalias(&cksum_libalias, new, old, nwords); #endif #ifdef RFC1624_3 DifferentialChecksum_RFC1624_3(&cksum_rfc1624_3, new, old, nwords); #endif #ifdef RFC1624_4 DifferentialChecksum_RFC1624_4(&cksum_rfc1624_4, new, old, nwords); #endif #ifdef LIBALIAS /* Check the libalias(3) current procedure. */ if (cksum_libalias != newcksum && (cksum_libalias != 0xffff || newcksum != 0)) { printf("cksum_libalias!=newcksum %#hx!=%#hx, nwords=%d\n", cksum_libalias, newcksum, nwords); break; } #endif #ifdef RFC1624_3 /* Check the implementation of algorithm for equation 3. */ if (cksum_rfc1624_3 != newcksum) { printf("cksum_rfc1624_3!=newcksum %#hx!=%#hx, nwords=%d\n", cksum_rfc1624_3, newcksum, nwords); break; } #endif #ifdef RFC1624_4 /* Check the implementation of algorithm for equation 4. */ if (cksum_rfc1624_4 != newcksum) { printf("cksum_rfc1624_4!=newcksum %#hx!=%#hx, nwords=%d\n", cksum_rfc1624_4, newcksum, nwords); break; } #endif } #undef MAXWORDS } int main(void) { test(0xffff, 0x0000); test(0x0000, 0xffff); return (0); } --fdj2RfSjLxBAspz7-- To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20001115174031.A10161>