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_P.ASM < prev    next >
Encoding:
Assembly Source File  |  1988-12-06  |  9.4 KB  |  258 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. ;Rewritten for Turbo Pascal v3.0 inline code and INLINE.COM.
  5. ;Now expects normal Pascal strings (first byte is length byte).
  6. ;Usage:
  7. ;
  8. ;FUNCTION Simil(VAR Str1,Str2) : INTEGER;
  9. ;  VAR  result : INTEGER;
  10. ;  BEGIN
  11. ;    (*$I simil_p.obj*)    (* this code *)
  12. ;    Simil := result;  (*return the function result*)
  13. ;  END;  (* of Simil *)
  14. ;
  15. ;See TESTSIM.PAS for required global variables.
  16. ;
  17. ;Extensive remarks removed.  See other versions.
  18. ; David Kirschbaum
  19. ; Toad Hall
  20. ; kirsch@braggvax.ARPA
  21.  
  22.   push  bp              ;save Turbo's BP
  23.   push  ES              ;and ES
  24.   cld                   ;insure forward
  25.   les   si,>str1[bp]    ;ES:SI = str1 addr
  26.   mov   di,>str2[bp]    ;ES:DI = str2 addr
  27. ;
  28.   xor   ax,ax           ;get a 0
  29.   mov   [>score],ax     ;zero out SCORE
  30.   mov   [>stcknum],ax   ;init nr of stack entries to 0
  31.   ES:
  32.   cmp   [si],al         ;is it a null string?
  33.   je    StrErr          ;can't process null strings
  34.    ES:
  35.    cmp  [di],al         ;is it a null string?
  36.    jne  DoCmp           ;Both strs ok, so process them
  37. StrErr:
  38.   jmp   Exit            ;exit routine
  39. ;
  40. DoCmp:
  41.   xor   ah,ah           ;clear msb
  42.   ES:
  43.   mov   al,[si]         ;get str1 length byte
  44.   mov   cx,ax           ;accum total len in CX
  45.   add   ax,si           ;add in string start
  46.   mov   bx,ax           ;BX points to str1 last char
  47.   inc   si              ;bump SI past str1 length byte
  48. ;
  49.   xor   ah,ah           ;clear msb
  50.   ES:
  51.   mov   al,[di]         ;str2 length byte
  52.   add   cx,ax           ;accum total len in CX
  53.   add   ax,di           ;add in start
  54.   mov   bp,ax           ;BP points to str2 last char
  55.   inc   di              ;bump DI past str2 length byte
  56. ;
  57.   mov   [>total],cx     ;store total string length
  58. ;
  59.   call  PushSt          ;push values for
  60. ;                        ; first call to SIMILIARITY
  61. Main:
  62.   cmp   word [>stcknum],0 ;anything on the stack?
  63.   je    Done            ;no, then all done!
  64. ;
  65.   call  PopSt           ;get regs set up for a compare call
  66.   call  Compare         ;do compare for this substring set
  67.   or    dx,dx           ;if nothing in common
  68.                         ; then nothing to push
  69.   jz    Main            ;try another set
  70. ;
  71.   shl   dx,1              ;*2
  72.   add   [>score],dx       ;add into score
  73.   mov   bp,[>stcknum]     ;get nr of entry
  74.                           ; I want to look at
  75.   shl   bp,1              ;get AX ready
  76.                           ; to access string stacks
  77.   DS:                     ;override SS:bp
  78.   mov   si,[>ststr1L][bp] ;move L1 into SI or L1
  79.   mov   bx,[>cL1]         ;move CL1 into BX or R1
  80.   DS:                     ;override SS:bp
  81.   mov   di,[>ststr2L][bp] ;move L2 into DI or L2
  82.   mov   cx,[>cL2]         ;move CL2 into CX temporarily
  83.   DS:                     ;override SS:bp
  84.   mov   ax,[>ststr1R][bp] ;get old R1 off of stack
  85.   mov   [>cL1],ax         ;place in CL1 temporarily
  86.   DS:                     ;override SS:bp
  87.   mov   ax,[>ststr2R][bp] ;get old R2 off of stack
  88.   mov   [>cL2],ax         ;save in CL2 temporarily
  89.   mov   bp,cx             ;place CL2 into BP
  90. ;
  91.   cmp   bx,si           ;compare CL1 to L1
  92.   je    Chrght          ;if zero, then nothing
  93. ;                       ; on left side str1
  94.   cmp   bp,di           ;compare CL2 to L2
  95.   je    Chrght          ;if zero, then nothing
  96. ;                       ; on left side str2
  97.   dec   bx              ;point to last part
  98.                         ; of left side str1
  99.   dec   bp              ;ditto, str2
  100.   cmp   bx,si           ;only one char to examine?
  101.   jne   PushIt          ;no->we need to examine this
  102.    cmp  bp,di           ; only one char in both?
  103.    je   Chrght          ;  nothing to look at
  104. ;                       ;  if both only contain 1 char
  105. PushIt:
  106.   call  PushSt          ;push left side on stack
  107. Chrght:
  108.   mov   si,[>cR1]       ;move CR1 into SI or L1
  109.   mov   bx,[>cL1]       ;move R1 into BX or R1
  110.   mov   di,[>cR2]       ;move CR2 into DI or L2
  111.   mov   bp,[>cL2]       ;move R2 into BP or R2
  112. ;
  113.   cmp   si,bx           ;compare CR1 to R1
  114.   je    Main            ;If zero, then nothing
  115.                         ; on right side str1
  116.   cmp   di,bp           ;compare CR2 to R2
  117.   je    Main            ;if zero, then nothing
  118.                         ; on right side str2
  119.   inc   si              ;point to last part
  120.                         ; of right side str1
  121.   inc   di              ;ditto, str2
  122.   cmp   bx,si           ;only one char to examine?
  123.   jne   Push2           ;no-> examine it
  124.    cmp  bp,di           ; only 1 char to examine in both?
  125.    je   Main            ; yes-> get next string off of stack
  126. ;
  127. Push2:
  128.   call  PushSt          ;push right side on stack
  129.   jmp   short Main      ;do next level of compares
  130. ;
  131. Done:
  132.   mov   ax,[>score]     ;get score into AX for MUL
  133.   or    ax,ax           ;zero score?
  134.   jz    Donit           ;yep, skip this mess
  135.    mov  cx,100          ; get 100 into CX for MUL
  136.    mul  cx              ; multiply by 100
  137.    mov  cx,[>total]     ; get total chars for divide
  138.    div  cx              ; divide by total
  139. Donit:
  140.   jmp   Exit            ;clean up and exit
  141. ;
  142. ;subroutines
  143. Compare:
  144.   mov   [>s2ed],bp      ;store end of str2
  145.   xor   dx,dx           ;init MAXCHARS
  146. ForL3:
  147.   push  di              ;save start of str2
  148. ForL4:
  149.   push  di              ;save start of str2
  150.   push  si              ;save start of str1
  151.   mov   cx,[>s2ed]      ;set up for calc
  152.                         ; of length of str1
  153.   sub   cx,di           ;get length of str1 -1
  154.   inc   cx              ;make proper length
  155.   push  cx              ;save str1 starting len
  156.   push  DS              ;save our DS a sec
  157.   mov   ax,ES
  158.   mov   DS,ax           ;force DS=ES for the compare
  159.   repz  cmpsb           ;compare strings
  160.   pop   DS              ;restore our DS
  161.   jz    Equal           ;if equal, then skip fixes
  162.    inc  cx              ; inc back because CMPS decs
  163.                         ; even if not equal
  164. Equal:
  165.   pop   ax              ;get str1 starting len
  166.   sub   ax,cx           ;get length of common characters
  167.   jnz   NewMax          ;more than 0 chars matched
  168. ;
  169.   pop   si              ;get back start of str1
  170.   pop   di              ;ditto str2
  171. ;
  172. Reent:
  173.   inc   di              ;do the next char no matter what
  174. Reent2:
  175.   cmp   di,bp           ;are we done with str2?
  176.   jle   ForL4           ;no, then do next string compare
  177.   pop   di              ;get back start of str2
  178.   inc   si              ;next char in str1 to scan
  179.   cmp   si,bx           ;are we done with str1?
  180.   jle   ForL3           ;no, then do next string compare
  181.   ret                   ;MAXCHARS is in DX
  182. ;
  183. NewMax:
  184.   pop   si              ;get back start of str1
  185.   pop   di              ;and str2
  186.   cmp   ax,dx           ;greater than MAXCHARS?
  187.   jg    NewMx2          ;yes, update new MAXCHARS
  188.                         ;and pointers
  189.    add  di,ax           ; skip past matching chars
  190.    jmp  short Reent2    ; reenter main loop
  191. ;
  192. NewMx2:
  193.   mov   [>cL1],si       ;put begin of match of str1
  194.   mov   [>cL2],di       ;ditto, str2
  195.   mov   cx,ax           ;save new MAXCHARS
  196. ;
  197.   sub   ax,dx           ;get delta for adjustment
  198.                         ; to ends of strings
  199.   sub   bx,ax           ;adjust end of str1
  200.   sub   bp,ax           ; and str2
  201. ;
  202.   mov   dx,cx           ;new MAXCHARS
  203.   dec   cx              ;set up for advance
  204.                         ; to last matching char
  205.   add   di,cx           ;bump to last matching char str2
  206.   mov   [>cR2],di       ;put end of match of str2
  207.   add   cx,si           ;bump to last matching char str1
  208.   mov   [>cR1],cx       ;put end of match of str1
  209.   jmp   short Reent     ;reenter inner loop
  210. ;
  211. PushSt:
  212. ; On Entry:
  213. ;       BX      = R1 (right side of str1)
  214. ;       DS:SI   = L1 (left side of str1)
  215. ;       ES:Di   = L2 (left side of str2)
  216. ;       BP      = R2 (right side of str2)
  217. ;
  218.   mov   cx,bp           ;save R2
  219.   mov   bp,[>stcknum]
  220.   shl   bp,1              ;*2 for words
  221.   DS:                     ;override SS:bp
  222.   mov   [>ststr1L][bp],si ;put left side of str1 on stack
  223.   DS:                     ;override SS:bp
  224.   mov   [>ststr1R][bp],bx ;same with right side
  225.   DS:                     ;override SS:bp
  226.   mov   [>ststr2L][bp],di ;put left side of str2 on stack
  227.   DS:                     ;override SS:bp
  228.   mov   [>ststr2R][bp],cx ;same with right side
  229.   inc   word [>stcknum]   ;bump nr of stack entries
  230.   mov   bp,cx             ;restore R2
  231.   ret
  232. ;
  233. PopSt:
  234. ;       BX      = R1 (right side of str1)
  235. ;       DS:SI   = L1 (left side of str1)
  236. ;       ES:Di   = L2 (left side of str2)
  237. ;       BP      = R2 (right side of str2)
  238. ;
  239.   dec   word [>stcknum]   ;point to last entry on stack
  240.   mov   bp,[>stcknum]     ;get number of stack entries
  241.   shl   bp,1              ;*2 for words
  242.   DS:                     ;override SS:bp
  243.   mov   si,[>ststr1L][bp] ;restore left side
  244.                           ; of str1 from stack
  245.   DS:                     ;override SS:bp
  246.   mov   bx,[>ststr1R][bp] ;ditto, right side
  247.   DS:                     ;override SS:bp
  248.   mov   di,[>ststr2L][bp] ;restore left side
  249.                           ; of str2 from stack
  250.   DS:                     ;override SS:bp
  251.   mov   bp,[>ststr2R][bp] ;ditto, right side
  252.   ret
  253. ;
  254. Exit:
  255.   pop   ES                ;restore ES
  256.   pop   bp                ;restore Turbo's BP
  257.   mov  >result[bp],ax     ;return local value
  258.