Previous | Table of Contents | Next

Listing 9.1 implements the scan-on-first-character approach. Listing 9.2 scans for whatever character the caller specifies. Listing 9.3 is a test program used to compare the two approaches. How much difference does Rob’s revelation make? Plenty. Even when the entire C function call to FindString is timed—strlen calls, parameter pushing, calling, setup, and all—the version of FindString in Listing 9.2, which is directed by Listing 9.3 to scan for the infrequently-occurring “Q,” is about 40 percent faster on a 20 MHz cached 386 for the test search of Listing 9.3 than is the version of FindString in Listing 9.1, which always scans for the first character, in this case “E.” However, when only the search loops (the code that actually does the searching) in the two versions of FindString are compared, Listing 9.2 is more than twice as fast as Listing 9.1—a remarkable improvement over code that already uses REPNZ SCASB and REPZ CMPS.

What I like so much about Rob’s approach is that it demonstrates that optimization involves much more than instruction selection and cycle counting. Listings 9.1 and 9.2 use pretty much the same instructions, and even use the same approach of scanning with REPNZ SCASB and using REPZ CMPS to check scanning matches.

| The difference between Listings 9.1 and 9.2 (which gives you more than a doubling of performance) is due entirely to understanding the nature of the data being handled, and biasing the code to reflect that knowledge.

Figure 9.2 Faster searching method for locating a text string.

LISTING 9.1 L9-1.ASM

    ; Searches a text buffer for a text string. Uses REPNZ SCASB to sca"n
    ; the buffer for locations that match the first character of the
    ; searched-for string, then uses REPZ CMPS to check fully only those
    ; locations that REPNZ SCASB has identified as potential matches.
    ;
    ; Adapted from Zen of Assembly Language, by Michael Abrash
    ;
    ; C small model-callable as:
    ;    unsigned char * FindString(unsigned char * Buffer,
    ;     unsigned int BufferLength, unsigned char * SearchString,
    ;     unsigned int SearchStringLength);
    ;
    ; Returns a pointer to the first match for SearchString in Buffer,or
    ; a NULL pointer if no match is found. Buffer should not start at
    ; offset 0 in the data segment to avoid confusing a match at 0 with
    ; no match found.
    Parmsstruc
                            dw    2 dup(?) ;pushed BP/return address
    Buffer                  dw      ?      ;pointer to buffer to search
    BufferLength            dw      ?      ;length of buffer to search
    SearchString            dw      ?      ;pointer to string for which to search
    SearchStringLength      dw      ?      ;length of string for which to search
    Parmsends
          .model      small
          .code
          public _FindString
    _FindStringprocnear
          push     bp      ;preserve caller’s stack frame
          mov      bp,sp   ;point to our stack frame
          push     si      ;preserve caller’s register variables
          push     di
          cld              ;make string instructions increment pointers
          mov      si,[bp+SearchString]       ;pointer to string to search for
          mov      bx,[bp+SearchStringLength] ;length of string
          and bx,bx
          jz       FindStringNotFound         ;no match if string is 0 length
          movd      x,[bp+BufferLength]       ;length of buffer
          sub      dx,bx                      ;difference between buffer and string lengths
          jc      FindStringNotFound          ;no match if search string is
                                              ; longer than buffer
          inc      dx      ;difference between buffer and search string
                           ; lengths, plus 1 (# of possible string start
                           ; locations to check in the buffer)
          mov      di,ds
          mov      es,di
          mov      di,[bp+Buffer]       ;point ES:DI to buffer to search thru
          lodsb                         ;put the first byte of the search string in AL
          mov      bp,si                ;set aside pointer to the second search byte
          dec      bx                   ;don’t need to compare the first byte of the
                                        ; string with CMPS; we’ll do it with SCAS
    FindStringLoop:
          mov    cx,dx ;put remaining buffer search length in CX
          repnz  scasb ;scan for the first byte of the string
          jnz    FindStringNotFound ;not found, so there’s no match
                                    ;found, so we have a potential match-check the
                                    ; rest of this candidate location
          push   di                 ;remember the address of the next byte to scan
          mov    dx,cx              ;set aside the remaining length to search in
                                    ; the buffer
          mov    si,bp              ;point to the rest of the search string
          mov    cx,bx              ;string length (minus first byte)
          shr    cx,1               ;convert to word for faster search
          jnc    FindStringWord     ;do word search if no odd byte
          cmpsb                     ;compare the odd byte
          jnz    FindStringNoMatch  ;odd byte doesn’t match, so we
                                    ; haven’t found the search string here
    FindStringWord:
          jcxz   FindStringFound    ;test whether we’ve already checked
                                    ; the whole string; if so, this is a match
                                    ; bytes long; if so, we’ve found a match
          repz   cmpsw              ;check the rest of the string a word at a time
          jz     FindStringFound    ;it’s a match
    FindStringNoMatch:
          pop    di                 ;get back pointer to the next byte to scan
          and    dx,dx              ;is there anything left to check?
          jnz    FindStringLoop     ;yes-check next byte
    FindStringNotFound:
          sub    ax,ax              ;return a NULL pointer indicating that the
          jmp    FindStringDone     ; string was not found
    FindStringFound:
          pop    ax                 ;point to the buffer location at which the
          dec    ax                 ; string was found (earlier we pushed the
                                    ; address of the byte after the start of the
                                    ; potential match)
    FindStringDone:
          pop    di                 ;restore caller’s register variables
          pop    si
          pop    bp                 ;restore caller’s stack frame
    ret
    _FindStringendp
          end

Previous | Table of Contents | Next

Graphics Programming Black Book © 2001 Michael Abrash