PPC optimized string function.
authordrepper <drepper>
Thu, 11 Sep 1997 11:31:23 +0000 (11:31 +0000)
committerdrepper <drepper>
Thu, 11 Sep 1997 11:31:23 +0000 (11:31 +0000)
sysdeps/powerpc/memset.S [new file with mode: 0644]
sysdeps/powerpc/strchr.S [new file with mode: 0644]
sysdeps/powerpc/strcmp.S [new file with mode: 0644]
sysdeps/powerpc/strlen.S [new file with mode: 0644]

diff --git a/sysdeps/powerpc/memset.S b/sysdeps/powerpc/memset.S
new file mode 100644 (file)
index 0000000..6ac32dd
--- /dev/null
@@ -0,0 +1,199 @@
+/* Optimized memset implementation for PowerPC.
+   Copyright (C) 1997 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Library General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Library General Public License for more details.
+
+   You should have received a copy of the GNU Library General Public
+   License along with the GNU C Library; see the file COPYING.LIB.  If not,
+   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+   Boston, MA 02111-1307, USA.  */
+
+#include <sysdep.h>
+
+EALIGN(memset,5,1)
+/* __ptr_t [r3] memset (__ptr_t s [r3], int c [r4], size_t n [r5]));
+   Returns 's'.
+
+   The memset is done in three sizes: byte (8 bits), word (32 bits),
+   cache line (256 bits). There is a special case for setting cache lines
+   to 0, to take advantage of the dcbz instruction.
+   r6: current address we are storing at
+   r7: number of bytes we are setting now (when aligning)  */
+
+/* take care of case for size <= 4  */
+       cmplwi %cr1,%r5,4
+       andi.  %r7,%r3,3
+       mr     %r6,%r3
+       ble-   %cr1,L(small)
+/* align to word boundary  */
+       cmplwi %cr5,%r5,31
+       rlwimi %r4,%r4,8,16,23
+       beq+   L(aligned)               # 8th instruction from .align
+       mtcrf  0x01,%r3
+       subfic %r7,%r7,4
+       add    %r6,%r6,%r7
+       sub    %r5,%r5,%r7
+       bf+    31,0f
+       stb    %r4,0(%r3)
+       bt     30,L(aligned)
+0:     sth    %r4,-2(%r6)              #  16th instruction from .align
+/* take care of case for size < 31 */
+L(aligned):
+       mtcrf  0x01,%r5
+       rlwimi %r4,%r4,16,0,15
+       ble    %cr5,L(medium)
+/* align to cache line boundary...  */
+       andi.  %r7,%r6,0x1C
+       subfic %r7,%r7,0x20
+       beq    L(caligned)
+       mtcrf  0x01,%r7
+       add    %r6,%r6,%r7
+       sub    %r5,%r5,%r7
+       cmplwi %cr1,%r7,0x10
+       mr     %r8,%r6
+       bf     28,1f
+       stw    %r4,-4(%r8)
+       stwu   %r4,-8(%r8)
+1:     blt    %cr1,2f
+       stw    %r4,-4(%r8)      # 32nd instruction from .align
+       stw    %r4,-8(%r8)
+       stw    %r4,-12(%r8)
+       stwu   %r4,-16(%r8)
+2:     bf     29,L(caligned)
+       stw    %r4,-4(%r8)
+/* now aligned to a cache line.  */
+L(caligned):
+       cmplwi %cr1,%r4,0
+       clrrwi. %r7,%r5,5
+       mtcrf  0x01,%r5         # 40th instruction from .align
+       beq    %cr1,L(zloopstart) # special case for clearing memory using dcbz
+       srwi   %r0,%r7,5
+       mtctr  %r0
+       beq    L(medium)        # we may not actually get to do a full line
+       clrlwi. %r5,%r5,27
+       add    %r6,%r6,%r7
+0:     li     %r8,-0x40
+       bdz    L(cloopdone)     # 48th instruction from .align
+
+3:     dcbz   %r8,%r6
+       stw    %r4,-4(%r6)
+       stw    %r4,-8(%r6)
+       stw    %r4,-12(%r6)
+       stw    %r4,-16(%r6)
+       nop                     # let 601 fetch last 4 instructions of loop
+       stw    %r4,-20(%r6)
+       stw    %r4,-24(%r6)     # 56th instruction from .align
+       nop                     # let 601 fetch first 8 instructions of loop
+       stw    %r4,-28(%r6)
+       stwu   %r4,-32(%r6)
+       bdnz   3b
+L(cloopdone):
+       stw    %r4,-4(%r6)
+       stw    %r4,-8(%r6)
+       stw    %r4,-12(%r6)
+       stw    %r4,-16(%r6)     # 64th instruction from .align
+       stw    %r4,-20(%r6)
+       cmplwi %cr1,%r5,16
+       stw    %r4,-24(%r6)
+       stw    %r4,-28(%r6)
+       stwu   %r4,-32(%r6)
+       beqlr
+       add    %r6,%r6,%r7
+       b      L(medium_tail2)  # 72nd instruction from .align
+
+       .align 5
+       nop
+/* Clear lines of memory in 128-byte chunks.  */
+L(zloopstart):
+       clrlwi %r5,%r5,27
+       mtcrf  0x02,%r7
+       srwi.  %r0,%r7,7
+       mtctr  %r0
+       li     %r7,0x20
+       li     %r8,-0x40
+       cmplwi %cr1,%r5,16      # 8
+       bf     26,0f
+       dcbz   0,%r6
+       addi   %r6,%r6,0x20
+0:     li     %r9,-0x20
+       bf     25,1f
+       dcbz   0,%r6
+       dcbz   %r7,%r6
+       addi   %r6,%r6,0x40     # 16
+1:     cmplwi %cr5,%r5,0
+       beq    L(medium)
+L(zloop):
+       dcbz   0,%r6
+       dcbz   %r7,%r6
+       addi   %r6,%r6,0x80
+       dcbz   %r8,%r6
+       dcbz   %r9,%r6
+       bdnz   L(zloop)
+       beqlr  %cr5
+       b      L(medium_tail2)
+
+       .align 5
+L(small):
+/* Memset of 4 bytes or less.  */
+       cmplwi %cr5,%r5,1
+       cmplwi %cr1,%r5,3
+       bltlr  %cr5
+       stb    %r4,0(%r6)
+       beqlr  %cr5
+       nop
+       stb    %r4,1(%r6)
+       bltlr  %cr1
+       stb    %r4,2(%r6)
+       beqlr  %cr1
+       nop
+       stb    %r4,3(%r6)
+       blr
+
+/* Memset of 0-31 bytes.  */
+       .align 5
+L(medium):
+       cmplwi %cr1,%r5,16
+L(medium_tail2):
+       add    %r6,%r6,%r5
+L(medium_tail):
+       bt-    31,L(medium_31t)
+       bt-    30,L(medium_30t)
+L(medium_30f):
+       bt-    29,L(medium_29t)
+L(medium_29f):
+       bge-   %cr1,L(medium_27t)
+       bflr-  28
+       stw    %r4,-4(%r6)              # 8th instruction from .align
+       stw    %r4,-8(%r6)
+       blr
+
+L(medium_31t):
+       stbu   %r4,-1(%r6)
+       bf-    30,L(medium_30f)
+L(medium_30t):
+       sthu   %r4,-2(%r6)
+       bf-    29,L(medium_29f)
+L(medium_29t):
+       stwu   %r4,-4(%r6)
+       blt-   %cr1,L(medium_27f)       # 16th instruction from .align
+L(medium_27t):
+       stw    %r4,-4(%r6)
+       stw    %r4,-8(%r6)
+       stw    %r4,-12(%r6)
+       stwu   %r4,-16(%r6)
+L(medium_27f):
+       bflr-  28
+L(medium_28t):
+       stw    %r4,-4(%r6)
+       stw    %r4,-8(%r6)
+       blr
+END(memset)
diff --git a/sysdeps/powerpc/strchr.S b/sysdeps/powerpc/strchr.S
new file mode 100644 (file)
index 0000000..156d4d1
--- /dev/null
@@ -0,0 +1,111 @@
+/* Optimized strchr implementation for PowerPC.
+   Copyright (C) 1997 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Library General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Library General Public License for more details.
+
+   You should have received a copy of the GNU Library General Public
+   License along with the GNU C Library; see the file COPYING.LIB.  If not,
+   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+   Boston, MA 02111-1307, USA.  */
+
+#include <sysdep.h>
+
+/* See strlen.s for comments on how this works.  */
+
+/* char * [r3] strchr (const char *s [r3] , int c [r4] )
+
+   r0: a temporary
+   r3: our return result.
+   r4: byte we're looking for, spread over the whole word
+   r5: the current word
+   r6: the constant 0xfefefeff (-0x01010101)
+   r7: the constant 0x7f7f7f7f
+   r8: pointer to the current word.
+   r9: a temporary
+   r10:        the number of bits we should ignore in the first word
+   r11:        a mask with the bits to ignore set to 0
+   r12:        a temporary  */
+ENTRY(strchr)
+       rlwimi %r4,%r4,8,16,23
+       li   %r11,-1
+       rlwimi %r4,%r4,16,0,15
+       lis  %r6,0xfeff
+       lis  %r7,0x7f7f
+       clrrwi %r8,%r3,2
+       addi %r7,%r7,0x7f7f
+       addi %r6,%r6,0xfffffeff
+       rlwinm %r10,%r3,3,27,28
+/* Test the first (partial?) word.  */
+       lwz  %r5,0(%r8)
+       srw  %r11,%r11,%r10
+       orc  %r5,%r5,%r11
+       add  %r0,%r6,%r5
+       nor  %r9,%r7,%r5
+       and. %r0,%r0,%r9
+       xor  %r12,%r4,%r5
+       orc  %r12,%r12,%r11
+       b    L(loopentry)
+
+/* The loop.  */
+
+L(loop):lwzu %r5,4(%r8)
+       and. %r0,%r0,%r9
+/* Test for 0.  */
+       add  %r0,%r6,%r5
+       nor  %r9,%r7,%r5
+       bne  L(foundit)
+       and. %r0,%r0,%r9
+/* Start test for the bytes we're looking for.  */
+       xor  %r12,%r4,%r5
+L(loopentry):
+       add  %r0,%r6,%r12
+       nor  %r9,%r7,%r12
+       beq  L(loop)
+/* There is a zero byte in the word, but may also be a matching byte (either
+   before or after the zero byte).  In fact, we may be looking for a
+   zero byte, in which case we return a match.  We guess that this hasn't
+   happened, though.  */
+L(missed):
+       and. %r0,%r0,%r9
+       li   %r3,0
+       beqlr
+/* It did happen. Decide which one was first...
+   I'm not sure if this is actually faster than a sequence of
+   rotates, compares, and branches (we use it anyway because it's shorter).  */
+       and  %r6,%r7,%r5
+       or   %r11,%r7,%r5
+       and  %r0,%r7,%r12
+       or   %r10,%r7,%r12
+       add  %r6,%r6,%r7
+       add  %r0,%r0,%r7
+       nor  %r5,%r11,%r6
+       nor  %r9,%r10,%r0
+       cmplw %r5,%r9
+       bgtlr
+       cntlzw %r4,%r9
+       srwi %r4,%r4,3
+       add  %r3,%r8,%r4
+       blr
+
+L(foundit):
+       and  %r0,%r7,%r12
+       or   %r10,%r7,%r12
+       add  %r0,%r0,%r7
+       nor  %r9,%r10,%r0
+       cntlzw %r4,%r9
+       subi %r8,%r8,4
+       srwi %r4,%r4,3
+       add  %r3,%r8,%r4
+       blr
+END(strchr)
+
+weak_alias(strchr,index)
diff --git a/sysdeps/powerpc/strcmp.S b/sysdeps/powerpc/strcmp.S
new file mode 100644 (file)
index 0000000..9f4d134
--- /dev/null
@@ -0,0 +1,115 @@
+/* Optimized strcmp implementation for PowerPC.
+   Copyright (C) 1997 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Library General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Library General Public License for more details.
+
+   You should have received a copy of the GNU Library General Public
+   License along with the GNU C Library; see the file COPYING.LIB.  If not,
+   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+   Boston, MA 02111-1307, USA.  */
+
+#include <sysdep.h>
+
+/* See strlen.s for comments on how the end-of-string testing works.  */
+
+EALIGN(strcmp,4,0)
+/* int [r3] strcmp (const char *p1 [r3], const char *p2 [r4])  */
+
+/* General register assignments:
+   r0: temporary
+   r3: pointer to previous word in s1
+   r4: pointer to previous word in s2
+   r5: current word from s1
+   r6: current word from s2
+   r7: 0xfefefeff
+   r8: 0x7f7f7f7f
+   r9: ~(word in s1 | 0x7f7f7f7f)  */
+
+/* Register assignments in the prologue:
+   r10:        low 2 bits of p2-p1
+   r11:        mask to orc with r5/r6  */
+
+       or    %r0,%r4,%r3
+       clrlwi. %r0,%r0,30
+       lis   %r7,0xfeff
+       bne   L(unaligned)
+
+       lwz   %r5,0(%r3)
+       lwz   %r6,0(%r4)
+       lis   %r8,0x7f7f
+       addi  %r7,%r7,-0x101
+       addi  %r8,%r8,0x7f7f
+       b     1f
+
+0:     lwzu  %r5,4(%r3)
+       bne   %cr1,L(different)
+       lwzu  %r6,4(%r4)
+1:     add   %r0,%r7,%r5
+       nor   %r9,%r8,%r5
+       and.  %r0,%r0,%r9
+       cmpw  %cr1,%r5,%r6
+       beq+  0b
+L(endstring):
+/* OK. We've hit the end of the string. We need to be careful that
+   we don't compare two strings as different because of gunk beyond
+   the end of the strings...  */
+       and   %r0,%r8,%r5
+       beq   %cr1,L(equal)
+       add   %r0,%r0,%r8
+       xor.  %r10,%r5,%r6
+       andc  %r9,%r9,%r0
+       blt-  L(highbit)
+       cntlzw %r10,%r10
+       cntlzw %r9,%r9
+       addi  %r9,%r9,7
+       cmpw  %cr1,%r9,%r10
+       sub   %r3,%r5,%r6
+       bgelr+ %cr1
+L(equal):
+       li    %r3,0
+       blr
+
+L(different):
+       lwz   %r5,-4(%r3)
+       xor.  %r10,%r5,%r6
+       sub   %r3,%r5,%r6
+       bgelr+
+L(highbit):
+       mr    %r3,%r6
+       blr
+
+
+/* Oh well.  In this case, we just do a byte-by-byte comparison.  */
+       .align 4
+L(unaligned):
+       lbz   %r5,0(%r3)
+       lbz   %r6,0(%r4)
+       b     1f
+
+0:     lbzu  %r5,1(%r3)
+       bne-  4f
+       lbzu  %r6,1(%r4)
+1:     cmpwi %cr1,%r5,0
+       beq-  %cr1,3f
+       cmpw  %r5,%r6
+       bne-  3f
+       lbzu  %r5,1(%r3)
+       lbzu  %r6,1(%r4)
+       cmpwi %cr1,%r5,0
+       cmpw  %r5,%r6
+       bne+  %cr1,0b
+3:     sub   %r3,%r5,%r6
+       blr
+4:     lbz   %r5,-1(%r3)
+       sub   %r3,%r5,%r6
+       blr
+END(strcmp)
diff --git a/sysdeps/powerpc/strlen.S b/sysdeps/powerpc/strlen.S
new file mode 100644 (file)
index 0000000..dc6660b
--- /dev/null
@@ -0,0 +1,144 @@
+/* Optimized strlen implementation for PowerPC.
+   Copyright (C) 1997 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Library General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Library General Public License for more details.
+
+   You should have received a copy of the GNU Library General Public
+   License along with the GNU C Library; see the file COPYING.LIB.  If not,
+   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+   Boston, MA 02111-1307, USA.  */
+
+#include <sysdep.h>
+
+/* The algorithm here uses the following techniques:
+
+   1) Given a word 'x', we can test to see if it contains any 0 bytes
+      by subtracting 0x01010101, and seeing if any of the high bits of each
+      byte changed from 0 to 1. This works because the least significant
+      0 byte must have had no incoming carry (otherwise it's not the least
+      significant), so it is 0x00 - 0x01 == 0xff. For all other
+      byte values, either they have the high bit set initially, or when
+      1 is subtracted you get a value in the range 0x00-0x7f, none of which
+      have their high bit set. The expression here is
+      (x + 0xfefefeff) & ~(x | 0x7f7f7f7f), which gives 0x00000000 when
+      there were no 0x00 bytes in the word.
+
+   2) Given a word 'x', we can test to see _which_ byte was zero by
+      calculating ~(((x & 0x7f7f7f7f) + 0x7f7f7f7f) | x | 0x7f7f7f7f).
+      This produces 0x80 in each byte that was zero, and 0x00 in all
+      the other bytes. The '| 0x7f7f7f7f' clears the low 7 bits in each
+      byte, and the '| x' part ensures that bytes with the high bit set
+      produce 0x00. The addition will carry into the high bit of each byte
+      iff that byte had one of its low 7 bits set. We can then just see
+      which was the most significant bit set and divide by 8 to find how
+      many to add to the index.
+      This is from the book 'The PowerPC Compiler Writer's Guide',
+      by Steve Hoxey, Faraydon Karim, Bill Hay and Hank Warren.
+
+   We deal with strings not aligned to a word boundary by taking the
+   first word and ensuring that bytes not part of the string
+   are treated as nonzero. To allow for memory latency, we unroll the
+   loop a few times, being careful to ensure that we do not read ahead
+   across cache line boundaries.
+
+   Questions to answer:
+   1) How long are strings passed to strlen? If they're often really long,
+   we should probably use cache management instructions and/or unroll the
+   loop more. If they're often quite short, it might be better to use
+   fact (2) in the inner loop than have to recalculate it.
+   2) How popular are bytes with the high bit set? If they are very rare,
+   on some processors it might be useful to use the simpler expression
+   ~((x - 0x01010101) | 0x7f7f7f7f) (that is, on processors with only one
+   ALU), but this fails when any character has its high bit set.  */
+
+/* Some notes on register usage: Under the SVR4 ABI, we can use registers
+   0 and 3 through 12 (so long as we don't call any procedures) without
+   saving them. We can also use registers 14 through 31 if we save them.
+   We can't use r1 (it's the stack pointer), r2 nor r13 because the user
+   program may expect them to hold their usual value if we get sent
+   a signal. Integer parameters are passed in r3 through r10.
+   We can use condition registers cr0, cr1, cr5, cr6, and cr7 without saving
+   them, the others we must save.  */
+
+ENTRY(strlen)
+/* On entry, r3 points to the string, and it's left that way.
+   We use r6 to store 0xfefefeff, and r7 to store 0x7f7f7f7f.
+   r4 is used to keep the current index into the string; r5 holds
+   the number of padding bits we prepend to the string to make it
+   start at a word boundary. r8 holds the 'current' word.
+   r9-12 are temporaries. r0 is used as a temporary and for discarded
+   results.  */
+       clrrwi %r4,%r3,2
+       lis   %r7,0x7f7f
+       rlwinm %r5,%r3,3,27,28
+       lwz   %r8,0(%r4)
+       li    %r9,-1
+       addi  %r7,%r7,0x7f7f
+/* That's the setup done, now do the first pair of words.
+   We make an exception and use method (2) on the first two words, to reduce
+   overhead.  */
+       srw   %r9,%r9,%r5
+       and   %r0,%r7,%r8
+       or    %r10,%r7,%r8
+       add   %r0,%r0,%r7
+       nor   %r0,%r10,%r0
+       and.  %r8,%r0,%r9
+       mtcrf 0x01,%r3
+       bne   L(done0)
+       lis   %r6,0xfeff
+       addi  %r6,%r6,-0x101
+/* Are we now aligned to a doubleword boundary?  */
+       bt    29,L(loop)
+
+/* Handle second word of pair.  */
+       lwzu  %r8,4(%r4)
+       and   %r0,%r7,%r8
+       or    %r10,%r7,%r8
+       add   %r0,%r0,%r7
+       nor.  %r8,%r10,%r0
+       bne   L(done0)
+
+/* The loop.  */
+
+L(loop):
+       lwz   %r8,4(%r4)
+       lwzu  %r9,8(%r4)
+       add   %r0,%r6,%r8
+       nor   %r10,%r7,%r8
+       and.  %r0,%r0,%r10
+       add   %r11,%r6,%r9
+       nor   %r12,%r7,%r9
+       bne   L(done1)
+       and.  %r0,%r11,%r12
+       beq   L(loop)
+
+       and   %r0,%r7,%r9
+       add   %r0,%r0,%r7
+       andc  %r8,%r12,%r0
+       b     L(done0)
+
+L(done1):
+       and   %r0,%r7,%r8
+       subi  %r4,%r4,4
+       add   %r0,%r0,%r7
+       andc  %r8,%r10,%r0
+
+/* When we get to here, r4 points to the first word in the string that
+   contains a zero byte, and the most significant set bit in r8 is in that
+   byte.  */
+L(done0):
+       cntlzw %r11,%r8
+       subf  %r0,%r3,%r4
+       srwi  %r11,%r11,3
+       add   %r3,%r0,%r11
+       blr
+END(strlen)