ppc/string/strcmp.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 C M P *
  29 // ***************
  30 //
  31 // int  strcmp(const char *s1, const char *s2);
  32 //
  33 // We optimize the compare by doing it word parallel.  This introduces
  34 // a complication: if we blindly did word loads from both sides until
  35 // finding a difference (or 0), we might get a spurious page fault by
  36 // reading bytes past the difference.  To avoid this, we never do a "lwz"
  37 // that crosses a page boundary.
  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         .text
  49         .globl EXT(strcmp)
  50
  51         .align  5
  52 LEXT(strcmp)                                    // int  strcmp(const char *s1, const char *s2);
  53         andi.   r0,r3,3                         // is LHS aligned?
  54         dcbt    0,r3                            // touch in LHS
  55         lis             r5,hi16(0xFEFEFEFF)     // start to load magic constants
  56         lis             r6,hi16(0x80808080)
  57         dcbt    0,r4                            // touch in RHS
  58         ori             r5,r5,lo16(0xFEFEFEFF)
  59         ori             r6,r6,lo16(0x80808080)
  60         subi    r3,r3,4                         // we use "lwzu" in the inner loops
  61         subi    r4,r4,4
  62         beq             Laligned                        // LHS is aligned
  63         subfic  r0,r0,4                         // r0 <- #bytes to word align LHS
  64         mtctr   r0
  65
  66 // Loop over bytes.
  67
  68 Lbyteloop:
  69         lbz             r7,4(r3)                        // r7 <- next LHS byte
  70         addi    r3,r3,1
  71         lbz             r8,4(r4)                        // r8 <- next RHS byte
  72         addi    r4,r4,1
  73         cntlzw  r9,r7                           // is r7 zero?
  74         sub             r0,r7,r8                        // different?
  75         srwi    r9,r9,5                         // r9 <- (r7==0) ? 1 : 0
  76         or.             r9,r9,r0                        // r9 is nonzero if either different or 0
  77         bdnzt   eq,Lbyteloop            // loop until different, 0, or buf end
  78
  79         bne             Ldone                           // done if different or 0
  80
  81 // LHS is word aligned.  If RHS also is, we need not worry about page
  82 // crossing.  Otherwise, we must stop the word loop before page is crossed.
  83
  84 Laligned:
  85         andi.   r0,r4,3                         // is RHS now word aligned too?
  86         addi    r9,r4,4                         // restore true address of next RHS byte
  87         rlwinm  r9,r9,0,0xFFF           // get RHS offset in page
  88         beq             Lalignedloop            // RHS word aligned, use simple loop
  89         subfic  r9,r9,4096                      // get #bytes left in RHS page
  90         srwi.   r0,r9,2                         // get #words left in RHS page
  91         mtctr   r0                                      // set up loop count
  92         bne++   Lunalignedloop          // at least one word left in RHS page
  93         li              r0,4                            // must check 4 bytes, a byte at a time...
  94         mtctr   r0                                      // ...in order to keep LHS word aligned
  95         b               Lbyteloop                       // go cross RHS page
  96
  97 // Unaligned inner loop: compare a word at a time, until one of three conditions:
  98 //              - a difference is found
  99 //              - a zero byte is found
 100 //              - end of RHS page (we dare not touch next page until we must)
 101 // At this point, registers are as follows:
 102 //              r3 = LHS ptr - 4 (word aligned)
 103 //              r4 = RHS ptr - 4 (not aligned)
 104 //              r5 = 0xFEFEFEFF
 105 //              r6 = 0x80808080
 106 //     ctr = whole words left in RHS page
 107
 108         .align  5                                       // align inner loop, which is 8 words long
 109 Lunalignedloop:
 110         lwzu    r7,4(r3)                        // r7 <- next 4 LHS bytes
 111         lwzu    r8,4(r4)                        // r8 <- next 4 RHS bytes
 112         add             r10,r7,r5                       // r10 <- LHS + 0xFEFEFEFF
 113         andc    r12,r6,r7                       // r12 <- ~LHS & 0x80808080
 114         xor             r11,r7,r8                       // r11 <- compare the words
 115         and             r0,r10,r12                      // r0 <- nonzero iff LHS has a 0-byte
 116         or.             r12,r0,r11                      // combine difference and 0-test vectors
 117         bdnzt   eq,Lunalignedloop       // loop if ctr!=0 and cr0_eq
 118
 119         bne++   Ldifferent                      // done if we found a 0 or difference
 120         li              r0,4                            // must check 4 bytes, a byte at a time...
 121         mtctr   r0                                      // ...in order to keep LHS word aligned
 122         b               Lbyteloop                       // cross RHS page, then resume word loop
 123
 124 // Aligned inner loop: compare a word at a time, until one of two conditions:
 125 //              - a difference is found
 126 //              - a zero byte is found
 127 // At this point, registers are as follows:
 128 //              r3 = LHS ptr - 4 (word aligned)
 129 //              r4 = RHS ptr - 4 (word aligned)
 130 //              r5 = 0xFEFEFEFF
 131 //              r6 = 0x80808080
 132
 133         .align  5                                       // align inner loop, which is 8 words ling
 134 Lalignedloop:
 135         lwzu    r7,4(r3)                        // r7 <- next 4 LHS bytes
 136         lwzu    r8,4(r4)                        // r8 <- next 4 RHS bytes
 137         add             r10,r7,r5                       // r10 <- LHS + 0xFEFEFEFF
 138         andc    r12,r6,r7                       // r12 <- ~LHS & 0x80808080
 139         xor             r11,r7,r8                       // r11 <- compare the words
 140         and             r0,r10,r12                      // r0 <- nonzero iff LHS has a 0-byte
 141         or.             r12,r0,r11                      // combine difference and 0-test vectors
 142         beq             Lalignedloop            // loop if neither found
 143
 144 // Found differing bytes and/or a 0-byte.  Determine which comes first, and
 145 // subtract the bytes to compute the return value.  We also need to mask out the
 146 // false hits in the 0-byte test, which consist of 0x01 bytes that preceed
 147 // the 0-byte.
 148
 149 Ldifferent:                                                     // r0 == 0-test vector (with 0x01 false hits)
 150         slwi    r9,r7,7                         // move 0x01 bits in LHS into position 0x80
 151         andc    r0,r0,r9                        // mask out the false 0-hits from 0x01 bytes
 152         or              r11,r11,r0                      // recompute difference vector
 153         cntlzw  r9,r11                          // find 1st difference (r9 = 0..31)
 154         rlwinm  r9,r9,0,0x18            // byte align bit offset (now, r9 = 0,8,16, or 24)
 155         addi    r9,r9,8                         // now, r9 = 8, 16, 24, or 32
 156         rlwnm   r5,r7,r9,24,31          // right justify differing bytes and mask off rest
 157         rlwnm   r6,r8,r9,24,31
 158         sub             r3,r5,r6                        // compute difference (0, +, or -)
 159         blr
 160
 161 Ldone:                                                          // r0 = return value
 162         mr              r3,r0                           // return in r3
 163         blr
 164