Цель-C: реализация хеширования Фаулера – Нолла – Во (FNV)

Question

У меня есть HTTP-коннектор в моем проекте iPhone, и запросы должны иметь набор параметров из имени пользователя с использованием хеша Фаулера-Нолля-Во (FNV).

В настоящее время у меня работает реализация Java, это код:

long fnv_prime = 0x811C9DC5;
long hash = 0;

for(int i = 0; i < str.length(); i++)
{
    hash *= fnv_prime;
    hash ^= str.charAt(i);
}

Теперь на стороне iPhone я сделал это:

int64_t fnv_prime = 0x811C9DC5;
int64_T hash = 0;

for (int i=0; i < [myString length]; i++)
{
    hash *= fnv_prime;
    hash ^= [myString characterAtIndex:i];
}

Этот скрипт не дает того же результата, что и Java.

В первом цикле я получаю это:

hash = 0

hash = 100 (первая буква "d")

hash = 1865261300 (для hash = 100 и fnv_prime = -2128831035, как в Java)

Кто-то видит то, что мне не хватает?

Заранее спасибо за помощь!

Answer 1

В Java эта строка:

long fnv_prime = 0x811C9DC5;

даст в fnv_prime числовое значение -2128831035, потому что константа интерпретируется как int, что является 32-битным значением со знаком в Java. Это значение затем расширяется до знака при записи в long.

И наоборот, в коде Objective-C:

int64_t fnv_prime = 0x811C9DC5;

0x811C9DC5 интерпретируется как константа unsigned int (поскольку она не помещается в 32-битный int со знаком) с числовым значением 2166136261. Затем это значение записывается в fnv_prime, и имеется Никаких признаков расширения, поскольку для компилятора C это значение положительное.

Таким образом, вы получите разные значения для fnv_prime, что объясняет ваши отличные результаты.

Это можно исправить в Java, добавив суффикс "L", например:

long fnv_prime = 0x811C9DC5L;

, который заставляет компилятор Java интерпретировать константу как long с тем же числовым значением, что и то, что вы получаете с кодом Objective-C.

Answer 2

Кстати, 0x811C9DC5 - это , а не простое число FNV (оно даже не простое); это 32-битный FNV "смещение". Вы получите неправильные хеш-значения, если будете использовать это значение (и другие хеш-коллизии). Правильное значение для 32-разрядного простого FNV - 0x1000193. Смотри http://www.isthe.com/chongo/tech/comp/fnv/index.html

Answer 3

Это разница в расширении знака, назначающем 32-битное значение 0x811C9DC5 для 64-битной переменной.

Answer 4

Являются ли символы в Java и Objective-c одинаковыми? NSString даст вам unichars.