如何修复strcpy函数，以便检测重叠字符串

Question

在一次面试中，我被要求实现strcpy的函数，并修复它以正确处理重叠字符串。我的实现很简单，如下所示。请问如何修改它：

1. 使其能够检测到重叠字符串，并且
2. 在检测到重叠后，如何处理重叠并继续进行拷贝？

---

char* my_strcpy(char *a, char *b) {

     if (a == NULL || b == NULL) {
         return NULL;
     }
     if (a > b) {
         //we have an overlap?
         return NULL;
     }
     char *n = a;

     while (*b != '\0') {
         *a = *b;
         a++;
         b++;
     }
     *a = '\0';
     return n;
}

int main(int argc, char *argv[])
{
    char str1[] = "wazzupdude";
    char *after_cpy = my_strcpy(str1 + 2, str1);
    return 0;
}

---

编辑：

根据@Secure的答案，可能的一种实现方法是：

char* my_strcpy(char *a, char *b) {

    if (a == NULL || b == NULL) {
        return NULL;
    }

    memmove(a, b, strlen(b) + 1);
    return a;
}

如果我们不依赖于 memmove，那么

char* my_strcpy(char *a, char *b) {

    if (a == NULL || b == NULL) {
        return NULL;
    }

    if (a == b) {
        return a;
    }

    // case1: b is placed further in the memory
    if ( a <= b && a + strlen(a) > b ) {
        char *n = a;

        while(*b != '\0') {
            *a = *b;
            a++; b++;
        }
        *a = '\0';
        return n;
    }

    // case 2: a is further in memory
    else if ( b <= a && b + strlen(b) > a ) { 
        char *src = b + strlen(b) - 1; // src points to end of b
        char *dest = a;

        while(src != b) {
            *dest = *src;
            dest--; src--;  // not sure about this..
        }
        *a = '\0';
        return a;
    }
}

- user7

---

a > b 如何“检测重叠”？它只是测试两个地址。 - Blagovest Buyukliev

@Steve：没错——“天下没有免费的午餐”；虽然首先做两份副本与免费午餐相去甚远 :-) - pmg

实际上...我首先会依赖于memmove，如果面试官要求详细了解或坚持不让我使用memmove，我才会给出详细的实现方式...顺便问一下，上面的实现方式正确吗？ - user7

@安全：如果它们不重叠的情况下，将以与case1相同的方式实现。然而，我无法想象第二种情况（a在内存中进一步）...因此出现了编码错误。我已经进行了一些编辑，但如果您能帮助我想象第二种情况，我将不胜感激。 - user7

注意：如果a，b指向C字符串，则不需要使用if(a == NULL || b == NULL){ return NULL; }。 - chux - Reinstate Monica

Answer 1

没有一种可移植的方法可以检测这个问题。您必须进行指针比较，而这些指针比较仅在同一对象内定义。也就是说，如果两个字符串不重叠并且实际上是不同的对象，则指针比较会导致未定义的行为。

我建议使用标准库来处理这个问题，使用memmove(a, b, strlen(b) + 1)。

编辑：

正如Steve Jessop在评论中指出的那样，在这种情况下实际上有一种可移植但缓慢的方法来检测重叠。将b中的每个地址与a的第一个和最后一个地址进行相等性比较。等于号==的相等性比较总是被明确定义的。

因此，您可以像这样做：

l = strlen(b);
isoverlap = 0;
for (i = 0; i <= l; i++)
{
    if ((b + i == a) || (b + i == a + l))        
    {
        isoverlap = 1;
        break;
    }
}

编辑2：案例2的可视化

您有以下数组和指针：

S t r i n g 0 _ _ _ _ _ _ _
^       ^
|       |
b       a

请注意，b + strlen(b) 的结果是指向终止符 \0 的指针。应该从它的后一个位置开始，否则需要额外处理边界情况。可以将指针设置在那里，但是不能对其进行取值操作。

src = b + strlen(b) + 1;
dst = a + strlen(b) + 1;

S t r i n g 0 _ _ _ _ _ _ _
^       ^     ^       ^  
|       |     |       |
b       a     src     dst

现在是复制循环，它也会复制\0。

while (src > b)
{
    src--; dst--;
    *dst = *src;
}

第一步得到这个结果：

src--; dst--;

S t r i n g 0 _ _ _ _ _ _ _
^       ^   ^       ^  
|       |   |       |
b       a   src     dst

*dst = *src;

S t r i n g 0 _ _ _ 0 _ _ _
^       ^   ^       ^  
|       |   |       |
b       a   src     dst

依此类推，直到 src 变成等于 b 为止：

S t r i S t r i n g 0 _ _ _
^       ^              
|       |            
b       a          
src     dst

如果你想要更加“黑客风格”，你可以进一步压缩它，但我不建议这样做：

while (src > b)
    *(--dst) = *(--src);

- Secure

---

不是说重叠不能被可移植地检测到。有一种令人震惊的低效方法。这适用于memmove，但我相信它可以适应strcpy：https://dev59.com/questions/Bm865IYBdhLWcg3wCp9A#4023563 - Steve Jessop

你必须进行指针比较，而这些只在同一对象内定义。-我该如何检查两个指针是否指向同一个对象（在这种情况下是数组）？ - user7

如果 a + strlen(a) == b + strlen(b)，则字符串重叠。 - Carl Norum

@szulat：无关指针的比较不仅会产生未指定的结果。一些编译器可能会推断，因为标准对于比较无关指针应该发生什么没有任何要求，所以标准对于程序在给定会导致这样的指针被比较的输入时应该做什么也没有任何要求。这样的编译器还可以进一步推断，如果一个条件只有在给定会调用未定义行为的输入时才可能为真，那么编译器可以假设该条件总是为假。因此，不存在安全的未定义行为。 - supercat

1. src = b + strlen(b) + 1; dst = a + strlen(b) + 1; 应该改为 src = b + strlen(b); dst = a + strlen(b);
2. 当 b>a 且 a+strlen(b) > b 时是错误的。

- John Zhang

Answer 2

如果您预计字符串会重叠，可以使用memmove()函数。

char* my_strcpy(char *a, char *b)
{
    memmove(a, b, strlen(b) + 1);
    return a;
}

- brain

---

这是考虑到一个字符等于一个字节的情况下的计算。我会将 strlen(b) + 1 改为 ( strlen(b) + 1 ) * sizeof( char )。 - Baltasarq

sizeof(char)始终精确为一个字节。 - brain

是的，但是memmove期望字节而不是字符，即使它们偶然具有相同的大小。无论如何，我只是说“我会”。 - Baltasarq

“memmove() 函数期望的是字节而不是字符”这句话有误导性。在 C 语言中，memmove() 函数期望的是以字符为单位的大小，而在 C 语言中，“字节”和“字符”的大小是相同的。“memmove函数从s2指向的对象中复制n个字符到s1指向的对象中。C11 '7.24.2.2'”。 - chux - Reinstate Monica

Answer 3

注意：这里的b是源字符串的地址，a是目标地址。

如果a > b，并不一定会有重叠。如果

(a <= b && a+strlen(a) >= b) || (b <= a && b+strlen(b) >= a)

如果出现重叠，那么你需要注意。除了为了面试而检测重叠外，a > b 对于 strcpy 来说应该是可以的。其思想是这样的：

如果 b 在内存中更远（b > a），那么你可以正常地将 b 复制到 a 中。部分 b 将被覆盖，但你已经过了那一部分。

如果 a 在内存中更远（a > b），这意味着通过在 a 的第一个位置上写入内容，你可能已经覆盖了具有更高索引的 b 中的某个位置。在这种情况下，你应该反向复制。因此，你应该从 strlen(b)-1 到 0 进行复制，而不是从索引 0 到 strlen(b)-1。

如果你对此感到困惑，请在纸上绘制两个重叠的数组，并尝试从数组的开头和结尾分别复制。在 a > b 和 a < b 两种情况下都试一试。

请注意，如果 a == b，则你不需要实际复制任何内容，可以直接返回。

编辑：我不确定，但是阅读其他解决方案，似乎这个答案可能不完全可移植。请注意。

- Shahbaz

---

如果 a==b，你甚至只需要返回 :-)。 strcpy 接受指向非易失性的指针，因此实际上没有必要触摸内存。话虽如此，为了优化那种荒谬的情况而添加代码是不值得的。 - Steve Jessop

@chux，你考虑了终止的NUL吗？ - Shahbaz

Answer 4

if a > b; then
    copy a from the beginning
else if a < b; then
    copy a from the ending
else // a == b
    do nothing

你可以参考 memmove 的实现，它与我所说的很相似。

- Mu Qiao

---

当 a 和 b 在不同的对象中时，a > b 存在 UB 的风险 - 因此不是一种可移植的解决方案。 - chux - Reinstate Monica

Answer 5

即使不使用关系指针比较、memmove或其等效物，也可以编写一个版本的strcpy，在非重叠情况下，它将作为strlen和memcpy执行，在重叠情况下，它将作为自上而下的复制执行。关键在于利用这样一个事实：如果读取目标的第一个字节并将其替换为零，调用源的strlen并将返回的值加到源指针上将产生一个合法的指针，该指针将在“棘手的重叠”情况下等于目标的起始位置。如果源和目标是不同的对象，则可以安全地计算“source plus strlen”指针，并观察其与目标是否相等。

