哪种mcu指令结构处理以下情况最快？

1万 · 2012-4-5 20:14

to: 13楼
把8个字节放在20H～27H中
MOV C, 20H.0
RRC A
MOV C, 21H.0
RRC A
......
这样更快, 程序空间也更短

只看该作者 · 2012-4-5 20:21

to: 13楼
把8个字节放在20H～27H中
MOV C, 20H.0
RRC A
MOV C, 21H.0
RRC A
......
这样更快, 程序空间也更短
airwill 发表于 2012-4-5 20:14

高低位对换，最简单的算法《Hackers Delight》这书里面也有

 

a = ((a << 4) & 0xf0) | ((a>> 4) & 0x0f); 

a = ((a << 2) & 0xcc) | ((a>> 2) & 0x33); 

a = ((a << 1) & 0xaa) | ((a>> 1) & 0x55);

只看该作者 · 2012-4-5 20:24

再上一个32位的位翻转让你们这群井底之蛙开开眼。

复制

 

unsigned rev(unsigned x) { 

x = (x & 0x55555555) << 1 | (x >> 1) & 0x55555555; 

x = (x & 0x33333333) << 2 | (x >> 2) & 0x33333333; 

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

x = (x << 24) | ((x & 0xFF00) << 8) | ((x >> 8) & 0xFF00) | (x >> 24); return x; 

}

1万 · 2012-4-5 20:27

改进的查表法：
把8×8变成4个4×4，然后查表再变回来？表的大小就可以接受了吧？

1万 · 2012-4-5 20:33

128K字节，对于51是太多了，对于STM32来说不算啥了。

1万 · 2012-4-5 20:36

实际也可以主频压算法，就是逐位算，老子主频高，（CPLD在一旁笑了）毕竟做显示你到底要处理多大数据不光是运算，扫描也很花资源的。DMA无敌。

只看该作者 · 2012-4-5 20:52

mark

只看该作者 · 2012-4-5 20:57

感觉像通信里面的交织，横写竖读，竖写横读:lol

只看该作者 · 2012-4-5 21:01

看了这么多2逼在这里不懂装懂，算了吧，我把书传上来吧。
楼猪要的转置矩阵和中间插入的位翻转都在第七章。

Hackers Delight [2002 - Henry S. Warren, Jr. - Pearson Education].pdf (3.64 MB)

只看该作者 · 2012-4-5 21:18

LZ 去那里面试了啊

1万 · 2012-4-5 22:15

19楼的分析挺长，做个记号有空时看看。
29楼的书有空也要拜读一下。

2万 · 2012-4-6 08:40

再上一个32位的位翻转让你们这群井底之蛙开开眼。

unsigned rev(unsigned x) {
x = (x & 0x55555555) > 1) & 0x55555555;
x = (x & 0x33333333) > 2) & 0x33333333;
x = (x & 0x0F0F0F0F) > 4) & 0x0F0F0F0F;
...
李富贵发表于 2012-4-5 20:24

典型的全家富贵

1万 · 2012-4-6 09:03

再上一个32位的位翻转让你们这群井底之蛙开开眼。

unsigned rev(unsigned x) {
x = (x & 0x55555555) > 1) & 0x55555555;
x = (x & 0x33333333) > 2) & 0x33333333;
x = (x & 0x0F0F0F0F) > 4) & 0x0F0F0F0F;
...
李富贵发表于 2012-4-5 20:24

"典型的井底之蛙"? 你最好编译成汇编码,再自己对比对比. 再来批评人家!
你虽然使用了 CM3 的 rev 指令, 但还是跳不过 128 次数据变换指令!

1万 · 2012-4-6 09:23

如果是处理字库的话，这种吃力不讨好的事，为什么非要单片机完成呢？可以考虑预先在计算机上把数据处理好再给单片机。

只看该作者 · 2012-4-6 09:50

19楼的算法很奇妙，但是也不难理解。我来推导一遍，类似的还有CRC计算时不用查表的快速计算方法
8个8bit的数据，可以放在2个32bit的数据中
行列的变化实质上就是这些位的变化。
现在x和y两个32位变量中有这些位

复制

x={

a7,a6,a5,a4,a3,a2,a1,a0

b7,b6,b5,b4,b3,b2,b1,b0

c7,c6,c5,c4,c3,c2,c1,c0

d7,d6,d5,d4,d3,d2,d1,d0

}



