1d2912cb1SThomas Gleixner/* SPDX-License-Identifier: GPL-2.0-only */ 21da177e4SLinus Torvalds/* 31da177e4SLinus Torvalds * linux/arch/arm/lib/findbit.S 41da177e4SLinus Torvalds * 51da177e4SLinus Torvalds * Copyright (C) 1995-2000 Russell King 61da177e4SLinus Torvalds * 71da177e4SLinus Torvalds * 16th March 2001 - John Ripley <jripley@sonicblue.com> 81da177e4SLinus Torvalds * Fixed so that "size" is an exclusive not an inclusive quantity. 91da177e4SLinus Torvalds * All users of these functions expect exclusive sizes, and may 101da177e4SLinus Torvalds * also call with zero size. 111da177e4SLinus Torvalds * Reworked by rmk. 121da177e4SLinus Torvalds */ 131da177e4SLinus Torvalds#include <linux/linkage.h> 141da177e4SLinus Torvalds#include <asm/assembler.h> 15*f424f2c1SRussell King (Oracle)#include <asm/unwind.h> 161da177e4SLinus Torvalds .text 171da177e4SLinus Torvalds 182511d032SRussell King (Oracle)#ifdef __ARMEB__ 192511d032SRussell King (Oracle)#define SWAB_ENDIAN le 202511d032SRussell King (Oracle)#else 212511d032SRussell King (Oracle)#define SWAB_ENDIAN be 222511d032SRussell King (Oracle)#endif 232511d032SRussell King (Oracle) 242953a3e1SRussell King (Oracle) .macro find_first, endian, set, name 252953a3e1SRussell King (Oracle)ENTRY(_find_first_\name\()bit_\endian) 26*f424f2c1SRussell King (Oracle) UNWIND( .fnstart) 271da177e4SLinus Torvalds teq r1, #0 281da177e4SLinus Torvalds beq 3f 291da177e4SLinus Torvalds mov r2, #0 302511d032SRussell King (Oracle)1: ldr r3, [r0], #4 312953a3e1SRussell King (Oracle) .ifeq \set 322511d032SRussell King (Oracle) mvns r3, r3 @ invert/test bits 332953a3e1SRussell King (Oracle) .else 342511d032SRussell King (Oracle) movs r3, r3 @ test bits 352953a3e1SRussell King (Oracle) .endif 362511d032SRussell King (Oracle) .ifc \endian, SWAB_ENDIAN 372511d032SRussell King (Oracle) bne .L_found_swab 382511d032SRussell King (Oracle) .else 392511d032SRussell King (Oracle) bne .L_found @ found the bit? 402511d032SRussell King (Oracle) .endif 412511d032SRussell King (Oracle) add r2, r2, #32 @ next index 421da177e4SLinus Torvalds2: cmp r2, r1 @ any more? 431da177e4SLinus Torvalds blo 1b 442511d032SRussell King (Oracle)3: mov r0, r1 @ no more bits 456ebbf2ceSRussell King ret lr 46*f424f2c1SRussell King (Oracle) UNWIND( .fnend) 472953a3e1SRussell King (Oracle)ENDPROC(_find_first_\name\()bit_\endian) 482953a3e1SRussell King (Oracle) .endm 491da177e4SLinus Torvalds 502953a3e1SRussell King (Oracle) .macro find_next, endian, set, name 512953a3e1SRussell King (Oracle)ENTRY(_find_next_\name\()bit_\endian) 52*f424f2c1SRussell King (Oracle) UNWIND( .fnstart) 53ec85bd36SRussell King (Oracle) cmp r2, r1 54ec85bd36SRussell King (Oracle) bhs 3b 552511d032SRussell King (Oracle) mov ip, r2, lsr #5 @ word index 562511d032SRussell King (Oracle) add r0, r0, ip, lsl #2 572511d032SRussell King (Oracle) ands ip, r2, #31 @ bit position 582511d032SRussell King (Oracle) beq 1b 592511d032SRussell King (Oracle) ldr r3, [r0], #4 602953a3e1SRussell King (Oracle) .ifeq \set 612511d032SRussell King (Oracle) mvn r3, r3 @ invert bits 622511d032SRussell King (Oracle) .endif 632511d032SRussell King (Oracle) .ifc \endian, SWAB_ENDIAN 642511d032SRussell King (Oracle) rev_l r3, ip 652511d032SRussell King (Oracle) .if .Lrev_l_uses_tmp 662511d032SRussell King (Oracle) @ we need to recompute ip because rev_l will have overwritten 672511d032SRussell King (Oracle) @ it. 682511d032SRussell King (Oracle) and ip, r2, #31 @ bit position 692511d032SRussell King (Oracle) .endif 702953a3e1SRussell King (Oracle) .endif 711da177e4SLinus Torvalds movs r3, r3, lsr ip @ shift off unused bits 728adbb371SNicolas Pitre bne .L_found 732511d032SRussell King (Oracle) orr r2, r2, #31 @ no zero bits 741da177e4SLinus Torvalds add r2, r2, #1 @ align bit pointer 751da177e4SLinus Torvalds b 2b @ loop for next bit 76*f424f2c1SRussell King (Oracle) UNWIND( .fnend) 772953a3e1SRussell King (Oracle)ENDPROC(_find_next_\name\()bit_\endian) 782953a3e1SRussell King (Oracle) .endm 792953a3e1SRussell King (Oracle) 802953a3e1SRussell King (Oracle) .macro find_bit, endian, set, name 812953a3e1SRussell King (Oracle) find_first \endian, \set, \name 822953a3e1SRussell King (Oracle) find_next \endian, \set, \name 832953a3e1SRussell King (Oracle) .endm 842953a3e1SRussell King (Oracle) 852953a3e1SRussell King (Oracle)/* _find_first_zero_bit_le and _find_next_zero_bit_le */ 862953a3e1SRussell King (Oracle) find_bit le, 0, zero_ 872953a3e1SRussell King (Oracle) 882953a3e1SRussell King (Oracle)/* _find_first_bit_le and _find_next_bit_le */ 892953a3e1SRussell King (Oracle) find_bit le, 1 901da177e4SLinus Torvalds 911da177e4SLinus Torvalds#ifdef __ARMEB__ 921da177e4SLinus Torvalds 932953a3e1SRussell King (Oracle)/* _find_first_zero_bit_be and _find_next_zero_bit_be */ 942953a3e1SRussell King (Oracle) find_bit be, 0, zero_ 951da177e4SLinus Torvalds 962953a3e1SRussell King (Oracle)/* _find_first_bit_be and _find_next_bit_be */ 972953a3e1SRussell King (Oracle) find_bit be, 1 981da177e4SLinus Torvalds 991da177e4SLinus Torvalds#endif 1001da177e4SLinus Torvalds 1011da177e4SLinus Torvalds/* 1021da177e4SLinus Torvalds * One or more bits in the LSB of r3 are assumed to be set. 1031da177e4SLinus Torvalds */ 1042511d032SRussell King (Oracle).L_found_swab: 105*f424f2c1SRussell King (Oracle) UNWIND( .fnstart) 1062511d032SRussell King (Oracle) rev_l r3, ip 1078adbb371SNicolas Pitre.L_found: 108bceab143SRussell King (Oracle)#if __LINUX_ARM_ARCH__ >= 7 109bceab143SRussell King (Oracle) rbit r3, r3 @ reverse bits 110bceab143SRussell King (Oracle) clz r3, r3 @ count high zero bits 111bceab143SRussell King (Oracle) add r0, r2, r3 @ add offset of first set bit 112bceab143SRussell King (Oracle)#elif __LINUX_ARM_ARCH__ >= 5 1130e91ec0cSJames Jones rsb r0, r3, #0 1147e009387SRussell King (Oracle) and r3, r3, r0 @ mask out lowest bit set 1157e009387SRussell King (Oracle) clz r3, r3 @ count high zero bits 1167e009387SRussell King (Oracle) rsb r3, r3, #31 @ offset of first set bit 1177e009387SRussell King (Oracle) add r0, r2, r3 @ add offset of first set bit 1181da177e4SLinus Torvalds#else 1192511d032SRussell King (Oracle) mov ip, #~0 1202511d032SRussell King (Oracle) tst r3, ip, lsr #16 @ test bits 0-15 1212511d032SRussell King (Oracle) addeq r2, r2, #16 1222511d032SRussell King (Oracle) moveq r3, r3, lsr #16 1232511d032SRussell King (Oracle) tst r3, #0x00ff 1242511d032SRussell King (Oracle) addeq r2, r2, #8 1252511d032SRussell King (Oracle) moveq r3, r3, lsr #8 1262511d032SRussell King (Oracle) tst r3, #0x000f 1271da177e4SLinus Torvalds addeq r2, r2, #4 1282511d032SRussell King (Oracle) moveq r3, r3, lsr #4 1292511d032SRussell King (Oracle) tst r3, #0x0003 1301da177e4SLinus Torvalds addeq r2, r2, #2 1312511d032SRussell King (Oracle) moveq r3, r3, lsr #2 1322511d032SRussell King (Oracle) tst r3, #0x0001 1331da177e4SLinus Torvalds addeq r2, r2, #1 1341da177e4SLinus Torvalds mov r0, r2 1351da177e4SLinus Torvalds#endif 1360e91ec0cSJames Jones cmp r1, r0 @ Clamp to maxbit 1370e91ec0cSJames Jones movlo r0, r1 1386ebbf2ceSRussell King ret lr 139*f424f2c1SRussell King (Oracle) UNWIND( .fnend) 140