15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2011 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef MEDIA_BASE_DJB2_H_ 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define MEDIA_BASE_DJB2_H_ 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "media/base/media_export.h" 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DJB2 is a hash algorithm with excellent distribution and speed 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// on many different sets. 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// It has marginally more collisions than FNV1, but makes up for it in 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// performance. 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The return value is suitable for table lookups. 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// For small fixed sizes (ie a pixel), it has low overhead and inlines well. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// For large data sets, it optimizes into assembly/simd and is appropriate 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for realtime applications. 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// See Also: 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// http://www.cse.yorku.ca/~oz/hash.html 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const uint32 kDJB2HashSeed = 5381u; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// These functions perform DJB2 hash. The simplest call is DJB2Hash() to 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// generate the DJB2 hash of the given data: 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// uint32 hash = DJB2Hash(data1, length1, kDJB2HashSeed); 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// You can also compute the DJB2 hash of data incrementally by making multiple 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// calls to DJB2Hash(): 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// uint32 hash_value = kDJB2HashSeed; // Initial seed for DJB2. 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for (size_t i = 0; i < copy_lines; ++i) { 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// hash_value = DJB2Hash(source, bytes_per_line, hash_value); 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// source += source_stride; 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// } 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// For the given buffer of data, compute the DJB2 hash of 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the data. You can call this any number of times during the computation. 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)MEDIA_EXPORT uint32 DJB2Hash(const void* buf, size_t len, uint32 seed); 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // MEDIA_BASE_DJB2_H_ 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 42