--- /dev/null
+/*
+ * Copyright (c) 2005 Apple Computer, Inc. All rights reserved.
+ *
+ * @APPLE_LICENSE_HEADER_START@
+ *
+ * This file contains Original Code and/or Modifications of Original Code
+ * as defined in and that are subject to the Apple Public Source License
+ * Version 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ and read it before using this
+ * file.
+ *
+ * The Original Code and all software distributed under the License are
+ * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
+ * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
+ * limitations under the License.
+ *
+ * @APPLE_LICENSE_HEADER_END@
+ */
+
+
+// *****************
+// * S T R N C M P *
+// *****************
+//
+// int strncmp(const char *s1, const char *s2, size_t len);
+//
+// We optimize the compare by doing it vector parallel. This introduces
+// a complication: if we blindly did vector loads from both sides until
+// finding a difference (or 0), we might get a spurious page fault by
+// reading bytes past the difference. To avoid this, we never do a load
+// that crosses a page boundary.
+
+#define kShort 20 // too short for vectors (must be >16)
+
+ .text
+ .globl _strncmp
+
+ .align 4
+_strncmp: // int strncmp(const char *s1, const char *s2, size_t len);
+ pushl %esi
+ pushl %edi
+ movl 20(%esp),%ecx // get length
+ movl 12(%esp),%esi // get LHS ptr
+ movl 16(%esp),%edi // get RHS ptr
+ push %ebx
+ cmpl $(kShort),%ecx // worth accelerating?
+ ja LNotShort // yes
+
+
+// Too short to bother with parallel compares. Loop over bytes.
+// %esi = LHS ptr
+// %edi = RHS ptr
+// %ecx = length (<= kShort)
+
+LShort:
+ testl %ecx,%ecx // 0-length?
+ jnz LShortLoop // no
+ jmp LReturn0 // yes, return 0
+ .align 4,0x90 // align inner loops to optimize I-fetch
+LShortLoop: // loop over bytes
+ movzb (%esi),%eax // get LHS byte
+ movzb (%edi),%ebx // get RHS byte
+ incl %esi
+ incl %edi
+ testl %eax,%eax // LHS==0 ?
+ jz LNotEqual // yes, this terminates comparison
+ subl %ebx,%eax // compare them
+ jnz LExit // done if not equal
+ decl %ecx // decrement length
+ jnz LShortLoop
+LReturn0:
+ xorl %eax,%eax // all bytes equal, so return 0
+LExit: // return value is in %eax
+ popl %ebx
+ popl %edi
+ popl %esi
+ ret
+
+LNotEqual: // LHS in eax, RHS in ebx
+ subl %ebx,%eax // generate return value (nonzero)
+ popl %ebx
+ popl %edi
+ popl %esi
+ ret
+
+
+// Loop over bytes until we reach end of a page.
+// %esi = LHS ptr
+// %edi = RHS ptr
+// %ecx = length remaining after end of loop (ie, already adjusted)
+// %edx = #bytes until next page (1..15)
+
+ .align 4,0x90 // align inner loops to optimize I-fetch
+LLoopOverBytes:
+ movzb (%esi),%eax // get LHS byte
+ movzb (%edi),%ebx // get RHS byte
+ inc %esi
+ inc %edi
+ testl %eax,%eax // LHS==0 ?
+ jz LNotEqual // yes, this terminates comparison
+ subl %ebx,%eax // compare them
+ jnz LExit // done if not equal
+ dec %edx // more to go?
+ jnz LLoopOverBytes
+
+
+// Long enough to justify overhead of setting up vector compares. In order to
+// avoid spurious page faults, we loop over:
+//
+// min( length, bytes_in_LHS_page, bytes_in_RHS_page) >> 4
+//
+// 16-byte chunks. When we near a page end, we have to revert to a byte-by-byte
+// comparison until reaching the next page, then resume the vector comparison.
+// %esi = LHS ptr
+// %edi = RHS ptr
+// %ecx = length (> kShort)
+
+LNotShort:
+ movl %esi,%eax // copy ptrs
+ movl %edi,%edx
+ andl $4095,%eax // mask down to page offsets
+ andl $4095,%edx
+ cmpl %eax,%edx // which is bigger?
+ cmova %edx,%eax // %eax = max(LHS offset, RHS offset);
+ movl $4096,%edx
+ subl %eax,%edx // get #bytes to next page crossing
+ cmpl %ecx,%edx // will operand run out first?
+ cmova %ecx,%edx // get min(length remaining, bytes to page end)
+ movl %edx,%eax
+ shrl $4,%edx // get #chunks till end of operand or page
+ jnz LLoopOverChunks // enter vector loop
+
+// Too near page end for vectors.
+
+ subl %eax,%ecx // adjust length remaining
+ movl %eax,%edx // %edx <- #bytes to page end
+ cmpl $(kShort),%ecx // will there be enough after we cross page for vectors?
+ ja LLoopOverBytes // yes
+ addl %eax,%ecx // no, restore total length remaining
+ jmp LShortLoop // compare rest byte-by-byte (%ecx != 0)
+
+
+// Loop over 16-byte chunks.
+// %esi = LHS ptr
+// %edi = RHS ptr
+// %ecx = length remaining
+// %edx = chunk count
+
+ .align 4,0x90 // align inner loops to optimize I-fetch
+LLoopOverChunks:
+ movdqu (%esi),%xmm1 // get LHS
+ movdqu (%edi),%xmm2 // get RHS
+ pxor %xmm0,%xmm0 // get some 0s in the shadow of the loads
+ addl $16,%esi
+ pcmpeqb %xmm1,%xmm2 // compare LHS to RHS
+ pcmpeqb %xmm1,%xmm0 // compare LHS to 0s
+ addl $16,%edi
+ pmovmskb %xmm2,%eax // get result mask for comparison of LHS and RHS
+ pmovmskb %xmm0,%ebx // get result mask for 0 check
+ subl $16,%ecx // decrement length remaining
+ xorl $0xFFFF,%eax // complement compare mask so 1 means "not equal"
+ orl %ebx,%eax // combine the masks and check for 1-bits
+ jnz LFoundDiffOr0 // we found differing bytes or a 0-byte
+ dec %edx // more to go?
+ jnz LLoopOverChunks // yes
+
+ cmpl $(kShort),%ecx // a lot more to compare?
+ jbe LShort // no
+ jmp LNotShort // compute distance to next page crossing etc
+
+
+// Found a zero and/or a difference in vector compare.
+// %esi = LHS ptr, already advanced by 16
+// %edi = RHS ptr, already advanced by 16
+// %eax = bit n set if bytes n differed or were 0
+
+LFoundDiffOr0:
+ bsf %eax,%edx // which byte differed or was 0?
+ subl $16,%esi // point to start of vectors while we wait for bit scan
+ subl $16,%edi
+ movzb (%esi,%edx),%eax // get LHS byte
+ movzb (%edi,%edx),%ecx // get RHS byte
+ popl %ebx
+ popl %edi
+ subl %ecx,%eax // compute difference (ie, return value)
+ popl %esi
+ ret
projects / apple / libc.git / blobdiff