musl中strlen原始碼實現和分析

2023-11-13 06:00:39

最近在學習《C 和指標》的第 6 章指標部分,在 6.12 章節看到了 strlen 函數的實現,聯想到最近有在看 musl 的原始碼,於是就把 musl 中 strlen 的原始碼認真地分析了一下,發現原始碼中有一些有意思的點,特地寫這篇文章跟各位感興趣的小夥伴分享一下。本文重點對 musl 的 strlen 原始碼中的一些有意思的點進行分析,希望能對你理解 strlen 函數實現有所幫助。

1. strlen 原始碼

要計算一個字串的長度,可以通過以下的程式碼實現:

/*
** 計算一個字串的長度
*/
#include <stdlib.h>
size_t strlen(char *string)
{
	int length = 0;
	// 依次存取字串的內容,計數位符數,直到遇見 NUL 終止符。
	while(*string++ != '\0')
		length++;
		
	return length;
}

在指標到達字串的末尾的 NUL 字元之前,while 語句中 *string++ 表示式的值一直為真。它同時增加指標的值,用於下一次測試。這個表示式甚至可以正確地處理空字串。
需要注意的是,如果呼叫這個函數時,傳入的引數是 NULL 指標,那麼 while 語句中的間接存取就會失敗。這是因為在 C 語言中 NULL 是一個宏定義,表示一個空指標常數,其值為 0。當我們試圖對 NULL 指標進行解除參照操作時,實際上是在嘗試存取一個不存在的記憶體地址。解除參照操作是指通過指標存取其指向的記憶體位置的值。當我們對一個 NULL 指標進行解除參照時,由於 NULL 指標並不指向任何有效的記憶體地址,因此無法獲取到有效的值。這會導致程式在執行時發生錯誤,通常會觸發一個異常,導致程式崩潰。
那麼問題來了,既然 strlen 傳入的引數有可能為 NULL,那麼有沒有必要在 strlen 函數的實現中加入指標為空的判斷呢?答案是不需要,因為檢查指標變數是否為 NULL,應該在指標變數建立之後就進行是否為 NULL 的判斷,這樣只需要檢查一次就行了,後邊再用指標變數的時候直接使用就行,不需要再對指標變數是否為 NULL 進行判斷。

2. musl 中 strlen 的原始碼

上節中的範例程式碼很簡單也很好理解,但是 musl 中的程式碼就沒那麼好理解了,musl 程式碼的 strlen 實現如下:

#include <string.h>
#include <stdint.h>
#include <limits.h>

#define ALIGN (sizeof(size_t))
#define ONES ((size_t)-1/UCHAR_MAX)
#define HIGHS (ONES * (UCHAR_MAX/2+1))
#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS)

size_t strlen(const char *s)
{
	const char *a = s;
#ifdef __GNUC__
	typedef size_t __attribute__((__may_alias__)) word;
	const word *w;
	for (; (uintptr_t)s % ALIGN; s++) if (!*s) return s-a;
	for (w = (const void *)s; !HASZERO(*w); w++);
	s = (const void *)w;
#endif
	for (; *s; s++);
	return s-a;
}

看到這裡,建議各位小夥伴花點兒時間仔細閱讀一下上面的原始碼,並試著回答以下幾個問題:

  • 在 64 位元運算系統中,宏 ALIGNONESHIGHS 的值分別為多少?
  • #ifdef __GNUC__#endif 中的程式碼的作用是什麼?只寫 #endif 後面的程式碼一樣可以實現字串長度的計算,為什麼還要寫 #ifdef __GNUC__#endif 中的程式碼呢?
  • HASZERO(*w) 的作用是什麼呢?試著舉例說明 HASZERO(*w) 檢測 word 中是否存在著 0 的過程。

2.1 問題 1 分析

在 64 位元運算系統中,宏 ALIGN 的值為8,ONES 的值為0x0101010101010101,HIGHS 的值為 0x8080808080808080。
計算過程如下:

  • ALIGN 的計算:sizeof(size_t) 的結果為8,所以 ALIGN 的值為 8。
  • ONES 的計算:UCHAR_MAX 的值為255,所以 (size_t)-1/UCHAR_MAX 的結果為 0xffffffffffffffff/0xff=0x0101010101010101
  • HIGHS 的計算:ONES 的值為0x0101010101010101,所以 UCHAR_MAX/2+1 的結果為128,所以 ONES * (UCHAR_MAX/2+1) 的結果為 0x8080808080808080。

2.2 問題 2 分析

