sysdeps/alpha/memchr.S

   1 /* Copyright (C) 1996 Free Software Foundation, Inc.
   2    Contributed by David Mosberger (davidm@cs.arizona.edu).
   3
   4 This file is part of the GNU C Library.
   5
   6 The GNU C Library is free software; you can redistribute it and/or
   7 modify it under the terms of the GNU Library General Public License as
   8 published by the Free Software Foundation; either version 2 of the
   9 License, or (at your option) any later version.
  10
  11 The GNU C Library is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 Library General Public License for more details.
  15
  16 You should have received a copy of the GNU Library General Public
  17 License along with the GNU C Library; see the file COPYING.LIB.  If
  18 not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  19 Cambridge, MA 02139, USA.  */
  20
  21 /* Finds characters in a memory area.  Optimized for the Alpha
  22 architecture:
  23
  24       - memory accessed as aligned quadwords only
  25       - uses cmpbge to compare 8 bytes in parallel
  26       - does binary search to find 0 byte in last
  27         quadword (HAKMEM needed 12 instructions to
  28         do this instead of the 9 instructions that
  29         binary search needs).
  30
  31 For correctness consider that:
  32
  33       - only minimum number of quadwords may be accessed
  34       - the third argument is an unsigned long
  35 */
  36
  37 #include <sysdep.h>
  38
  39         .set noreorder
  40         .set noat
  41
  42 ENTRY(memchr)
  43         .prologue 0
  44
  45         beq     a2, not_found
  46         ldq_u   t0, 0(a0)       # load first quadword (a0 may be misaligned)
  47         addq    a0, a2, t4
  48         and     a1, 0xff, a1    # a1 = 00000000000000ch
  49         ldq_u   t5, -1(t4)
  50         sll     a1,  8, t1      # t1 = 000000000000ch00
  51         cmpult  a2, 9, t3
  52         or      t1, a1, a1      # a1 = 000000000000chch
  53         sll     a1, 16, t1      # t1 = 00000000chch0000
  54         lda     t2, -1(zero)
  55         or      t1, a1, a1      # a1 = 00000000chchchch
  56         sll     a1, 32, t1      # t1 = chchchch00000000
  57         extql   t0, a0, t6
  58         or      t1, a1, a1      # a1 = chchchchchchchch
  59
  60         beq     t3, first_quad
  61
  62         extqh   t5, a0, t5
  63         mov     a0, v0
  64         or      t6, t5, t0      # t0 = quadword starting at a0
  65
  66         #
  67         # Deal with the case where at most 8 bytes remain to be searched
  68         # in t0.  E.g.:
  69         #       a2 = 6
  70         #       t0 = ????c6c5c4c3c2c1
  71 last_quad:
  72         negq    a2, t5
  73         srl     t2, t5, t5      # t5 = mask of a2 bits set
  74         xor     a1, t0, t0
  75         cmpbge  zero, t0, t1
  76         and     t1, t5, t1
  77         beq     t1, not_found
  78
  79 found_it:
  80         # now, determine which byte matched:
  81         negq    t1, t2
  82         and     t1, t2, t1
  83
  84         and     t1, 0x0f, t0
  85         addq    v0, 4, t2
  86         cmoveq  t0, t2, v0
  87
  88         and     t1, 0x33, t0
  89         addq    v0, 2, t2
  90         cmoveq  t0, t2, v0
  91
  92         and     t1, 0x55, t0
  93         addq    v0, 1, t2
  94         cmoveq  t0, t2, v0
  95
  96 done:   ret
  97
  98
  99         #
 100         # Deal with the case where a2 > 8 bytes remain to be
 101         # searched.  a0 may not be aligned.
 102         #
 103 first_quad:
 104         andnot  a0, 0x7, v0
 105         insqh   t2, a0, t1      # t1 = 0000ffffffffffff (a0<0:2> ff bytes)
 106         xor     t0, a1, t0
 107         or      t0, t1, t0      # t0 = ====ffffffffffff
 108         cmpbge  zero, t0, t1
 109         bne     t1, found_it
 110
 111         /* at least one byte left to process */
 112
 113         ldq     t0, 8(v0)
 114         addq    v0, 8, v0
 115         /*
 116          * Make a2 point to last quad to be accessed (the
 117          * last quad may or may not be partial).
 118          */
 119         subq    t4, 1, a2
 120         andnot  a2, 0x7, a2
 121         cmpult  v0, a2, t1
 122         beq     t1, final
 123
 124         /* at least two quads remain to be accessed */
 125
 126         subq    a2, v0, t3      # t3 <- number of quads to be processed in loop
 127         and     t3, 8, t3       # odd number of quads?
 128         bne     t3, odd_quad_count
 129
 130         /* at least three quads remain to be accessed */
 131
 132         mov     t0, t3          # move prefetched value into correct register
 133
 134         .align  3
 135 unrolled_loop:
 136         ldq     t0, 8(v0)       # prefetch t0
 137         xor     a1, t3, t1
 138         cmpbge  zero, t1, t1
 139         bne     t1, found_it
 140
 141         addq    v0, 8, v0
 142 odd_quad_count:
 143         xor     a1, t0, t1
 144         ldq     t3, 8(v0)       # prefetch t3
 145         cmpbge  zero, t1, t1
 146         bne     t1, found_it
 147
 148         addq    v0, 8, v0
 149         cmpult  v0, a2, t5
 150         bne     t5, unrolled_loop
 151
 152         mov     t3, t0          # move prefetched value into t0
 153 final:  subq    t4, v0, a2      # a2 <- number of bytes left to do
 154         bne     a2, last_quad
 155
 156 not_found:
 157         mov     zero, v0
 158         ret
 159
 160         .end    memchr