src/zxcvbn.c

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