Add generic ilog2 functions

Add ilog2_{32,64}() and alignlog2_{32,64}() ... the latter is intended
for alignment statements and return -1 for non-power-of-2 other than 0
(which returns 0).

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>

7 files changed, 216 insertions, 12 deletions

diff --git a/Makefile.in b/Makefile.in
index 3fb8184a..5388dea1 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -73,6 +73,7 @@ NASM =	nasm.$(O) nasmlib.$(O) ver.$(O) \
 	output/outmacho64.$(O) preproc.$(O) quote.$(O) pptok.$(O) \
 	macros.$(O) listing.$(O) eval.$(O) exprlib.$(O) stdscan.$(O) \
 	strfunc.$(O) tokhash.$(O) regvals.$(O) regflags.$(O) \
+	ilog2.$(O) \
 	lib/strlcpy.$(O)
 
 NDISASM = ndisasm.$(O) disasm.$(O) sync.$(O) nasmlib.$(O) ver.$(O) \
@@ -272,6 +273,7 @@ float.$(O): float.c compiler.h config.h directives.h float.h insnsi.h nasm.h \
  nasmlib.h opflags.h pptok.h preproc.h regs.h
 hashtbl.$(O): hashtbl.c compiler.h config.h directives.h hashtbl.h insnsi.h \
  nasm.h nasmlib.h opflags.h pptok.h preproc.h regs.h
+ilog2.$(O): ilog2.c compiler.h config.h nasmlib.h
 insnsa.$(O): insnsa.c compiler.h config.h directives.h insns.h insnsi.h \
  nasm.h nasmlib.h opflags.h pptok.h preproc.h regs.h tokens.h
 insnsb.$(O): insnsb.c compiler.h config.h directives.h insns.h insnsi.h \
@@ -312,9 +314,9 @@ output/outas86.$(O): output/outas86.c compiler.h config.h directives.h \
 output/outbin.$(O): output/outbin.c compiler.h config.h directives.h eval.h \
  insnsi.h labels.h nasm.h nasmlib.h opflags.h output/outform.h \
  output/outlib.h pptok.h preproc.h regs.h saa.h stdscan.h
-output/outcoff.$(O): output/outcoff.c output/pecoff.h compiler.h config.h directives.h \
+output/outcoff.$(O): output/outcoff.c compiler.h config.h directives.h \
  eval.h insnsi.h nasm.h nasmlib.h opflags.h output/outform.h output/outlib.h \
- pptok.h preproc.h raa.h regs.h saa.h
+ output/pecoff.h pptok.h preproc.h raa.h regs.h saa.h
 output/outdbg.$(O): output/outdbg.c compiler.h config.h directives.h \
  insnsi.h nasm.h nasmlib.h opflags.h output/outform.h pptok.h preproc.h \
  regs.h
@@ -323,11 +325,11 @@ output/outelf.$(O): output/outelf.c compiler.h config.h directives.h \
  output/outelf.h output/outform.h pptok.h preproc.h regs.h
 output/outelf32.$(O): output/outelf32.c compiler.h config.h directives.h \
  eval.h insnsi.h nasm.h nasmlib.h opflags.h output/dwarf.h output/elf.h \
- output/outelf.h output/outform.h output/stabs.h output/outlib.h pptok.h \
+ output/outelf.h output/outform.h output/outlib.h output/stabs.h pptok.h \
  preproc.h raa.h rbtree.h regs.h saa.h stdscan.h
 output/outelf64.$(O): output/outelf64.c compiler.h config.h directives.h \
  eval.h insnsi.h nasm.h nasmlib.h opflags.h output/dwarf.h output/elf.h \
- output/outelf.h output/outform.h output/stabs.h output/outlib.h pptok.h \
+ output/outelf.h output/outform.h output/outlib.h output/stabs.h pptok.h \
  preproc.h raa.h rbtree.h regs.h saa.h stdscan.h
 output/outform.$(O): output/outform.c compiler.h config.h directives.h \
  insnsi.h nasm.h nasmlib.h opflags.h output/outform.h pptok.h preproc.h \
