/***************************************************************************
 *             __________               __   ___.
 *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
 *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
 *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
 *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
 *                     \/            \/     \/    \/            \/
 * $Id$
 *
 * Copyright (C) 2008 by Michael Sevakis
 *
 * All files in this archive are subject to the GNU General Public License.
 * See the file COPYING in the source tree root for full license agreement.
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
 * KIND, either express or implied.
 *
 ****************************************************************************/
 #include "config.h"

/****************************************************************************
 * int find_first_set_bit(uint32_t val);
 *
 * Find the index of the least significant set bit in the 32-bit word.
 *
 * return values:
 *   0  - bit 0 is set
 *   1  - bit 1 is set
 *   ...
 *   31 - bit 31 is set
 *   32 - no bits set
 ****************************************************************************/
    .align  2
    .global find_first_set_bit
    .type   find_first_set_bit,%function
find_first_set_bit:
    @ Standard trick to isolate bottom bit in r0 or 0 if r0 = 0 on entry
    rsb     r2, r0, #0               @ r1 = r0 & -r0
    ands    r1, r0, r2               @
    
    @ now r1 has at most one set bit, call this X
    
#if ARM_ARCH >= 5
    clz     r0, r1                   @ Get lead 0's count
    rsbne   r0, r0, #31              @ lead 0's -> bit index
    bx      lr                       @
#else
    @ this is the ffs algorithm devised by D.Seal and posted to
    @ comp.sys.arm on 16 Feb 1994.
    @
    @ Output modified to suit Rockbox purposes.

    adr     r2, L_ffs_table
    orrne   r1, r1, r1, lsl #4       @ r1 = X * 0x11
    orrne   r1, r1, r1, lsl #6       @ r1 = X * 0x451
    rsbne   r1, r1, r1, lsl #16      @ r1 = X * 0x0450fbaf

    @ now lookup in table indexed on top 6 bits of r1
    ldrb    r0, [ r2, r1, lsr #26 ]  @
    bx      lr                       @

L_ffs_table:
    @        0   1   2   3   4   5   6   7
    @----------------------------------------------
    .byte   32,  0,  1, 12,  2,  6,  0, 13  @  0- 7
    .byte    3,  0,  7,  0,  0,  0,  0, 14  @  8-15
    .byte   10,  4,  0,  0,  8,  0,  0, 25  @ 16-23
    .byte    0,  0,  0,  0,  0, 21, 27, 15  @ 24-31
    .byte   31, 11,  5,  0,  0,  0,  0,  0  @ 32-39
    .byte    9,  0,  0, 24,  0,  0, 20, 26  @ 40-47
    .byte   30,  0,  0,  0,  0, 23,  0, 19  @ 48-55
    .byte   29,  0, 22, 18, 28, 17, 16,  0  @ 56-63
#endif
    .size   find_first_set_bit, .-find_first_set_bit