如果将字符串长度添加到源指针中产生目标指针，那么将零字节替换为早先读取的值，并在目标上调用strlen将允许代码确定源和目标字符串的结束地址。此外，源字符串的长度将指示指针之间的距离。如果此值很大（可能大于16左右），则代码可以将“move”操作高效地分成自上而下的一系列memcpy操作。否则，可以使用自上而下的单字节复制操作循环或使用一系列“memcpy到源到缓冲区”/“memcpy缓冲区到目标”操作来复制字符串[如果大型memcpy的每字节成本小于单字符复制循环的一半，则使用~256字节的缓冲区可能是一个有用的优化]。

- supercat

---

"目的地的第一个字节被读取并替换为零。" --> 有趣。 - chux - Reinstate Monica

Answer 6

if (a>= b && a <= b+strlen(b))) || (b+strlen(b) >= a && b+strlen(b) <= a + strlen(b))

(*) 你应该缓存 strlen(b) 以提高性能。 功能：
检查 a+len [a地址+额外len字节] 是否在字符串内，或者 a [a地址] 是否在字符串内，这些是字符串重叠的唯一可能性。

- amit

---

当a和b在不同的对象中时，a>= b存在未定义行为，因此不是一种可移植的解决方案。 - chux - Reinstate Monica

Answer 7

我最近在面试中被问到这个问题。我们不需要“检测”重叠。我们可以以这样的方式编写strcpy，以处理重叠地址。关键是从源字符串的末尾开始复制，而不是从开头开始。

以下是一个快速代码示例。

void str_copy(const char *src, char *dst) 
{
    /* error checks */

    int i = strlen(a); /* may have to account for null character */

    while(i >= 0) 
    {
        dst[i] = src[i];  
        i--; 
    }
}

编辑：这仅适用于 a < b 的情况。对于 a > b，请从开头复制。

- Bhaskar

---

在出现重叠字符串的情况下，问题仍然存在。就像memcpy一样，您应该根据目标复制的地址是否低于或高于源来从开头或末尾进行复制。 - Shahbaz

1. 代码无法编译。
2. 建议重新编写答案/代码，使用src dest而不是a b。
3. strlen（）返回类型size_t，但然后size_t i与while(i>=0)测试有问题，这个测试总是为真。

- chux - Reinstate Monica

Answer 8

如果这两个字符串重叠，那么在复制时你会超过原始的 a 或 b 指针。

假设 strcpy(a, b) 大致意味着 a <- b，即第一个参数是复制的目标，那么你只需要检查复制指针是否到达了 b 的位置。

你只需要保存 b 的原始位置，在复制时检查是否已经到达该位置。此外，如果已经到达该位置，则不要写入尾随零。

 char* my_strcpy(char *a, const char *b)
 {

    if ( a == NULL
      || b == NULL )
    {
        return NULL;
    }

    char *n = a;
    const char * oldB = b;

    while( *b != '\0'
       &&  a != oldB )
    {
        *a = *b;
        a++;
        b++;
    }

    if ( a != oldB ) {
        *a = '\0';
    }

    return n;
 }

这个算法仅停止了复制。或许你想做一些其他的事情，比如标记错误条件或在前一个位置添加字符串结束标记（尽管静默失败（就像当前算法一样）并不是最好的选择）。

希望这能有所帮助。

- Baltasarq

Answer 9

这个SO条目已经比较老了，但我目前正在处理一段使用strcpy()复制重叠字符串的旧代码。日志输出中缺少字符。我决定使用以下紧凑的解决方案，逐个char地进行复制。

static char *overlapped_strcpy(char *dest, const char *src)
{
  char *dst = dest;

  if (dest == NULL || src == NULL || dest == src)
    return dest;

  do {
    *dst++ = *src;
  } while (*src++);

  return dest;
}

---

编辑：

正如@Gerhardh所指出的那样，上面的代码仅在dest <= src的情况下有效（我只需要解决这种情况）。对于dest > src的情况，它更加复杂。然而，从后面复制，就像其他答案已经提到的那样，会导致成功。例如：

if (dest <= src) {
  /* do the above */
} else {
  int i = (int)strlen(src);
  while (i >= 0) {
    dst[i] = src[i];
    i--;
  }
}

- Andreas

---

这个如何处理重叠的部分？假设 strlen(src) == 20 并且 dest=src+5。 - Gerhardh

@Gerhardh 我只需要解决strcpy(posPtr, posPtr+2);。相反的情况会很麻烦。 - Andreas

检测和处理混乱将是这样一个函数的全部意义。 ;) - Gerhardh

当 dest 和 src 在不同的对象中时，dest <= src 存在 UB 风险 - 因此不是一种可移植的解决方案。 - chux - Reinstate Monica