当前位置:网站首页>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;
}
}
}
边栏推荐
- Design and practice of kubernetes cluster and application monitoring scheme
- IPv6 experiment
- Kubernetes - Multi cluster management
- LeetCode 237. Delete nodes in the linked list
- Blue Bridge Cup single chip microcomputer -- PWM pulse width modulation
- SQL performance optimization skills
- IPv6 experiment
- Devtools的簡單使用
- Basic authorization command for Curl
- Kubernetes - identity and authority authentication
猜你喜欢
[200 opencv routines] 99 Modified alpha mean filter
Sqoop installation
[groovy] groovy environment setup (download groovy | install groovy | configure groovy environment variables)
Design and implementation of campus epidemic prevention and control system based on SSM
Port, domain name, protocol.
Design of kindergarten real-time monitoring and control system
1. Five layer network model
SQL injection exercise -- sqli Labs
The latest blind box mall, which has been repaired very popular these days, has complete open source operation source code
El select, El option drop-down selection box
随机推荐
[deep learning] deep learning reference materials
About MySQL database connection exceptions
Last words record
Accuracy problem and solution of BigDecimal
Three line by line explanations of the source code of anchor free series network yolox (a total of ten articles, which are guaranteed to be explained line by line. After reading it, you can change the
DECLARE_ WAIT_ QUEUE_ HEAD、wake_ up_ Interruptible macro analysis
IPv6 experiment
[groovy] string (string splicing | multi line string)
Daily question 2 12
Azkaban actual combat
51 independent key basic experiment
Design of kindergarten real-time monitoring and control system
Solve the problem that sqlyog does not have a schema Designer
Linux Installation redis
The perfect car for successful people: BMW X7! Superior performance, excellent comfort and safety
Cette ADB MySQL prend - elle en charge SQL Server?
1.五层网络模型
The perfect car for successful people: BMW X7! Superior performance, excellent comfort and safety
ICSI213/IECE213 Data Structures
Design of KTV intelligent dimming system based on MCU