Nyall Le 09/12/2003 à 04:44 pardon the english.
In Pedrom when an entry is made into the vat is it always null padded? Meaning if there is a file called "bill" will it be stored as 'b','i','l','l',0,0,0,0 ? Or will it be stored as 'b','i','l','l',0,junk,junk,junk?
The reason is that if it is null padded certain optomizations can be made to the vat searching routine. Here is something I would have liked to have added to tios.
-Samuel S
; Destroy:
; d0-d2/a0-a1
; a0 : handle of the list we look into
; a1 : name of the entry we look for
; Return:
; a0 -> Sym Entry or NULL
FindSymEntry:
move.w a2,-(a7)
trap #3 ; a0 : contents of the list
addq.l #2,a0 ; skips the 1st word (Max items)
move.w (a0)+,d2 ; d2 = # items in the list
beq.s \false ; -> not found
;---Align the name on an even address and null pad unused bytes.
;---The null padding is important
clr.l -(a7)
clr.l -(a7)
move.l a7,a2
moveq #7,d0
\align_loop
move.b (a1)+,(a2)+
dbeq d0,\align_loop
move.w (a7)+,d0 ;get the entire name into d0.w, a1.l and d1.w
move.l (a7)+,a1
move.w (a7)+,d1
lea -SYM_ENTRY.sizeof(a0),a0
subq.w #1,d2 ; - 1 for dbra
;----The idea behind the next bit is that the first comparison will most likely fail but once
;----it succeeds the next comparisons will most likely also succeed.
;----Hopefully it will spend most its time in the first 3 instructions. And it will only come
;----out of the first 3 instructions when d2 = -1 or a FULL match is found
\search
lea SYM_ENTRY.sizeof(a0),a0
cmp.w (a0),d0
\nextSymbol
dbeq d2,\search
bne.s \false
cmp.l 2(a0),a1
bne.s \nextSymbol ;this could be replaced by another "dbeq d2,\search" "bne.s \false" combination
cmp.w 6(a0),d1
dbeq d2,\search
beq.s \end
\false
suba.l a0,a0
\end
move.w (a7)+,d3
rts
I am the one and only cheerio.
-Samuel Stearley
By the way, I assume you kept compatibility with the TIOS so that sym_entry->name[8] is always zero? (this seems to be wrong with some kernels, so actually it might be the same with PedRom...)
« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)
PpHd Le 09/12/2003 à 16:49 1. Yes, sym_entry->name[8] is zero.
2. Yes, Preos 0.67 may corrupt this for some libraries files. But it is no longer the case with Preos 0.68.
Nyall Le 09/12/2003 à 18:00 Have you looked into cordic at all for trig functions? It is quite accurate and the math is only adds/subtracts and left shifting.
I know a binary search would be faster for really large vat tables, but just because I like combining conditional codes with dbra I'll give one more version of the seach code.
;---First loop-----------
\search
lea SYM_ENTRY.sizeof(a0),a0
cmp.w (a0),d0
dbls d2,\search ;go till d2 = -1 or c=1 or z =1
bcs \false ;if c=1 then loop gave out becasue of alphabetic ordering
bne.s \false ;branch if loop gave out because d2 =-1
;---special optomization of 1 letter names. Makes more sense if there is a basic interpreter-----
tst.b d0
bne.s \into_next
move.l (a7)+,a2
rts
;---second loop------
\search2
lea SYM_ENTRY.sizeof(a0),a0
cmp.w (a0),d0
bne \false
\into_next
cmp.l 2(a0),a1
dbls d2,\search2 ;go till d2 =-1 or c=1 or z =1
bcs \false ;if c=1 then loop gave out becasue of alphabetic ordering
bne.s \false ;branch if loop gave out because d2=-1
;----;special optomizaiton for 2, 3, 4,5 letter names-----
exg a1,d0
tst.b d0
beq.s \end
exg a1,d0
lea -SYM_ENTRY.sizeof(a0),a0
;---third loop-----
\search3
lea SYM_ENTRY.sizeof(a0),a0
cmp.w (a0),d0
bne \false
cmp.l 2(a0),a1
bne.s \false
cmp.w 6(a0),d1
dbls d2,\search3 ;go till d2 =-1 or c=1 or z =1
beq \end
beq.s \end
\false
suba.l a0,a0
\end
move.w (a7)+,d3
rts
I am the one and only cheerio.
-Samuel Stearley
Nyall Le 09/12/2003 à 19:45 You might be right about it being faster. the cmp will be slower, but the addq is faster faster. And it checks more letters at once. Also you could add a tst.b d0 to provide special optomization for 1, 2, or 3 letter names.
About cordic on each iteration i you will have to do a mulitply by 2^-i.
-Samuel
I am the one and only cheerio.
-Samuel Stearley
Nyall Le 10/12/2003 à 01:38 >>I believe PpHd's solution is fairly good,
Please let me rephrase: You can search for a name as a long-long value. Or as a variable width string. For the quick code I wrote I chose it to be a word-long-word. Even if PpHd goes with a binary search I think it will be much faster to search for it as a long-long than as a string. I'm not going to push it. Hope I fed some food for thought.
>>(but, would the speed difference ever be noticeable?)
Vat search could be 10x faster. The speed difference will be noticeable if there is a basic interpretter.
One more thing:
\search
cmp.l (a0)+,d0
addq.l #8,a0
dbls d2,\search
bcs.s \False
It won't work because Vat entries are 14 bytes, while this loop is adding 12.
-Samuel S
I am the one and only cheerio.
-Samuel Stearley