Tony Bai

比较以下两组代码，你认为哪组运行的更快些呢？
Example1：
        int n   = 100;
        int n4  = n >> 2;
        int i   = 0;

        int a[100];

        for (i = 0; i < n4 ;i += 4) {
                a[i] = i;
                a[i+1] = i+1;
                a[i+2] = i+2;
                a[i+3] = i+3;
        }

Example2：
       for (i = 0;i < 100;i++) {
             a[i] = i;
       }

其实这个问题在"代码大全2nd"中也有讨论，从"代码大全"中的统计结果来看，一般来说Example1更占有优势。我在solaris上做了测试，在未开优化的情况下：两者运行时间分别为2ms和6ms；在打开-O2优化后，两者均为1ms。这种通过减少循环次数的方法在GLIBC中也有体现，比如说strncpy的实现：

下面是strncpy的GLIBC源码：
char *
x_strncpy (s1, s2, n)
        char *s1;
        const char *s2;
        size_t n;
{
        reg_char c;
        char *s = s1;

        --s1;

        if (n >= 4)
        {
                size_t n4 = n >> 2; /* n4 = n / 4， n4表示下面的循环执行的次数*/

                for (;;)
                {
                        c = *s2++;
                        *++s1 = c;
                        if (c == '\0')
                                break;
                        c = *s2++;
                        *++s1 = c;
                        if (c == '\0')
                                break;
                        c = *s2++;
                        *++s1 = c;
                        if (c == '\0')
                                break;
                        c = *s2++;
                        *++s1 = c;
                        if (c == '\0')
                                break;
                        if (--n4 == 0)
                                goto last_chars;  /* 如果n = 10，s2 = "hello world"，则两轮循环后，还有"尾巴"没有copy完，在last_chars处继续处理 */
                }
                n = n - (s1 - s) - 1;  /* 还没有copy完n个字节，s2就到达末尾了，跳到zero_fill处继续为s1补零 */
                if (n == 0)
       return s;
                goto zero_fill;
        }

last_chars:     
        n &= 3;       /* n = n & 3 结果 n <= 3，n即为上面循环过后"尾巴字符"的数量 */
        if (n == 0)
                return s;
        do
        {
                c = *s2++;
                *++s1 = c;
                if (--n == 0)
                        return s;
        } while (c != '\0');

zero_fill:       
        do
                *++s1 = '\0';
        while (--n > 0);

        return s;
}

相比于strlen的实现，strncpy的实现更易理解。其字面上的逻辑就是每四个字节(n>>2)作为一组，每组逐个字节进行拷贝赋值，其内在目的则是减少循环次数，以获得性能的提升。要想知道为什么减少循环次数能提升性能的话，那就要深入到汇编层面去了，这里不再详述。另外还要一提的是GLIBC中的strncmp，strncat的实现也遵循着与上面同样的逻辑。

直接操作C标准库提供的字符串操作函数是有一定风险的，稍有不慎就会导致内存问题。这周用业余时间写了一个小型的安全字符串操作库，但是测试之后才发现自己的实现有很大的性能缺陷。

在Solaris上初步做了一个简单的性能比对，以下是得到的性能数据(以strlen的数据为例)：
当传入的字符串长度为10时，执行100w次：
strlen 执行时间是：32762毫秒
my_strlen执行时间是：491836毫秒

当传入的字符串长度为20时，执行100w次：
strlen 执行时间是：35075毫秒
my_strlen执行时间是：770397毫秒

很显然，标准库中strlen的消耗仅是my_strlen的十分之一不到，且其性能消耗随着字符串长度的增加并未有近线性的增加，而my_strlen则是变化明显。想必大家这时也能猜到my_strlen采用了传统的实现的方式，即采用逐个字节判断是否为'\0'方式，这也与测试出的现象相符。本着刨根问底的精神，我在网上找到了GNU提供的C标准库中strlen实现的源码，要看看GLIBC中strlen究竟采用何种技巧才达到了那么高的性能。说实话在性能优化这方面自己一直还处于比较初级的位置，这也将是自己将来努力的一个方向。

下载了全部GLIBC的代码包，这个包还真不小。在string子目录下找到strlen.c，这就是大多数UNIX平台、Linux平台以及绝大多数GNU软件使用的strlen的实现源码了。这份代码由Torbjorn Granlund(还实现了memcpy)编写，Jim Blandy和Dan Sahlin提供了帮助和注释。包括注释在内，GLIBC的strlen的代码足足有近130行，大致浏览一下， 没有怎么看懂，可耐下心来细致阅读，还是有些心得的。下面是strlen源码摘要版，后面我将针对这段代码写一些我的理解：
 
  1 /* Return the length of the null-terminated string STR.  Scan for
  2    the null terminator quickly by testing four bytes at a time.  */
  3 size_t strlen (str)  const char *str;
  4 {
  5         const char *char_ptr;
  6         const unsigned long int *longword_ptr;
  7         unsigned long int longword, magic_bits, himagic, lomagic;
  8
  9         /* Handle the first few characters by reading one character at a time.
 10            Do this until CHAR_PTR is aligned on a longword boundary.  */
 11
 12         for (char_ptr = str; ((unsigned long int) char_ptr
 13              & (sizeof (longword) - 1)) != 0;
 14              ++char_ptr)
 15                 if (*char_ptr == '\0')
 16                         return char_ptr - str;
 17
 18         /* All these elucidatory comments refer to 4-byte longwords,
 19            but the theory applies equally well to 8-byte longwords.  */
 20
 21         longword_ptr = (unsigned long int *) char_ptr;
 22
 23         himagic = 0x80808080L;
 24         lomagic = 0x01010101L;
 25
 26         if (sizeof (longword) > 8)
 27                 abort ();
 28
 29         /* Instead of the traditional loop which tests each character,
 30            we will test a longword at a time.  The tricky part is testing
 31            if *any of the four* bytes in the longword in question are zero.  */
 32
 33         for (;;)     
 34         {                        
 35                 longword = *longword_ptr++;    
 36
 37                 if ( ((longword - lomagic) & himagic) != 0)
 38                 {
 39                         /* Which of the bytes was the zero?  If none of them were, it was
 40                            a misfire; continue the search.  */
 41
 42                         const char *cp = (const char *) (longword_ptr - 1);
 43
 44                         if (cp[0] == 0)
 45                                 return cp - str;
 46                         if (cp[1] == 0)
 47                                 return cp - str + 1;
 48                         if (cp[2] == 0)
 49                                 return cp - str + 2;
 50                         if (cp[3] == 0)
 51                                 return cp - str + 3;
 52                         if (sizeof (longword) > 4)
 53                         {
 54                                 if (cp[4] == 0)
 55                                         return cp - str + 4;
 56                                 if (cp[5] == 0)
 57                                         return cp - str + 5;
 58                                 if (cp[6] == 0)
 59                                         return cp - str + 6;
 60                                 if (cp[7] == 0)
 61                                         return cp - str + 7;
 62                         }
 63                 }
 64         }
 65 }

