From 729be61ffc589a01850d93ab9b9679b097b559b3 Mon Sep 17 00:00:00 2001 From: Perlbotics Date: Wed, 15 Nov 2017 21:11:43 +0100 Subject: Fix for UK_Qwerty layout. Fix for Dvorak array size. Two layout fixes around the keys ',' and ';'. Dvorak layout array size reduced to 47*7. Test outcome was not affected. --- zxcvbn.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/zxcvbn.c b/zxcvbn.c index 7ab2eb2..af84b65 100644 --- a/zxcvbn.c +++ b/zxcvbn.c @@ -937,14 +937,14 @@ 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 +990,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', -- cgit v1.2.3 From 1316210f7d795de8ff7d4c5651501a33248b6e20 Mon Sep 17 00:00:00 2001 From: Perlbotics Date: Wed, 15 Nov 2017 21:34:07 +0100 Subject: Exhaustive spacial tests across all registered keyboard layouts. The previous test stopped when a (any) match for a given substring was found. While this is slightly faster than an exhaustive search across all registered keyboard layouts, it could result in a too optimistic entropy estimation. Example: The string jkl;'# yield the following entropies depending whether the UK-keyboard layout had a chance to be tested or not: Layout Code base Entropy ---------------------------------------------------------------------- US previous bits=17.080 log10=5.142 Multi-word extra bits=1.0 UK this bits=11.116 log10=3.346 Multi-word extra bits=0.0 ---------------------------------------------------------------------- The time to perform these checks were identical (i.e. 0.07ms, here). A new testcase for UK-layout was added. All legacy tests pass. New test passes. valgrind-check: passed --- testcases.txt | 4 ++++ zxcvbn.c | 3 +-- 2 files changed, 5 insertions(+), 2 deletions(-) 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 af84b65..8afe64d 100644 --- a/zxcvbn.c +++ b/zxcvbn.c @@ -1148,9 +1148,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 +1201,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; } } } -- cgit v1.2.3 From 3417c5e6d0a3647c6d453dbd3fad91649663df2b Mon Sep 17 00:00:00 2001 From: Perlbotics Date: Thu, 16 Nov 2017 00:14:04 +0100 Subject: Internal selftest added. Keyboard-layout integrity checked. Test binaries perform additional selftests now. This helps to detect errors in keyboard layout definitions early. --- test.c | 10 +++++ zxcvbn.c | 143 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 152 insertions(+), 1 deletion(-) diff --git a/test.c b/test.c index 8a4797b..4634dab 100644 --- a/test.c +++ b/test.c @@ -33,6 +33,9 @@ #include "stdafx.h" #endif +/* forward declaration / not part of official API */ +unsigned int _selftest_errors(); + const char *UsrDict[] = { "Onename.Twoname@example.com", "Onename", "Twoname", "example.com", "example", @@ -207,9 +210,16 @@ int DoChecks(char *file) int main(int argc, char **argv) { int i, Quiet, Checks, White; + unsigned int SelftestErrors; Quiet = 0; Checks = 0; White = 0; + + SelftestErrors = _selftest_errors(); + printf("Selftest returned %d error(s).\n", SelftestErrors ); + if (SelftestErrors) + return 1; + if (!ZxcvbnInit("zxcvbn.dict")) { printf("Failed to open dictionary file\n"); diff --git a/zxcvbn.c b/zxcvbn.c index 8afe64d..91785b3 100644 --- a/zxcvbn.c +++ b/zxcvbn.c @@ -29,6 +29,13 @@ #include #include +/* printf */ +#ifdef __cplusplus +#include +#else +#include +#endif + #ifdef USE_DICT_FILE #if defined(USE_FILE_IO) || !defined(__cplusplus) #include @@ -932,7 +939,7 @@ 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 */ @@ -1759,3 +1766,137 @@ void ZxcvbnFreeInfo(ZxcMatch_t *Info) Info = p; } } + +/********************************************************************************** + * 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; +} + +/********************************************************************************** + * Performs all internal checks. + * Should be used by test programs. Might be used by applications. + * Returns 0 on success (no output). + * Reports number of errors otherwise. Error indication printed to STDOUT. + */ +unsigned int _selftest_errors() { + unsigned int errors; + errors = _selftest_keyboards(); /* currently only these */ + return errors; +} -- cgit v1.2.3 From f7037ff39bdff62f20ba325f25c86c035840691d Mon Sep 17 00:00:00 2001 From: Perlbotics Date: Tue, 21 Nov 2017 23:46:21 +0100 Subject: Selftests removed from library and placed into test-internals. Selftests extracted (removed) from zxcvbn.c and test.c and placed into test-internals.c Makefile updated. --- makefile | 12 +++-- test-internals.c | 145 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ test.c | 9 ---- zxcvbn.c | 134 -------------------------------------------------- 4 files changed, 154 insertions(+), 146 deletions(-) create mode 100644 test-internals.c 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 4634dab..df2b41f 100644 --- a/test.c +++ b/test.c @@ -33,9 +33,6 @@ #include "stdafx.h" #endif -/* forward declaration / not part of official API */ -unsigned int _selftest_errors(); - const char *UsrDict[] = { "Onename.Twoname@example.com", "Onename", "Twoname", "example.com", "example", @@ -210,16 +207,10 @@ int DoChecks(char *file) int main(int argc, char **argv) { int i, Quiet, Checks, White; - unsigned int SelftestErrors; Quiet = 0; Checks = 0; White = 0; - SelftestErrors = _selftest_errors(); - printf("Selftest returned %d error(s).\n", SelftestErrors ); - if (SelftestErrors) - return 1; - if (!ZxcvbnInit("zxcvbn.dict")) { printf("Failed to open dictionary file\n"); diff --git a/zxcvbn.c b/zxcvbn.c index 91785b3..8e96609 100644 --- a/zxcvbn.c +++ b/zxcvbn.c @@ -1766,137 +1766,3 @@ void ZxcvbnFreeInfo(ZxcMatch_t *Info) Info = p; } } - -/********************************************************************************** - * 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; -} - -/********************************************************************************** - * Performs all internal checks. - * Should be used by test programs. Might be used by applications. - * Returns 0 on success (no output). - * Reports number of errors otherwise. Error indication printed to STDOUT. - */ -unsigned int _selftest_errors() { - unsigned int errors; - errors = _selftest_keyboards(); /* currently only these */ - return errors; -} -- cgit v1.2.3