[PATCH, ARM] ARMv7 optimised strlen

["Dr. David Alan Gilbert" <david dot gilbert at linaro dot org>]

Hi,
  Please find below an ARMv7 optimised strlen routine which uses
techniques similar to those posted in my memchr patch a few days ago.
(Indeed this patch is based on the memchr patch, the overlap is
only in terms of needing a fix that was in the memchr patch for arm-asm.h)

The following graph shows the performance benefit:
https://wiki.linaro.org/WorkingGroups/ToolChain/Benchmarks/InitialStrlen?action=AttachFile&do=view&target=sizes-strlen-04.png

(That was actually done without the ldrd that this version uses,
but I've compared the ldrd to the existing version on a9 and it matches).

This patch ifdef's the existing assembler version so that it is used
in the optimise for size case or for older CPUs, and only uses this
version on newer CPUs.

It's been tested on arm-sim target and the same assembly has been
tested on eglibc as well on real hardware under Linux.

As with the memchr patch, I've included the Makefile.in changes in the
patch but it would be better to regenerate.

(I'm out of the office next week, so may not respond to comments for a few
days).

Dave

2011-10-13 Dr David Alan Gilbert <david.gilbert@linaro.org>
 libc/machine/arm/Makefile.am (lib_a_SOURCES): Add strlen-armv7.S
 libc/machine/arm/strlen-armv7.S: New file
 libc/machine/arm/strlen.c: ifdef optimised code so it isn't for v7 or 6t2
 libc/machine/arm/Makefile.in: Manually add same changes as .am

diff -urN src.memchr/newlib/libc/machine/arm/Makefile.am src/newlib/libc/machine/arm/Makefile.am
--- src.memchr/newlib/libc/machine/arm/Makefile.am	2011-10-12 11:39:26.000000000 +0100
+++ src/newlib/libc/machine/arm/Makefile.am	2011-10-13 13:51:34.000000000 +0100
@@ -8,8 +8,9 @@
 
 noinst_LIBRARIES = lib.a
 
-lib_a_SOURCES = setjmp.S access.c strlen.c strcmp.c strcpy.c \
-		memchr-stub.c memchr.S
+lib_a_SOURCES = setjmp.S access.c strcmp.c strcpy.c \
+		memchr-stub.c memchr.S\
+		strlen.c strlen-armv7.S
 lib_a_CCASFLAGS=$(AM_CCASFLAGS)
 lib_a_CFLAGS = $(AM_CFLAGS)
 
diff -urN src.memchr/newlib/libc/machine/arm/Makefile.in src/newlib/libc/machine/arm/Makefile.in
--- src.memchr/newlib/libc/machine/arm/Makefile.in	2011-10-12 11:43:40.000000000 +0100
+++ src/newlib/libc/machine/arm/Makefile.in	2011-10-13 15:05:59.000000000 +0100
@@ -53,9 +53,10 @@
 lib_a_AR = $(AR) $(ARFLAGS)
 lib_a_LIBADD =
 am_lib_a_OBJECTS = lib_a-setjmp.$(OBJEXT) lib_a-access.$(OBJEXT) \
-	lib_a-strlen.$(OBJEXT) lib_a-strcmp.$(OBJEXT) \
+	lib_a-strcmp.$(OBJEXT) \
 	lib_a-strcpy.$(OBJEXT) \
-	lib_a-memchr.$(OBJEXT) lib_a-memchr-stub.$(OBJEXT)
+	lib_a-memchr.$(OBJEXT) lib_a-memchr-stub.$(OBJEXT) \
+	lib_a-strlen.$(OBJEXT) lib_a-strlen-armv7.$(OBJEXT)
 lib_a_OBJECTS = $(am_lib_a_OBJECTS)
 DEFAULT_INCLUDES = -I.@am__isrc@
 depcomp =
@@ -175,7 +176,7 @@
 INCLUDES = $(NEWLIB_CFLAGS) $(CROSS_CFLAGS) $(TARGET_CFLAGS)
 AM_CCASFLAGS = $(INCLUDES)
 noinst_LIBRARIES = lib.a
-lib_a_SOURCES = setjmp.S access.c strlen.c strcmp.c strcpy.c memchr.S memchr-stub.c
+lib_a_SOURCES = setjmp.S access.c strlen.c strlen-armv7.S strcmp.c strcpy.c memchr.S memchr-stub.c
 lib_a_CCASFLAGS = $(AM_CCASFLAGS)
 lib_a_CFLAGS = $(AM_CFLAGS)
 ACLOCAL_AMFLAGS = -I ../../.. -I ../../../..
@@ -250,6 +251,12 @@
 lib_a-memchr.obj: memchr.S
 	$(CCAS) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(lib_a_CCASFLAGS) $(CCASFLAGS) -c -o lib_a-memchr.obj `if test -f 'memchr.S'; then $(CYGPATH_W) 'memchr.S'; else $(CYGPATH_W) '$(srcdir)/memchr.S'; fi`
 
+lib_a-strlen-armv7.o: strlen-armv7.S
+	$(CCAS) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(lib_a_CCASFLAGS) $(CCASFLAGS) -c -o lib_a-strlen-armv7.o `test -f 'strlen-armv7.S' || echo '$(srcdir)/'`strlen-armv7.S
+
+lib_a-strlen-armv7.obj: strlen-armv7.S
+	$(CCAS) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(lib_a_CCASFLAGS) $(CCASFLAGS) -c -o lib_a-strlen-armv7.obj `if test -f 'strlen-armv7.S'; then $(CYGPATH_W) 'strlen-armv7.S'; else $(CYGPATH_W) '$(srcdir)/strlen-armv7.S'; fi`
+
 .c.o:
 	$(COMPILE) -c $<
 
diff -urN src.memchr/newlib/libc/machine/arm/strlen-armv7.S src/newlib/libc/machine/arm/strlen-armv7.S
--- src.memchr/newlib/libc/machine/arm/strlen-armv7.S	1970-01-01 01:00:00.000000000 +0100
+++ src/newlib/libc/machine/arm/strlen-armv7.S	2011-10-13 15:09:25.000000000 +0100
@@ -0,0 +1,127 @@
+/* Copyright (c) 2010-2011, Linaro Limited
+   All rights reserved.
+
+   Redistribution and use in source and binary forms, with or without
+   modification, are permitted provided that the following conditions
+   are met:
+
+      * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+      * Redistributions in binary form must reproduce the above copyright
+      notice, this list of conditions and the following disclaimer in the
+      documentation and/or other materials provided with the distribution.
+
+      * Neither the name of Linaro Limited nor the names of its
+      contributors may be used to endorse or promote products derived
+      from this software without specific prior written permission.
+
+   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+   HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+   Written by Dave Gilbert <david.gilbert@linaro.org>
+
+   This strlen routine is optimised on a Cortex-A9 and should work on
+   all ARMv7 processors.   This routine is reasonably fast for short
+   strings, but is probably slower than a simple implementation if all
+   your strings are very short */
+
+@ 2011-02-08 david.gilbert@linaro.org
+@    Extracted from local git 6848613a
+@ 2011-10-13 david.gilbert@linaro.org
+@    Extracted from cortex-strings bzr rev 63
+@      Integrate to newlib, flip to ldrd
+@      Pull in Endian macro from my memchr
+
+#include "arm_asm.h"
+
+@ NOTE: This ifdef MUST match the ones in arm/strlen.c
+@ We fallback to the one in arm/strlen.c for size optimised or
+@ for older arch's
+#if defined(_ISA_ARM_7) || defined(__ARM_ARCH_6T2__) && \
+    !(defined (__OPTIMIZE_SIZE__) || defined (PREFER_SIZE_OVER_SPEED) || \
+      (defined (__thumb__) && !defined (__thumb2__)))
+
+@ this lets us check a flag in a 00/ff byte easily in either endianness
+#ifdef __ARMEB__
+#define CHARTSTMASK(c) 1<<(31-(c*8))
+#else
+#define CHARTSTMASK(c) 1<<(c*8)
+#endif
+
+@------------------------------------------------------------------------------
+	.syntax unified
+	.arch armv7-a
+
+	.thumb_func
+	.align 2
+	.p2align 4,,15
+	.global strlen
+	.type strlen,%function
+strlen:
+	@ r0 = string
+	@ returns count of bytes in string not including terminator
+	mov	r1, r0
+	push	{ r4,r6 }
+	mvns	r6, #0		@ all F
+	movs	r4, #0
+	tst	r0, #7
+	beq	2f
+
+1:
+	ldrb	r2, [r1], #1
+	tst	r1, #7		@ Hit alignment yet?
+	cbz	r2, 10f		@ Exit if we found the 0
+	bne	1b
+
+	@ So we're now aligned
+2:
+	ldrd    r2,r3,[r1],#8
+	uadd8	r2, r2, r6	@ Par add 0xff - sets the GE bits for bytes!=0
+	sel	r2, r4, r6	@ bytes are 00 for none-00 bytes,
+				@ or ff for 00 bytes - NOTE INVERSION
+	uadd8	r3, r3, r6	@ Par add 0xff - sets the GE bits for bytes!=0
+	sel	r3, r2, r6	@ chained...bytes are 00 for none-00 bytes,
+				@ or ff for 00 bytes - NOTE INVERSION
+	cmp	r3, #0
+	beq	2b
+
+strlenendtmp:
+	@ One (or more) of the bytes we loaded was 0 - but which one?
+	@ r2 has the mask corresponding to the first loaded word
+	@ r3 has a combined mask of the two words - but if r2 was all-non 0 
+	@ then it's just the 2nd words
+	cmp	r2, #0
+	itte	eq
+	moveq	r2, r3		@ the end is in the 2nd word
+	subeq	r1,r1,#3
+	subne	r1,r1,#7
+
+	@ r1 currently points to the 2nd byte of the word containing the 0
+	tst	r2, # CHARTSTMASK(0)	@ 1st character
+	bne	10f
+	adds	r1,r1,#1
+	tst	r2, # CHARTSTMASK(1)	@ 2nd character
+	ittt	eq
+	addeq	r1,r1,#1
+	tsteq	r2, # (3<<15)	@ 2nd & 3rd character
+	@ If not the 3rd must be the last one
+	addeq	r1,r1,#1
+
+10:
+	@ r0 is still at the beginning, r1 is pointing 1 byte after the nul
+	sub	r0, r1, r0
+	subs	r0, r0, #1
+	pop	{ r4, r6 }
+	bx	lr
+
+#endif
diff -urN src.memchr/newlib/libc/machine/arm/strlen.c src/newlib/libc/machine/arm/strlen.c
--- src.memchr/newlib/libc/machine/arm/strlen.c	2009-03-16 20:12:30.000000000 +0000
+++ src/newlib/libc/machine/arm/strlen.c	2011-10-13 15:27:49.000000000 +0100
@@ -60,6 +60,8 @@
 }
 #else
 
+#if !(defined(_ISA_ARM_7) || defined(__ARM_ARCH_6T2__))
+
 size_t __attribute__((naked))
 strlen (const char* str)
 {
@@ -178,3 +180,4 @@
        "RETURN");
 }
 #endif
+#endif