diff options
Diffstat (limited to 'sysdeps/powerpc/strlen.s')
-rw-r--r-- | sysdeps/powerpc/strlen.s | 145 |
1 files changed, 145 insertions, 0 deletions
diff --git a/sysdeps/powerpc/strlen.s b/sysdeps/powerpc/strlen.s new file mode 100644 index 0000000..eb6a88e --- /dev/null +++ b/sysdeps/powerpc/strlen.s @@ -0,0 +1,145 @@ + # 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. + + # 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), nor r2 or r13 because the user + # program may expect them to be 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. + + .section ".text" + .align 3 + .globl strlen + .type strlen,@function +strlen: + # On entry, r3 points to the string, and it's left that way. + # We use r6 to store 0x01010101, 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 4,3,2 + lis 6,0xfeff + lis 7,0x7f7f + rlwinm 10,3,0,29,29 + lwz 8,0(4) + addi 7,7,0x7f7f + rlwinm 5,3,3,27,28 + cmpwi 1,10,0 + li 9,-1 + # 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 9,9,5 + and 0,7,8 + or 10,7,8 + add 0,0,7 + nor 0,10,0 + and. 8,0,9 + bne done0 + # Handle second word of pair. Put addi between branches to avoid hurting + # branch prediction. + addi 6,6,0xfffffeff + + bne 1,loop + lwzu 8,4(4) + and 0,7,8 + or 10,7,8 + add 0,0,7 + nor. 0,10,0 + bne done0 + + # The loop. + +loop: lwz 8,4(4) + lwzu 9,8(4) + add 0,6,8 + nor 10,7,8 + and. 0,0,10 + add 11,6,9 + nor 12,7,9 + bne done1 + and. 0,11,12 + beq loop + + and 0,7,9 + or 10,7,9 + b done2 + +done1: addi 4,4,-4 + and 0,7,9 + or 10,7,9 +done2: add 0,0,7 + nor 0,10,0 + + # 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. +done0: cntlzw 11,8 + subf 0,3,4 + srwi 11,11,3 + add 3,0,11 + blr +0: + .size strlen,0b-strlen |