Skip to contentSkip to conversation

- trivial - Improve appletalk checksum calculation

PATCH In review Joe Perches 5 participants 11 messages Oct 22, 2007 – Oct 29, 2007

Subsystems (2)
Networking Network drivers
lore
Share & tools
lore

Joe Perches

author
#0 lore raw

PATCH 1/1 - trivial - Improve appletalk checksum calculation

It's a bit after 2.6.1 now...

Removes unnecessary if, uses 16 bit rotate left.
Performance improves ~30%

Signed-off-by Joe Perches <[email protected]>
net/appletalk/ddp.c +2 -8
index 7c0b515..1c50f4c 100644
@@ -925,15 +925,9 @@ static int atrtr_ioctl(unsigned int cmd, void __user *arg)
 static unsigned long atalk_sum_partial(const unsigned char *data,
 				       int len, unsigned long sum)
 {
-	/* This ought to be unwrapped neatly. I'll trust gcc for now */
 	while (len--) {
-		sum += *data;
-		sum <<= 1;
-		if (sum & 0x10000) {
-			sum++;
-			sum &= 0xffff;
-		}
-		data++;
+		sum += *data++;
+		sum = ((sum & 0x8000)>>15) | ((sum & 0x7fff)<<1);
 	}
 	return sum;
 }
maintainer
#1 lore raw

From: Joe Perches <[email protected]>
Date: Mon, 22 Oct 2007 12:36:19 -0700

Quoted 6 lines

It's a bit after 2.6.1 now...

Removes unnecessary if, uses 16 bit rotate left.
Performance improves ~30%

Signed-off-by Joe Perches <[email protected]>

I'm not sure your transformation is equivalent. Did you actually test this with appletalk traffic to make sure the sum is computed correctly? Or more simply, did you write a test program to send some test data through the old and new functions?

Here is what I think the problem is:

Quoted 7 lines

static unsigned long atalk_sum_partial(const unsigned char *data,

net/appletalk/ddp.c +0 -3
 				       int len, unsigned long sum)
 {
-	/* This ought to be unwrapped neatly. I'll trust gcc for now */
 	while (len--) {
-		sum += *data;
-		sum <<= 1;

net/appletalk/ddp.c static int atrtr_ioctl(unsigned int cmd, void __user *arg) · line 933

Quoted 10 lines
net/appletalk/ddp.c +2 -5
-		if (sum & 0x10000) {
-			sum++;
-			sum &= 0xffff;
-		}
-		data++;
+		sum += *data++;
+		sum = ((sum & 0x8000)>>15) | ((sum & 0x7fff)<<1);
 	}
 	return sum;
 }

The old code is handling overflow, so that when bit 16 gets set by and addition, that overflow bit gets cleared and then added back into the sum.

Your code is rotating bit 15 down by one bit and bits 0-14 up by one bit, my remedial math knowledge tell me that's likely not the same thing. :-)

maintainer
#3 lore raw
In reply to Joe Perches

From: Joe Perches <[email protected]>
Date: Mon, 22 Oct 2007 18:36:28 -0700

Quoted 10 lines · David Miller
Quoted 2 lines

Your code is rotating bit 15 down by one bit and bits 0-14 up by one bit.

Yes, a 16 bit rotate left.

There was a discussion a few years ago:
http://oss.sgi.com/archives/netdev/2003-10/msg00734.html

Quoted 1 line

From the spec:

...

Quoted 2 lines

Reception of a datagram with CkSum equal to 0 implies that a checksum is not performed.

Ok, but again did you test it?

author
#4 lore raw
Quoted 1 line · David Miller

Ok, but again did you test it?

Nope. Stephen Hemminger did in 2003.

author
#2 lore raw
In reply to David Miller
Quoted 2 lines · David Miller

Your code is rotating bit 15 down by one bit and bits 0-14 up by one bit.

Yes, a 16 bit rotate left.

There was a discussion a few years ago:
http://oss.sgi.com/archives/netdev/2003-10/msg00734.html

Quoted 1 line

From the spec:

Implementers of DDP should treat generating the checksum as an optional feature. The 16-bit DDP checksum is computed as follows:

CkSum := 0 ;
FOR each datagram byte starting with the byte immediately following this Checksum field
REPEAT the following algorithm:
CkSum := CkSum + byte; (unsigned addition)
Rotate CkSum left one bit, rotating the
most significant bit in least significant bit;
IF, at the end, CkSum = 0 THEN
CkSum := $FFFF (all ones).

Reception of a datagram with CkSum equal to 0 implies that a checksum is not performed.

#9 lore raw
In reply to Joe Perches
Quoted 20 lines · On Mon, 22 Oct 2007 12:36:19 -0700 Joe Perches <[email protected]> wrote:

It's a bit after 2.6.1 now...

Removes unnecessary if, uses 16 bit rotate left.
Performance improves ~30%

Signed-off-by Joe Perches <[email protected]>
net/appletalk/ddp.c +0 -3
index 7c0b515..1c50f4c 100644
@@ -925,15 +925,9 @@ static int atrtr_ioctl(unsigned int cmd, void __user *arg)
 static unsigned long atalk_sum_partial(const unsigned char *data,
 				       int len, unsigned long sum)
 {
-	/* This ought to be unwrapped neatly. I'll trust gcc for now */
 	while (len--) {
-		sum += *data;
-		sum <<= 1;

net/appletalk/ddp.c static int atrtr_ioctl(unsigned int cmd, void __user *arg) · line 933

Quoted 10 lines
net/appletalk/ddp.c +2 -5
-		if (sum & 0x10000) {
-			sum++;
-			sum &= 0xffff;
-		}
-		data++;
+		sum += *data++;
+		sum = ((sum & 0x8000)>>15) | ((sum & 0x7fff)<<1);
 	}
 	return sum;
 }

