Обратить хэш спереди

Существует ли такой хэш от последовательности байт Hash(b1, b2, b3, b4, b5...) чтобы можно было ьыстро вычислить Hash(b2, b3, b4, b5...) , не пересчитывая его целиком?

пока кроме тривиальной суммы ничего на ум не приходит. =(((
как сделать такую штуку для crc32 или для хеша "вращай, прибавляй, вращай, прибавляй", которые вроде так просто не обращаются?

 

google: RElf crc32 adjuster|inverter

 

Конкретно мне нужно обратить хеш

rol eax,13
mov bl,[esi]
add eax,ebx

но не пересчитывая его весь с конца, а "вычитая" влияние первого байта.

 

А если попробовать сделать
ror eax,13*(N-1)
sub eax,movzx [first_byte]
rol eax,13*(N-1)
?

 

Со сложением такая штука не работает, но идея хорошая, если заменить add/sub на xor тада работает.
Однако, хеш слабоват будет, т.к. слабо меняется от нулей, еще бы че придумать покруче!

Говорят, что такую штуку можно проделать даже для crc32, но этот вопрос нужно изучать.

 

Black_mirror
Забыл сказать мерси =)))

 

persicum
Если у тебя окно фиксированной длины, то ты можешь составить таблицу остатков для всех значений первого байта, дополненного нулями до длины окна, и чтобы выкинуть влияние первого байта, просто делаешь XOR со значением из этой таблицы, а потом обновляешь CRC со следующим байтом.

 

Да, так оно и есть, по индексу первого байта из волшебной таблицы вынимается значение, ксорится, и влияние первого байта на CRC устраняется. Скачал сырцы. Однако код для построение такой таблицы довольно сложный, чтобы самому допетрить, ведь CRC начинается с FFFFFFFF и это начальное значение тоже влияет, короче, практический код непростой.

 

persicum
Тогда Magic[BB]=CRC( BB и далее N-1 нулевых байт) ^ CRC(N-1 нулевых байт). Кажется так.

 

Можно задачу саму чуть по проще ввести. Если мы сделаем счётчик N для считываемых байт и какую-то хорошую хеш функцию F от двух параметров. Расчёт суммы будет выглядеть так:

S=S^F(N,data[N]), N++;

Первый байт можно вычитать легко S=S^(N-4,data[N-4]); и сумма достаточно хорошая.

Только вот хорошей хеш функции на ум не приходит.

 

кстати тут редактирование сломалось или как?

 

persicum
Если для вычисления хеша использовать сложение по модулю 2^32-1(то есть после ADD добавить еще ADC EAX,0), то хеш очень легко обращается:

Код (Text):

1. ror eax,(BLOCK_LEN-1)*13
2. movzx ebx,[old_byte]
3. not ebx
4. add eax,ebx
5. adc eax,0
6. rol eax,BLOCK_LEN*13
7. movzx ebx,[new_byte]
8. add eax,ebx
9. adc eax,0

 

Код (Text):

1. #define C 239      
2. #define M 11883089 
3. dword dd;
4. dword int Chc(byte *text,int size)
5. {
6.     dword res=0; dd=1;
7.     while(size--) {
8.         dd=(dd*C)%M;
9.         res=(res*C+*text++)%M;
10.     }
11.     return res;
12. }
13.  
14. dword update(dword chc,byte b0,byte bn)
15. {
16.  
17.     ss=-dd*(int)(BYTE)ref[0];
18.     ss+=(M-ss)/M*M;
19.  
20. }

 

Код (Text):

1. dword update(dword sum,byte b0,byte bn)
2. {
3.     dword ss;
4.     ss=-dd*(int)b0;
5.     ss+=(M-ss)/M*M;
6.     return (sum*C+ss+bn)%M;
7. }

(редактировать не даёт, падла тупая).
вообщем вот такая функция, она довольно качественный хеш даёт...

 

Константы нежелательно просто так трогать. Переполнение, т.е. ошибки легко получить...

 

Интересная идея!!!

Proteus
Чуть попозже заценю обязательно...

Ну принцип такой... только реальный код еще учитывает инициализацию и финализацию с FFFFFFFF, то есть по сути выкусывает не первый байт, а пятый байт.

Да, выкусывание первого байта от CRC32 представляется парадоксальным, т.к. первый байт опрелеляет все последующие байты и все случайные выборы из таблицы. Однако, действительно, abcdef = a00000 xor bcdef, поэтому можно найти остаток от a00000 и его отксорить.

 

Hash(b1, b2, b3, b4, b5...)=F(b1, Hash(b2, b3, b4, b5...))
весь вопрос в том чтоб найти эту функцию и уж по ней судить можно ли найти к ней обратную так чтоб
Hash(b2, b3, b4, b5...)=F'(b1, Hash(b1, b2, b3, b4, b5...))

 

Ну надо же, кто-то еще помнит

 

RElf
если честно, гуглить не стал, так как подумал что у Вас наверняка идет речь о подгоне CRC32 путем обычного реверса с конца вплоть до того места, куда нужно вставить патч.
Я не уверен, что задача скользящего поиска CRC32 кемто ставилась и решалась до меня. Slide_CRC32_update это прикольная процедура, она принимает первый и последний байт окна и за одно действие выдает обновленный вариант.

Пользуясь случаем, так как найти Вас может быть не просто, как выдающемуся алгебраисту в сети хочу подкинуть Вам вопросик об умножении в поле GF(2^32) с использованием небольших таблиц.
Я знаю два варианта решения задачи, первый это в регистрах процессора за 32 оборота,
а второй это побайтово за 16 оборотов и 7 таблиц на 64К. Интересно, что по битам может быть даже быстрее за счет фактора параллельности в 32 , а побайтово параллельности нет.
Есть еще метод через генераторы 16 битных субполей в поле 2^32, вот там вроде нужно всего пять или шесть раз в табицы слазить. Не знаю, как к этому подойти, почему не четыре или не 65537, а пять субполей нужно... Гуглил гуглил по теме умножения полиномов при отсутствии аппаратной поддержки такого умножения статей много, но все чегото не про то ... В общем, нужны ублюдочные неполные генераторы и умение както потом сцеплять результат. Китайская теорема о расстановке солдат в рядки вроде тоже не поможет, тк поле образует неприводимый многочлен... В общем, если не затруднит дайте решение проблемки...

 

persicum
По поводу аппаратной оптимизации - это не ко мне. Могу посмотреть на этот вопрос, если вы его четко сформулируете: