1/* 2 * Copyright (c) 2012 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 * 28 * This file implements the following function for the arm64 architecture: 29 * 30 * int strncmp(const char *s1, const char *s2, size_t n); 31 * 32 * Returns 0 if the two strings are equal up to the first n bytes or to the 33 * end of the string, whichever comes first. Otherwise, returns the difference 34 * of the first mismatched characters interpreted as uint8_t. 35 */ 36 37#include <arm64/asm.h> 38 39.globl _strncmp 40 41/***************************************************************************** 42 * Macros * 43 *****************************************************************************/ 44 45.macro EstablishFrame 46 ARM64_STACK_PROLOG 47 stp fp, lr, [sp, #-16]! 48 mov fp, sp 49.endm 50 51.macro ClearFrameAndReturn 52 ldp fp, lr, [sp], #16 53 ARM64_STACK_EPILOG 54.endm 55 56#include "../mach/arm/vm_param.h" 57#define kVectorSize 16 58 59/***************************************************************************** 60 * Constants * 61 *****************************************************************************/ 62 63.text 64.align 5 65L_mask: 66.quad 0x0706050403020100, 0x0f0e0d0c0b0a0908 67 68/***************************************************************************** 69 * Entrypoints * 70 *****************************************************************************/ 71 72_strncmp: 73 EstablishFrame 74 eor x3, x3, x3 75 cbz x2, L_scalarDone 76// Compare one byte at a time until s1 has vector alignment. 770: tst x0, #(kVectorSize-1) 78 b.eq L_s1aligned 79 ldrb w4, [x0],#1 // load byte from src1 80 ldrb w5, [x1],#1 // load byte from src2 81 subs x3, x4, x5 // if the are not equal 82 ccmp w4, #0, #4, eq // or we find an EOS 83 b.eq L_scalarDone // return the difference 84 subs x2, x2, #1 // decrement length 85 b.ne 0b // continue loop if non-zero 86 87// We found a mismatch or EOS before s1 became aligned. Simply return the 88// difference between the last bytes that we loaded. 89L_scalarDone: 90 mov x0, x3 91 ClearFrameAndReturn 92 93L_s1aligned: 94// If s2 is similarly aligned to s1, then we can use a naive vector comparison 95// from this point on without worrying about spurious page faults; none of our 96// loads will ever cross a page boundary, because they are all aligned. 97 98 99 tst x1, #(kVectorSize-1) 100 b.eq L_naiveVector 101 102/***************************************************************************** 103 * Careful chunk comparison * 104 *****************************************************************************/ 105 106// Otherwise, we need to be careful; although vector loads from s1 cannot 107// cross a page boundary because they are aligned, s2 is not aligned. We 108// compute the multiple of vector size that we can safely load before reaching 109// a page boundary, and compare only that far before switching over to scalar 110// comparisons to step across the page boundary. If this number happens to 111// be zero, we jump directly to the scalar comparison. 112 neg x7, x1 113 ands x7, x7, #(PAGE_MIN_SIZE-kVectorSize) 114 b.eq 2f 115 116.align 4 117// If n is less than the number of bytes before a page-crossing load, jump 118// into the naive vector path instead, since we will not even reach a page 119// crossing. Otherwise, decrement n by that number before we monkey with it, 120// and set the decremented value aside. 1210: cmp x2, x7 122 b.ls L_naiveVector 123 sub x6, x2, x7 124// Use vector comparisons until a mismatch or EOS is encountered, or the next 125// vector load from s2 would be page-crossing. 1261: ldr q0, [x0],#(kVectorSize) 127 ldr q1, [x1],#(kVectorSize) 128 cmeq.16b v1, v0, v1 129 and.16b v0, v0, v1 // contains zero byte iff mismatch or EOS 130 uminv.16b b1, v0 131 fmov w3, s1 // zero only iff comparison is finished 132 cbz w3, L_vectorDone 133 subs x7, x7, #(kVectorSize) 134 b.ne 1b 135// Restore the updated n to x2 136 mov x2, x6 137// The next vector load will cross a page boundary. Instead, compare one byte 138// at a time until s1 again has vector alignment, at which point we will have 139// compared exactly 16 bytes. 1402: ldrb w4, [x0],#1 // load byte from src1 141 ldrb w5, [x1],#1 // load byte from src2 142 subs x3, x4, x5 // if the are not equal 143 ccmp w4, #0, #4, eq // or we find an EOS 144 b.eq L_scalarDone // return the difference 145 subs x2, x2, #1 // decrement length 146 b.eq L_scalarDone // exit loop if zero. 147 tst x0, #(kVectorSize-1) 148 b.ne 2b 149// Having compared one vector's worth of bytes using a scalar comparison, we 150// know that we are safely across the page boundary. Initialize x7 and jump 151// back into the vector comparison part of the loop. 152 mov x7, #(PAGE_MIN_SIZE-kVectorSize) 153 b 0b 154 155 156 157/***************************************************************************** 158 * Naive vector comparison * 159 *****************************************************************************/ 160 161L_naiveVector: 162 subs x3, x2, #(kVectorSize) 163 b.lo L_scalar 164 add x4, x0, x3 // save the addresses of the last vectors 165 add x5, x1, x3 166 mov x2, x3 // length -= kVectorSize 167.align 4 1680: 169 ldr q0, [x0],#(kVectorSize) 170 ldr q1, [x1],#(kVectorSize) 171 cmeq.16b v1, v0, v1 172 and.16b v0, v0, v1 // contains zero byte iff mismatch or EOS 173 uminv.16b b1, v0 174 fmov w3, s1 // zero only iff comparison is finished 175 cbz w3, L_vectorDone 176 subs x2, x2, #(kVectorSize) 177 b.hi 0b 178 179 // compare the last vector 180 mov x0, x4 181 mov x1, x5 182 ldr q0, [x0],#(kVectorSize) 183 ldr q1, [x1],#(kVectorSize) 184 cmeq.16b v1, v0, v1 185 and.16b v0, v0, v1 // contains zero byte iff mismatch or EOS 186 uminv.16b b1, v0 187 fmov w3, s1 // zero only iff comparison is finished 188 cbz w3, L_vectorDone 189 190L_readNBytes: 191 eor x0, x0, x0 192 ClearFrameAndReturn 193 194L_vectorDone: 195// Load the bytes corresponding to the first mismatch or EOS and return 196// their difference. 197 eor.16b v1, v1, v1 198 cmhi.16b v0, v0, v1 // force non-zero lanes to 0xff 199 ldr q1, L_mask 200 orr.16b v0, v0, v1 // lane index in lanes containing mismatch or EOS 201 uminv.16b b1, v0 202 fmov w3, s1 203 sub x3, x3, #(kVectorSize) 204 ldrb w4, [x0, x3] 205 ldrb w5, [x1, x3] 206 sub x0, x4, x5 207 ClearFrameAndReturn 208 209L_scalar: 2100: 211 ldrb w4, [x0],#1 // load byte from src1 212 ldrb w5, [x1],#1 // load byte from src2 213 subs x3, x4, x5 // if the are not equal 214 ccmp w4, #0, #4, eq // or we find an EOS 215 b.eq 1f // return the difference 216 subs x2, x2, #1 // decrement length 217 b.ne 0b // continue loop if non-zero 2181: 219 mov x0, x3 220 ClearFrameAndReturn 221