#ifdef __GNUC__#endif 中的程式碼的作用是檢查是否使用的是 GCC 編譯器。如果是 GCC 編譯器,那麼就會執行 #ifdef __GNUC__#endif 之間的程式碼塊。這段程式碼塊中定義了一些型別別名和變數,用於優化字串長度的計算。如果不是 GCC 編譯器,那麼這段程式碼塊會被忽略。
儘管只寫 #endif 後面的程式碼也可以實現字串長度的計算,但是通過使用 GCC 特定的優化技巧,可以提高計算效率。因此,為了在 GCC 編譯器下獲得更好的效能,才需要寫 #ifdef __GNUC__#endif 中的程式碼。
這樣設計的好處是,在一次位運算操作中,就可以快速檢查一個 64 位無符號整數中是否存在位元組值為 0 的位元組,而不需要使用迴圈或其他複雜的邏輯。這種設計可以提高程式碼的效率和效能。

2.3 問題 3 分析

HASZERO(*w) 的作用是檢查一個 size_t 型別的值中是否存在位元組值為0的位元組。它的計算過程是將該值減去 ONES,然後與其取反進行按位元與操作,再與 HIGHS 進行按位元與操作。如果最終的結果為非 0,說明該值中存在位元組值為 0 的位元組。
看到這裡後,各位小夥伴可能對 HASZERO(*w) 的具體計算過程仍然不太理解,如果對這塊不太感興趣的話,後邊的內容可以簡單看一下,對這部分有點印象就行,等後邊有用到的時候再花點時間研究一下就好。這裡列舉兩個例子來說明具體的計算過程,需要說明的是,在 64 位元運算系統中 sizeof(size_t)=8*w 為一個 8 個位元組的數,例 1 中 *w 的值為 0x1101110111011101,各個位元組都非 0;例 2 中 *w 的值為 0x1100110111011101,第二個位元組為 0。

2.3.1 例 1 的計算過程

例 1,在 64 位元運算系統中 ONES 的值為0x0101010101010101,HIGHS 的值為0x8080808080808080,*w 的值為 0x1101110111011101。那麼,HASZERO(*w) 的計算過程如下:

  1. *w 減去 ONES:0x1101110111011101 - 0x0101010101010101 = 0x1000100010001000
  2. 將結果與其取反進行按位元與操作:0x1000100010001000 & ~0x1101110111011101 = 0x1000100010001000 & 0xEEFEEEFEEEFEEEFE=0x0000000000000000
  3. 將結果與 HIGHS 進行按位元與操作:0x0000000000000000 & 0x8080808080808080 = 0x0000000000000000
    由於最終的結果為0,說明 *w 中不存在位元組值為 0 的位元組。

2.3.2 例 2 的計算過程

例 2,在 64 位元運算系統中 ONESHIGHS 的值同上例一樣,本例中 *w 的值為 0x1100110111011101。那麼,HASZERO(*w) 的計算過程如下:

  1. *w 減去 ONES:0x1100110111011101 - 0x0101010101010101 = 0x0FFF100010001000
  2. 將結果與其取反進行按位元與操作:0x0fff100010001000 & ~0x1100110111011101 = 0x0FFF100010001000 & 0xEEFFEEFEEEFEEEFE=0x0EFF000000000000
  3. 將結果與 HIGHS 進行按位元與操作:0x0000000000000000 & 0x8080808080808080 = 0x0080000000000000
    由於最終的結果不為 0,說明 *w 中存在位元組值為 0 的位元組。

2.3.3 對上述兩個例子的總結

通過上面的兩個例子可以發現,利用 HASZERO(*w) 可以有效地確定字 *w 的 8個位元組(64 位元運算系統中,1字=8位元組)中是否存在值為 0 的位元組。
上面的兩個例子很好地介紹了 HASZERO(*w) 的計算過程,但是多位元組的計算過程較為複雜,接下來我們以單位元組為例,來分析 HASZERO(*w) 可以檢測字中是否存在 0 的原因:
首先,我們知道一個無符號位元組的表示範圍為:0~255,可以把這個範圍分為如下幾段,並計算 HASZERO(*w) 的結果(本例中以 8 位元運算系統為例),由於只涉及單位元組的計算過程,所以計算過程較為簡單,並且很容易發現規律:

範圍 HASZERO(*w)
0 0x80
1~127 0x00
128 0x00
129~255 0x00
分析上面的表格可以發現,只有在 *w=0 的時候,HASZERO(*w) 的結果才為非 0。

3. 總結

上面對 musl 中 strlen 的原始碼實現囉嗦了這麼多,那麼 HASZERO(*w) 對我們的日常編碼有什麼用呢?一個容易想到的用處是,可以參考 strlen 的原始碼寫出判斷 int 型別或者 long 型別的資料中是否存在著位元組值為 0 的位元組。當然,如果用迴圈+移位的方法也可以很方便的實現,但在追求效率的情況下,可以考慮利用 strlen 原始碼中的 HASZERO(*w) 來實現。當然知道有這麼個用處只是一方面,我想更重要的是通過本文的分析,你可以對 strlen 的設計有更深的瞭解,對一些細節也有了更深的認識。
希望本文對你有所幫助!