1*0Sstevel@tonic-gate/* 2*0Sstevel@tonic-gate * CDDL HEADER START 3*0Sstevel@tonic-gate * 4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 7*0Sstevel@tonic-gate * with the License. 8*0Sstevel@tonic-gate * 9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 11*0Sstevel@tonic-gate * See the License for the specific language governing permissions 12*0Sstevel@tonic-gate * and limitations under the License. 13*0Sstevel@tonic-gate * 14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 19*0Sstevel@tonic-gate * 20*0Sstevel@tonic-gate * CDDL HEADER END 21*0Sstevel@tonic-gate */ 22*0Sstevel@tonic-gate/* 23*0Sstevel@tonic-gate * Copyright 2003 Sun Microsystems, Inc. All rights reserved. 24*0Sstevel@tonic-gate * Use is subject to license terms. 25*0Sstevel@tonic-gate */ 26*0Sstevel@tonic-gate 27*0Sstevel@tonic-gate.ident "%Z%%M% %I% %E% SMI" 28*0Sstevel@tonic-gate 29*0Sstevel@tonic-gate .file "%M%" 30*0Sstevel@tonic-gate/* 31*0Sstevel@tonic-gate * Return the ptr in sptr at which the character c1 appears; 32*0Sstevel@tonic-gate * or NULL if not found in n chars; don't stop at \0. 33*0Sstevel@tonic-gate * void * 34*0Sstevel@tonic-gate * memchr(const void *sptr, int c1, size_t n) 35*0Sstevel@tonic-gate * { 36*0Sstevel@tonic-gate * if (n != 0) { 37*0Sstevel@tonic-gate * unsigned char c = (unsigned char)c1; 38*0Sstevel@tonic-gate * const unsigned char *sp = sptr; 39*0Sstevel@tonic-gate * 40*0Sstevel@tonic-gate * do { 41*0Sstevel@tonic-gate * if (*sp++ == c) 42*0Sstevel@tonic-gate * return ((void *)--sp); 43*0Sstevel@tonic-gate * } while (--n != 0); 44*0Sstevel@tonic-gate * } 45*0Sstevel@tonic-gate * return (NULL); 46*0Sstevel@tonic-gate * } 47*0Sstevel@tonic-gate */ 48*0Sstevel@tonic-gate 49*0Sstevel@tonic-gate#include <sys/asm_linkage.h> 50*0Sstevel@tonic-gate#include "synonyms.h" 51*0Sstevel@tonic-gate 52*0Sstevel@tonic-gate ! The first part of this algorithm focuses on determining 53*0Sstevel@tonic-gate ! whether or not the desired character is in the first few bytes 54*0Sstevel@tonic-gate ! of memory, aligning the memory for word-wise copies, and 55*0Sstevel@tonic-gate ! initializing registers to detect zero bytes 56*0Sstevel@tonic-gate 57*0Sstevel@tonic-gate ENTRY(memchr) 58*0Sstevel@tonic-gate 59*0Sstevel@tonic-gate .align 32 60*0Sstevel@tonic-gate 61*0Sstevel@tonic-gate tst %o2 ! n == 0 ? 62*0Sstevel@tonic-gate bz .notfound ! yup, c not found, return null ptr 63*0Sstevel@tonic-gate andcc %o0, 3, %o4 ! s word aligned ? 64*0Sstevel@tonic-gate add %o0, %o2, %o0 ! s + n 65*0Sstevel@tonic-gate sub %g0, %o2, %o2 ! n = -n 66*0Sstevel@tonic-gate bz .prepword ! yup, prepare for word-wise search 67*0Sstevel@tonic-gate and %o1, 0xff, %o1 ! search only for this one byte 68*0Sstevel@tonic-gate 69*0Sstevel@tonic-gate ldub [%o0 + %o2], %o3 ! s[0] 70*0Sstevel@tonic-gate cmp %o3, %o1 ! s[0] == c ? 71*0Sstevel@tonic-gate be .done ! yup, done 72*0Sstevel@tonic-gate nop ! 73*0Sstevel@tonic-gate addcc %o2, 1, %o2 ! n++, s++ 74*0Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 75*0Sstevel@tonic-gate cmp %o4, 3 ! only one byte needed to align? 76*0Sstevel@tonic-gate bz .prepword2 ! yup, prepare for word-wise search 77*0Sstevel@tonic-gate sll %o1, 8, %g1 ! start spreading c across word 78*0Sstevel@tonic-gate ldub [%o0 + %o2], %o3 ! s[1] 79*0Sstevel@tonic-gate cmp %o3, %o1 ! s[1] == c ? 80*0Sstevel@tonic-gate be .done ! yup, done 81*0Sstevel@tonic-gate nop ! 82*0Sstevel@tonic-gate addcc %o2, 1, %o2 ! n++, s++ 83*0Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 84*0Sstevel@tonic-gate cmp %o4, 2 ! only two bytes needed to align? 85*0Sstevel@tonic-gate bz .prepword3 ! yup, prepare for word-wise search 86*0Sstevel@tonic-gate sethi %hi(0x01010101), %o4 ! start loading Alan Mycroft's magic1 87*0Sstevel@tonic-gate ldub [%o0 + %o2], %o3 ! s[1] 88*0Sstevel@tonic-gate cmp %o3, %o1 ! s[1] == c ? 89*0Sstevel@tonic-gate be .done ! yup, done 90*0Sstevel@tonic-gate nop 91*0Sstevel@tonic-gate addcc %o2, 1, %o2 ! n++, s++ 92*0Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 93*0Sstevel@tonic-gate nop 94*0Sstevel@tonic-gate 95*0Sstevel@tonic-gate.prepword: 96*0Sstevel@tonic-gate sll %o1, 8, %g1 ! spread c -------------+ 97*0Sstevel@tonic-gate.prepword2: ! ! 98*0Sstevel@tonic-gate sethi %hi(0x01010101), %o4 ! Alan Mycroft's magic1 ! 99*0Sstevel@tonic-gate.prepword3: ! ! 100*0Sstevel@tonic-gate or %o1, %g1, %o1 ! across all <---------+ 101*0Sstevel@tonic-gate or %o4, %lo(0x01010101),%o4! finish loading magic1 ! 102*0Sstevel@tonic-gate sll %o1, 16, %g1 ! four bytes <--------+ 103*0Sstevel@tonic-gate sll %o4, 7, %o5 ! Alan Mycroft's magic2 ! 104*0Sstevel@tonic-gate or %o1, %g1, %o1 ! of a word <--------+ 105*0Sstevel@tonic-gate 106*0Sstevel@tonic-gate.searchchar: 107*0Sstevel@tonic-gate lduw [%o0 + %o2], %o3 ! src word 108*0Sstevel@tonic-gate.searchchar2: 109*0Sstevel@tonic-gate addcc %o2, 4, %o2 ! s+=4, n+=4 110*0Sstevel@tonic-gate bcs .lastword ! if counter wraps, last word 111*0Sstevel@tonic-gate xor %o3, %o1, %g1 ! tword = word ^ c 112*0Sstevel@tonic-gate andn %o5, %g1, %o3 ! ~tword & 0x80808080 113*0Sstevel@tonic-gate sub %g1, %o4, %g1 ! (tword - 0x01010101) 114*0Sstevel@tonic-gate andcc %o3, %g1, %g0 ! ((tword - 0x01010101) & ~tword & 0x80808080) 115*0Sstevel@tonic-gate bz,a .searchchar2 ! c not found if magic expression == 0 116*0Sstevel@tonic-gate lduw [%o0 + %o2], %o3 ! src word 117*0Sstevel@tonic-gate 118*0Sstevel@tonic-gate ! here we know "word" contains the searched character, and no byte in 119*0Sstevel@tonic-gate ! "word" exceeds n. If we had exceeded n, we would have gone to label 120*0Sstevel@tonic-gate ! .lastword. "tword" has null bytes where "word" had c. After 121*0Sstevel@tonic-gate ! restoring "tword" from "(tword - 0x01010101)" in %g1, examine "tword" 122*0Sstevel@tonic-gate 123*0Sstevel@tonic-gate.foundchar: 124*0Sstevel@tonic-gate add %g1, %o4, %g1 ! restore tword 125*0Sstevel@tonic-gate set 0xff000000, %o4 ! mask for 1st byte 126*0Sstevel@tonic-gate andcc %g1, %o4, %g0 ! first byte zero (= found c) ? 127*0Sstevel@tonic-gate bz,a .done ! yup, done 128*0Sstevel@tonic-gate sub %o2, 4, %o2 ! n -= 4 (undo counter bumping) 129*0Sstevel@tonic-gate set 0x00ff0000, %o5 ! mask for 2nd byte 130*0Sstevel@tonic-gate andcc %g1, %o5, %g0 ! second byte zero (= found c) ? 131*0Sstevel@tonic-gate bz,a .done ! yup, done 132*0Sstevel@tonic-gate sub %o2, 3, %o2 ! n -= 3 (undo counter bumping) 133*0Sstevel@tonic-gate srl %o4, 16, %o4 ! 0x0000ff00 = mask for 3rd byte 134*0Sstevel@tonic-gate andcc %g1, %o4, %g0 ! third byte zero (= found c) ? 135*0Sstevel@tonic-gate bz,a .done ! nope, must be fourth byte 136*0Sstevel@tonic-gate sub %o2, 2, %o2 ! n -= 2 (undo counter bumping) 137*0Sstevel@tonic-gate sub %o2, 1, %o2 ! n -= 1, if fourth byte 138*0Sstevel@tonic-gate retl ! done with leaf function 139*0Sstevel@tonic-gate add %o0, %o2, %o0 ! return pointer to c in s 140*0Sstevel@tonic-gate.done: 141*0Sstevel@tonic-gate retl ! done with leaf function 142*0Sstevel@tonic-gate add %o0, %o2, %o0 ! return pointer to c in s 143*0Sstevel@tonic-gate nop 144*0Sstevel@tonic-gate nop 145*0Sstevel@tonic-gate 146*0Sstevel@tonic-gate ! Here we know that "word" is the last word in the search, and that 147*0Sstevel@tonic-gate ! some bytes possibly exceed n. However, "word" might also contain c. 148*0Sstevel@tonic-gate ! "tword" (in %g1) has null bytes where "word" had c. Examine "tword" 149*0Sstevel@tonic-gate ! while keeping track of number of remaining bytes 150*0Sstevel@tonic-gate 151*0Sstevel@tonic-gate.lastword: 152*0Sstevel@tonic-gate set 0xff000000, %o4 ! mask for 1st byte 153*0Sstevel@tonic-gate sub %o2, 4, %o2 ! n -= 4 (undo counter bumping) 154*0Sstevel@tonic-gate andcc %g1, %o4, %g0 ! first byte zero (= found c) ? 155*0Sstevel@tonic-gate bz .done ! yup, done 156*0Sstevel@tonic-gate set 0x00ff0000, %o5 ! mask for 2nd byte 157*0Sstevel@tonic-gate addcc %o2, 1, %o2 ! n += 1 158*0Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 159*0Sstevel@tonic-gate andcc %g1, %o5, %g0 ! second byte zero (= found c) ? 160*0Sstevel@tonic-gate bz .done ! yup, done 161*0Sstevel@tonic-gate srl %o4, 16, %o4 ! 0x0000ff00 = mask for 3rd byte 162*0Sstevel@tonic-gate addcc %o2, 1, %o2 ! n += 1 163*0Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 164*0Sstevel@tonic-gate andcc %g1, %o4, %g0 ! third byte zero (= found c) ? 165*0Sstevel@tonic-gate bz .done ! yup, done 166*0Sstevel@tonic-gate nop ! 167*0Sstevel@tonic-gate addcc %o2, 1, %o2 ! n += 1 168*0Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 169*0Sstevel@tonic-gate andcc %g1, 0xff, %g0 ! fourth byte zero (= found c) ? 170*0Sstevel@tonic-gate bz .done ! yup, done 171*0Sstevel@tonic-gate nop 172*0Sstevel@tonic-gate 173*0Sstevel@tonic-gate.notfound: 174*0Sstevel@tonic-gate retl ! done with leaf function 175*0Sstevel@tonic-gate mov %g0, %o0 ! return null pointer 176*0Sstevel@tonic-gate 177*0Sstevel@tonic-gate SET_SIZE(memchr) 178