从这段代码开头作者的注释我们大致可以了解到该strlen实现的原理：就是通过每次测试四个字节来代替传统实现中每次测试一个字节的方法。知道这个原理了，那么还需要解决两个难题：
1) C标准库要求有很好的移植性，在绝大部分系统体系结构下都应该能正确运行。那么每次拿出4个字节比较(unsigned long int)，就需要考虑内存对齐问题，传入的字符串的首字符地址可不一定在4对齐的地址上；
2) 如何对四个字节进行测试，找出其中某个字节为全0，这是个技巧问题。

12～21行的代码解决的就是第一个问题：
      for (char_ptr = str; ((unsigned long int) char_ptr
             & (sizeof (longword) - 1)) != 0;
             ++char_ptr)
                if (*char_ptr == '\0')
                        return char_ptr - str;

        /* All these elucidatory comments refer to 4-byte longwords,
           but the theory applies equally well to 8-byte longwords.  */

        longword_ptr = (unsigned long int *) char_ptr;
作者通过一个for-loop找到传入字符串中第一个地址对齐到4的字符的地址，由于该地址已经对齐到4，所以最后一行那个强制转型是安全的。虽然可以通过圆整算式直接得到该对齐地址，但是考虑到这个区间可能存在的'\0'，一个字符一个字符比对也是不可避免的。在很多严格对齐的架构上(比如SUN的SPARC平台)，编译器一般会将字符串地址在编译器就放到对齐的地址上，这样一来，实际执行strlen时for-loop很少能执行一步。

第二个问题作者则是通过一个"带前提"的技巧来解决的。作者设定了两个掩码变量：
 himagic = 0x80808080L;
 lomagic = 0x01010101L;
并通过一个conditional expression完成了对四字节中全0字节的检测：((longword - lomagic) & himagic) != 0
我们将himagic和lomagic按bit展开：
himagic   1000 0000 1000 0000 1000 0000 1000 0000
lomagic   0000 0001 0000 0001 0000 0001 0000 0001

对于这样的代码，似乎没有什么理论可以遵循，需要在实践中去理解。起初我构造了一个不含全0字节的longword，比如：
longword  1000 0001 1000 0001 1000 0001 1000 0001，然后按照那个条件表达式计算后，居然也满足!=0的条件，是不是作者的逻辑有问题呢？后来转念一想，这种逻辑是有“前提条件”的。回顾一下strlen是做什么的，其输入参数是任意的么？当然不是。输入的字符串中每个字符的值都在[0, 127]的ascii码范围内，也就是说每个字节最高位的bit都是0，这样longword就应该是如下这个样子了：
longword  0xxx xxxx 0xxx xxxx 0xxx xxxx 0xxx xxxx

基于这样的前提我们考虑两种情况：
当longword中没有全0字节时，比如：
longword 0000 0001 0000 0001 0000 0001 0000 0001
这样在做完计算后，值为0，不满足条件。

当longword中有全零字节时，比如：
longword 0000 0000 0000 0001 0000 0001 0000 0001
这样在做完计算后，最高字节最高bit的值肯定为1，满足!=0条件，全0字节被检测出来。也就是说一旦有全0字节，在减去lomagic时势必会产生借位，全0的那个字节在减去lomagic后最高位bit肯定由0变1，这样与himagic一与，肯定不为0，就是这么检测出来的。

这一方法在64位平台依然适用，上面的代码摘要中省略了对64bit平台的特殊处理，为的是使代码逻辑更清晰，更易读。

今天闲时写了一个Demo测试程序，目的：测试64位编译下使用mmap映射共享内存的能力。程序很简单，大致如下结构：
#define MAP_SPACE_SIZE  (4*1024*1024*1024)
unsigned long int ms_sz = MAP_SPACE_SIZE;
.... ....
ptr = mmap( NULL, ms_sz, PROT_READ|PROT_WRITE,MAP_SHARED, fd, 0 );

我尝试在64位编译模式下映射4G的空间，结果mmap返回MAP_FAILED，errno返回EINVAL，通过查看mmap的manual得知，很可能是ms_sz这个参数的问题，当该参数实际值为0或<0时，mmap如是返回错误。输出一下ms_sz，居然真的是零，让我有些不解，但细致想了以后，觉得还是有道理的。

我遂尝试了重新定义MAP_SPACE_SIZE，结果印证了我的分析是正确的。
当#define MAP_SPACE_SIZE  (4*1024*1024*1024L)时，ms_sz输出 4294967296；
当#define MAP_SPACE_SIZE  4294967296时，ms_sz同样输出 4294967296；

