sysdeps/powerpc/strlen.s

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