crc32: final-cleanup.diff

Some final cleanup changes

- added a comment at the top of crc32.c
- moved macros ahead of function prototype
- replaced loops with for (i = 0; i < xxx; i++) which requires fewer instructions on x86 since the buffer lookups can use i as an index.

lib/crc32.c +0 -3

-/* implements slicing-by-4 or slicing-by-8 algorithm */
-static inline u32
-crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32

(*tab)[256])

lib/crc32.c +0 -4

-{
 # ifdef __LITTLE_ENDIAN
 #  define DO_CRC(x) crc = tab[0][(crc ^ (x)) & 255] ^ (crc >> 8)
-#  define DO_CRC4 crc = tab[3][(crc) & 255] ^ \
-		tab[2][(crc >> 8) & 255] ^ \
-		tab[1][(crc >> 16) & 255] ^ \

lib/crc32.c +28 -19

+#  define DO_CRC8 (tab[7][(q) & 255] ^ \
+		tab[6][(q >> 8) & 255] ^ \
+		tab[5][(q >> 16) & 255] ^ \
+		tab[4][(q >> 24) & 255])
 # else
 #  define DO_CRC(x) crc = tab[0][((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
-#  define DO_CRC4 crc = tab[0][(crc) & 255] ^ \
-		tab[1][(crc >> 8) & 255] ^ \
-		tab[2][(crc >> 16) & 255] ^ \
-		tab[3][(crc >> 24) & 255]
-#  define DO_CRC8a (tab[4][(q) & 255] ^ \
-		tab[5][(q >> 8) & 255] ^ \
-		tab[6][(q >> 16) & 255] ^ \
-		tab[8][(q >> 24) & 255])
-#  define DO_CRC8b (tab[0][(q) & 255] ^ \
+#  define DO_CRC4 (tab[0][(q) & 255] ^ \
 		tab[1][(q >> 8) & 255] ^ \
 		tab[2][(q >> 16) & 255] ^ \
 		tab[3][(q >> 24) & 255])
+#  define DO_CRC8 (tab[4][(q) & 255] ^ \
+		tab[5][(q >> 8) & 255] ^ \
+		tab[6][(q >> 16) & 255] ^ \
+		tab[7][(q >> 24) & 255])
 # endif
+
+/* implements slicing-by-4 or slicing-by-8 algorithm */
+static inline u32 crc32_body(u32 crc, unsigned char const *buf,
+			     size_t len, const u32 (*tab)[256])
+{
 	const u32 *b;
+	u8 *p;
+	u32 q;
 	size_t init_len;
 	size_t middle_len;
 	size_t rem_len;
+	size_t i;
 
 	/* break buf into init_len bytes before and
 	 * rem_len bytes after a middle section with

@@ -96,37 +96,34 @@ crc32_body(u32 crc, unsigned char const
 	rem_len = (len - init_len) & 7;
 # endif
 
-	/* Align it */
-	if (unlikely(init_len)) {
-		do {
-			DO_CRC(*buf++);
-		} while (--init_len);
-	}
-	b = (const u32 *)buf;
-	for (--b; middle_len; --middle_len) {
+	/* process unaligned initial bytes */
+	for (i = 0; i < init_len; i++)
+		DO_CRC(*buf++);
+
+	/* process aligned words */
+	b = (const u32 *)(buf - 4);
+
+	for (i = 0; i < middle_len; i++) {
 # if CRC_LE_BITS == 32
-		crc ^= *++b; /* use pre increment for speed */
-		DO_CRC4;
+		/* slicing-by-4 algorithm */
+		q = crc ^ *++b; /* use pre increment for speed */
+		crc = DO_CRC4;

lib/crc32.c +7 -11

 	}
-	/* And the last few bytes */
-	if (rem_len) {
-		u8 *p = (u8 *)(b + 1) - 1;
-		do {
-			DO_CRC(*++p); /* use pre increment for speed */
-		} while (--rem_len);
-	}
+
+	/* process unaligned remaining bytes */
+	p = (u8 *)(b + 1) - 1;
+
+	for (i = 0; i < rem_len; i++)
+		DO_CRC(*++p); /* use pre increment for speed */
+
 	return crc;
-#undef DO_CRC
-#undef DO_CRC4
-#undef DO_CRC8a
-#undef DO_CRC8b
 }
 #endif

Additional comments.

Quoted 7 lines

Some final cleanup changes

- added a comment at the top of crc32.c
- moved macros ahead of function prototype
- replaced loops with for (i = 0; i < xxx; i++) which requires fewer instructions on x86 since the buffer lookups can use i as an index.

Quoted 5 lines

lib/crc32.c +0 -3

-/* implements slicing-by-4 or slicing-by-8 algorithm */
-static inline u32
-crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32

(*tab)[256])

