The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/libkern/arm/ffs.S

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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: releng/8.0/sys/libkern/arm/ffs.S 172615 2007-10-13 12:05:36Z cognet $");
   33 
   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  * under ARMv5 there's an instruction called CLZ (count leading Zero's) that
   42  * could be used
   43  *
   44  * This is the ffs algorithm devised by d.seal and posted to comp.sys.arm on
   45  * 16 Feb 1994.
   46  */
   47 
   48 ENTRY(ffs)
   49 
   50         /* Standard trick to isolate bottom bit in r0 or 0 if r0 = 0 on entry */
   51         rsb     r1, r0, #0
   52         ands    r0, r0, r1
   53 #ifndef _ARM_ARCH_5
   54         
   55         /*
   56          * now r0 has at most one set bit, call this X
   57          * if X = 0, all further instructions are skipped
   58          */
   59         adrne   r2, .L_ffs_table
   60         orrne   r0, r0, r0, lsl #4  /* r0 = X * 0x11 */ 
   61         orrne   r0, r0, r0, lsl #6  /* r0 = X * 0x451 */
   62         rsbne   r0, r0, r0, lsl #16 /* r0 = X * 0x0450fbaf */
   63               
   64         /* now lookup in table indexed on top 6 bits of r0 */
   65         ldrneb  r0, [ r2, r0, lsr #26 ]
   66 
   67         RET
   68 .text;
   69 .type .L_ffs_table, _ASM_TYPE_OBJECT;
   70 .L_ffs_table:
   71 /*               0   1   2   3   4   5   6   7           */
   72         .byte    0,  1,  2, 13,  3,  7,  0, 14  /*  0- 7 */
   73         .byte    4,  0,  8,  0,  0,  0,  0, 15  /*  8-15 */
   74         .byte   11,  5,  0,  0,  9,  0,  0, 26  /* 16-23 */
   75         .byte    0,  0,  0,  0,  0, 22, 28, 16  /* 24-31 */
   76         .byte   32, 12,  6,  0,  0,  0,  0,  0  /* 32-39 */
   77         .byte   10,  0,  0, 25,  0,  0, 21, 27  /* 40-47 */
   78         .byte   31,  0,  0,  0,  0, 24,  0, 20  /* 48-55 */
   79         .byte   30,  0, 23, 19, 29, 18, 17,  0  /* 56-63 */
   80 #else
   81         clzne   r0, r0
   82         rsbne   r0, r0, #32
   83         RET
   84 #endif

Cache object: de3f38d9d8d05fcc8276f367f92c4638


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.