就目前而言,在編程領(lǐng)域中,C語(yǔ)言的運(yùn)用非常之多,它兼顧了高級(jí)語(yǔ)言的匯編語(yǔ)言的優(yōu)點(diǎn),相較于其它編程語(yǔ)言具有較大優(yōu)勢(shì)。
在所有標(biāo)準(zhǔn)C語(yǔ)言<string.h>頭文件中聲明的字符串處理函數(shù)中,最常用的是那些用來復(fù)制和連接字符串的函數(shù)。這兩組函數(shù)都將字符從一個(gè)對(duì)象復(fù)制到另一個(gè)對(duì)象,并且都返回它們的第一個(gè)參數(shù):指向目標(biāo)對(duì)象的起始指針。這種返回值的方式是導(dǎo)致函數(shù)效率低下的一個(gè)原因,而這正是本文要探討的主題。
本文中展示的示例代碼僅僅用于說明目的。它們可能包含細(xì)微的錯(cuò)誤,不應(yīng)該被視為最佳代碼實(shí)踐。
這種返回函數(shù)的第一個(gè)參數(shù)的設(shè)計(jì),有時(shí)候會(huì)被不明白其用途的用戶所質(zhì)疑。這樣的例子在StackOverflow網(wǎng)站上有不少,例如關(guān)于strcpy()返回值,或者C語(yǔ)言的strcpy為什么返回它的參數(shù)?的討論。簡(jiǎn)單的答案是,這是一個(gè)歷史性的意外。函數(shù)的第一個(gè)子集是由Unix第七版在1979年引入的,它由strcat、strncat、strcpy和strncpy函數(shù)組成。盡管這四個(gè)函數(shù)都在Unix的各種版本中使用,但通常情況下,對(duì)這些函數(shù)的調(diào)用卻沒有使用它們的返回值。盡管這些函數(shù)可以同樣很容易地定義為返回一個(gè)指針來指向最后一個(gè)復(fù)制的字符(或它的后一位),而且事實(shí)證明這種做法也非常有用。
兩個(gè)或多個(gè)字符串的連接操作的最佳復(fù)雜度和字符數(shù)量成線性關(guān)系。但是,如上所述,讓函數(shù)返回指向目標(biāo)字符串的指針會(huì)導(dǎo)致操作的效率明顯低于最佳效率。該函數(shù)遍歷源字符串序列和目標(biāo)字符串序列,并獲取指向這兩個(gè)序列末尾的指針。該指針指向函數(shù)(strncpy除外)附加到目標(biāo)序列上的字符串結(jié)束符NUL('\0')處或它的后一位。但是,如果返回的指針指向第一個(gè)字符而不是最后一個(gè)字符(或它的下一個(gè)字符),NUL結(jié)束符的位置會(huì)丟失,必須在需要時(shí)重新計(jì)算。這種做法的低效率可以在將兩個(gè)字符串s1和s2連接到目標(biāo)緩沖區(qū)d中的示例中得到說明。將一個(gè)字符串添加到另一個(gè)字符串的慣用方法(雖然遠(yuǎn)非理想)是調(diào)用strcpy和strcat函數(shù),如下所示:
strcat (
strcpy (d, s1), s2);
為了執(zhí)行這個(gè)連接操作,除了同時(shí)發(fā)生的相應(yīng)地在d上的傳遞之外,一次在s1的傳遞和一次在s2上的傳遞是必須要執(zhí)行的操作,但是上面的調(diào)用在s1上進(jìn)行了兩次傳遞。讓我們把這些調(diào)用分成兩個(gè)語(yǔ)句。
char *d1 =
strcpy (d, s1);
// pass 1 over s1
strcat (d1, s2);
// pass 2 over the copy of s1 in d
因?yàn)閟trcpy返回其第一個(gè)參數(shù)d的值,所以d1的值與d相同。為簡(jiǎn)單起見,在后面的示例中我們將使用d,而不是將返回值存儲(chǔ)在d1中并使用它。在strcat調(diào)用中,我們遍歷剛剛復(fù)制到d1的字符串以確定最后一個(gè)字符的位置,這個(gè)成本和第一個(gè)字符串s1的長(zhǎng)度是線性關(guān)系。這個(gè)成本乘以每個(gè)要連接的字符串。因而最終整個(gè)連接操作的成本相當(dāng)于連接數(shù)和所以字符串長(zhǎng)度的乘積,趨于一種二次方的關(guān)系。這種低效率是如此的臭名昭著,以至于為自己贏得了一個(gè)名字:畫師施萊米爾算法。(另見http://www.open-
std.org/jtc1/sc22/wg14/www/docs/n2349.htm#sad-string)
必須指出的是,除了效率低
下之外,strcat和strcpy還因其緩沖區(qū)溢出的問題而臭名昭著,因?yàn)樗鼈兌紝?duì)復(fù)制字符的數(shù)量不做任何限制。
當(dāng)源字符串的長(zhǎng)度未知且目標(biāo)字符串大小固定時(shí),遵循一些流行的安全編碼準(zhǔn)則來將連接結(jié)果限制為目標(biāo)區(qū)大小實(shí)際上會(huì)導(dǎo)致兩個(gè)冗余的傳遞。例如,按照CERT關(guān)于安全使用strncpy()和strncat() 的建議,并且目標(biāo)區(qū)的大小是dsize字節(jié),我們可能會(huì)得到以下代碼。
strncpy (d, s1, dsize -
1);
// pass 1 over s1 plus over d up to dsize - 1
d[dsize -
1] =
'\0';
// remember to nul-terminate
size_t n =
strlen (d);
// pass 2 over copy of s1 in d
strncat (d, s2, dsize - n -
1);
// pass 3 over copy of s1 in d
注意,與對(duì)strncat的調(diào)用不同,當(dāng)s1的長(zhǎng)度大于d的大小時(shí),上面對(duì)strncpy的調(diào)用不會(huì)將NUL('\0')結(jié)束符追加到d上。
它是一個(gè)常見的想當(dāng)然的錯(cuò)誤。
此外,當(dāng)s1短于dsize-1時(shí),strncpy函數(shù)將所有剩余的
字符填滿為NUL('\0'),這也被視為一種浪費(fèi)的,因?yàn)殡S后對(duì)strncat的調(diào)用將覆蓋掉它
們。
為了避免一些冗余,程序員有時(shí)會(huì)選擇先計(jì)算字符串長(zhǎng)度,然后使用memcpy,如下所示。這種方法仍然效率不高,而且更容易出錯(cuò),并且代碼難以閱讀和維護(hù)。
size_t s1len =
strlen (s1);
// pass 1 over s1
if (dsize <= s1len)
s1len = dsize -
1;
// no need to nul-terminate
memcpy (d, s1, s1len);
// pass 2 over s1
size_t s2len =
strlen (s2);
// pass 1 over s2
if (dsize - s1len <= s2len)
s2len = dsize - s1len -
1;
memcpy (d + s1len, s2, s2len);
// pass 2, over s2
d[s1len + s1len] =
'\0';
// nul-terminate result
使用sprintf和snprintf進(jìn)行連接
出于對(duì)代碼復(fù)雜性和可讀性的擔(dān)心,程序員們有時(shí)會(huì)使用snprintf函數(shù)進(jìn)行字符串連接。
snprintf (d, dsize,
"%s%s", s1, s2);
這樣做代碼的可讀性非常好,但是,由于snprintf的開銷相當(dāng)大,它的低效率導(dǎo)致它可能比使用字符串函數(shù)慢幾個(gè)數(shù)量級(jí)。snprintf的開銷不僅是由于解析格式字符串,而且還由于格式化I/O函數(shù)實(shí)現(xiàn)中通常固有的復(fù)雜性。
一些編譯器(如GCC和Clang)試圖通過將非常簡(jiǎn)單的sprintf和snprintf調(diào)用轉(zhuǎn)換為strcpy或memcpy調(diào)用以提高效率,避免了對(duì)I/O函數(shù)的某些調(diào)用的開銷(請(qǐng)參閱這個(gè)在線示例https://godbolt.org/z/RaWkyd)。然而,由于C庫(kù)中沒有等價(jià)的字符串函數(shù),而只有當(dāng)snprintf調(diào)用被證明不會(huì)導(dǎo)致輸出的截?cái)鄷r(shí),轉(zhuǎn)換才會(huì)完成,因此對(duì)snprintf的相應(yīng)轉(zhuǎn)換很少能夠發(fā)生。memcpy本身不合適,因?yàn)樗鼜?fù)制的字節(jié)數(shù)與指定的字節(jié)數(shù)完全相同,strncpy也不適合,因?yàn)樗涯繕?biāo)字符串的最后的NUL結(jié)束符之后的位數(shù)都覆蓋了。
由于字符串的冗余傳遞次數(shù),將snprintf調(diào)用轉(zhuǎn)換為strlen和memcpy調(diào)用序列產(chǎn)生的額外開銷,也被視為得不償失。在這個(gè)頁(yè)面上,標(biāo)題為Better builtin string functions部分列出了GCC優(yōu)化器在這方面的一些限制,以及改進(jìn)它的一些折中措施。
POSIX的stpcpy和stpncpy函數(shù)
為了幫助解決這個(gè)問題,在過去很多年里出現(xiàn)了很多超出標(biāo)準(zhǔn)C的庫(kù)解決方案。POSIX標(biāo)準(zhǔn)包括stpcpy和stpncpy函數(shù),這兩個(gè)函數(shù)的實(shí)現(xiàn)方法是如果找到NUL結(jié)束符,則返回指向該字符的指針。這些函數(shù)可以用來緩解上面提到的麻煩和低效率。
const char* stpcpy (char* restrict, const char* restrict);
const char* stpncpy (char* restrict, const char* restrict, size_t);
特別是,在不考慮緩沖區(qū)溢出的情況下,可以像下面這樣調(diào)用stpcpy來連接字符串:
stpcpy (stpcpy (d, s1), s2);
然而,當(dāng)字符串副本必須以目標(biāo)大小為邊界時(shí),等效地使用stpncpy并不會(huì)消除將第一個(gè)NUL字符之后的剩余目標(biāo)位置清零并直到邊界指定的最大字符位置的開銷。
char *ret = stpncpy (d, dsize, s1);
// zeroes out d beyond the end of s1
dsize -= (ret - d);
stpncpy (d, dsize, s2);
// again zeroes out d beyond the end
所以,這個(gè)函數(shù)仍然效率低下,因?yàn)閷?duì)它的每次調(diào)用都會(huì)將目標(biāo)中剩余的空間以及復(fù)制的字符串的末尾的空間清零。因此,這個(gè)操作的復(fù)雜性仍然是二次方的。效率低下的嚴(yán)重程度隨著目標(biāo)的大小成比例地增加,而與被連接的字符串的長(zhǎng)度成反比增加。
OpenBSD的strlcpy和strlcat函數(shù)
為了應(yīng)對(duì)針對(duì)strcpy和strcat函數(shù)的弱點(diǎn)以及上面討論的strncpy和strncat的一些缺點(diǎn)的緩沖區(qū)溢出攻擊,OpenBSD項(xiàng)目在20世紀(jì)90年代末引入了一對(duì)替代API(strlcpy和strlcat),旨在使字符串復(fù)制和連接更加安全(http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2349.htm)。
size_t strlcpy (
char*
restrict,
const
char*
restrict,
size_t);
size_t strlcat (
char*
restrict,
const
char*
restrict,
size_t);
strncpy和strlcpy函數(shù)之間的主要區(qū)別在于返回值:前者返回指向目標(biāo)的指針,后者則返回復(fù)制的字符數(shù)。另一個(gè)區(qū)別是strlcpy函數(shù)總是在目標(biāo)中只存儲(chǔ)一個(gè)NUL結(jié)束符。要連接s1和s2,可以按以下方式使用strlcpy函數(shù):
size_t n = strlcpy (d, s1, dsize);
dsize -= n;
d += n;
strlcpy (d, s2, dsize);
這使得strlcpy在使用性和簡(jiǎn)單性方面都可以與snprintf相提并論(當(dāng)然snprintf的開銷雖然恒定,但要大得多)。
除了OpenBSD以外,strlcpy和strlcat函數(shù)在其他系統(tǒng)上也可用,包括Solaris和Linux(在BSD兼容庫(kù)中)。但是由于這些系統(tǒng)不是由POSIX指定的,所以這兩個(gè)函數(shù)在那些系統(tǒng)中并不總是存在。
POSIX還定義了另一個(gè)函數(shù)memccpy,該函數(shù)具有上面討論過的所有理想屬性,可以用來解決上面的問題。
void* memccpy (void* restrict dst, const void* restrict src, int c, size_t n);
這個(gè)函數(shù)結(jié)合了memcpy、memchr的特性以及上面討論的API的最佳方面的特性。
和memchr一樣,它會(huì)掃描源序列以查找由其參數(shù)之一指定的字符的第一次出現(xiàn)。字符可以是任何值,包括零。
和strlcpy一樣,它最多將指定數(shù)量的字符從源序列復(fù)制到目標(biāo)序列,而不會(huì)寫入超出其范圍。這解決了有關(guān)strncpy和stpncpy的低效率的報(bào)怨。
和stpcpy和stpncpy類似(盡管不完全相同),它返回一個(gè)指針,該指針指向指定字符的副本(如果存在)的后一位。(回想一下stpcpy和stpncpy返回一個(gè)指向復(fù)制的NUL的指針。)這避免了strcpy和strncpy固有的低效性。
因此,可以使用memccpy重寫上面的第一個(gè)示例(strcat(strcpy(d,s1,s2))以避免在字符串上進(jìn)行任何冗余傳遞,如下所示。請(qǐng)注意,這里使用SIZE_MAX作為大小限制,這個(gè)重寫無法避免原始示例中存在的目標(biāo)緩沖區(qū)溢出的風(fēng)險(xiǎn),因此應(yīng)避免。
memccpy (memccpy (d, s1,
'\0', SIZE_MAX) -
1, s2,
'\0', SIZE_MAX);
為了避免緩沖區(qū)溢出的風(fēng)險(xiǎn),需要為每個(gè)調(diào)用確定適當(dāng)?shù)拇笮∠拗撇⒆鳛閰?shù)提供。因此,像在snprintf(d, dsize, "%s%s", s1, s2)函數(shù)中那樣限制目標(biāo)大小的連接調(diào)用,可以像下面這樣計(jì)算目標(biāo)大?。?/span>
char *p = memccpy (d, s1,
'\0', dsize);
dsize -= (p - d -
1);
memccpy (p -
1, s2,
'\0', dsize);
如果字符串函數(shù)返回指向最后一個(gè)存儲(chǔ)字符或它的后面一位的指針,而不是返回其第一個(gè)參數(shù)的值,則上面討論的效率問題可以得到解決。然而,在現(xiàn)有函數(shù)使用了接近半個(gè)世紀(jì)后,對(duì)其進(jìn)行更改是不太可行的。
盡管解決現(xiàn)有C標(biāo)準(zhǔn)字符串函數(shù)的問題是不可行的,但是可以通過添加一個(gè)或多個(gè)不受相同限制的函數(shù)來在新代碼中緩解這個(gè)問題。由于C標(biāo)準(zhǔn)的章程正在對(duì)現(xiàn)有的實(shí)踐進(jìn)行編纂整理,所以C語(yǔ)言標(biāo)準(zhǔn)化委員有義不容辭的責(zé)任調(diào)查這種功能是否已經(jīng)存在于流行的實(shí)現(xiàn)中,如果已經(jīng)存在,則應(yīng)該考慮采納它們。如上文提到的這幾種解決方案。
在上面提到的解決方案中,memccpy函數(shù)是最通用和最高效的,它由ISO 標(biāo)準(zhǔn)支持。即使在POSIX標(biāo)準(zhǔn)實(shí)現(xiàn)之外,它的應(yīng)用范圍最廣,爭(zhēng)議最小。
相比之下,stpcpy和stpncpy函數(shù)的通用性較差,stpncpy函數(shù)會(huì)產(chǎn)生不必要的開銷,因此無法達(dá)到既定的目標(biāo)。這些函數(shù)在C2X中仍然值得采用,以提高移植性。詳情請(qǐng)參閱N2352–將stpcpy和stpncpy添加到C2X中的提案。
OpenBSD的strlcpy和strlcat函數(shù)雖然是最優(yōu)的,但是它們的通用性較差,支持范圍也較低,而且沒有得到ISO標(biāo)準(zhǔn)的指定。
memccpy函數(shù)不僅存在于Unix實(shí)現(xiàn)的子集中,它還由另一個(gè)名為ISO/IEC 9945的ISO標(biāo)準(zhǔn)指定。ISO/IEC 9945還有另外一個(gè)名字,也即大家熟知的IEEE Std 1003.1, 2017版,或者簡(jiǎn)言之- POSIX: memccpy,在那里它是作為XSI擴(kuò)展提供給C的。這個(gè)函數(shù)可以追溯到System V接口定義第1版(SVID1),最初于1985年發(fā)布。
memccpy甚至可以用于UNIX和POSIX以外的實(shí)現(xiàn),例如:
安卓系統(tǒng)中的memccpy函數(shù),
蘋果Mac OS X中的memccpy函數(shù),
BlackBerry Native SDK 的memccpy函數(shù),
Compaq Run-Time Library for VAX中的memccpy函數(shù),
微軟Visual Studio C Runtime Library中的 memccpy 函數(shù),
IBM z/OS 中的memccpy函數(shù).
下面提供了一個(gè)簡(jiǎn)單(但是效率低下)的memccpy參考實(shí)現(xiàn):
void* memccpy (void* restrict dst, const void* restrict src, int c, size_t n)
{
void *pc =
memchr (src, c, n);
void *ret;
if (pc)
{
n = (
char*)pc - (
char*)src +
1;
ret = (
char*)dst + n;
}
else
ret =
0;
memcpy (dst, src, n);
return ret;
}
這個(gè)函數(shù)的一個(gè)更優(yōu)化的實(shí)現(xiàn)可能如下。
void* memccpy (void* restrict dst, const void* restrict src, int c, size_t n)
{
const
char *s = src;
for (
char *ret = dst; n; ++ret, ++s, --n)
{
*ret = *s;
if ((
unsigned
char)*ret == (
unsigned
char)c)
return ret +
1;
}
return
0;
}
借助于memccpy的性能優(yōu)化,編譯器將能夠把對(duì)snprintf (d, dsize, "%s", s)函數(shù)的簡(jiǎn)單調(diào)用轉(zhuǎn)換為對(duì)memccpy(d, s, '\0', dsize)的最佳有效調(diào)用。通過以代碼大小換取速度,激進(jìn)的優(yōu)化器甚至可以將符合下列條件的snprintf函數(shù)調(diào)用(其格式字符串由多個(gè)%s指令組成,這些指令中間穿插有普通字符,如%s/%s)轉(zhuǎn)換成一系列的此類memccpy函數(shù)調(diào)用:如下所示
char *p = memccpy (d, s1,
'\0', dsize);
if (p)
{
--p;
p = memccpy (p,
"/",
'\0', dsize - (p - d));
if (p)
{
--p;
p = memccpy (p, s2,
'\0', dsize - (p - d));
}
}
if (!p)
d[dsize -
1] =
'\0';
將memccpy函數(shù)和本文討論的其他標(biāo)準(zhǔn)函數(shù)(除了strlcpy和strlcat),以及另外兩個(gè)標(biāo)準(zhǔn)函數(shù)納入下一個(gè)C編程語(yǔ)言修訂版的提議于2019年4月提交給了C語(yǔ)言標(biāo)準(zhǔn)化委員會(huì)(見 3, 4, 5和 6)。委員會(huì)最終決定采納memccpy函數(shù),但否決了其余提案。
原文:https://developers.redhat.com/blog/2019/08/12/efficient-string-copying-and-concatenation-in-c/
免責(zé)聲明:整理文章為傳播相關(guān)技術(shù),版權(quán)歸原作者所有,如有侵權(quán),請(qǐng)聯(lián)系刪除