看《编程卓越之道Write Great Code》的时候，在看数据总线的时候，明白了一些内存访问的基本原理，而最近在做SIMPLE，正好可以利用内存访问的一个技巧来优化一下我的程序。这 个技巧就是”数据对齐”。顺便拿出来分享一下。我会简单说一下数据对齐的由来，原因和应用方法。

首先说数据对其这种说法怎么来的。我以使 用16位(16-bit)数据总线的处理器来举例。32位的原理相同。处理器将16位的数据总线分为两部分d0-d7为低字节，d8-d15为高字节。相 应将内存分为对应两列。偶地址的接在d0-d7数据线上，奇地址的接在d8-d15位上。这样处理器就可以任意访问一个偶地址的数据，或一个奇地址的数 据，或者一个以偶地址开头的字(Word, 1word == 2byte)。
然而，例如在80×86系列的16位处理器上，它允许从任意地址读 取一个字。处理器从指定的地址取得低端字节，而从下一个地址获得高端字节。如果低端地址是偶地址的话，没有什么问题。但是，如果是奇地址的话，那么数据的 高端字节就需要到下一个字去获得了。例如希望从地址21获取一个字。这个数据位置就是在21, 22两个字节。但是要注意，处理只能将偶地址作为低位放入地址总线，所以处理器首先通过访问地址为20, 21的字节，获得一个字，然后再访问下一个字，获得地址为22, 23的两个字节。并在内部将地址21和地址22的数据交换位置，通过数据总线传递给处理器。
这在大规模访问连续数据的时候就会产生问题(当然其他 时候也可能会有)。例如，一个图像数据顺序保存在内存中，假设每个象素是两字节，数据的起始字节是奇数。并假设处理器没有做任何优化，没有缓存，那么每个 象素的读取都会有两次的内存访问，一次的高低字节数据交换。一个800*600的图像就会有480000次的多余内存访问。这个效率会差很多。所以要想办 法解决。

这里我介绍两种需要手动设置数据的对齐的情况。
1. 在一个大的数据块的开始，如果数据没有对齐，那么后面的数据都回相应错位。设置数据开始部分对齐的方法如下：(从SIMPLE中摘录，为了便于阅读，有改 动，另由于blogger对尖括号的支持不够好，所以下面的代码中可能使用全角的尖括号代替半角尖括号，使用时请自行替换。)

[code:c]< T* > alignPointer(void * raw, int align)
{
T*p = reinterpret_cast<T*>(
(reinterpret_cast<uintptr_t>(raw) + align - 1)
&~(align - 1);
return p;
}[/code]

解释一下，假设我们需要N个字节的数据，并以align对齐。(align==0,1的时候不对齐, 2的时候两字节对齐，以此类推，align为2的幂。)。void * raw是申请的空间，大小为N + align - 1个空间。多余的align - 1个空间是为了对齐而预留的。T类型是指定的每个元素的类型。

首先，通过reinterpret_cast<uintptr_t>(raw)将raw转化成uintptr_t类型，(uintptr_t是一种足够大从而可以保存指针的类型，如果没有定义uintptr_t的系统，可以使用typedef int uintptr_t来自行定义)。
结果加align - 1，相当于这个元素最后一个字节的位置。然后对~(align - 1)取与(and)运算。相当与计算出元素最后一个字节所在的内存的对齐列的第一个字节的地址。这么说有些晕，我来举个例子：例如分配n个字节，其中起始地址是7，对齐字节是4字节对齐。如果不对齐的话那么这个数据的第一个元素占用的就是7~10字节。如果对齐的话，首先7 + (4 - 1) = 10，计算出理论的最后一个字节的地址是10。然后10 & ~3。换算成二进制更好理解：1011 & 1100 = 1000，也就是十进制的8。所以起始的字节是从8开始的，那么地址是7的字节以及分配的最后两个字节会被忽略。再假设起始地址是4，那么计算后还是4，不用对齐。
2. 行对齐。在图像的内存表示中，除了开头的内存对其外，还有一个地方需要注意，就是行与行之间的对齐。例如一个RGB像素3字节，一个2*3的图像，再内存中的布局应该是：

0- 2为(0, 0) 3- 5为(1, 0) 6- 7空闲
8-10为(0, 1) 11-13为(1, 1) 14-15空闲
16-18为(0, 2) 19-21为(1, 2) 22-23空闲

图像的每一行都需要8个字节存储。不过其中仅有6个字节包含象素数据。前三个字节保存该行第一个象素的存储，其后3个字节保存下一个像素。为了另下一行从双字开始，在存储下一行的象素之前必须跳过两个字节。这里的做法跟上面的那种差不多，所以就不再举出代码了。

“为了表示实数，大多数浮点格式使用一些位来表示尾数(mantissa)，一小部分位来表示阶码(exponent，又译作指数)。尾数是一个基数，它的值通常落在一个有限的范围内（例如，零到一），而阶码是一个乘数，他作用到位数值后，产生的值就超出了这个范围。将浮点数分成这两部分结果就是，浮点 数只能以一定数量的有效数字(significant digit)来表示数值。”

“为了提高浮点计算的准确性，有必要在计算过程中使用额外的有效数字。这些额外的有效数字被称为保护位（guard digits，二进制格式时为guard bits）。在进行一长串的运算时，保护为极大地提高了准确性。”

阅读全文 »

“ASCII（美国信息交换标准码， American Standard Code for Information Interchange） 字符集将128个字符映射到无符号整型数0 .. 127 (#0 .. #7F)。”
“ASCII字符集被划分为四个包含32个字符的组。头32个字符，其ASCII码为#0到#1F(0到31)，组成了一组特殊的非打印字符，被称为控制字符。”
“第二组32个ASCII字符码包括各种标点符号，特殊字符以及数字。驻足字符中最值得关注的包括空格字符（ASCII码#20）以及数字（ASCII码#30..#39）。”
“第三组32个ASCII字符码包括大写字符字符。字符A到Z的ASCII码分布在#41..#5A的范围内。由于只有26个字母字符，多出来的六个码表示一些特殊符号。”
“第四组也是最后一组32个ASCII字符码表示小写字母字符，五个特殊符号以及另一个控制符（删除delete）。”

“第五位与第六位决定了字符所在的组。”五六位为00，表示控制字符，01表示数字与标点符号，10表示大写字母与特殊字符，11表示小写字符与特殊符号。

“如果你将大写字母与小写字母的编码转换成二进制，你会注意到大写字母与对应的小写字母的符号差别只有一位。”例如，E的二进制编码是 01000101，e的编码是01100101。相差第五位。“这两个ASCII码的唯一不同之处在第五位。大写字母符号的第五位永远是零，而小写字母字 符的第五位永远是一。你可以利用这个事实来快速地将一个字母字符在大写与小写之间进行转化，只须将第五位取反即可。”

数字的十六进制“ASCII码的低端半字节等于被表示的数。只要将ASCII码的高端半字节去掉（置全零），就得到了该数字的二进制表示。”反之可得到对应数字的ASCII码。