Adopted lfs_ctz_index implementation using popcount

This reduces the O(n^2logn) runtime to read a file to only O(nlog).
The extra O(n) did not touch the disk, so it isn't a problem until the
files become very large, but this solution comes with very little cost.

Long story short, you can find the block index + offset pair for a
CTZ linked-list with this series of formulas:

n' = floor(N / (B - 2w/8))
N' = (B - 2w/8)n' + (w/8)popcount(n')
off' = N - N'
n, off =
  n'-1, off'+B                if off' <  0
  n',   off'+(w/8)(ctz(n')+1) if off' >= 0

For the long story, you will need to see the updated DESIGN.md

1 files changed, 4 insertions, 0 deletions

diff --git a/lfs_util.h b/lfs_util.h
index cee7644..9d23ab4 100644
--- a/lfs_util.h
+++ b/lfs_util.h
@@ -41,6 +41,10 @@ static inline uint32_t lfs_npw2(uint32_t a) {
     return 32 - __builtin_clz(a-1);
 }
 
+static inline uint32_t lfs_popc(uint32_t a) {
+    return __builtin_popcount(a);
+}
+
 static inline int lfs_scmp(uint32_t a, uint32_t b) {
     return (int)(unsigned)(a - b);
 }