这里简单说一下，首先 (4*1024*1024*1024)是不是常量呢？从程序的输出结果来看，编译器没有直接将其与数值常量4294967296等价，而是执行了计算过程。这也是我们第一次得到0这个结果的原因了。由于没有显式的后缀，编译器按照int, long, long long的顺序识别数值类型，编译器在识别4*1024*1024*1024中的各个数值时，显然将各个值识别为int了，而乘积的结果也放到了一个int临时存储区中，4G对于一个32bit的int刚好过庞大，结果溢出，导致该值变成了0，将0赋给ms_sz(unsigned long int)，同样也是0，这就是原因。

当#define MAP_SPACE_SIZE  (4*1024*1024*1024L)时，由于显式给出了L后缀，编译器将运算结果直接存储在8 byte的long中，这样ms_sz自然很easy的得到了正确的值 4294967296。

当#define MAP_SPACE_SIZE  4294967296时，这时4294967296可是一个常量，标准的整型常量，编译器发现unsigned int无法将其装下，遂将之识别为long int类型了，这样该值赋给ms_size时就是同类型的了。

每年都有应届毕业生来到公司，每年都要对新同事进行代码方面的培训，比如编码规范就是其中之一。编码规范初听起来比较新鲜，但是培训时间长了，显然有些乏味。今年我打算改变策略，让新同事结合已有规范文档和项目代码，自己先挖掘一遍，然后大家通过坐下来讨论的互动方式来加深对规范的理解，每次讨论时间限制在1 hour以内，不给大家打瞌睡的机会^_^。

上周和新同事一起讨论表达式和语句，说到了switch和if，谈到了他们的用途和区别。大家都清楚switch语句被称为多分支语句，当代码中即将出现3个及3个以上分支时，推荐用switch，这样代码可读性好，清晰，格式工整；但是同样switch也是有局限的，就是switch(xx)中的xx必须是整型变量；如果你的条件判断是字符串比较，就无法直接使用switch了。switch的这一局限实际上是有原因的，为什么呢？在于其性能优化。那switch语句在底层到底是如何实现的呢？和if语句相比，switch除了美观之外，优势又在哪里呢？我们唯有到汇编层去看个究竟了。

我们先来看看if多分支的情况：//Windows XP + gcc v3.4.2 (mingw-special)
//testif.c
int test_if_performance(int i) {
    int rv = i;

    if (rv == 10) {
        rv += 100;
    } else if (rv == 11) {
        rv += 101;
    } else if (rv == 12) {
        rv += 102;
    } else if (rv == 13||rv == 14 || rv == 15) {
        rv += 105;
    } else {
        rv += 0;
    }
    return rv;
}

我们通过-S选项得到test_if_performance的汇编代码，我们加上了-O2的优化选项：
//gcc -S O2 testif.c
//testif.s
... ...
_test_if_performance:
    pushl    %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    cmpl    $10, %edx
    je    L11
    cmpl    $11, %edx
    je    L12
    cmpl    $12, %edx
    je    L13
    leal    -13(%edx), %eax
    cmpl    $2, %eax
    ja    L3
    addl    $105, %edx
L3:
    popl    %ebp
    movl    %edx, %eax
    ret
    .p2align 4,,7
L11:
    popl    %ebp
    movl    $110, %edx
    movl    %edx, %eax
    ret
    .p2align 4,,7
L12:
    popl    %ebp
    movl    $112, %edx
    movl    %edx, %eax
    ret
    .p2align 4,,7
L13:
    popl    %ebp
    movl    $114, %edx
    movl    %edx, %eax
    ret

从这段汇编码来看，if语句是逐个判断下来的，如果i = 19的话，程序需要从头判断到尾，"一个都不能少"^_^。那么拥有同样语义功能的switch代码又是如何实现的呢？我们继续看下去。
// testswitch.c 这个文件实现的是和上述testif.c同样的功能
int test_switch_performance(int i) {
        int rv = i;

        switch(rv) {
                case 10:
                        rv += 100;
                        break;
                case 11:
                        rv += 101;
                        break;
                case 12:
                        rv += 102;
                        break;
                case 13:
                case 14:
                case 15:
                        rv += 105;
                        break;
                default:
                        rv += 0;
        }
        return rv;
}

我们同样用-O2来得到switch的汇编代码：
//gcc -S O2 testswitch.c
//testswitch.s
... ...
_test_switch_performance:
    pushl    %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %ecx
    leal    -10(%ecx), %edx
    movl    %ecx, %eax
    cmpl    $5, %edx
    ja    L2
    jmp    *L10(,%edx,4)
    .section .rdata,"dr"
    .align 4
L10:
    .long    L3
    .long    L4
    .long    L5
    .long    L8
    .long    L8
    .long    L8
    .text
    .p2align 4,,7
L8:
    leal    105(%ecx), %eax
    .p2align 4,,15
L2:
    popl    %ebp
    ret
    .p2align 4,,7
L3:
    popl    %ebp
    leal    100(%ecx), %eax
    ret
    .p2align 4,,7
L4:
    popl    %ebp
    leal    101(%ecx), %eax
    ret
    .p2align 4,,7
L5:
    popl    %ebp
    leal    102(%ecx), %eax
    ret
看完汇编码，第一感觉：cmpl少了许多，一个只读数据段中的L10的标签映入眼帘，以L10标签为起始的内存中依次存储了L3、L4、L5和三个L8的地址，看起来就像是一个地址数组，或者是一个地址表，访问这个数组中的元素实际上就是调用每个元素对应地址中的一段代码。我们继续往前看，来证实一下这个想法。代码不多，比对着汇编指令手册读起来也不甚难。

pushl    %ebp
movl    %esp, %ebp        // 将栈帧地址存在%ebp中
movl    8(%ebp), %ecx        // 将rv值存储到%ecx中
leal    -10(%ecx), %edx        // 将rv值-10之后的值，作为地址偏移量存放到%edx
movl    %ecx, %eax        // 将%ecx中的rv值存储到%eax中
cmpl    $5, %edx            // 比较5 vs. (rv - 10)，显然5是编译器经过代码扫描后，算出的一个最大偏移值
ja    L2            // jump if above ，如果5 > %edx中的值，则跳到L2继续执行
jmp    *L10(,%edx,4)        // 如果5 <= %edx中的值，则jmp    *L10(,%edx,4)

