strlen的神奇實現

https://blog.delphij.net/2012/04/freebsd-strlen3.html

與 Pascal 等語言不同，C 的字符串并不保存串的長度，而是在字符串末尾以 nul 字符（'\0'）來表示字符串結束。這個設計決策是上世紀 60 年代作出的，有都市傳說是為了省幾個字節的空間，不過我個人認為也可能是因為匯編里面到處都是判斷是否碰到了 0 的操作。不管怎么說，這個設計令 strlen 變成了一個 O(n) 的操作。

早期的 BSD Unix 采用的 strlen 是非常簡單的循環比較每一個字符是不是 nul。1993年，J.T. Conklin 為 i386 系統撰寫了一個匯編的版本，這個版本的核心用的是 REP SCASB，實際上和 C 版本的算法是一樣的（不知道為什么 C 編譯器不能寫出同樣的代碼）。

為了配合 x86_64 平臺，后來又有了一個新的匯編版本，這個版本的核心算法是按字匹配，找到包含 nul 字符的字之后，再在其中用原始的算法找到 nul 字符。

我在 2009 年根據這個 x86_64 版本的匯編的思路重寫了一個 C 的版本，并在 2010 年做了一次最終的變動，形成了目前的版本。這個版本的大致流程如下：

• 判斷第一個字中是否存在 nul，如果存在，掃描查找其中有效位置的 nul 字符；
• 按字掃描剩余的字符串；如果發現字中帶 nul，則掃描并返回其位置。

實現細節

整個算法中，比較難理解的是判斷字中是否帶 nul 字符。具體的方法是計算兩個中間變量：

1. a = (x - 0x01010101)
2. b = (~x & 0x80808080)
3. 計算 a & b == 0

這里的 0x01010101 和 0x80808080 可以進一步擴展。第一步，如果每個字節都 <= 0x7f，只要那個字節不是 0，做差必然得到一個 < 0x80 的結果（換言之，最高位是0）；如果有字節 >= 0x81，做差必然得到一個 > 0x80 的結果。對于等于 0x80 的情況，我們會得到 0x7f，但這并不重要。

注意到，此處，任何一個字節的最高 bit 是 1 的話，則必然是前面兩種情況之一：要么這個字節是 0，要么它 >= 0x81。如果不考慮后一種情況，我們直接把結果 & 0x80808080 即可；然而，由于需要考慮后一種情況，我們接著計算 ~x & 0x80808080。若某一字節 >= 0x80，則對應的結果將是那個位置上的一個 0x80。

將兩個結果做邏輯與，若結果非 0 則說明至少有一個字節是 nul。

這里說起來的過程很復雜，但事實上計算機計算這些要比一個一個去判斷每個字節是否為 0 要快。這里有幾方面的原因：

• 按字長做操作，令 CPU 無需模擬按字節為長度操作的情況，后者是比較耗時的；
• 前兩步操作（分別計算a, b）可以并發執行；
• 最后一步操作可以直接在兩個寄存器之間進行，且是速度較快的與運算；

在實際的實現中，還有一些其他的技巧。

第一個技巧是，從第一個小節就開始用字長的操作。一般來說，內存分配器在分配內存時是以字邊界開始的，因此，通常 strlen() 的操作的指針都是對齊的。不過，即使不是，這個指針往前退到第一個整字位置（例如字長=8，指針 0x9，則退回 0x8）開始的一個整字必然是在同一個內存頁上，因此這個訪問不會越界。如果在這個整字中有 nul 字符，我們只需從指針開始處掃描到第一個整字結尾的地方即可知道是不是真的找到了字符串的末尾。

由于整個字已經在處理器緩存中，后續的循環也不會太慢。

第二個技巧與此類似，我們一直都用整字的操作。如果字的起始地址在內存頁中，則終止地址也必然在同一個內存頁中。這個訪問同樣也不會發生意外越界（盡管在分配內存時可能出現類似分配了 4 個字節，但訪問了 8 個字節的情況）。換言之，如果程序原先不會發生越界異常，則現在也不會。

這個版本的 strlen 源代碼可以在?這里?找到。