526互联

musl中strlen源码实现和分析

发布时间 2023-11-12 23:36:07作者: JobYan

最近在学习《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) 的计算过程如下：

  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 位操作系统中 ONES、HIGHS 的值同上例一样，本例中 *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 的设计有更深的了解，对一些细节也有了更深的认识。
希望本文对你有所帮助！