Menu
▾
▴
Re: AW: [Sdcc-user] Calculating IP Checksum
|
From: Dawid M. <D.M...@el...> - 2003-03-16 22:26:30
|
Dear all,
Michael, thanks for the rushy criticism, not something I expected after
coming back home after the weekend. Believe it or not I actually have
studied RFCs 791,792,793,1071, ... and many others before attemting to =
write
my code. And, surprisingly enough the final outcome worked quite well, =
even
when tested with Explorer, Netscape, Lynx.... Anyway, no hard feelings =
on my
side.
Erik, thanks a lot for the detailed claryfing of "16 bit one's complem=
ent
of the one's complement sum of 16 bit words" :-)
Regards,
Dave
----- Original Message -----
=46rom: "Michael S=F6gtrop" <MSo...@Mi...>
To: <sdc...@li...>
Sent: Sunday, March 16, 2003 11:03 AM
Subject: AW: AW: [Sdcc-user] Calculating IP Checksum
> Dear Erik,
>
> Thank you for putting this straight and sorry Dave.
> I have been to fast and missinterpreted the sentence:
>
> The checksum field is the 16 bit one's complement of the one's
> complement sum of all 16 bit words in the header.
>
> with an additional plural s as
>
> The checksum field is the 16 bit one's complement of the one's
> complements sum of all 16 bit words in the header.
>
> But then, most probably the original poster, Charles, is right
> in doing it in assembly and trying to use the processors
> carry logic to do the extra carrys right away to avoid the
> 32 bit arithmetic.
>
> Best regards and sorry again,
>
> Michael
>
>
> > -----Urspr=FCngliche Nachricht-----
> > Von: sdc...@li...
> > [mailto:sdc...@li...] Im Auftrag von
> > Erik Petrich
> > Gesendet: Samstag, 15. M=E4rz 2003 21:14
> > An: sdc...@li...
> > Betreff: Re: AW: [Sdcc-user] Calculating IP Checksum
> >
> >
> >
> > On Sat, 15 Mar 2003, Michael S=F6gtrop wrote:
> >
> > > Dear Dave,
> > >
> > > Sure, you can kill yourself with C code as well. It is quite a
> > > miracle, that your tcp/ip stack can communicate with anything els=
e
> > > than your own code.
> >
> > Actually, it is not so miraculous that it works. It is
> > essentially following the method of the sample C code given
> > in RFC 1071 for efficiently calculating a one's complement checksum=
=2E
> >
> > > Using a long accumulator and doing all this shifting and
> > everything is
> > > quite a complicated (and inefficient) relacement for just adding =
up
> > > the ones complements (~) of every 16 bit word and padding
> > odd length
> > > blocks with a zero byte.
> >
> > The 8051 as well as all other processors from the past 20
> > years that I know of perform a two's complement sum when
> > asked to do integer addition. Taking the one's complement of
> > some values, and then computing a two's complement sum on the
> > result is NOT the same as computing a one's complement sum on
> > the original values. Similar wording is the cause of this
> > sort of confusion; a one's complement sum is performing a sum
> > according to the rules of arithmetic in a number system known
> > as "one's complement", but computing the one's complement of
> > a number involves flipping all the bits of a number. It
> > happens to have this name because this is how you find the
> > negative (complement) of a number in, again, the number
> > system known as "one's complement".
> >
> >
> > Consider two number systems with 16 bits.
> >
> > In the ubiquitous two's complement system, 16 bits would give
> > us positive numbers from 1 to 32767, negative numbers from -1
> > to -32768, and 0. It has the nice property that implementing
> > addition and subtraction for signed numbers is exactly the
> > same as if dealing with unsigned numbers (0 to 65535), as
> > long as all the results stay in the defined ranges.
> >
> > In a one's complement arithmetic system, there are positive
> > numbers from
> > 1 to 32767, negative numbers from -1 to -32767, and two zeros
> > (which could be considered as +0 and -0). The symmetry makes
> > it easier to negate a number (which simplifies the
> > implementation of subtraction), but a little harder to compute a su=
m.
> >
> > A key difference between these two systems is that whereas in
> > a two's complement system the carry out from the most
> > significant bits is discarded, in a one's complement system
> > the carry out from the most siginificant bits is sent back as
> > the carry in to the least significant bits. This is usually
> > refered to as wrap-around or end-around carry.
> >
> > Let's compute -1+1+1=3D1 in both systems. In two's complement
> > this is (with some extra spaces to keep from going crosseyed):
> >
> > 1111 1111 1111 1111 (-1)
> > + 0000 0000 0000 0001 (1)
> > --------------------
> > 1 0000 0000 0000 0000 (0, ignoring the carry out)
> >
> > 0000 0000 0000 0000 (0)
> > + 0000 0000 0000 0001 (1)
> > --------------------
> > 0000 0000 0000 0001 (1)
> >
> > In one's complement:
> >
> > 1111 1111 1111 1110 (-1, the one's complement of 1)
> > + 0000 0000 0000 0001 (1)
> > --------------------
> > 1111 1111 1111 1111 (-0, the one's complement of 0)
> >
> > 1111 1111 1111 1111 (-0)
> > + 0000 0000 0000 0001 (1)
> > --------------------
> > 1 0000 0000 0000 0000 (+0, but there's a carry out)
> > + 1 (so wrap the carry back around)
> > --------------------
> > 0000 0000 0000 0001 (1)
> >
> > But if we just take the one's complement of the operands and
> > do two's complement addition on them, it doesn't work out the
> > same. Let's compute
> > 1+1=3D2 this way:
> >
> > 1111 1111 1111 1110 (~1)
> > + 1111 1111 1111 1110 (~1)
> > --------------------
> > 1 1111 1111 1111 1100 (~3, ignoring the carry out)
> >
> > which is quite a bit different from actual one's complement additio=
n:
> >
> > 0000 0000 0000 0001 (1)
> > + 0000 0000 0000 0001 (1)
> > --------------------
> > 0000 0000 0000 0010 (2, carry out is 0, so no need to wrap=
)
> >
> > Dave's code correctly works by accumulating all the
> > intermediate carries into the high half of sum and then
> > wrapping them around, to get the correct one's complement
> > sum, in the final step:
> >
> > while (sum >> 16)
> > sum =3D (u_WORD) ( (sum >> 16)&0xffff ) + (sum & 0xffff);
> >
> > Admittedly, the 8051 doesn't handle the 32-bit sum as well as
> > bigger processors, but the >> 16 and & 0xffff operations are
> > byte aligned and so should be compiled to at most a few mov
> > instructions.
> >
> > Erik
> >
> > >
> > > Btw: I think the code I posted before had two bugs: It is
> > lenBytes>>=3D1
> > > and you have to return ~sum.
> > >
> > > Best regards,
> > >
> > > Michael
> > > > -----Urspr=FCngliche Nachricht-----
> > > > Von: sdc...@li...
> > > > [mailto:sdc...@li...] Im Auftrag von
> > > > Dawid Mielnik
> > > > Gesendet: Donnerstag, 13. M=E4rz 2003 18:50
> > > > An: sdc...@li...
> > > > Betreff: Re: [Sdcc-user] Calculating IP Checksum
> > > >
> > > >
> > > > hey,
> > > >
> > > > why do you kill yourself with assemlby..... try doing so
> > in C I also
> > > > have developed TCP/IP stack on an 8051 about a year ago
> > myself.....
> > > > there are many usefull solutions from already implemented stack=
s,
> > > > such as uIP.
> > > >
> > > > this is an axtract of my code for calculating Internet
> > > > checksum in general (IP and TCP)
> > > >
> > > > WORD inet_checksum (xdata u_BYTE *buff, u_WORD len)
> > > > {
> > > > WORD i =3D 0;
> > > > LONG sum =3D 0;
> > > > u_WORD temp =3D 0;
> > > > u_WORD answer =3D 0;
> > > >
> > > > for(i=3D0; i < (len-1); i +=3D 2)
> > > > sum +=3D (u_WORD) *((u_WORD *) ( buff+i ) ) ;
> > > >
> > > > if (i =3D=3D (len - 1))
> > > > sum +=3D (u_WORD) ((*(u_BYTE *)(buff+len-1)) & 0xff);
> > > >
> > > > while (sum >> 16)
> > > > sum =3D (u_WORD) ( (sum >> 16)&0xffff ) + (sum & 0xffff);
> > > >
> > > > answer =3D ~sum;
> > > > return (answer);
> > > > }
> > > >
> > > > "buff" is a pointer to buffer containing the packet, "len" is
> > > > the header length
> > > >
> > > > regards
> > > >
> > > > Dave
> > > >
> > > > ----- Original Message -----
> > > > From: "Olaniyi Bajomo" <zu...@em...>
> > > > To: <sdc...@li...>
> > > > Sent: Thursday, March 13, 2003 3:44 PM
> > > > Subject: [Sdcc-user] Calculating IP Checksum
> > > >
> > > >
> > > > > Hello guys/Gals I have a small problem. I want biuld an
> > > > TCP/IP packet
> > > > > in
> > > > my code and calculate the checksum for IP and the TCP. but
> > > > for some reason I can't get my checksum program to so it. All
> > > > it those is perfrom 16bit 2's complement addition of a buffer
> > > > that contains the IP pseudo header, the TCP header and data.
> > > > but I think there is a problem when ever the summation
> > > > results in 0xff in any of my 8bit result registers as I dont
> > > > think this is treated as a carry or am I wrong? I have the
> > > > code attached to this email. if anyone has a better idea as
> > > > to how to do this please let me know.
> >
> > The comment above about 2's complement addition confused me
> > earlier since the assembly code is clearly doing 1's
> > complement addition. After looking at RFCs, the only thing
> > that seems wrong is the implementation of the conversion of
> > the length from 8 bit units to 16 bit units and, if you
> > haven't already prepadded the packets to an even size,
> > handling of odd lengths.
> >
> > > > > thanks
> > > > >
> > > > > ------------------------CODE STRIP---------------------------=
--
> > > > >
> > > > > code unsigned int ip_checksum(xdata u_int16_t *Ip_Pak, int
> > > > pckLength)
> > > > > {
> > > > > Ip_Pak;
> > > > > pckLength;
> > > > > // first 16bit set to r1 r2
> > > > > // second 16bit set to r5 r6
> > > > > // pckLength set to _ip_checksum_PARM_2
> > > > > _asm
> > > > >
> > > > > mov r3, _ip_checksum_PARM_2
> > > > > mov r4, (_ip_checksum_PARM_2+1)
> > > > > mov a ,r3 // divide lenght by 2
> > > > > clr c // clear carry
> > > > > rrc a // shift lower length by 1 to right
> > > > > mov r3,a // save lower
> > > > > mov a,r4
> > > > > clr c
> > > > > rrc a // shift high length by 1 to right
> > > > > mov r4,a // save higher
> > > > > movx a, @dptr
> > > > > mov r1,a // get high byte of 16 bit numer
> > > > > inc dptr
> > > > > movx a, @dptr
> > > > > mov r2,a // get lower byte of 16bit number
> > > > > dec r3
> > > > > loop:
> > > > > inc dptr
> > > > > movx a, @dptr
> > > > > mov r5, a // get next number
> > > > > inc dptr
> > > > > movx a, @dptr
> > > > > add a,r2 // add lower bytes
> > > > > mov r2,a
> > > > > ;clr a
> > > > > mov a,r1
> > > > > addc a,r5 // add carrys
> > > > > ;add a,r5 // add higher byte
> > > > > mov r1,a // store addition
> > > > > clr a
> > > > > addc a,r2 // add carry to lower byte
> > > > > mov r2,a
> > > > > djnz r3 , loop
> > > > > cjne r4,#0x00,high
> > > > > finish:
> > > > > mov a, r1
> > > > > cpl a
> > > > > mov dph,a
> > > > > mov a, r2
> > > > > cpl a
> > > > > mov dpl,a
> > > > > ajmp end
> > > > > high:
> > > > > djnz r4,loop
> > > > > ajmp finish
> > > > > end:
> > > > > _endasm;
> > > > > }
> > > > > ------------------END CODE STRIP-----------------------------
> > > > >
> > > > > Please HELP!!!
> > > > >
> > > > > Charles
> > > > > --
> >
> >
> >
> > -------------------------------------------------------
> > This SF.net email is sponsored by:Crypto Challenge is now open!
> > Get cracking and register here for some mind boggling fun and
> > the chance of winning an Apple iPod:
> > http://ads.sourceforge.net/cgi-> bin/redirect.pl?thaw0031en
> >
> >
> > _______________________________________________
> > Sdcc-user mailing list
> > Sdc...@li...
> > https://lists.sourceforge.net/lists/listinfo/s> dcc-user
> >
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by:Crypto Challenge is now open!
> Get cracking and register here for some mind boggling fun and
> the chance of winning an Apple iPod:
> http://ads.sourceforge.net/cgi-bin/redirect.pl?thaw0031en
> _______________________________________________
> Sdcc-user mailing list
> Sdc...@li...
> https://lists.sourceforge.net/lists/listinfo/sdcc-user
>
|
