当前位置:网站首页>glibc strlen 实现方式分析
glibc strlen 实现方式分析
2022-07-05 03:33:00 【枫铃树】
摘要
本文对 glibc 2.35 源码中的 strlen
函数实现展开研究,分析其使用位运算实现更快长度计算的原理。
函数位置
glibc-2.35/string/strlen.c
原始实现
下面是 glibc strlen.c 的文件内容:
/* Copyright (C) 1991-2022 Free Software Foundation, Inc. This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. The GNU C Library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with the GNU C Library; if not, see <https://www.gnu.org/licenses/>. */
#include <string.h>
#include <stdlib.h>
#undef strlen
#ifndef STRLEN
# define STRLEN strlen
#endif
/* Return the length of the null-terminated string STR. Scan for the null terminator quickly by testing four bytes at a time. */
size_t
STRLEN (const char *str)
{
const char *char_ptr;
const unsigned long int *longword_ptr;
unsigned long int longword, himagic, lomagic;
/* Handle the first few characters by reading one character at a time. Do this until CHAR_PTR is aligned on a longword boundary. */
for (char_ptr = str; ((unsigned long int) char_ptr
& (sizeof (longword) - 1)) != 0;
++char_ptr)
if (*char_ptr == '\0')
return char_ptr - str;
/* All these elucidatory comments refer to 4-byte longwords, but the theory applies equally well to 8-byte longwords. */
longword_ptr = (unsigned long int *) char_ptr;
/* Bits 31, 24, 16, and 8 of this number are zero. Call these bits the "holes." Note that there is a hole just to the left of each byte, with an extra at the end: bits: 01111110 11111110 11111110 11111111 bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD The 1-bits make sure that carries propagate to the next 0-bit. The 0-bits provide holes for carries to fall into. */
himagic = 0x80808080L;
lomagic = 0x01010101L;
if (sizeof (longword) > 4)
{
/* 64-bit version of the magic. */
/* Do the shift in two steps to avoid a warning if long has 32 bits. */
himagic = ((himagic << 16) << 16) | himagic;
lomagic = ((lomagic << 16) << 16) | lomagic;
}
if (sizeof (longword) > 8)
abort ();
/* Instead of the traditional loop which tests each character, we will test a longword at a time. The tricky part is testing if *any of the four* bytes in the longword in question are zero. */
for (;;)
{
longword = *longword_ptr++;
if (((longword - lomagic) & ~longword & himagic) != 0)
{
/* Which of the bytes was the zero? If none of them were, it was a misfire; continue the search. */
const char *cp = (const char *) (longword_ptr - 1);
if (cp[0] == 0)
return cp - str;
if (cp[1] == 0)
return cp - str + 1;
if (cp[2] == 0)
return cp - str + 2;
if (cp[3] == 0)
return cp - str + 3;
if (sizeof (longword) > 4)
{
if (cp[4] == 0)
return cp - str + 4;
if (cp[5] == 0)
return cp - str + 5;
if (cp[6] == 0)
return cp - str + 6;
if (cp[7] == 0)
return cp - str + 7;
}
}
}
}
libc_hidden_builtin_def (strlen)
分析
区别于逐一比较每个字符是否为0,glibc的strlen采用每8字节(64位程序)一比较的方式,快速找到为0的字节。之后,对含0的8字节内进行逐字节比较,找到0的位置。
对齐
为提升效率,首先对前几个字符进行逐一比较,直到指针与long型地址对齐。
const char *char_ptr;
const unsigned long int *longword_ptr;
unsigned long int longword, himagic, lomagic;
/* Handle the first few characters by reading one character at a time. Do this until CHAR_PTR is aligned on a longword boundary. */
for (char_ptr = str; ((unsigned long int) char_ptr
& (sizeof (longword) - 1)) != 0;
++char_ptr)
if (*char_ptr == '\0')
return char_ptr - str;
/* All these elucidatory comments refer to 4-byte longwords, but the theory applies equally well to 8-byte longwords. */
longword_ptr = (unsigned long int *) char_ptr;
比较原理
之后,是每8位一比较的原理。
假如某字节为全0,即为 00000000(二进制)。那么,如果我们对它进行减1的操作,它会变为11111111。
注意最高位。如果我们将原字节0进行取反,得到的也是11111111,那么两个结果取与运算,得到的值将会是最高位为1的值。注意,即便紧跟其后的字节在做减法时要借位,该字节只会变成11111110,最高位依旧是1。
如果该字节不全为0,则可分两种情况:首位为1和首位为0.
如果该字节首位为0,则其为0abcdef,a-f中至少有1个为1,因此对最低位减1后,首位依然是0.
如果该字节首位为1,且为该字节二进制表示中的唯一一个1,则做减1操作时,首位会变成0。如果不是唯一的1,则首位仍然是1。
综合以上,可以看出,如果某字节最低位减1后,最高位为1,且字节取反后最高位也是1,那么该字节一定是0。基于此,我们可以对字节做批量比较。
for (;;) {
longword = *longword_ptr++;
if (((longword - lomagic) & ~longword & himagic) != 0) {
/* Which of the bytes was the zero? If none of them were, it was a misfire; continue the search. */
const char *cp = (const char *) (longword_ptr - 1);
if (cp[0] == 0)
return cp - str;
if (cp[1] == 0)
return cp - str + 1;
if (cp[2] == 0)
return cp - str + 2;
if (cp[3] == 0)
return cp - str + 3;
if (sizeof (longword) > 4) {
if (cp[4] == 0)
return cp - str + 4;
if (cp[5] == 0)
return cp - str + 5;
if (cp[6] == 0)
return cp - str + 6;
if (cp[7] == 0)
return cp - str + 7;
}
}
}
边栏推荐
- LeetCode 234. Palindrome linked list
- MySQL winter vacation self-study 2022 11 (9)
- el-select,el-option下拉选择框
- Leetcode92. reverse linked list II
- Linux安装Redis
- SFTP cannot connect to the server # yyds dry goods inventory #
- [deep learning] deep learning reference materials
- How can we truncate the float64 type to a specific precision- How can we truncate float64 type to a particular precision?
- 为什么腾讯阿里等互联网大厂诞生的好产品越来越少?
- 打破信息茧房-我主动获取信息的方法 -#3
猜你喜欢
Azkaban实战
Tiny series rendering tutorial
Bumblebee: build, deliver, and run ebpf programs smoothly like silk
端口,域名,协议。
51 independent key basic experiment
Leetcode42. connect rainwater
Vb+access hotel service management system
Easy processing of ten-year futures and stock market data -- Application of tdengine in Tongxinyuan fund
Simple use of devtools
Smart pointer shared_ PTR and weak_ Difference of PTR
随机推荐
Azkaban actual combat
Devtools的简单使用
In MySQL Association query, the foreign key is null. What if the data cannot be found?
How to make OS X read bash_ Profile instead of Profile file - how to make OS X to read bash_ profile not . profile file
单项框 复选框
Design of kindergarten real-time monitoring and control system
[105] Baidu brain map - Online mind mapping tool
Azkaban overview
[2022 repair version] community scanning code into group activity code to drain the complete operation source code / connect the contract free payment interface / promote the normal binding of subordi
Anchor free series network yolox source code line by line explanation Part 2 (a total of 10, ensure to explain line by line, after reading, you can change the network at will, not just as a participan
Linux安装Redis
Idea inheritance relationship
Why is this an undefined behavior- Why is this an undefined behavior?
el-select,el-option下拉选择框
Sqoop command
SQL performance optimization skills
Zero foundation uses paddlepaddle to build lenet-5 network
Tencent cloud, realize image upload
Multi person online anonymous chat room / private chat room source code / support the creation of multiple chat rooms at the same time
Tiny series rendering tutorial