解析一下jmp    *L10(,%edx,4)，按照书中所说，*L10(,%edx,4)应该对应一个叫indexed memory mode的模式，格式一般是base_address(offset_address, index, size)，含义就是base_address + offset_address + index * size；这样似乎就一目了然了。我们拿i = 12为例，经过前面的计算，%edx中存储的是2，L10(,%edx,4)相当于L10 + 0 + 2 * 4，也就是起始地址=L10 + 8的那个内存区域，恰好是L5的起始地址，jmp    *L10(,%edx,4)，直接将代码执行routine转到L5了：

L5:
    popl    %ebp
    leal    102(%ecx), %eax
    ret
显然这和前面的猜测是一致的，switch并没有使用性能低下的逐个cmpl的方式，而是形成了一个跳转表(以L10为首地址的地址数组)，并将传入switch的那个整型值经过已经的运算后作为offset值，通过一个jmp直接转到目的代码区，这样无论switch有多少个分支，实际上都只是做了一次cmpl，性能照比多if有很大提升。

assert是大家常用的宏，它的用法相信大家都有所了解。P.J Plauger的"The C Standard Library"一书中提到在源代码中切换assert宏定义的方法：
/* turn assertion on */
#undef NDEBUG
#include <assert.h>

/* turn assertions off */
#define NDEBUG
#include <assert.h>

我顺手写了一个例子如下：
/* testmacro1.c */
#define NDEBUG
#include <assert.h>

int main() {

        assert(0); // => ((void)0);

#undef NDEBUG
        #include <assert.h>
        assert(0); // => (void)((0) || (__assert("0", "testmacro.c", 10), 0));
}
测试结果正如P.J Plauger的说明。但仔细看来似乎有些疑惑：总觉得第二个assert也应该展开成((void)0)才对啊。由于NDEBUG被定义，在第一次assert.h展开时，assert就被替换成了((void)0)，而后虽然NDEBUG被disable了，但此时由于assert.h的header file guard保护，assert的新定义并没有被重新loaded & evaluated，所以assert似乎依然应该被展开为((void)0)，但执行结果却不是。

我自己写了一个程序测试了一下：
/* testmacro1.h */
#ifndef TEST_MACRO1_H
#define TEST_MACRO1_H

#ifdef X_DEBUG
#define x_debug(expr)   ((void)0)
#else
#define x_debug(expr)   #expr
#endif
#endif

/* testmacro1.c */
#define X_DEBUG
#include "testmacro1.h"

int main() {
        x_debug(0); // => ((void)0);

#undef X_DEBUG
        #include "testmacro1.h"
        x_debug(0); // => ((void)0)
}
果不其然，结果正如我所猜测的：
#undef X_DEBUG
#include "testmacro1.h"
并没有改变x_debug的定义，那么第一个例子到底是怎么回事呢？

其实这是C标准库设计所致，打开你所在系统的assert.h标准文件，我在sun solairs 9上是这样的：
#ifndef _ASSERT_H
#define _ASSERT_H
... ...
#endif

#undef  assert
#ifdef  NDEBUG
#define assert(EX) ((void)0)
#else
#define assert(EX) (void)((EX) || (__assert(#EX, __FILE__, __LINE__), 0))
#endif  /* NDEBUG */

哈哈，这下子看清楚了，原来assert的定义根本不在Header File Guards的保护下，怪不得我思前想后都对不上呢:)，因为没有File Guards的保护。使头文件中的宏有机会被重新loaded&envaluated。

下面例子中的第三个assert屏蔽掉了标准库中的assert实现：
/* testmacro3.c */
#define NDEBUG
#include <assert.h>

int main() {

        assert(0); // => ((void)0);

#undef NDEBUG
        #include <assert.h>
        assert(0); // => (void)((0) || (__assert("0", "testmacro3.c", 10), 0));

#define assert(exp) (#exp)
        assert(x==0); // => ("x==0");
}
这种屏蔽很简单，就不多说了，自己看吧。

P.J Plauger的"The Standard C Library"一书的Chapter0的章后练习中有这样的一道题：编写一个包含如下一行语句的正确的程序：
x:      ((struct x*)x)->x=x(5);
并描述这行语句中x的5种截然不同的use，这里其实涉及到这么一个知识或者说概念：C语言的命名空间(namespace)，在"C语言参考手册"中还被称作: overloading class。

这里namespace，并非C++中的那个keyword "namespace"，这里的namespace更多是编译器为了识别不同范围下的标识符而进行的划分，而不是提供给应用程序员的类似c++中的那个namespace facility。再次注意：C的namespace不是一个关键字。

简单分析一下这行语句：x:      ((struct x*)x)->x=x(5);
这里有5个x，第一印象：这样的语句能编译过去么？那既然P.J Plauger提出了这样的问题，那么自然有solution。
从左到右顺序：
第一个x -- 毋庸置疑，这是一个标号(label) ；
第二个x -- 这里的x显然是一个struct tag(结构体标志)；
第三个x -- 这里的x 无法确定其具体身份，可能是一指针类型，也可能就是一个整型；
第四个x -- x前面有->，显然这个x是某结构体的一个成员变量；
第五个x -- x(5)让人"浮想联翩"，第一印象是函数调用，细致一想还可能是一个宏哦(你肯定会说不可能，呵呵，别着急，慢慢来)

到底如何增加一些语法元素能让这一行能顺利通过编译，并执行后得到合理结果呢？我们不妨先来温习一下C标准中对C的"命名空间"的诠释。

在"C语言参考手册"中有如此说明，标准C将其Namespace分成了五种，分别是：
1) 预处理器宏名
2) 语句标号
3) 结构、枚举、联合结构的标志
4) 成员名
5) 其他名称 包括变量名、函数名、typedef名称和枚举常量

