Thu Jun 13 00:02:25 1996 Roland McGrath <roland@delasyd.gnu.ai.mit.edu>
[kopensolaris-gnu/glibc.git] / 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)