Бит-взлом и модуляция

При чтении: http://graphics.stanford.edu/~seander/bithacks.html#ReverseByteWith64BitsDiv

Я пришел к фразе:

Последний шаг, который включает в себя модульное деление на 2 ^ 10 - 1, имеет эффект объединения каждого набора из 10 бит (с позиций 0-9, 10-19, 20-29,...) в 64-битном значении.

(речь идет об изменении битов в числе)...

поэтому я сделал несколько расчетов:

reverted = (input * 0x0202020202ULL & 0x010884422010ULL) % 1023;

b = 74          :                                 01001010
b 
 * 0x0202020202 :       1000000010000000100000001000000010
   = 9494949494 :01001010010010100100101001001010010010100
  & 10884422010 :10000100010000100010000100010000000010000 
    = 84000010  :         10000100000000000000000000010000
  % 1023        :                               1111111111
    = 82        :                                 01010010

Теперь единственная часть, которая несколько неясна, является частью, где большое число по модулю 1023 (2 ^ 10 - 1) упаковывает и дает мне перевернутые биты... Я не нашел хорошего документа о связи между бит операций и операции по модулю (около x % 2^n == x & (2^n - 1))), поэтому, возможно, если кто-то осветит это, это будет очень плодотворно.

Ответы

Ответ 1

Операция modulo не дает вам перевернутые биты как таковые, это просто операция биннинга.

Первая строка: расширение слова

b * 0x0202020202 = 01001010 01001010 01001010 01001010 01001010 0 p >

Операция умножения имеет свойство convolution, что означает, что она несколько раз реплицирует входную переменную (здесь 5, так как это 8-битное слово).

Первая строка: реверсивные биты

Это самая сложная часть взлома. Вы должны помнить, что мы работаем над 8-битным словом: b = abcdefgh, где [a-h] - 1 или 0.

b  * 0x0202020202 = abcdefghabcdefghabcdefghabcdefghabcdefgha
    & 10884422010 = a0000f000b0000g000c0000h000d00000000e0000

Последняя строка: слово binning

Modulo обладает своеобразным свойством: 10 ≡ 1 (mod 9) so 100 ≡ 10*10 ≡ 10*1 (mod 9) ≡ 1 (mod 9).

В общем случае для базы b, b ≡ 1 (mod b - 1) так для всего числа a ≡ sum(a_k*b^k) ≡ sum (a_k) (mod b - 1).

В примере base = 1024 (10 бит), поэтому

b ≡ a0000f000b0000g000c0000h000d00000000e0000 
  ≡ a*base^4 + 0000f000b0*base^3 + 000g000c00*base^2 + 00h000d000*base +00000e0000 
  ≡ a + 0000f000b0 + 000g000c00 + 00h000d000 + 00000e0000 (mod b - 1)
  ≡  000000000a
   + 0000f000b0 
   + 000g000c00 
   + 00h000d000 
   + 00000e0000 (mod b - 1)
 ≡   00hgfedcba (mod b - 1) since there is no carry (no overlap)