バイト配列を 12 ビットでシフトする方法

ポインターをどうぞ！

このコードは、各バイトの 12 ビットを先読みし、適切なビットを前方にコピーすることによって機能します。 12 ビットは、次のバイトの下半分 (ニブル) であり、2 バイトの上半分は離れています。

unsigned char length = 10;
unsigned char data[10] = {0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0A,0xBC};
unsigned char *shift = data;
while (shift < data+(length-2)) {
    *shift = (*(shift+1)&0x0F)<<4 | (*(shift+2)&0xF0)>>4;
    shift++;
}
*(data+length-2) = (*(data+length-1)&0x0F)<<4;
*(data+length-1) = 0x00;

まあ、通常のシフト操作はまさにそれを行い（オーバーフローと呼ばれます）、余分なビットを右または左に落とすだけだと思います。必要に応じて簡単に持ち運ぶことができます。シフトを開始する前に 12 ビットを保存するだけです。オーバーフローしたビットを一番下に戻すために、循環シフトが必要な場合がありますか?たぶん、配列を再割り当てして大きくしたいですか？呼び出し元にオーバーフローを返しますか?ゼロ以外のデータがオーバーフローした場合、ブール値を返しますか?キャリーが何を意味するかを定義する必要があります.

unsigned char overflow[2];
*overflow = (*data&0xF0)>>4;
*(overflow+1) = (*data&0x0F)<<4 | (*(data+1)&0xF0)>>4;
while (shift < data+(length-2)) {
    /* normal shifting */
}  
/* now would be the time to copy it back if you want to carry it somewhere */
*(data+length-2) = (*(data+length-1)&0x0F)<<4 | (*(overflow)&0x0F);
*(data+length-1) = *(overflow+1);  

/* You could return a 16-bit carry int, 
 * but endian-ness makes that look weird 
 * if you care about the physical layout */
unsigned short carry = *(overflow+1)<<8 | *overflow;

これが私の解決策ですが、さらに重要なのは、問題を解決するための私のアプローチです。

私は

で問題に取り組みました

メモリセルを描画し、宛先からソースへの矢印を描画する
上の図を示す表を作成しました。
表の各行に相対バイトアドレスでラベルを付ける

これは私にパターンを示しました：

let iL a[i] の下位ニブル (半バイト)
let iH a[i] の高いニブルになる
iH = (i+1)L
iL = (i+2)H

このパターンはすべてのバイトに適用されます。

C に翻訳すると、これは次のことを意味します:

a[i] = (iH << 4) OR iL
a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4)

ここで、さらに 3 つの観察を行います。

割り当ては左から右に行うため、一時変数に値を保存する必要はありません。
テールには特別なケースがあります:すべて 12 bits 最後はゼロになります。
配列を超えて未定義のメモリを読み取らないようにする必要があります。 a[i+2] 以上を読み取ったことがないため、これは最後の 2 バイトにのみ影響します

だから、

N-2 bytes をループして一般的なケースを処理する上記の一般的な計算を実行する
iH = (i+1)L を設定して、最後のバイトの次のバイトを処理します
最後のバイトを 0 に設定して処理します

指定された a 長さ N 、取得:

for (i = 0; i < N - 2; ++i) {
    a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4);
}
a[N-2] = (a[N-1) & 0x0f) << 4;
a[N-1] = 0;

これで、配列は 12 bits だけ左にシフトされます。 . N bits のシフトに簡単に一般化できます、 M があることに注意してください M = number of bits modulo 8 の割り当てステートメント

一部のマシンでは、ポインターに変換することでループをより効率的にすることができます

for (p = a, p2=a+N-2; p != p2; ++p) {
    *p = ((*(p+1) & 0x0f) << 4) | (((*(p+2) & 0xf0) >> 4);
}

CPU がサポートする最大の整数データ型を使用します。

(私はちょうどこれを入力したので、誰かがコードをレビューする良い機会になるでしょう。特に、ビットいじりは間違いやすいことで知られているためです。)

N をシフトする最良の方法にしましょう 8 ビット整数の配列内のビット。

N            - Total number of bits to shift
F = (N / 8) - Full 8 bit integers shifted
R = (N % 8) - Remaining bits that need to be shifted

ここから、このデータを利用して配列内のintを移動するための最適な方法を見つける必要があると思います。一般的なアルゴリズムは、配列の右側から開始して各整数 F を移動することにより、完全な整数シフトを適用することです。インデックス。新しく空いたスペースをゼロで埋めます。最後に R を実行します再び右から開始して、すべてのインデックスのビットシフト。

0xBCをシフトする場合 R までビット単位の AND を実行してオーバーフローを計算し、ビットシフト演算子を使用してシフトを計算できます。

// 0xAB shifted 4 bits is:
(0xAB & 0x0F) >> 4   // is the overflow      (0x0A)
0xAB << 4            // is the shifted value (0xB0)

4 ビットは単純なマスクであることに注意してください:0x0F または 0b00001111 です。これは簡単に計算でき、動的に作成できます。また、単純な静的ルックアップテーブルを使用することもできます。

それが十分に一般的であることを願っています。私は C/C++ がまったく得意ではないので、誰かが私の構文をクリーンアップするか、より具体的に説明してくれるかもしれません.

おまけ:C を巧みに扱えば、複数の配列インデックスを単一の 16、32、または 64 ビット整数に変換してシフトを実行できる場合があります。しかし、それはおそらくあまり移植性が高くないため、これには反対することをお勧めします。可能な最適化です。