Home | History | Annotate | Line # | Download | only in string 
      1 /*	$NetBSD: strlen.S,v 1.6 2011/01/15 07:31:12 matt Exp $ */
      2 
      3 /*-
      4  * Copyright (C) 2001	Martin J. Laubach <mjl (at) NetBSD.org>
      5  * All rights reserved.
      6  *
      7  * Redistribution and use in source and binary forms, with or without
      8  * modification, are permitted provided that the following conditions
      9  * are met:
     10  * 1. Redistributions of source code must retain the above copyright
     11  *    notice, this list of conditions and the following disclaimer.
     12  * 2. Redistributions in binary form must reproduce the above copyright
     13  *    notice, this list of conditions and the following disclaimer in the
     14  *    documentation and/or other materials provided with the distribution.
     15  * 3. The name of the author may not be used to endorse or promote products
     16  *    derived from this software without specific prior written permission.
     17  *
     18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     21  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     28  */
     29 /*----------------------------------------------------------------------*/
     30 
     31 #include <machine/asm.h>
     32 
     33 __RCSID("$NetBSD: strlen.S,v 1.6 2011/01/15 07:31:12 matt Exp $");
     34 
     35 /*----------------------------------------------------------------------*/
     36 /* The algorithm here uses the following techniques:
     37 
     38    1) Given a word 'x', we can test to see if it contains any 0 bytes
     39       by subtracting 0x01010101, and seeing if any of the high bits of each
     40       byte changed from 0 to 1. This works because the least significant
     41       0 byte must have had no incoming carry (otherwise it's not the least
     42       significant), so it is 0x00 - 0x01 == 0xff. For all other
     43       byte values, either they have the high bit set initially, or when
     44       1 is subtracted you get a value in the range 0x00-0x7f, none of which
     45       have their high bit set. The expression here is
     46       (x + 0xfefefeff) & ~(x | 0x7f7f7f7f), which gives 0x00000000 when
     47       there were no 0x00 bytes in the word.
     48 
     49    2) Given a word 'x', we can test to see _which_ byte was zero by
     50       calculating ~(((x & 0x7f7f7f7f) + 0x7f7f7f7f) | x | 0x7f7f7f7f).
     51       This produces 0x80 in each byte that was zero, and 0x00 in all
     52       the other bytes. The '| 0x7f7f7f7f' clears the low 7 bits in each
     53       byte, and the '| x' part ensures that bytes with the high bit set
     54       produce 0x00. The addition will carry into the high bit of each byte
     55       iff that byte had one of its low 7 bits set. We can then just see
     56       which was the most significant bit set and divide by 8 to find how
     57       many to add to the index.
     58       This is from the book 'The PowerPC Compiler Writer's Guide',
     59       by Steve Hoxey, Faraydon Karim, Bill Hay and Hank Warren.
     60 */
     61 /*----------------------------------------------------------------------*/
     62 
     63 		.text
     64 		.align 4
     65 
     66 ENTRY(strlen)
     67 
     68 		/* Setup constants */
     69 		lis	%r10, 0x7f7f
     70 		lis	%r9, 0xfefe
     71 		ori	%r10, %r10, 0x7f7f
     72 		ori	%r9, %r9, 0xfeff
     73 
     74 		/* Mask out leading bytes on non aligned strings */
     75 		rlwinm.	%r8, %r3, 3, 27, 28	/* leading bits to mask */
     76 #ifdef _LP64
     77 		clrrdi	%r5, %r3, 2		/*  clear low 2 addr bits */
     78 #else
     79 		clrrwi	%r5, %r3, 2		/*  clear low 2 addr bits */
     80 #endif
     81 		li	%r0, -1
     82 		beq+	3f			/* skip alignment if already */
     83 						/* aligned */
     84 
     85 		srw	%r0, %r0, %r8		/* make 0000...1111 mask */
     86 
     87 		lwz	%r7, 0(%r5)
     88 		nor	%r0, %r0, %r0		/* invert mask */
     89 		or	%r7, %r7, %r0		/* make leading bytes != 0 */
     90 		b	2f
     91 
     92 3:		subi	%r5, %r5, 4
     93 
     94 1:		lwzu	%r7, 4(%r5)		/* fetch data word */
     95 
     96 2:		nor	%r0, %r7, %r10		/* do step 1 */
     97 		add	%r6, %r7, %r9
     98 		and.	%r0, %r0, %r6
     99 
    100 		beq+	1b			/* no NUL bytes here */
    101 
    102 		and	%r8, %r7, %r10		/* ok, a NUL is somewhere */
    103 		or	%r7, %r7, %r10		/* do step 2 to find out */
    104 		add	%r0, %r8, %r10		/* where */
    105 		nor	%r8, %r7, %r0
    106 
    107 		cntlzw	%r0, %r8		/* offset from this word */
    108 		srwi	%r4, %r0, 3
    109 
    110 		add	%r4, %r5, %r4		/* r4 contains end pointer */
    111 		/* NOTE: Keep it so this function returns the end pointer
    112 		   in r4, so we can it use from other str* calls (strcat
    113 		   comes to mind */
    114 
    115 		subf	%r3, %r3, %r4
    116 		blr
    117 END(strlen)
    118 /*----------------------------------------------------------------------*/
    119