前言 - strlen 概述
無意間掃到 glibc strlen.c 中代碼, 久久不能忘懷. 在一無所知的編程生涯中又記起點點滴滴:
編程可不是兒戲 ?, 有些難, 也有些不舍. 而 strlen 仿佛還在那個求學的年代, 還是那么青澀誘人 ~
/* Copyright (C) 1991-2020 Free Software Foundation, Inc. This file is part of the GNU C Library. Written by Torbjorn Granlund ([email protected]), with help from Dan Sahlin ([email protected]); commentary by Jim Blandy ([email protected]). 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)
正文 - 思考和分析
1. unsigned long int 位元組多大 4 位元組, 8 位元組 ?
unsigned long int longword, himagic, lomagic;
long 具體多長和平臺有關, 例如大多數 linux , x86 sizeof (long) = 4, x64 sizeof (long) = 8.
window x86, x64 sizeof (long) = 4. (2020年05月28日), C 標準保證 sizeof(long) >= sizeof (int)
具體多少位元組交給了實作方.
2. ((unsigned long int) char_ptr & (sizeof (longword) - 1)) 位對齊 ?
/* 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;
起始的這些代碼的作用是, 讓 chart_ptr 按照 sizeof (unsigned long) 位元組大小進行位對齊.
這涉及到多數計算機硬體對齊有要求和性能方面的考慮等等(性能是主要因素).
3. himagic = 0x80808080L; lomagic = 0x01010101L; what fuck ?
/* 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) {
3.1 (((longword - lomagic) & ~longword & himagic) != 0) ? mmp ?
可能這就是藝術吧. 想到這個想法的, 真是個天才啊! 好巧妙. 哈哈哈. 我們會分兩個小點說明下.
首次看, 感覺有點萌. 我這里用個簡單的思路來帶大家理解這個問題. 上面代碼主要圍繞
sizeof (unsigned long) 4 位元組和 8 位元組去處理得到. 我們簡單點, 通過處理 1 位元組, 類比遞回機制.
搞懂這個公式背后的原理 (ˇ?ˇ) ～
/** * himagic : 1000 0000 * lomagic : 0000 0001 * longword : XXXX XXXX * / unsigned long himagic = 0x80L; unsigned long lomagic = 0x01L; unsigned long longword ;
隨后我們仔細分析下面公式
((longword - lomagic) & ~longword & himagic)
( & himagic ) = ( & 1000 0000) 表明最終只在乎最高位.
longword 分三種情況討論
longword : 1XXX XXXX 128 =< x <= 255 longword : 0XXX XXXX 0 < x < 128 longword : 0000 0000 x = 0
第一種 longword = 1XXX XXXX
那么 ~longword = 0YYY YYYY 顯然 ~ longword & himagic = 0000 0000 不用繼續了.
第二種 longword = 0XXX XXXX 且不為 0, 及不小于 1
顯然 (longword - lomagic) = 0ZZZ ZZZ >= 0 且 < 127, 因為 lomagic = 1;
此刻 (longword - lomagic) & himagic = 0ZZZ ZZZZ & 1000 0000 = 0 , 所以也不需要繼續了.
第三種 longword = 0000 0000
那么 ~longword & himagic = 1111 1111 & 1000 0000 = 1000 000;
再看 (longword - lomagic) = (0000 0000 - 0000 0001) , 由于無符號數減法是按照
(補碼(0000 0000) + 補碼(-000 0001)) = (補碼(0000 0000) + 補碼(~000 0001 + 1))
= (補碼(0000 0000) + 補碼(1111 1111)) = 1111 1111 (快捷的可以查公式得到最終結果),
因而 此刻最終結果為 1111 1111 & 1000 0000 = 1000 0000 > 0.
綜合討論, 可以根據上面公式巧妙的篩選出值是否為 0. 對于 2位元組, 4 位元組, 8 位元組, 思路完全相似.
3.2 (sizeof (longword) > 4) ? (sizeof (longword) > 8) 為什么不用宏, 大展宏圖唄 ?
宏可以做到多平臺原始碼共享, 無法做到多平臺二進制共享. glibc 這么通用專案, 可移植性影響因子
可能會很重. (性能是毒酒, 想活的久還是少喝 ~ )
4. libc_hidden_builtin_def (strlen) ? 鬧哪樣 ~
理解這個東西, 要引入些場外資訊 (不同編譯引數會不一樣, 這里只抽取其中一條分支解法)
// file : glibc-2.31/include/libc-symbols.h libc_hidden_builtin_def (strlen) #define libc_hidden_builtin_def(name) libc_hidden_def (name) # define libc_hidden_def(name) hidden_def (name) /* Define ALIASNAME as a strong alias for NAME. */ # define strong_alias(name, aliasname) _strong_alias(name, aliasname) # define _strong_alias(name, aliasname) \ extern __typeof (name) aliasname __attribute__ ((alias (#name))) \ __attribute_copy__ (name); /* For assembly, we need to do the opposite of what we do in C: in assembly gcc __REDIRECT stuff is not in place, so functions are defined by its normal name and we need to create the __GI_* alias to it, in C __REDIRECT causes the function definition to use __GI_* name and we need to add alias to the real name. There is no reason to use hidden_weak over hidden_def in assembly, but we provide it for consistency with the C usage. hidden_proto doesn't make sense for assembly but the equivalent is to call via the HIDDEN_JUMPTARGET macro instead of JUMPTARGET. */ # define hidden_def(name) strong_alias (name, __GI_##name) /* Undefine (also defined in libc-symbols.h). */ #undef __attribute_copy__ #if __GNUC_PREREQ (9, 0) /* Copies attributes from the declaration or type referenced by the argument. */ # define __attribute_copy__(arg) __attribute__ ((__copy__ (arg))) #else # define __attribute_copy__(arg) #endif
利用上面宏定義, 進行展開
libc_hidden_builtin_def (strlen) | hidden_def (strlen) | strong_alias (strlen, __GI_strlen) | _strong_alias (strlen, __GI_strlen) | extern __typeof (strlen) __GI_strlen __attribute__ ((alias ("strlen"))) __attribute_copy__ (strlen); |
extern __typeof (strlen) __GI_strlen __attribute__ ((alias ("strlen"))) __attribute__ ((__copy__ (strlen))); ``
其中 GUN C 擴展語法
__typeof (arg) : 獲取變數的宣告的型別 __attribute__ ((__copy__ (arg))) : GCC 9 以上版本 attribute copy 復制特性 alias_name __attribute__ ((alias (name))) : 為 name 宣告符號別名 alias name. 總結: libc_hidden_builtin_def (strlen) 意思是基于 strlen 符號, 重新定義一個符號別名 __GI_strlen. (補充資料 strong_alias 注釋) strlen 工程代碼有很多種, 我們這里選擇一個通用 glibc 版本去思考和分析. 有興趣可以自行查閱更多. 隨口就來 ~ 做人嘛開心最重要 ~ 千錘百煉芮成鋼 ~ 哈哈哈
后記 - 展望與生活
錯誤是難免的, 歡迎指正和交流 ~
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/20787.html
標籤：C