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