| blob | 3069e41cf77707bed555c1210b4a59037af1e092 |
1 /* $NetBSD: strlen.S,v 1.1 2014/09/03 19:34:25 matt Exp $ */
3 /*-
4 * Copyright (C) 2001 Martin J. Laubach <mjl@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 /*----------------------------------------------------------------------*/
31 #include <machine/asm.h>
33 __RCSID("$NetBSD: strlen.S,v 1.1 2014/09/03 19:34:25 matt Exp $");
35 /*----------------------------------------------------------------------*/
36 /* The algorithm here uses the following techniques:
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.
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 /*----------------------------------------------------------------------*/
63 ENTRY(strlen)
65 l.or r12, r3, r0 /* save start */
67 /* Setup constants */
68 l.movhi r13, 0x7f7f
69 l.movhi r15, 0xfefe
70 l.ori r13, r13, 0x7f7f
71 l.ori r15, r15, 0xfeff
73 1: l.andi r7, r12, 3 /* get low bits of start */
74 l.sfeqi r7, 0 /* all clear? */
75 l.bf 3f /* yes, skip alignment */
76 l.nop /* -- delay slot -- */
78 l.sub r12, r12, r7 /* word align start */
79 l.lwz r8, 0(r12) /* load data */
80 l.addi r6, r0, -1 /* r6 = 0xffffffff */
81 l.slli r5, r7, 3 /* bits to bytes */
82 l.srl r6, r6, r5 /* clear low (MSB) bytes */
83 l.xori r6, r6, -1 /* complement */
84 l.or r8, r8, r6 /* merge with loaded word */
85 l.j 4f /* and process */
86 l.nop /* -- delay-slot -- */
88 2: l.addi r12, r12, 4 /* advance to next word */
89 3: l.lwz r8, 0(r12) /* fetch data word */
91 // Step 1: (x + 0xfefefeff) & ~(x | 0x7f7f7f7f)
92 4: l.or r7, r8, r13 /* t0 = x | 0x7f7f7f7f */
93 l.xori r6, r7, -1 /* t1 = ~t0 */
94 l.add r5, r8, r15 /* t2 = x + 0xfefefeff */
95 l.and r4, r7, r5 /* t3 = t1 & t2 */
96 l.sfeqi r4, 0
97 l.bf 2b /* no NUL bytes here */
98 l.nop /* -- delay slot -- */
100 // Step 2: ~(((x & 0x7f7f7f7f) + 0x7f7f7f7f) | x | 0x7f7f7f7f)
101 l.and r7, r8, r13 /* t0 = x & 0x7f7f7f7f */
102 l.or r6, r8, r13 /* t1 = x | 0x7f7f7f7f */
103 l.add r5, r7, r13 /* t2 = t0 + 0x7f7f7f7f */
104 l.or r4, r5, r6 /* t3 = t2 | t1 */
105 l.xori r4, r4, -1 /* t3 = ~t3 */
107 l.fl1 r5, r4 /* find last bit set */
108 l.ori r6, r0, 32 /* bits per word */
109 l.sub r7, r6, r5 /* cvt to leading zeros */
110 l.srli r8, r7, 3 /* shift to byte count */
112 Ldone:
113 l.add r12, r12, r8 /* r12 contains end pointer */
115 /* NOTE: Keep it so this function returns the end pointer
116 in r12, so we can it use from other str* calls (strcat
117 comes to mind */
119 l.sub r11, r12, r3 /* length = end - start */
120 l.jr lr /* return */
121 l.nop /* -- delay slot -- */
122 END(strlen)
123 /*----------------------------------------------------------------------*/