i386/string/strlcat.s

   1 /*
   2  * Copyright (c) 2007 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_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. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24
  25 // *****************
  26 // * S T R L C A T *
  27 // *****************
  28 //
  29 // size_t  strlcat(char *dst, const char *src, size_t size);
  30 //
  31 // We use SSE to do the initial strlen(), and word-parallel copies
  32 // to do the move.  This appears to be faster than either all SSE
  33 // or all word-parallel, at least on Core2 class machines.
  34 //
  35 // Using 4- or 16-byte parallel loops introduce a complication:
  36 // if we blindly did parallel load/stores until finding
  37 // a 0, we might get a spurious page fault by touching bytes past it.
  38 // To avoid this, we never do a load that crosses a page boundary,
  39 // or store unnecessary bytes.
  40 //
  41 // The word parallel test for 0s relies on the following inobvious
  42 // but very efficient test:
  43 //              x =  dataWord + 0xFEFEFEFF
  44 //              y = ~dataWord & 0x80808080
  45 //              if (x & y) == 0 then no zero found
  46 // The test maps any non-zero byte to zero, and any zero byte to 0x80,
  47 // with one exception: 0x01 bytes preceeding the first zero are also
  48 // mapped to 0x80.
  49 //
  50 // On Core2 class machines, this algorithm seems to be faster than the
  51 // naive byte-by-byte version for operands longer than about 10 bytes.
  52
  53         .text
  54         .globl _strlcat
  55
  56         .align  4
  57 _strlcat:                               // size_t *strlcat(char *dst, const char *src, size_t size);
  58         pushl   %edi
  59         pushl   %esi
  60         pushl   %ebx
  61         movl    16(%esp),%edi           // get dest ptr
  62         movl    20(%esp),%esi           // get source ptr
  63         movl    24(%esp),%ebx           // get length of buffer
  64
  65
  66 // Use SSE to find the 0-byte at current end of buffer.
  67 // This is just a minor variant of strlen().
  68
  69         movl    %edi,%ecx               // copy buffer ptr
  70         andl    $(-16),%edi             // 16-byte align buffer ptr
  71         pxor    %xmm0,%xmm0             // get some 0s
  72         andl    $15,%ecx                // get #bytes in dq before start of buffer
  73         movl    $16,%edx
  74         orl     $(-1),%eax
  75         subl    %ecx,%edx               // #bytes from buffer start to end of dq
  76         subl    %edx,%ebx               // does buffer end before end of dq?
  77         jb      LShortBuf1              // yes, drop into byte-by-byte mode
  78         movdqa  (%edi),%xmm1            // get first aligned chunk of buffer
  79         addl    $16,%edi
  80         pcmpeqb %xmm0,%xmm1             // check for 0s
  81         shl     %cl,%eax                // create mask for the bytes of aligned dq in operand
  82         pmovmskb %xmm1,%ecx             // collect mask of 0-bytes
  83         andl    %eax,%ecx               // mask out any 0s that occur before buffer start
  84         jnz     2f                      // found end of buffer
  85 1:
  86         subl    $16,%ebx                // another dq in buffer?
  87         jb      LShortBuf2              // no, drop into byte-by-byte mode
  88         movdqa  (%edi),%xmm1            // get next chunk
  89         addl    $16,%edi
  90         pcmpeqb %xmm0,%xmm1             // check for 0s
  91         pmovmskb %xmm1,%ecx             // collect mask of 0-bytes
  92         testl   %ecx,%ecx               // any 0-bytes?
  93         jz      1b                      // no
  94 2:
  95         bsf     %ecx,%edx               // find first 1-bit (ie, first 0-byte)
  96         subl    $16,%edi                // back up ptr into buffer
  97         addl    $16,%ebx                // recover length remaining as of start of dq
  98         addl    %edx,%edi               // point to 0-byte
  99         subl    %edx,%ebx               // compute #bytes remaining in buffer
 100
 101
 102 // Copy byte-by-byte until source is 4-byte aligned.
 103 //      %edi = points to 1st byte available in buffer
 104 //      %esi = src ptr
 105 //      %ebx = buffer length remaining (ie, starting at %edi)
 106 //
 107 // NB: the rest of this code is cut-and-pasted from strlcpy().
 108
 109         movl    %esi,%edx               // copy source ptr
 110         negl    %edx
 111         andl    $3,%edx                 // how many bytes to align source ptr?
 112         jz      LAligned                // already aligned
 113
 114
 115 // Loop over bytes.
 116 //      %edi = dest ptr
 117 //      %esi = source ptr
 118 //      %ebx = length remaining in buffer
 119 //      %edx = number of bytes to copy (>0, may not fit in buffer)
 120
 121 LLoopOverBytes:
 122         movzb   (%esi),%eax             // get source byte before checking buffer length
 123         testl   %ebx,%ebx               // buffer full?
 124         jz      L0NotFound              // yes
 125         inc     %esi
 126         dec     %ebx
 127         movb    %al,(%edi)              // pack into dest
 128         inc     %edi
 129         testl   %eax,%eax               // 0?
 130         jz      LDone                   // yes, done
 131         dec     %edx                    // more to go?
 132         jnz     LLoopOverBytes
 133
 134
 135 // Source is aligned.  Loop over words until end of buffer.  We
 136 // align the source, rather than the dest, to avoid getting spurious page faults.
 137 //      %edi = dest ptr (unaligned)
 138 //      %esi = source ptr (word aligned)
 139 //      %ebx = length remaining in buffer
 140
 141 LAligned:
 142         movl    $5,%edx                 // if buffer almost exhausted, prepare to copy rest byte-by-byte
 143         cmpl    $4,%ebx                 // enough for at least one word?
 144         jb      LLoopOverBytes
 145
 146
 147 // Loop over words.
 148 //      %edi = dest ptr (unaligned)
 149 //      %esi = source ptr (word aligned)
 150 //      %ebx = length remaining in buffer (>=4)
 151
 152 LLoopOverWords:
 153         movl    (%esi),%eax             // get next 4 bytes of source
 154         subl    $4,%ebx
 155         addl    $4,%esi
 156         movl    %eax,%edx               // make 2 copies of word
 157         movl    %eax,%ecx
 158         notl    %edx                    // use magic word-parallel test for 0s
 159         addl    $0xFEFEFEFF,%ecx
 160         andl    $0x80808080,%edx
 161         testl   %ecx,%edx
 162         jnz     L0Found                 // one of the bytes of %eax is a 0
 163         movl    %eax,(%edi)             // pack 4 bytes into destination
 164         addl    $4,%edi
 165         cmpl    $4,%ebx                 // room in buffer for another word?
 166         jae     LLoopOverWords          // yes
 167
 168         movl    %ebx,%edx               // copy leftovers in byte loop
 169         jmp     LLoopOverBytes
 170
 171 // Found a 0-byte in the word of source.  Store a byte at a time until the 0.
 172 //      %edi = dest ptr (unaligned)
 173 //      %eax = last word of source, known to have a 0-byte
 174
 175 LNextByte:
 176         shrl    $8,%eax                 // next byte
 177 L0Found:
 178         movb    %al,(%edi)              // pack in next byte
 179         incl    %edi
 180         testb   %al,%al                 // 0?
 181         jnz     LNextByte
 182
 183 // Done storing string.
 184 //      %edi = ptr to byte after 0-byte
 185
 186 LDone:
 187         subl    16(%esp),%edi           // subtract original dest ptr to get length stored
 188         decl    %edi                    // don't count the 0-byte
 189         movl    %edi,%eax               // copy to return value
 190 LExit:
 191         popl    %ebx
 192         popl    %esi
 193         popl    %edi
 194         ret
 195
 196 // Buffer filled but 0-byte not found.  We return the length of the buffer plus the length
 197 // of the source string.  This is not optimized, as it is an error condition.
 198 //      %edi = dest ptr (ie, 1 past end of buffer)
 199 //      %esi = source ptr (ptr to 1st byte that does not fit)
 200
 201 L0NotFound:
 202         movl    24(%esp),%eax           // reload buffer length
 203         testl   %eax,%eax               // null?
 204         jz      LScanSourceTo0          // yes, cannot store a 0
 205         xorl    %edx,%edx               // get a 0
 206         movb    %dl,-1(%edi)            // store a 0 at end of buffer to delimit string
 207 LScanSourceTo0:
 208         movzb   (%esi),%edx             // get next byte of source
 209         incl    %esi
 210         incl    %eax
 211         testl   %edx,%edx               // 0?
 212         jnz     LScanSourceTo0
 213         decl    %eax                    // don't count the 0-byte
 214         jmp     LExit
 215
 216
 217 // Buffer too short to reach end of even one 16-byte aligned chunk.
 218 //      %esi = src ptr
 219
 220 LShortBuf1:
 221         movl    16(%esp),%edi           // recover ptr to start of buffer
 222         movl    24(%esp),%ebx           // recover buffer length
 223         jmp     LShortBuf3
 224
 225
 226 // Out of aligned dq's of buffer, 0-byte still not found.
 227 //      %esi = src ptr
 228 //      %edi = 1st buffer byte not checked for 0
 229 //      %ebx = length remaining - 16
 230
 231 LShortBuf2:
 232         addl    $16,%ebx                // length remaining
 233 LShortBuf3:
 234         movl    24(%esp),%eax           // recover original buffer length, in case 0-byte not found
 235         movl    $17,%edx                // buffer almost exhausted, prepare to copy byte-by-byte
 236 1:
 237         testl   %ebx,%ebx               // no 0s in buffer at all?
 238         jz      LScanSourceTo0          // yes, cannot store a 0
 239         cmpb    $0,(%edi)               // is this the 0?
 240         jz      LLoopOverBytes          // yes, append source
 241         incl    %edi
 242         decl    %ebx
 243         jmp     1b                      // loop looking for 0