common/lib/libc/arch/arm/string/ffs.S

   1 /*      $NetBSD: ffs.S,v 1.9 2015/05/17 22:14:38 justin 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
  33 RCSID("$NetBSD: ffs.S,v 1.9 2015/05/17 22:14:38 justin Exp $")
  34
  35 /*
  36  * ffs - find first set bit, this algorithm isolates the first set
  37  * bit, then multiplies the number by 0x0450fbaf which leaves the top
  38  * 6 bits as an index into the table.  This algorithm should be a win
  39  * over the checking each bit in turn as per the C compiled version.
  40  *
  41  * On ARMv5 we use CLZ (count leading Zero's) and then subtract the result
  42  * from 32.
  43  *
  44  * This is the ffs algorithm devised by d.seal and posted to comp.sys.arm on
  45  * 16 Feb 1994.
  46  */
  47 #ifndef _RUMPKERNEL
  48 STRONG_ALIAS(__ffssi2,ffs)
  49 #endif
  50 #if (defined(_ARM_ARCH_5) && !defined(__thumb__)) || defined(_ARM_ARCH_T2)
  51 #if defined(_ARM_ARCH_T2)
  52 ENTRY(ffs)
  53 #else
  54 ARM_ENTRY(ffs)
  55 #endif
  56         /* (X & -X) gives LSB or zero.  */
  57         neg     r1, r0
  58         and     r0, r0, r1
  59         clz     r0, r0
  60         rsb     r0, r0, #32
  61         RET
  62 END(ffs)
  63 #else
  64 ARM_ENTRY(ffs)
  65         /* Standard trick to isolate bottom bit in r0 or 0 if r0 = 0 on entry */
  66         neg     r1, r0
  67         ands    r0, r0, r1
  68         /*
  69          * now r0 has at most one set bit, call this X
  70          * if X = 0, all further instructions are skipped
  71          */
  72         adrne   r2, .L_ffs_table
  73         orrne   r0, r0, r0, lsl #4  /* r0 = X * 0x11 */
  74         orrne   r0, r0, r0, lsl #6  /* r0 = X * 0x451 */
  75         rsbne   r0, r0, r0, lsl #16 /* r0 = X * 0x0450fbaf */
  76
  77         /* now lookup in table indexed on top 6 bits of r0 */
  78         ldrbne  r0, [r2, r0, lsr #26]
  79
  80         RET
  81 .text;
  82 .type .L_ffs_table, _ASM_TYPE_OBJECT;
  83 .L_ffs_table:
  84 /*               0   1   2   3   4   5   6   7           */
  85         .byte    0,  1,  2, 13,  3,  7,  0, 14  /*  0- 7 */
  86         .byte    4,  0,  8,  0,  0,  0,  0, 15  /*  8-15 */
  87         .byte   11,  5,  0,  0,  9,  0,  0, 26  /* 16-23 */
  88         .byte    0,  0,  0,  0,  0, 22, 28, 16  /* 24-31 */
  89         .byte   32, 12,  6,  0,  0,  0,  0,  0  /* 32-39 */
  90         .byte   10,  0,  0, 25,  0,  0, 21, 27  /* 40-47 */
  91         .byte   31,  0,  0,  0,  0, 24,  0, 20  /* 48-55 */
  92         .byte   30,  0, 23, 19, 29, 18, 17,  0  /* 56-63 */
  93 END(ffs)
  94 #endif