After careful measurements and looking at asm code I figured out that there was no penalty for using 2D array. That allowed me to go back to the original form.

Quoted 7 lines

lib/crc32.c +0 -4

-{
 # ifdef __LITTLE_ENDIAN
 #  define DO_CRC(x) crc = tab[0][(crc ^ (x)) & 255] ^ (crc >> 8)
-#  define DO_CRC4 crc = tab[3][(crc) & 255] ^ \
-      tab[2][(crc >> 8) & 255] ^ \
-      tab[1][(crc >> 16) & 255] ^ \

lib/crc32.c MODULE_LICENSE("GPL"); · line 57

Quoted 10 lines

lib/crc32.c +1 -6

-      tab[0][(crc >> 24) & 255]
-#  define DO_CRC8a (tab[7][(q) & 255] ^ \
-      tab[6][(q >> 8) & 255] ^ \
-      tab[5][(q >> 16) & 255] ^ \
-      tab[4][(q >> 24) & 255])
-#  define DO_CRC8b (tab[3][(q) & 255] ^ \
+#  define DO_CRC4 (tab[3][(q) & 255] ^ \
       tab[2][(q >> 8) & 255] ^ \
       tab[1][(q >> 16) & 255] ^ \
       tab[0][(q >> 24) & 255])

By changing the syntax a little so that the assignment is done down below the 4 byte and 8 byte algorithms can share DO_CRC4.

Quoted 69 lines

lib/crc32.c +29 -20

+#  define DO_CRC8 (tab[7][(q) & 255] ^ \
+      tab[6][(q >> 8) & 255] ^ \
+      tab[5][(q >> 16) & 255] ^ \
+      tab[4][(q >> 24) & 255])
 # else
 #  define DO_CRC(x) crc = tab[0][((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
-#  define DO_CRC4 crc = tab[0][(crc) & 255] ^ \
-      tab[1][(crc >> 8) & 255] ^ \
-      tab[2][(crc >> 16) & 255] ^ \
-      tab[3][(crc >> 24) & 255]
-#  define DO_CRC8a (tab[4][(q) & 255] ^ \
-      tab[5][(q >> 8) & 255] ^ \
-      tab[6][(q >> 16) & 255] ^ \
-      tab[8][(q >> 24) & 255])
-#  define DO_CRC8b (tab[0][(q) & 255] ^ \
+#  define DO_CRC4 (tab[0][(q) & 255] ^ \
       tab[1][(q >> 8) & 255] ^ \
       tab[2][(q >> 16) & 255] ^ \
       tab[3][(q >> 24) & 255])
+#  define DO_CRC8 (tab[4][(q) & 255] ^ \
+      tab[5][(q >> 8) & 255] ^ \
+      tab[6][(q >> 16) & 255] ^ \
+      tab[7][(q >> 24) & 255])
 # endif
