最近在学习《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 位操作系统中,宏
ALIGN
、ONES
、HIGHS
的值分别为多少? #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)
的计算过程如下:
- 将
*w
减去ONES
:0x1101110111011101 - 0x0101010101010101 = 0x1000100010001000 - 将结果与其取反进行按位与操作:0x1000100010001000 & ~0x1101110111011101 = 0x1000100010001000 & 0xEEFEEEFEEEFEEEFE=0x0000000000000000
- 将结果与
HIGHS
进行按位与操作:0x0000000000000000 & 0x8080808080808080 = 0x0000000000000000
由于最终的结果为0,说明*w
中不存在字节值为 0 的字节。
2.3.2 例 2 的计算过程
例 2,在 64 位操作系统中 ONES
、HIGHS
的值同上例一样,本例中 *w
的值为 0x1100110111011101。那么,HASZERO(*w)
的计算过程如下:
- 将
*w
减去ONES
:0x1100110111011101 - 0x0101010101010101 = 0x0FFF100010001000 - 将结果与其取反进行按位与操作:0x0fff100010001000 & ~0x1100110111011101 = 0x0FFF100010001000 & 0xEEFFEEFEEEFEEEFE=0x0EFF000000000000
- 将结果与
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 的设计有更深的了解,对一些细节也有了更深的认识。
希望本文对你有所帮助!