Разработчики из компании Google представили (http://google-opensource.blogspot.com/2011/04/introducing-ci...) реализацию 64- и 128-разрядных hash-функций CityHash (http://code.google.com/p/cityhash/), позволяющих получить отпечаток фиксированной длинны, идентифицирующий больший по размеру набор входящих данных. Код функций написан на языке C++, распространяется в рамках лицензии MIT и разработан в стиле "все ради высокой производительности".Код CityHash был написан для реализации высокопроизводительных хэш-таблиц, используемых для организации хранения баз ключ-значение. Функция CityHash128 оптимизирована для строк размером в несколько сотен байт. Оптимизация кода, использование 64-разрядных регистров, обеспечение параллелизма выполнения на уровне инструкций и быстрый доступ к невыровненным областям памяти, позволили добиться значительного превосходства в производительности, по сравнению с другими реализациями хэшей. Ценой производительности является достаточно сильная...
URL: http://google-opensource.blogspot.com/2011/04/introducing-ci...
Новость: http://www.opennet.me/opennews/art.shtml?num=30218
http://code.google.com/p/cityhash/source/browse/trunk/src/ci...А где там C++ ? :)
---
А, во, нашел
#include <algorithm>
using namespace std;
pair<uint64, uint64> v, w;
std::swap(z, x);и всё :)
По вашему любой код на плюсах должен использовать все, включая самые безумные, возможности этого монструозного языка?
блин, ну оберни это в класс, сделай фабрику, опиши это в интерфейсах, как-нибудь припиши к этому буст, и оповести всех нас и компанию гугл о своих достижениях письмом на spam@google.com и очередным бессмысленно-неинформативным комментом здесь. порадуй.
На, жуйhttp://pavlinux.ru/CityHash/city.c
http://pavlinux.ru/CityHash/city.hКампилитца как С так С++ одновременно.
И где там C++?А, во, нашел #ifdef __cplusplus
> И где там C++?
> А, во, нашел #ifdef __cplusplus:)
В коде есть объявления локальных переменных в середине тела функции - такое C-компилятор не "переварит".
> В коде есть объявления локальных переменных в середине тела функции - такое
> C-компилятор не "переварит".переварит.
> переварит.Visual C++ 2008 не возьмёт. GCC я думаю тоже, если расширенный синтаксис отключить.
>> переварит.
> Visual C++ 2008 не возьмёт. GCC я думаю тоже, если расширенный синтаксис
> отключить.Я чего-то не пойму... где проблема?
struct a {int x; int y;};void vodi() {
int x = 0;
printf("%e\n", x);
memset(NULL, 0, 1);
for (int i = 0; i < 1024; i++) { // С99int x = 1024; // С99
struct a vec = {i+2*i, (x+i)/i}; // С99
}
}какое место не нравиться?
>>> переварит.
>> Visual C++ 2008 не возьмёт. GCC я думаю тоже, если расширенный синтаксис
>> отключить.
> Я чего-то не пойму... где проблема?
> ...
> какое место не нравиться?Здесь всё в порядке. Но код вида
int a = 1; // объявление переменной
a = a + 1; // операция без объявления переменной
int b = 2; // снова объявление переменной
по крайнёй мере Visual C++ 9 (2008) не возьмёт - в 3й строке выдаст ошибку, если компились файл как C, а не как C++. Недавно перекомпилировал SDL 1.3 - там как раз была такая проблема.
Уже лет 8 как жуёт без всяких расширений, если не больше.
> http://code.google.com/p/cityhash/source/browse/trunk/src/ci...
> А где там C++ ? :)
> #include <algorithm>
> using namespace std;
> pair<uint64, uint64> v, w;
> std::swap(z, x);
> и всё :)Еще коменты в виде // :).Или в свежих вариантах стандарта си это уже можно? Я понимаю что компилерам пофиг и они и это жрут, но формально // вроде как считается не совместимым с большей частью стандартов на си.
Это C++. Там же теплейты, а это щастье доступно только на C++.
>> http://code.google.com/p/cityhash/source/browse/trunk/src/ci...
>> А где там C++ ? :)
>> #include <algorithm>
>> using namespace std;
>> pair<uint64, uint64> v, w;
>> std::swap(z, x);
>> и всё :)
> Еще коменты в виде // :).Или в свежих вариантах стандарта си это
> уже можно?С99 можно.
> С99 можно.А, тогда ок.
> Еще коменты в виде // :).Или в свежих вариантах стандарта си это уже можно? Я понимаю что компилерам пофиг и они и это жрут, но формально // вроде как считается не совместимым с большей частью стандартов на си.ISO/IEC 9899:1999 (E)
6.4.9 Comments
1 Except within a character constant, a string literal, or a comment, the characters /*
introduce a comment. The contents of such a comment are examined only to identify
multibyte characters and to find the characters */ that terminate it.69)
2 Except within a character constant, a string literal, or a comment, the characters //
introduce a comment that includes all multibyte characters up to, but not including, the
next new-line character. The contents of such a comment are examined only to identify
multibyte characters and to find the terminating new-line character.
Согласен - везде где можно использовать возможности плюсов, надо их использовать. Не на убогом Си же в конце то концов писать? Хотя мазохистов в последнее время полно. =)
Им было удобнее выразить uint128 через пару uint64 + uint64. Хотя от плюсов там конечно не много. Прямо скажем - ничего. Да и то, что есть... using namespace std - расстрел. stdlib.h vs cstdlib, переопределение uintXX_t в uintXX (нахуа?), сплошной char * vs std::string & и пр.. в общем, тяжелое бремя C просто так не проходит. Уж лучше бы написали на C и не вы&^$%&^сь почем зря.
> Им было удобнее выразить uint128 через пару uint64 + uint64. Хотя от плюсов там конечно не много. Прямо скажем - ничего. Да и то, что есть... using namespace std - расстрел. stdlib.h vs cstdlib, переопределение uintXX_t в uintXX (нахуа?), сплошной char * vs std::string & и пр.. в общем, тяжелое бремя C просто так не проходит. Уж лучше бы написали на C и не вы&^$%&^сь почем зря.PS: Впрочем, к самому алгоритму и получаемому хешу это отношения не имеет. Переписывается на что угодно как угодно в течении часа. Если очень хочется. Всего лишь мелкие придирки к стилю конкретного девелупера гугла, не более. А вот то, что описание подоплеки и математическое обоснование алгоритма отсутствует и есть лишь тупой код не важно какого размера - use it on your own risk. Удачи.
static uint128 CityMurmur(const char *s,...Как англоязычные программеры читают этот бред?! :)
cтатичный бцел128 ГородМурмур(пост символ *s,...
> static uint128 CityMurmur(const char *s,...
> Как англоязычные программеры читают этот бред?! :)
> cтатичный бцел128 ГородМурмур(пост символ *s,...А все-равно у нас круче умеют :). На вот тебе, http://habrahabr.ru/blogs/compilers/116301/
Самопальный гопоязык то черт с ним, а вот "сишный" сорц в коментах выглядит убедительно....
CityMurmur - ШёпотГорода, что такого?
char* вместо std::string это как раз очень правильно, с остальным согласен.
> Утверждается, что представленные функции не подходят для использования в криптографии, так как алгоритм работы CityHash подразумевает смешивание битов входящего потока, что допускает появление коллизий (вероятность коллизий крайне низка, что подтверждено накопленной статистикой).существование коллизий - генетическое свойство любых hash-функций
P.S. математики это доказали задолго до появления компьютеров
Все правильно, просто для криптографически стойких хеш-функций подбор коллизии для известного хеша должен быть сравним по затратности с лобовым брутфорсом. У гугли видимо это требование не выполняется - видимо, можно подобрать коллизии существенно проще. Поэтому их функция может и неплоха для некоторых применений (как фукция для hash-table), но не годится для криптографических применений(как функция криптографически удостоверяющая неизменность некоего сообщения, например). А то что существует бесконечно много наборов данных которые мапятся в 128-битный результат не понятно только идиотам да копирасам которые дошли до того что пытаются качать права на вполне конкретные хеши :))))
Её и не предполагается использовать для криптографии. Об этом в статье написано.
> Утверждается, что представленные функции не подходят для использования в криптографии, так как алгоритм работы CityHash подразумевает смешивание битов входящего потока, что допускает появление коллизий (вероятность коллизий крайне низка, что подтверждено накопленной статистикой).Давно не читал подобного бреда.
1. Коллизии по определению имеет абсолютно любая хэш-функция, у которой на входе бит больше, чем на выходе.
2. Для криптографии интерес представляет обратимость хэш-функции (то есть возможность за разумное время угадать такую входную последовательность, чтобы она давала нужную выходную).
Мы вам верим, но всё же - где ссылка на бенчмарки?