Previous | Table of Contents | Next

Listing 16.6 OPT2.ASM

     ;
     ;          Opt2         Final optimization word count
     ;          Written by   Michael Abrash
     ;          Modified by  Willem Clements
     ;                       C/ Moncayo 5,  Laurel de la Reina
     ;                       18140 La Zubia
     ;                       Granada, Spain
     ;                       Tel 34-58-890398
     ;                       Fax 34-58-224102
     ;
     parms          struc
                    dw         2 dup(?)
     buffer         dw         ?
     bufferlength   dw         ?
     charflag       dw         ?
     wordcount      dw         ?
     parms          ends
                    .model     small
                    .data
     charstatustable label byte
                    rept       2
                    db         39 dup(0)
                    db         1
                    db         8 dup(0)
                    db         10 dup(1)
                    db         7 dup(0)
                    db         26 dup(1)
                    db         6 dup(0)
                    db         26 dup(1)
                    db         5 dup(0)
                    endm
                    .code
                    public     _ScanBuffer
     _ScanBuffer    proc       near
                    push       bp
                    mov        bp,sp
                    push       si
                    push       di
                    mov        si,[bp+buffer]
                    mov        bx,[bp+charflag]
                    mov        al,[bx]
                    mov        cx,[bp+bufferlength]
                    mov        bx,offset charstatustable
                    xor        di,di      ; set wordcount to zero
                    shr        cx,1       ; change count to wordcount
                    jc         oddentry   ; odd number of bytes to process
                    cmp        al,01h     ; check if last one is char
                    jne        scanloop4  ; if not so, search for char
                    jmp        scanloop1  ; if so, search for zero
     oddentry:      xchg       al,ah      ; last one in ah
                    lodsb                 ; get first byte
                    inc        cx
                    cmp        ah,01h     ; check if last one was char
                    jne        scanloop5  ; if not so, search for char
                    jmp        scanloop2  ; if so, search for zero
     ;
     ;              locate the end of a word
     scanloop1:     lodsw                  ; get two chars
                    xlat                   ; translate first
                    xchg       al,ah       ; first in ah
     scanloop2:     xlat                   ; translate second
                    dec        cx          ; count down
                    jz         done1       ; no more bytes left
                    cmp        ax,0101h    ; check if two chars
                    je         scanloop1   ; go for next two bytes
                    inc        di          ; increase wordcount
                    cmp        al,01h      ; check if new word started
                    je         scanloop1   ; locate end of word
     ;
     ;              locate the begin of a word
     scanloop4:     lodsw                     ; get two chars
                    xlat                      ; translate first
                    xchg       al,ah          ; first in ah
     scanloop5:     xlat                      ; translate second
                    dec        cx             ; count down
                    jz         done2          ; no more bytes left
                    cmp        ax,0           ; check if word started
                    je         scanloop4      ; if not, locate begin
                    cmp        al,01h         ; check one-letter word
                    je         scanloop1      ; if not, locate end of word
                    inc        di             ; increase wordcount
                    jmp        scanloop4      ; locate begin of next word
     done1:         cmp        ax,0101h       ; check if end-of-word
                    je         done           ; if not, we have finished
                    inc        di             ; increase wordcount
                    jmp        done
     done2:         cmp        ax,0100h       ; check for one-letter word
                    jne        done           ; if not, we have finished
                    inc        di             ; increase wordcount
     done:          mov        si,[bp+charflag]
                    mov        [si],al
                    mov        bx,[bp+wordcount]
                    mov        ax,[bx]
                    mov        dx,[bx+2]
                    add        di,ax
                    adc        dx,0
                    mov        [bx],di
                    mov        [bx+2],dx
                    pop        di
                    pop        si
                    pop        bp
                    ret
     _ScanBuffer    endp
                    end

### Level 2: A New Perspective

The second level of optimization is one of breaking out of the mode of thinking established by my original code. Some entrants clearly did exactly that. They stepped back, thought about what the code actually needed to do, rather than just improving how it already worked, and implemented code that sprang from that new perspective.

You can see one example of this in Listing 16.6, where Willem uses CMP AX,0101H to check two bytes at once. While you might think of this as nothing more than a doubling up of tests, it’s a little more than that, especially when taken together with the use of two loops. This is a break with the serial nature of the C code, a recognition that word counting is really nothing more than a state machine that transitions from the “in word” state to the “not in word” state and back, counting a word on one but not both of those transitions. Willem says, in effect, “We’re in a word; if the next two bytes are non-separators, then we’re still in a word, else we’re not in a word, so count and change to the appropriate state.” That’s really quite different from saying, as I originally did, “If the last byte was a non-separator, then if the current byte is a separator, then count a word.” Willem has moved away from the all-in-one approach, splitting the code up into state-specific chunks that are more efficient because each does only the work required in a particular state.

Another example of coming at the code from a new perspective is counting a word as soon as a non-separator follows a separator (at the start of the word), rather than waiting for a separator following a non-separator (at the end of the word). My friend Dan Illowsky describes the thought process leading to this approach thusly:

“I try to code as closely as possible to the real world nature of those things my program models. It seems somehow wrong to me to count the end of a word as you do when you look for a transition from a word to a non-word. A word is not a transition, it is the presence of a group of characters. Thought of this way, the code would have counted the word when it first detected the group. Had you done this, your main program would not have needed to look for the possible last transition or deal with the semantics of the value in CharValue.”

John Richardson, of New York, contributed a good example of the benefits of a different perspective (in this case, a hardware perspective). John eliminated all branches used for detecting word edges; the inner loop of his code is shown in Listing 16.7. As John explains it:

“My next shot was to get rid of all the branches in the loop. To do that, I reached back to my college hardware courses. I noticed that we were really looking at an edge triggered device we want to count each time the I’m a character state goes from one to zero. Remembering that XOR on two single-bit values will always return whether the bits are different or the same, I implemented a transition counter. The counter triggers every time a word begins or ends.”

Previous | Table of Contents | Next

Graphics Programming Black Book © 2001 Michael Abrash