src/zxcvbn.c

   1 /**********************************************************************************
   2  * C implementation of the zxcvbn password strength estimation method.
   3  * Copyright (c) 2015-2017 Tony Evans
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a copy
   6  * of this software and associated documentation files (the "Software"), to deal
   7  * in the Software without restriction, including without limitation the rights
   8  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   9  * copies of the Software, and to permit persons to whom the Software is
  10  * furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in
  13  * all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  21  * THE SOFTWARE.
  22  *
  23  **********************************************************************************/
  24
  25 #include <zxcvbn.h>
  26 #include <ctype.h>
  27 #include <string.h>
  28 #include <stdint.h>
  29 #include <math.h>
  30 #include <float.h>
  31
  32 /* printf */
  33 #ifdef __cplusplus
  34 #include <cstdio>
  35 #else
  36 #include <stdio.h>
  37 #endif
  38
  39 #ifdef USE_DICT_FILE
  40 #if defined(USE_FILE_IO) || !defined(__cplusplus)
  41 #include <stdio.h>
  42 #else
  43 #include <fstream>
  44 #endif
  45 #endif
  46
  47 /* For pre-compiled headers under windows */
  48 #if defined (_WIN32) && !defined (__MINGW32__)
  49 #include "stdafx.h"
  50 #endif
  51
  52 /* Minimum number of characters in a incrementing/decrementing sequence match */
  53 #define MIN_SEQUENCE_LEN 3
  54
  55 /* Maximum number of characters to perform full entropy calculation */
  56 #ifndef ZXCVBN_DETAIL_LEN
  57 #define ZXCVBN_DETAIL_LEN 100
  58 #endif
  59
  60 /* Year range for data matching */
  61 #define MIN_YEAR 1901
  62 #define MAX_YEAR 2050
  63
  64 /* Minimum number of characters in a spatial matching sequence */
  65 #define MIN_SPATIAL_LEN 3
  66
  67 /* Minimum number of characters in a repeat sequence match */
  68 #define MIN_REPEAT_LEN 2
  69
  70 /* Additional entropy to add when password is made of multiple matches. Use different
  71  * amounts depending on whether the match is at the end of the password, or in the
  72  * middle. If the match is at the begining then there is no additional entropy.
  73  */
  74 #define MULTI_END_ADDITION 1.0
  75 #define MULTI_MID_ADDITION 1.75
  76
  77 /*################################################################################*
  78  *################################################################################*
  79  * Begin utility function code
  80  *################################################################################*
  81  *################################################################################*/
  82
  83 /**********************************************************************************
  84  * Binomial coefficient function. Uses method described at
  85  *      http://blog.plover.com/math/choose.html
  86  */
  87 static double nCk(int n, int k)
  88 {
  89     int d;
  90     double r;
  91     if (k > n)
  92         return 0.0;
  93     if (!k)
  94         return 1.0;
  95     r = 1.0;
  96     for(d = 1; d <= k; ++d)
  97     {
  98         r *= n--;
  99         r /= d;
 100     }
 101     return r;
 102 }
 103
 104 /**********************************************************************************
 105  * Binary search function to find a character in a string.
 106  * Parameters:
 107  *  Ch      The character to find
 108  *  Ents    The string to search
 109  *  NumEnts The number character groups in the string Ents
 110  *  SizeEnt The size of each character group.
 111  * Returns a pointer to the found character, or null if not found.
 112  */
 113 static const uint8_t *CharBinSearch(uint8_t Ch, const uint8_t *Ents, unsigned int NumEnts, unsigned int SizeEnt)
 114 {
 115     while(NumEnts > 0)
 116     {
 117         const uint8_t *Mid = Ents + (NumEnts >> 1) * SizeEnt;
 118         int Dif = Ch - *Mid;
 119         if (!Dif)
 120         {
 121             return Mid;
 122         }
 123         if (Dif > 0)
 124         {
 125             Ents = Mid + SizeEnt;
 126             --NumEnts;
 127         }
 128         NumEnts /= 2;
 129     }
 130     return 0;
 131 }
 132
 133 /**********************************************************************************
 134  * Calculate potential number of different characters in the passed string.
 135  * Parameters:
 136  *  Str     The string of characters
 137  *  Len     The maximum number of characters to scan
 138  * Returns the potential number of different characters in the string.
 139  */
 140 static int Cardinality(const uint8_t *Str, int Len)
 141 {
 142     int Card=0, Types=0;
 143     int c;
 144     while(Len > 0)
 145     {
 146         c = *Str++ & 0xFF;
 147         if (!c)
 148             break;
 149         if (islower(c))      Types |= 1;    /* Lowercase letter */
 150         else if (isupper(c)) Types |= 2;    /* Uppercase letter */
 151         else if (isdigit(c)) Types |= 4;    /* Numeric digit */
 152         else if (c <= 0x7F)  Types |= 8;    /* Punctuation character */
 153         else                 Types |= 16;   /* Other (Unicode?) */
 154         --Len;
 155     }
 156     if (Types & 1)  Card += 26;
 157     if (Types & 2)  Card += 26;
 158     if (Types & 4)  Card += 10;
 159     if (Types & 8)  Card += 33;
 160     if (Types & 16) Card += 100;
 161     return Card;
 162 }
 163
 164 /**********************************************************************************
 165  * Allocate a ZxcMatch_t struct, clear it to zero
 166  */
 167 static ZxcMatch_t *AllocMatch()
 168 {
 169     ZxcMatch_t *p = MallocFn(ZxcMatch_t, 1);
 170     memset(p, 0, sizeof *p);
 171     return p;
 172 }
 173
 174 /**********************************************************************************
 175  * Add new match struct to linked list of matches. List ordered with shortest at
 176  * head of list. Note: passed new match struct in parameter Nu may be de allocated.
 177  */
 178 static void AddResult(ZxcMatch_t **HeadRef, ZxcMatch_t *Nu, int MaxLen)
 179 {
 180     /* Adjust the entropy to be used for calculations depending on whether the passed match is
 181      * at the begining, middle or end of the password
 182      */
 183     if (Nu->Begin)
 184     {
 185         if (Nu->Length >= MaxLen)
 186             Nu->MltEnpy = Nu->Entrpy + MULTI_END_ADDITION * log(2.0);
 187         else
 188             Nu->MltEnpy = Nu->Entrpy + MULTI_MID_ADDITION * log(2.0);
 189     }
 190     else
 191         Nu->MltEnpy = Nu->Entrpy;
 192
 193     /* Find the correct insert point */
 194     while(*HeadRef && ((*HeadRef)->Length < Nu->Length))
 195         HeadRef = &((*HeadRef)->Next);
 196
 197     /* Add new entry or replace existing */
 198     if (*HeadRef && ((*HeadRef)->Length == Nu->Length))
 199     {
 200         /* New entry has same length as existing, so one of them needs discarding */
 201         if ((*HeadRef)->MltEnpy <= Nu->MltEnpy)
 202         {
 203             /* Existing entry has lower entropy - keep it, discard new entry */
 204             FreeFn(Nu);
 205         }
 206         else
 207         {
 208             /* New entry has lower entropy - replace existing entry */
 209             Nu->Next = (*HeadRef)->Next;
 210             FreeFn(*HeadRef);
 211             *HeadRef = Nu;
 212         }
 213     }
 214     else
 215     {
 216         /* New entry has different length, so add it */
 217         Nu->Next = *HeadRef;
 218         *HeadRef = Nu;
 219     }
 220 }
 221
 222 /**********************************************************************************
 223  * See if the match is repeated. If it is then add a new repeated match to the results.
 224  */
 225 static void AddMatchRepeats(ZxcMatch_t **Result, ZxcMatch_t *Match, const uint8_t *Passwd, int MaxLen)
 226 {
 227     int Len = Match->Length;
 228     const uint8_t *Rpt = Passwd + Len;
 229     int RepeatCount = 2;
 230
 231     while(MaxLen >= (Len * RepeatCount))
 232     {
 233         if (strncmp((const char *)Passwd, (const char *)Rpt, Len) == 0)
 234         {
 235             /* Found a repeat */
 236             ZxcMatch_t *p = AllocMatch();
 237             p->Entrpy = Match->Entrpy + log(RepeatCount);
 238             p->Type = (ZxcTypeMatch_t)(Match->Type + MULTIPLE_MATCH);
 239             p->Length = Len * RepeatCount;
 240             p->Begin = Match->Begin;
 241             AddResult(Result, p, MaxLen);
 242         }
 243         else
 244             break;
 245         ++RepeatCount;
 246         Rpt += Len;
 247     }
 248 }
 249
 250 /*################################################################################*
 251  *################################################################################*
 252  * Begin dictionary matching code
 253  *################################################################################*
 254  *################################################################################*/
 255
 256 #ifdef USE_DICT_FILE
 257 /* Use dictionary data from file */
 258
 259 #if defined(USE_FILE_IO) || !defined(__cplusplus)
 260 /* Use the FILE streams from stdio.h */
 261
 262 typedef FILE *FileHandle;
 263
 264 #define MyOpenFile(f, name)       (f = fopen(name, "rb"))
 265 #define MyReadFile(f, buf, bytes) (fread(buf, 1, bytes, f) == (bytes))
 266 #define MyCloseFile(f)            fclose(f)
 267
 268 #else
 269
 270 /* Use the C++ iostreams */
 271 typedef std::ifstream FileHandle;
 272
 273 static inline void MyOpenFile(FileHandle & f, const char *Name)
 274 {
 275     f.open(Name, std::ifstream::in | std::ifstream::binary);
 276 }
 277 static inline bool MyReadFile(FileHandle & f, void *Buf, unsigned int Num)
 278 {
 279     return (bool)f.read((char *)Buf, Num);
 280 }
 281 static inline void MyCloseFile(FileHandle & f)
 282 {
 283     f.close();
 284 }
 285
 286 #endif
 287
 288 /* Include file contains the CRC of the dictionary data file. Used to detect corruption */
 289 /* of the file. */
 290 #include "dict-crc.h"
 291
 292 #define MAX_DICT_FILE_SIZE  (100+WORD_FILE_SIZE)
 293 #define CHK_INIT 0xffffffffffffffffULL
 294
 295 /* Static table used for the crc implementation. */
 296 static const uint64_t CrcTable[16] =
 297 {
 298     0x0000000000000000ULL, 0x7d08ff3b88be6f81ULL, 0xfa11fe77117cdf02ULL, 0x8719014c99c2b083ULL,
 299     0xdf7adabd7a6e2d6fULL, 0xa2722586f2d042eeULL, 0x256b24ca6b12f26dULL, 0x5863dbf1e3ac9decULL,
 300     0x95ac9329ac4bc9b5ULL, 0xe8a46c1224f5a634ULL, 0x6fbd6d5ebd3716b7ULL, 0x12b5926535897936ULL,
 301     0x4ad64994d625e4daULL, 0x37deb6af5e9b8b5bULL, 0xb0c7b7e3c7593bd8ULL, 0xcdcf48d84fe75459ULL
 302 };
 303
 304 static const unsigned int MAGIC = 'z' + ('x'<< 8) + ('c' << 16) + ('v' << 24);
 305
 306 static unsigned int NumNodes, NumChildLocs, NumRanks, NumWordEnd, NumChildMaps;
 307 static unsigned int SizeChildMapEntry, NumLargeCounts, NumSmallCounts, SizeCharSet;
 308
 309 static unsigned int   *DictNodes;
 310 static uint8_t        *WordEndBits;
 311 static unsigned int   *ChildLocs;
 312 static unsigned short *Ranks;
 313 static uint8_t        *ChildMap;
 314 static uint8_t        *EndCountLge;
 315 static uint8_t        *EndCountSml;
 316 static char           *CharSet;
 317
 318 /**********************************************************************************
 319  * Calculate the CRC-64 of passed data.
 320  * Parameters:
 321  *  Crc     The initial or previous CRC value
 322  *  v       Pointer to the data to add to CRC calculation
 323  *  Len     Length of the passed data
 324  * Returns the updated CRC value.
 325  */
 326 static uint64_t CalcCrc64(uint64_t Crc, const void *v, unsigned int Len)
 327 {
 328     const uint8_t *Data = (const unsigned char *)v;
 329     while(Len--)
 330     {
 331         Crc = CrcTable[(Crc ^ (*Data >> 0)) & 0x0f] ^ (Crc >> 4);
 332         Crc = CrcTable[(Crc ^ (*Data >> 4)) & 0x0f] ^ (Crc >> 4);
 333         ++Data;
 334     }
 335     return Crc;
 336 }
 337
 338 /**********************************************************************************
 339  * Read the dictionary data from file.
 340  * Parameters:
 341  *  Filename    Name of the file to read.
 342  * Returns 1 on success, 0 on error
 343  */
 344 int ZxcvbnInit(const char *Filename)
 345 {
 346     FileHandle f;
 347     uint64_t Crc = CHK_INIT;
 348     if (DictNodes)
 349         return 1;
 350     MyOpenFile(f, Filename);
 351     if (f)
 352     {
 353         unsigned int i, DictSize;
 354
 355         /* Get magic number */
 356         if (!MyReadFile(f, &i, sizeof i))
 357             i = 0;
 358
 359         /* Get header data */
 360         if (!MyReadFile(f, &NumNodes, sizeof NumNodes))
 361             i = 0;
 362         if (!MyReadFile(f, &NumChildLocs, sizeof NumChildLocs))
 363             i = 0;
 364         if (!MyReadFile(f, &NumRanks, sizeof NumRanks))
 365             i = 0;
 366         if (!MyReadFile(f, &NumWordEnd, sizeof NumWordEnd))
 367             i = 0;
 368         if (!MyReadFile(f, &NumChildMaps, sizeof NumChildMaps))
 369             i = 0;
 370         if (!MyReadFile(f, &SizeChildMapEntry, sizeof SizeChildMapEntry))
 371             i = 0;
 372         if (!MyReadFile(f, &NumLargeCounts, sizeof NumLargeCounts))
 373             i = 0;
 374         if (!MyReadFile(f, &NumSmallCounts, sizeof NumSmallCounts))
 375             i = 0;
 376         if (!MyReadFile(f, &SizeCharSet, sizeof SizeCharSet))
 377             i = 0;
 378
 379         /* Validate the header data */
 380         if (NumNodes >= (1<<17))
 381             i = 1;
 382         if (NumChildLocs >= (1<<BITS_CHILD_MAP_INDEX))
 383             i = 2;
 384         if (NumChildMaps >= (1<<BITS_CHILD_PATT_INDEX))
 385             i = 3;
 386         if ((SizeChildMapEntry*8) < SizeCharSet)
 387             i = 4;
 388         if (NumLargeCounts >= (1<<9))
 389             i = 5;
 390         if (NumSmallCounts != NumNodes)
 391             i = 6;
 392
 393         if (i != MAGIC)
 394         {
 395             MyCloseFile(f);
 396             return 0;
 397         }
 398         Crc = CalcCrc64(Crc, &i,    sizeof i);
 399         Crc = CalcCrc64(Crc, &NumNodes,     sizeof NumNodes);
 400         Crc = CalcCrc64(Crc, &NumChildLocs, sizeof NumChildLocs);
 401         Crc = CalcCrc64(Crc, &NumRanks,     sizeof NumRanks);
 402         Crc = CalcCrc64(Crc, &NumWordEnd,   sizeof NumWordEnd);
 403         Crc = CalcCrc64(Crc, &NumChildMaps, sizeof NumChildMaps);
 404         Crc = CalcCrc64(Crc, &SizeChildMapEntry, sizeof SizeChildMapEntry);
 405         Crc = CalcCrc64(Crc, &NumLargeCounts,   sizeof NumLargeCounts);
 406         Crc = CalcCrc64(Crc, &NumSmallCounts,   sizeof NumSmallCounts);
 407         Crc = CalcCrc64(Crc, &SizeCharSet,      sizeof SizeCharSet);
 408
 409         DictSize = NumNodes*sizeof(*DictNodes) + NumChildLocs*sizeof(*ChildLocs) + NumRanks*sizeof(*Ranks) +
 410                    NumWordEnd + NumChildMaps*SizeChildMapEntry + NumLargeCounts + NumSmallCounts + SizeCharSet;
 411         if (DictSize < MAX_DICT_FILE_SIZE)
 412         {
 413             DictNodes = MallocFn(unsigned int, DictSize / sizeof(unsigned int) + 1);
 414             if (!MyReadFile(f, DictNodes, DictSize))
 415             {
 416                 FreeFn(DictNodes);
 417                 DictNodes = 0;
 418             }
 419         }
 420         MyCloseFile(f);
 421
 422         if (!DictNodes)
 423             return 0;
 424         /* Check crc */
 425         Crc = CalcCrc64(Crc, DictNodes, DictSize);
 426         if (memcmp(&Crc, WordCheck, sizeof Crc))
 427         {
 428             /* File corrupted */
 429             FreeFn(DictNodes);
 430             DictNodes = 0;
 431             return 0;
 432         }
 433         fflush(stdout);
 434         /* Set pointers to the data */
 435         ChildLocs = DictNodes + NumNodes;
 436         Ranks = (unsigned short *)(ChildLocs + NumChildLocs);
 437         WordEndBits = (unsigned char *)(Ranks + NumRanks);
 438         ChildMap = (unsigned char*)(WordEndBits + NumWordEnd);
 439         EndCountLge = ChildMap + NumChildMaps*SizeChildMapEntry;
 440         EndCountSml = EndCountLge + NumLargeCounts;
 441         CharSet = (char *)EndCountSml + NumSmallCounts;
 442         CharSet[SizeCharSet] = 0;
 443         return 1;
 444     }
 445     return 0;
 446 }
 447 /**********************************************************************************
 448  * Free the data allocated by ZxcvbnInit().
 449  */
 450 void ZxcvbnUnInit()
 451 {
 452     if (DictNodes)
 453         FreeFn(DictNodes);
 454     DictNodes = 0;
 455 }
 456
 457 #else
 458
 459 /* Include the source file containing the dictionary data */
 460 #include "dict-src.h"
 461
 462 #endif
 463
 464 /**********************************************************************************
 465  * Leet conversion strings
 466  */
 467 /* String of normal chars that could be given as leet chars in the password */
 468 static const uint8_t L33TChr[] = "abcegilostxz";
 469
 470 /* String of leet,normal,normal char triples. Used to convert supplied leet char to normal. */
 471 static const uint8_t L33TCnv[] = "!i $s %x (c +t 0o 1il2z 3e 4a 5s 6g 7lt8b 9g <c @a [c {c |il";
 472 #define LEET_NORM_MAP_SIZE 3
 473
 474 /* Struct holding additional data on the word match */
 475 typedef struct
 476 {
 477     int Rank;                        /* Rank of word in dictionary */
 478     int  Caps;                       /* Number of capital letters */
 479     int  Lower;                      /* Number of lower case letters */
 480     int NumLeet;                     /* Total number of leeted characters */
 481     uint8_t  Leeted[sizeof L33TChr]; /* Number of leeted chars for each char found in L33TChr */
 482     uint8_t  UnLeet[sizeof L33TChr]; /* Number of normal chars for each char found in L33TChr */
 483 } DictMatchInfo_t;
 484
 485 /* Struct holding working data for the word match */
 486 typedef struct
 487 {
 488     uint32_t StartLoc;
 489     int     Ordinal;
 490     int     PwdLength;
 491     int     Begin;
 492     int     Caps;
 493     int     Lower;
 494     int     NumPossChrs;
 495     uint8_t Leeted[sizeof L33TChr];
 496     uint8_t UnLeet[sizeof L33TChr];
 497     uint8_t LeetCnv[sizeof L33TCnv / LEET_NORM_MAP_SIZE + 1];
 498     uint8_t First;
 499     uint8_t PossChars[CHARSET_SIZE];
 500 } DictWork_t;
 501
 502 /**********************************************************************************
 503  * Given a map entry create a string of all possible characters for following to
 504  * a child node
 505  */
 506 static int ListPossibleChars(uint8_t *List, const uint8_t *Map)
 507 {
 508     unsigned int i, j, k;
 509     int Len = 0;
 510     for(k = i = 0; i < SizeChildMapEntry; ++i, ++Map)
 511     {
 512         if (!*Map)
 513         {
 514             k += 8;
 515             continue;
 516         }
 517         for(j = 0; j < 8; ++j)
 518         {
 519             if (*Map & (1<<j))
 520             {
 521                 *List++ = CharSet[k];
 522                 ++Len;
 523             }
 524             ++k;
 525         }
 526     }
 527     *List=0;
 528     return Len;
 529 }
 530
 531 /**********************************************************************************
 532  * Increment count of each char that could be leeted.
 533  */
 534 static void AddLeetChr(uint8_t c, int IsLeet, uint8_t *Leeted, uint8_t *UnLeet)
 535 {
 536     const uint8_t *p = CharBinSearch(c, L33TChr, sizeof L33TChr - 1, 1);
 537     if (p)
 538     {
 539         int i = p - L33TChr;
 540         if (IsLeet > 0)
 541         {
 542             Leeted[i] += 1;
 543         }
 544         else if (IsLeet < 0)
 545         {
 546             Leeted[i] += 1;
 547             UnLeet[i] -= 1;
 548         }
 549         else
 550         {
 551             UnLeet[i] += 1;
 552         }
 553     }
 554 }
 555
 556 /**********************************************************************************
 557  * Given details of a word match, update it with the entropy (as natural log of
 558  * number of possiblities)
 559  */
 560 static void DictionaryEntropy(ZxcMatch_t *m, DictMatchInfo_t *Extra, const uint8_t *Pwd)
 561 {
 562     double e = 0.0;
 563     /* Add allowance for uppercase letters */
 564     if (Extra->Caps)
 565     {
 566         if (Extra->Caps == m->Length)
 567         {
 568             /* All uppercase, common case so only 1 bit */
 569             e += log(2.0);
 570         }
 571         else if ((Extra->Caps == 1) && (isupper(*Pwd) || isupper(Pwd[m->Length - 1])))
 572         {
 573             /* Only first or last uppercase, also common so only 1 bit */
 574             e += log(2.0);
 575         }
 576         else
 577         {
 578             /* Get number of combinations of lowercase, uppercase letters */
 579             int Up = Extra->Caps;
 580             int Lo = Extra->Lower;
 581             int i = Up;
 582             if (i > Lo)
 583                 i = Lo;
 584             for(Lo += Up; i >= 0; --i)
 585                 e += nCk(Lo, i);
 586             if (e > 0.0)
 587                 e = log(e);
 588         }
 589     }
 590     /* Add allowance for using leet substitution */
 591     if (Extra->NumLeet)
 592     {
 593         int i;
 594         double d = 0.0;
 595         for(i = sizeof Extra->Leeted - 1; i >= 0; --i)
 596         {
 597             int Sb = Extra->Leeted[i];
 598             if (Sb)
 599             {
 600                 int Un = Extra->UnLeet[i];
 601                 int j = m->Length - Extra->NumLeet;
 602                 if ((j >= 0) && (Un > j))
 603                     Un = j;
 604                 j = Sb;
 605                 if (j > Un)
 606                     j = Un;
 607                 for(Un += Sb; j >= 0; --j)
 608                 {
 609                     double z = nCk(Un, j);
 610                     d += z;
 611                 }
 612             }
 613         }
 614         if (d > 0.0)
 615             d = log(d);
 616         if (d < log(2.0))
 617             d = log(2.0);
 618         e += d;
 619     }
 620     /* Add entropy due to word's rank */
 621     e += log((double)Extra->Rank);
 622     m->Entrpy = e;
 623 }
 624
 625 /**********************************************************************************
 626  * Function that does the word matching
 627  */
 628 static void DoDictMatch(const uint8_t *Passwd, int Start, int MaxLen, DictWork_t *Wrk, ZxcMatch_t **Result, DictMatchInfo_t *Extra, int Lev)
 629 {
 630     int Len;
 631     uint8_t TempLeet[LEET_NORM_MAP_SIZE];
 632     int Ord = Wrk->Ordinal;
 633     int Caps = Wrk->Caps;
 634     int Lower = Wrk->Lower;
 635     unsigned int NodeLoc = Wrk->StartLoc;
 636     uint8_t *PossChars = Wrk->PossChars;
 637     int NumPossChrs = Wrk->NumPossChrs;
 638     const uint8_t *Pwd = Passwd;
 639     uint32_t NodeData = DictNodes[NodeLoc];
 640     Passwd += Start;
 641     for(Len = 0; *Passwd && (Len < MaxLen); ++Len, ++Passwd)
 642     {
 643         uint8_t c;
 644         int w, x, y, z;
 645         const uint8_t *q;
 646         z = 0;
 647         if (!Len && Wrk->First)
 648         {
 649             c = Wrk->First;
 650         }
 651         else
 652         {
 653             /* Get char and set of possible chars at current point in word. */
 654             const uint8_t *Bmap;
 655             c = *Passwd;
 656             Bmap = ChildMap + (NodeData & ((1<<BITS_CHILD_PATT_INDEX)-1)) * SizeChildMapEntry;
 657             NumPossChrs = ListPossibleChars(PossChars, Bmap);
 658
 659             /* Make it lowercase and update lowercase, uppercase counts */
 660             if (isupper(c))
 661             {
 662                 c = tolower(c);
 663                 ++Caps;
 664             }
 665             else if (islower(c))
 666             {
 667                 ++Lower;
 668             }
 669             /* See if current char is a leet and can be converted  */
 670             q = CharBinSearch(c, L33TCnv, sizeof L33TCnv / LEET_NORM_MAP_SIZE, LEET_NORM_MAP_SIZE);
 671             if (q)
 672             {
 673                 /* Found, see if used before */
 674                 unsigned int j;
 675                 unsigned int i = (q - L33TCnv ) / LEET_NORM_MAP_SIZE;
 676                 if (Wrk->LeetCnv[i])
 677                 {
 678                     /* Used before, so limit characters to try */
 679                     TempLeet[0] = c;
 680                     TempLeet[1] = Wrk->LeetCnv[i];
 681                     TempLeet[2] = 0;
 682                     q = TempLeet;
 683                 }
 684                 for(j = 0; (*q > ' ') && (j < LEET_NORM_MAP_SIZE); ++j, ++q)
 685                 {
 686                     const uint8_t *r = CharBinSearch(*q, PossChars, NumPossChrs, 1);
 687                     if (r)
 688                     {
 689                         /* valid conversion from leet */
 690                         DictWork_t w;
 691                         w = *Wrk;
 692                         w.StartLoc = NodeLoc;
 693                         w.Ordinal = Ord;
 694                         w.PwdLength += Len;
 695                         w.Caps = Caps;
 696                         w.Lower = Lower;
 697                         w.First = *r;
 698                         w.NumPossChrs = NumPossChrs;
 699                         memcpy(w.PossChars, PossChars, sizeof w.PossChars);
 700                         if (j)
 701                         {
 702                             w.LeetCnv[i] = *r;
 703                             AddLeetChr(*r, -1, w.Leeted, w.UnLeet);
 704                         }
 705                         DoDictMatch(Pwd, Passwd - Pwd, MaxLen - Len, &w, Result, Extra, Lev+1);
 706                     }
 707                 }
 708                 return;
 709             }
 710         }
 711         q = CharBinSearch(c, PossChars, NumPossChrs, 1);
 712         if (q)
 713         {
 714             /* Found the char as a normal char */
 715             if (CharBinSearch(c, L33TChr, sizeof L33TChr - 1, 1))
 716             {
 717                 /* Char matches, but also a normal equivalent to a leet char */
 718                 AddLeetChr(c, 0,  Wrk->Leeted, Wrk->UnLeet);
 719             }
 720         }
 721         if (!q)
 722         {
 723             /* No match for char - return */
 724             return;
 725         }
 726         /* Add all the end counts of the child nodes before the one that matches */
 727         x = (q - Wrk->PossChars);
 728         y = (NodeData >> BITS_CHILD_PATT_INDEX) & ((1 << BITS_CHILD_MAP_INDEX) - 1);
 729         NodeLoc = ChildLocs[x+y];
 730         for(w=0; w<x; ++w)
 731         {
 732             unsigned int Cloc = ChildLocs[w+y];
 733             z = EndCountSml[Cloc];
 734             if (Cloc < NumLargeCounts)
 735                 z += EndCountLge[Cloc]*256;
 736             Ord += z;
 737         }
 738
 739         /* Move to next node */
 740         NodeData = DictNodes[NodeLoc];
 741         if (WordEndBits[NodeLoc >> 3] & (1<<(NodeLoc & 7)))
 742         {
 743             /* Word matches, save result */
 744             unsigned int v;
 745             ZxcMatch_t *p;
 746             v = Ranks[Ord];
 747             if (v & (1<<15))
 748                 v = (v & ((1 << 15) - 1)) * 4 + (1 << 15);
 749             Extra->Caps = Caps;
 750             Extra->Rank = v;
 751             Extra->Lower = Lower;
 752             for(x = 0, y = sizeof Extra->Leeted - 1; y >= 0; --y)
 753                 x += Wrk->Leeted[y];
 754             Extra->NumLeet = x;
 755
 756             memcpy(Extra->UnLeet, Wrk->UnLeet, sizeof Extra->UnLeet);
 757             memcpy(Extra->Leeted, Wrk->Leeted, sizeof Extra->Leeted);
 758
 759             p = AllocMatch();
 760             if (x)
 761                 p->Type = DICT_LEET_MATCH;
 762             else
 763                 p->Type = DICTIONARY_MATCH;
 764             p->Length = Wrk->PwdLength + Len + 1;
 765             p->Begin = Wrk->Begin;
 766             DictionaryEntropy(p, Extra, Pwd);
 767             AddMatchRepeats(Result, p, Pwd, MaxLen);
 768             AddResult(Result, p, MaxLen);
 769             ++Ord;
 770         }
 771     }
 772 }
 773
 774 /**********************************************************************************
 775  * Try to match password part with user supplied dictionary words
 776  * Parameters:
 777  *  Result  Pointer head of linked list used to store results
 778  *  Words   Array of pointers to dictionary words
 779  *  Passwd  The start of the password
 780  *  Start   Where in the password to start attempting to match
 781  *  MaxLen  Maximum number characters to consider
 782  */
 783 static void UserMatch(ZxcMatch_t **Result, const char *Words[], const uint8_t *Passwd, int Start, int MaxLen)
 784 {
 785     int Rank;
 786     if (!Words)
 787         return;
 788     Passwd += Start;
 789     for(Rank = 0; Words[Rank]; ++Rank)
 790     {
 791         DictMatchInfo_t Extra;
 792         uint8_t LeetChr[sizeof L33TCnv / LEET_NORM_MAP_SIZE + 1];
 793         uint8_t TempLeet[3];
 794         int Len = 0;
 795         int Caps = 0;
 796         int Lowers = 0;
 797         int Leets = 0;
 798         const uint8_t *Wrd = (const uint8_t *)(Words[Rank]);
 799         const uint8_t *Pwd = Passwd;
 800         memset(Extra.Leeted, 0, sizeof Extra.Leeted);
 801         memset(Extra.UnLeet, 0, sizeof Extra.UnLeet);
 802         memset(LeetChr, 0, sizeof LeetChr);
 803         while(*Wrd)
 804         {
 805             const uint8_t *q;
 806             uint8_t d = tolower(*Wrd++);
 807             uint8_t c = *Pwd++;
 808             if (isupper(c))
 809             {
 810                 c = tolower(c);
 811                 ++Caps;
 812             }
 813             else if (islower(c))
 814             {
 815                 ++Lowers;
 816             }
 817             /* See if current char is a leet and can be converted  */
 818             q = CharBinSearch(c, L33TCnv, sizeof L33TCnv / LEET_NORM_MAP_SIZE, LEET_NORM_MAP_SIZE);
 819             if (q)
 820             {
 821                 /* Found, see if used before */
 822                 unsigned int j;
 823                 unsigned int i = (q - L33TCnv ) / LEET_NORM_MAP_SIZE;
 824                 if (LeetChr[i])
 825                 {
 826                     /* Used before, so limit characters to try */
 827                     TempLeet[0] = c;
 828                     TempLeet[1] = LeetChr[i];
 829                     TempLeet[2] = 0;
 830                     q = TempLeet;
 831                 }
 832                 c = d+1;
 833                 for(j = 0; (*q > ' ') && (j < LEET_NORM_MAP_SIZE); ++j, ++q)
 834                 {
 835                     if (d == *q)
 836                     {
 837                         c = d;
 838                         if (i)
 839                         {
 840                             LeetChr[i] = c;
 841                             AddLeetChr(c, 1, Extra.Leeted, Extra.UnLeet);
 842                             ++Leets;
 843                         }
 844                         break;
 845                     }
 846                 }
 847                 if (c != d)
 848                 {
 849                     Len = 0;
 850                     break;
 851                 }
 852             }
 853             else if (c == d)
 854             {
 855                 /* Found the char as a normal char */
 856                 if (CharBinSearch(c, L33TChr, sizeof L33TChr - 1, 1))
 857                 {
 858                     /* Char matches, but also a normal equivalent to a leet char */
 859                     AddLeetChr(c, 0,  Extra.Leeted, Extra.UnLeet);
 860                 }
 861             }
 862             else
 863             {
 864                 /* No Match */
 865                 Len = 0;
 866                 break;
 867             }
 868             if (++Len > MaxLen)
 869             {
 870                 Len = 0;
 871                 break;
 872             }
 873         }
 874         if (Len)
 875         {
 876             ZxcMatch_t *p = AllocMatch();
 877             if (!Leets)
 878                 p->Type = USER_MATCH;
 879             else
 880                 p->Type = USER_LEET_MATCH;
 881             p->Length = Len;
 882             p->Begin = Start;
 883             /* Add Entrpy */
 884             Extra.Caps = Caps;
 885             Extra.Lower = Lowers;
 886             Extra.NumLeet = Leets;
 887             Extra.Rank = Rank+1;
 888             DictionaryEntropy(p, &Extra, Passwd);
 889             AddMatchRepeats(Result, p, Passwd, MaxLen);
 890             AddResult(Result, p, MaxLen);
 891         }
 892     }
 893 }
 894
 895 /**********************************************************************************
 896  * Try to match password part with the dictionary words
 897  * Parameters:
 898  *  Result  Pointer head of linked list used to store results
 899  *  Passwd  The start of the password
 900  *  Start   Where in the password to start attempting to match
 901  *  MaxLen  Maximum number characters to consider
 902  */
 903 static void DictionaryMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int MaxLen)
 904 {
 905     DictWork_t Wrk;
 906     DictMatchInfo_t Extra;
 907
 908     memset(&Extra, 0, sizeof Extra);
 909     memset(&Wrk, 0, sizeof Wrk);
 910     Wrk.Ordinal = 1;
 911     Wrk.StartLoc = ROOT_NODE_LOC;
 912     Wrk.Begin = Start;
 913     DoDictMatch(Passwd+Start, 0, MaxLen, &Wrk, Result, &Extra, 0);
 914 }
 915
 916
 917 /*################################################################################*
 918  *################################################################################*
 919  * Begin keyboard spatial sequence matching code
 920  *################################################################################*
 921  *################################################################################*/
 922
 923 /* Struct to hold information on a keyboard layout */
 924 typedef struct Keyboard
 925 {
 926     const uint8_t *Keys;
 927     const uint8_t *Shifts;
 928     int NumKeys;
 929     int NumNear;
 930     int NumShift;
 931     int NumBlank;
 932 } Keyboard_t;
 933
 934 /* Struct to hold information on the match */
 935 typedef struct
 936 {
 937     int Keyb;
 938     int Turns;
 939     int Shifts;
 940 } SpatialMatchInfo_t;
 941
 942 /* Shift mapping, characters in pairs: first is shifted, second un-shifted. Ordered for increasing shifted character code.*/
 943 /* Note: on a UK keyboard  \243 is the £ (Pound stirling),  \244 is the ¤ (Euro),  \254 is the ¬ (Not sign)  */
 944 static const uint8_t UK_Shift[] = "!1\"2$4%5&7(9)0*8:;<,>.?/@'AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz^6_-{[|\\}]~#\2433\2444\254`";
 945 static const uint8_t US_Shift[] = "!1\"'#3$4%5&7(9)0*8:;<,>.?/@2AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz^6_-{[|\\}]~`";
 946
 947
 948 /* Neighbour tables */
 949 static const uint8_t UK_Qwerty[48*7] =
 950 {
 951 /* key, left, up-left, up-right, right, down-right, down-left */
 952     '#', '\'',']',   0,   0,   0,   0,    '\'',';', '[', ']', '#',   0, '/',
 953     ',', 'm', 'k', 'l', '.',   0,   0,    '-', '0',   0,   0, '=', '[', 'p',
 954     '.', ',', 'l', ';', '/',   0,   0,    '/', '.', ';', '\'',  0,   0,   0,
 955     '0', '9',   0,   0, '-', 'p', 'o',    '1', '`',   0,   0, '2', 'q',   0,
 956     '2', '1',   0,   0, '3', 'w', 'q',    '3', '2',   0,   0, '4', 'e', 'w',
 957     '4', '3',   0,   0, '5', 'r', 'e',    '5', '4',   0,   0, '6', 't', 'r',
 958     '6', '5',   0,   0, '7', 'y', 't',    '7', '6',   0,   0, '8', 'u', 'y',
 959     '8', '7',   0,   0, '9', 'i', 'u',    '9', '8',   0,   0, '0', 'o', 'i',
 960     ';', 'l', 'p', '[','\'', '/', '.',    '=', '-',   0,   0,   0, ']', '[',
 961     '[', 'p', '-', '=', ']', '\'',';',    '\\',  0,   0, 'a', 'z',   0,   0,
 962     ']', '[', '=',   0,   0, '#','\'',    '`',   0,   0,   0, '1',   0,   0,
 963     'a',   0, 'q', 'w', 's', 'z','\\',    'b', 'v', 'g', 'h', 'n',   0,   0,
 964     'c', 'x', 'd', 'f', 'v',   0,   0,    'd', 's', 'e', 'r', 'f', 'c', 'x',
 965     'e', 'w', '3', '4', 'r', 'd', 's',    'f', 'd', 'r', 't', 'g', 'v', 'c',
 966     'g', 'f', 't', 'y', 'h', 'b', 'v',    'h', 'g', 'y', 'u', 'j', 'n', 'b',
 967     'i', 'u', '8', '9', 'o', 'k', 'j',    'j', 'h', 'u', 'i', 'k', 'm', 'n',
 968     'k', 'j', 'i', 'o', 'l', ',', 'm',    'l', 'k', 'o', 'p', ';', '.', ',',
 969     'm', 'n', 'j', 'k', ',',   0,   0,    'n', 'b', 'h', 'j', 'm',   0,   0,
 970     'o', 'i', '9', '0', 'p', 'l', 'k',    'p', 'o', '0', '-', '[', ';', 'l',
 971     'q',   0, '1', '2', 'w', 'a',   0,    'r', 'e', '4', '5', 't', 'f', 'd',
 972     's', 'a', 'w', 'e', 'd', 'x', 'z',    't', 'r', '5', '6', 'y', 'g', 'f',
 973     'u', 'y', '7', '8', 'i', 'j', 'h',    'v', 'c', 'f', 'g', 'b',   0,   0,
 974     'w', 'q', '2', '3', 'e', 's', 'a',    'x', 'z', 's', 'd', 'c',   0,   0,
 975     'y', 't', '6', '7', 'u', 'h', 'g',    'z', '\\','a', 's', 'x',   0,   0
 976 };
 977
 978 static const uint8_t US_Qwerty[47*7] =
 979 {
 980 /* key, left, up-left, up-right, right, down-right, down-left */
 981     '\'',';', '[', ']',   0,   0, '/',    ',', 'm', 'k', 'l', '.',   0,   0,
 982     '-', '0',   0,   0, '=', '[', 'p',    '.', ',', 'l', ';', '/',   0,   0,
 983     '/', '.', ';','\'',   0,   0,   0,    '0', '9',   0,   0, '-', 'p', 'o',
 984     '1', '`',   0,   0, '2', 'q',   0,    '2', '1',   0,   0, '3', 'w', 'q',
 985     '3', '2',   0,   0, '4', 'e', 'w',    '4', '3',   0,   0, '5', 'r', 'e',
 986     '5', '4',   0,   0, '6', 't', 'r',    '6', '5',   0,   0, '7', 'y', 't',
 987     '7', '6',   0,   0, '8', 'u', 'y',    '8', '7',   0,   0, '9', 'i', 'u',
 988     '9', '8',   0,   0, '0', 'o', 'i',    ';', 'l', 'p', '[','\'', '/', '.',
 989     '=', '-',   0,   0,   0, ']', '[',    '[', 'p', '-', '=', ']','\'', ';',
 990     '\\',']',   0,   0,   0,   0,   0,    ']', '[', '=',   0,'\\',   0,'\'',
 991     '`',   0,   0,   0, '1',   0,   0,    'a',   0, 'q', 'w', 's', 'z',   0,
 992     'b', 'v', 'g', 'h', 'n',   0,   0,    'c', 'x', 'd', 'f', 'v',   0,   0,
 993     'd', 's', 'e', 'r', 'f', 'c', 'x',    'e', 'w', '3', '4', 'r', 'd', 's',
 994     'f', 'd', 'r', 't', 'g', 'v', 'c',    'g', 'f', 't', 'y', 'h', 'b', 'v',
 995     'h', 'g', 'y', 'u', 'j', 'n', 'b',    'i', 'u', '8', '9', 'o', 'k', 'j',
 996     'j', 'h', 'u', 'i', 'k', 'm', 'n',    'k', 'j', 'i', 'o', 'l', ',', 'm',
 997     'l', 'k', 'o', 'p', ';', '.', ',',    'm', 'n', 'j', 'k', ',',   0,   0,
 998     'n', 'b', 'h', 'j', 'm',   0,   0,    'o', 'i', '9', '0', 'p', 'l', 'k',
 999     'p', 'o', '0', '-', '[', ';', 'l',    'q',   0, '1', '2', 'w', 'a',   0,
1000     'r', 'e', '4', '5', 't', 'f', 'd',    's', 'a', 'w', 'e', 'd', 'x', 'z',
1001     't', 'r', '5', '6', 'y', 'g', 'f',    'u', 'y', '7', '8', 'i', 'j', 'h',
1002     'v', 'c', 'f', 'g', 'b',   0,   0,    'w', 'q', '2', '3', 'e', 's', 'a',
1003     'x', 'z', 's', 'd', 'c',   0,   0,    'y', 't', '6', '7', 'u', 'h', 'g',
1004     'z',   0, 'a', 's', 'x',   0,   0,
1005 };
1006 static const uint8_t Dvorak[47*7] =
1007 {
1008     '\'',  0, '1', '2', ',', 'a',   0,    ',','\'', '2', '3', '.', 'o', 'a',
1009     '-', 's', '/', '=',   0,   0, 'z',    '.', ',', '3', '4', 'p', 'e', 'o',
1010     '/', 'l', '[', ']', '=', '-', 's',    '0', '9',   0,   0, '[', 'l', 'r',
1011     '1', '`',   0,   0, '2','\'',   0,    '2', '1',   0,   0, '3', ',','\'',
1012     '3', '2',   0,   0, '4', '.', ',',    '4', '3',   0,   0, '5', 'p', '.',
1013     '5', '4',   0,   0, '6', 'y', 'p',    '6', '5',   0,   0, '7', 'f', 'y',
1014     '7', '6',   0,   0, '8', 'g', 'f',    '8', '7',   0,   0, '9', 'c', 'g',
1015     '9', '8',   0,   0, '0', 'r', 'c',    ';',   0, 'a', 'o', 'q',   0,   0,
1016     '=', '/', ']',   0,'\\',   0, '-',    '[', '0',   0,   0, ']', '/', 'l',
1017     '\\','=',   0,   0,   0,   0,   0,    ']', '[',   0,   0,   0, '=', '/',
1018     '`',   0,   0,   0, '1',   0,   0,    'a',   0,'\'', ',', 'o', ';',   0,
1019     'b', 'x', 'd', 'h', 'm',   0,   0,    'c', 'g', '8', '9', 'r', 't', 'h',
1020     'd', 'i', 'f', 'g', 'h', 'b', 'x',    'e', 'o', '.', 'p', 'u', 'j', 'q',
1021     'f', 'y', '6', '7', 'g', 'd', 'i',    'g', 'f', '7', '8', 'c', 'h', 'd',
1022     'h', 'd', 'g', 'c', 't', 'm', 'b',    'i', 'u', 'y', 'f', 'd', 'x', 'k',
1023     'j', 'q', 'e', 'u', 'k',   0,   0,    'k', 'j', 'u', 'i', 'x',   0,   0,
1024     'l', 'r', '0', '[', '/', 's', 'n',    'm', 'b', 'h', 't', 'w',   0,   0,
1025     'n', 't', 'r', 'l', 's', 'v', 'w',    'o', 'a', ',', '.', 'e', 'q', ';',
1026     'p', '.', '4', '5', 'y', 'u', 'e',    'q', ';', 'o', 'e', 'j',   0,   0,
1027     'r', 'c', '9', '0', 'l', 'n', 't',    's', 'n', 'l', '/', '-', 'z', 'v',
1028     't', 'h', 'c', 'r', 'n', 'w', 'm',    'u', 'e', 'p', 'y', 'i', 'k', 'j',
1029     'v', 'w', 'n', 's', 'z',   0,   0,    'w', 'm', 't', 'n', 'v',   0,   0,
1030     'x', 'k', 'i', 'd', 'b',   0,   0,    'y', 'p', '5', '6', 'f', 'i', 'u',
1031     'z', 'v', 's', '-',   0,   0,   0
1032 };
1033
1034 static const uint8_t PC_Keypad[15*9] =
1035 {
1036 /*Key, left, up-left, up, up-right, right, down-right, down, down-left */
1037     '*', '/',   0,   0,   0, '-', '+', '9', '8',
1038     '+', '9', '*', '-',   0,   0,   0,   0, '6',
1039     '-', '*',   0,   0,   0,   0,   0, '+', '9',
1040     '.', '0', '2', '3',   0,   0,   0,   0,   0,
1041     '/',   0,   0,   0,   0, '*', '9', '8', '7',
1042     '0',   0, '1', '2', '3', '.',   0,   0,   0,
1043     '1',   0,   0, '4', '5', '2', '0',   0,   0,
1044     '2', '1', '4', '5', '6', '3', '.', '0',   0,
1045     '3', '2', '5', '6',   0,   0,   0, '.', '0',
1046     '4',   0,   0, '7', '8', '5', '2', '1',   0,
1047     '5', '4', '7', '8', '9', '6', '3', '2', '1',
1048     '6', '5', '8', '9', '+',   0,   0, '3', '2',
1049     '7',   0,   0,   0, '/', '8', '5', '4',   0,
1050     '8', '7',   0, '/', '*', '9', '6', '5', '4',
1051     '9', '8', '/', '*', '-', '+',   0, '6', '5'
1052 };
1053
1054 static const uint8_t MacKeypad[16*9] =
1055 {
1056     '*', '/',   0,   0,   0,   0,   0, '-', '9',
1057     '+', '6', '9', '-',   0,   0,   0,   0, '3',
1058     '-', '9', '/', '*',   0,   0,   0, '+', '6',
1059     '.', '0', '2', '3',   0,   0,   0,   0,   0,
1060     '/', '=',   0,   0,   0, '*', '-', '9', '8',
1061     '0',   0, '1', '2', '3', '.',   0,   0,   0,
1062     '1',   0,   0, '4', '5', '2', '0',   0,   0,
1063     '2', '1', '4', '5', '6', '3', '.', '0',   0,
1064     '3', '2', '5', '6', '+',   0,   0, '.', '0',
1065     '4',   0,   0, '7', '8', '5', '2', '1',   0,
1066     '5', '4', '7', '8', '9', '6', '3', '2', '1',
1067     '6', '5', '8', '9', '-', '+',   0, '3', '2',
1068     '7',   0,   0,   0, '=', '8', '5', '4',   0,
1069     '8', '7',   0, '=', '/', '9', '6', '5', '4',
1070     '9', '8', '=', '/', '*', '-', '+', '6', '5',
1071     '=',   0,   0,   0,   0, '/', '9', '8', '7'
1072 };
1073
1074 static const Keyboard_t Keyboards[] =
1075 {
1076     { US_Qwerty, US_Shift, sizeof US_Qwerty / 7, 7, sizeof US_Shift / 2, 66 },
1077     { Dvorak,    US_Shift, sizeof Dvorak / 7,    7, sizeof US_Shift / 2, 66 },
1078     { UK_Qwerty, UK_Shift, sizeof UK_Qwerty / 7, 7, sizeof UK_Shift / 2, 66 },
1079     { MacKeypad, 0, sizeof MacKeypad / 9, 9, 0, 44 },
1080     { PC_Keypad, 0, sizeof PC_Keypad / 9, 9, 0, 44 }
1081 };
1082
1083 /**********************************************************************************
1084  * Match password for the given keyboard layout
1085  */
1086 static int DoSptlMatch(const uint8_t *Passwd, int MaxLen, const Keyboard_t *Keyb, SpatialMatchInfo_t *Extra)
1087 {
1088     int i;
1089     int ShiftCount = 0;
1090     int Turns = 0;
1091     int Dir = -1;
1092     int Len = 0;
1093     uint8_t PrevChar = 0;
1094     for( ; *Passwd && (Len < MaxLen); ++Passwd, ++Len)
1095     {
1096         const uint8_t *Key;
1097         int s = 0;
1098         uint8_t CurChar = *Passwd;
1099         /* Try to unshift the character */
1100         if (Keyb->Shifts)
1101         {
1102             Key = CharBinSearch(CurChar, Keyb->Shifts, Keyb->NumShift, 2);
1103             if (Key)
1104             {
1105                 /* Shifted char */
1106                 CurChar = Key[1];
1107                 s = 1;
1108             }
1109         }
1110         if (PrevChar)
1111         {
1112             /* See if the pattern can be extended */
1113             i = 0;
1114             Key = CharBinSearch(PrevChar, Keyb->Keys, Keyb->NumKeys, Keyb->NumNear);
1115             if (Key)
1116             {
1117                 for(i = Keyb->NumNear - 1; i > 0; --i)
1118                 {
1119                     if (Key[i] == CurChar)
1120                         break;
1121                 }
1122             }
1123             if (i)
1124             {
1125                 Turns += (i != Dir);
1126                 Dir = i;
1127                 ShiftCount += s;
1128             }
1129             else
1130             {
1131                 break;
1132             }
1133         }
1134         PrevChar = CurChar;
1135     }
1136     if (Len >= MIN_SPATIAL_LEN)
1137     {
1138         Extra->Turns = Turns;
1139         Extra->Shifts = ShiftCount;
1140         return Len;
1141     }
1142     return 0;
1143 }
1144
1145 /**********************************************************************************
1146  *  Try to match spatial patterns on the keyboard
1147  * Parameters:
1148  *  Result  Pointer head of linked list used to store results
1149  *  Passwd  The start of the password
1150  *  Start   Where in the password to start attempting to match
1151  *  MaxLen  Maximum number characters to consider
1152  */
1153 static void SpatialMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int MaxLen)
1154 {
1155     unsigned int Indx;
1156     int Len, CurLen;
1157     SpatialMatchInfo_t Extra;
1158     const Keyboard_t *k;
1159     Passwd += Start;
1160
1161     for(CurLen = MaxLen; CurLen >= MIN_SPATIAL_LEN;CurLen = Len - 1)
1162     {
1163         Len = 0;
1164         for(k = Keyboards, Indx = 0; Indx < (sizeof Keyboards / sizeof Keyboards[0]); ++Indx, ++k)
1165         {
1166             memset(&Extra, 0, sizeof Extra);
1167             Len = DoSptlMatch(Passwd, CurLen, k, &Extra);
1168             if (Len > 0)
1169             {
1170                 /* Got a sequence of required length so add to result list */
1171                 int i, j, s;
1172                 double Degree, Entropy;
1173                 ZxcMatch_t *p;
1174                 Degree = (k->NumNear-1) - (double)k->NumBlank / (double)k->NumKeys;
1175                 s = k->NumKeys;
1176                 if (k->Shifts)
1177                     s *= 2;
1178
1179                 /* Estimate the number of possible patterns with length ranging 2 to match length and */
1180                 /* with turns ranging from 0 to match turns */
1181                 Entropy = 0.0;
1182                 for(i = 2; i <= Len; ++i)
1183                 {
1184                     int PossTurns = Extra.Turns;
1185                     if (PossTurns >= i)
1186                         PossTurns = i-1;
1187                     for(j = 1; j <= PossTurns; ++j)
1188                         Entropy += nCk(i-1, j-1) * pow(Degree, j) * s;
1189                 }
1190                 if (Entropy > 0.0)
1191                     Entropy = log(Entropy);
1192                 if (Extra.Shifts)
1193                 {
1194                     /* Add extra entropy for shifted keys. (% instead of 5, A instead of a etc.) */
1195                     /* Math is similar to extra entropy from uppercase letters in dictionary matches. */
1196                     int Shift = Extra.Shifts;
1197                     int Unshift = Len - Shift;
1198
1199                     Degree = 0.0;
1200                     j = Shift;
1201                     if (j > Unshift)
1202                         j = Unshift;
1203                     for(i = 0; i <= j; ++i)
1204                     {
1205                         Degree += nCk(Len, i);
1206                     }
1207                     if (Degree > 0.0)
1208                         Entropy += log(Degree);
1209                 }
1210                 p = AllocMatch();
1211                 p->Type = SPATIAL_MATCH;
1212                 p->Begin = Start;
1213                 p->Entrpy = Entropy;
1214                 p->Length = Len;
1215                 AddMatchRepeats(Result, p, Passwd, MaxLen);
1216                 AddResult(Result, p, MaxLen);
1217             }
1218         }
1219     }
1220 }
1221
1222
1223 /*################################################################################*
1224  *################################################################################*
1225  * Begin date matching code
1226  *################################################################################*
1227  *################################################################################*/
1228
1229 /* The possible date formats ordered by length (d for day, m for month, */
1230 /*  y for year, ? for separator) */
1231 static const char *Formats[] =
1232 {
1233     "yyyy",
1234     "d?m?yy",
1235     "ddmmyy",
1236     "dmyyyy",
1237     "dd?m?yy",
1238     "d?mm?yy",
1239     "ddmyyyy",
1240     "dmmyyyy",
1241     "yyyymmd",
1242     "yyyymdd",
1243     "d?m?yyyy",
1244     "dd?mm?yy",
1245     "ddmmyyyy",
1246     "yyyy?m?d",
1247     "yyyymmdd",
1248     "dd?m?yyyy",
1249     "d?mm?yyyy",
1250     "yyyy?mm?d",
1251     "yyyy?m?dd",
1252     "dd?mm?yyyy",
1253     "yyyy?mm?dd",
1254     0
1255 };
1256 /* Possible separator characters that could be used */
1257 static const char DateSeperators[] = "/\\-_. ";
1258
1259 /**********************************************************************************
1260  * Try to match the password with the formats above.
1261  */
1262 static void DateMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int MaxLen)
1263 {
1264     int CurFmt;
1265     int YrLen = 0;
1266     int PrevLen = 0;
1267     uint8_t Sep = 0;
1268     Passwd += Start;
1269
1270     for(CurFmt = 0; Formats[CurFmt]; ++CurFmt)
1271     {
1272         int Len = 0;
1273         int Year = 0;
1274         int Mon  = 0;
1275         int Day  = 0;
1276         int Fail = 0;
1277         const uint8_t *p = Passwd;
1278         const char *Fmt;
1279         YrLen = 0;
1280         Sep = 0;
1281         /* Scan along the format, trying to match the password */
1282         for(Fmt = Formats[CurFmt]; *Fmt && !Fail; ++Fmt)
1283         {
1284             if (*Fmt == '?')
1285             {
1286                 if (!Sep && strchr(DateSeperators, *p))
1287                         Sep = *p;
1288                 Fail = (*p != Sep);
1289             }
1290             else if (isdigit(*p))
1291             {
1292                 if (*Fmt == 'd')
1293                 {
1294                     Day = 10 * Day + *p - '0';
1295                 }
1296                 else if (*Fmt == 'm')
1297                 {
1298                     Mon = 10 * Mon + *p - '0';
1299                 }
1300                 else
1301                 {
1302                     Year = 10 * Year + *p - '0';
1303                     ++YrLen;
1304                 }
1305             }
1306             else
1307             {
1308                 Fail = 1;
1309             }
1310             ++p;
1311             ++Len;
1312             if (Len >= MaxLen)
1313                 break;
1314         }
1315         if (Len < 4)
1316             Fail = 1;
1317         if (!Fail)
1318         {
1319             /* Character matching is OK, now check to see if valid date */
1320             if (((YrLen > 3) || (Len <= 4)) && ((Year < MIN_YEAR) || (Year > MAX_YEAR)))
1321                 Fail = 1;
1322             else if (Len > 4)
1323             {
1324                 if ((Mon > 12) && (Day < 13))
1325                 {
1326                     /* Swap day,month to try to make both in range */
1327                     int i = Mon;
1328                     Mon = Day;
1329                     Day = i;
1330                 }
1331                 /* Check for valid day, month. Currently assumes all months have 31 days. */
1332                 if ((Mon < 1) || (Mon > 12))
1333                     Fail = 1;
1334                 else if ((Day < 1) || (Day > 31))
1335                     Fail = 1;
1336             }
1337         }
1338         if (!Fail && (Len > PrevLen))
1339         {
1340             /* String matched the date, store result */
1341             double e;
1342             ZxcMatch_t *p = AllocMatch();
1343
1344             if (Len <= 4)
1345                 e = log(MAX_YEAR - MIN_YEAR + 1.0);
1346             else if (YrLen > 3)
1347                 e = log(31 * 12 * (MAX_YEAR - MIN_YEAR + 1.0));
1348             else
1349                 e = log(31 * 12 * 100.0);
1350             if (Sep)
1351                 e += log(4.0);  /* Extra 2 bits for separator */
1352             p->Entrpy = e;
1353             p->Type = DATE_MATCH;
1354             p->Length = Len;
1355             p->Begin = Start;
1356             AddMatchRepeats(Result, p, Passwd, MaxLen);
1357             AddResult(Result, p, MaxLen);
1358             PrevLen = Len;
1359         }
1360     }
1361 }
1362
1363
1364 /*################################################################################*
1365  *################################################################################*
1366  * Begin repeated character matching code
1367  *################################################################################*
1368  *################################################################################*/
1369
1370 /**********************************************************************************
1371  * Try to match password part as a set of repeated characters.
1372  * Parameters:
1373  *  Result  Pointer head of linked list used to store results
1374  *  Passwd  The start of the password
1375  *  Start   Where in the password to start attempting to match
1376  *  MaxLen  Maximum number characters to consider
1377  */
1378 static void RepeatMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int MaxLen)
1379 {
1380     int Len, i;
1381     uint8_t c;
1382     Passwd += Start;
1383     /* Remember first char and the count its occurances */
1384     c = *Passwd;
1385     for(Len = 1; (Len < MaxLen) && (c == Passwd[Len]); ++Len)
1386     { }
1387     if (Len >= MIN_REPEAT_LEN)
1388     {
1389         /* Enough repeated char, so create results from number found down to min acceptable repeats */
1390         double Card = Cardinality(&c, 1);
1391         for(i = Len; i >= MIN_REPEAT_LEN; --i)
1392         {
1393             ZxcMatch_t *p = AllocMatch();
1394             p->Type = REPEATS_MATCH;
1395             p->Begin = Start;
1396             p->Length = i;
1397             p->Entrpy = log(Card * i);
1398             AddResult(Result, p, MaxLen);
1399         }
1400     }
1401
1402     /* Try to match a repeated sequence e.g. qxno6qxno6 */
1403     for(Len = MaxLen/2; Len >= MIN_REPEAT_LEN; --Len)
1404     {
1405         const uint8_t *Rpt = Passwd + Len;
1406         int RepeatCount = 2;
1407         while(MaxLen >= (Len * RepeatCount))
1408         {
1409             if (strncmp((const char *)Passwd, (const char *)Rpt, Len) == 0)
1410             {
1411                 /* Found a repeat */
1412                 int c = Cardinality(Passwd, Len);
1413                 ZxcMatch_t *p = AllocMatch();
1414                 p->Entrpy = log((double)c) * Len + log(RepeatCount);
1415                 p->Type = (ZxcTypeMatch_t)(BRUTE_MATCH + MULTIPLE_MATCH);
1416                 p->Length = Len * RepeatCount;
1417                 p->Begin = Start;
1418                 AddResult(Result, p, MaxLen);
1419             }
1420             else
1421                 break;
1422             ++RepeatCount;
1423             Rpt += Len;
1424         }
1425     }
1426 }
1427
1428 /**********************************************************************************
1429  **********************************************************************************
1430  * Begin character sequence matching code
1431  **********************************************************************************
1432  *********************************************************************************/
1433
1434 #define MAX_SEQUENCE_STEP 5
1435 /**********************************************************************************
1436  * Try to match password part as a set of incrementing or decrementing characters.
1437  * Parameters:
1438  *  Result  Pointer head of linked list used to store results
1439  *  Passwd  The start of the password
1440  *  Start   Where in the password to start attempting to match
1441  *  MaxLen  Maximum number characters to consider
1442  */
1443 static void SequenceMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int MaxLen)
1444 {
1445     int Len=0;
1446     int SetLow, SetHigh, Dir;
1447     uint8_t First, Next, IsDigits;
1448     const uint8_t *Pwd;
1449     Passwd += Start;
1450     Pwd = Passwd;
1451     First = Passwd[0];
1452     Dir = Passwd[1] - First;
1453     Len = 0;
1454     IsDigits = 0;
1455     /* Decide on min and max character code for sequence */
1456     if (islower(*Passwd))
1457     {
1458         SetLow = 'a';
1459         SetHigh = 'z';
1460     }
1461     else if (isupper(*Passwd))
1462     {
1463         SetLow = 'A';
1464         SetHigh = 'Z';
1465     }
1466     else if (isdigit(*Passwd))
1467     {
1468         SetLow = '0';
1469         SetHigh = '9';
1470         if ((First == '0') && isdigit(Passwd[1]) && (Dir > MAX_SEQUENCE_STEP))
1471         {
1472             /* Special case for decrementing sequence of digits, treat '0 as a 'ten' character */
1473             Dir = Passwd[1] - ('9' + 1);
1474         }
1475         IsDigits = 1;
1476     }
1477     else
1478         return;
1479
1480     /* Only consider it a sequence if the character increment is not too large */
1481     if (Dir && (Dir <= MAX_SEQUENCE_STEP) && (Dir >= -MAX_SEQUENCE_STEP))
1482     {
1483         ++Len;
1484         while(1)
1485         {
1486             Next = Passwd[0] + Dir;
1487             if (IsDigits && (Dir > 0) && (Next == ('9' + 1)) && (Passwd[1] == '0'))
1488             {
1489                 /* Incrementing digits, consider '0' to be same as a 'ten' character */
1490                 ++Len;
1491                 ++Passwd;
1492                 break;
1493             }
1494             if (IsDigits && (Dir < 0) && (Passwd[0] == '0') && (Passwd[1] == ('9'+1 + Dir)))
1495             {
1496                 ++Len;
1497                 ++Passwd;
1498                 break;
1499             }
1500             if ((Next > SetHigh) || (Next < SetLow) || (Passwd[1] != Next))
1501                 break;
1502             ++Len;
1503             ++Passwd;
1504             if (Len >= MaxLen)
1505                 break;
1506         }
1507     }
1508     if (Len >= MIN_SEQUENCE_LEN)
1509     {
1510         /* Enough repeated char, so create results from number found down to min acceptable length */
1511         int i;
1512         double e;
1513         if ((First == 'a') || (First == 'A') || (First == 'z') || (First == 'Z') ||
1514             (First == '0') || (First == '1') || (First == '9'))
1515             e = log(2.0);
1516         else if (IsDigits)
1517             e = log(10.0);
1518         else if (isupper(First))
1519             e = log(26*2.0);
1520         else
1521             e = log(26.0);
1522         if (Dir < 0)
1523             e += log(2.0);
1524
1525         for(i = Len; i >= MIN_SEQUENCE_LEN; --i)
1526         {
1527             ZxcMatch_t *p = AllocMatch();
1528             /* Add new result to head of list as it has lower entropy */
1529             p->Type = SEQUENCE_MATCH;
1530             p->Begin = Start;
1531             p->Length = i;
1532             p->Entrpy = e + log((double)i);
1533             AddMatchRepeats(Result, p, Pwd, MaxLen);
1534             AddResult(Result, p, MaxLen);
1535         }
1536     }
1537 }
1538
1539 /**********************************************************************************
1540  **********************************************************************************
1541  * Begin top level zxcvbn code
1542  **********************************************************************************
1543  *********************************************************************************/
1544
1545 /**********************************************************************************
1546  * Matching a password is treated as a problem of finding the minimum distance
1547  * between two vertexes in a graph. This is solved using Dijkstra's algorithm.
1548  *
1549  * There  are a series of nodes (or vertexes in graph terminology) which correspond
1550  * to points between each character of the password. Also there is a start node
1551  * before the first character and an end node after the last character.
1552  *
1553  * The paths between the nodes (or edges in graph terminology) correspond to the
1554  * matched parts of the password (e.g. dictionary word, repeated characters etc).
1555  * The distance of the path is equal to the entropy of the matched part. A default
1556  * single character bruteforce match path is also added for all nodes except the
1557  * end node.
1558  *
1559  * Dijkstra's algorithm finds the combination of these part matches (or paths)
1560  * which gives the lowest entropy (or smallest distance) from begining to end
1561  * of the password.
1562  */
1563
1564 /* Struct to hold the data of a node (imaginary point between password characters) */
1565 typedef struct
1566 {
1567     ZxcMatch_t *Paths;  /* Partial matches that lead to a following node */
1568     double      Dist;   /* Distance (or entropy) from start of password to this node */
1569     ZxcMatch_t *From;   /* Which path was used to get to this node with lowest distance/entropy */
1570     int         Visit;  /* Non zero when node has been visited during Dijkstra evaluation */
1571 } Node_t;
1572
1573 /**********************************************************************************
1574  * Main function of the zxcvbn password entropy estimation
1575  */
1576 double ZxcvbnMatch(const char *Pwd, const char *UserDict[], ZxcMatch_t **Info)
1577 {
1578     int i, j;
1579     ZxcMatch_t *Zp;
1580     Node_t *Np;
1581     double e;
1582     int FullLen = strlen(Pwd);
1583     int Len = FullLen;
1584     const uint8_t *Passwd = (const uint8_t *)Pwd;
1585     uint8_t *RevPwd;
1586     /* Create the paths */
1587     Node_t *Nodes = MallocFn(Node_t, Len+2);
1588     memset(Nodes, 0, (Len+2) * sizeof *Nodes);
1589     i = Cardinality(Passwd, Len);
1590     e = log((double)i);
1591
1592     /* Limit length used to full entropy estimation to prevent excessive calculation time */
1593     if (Len > ZXCVBN_DETAIL_LEN)
1594         Len = ZXCVBN_DETAIL_LEN;
1595
1596     /* Do matching for all parts of the password */
1597     for(i = 0; i < Len; ++i)
1598     {
1599         int MaxLen = Len - i;
1600         /* Add all the 'paths' between groups of chars in the password, for current starting char */
1601         UserMatch(&(Nodes[i].Paths), UserDict, Passwd, i, MaxLen);
1602         DictionaryMatch(&(Nodes[i].Paths), Passwd, i, MaxLen);
1603         DateMatch(&(Nodes[i].Paths), Passwd, i, MaxLen);
1604         SpatialMatch(&(Nodes[i].Paths), Passwd, i, MaxLen);
1605         SequenceMatch(&(Nodes[i].Paths), Passwd, i, MaxLen);
1606         RepeatMatch(&(Nodes[i].Paths), Passwd, i, MaxLen);
1607
1608         /* Initially set distance to nearly infinite */
1609         Nodes[i].Dist = DBL_MAX;
1610     }
1611
1612     /* Reverse dictionary words check */
1613     RevPwd = MallocFn(uint8_t, Len+1);
1614     for(i = Len-1, j = 0; i >= 0; --i, ++j)
1615         RevPwd[j] = Pwd[i];
1616     RevPwd[j] = 0;
1617     for(i = 0; i < Len; ++i)
1618     {
1619         ZxcMatch_t *Path = 0;
1620         int MaxLen = Len - i;
1621         DictionaryMatch(&Path, RevPwd, i, MaxLen);
1622         UserMatch(&Path, UserDict, RevPwd, i, MaxLen);
1623
1624         /* Now transfer any reverse matches to the normal results */
1625         while(Path)
1626         {
1627             ZxcMatch_t *Nxt = Path->Next;
1628             Path->Next = 0;
1629             Path->Begin = Len - (Path->Begin + Path->Length);
1630             AddResult(&(Nodes[Path->Begin].Paths), Path, MaxLen);
1631             Path = Nxt;
1632         }
1633     }
1634
1635     /* Add a set of brute force matches. Start by getting all the start points and all */
1636     /* points at character position after end of the matches.  */
1637     memset(RevPwd, 0, Len+1);
1638     for(i = 0; i < Len; ++i)
1639     {
1640         ZxcMatch_t *Path = Nodes[i].Paths;
1641         while(Path)
1642         {
1643             RevPwd[Path->Begin] |= 1;
1644             RevPwd[Path->Begin + Path->Length] |= 2;
1645             Path = Path->Next;
1646         }
1647     }
1648     RevPwd[0] = 1;
1649     RevPwd[Len] = 2;
1650
1651     /* Add the brute force matches */
1652     for(i = 0; i < Len; ++i)
1653     {
1654         int MaxLen = Len - i;
1655         int j;
1656         if (!RevPwd[i])
1657             continue;
1658         for(j = i+1; j <= Len; ++j)
1659         {
1660             if (RevPwd[j])
1661             {
1662                 Zp = AllocMatch();
1663                 Zp->Type = BRUTE_MATCH;
1664                 Zp->Begin = i;
1665                 Zp->Length = j - i;
1666                 Zp->Entrpy = e * (j - i);
1667                 AddResult(&(Nodes[i].Paths), Zp, MaxLen);
1668             }
1669         }
1670     }
1671     FreeFn(RevPwd);
1672     if (FullLen > Len)
1673     {
1674         /* Only the first MAX_DETAIL_LEN characters are used for full  entropy estimation, for */
1675         /* very long passwords the remainding characters are treated as being a incrementing */
1676         /* sequence. This will give a low (and safe) entropy value for them. */
1677         Nodes[Len].Dist = DBL_MAX;
1678         Zp = AllocMatch();
1679         Zp->Type = LONG_PWD_MATCH;
1680         Zp->Begin = Len;
1681         /* Length is negative as only one extra node to represent many extra characters */
1682         Zp->Length = Len - FullLen;
1683         Zp->Entrpy = log(2 * (FullLen - Len));
1684         AddResult(&(Nodes[i].Paths), Zp, FullLen - Len);
1685         ++Len;
1686     }
1687     /* End node has infinite distance/entropy, start node has 0 distance */
1688     Nodes[Len].Dist = DBL_MAX;
1689     Nodes[0].Dist = 0.0;
1690
1691     /* Reduce the paths using Dijkstra's algorithm */
1692     for(i = 0; i < Len; ++i)
1693     {
1694         int j;
1695         double MinDist = DBL_MAX;
1696         int MinIdx = 0;
1697         /* Find the unvisited node with minimum distance or entropy */
1698         for(Np = Nodes, j = 0; j < Len; ++j, ++Np)
1699         {
1700             if (!Np->Visit && (Np->Dist < MinDist))
1701             {
1702                 MinIdx = j;
1703                 MinDist = Np->Dist;
1704             }
1705         }
1706         /* Mark the minimum distance node as visited */
1707         Np = Nodes + MinIdx;
1708         Np->Visit = 1;
1709         e = Np->Dist;
1710         /* Update all unvisited neighbouring nodes with their new distance. A node is a */
1711         /* neighbour if there is a path/match from current node Np to it. The neighbour */
1712         /* distance is the current node distance plus the path distance/entropy. Only */
1713         /* update if the new distance is smaller. */
1714         for(Zp = Np->Paths; Zp; Zp = Zp->Next)
1715         {
1716             Node_t *Ep;
1717             double d = e + Zp->MltEnpy;
1718             if (Zp->Length >= 0)
1719                 Ep = Np + Zp->Length;
1720             else
1721                 Ep = Np + 1;
1722             if (!Ep->Visit &&  (d < Ep->Dist))
1723             {
1724                 /* Update as lower dist, also remember the 'from' node */
1725                 Ep->Dist = d;
1726                 Ep->From = Zp;
1727             }
1728         }
1729     }
1730     /* Make e hold entropy result and adjust to log base 2 */
1731     e = Nodes[Len].Dist / log(2.0);
1732
1733     if (Info)
1734     {
1735         /* Construct info on password parts */
1736         *Info = 0;
1737         for(Zp = Nodes[Len].From; Zp; )
1738         {
1739             ZxcMatch_t *Xp;
1740             i = Zp->Begin;
1741
1742             /* Remove all but required path */
1743             Xp = Nodes[i].Paths;
1744             Nodes[i].Paths = 0;
1745             while(Xp)
1746             {
1747                 ZxcMatch_t *p = Xp->Next;
1748                 if (Xp == Zp)
1749                 {
1750                     /* Adjust the entropy to log to base 2 */
1751                     Xp->Entrpy /= log(2.0);
1752                     Xp->MltEnpy /= log(2.0);
1753                     if (Xp->Length < 0)
1754                         Xp->Length = -Xp->Length;
1755
1756                     /* Put previous part at head of info list */
1757                     Xp->Next = *Info;
1758                     *Info = Xp;
1759                 }
1760                 else
1761                 {
1762                     /* Not going on info list, so free it */
1763                     FreeFn(Xp);
1764                 }
1765                 Xp = p;
1766             }
1767             Zp = Nodes[i].From;
1768         }
1769     }
1770     /* Free all paths. Any being returned to caller have already been freed */
1771     for(i = 0; i <= Len; ++i)
1772     {
1773         Zp = Nodes[i].Paths;
1774         while(Zp)
1775         {
1776             ZxcMatch_t *p = Zp->Next;
1777             FreeFn(Zp);
1778             Zp = p;
1779         }
1780     }
1781     FreeFn(Nodes);
1782     return e;
1783 }
1784
1785 /**********************************************************************************
1786  * Free the path info returned by ZxcvbnMatch().
1787  */
1788 void ZxcvbnFreeInfo(ZxcMatch_t *Info)
1789 {
1790     ZxcMatch_t *p;
1791     while(Info)
1792     {
1793         p = Info->Next;
1794         FreeFn(Info);
1795         Info = p;
1796     }
1797 }