1/*        $NetBSD: ffs.S,v 1.3 2013/09/12 15:36:14 joerg Exp $        */
2
3/*
4 * Copyright (c) 1992, 1993
5 *        The Regents of the University of California.  All rights reserved.
6 *
7 * This software was developed by the Computer Systems Engineering group
8 * at Lawrence Berkeley Laboratory under DARPA contract BG 91-66 and
9 * contributed to Berkeley.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 *    notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 *    notice, this list of conditions and the following disclaimer in the
18 *    documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the University nor the names of its contributors
20 *    may be used to endorse or promote products derived from this software
21 *    without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 *
35 * from: Header: ffs.s,v 1.3 92/07/07 00:23:57 torek Exp
36 */
37
38#include <machine/asm.h>
39#if defined(LIBC_SCCS) && !defined(lint)
40#if 0
41          .asciz "@(#)ffs.s   8.1 (Berkeley) 6/4/93"
42#else
43          RCSID("$NetBSD: ffs.S,v 1.3 2013/09/12 15:36:14 joerg Exp $")
44#endif
45#endif  /* LIBC_SCCS and not lint */
46
47#if 0
48          /*
49           * We have a popcount instruction -- use it.
50           * only uses %o0, %o1, %o2
51           *
52           * Here's the pseudo-code from the v9 spec:
53           *
54           * int ffs(unsigned zz) {
55           *        return popc( zz ^ ( ~ (-zz)));
56           * }
57           *
58           * XXXX sptifires and blackbirds don't implement popc,
59           * so we won't use this nice clean code 8^(.
60           */
61ENTRY(ffs)
62          neg       %o0, %o1                                ! %o1 = -zz
63          xnor      %o0, %o1, %o2                                     ! %o2 = zz ^ ~ -zz
64          popc      %o2, %o1
65          movrz     %o0, %g0, %o1                                     ! result of ffs(0) should be zero
66          retl
67           mov      %o1, %o0
68#endif
69/*
70 * ffs returns the number of the rightmost bit set in its argument,
71 * i.e., the lowest value such that (x & (ffs(x) - 1)) is nonzero.
72 * If no bits are set, ffs returns 0.
73 *
74 * We use a table lookup on each byte.
75 *
76 * In each section below, %o1 is the current byte (0, 1, 2, or 3).
77 * The last byte is handled specially: for the first three,
78 * if that byte is nonzero, we return the table value
79 * (plus 0, 8, or 16 for the byte number), but for the last
80 * one, we just return the table value plus 24.  This means
81 * that ffstab[0] must be -24 so that ffs(0) will return 0.
82 */
83ENTRY(ffs)
84#ifdef __PIC__
85          PICCY_SET(ffstab, %o2, %o3)
86#else
87          set       ffstab, %o2
88#endif
89          andcc     %o0, 0xff, %o1      ! get low byte
90          be,a      1f                  ! try again if 0
91           srl      %o0, 8, %o0         ! delay slot, get ready for next byte
92
93          retl                          ! return ffstab[%o1]
94           ldsb     [%o2 + %o1], %o0
95
961:
97          andcc     %o0, 0xff, %o1      ! byte 1 like byte 0...
98          be,a      2f
99           srl      %o0, 8, %o0         ! (use delay to prepare for byte 2)
100
101          ldsb      [%o2 + %o1], %o0
102          retl                          ! return ffstab[%o1] + 8
103           add      %o0, 8, %o0
104
1052:
106          andcc     %o0, 0xff, %o1
107          be,a      3f
108           srl      %o0, 8, %o0         ! (prepare for byte 3)
109
110          ldsb      [%o2 + %o1], %o0
111          retl                          ! return ffstab[%o1] + 16
112           add      %o0, 16, %o0
113
1143:                                      ! just return ffstab[%o0] + 24
115          ldsb      [%o2 + %o0], %o0
116          retl
117           add      %o0, 24, %o0
118
119ffstab:
120          .byte     -24,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 /* 00-0f */
121          .byte     5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* 10-1f */
122          .byte     6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* 20-2f */
123          .byte     5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* 30-3f */
124          .byte     7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* 40-4f */
125          .byte     5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* 50-5f */
126          .byte     6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* 60-6f */
127          .byte     5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* 70-7f */
128          .byte     8,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* 80-8f */
129          .byte     5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* 10-9f */
130          .byte     6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* a0-af */
131          .byte     5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* b0-bf */
132          .byte     7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* c0-cf */
133          .byte     5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* d0-df */
134          .byte     6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* e0-ef */
135          .byte     5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1         /* f0-ff */
136