Почему моя текущая контрольная сумма adler32 не работает? (по модулю арифметики)

Question

Я реализую в версии rolling версию adler32 checksum.

Это answer было полезно дважды проверить мои математические данные. Однако я стараюсь правильно ее внедрить в golang.

Я написал следующий код:

func roll(adler, n, leave, enter uint32) uint32 { 
    a := adler & 0xffff 
    b := adler >> 16 

    a = (a + enter - leave) % MOD 
    b = (b - n*leave - 1 + a) % MOD 
    return b<<16 | a 
} 

тестировал его на различные входы и она работала хорошо, пока я не решил запустить его на случайных данных. Вот sample, где он не работает (я нашел несколько из них).

Что озадачивает меня в том, что тот же самый код в питоне отлично работает на этих входах:

def roll(adler, n, leave, enter): 
    a = adler & 0xffff 
    b = adler >> 16 

    a = (a + enter - leave) % MOD 
    b = (b - n*leave - 1 + a) % MOD 
    return b<<16 | a 

Для хорошей меры, я в том числе proof, что это работает в питоне. Обратите внимание, что контрольная сумма python соответствует некалиберной версии контрольной суммы go (и эта часть находится непосредственно из основных библиотек go).

Я изучил свои результаты по всем другим проблемным образцам и обнаружил, что я никогда не ошибаюсь в младших значащих бит контрольной суммы (бит «а»). Кроме того, ошибка постоянно одинакова, равна 0xe10000. Я подозреваю, что причиной того, как go обрабатывает по модулю операции с целыми числами uint32, является причиной этого.

Что происходит и как я могу исправить свой код?

Answer 1

Целые в Python вошедшие. Вы указали, что все целые числа в версии golang не имеют знака. В этом разница.

Когда беззнаковое число вычитается из меньшего числа без знака, вы получаете огромное количество без знака, которое дает разный остаток при делении, чем небольшая отрицательная разница. Когда вы завертываете, вы фактически добавляете 2 . 2 mod 65521 - 225, или 0xe1, поэтому вы видите эту разницу в b. Скорее всего, это будет связано с вычислением b, но это может произойти и для a, если a окажется очень маленьким на этом шаге.

В комментарии @samgak вам также нужно беспокоиться об определении оператора% на разных языках для подписанных значений. Таким образом, решение, которое работает в разных соглашениях, должно было бы сделать значения положительными, добавив как можно больше MOD s, прежде чем делать % MOD. Для a просто добавьте MOD. Для b, добавить (1 + n * leave/MOD) * MOD.

Позаботьтесь о том, чтобы промежуточные значения не переполнялись. Код в go может дать ошибочные результаты, если n*leave достаточно большой, чтобы обернуть используемый целочисленный тип.

Answer 2

Я не знаю, идти, но здесь есть некоторые возможности:

b := adler >> 16 change to b := (adler >> 16) & 0xffff 

b = (b - n*leave - 1 + a) % MOD ... what happens if expression in() is negative? 

return b<<16 | a ... check operator precedence; (b<<16)|a or b<<(16|a) ? 

32-bit machine or 64-bit?