10Sstevel@tonic-gate/* 20Sstevel@tonic-gate * CDDL HEADER START 30Sstevel@tonic-gate * 40Sstevel@tonic-gate * The contents of this file are subject to the terms of the 56812Sraf * Common Development and Distribution License (the "License"). 66812Sraf * You may not use this file except in compliance with the License. 70Sstevel@tonic-gate * 80Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 90Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 100Sstevel@tonic-gate * See the License for the specific language governing permissions 110Sstevel@tonic-gate * and limitations under the License. 120Sstevel@tonic-gate * 130Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 140Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 150Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 160Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 170Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 180Sstevel@tonic-gate * 190Sstevel@tonic-gate * CDDL HEADER END 200Sstevel@tonic-gate */ 216812Sraf 220Sstevel@tonic-gate/* 236812Sraf * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 240Sstevel@tonic-gate * Use is subject to license terms. 250Sstevel@tonic-gate */ 260Sstevel@tonic-gate 27*7298SMark.J.Nelson@Sun.COM .file "memchr.s" 286812Sraf 290Sstevel@tonic-gate/* 300Sstevel@tonic-gate * Return the ptr in sptr at which the character c1 appears; 310Sstevel@tonic-gate * or NULL if not found in n chars; don't stop at \0. 320Sstevel@tonic-gate * void * 330Sstevel@tonic-gate * memchr(const void *sptr, int c1, size_t n) 340Sstevel@tonic-gate * { 350Sstevel@tonic-gate * if (n != 0) { 360Sstevel@tonic-gate * unsigned char c = (unsigned char)c1; 370Sstevel@tonic-gate * const unsigned char *sp = sptr; 380Sstevel@tonic-gate * 390Sstevel@tonic-gate * do { 400Sstevel@tonic-gate * if (*sp++ == c) 410Sstevel@tonic-gate * return ((void *)--sp); 420Sstevel@tonic-gate * } while (--n != 0); 430Sstevel@tonic-gate * } 440Sstevel@tonic-gate * return (NULL); 450Sstevel@tonic-gate * } 460Sstevel@tonic-gate */ 470Sstevel@tonic-gate 480Sstevel@tonic-gate#include <sys/asm_linkage.h> 490Sstevel@tonic-gate 500Sstevel@tonic-gate ! The first part of this algorithm focuses on determining 510Sstevel@tonic-gate ! whether or not the desired character is in the first few bytes 520Sstevel@tonic-gate ! of memory, aligning the memory for word-wise copies, and 530Sstevel@tonic-gate ! initializing registers to detect zero bytes 540Sstevel@tonic-gate 550Sstevel@tonic-gate ENTRY(memchr) 560Sstevel@tonic-gate 570Sstevel@tonic-gate .align 32 580Sstevel@tonic-gate 590Sstevel@tonic-gate tst %o2 ! n == 0 ? 600Sstevel@tonic-gate bz .notfound ! yup, c not found, return null ptr 610Sstevel@tonic-gate andcc %o0, 3, %o4 ! s word aligned ? 620Sstevel@tonic-gate add %o0, %o2, %o0 ! s + n 630Sstevel@tonic-gate sub %g0, %o2, %o2 ! n = -n 640Sstevel@tonic-gate bz .prepword ! yup, prepare for word-wise search 650Sstevel@tonic-gate and %o1, 0xff, %o1 ! search only for this one byte 660Sstevel@tonic-gate 670Sstevel@tonic-gate ldub [%o0 + %o2], %o3 ! s[0] 680Sstevel@tonic-gate cmp %o3, %o1 ! s[0] == c ? 690Sstevel@tonic-gate be .done ! yup, done 700Sstevel@tonic-gate nop ! 710Sstevel@tonic-gate addcc %o2, 1, %o2 ! n++, s++ 720Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 730Sstevel@tonic-gate cmp %o4, 3 ! only one byte needed to align? 740Sstevel@tonic-gate bz .prepword2 ! yup, prepare for word-wise search 750Sstevel@tonic-gate sll %o1, 8, %g1 ! start spreading c across word 760Sstevel@tonic-gate ldub [%o0 + %o2], %o3 ! s[1] 770Sstevel@tonic-gate cmp %o3, %o1 ! s[1] == c ? 780Sstevel@tonic-gate be .done ! yup, done 790Sstevel@tonic-gate nop ! 800Sstevel@tonic-gate addcc %o2, 1, %o2 ! n++, s++ 810Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 820Sstevel@tonic-gate cmp %o4, 2 ! only two bytes needed to align? 830Sstevel@tonic-gate bz .prepword3 ! yup, prepare for word-wise search 840Sstevel@tonic-gate sethi %hi(0x01010101), %o4 ! start loading Alan Mycroft's magic1 850Sstevel@tonic-gate ldub [%o0 + %o2], %o3 ! s[1] 860Sstevel@tonic-gate cmp %o3, %o1 ! s[1] == c ? 870Sstevel@tonic-gate be .done ! yup, done 880Sstevel@tonic-gate nop 890Sstevel@tonic-gate addcc %o2, 1, %o2 ! n++, s++ 900Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 910Sstevel@tonic-gate nop 920Sstevel@tonic-gate 930Sstevel@tonic-gate.prepword: 940Sstevel@tonic-gate sll %o1, 8, %g1 ! spread c -------------+ 950Sstevel@tonic-gate.prepword2: ! ! 960Sstevel@tonic-gate sethi %hi(0x01010101), %o4 ! Alan Mycroft's magic1 ! 970Sstevel@tonic-gate.prepword3: ! ! 980Sstevel@tonic-gate or %o1, %g1, %o1 ! across all <---------+ 990Sstevel@tonic-gate or %o4, %lo(0x01010101),%o4! finish loading magic1 ! 1000Sstevel@tonic-gate sll %o1, 16, %g1 ! four bytes <--------+ 1010Sstevel@tonic-gate sll %o4, 7, %o5 ! Alan Mycroft's magic2 ! 1020Sstevel@tonic-gate or %o1, %g1, %o1 ! of a word <--------+ 1030Sstevel@tonic-gate 1040Sstevel@tonic-gate.searchchar: 1050Sstevel@tonic-gate lduw [%o0 + %o2], %o3 ! src word 1060Sstevel@tonic-gate.searchchar2: 1070Sstevel@tonic-gate addcc %o2, 4, %o2 ! s+=4, n+=4 1080Sstevel@tonic-gate bcs .lastword ! if counter wraps, last word 1090Sstevel@tonic-gate xor %o3, %o1, %g1 ! tword = word ^ c 1100Sstevel@tonic-gate andn %o5, %g1, %o3 ! ~tword & 0x80808080 1110Sstevel@tonic-gate sub %g1, %o4, %g1 ! (tword - 0x01010101) 1120Sstevel@tonic-gate andcc %o3, %g1, %g0 ! ((tword - 0x01010101) & ~tword & 0x80808080) 1130Sstevel@tonic-gate bz,a .searchchar2 ! c not found if magic expression == 0 1140Sstevel@tonic-gate lduw [%o0 + %o2], %o3 ! src word 1150Sstevel@tonic-gate 1160Sstevel@tonic-gate ! here we know "word" contains the searched character, and no byte in 1170Sstevel@tonic-gate ! "word" exceeds n. If we had exceeded n, we would have gone to label 1180Sstevel@tonic-gate ! .lastword. "tword" has null bytes where "word" had c. After 1190Sstevel@tonic-gate ! restoring "tword" from "(tword - 0x01010101)" in %g1, examine "tword" 1200Sstevel@tonic-gate 1210Sstevel@tonic-gate.foundchar: 1220Sstevel@tonic-gate add %g1, %o4, %g1 ! restore tword 1230Sstevel@tonic-gate set 0xff000000, %o4 ! mask for 1st byte 1240Sstevel@tonic-gate andcc %g1, %o4, %g0 ! first byte zero (= found c) ? 1250Sstevel@tonic-gate bz,a .done ! yup, done 1260Sstevel@tonic-gate sub %o2, 4, %o2 ! n -= 4 (undo counter bumping) 1270Sstevel@tonic-gate set 0x00ff0000, %o5 ! mask for 2nd byte 1280Sstevel@tonic-gate andcc %g1, %o5, %g0 ! second byte zero (= found c) ? 1290Sstevel@tonic-gate bz,a .done ! yup, done 1300Sstevel@tonic-gate sub %o2, 3, %o2 ! n -= 3 (undo counter bumping) 1310Sstevel@tonic-gate srl %o4, 16, %o4 ! 0x0000ff00 = mask for 3rd byte 1320Sstevel@tonic-gate andcc %g1, %o4, %g0 ! third byte zero (= found c) ? 1330Sstevel@tonic-gate bz,a .done ! nope, must be fourth byte 1340Sstevel@tonic-gate sub %o2, 2, %o2 ! n -= 2 (undo counter bumping) 1350Sstevel@tonic-gate sub %o2, 1, %o2 ! n -= 1, if fourth byte 1360Sstevel@tonic-gate retl ! done with leaf function 1370Sstevel@tonic-gate add %o0, %o2, %o0 ! return pointer to c in s 1380Sstevel@tonic-gate.done: 1390Sstevel@tonic-gate retl ! done with leaf function 1400Sstevel@tonic-gate add %o0, %o2, %o0 ! return pointer to c in s 1410Sstevel@tonic-gate nop 1420Sstevel@tonic-gate nop 1430Sstevel@tonic-gate 1440Sstevel@tonic-gate ! Here we know that "word" is the last word in the search, and that 1450Sstevel@tonic-gate ! some bytes possibly exceed n. However, "word" might also contain c. 1460Sstevel@tonic-gate ! "tword" (in %g1) has null bytes where "word" had c. Examine "tword" 1470Sstevel@tonic-gate ! while keeping track of number of remaining bytes 1480Sstevel@tonic-gate 1490Sstevel@tonic-gate.lastword: 1500Sstevel@tonic-gate set 0xff000000, %o4 ! mask for 1st byte 1510Sstevel@tonic-gate sub %o2, 4, %o2 ! n -= 4 (undo counter bumping) 1520Sstevel@tonic-gate andcc %g1, %o4, %g0 ! first byte zero (= found c) ? 1530Sstevel@tonic-gate bz .done ! yup, done 1540Sstevel@tonic-gate set 0x00ff0000, %o5 ! mask for 2nd byte 1550Sstevel@tonic-gate addcc %o2, 1, %o2 ! n += 1 1560Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 1570Sstevel@tonic-gate andcc %g1, %o5, %g0 ! second byte zero (= found c) ? 1580Sstevel@tonic-gate bz .done ! yup, done 1590Sstevel@tonic-gate srl %o4, 16, %o4 ! 0x0000ff00 = mask for 3rd byte 1600Sstevel@tonic-gate addcc %o2, 1, %o2 ! n += 1 1610Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 1620Sstevel@tonic-gate andcc %g1, %o4, %g0 ! third byte zero (= found c) ? 1630Sstevel@tonic-gate bz .done ! yup, done 1640Sstevel@tonic-gate nop ! 1650Sstevel@tonic-gate addcc %o2, 1, %o2 ! n += 1 1660Sstevel@tonic-gate bz .notfound ! c not found in first n bytes 1670Sstevel@tonic-gate andcc %g1, 0xff, %g0 ! fourth byte zero (= found c) ? 1680Sstevel@tonic-gate bz .done ! yup, done 1690Sstevel@tonic-gate nop 1700Sstevel@tonic-gate 1710Sstevel@tonic-gate.notfound: 1720Sstevel@tonic-gate retl ! done with leaf function 1730Sstevel@tonic-gate mov %g0, %o0 ! return null pointer 1740Sstevel@tonic-gate 1750Sstevel@tonic-gate SET_SIZE(memchr) 176