lib: Unify log2() and related functions

This patch adds a few bit counting functions that are commonly needed
for certain register calculations. We previously had a log2()
implementation already, but it was awkwardly split between some C code
that's only available in ramstage and an optimized x86-specific
implementation in pre-RAM that prevented other archs from pulling it
into earlier stages.

Using __builtin_clz() as the baseline allows GCC to inline optimized
assembly for most archs (including CLZ on ARM/ARM64 and BSR on x86), and
to perform constant-folding if possible. What was previously named log2f
on pre-RAM x86 is now ffs, since that's the standard name for that
operation and I honestly don't have the slightest idea how it could've
ever ended up being called log2f (which in POSIX is 'binary(2) LOGarithm
with Float result, whereas the Find First Set operation has no direct
correlation to logarithms that I know of). Make ffs result 0-based
instead of the POSIX standard's 1-based since that is consistent with
clz, log2 and the former log2f, and generally closer to what you want
for most applications (a value that can directly be used as a shift to
reach the found bit). Call it __ffs() instead of ffs() to avoid problems
when importing code, since that's what Linux uses for the 0-based
operation.

CQ-DEPEND=CL:273023
BRANCH=None
BUG=None
TEST=Built on Big, Falco, Jerry, Oak and Urara. Compared old and new
log2() and __ffs() results on Falco for a bunch of test values.

Change-Id: I599209b342059e17b3130621edb6b6bbeae26876
Signed-off-by: Patrick Georgi <pgeorgi@chromium.org>
Original-Commit-Id: 3701a16ae944ecff9c54fa9a50d28015690fcb2f
Original-Change-Id: I60f7cf893792508188fa04d088401a8bca4b4af6
Original-Signed-off-by: Julius Werner <jwerner@chromium.org>
Original-Reviewed-on: https://chromium-review.googlesource.com/273008
Original-Reviewed-by: Patrick Georgi <pgeorgi@chromium.org>
Reviewed-on: http://review.coreboot.org/10394
Tested-by: build bot (Jenkins)
Reviewed-by: Stefan Reinauer <stefan.reinauer@coreboot.org>

4 files changed, 44 insertions, 46 deletions

diff --git a/payloads/libpayload/include/libpayload.h b/payloads/libpayload/include/libpayload.h
index 781a41d354..c3ca123f1f 100644
--- a/payloads/libpayload/include/libpayload.h
+++ b/payloads/libpayload/include/libpayload.h
@@ -311,6 +311,13 @@ u8 bin2hex(u8 b);
 u8 hex2bin(u8 h);
 void hexdump(const void *memory, size_t length);
 void fatal(const char *msg) __attribute__ ((noreturn));
+
+/* Count Leading Zeroes: clz(0) == 32, clz(0xf) == 28, clz(1 << 31) == 0 */
+static inline int clz(u32 x) { return x ? __builtin_clz(x) : sizeof(x) * 8; }
+/* Integer binary logarithm (rounding down): log2(0) == -1, log2(5) == 2 */
+static inline int log2(u32 x) { return sizeof(x) * 8 - clz(x) - 1; }
+/* Find First Set: __ffs(0xf) == 0, __ffs(0) == -1, __ffs(1 << 31) == 31 */
+static inline int __ffs(u32 x) { return log2(x & (u32)(-(s32)x)); }
 /** @} */
 
 
diff --git a/payloads/libpayload/include/strings.h b/payloads/libpayload/include/strings.h
deleted file mode 100644
index 5beddc6a7f..0000000000
--- a/payloads/libpayload/include/strings.h
+++ /dev/null
@@ -1,35 +0,0 @@
-/*
- * This file is part of the libpayload project.
- *
- * Copyright (C) 2011 secunet Security Networks AG
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- * 3. The name of the author may not be used to endorse or promote products
- *    derived from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#ifndef _STRINGS_H
-#define _STRINGS_H
-
-int ffs(int i);
-
-#endif
diff --git a/payloads/libpayload/libc/Makefile.inc b/payloads/libpayload/libc/Makefile.inc
index b4f75a6cb5..272cda9ac4 100644
--- a/payloads/libpayload/libc/Makefile.inc
+++ b/payloads/libpayload/libc/Makefile.inc
@@ -29,10 +29,10 @@
 ##
 
 libc-$(CONFIG_LP_LIBC) += malloc.c printf.c console.c string.c
-libc-$(CONFIG_LP_LIBC) += memory.c ctype.c ipchecksum.c lib.c
+libc-$(CONFIG_LP_LIBC) += memory.c ctype.c ipchecksum.c lib.c libgcc.c
 libc-$(CONFIG_LP_LIBC) += rand.c time.c exec.c
 libc-$(CONFIG_LP_LIBC) += readline.c getopt_long.c sysinfo.c
-libc-$(CONFIG_LP_LIBC) += args.c strings.c
+libc-$(CONFIG_LP_LIBC) += args.c
 libc-$(CONFIG_LP_LIBC) += strlcpy.c
 libc-$(CONFIG_LP_LIBC) += qsort.c
 libc-$(CONFIG_LP_LIBC) += hexdump.c
diff --git a/payloads/libpayload/libc/strings.c b/payloads/libpayload/libc/libgcc.c
index 465ae4f12d..86698d8db3 100644
--- a/payloads/libpayload/libc/strings.c
+++ b/payloads/libpayload/libc/libgcc.c
@@ -1,7 +1,7 @@
 /*
  * This file is part of the libpayload project.
  *
- * Copyright (C) 2011 secunet Security Networks AG
+ * Copyright 2015 Google Inc.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -14,6 +14,10 @@
  * 3. The name of the author may not be used to endorse or promote products
  *    derived from this software without specific prior written permission.
  *
+ * Alternatively, this software may be distributed under the terms of the
+ * GNU General Public License ("GPL") version 2 as published by the Free
+ * Software Foundation.
+ *
  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
@@ -27,16 +31,38 @@
  * SUCH DAMAGE.
  */
 
-#include <strings.h>
+#include <libpayload.h>
 
-int ffs(int i)
+/*
+ * Provide platform-independent backend implementation for __builtin_clz() in
+ * <libpayload.h> in case GCC does not have an assembly version for this arch.
+ */
+
+int __clzsi2(u32 a);
+int __clzsi2(u32 a)
 {
-	int count = 1;
-	if (i == 0) return 0;
+	static const u8 four_bit_table[] = {
+		[0x0] = 4, [0x1] = 3, [0x2] = 2, [0x3] = 2,
+		[0x4] = 1, [0x5] = 1, [0x6] = 1, [0x7] = 1,
+		[0x8] = 0, [0x9] = 0, [0xa] = 0, [0xb] = 0,
+		[0xc] = 0, [0xd] = 0, [0xe] = 0, [0xf] = 0,
+	};
+	int r = 0;
 
-	while ((i & 1) != 1) {
-		i>>=1;
-		count++;
+	if (!(a & (0xffff << 16))) {
+		r += 16;
+		a <<= 16;
 	}
-	return count;
+
+	if (!(a & (0xff << 24))) {
+		r += 8;
+		a <<= 8;
+	}
+
+	if (!(a & (0xf << 28))) {
+		r += 4;
+		a <<= 4;
+	}
+
+	return r + four_bit_table[a >> 28];
 }