Searching \ for '[PIC]: IP Checksum coding challenge ?' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/method/errors.htm?key=checksum
Search entire site for: 'IP Checksum coding challenge ?'.

Exact match. Not showing close matches.
PICList Thread
'[PIC]: IP Checksum coding challenge ?'
2001\01\09@140928 by Bill Westfield

face picon face
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.


2001\01\09@142819 by Scott Dattalo

face
flavicon
face
On Tue, 9 Jan 2001, William Chops Westfield wrote:

<snip>
{Quote hidden}

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.


2001\01\09@212800 by Scott Dattalo

face
flavicon
face
On Tue, 9 Jan 2001, Scott Dattalo wrote:

{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

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.


2001\01\10@034630 by Nikolai Golovchenko

flavicon
face
---- Original Message ----
From: Scott Dattalo <spam_OUTscottTakeThisOuTspamDATTALO.COM>
Sent: Wednesday, January 10, 2001 4:24:17
 To: .....PICLISTKILLspamspam@spam@MITVMA.MIT.EDU
Subj: [PIC]: IP Checksum coding challenge ?
<snip>
{Quote hidden}

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 listservspamKILLspammitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@123726 by Scott Dattalo

face
flavicon
face
On Wed, 10 Jan 2001, Nikolai Golovchenko wrote:

{Quote hidden}

<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 listservspamspam_OUTmitvma.mit.edu with SET PICList DIGEST in the body


2001\01\10@231800 by Nikolai Golovchenko

flavicon
face
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@listservKILLspamspammitvma.mit.edu with SET PICList DIGEST in the body


2001\01\11@013140 by Scott Dattalo

face
flavicon
face
On Thu, 11 Jan 2001, Nikolai Golovchenko wrote:

> I'm afraid that doesn't work either. Suppose the carry is cleared

Damn!

>
> 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:

Could you or Dmitry send me a case of that Magic Vodka?

Excellent solution!

Scott

--
http://www.piclist.com hint: To leave the PICList
KILLspampiclist-unsubscribe-requestKILLspamspammitvma.mit.edu


More... (looser matching)
- Last day of these posts
- In 2001 , 2002 only
- Today
- New search...