home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / msdos / txtutl / gestalt.arc / SIMIL_A.ASM < prev    next >
Encoding:
Assembly Source File  |  1988-12-06  |  13.1 KB  |  339 lines
  1. ;From the article "Pattern Matching - The Gestalt Approach"
  2. ;by John W. Ratcliff and David E. Metzener
  3. ;Dr. Dobbs Journal, July 1988
  4.  
  5. ; This version is for use in assembly language programs.
  6. ; See TESTSIM.ASM for a demonstration.
  7. ;
  8. ; -    All required local variables are right here in this procedure.
  9. ; -    Enter with DS:SI = pointer to string 1,
  10. ;           DS:DI = pointer to string 2
  11. ;    Preserves all registers except AX (which returns the similarity)
  12. ; It is CRITICAL that SS=CSeg!  Else the bp referencing will not work!
  13. ; I have no intentions of hacking it for other configurations ..
  14. ; that's left as an exercise for the student.
  15. ; (Hint:  Look in the Turbo Pascal version for an example.)
  16. ;
  17. ; David Kirschbaum
  18. ; Toad Hall
  19. ; kirsch@braggvax.ARPA
  20.  
  21.  
  22. ;TITLE    SIMIL.ASM written by John W. Ratcliff and David E. Metzener
  23.  
  24. ; November 10, 1987
  25. ; Uses the Ratcliff/Obershelp pattern recognition algorithm.
  26. ; The function SIMIL returns a percentage value corresponding to how
  27. ; alike any two strings are.  Be certain to upper case the two strings
  28. ; passed if you are not concerned about case sensitivity.
  29.  
  30. _Simil_a    proc    near
  31.  
  32. ;TH Data moved down here so it'll be completely contained in our procedure.
  33.  
  34. ststr1L    dw    25 dup(?)        ;contains lefts for string 1
  35. ststr1R    dw    25 dup(?)        ;contains rights for string 1
  36. ststr2L    dw    25 dup(?)        ;contains lefts for string 2
  37. ststr2R    dw    25 dup(?)        ;contains rights for string 2
  38. stcknum    dw    ?            ;number of elements on the stack
  39. score    dw    ?            ;the # of chars in common times 2
  40. total    dw    ?            ;total # of chars in string 1 and 2
  41. cL1    dw    ?            ;left of string 1 found in common
  42. cR1    dw    ?            ;right of string 1 found in common
  43. cL2    dw    ?            ;left of string 2 found in common
  44. cR2    dw    ?            ;right of string 2 found in common
  45. s2ed    dw    ?            ;the end of string 2 used in compare
  46.  
  47. _simil:
  48. ; This routine expects pointers passed in two character strings, null
  49. ; terminated, that you wish compared.  It returns a percentage value
  50. ; from 0 to 100% corresponding to how alike the two strings are.
  51. ; Usage:    DS:SI = pointer to string 1                TH
  52. ;        DS:DI = pointer to string 2                TH
  53. ; The similarity routine is composed of three major components
  54. ; pushst    --- pushes a string section to be compared on the stack
  55. ; popst        --- pops a string section to be examined off of the stack
  56. ; compare    --- finds the largest group of characters in common between
  57. ;            any two string sections
  58. ; The similarity routine begins by computing the total length of both
  59. ; strings passed and placing that value in TOTAL.  It then takes
  60. ; the beginning and ending of both strings passed and pushes them on
  61. ; the stack.  It then falls into the main line code.
  62. ; The original two strings are immediately popped off of the stack and
  63. ; are passed to the compare routine.  The compare routine will find the
  64. ; largest group of characters in common between the two strings.
  65. ; The number of characters in common is multiplied times two and added
  66. ; to the total score.  If there were no characters in common, then there
  67. ; is nothing to push onto the stack.  If there are exactly one character
  68. ; to the left in both strings, then we needn't push it on the stack.
  69. ; (We already know they aren't equal from the previous call to compare.)
  70. ; Otherwise the characters to the left are pushed onto the stack.  These
  71. ; same rules apply to characters to the right of the substring found in
  72. ; common.  This process of pulling substrings off of the stack, comparing
  73. ; them, and pushing remaining sections on the stack is continued until
  74. ; the stack is empty.  On return the total score is divided by the
  75. ; number of characters in both strings.  This is multiplied times 100 to
  76. ; yield a percentage.  This percentage similarity is returned to the
  77. ; calling procedure.
  78.  
  79.     push    bp        ;save BP reg.
  80.     mov    bp,sp        ;save SP reg in BP for use in program
  81.     push    bx        ;save all regs we're gonna trash    TH
  82.     push    cx
  83.     push    dx
  84.     push    si
  85.     push    di
  86.     push    ES        ;save the ES seg register
  87.  
  88.     mov    ax,DS        ;copy DS segment reg to ES
  89.     mov    ES,ax
  90.  
  91.     xor    ax,ax        ;zero out AX for clearing of SCORE var
  92.     mov    score,ax    ;zero out SCORE
  93.     mov    stcknum,ax    ;initialize number of stack entries to 0
  94. ;TH DS:SI and DS:DI already point to string 1 and string 2 respectively.
  95. ;TH    mov    si,[bp+4]    ;move beginning pointer of string 1 to SI
  96. ;TH    mov    di,[bp+6]    ;move beginning pointer of string 2 to SI
  97.  
  98.     cmp    [si],al        ;is it a null string?
  99.     je    StrErr        ;can't process null strings
  100.      cmp    [di],al        ;is it a null string?
  101.      jne    DoCmp        ;Neither is a null string, so process them
  102. StrErr:    jmp    Donit        ;exit routine
  103.  
  104. DoCmp:    push    di        ;save DI because of SCAS opcode
  105.     push    si        ;save SI because of SCAS opcode
  106.     xor    al,al        ;clear out AL to search for end of string
  107.     cld            ;set direction flag forward
  108.     mov    cx,-1        ;make sure we repeat the correct # of times
  109.  
  110.     repnz    scasb        ;scan for string delimiter in string 2
  111.     dec    di        ;point DI to '$00' byte of string 2
  112.     dec    di        ;point DI to last char of string 2
  113.     mov    bp,di        ;move DI to BP where it is supposed to be
  114.  
  115.     pop    di        ;restore SI into DI for SCAS (string 1)
  116.     repnz    scasb        ;scan for string delimiter in string 1
  117.  
  118.     not    cx        ;do one's complement for correct length of st
  119.     sub    cx,2        ;subtract the two zero bytes at the end of st
  120.     mov    total,cx    ;store string 2's length
  121.  
  122.     dec    di        ;point DI to '$00' byte of string 1
  123.     dec    di        ;point DI to last char of string 1
  124.     mov    bx,di        ;move DI to BX where it is supposed to be
  125.  
  126.     pop    di        ;restore DI to what it should be
  127.     call    PushSt        ;push values for the first call to SIMILIARITY
  128.  
  129. Main:    cmp    stcknum,0    ;is there anything on the stack?
  130.     je    Done        ;no, then all done!
  131.  
  132.     call    PopSt        ;get regs set up for a compare call
  133.     call    Compare        ;do compare for this substring set
  134.     or    dx,dx        ;if nothing in common then nothing to push TH
  135.     jz    Main        ;try another set            TH
  136.  
  137.     shl    dx,1        ;*2 for add to score
  138.     add    score,dx    ;add into score
  139.     mov    bp,stcknum    ;get number of entry I want to look at
  140.     shl    bp,1        ;get AX ready to access string stacks
  141.     mov    si,[ststr1L+bp]    ;move L1 into SI or L1
  142.     mov    bx,cL1        ;move CL1 into BX or R1
  143.     mov    di,[ststr2L+bp]    ;move L2 into DI or L2
  144.     mov    cx,cL2        ;move CL2 into CX temporarily
  145.     mov    ax,[ststr1R+bp]    ;get old R1 off of stack
  146.     mov    cL1,ax        ;place in CL1 temporarily
  147.     mov    ax,[ststr2R+bp]    ;get old R2 off of stack
  148.     mov    cL2,ax        ;save in CL2 temporarily
  149.     mov    bp,cx        ;place CL2 into BP
  150.  
  151.     cmp    bx,si        ;compare CL1 to L1
  152.     je    ChRght        ;if zero, then nothing on left side string 1
  153.  
  154.     cmp    bp,di        ;compare CL2 to L2
  155.     je    ChRght        ;if zero, then nothing on left side string 2
  156.  
  157.     dec    bx        ;point to last part of left side string 1
  158.     dec    bp        ;point to last part of left side string 2
  159.     cmp    bx,si        ;only one char to examine?
  160.     jne    PushIt        ;no->we need to examine this
  161.     cmp    bp,di        ;only one char in both?
  162.     je    ChRght        ;nothing to look at if both only contain 1 char
  163.  
  164. PushIt:    call    PushSt        ;push left side on stack
  165. ChRght:    mov    si,cR1        ;move CR1 into SI or L1
  166.     mov    bx,cL1        ;move R1 into BX or R1
  167.     mov    di,cR2        ;move CR2 into DI or L2
  168.     mov    bp,cL2        ;move R2 into BP or R2
  169.  
  170.     cmp    si,bx        ;compare CR1 to R1
  171.     je    Main        ;If zero, then nothing on right side string 1
  172.     cmp    di,bp        ;compare CR2 to R2
  173.     je    Main        ;if zero, then nothing on right side string 2
  174.  
  175.     inc    si        ;point to last part of right side string 1
  176.     inc    di        ;point to last part of right side string 2
  177.     cmp    bx,si        ;only one char to examine?
  178.     jne    Push2        ;no-> examine it
  179.     cmp    bp,di        ;only 1 char to examine in both?
  180.     je    Main        ;yes-> get next string off of stack
  181.  
  182. Push2:    call    PushSt        ;push right side on stack
  183.     jmp    short Main    ;do next level of compares
  184.  
  185. Done:    mov    ax,score    ;get score into AX for MUL
  186.     or    ax,ax        ;anything?                TH
  187.     jz    Donit        ;nope, forget this mess            TH
  188.     mov    cx,100        ;get 100 into CX for MUL
  189.     mul    cx        ;multiply by 100
  190.     mov    cx,total    ;get total chars for divide
  191.     div    cx        ;divide by total
  192. Donit:
  193.     pop    ES        ;restore ES to entry value
  194.     pop    di        ;and all other regs also        TH
  195.     pop    si
  196.     pop    dx
  197.     pop    cx
  198.     pop    bx
  199.     pop    bp        ;restore BP back to entry value
  200.     ret            ;leave with AX holding % similarity
  201.  
  202.  
  203. Compare:
  204.  
  205. ; The compare routine locates the largest group of characters between string 1
  206. ; and string 2.  This routine assumes that the direction flag is clear.
  207. ; Pass to this routine:
  208. ;    BX    = R1 (right side of string 1)
  209. ;    DS:SI    = L1 (left side of string 1)
  210. ;    ES:Di    = L2 (left side of string 2)
  211. ;    BP    = R2 (right side of string 2)
  212. ;
  213. ; This routine returns:
  214. ;    DX    = # of characters matching
  215. ;    CL1    = Left side of first string that matches
  216. ;    CL2    = Left side of second string that matches
  217. ;    CR1    = Right side of first string that matches
  218. ;    CR2    = Right side of second string that matches
  219. ;
  220. ; The compare routine is composed of two loops, an inner and an outer.
  221. ; The worst case scenario is that there are absolutely no characters in
  222. ; common between string 1 and string 2.  In this case N x M compares are
  223. ; performed.  However, when an equal condition occurs in the inner
  224. ; loop, then the next character to be examined in string 2 (for this loop)
  225. ; is advanced by the number of characters found equal.  Whenever a new
  226. ; maximum number of characters in common is found, then the ending location
  227. ; of both the inner and outer loop is backed off by the difference between
  228. ; the new max chars value and the old max chars value for both loops.  In
  229. ; short, if 5 characters have been found in common part of the way through
  230. ; the search, then we can cut our search short 5 characters before the
  231. ; true end of both strings since there is no chance of finding better than
  232. ; a 5 character match at that point.  This technique means that an exact
  233. ; equal match will require only a single compare and combinations of other
  234. ; matches will proceed as efficiently as possible.
  235.  
  236.     mov    s2ed,bp        ;store end of string 2
  237.     xor    dx,dx        ;init MAXCHARS
  238. ForL3:    push    di        ;save start of string 2
  239. ForL4:    push    di        ;save start of string 2
  240.     push    si        ;save start of string 1
  241.     mov    cx,s2ed        ;set up for calc of length of string 1
  242.     sub    cx,di        ;get length of string 1 -1
  243.     inc    cx        ;make proper length
  244.     push    cx        ;save starting length of string 1
  245.     repz    cmpsb        ;compare strings
  246.     jz    Equal        ;if equal, then skip fixes
  247.      inc    cx        ;inc back because CMPS decs even if not equal
  248. Equal:    pop    ax        ;get starting length of string 1
  249.     sub    ax,cx        ;get length of common characters
  250.     jnz    NewMax        ;more than 0 chars matched
  251.  
  252.     pop    si        ;get back start of string 1
  253.     pop    di        ;get back start of string 2
  254.  
  255. Reent:    inc    di        ;do the next char no matter what
  256. Reent2:    cmp    di,bp        ;are we done with string 2?
  257.     jle    ForL4        ;no, then do next string compare
  258.     pop    di        ;get back start of string 2
  259.     inc    si        ;next char in string 1 to scan
  260.     cmp    si,bx        ;are we done with string 1?
  261.     jle    ForL3        ;no, then do next string compare
  262.     ret            ;MAXCHARS is in DX
  263.  
  264. ; We branch downwards for both newmax and newmx2 because on the
  265. ; 8086 line of processors a branch not taken is much faster than
  266. ; one which is.  Since the not equal condition is to be found
  267. ; most often and we would like the inner loop to execute as quickly
  268. ; as possible, we branch outside of this loop on the less frequent
  269. ; occurrence.  When a match or a new MAXCHARS is found, we branch down
  270. ; to these two routines, process the new conditions, and then branch
  271. ; back up to the main line code.
  272.  
  273. NewMax:
  274. ;TH: we pop SI and DI in any case
  275.     pop    si        ;get back start of string 1        TH
  276.     pop    di        ;get back start of string 2        TH
  277.     cmp    ax,dx        ;greater than MAXCHARS?
  278.     jg    NewMx2        ;yes, update new MAXCHARS and pointers
  279. ;TH    pop    si        ;get back start of string 1
  280. ;TH    pop    di        ;get back start of string 2
  281.     add    di,ax        ;skip past matching chars
  282.     jmp    short Reent2    ;reenter main loop
  283.  
  284. NewMx2:
  285. ;TH    pop    si        ;get back start of string 1
  286. ;TH    pop    di        ;get back start of string 2
  287.     mov    cL1,si        ;put begin of match of string 1
  288.     mov    cL2,di        ;put begin of match of string 2
  289.     mov    cx,ax        ;save new MAXCHARS
  290.  
  291.     sub    ax,dx        ;get delta for adjustment to ends of strings
  292.     sub    bx,ax        ;adjust end of string 1
  293.     sub    bp,ax        ;adjust end of string 2
  294.  
  295.     mov    dx,cx        ;new MAXCHARS
  296.     dec    cx        ;set up for advance to last matching char
  297.     add    di,cx        ;advance to last matching char string 2
  298.     mov    cR2,di        ;put end of match of string 2
  299.     add    cx,si        ;advance to last matching char string 1
  300.     mov    cR1,cx        ;put end of match of string 1
  301.     jmp    short Reent    ;reenter inner loop
  302.  
  303.  
  304. PushSt:
  305. ; On Entry:
  306. ;    BX    = R1 (right side of string 1)
  307. ;    DS:SI    = L1 (left side of string 1)
  308. ;    ES:Di    = L2 (left side of string 2)
  309. ;    BP    = R2 (right side of string 2)
  310.  
  311.     mov    cx,bp        ;save R2
  312.     mov    bp,stcknum
  313.     shl    bp,1        ;*2 for words
  314.     mov    [bp+ststr1L],si    ;put left side of string 1 on stack
  315.     mov    [bp+ststr1R],bx    ;put right side of string 1 on stack
  316.     mov    [bp+ststr2L],di    ;put left side of string 2 on stack
  317.     mov    [bp+ststr2R],cx    ;put right side of string 2 on stack
  318.     inc    stcknum        ;add one to number of stack entries
  319.     mov    bp,cx        ;restore R2
  320.     ret
  321.  
  322.  
  323. PopSt:
  324. ;    BX    = R1 (right side of string 1)
  325. ;    DS:SI    = L1 (left side of string 1)
  326. ;    ES:Di    = L2 (left side of string 2)
  327. ;    BP    = R2 (right side of string 2)
  328.  
  329.     dec    stcknum        ;point to last entry on stack
  330.     mov    bp,stcknum    ;get number of stack entries
  331.     shl    bp,1        ;*2 for words
  332.     mov    si,[bp+ststr1L]    ;restore left side of string 1 from stack
  333.     mov    bx,[bp+ststr1R]    ;restore right side of string 1 from stack
  334.     mov    di,[bp+ststr2L]    ;restore left side of string 2 from stack
  335.     mov    bp,[bp+ststr2R]    ;restore right side of string 2 from stack
  336.     ret
  337.  
  338. _Simil_a    endp
  339.