Как использовать 64-битное целое число без знака в Python, учитывая переполнение C? - PullRequest
Новая
       44

Как использовать 64-битное целое число без знака в Python, учитывая переполнение C?

3 голосов
/ 08 марта 2019

Я пытаюсь реализовать хэш djb2 в Python.

Вот оно в C: 

/* djb2 hash http://www.cse.yorku.ca/~oz/hash.html */

uint64_t djb2(size_t len, char const str[len]) {
    uint64_t hash = 5381;
    uint8_t c;
    for(size_t i = 0; i < len; i++) {
        c = str[i];
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    return hash;
}

А вот моя попытка в Python: 

from ctypes import c_uint64, c_byte, cast, POINTER

def djb2(string: str) -> c_uint64:
    hash = c_uint64(5381)
    raw_bytes = cast(string, POINTER(c_byte * len(string)))[0]
    for i in range(0, len(raw_bytes)):
        hash = c_uint64((((((hash.value << 5) & 0xffffffffffffffff) + hash.value) & 0xffffffffffffffff) + raw_bytes[i]) & 0xffffffffffffffff) # hash * 33 + c
    return hash

Тем не менее, я получаю разные результаты между этими двумя, что я подозреваю, из-за разного поведения переполнения или других математических различий.

Причиной маскировки в версии Python была попытка вызвать переполнение (на основе этого ответа ).

1 Ответ

2 голосов
/ 08 марта 2019

Вы можете очень легко реализовать алгоритм, выполняемый кодом C, на чистом Python, без необходимости каких-либо вещей ctypes. Просто сделайте все это с обычными целыми числами Python и возьмите модуль в конце (старшие биты не будут влиять на младшие для операций, которые вы делаете): 

def djb2(string: bytes) -> int:  # note, use a bytestring for this, not a Unicode string!
    h = 5381
    for c in string:    # iterating over the bytestring directly gives integer values
        h = h * 33 + c  # use the computation from the C comments, but consider ^ instead of +
    return h % 2**64    # note you may actually want % 2**32, as this hash is often 32-bit

Как я прокомментировал в коде, поскольку это операция, определенная для строк байтов, вы должны использовать экземпляр bytes в качестве аргумента. Обратите внимание, что существует множество различных реализаций этого алгоритма. Некоторые используют ^ (побитовый xor) вместо + на шаге, где вы обновляете значение хеша, и часто определяется использование unsigned long, которое обычно было 32-битным вместо явно 64-битного целого числа C версия в вашем вопросе использует.

...