Make av1_ceil_log2 work for full range of int type
The current implementation of av1_ceil_log2() gets into an infinite loop
if the input is greater than 2^30. Fix this bug by judicious use of the
unsigned int type.
It would be better to define av1_ceil_log2(n) as get_msb(n - 1) + 1
because get_msb() has optimized implementations.
Change-Id: I433da0aeea03214b440ecb82e9189d20a56e3d4d
diff --git a/av1/common/entropymode.h b/av1/common/entropymode.h
index d1b0df2..09cd6bd 100644
--- a/av1/common/entropymode.h
+++ b/av1/common/entropymode.h
@@ -190,11 +190,11 @@
void av1_setup_past_independence(struct AV1Common *cm);
// Returns (int)ceil(log2(n)).
-// NOTE: This implementation only works for n <= 2^30.
static INLINE int av1_ceil_log2(int n) {
if (n < 2) return 0;
- int i = 1, p = 2;
- while (p < n) {
+ int i = 1;
+ unsigned int p = 2;
+ while (p < (unsigned int)n) {
i++;
p = p << 1;
}
diff --git a/test/log2_test.cc b/test/log2_test.cc
index d7840c6..71cf8b2 100644
--- a/test/log2_test.cc
+++ b/test/log2_test.cc
@@ -9,6 +9,7 @@
* PATENTS file, you can obtain it at www.aomedia.org/license/patent.
*/
+#include <limits.h>
#include <math.h>
#include "aom_ports/bitops.h"
@@ -42,9 +43,9 @@
const int power_of_2 = 1 << exponent;
EXPECT_EQ(av1_ceil_log2(power_of_2 - 1), exponent);
EXPECT_EQ(av1_ceil_log2(power_of_2), exponent);
- // The current implementation of av1_ceil_log2 only works up to 2^30.
- if (exponent < 30) {
- EXPECT_EQ(av1_ceil_log2(power_of_2 + 1), exponent + 1);
- }
+ EXPECT_EQ(av1_ceil_log2(power_of_2 + 1), exponent + 1);
}
+
+ // INT_MAX = 2^31 - 1
+ EXPECT_EQ(av1_ceil_log2(INT_MAX), 31);
}