diff --git a/Mkfiles/msvc.mak b/Mkfiles/msvc.mak
index 5e8d25b2..4b48f95c 100644
--- a/Mkfiles/msvc.mak
+++ b/Mkfiles/msvc.mak
@@ -48,6 +48,7 @@ NASM =	nasm.$(O) nasmlib.$(O) ver.$(O) \
 	output/outmacho64.$(O) preproc.$(O) quote.$(O) pptok.$(O) \
 	macros.$(O) listing.$(O) eval.$(O) exprlib.$(O) stdscan.$(O) \
 	strfunc.$(O) tokhash.$(O) regvals.$(O) regflags.$(O) \
+	ilog2.$(O) \
 	lib/strlcpy.$(O)
 
 NDISASM = ndisasm.$(O) disasm.$(O) sync.$(O) nasmlib.$(O) ver.$(O) \
@@ -205,6 +206,7 @@ float.$(O): float.c compiler.h directives.h float.h insnsi.h nasm.h \
  nasmlib.h opflags.h pptok.h preproc.h regs.h
 hashtbl.$(O): hashtbl.c compiler.h directives.h hashtbl.h insnsi.h nasm.h \
  nasmlib.h opflags.h pptok.h preproc.h regs.h
+ilog2.$(O): ilog2.c compiler.h nasmlib.h
 insnsa.$(O): insnsa.c compiler.h directives.h insns.h insnsi.h nasm.h \
  nasmlib.h opflags.h pptok.h preproc.h regs.h tokens.h
 insnsb.$(O): insnsb.c compiler.h directives.h insns.h insnsi.h nasm.h \
@@ -241,9 +243,9 @@ output/outas86.$(O): output/outas86.c compiler.h directives.h insnsi.h \
 output/outbin.$(O): output/outbin.c compiler.h directives.h eval.h insnsi.h \
  labels.h nasm.h nasmlib.h opflags.h output/outform.h output/outlib.h \
  pptok.h preproc.h regs.h saa.h stdscan.h
-output/outcoff.$(O): output/outcoff.c output/pecoff.h compiler.h directives.h eval.h \
+output/outcoff.$(O): output/outcoff.c compiler.h directives.h eval.h \
  insnsi.h nasm.h nasmlib.h opflags.h output/outform.h output/outlib.h \
- pptok.h preproc.h raa.h regs.h saa.h
+ output/pecoff.h pptok.h preproc.h raa.h regs.h saa.h
 output/outdbg.$(O): output/outdbg.c compiler.h directives.h insnsi.h nasm.h \
  nasmlib.h opflags.h output/outform.h pptok.h preproc.h regs.h
 output/outelf.$(O): output/outelf.c compiler.h directives.h insnsi.h nasm.h \
diff --git a/Mkfiles/netware.mak b/Mkfiles/netware.mak
index 2d833918..731219c7 100644
--- a/Mkfiles/netware.mak
+++ b/Mkfiles/netware.mak
@@ -44,6 +44,7 @@ NASM =	nasm.o nasmlib.o ver.o \
 	outmacho64.o preproc.o quote.o pptok.o \
 	macros.o listing.o eval.o exprlib.o stdscan.o \
 	strfunc.o tokhash.o regvals.o regflags.o \
+	ilog2.o \
 	strlcpy.o
 
 NDISASM = ndisasm.o disasm.o sync.o nasmlib.o ver.o \
@@ -142,6 +143,7 @@ float.o: float.c compiler.h config.h directives.h float.h insnsi.h nasm.h \
  nasmlib.h opflags.h pptok.h preproc.h regs.h
 hashtbl.o: hashtbl.c compiler.h config.h directives.h hashtbl.h insnsi.h \
  nasm.h nasmlib.h opflags.h pptok.h preproc.h regs.h
