/*
 * 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)