ppc/string/strncat.s

   1 /*
   2  * Copyright (c) 2002 Apple Computer, 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 #define ASSEMBLER
  24 #include <mach/ppc/asm.h>
  25 #undef  ASSEMBLER
  26
  27 // *****************
  28 // * S T R N C A T *
  29 // *****************
  30 //
  31 // char*        strncat(char *dst, const char *src, size_t count);
  32 //
  33 // We optimize the move by doing it word parallel.  This introduces
  34 // a complication: if we blindly did word load/stores until finding
  35 // a 0, we might get a spurious page fault by touching bytes past it.
  36 // To avoid this, we never do a "lwz" that crosses a page boundary,
  37 // or store extra bytes.
  38 //
  39 // The test for 0s relies on the following inobvious but very efficient
  40 // word-parallel test:
  41 //              x =  dataWord + 0xFEFEFEFF
  42 //              y = ~dataWord & 0x80808080
  43 //              if (x & y) == 0 then no zero found
  44 // The test maps any non-zero byte to zero, and any zero byte to 0x80,
  45 // with one exception: 0x01 bytes preceeding the first zero are also
  46 // mapped to 0x80.
  47 //
  48 // Note that "count" refers to the max number of bytes to _append_.
  49 // There is no limit to the number of bytes we will scan looking for
  50 // the end of the "dst" string.
  51
  52         .text
  53         .globl EXT(strncat)
  54
  55         .align  5
  56 LEXT(strncat)
  57         andi.   r0,r3,3                         // is dst aligned?
  58         dcbtst  0,r3                            // touch in dst
  59         lis             r6,hi16(0xFEFEFEFF)     // start to load magic constants
  60         lis             r7,hi16(0x80808080)
  61         dcbt    0,r4                            // touch in source
  62         ori             r6,r6,lo16(0xFEFEFEFF)
  63         ori             r7,r7,lo16(0x80808080)
  64         mr              r9,r3                           // use r9 for dest ptr (must return r3 intact)
  65         beq             Lword0loop                      // dest is aligned
  66         subfic  r0,r0,4                         // r0 <- #bytes to word align dest
  67         mtctr   r0                                      // set up byte loop
  68
  69 // Loop over bytes looking for 0-byte marking end of dest, until dest is
  70 // word aligned.
  71 //              r4 = source ptr (unaligned)
  72 //              r5 = count (unchanged so far)
  73 //              r6 = 0xFEFEFEFF
  74 //              r7 = 0x80808080
  75 //              r9 = dest ptr (unaligned)
  76 //         ctr = byte count
  77
  78 Lbyte0loop:
  79         lbz             r8,0(r9)                        // r8 <- next dest byte
  80         addi    r9,r9,1
  81         cmpwi   r8,0                            // test for 0
  82         bdnzf   eq,Lbyte0loop           // loop until (ctr==0) | (r8==0)
  83
  84         bne             Lword0loop                      // haven't found 0, so enter word-aligned loop
  85         andi.   r0,r4,3                         // is source aligned?
  86         subi    r9,r9,1                         // point to the 0-byte we just stored
  87         beq             Laligned                        // source is already aligned
  88         subfic  r0,r0,4                         // r0 <- #bytes to word align source
  89         b               Lbyteloop                       // must align source
  90
  91 // Loop over words looking for 0-byte marking end of dest.
  92 //              r4 = source ptr (unaligned)
  93 //              r5 = count (unchanged so far)
  94 //              r6 = 0xFEFEFEFF
  95 //              r7 = 0x80808080
  96 //              r9 = dest ptr (word aligned)
  97
  98         .align  5                                       // align inner loops for speed
  99 Lword0loop:
 100         lwz             r8,0(r9)                        // r8 <- next dest word
 101         addi    r9,r9,4
 102         add             r10,r8,r6                       // r10 <-  word + 0xFEFEFEFF
 103         andc    r12,r7,r8                       // r12 <- ~word & 0x80808080
 104         and.    r11,r10,r12                     // r11 <- nonzero iff word has a 0-byte
 105         beq             Lword0loop                      // loop until 0 found
 106
 107         slwi    r10,r8,7                        // move 0x01 bits (false hits) into 0x80 position
 108         andi.   r0,r4,3                         // is source aligned?
 109         andc    r11,r11,r10                     // mask out false hits
 110         subi    r9,r9,4                         // back up r9 to the start of the word
 111         cntlzw  r10,r11                         // find 0 byte (r0 = 0, 8, 16, or 24)
 112         srwi    r10,r10,3                       // now r10 = 0, 1, 2, or 3
 113         add             r9,r9,r10                       // now r9 points to the 0-byte in dest
 114         beq             Laligned                        // skip if source already aligned
 115         subfic  r0,r0,4                         // r0 <- #bytes to word align source
 116
 117 // Copy min(r0,r5) bytes, until 0-byte.
 118 //              r0 = #bytes we propose to copy (NOTE: must be >0)
 119 //              r4 = source ptr (unaligned)
 120 //              r5 = length remaining in buffer (may be 0)
 121 //              r6 = 0xFEFEFEFF
 122 //              r7 = 0x80808080
 123 //              r9 = dest ptr (unaligned)
 124
 125 Lbyteloop:
 126         cmpwi   r5,0                            // buffer empty? (note: unsigned)
 127         beq--   L0notfound                      // buffer full but 0 not found
 128         lbz             r8,0(r4)                        // r8 <- next source byte
 129         subic.  r0,r0,1                         // decrement count of bytes to move
 130         addi    r4,r4,1
 131         subi    r5,r5,1                         // decrement buffer length remaining
 132         stb             r8,0(r9)                        // pack into dest
 133         cmpwi   cr1,r8,0                        // 0-byte?
 134         addi    r9,r9,1
 135         beqlr   cr1                                     // byte was 0, so done
 136         bne             Lbyteloop                       // r0!=0, source not yet aligned
 137
 138 // Source is word aligned.  Loop over words until 0-byte found or end
 139 // of buffer.
 140 //              r4 = source ptr (word aligned)
 141 //              r5 = length remaining in buffer
 142 //              r6 = 0xFEFEFEFF
 143 //              r7 = 0x80808080
 144 //              r9 = dest ptr (unaligned)
 145
 146 Laligned:
 147         srwi.   r8,r5,2                         // get #words in buffer
 148         addi    r0,r5,1                         // if no words, copy rest of buffer
 149         beq--   Lbyteloop                       // fewer than 4 bytes in buffer
 150         mtctr   r8                                      // set up word loop count
 151         rlwinm  r5,r5,0,0x3                     // mask buffer length down to leftover bytes
 152         b               LwordloopEnter
 153
 154 // Inner loop: move a word at a time, until one of two conditions:
 155 //              - a zero byte is found
 156 //              - end of buffer
 157 // At this point, registers are as follows:
 158 //              r4 = source ptr (word aligned)
 159 //              r5 = bytes leftover in buffer (0..3)
 160 //              r6 = 0xFEFEFEFF
 161 //              r7 = 0x80808080
 162 //              r9 = dest ptr (unaligned)
 163 //     ctr = whole words left in buffer
 164
 165         .align  5                                       // align inner loop, which is 8 words long
 166 Lwordloop:
 167         stw             r8,0(r9)                        // pack word into destination
 168         addi    r9,r9,4
 169 LwordloopEnter:
 170         lwz             r8,0(r4)                        // r8 <- next 4 source bytes
 171         addi    r4,r4,4
 172         add             r10,r8,r6                       // r10 <-  word + 0xFEFEFEFF
 173         andc    r12,r7,r8                       // r12 <- ~word & 0x80808080
 174         and.    r11,r10,r12                     // r11 <- nonzero iff word has a 0-byte
 175         bdnzt   eq,Lwordloop            // loop if ctr!=0 and cr0_eq
 176
 177         beq--   LcheckLeftovers         // skip if 0-byte not found
 178
 179 // Found a 0-byte.  Store last word up to and including the 0, a byte at a time.
 180 //              r8 = last word, known to have a 0-byte
 181 //              r9 = dest ptr
 182
 183 Lstorelastbytes:
 184         srwi.   r0,r8,24                        // right justify next byte and test for 0
 185         slwi    r8,r8,8                         // shift next byte into position
 186         stb             r0,0(r9)                        // pack into dest
 187         addi    r9,r9,1
 188         bne             Lstorelastbytes         // loop until 0 stored
 189
 190         blr
 191
 192 // 0-byte not found while appending words to source.  There might be up to
 193 // 3 "leftover" bytes to append, hopefully the 0-byte is in there.
 194 //              r4 = source ptr (past word in r8)
 195 //              r5 = bytes leftover in buffer (0..3)
 196 //              r6 = 0xFEFEFEFF
 197 //              r7 = 0x80808080
 198 //              r8 = last word of source, with no 0-byte
 199 //              r9 = dest ptr (unaligned)
 200
 201 LcheckLeftovers:
 202         stw             r8,0(r9)                        // store last whole word of source
 203         addi    r9,r9,4
 204         addi    r0,r5,1                         // let r5 (not r0) terminate byte loop
 205         b               Lbyteloop                       // append last few bytes
 206
 207 // 0-byte not found in source.  We append a 0 anyway, even though it will
 208 // be past the end of the buffer.  That's the way it's defined.
 209 //              r9 = dest ptr
 210
 211 L0notfound:
 212         li              r0,0
 213         stb             r0,0(r9)                        // add a 0, past end of buffer
 214         blr
 215