summaryrefslogtreecommitdiffstats
path: root/media
diff options
context:
space:
mode:
authorfbarchard@chromium.org <fbarchard@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98>2009-10-09 09:51:37 +0000
committerfbarchard@chromium.org <fbarchard@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98>2009-10-09 09:51:37 +0000
commit7f5dfbf327c9f19e9b739e81c1c1f6b11d47d4b5 (patch)
tree770e39008e4d6d18f35ae76a98a970116da3264b /media
parentef1f6d8071ed54a6126d2a963feef8d37283cbff (diff)
downloadchromium_src-7f5dfbf327c9f19e9b739e81c1c1f6b11d47d4b5.zip
chromium_src-7f5dfbf327c9f19e9b739e81c1c1f6b11d47d4b5.tar.gz
chromium_src-7f5dfbf327c9f19e9b739e81c1c1f6b11d47d4b5.tar.bz2
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
Diffstat (limited to 'media')
-rw-r--r--media/base/djb2.cc16
-rw-r--r--media/base/djb2.h40
-rw-r--r--media/base/djb2_unittest.cc15
-rw-r--r--media/media.gyp3
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',