Moved bits.h from O3D to Chrome base.

TEST=none
BUG=none

Review URL: http://codereview.chromium.org/373001

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@32428 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 97 insertions, 0 deletions

diff --git a/base/base.gyp b/base/base.gyp
index 51aa6c8..ca71829 100644
--- a/base/base.gyp
+++ b/base/base.gyp
@@ -84,6 +84,7 @@
         'base_switches.cc',
         'base_switches.h',
         'basictypes.h',
+        'bits.h',
         'bzip2_error_handler.cc',
         'chrome_application_mac.h',
         'chrome_application_mac.mm',
@@ -591,6 +592,7 @@
         'at_exit_unittest.cc',
         'atomic_flag_unittest.cc',
         'atomicops_unittest.cc',
+        'bits_unittest.cc',
         'command_line_unittest.cc',
         'condition_variable_unittest.cc',
         'crypto/rsa_private_key_unittest.cc',
diff --git a/base/bits.h b/base/bits.h
new file mode 100644
index 0000000..b2209e8
--- /dev/null
+++ b/base/bits.h
@@ -0,0 +1,47 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// This file defines some bit utilities.
+
+#ifndef BASE_BITS_H_
+#define BASE_BITS_H_
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+
+namespace base {
+namespace bits {
+
+// Returns the integer i such as 2^i <= n < 2^(i+1)
+inline int Log2Floor(uint32 n) {
+  if (n == 0)
+    return -1;
+  int log = 0;
+  uint32 value = n;
+  for (int i = 4; i >= 0; --i) {
+    int shift = (1 << i);
+    uint32 x = value >> shift;
+    if (x != 0) {
+      value = x;
+      log += shift;
+    }
+  }
+  DCHECK_EQ(value, 1u);
+  return log;
+}
+
+// Returns the integer i such as 2^(i-1) < n <= 2^i
+inline int Log2Ceiling(uint32 n) {
+  if (n == 0) {
+    return -1;
+  } else {
+    // Log2Floor returns -1 for 0, so the following works correctly for n=1.
+    return 1 + Log2Floor(n - 1);
+  }
+}
+
+}  // namespace bits
+}  // namespace base
+
+#endif  // BASE_BITS_H_
diff --git a/base/bits_unittest.cc b/base/bits_unittest.cc
new file mode 100644
index 0000000..e913d6a
--- /dev/null
+++ b/base/bits_unittest.cc
@@ -0,0 +1,48 @@
+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// This file contains the unit tests for the bit utilities.
+
+#include "base/bits.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+namespace bits {
+
+TEST(BitsTest, Log2Floor) {
+  EXPECT_EQ(-1, Log2Floor(0));
+  EXPECT_EQ(0, Log2Floor(1));
+  EXPECT_EQ(1, Log2Floor(2));
+  EXPECT_EQ(1, Log2Floor(3));
+  EXPECT_EQ(2, Log2Floor(4));
+  for (int i = 3; i < 31; ++i) {
+    unsigned int value = 1U << i;
+    EXPECT_EQ(i, Log2Floor(value));
+    EXPECT_EQ(i, Log2Floor(value + 1));
+    EXPECT_EQ(i, Log2Floor(value + 2));
+    EXPECT_EQ(i - 1, Log2Floor(value - 1));
+    EXPECT_EQ(i - 1, Log2Floor(value - 2));
+  }
+  EXPECT_EQ(31, Log2Floor(0xffffffffU));
+}
+
+TEST(BitsTest, Log2Ceiling) {
+  EXPECT_EQ(-1, Log2Ceiling(0));
+  EXPECT_EQ(0, Log2Ceiling(1));
+  EXPECT_EQ(1, Log2Ceiling(2));
+  EXPECT_EQ(2, Log2Ceiling(3));
+  EXPECT_EQ(2, Log2Ceiling(4));
+  for (int i = 3; i < 31; ++i) {
+    unsigned int value = 1U << i;
+    EXPECT_EQ(i, Log2Ceiling(value));
+    EXPECT_EQ(i + 1, Log2Ceiling(value + 1));
+    EXPECT_EQ(i + 1, Log2Ceiling(value + 2));
+    EXPECT_EQ(i, Log2Ceiling(value - 1));
+    EXPECT_EQ(i, Log2Ceiling(value - 2));
+  }
+  EXPECT_EQ(32, Log2Ceiling(0xffffffffU));
+}
+
+}  // namespace bits
+}  // namespace base