就目前而言,在编程领域中,C语言的运用非常之多,它兼顾了高级语言的汇编语言的优点,相较于其它编程语言具有较大优势。 以下为译文: 在所有标准C语言<string.h>头文件中声明的字符串处理函数中,最常用的是那些用来复制和连接字符串的函数。这两组函数都将字符从一个对象复制到另一个对象,并且都返回它们的第一个参数:指向目标对象的起始指针。这种返回值的方式是导致函数效率低下的一个原因,而这正是本文要探讨的主题。 本文中展示的示例代码仅仅用于说明目的。它们可能包含细微的错误,不应该被视为最佳代码实践。 这种返回函数的第一个参数的设计,有时候会被不明白其用途的用户所质疑。这样的例子在StackOverflow网站上有不少,例如关于strcpy()返回值,或者C语言的strcpy为什么返回它的参数?的讨论。简单的答案是,这是一个历史性的意外。函数的第一个子集是由Unix第七版在1979年引入的,它由strcat、strncat、strcpy和strncpy函数组成。尽管这四个函数都在Unix的各种版本中使用,但通常情况下,对这些函数的调用却没有使用它们的返回值。尽管这些函数可以同样很容易地定义为返回一个指针来指向最后一个复制的字符(或它的后一位),而且事实证明这种做法也非常有用。 两个或多个字符串的连接操作的最佳复杂度和字符数量成线性关系。但是,如上所述,让函数返回指向目标字符串的指针会导致操作的效率明显低于最佳效率。该函数遍历源字符串序列和目标字符串序列,并获取指向这两个序列末尾的指针。该指针指向函数(strncpy除外)附加到目标序列上的字符串结束符NUL('\0')处或它的后一位。但是,如果返回的指针指向第一个字符而不是最后一个字符(或它的下一个字符),NUL结束符的位置会丢失,必须在需要时重新计算。这种做法的低效率可以在将两个字符串s1和s2连接到目标缓冲区d中的示例中得到说明。将一个字符串添加到另一个字符串的惯用方法(虽然远非理想)是调用strcpy和strcat函数,如下所示: strcat (strcpy (d, s1), s2); 为了执行这个连接操作,除了同时发生的相应地在d上的传递之外,一次在s1的传递和一次在s2上的传递是必须要执行的操作,但是上面的调用在s1上进行了两次传递。让我们把这些调用分成两个语句。
必须指出的是,除了效率低下之外,strcat和strcpy还因其缓冲区溢出的问题而臭名昭著,因为它们都对复制字符的数量不做任何限制。 克服局限性的尝试 当源字符串的长度未知且目标字符串大小固定时,遵循一些流行的安全编码准则来将连接结果限制为目标区大小实际上会导致两个冗余的传递。例如,按照CERT关于安全使用strncpy()和strncat() 的建议,并且目标区的大小是dsize字节,我们可能会得到以下代码。 strncpy (d, s1, dsize - 1); // pass 1 over s1 plus over d up to dsize - 1 为了避免一些冗余,程序员有时会选择先计算字符串长度,然后使用memcpy,如下所示。这种方法仍然效率不高,而且更容易出错,并且代码难以阅读和维护。
出于对代码复杂性和可读性的担心,程序员们有时会使用snprintf函数进行字符串连接。 snprintf (d, dsize, '%s%s', s1, s2); 一些编译器(如GCC和Clang)试图通过将非常简单的sprintf和snprintf调用转换为strcpy或memcpy调用以提高效率,避免了对I/O函数的某些调用的开销(请参阅这个在线示例https:///z/RaWkyd)。然而,由于C库中没有等价的字符串函数,而只有当snprintf调用被证明不会导致输出的截断时,转换才会完成,因此对snprintf的相应转换很少能够发生。memcpy本身不合适,因为它复制的字节数与指定的字节数完全相同,strncpy也不适合,因为它把目标字符串的最后的NUL结束符之后的位数都覆盖了。 由于字符串的冗余传递次数,将snprintf调用转换为strlen和memcpy调用序列产生的额外开销,也被视为得不偿失。在这个页面上,标题为Better builtin string functions部分列出了GCC优化器在这方面的一些限制,以及改进它的一些折中措施。 为了帮助解决这个问题,在过去很多年里出现了很多超出标准C的库解决方案。POSIX标准包括stpcpy和stpncpy函数,这两个函数的实现方法是如果找到NUL结束符,则返回指向该字符的指针。这些函数可以用来缓解上面提到的麻烦和低效率。
stpcpy (stpcpy (d, s1), s2);
为了应对针对strcpy和strcat函数的弱点以及上面讨论的strncpy和strncat的一些缺点的缓冲区溢出攻击,OpenBSD项目在20世纪90年代末引入了一对替代API(strlcpy和strlcat),旨在使字符串复制和连接更加安全(http://www./jtc1/sc22/wg14/www/docs/n2349.htm)。 size_t strlcpy (char* restrict, const char* restrict, size_t);
POSIX还定义了另一个函数memccpy,该函数具有上面讨论过的所有理想属性,可以用来解决上面的问题。 void* memccpy (void* restrict dst, const void* restrict src, int c, size_t n);
因此,可以使用memccpy重写上面的第一个示例(strcat(strcpy(d,s1,s2))以避免在字符串上进行任何冗余传递,如下所示。请注意,这里使用SIZE_MAX作为大小限制,这个重写无法避免原始示例中存在的目标缓冲区溢出的风险,因此应避免。
char *p = memccpy (d, s1, '\0', dsize); 选择一个解决方案 如果字符串函数返回指向最后一个存储字符或它的后面一位的指针,而不是返回其第一个参数的值,则上面讨论的效率问题可以得到解决。然而,在现有函数使用了接近半个世纪后,对其进行更改是不太可行的。 尽管解决现有C标准字符串函数的问题是不可行的,但是可以通过添加一个或多个不受相同限制的函数来在新代码中缓解这个问题。由于C标准的章程正在对现有的实践进行编纂整理,所以C语言标准化委员有义不容辞的责任调查这种功能是否已经存在于流行的实现中,如果已经存在,则应该考虑采纳它们。如上文提到的这几种解决方案。 在上面提到的解决方案中,memccpy函数是最通用和最高效的,它由ISO 标准支持。即使在POSIX标准实现之外,它的应用范围最广,争议最小。 相比之下,stpcpy和stpncpy函数的通用性较差,stpncpy函数会产生不必要的开销,因此无法达到既定的目标。这些函数在C2X中仍然值得采用,以提高移植性。详情请参阅N2352–将stpcpy和stpncpy添加到C2X中的提案。 OpenBSD的strlcpy和strlcat函数虽然是最优的,但是它们的通用性较差,支持范围也较低,而且没有得到ISO标准的指定。 memccpy函数不仅存在于Unix实现的子集中,它还由另一个名为ISO/IEC 9945的ISO标准指定。ISO/IEC 9945还有另外一个名字,也即大家熟知的IEEE Std 1003.1, 2017版,或者简言之- POSIX: memccpy,在那里它是作为XSI扩展提供给C的。这个函数可以追溯到System V接口定义第1版(SVID1),最初于1985年发布。 memccpy甚至可以用于UNIX和POSIX以外的实现,例如:
下面提供了一个简单(但是效率低下)的memccpy参考实现:
void* memccpy (void* restrict dst, const void* restrict src, int c, size_t n)
将memccpy函数和本文讨论的其他标准函数(除了strlcpy和strlcat),以及另外两个标准函数纳入下一个C编程语言修订版的提议于2019年4月提交给了C语言标准化委员会(见 3, 4, 5和 6)。委员会最终决定采纳memccpy函数,但否决了其余提案。 原文:https://developers./blog/2019/08/12/efficient-string-copying-and-concatenation-in-c/ 【END】 |
|