[mOved] Entries in the VAT? - Page 1

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

The answer is: no:

Extract from SymAdd

\Created:	move.l	(a7),a1		; Get Name
		moveq	#8-1,d0
\loop			move.b	(a1)+,(a0)+
			dbf	d0,\loop
		move.l	#$00030000,(a0)+	; Compat + Flags
		clr.w	(a0)+		; No Handle

But it could. quite easilly.

Otherwise, your optimisation doesn't take into account when you have such files:
ar0000
ar0001
ar0002
etc.

Indeed, speeding up the search of a file in the VAT is really important if you have many files. I have tested PedroM with 1950 archived files. and the reset is slow.

Nevertheless, I think a binary search will be better since the VAT is always sorted (And the function is already in PedroM).

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...)

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.

Good

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

You really like combining conditional codes with dbra !!!!!!!!!!!!!!!!
I am not sure your code will be faster than a simple :

\search
 cmp.l (a0)+,d0
 addq.l #8,a0
 dbls   d2,\search
 bcs.s \False
 [...] Fix code

>Have you looked into cordic at all for trig functions?
No. Do you mean div by 2 or by 10 ?

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

the addq is faster faster

It doesn't change anything except for size. Though, using (a0)+ would have spared you the 2(a0) and 6(a0) addressing modes.

I believe PpHd's solution is fairly good, but it might be even more efficient to perform a dichotomic search (but, would the speed difference ever be noticeable?)

>>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

1. Multiply by 2^-i isn't quite easy with SMAP BCD format.
2. Searching for a long long is really faster than searching for a string.
3. I think a Ti Basic interpreter should keep a separate table for its variable for performance.
4. The speed difference will be noticeable: try to have more than 1900 files in a folder
5. Yes, I was wrong: It was a VAT searching routine for ti-92 (The vat entry is only 12 bytes).
6. I have a lot of things to do.
But I may introduce a binary search with long long cmp. (No word -long-word, even if I may tests it).

PpHd
: 1. Multiply by 2^-i isn't quite easy with SMAP BCD format.

You're right. Here's how I'd attack the problem:

x*2^-i=x*5ⁱ*10^-i. Multiplying by 10^-i is trivial. Remains x*5ⁱ to compute.

One possible algorithm: convert your mantissa to a binary long long, multiply with 5ⁱ, normalize (divide by 10 until it fits), convert back to decimal.

This might be optimizable by combining the multiplication with the normalization: rather than multiplying by 5ⁱ and dividing by 10^j, multiply with 5^i-j and divide by 2^j.