sysdeps/powerpc/strlen.S

   1 /* Optimized strlen implementation for PowerPC.
   2    Copyright (C) 1997, 1999 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Library General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Library General Public License for more details.
  14
  15    You should have received a copy of the GNU Library General Public
  16    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  17    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18    Boston, MA 02111-1307, USA.  */
  19
  20 #include <sysdep.h>
  21
  22 /* The algorithm here uses the following techniques:
  23
  24    1) Given a word 'x', we can test to see if it contains any 0 bytes
  25       by subtracting 0x01010101, and seeing if any of the high bits of each
  26       byte changed from 0 to 1. This works because the least significant
  27       0 byte must have had no incoming carry (otherwise it's not the least
  28       significant), so it is 0x00 - 0x01 == 0xff. For all other
  29       byte values, either they have the high bit set initially, or when
  30       1 is subtracted you get a value in the range 0x00-0x7f, none of which
  31       have their high bit set. The expression here is
  32       (x + 0xfefefeff) & ~(x | 0x7f7f7f7f), which gives 0x00000000 when
  33       there were no 0x00 bytes in the word.
  34
  35    2) Given a word 'x', we can test to see _which_ byte was zero by
  36       calculating ~(((x & 0x7f7f7f7f) + 0x7f7f7f7f) | x | 0x7f7f7f7f).
  37       This produces 0x80 in each byte that was zero, and 0x00 in all
  38       the other bytes. The '| 0x7f7f7f7f' clears the low 7 bits in each
  39       byte, and the '| x' part ensures that bytes with the high bit set
  40       produce 0x00. The addition will carry into the high bit of each byte
  41       iff that byte had one of its low 7 bits set. We can then just see
  42       which was the most significant bit set and divide by 8 to find how
  43       many to add to the index.
  44       This is from the book 'The PowerPC Compiler Writer's Guide',
  45       by Steve Hoxey, Faraydon Karim, Bill Hay and Hank Warren.
  46
  47    We deal with strings not aligned to a word boundary by taking the
  48    first word and ensuring that bytes not part of the string
  49    are treated as nonzero. To allow for memory latency, we unroll the
  50    loop a few times, being careful to ensure that we do not read ahead
  51    across cache line boundaries.
  52
  53    Questions to answer:
  54    1) How long are strings passed to strlen? If they're often really long,
  55    we should probably use cache management instructions and/or unroll the
  56    loop more. If they're often quite short, it might be better to use
  57    fact (2) in the inner loop than have to recalculate it.
  58    2) How popular are bytes with the high bit set? If they are very rare,
  59    on some processors it might be useful to use the simpler expression
  60    ~((x - 0x01010101) | 0x7f7f7f7f) (that is, on processors with only one
  61    ALU), but this fails when any character has its high bit set.  */
  62
  63 /* Some notes on register usage: Under the SVR4 ABI, we can use registers
  64    0 and 3 through 12 (so long as we don't call any procedures) without
  65    saving them. We can also use registers 14 through 31 if we save them.
  66    We can't use r1 (it's the stack pointer), r2 nor r13 because the user
  67    program may expect them to hold their usual value if we get sent
  68    a signal. Integer parameters are passed in r3 through r10.
  69    We can use condition registers cr0, cr1, cr5, cr6, and cr7 without saving
  70    them, the others we must save.  */
  71
  72 ENTRY(strlen)
  73 /* On entry, r3 points to the string, and it's left that way.
  74    We use r6 to store 0xfefefeff, and r7 to store 0x7f7f7f7f.
  75    r4 is used to keep the current index into the string; r5 holds
  76    the number of padding bits we prepend to the string to make it
  77    start at a word boundary. r8 holds the 'current' word.
  78    r9-12 are temporaries. r0 is used as a temporary and for discarded
  79    results.  */
  80         clrrwi r4,r3,2
  81         lis   r7,0x7f7f
  82         rlwinm r5,r3,3,27,28
  83         lwz   r8,0(r4)
  84         li    r9,-1
  85         addi  r7,r7,0x7f7f
  86 /* That's the setup done, now do the first pair of words.
  87    We make an exception and use method (2) on the first two words, to reduce
  88    overhead.  */
  89         srw   r9,r9,r5
  90         and   r0,r7,r8
  91         or    r10,r7,r8
  92         add   r0,r0,r7
  93         nor   r0,r10,r0
  94         and.  r8,r0,r9
  95         mtcrf 0x01,r3
  96         bne   L(done0)
  97         lis   r6,0xfeff
  98         addi  r6,r6,-0x101
  99 /* Are we now aligned to a doubleword boundary?  */
 100         bt    29,L(loop)
 101
 102 /* Handle second word of pair.  */
 103         lwzu  r8,4(r4)
 104         and   r0,r7,r8
 105         or    r10,r7,r8
 106         add   r0,r0,r7
 107         nor.  r8,r10,r0
 108         bne   L(done0)
 109
 110 /* The loop.  */
 111
 112 L(loop):
 113         lwz   r8,4(r4)
 114         lwzu  r9,8(r4)
 115         add   r0,r6,r8
 116         nor   r10,r7,r8
 117         and.  r0,r0,r10
 118         add   r11,r6,r9
 119         nor   r12,r7,r9
 120         bne   L(done1)
 121         and.  r0,r11,r12
 122         beq   L(loop)
 123
 124         and   r0,r7,r9
 125         add   r0,r0,r7
 126         andc  r8,r12,r0
 127         b     L(done0)
 128
 129 L(done1):
 130         and   r0,r7,r8
 131         subi  r4,r4,4
 132         add   r0,r0,r7
 133         andc  r8,r10,r0
 134
 135 /* When we get to here, r4 points to the first word in the string that
 136    contains a zero byte, and the most significant set bit in r8 is in that
 137    byte.  */
 138 L(done0):
 139         cntlzw r11,r8
 140         subf  r0,r3,r4
 141         srwi  r11,r11,3
 142         add   r3,r0,r11
 143         blr
 144 END(strlen)