sysdeps/alpha/memchr.S

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