+
+/* implements slicing-by-4 or slicing-by-8 algorithm */
+static inline u32 crc32_body(u32 crc, unsigned char const *buf,
+              size_t len, const u32 (*tab)[256])
+{
    const u32 *b;
+   u8 *p;
+   u32 q;
    size_t init_len;
    size_t middle_len;
    size_t rem_len;
+   size_t i;
 
    /* break buf into init_len bytes before and
     * rem_len bytes after a middle section with

@@ -96,37 +96,34 @@ crc32_body(u32 crc, unsigned char const
    rem_len = (len - init_len) & 7;
 # endif
 
-   /* Align it */
-   if (unlikely(init_len)) {
-      do {
-         DO_CRC(*buf++);
-      } while (--init_len);
-   }
-   b = (const u32 *)buf;
-   for (--b; middle_len; --middle_len) {
+   /* process unaligned initial bytes */
+   for (i = 0; i < init_len; i++)
+      DO_CRC(*buf++);
+
+   /* process aligned words */
+   b = (const u32 *)(buf - 4);
+
+   for (i = 0; i < middle_len; i++) {
 # if CRC_LE_BITS == 32
-      crc ^= *++b; /* use pre increment for speed */
-      DO_CRC4;
+      /* slicing-by-4 algorithm */
+      q = crc ^ *++b; /* use pre increment for speed */
+      crc = DO_CRC4;
 # else
-      u32 q;
+      /* slicing-by-8 algorithm */
       q = crc ^ *++b;

lib/crc32.c crc32_body(u32 crc, unsigned char const · line 117

Quoted 6 lines

lib/crc32.c +2 -2

-      crc = DO_CRC8a;
+      crc = DO_CRC8;
       q = *++b;
-      crc ^= DO_CRC8b;
+      crc ^= DO_CRC4;
 # endif

This really shows how close the two algorithms are.

Quoted 23 lines

lib/crc32.c +7 -11

    }
-   /* And the last few bytes */
-   if (rem_len) {
-      u8 *p = (u8 *)(b + 1) - 1;
-      do {
-         DO_CRC(*++p); /* use pre increment for speed */
-      } while (--rem_len);
-   }
+
+   /* process unaligned remaining bytes */
+   p = (u8 *)(b + 1) - 1;
+
+   for (i = 0; i < rem_len; i++)
+      DO_CRC(*++p); /* use pre increment for speed */
+
    return crc;
-#undef DO_CRC
-#undef DO_CRC4
-#undef DO_CRC8a
-#undef DO_CRC8b
 }
 #endif

Doing this adds one insn to ppc. What is good for x86 isn't for pcc32 (and I guess any modern arch).

Quoted 8 lines

Quoted 6 lines

lib/crc32.c +0 -3

-/* implements slicing-by-4 or slicing-by-8 algorithm */
-static inline u32
-crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32

(*tab)[256])

After careful measurements and looking at asm code I figured out that

there

Quoted 2 lines

was no penalty for using 2D array. That allowed me to go back to the original form.

What about my suggestion to assign each table to a ptr? This was good for ppc so if it doesn't slow x86 it should be added.

Quoted 4 lines

Doing this adds one insn to ppc. What is good for x86 isn't for pcc32 (and I guess any modern arch).

I looked at the assembly output from the original code and I see two compares at the end of the first loop, one for --len and one for (buf & 3) which it has to compute. You are better off just computing buf & 3 once and comparing with len once to compute init_len then in each iteration in the loop you only have to compare one thing.

As proposed:

        init_len = min((-((uintptr_t)buf)) & 3, len);
        ...

        /* process unaligned initial bytes */
        for (i = 0; i < init_len; i++)
                DO_CRC(*buf++);

crc32x_le:
<.....>
negq %rcx # (-buf)
andl $3, %ecx # (-buf) & 3
cmpq %rdx, %rcx # min()
cmova %rdx, %rcx # init_len =
xorl %edi, %edi # i = 0
<.....>
jmp .L2
.L3:

# crc = tab[0][(crc ^ (*buf++)) & 255] ^ (crc >> 8)
        movb    (%rsi,%rdi), %dl         # buf[i]
        incq    %rdi               # buf++
        xorl    %eax, %edx            # crc ^ *buf++
        shrl    $8, %eax            # crc >> 8
        movzbl  %dl, %edx            # & 255
        xorl    crc32table_le(,%rdx,4), %eax                 # crc =
tab[...] ^ (crc >> 8)
.L2:
        cmpq    %rcx, %rdi            # compare i with
init_len
        jb      .L3
        <.....>

As was originally:

        if (unlikely((long)buf & 3 && len)) {
                do {
                        DO_CRC(*buf++);
                } while ((--len) && ((long)buf)&3);
        }

crc32x_le:

        pushq   %rbp
        movl    %edi, %eax
        pushq   %rbx
        testb   $3, %sil
        je      .L16
        testq   %rdx, %rdx
.L25:
        je      .L16
        movb    (%rsi), %cl            # *p
        incq    %rsi               # p++
        xorl    %eax, %ecx            # crc ^ *p
        shrl    $8, %eax            # crc >> 8
        movzbl  %cl, %ecx            # ... & 255
        xorl    crc32table_le(,%rcx,4), %eax      # tab[...] ^ (crc >>

8)
decq %rdx # len--
je .L16 # if len != 0
continue
testb $3, %sil # buf & 3
jmp .L25 # if buf & 3
continue
.L16:

