Post by thread:[PIC]: IP Checksum coding challenge ?

I'm not sure what the competitive status of IP-related IP ( :-) is these days. In another conversation, I suggested the following algorithm for computing an IP checksum on a small processor like a PIC (I hearby publish the algorithm and place it in the public domain, if you can do something like that with an algorithm!) It might be neat to get this FIRMLY in the public domain by issuing a "coding challenge" to actually implement this on a PIC (and/or whatever.) Code should be optimized for code space - I don't think any PIC based internet device is going to have speed limitations in the ip checksum routine. The ip checksum is described in detail in RFC1071, including representative code for several processors (the "smallest" of which is either a 68020, or C based code that uses 32bit math (depending on how you look at it.) Code for the "challenge" should generate correct ip checksums, regardless of errors in the algorithm described here :-) Use a different algorithm if you want. You must handle bytestream of up to 1500 bytes, though. (hmm. Interesting optimizations come to mind for less than 256 bytes.) BillW [previously] I have not looked at the PIC code in question, [AN724 - I have now. It doesn't have any general purpos ip checksum routine, and what IS there uses 16bit math and is really ugly.] Nor have I actually done or even thought much about doing an IP checksum on a CPU with only 8 bit math. It's probably easier to think of the checksum as two 8bit parts and keep track of which one you're adding to at the moment, than to do 16bit math. Ie (real pseudo-code here, cause I don't actually program PICs enough to produce actual PIC code without consulting a manual): /* * bytestream-based ip checksum. Given a series of bytes, calculate an * ip checksum using only 8bit math. * ipsum_reset resets/initializes the checksum * ipsum_running adds in each byte as appropriate, leaving the result in * bytes ipcksum_h and ipcksum_l * While this may look like C, it's supposed to translate somewhat trivially * to assembler/machine code for any particular processor... */ byte8 ipcksum_h, /* ip checksum high byte */ ipcksum_l, /* ip checksum low bytes */ ipcksum_b; /* running byte count (one byte's worth. */ /* Note that this wraps for long data, */ /* but we only use the low bit to check */ /* for odd/even bytes */ ipsum_reset() { ipcksum_h = 0; ipcksum_l = 0; ipcksum_b = 0; } ipsum_running (byte8 b) { ++ipcksum_b; /* Increment count */ if (ipcksum_b & 1) { /* a high byte ? */ ipcksum_h += b; /* Add byte to high checksum */ if (CARRYFLAG) { /* If this resulted in a carry */ ipcksum_l += 1; /* add the carry into low sum */ if (CARRYFLAG) { /* and perhaps continue to propagate */ ipcksum_h += 1; /* that into the bottom of high byte */ /* (note that if A+B generates carry, */ /* then (A+B)+1 will never generate */ /* an additional carry. I hope.) */ } } } else { /* do the low byte */ ipcksum_l += b; /* Add byte to high checksum */ if (CARRYFLAG) { /* If this resulted in a carry */ ipcksum_h += 1; /* add the carry into low sum */ if (CARRYFLAG) { /* and perhaps continue to propagate */ ipcksum_l += 1; /* that into the bottom of high byte */ } } } } -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

On Tue, 9 Jan 2001, William Chops Westfield wrote: <snip> {Quote hidden}> /* > * bytestream-based ip checksum. Given a series of bytes, calculate an > * ip checksum using only 8bit math. > * ipsum_reset resets/initializes the checksum > * ipsum_running adds in each byte as appropriate, leaving the result in > * bytes ipcksum_h and ipcksum_l > * While this may look like C, it's supposed to translate somewhat trivially > * to assembler/machine code for any particular processor... > */ > byte8 ipcksum_h, /* ip checksum high byte */ > ipcksum_l, /* ip checksum low bytes */ > ipcksum_b; /* running byte count (one byte's worth. */ > /* Note that this wraps for long data, */ > /* but we only use the low bit to check */ > /* for odd/even bytes */ > ipsum_reset() > { > ipcksum_h = 0; > ipcksum_l = 0; > ipcksum_b = 0; > } > > ipsum_running (byte8 b) > { > ++ipcksum_b; /* Increment count */ > if (ipcksum_b & 1) { /* a high byte ? */ > ipcksum_h += b; /* Add byte to high checksum */ > if (CARRYFLAG) { /* If this resulted in a carry */ > ipcksum_l += 1; /* add the carry into low sum */ > if (CARRYFLAG) { /* and perhaps continue to propagate */ > ipcksum_h += 1; /* that into the bottom of high byte */ > /* (note that if A+B generates carry, */ > /* then (A+B)+1 will never generate */ > /* an additional carry. I hope.) */ > } > } > } else { /* do the low byte */ > ipcksum_l += b; /* Add byte to high checksum */ > if (CARRYFLAG) { /* If this resulted in a carry */ > ipcksum_h += 1; /* add the carry into low sum */ > if (CARRYFLAG) { /* and perhaps continue to propagate */ > ipcksum_l += 1; /* that into the bottom of high byte */ > } > } > } > } Well, here's an implementation of ipsum_running: ; enter with "b" in W ipsum_running: incf ipcksum_b,f btfsc ipcksum_b,0 goto l1 addwf ipcksum_h,f rlf known_zero,w addwf ipcksum_l,f rlf known_zero,w addwf ipcksum_h,f return l1: addwf ipcksum_l,f rlf known_zero,w addwf ipcksum_h,f rlf known_zero,w addwf ipcksum_l,f return Scott -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

