经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
musl中strlen源码实现和分析
来源:cnblogs  作者:JobYan  时间:2023/11/13 8:45:21  对本文有异议

最近在学习《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 的设计有更深的了解,对一些细节也有了更深的认识。
希望本文对你有所帮助!

原文链接:https://www.cnblogs.com/jobyan/p/17828181.html

 友情链接:直通硅谷  直通硅谷 怎么样 mac软件下载