有了以上的说明，我们有了第一种方案：
上面说了，语句x:      ((struct x*)x)->x=x(5)中有三个x都是可以确定的，不确定的是第三个x和最后一个x。我们先考虑让最后一个x为一个函数。

考虑到最后一个名称空间的说明，一旦最后一个x为函数的话，第三个x就不能为变量名、typedef名称和枚举常量了。如果x是对象宏(不带参数的宏)，显然也不合理；那么我们先将x实现为函数看看：
struct x { //for the 2nd x
        int x;  //for the 4th x
};

int x(int a) { //for the 3rd and 5th x
        return a;
}

int main() {
x:      ((struct x*)x)->x=x(5);
}
这个在gcc(sunos or mingw on windows下)下编译能顺利通过。但是执行一下编译出的程序，会出现致命错误。初略分析一下也不奇怪。函数x的地址是在代码段，那块内存区域是只读且受保护的，尝试强制赋值显然os是不允许的。

第一种方案虽然能通过编译，但是执行结果不合理。我们来做第二种尝试：试着将最后一个x实现为一个函数宏(带参数的宏)。
struct x { //for the 2nd x
        int x;  //for the 4th x
};

struct x ax;

#define x(a)  (a);

int main() {
        int x = (int)(&ax);
x:      ((struct x*)x)->x=x(5);  
        printf("%d\n", ((struct x*)x)->x); //output: 5
}
这回，我们得到了正确的且合理的solution了。在P.J Plauger的"The Standard C Library"一书中还有一张关于C语言命名空间的图，记起来更形象。

很多技术人员都有在"技术细节"上"钻牛角尖"的"癖好"，对此很多人褒贬不一；无论怎样，我也是属于这类人。C语言的变长参数在平时做开发时很少会在自己设计的接口中用到，但我们最常用的接口printf就是使用的变长参数接口，在感受到printf强大的魅力的同时，是否想挖据一下到底printf是如何实现的呢？这里我们一起来挖掘一下C语言变长参数的奥秘。

先考虑这样一个问题：如果我们不使用C标准库(libc)中提供的Facilities，我们自己是否可以实现拥有变长参数的函数呢？我们不妨试试。

一步一步进入正题，我们先看看固定参数列表函数，
void fixed_args_func(int a, double b, char *c) {
        printf("a = 0x%p\n", &a);
        printf("b = 0x%p\n", &b);
        printf("c = 0x%p\n", &c);
}
对于固定参数列表的函数，每个参数的名称、类型都是直接可见的，他们的地址也都是可以直接得到的，比如：通过&a我们可以得到a的地址，并通过函数原型声明了解到a是int类型的; 通过&b我们可以得到b的地址，并通过函数原型声明了解到b是double类型的; 通过&c我们可以得到c的地址，并通过函数原型声明了解到c是char*类型的。

但是对于变长参数的函数，我们就没有这么顺利了。还好，按照C标准的说明，支持变长参数的函数在原型声明中，必须有至少一个最左固定参数(这一点与传统C有区别，传统C允许不带任何固定参数的纯变长参数函数)，这样我们可以得到其中固定参数的地址，但是依然无法从声明中得到其他变长参数的地址，比如：
void var_args_func(const char * fmt, ... ) {
    ... ...
}
这里我们只能得到fmt这固定参数的地址，仅从函数原型我们是无法确定"..."中有几个参数、参数都是什么类型的，自然也就无法确定其位置了。那么如何可以做到呢？在大脑中回想一下函数传参的过程，无论"..."中有多少个参数、每个参数是什么类型的，它们都和固定参数的传参过程是一样的，简单来讲都是栈操作，而栈这个东西对我们是开放的。这样一来，一旦我们知道某函数帧的栈上的一个固定参数的位置，我们完全有可能推导出其他变长参数的位置，顺着这个思路，我们继续往下走，通过一个例子来诠释一下：(这里要说明的是：函数参数进栈以及参数空间地址分配都是"实现相关"的，不同平台、不同编译器都可能不同，所以下面的例子仅在IA-32，Windows XP， MinGW gcc v3.4.2下成立)

我们先用上面的那个fixed_args_func函数确定一下这个平台下的入栈顺序。

int main() {
    fixed_args_func(17, 5.40, "hello world");
    return 0;
}
a = 0x0022FF50
b = 0x0022FF54
c = 0x0022FF5C

从这个结果来看，显然参数是从右到左，逐一压入栈中的(栈的延伸方向是从高地址到低地址，栈底的占领着最高内存地址，先入栈的参数，其地理位置也就最高了)。我们基本可以得出这样一个结论：
 c.addr = b.addr + x_sizeof(b);  /*注意:  x_sizeof != sizeof，后话再说 */
 b.addr = a.addr + x_sizeof(a);

有了以上的"等式"，我们似乎可以推导出 void var_args_func(const char * fmt, ... ) 函数中，可变参数的位置了。起码第一个可变参数的位置应该是：first_vararg.addr = fmt.addr + x_sizeof(fmt);  根据这一结论我们试着实现一个支持可变参数的函数：

void var_args_func(const char * fmt, ... ) {
    char    *ap;

    ap = ((char*)&fmt) + sizeof(fmt);
    printf("%d\n", *(int*)ap);  
        
    ap =  ap + sizeof(int);
    printf("%d\n", *(int*)ap);

    ap =  ap + sizeof(int);
    printf("%s\n", *((char**)ap));
}

int main(){
    var_args_func("%d %d %s\n", 4, 5, "hello world");
}

输出结果:
4
5
hello world

