/*
 * 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      %ncc, .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      %ncc, .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      %ncc, .done             ! yup, done
        nop                             !
        addcc   %o2, 1, %o2             ! n++, s++
        bz      %ncc, .notfound         ! c not found in first n bytes
        cmp     %o4, 3                  ! only one byte needed to align?
        bz      %ncc, .prepword2        ! yup, prepare for word-wise search
        sllx    %o1, 8, %g1             ! start spreading c across word
        ldub    [%o0 + %o2], %o3        ! s[1]
        cmp     %o3, %o1                ! s[1] == c ?
        be      %ncc, .done             ! yup, done
        nop                             !
        addcc   %o2, 1, %o2             ! n++, s++
        bz      %ncc, .notfound         ! c not found in first n bytes
        cmp     %o4, 2                  ! only two bytes needed to align?
        bz      %ncc, .prepword3        ! yup, prepare for word-wise search
        sethi   %hi(0x80808080), %o5    ! start loading Alan Mycroft's magic1
        ldub    [%o0 + %o2], %o3        ! s[1]
        cmp     %o3, %o1                ! s[1] == c ?
        be      %ncc, .done             ! yup, done
        nop                             !
        addcc   %o2, 1, %o2             ! n++, s++
        bz      %ncc, .notfound         ! c not found in first n bytes
        nop                             !

.prepword:
        sllx    %o1, 8, %g1             ! spread c -------------+
.prepword2:                             !                       !
        sethi   %hi(0x80808080), %o5    ! Alan Mycroft's magic2 !
.prepword3:                             !                       !
        or      %o1, %g1, %o1           !  across all <---------+
        or      %o5, %lo(0x80808080),%o5! finish loading magic2 !
        sllx    %o1, 16, %g1            !   four bytes <--------+
        srlx    %o5, 7, %o4             ! Alan Mycroft's magic1 !
        or      %o1, %g1, %o1           !    of a word <--------+

.searchchar:
        lduw    [%o0 + %o2], %o3        ! src word
.searchchar2:
        addcc   %o2, 4, %o2             ! s+=4, n+=4
        bcs     %ncc, .lastword         ! if counter wraps, last word
        xor     %o3, %o1, %g1           ! tword = word ^ c
        andn    %o5, %g1, %o3           ! ~tword & 0x80808080
        sub     %g1, %o4, %g4           ! (tword - 0x01010101)
        andcc   %o3, %g4, %g0           ! ((tword - 0x01010101) & ~tword & 0x80808080)
        bz,a    %ncc, .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:
        set     0xff000000, %o4         ! mask for 1st byte
        andcc   %g1, %o4, %g0           ! first byte zero (= found c) ?
        bz,a    %ncc, .done             ! yup, done
        sub     %o2, 4, %o2             ! n -= 4 (undo counter bumping)
        nop
        set     0x00ff0000, %o5         ! mask for 2nd byte
        andcc   %g1, %o5, %g0           ! second byte zero (= found c) ?
        bz,a    %ncc, .done             ! yup, done
        sub     %o2, 3, %o2             ! n -= 3 (undo counter bumping)
        srlx    %o4, 16, %o4            ! 0x0000ff00 = mask for 3rd byte
        andcc   %g1, %o4, %g0           ! third byte zero (= found c) ?
        bz,a    %ncc, .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      %ncc, .done             ! yup, done
        set     0x00ff0000, %o5         ! mask for 2nd byte
        addcc   %o2, 1, %o2             ! n += 1
        bz      %ncc, .notfound         ! c not found in first n bytes
        andcc   %g1, %o5, %g0           ! second byte zero (= found c) ?
        bz      %ncc, .done             ! yup, done
        srlx    %o4, 16, %o4            ! 0x0000ff00 = mask for 3rd byte
        addcc   %o2, 1, %o2             ! n += 1
        bz      %ncc, .notfound         ! c not found in first n bytes
        andcc   %g1, %o4, %g0           ! third byte zero (= found c) ?
        bz      %ncc, .done             ! yup, done
        nop                             !
        addcc   %o2, 1, %o2             ! n += 1
        bz      %ncc, .notfound         ! c not found in first n bytes
        andcc   %g1, 0xff, %g0          ! fourth byte zero (= found c) ?
        bz      %ncc, .done             ! yup, done
        nop

.notfound:
        retl                            ! done with leaf function
        mov     %g0, %o0                ! return null pointer

        SET_SIZE(memchr)