utils/naf.c: Non-adjacent form calculator, from math/mpreduce.c.

Rescue the plain old state machine, in case it's interesting later.

diff --git a/utils/naf.c b/utils/naf.c
new file mode 100644 (file)
index 0000000..550a271
--- /dev/null
+++ b/utils/naf.c
@@ -0,0 +1,30 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "mp.h"
+#include "mptext.h"
+
+
+int main(int argc, char *argv[])
+{
+  mp *x;
+  mpscan sc;
+  unsigned long d, i;
+  enum { Z = 0, Z1 = 2, X = 4, X0 = 6 };
+  unsigned st = Z;
+
+  x = mp_readstring(MP_NEW, argv[1], 0, 0);
+  d = mp_bits(x);
+
+  for (i = 0, mp_scan(&sc, x); mp_step(&sc); i++) {
+    switch (st | mp_bit(&sc)) {
+      case  Z | 1: st = Z1; break;
+      case Z1 | 0: st =         Z; printf("+ %lu\n", i - 1); break;
+      case Z1 | 1: st =         X; printf("- %lu\n", i - 1); break;
+      case  X | 0: st = X0; break;
+      case X0 | 1: st =         X; printf("- %lu\n", i - 1); break;
+      case X0 | 0: st =         Z; printf("+ %lu\n", i - 1); break;
+    }
+  }
+  if (st >= X) printf("+ %lu\n", i - 1);
+}