home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / dbmsg / mapi / manager.sh / smhrk.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-11  |  4.8 KB  |  171 lines
  1. /*
  2.  *  S M H P S . C
  3.  *  
  4.  *  Sample mail handling sub-string search functions
  5.  *  Uses Rabin/Karp algorythms to find sub-strings
  6.  *  Copyright 1992-95 Microsoft Corporation.  All Rights Reserved.
  7.  */
  8.  
  9. #include "_pch.h"
  10. #include "smhnls.h"
  11.  
  12. #define ulPrime ((ULONG) 0x00FF00F1)
  13. #define ulBase  ((ULONG) 0x00000100)
  14.  
  15. BOOL
  16. FRKFindSubpb (LPBYTE pbTarget,
  17.     ULONG cbTarget,
  18.     LPBYTE pbPattern,
  19.     ULONG cbPattern)
  20. {
  21.     UINT    i;
  22.     LPBYTE  pbTargetMax = pbTarget + cbTarget;
  23.     LPBYTE  pbPatternMax = pbPattern + cbPattern;
  24.     ULONG   ulBaseToPowerMod = 1;
  25.     ULONG   ulHashPattern = 0;
  26.     ULONG   ulHashTarget = 0;
  27.  
  28.     if (cbPattern > cbTarget)
  29.         return FALSE;
  30.  
  31.     // Compute the power of the left most character in base ulBase
  32.     for (i = 1; i < cbPattern; i++)
  33.         ulBaseToPowerMod = (ulBase * ulBaseToPowerMod) % ulPrime;
  34.  
  35.     // Calculate the hash function for the src (and the first dst)
  36.     while (pbPattern < pbPatternMax)
  37.     {
  38.         ulHashPattern = (ulHashPattern*ulBase+*pbPattern) % ulPrime;
  39.         ulHashTarget = (ulHashTarget*ulBase+*pbTarget) % ulPrime;
  40.         pbPattern++;
  41.         pbTarget++;
  42.     }
  43.  
  44.     // Dynamically produce hash values for the string as we go
  45.     for ( ;; )
  46.     {
  47.         // Remember to do the memcmp for the off-chance it doesn't work
  48.         // according to probability
  49.         if (    ulHashPattern == ulHashTarget
  50.             && !memcmp(pbPattern-cbPattern, pbTarget-cbPattern,
  51.             (UINT)cbPattern))
  52.             return TRUE;
  53.  
  54.         // Assert because this is very unprobable
  55. #ifdef DEBUG
  56.         if (ulHashPattern == ulHashTarget)
  57.             DebugTrace("This is very unprobable!\n");
  58. #endif
  59.  
  60.         if (pbTarget == pbTargetMax)
  61.             return FALSE;
  62.  
  63.         ulHashTarget = (ulHashTarget+ulBase*ulPrime-
  64.             *(pbTarget-cbPattern)*ulBaseToPowerMod) % ulPrime;
  65.         ulHashTarget = (ulHashTarget*ulBase+*pbTarget) % ulPrime;
  66.         pbTarget++;
  67.     }
  68. }
  69.  
  70. BOOL
  71. FRKFindSubpsz (LPSTR pszTarget,
  72.     ULONG cbTarget,
  73.     LPSTR pszPattern,
  74.     ULONG cbPattern,
  75.     ULONG ulFuzzyLevel)
  76. {
  77.     UINT    i;
  78.     ULONG   ulBaseToPowerMod = 1;
  79.     ULONG   ulHashPattern = 0;
  80.     ULONG   ulHashTarget = 0;
  81.     LCID    lcid = GetUserDefaultLCID();
  82.     LPBYTE  pbTarget;
  83.     LPBYTE  pbPattern;
  84.     LPBYTE  pbTargetMax;
  85.     LPBYTE  pbPatternMax;
  86.     BOOL    fResult = FALSE;
  87.     CHAR    *rgchHash;
  88.  
  89.     // Validate parameters
  90.  
  91.     switch (ulFuzzyLevel & (FL_IGNORECASE | FL_IGNORENONSPACE))
  92.     {
  93.       case 0:       
  94.       default:
  95.         rgchHash = rgchCsds;
  96.         break;
  97.         
  98.       case FL_IGNORECASE:
  99.         rgchHash = rgchCids;
  100.         break;
  101.         
  102.       case FL_IGNORENONSPACE:
  103.         rgchHash = rgchCsdi;
  104.         break;
  105.         
  106.       case FL_IGNORECASE | FL_IGNORENONSPACE:
  107.         rgchHash = rgchCidi;
  108.         break;
  109.     }
  110.  
  111.     if (ulFuzzyLevel & FL_LOOSE)
  112.         rgchHash = rgchCids;
  113.  
  114.     pbTarget = (LPBYTE) pszTarget;
  115.     pbPattern = (LPBYTE) pszPattern;
  116.     pbTargetMax = pbTarget + cbTarget;
  117.     pbPatternMax = pbPattern + cbPattern;
  118.  
  119.     if (cbPattern > cbTarget)
  120.         goto end;
  121.  
  122.     // Compute the power of the left most character in base ulBase
  123.     for (i = 1; i < cbPattern; i++)
  124.         ulBaseToPowerMod = (ulBase * ulBaseToPowerMod) % ulPrime;
  125.  
  126.     // Calculate the hash function for the src (and the first dst)
  127.     while (pbPattern < pbPatternMax)
  128.     {
  129.         ulHashPattern = (ulHashPattern*ulBase+rgchHash[*pbPattern]) % ulPrime;
  130.         ulHashTarget = (ulHashTarget*ulBase+rgchHash[*pbTarget]) % ulPrime;
  131.         pbPattern++;
  132.         pbTarget++;
  133.     }
  134.  
  135.     // Dynamically produce hash values for the string as we go
  136.     for ( ;; )
  137.     {
  138.         if (ulHashPattern == ulHashTarget)
  139.         {
  140.             if (CompareStringA(lcid,
  141.                 ((ulFuzzyLevel & FL_IGNORECASE) ? NORM_IGNORECASE : 0) |
  142.                 ((ulFuzzyLevel & FL_LOOSE) ? NORM_IGNORECASE : 0) |
  143.                 ((ulFuzzyLevel & FL_IGNORENONSPACE) ? NORM_IGNORENONSPACE : 0),
  144.                 pbPattern-cbPattern, (UINT)cbPattern,
  145.                 pbTarget-cbPattern, (UINT)cbPattern) == 2)
  146.             {
  147.                 fResult = TRUE;
  148.                 goto end;
  149.             }
  150.         }
  151.  
  152. #ifdef DEBUG
  153.         if (ulHashPattern == ulHashTarget)
  154.             DebugTrace ("This is very unprobable, unless you are doing "
  155.                 "FL_EXACT and an case insensitive match came up "
  156.                 "(or you are on DBCS)\n");
  157. #endif
  158.  
  159.         if (pbTarget == pbTargetMax)
  160.             goto end;
  161.  
  162.         ulHashTarget = (ulHashTarget+ulBase*ulPrime-
  163.             rgchHash[*(pbTarget-cbPattern)]*ulBaseToPowerMod) % ulPrime;
  164.         ulHashTarget = (ulHashTarget*ulBase+rgchHash[*pbTarget]) % ulPrime;
  165.         pbTarget++;
  166.     }
  167.  
  168. end:
  169.     return fResult;
  170. }
  171.