y={

e7,e6,e5,e4,e3,e2,e1,e0

f7,f6,f5,f4,f3,f2,f1,f0

g7,g6,g5,g4,g3,g2,g1,g0

h7,h6,h5,h4,h3,h2,h1,h0

}

要将他们转化成如下的形式

复制

x={

a7,b7,c7,d7,e7,f7,g7,h7

a6,b6,c6,d6,e6,f6,g6,h6

a5,b5,c5,d5,e5,f5,g5,h5

a4,b4,c4,d4,e4,f4,g4,h4

}



y={

a3,b3,c3,d3,e3,f3,g3,h3

a2,b2,c2,d2,e2,f2,g2,h2

a1,b1,c1,d1,e1,f1,g1,h1

a0,b0,c0,d0,e0,f0,g0,h0

}

可以看到转化后x中只有n7,n6,n5,n4部分，y中只有n3,n2,n1,n0的部分(n取a,b,c,d,e,f,g,h)
那么，我们可以用位运算，先把这些位的高低部分分离出来，分别放在x和y中
即
x1 = (x&0xf0f0f0f0) | ((y>>4)&0x0f0f0f0f)
y1 = ((x<<4)&0xf0f0f0f0) | (y&0x0f0f0f0f)
这个时候x1,y1变为

复制

x1={

a7,a6,a5,a4,e7,e6,e5,e4

b7,b6,b5,b4,f7,f6,f5,f4

c7,c6,c5,c4,g7,g6,g5,g4

d7,d6,d5,d4,h7,h6,h5,h4

}



y2={

a3,a2,a1,a0,e3,e2,e1,e0

b3,b2,b1,b0,f3,f2,f1,f0

c3,c2,c1,c0,g3,g2,g1,g0

d3,d2,d1,d0,h3,h2,h1,h0

}

这个时候再看x内部的情况
我们需要把n7,n6放在x的前面，n5,n4放在x的后面
用上面的方式放的话就是这样的
x2 = (x1 & 0xcccc0000) | ((x1<<14) & 0x33330000) | ((x1>>14) & 0x0000cccc) | (x1&0x00003333);
这个时候x1变成x2

复制

x2={

a7,a6,c7,c6,e7,e6,g7,g6

b7,b6,d7,d6,f7,f6,h7,h6

a5,a4,c5,c4,e5,e4,g5,g4

b5,b4,d5,d4,f5,f4,h5,h4

}

其实这一步的目的是把(a5,a4-c7,c6),(e5,e4-g7,g6),(b5,b4-d7,d6),(f5,f4-h7,h6)这些位交換位置
对于单个的位a,b交换，有这样的算法
t = a^b
a = t^a
b = t^b
对于多个位也可以用这样的算法
t = (a5,a4^c7,c6),(e5,e4^g7,g6),(b5,b4^d7,d6),(f5,f4^h7,h6) ==> x1^(x1>>14)&0xcccc; 这个时候t里面就只包含了这些位的异或信息

复制

t={

  a5^c7,a4^c6,0,0,e5^g7,e4^g6,0,0,

  b5^d7,b4^d6,0,0,f5^h7,f4^h6,0,0,

}

下面取出c7,c6,g7,g6,d7,d6,h7,h6
x2 = x1 ^ t<<14
再取出a5,a4,e5,e4,b5,b4,f5,f4
x2 = x1^t
合并后就是
x2 = x1 ^ t ^ (t<<14)

最后一步把n7放在第一排，n6放在第二排的算法推导后可以得到
t = (x2 ^ (x2 >> 7)) & 0x00AA00AA; x3 = x2 ^ t ^ (t << 7);

最后写成代码就是

复制



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

unsigned long x,y,t;

x = A[0]|(A[1]<<8)|(A[2]<<16)|(A[3]<<24);

y = A[4]|(A[5]<<8)|(A[6]<<16)|(A[7]<<24);

t = x;

x = (x&0xf0f0f0f0) | ((y>>4)&0x0f0f0f0f);

y = ((t<<4)&0xf0f0f0f0) | (y&0x0f0f0f0f);

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

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

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

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

B[0] = x; B[1] = x>>8; B[2] = x>>16; B[3] = x>>24;

B[4] = y; B[5] = y>>8; B[6] = y>>16; B[7] = y>>24;