The first loop has 8 instructions second one has 11 instructions. First loop has slightly more setup to compute init_len, second loop has a couple of extra branches to compute the if() outside of the loop.

I get better performance with the new form of the loop. How, does PPC get better results with two tests?

Quoted 9 lines

Quoted 9 lines

Quoted 7 lines

lib/crc32.c +0 -3

-/* implements slicing-by-4 or slicing-by-8 algorithm */
-static inline u32
-crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32

(*tab)[256])

After careful measurements and looking at asm code I figured out that

Quoted 6 lines

there

Quoted 2 lines

was no penalty for using 2D array. That allowed me to go back to the original form.

What about my suggestion to assign each table to a ptr? This was good for ppc so if it doesn't slow x86 it should be added.

Gcc is very clever and inlined crc32_body() into crc32_le() and crc32_be() and then replaced references to tab[x][y] with references to crc32table_le and crc32table_be plus a constant offset which depended on the first index ([x]). So in effect it completely unrolled back to 1D arrays as (crc32table_le + offset)[y], which is equivalent to the t0_le[y] code I had before.

-----Original Message-----
From: Joakim Tjernlund [mailto:[email protected]]
Sent: Wednesday, August 10, 2011 6:41 AM
To: Bob Pearson
Cc: [email protected]; [email protected]; George Spelvin; [email protected]
Subject: RE: [patch v3 7/7] crc32: final-cleanup.diff

"Bob Pearson" <[email protected]> wrote on 2011/08/10 01:05:56:

Quoted 7 lines

Quoted 4 lines

Doing this adds one insn to ppc. What is good for x86 isn't for pcc32 (and I guess any modern arch).

