Перевести алгоритм хеширования с C на Python

Мой клиент - программист на Python, и я создал для него бэкэнд C++, который включает генерацию и проверку лицензий. Для дополнительной безопасности интерфейс Python также выполнит проверку действительности лицензии.

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

Это упрощенный пример кода:

unsigned int HashString(const char* str) {
    unsigned int hash = 3151;
    while (*str != 0) {
        hash = (hash << 3) + (*str << 2) * 3;
        str++;
    }
    return hash;
}

Как это можно перевести на Python? Прямой перевод, очевидно, дает другой результат:

def hash_string(str):
    hash = 3151
    for c in str:
        hash = (hash << 3) + (ord(c) << 2) * 3
    return hash

Например:

hash_string("foo bar spam")  #  228667414299004
HashString("foo bar spam")   // 3355459964

Изменить: То же самое будет необходимо для PHP, так как интернет-магазин должен иметь возможность генерировать действительные лицензии тоже.

Источник

2 ответа

Решение

Проблема здесь в том, что С unsigned int автоматически переворачивается, когда он проходит UINT_MAX в то время как питон int просто становится больше

Самый простой способ исправить это просто исправить в конце:

return hash % (1 << 32)

Для очень больших струн может быть немного быстрее маскироваться после каждой операции, чтобы избежать попадания в огромные строки int значения, с которыми медленно работать. Но для небольших строк это, вероятно, будет медленнее, потому что стоимость звонка % 12 раз вместо 1 легко перевесят стоимость работы с 48-битным int.

У PHP может быть та же проблема или другая.

Целочисленный тип PHP по умолчанию - C long. На 64-битной платформе Unix это больше, чем unsigned int, так что вам придется использовать тот же трюк, что и на Python (либо % или же & в зависимости от того, что имеет больше смысла для вас.)

Но на 32-битной платформе Unix или в Windows этот размер равен unsigned int но подписано, что означает, что вам нужен другой трюк. Вы не можете на самом деле представлять, скажем, 4294967293 напрямую (попробуйте, и вы получите -3 вместо). Вы можете использовать GMP или же BCMathцелое число вместо типа по умолчанию (в этом случае он в основном такой же, как в Python), или вы можете просто написать собственный код для печати, сравнения и т. д., который будет обрабатывать это -3 как будто это было 4294967293,

Обратите внимание, что я просто предполагаю, что int составляет 32 бита, и long либо 32, либо 64, потому что это происходит на всех популярных сегодня платформах. Но стандарт С требует только int быть длиной не менее 16 бит и long быть не менее 32 бит и не короче int, Если вам нужно иметь дело с очень старыми платформами, где int может быть 16 бит (или 18!) или будущие платформы, где может быть 64 или более, вы должны корректировать свой код соответствующим образом.

Источник

Маскировать значение хеша &:

def hash_string(str, _width=2**32-1):
    hash = 3151
    for c in str:
        hash = ((hash << 3) + (ord(c) << 2) * 3)
    return hash & _width

Это вручную сокращает хэш до размера. Вам нужно ограничить результат только один раз; это не так, как будто эти старшие биты имеют значение для конечного результата.

Демо-версия:

>>> hash_string("foo bar spam")
3355459964
Источник
Другие вопросы по тегам