sys/libkern/arm/ffs.S

   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$");
  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
  49 ENTRY(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         clzne   r0, r0
  55         rsbne   r0, r0, #32
  56         RET
  57 END(ffs)
  58