{ The originial benchmark program was to demonstrate the speed difference between the POS() in Turbo Pascal 4 or 5 brute-force and the Boyer-Moore method function POSBM() Program author: Costas Menico Call: posbm(pat,buf,buflen); or if you are using a string buffer: posbm(pat,s[1],length(s)); } program bufSearch; uses dos, crt; {$F+} function posbm(pat:string; var buf; buflen:word):word; EXTERNAL; {$L BM.OBJ} {$F-} function bruteForce(var such:string; var buf; buflen:word):word; ASSEMBLER; ASM cld push ds les di,buf mov cx,buflen jcxz @@30 lds si,such mov al,[si] or al,al je @@30 xor ah,ah cmp ax,cx ja @@30 mov bx,si dec cx @@10: mov si,bx lodsw xchg al,ah { AH=Stringl„nge, AL=Suchchar } repne scasb jne @@30 dec ah or ah,ah je @@20 inc cx { CX++ nach rep... } xchg cx,ax mov cl,ch xor ch,ch mov dx,di repe cmpsb mov di,dx mov cx,ax loopne @@10 @@20: mov ax,buflen sub ax,cx dec ax jmp @@40 @@30: xor ax,ax @@40: pop ds end; procedure showtime(s : string; t : registers); begin writeln(s, ' Hrs:', t.ch, ' Min:', t.cl, ' Sec:', t.dh, ' Milsec:', t.dl); end; var pat : string; i, j : integer; start, finish : registers; arr : array[1..4096] of char; const longloop = 5000; begin clrscr; randomize; for i := 1 to 4096 do arr[i] := chr(random(255)+1); move(arr[4090],pat[1],5); pat[0]:=#5; writeln('Search using Brute-Force Method '); start.ah := $2C; msdos(start); for j := 1 to longloop do i := bruteForce(pat,arr,4096); finish.ah := $2C; msdos(finish); showtime('Start ', start); showtime('Finish ', finish); writeln('Pattern found at position ', i); writeln; writeln('Search using Boyer-Moore Method '); start.ah := $2C; msdos(start); for j := 1 to longloop do i := posbm(pat, arr,4096); finish.ah := $2C; msdos(finish); showtime('Start ', start); showtime('Finish ', finish); writeln('Pattern found at position ', i); writeln; writeln('Done ... Press Enter'); readln; end. { -------------------------- XX34 OBJECT CODE ----------------------- } { ------------------------- CUT OUT AND SAVE AS BM.XX ------------------} { ------------------------ USE XX3401 D BM.XX ------------------------} *XX3401-000392-050693--68--85-03573----------BM.OBJ--1-OF--1 U-M+32AuL3--IoB-H3l-IopQEYoiEJBBYcUU++++53FpQa7j623nQqJhMalZQW+UJaJm QqZjPW+n9X8NW-k+ECbfXgIO32AuL3--IoB-H3l-IopQEYoiEJBB+sU1+21dH7M0++-c W+A+E84IZUM+-2BDF2J3a+Q+OCQ++U2-1d+A+++--J-DIo7B++++rMU2+20W+N4Uuk+- ++-JUSkA+Mjg5X9YzAKq4+4AbUM-f+f+REDdjU09m6Z4+6aq-+53hVE-X7s8+Mi42U29 k5I1uO6+WIM0WPM6+MDt+LIPlPM2+On2jUU-Wos0weto+ya1+6jrUys0uqyEXLs2XB8C kcd4+6fUiM++wuj3hUE-XJs2Wos+GMjRXKs2AiGgWzW60y9tf6jsW+i9uwKq0+4BTUG9 JU78WoM+G19zzGjEQXE1w6cQBcc-0g-pwMjSWos+l9s2+Iw1yTCaR+ms+E0BTUG9wn9z uxK9lgKq0+2flUI0+Cg0Aw1w5sjZUQEA+Jr80U-fWU6++5E+ ***** END OF XX-BLOCK ***** { -------------------------- ASSEMBLER CODE ------------------------- } { ------------------------- CUT OUT AND SAVE AS BM.AMS ------------------} { ------------------------ USE TASM TO ASSEMBLE ------------------------} ; filename: BM.ASM ; fast search routine to search strings in ARRAYS OF CHARS ; function in Turbo Pascal >= 4. Based on the Boyer-Moore algorithm. ; program author: Costas Menico. ; Very small modifications for using an ARRAY OF CHAR buffer instead of ; a string made by Jochen Magnus in May 93. ; declare as follows: ; {$F+} ; {$L BM.OBJ} ; function posbm(pat:string; var buffer; buflen:word):WORD; external; ; call as follows from Turbo 4..7: ; location := posbm(pat, buf, buflen); ; call for a search in a string typed buffer: ; location := posbm(pat, str[1], length(str)); skiparrlength equ 256 ; function work stack dstk struc patlen dw ? strlen dw ? skiparr db skiparrlength dup(?) pattxt dd 0 strtxt dd 0 dstk ends ; total stack (callers plus work stack) cstk struc ourdata db size dstk dup(?) bpsave dw 0 retaddr dd 0 paramlen dw 0 ; JO straddr dd 0 pataddr dd 0 cstk ends paramsize equ size pataddr+size straddr +size paramlen ; +2 JO code segment para public assume cs:code ; entry point to posbm function posbm proc far public posbm push bp sub sp, size dstk mov bp, sp push ds xor ah, ah cld ; get and save the length and address of the pattern lds si, [bp.pataddr] mov word ptr [bp.pattxt][2], ds lodsb or al, al jne notnullp jmp nomatch notnullp: mov cx, ax mov [bp.patlen], ax mov word ptr [bp.pattxt], si ; get and save the length and address of the string text lds si, [bp.straddr] mov word ptr [bp.strtxt][2], ds mov ax,[bp.paramlen] ; JO or ax,ax ; JO jne notnulls jmp nomatch notnulls: mov [bp.strlen], ax mov word ptr [bp.strtxt], si cmp cx, 1 jne do_boyer_moore lds si, [bp.pattxt] lodsb les di, [bp.strtxt] mov cx, [bp.strlen] repne scasb jz match1 jmp nomatch match1: mov si, di sub si, 2 jmp exactmatch do_boyer_moore: ; fill the ASCII character skiparray with the ; length of the pattern lea di, [bp.skiparr] mov dx, ss mov es, dx mov al, byte ptr [bp.patlen] mov ah, al mov cx, skiparrlength/2 rep stosw ; replace in the ASCII skiparray the corresponding ; character offset from the end of the pattern minus 1 lds si, [bp.pattxt] lea bx, [bp.skiparr] mov cx, [bp.patlen] dec cx mov bx, bp lea bp, [bp.skiparr] xor ah, ah fill_skiparray: lodsb mov di, ax mov [bp+di], cl loop fill_skiparray lodsb mov di, ax mov [bp+di], cl mov bp, bx ; now initialize our pattern and string text pointers to ; start searching lds si, [bp.strtxt] lea di, [bp.skiparr] mov dx, [bp.strlen] dec dx mov ax, [bp.patlen] dec ax xor bh, bh std ; get character from text. use the character as an index ; into the skiparray, looking for a skip value of 0. ; if found, execute a brute-force search on the pattern searchlast: sub dx, ax jc nomatch add si, ax mov bl, [si] mov al, ss:[di+bx] or al, al jne searchlast ; we have a possible match, therefore ; do the reverse brute-force compare mov bx, si mov cx, [bp.patlen] les di, [bp.pattxt] dec di add di, cx repe cmpsb je exactmatch mov ax, 1 lea di, [bp.skiparr] mov si, bx xor bh, bh jmp short searchlast exactmatch: mov ax, si lds si, [bp.strtxt] sub ax, si add ax, 2 jmp short endsearch nomatch: xor ax, ax endsearch: cld pop ds mov sp, bp add sp, size dstk pop bp ret paramsize posbm endp code ends end {----------------------- END OF ASSEMBLER CODE -------------------------}