Как перенести алгоритм вычисления хеша на lua?

Question

[Влад Зайцев]

Есть алгоритм на Си:

extern uint32 HashRot13(const uint8 * str, int length)
{
    uint32 hash = 0;
    int i;
    for(i = 0; i < length; ++i, str++)
    {
        hash += (uint32)(*str);
        hash -= (hash << 13) | (hash >> 19);
    }
    return hash;
}

Как перенести его на Lua? Или хотя бы расскажите, что он делает.

Answer 1

[Влад Зайцев]

function HashRot13(bytes)
hash = 0
for i = 1, #bytes do
hash = hash + bytes[i]
hash = bit.band(hash - bit.rol(hash, 13), 0xFFFFFFFF)
end
return bit.bswap(hash)
end

Answer 2

[Владимир Мартьянов]

Изучить C, изучить Lua. Потом взять и перевести в одного языка на другой.

Comments

[Влад Зайцев]

Хороший, годный ответ, теперь мне все стало понятно.

[Владимир Мартьянов]

Влад Зайцев: Старался: полностью отвечает на поставленный вопрос "как?".

Answer 3

[Everything_is_not_so_bad]

hash += (uint32)(*str);
берёт uint32 число по текущему указателю *str и аккумулирует его в переменной hash.

Битовые операторы
hash << 13
выполняет сдвиг влево на 13 бит (умножение hash на 2^13)

hash >> 19
выполняет сдвиг вправо на 19 бит (деление hash на 2^19)

(hash << 13) | (hash >> 19)
Побитовое ИЛИ от результата сдвигов выше

hash -= (hash << 13) | (hash >> 19);
обновление с вычитанием из аккумулированного значения hash

Comments

[Влад Зайцев]

Это да, более-менее теперь понятно. А сколько раз это делается? По количеству разрядов в str? А что делает "str++" в "for(i = 0; i < length; ++i, str++)"?

[Everything_is_not_so_bad]

Влад Зайцев: цикл выполняется пока указатель str не достигнет конца строки. Берётся каждый байт строки.

[Everything_is_not_so_bad]

str++
инкремент указателя, здесь это то же самое, что и
str = str +1

[Влад Зайцев]

Роман Мирр: про инкремент понимаю. Не понимаю, что это дает. Куда берется каждый байт? Все, что происходит внутри цикла(два сдвига, или, вычитание) — это делается с каждым байтом?

[Everything_is_not_so_bad]

Здесь (uint32) - это приведение к типу uint32, т.е. от байта к целому 32-разрядному без знака.
Операция в цикле над каждым байтом строки.

[abcd0x00]

Битовые операторы

Во-первых, не операторы, а операции. Оператор в языке C означает выражение, оканчивающееся точкой с запятой (которая является его частью).

А во-вторых, там ошибка на сайте:

В том случае, если вправо сдвигается отрицательное число, слева появляются единицы (поддерживается знаковый бит).

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

Соответственно, не стоит изучать язык по сайту, где автор не читал стандарта и путает некоторые понятия.

Answer 4

[bromzh]

Можно взять и переписать код с C на Lua. Беда в том, что битовые операции в луа из коробки фиговые. Но есть эта библиотека (правда она вроде только для luajit).

Второй и более лучший вариант - использовать сишную библиотеку. Луа очень хорошо интегрируется с сишкой. Если берёшь обычную реализацию - можно написать сишный модуль для луа. Если luajit - то там FFI из коробки, достаточно дёргать сишные функции.

Answer 5

[abcd0x00]

Или хотя бы расскажите, что он делает.

1. Он добавляет 8-битное значение к 32-битному значению.
2. Затем берёт у этого 32-битного значения 13 бит слева и переставляет их направо.
3. Потом из исходного 32-битного значения вычитается полученное 32-битное значение.
4. Потом всё повторяется, пока есть 8-битные значения.

Если бы ты запустил это в дебаггере, то увидел бы по шагам, что происходит в цикле.