8

私がやろうとしていることの正確な用語はわかりません。に格納された8x8ブロックがあり、各バイトは1行を格納します。終了したら、各バイトに1つの列を格納します。bits8 bytes

たとえば、私が終了したとき：

Byte0out = Byte0inBit0 + Bit0inByte1 + Bit0inByte2 + Bit0inByte3 + ...
Byte1out = Bit1inByte0 + Bit1inByte1 + Bit1inByte2 + Bit1inByte3 + ...

What is the easiest way to do this in C which performs well? This will run on a dsPIC microcontroller

4

7 に答える 7

16

このコードは "Hacker's Delight" から直接引用したものです- Figure 7-2 Transpose an 8x8-bit matrix , 私はそれを信用しません:

void transpose8(unsigned char A[8], int m, int n, 
                unsigned char B[8]) {
   unsigned x, y, t; 

   // Load the array and pack it into x and y. 

   x = (A[0]<<24)   | (A[m]<<16)   | (A[2*m]<<8) | A[3*m]; 
   y = (A[4*m]<<24) | (A[5*m]<<16) | (A[6*m]<<8) | A[7*m]; 

   t = (x ^ (x >> 7)) & 0x00AA00AA;  x = x ^ t ^ (t << 7); 
   t = (y ^ (y >> 7)) & 0x00AA00AA;  y = y ^ t ^ (t << 7); 

   t = (x ^ (x >>14)) & 0x0000CCCC;  x = x ^ t ^ (t <<14); 
   t = (y ^ (y >>14)) & 0x0000CCCC;  y = y ^ t ^ (t <<14); 

   t = (x & 0xF0F0F0F0) | ((y >> 4) & 0x0F0F0F0F); 
   y = ((x << 4) & 0xF0F0F0F0) | (y & 0x0F0F0F0F); 
   x = t; 

   B[0]=x>>24;    B[n]=x>>16;    B[2*n]=x>>8;  B[3*n]=x; 
   B[4*n]=y>>24;  B[5*n]=y>>16;  B[6*n]=y>>8;  B[7*n]=y; 
}

これが必要な方向に回転するかどうかは確認しませんでした。そうでない場合は、コードを調整する必要があるかもしれません。

intまた、データ型とサイズに注意しunsigned (int)てください。プラットフォームでは 32 ビットではない可能性があります。

ところで、この本 (Hacker's Delight) は、あなたが行っている種類の仕事には欠かせないと思います...チェックしてみてください。

于 2011-08-03T19:44:38.520 に答える
5

最も簡単な解決策を探している場合：

/* not tested, not even compiled */

char bytes_in[8];
char bytes_out[8];

/* please fill bytes_in[] here with some pixel-crap */

memset(bytes_out, 0, 8);
for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 8; j++) {
        bytes_out[i] = (bytes_out[i] << 1) | ((bytes_in[j] >> (7 - i)) & 0x01);
    }
}

最速のソリューションをお探しの場合:

SSE2 を利用して、アセンブリ内のビット マトリックスを転置する方法。

于 2011-08-03T17:51:19.800 に答える
3

これは、ビットプレーンを使用するディスプレイで使用される、いわゆる「チャンキーから平面へ」ルーチンによく似ています。次のリンクでは、コードに MC68K アセンブラーを使用していますが、問題の概要をわかりやすく説明しています (質問を正しく理解していると仮定します)。

http://membres.multimania.fr/amycoders/sources/c2ptut.html

于 2011-08-03T17:39:28.343 に答える
3

Lisp プロトタイプ:

(declaim (optimize (speed 3) (safety 0)))
(defun bit-transpose (a)
  (declare (type (simple-array unsigned-byte 1) a))
  (let ((b (make-array 8 :element-type '(unsigned-byte 8))))
    (dotimes (j 8)
      (dotimes (i 8)
    (setf (ldb (byte 1 i) (aref b j))
          (ldb (byte 1 j) (aref a i)))))
    b))

これは、コードを実行する方法です。

#+nil
(bit-transpose (make-array 8 :element-type 'unsigned-byte
               :initial-contents '(1 2 3 4 5 6 7 8)))
;; => #(85 102 120 128 0 0 0 0)

ときどきコードを逆アセンブルして、安全機能への不要な呼び出しがないことを確認します。 

#+nil
(disassemble #'bit-transpose)

これはベンチマークです。(バイナリ) HDTV 画像を処理するのに十分な頻度で関数を実行します。

#+nil
(time 
 (let ((a (make-array 8 :element-type 'unsigned-byte
              :initial-contents '(1 2 3 4 5 6 7 8)))
       (b (make-array 8 :element-type 'unsigned-byte
              :initial-contents '(1 2 3 4 5 6 7 8))))
   (dotimes (i (* (/ 1920 8) (/ 1080 8)))
     (bit-transpose a))))

それは51ミリ秒しかかかりませんでした。関数は常に新しい 8 バイト配列を割り当てるため、かなり多くのことを考えていることに注意してください。C での実装は、もっと微調整できると確信しています。

Evaluation took:
  0.051 seconds of real time
  0.052004 seconds of total run time (0.052004 user, 0.000000 system)
  101.96% CPU
  122,179,503 processor cycles
  1,048,576 bytes consed

さらにいくつかのテストケースを次に示します。

#+nil
(loop for j below 12 collect
  (let ((l (loop for i below 8 collect (random 255))))
    (list l (bit-transpose (make-array 8 :element-type 'unsigned-byte
                :initial-contents l)))))
;; => (((111 97 195 202 47 124 113 164) #(87 29 177 57 96 243 111 140))
;;     ((180 192 70 173 167 41 30 127) #(184 212 221 232 193 185 134 27))
;;     ((244 86 149 57 191 65 129 178) #(124 146 23 24 159 153 35 213))
;;     ((227 244 139 35 38 65 214 64) #(45 93 82 4 66 27 227 71))
;;     ((207 62 236 89 50 64 157 120) #(73 19 71 207 218 150 173 69))
;;     ((89 211 149 140 233 72 193 192) #(87 2 12 57 7 16 243 222))
;;     ((97 144 19 13 135 198 238 33) #(157 116 120 72 6 193 97 114))
;;     ((145 119 3 85 41 202 79 134) #(95 230 202 112 11 18 106 161))
;;     ((42 153 67 166 175 190 114 21) #(150 125 184 51 226 121 68 58))
;;     ((58 232 38 210 137 254 19 112) #(80 109 36 51 233 167 170 58))
;;     ((27 245 1 197 208 221 21 101) #(239 1 234 33 115 130 186 58))
;;     ((66 204 110 232 46 67 37 34) #(96 181 86 30 0 220 47 10)))

今、私は自分のコードが Andrejs Cainikovs の C ソリューションとどのように比較されるかを本当に知りたいです (編集: 私はそれが間違っていると思います):

#include <string.h>

unsigned char bytes_in[8]={1,2,3,4,5,6,7,8};
unsigned char bytes_out[8];

/* please fill bytes_in[] here with some pixel-crap */
void bit_transpose(){
  memset(bytes_out, 0, 8);
  int i,j;
  for(i = 0; i < 8; i++)
    for(j = 0; j < 8; j++) 
      bytes_out[i] = (bytes_out[i] << 1) | ((bytes_in[j] >> (7 - i)) & 0x01);
}

int
main()
{
  int j,i;
  for(j=0;j<100;j++)
    for(i=0;i<(1920/8*1080/8);i++)
      bit_transpose();
  return 0;
}

そしてそれをベンチマークする：

wg@hp:~/0803/so$ gcc -O3 trans.c
wg@hp:~/0803/so$ time ./a.out 

real    0m0.249s
user    0m0.232s
sys     0m0.000s

HDTV 画像の各ループには 2.5 ミリ秒かかります。これは、最適化されていない Lisp よりもかなり高速です。

残念ながら、C コードでは、私の Lisp と同じ結果が得られません。

#include <stdio.h>
int
main()
{
  int j,i;
  bit_transpose();
  for(i=0;i<8;i++)
    printf("%d ",(int)bytes_out[i]);
  return 0;
}
wg@hp:~/0803/so$ ./a.out 
0 0 0 0 1 30 102 170
于 2011-08-03T17:44:21.480 に答える
1

あなたは本当にGCCベクトルベクトルサポートのような何かでSIMD命令でこのようなことをしたい: http://ds9a.nl/gcc-simd/example.html

于 2011-08-03T17:40:13.397 に答える
1

最適化されたソリューションが必要な場合は、x86 で SSE 拡張機能を使用します。これらの SIMD オペコードを 4 つ使用する必要があります。MOVQ - 8 バイトを移動 PSLLW - パックされた左シフト論理ワード PMOVMSKB - パックされた移動マスク バイト および 2 つの通常の x86 オペコード LEA - 実効アドレスをロード MOV - 移動

byte[] m = byte[8]; //input
byte[] o = byte[8]; //output
LEA ecx, [o]
// ecx = the address of the output array/matrix
MOVQ xmm0, [m]
// xmm0 = 0|0|0|0|0|0|0|0|m[7]|m[6]|m[5]|m[4]|m[3]|m[2]|m[1]|m[0]
PMOVMSKB eax, xmm0
// eax = m[7][7]...m[0][7] the high bit of each byte
MOV [ecx+7], al
// o[7] is now the last column
PSLLW xmm0, 1
// shift 1 bit to the left
PMOVMSKB eax, xmm0
MOV [ecx+6], al
PSLLW xmm0, 1
PMOVMSKB eax, xmm0
MOV [ecx+5], al
PSLLW xmm0, 1
PMOVMSKB eax, xmm0
MOV [ecx+4], al
PSLLW xmm0, 1
PMOVMSKB eax, xmm0
MOV [ecx+3], al
PSLLW xmm0, 1
PMOVMSKB eax, xmm0
MOV [ecx+2], al
PSLLW xmm0, 1
PMOVMSKB eax, xmm0
MOV [ecx+1], al
PSLLW xmm0, 1
PMOVMSKB eax, xmm0
MOV [ecx], al

スタックされた for... ループ ソリューションの 64 回の繰り返しとは対照的に、25 個の x86 オペコード/命令。申し訳ありませんが、表記は c/c++ コンパイラが受け入れる ATT スタイルの構文ではありません。

于 2011-08-03T19:21:38.347 に答える