The end of the message you quoted was:

Quoted 11 lines

Corrected fast code is:

        while (len--) {
                sum += *data++;
                sum <<= 1;
                sum = (((sum & 0x10000) >> 16) + sum) & 0xffff;
        }

At least it is correct on the standalone random data test, and the new code is 30% faster for the cached memory case (13.7 clks/byte vs 18 clks/byte).

Your code looks different...

Signature · 1 line
Stephen Hemminger <[email protected]>
#5 lore raw
In reply to Joe Perches
Quoted 4 lines · Joe Perches
Quoted 1 line · David Miller

Ok, but again did you test it?

Nope. Stephen Hemminger did in 2003.

But your code differs significantly from Stephen's version. However, if it is correct it does look like a good improvement.

So please write a simple test program. It can't that bad since there are only 65536 values to test :)

Cheers,

Signature · 4 lines
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
author
#10 lore raw
In reply to Stephen Hemminger
Quoted 8 lines · Stephen Hemminger
Quoted 8 lines

Corrected fast code is:

        while (len--) {
                sum += *data++;
                sum <<= 1;
                sum = (((sum & 0x10000) >> 16) + sum) & 0xffff;
        }
Quoted 4 lines
Quoted 3 lines

At least it is correct on the standalone random data test, and the new code is 30% faster for the cached memory case (13.7 clks/byte vs 18 clks/byte).

Your code looks different...

Both are 16 bit rotate lefts.
Which looks clearer?

#6 lore raw
In reply to Herbert Xu
Quoted 5 lines · Herbert Xu

But your code differs significantly from Stephen's version. However, if it is correct it does look like a good improvement.

So please write a simple test program. It can't that bad since there are only 65536 values to test :)

I think the code is simple enough to see immediately that it should calculate the same checksum. But I have written a short test program to show this and tested it on i686 (gcc-4.2.2) and powerpc (gcc-3.4.5) without optimization and with -O6.

BTW, shouldn't unsigned long be replaced by unsigned int to avoid 64-bit operations one some platforms?

urs

#include <stdio.h>

unsigned long f1(unsigned long sum)

{
    sum <<= 1;
    if (sum & 0x10000) {
	sum++;
	sum &= 0xffff;
    }
    return sum;
}

unsigned long f2(unsigned long sum)

{
    sum = ((sum & 0x8000)>>15) | ((sum & 0x7fff)<<1);
    return sum;
}

int main()

{
    unsigned long s;

    for (s = 0; s < 65536; s++) {
	if (f1(s) != f2(s) || f1(s) > 65535)
	    printf("%ld\n", s);
    }
    return 0;
}
author
#7 lore raw
Quoted 2 lines · Urs Thuermann

I have written a short test program to show this and tested it on i686 (gcc-4.2.2) and powerpc (gcc-3.4.5) without optimization and with -O6.

Thanks for that.

Quoted 2 lines

BTW, shouldn't unsigned long be replaced by unsigned int to avoid 64-bit operations one some platforms?

probably unsigned long should be u16.

Compiled, untested.

net/appletalk/ddp.c +8 -14
index 7c0b515..c3890cc 100644
@@ -922,25 +922,19 @@ static int atrtr_ioctl(unsigned int cmd, void __user *arg)
  * Checksum: This is 'optional'. It's quite likely also a good
  * candidate for assembler hackery 8)
  */
-static unsigned long atalk_sum_partial(const unsigned char *data,
-				       int len, unsigned long sum)
+static u16 atalk_sum_partial(const unsigned char *data,
+			     int len, u16 sum)
 {
-	/* This ought to be unwrapped neatly. I'll trust gcc for now */
 	while (len--) {
-		sum += *data;
-		sum <<= 1;
-		if (sum & 0x10000) {
-			sum++;
-			sum &= 0xffff;
-		}
-		data++;
+		sum += *data++;
+		sum = ((sum & 0x8000) >> 15) | ((sum & 0x7fff) << 1);
 	}
 	return sum;
 }
 
 /*  Checksum skb data --  similar to skb_checksum  */
-static unsigned long atalk_sum_skb(const struct sk_buff *skb, int offset,
-				   int len, unsigned long sum)
+static u16 atalk_sum_skb(const struct sk_buff *skb, int offset,
+			 int len, u16 sum)
 {
 	int start = skb_headlen(skb);
 	int i, copy;

@@ -1010,13 +1004,13 @@ static unsigned long atalk_sum_skb(const struct sk_buff *skb, int offset,
 
 static __be16 atalk_checksum(const struct sk_buff *skb, int len)
 {
-	unsigned long sum;
+	u16 sum;
 
 	/* skip header 4 bytes */
 	sum = atalk_sum_skb(skb, 4, len-4, 0);
 
 	/* Use 0xFFFF for 0. 0 itself means none */
-	return sum ? htons((unsigned short)sum) : htons(0xFFFF);
+	return cpu_to_be16(sum ? sum : 0xFFFF);
 }
 
 static struct proto ddp_proto = {

      *
author
#8 lore raw
Quoted 1 line · Joe Perches

probably unsigned long should be u16.

Or not.
x86 u16 performs much worse than u32 (~ 50% worse)