3 ms·
Back in the days of MS-DOS I wrote what I thought was a fairly clever search algorithm making use of the XLAT instruction. It could search for N= 1-8 characters
by mikewarot 6y ago
Back in the days of MS-DOS I wrote what I thought was a fairly clever search algorithm making use of the XLAT instruction. It could search for N= 1-8 characters in a block of text in a loop 7 instructions long, which I'm trying to reproduce from memory
start:
xor ah,ah
lea bx, masktable
mov cx, textlength
lea si, texttosearch
test_character:
or ah, startbit (set bit 8-N of the ah register)
lodsb (get a character into AL)
xlat (AL gets [BX+AL])
and ah,al (masks off non-matching characters)
shl ah,1 (AH=AH*2, carry goes into Carry Flag)
jc match_found ; we found a match, break out
loopnz test_character
no_match_found: ; get here if there isn't a match
In a 64 bit environment, you should be able to search for up to 64 characters fairly quickly, using a table that is 8*256 bytes, you can do case insensitive searches, along with a ? for any character to do some wildcarding. The nice thing is that everything is in the cache until you jump out when you have a match, and not before.
- mikewarot 6y agoI went through the work, and re-implemented it as an assembly language routine inside a 64bit free pascal program. It searches about 1 gigabyte of text in 2 seconds. https://github.com/mikewarot/fastsearch/blob/master/fastsearch_demo.lpr https://github.com/mikewarot/fastsearch/blob/master/fastsear...