New line tokeniser.

[hutch--]

Be interesting to see the comparison. here is the simple benchmark for the tokeniser.

Code Select Expand


172 ms for tokenising 2673001 lines of text
Press any key to continue ...


With the 101 meg file it runs at just under 600 meg/sec including both the allocation and deallocation on this core2 quad.

To run the test run the exe file BLDTST.EXE first to create the test piece.

It will run on a 486.

[jj2007]

688 ms for tokenising 2673001 lines of text (Hutch)
359 ms for tokenising 2673000 lines of text (MasmBasic)

[oex]

How long does the other line take JJ? :lol

[dedndave]

 :lol
i was wondering which is correct, myself
and - if the last line of the file has no CR or LF, does it still count as a line ?
next question - if you are going to count the last line that has no CR or LF, i take it it must have some other char in order to be a line

how many lines in this file ?

10,10,13,13,13,13,10,10,10,10,10,10,13,13,13

[jj2007]

How long does the other line take JJ? :lol

Depends on whether you count a trailing CrLf as a "line" :wink

[jj2007]

:lol
i was wondering which is correct, myself
and - if the last line of the file has no CR or LF, does it still count as a line ?
next question - if you are going to count the last line that has no CR or LF, i take it it must have some other char in order to be a line

how many lines in this file ?

10,10,13,13,13,13,10,10,10,10,10,10,13,13,13

Two with Recall - correctly, if end of line is defined as CrLf.

[dedndave]

well, i can tell you that a printer would see 8 lines

for this one...

10,10,13,13,13,13,10,10,10,10,10,10,13,65,13,13

the printer would see 9 lines

it counts line feeds only
if there is a non-control character between the last line feed and EOF, add an additional line to the count
of course, form feed adds a few lines   :P
you have to know how many lines per page, then count back and supplement - yikes !

[jj2007]

Well, to be precise, Recall returns 2 lines and 7 BadLines. You need rules, and CrLf is CrLf, not LF.
Notepad sees two lines, MS Word and QEditor see 12, Notepad++ arrives at 15, WordPad 13...

[hutch--]

These are the times from the version that JJ posted.

Code Select Expand


266 ms for tokenising 2673001 lines of text
156 ms for tokenising 2673000 lines of text
Press any key to continue ...


I am guessing its an SSE version but with no source supplied I cannot build it. The tokeniser at the top of this topic runs on a 486 and is fully backwards compatible with any OS version that will run 32 bit Windows.

This is as close as I can identify it from disassembly.

Code Select Expand


fn_00401D50:

    push ebp
    mov ebp, esp
    sub esp, 34h
    pushad
    lea eax, [ebp-34h]
    movups [eax], xmm0
    movups [eax+10h], xmm1
    mov eax, [ebp+8]
    xor edi, edi
    cmp eax, 0Ah
    jbe lbl0
    push eax
    push edi
    push eax
    push 9
    call fn_00402348
    pop edx
    push eax
    sub eax, 0FFFFFFFFh
    je loc_00402721
    push 9
    pop eax
    jmp lbl1

  lbl0:
    push DWORD PTR [4072B6h+eax*4]

  lbl1:
    and [4072B6h+eax*4], edi
    push edi
    push DWORD PTR [esp+4]
    call GetFileSize
    mov [ebp-10h], eax
    lea ebx, [eax+4]
    shr ebx, 1
    mov esi, eax
    add eax, 29h
    push edi
    push eax
    call fn_004027EF
    mov [ebp-14h], eax
    test al, 0Fh
    jz lbl2
    add eax, 8

  lbl2:
    xorps xmm0, xmm0
    movups [eax+esi], xmm0
    movups [eax+esi+10h], xmm0
    mov edi, eax
    mov edx, [esp]
    push 0
    lea eax, [ebp-8]
    push eax
    push esi
    push edi
    push edx
    call ReadFile
    call CloseHandle
    push DWORD PTR [ebp+10h]
    push ebx
    push 0
    call fn_00402CC7
    mov [eax+4], edi
    cmp edi, [ebp-14h]
    jz lbl3
    inc DWORD PTR [eax+4]

  lbl3:
    mov edx, [ebp+14h]
    cmp edx, 0FFFFFF88h
    jg lbl4
    mov [eax+0Ch], edx
    and DWORD PTR [ebp+14h], 0

  lbl4:
    add eax, 10h
    mov [ebp-0Ch], eax
    mov eax, 0A0A0A0Ah
    movd xmm1, eax
    pshufd xmm1, xmm1, 0
    add esi, edi
    mov ecx, [ebp-0Ch]
    push DWORD PTR [ebp+14h]
    push ebx
    mov ebx, ecx
    mov [ebx], edi
    and DWORD PTR [405F50h], 0
    xor eax, eax

  lbl5:
    movaps xmm0, xmm1
    pcmpeqb xmm0, [edi+10h]
    pmovmskb ecx, xmm0
    movaps xmm0, xmm1
    pcmpeqb xmm0, [edi]
    pmovmskb edx, xmm0
    lea edi, [edi+20h]
    shl ecx, 10h
    cmp edi, esi
    jnb lbl6
    or edx, ecx
    jz lbl5
    call fn_00401ED6
    jmp lbl5

  lbl6:
    or edx, ecx
    jz lbl7
    call fn_00401ED6

  lbl7:
    cmp BYTE PTR [esi-1], 0Ah
    jz lbl8
    inc eax
    add esi, 2

  lbl8:
    mov edx, [esp+4]
    test edx, edx
    jz lbl10
    bswap edx
    cmp dh, 91h
    jnz lbl9
    inc eax
    jmp lbl10

  lbl9:
    bswap edx
    mov [edx], eax

  lbl10:
    mov [ebx+eax*8], esi
    pop ebx
    pop edi
    mov edi, [ebp-0Ch]
    mov [edi-10h], eax
    mov ecx, eax

  lbl11:
    mov edx, [edi]
    sub edx, [edi+8]
    add edx, 2
    mov [edi+4], edx
    add edi, 8
    dec ecx
    jg lbl11
    mov [esp+1Ch], eax
    xor edi, edi
    push edi
    push eax
    push DWORD PTR [ebp+0Ch]
    call fn_00402CC7
    push DWORD PTR [ebp+0Ch]
    push edi
    call fn_00402FFF
    push edi
    call fn_00402EDC
    lea eax, [ebp-34h]
    movups xmm0, [eax]
    movups xmm1, [eax+10h]
    popad
    mov edx, [ebp-10h]
    mov esp, ebp
    pop ebp
    ret 10h

  lbl12:
    pop esi
    ret


[jj2007]

These are the times from the version that JJ posted.

Code Select Expand


266 ms for tokenising 2673001 lines of text
156 ms for tokenising 2673000 lines of text
Press any key to continue ...


I am guessing its an SSE version but with no source supplied I cannot build it. The tokeniser at the top of this topic runs on a 486 and is fully backwards compatible with any OS version that will run 32 bit Windows.

This is as close as I can identify it from disassembly.
...

Hutch,
It used to be available as getlinesjj through the Forum's search function - there was an endless thread testing this algo and variants.
Here is the innermost loop (with some inspiration from Lingo, NightWare and Agner Fog):

Code Select Expand

L1: movaps xmm0, xmm1 ; linefeeds in xmm0 & xmm1
pcmpeqb xmm0, [edi+16] ; compare packed bytes in [m128] and xmm0 for equality
pmovmskb ecx, xmm0 ; set byte mask in edx for second 16 byte chunk
movaps xmm0, xmm1 ; linefeeds in xmm0 (pcmpeqb resets xmm0 to zero - we must reload it!)
pcmpeqb xmm0, [edi] ; compare packed bytes in [m128] and xmm0 for equality
pmovmskb edx, xmm0 ; set byte mask in edx for first 16 byte chunk
lea edi, [edi+32] ; point to next chunk
shl ecx, 16
cmp edi, esi ; test boundary
jae LastString
or edx, ecx
jz L1


P.S.: The source is included in toktok.zip - all you need is include \masm32\MasmBasic\MasmBasic.inc :wink