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