decbin/decoct/dechex optimization.

4 files changed, 121 insertions, 3 deletions

diff --git a/Zend/zend_bitset.h b/Zend/zend_bitset.h
index 9e196713f0..b7c369c749 100644
--- a/Zend/zend_bitset.h
+++ b/Zend/zend_bitset.h
@@ -75,6 +75,46 @@ static zend_always_inline int zend_ulong_ntz(zend_ulong num)
 #endif
 }
 
+/* Number of leading zero bits (Undefined for zero) */
+static zend_always_inline int zend_ulong_nlz(zend_ulong num)
+{
+#if (defined(__GNUC__) || __has_builtin(__builtin_clzl)) \
+	&& SIZEOF_ZEND_LONG == SIZEOF_LONG && defined(PHP_HAVE_BUILTIN_CLZL)
+	return __builtin_clzl(num);
+#elif (defined(__GNUC__) || __has_builtin(__builtin_clzll)) && defined(PHP_HAVE_BUILTIN_CLZLL)
+	return __builtin_clzll(num);
+#elif defined(_WIN32)
+	unsigned long index;
+
+#if defined(_WIN64)
+	if (!BitScanReverse64(&index, num)) {
+#else
+	if (!BitScanReverse(&index, num)) {
+#endif
+		/* undefined behavior */
+		return SIZEOF_ZEND_LONG * 8;
+	}
+
+	return (int) (SIZEOF_ZEND_LONG * 8 - 1)- index;
+#else
+	zend_ulong x;
+	int n;
+
+#if SIZEOF_ZEND_LONG == 8
+	n = 64;
+	x = num >> 32; if (x != 0) {n -= 32; num = x;}
+#else
+	n = 32;
+#endif
+	x = num >> 16; if (x != 0) {n -= 16; num = x;}
+	x = num >> 8;  if (x != 0) {n -=  8; num = x;}
+	x = num >> 4;  if (x != 0) {n -=  4; num = x;}
+	x = num >> 2;  if (x != 0) {n -=  2; num = x;}
+	x = num >> 1;  if (x != 0) return n - 2;
+	return n - num;
+#endif
+}
+
 /* Returns the number of zend_ulong words needed to store a bitset that is N
    bits long.  */
 static inline uint32_t zend_bitset_len(uint32_t n)
diff --git a/build/php.m4 b/build/php.m4
index da1007ff4e..b0e3c424d1 100644
--- a/build/php.m4
+++ b/build/php.m4
@@ -2449,6 +2449,44 @@ AC_DEFUN([PHP_CHECK_BUILTIN_CLZ], [
 ])
 
 dnl
+dnl PHP_CHECK_BUILTIN_CLZL
+dnl
+AC_DEFUN([PHP_CHECK_BUILTIN_CLZL], [
+  AC_MSG_CHECKING([for __builtin_clzl])
+
+  AC_LINK_IFELSE([AC_LANG_PROGRAM([], [[
+    return __builtin_clzl(1) ? 1 : 0;
+  ]])], [
+    have_builtin_clzl=1
+    AC_MSG_RESULT([yes])
+  ], [
+    have_builtin_clzl=0
+    AC_MSG_RESULT([no])
+  ])
+
+  AC_DEFINE_UNQUOTED([PHP_HAVE_BUILTIN_CLZL], [$have_builtin_clzl], [Whether the compiler supports __builtin_clzl])
+])
+
+dnl
+dnl PHP_CHECK_BUILTIN_CLZLL
+dnl
+AC_DEFUN([PHP_CHECK_BUILTIN_CLZLL], [
+  AC_MSG_CHECKING([for __builtin_clzll])
+
+  AC_LINK_IFELSE([AC_LANG_PROGRAM([], [[
+    return __builtin_clzll(1) ? 1 : 0;
+  ]])], [
+    have_builtin_clzll=1
+    AC_MSG_RESULT([yes])
+  ], [
+    have_builtin_clzll=0
+    AC_MSG_RESULT([no])
+  ])
+
+  AC_DEFINE_UNQUOTED([PHP_HAVE_BUILTIN_CLZLL], [$have_builtin_clzll], [Whether the compiler supports __builtin_clzll])
+])
+
+dnl
 dnl PHP_CHECK_BUILTIN_CTZL
 dnl
 AC_DEFUN([PHP_CHECK_BUILTIN_CTZL], [
diff --git a/configure.ac b/configure.ac
index 3ff9a91bf9..f82783a03b 100644
--- a/configure.ac
+++ b/configure.ac
@@ -465,6 +465,10 @@ dnl Check __builtin_expect
 PHP_CHECK_BUILTIN_EXPECT
 dnl Check __builtin_clz
 PHP_CHECK_BUILTIN_CLZ
+dnl Check __builtin_clzl
+PHP_CHECK_BUILTIN_CLZL
+dnl Check __builtin_clzll
+PHP_CHECK_BUILTIN_CLZLL
 dnl Check __builtin_ctzl
 PHP_CHECK_BUILTIN_CTZL
 dnl Check __builtin_ctzll
diff --git a/ext/standard/math.c b/ext/standard/math.c
index 2aedcc259d..4f723be365 100644
--- a/ext/standard/math.c
+++ b/ext/standard/math.c
@@ -22,6 +22,7 @@
 #include "zend_multiply.h"
 #include "zend_exceptions.h"
 #include "zend_portability.h"
+#include "zend_bitset.h"
 
 #include <math.h>
 #include <float.h>
@@ -821,6 +822,41 @@ PHPAPI zend_string * _php_math_longtobase(zend_long arg, int base)
 }
 /* }}} */
 
+/* {{{ _php_math_longtobase_pwr2 */
+/*
+ * Convert a long to a string containing a base(2,4,6,16,32) representation of
+ * the number.
+ */
+static zend_always_inline zend_string * _php_math_longtobase_pwr2(zend_long arg, int base_log2)
+{
+	static const char digits[] = "0123456789abcdefghijklmnopqrstuvwxyz";
+	zend_ulong value;
+	size_t len;
+	zend_string *ret;
+	char *ptr;
+
+	value = arg;
+
+	if (value == 0) {
+		len = 1;
+	} else {
+		len = ((sizeof(value) * 8 - zend_ulong_nlz(value)) + (base_log2 - 1)) / base_log2;
+	}
+
+	ret = zend_string_alloc(len, 0);
+	ptr = ZSTR_VAL(ret) + len;
+	*ptr = '\0';
+
+	do {
+		ZEND_ASSERT(ptr > ZSTR_VAL(ret));
+		*--ptr = digits[value & ((1 << base_log2) - 1)];
+		value >>= base_log2;
+	} while (value);
+
+	return ret;
+}
+/* }}} */
+
 /* {{{ _php_math_zvaltobase */
 /*
  * Convert a zval to a string containing a base(2-36) representation of
@@ -908,7 +944,7 @@ PHP_FUNCTION(decbin)
 		Z_PARAM_LONG(arg)
 	ZEND_PARSE_PARAMETERS_END();
 
-	RETURN_STR(_php_math_longtobase(arg, 2));
+	RETURN_STR(_php_math_longtobase_pwr2(arg, 1));
 }
 /* }}} */
 
@@ -921,7 +957,7 @@ PHP_FUNCTION(decoct)
 		Z_PARAM_LONG(arg)
 	ZEND_PARSE_PARAMETERS_END();
 
-	RETURN_STR(_php_math_longtobase(arg, 8));
+	RETURN_STR(_php_math_longtobase_pwr2(arg, 3));
 }
 /* }}} */
 
@@ -934,7 +970,7 @@ PHP_FUNCTION(dechex)
 		Z_PARAM_LONG(arg)
 	ZEND_PARSE_PARAMETERS_END();
 
-	RETURN_STR(_php_math_longtobase(arg, 16));
+	RETURN_STR(_php_math_longtobase_pwr2(arg, 4));
 }
 /* }}} */