var_args_func只是为了演示，并未根据fmt消息中的格式字符串来判断变参的个数和类型，而是直接在实现中写死了，如果你把这个程序拿到solaris 9下，运行后，一定得不到正确的结果，为什么呢，后续再说。先来解释一下这个程序。我们用ap获取第一个变参的地址，我们知道第一个变参是4，一个int型，所以我们用(int*)ap以告诉编译器，以ap为首地址的那块内存我们要将之视为一个整型来使用，*(int*)ap获得该参数的值；接下来的变参是5，又一个int型，其地址是ap + sizeof(第一个变参)，也就是ap + sizeof(int)，同样我们使用*(int*)ap获得该参数的值；最后的一个参数是一个字符串，也就是char*，与前两个int型参数不同的是，经过ap + sizeof(int)后，ap指向栈上一个char*类型的内存块(我们暂且称之tmp_ptr, char *tmp_ptr)的首地址，即ap -> &tmp_ptr，而我们要输出的不是printf("%s\n", ap)，而是printf("%s\n", tmp_ptr); printf("%s\n", ap)是意图将ap所指的内存块作为字符串输出了，但是ap -> &tmp_ptr，tmp_ptr所占据的4个字节显然不是字符串，而是一个地址。如何让&tmp_ptr是char **类型的，我们将ap进行强制转换(char**)ap <=> &tmp_ptr，这样我们访问tmp_ptr只需要在(char**)ap前面加上一个*即可，即printf("%s\n",  *(char**)ap);

前面说过，如果将var_args_func放到solaris上，一定是得不到正确结果的？为什么呢？由于内存对齐。编译器在栈上压入参数时，不是一个紧挨着另一个的，编译器会根据变参的类型将其放到满足类型对齐的地址上的，这样栈上参数之间实际上可能会是有空隙的。上述例子中，我是根据反编译后的汇编码得到的参数间隔，还好都是4，然后在代码中写死了。

为了满足代码的可移植性，C标准库在stdarg.h中提供了诸多Facilities以供实现变长长度参数时使用。这里也列出一个简单的例子，看看利用标准库是如何支持变长参数的：
#include <stdarg.h>

void std_vararg_func(const char *fmt, ... ) {
        va_list ap;
        va_start(ap, fmt);

        printf("%d\n", va_arg(ap, int));
        printf("%f\n", va_arg(ap, double));
        printf("%s\n", va_arg(ap, char*));

        va_end(ap);
}

int main() {
        std_vararg_func("%d %f %s\n", 4, 5.4, "hello world");
}
输出:
4
5.400000
hello world

对比一下 std_vararg_func和var_args_func的实现，va_list似乎就是char*， va_start似乎就是 ((char*)&fmt) + sizeof(fmt)，va_arg似乎就是得到下一个参数的首地址。没错，多数平台下stdarg.h中va_list, va_start和var_arg的实现就是类似这样的。一般stdarg.h会包含很多宏，看起来比较复杂。在有的系统中stdarg.h的实现依赖some special functions built into the the compilation system to handle variable argument lists and stack allocations，多数其他系统的实现与下面很相似：(Visual C++ 6.0的实现较为清晰，因为windows上的应用程序只需要在windows平台间做移植即可，没有必要考虑太多的平台情况)。

Microsoft Visual Studio\VC98\Include\stdarg.h中，
typedef char *  va_list;

#define _INTSIZEOF(n)   ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )
#define va_start(ap,v)  ( ap = (va_list)&v + _INTSIZEOF(v) )
#define va_arg(ap,t)    ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) )
#define va_end(ap)      ( ap = (va_list)0 )

这里有两个地方需要深入挖掘一下：
1、#define _INTSIZEOF(n)   ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )
我们这里简化一下这个宏：
#define _INTSIZEOF(n)  ((sizeof(n) + x) & ~(x))
x = sizeof(int) - 1 = 3 = 0000 0000 0000 0011(b)
~x = 1111 1111 1111 1100(b)

当一个数 & (-x)时，得到的值始终是sizeof(int)的倍数，也就是说_INTSIZEOF(n)的功能是将n圆整到sizeof(int)的倍数上去。sizeof(n) >= 1, sizeof(n)+sizeof(int)-1经过圆整后，一定会是>=4的整数；在其他系统平台上，圆整的目标值有的是4，有的则是8，视具体系统而定。