I looked at the assembly output from the original code and I see two compares at the end of the first loop, one for --len and one for (buf &

Quoted 1 line

which it has to compute. You are better off just computing buf & 3 once

and

Quoted 1 line

comparing with len once to compute init_len then in each iteration in

Quoted 66 lines

loop you only have to compare one thing.

As proposed:

        init_len = min((-((uintptr_t)buf)) & 3, len);
        ...

        /* process unaligned initial bytes */
        for (i = 0; i < init_len; i++)
                DO_CRC(*buf++);

crc32x_le:
<.....>
negq %rcx # (-buf)
andl $3, %ecx # (-buf) & 3
cmpq %rdx, %rcx # min()
cmova %rdx, %rcx # init_len =
xorl %edi, %edi # i = 0
<.....>
jmp .L2
.L3:

# crc = tab[0][(crc ^ (*buf++)) & 255] ^ (crc >> 8)
        movb    (%rsi,%rdi), %dl         # buf[i]
        incq    %rdi               # buf++
        xorl    %eax, %edx            # crc ^ *buf++
        shrl    $8, %eax            # crc >> 8
        movzbl  %dl, %edx            # & 255
        xorl    crc32table_le(,%rdx,4), %eax                 # crc =
tab[...] ^ (crc >> 8)
.L2:
        cmpq    %rcx, %rdi            # compare i with
init_len
        jb      .L3
        <.....>

As was originally:

        if (unlikely((long)buf & 3 && len)) {
                do {
                        DO_CRC(*buf++);
                } while ((--len) && ((long)buf)&3);
        }

crc32x_le:

        pushq   %rbp
        movl    %edi, %eax
        pushq   %rbx
        testb   $3, %sil
        je      .L16
        testq   %rdx, %rdx
.L25:
        je      .L16
        movb    (%rsi), %cl            # *p
        incq    %rsi               # p++
        xorl    %eax, %ecx            # crc ^ *p
        shrl    $8, %eax            # crc >> 8
        movzbl  %cl, %ecx            # ... & 255
        xorl    crc32table_le(,%rcx,4), %eax      # tab[...] ^ (crc >>

8)
decq %rdx # len--
je .L16 # if len != 0
continue
testb $3, %sil # buf & 3
jmp .L25 # if buf & 3
continue
.L16:

Quoted 1 line

The first loop has 8 instructions second one has 11 instructions. First

Quoted 4 lines

has slightly more setup to compute init_len, second loop has a couple of extra branches to compute the if() outside of the loop.

I get better performance with the new form of the loop. How, does PPC

get

Quoted 1 line

better results with two tests?

You are right, even ppc gets less insns in the byte loop. However I tested your latest patch series and your version is a tiny bit slower than my

version(numbers below)
Probably due to that your version has a higher startup cost and uses more registers(3 regs are pushed to the stack vs. 2 regs in mine)

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

lib/crc32.c MODULE_LICENSE("GPL");

Quoted 6 lines

lib/crc32.c +0 -3

-/* implements slicing-by-4 or slicing-by-8 algorithm */
-static inline u32
-crc32_body(u32 crc, unsigned char const *buf, size_t len, const

Quoted 3 lines

Quoted 3 lines

Quoted 3 lines

Quoted 1 line

(*tab)[256])

After careful measurements and looking at asm code I figured out

Quoted 8 lines

Quoted 6 lines

there

Quoted 2 lines

was no penalty for using 2D array. That allowed me to go back to the original form.

What about my suggestion to assign each table to a ptr? This was good for ppc so if it doesn't slow x86 it should be added.

Gcc is very clever and inlined crc32_body() into crc32_le() and

Quoted 1 line

and then replaced references to tab[x][y] with references to

Quoted 1 line

and crc32table_be plus a constant offset which depended on the first

Quoted 2 lines

([x]). So in effect it completely unrolled back to 1D arrays as (crc32table_le + offset)[y], which is equivalent to the t0_le[y] code I

Quoted 1 line

before.

So x86 optimizes the table accesses well then. PPC32 doesn't and adding my small optimization makes a huge difference:
org:
crc32: CRC_LE_BITS = 8, CRC_BE BITS = 8
crc32: self tests passed, processed 225944 bytes in 2257673 nsec

my t0, t1, t2, t3 ptrs
crc32: CRC_LE_BITS = 8, CRC_BE BITS = 8
crc32: self tests passed, processed 225944 bytes in 1949869 nsec

Numbers for 32 bits with your patch.

v3 up to 6 of 7
crc32: CRC_LE_BITS = 32, CRC_BE BITS = 32
crc32: self tests passed, processed 225944 bytes in 2362044 nsec

v3 up to 7 of 7
crc32: CRC_LE_BITS = 32, CRC_BE BITS = 32
crc32: self tests passed, processed 225944 bytes in 2149972 nsec

my t0, t1, t2, t3 ptrs on v3 7 of 7
crc32: CRC_LE_BITS = 32, CRC_BE BITS = 32
crc32: self tests passed, processed 225944 bytes in 1953290 nsec