+ilog2.o: ilog2.c compiler.h config.h nasmlib.h
 insnsa.o: insnsa.c compiler.h config.h directives.h insns.h insnsi.h nasm.h \
  nasmlib.h opflags.h pptok.h preproc.h regs.h tokens.h
 insnsb.o: insnsb.c compiler.h config.h directives.h insns.h insnsi.h nasm.h \
@@ -178,8 +180,9 @@ outas86.o: outas86.c compiler.h config.h directives.h insnsi.h nasm.h \
 outbin.o: outbin.c compiler.h config.h directives.h eval.h insnsi.h labels.h \
  nasm.h nasmlib.h opflags.h outform.h outlib.h pptok.h preproc.h regs.h \
  saa.h stdscan.h
-outcoff.o: outcoff.c pecoff.h compiler.h config.h directives.h eval.h insnsi.h nasm.h \
- nasmlib.h opflags.h outform.h outlib.h pptok.h preproc.h raa.h regs.h saa.h
+outcoff.o: outcoff.c compiler.h config.h directives.h eval.h insnsi.h nasm.h \
+ nasmlib.h opflags.h outform.h outlib.h pecoff.h pptok.h preproc.h raa.h \
+ regs.h saa.h
 outdbg.o: outdbg.c compiler.h config.h directives.h insnsi.h nasm.h \
  nasmlib.h opflags.h outform.h pptok.h preproc.h regs.h
 outelf.o: outelf.c compiler.h config.h directives.h insnsi.h nasm.h \
diff --git a/Mkfiles/openwcom.mak b/Mkfiles/openwcom.mak
index 66e37f4b..26575a76 100644
--- a/Mkfiles/openwcom.mak
+++ b/Mkfiles/openwcom.mak
@@ -60,6 +60,7 @@ NASM =	nasm.$(O) nasmlib.$(O) ver.$(O) &
 	output\outmacho64.$(O) preproc.$(O) quote.$(O) pptok.$(O) &
 	macros.$(O) listing.$(O) eval.$(O) exprlib.$(O) stdscan.$(O) &
 	strfunc.$(O) tokhash.$(O) regvals.$(O) regflags.$(O) &
+	ilog2.$(O) &
 	lib\strlcpy.$(O)
 
 NDISASM = ndisasm.$(O) disasm.$(O) sync.$(O) nasmlib.$(O) ver.$(O) &
@@ -234,6 +235,7 @@ float.$(O): float.c compiler.h directives.h float.h insnsi.h nasm.h &
  nasmlib.h opflags.h pptok.h preproc.h regs.h
 hashtbl.$(O): hashtbl.c compiler.h directives.h hashtbl.h insnsi.h nasm.h &
  nasmlib.h opflags.h pptok.h preproc.h regs.h
+ilog2.$(O): ilog2.c compiler.h nasmlib.h
 insnsa.$(O): insnsa.c compiler.h directives.h insns.h insnsi.h nasm.h &
  nasmlib.h opflags.h pptok.h preproc.h regs.h tokens.h
 insnsb.$(O): insnsb.c compiler.h directives.h insns.h insnsi.h nasm.h &
@@ -270,9 +272,9 @@ output\outas86.$(O): output\outas86.c compiler.h directives.h insnsi.h &
 output\outbin.$(O): output\outbin.c compiler.h directives.h eval.h insnsi.h &
  labels.h nasm.h nasmlib.h opflags.h output\outform.h output\outlib.h &
  pptok.h preproc.h regs.h saa.h stdscan.h
-output\outcoff.$(O): output\outcoff.c output\pecoff.h compiler.h directives.h eval.h &
+output\outcoff.$(O): output\outcoff.c compiler.h directives.h eval.h &
  insnsi.h nasm.h nasmlib.h opflags.h output\outform.h output\outlib.h &