2、#define va_arg(ap,t)    ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) )
其实有了var_args_func的实现，这里也就不难理解了。不过这里有一个trick，很多人一开始肯定对先加上_INTSIZEOF(t)，又减去_INTSIZEOF(t)很不理解，其实这里是一点就透的：整个表达式((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) 返回的值其实和最初的ap所指向的地址是一致的，关键就是在整个表达式被evaluated后，ap却指向了下一个参数的地址了，就这么简单。

在P.J.Plauger的"The standard C library"一书的第10章节中也有对stdarg实现的分析，那个版本虽然比较老，但我想应该是现有版本的一个雏形。

C语言语法简单，但内涵却博大精深；如果在学习时只是止步于表面，那么往往后期会遇到很多困难。typedef是C语言中一个很好用的工具，大量存在于已有代码中，特别值得一提的是：C++标准库实现中更是对typedef有着大量的使用。但很多初学者对其的理解仅局限于：typedef用来定义一个已有类型的"别名(alias)"。正是因为有了这样的理解，才有了后来初学者在typedef int myint和typedef myint int之间的犹豫不决。很多国内大学的C语言课之授课老师也都是如是说的，或者老师讲的不够透彻，导致学生们都是如是理解的。我这里想结合C语言标准文档以及一些代码实例，也说说typedef。

int    *p;
这样的代码是C语言中最最基础的一个语句了，大家都知道这个语句声明了一个变量p，其类型是指向整型的指针(pointer to int)；如果在这个声明的前面加上一个typedef后，整个语义(semantics)又会是如何改变的呢？
typedef  int    *p;

我们先来看看C99标准中关于typedef是如何诠释的？C99标准中这样一小段精辟的描述："In a declaration whose storage-class specifier is typedef, each declarator defines an identifier to be a typedef name that denotes the type specified for the identifier in the way described in xx"。

参照这段描述，并拿typedef  int    *p作为例子来理解：在一个声明中，如果有存储类说明符typedef的修饰，标识符p将被定义为了一个typedef name，这个typedef name表示(denotes)一个类型，什么类型呢？就是int *p这个声明(declarator)中标识符(indentifier)p的类型(int*)。

再比对一下两个声明：
int    *p;
typedef  int    *p;
是不是有点"茅舍顿开"的感觉，int *p中, p是一个变量，其类型为pointer to int；在int *p前面增加一个typedef后，p变为一个typedef-name，这个typedef-name所表示的类型就是int *p声明式中p的类型(int*)。说句白话，typedef让p去除了普通变量的身份，摇身一变，变成了p的类型的一个typedef-name了。

为了巩固上面的理解，我们再来看看"C语言参考手册(C: A Reference Manual)"中的说法：任何declarator(如typedef int   *p)中的indentifier(如p)定义为typedef-name， 其(指代p)表示的类型是declarator为正常变量声明(指代int  *p)的那个标识符(指代p)的类型(int*)。有些绕嘴，不过有例子支撑：

[例1]
typedef double MYDOUBLE;  

分析:
去掉typedef ，得到正常变量声明=> double MYDOUBLE;
变量MYDOUBLE的类型为double;
=> "typedef double MYDOUBLE"中MYDOUBLE是类型double的一个typedef-name。

MYDOUBLE    d; <=> d是一个double类型的变量

[例2]
typedef double *Dp;  

分析:
去掉typedef  ，得到正常变量声明=> double *Dp;
变量Dp的类型为double*，即pointer to double;
=> "typedef double *Dp"中Dp是类型double*的一个typedef-name。

Dp    dptr; <=> dptr是一个pointer to double的变量

[例3]
typedef int* Func(int);

分析:
去掉typedef  ，得到正常变量声明=> int* Func(int);
变量Func的类型为一个函数标识符，该函数返回值类型为int*，参数类型为int;
=> "typedef int* Func(int)"中Func是函数类型(函数返回值类型为int*，参数类型为int)的一个typedef-name。

Func    *fptr; <=> fptr是一个pointer to function with one int parameter, returning a pointer to int
Func     f;   这样的声明意义就不大了。

[例4]
typedef int (*PFunc)(int);

分析:
去掉typedef  ，得到正常变量声明=> int (*PFunc)(int);
变量PFunc的类型为一个函数指针，指向的返回值类型为int，参数类型为int的函数原型;
=> "typedef int (*PFunc)(int)"中PFunc是函数指针类型(该指针类型指向返回值类型为int，参数类型为int的函数)的一个typedef-name。

PFunc     fptr; <=> fptr是一个pointer to function with one int parameter, returning int

[例5]
typedef    int   A[5];

分析:
去掉typedef ，得到正常变量声明 => int   A[5];
变量A的类型为一个含有5个元素的整型数组；
=> "typedef    int   A[5]"中A是含有5个元素的数组类型的一个typedef-name。

A   a = {3, 4, 5, 7, 8};
A   b = { 3, 4, 5, 7, 8, 9}; /* 会给出Warning: excess elements in array initializer */

[例6]
typedef    int   (*A)[5]; (注意与typedef    int*    A[5]; 区分)

分析:
去掉typedef ，得到正常变量声明 => int   (*A)[5];
变量A的类型为pointer to an array with 5 int elements；
=> "typedef    int   (*A)[5]"中A是"pointer to an array with 5 int elements"的一个typedef-name。

int   c[5] = {3, 4, 5, 7, 8};  
A    a = &c;
printf("%d\n", (*a)[0]); /* output: 3 */

如果这样赋值：
int   c[6] = {3, 4, 5, 7, 8, 9};  
A    a = &c; /* 会有Warning: initialization from incompatible pointer type */

[例7]
typedef struct _Foo_t Foo_t;

分析:
去掉typedef ，得到正常变量声明 => struct _Foo_t Foo_t;
变量Foo_t的类型为struct _Foo_t;
=> "typedef struct _Foo_t Foo_t"中Foo_t是"struct _Foo_t"的一个typedef-name。

[例8]
typedef   struct { ... // }   Foo_t;

分析:
去掉typedef ，得到正常变量声明 => struct { ... // }   Foo_t;
变量Foo_t的类型为struct { ... // } ;
=> "typedef   struct { ... // }   Foo_t "中Foo_t是"struct { ... // }"的一个typedef-name。这里struct {...//}是一个无"标志名称(tag name)"的结构体声明。

[例9]
typedef      struct { ... // }   Foo_t[1];

分析：
去掉typedef ，得到正常变量声明 => struct { ... // }   Foo_t[1];
变量Foo_t的类型为包含一个元素的struct { ... // }类别的数组类型;
=> 这样一来，Foo_t在typedef定义后实际上就变成了一个struct { ... // }数组类型。要问实际编程中会这么用typedef吗？你还别说，这还是C语言常用的一个小技巧，如果你有机会看到jmp_buf的类型定义，你就会发现jmp_buf在很多系统实现中也是如此定义的，大约类似：typedef struct XX {...} jmp_buf[1]; 这样做的目的大致是这样的：如果你在函数里定义了一个char a[n]；那么a和&a作为参数传入某个函数时是等价的。看似传值，实则传址，在被调用函数中通过参数可直接修改数组a的元素的内容。另外这么做的目的是否是为了让代码更符合某些人的口味我还不得而知。

参考资料：
1、"ISOIEC-98991999(E)--Programming Languages--C"之Page 123;
2、C语言参考手册(中文版) 之 Page 119

早上在写代码时遇到这样一个问题：即如何在一个拥有多行的宏定义中做注释？，这里把方法演化的过程贴出来，可能对某些朋友有些借鉴意义。

宏定义高深莫测，而且是比较细节的东西，详细说明请参见"C参考手册"之类的书籍。

在我的代码中，我大致要做这样一个简单的事情：printf("%s%s%s\n", "hello", "macro", "yeah!"); "%s%s%s\n"这个字符串中每一项输出都有一定的含义，而且在真实代码里，这个串中的输出项可不止3个，所以一个直接的想法就是将其定义为一个宏。

#define STR_OUTPUT_FORMAT_V0  "%s%s%s\n"
printf(STR_OUTPUT_FORMAT_V0, "hello ", "macro, ", "yeah!");
程序输出：hello macro, yeah!

由于真实代码中这个串很长，所以打算美化一下格式，定义成下面的样子：
#define STR_OUTPUT_FORMAT_V1  "%s\
                               %s\
                               %s\n"
printf(STR_OUTPUT_FORMAT_V1, "hello ", "macro, ", "yeah!");
程序输出：hello                                macro,                                yeah!

这样的定义显然不对，也在我意料之中，续行符将空格也续到格式串中了，导致输出的结果中带有大量空格。

改进一下，利用C语言的字符串自动连接语法。
#define STR_OUTPUT_FORMAT_V2  "%s"\
                              "%s"\
                              "%s\n"
printf(STR_OUTPUT_FORMAT_V2, "hello ", "macro, ", "yeah!");
程序输出：hello macro, yeah!

现在的问题是如何在这样一个多行的宏定义里加入注释，字段含义特殊，加上注释有利于以后维护以及别人阅读你的代码，否则一堆%s%s，让人看了就头痛。先这么加试试：
#define STR_OUTPUT_FORMAT_E1  "%s"\   /* comment1 */
                              "%s"\   /* comment2 */
                              "%s\n"  /* comment3 */
printf(STR_OUTPUT_FORMAT_E1, "hello ", "macro, ", "yeah!");
我们得到的结果：编译错误。
通过gcc -E 选项我们看到，宏替换后的代码:
                              "%s"\
                              "%s\n"
int main() {
        printf("%s"\, "hello ", "macro, ", "yeah!");
}

由于没有续行符在注释前面，所以宏定义的后两行实际上并没有被包含在宏定义中，就像没有暂住证的人一样，被GCC这个"警察"逮个正着。

继续改进：
#define STR_OUTPUT_FORMAT_V3  "%s"   /* comment1 */ \
                              "%s"   /* comment2 */ \
                              "%s\n"  /* comment3 */
printf(STR_OUTPUT_FORMAT_V3, "hello ", "macro, ", "yeah!");
程序输出：hello macro, yeah!
显然预编译器忽略宏定义中的注释以及空格，STR_OUTPUT_FORMAT_V3就完全符合我的要求了。

当然，很多人不建议使用宏，特别是C++的Fans，宏也的确有很多弊端，这里也有替代方法：
const char *str_output_format = "%s"    /* comment1 */
                                 "%s"    /* comment2 */
                                 "%s\n"; /* comment3 */
printf(str_output_format, "hello ", "macro, ", "yeah!");
程序输出：hello macro, yeah!

用一个字符串变量代替格式宏，还可以避免上述由于在宏中做注释带来的一系列问题。

'自然数对'是这样的一对自然数，他们的和与差的结果都是平方数，比如：自然数对32和68，根据定义32+68 = 100 = 10^2，68-32 = 36 = 6^2。现在的题目是：根据输入的两个100以内的自然数，打印出这两个整数之间的所有自然数对。

这道题不难，而且限制了范围，在两个100以内的自然数区间，很多人马上就能给出程序。这道题的有两个点需要思考：一个是关于平方数的判断；另一个就是两个数的组合控制。

关于平方数的判断，多数人采用的方法就是利用现成的sqrt函数来做判断。当然也有人和我想的一样，采用表查询的方法。因为题目明确限制了范围是两个100以内的数，试想一下100以内最大的两个数的和99+98=197，也就是说100以内自然数对的和如果是平方数的话，肯定是下面集合中的一个，这个集合为{1,4,9,16,25,36,49,64,81,100,121,144,169,196}。那么既然我们已经肯定了如此，我们还何必去做sqrt操作呢，直接在这个集合中查找不就行了，这也是一种最简单的查表法，至于表的存储结构和查询算法可自定义(影响性能)。

关于数的组合控制，很多人都会使用两层循环，这没错。除了循环，递归也是一个不错的方法。简单的看了下，这个例子还是比较符合递归的两个条件的：
1、有basis case；
2、规模逐渐缩小；

基于上述两点，这里给出一个简单的实现：
int square_number_tbl[] = {1,4,9,16,25,36,49,64,81,100,121,144,169,196};

int is_natural_number_pair(int a) {
    int i;
    //简单的顺序查找
    for (i = 0; i < sizeof(square_number_tbl)/sizeof(square_number_tbl[0]); i++) {
        if (square_number_tbl[i] == a) return 1;
    }
    return 0;
}

//find natural number pair
void find_nnp(int a, int b) {
    int i;
    if (b - a <=0) { //basis case
        return;
    }
    
    i = a;
    do {
        if (is_natural_number_pair(b+i) && is_natural_number_pair(b-i)) {
            printf("%d, %d\n", b, i);
        }
        i++;
    }while (i <= b);
    return find_nnp(a, b-1);//recursive invoke
}

int main() {
    int a, b;  //we suppose that b is greater than a, and both are less than 100
    printf("Please Input two integrals (1，100):");
    scanf("%d %d",&a,&b);
    
    find_nnp(a, b);
}

完成这个后，突然又想到的一个方法：根据输入的范围[a, b]动态构造一张矩阵，矩阵的x轴方向和y轴方向的都是由a->b的数轴。矩阵中的数值按如下方式初始化M(x, y) = x + y; M(y, x) = y - x; (y > x)；初始化完矩阵后，对矩阵进行一次扫描，并在is_natural_number_pair的帮助下找到所有自然数对。