C语言常用库函数实现（一）_内存拷贝

  库函数的实现也是面试中的常考题，因为这是最能体现C语言功底的。
一、strcpy与strncpy
    先看一下函数的原型：
       
  strcpy函数可以按如下的方式实现：
  

char * strcpy(char *strDest, const char *strSrc)
{
    if (strDest == NULL)
       || (strSrc == NULL)
       printf("Input parameter invalid!\n");

    char *strDestCopy = strDest;

    while ((*strDest++ = *strSrc++) != '\0');

    return strDestCopy;
}

   关于这个库函数的使用还需做如下的说明：
1. 为什么要返回char *
答：为了实现链式表达式  e.g int length = strlen(strcpy(strDest, "Hello world!"));
2. 由于strcpy一直拷贝到‘\0’才结束，所以要注意以下几点：
    首先是越界的问题，看如下的例子：
     char buf[10];
     strcpy(buf, "Hello world!");
   这个例子提醒调用strcpy时一定要确保目标内存足够大
  再看下面这个例子：
     char buf[10] = "123456789"
     char str[4] = "hell";
     strcpy(buf,  str);
   由于str的空间不够，故其没有以'\0'结尾，则拷贝时一定会出现越界错误，这个例子告诉我们调用strcpy时要检查源拷贝字符串是否以'\0'结尾 
 总之，“确保不会写越界”是调用者的责任，调用者在调用之前一定要仔细检查源字符串与目标字符串是否以'\0'结尾，如果不注意这一点，strcpy函数很有可能发生“缓冲区溢出错误(buffer overflow)”，这一错误如果被恶意用户利用，那引起的问题就会非常严重，看下面的例子：
      void foo(char *str)
      {
            char buf[10];
            strcpy(buf, str);
            .......
      }
如果str指向的字符串超过10个字节，而像上面的代码所示没有任何检查工作，则会导致写越界，这样的写越界错误会覆盖保存在栈帧上的返回地址，使函数返回时跳转到非法地址，出现段错误，如果这样还算好，更严重的是如果恶意用户利用了这个Bug，使函数返回时跳转到一个事先设好的地址，执行事先设好的指令，如果设计得巧妙甚至可以启动一个Shell，然后随心所欲执行任何命令，可想而知，如果一个用root权限执行的程序存在这样的Bug，被攻陷了，后果将很不堪设想，因此写代码时这个问题一定要给予充分重视。
3. src与dest所指向的内存空间不能有重叠（凡是有指针参数的C标准库函数都有这条要求）
      char buf[10] = "Hello";
      strcpy(buf, buf+1);  
  这样的代码是有问题的

Man Page中给出了strncpy的定义：

char * strncpy(char *dest, const char *src, size_t n)
{
    size_t i;

    for (i = 0; i < n && src[i] != '\0'; i++)
         dest[i] = src[i];

    for ( ; i < n ; i++)
         dest[i] = '\0';

    return dest;
}

从函数的定义可以知道，如果src字符串全部拷完了不足n个字节，那么还差多少个字节就补多少个'\0'，但是函数并不保证dest一定以'\0'结束，当src字符串的长度大于n时，不但不补多余的'\0'，连字符串的结尾'\0'也不拷贝。
简单点说就是strnpy并不保证dest一定以'\0'结尾，因此我们使用时一定要特别注意，推荐下面的使用方式：
     strncpy(buf, str, n);
     if (n > 0)
        buf[n-1] = '\0';
二、memcpy与memmove
  还是先看一下这两个函数的原型，这两个函数仍然都包含在string.h头文件中：
        void *memcpy(void *dst, const void *src, size_t count);
     void *memmove(void *dst, const void *src, size_t count);
  这两个函数实现的功能都是拷贝从src所指向的内存位置，拷贝count字节的字符到dst所指向的内存位置，唯一的区别是当内存发生部分重叠时，memmove保证拷贝结果的正确性
   还要说明以下两点：
  1. 这两个函数不关心src与dst所指向内存的数据类型（所以指针为void型），仅对所指内存内容进行二进制拷贝
  2. 这两个函数不检测字符串结束符'\0'，等，仅做count字节的拷贝
事实上为了效率，这两个函数均是用汇编语言实现的，但是研究它们的实现过程是非常有趣的，这里就分别来看一下，首先是memcpy函数：

