diff options
| author | Mark Kettenis <kettenis@cvs.openbsd.org> | 2018-01-21 21:56:03 +0000 |
|---|---|---|
| committer | Mark Kettenis <kettenis@cvs.openbsd.org> | 2018-01-21 21:56:03 +0000 |
| commit | 82946774b8f655196f950df4e0977f2365423ca2 (patch) | |
| tree | e3819018bb0eb40989ad23401cd5d032140972bd /lib/libc | |
| parent | 6783bb61aea5f515f7d9a5077207ad1cf421280b (diff) | |
Implement ffs(3) using the CLZ instructions which has been available ever
since ARMv5. Should be much faster but more importantly it removes the
data table from .text which could introduce unwanted ROP gadgets.
Based on changes in Android/Bionic by Elliott Hughes.
ok patrick@
Diffstat (limited to 'lib/libc')
| -rw-r--r-- | lib/libc/arch/arm/string/ffs.S | 49 |
1 files changed, 6 insertions, 43 deletions
diff --git a/lib/libc/arch/arm/string/ffs.S b/lib/libc/arch/arm/string/ffs.S index 9cb18ce92f7..2503f334635 100644 --- a/lib/libc/arch/arm/string/ffs.S +++ b/lib/libc/arch/arm/string/ffs.S @@ -1,4 +1,4 @@ -/* $OpenBSD: ffs.S,v 1.8 2018/01/19 11:10:43 jca Exp $ */ +/* $OpenBSD: ffs.S,v 1.9 2018/01/21 21:56:02 kettenis Exp $ */ /* $NetBSD: ffs.S,v 1.5 2003/04/05 23:08:52 bjh21 Exp $ */ /* * Copyright (c) 2001 Christopher Gilbert @@ -31,49 +31,12 @@ #include "DEFS.h" -/* - * ffs - find first set bit, this algorithm isolates the first set - * bit, then multiplies the number by 0x0450fbaf which leaves the top - * 6 bits as an index into the table. This algorithm should be a win - * over the checking each bit in turn as per the C compiled version. - * - * under ARMv5 there's an instruction called CLZ (count leading Zero's) that - * could be used - * - * This is the ffs algorithm devised by d.seal and posted to comp.sys.arm on - * 16 Feb 1994. - */ - - .syntax unified - ENTRY(ffs) /* Standard trick to isolate bottom bit in r0 or 0 if r0 = 0 on entry */ - rsb r1, r0, #0 - ands r0, r0, r1 - /* - * now r0 has at most one set bit, call this X - * if X = 0, all further instructions are skipped - */ - adrne r2, .L_ffs_table - orrne r0, r0, r0, lsl #4 /* r0 = X * 0x11 */ - orrne r0, r0, r0, lsl #6 /* r0 = X * 0x451 */ - rsbne r0, r0, r0, lsl #16 /* r0 = X * 0x0450fbaf */ - - /* now lookup in table indexed on top 6 bits of r0 */ - ldrbne r0, [ r2, r0, lsr #26 ] - - mov pc, lr + rsb r1, r0, #0 + ands r0, r0, r1 + clzne r0, r0 + rsbne r0, r0, #32 + bx lr END(ffs) .protected ffs - -.type .L_ffs_table, _ASM_TYPE_OBJECT; -.L_ffs_table: -/* 0 1 2 3 4 5 6 7 */ - .byte 0, 1, 2, 13, 3, 7, 0, 14 /* 0- 7 */ - .byte 4, 0, 8, 0, 0, 0, 0, 15 /* 8-15 */ - .byte 11, 5, 0, 0, 9, 0, 0, 26 /* 16-23 */ - .byte 0, 0, 0, 0, 0, 22, 28, 16 /* 24-31 */ - .byte 32, 12, 6, 0, 0, 0, 0, 0 /* 32-39 */ - .byte 10, 0, 0, 25, 0, 0, 21, 27 /* 40-47 */ - .byte 31, 0, 0, 0, 0, 24, 0, 20 /* 48-55 */ - .byte 30, 0, 23, 19, 29, 18, 17, 0 /* 56-63 */ |