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, 14 insertions, 7 deletions

diff --git a/lfs.c b/lfs.c
index 52bdb6d..927e7c8 100644
--- a/lfs.c
+++ b/lfs.c
@@ -1004,15 +1004,22 @@ int lfs_dir_rewind(lfs_t *lfs, lfs_dir_t *dir) {
 
 /// File index list operations ///
 static int lfs_ctz_index(lfs_t *lfs, lfs_off_t *off) {
-    lfs_off_t i = 0;
-
-    while (*off >= lfs->cfg->block_size) {
-        i += 1;
-        *off -= lfs->cfg->block_size;
-        *off += 4*(lfs_ctz(i) + 1);
+    lfs_off_t size = *off;
+    lfs_off_t i = size / (lfs->cfg->block_size-2*4);
+    if (i == 0) {
+        return 0;
     }
 
-    return i;
+    lfs_off_t nsize = (lfs->cfg->block_size-2*4)*i + 4*lfs_popc(i-1) + 2*4;
+    lfs_soff_t noff = size - nsize;
+
+    if (noff < 0) {
+        *off = noff + lfs->cfg->block_size;
+        return i-1;
+    } else {
+        *off = noff + 4*(lfs_ctz(i) + 1);
+        return i;
+    }
 }
 
 static int lfs_ctz_find(lfs_t *lfs,