void* memcpy(void *dst, const void *src, size_t count)
{
    //安全检查
    assert( (dst != NULL) && (src != NULL) );

    unsigned char *pdst = (unsigned char *)dst;
    const unsigned char *psrc = (const unsigned char *)src;

    //防止内存重复
    assert(!(psrc<=pdst && pdst<psrc+count));
    assert(!(pdst<=psrc && psrc<pdst+count));

    while(count--)
    {
        *pdst = *psrc;
        pdst++;
        psrc++;
    }
    return dst;
}

    第10句和第11句是为了检测内存覆盖，这里把它的含义大概说明一下，如果psrc <= pdst，说明psrc在低地址，pdst在高地址，则如果
pdst < psrc + count，说明两段内存是重叠的；同样的道理，pdst <= psrc, 说明pdst在低地址，psrc在高地址,  则psrc < pdst + count说明两段内存重叠了。
  上面的程序实现了memcpy函数的基本功能，但事实上memcpy是一个高效的内存拷贝函数，它的内部实现并非是一个字节一个字节的拷贝，仅仅仅在地址不对齐的情况下，memcpy才会一个字节一个字节的拷贝内存内容，当地址对齐时，memcpy会使用CPU字长(32bit或64bit)来拷贝，而且还会根据CPU类型选择一些优化的指令。再看下面的优化代码：

void *mymemcpy(void *dst,const void *src,size_t num)
{
    assert((dst!=NULL)&&(src!=NULL));
    assert(!(src <= dst && dst < src + num);
    assert(!(dst <= src && src < dst + num);

    int slice = num % 4;//首先按字节拷贝
    int wordnum = num/4;//计算有多少个32位，按4字节拷贝

    const int * pintsrc = (const int *)src;
    int * pintdst = (int *)dst;

    while (slice--)*((char *)pintdst++) =*((const char *)pintsrc++);

    while(wordnum--)*pintdst++ = *pintsrc++;  //后面的地址应当是对齐的

    return dst;
}

注意：要真实模拟系统的状况，必须是先拷贝零散的字节(slice长)，因为不对齐的情况是由于这些零散字节的存在。
前面说过，memmove与memcpy相比，唯一的区别就是可以处理内存局部重叠的情况，我们于是看一下内存局部重叠的两种情况：
      
第一种情况下，拷贝重叠的区域不会出现问题，内容均可以正确的被拷贝。
第二种情况下，问题出现在右边的两个字节，这两个字节的原来的内容首先就被覆盖了，而且没有保存。所以接下来拷贝的时候，拷贝的是已经被覆盖的内容，显然这是有问题的。     
有了这个直观的认识后，可以写出如下的代码：

void *mymemmove(void *dst, const void *src, size_t n)
{
    char temp[n];
    int i;
    char *d = dst;
    const char *s = src;

    for (i = 0; i < n; i++)
        temp[i] = s[i];
    for (i = 0; i < n; i++)
        d[i] = temp[i];

    return dest;
}

这段代码的思路非常简单，既然字节覆盖是因为原先的内容被覆盖造成的，那就把原先的内容先保存下来，所以开辟一段大小为n的内存空间，先把src所指向的内容保存下来，然后再拷贝到dst中。
下面这段实现是VC的源码：

void * __cdecl memmove ( void * dst, const void * src, size_t count )
{
        void * ret = dst;

        if (dst <= src || (char *)dst >= ((char *)src + count)) {
                /*
                 * Non-Overlapping Buffers
                 * copy from lower addresses to higher addresses
                 */
                while (count--) {
                        *(char *)dst = *(char *)src;
                        dst = (char *)dst + 1;
                        src = (char *)src + 1;
                }
        }
        else {
                /*
                 * Overlapping Buffers
                 * copy from higher addresses to lower addresses
                 */
                dst = (char *)dst + count - 1;
                src = (char *)src + count - 1;

                while (count--) {
                        *(char *)dst = *(char *)src;
                        dst = (char *)dst - 1;
                        src = (char *)src - 1;
                }
        }

        return(ret);
}

如果看注释，这段代码是很容易懂的，dst <= src(表明目标地址为低地址，源地址为高地址，对应于图中第1种情况), dst >= src + count(表明没有内存局部重叠），这种情况即使用memcpy拷贝结果也是不会有问题的，所以按字节拷贝即可。else语句对应于图中的第二种情况, 则从高地址向低地址拷贝，这样就规避了内容被覆盖的问题，也能得到正确的结果。