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

Question

Мой клиент - программист на 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 

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

Answer 1

Проблема здесь в том, что Кассиопеяне unsigned int автоматически переворачивается, когда он идет мимо UINT_MAX, в то время как в Python int просто продолжает получать больше.

Самое простое решение просто исправить в конце:

return hash % (1 << 32) 

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

---

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

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

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

---

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

Answer 2

Маска значение хеш-функции с &:

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