Megnéztem, hogy a glibc hogyan csinálja a strlen() vagy strchr() implementációjában. Nagyon durva! Eltartott jódarabig, mire megértettem, a baromi hosszú megjegyzés ellenére. (Egyébként az egyik "left" szó helyett "right"-ot akartak írni, ez tovább nehezített a megértésen.) Mondjuk az alap ötlet tök egyszerű: az összeadás vagy kivonás műveletet kell okosan úgy használni, hogy ha egy byte csupa nulla bitből áll, akkor a carry bit a végén másképp alakul, mint ha nem csupa nullából. Konkrétan hozzáadja a bináris 01111110 11111110 11111110 11111111 számot, és azzal játszik, hogy ha valamelyik byte nullás volt, akkor ott a carry bit elakad és ezáltal a következő byte LSB-je nem változik, míg ha bármelyik bit 1-es volt, akkor az végigszalad egészen a következő byte LSB-jéig és ott ellenkezőjére változtatja azt a bitet és ott megáll.
Kivonat a glibc-2.7/string/strchr.c fájlból:
unsigned long int magic_bits = 0x7efefeffL;
unsigned long int longword = (((amit tesztelni akarsz)));
/* We tentatively exit the loop if adding MAGIC_BITS to
LONGWORD fails to change any of the hole bits of LONGWORD. */
if ((((longword + magic_bits) ^ ~longword) & ~magic_bits) != 0) {
/* vagy van 0-s byte, vagy false pozitívként elképzelhető, hogy az első byte 128-as, de mivel itt úgyis elkezdesz egyenként lépni, így ez kiszűrhető */
} else {
/* tuti nincs nullás byte, száguldhatsz tovább */
}
Assemblyben hozzáférsz a kieső carry bithez, így valszeg a false positive is elkerülhető.