|
Statistics
Members: 1927
News: 293
Web Links: 1
Visitors: 3930261
Who's Online
|
 Damn Vulnerable Linux (DVL) is a Linux-based (modified Damn Small Linux) tool for IT-Security & IT-Anti- Security and Attack & Defense. [ CLICK HERE FOR MORE INFOS! ]
|
Featured Conference Video
 OllyBone - Semi-Automatic Unpacking on IA-32. View the conference video here!
|
Home  About/Disclaimer
|
Fastest Binary String Search Algorithm |
|
Written by buliaNaza
|
; Fastest binary string search algo with
; PPlain and PMMX type of processors
; <c> 2001 by buliaNaza ;
; ;
.data? ;
align 4 ; !!!
skip_table DD 256 Dup(?) ; skip table
; ;
;...............................;
; Usage: esi ->pBuffer ; esi->buffer with bytes to be searched through
; ebp = lenBuffer ; ebp =length of the buffer
; ebx ->pSrchData ; ebx->pointer to data to be searched for
; edx = lenSrchData ; edx=length of data to be searched for
; edi ->pskip_table ; edi->pointer to skip table (must be aligned)
; call BMCaseSNext ;
;.................................;
.code ;
BMCaseSNext: ;
cmp edx, 4 ; edx = length of data to be searched for
jg Boyer_Moore ;
;... Brute Force Search ..........; for 4 digits or less only!
mov edi, [ebx] ; edi = dword of data to be searched for
mov ecx, 5 ;
sub ecx, edx ;
lea eax, [esi+edx-1] ; eax->new starting address in pBuffer
shl ecx, 3 ; *8
mov bl, [ebx+edx-1] ; get last byte only
mov bh, bl ; copy in bh
bswap edi ;
shr edi, cl ;
add ebp, esi ; ebp ->end of buffer
and ebx, 0FFFFh ; ebx = need the bx word only
mov ecx, ebx ;
mov esi, edx ; esi=edx = length of data to be searched for
shl ecx, 16 ;
test eax, 3 ;
lea ebx, [ebx+ecx] ;
jz Search_2 ;
Unalign_1: ;
cmp eax, ebp ; ebp ->end of buffer
jge Not_found ;
mov cl, [eax] ;
inc eax ;
cmp cl, bl ;
jz Compare_1 ;
Search_1: ;
test eax, 3 ;
jnz Unalign_1 ;
Search_2: ;
cmp eax, ebp ;u ebp ->end of buffer
jge Not_found ;v
mov ecx, [eax] ;u scasb for the last byte from pSrchData
add eax, 4 ;v
xor ecx, ebx ;u
mov edx, 7EFEFEFFh ;v
add edx, ecx ;u
xor ecx, -1 ;v
xor ecx, edx ;u
mov edx, [eax-4] ;v
and ecx, 81010100h ;u
jz Search_2 ;v
;
cmp dl, bl ;
jz Minus_4 ;
cmp dh, bl ;
jz Minus_3 ;
shr edx, 16 ;
cmp dl, bl ;
jz Minus_2 ;
cmp dh, bl ;
jz Compare_1 ;
jnz Search_2 ;
Minus_2: ;
dec eax ;
jnz Compare_1 ;
Minus_4: ;
sub eax, 3 ;
jnz Compare_1 ;
Minus_3: ;
sub eax, 2 ;
Compare_1: ;
mov edx, edi ;
cmp eax, ebp ; ebp ->end of buffer
jg Not_found ;
cmp esi, 1 ;
jz Found_1 ;
cmp dl, [eax-2] ; eax->pBuffer
jnz Search_1 ;
cmp esi, 2 ;
jz Found_1 ;
cmp dh, [eax-3] ; eax->pBuffer
jnz Search_1 ;
cmp esi, 3 ;
jz Found_1 ;
shr edx, 16 ;
mov cl, [eax-4] ; eax->pBuffer
cmp dl, cl ;
jnz Search_1 ;
Found_1: ;
sub eax, esi ; in eax->pointer to 1st
ret ; occurrence of data found in pBuffer
;...Boyer Moore Case Sens Next Search...;
Boyer_Moore: ;
add esi, ebp ; esi->pointer to the last byte of pBuffer
lea ebx, [ebx+edx-1] ; ebx->pointer to the last byte of pSrchData
neg edx ; edx= -lenSrchData
mov ecx, edx ; ecx = edx = -lenSrchData
add ebp, edx ; sub lenSrchData from lenBuffer
mov eax, 256 ; eax = counter
xor ebp, -1 ; not ebp->current negative index
MaxSkipLens: ;
mov [eax*4+edi-4], edx ; filling up the skip_table with -lenSrchData
mov [eax*4+edi-8], edx ;
mov [eax*4+edi-12], edx ;
mov [eax*4+edi-16], edx ;
mov [eax*4+edi-20], edx ;
mov [eax*4+edi-24], edx ;
mov [eax*4+edi-28], edx ;
mov [eax*4+edi-32], edx ;
mov [eax*4+edi-36], edx ;
mov [eax*4+edi-40], edx ;
mov [eax*4+edi-44], edx ;
mov [eax*4+edi-48], edx ;
mov [eax*4+edi-52], edx ;
mov [eax*4+edi-56], edx ;
mov [eax*4+edi-60], edx ;
mov [eax*4+edi-64], edx ;
mov [eax*4+edi-68], edx ;
mov [eax*4+edi-72], edx ;
mov [eax*4+edi-76], edx ;
mov [eax*4+edi-80], edx ;
mov [eax*4+edi-84], edx ;
mov [eax*4+edi-88], edx ;
mov [eax*4+edi-92], edx ;
mov [eax*4+edi-96], edx ;
mov [eax*4+edi-100], edx ;
mov [eax*4+edi-104], edx ;
mov [eax*4+edi-108], edx ;
mov [eax*4+edi-112], edx ;
mov [eax*4+edi-116], edx ;
mov [eax*4+edi-120], edx ;
mov [eax*4+edi-124], edx ;
mov [eax*4+edi-128], edx ;
sub eax, 32 ;
jne MaxSkipLens ; loop while eax=0
SkipLens: ;
mov al, [ecx+ebx+1] ;u filling up with the real negative offset of
inc ecx ;v every byte from the pSrchData, starting from
mov [eax*4+edi], ecx ;u the last to the first, at the offset in
jne SkipLens ;v skip_table equal to the ASCII code of the
; byte, multiplied by 4
Search: ; the main searching loop-> FAST PART
mov al, [esi+ebp] ;u get a byte from pBuffer ->esi +ebp
mov ecx, edx ;v ecx=edx= -lenSrchData
sub ebp, [eax*4+edi] ;u sub negative offset for this byte from
; skip_table
jc Search ;v if dword ptr [eax*4+edi] AND ebp <> 0 loop
; again
lea ebp, [ebp+esi+1] ;u current negative index -> next byte (+1)
jge Not_found ;v end of pBuffer control (if ebp>=0 end)
; compare previous bytes from pSrchData (->ebx)
Compare: ; and current offset in pBuffer (->ebp)->SLOW
; PART
mov eax, [ebx+ecx+1] ; one dword from pSrchData -> ebx
inc ecx ; ecx = -lenSrchData
jz Found ; if ecx = 0 Found&Exit
cmp al, [ebp+ecx-1] ; ebp->pBuffer
jnz Not_equal ;
inc ecx ; ecx = -lenSrchData
jz Found ; if ecx = 0 Found&Exit
cmp ah, [ebp+ecx-1] ; ebp->pBuffer
jnz Not_equal ;
inc ecx ; ecx = -lenSrchData
jz Found ; if ecx=0 Found&Exit
shr eax, 16 ;
inc ecx ;
cmp al, [ebp+ecx-2] ; ebp->pBuffer
jnz Not_equal ;
test ecx, ecx ; ecx = -lenSrchData
jz Found ; if ecx=0 Found&Exit
cmp ah, [ebp+ecx-1] ; ebp->pBuffer
jz Compare ;
Not_equal: ;
sub eax, eax ; eax = 0
sub ebp, esi ; restore ebp->current negative index
jl Search ; end of pBuffer control
Not_found: ;
or eax, -1 ; Exit with flag Not_Found eax=-1
ret ;
Found: ;
lea eax, [ebp+edx] ; in eax->pointer to 1st
ret ; occurrence of data found in pBuffer
|
|