[NUT-devel] Info packets in NUT stream (spec bugs?)

[Michael Niedermayer]

Hi

On Tue, Nov 21, 2006 at 10:35:57PM +0100, Michael Niedermayer wrote:
[...]
> > > > It is always possible via linear search. If the demuxer SHOULD NOT
> > > > search for them then we should not go out of our way to make it easy
> > > > to search... Just my 2¢...
> > > 
> > > well there really are 2 cases IMHO
> > > A. midstream info packets are not allowed in normal nut files
> > > B. midstream info packets are allowed in normal nut files
> > > 
> > > for A i agree that the pointers and repeating shouldnt be required, there may
> > > be other reasons though why repeating the info makes sense ...
> > > 
> > > for B i dont agree, simply because if info is there, then there are cases
> > > where the user will want to have that info, think of some capture of odeds
> > > radio stream, its not unlikely to think that the user would want to seek to
> > > a specific song (she knows the song title but not the time to seek to)
> > 
> > Arrg, this is what I was saying way back about info streams and I got
> > flamed to death. Anyway such file has no index already, so it's not
> > meant to be searchable by index, and searching by chapter _name_ does
> > not work with binary search so linear search is the natural
> > requirement anyway.
> 
> it is possible to extend info packets so that O(log n) search for
> names can be done ill explain how (and no iam not saying i actually propose
> doing that, its just a random thought)
> 1. add a hash table to every info packet which contains pointers to info
>    packets for all names in the X previous info packets
> 2. X is the largst power of 2 which divides n which is the number of the
>    current info packet, (n=5 -> X=1, n=6 -> X=2, n=8 -> X=8)
> 3. add a pointer to the Xth previous info packet

another idea, if we choose Y=sqrt( number of info packets )
and then duplicate the last Y info packets in every Yth info packet
and give the small info packets a pointer to the last and the large ones
a pointer to the last large one, then it should look like:
1 2 3 1234 5 6 7 5678 9 A B 9ABC D E 

and needs O(n) space (actually exactly 2*n) and O(sqrt(n)) seeks for
finding a info packet

the same can be done with the xth root, O(n^(1/x)) time and x*n overhead

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

In the past you could go to a library and read, borrow or copy any book
Today you'd get arrested for mere telling someone where the library is