/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2008 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
.file "memchr.s"
/*
* Return the ptr in sptr at which the character c1 appears;
* or NULL if not found in n chars; don't stop at \0.
* void *
* memchr(const void *sptr, int c1, size_t n)
* {
* if (n != 0) {
* unsigned char c = (unsigned char)c1;
* const unsigned char *sp = sptr;
*
* do {
* if (*sp++ == c)
* return ((void *)--sp);
* } while (--n != 0);
* }
* return (NULL);
* }
*/
#include <sys/asm_linkage.h>
! The first part of this algorithm focuses on determining
! whether or not the desired character is in the first few bytes
! of memory, aligning the memory for word-wise copies, and
! initializing registers to detect zero bytes
ENTRY(memchr)
.align 32
tst %o2 ! n == 0 ?
bz .notfound ! yup, c not found, return null ptr
andcc %o0, 3, %o4 ! s word aligned ?
add %o0, %o2, %o0 ! s + n
sub %g0, %o2, %o2 ! n = -n
bz .prepword ! yup, prepare for word-wise search
and %o1, 0xff, %o1 ! search only for this one byte
ldub [%o0 + %o2], %o3 ! s[0]
cmp %o3, %o1 ! s[0] == c ?
be .done ! yup, done
nop !
addcc %o2, 1, %o2 ! n++, s++
bz .notfound ! c not found in first n bytes
cmp %o4, 3 ! only one byte needed to align?
bz .prepword2 ! yup, prepare for word-wise search
sll %o1, 8, %g1 ! start spreading c across word
ldub [%o0 + %o2], %o3 ! s[1]
cmp %o3, %o1 ! s[1] == c ?
be .done ! yup, done
nop !
addcc %o2, 1, %o2 ! n++, s++
bz .notfound ! c not found in first n bytes
cmp %o4, 2 ! only two bytes needed to align?
bz .prepword3 ! yup, prepare for word-wise search
sethi %hi(0x01010101), %o4 ! start loading Alan Mycroft's magic1
ldub [%o0 + %o2], %o3 ! s[1]
cmp %o3, %o1 ! s[1] == c ?
be .done ! yup, done
nop
addcc %o2, 1, %o2 ! n++, s++
bz .notfound ! c not found in first n bytes
nop
.prepword:
sll %o1, 8, %g1 ! spread c -------------+
.prepword2: ! !
sethi %hi(0x01010101), %o4 ! Alan Mycroft's magic1 !
.prepword3: ! !
or %o1, %g1, %o1 ! across all <---------+
or %o4, %lo(0x01010101),%o4! finish loading magic1 !
sll %o1, 16, %g1 ! four bytes <--------+
sll %o4, 7, %o5 ! Alan Mycroft's magic2 !
or %o1, %g1, %o1 ! of a word <--------+
.searchchar:
lduw [%o0 + %o2], %o3 ! src word
.searchchar2:
addcc %o2, 4, %o2 ! s+=4, n+=4
bcs .lastword ! if counter wraps, last word
xor %o3, %o1, %g1 ! tword = word ^ c
andn %o5, %g1, %o3 ! ~tword & 0x80808080
sub %g1, %o4, %g1 ! (tword - 0x01010101)
andcc %o3, %g1, %g0 ! ((tword - 0x01010101) & ~tword & 0x80808080)
bz,a .searchchar2 ! c not found if magic expression == 0
lduw [%o0 + %o2], %o3 ! src word
! here we know "word" contains the searched character, and no byte in
! "word" exceeds n. If we had exceeded n, we would have gone to label
! .lastword. "tword" has null bytes where "word" had c. After
! restoring "tword" from "(tword - 0x01010101)" in %g1, examine "tword"
.foundchar:
add %g1, %o4, %g1 ! restore tword
set 0xff000000, %o4 ! mask for 1st byte
andcc %g1, %o4, %g0 ! first byte zero (= found c) ?
bz,a .done ! yup, done
sub %o2, 4, %o2 ! n -= 4 (undo counter bumping)
set 0x00ff0000, %o5 ! mask for 2nd byte
andcc %g1, %o5, %g0 ! second byte zero (= found c) ?
bz,a .done ! yup, done
sub %o2, 3, %o2 ! n -= 3 (undo counter bumping)
srl %o4, 16, %o4 ! 0x0000ff00 = mask for 3rd byte
andcc %g1, %o4, %g0 ! third byte zero (= found c) ?
bz,a .done ! nope, must be fourth byte
sub %o2, 2, %o2 ! n -= 2 (undo counter bumping)
sub %o2, 1, %o2 ! n -= 1, if fourth byte
retl ! done with leaf function
add %o0, %o2, %o0 ! return pointer to c in s
.done:
retl ! done with leaf function
add %o0, %o2, %o0 ! return pointer to c in s
nop
nop
! Here we know that "word" is the last word in the search, and that
! some bytes possibly exceed n. However, "word" might also contain c.
! "tword" (in %g1) has null bytes where "word" had c. Examine "tword"
! while keeping track of number of remaining bytes
.lastword:
set 0xff000000, %o4 ! mask for 1st byte
sub %o2, 4, %o2 ! n -= 4 (undo counter bumping)
andcc %g1, %o4, %g0 ! first byte zero (= found c) ?
bz .done ! yup, done
set 0x00ff0000, %o5 ! mask for 2nd byte
addcc %o2, 1, %o2 ! n += 1
bz .notfound ! c not found in first n bytes
andcc %g1, %o5, %g0 ! second byte zero (= found c) ?
bz .done ! yup, done
srl %o4, 16, %o4 ! 0x0000ff00 = mask for 3rd byte
addcc %o2, 1, %o2 ! n += 1
bz .notfound ! c not found in first n bytes
andcc %g1, %o4, %g0 ! third byte zero (= found c) ?
bz .done ! yup, done
nop !
addcc %o2, 1, %o2 ! n += 1
bz .notfound ! c not found in first n bytes
andcc %g1, 0xff, %g0 ! fourth byte zero (= found c) ?
bz .done ! yup, done
nop
.notfound:
retl ! done with leaf function
mov %g0, %o0 ! return null pointer
SET_SIZE(memchr)