On Tue, 9 Jan 2001, Scott Dattalo wrote: {Quote hidden}> > > On Tue, 9 Jan 2001, William Chops Westfield wrote: > > <snip> > > /* > > * bytestream-based ip checksum. Given a series of bytes, calculate an > > * ip checksum using only 8bit math. > > * ipsum_reset resets/initializes the checksum > > * ipsum_running adds in each byte as appropriate, leaving the result in > > * bytes ipcksum_h and ipcksum_l > > * While this may look like C, it's supposed to translate somewhat trivially > > * to assembler/machine code for any particular processor... > > */ > > byte8 ipcksum_h, /* ip checksum high byte */ > > ipcksum_l, /* ip checksum low bytes */ > > ipcksum_b; /* running byte count (one byte's worth. */ > > /* Note that this wraps for long data, */ > > /* but we only use the low bit to check */ > > /* for odd/even bytes */ > > ipsum_reset() > > { > > ipcksum_h = 0; > > ipcksum_l = 0; > > ipcksum_b = 0; > > } > > > > ipsum_running (byte8 b) > > { > > ++ipcksum_b; /* Increment count */ > > if (ipcksum_b & 1) { /* a high byte ? */ > > ipcksum_h += b; /* Add byte to high checksum */ > > if (CARRYFLAG) { /* If this resulted in a carry */ > > ipcksum_l += 1; /* add the carry into low sum */ > > if (CARRYFLAG) { /* and perhaps continue to propagate */ > > ipcksum_h += 1; /* that into the bottom of high byte */ > > /* (note that if A+B generates carry, */ > > /* then (A+B)+1 will never generate */ > > /* an additional carry. I hope.) */ > > } > > } > > } else { /* do the low byte */ > > ipcksum_l += b; /* Add byte to high checksum */ > > if (CARRYFLAG) { /* If this resulted in a carry */ > > ipcksum_h += 1; /* add the carry into low sum */ > > if (CARRYFLAG) { /* and perhaps continue to propagate */ > > ipcksum_l += 1; /* that into the bottom of high byte */ > > } > > } > > } > > } > > Well, here's an implementation of ipsum_running: > > > ; enter with "b" in W > > ipsum_running: > > incf ipcksum_b,f > btfsc ipcksum_b,0 > goto l1 > > addwf ipcksum_h,f > rlf known_zero,w > addwf ipcksum_l,f > rlf known_zero,w > addwf ipcksum_h,f > return > > l1: > addwf ipcksum_l,f > rlf known_zero,w > addwf ipcksum_h,f > rlf known_zero,w > addwf ipcksum_l,f > return And here's another version without the known_zero trick. ; enter with "b" in W ipsum_running: incf ipcksum_b,f btfsc ipcksum_b,0 goto l1 addwf ipcksum_h,f skpnz incf ipcksum_l,f skpnz incf ipcksum_h,f return l1: addwf ipcksum_l,f skpnz incf ipcksum_h,f skpnz incf ipcksum_l,f return -- http://www.piclist.com hint: The PICList is archived three different ways. See http://www.piclist.com/#archives for details.

---- Original Message ---- From: Scott Dattalo <spam_OUTscottTakeThisOuTDATTALO.COM> Sent: Wednesday, January 10, 2001 4:24:17 To: .....PICLISTKILLspam@spam@MITVMA.MIT.EDU Subj: [PIC]: IP Checksum coding challenge ? <snip> {Quote hidden}> And here's another version without the known_zero trick. > ; enter with "b" in W > ipsum_running: > incf ipcksum_b,f > btfsc ipcksum_b,0 > goto l1 > addwf ipcksum_h,f > skpnz > incf ipcksum_l,f > skpnz > incf ipcksum_h,f > return > l1: > addwf ipcksum_l,f > skpnz > incf ipcksum_h,f > skpnz > incf ipcksum_l,f > return Scott, this doesn't seem to work! You don't check the carry flag after addition. Also, when ipcksum_b.0==1 the data byte should be added to the higher part of the checksum. Here is an alternative, not using the known_zero register (17 instructions): ; enter with "b" in W ipsum_running: incf ipcksum_b,f btfss ipcksum_b,0 goto l1 addwf ipcksum_h,f movlw 1 skpnc addwf ipcksum_l,f skpnc addwf ipcksum_h,f return l1: addwf ipcksum_l,f movlw 1 skpnc addwf ipcksum_h,f skpnc addwf ipcksum_l,f return Or, shrinked to 14 instructions: ipsum_running incf ipcksum_b,f btfsc ipcksum_b,0 addwf ipcksum_h,f btfss ipcksum_b,0 addwf ipcksum_l,f skpc return btfss ipcksum_b,0 incfsz ipcksum_h,f btfsc ipcksum_b,0 incf ipcksum_l,f skpnz incf ipcksum_h,f return I think there should be 2 too many instructions, as always :) Nikolai -- http://www.piclist.com#nomail Going offline? Don't AutoReply us! email listservKILLspammitvma.mit.edu with SET PICList DIGEST in the body

On Wed, 10 Jan 2001, Nikolai Golovchenko wrote: {Quote hidden}> ---- Original Message ---- > From: Scott Dattalo <.....scottKILLspam.....DATTALO.COM> > Sent: Wednesday, January 10, 2001 4:24:17 > To: EraseMEPICLISTspam_OUTTakeThisOuTMITVMA.MIT.EDU > Subj: [PIC]: IP Checksum coding challenge ? > <snip> > > And here's another version without the known_zero trick. > > > ; enter with "b" in W > > > ipsum_running: > > > incf ipcksum_b,f > > btfsc ipcksum_b,0 > > goto l1 > > > addwf ipcksum_h,f > > skpnz > > incf ipcksum_l,f > > skpnz > > incf ipcksum_h,f > > return > > > l1: > > addwf ipcksum_l,f > > skpnz > > incf ipcksum_h,f > > skpnz > > incf ipcksum_l,f > > return > > Scott, this doesn't seem to work! You don't check the carry flag > after addition. Also, when ipcksum_b.0==1 the data byte should be > added to the higher part of the checksum. Here is an alternative, > not using the known_zero register (17 instructions): <snip> You're right. Bill caught this too. > I think there should be 2 too many instructions, as always :) You're right again :). This is what I posted to Bill: I was thinking add +1 in which case the carry and Z would both be set. However, that's not necessarily the case. You can say that if Z is set after the addwf, then the carry will be set too. So change the spknz above to a skpnc. Now suppose the carry is set after the addwf. The skpnc will not skip and the incf ipcksum_l will execute. If this rolls over, then the z bit will be set (but the carry won't be affected. The next skpnz will detect this rollover and increment the high byte accordingly. Note, at the cost of increasing the worst case execution time, you can improve the average execution time by inverting the polarity of the skp instructions and execute returns if the skip is not taken. ; enter with "b" in W ipsum_running: incf ipcksum_b,f btfsc ipcksum_b,0 goto l1 addwf ipcksum_h,f skpnc incf ipcksum_l,f skpnz incf ipcksum_h,f return l1: addwf ipcksum_l,f skpnc incf ipcksum_h,f skpnz incf ipcksum_l,f return Scott -- http://www.piclist.com#nomail Going offline? Don't AutoReply us! email listservspam_OUTmitvma.mit.edu with SET PICList DIGEST in the body

Scott Dattalo wrote: > Now suppose the carry is set after the addwf. The skpnc will not skip and the > incf ipcksum_l will execute. If this rolls over, then the z bit will be set (but > the carry won't be affected. The next skpnz will detect this rollover and > increment the high byte accordingly. I'm afraid that doesn't work either. Suppose the carry is cleared after the addwf, and zero flag is set, which is the case when zero added to zero. The increment after skpnc will be skipped, but the next one after skpnz won't! > Note, at the cost of increasing the worst case execution time, you can improve > the average execution time by inverting the polarity of the skp instructions and > execute returns if the skip is not taken. That would fix the problem also, since the increment will never be executed on cleared carry. But I see a way to avoid the code size grows. Take a look: ; enter with "b" in W ipsum_running: incf ipcksum_b,f btfss ipcksum_b,0 goto l1 addwf ipcksum_h,f skpnc incfsz ipcksum_l,f return incf ipcksum_h,f return l1: addwf ipcksum_l,f skpnc incfsz ipcksum_h,f return incf ipcksum_l,f return Nikolai -- http://www.piclist.com#nomail Going offline? Don't AutoReply us! email @spam@listservKILLspammitvma.mit.edu with SET PICList DIGEST in the body