optimize ctlz and add cttz; fixes #797

2 files changed, 53 insertions, 5 deletions

diff --git a/src/library.js b/src/library.js
index c537ba57..647aa738 100644
--- a/src/library.js
+++ b/src/library.js
@@ -4862,13 +4862,25 @@ LibraryManager.library = {
 #endif
   },
 
-  llvm_ctlz_i32: function(x) {
-    for (var i=0; i<32; i++) {
-        if ( (x & (1 << (31-i))) != 0 ) {
-            return i;
+  llvm_ctlz_i32__deps: [function() {
+    function ctlz(x) {
+      for (var i = 0; i < 8; i++) {
+        if (x & (1 << (7-i))) {
+          return i;
         }
+      }
+      return 8;
     }
-    return 32;
+    return 'var ctlz_i8 = [' + range(256).map(function(x) { return ctlz(x) }).join(',') + '];';
+  }],
+  llvm_ctlz_i32: function(x) {
+    var ret = ctlz_i8[x >>> 24];
+    if (ret < 8) return ret;
+    var ret = ctlz_i8[(x >> 16)&0xff];
+    if (ret < 8) return ret + 8;
+    var ret = ctlz_i8[(x >> 8)&0xff];
+    if (ret < 8) return ret + 16;
+    return ctlz_i8[x&0xff] + 24;
   },
 
   llvm_ctlz_i64__deps: ['llvm_ctlz_i32'],
@@ -4882,6 +4894,38 @@ LibraryManager.library = {
 #endif
   },
 
+  llvm_cttz_i32__deps: [function() {
+    function cttz(x) {
+      for (var i = 0; i < 8; i++) {
+        if (x & (1 << i)) {
+          return i;
+        }
+      }
+      return 8;
+    }
+    return 'var cttz_i8 = [' + range(256).map(function(x) { return cttz(x) }).join(',') + '];';
+  }],
+  llvm_cttz_i32: function(x) {
+    var ret = cttz_i8[x & 0xff];
+    if (ret < 8) return ret;
+    var ret = cttz_i8[(x >> 8)&0xff];
+    if (ret < 8) return ret + 8;
+    var ret = cttz_i8[(x >> 16)&0xff];
+    if (ret < 8) return ret + 16;
+    return cttz_i8[x >>> 24] + 24;
+  },
+
+  llvm_cttz_i64__deps: ['llvm_cttz_i32'],
+  llvm_cttz_i64: function(l, h) {
+    var ret = _llvm_cttz_i32(l);
+    if (ret == 32) ret += _llvm_cttz_i32(h);
+#if USE_TYPED_ARRAYS == 2
+    {{{ makeStructuralReturn(['ret', '0']) }}};
+#else
+    return ret;
+#endif
+  },
+
   llvm_trap: function() {
     throw 'trap! ' + new Error().stack;
   },
diff --git a/tests/runner.py b/tests/runner.py
index 4e79f7e9..58a79a9c 100755
--- a/tests/runner.py
+++ b/tests/runner.py
@@ -1220,6 +1220,8 @@ m_divisor is 1091269979
           extern unsigned int llvm_bswap_i32(unsigned int x);
           extern int32_t llvm_ctlz_i32(int32_t x);
           extern int64_t llvm_ctlz_i64(int64_t x);
+          extern int32_t llvm_cttz_i32(int32_t x);
+          extern int64_t llvm_cttz_i64(int64_t x);
           extern int llvm_expect_i32(int x, int y);
         }
 
@@ -1235,6 +1237,7 @@ m_divisor is 1091269979
             printf("%x,%x,%x,%x\n", y&0xff, (y>>8)&0xff, (y>>16)&0xff, (y>>24)&0xff);
 
             printf("%d,%d\n", (int)llvm_ctlz_i64(((int64_t)1) << 40), llvm_ctlz_i32(1<<10));
+            printf("%d,%d\n", (int)llvm_cttz_i64(((int64_t)1) << 40), llvm_cttz_i32(1<<10));
 
             printf("%d\n", llvm_expect_i32(x % 27, 3));
 
@@ -1250,6 +1253,7 @@ c8,ef
 8a,15,de,c5
 c5,de,15,8a
 23,21
+40,10
 13
 72057594037927936
 ''')