Как реализовать 128-битный регистр сдвига с линейной обратной связью с массивом байтовых элементов в C

Question

У меня есть массив следующим образом,

unsigned char A[16]

Я использую этот массив для представления 128-битного аппаратного регистра. Теперь я хочу реализовать регистр сдвига с линейной обратной связью (LFSR, реализация Фибоначчи), используя этот длинный регистр. Полиномы (или ответвления), которые соединяются с затвором xnor обратной связи этого LFSR, [128, 29, 27, 2, 1].

Реализация 16-битного LFSR (отводы в [16, 14, 13, 11]) может быть получена из Wikipedia следующим образом.

  unsigned short lfsr = 0xACE1u;
  unsigned bit;

  unsigned rand()
  {
    bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
    return lfsr =  (lfsr >> 1) | (bit << 15);
  }

В моем случае, однако, мне нужно сдвинуть биты с одного байтового элемента на другой, например, msb или A [0] должны быть сдвинуты к lsb A 1 . Какое минимальное кодирование для этого сдвига? Спасибо!

Answer 1

Чтобы вычислить сдвигаемый бит, вам не нужно каждый раз сдвигать весь массив, поскольку вас интересует только один бит (обратите внимание на & 1 в конце строки bit = из Википедии).

Правильные суммы смены:

128 - 128 =   0   => byte  0 bit 0
128 -  29 =  99   => byte 12 bit 3
128 -  27 = 101   => byte 12 bit 5
128 -   2 = 126   => byte 15 bit 6
128 -   1 = 127   => byte 15 bit 7

Итак,

bit = ((A[0] >> 0) 
    ^  (A[12] >> 3) 
    ^  (A[12] >> 5) 
    ^  (A[15] >> 6) 
    ^  (A[15) >> 7)) & 1;

Теперь вам действительно нужно сдвинуть бит:

A[0] = (A[0] >> 1) | (A[1] << 7);
A[1] = (A[1] >> 1) | (A[2] << 7);
// and so on, until
A[14] = (A[14] >> 1) | (A[15] << 7);
A[15] = (A[15] >> 1) | (bit << 7);

Вы можете сделать это немного более эффективным, используя uint32_t или uint64_t вместо знаков без знака (в зависимости от размера слова вашего процессора), но принцип тот же.