Update to upstream 2.4+dfsg

[git-debrebase anchor: new upstream 2.4+dfsg, merge]

6 files changed, 189 insertions, 26 deletions

diff --git a/README.md b/README.md
index 73cd924..1fe31e7 100644
--- a/README.md
+++ b/README.md
@@ -5,18 +5,18 @@ The code is intended to be included as part of the source of a C/C++ program. Li
 original this code is for character sets which use single byte characters primarily in the
 code range 0x20 to 0x7E.
 
-The original coffee script version is available at 
+The original CoffeeScript version is available at 
  https://github.com/lowe/zxcvbn
 
 An article on the reasons for zxcvbn is at
-https://tech.dropox.com/2012/04/zxcvbn-realistic-password-strength-estimation
+https://blogs.dropbox.com/tech/2012/04/zxcvbn-realistic-password-strength-estimation/
 
-##Building
+## Building
 
 The makefile will build several test programs to test the code. It shows the steps needed
 to use the code in C and C++ programs, using the dictionary data read from file or included
 within the program executable.
-The makefile has only been tried on Linux using GCC version 4.8.4, but should be faily
+The makefile has only been tried on Linux using GCC version 4.8.4, but should be fairly
 portable to other systems.
 
 When dictionary data is included in your program's executable, the files `zxcvbn.c` ,
@@ -32,7 +32,7 @@ Rename `zxcvbn.c` to `zxcvbn.cpp` (or whatever your compiler uses) to compile as
 The `dict*.h` and `zxcvbn.dict` files are generated by the dictgen program compiled from
 dict-generate.cpp (see makefile for details).
 
-##Using
+## Using
 
 Initially call `ZxcvbnInit()` with the pathname of the `zxcvbn.dict` file. This can be
 omitted when dictionary data is included in the executable.
@@ -49,7 +49,7 @@ omitted when dictionary data is included in the executable.
 Review the test program in `test.c` for an example.
 
 
-## Differences from the original version.
+## Differences from the original version
 
 The entropy calculated will sometimes differ from the original because of
 
@@ -57,28 +57,28 @@ The entropy calculated will sometimes differ from the original because of
 **;'#** is a spacial sequence.
 * The different character classes in a password are taken into account when calculating the
 strength of brute-force matches.
-* Dijktra's path searching algorithm is used to combine parts of the entered password. This
+* Dijkstra's path searching algorithm is used to combine parts of the entered password. This
 can result in the found parts of the password being combined differently than the
-original coffee script. E.g. the password **passwordassword**
-is combined by the original coffee script as **p** (3.5 bits) + **asswordassword** (12.6
+original CoffeeScript. E.g. the password **passwordassword**
+is combined by the original CoffeeScript as **p** (3.5 bits) + **asswordassword** (12.6
 bits) + multiple part allowance (1.0bit) to give total entropy of 17.1 bits. This
 implementation combines it as **password** (1.0 bit) + **assword** (11.6 bits) + multiple
 part allowance (1.0bit) to give 13.6 bits.
-* For multi part passwords the original coffee script version multiplies the number of
+* For multi-part passwords the original CoffeeScript version multiplies the number of
 guesses needed by the factorial of the number of parts. This is not possible in this
-version as Dijktra's algorithm is used. Instead one bit entropy is added for the part at the
+version as Dijkstra's algorithm is used. Instead one bit entropy is added for the part at the
 end of the password, 1.7 bits for each part in the middle of a password and nothing
-for the part at the beginning. This gives similar results compared to the coffee script
+for the part at the beginning. This gives similar results compared to the CoffeeScript
 version when there are 4 or less parts, but will differ significantly when there are many
 parts (which is likely to be a rare occurrence).
 
 
-##References
+## References
 
-The original coffee-script version is available at 
+The original CoffeeScript version is available at 
  https://github.com/lowe/zxcvbn
 
-The dictionary words are taken from the original coffee script version.
+The dictionary words are taken from the original CoffeeScript version.
 
 Dictionary trie encoding (used for by the word lookup code) based on idea from the Caroline
 Word Graph from
diff --git a/makefile b/makefile
index 3b1b519..40c88f2 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-10k-pass.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 f9f2b4b..cebb51c 100644
--- a/testcases.txt
+++ b/testcases.txt
@@ -59,4 +59,8 @@ pass.word.pass.word.pass.word.          60.41
 passpasswordword         16.23
 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..ebe9e31 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>
@@ -927,24 +934,25 @@ typedef struct
     int Shifts;
 } SpatialMatchInfo_t;
 
-/* Shift mapping, characters in pairs: first is shifted, second un-shifted. */
-static const uint8_t UK_Shift[] = "!1\"2$4%5&7(9)0*8:;<,>.?/@'AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz^6_-{[|\\}]~#€4£3¬`";
+/* Shift mapping, characters in pairs: first is shifted, second un-shifted. Ordered for increasing shifted character code.*/
+/* Note: on a UK keyboard  \243 is the £ (Pound stirling),  \244 is the ¤ (Euro),  \254 is the ¬ (Not sign)  */
+static const uint8_t UK_Shift[] = "!1\"2$4%5&7(9)0*8:;<,>.?/@'AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz^6_-{[|\\}]~#\2433\2444\254`";
 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 +998,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 +1156,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 +1209,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;
             }
         }
     }