[A89] Re: Quick, fast, find and replace
[Prev][Next][Index][Thread]
[A89] Re: Quick, fast, find and replace
Thank you, maybe I should have specified C, but I have made a for routine to
do a fairly fast lookup.
----- Original Message -----
From: <jorma.oksanen@aina.fi>
To: <assembly-89@lists.ticalc.org>
Sent: Saturday, May 10, 2003 9:40 AM
Subject: [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
>
>
---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.476 / Virus Database: 273 - Release Date: 4/24/2003
Follow-Ups:
References: