軽量ハッシュアルゴリズム

今回はハッシュアルゴリズムについて少し触れてみたいと思います。

既存のハッシュアルゴリズムはどういうものがあるでしょうか？
SHA-1, MD5等が浮かんだ方も多いと思います。

「じゃあそれでいいじゃん」

・・・ちょっと待ってください。
SHA-1, MD5というものは、暗号化のためのハッシュアルゴリズムです。
もし用途が単純なファイル比較等であれば、ここまで大げさなハッシュは冗長で高負荷低速であると言えます。
適切なアルゴリズムは状況によって適切に選びたいところです。

そこで今回は単純なファイル比較等に使用できる、簡単＆軽量なハッシュアルゴリズムの

FNV-1

というアルゴリズムを紹介します。

詳細はこちらへどうぞ
http://wowdev.jp/?p=873

ソースはこちらです。

#include <stdio.h>
#include <stdint.h>

/**
 * FNV Constants
 */
static const uint32_t FNV_OFFSET_BASIS_32 = 2166136261U;
static const uint64_t FNV_OFFSET_BASIS_64 = 14695981039346656037U;

static const uint32_t FNV_PRIME_32 = 16777619U;
static const uint64_t FNV_PRIME_64 = 1099511628211LLU;

/**
 * FNV Hash Algorithm
 */
uint32_t fnv_1_hash_32(uint8_t *bytes, size_t length)
{
    uint32_t hash;
    size_t i;

    hash = FNV_OFFSET_BASIS_32;
    for( i = 0 ; i < length ; ++i) {
        hash = (FNV_PRIME_32 * hash) ^ (bytes[i]);
    }

    return hash;
}
uint64_t fnv_1_hash_64(uint8_t *bytes, size_t length)
{
    uint64_t hash;
    size_t i;

    hash = FNV_OFFSET_BASIS_64;
    for( i = 0 ; i < length ; ++i) {
        hash = (FNV_PRIME_64 * hash) ^ (bytes[i]);
    }

    return hash;
}