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