- pptok.h preproc.h raa.h regs.h saa.h
+ output\pecoff.h pptok.h preproc.h raa.h regs.h saa.h
 output\outdbg.$(O): output\outdbg.c compiler.h directives.h insnsi.h nasm.h &
  nasmlib.h opflags.h output\outform.h pptok.h preproc.h regs.h
 output\outelf.$(O): output\outelf.c compiler.h directives.h insnsi.h nasm.h &
diff --git a/Mkfiles/owlinux.mak b/Mkfiles/owlinux.mak
index d6a9af73..3241b28c 100644
--- a/Mkfiles/owlinux.mak
+++ b/Mkfiles/owlinux.mak
@@ -71,6 +71,7 @@ NASM =	nasm.$(O) nasmlib.$(O) ver.$(O) \
 	output/outmacho64.$(O) preproc.$(O) quote.$(O) pptok.$(O) \
 	macros.$(O) listing.$(O) eval.$(O) exprlib.$(O) stdscan.$(O) \
 	strfunc.$(O) tokhash.$(O) regvals.$(O) regflags.$(O) \
+	ilog2.$(O) \
 	lib/strlcpy.$(O)
 
 NDISASM = ndisasm.$(O) disasm.$(O) sync.$(O) nasmlib.$(O) ver.$(O) \
@@ -244,6 +245,7 @@ float.$(O): float.c compiler.h directives.h float.h insnsi.h nasm.h \
  nasmlib.h opflags.h pptok.h preproc.h regs.h
 hashtbl.$(O): hashtbl.c compiler.h directives.h hashtbl.h insnsi.h nasm.h \
  nasmlib.h opflags.h pptok.h preproc.h regs.h
+ilog2.$(O): ilog2.c compiler.h nasmlib.h
 insnsa.$(O): insnsa.c compiler.h directives.h insns.h insnsi.h nasm.h \
  nasmlib.h opflags.h pptok.h preproc.h regs.h tokens.h
 insnsb.$(O): insnsb.c compiler.h directives.h insns.h insnsi.h nasm.h \
@@ -280,9 +282,9 @@ output/outas86.$(O): output/outas86.c compiler.h directives.h insnsi.h \
 output/outbin.$(O): output/outbin.c compiler.h directives.h eval.h insnsi.h \
  labels.h nasm.h nasmlib.h opflags.h output/outform.h output/outlib.h \
  pptok.h preproc.h regs.h saa.h stdscan.h
-output/outcoff.$(O): output/outcoff.c output/pecoff.h compiler.h directives.h eval.h \
+output/outcoff.$(O): output/outcoff.c compiler.h directives.h eval.h \
  insnsi.h nasm.h nasmlib.h opflags.h output/outform.h output/outlib.h \
- pptok.h preproc.h raa.h regs.h saa.h
+ output/pecoff.h pptok.h preproc.h raa.h regs.h saa.h
 output/outdbg.$(O): output/outdbg.c compiler.h directives.h insnsi.h nasm.h \
  nasmlib.h opflags.h output/outform.h pptok.h preproc.h regs.h
 output/outelf.$(O): output/outelf.c compiler.h directives.h insnsi.h nasm.h \
