ffs.S revision 302408 
1/*	$NetBSD: ffs.S,v 1.3 2003/04/05 23:27:15 bjh21 Exp $	*/
2/*-
3 * Copyright (c) 2001 Christopher Gilbert
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 * 3. The name of the company nor the name of the author may be used to
15 *    endorse or promote products derived from this software without specific
16 *    prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
22 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
24 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31#include <machine/asm.h>
32__FBSDID("$FreeBSD: stable/11/sys/libkern/arm/ffs.S 275520 2014-12-05 19:08:36Z andrew $");
33
34	.syntax	unified
35
36/*
37 * ffs - find first set bit, this algorithm isolates the first set
38 * bit, then multiplies the number by 0x0450fbaf which leaves the top
39 * 6 bits as an index into the table.  This algorithm should be a win
40 * over the checking each bit in turn as per the C compiled version.
41 *
42 * under ARMv5 there's an instruction called CLZ (count leading Zero's) that
43 * could be used
44 *
45 * This is the ffs algorithm devised by d.seal and posted to comp.sys.arm on
46 * 16 Feb 1994.
47 */
48
49ENTRY(ffs)
50
51	/* Standard trick to isolate bottom bit in r0 or 0 if r0 = 0 on entry */
52 	rsb     r1, r0, #0
53 	ands    r0, r0, r1
54#ifndef _ARM_ARCH_5
55
56	/*
57	 * now r0 has at most one set bit, call this X
58	 * if X = 0, all further instructions are skipped
59	 */
60	adrne   r2, .L_ffs_table
61	orrne   r0, r0, r0, lsl #4  /* r0 = X * 0x11 */
62	orrne   r0, r0, r0, lsl #6  /* r0 = X * 0x451 */
63	rsbne   r0, r0, r0, lsl #16 /* r0 = X * 0x0450fbaf */
64
65	/* now lookup in table indexed on top 6 bits of r0 */
66	ldrbne  r0, [ r2, r0, lsr #26 ]
67
68	RET
69.text;
70.type .L_ffs_table, _ASM_TYPE_OBJECT;
71.L_ffs_table:
72/*               0   1   2   3   4   5   6   7           */
73	.byte	 0,  1,  2, 13,  3,  7,  0, 14  /*  0- 7 */
74	.byte	 4,  0,  8,  0,  0,  0,  0, 15  /*  8-15 */
75	.byte	11,  5,  0,  0,  9,  0,  0, 26  /* 16-23 */
76	.byte	 0,  0,  0,  0,  0, 22, 28, 16  /* 24-31 */
77	.byte	32, 12,  6,  0,  0,  0,  0,  0	/* 32-39 */
78	.byte	10,  0,  0, 25,  0,  0, 21, 27  /* 40-47 */
79	.byte	31,  0,  0,  0,  0, 24,  0, 20  /* 48-55 */
80	.byte   30,  0, 23, 19, 29, 18, 17,  0  /* 56-63 */
81#else
82	clzne	r0, r0
83	rsbne	r0, r0, #32
84	RET
85#endif
86END(ffs)
87
88