firmware/target/arm/ffs-arm.S

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  * $Id$
   9  *
  10  * Copyright (C) 2008 by Michael Sevakis
  11  *
  12  * This program is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU General Public License
  14  * as published by the Free Software Foundation; either version 2
  15  * of the License, or (at your option) any later version.
  16  *
  17  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  18  * KIND, either express or implied.
  19  *
  20  ****************************************************************************/
  21  #include "config.h"
  22
  23 /****************************************************************************
  24  * int find_first_set_bit(uint32_t val);
  25  *
  26  * Find the index of the least significant set bit in the 32-bit word.
  27  *
  28  * return values:
  29  *   0  - bit 0 is set
  30  *   1  - bit 1 is set
  31  *   ...
  32  *   31 - bit 31 is set
  33  *   32 - no bits set
  34  ****************************************************************************/
  35     .align  2
  36     .global find_first_set_bit
  37     .type   find_first_set_bit,%function
  38 find_first_set_bit:
  39     @ Standard trick to isolate bottom bit in r0 or 0 if r0 = 0 on entry
  40     rsb     r2, r0, #0               @ r1 = r0 & -r0
  41     ands    r1, r0, r2               @
  42
  43     @ now r1 has at most one set bit, call this X
  44
  45 #if ARM_ARCH >= 5
  46     clz     r0, r1                   @ Get lead 0's count
  47     rsbne   r0, r0, #31              @ lead 0's -> bit index
  48     bx      lr                       @
  49 #else
  50     @ this is the ffs algorithm devised by D.Seal and posted to
  51     @ comp.sys.arm on 16 Feb 1994.
  52     @
  53     @ Output modified to suit Rockbox purposes.
  54
  55     adr     r2, L_ffs_table
  56     orrne   r1, r1, r1, lsl #4       @ r1 = X * 0x11
  57     orrne   r1, r1, r1, lsl #6       @ r1 = X * 0x451
  58     rsbne   r1, r1, r1, lsl #16      @ r1 = X * 0x0450fbaf
  59
  60     @ now lookup in table indexed on top 6 bits of r1
  61     ldrb    r0, [ r2, r1, lsr #26 ]  @
  62     bx      lr                       @
  63
  64 L_ffs_table:
  65     @        0   1   2   3   4   5   6   7
  66     @----------------------------------------------
  67     .byte   32,  0,  1, 12,  2,  6,  0, 13  @  0- 7
  68     .byte    3,  0,  7,  0,  0,  0,  0, 14  @  8-15
  69     .byte   10,  4,  0,  0,  8,  0,  0, 25  @ 16-23
  70     .byte    0,  0,  0,  0,  0, 21, 27, 15  @ 24-31
  71     .byte   31, 11,  5,  0,  0,  0,  0,  0  @ 32-39
  72     .byte    9,  0,  0, 24,  0,  0, 20, 26  @ 40-47
  73     .byte   30,  0,  0,  0,  0, 23,  0, 19  @ 48-55
  74     .byte   29,  0, 22, 18, 28, 17, 16,  0  @ 56-63
  75 #endif
  76     .size   find_first_set_bit, .-find_first_set_bit