DJB2 Hash for applications where high speed hash or checksum values are needed.

BUG=21126
TEST=djb2_unittest.cc has a quick test.  will replace versions in media unittests and media_bench in future.

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

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

4 files changed, 74 insertions, 0 deletions

diff --git a/media/base/djb2.cc b/media/base/djb2.cc
new file mode 100644
index 0000000..3f790ed
--- /dev/null
+++ b/media/base/djb2.cc
@@ -0,0 +1,16 @@
+// 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.
+
+#include "media/base/djb2.h"
+
+uint32 DJB2Hash(const void* buf, size_t len, uint32 hash) {
+  const uint8* s = reinterpret_cast<const uint8*>(buf);
+  if (len > 0) {
+    do {
+      hash = hash * 33 + *s++;
+    } while (--len);
+  }
+  return hash;
+}
+
diff --git a/media/base/djb2.h b/media/base/djb2.h
new file mode 100644
index 0000000..2b696fa
--- /dev/null
+++ b/media/base/djb2.h
@@ -0,0 +1,40 @@
+// 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.
+
+#ifndef MEDIA_BASE_DJB2_H_
+#define MEDIA_BASE_DJB2_H_
+
+#include "base/basictypes.h"
+
+// DJB2 is a hash algorithm with excellent distribution and speed
+// on many different sets.
+// It has marginally more collisions than FNV1, but makes up for it in
+// performance.
+// The return value is suitable for table lookups.
+// For small fixed sizes (ie a pixel), it has low overhead and inlines well.
+// For large data sets, it optimizes into assembly/simd and is appropriate
+// for realtime applications.
+// See Also:
+//   http://www.cse.yorku.ca/~oz/hash.html
+
+static const uint32 kDJB2HashSeed = 5381u;
+
+// These functions perform DJB2 hash. The simplest call is DJB2Hash() to
+// generate the DJB2 hash of the given data:
+//   uint32 hash = DJB2Hash(data1, length1, kDJB2HashSeed);
+//
+// You can also compute the DJB2 hash of data incrementally by making multiple
+// calls to DJB2Hash():
+//   uint32 hash_value = kDJB2HashSeed;  // Initial seed for DJB2.
+//   for (size_t i = 0; i < copy_lines; ++i) {
+//     hash_value = DJB2Hash(source, bytes_per_line, hash_value);
+//     source += source_stride;
+//   }
+
+// For the given buffer of data, compute the DJB2 hash of
+// the data. You can call this any number of times during the computation.
+uint32 DJB2Hash(const void* buf, size_t len, uint32 seed);
+
+#endif  // MEDIA_BASE_DJB2_H_
+
diff --git a/media/base/djb2_unittest.cc b/media/base/djb2_unittest.cc
new file mode 100644
index 0000000..f7898aaf
--- /dev/null
+++ b/media/base/djb2_unittest.cc
@@ -0,0 +1,15 @@
+// Copyright (c) 2008 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.
+
+#include "media/base/djb2.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+uint8 kTestData[] = { 1, 2, 3 };
+
+TEST(DJB2HashTest, HashTest) {
+  EXPECT_EQ(DJB2Hash(NULL, 0, 0u), 0u);
+  EXPECT_EQ(DJB2Hash(kTestData, sizeof(kTestData), 5381u),
+                     ((5381u * 33u + 1u) * 33u + 2u) * 33u + 3u);
+}
diff --git a/media/media.gyp b/media/media.gyp
index ce3abca..4825347 100644
--- a/media/media.gyp
+++ b/media/media.gyp
@@ -57,6 +57,8 @@
         'base/clock_impl.h',
         'base/data_buffer.cc',
         'base/data_buffer.h',
+        'base/djb2.cc',
+        'base/djb2.h',
         'base/factory.h',
         'base/filter_host.h',
         'base/filters.h',
@@ -169,6 +171,7 @@
         'base/buffer_queue_unittest.cc',
         'base/clock_impl_unittest.cc',
         'base/data_buffer_unittest.cc',
+        'base/djb2_unittest.cc',
         'base/mock_ffmpeg.cc',
         'base/mock_ffmpeg.h',
         'base/mock_filter_host.h',