Finally, 64 bits on PPC is broken in v3!

Jocke

From: "Bob Pearson" <[email protected]>
To: "'Joakim Tjernlund'" <[email protected]>
Cc: <[email protected]>, <[email protected]>, "'George Spelvin'" <[email protected]>, <[email protected]>
Date: 2011/08/10 17:13
Subject: RE: [patch v3 7/7] crc32: final-cleanup.diff

OK. Can you post your current version of crc32.c? I'll try to merge them together.

From f5268d74f1a81610820e92785397f1247946ce15 Mon Sep 17 00:00:00 2001

-----Original Message-----
From: Joakim Tjernlund [mailto:[email protected]]
Sent: Wednesday, August 10, 2011 10:49 AM
To: Bob Pearson
Cc: [email protected]; [email protected]; 'George Spelvin'; [email protected]
Subject: RE: [patch v3 7/7] crc32: final-cleanup.diff

"Bob Pearson" <[email protected]> wrote on 2011/08/10 17:13:00:

Quoted 3 lines

From: "Bob Pearson" <[email protected]>
To: "'Joakim Tjernlund'" <[email protected]>
Cc: <[email protected]>, <[email protected]>,

"'George Spelvin'" <[email protected]>, <[email protected]>

Quoted 5 lines

Date: 2011/08/10 17:13
Subject: RE: [patch v3 7/7] crc32: final-cleanup.diff

OK. Can you post your current version of crc32.c? I'll try to merge them together.

OK, here it comes again, prefably this should be the first patch in the series.

From f5268d74f1a81610820e92785397f1247946ce15 Mon Sep 17 00:00:00 2001
From: Joakim Tjernlund <[email protected]>
Date: Fri, 5 Aug 2011 17:49:42 +0200
Subject: [PATCH] crc32: Optimize inner loop.

taking a pointer reference to each row in the crc table matrix, one can reduce the inner loop with a few insn's on RISC archs like PowerPC.

---
 lib/crc32.c |   21 +++++++++++----------
 1 files changed, 11 insertions(+), 10 deletions(-)

lib/crc32.c +11 -10

index 4855995..b06d1e7 100644
@@ -51,20 +51,21 @@ static inline u32
 crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32
 (*tab)[256])
 {
 # ifdef __LITTLE_ENDIAN
-#  define DO_CRC(x) crc = tab[0][(crc ^ (x)) & 255] ^ (crc >> 8)
-#  define DO_CRC4 crc = tab[3][(crc) & 255] ^ \
-		tab[2][(crc >> 8) & 255] ^ \
-		tab[1][(crc >> 16) & 255] ^ \
-		tab[0][(crc >> 24) & 255]
+#  define DO_CRC(x) crc = t0[(crc ^ (x)) & 255] ^ (crc >> 8)
+#  define DO_CRC4 crc = t3[(crc) & 255] ^ \
+		t2[(crc >> 8) & 255] ^ \
+		t1[(crc >> 16) & 255] ^ \
+		t0[(crc >> 24) & 255]
 # else
-#  define DO_CRC(x) crc = tab[0][((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
-#  define DO_CRC4 crc = tab[0][(crc) & 255] ^ \
-		tab[1][(crc >> 8) & 255] ^ \
-		tab[2][(crc >> 16) & 255] ^ \
-		tab[3][(crc >> 24) & 255]
+#  define DO_CRC(x) crc = t0[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
+#  define DO_CRC4 crc = t0[(crc) & 255] ^ \
+		t1[(crc >> 8) & 255] ^  \
+		t2[(crc >> 16) & 255] ^	\
+		t3[(crc >> 24) & 255]
 # endif
 	const u32 *b;
 	size_t    rem_len;
+	const u32 *t0=tab[0], *t1=tab[1], *t2=tab[2], *t3=tab[3];
 
 	/* Align it */

if (unlikely((long)buf & 3 && len)) {
--
1.7.3.4