魔術比特如何改善glibc中的strlen函數

Question

我正在經歷strlen for glibc的來源。他們使用magic bits來查找字符串的長度。有人可以解釋它是如何工作的。 謝謝

Answer 1

比方說，這個功能是通過尋找一個字符串 - 一次4個字節，由註釋解釋（我們假設long ints是4個字節） - 與當前「塊」這個樣子：

'\3'  '\3'  '\0'  '\3' 
00000011 00000011 00000000 00000011 (as a string: "\x03\x03\x00\x03") 

strlen函數只是尋找這個字符串中的第一個零字節。它首先確定，對於每個4字節塊，是否有任何零字節在那裏，首先檢查該magic_bits快捷方式：它增加了的4個字節爲這個值：

01111110 11111110 11111110 11111111 

添加任何非零字節到這個值將導致1通過傳播載體而溢出到由零標記的孔中。對於我們的塊，它會是這樣的：

11111111 111111   1 1111111 Carries 
    00000011 00000011 00000000 00000011 Chunk 
    01111110 11111110 11111110 11111111 Magic bits 
+ ----------------------------------- 
    10000010 00000001 11111111 00000010 
^ ^ ^ ^  

（孔位由^的標記）

，並從評論：

 /* Look at only the hole bits. If any of the hole bits 
      are unchanged, most likely one of the bytes was a 
      zero. */ 

如果沒有零中的所有洞位將被設置爲1's。但是，由於零字節，一個孔位沒有被傳播進位填充，我們可以檢查它是哪個字節。

本質上，它通過在4個字節塊上應用一些位加法魔術來掃描零來加速strlen計算，然後將搜索範圍縮小到單個字節比較。

Answer 2

的想法是不是一個字節在對零的時間比較，而在一次檢查一個unsigned long對象，如果它的字節之一是零。這意味着當sizeof (unsigned long)爲8時，檢查8字節。

隨着位的攻擊，有一個快速已知的表達式，可以確定其中一個字節比較是否等於零。然後，如果其中一個字節等於零，則單獨測試對象的字節以找到第一個爲零的字節。使用按位操作的優點是減少了分支指令的數量。

位劈表達，以檢查是否一個多字節對象的字節之一等於零在著名的斯坦福位操作黑客頁進行了解釋，在

確定一個字具有零字節 http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord