3 ms·
For me coolest part is the algorithm for determining if word contains zero byte. #define ALIGN (sizeof(size_t)) #define ONES ((size_t)-1/UCHAR_MAX)
by scotty79 10y ago
For me coolest part is the algorithm for determining if word contains zero byte.
#define ALIGN (sizeof(size_t))
#define ONES ((size_t)-1/UCHAR_MAX)
#define HIGHS (ONES * (UCHAR_MAX/2+1))
#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS)
Assuming sizeof(size_t) is 4 and UCHAR_MAX is FF...
It takes FF FF FF FF (by casting -1 to unsigned size_t), divides it by FF, getting 01 01 01 01 (ONES).
Then gets 80 80 80 80 (HIGHS) by multiplying 01 01 01 01 by 80 (which is gets from (FF+1)/2).
Once it has these two values it tests which bytes are lower than 80 by doing ~(x) & HIGHS and keeps result in highest bit of each byte and zeroes lower ones.
Other part is subtracting ONES from (x) which results in highest bit set in each byte either because (x) had more than 80 in that byte or (x) having zero in that byte and borrowing from higher byte (underflow in case of highest byte).
ANDing those two cases rules out highest bit set due to (x) byte being more than 80. What's left is all zeroes if and only if all bytes of (x) were non-zero.
Funny thing is that if borrowing from higher byte happens (because some byte was zero) it might mess up test for that higher byte but it doesn't matter because you will already detect zero in lower byte so you don't care about test on higher bytes then.
If what I wrote above is unclear then try here: http://stackoverflow.com/a/34643025/166921 http://stackoverflow.com/a/34643025/166921
This is algorithm that checks if word has a byte that is less than given value (1 in that case, but surely valid up to 7F ... maybe more by some magic? probably not...). Also works for different lengths of "words" and "bytes" provided that whole number of "bytes" fits in a "word".
- scotty79 10y agoThus I give you my first Rust program ;) // needs in main.rs or lib.rs #![feature(const_fn)] use std::os::raw::c_schar; use std::mem; const ALLSET:usize = (-1_isize) as usize; const MAXCHR:usize = u8::max_value() as usize; const ONES:usize = ALLSET / MAXCHR; const HIGHS:usize = ONES * ((MAXCHR+1)/2); const ALIGN:usize = 8; // mem::size_of::<usize>(); // mem::size_of<T>() is not const fn (yet?) pub unsafe extern "C" fn strlen(s: *const c_schar) -> usize { let mut i:usize = 0; loop { if *s.offset(i as isize) == 0 { return i; } i += 1; if (i % ALIGN) == 0 { break; } } loop { let v = *mem::transmute::<*const c_schar, *const usize>(s.offset(i as isize)); if v.wrapping_sub(ONES) & !v & HIGHS != 0 { break; } i += ALIGN; } loop { if *s.offset(i as isize) == 0 { return i; } i += 1; } }