The Neverhood, хеш алгоритм Опции

[-=CHE@TER=-]

Пишу сейчас страничку для сайта (ctpax-cheater) для игры The Neverhood.

В игре во всю используется вот такая хеш-функция (я её немножно переписал под свои нужды):

CODE

// The Neverhood hash routine
Const chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

Function StrHash(S: String): Longword;
Var I, C, K: Longword;
Begin
  result:=0;
  C:=0;
  For I:=1 To Length(S) Do
  Begin
    S[I]:=UpCase(S[I]);
    K:=Pos(S[I], chars);
    If K <> 0 Then
    Begin
      If K <= 10 Then // Digits
        C:=C + (Ord(S[I]) + $16 - $40)
      Else
        C:=C + (Ord(S[I]) - $40);
      If C >= $20 Then C:=C - $20;
      result:=result xor (1 ShL C);
    End;
  End;
End;

Т.е. игнорируется всё, что не цифры и английские буквы, затем от получившегося считается хеш.
В demo-версии эта функция находится в sub_425C10.
Ею зашифрованы как коды, так и имена файлов в .BLB архивах.

В Интернете нагуглил только два кода (там ещё один есть, но он неработающий - что-то забыли):
fastforward - увеличивает скорость игры в два раза (хеш $843070C0)
happybirthdayklaymen - работает только на первом экране - перекидывает игрока на второй (*улыбается*) (хеш $188B2105)
После набора кода нужно нажать ENTER. Перед набором, кстати, тоже неплохо будет - вдруг уже что-то нажимали (ENTER отправляет код на обработку и чистит буфер ввода для кода).

Однако, если поглядеть под отладчиком даже demo-версию - кодов там дохрена и больше (вернее хешей). Плюс они раскиданы по нескольким разным функциям (как два кода выше), что затрудняет работу с ними.

Есть, например, хеш $10410127 - он сохраняет текущий кадр игры в c:\NevShot.bmp (даже во время проигрывания smack-видео!). Но вот какой код ему соответствует - хрен знает.

Есть два способа посмотреть все коды:
1) Заменить хеши на известные значения.
2) Brute-force (полный перебор).

1-ый способ очень неудобен, потому что:
а) Все хеши кодов внутри какого-то case/switch и они должны быть заменены на соответствующие (т.е. отсортированы по возрастанию, а не как попало).
б) Они разбросаны по разным функциям, так что бегать между ними очень неудобно.
в) Этот способ неудобен ещё и тем, что его нельзя предложить всем имеющим игру - им придётся её как минимум патчить.

Перебор же очень трудоёмкий, даже если выбросить оттуда UpCase (т.е. заведомо перебирать только заглавные буквы и цифры) и оптимизировать.
Я заметил, что в этом алгоритме на каждом шаге зажигается или гасится (если уже был зажжён) 1 бит в хеше. Т.е. для упомянутого хеша $10410127 слово-пароль должно состоять как минимум из 8 знаков (с учётом того, что ни один бит не выключался), так как в этом числе 8 не нулевых бит.

Собственно, вопрос: кто-нибудь может предложить простой и быстрый алгоритм для перебора?

Может быть я чего-то не вижу и здесь можно гораздо быстрее и проще хеш подобрать.
Мне не обязательно получить именно тот код, который задумывался создателями - какая-нибудь последовательность типа "bsb99dc" - тоже сойдёт.

[-=CHE@TER=-]

Вчера обновил (так, мелкое обновление перед перемещением на другую площадку) патч для The Neverhood - со мной связался один товарищ и помог его оттестировать, так что теперь в него включено и исправление версии от "Фаргус". Если кто забыл или не в курсе, то эта версия падала при вызове меню. Существующие исправления этой проблемы заключались в тупом копировании и замены файлов NHC.EXE и HD.BLB от версии "Рисёча", что исправлением назвать можно было с натяжкой.

Как оказалось, в "Фаргус" криво закодировали две картинки: одна с надписью "опции" в главном меню, а вторая с надписями "загрузка отмена" для меню "Загрузка игры". Обе картинки были нормальные, но в хвосте, почему-то, содержали мусор из-за которого после декодирования изображение получалось больше чем нужно, происходило переполнение буфера и картинка начинала уничтожать память игры. Таким образом игра падала либо при вызове меню, либо при входе в подменю загрузки игры. Я поглядел картинки (они кроме PKWARE implode были сжаты неким алгоритмом RLE) и просто занулил один байт в каждой остановив распаковку после того как надпись полностью распаковалась, но за пределы отведённого ей буфера картинка ещё не вышла. Потом упаковал обратно (ещё то развлечение было - см. исходные коды, файл resource/packinfo.txt). Одна картинка упаковалась на пару байт меньше, а вот другая больше, так что пришлось мусорные байты в хвосте занулять, пока она не стала в упакованном виде такая же как и оригинальная.
После этого я заменил их в HD.BLB и всё стало нормально (т.к. в упаковонном виде они столько же занимают или меньше и распакованного буфера под них хватает - специально таблицу размещения файлов в архиве проверял).

А вот теперь интересное - встал вопрос как делать патч? Дело в том, что различия в упакованных данных были слишком большие, так что пришлось полностью хранить патченные файлы для замены.

Если кто помнит, то у меня все патчи можно как поставить, так и откатить. Если я включу в ресурсы патча только исправленные картинки, то мне где-то нужно будет сохранять оригинальные. Если и оригинальные и исправленные... то меня жаба давить начинает место зря тратить (около 8 Кб в сумме, но теме не менее). И тут меня осенило! Я выравнял файлы, чтобы они были одного размера - ко второму просто в хвост дописал байты из хвоста его оригинала, а затем поXORил оба патченных файла на их оригинальные версии. Получились этакие файлы-маски. Теперь всё что мне осталось - это записать CRC32 оригинального файла и изменённого.
После чего патч выглядел так:

Если ((CRC32_файла_в_архиве = CRC32_оригинального_файла) И (Install = Истина)) // ставим патч
ИЛИ ((CRC32_файла_в_архиве = CRC32_патченного_файла) И (Install = Ложь)) // откатываем патч
Тогда
for i:=1 to file_size do
file_in_archive[i]:=file_in_archive[i] xor xored_data[i];

file_in_archive - это как раз файл, который мы прочитали из архива, а xored_data - это файл-маска, полученный как "байты_оригинального_файла XOR байты_патченного_файла".

Как мы помним, операция XOR чем удобна, что возвращает всё взад-назад.
Рассмотрим на примере:

$12 (original) xor $34 (patched) => $26 (xored)
Но тогда:
$12 (original) xor $26 (xored) => $34 (patched)
$34 (patched) xor $26 (xored) => $12 (original)

Т.е. благодаря созданной маске мы можем одной и той же операцией (XOR) как ставить патч, так и откатывать! И всё что нам нужно, так это хранить две CRC32 (жалкие 4*2 = 8 байт) для оригинального и патченного файла (для каждого файла, которые мы будем заменять), чтобы знать когда какой ставить, а также случайно не поставить патч на другую версию игры.

Иными словами, я в размер одного файла, впихнул сразу два: оригинальный и патченный!