C でバイト要素配列を持つ 128 ビット線形フィードバック シフト レジスタを実装する方法

Question

次のような配列があります。

unsigned char A[16]

この配列を使用して 128 ビットのハードウェア レジスタを表します。この長いレジスタを使用して線形フィードバック シフト レジスタ (LFSR、フィボナッチ実装) を実装したいと思います。この LFSR のフィードバック xnor ゲートに接続する多項式 (またはタップ) は [128, 29, 27, 2, 1] です。

16 ビット LFSR ([16、14、13、11] のタップ) の実装は、次から取得できます。 ウィキペディア 以下のように。

  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] は A の lsb にシフトする必要があります1. 。この移行を行うための最小限のコーディングは何でしょうか?ありがとう！

Answer 1

シフトインするビットを計算するために、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 unsigned char の代わりに (プロセッサのワード サイズに応じて) 使用されますが、原理は同じです。