[A89] Re: Quick, fast, find and replace
[Prev][Next][Index][Thread]
[A89] Re: Quick, fast, find and replace
On 9 May 2003 at 23:30, Nick Peaden wrote:
> I need to make a routine that would be quick and fast to lookup and
> replace about 50 different values.
Assuming 16-bit values:
start: lea table(pc),a0 ; data to be scanned
lea replace(pc),a1 ; values to search for
move.l #with-replace,d1 ; offset between search/replace table start
.loop move.w (a0)+,d0
beq.s .end ; data ends with NULL
move.l a1,a2
.search cmp.w (a2)+,d0
bgt.s .search ; search data sorted, can use bgt instead of bne
bne.s .loop ; no match, search next
move.w 0(a2,d1.l),-2(a0)
bra.s .loop
.end rts
table dc.w data1,data2,0
replace dc.w old1,old2,-1 ; ascendingly sorted
with dc.w new1,new2,-1
You can unroll search loop for speedup:
.search cmp.w (a2)+,d0
ble.s .maybe
...
cmp.w (a2)+,d0
bgt.s .search
.maybe bne.s .loop
With 8-bit values it's most efficient to use straight lookup table.
You can do that quite efficiently with 16/32-bit values as well,
using bits 1-8 as hash value:
; d0.l=replace(d0.l)
lea hash(pc),a0
move.w d0,d1
and.w #$1FE,d1
move.w 0(a0,d1.w),d1 ; offset to subtable
beq.s .not_found
lea 0(a0,d1.w),a0 ; new1,old1, ... ,-1,-1
.loop move.l (a0)+,d1
cmp.l (a0)+,d0
ble.s .loop
bne.s .not_found
move.l d1,d0
.not_found
"hash" holds offset (from start of "hash" itself) to the table with
matching bits 1-8, in ascending search-value order. Memory overhead
compared to single table as in first example is only 512 bytes for
hash table, and couple of bytes for each subtable end-mark.
You might be talking about variable-length values tho.
Jorma
Follow-Ups:
References: