Merge pull request #20 from Perlbotics/bugfix-kbd

Bugfix kbd

5 files changed, 171 insertions, 9 deletions

diff --git a/makefile b/makefile
index 5c3f545..5076c6c 100644
--- a/makefile
+++ b/makefile
@@ -15,7 +15,7 @@ SONAME = libzxcvbn.so.0
 
 WORDS = words-eng_wiki.txt words-female.txt words-male.txt words-passwd.txt words-surname.txt words-tv_film.txt
 
-all: test-file test-inline test-c++inline test-c++file test-shlib test-statlib
+all: test-file test-inline test-c++inline test-c++file test-shlib test-statlib test-internals
 
 test-shlib: test.c $(TARGET_LIB)
 	if [ ! -e libzxcvbn.so ]; then ln -s $(TARGET_LIB) libzxcvbn.so; fi
@@ -44,6 +44,10 @@ test-inline: test.c zxcvbn-inline.o
 	$(CC) $(CPPFLAGS) $(CFLAGS) \
 		-o test-inline test.c zxcvbn-inline.o $(LDFLAGS) -lm
 
+test-internals: test-internals.c zxcvbn.c dict-crc.h zxcvbn.h
+	$(CC) $(CPPFLAGS) $(CFLAGS) \
+		-o test-internals test-internals.c $(LDFLAGS) -lm
+
 zxcvbn-inline-pic.o: zxcvbn.c dict-src.h zxcvbn.h
 	$(CC) $(CPPFLAGS) $(CFLAGS) -fPIC -c -o $@ $<
 
@@ -80,7 +84,9 @@ zxcvbn-c++file.o: zxcvbn.c dict-crc.h zxcvbn.h
 	$(CXX) $(CPPFLAGS) $(CXXFLAGS) \
 		-DUSE_DICT_FILE -c -o zxcvbn-c++file.o zxcvbn.cpp
 
-test: test-file test-inline test-c++inline test-c++file test-shlib test-statlib testcases.txt
+test: test-internals test-file test-inline test-c++inline test-c++file test-shlib test-statlib testcases.txt
+	@echo Testing internals...
+	./test-internals
 	@echo Testing C build, dictionary from file
 	./test-file -t testcases.txt
 	@echo Testing C build, dictionary in executable
@@ -97,7 +103,7 @@ test: test-file test-inline test-c++inline test-c++file test-shlib test-statlib
 
 clean:
 	rm -f test-file zxcvbn-file.o test-c++file zxcvbn-c++file.o 
-	rm -f test-inline zxcvbn-inline.o zxcvbn-inline-pic.o test-c++inline zxcvbn-c++inline.o
+	rm -f test-inline test-internals zxcvbn-inline.o zxcvbn-inline-pic.o test-c++inline zxcvbn-c++inline.o
 	rm -f dict-*.h zxcvbn.dict zxcvbn.cpp test.cpp
 	rm -f dictgen
 	rm -f ${TARGET_LIB} ${SONAME} libzxcvbn.so test-shlib libzxcvbn.a test-statlib
diff --git a/test-internals.c b/test-internals.c
new file mode 100644
index 0000000..0ccd0de
--- /dev/null
+++ b/test-internals.c
@@ -0,0 +1,145 @@
+
+/* Internal tests that cannot be run against the library without unnecessary export of symbols.
+   Copyright (c) 2017, Perlbotics / see LICENSE.txt
+ */
+
+
+#include "zxcvbn.h"
+/* need access to internals for testing; not linked against library, just inlined */
+#include "zxcvbn.c"
+
+
+/**********************************************************************************
+ * Internal checks: Validate if the first element of each group is sorted in
+ *                  ascending order. CharBinSearch(...) fails otherwise.
+ * Returns 0 on success.
+ * Returns element index [1..] of first error entry that is less than previous one.
+ */
+static int check_order(const uint8_t *Ents, unsigned int NumEnts, unsigned int SizeEnts) {
+  const uint8_t *last;
+  unsigned int i;
+
+  if (!Ents) return 0;
+  last = 0;
+
+  for (i = 0; i < NumEnts; ++i, Ents += SizeEnts) {
+    if (last  &&  *last > *Ents) {
+      unsigned int j;
+
+      printf("Entry#%d [%d]:  '%c' > '%c'  (0x%02X > 0x%02X)\n    A:  ", i, i * SizeEnts, *last, *Ents, *last, *Ents);
+      for (j = 0; j < SizeEnts; ++j) {
+        printf("'%c' ", last[j] ? last[j] : ' ');
+      }
+      printf("\n    >\n    B:  ");
+      for (j = 0; j < SizeEnts; ++j) {
+        printf("'%c' ", Ents[j] ? Ents[j] : ' ');
+      }
+      printf("\n");
+
+      return i;
+    }
+    last = Ents;
+  }
+
+  return 0; /* cannot be a misordered position; first possible one: 1 */
+}
+
+/**********************************************************************************
+ * Internal checks: Checks keyboard data integrity.
+ * Returns 0 on succes.
+ * Otherwise, number of errors are reported.
+ */
+static unsigned int selftest_keyboards() {
+  unsigned int errors;
+  const Keyboard_t *k;
+  unsigned int Indx;
+  const uint8_t *keys;
+  int i,j,errpos, blanks;
+
+  errors = 0;
+  for(k = Keyboards, Indx = 0; Indx < (sizeof Keyboards / sizeof Keyboards[0]); ++Indx, ++k) {
+    /* if one of these assrtion fails, we cannot use binary search algorithm */
+    if (k->Shifts  &&  strlen((const char*)k->Shifts) % 2 == 1) {
+      printf("ERROR: Keyboard[%d]: Shifts-string has odd number of entries.\n", Indx);
+      ++errors;
+    }
+
+    if ( (errpos = check_order(k->Shifts, k->NumShift, 2)) ) {
+      printf("ERROR: Keyboard[%d]: Error above in sort order of Shifts-string near item #%d.\n", Indx, errpos);
+      ++errors;
+    }
+
+    if ( (errpos = check_order(k->Keys, k->NumKeys, k->NumNear)) ) {
+      printf("ERROR: Keyboard[%d]: Error above in sort order of keyboard-entries! Problem near item #%d.\n", Indx, errpos);
+      ++errors;
+      continue;
+    }
+
+    /* For each key (c0), check all its neighbours (ci):
+     * Does the neighbour key (c1==ci) have an entry (cx) in the opposite direction [rev_idx]
+     * pointing back to the current key c0?
+     * c0: ...ci..   -->   c1: ..cx...   -->   cx==c0?
+     */
+    keys = k->Keys;
+    blanks = 0;
+    for(i = 0; i < k->NumKeys; ++i) {
+      uint8_t c0;
+      c0 = keys[i * k->NumNear];
+
+      for (j = 0; j < k->NumNear - 1; ++j) {
+        const uint8_t *c1;
+        uint8_t ci, cx;
+        int rev_idx;
+
+        /* rev_idx: reverse/opposite index to find opposite key location [0..6|8] --> [0..6|8] */
+        rev_idx = (j + (k->NumNear - 1)/2) % (k->NumNear - 1);
+        ci = keys[i * k->NumNear + j + 1];
+
+        if (ci) {
+          c1 = CharBinSearch(ci, keys, k->NumKeys, k->NumNear);
+          if (c1) {
+            if (ci == c0) {
+              printf("ERROR: Keyboard[%d]:  recursion - key '%c' cannot be its own neighbour!\n", Indx, *c1);
+              ++errors;
+            } else {
+              if ( (cx = c1[ 1 + rev_idx ]) ) {
+                if ( cx != c0 ) {
+                  printf("ERROR: Keyboard[%d]:  c0='%c':...(ci=%c)... ->  c1='%c':...(cx=%c)... --!--> c0='%c':... \n",
+                         Indx, c0, ci, *c1, cx, c0);
+                  ++errors;
+                }
+              } else { /* reverse pointer is NULL */
+                printf("ERROR: Keyboard[%d]:  reverse entry missing in row c1='%c'[%d] pointing back to c0='%c'!\n", Indx, *c1, 1+rev_idx, c0);
+                ++errors;
+              }
+            }
+          } else {
+            printf("ERROR: Keyboard[%d]:  no entry (neighbour list) found for src-char c1==ci='%c'\n", Indx, ci);
+            ++errors;
+          }
+        } else { /* blank neighbour key reference found */
+          ++blanks;
+        }
+      }
+    }
+    if (blanks != k->NumBlank) {
+      printf("ERROR: Keyboard[%d]:  number of blank keys announced (%d) does not match number of blank keys counted (%d)!\n",
+             Indx, k->NumBlank, blanks);
+      ++errors;
+    }
+  }
+  return errors;
+}
+
+
+
+
+int main() {
+  unsigned int errors;
+
+  if( (errors = selftest_keyboards()) ){  /* currently only these */
+    printf("FAILED: [KEYBOARDS] - selftest returned %d error(s).\n", errors);
+  }
+
+  return errors ? 1 : 0;
+}
diff --git a/test.c b/test.c
index 8a4797b..df2b41f 100644
--- a/test.c
+++ b/test.c
@@ -210,6 +210,7 @@ int main(int argc, char **argv)
     Quiet = 0;
     Checks = 0;
     White = 0;
+
     if (!ZxcvbnInit("zxcvbn.dict"))
     {
         printf("Failed to open dictionary file\n");
diff --git a/testcases.txt b/testcases.txt
index 8eaeac3..cddf519 100644
--- a/testcases.txt
+++ b/testcases.txt
@@ -59,4 +59,8 @@ pass.word.pass.word.pass.word.          60.41
 passpasswordword         17.28
 quvpzquvpz               24.50
 
+#-- with UK KBD  (US-KBD=17.08)
+jkl;'#                   11.12
+
 magicfavoriteunclepromisedpublicbotherislandjimseriouslycellleadknowingbrokenadvicesomehowpaidblairlosingpushhelpedkillingusuallyearlierbosslaurabeginninglikedinnocentdocruleselizabethsabrinasummerexcoplearnedthirtyrisklettingphillipspeakingofficerridiculoussupportafternoonericwithsobutallwellareheohaboutrightyou're   545.9
+
diff --git a/zxcvbn.c b/zxcvbn.c
index 7ab2eb2..8e96609 100644
--- a/zxcvbn.c
+++ b/zxcvbn.c
@@ -29,6 +29,13 @@
 #include <math.h>
 #include <float.h>
 
+/* printf */
+#ifdef __cplusplus
+#include <cstdio>
+#else
+#include <stdio.h>
+#endif
+
 #ifdef USE_DICT_FILE
 #if defined(USE_FILE_IO) || !defined(__cplusplus)
 #include <stdio.h>
@@ -932,19 +939,19 @@ static const uint8_t UK_Shift[] = "!1\"2$4%5&7(9)0*8:;<,>.?/@'AaBbCcDdEeFfGgHhIi
 static const uint8_t US_Shift[] = "!1\"'#3$4%5&7(9)0*8:;<,>.?/@2AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz^6_-{[|\\}]~`";
 
 
-/* Neighour tables */
+/* Neighbour tables */
 static const uint8_t UK_Qwerty[48*7] =
 {
 /* key, left, up-left, up-right, right, down-right, down-left */
     '#', '\'',']',   0,   0,   0,   0,    '\'',';', '[', ']', '#',   0, '/',
-    ',', 'm', 'k', 'l', '.',   0,   0,    '-', '0',   0,   0, '-', 'p', 'o',
+    ',', 'm', 'k', 'l', '.',   0,   0,    '-', '0',   0,   0, '=', '[', 'p',
     '.', ',', 'l', ';', '/',   0,   0,    '/', '.', ';', '\'',  0,   0,   0, 
     '0', '9',   0,   0, '-', 'p', 'o',    '1', '`',   0,   0, '2', 'q',   0, 
     '2', '1',   0,   0, '3', 'w', 'q',    '3', '2',   0,   0, '4', 'e', 'w',
     '4', '3',   0,   0, '5', 'r', 'e',    '5', '4',   0,   0, '6', 't', 'r',
     '6', '5',   0,   0, '7', 'y', 't',    '7', '6',   0,   0, '8', 'u', 'y',
     '8', '7',   0,   0, '9', 'i', 'u',    '9', '8',   0,   0, '0', 'o', 'i',
-    ';', 'l', 'o', 'p','\'', '/', '.',    '=', '-',   0,   0,   0, ']', '[',
+    ';', 'l', 'p', '[','\'', '/', '.',    '=', '-',   0,   0,   0, ']', '[',
     '[', 'p', '-', '=', ']', '\'',';',    '\\',  0,   0, 'a', 'z',   0,   0,
     ']', '[', '=',   0,   0, '#','\'',    '`',   0,   0,   0, '1',   0,   0,
     'a',   0, 'q', 'w', 's', 'z','\\',    'b', 'v', 'g', 'h', 'n',   0,   0,
@@ -990,7 +997,7 @@ static const uint8_t US_Qwerty[47*7] =
     'x', 'z', 's', 'd', 'c',   0,   0,    'y', 't', '6', '7', 'u', 'h', 'g',
     'z',   0, 'a', 's', 'x',   0,   0,
 };
-static const uint8_t Dvorak[48*7] =
+static const uint8_t Dvorak[47*7] =
 {
     '\'',  0, '1', '2', ',', 'a',   0,    ',','\'', '2', '3', '.', 'o', 'a',
     '-', 's', '/', '=',   0,   0, 'z',    '.', ',', '3', '4', 'p', 'e', 'o',
@@ -1148,9 +1155,9 @@ static void SpatialMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start,
     for(CurLen = MaxLen; CurLen >= MIN_SPATIAL_LEN;CurLen = Len - 1)
     {
         Len = 0;
-        memset(&Extra, 0, sizeof Extra);
         for(k = Keyboards, Indx = 0; Indx < (sizeof Keyboards / sizeof Keyboards[0]); ++Indx, ++k)
         {
+            memset(&Extra, 0, sizeof Extra);
             Len = DoSptlMatch(Passwd, CurLen, k, &Extra);
             if (Len > 0)
             {
@@ -1201,7 +1208,6 @@ static void SpatialMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start,
                 p->Length = Len;
                 AddMatchRepeats(Result, p, Passwd, MaxLen);
                 AddResult(Result, p, MaxLen);
-                break;
             }
         }
     }