Lcc内存对齐代码

"A ship is safe in harbor, but that's not what ships are for."
Willam G.T. Shedd

今天看lcc源码内存对齐时看到一个roundup(x,n)

1
#define roundup(x,n) (((x)+((n)-1))&(~((n)-1)))

从字面意思看这个宏应该是用来向上取整的。但是(x+n-1)&(~(n-1))的确让人一时傻眼了。

这里要从头说起,首先roundup(x,n)的作用就是向上取整,即求出最小的a * n,使得a*n >= x,即

1
x = a * n - b (0 <= b < n)

这里就要引入小学时的余数概念了:

除数 × 商 = 被除数 - 余数

即对于任意两个正整数xn,总存在整数ab,使得:

x = a * n + b (0 <= b < n)

在C语言中求ab非常简单:

a = x / n;
b = x % n;

所以,如果把roundup(x,n)转换,就可以求a*n了:

1
2
3
4
x = a * n - b (0 <= b < n)
x+n = a * n - b + n
x+n = a*n + (n-b) (0 < (n-b) <= n)
x+n-1 = a*n + (n-b-1) (0 <= (n-b-1) < n)

于是:

1
2
a = (x+n-1)/n
a*n = (x+n-1) / n * n

到这里就可以算出a*n了,但是很明显roundup(x,n)在这里继续对公式进行优化。

因为n是内存块的单位,一定是2的幂,于是有如下的特性:

  • n = 2^m,则m = n - 1
  • n的二进制必然是100...的形态,其中有m0
  • 对于n的乘除操作,可以用左移右移完成

所以看回算式

1
a*n = (x+n-1) / n * n

可以看作是(x+n-1)右移m个位,在左移m个位,也就是把最低的m个位清零就可以了。

而从上面的属性可以知道,n-1的二进制必然是111...的形态,其中有m1,所以清零只要对m的反码进行与操作就可以了。

于是

1
a*n = (x+n-1)&(~(n-1))

多么优美的一行代码,虽然可读性不高,但是理解了之后心中还是会产生无比的敬仰,这就是编程的魔力啊,作者就像在尽情的揉捏语言,这感觉一定很棒吧!

您还在局域网,评论加载不了。