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