Recently, I was studying the pointer part of Chapter 6 of “C and Pointers”. I saw the implementation of the strlen function in Chapter 6.12. I thought that I was looking at the source code of musl recently, so I carefully analyzed the source code of strlen in musl and found that There are some interesting points in the source code, and I specially wrote this article to share them with all of you who are interested. This article focuses on analyzing some interesting points in the strlen source code of musl. I hope it will be helpful to you in understanding the strlen function implementation.
1. strlen source code
To calculate the length of a string, you can use the following code:
/*
** Calculate the length of a string
*/
#include <stdlib.h>
size_t strlen(char *string)
{<!-- -->
int length = 0;
//Access the contents of the string in sequence, counting the number of characters until the NUL terminator is encountered.
while(*string + + != '\0')
length + + ;
\t\t
return length;
}
The *string + + expression in the while statement evaluates to true until the pointer reaches the NUL character at the end of the string. It also increments the pointer’s value for the next test. This expression even handles empty strings correctly.
It should be noted that if the parameter passed in is a NULL pointer when calling this function, the indirect access in the while statement will fail. This is because NULL is a macro definition in C language, which represents a null pointer constant with a value of 0. When we try to dereference a NULL pointer, we are actually trying to access a memory address that does not exist. A dereference operation refers to accessing the value of the memory location pointed to by a pointer. When we dereference a NULL pointer, since the NULL pointer does not point to any valid memory address, a valid value cannot be obtained. This causes an error to occur while the program is running, usually triggering an exception that causes the program to crash.
So here comes the question. Since the parameter passed in by strlen may be NULL, is it necessary to add a judgment that the pointer is null in the implementation of the strlen function? The answer is no, because to check whether the pointer variable is NULL, you should judge whether it is NULL after the pointer variable is created. In this way, you only need to check it once. When you use the pointer variable later, you can use it directly. There is no need to check it again. Determine whether the pointer variable is NULL.
2. Source code of strlen in musl
The sample code in the previous section is very simple and easy to understand, but the code in musl is not so easy to understand. The strlen implementation of musl code is as follows:
#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 & amp; ~(x) & amp; 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;
}
Seeing this, I suggest you take some time to read the above source code carefully and try to answer the following questions:
- What are the values of the macros
ALIGN,ONES, andHIGHSon a 64-bit operating system? - What does the code in
#ifdef __GNUC__and#endifdo? Just write#endifand the following code can also calculate the string length. Why do you need to write the code in#ifdef __GNUC__and#endifWoolen cloth? - What is the function of
HASZERO(*w)? Try to give an example to illustrate the process ofHASZERO(*w)detecting whether there is 0 in word.
2.1 Analysis of Question 1
On 64-bit operating systems, the macro ALIGN has a value of 8, ONES has a value of 0x0101010101010101, and HIGHS has a value of 0x8080808080808080.
The calculation process is as follows:
- Calculation of
ALIGN: The result ofsizeof(size_t)is 8, so the value ofALIGNis 8. - Calculation of
ONES: The value ofUCHAR_MAXis 255, so the result of(size_t)-1/UCHAR_MAXis0xffffffffffffffff/0xff=0x0101010101010101. - Calculation of
HIGHS: The value ofONESis 0x0101010101010101, so the result ofUCHAR_MAX/2 + 1is 128, soONES * (UCHAR_MAX The result of /2 + 1)is 0x8080808080808080.
2.2 Analysis of Question 2
The code in #ifdef __GNUC__ and #endif checks whether the GCC compiler is used. If it is the GCC compiler, the code block between #ifdef __GNUC__ and #endif will be executed. This block of code defines some type aliases and variables to optimize string length calculations. If it is not a GCC compiler, this block of code will be ignored.
Although it is possible to calculate the string length by just writing the code after #endif, the calculation efficiency can be improved by using GCC-specific optimization techniques. Therefore, in order to obtain better performance under the GCC compiler, you need to write the code in #ifdef __GNUC__ and #endif.
The advantage of this design is that in one bit operation operation, you can quickly check whether there is a byte with a byte value of 0 in a 64-bit unsigned integer, without using loops or other complex logic. This design improves code efficiency and performance.
2.3 Analysis of Question 3
The function of HASZERO(*w) is to check whether there is a byte with a byte value of 0 in a value of type size_t. Its calculation process is to subtract ONES from the value, then invert it and perform a bitwise AND operation, and then perform a bitwise AND operation with HIGHS. If the final result is non-0, it means that there is a byte with a byte value of 0 in the value.
After reading this, you may still not understand the specific calculation process of HASZERO(*w). If you are not very interested in this, you can simply take a look at the following content. Just have some impression of this part, and spend some time studying it when you need it later. Here are two examples to illustrate the specific calculation process. It should be noted that in a 64-bit operating system, sizeof(size_t)=8, *w is an 8 The number of bytes. In Example 1, the value of *w is 0x1101110111011101, and each byte is non-0; in Example 2, the value of *w is 0x1100< /strong>110111011101, the second byte is 0.
2.3.1 Calculation process of Example 1
Example 1, in a 64-bit operating system, the value of ONES is 0x0101010101010101, the value of HIGHS is 0x8080808080808080, and the value of *w is 0x1101110111011101. Then, the calculation process of HASZERO(*w) is as follows:
- Subtract
ONESfrom*w: 0x1101110111011101 – 0x0101010101010101 = 0x1000100010001000 - Perform a bitwise AND operation on the result and its inversion: 0x1000100010001000 & ~0x1101110111011101 = 0x1000100010001000 & 0xEEFEEEFEEEFEEEFE=0x0000000000000000
- Bitwise AND the result with
HIGHS: 0x0000000000000000 & amp; 0x8080808080808080 = 0x0000000000000000
Since the final result is 0, it means that there is no byte with a byte value of 0 in*w.
2.3.2 Calculation process of Example 2
Example 2: In a 64-bit operating system, the values of ONES and HIGHS are the same as the above example. In this example, the value of *w is 0x1100110111011101. Then, the calculation process of HASZERO(*w) is as follows:
- Subtract
ONESfrom*w: 0x1100110111011101 – 0x0101010101010101 = 0x0FFF100010001000 - Invert the result and perform a bitwise AND operation: 0x0fff100010001000 & ~0x1100110111011101 = 0x0FFF100010001000 & 0xEEFFEEFEEEFEEEFE=0x0EFF000000000000
- Bitwise AND the result with
HIGHS: 0x0000000000000000 & 0x8080808080808080 = 0x0080000000000000
Since the final result is not 0, it means that there is a byte with a byte value of 0 in*w.
2.3.3 Summary of the above two examples
Through the above two examples, we can find that using HASZERO(*w) can effectively determine the 8 bytes of the word *w (in 64-bit operating systems, 1 word = 8 bytes) whether there is a byte with a value of 0.
The above two examples provide a good introduction to the calculation process of HASZERO(*w), but the multi-byte calculation process is more complicated. Next, we take a single byte as an example to analyze HASZERO(*w) can detect the reason why 0 exists in a word:
First of all, we know that the representation range of an unsigned byte is: 0~255. We can divide this range into the following segments and calculate the result of HASZERO(*w) (in this example, 8 Bit operating system as an example), since it only involves the calculation process of a single byte, the calculation process is relatively simple, and it is easy to find the rules:
| Range | HASZERO(*w) |
|---|---|
| 0 | 0x80 |
| 1~127 | 0x00 |
| 128 | 0x00 |
| 129~255 | 0x00 |
Analyzing the above table, we can find that only when *w=0, |
3. Summary
The source code implementation of strlen in musl has been talked about so much, so what use does HASZERO(*w) have for our daily coding? An easy to think of use is to refer to the source code of strlen to determine whether there is a byte with a byte value of 0 in the int type or long type data. Of course, it can also be easily implemented using the rotation + shift method, but when pursuing efficiency, you can consider using HASZERO(*w) in the strlen source code to implement it. Of course, knowing that there is such a use is only one aspect. I think the more important thing is that through the analysis of this article, you can have a deeper understanding of the design of strlen and a deeper understanding of some details.
Hope this article is helpful to you!