diff --git a/ilog2.c b/ilog2.c
new file mode 100644
index 00000000..3a0b4a41
--- /dev/null
+++ b/ilog2.c
@@ -0,0 +1,181 @@
+/* ----------------------------------------------------------------------- *
+ *
+ *   Copyright 1996-2010 The NASM Authors - All Rights Reserved
+ *   See the file AUTHORS included with the NASM distribution for
+ *   the specific copyright holders.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following
+ *   conditions are met:
+ *
+ *   * Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ *   * 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.
+ *
+ *     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER 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.
+ *
+ * ----------------------------------------------------------------------- */
+
+#include "compiler.h"
+#include "nasmlib.h"
+
+#if defined(__GNUC__) && defined(__x86_64__)
+
+int ilog2_32(uint32_t v)
+{
+    int n;
+
+    __asm__("bsrl %1,%0 ; cmovel %2,%0"
+	    : "=&r" (n)
+	    : "rm" (v), "rm" (0));
+    return n;
+}
+
+#elif defined(__GNUC__) && defined(__i386__)
+
+int ilog2_32(uint32_t v)
+{
+    int n;
+
+    __asm__("bsrl %1,%0 ; jnz 1f ; xorl %0,%0\n"
+	    "1:"
+	    : "=&r" (n)
+	    : "rm" (v));
+    return n;
+}
+
+#elif defined(HAVE_GNUC_4)
+
+int ilog2_32(uint32_t v)
+{
+    if (!v)
+	return 0;
+    else
+	return __builtin_clz(v) ^ 31;
+}
+
+#else
+
+int ilog2_32(uint32_t v)
+{
+	int p = 0;
+
+	if (v & 0xffff0000) {
+		p += 16;
+		v >>= 16;
+	}
+	if (v & 0xff00) {
+		p += 8;
+		v >>= 8;
+	}
+	if (v & 0xf0) {
+		p += 4;
+		v >>= 4;
+	}
+	if (v & 0xc) {
+		p += 2;
+		v >>= 2;
+	}
+	if (v & 0x2) {
+		p += 1;
+		v >>= 1;
+	}
+
+	return p;
+}
+
+#endif
+
+#if defined(__GNUC__) && defined(__x86_64__)
+
+int ilog2_64(uint64_t v)
+{
+    uint64_t n;
+
+    __asm__("bsrq %1,%0 ; cmoveq %2,%0"
+	    : "=&r" (n)
+	    : "rm" (v), "rm" (UINT64_C(0)));
+    return n;
+}
+
+#elif defined(HAVE_GNUC_4)
+
+int ilog2_64(uint64_t v)
+{
+    if (!v)
+	return 0;
+    else
+	return __builtin_clzll(v) ^ 63;
+}
+
+#else
+
+int ilog2_64(uint64_t vv)
+{
+	int p = 0;
+	uint32_t v;
+
+	if ((v = vv >> 32) != 0) {
+	    p += 32;
+	} else {
+	    v = vv;
+	}
+	if (v & 0xffff0000) {
+		p += 16;
+		v >>= 16;
+	}
+	if (v & 0xff00) {
+		p += 8;
+		v >>= 8;
+	}
+	if (v & 0xf0) {
+		p += 4;
+		v >>= 4;
+	}
+	if (v & 0xc) {
+		p += 2;
+		v >>= 2;
+	}
+	if (v & 0x2) {
+		p += 1;
+		v >>= 1;
+	}
+
+	return p;
+}
+
+#endif
+
+/*
+ * v == 0 ? 0 : is_power2(x) ? ilog2_X(v) : -1
+ */
+int alignlog2_32(uint32_t v)
+{
+    if (unlikely(v & (v-1)))
+	return -1;		/* invalid alignment */
+
+    return ilog2_32(v);
+}
+
+int alignlog2_64(uint64_t v)
+{
+    if (unlikely(v & (v-1)))
+	return -1;		/* invalid alignment */
+
+    return ilog2_64(v);
+}
diff --git a/nasmlib.h b/nasmlib.h
index 5efb0b4c..02876c74 100644
--- a/nasmlib.h
+++ b/nasmlib.h
@@ -463,4 +463,16 @@ int idata_bytes(int opcode);
 /* check if value is power of 2 */
 #define is_power2(v)   ((v) && ((v) & ((v) - 1)) == 0)
 
+/*
+ * floor(log2(v))
+ */
+int ilog2_32(uint32_t v);
+int ilog2_64(uint64_t v);
+
+/*
+ * v == 0 ? 0 : is_power2(x) ? ilog2_X(v) : -1
+ */
+int alignlog2_32(uint32_t v);
+int alignlog2_64(uint64_t v);
+
 #endif