Complete first-cut rearrangement of bisection and initialization code to reduce stream seeks.

svn path=/trunk/vorbis/; revision=15928

2 files changed, 243 insertions, 214 deletions

diff --git a/include/vorbis/vorbisfile.h b/include/vorbis/vorbisfile.h
index e128fe88..7c6cbc4d 100644
--- a/include/vorbis/vorbisfile.h
+++ b/include/vorbis/vorbisfile.h
@@ -48,9 +48,12 @@ typedef struct {
  * ov_open() to avoid problems with incompatable crt.o version linking
  * issues. */
 
+#include <stdio.h>
 static int _ov_header_fseek_wrap(FILE *f,ogg_int64_t off,int whence){
   if(f==NULL)return(-1);
 
+  fprintf(stderr,"seek: %s %ld\n",(whence==SEEK_END?"END":(whence==SEEK_SET?"SET":"CUR")), (long)off);
+
 #ifdef __MINGW32__
   return fseeko64(f,off,whence);
 #elif defined (_WIN32)
diff --git a/lib/vorbisfile.c b/lib/vorbisfile.c
index 88a53fc8..5308696d 100644
--- a/lib/vorbisfile.c
+++ b/lib/vorbisfile.c
@@ -167,7 +167,7 @@ static ogg_int64_t _get_prev_page(OggVorbis_File *vf,ogg_page *og){
 
   /* In a fully compliant, non-multiplexed stream, we'll still be
      holding the last page.  In multiplexed (or noncompliant streams),
-     we may need to re-read the last page we saw */
+     we will probably have to re-read the last page we saw */
   if(og->header_len==0){
     ret=_seek_helper(vf,offset);
     if(ret)return(ret);
@@ -181,6 +181,59 @@ static ogg_int64_t _get_prev_page(OggVorbis_File *vf,ogg_page *og){
   return(offset);
 }
 
+/* performs the same search as _get_prev_page, but prefers pages of
+   the specified serial number. If a page of the specified serialno is
+   spotted during the seek-back-and-read-forward, it will return the
+   info of last page of the matching serial number instead of the very
+   last page.  If no page of the specified serialno is seen, it will
+   return the info of last page and alter *serialno.  */
+static ogg_int64_t _get_prev_page_serial(OggVorbis_File *vf,int *serialno, ogg_int64_t *granpos){
+  ogg_page og;
+  ogg_int64_t begin=vf->offset;
+  ogg_int64_t end=begin;
+  ogg_int64_t ret;
+
+  ogg_int64_t prefoffset=-1;
+  ogg_int64_t offset=-1;
+  ogg_int64_t ret_serialno;
+  ogg_int64_t ret_gran;
+
+  while(offset==-1){
+    begin-=CHUNKSIZE;
+    if(begin<0)
+      begin=0;
+
+    ret=_seek_helper(vf,begin);
+    if(ret)return(ret);
+
+    while(vf->offset<end){
+      ret=_get_next_page(vf,&og,end-vf->offset);
+      if(ret==OV_EREAD)return(OV_EREAD);
+      if(ret<0){
+	break;
+      }else{
+	ret_serialno=ogg_page_serialno(&og);
+	ret_gran=ogg_page_granulepos(&og);
+	offset=ret;
+
+	if(ret_serialno == *serialno){
+	  prefoffset=ret;
+	  *granpos=ret_gran;
+	}
+	
+      }
+    }
+  }
+
+  /* we're not interested in the page... just the serialno and granpos. */
+  if(prefoffset>=0)return(prefoffset);
+
+  *serialno = ret_serialno;
+  *granpos = ret_gran;
+  return(offset);
+
+}
+
 static void _add_serialno(ogg_page *og,long **serialno_list, int *n){
   long s = ogg_page_serialno(og);
   (*n)++;
@@ -195,9 +248,7 @@ static void _add_serialno(ogg_page *og,long **serialno_list, int *n){
 }
 
 /* returns nonzero if found */
-static int _lookup_serialno(ogg_page *og, long *serialno_list, int n){
-  long s = ogg_page_serialno(og);
-
+static int _lookup_serialno(long s, long *serialno_list, int n){
   if(serialno_list){
     while(n--){
       if(*serialno_list == s) return 1;
@@ -207,102 +258,15 @@ static int _lookup_serialno(ogg_page *og, long *serialno_list, int n){
   return 0;
 }
 
-/* start parsing pages at current offset, remembering all serial
-   numbers.  Stop logging at first non-bos page */
-static int _get_serialnos(OggVorbis_File *vf, long **s, int *n){
-  ogg_page og;
-
-  *s=NULL;
-  *n=0;
-
-  while(1){
-    ogg_int64_t llret=_get_next_page(vf,&og,CHUNKSIZE);
-    if(llret==OV_EOF)return(0);
-    if(llret<0)return(llret);
-    if(!ogg_page_bos(&og)) return 0;
-
-    /* look for duplicate serialnos; add this one if unique */
-    if(_lookup_serialno(&og,*s,*n)){
-      if(*s)_ogg_free(*s);
-      *s=0;
-      *n=0;
-      return(OV_EBADHEADER);
-    }
-
-    _add_serialno(&og,s,n);
-  }
-}
-
-/* finds each bitstream link one at a time using a bisection search
-   (has to begin by knowing the offset of the lb's initial page).
-   Recurses for each link so it can alloc the link storage after
-   finding them all, then unroll and fill the cache at the same time */
-static int _bisect_forward_serialno(OggVorbis_File *vf,
-				    ogg_int64_t begin,
-				    ogg_int64_t searched,
-				    ogg_int64_t end,
-				    long *currentno_list,
-				    int  currentnos,
-				    long m){
-  ogg_int64_t endsearched=end;
-  ogg_int64_t next=end;
-  ogg_page og;
-  ogg_int64_t ret;
-  
-  /* the below guards against garbage seperating the last and
-     first pages of two links. */
-  while(searched<endsearched){
-    ogg_int64_t bisect;
-    
-    if(endsearched-searched<CHUNKSIZE){
-      bisect=searched;
-    }else{
-      bisect=(searched+endsearched)/2;
-    }
-    
-    ret=_seek_helper(vf,bisect);
-    if(ret)return(ret);
-
-    ret=_get_next_page(vf,&og,-1);
-    if(ret==OV_EREAD)return(OV_EREAD);
-    if(ret<0 || !_lookup_serialno(&og,currentno_list,currentnos)){
-      endsearched=bisect;
-      if(ret>=0)next=ret;
-    }else{
-      searched=ret+og.header_len+og.body_len;
-    }
-  }
-
-  {
-    long *next_serialno_list=NULL;
-    int next_serialnos=0;
-
-    ret=_seek_helper(vf,next);
-    if(ret)return(ret);
-    ret=_get_serialnos(vf,&next_serialno_list,&next_serialnos);
-    if(ret)return(ret);
-    
-    if(searched>=end || next_serialnos==0){
-      vf->links=m+1;
-      if(vf->offsets)_ogg_free(vf->offsets);
-      vf->offsets=_ogg_malloc((vf->links+1)*sizeof(*vf->offsets));
-      vf->offsets[m+1]=searched;
-    }else{
-      ret=_bisect_forward_serialno(vf,next,vf->offset,
-				   end,next_serialno_list,next_serialnos,m+1);
-      if(ret)return(ret);
-    }
-    
-    if(next_serialno_list)_ogg_free(next_serialno_list);
-  }
-  vf->offsets[m]=begin;
-  return(0);
+static int _lookup_page_serialno(ogg_page *og, long *serialno_list, int n){
+  long s = ogg_page_serialno(og);
+  return _lookup_serialno(s,serialno_list,n);
 }
 
 /* uses the local ogg_stream storage in vf; this is important for
    non-streaming input sources */
 static int _fetch_headers(OggVorbis_File *vf,vorbis_info *vi,vorbis_comment *vc,
-			  long *serialno, long **serialno_list, int *serialno_n,
+			  long **serialno_list, int *serialno_n,
                           ogg_page *og_ptr){
   ogg_page og;
   ogg_packet op;
@@ -318,13 +282,14 @@ static int _fetch_headers(OggVorbis_File *vf,vorbis_info *vi,vorbis_comment *vc,
 
   vorbis_info_init(vi);
   vorbis_comment_init(vc);
+  vf->ready_state=OPENED;
 
   /* extract the serialnos of all BOS pages + the first set of vorbis
      headers we see in the link */
 
   while(ogg_page_bos(og_ptr)){
     if(serialno_list){
-      if(_lookup_serialno(og_ptr,*serialno_list,*serialno_n)){
+      if(_lookup_page_serialno(og_ptr,*serialno_list,*serialno_n)){
         /* a dupe serialnumber in an initial header packet set == invalid stream */
         if(*serialno_list)_ogg_free(*serialno_list);
         *serialno_list=0;
@@ -345,7 +310,6 @@ static int _fetch_headers(OggVorbis_File *vf,vorbis_info *vi,vorbis_comment *vc,
       if(ogg_stream_packetout(&vf->os,&op) > 0 &&
          vorbis_synthesis_idheader(&op)){
         /* vorbis header; continue setup */
-        if(serialno)*serialno=vf->os.serialno;
         vf->ready_state=STREAMSET;
         if((ret=vorbis_synthesis_headerin(vi,vc,&op))){
           ret=OV_EBADHEADER;
@@ -437,132 +401,183 @@ static int _fetch_headers(OggVorbis_File *vf,vorbis_info *vi,vorbis_comment *vc,
   return ret;
 }
 
-/* last step of the OggVorbis_File initialization; get all the
-   vorbis_info structs and PCM positions.  Only called by the seekable
-   initialization (local stream storage is hacked slightly; pay
-   attention to how that's done) */
+/* Starting from current cursor position, get initial PCM offset of
+   next page.  Consumes the page in the process without decoding
+   audio, however this is only called during stream parsing upon
+   seekable open. */
+static ogg_int64_t _initial_pcmoffset(OggVorbis_File *vf, vorbis_info *vi){
+  ogg_page    og;
+  ogg_int64_t accumulated=0;
+  long        lastblock=-1;
+  int         result;
+  int         serialno = vf->os.serialno;
 
-/* this is void and does not propogate errors up because we want to be
-   able to open and use damaged bitstreams as well as we can.  Just
-   watch out for missing information for links in the OggVorbis_File
-   struct */
-static void _prefetch_all_headers(OggVorbis_File *vf, ogg_int64_t dataoffset){
-  ogg_page og;
-  int i;
-  ogg_int64_t ret;
+  while(1){
+    ogg_packet op;
+    if(_get_next_page(vf,&og,-1)<0)
+      break; /* should not be possible unless the file is truncated/mangled */
+       
+    if(ogg_page_bos(&og)) break;
+    if(ogg_page_serialno(&og)!=serialno) continue;
+	
+    /* count blocksizes of all frames in the page */
+    ogg_stream_pagein(&vf->os,&og);
+    while((result=ogg_stream_packetout(&vf->os,&op))){
+      if(result>0){ /* ignore holes */
+	long thisblock=vorbis_packet_blocksize(vi,&op);
+	if(lastblock!=-1)
+	  accumulated+=(lastblock+thisblock)>>2;
+	lastblock=thisblock;
+      }
+    }
 
-  if(vf->serialnos)_ogg_free(vf->serialnos);
-  if(vf->dataoffsets)_ogg_free(vf->dataoffsets);
+    if(ogg_page_granulepos(&og)!=-1){
+      /* pcm offset of last packet on the first audio page */
+      accumulated= ogg_page_granulepos(&og)-accumulated;
+      break;
+    }
+  }
 
-  vf->vi=_ogg_realloc(vf->vi,vf->links*sizeof(*vf->vi));
-  vf->vc=_ogg_realloc(vf->vc,vf->links*sizeof(*vf->vc));
-  vf->serialnos=_ogg_malloc(vf->links*sizeof(*vf->serialnos));
-  vf->dataoffsets=_ogg_malloc(vf->links*sizeof(*vf->dataoffsets));
-  vf->pcmlengths=_ogg_malloc(vf->links*2*sizeof(*vf->pcmlengths));
+  /* less than zero?  This is a stream with samples trimmed off
+     the beginning, a normal occurrence; set the offset to zero */
+  if(accumulated<0)accumulated=0;
   
-  for(i=0;i<vf->links;i++){
-    if(i==0){
-      /* we already grabbed the initial header earlier.  Just set the offset */
-      vf->serialnos[i]=vf->current_serialno;
-      vf->dataoffsets[i]=dataoffset;
-      ret=_seek_helper(vf,dataoffset);
-      if(ret)
-	vf->dataoffsets[i]=-1;
-
-    }else{
+  return accumulated;
+}
 
-      /* seek to the location of the initial header */
+/* finds each bitstream link one at a time using a bisection search
+   (has to begin by knowing the offset of the lb's initial page).
+   Recurses for each link so it can alloc the link storage after
+   finding them all, then unroll and fill the cache at the same time */
+static int _bisect_forward_serialno(OggVorbis_File *vf,
+				    ogg_int64_t begin,
+				    ogg_int64_t searched,
+				    ogg_int64_t end,
+				    ogg_int64_t endgran,
+				    int endserial,
+				    long *currentno_list,
+				    int  currentnos,
+				    long m){
+  ogg_int64_t pcmoffset;
+  ogg_int64_t dataoffset=searched;
+  ogg_int64_t endsearched=end;
+  ogg_int64_t next=end;
+  ogg_int64_t searchgran=-1;
+  ogg_page og;
+  ogg_int64_t ret,last;
+  int serialno = vf->os.serialno;
 
-      ret=_seek_helper(vf,vf->offsets[i]);
-      if(ret){
-	vf->dataoffsets[i]=-1;
-      }else{
-	if(_fetch_headers(vf,vf->vi+i,vf->vc+i,vf->serialnos+i,NULL,NULL,NULL)<0){
-	  vf->dataoffsets[i]=-1;
-	}else{
-	  vf->dataoffsets[i]=vf->offset;
-	}
-      }
-    }
+  /* invariants: 
+     we have the headers and serialnos for the link beginning at 'begin'
+     we have the offset and granpos of the last page in the file (potentially 
+       not a page we care about)
+  */
 
-    /* fetch beginning PCM offset */
+  /* Is the last page in our list of current serialnumbers? */
+  if(_lookup_serialno(endserial,currentno_list,currentnos)){
 
-    if(vf->dataoffsets[i]!=-1){
-      ogg_int64_t accumulated=0;
-      long        lastblock=-1;
-      int         result;
+    /* last page is in the starting serialno list, so we've bisected
+       down to (or just started with) a single link.  Now we need to
+       find the last vorbis page belonging to the first vorbis stream
+       for this link. */
+    
+    while(endserial != serialno){
+      endserial = serialno;
+      vf->offset=_get_prev_page_serial(vf,&endserial,&endgran);
+    }
 
-      ogg_stream_reset_serialno(&vf->os,vf->serialnos[i]);
+    vf->links=m+1;
+    if(vf->offsets)_ogg_free(vf->offsets);
+    if(vf->serialnos)_ogg_free(vf->serialnos);
+    if(vf->dataoffsets)_ogg_free(vf->dataoffsets);
 
-      while(1){
-	ogg_packet op;
+    vf->offsets=_ogg_malloc((vf->links+1)*sizeof(*vf->offsets));
+    vf->vi=_ogg_realloc(vf->vi,vf->links*sizeof(*vf->vi));
+    vf->vc=_ogg_realloc(vf->vc,vf->links*sizeof(*vf->vc));
+    vf->serialnos=_ogg_malloc(vf->links*sizeof(*vf->serialnos));
+    vf->dataoffsets=_ogg_malloc(vf->links*sizeof(*vf->dataoffsets));
+    vf->pcmlengths=_ogg_malloc(vf->links*2*sizeof(*vf->pcmlengths));
 
-	ret=_get_next_page(vf,&og,-1);
-	if(ret<0)
-	  /* this should not be possible unless the file is
-             truncated/mangled */
-	  break;
-       
-	if(ogg_page_bos(&og)) break;
+    vf->offsets[m+1]=end;
+    vf->offsets[m]=begin;
+    vf->pcmlengths[m*2+1]=endgran; 
 
-	if(ogg_page_serialno(&og)!=vf->serialnos[i])
-	  continue;
-	
-	/* count blocksizes of all frames in the page */
-	ogg_stream_pagein(&vf->os,&og);
-	while((result=ogg_stream_packetout(&vf->os,&op))){
-	  if(result>0){ /* ignore holes */
-	    long thisblock=vorbis_packet_blocksize(vf->vi+i,&op);
-	    if(lastblock!=-1)
-	      accumulated+=(lastblock+thisblock)>>2;
-	    lastblock=thisblock;
-	  }
-	}
+  }else{
+    
+    long *next_serialno_list=NULL;
+    int next_serialnos=0;
+    vorbis_info vi;
+    vorbis_comment vc;
 
-	if(ogg_page_granulepos(&og)!=-1){
-	  /* pcm offset of last packet on the first audio page */
-	  accumulated= ogg_page_granulepos(&og)-accumulated;
-	  break;
-	}
+    /* the below guards against garbage seperating the last and
+       first pages of two links. */
+    while(searched<endsearched){
+      ogg_int64_t bisect;
+      
+      if(endsearched-searched<CHUNKSIZE){
+	bisect=searched;
+      }else{
+	bisect=(searched+endsearched)/2;
       }
+      
+      ret=_seek_helper(vf,bisect);
+      if(ret)return(ret);
 
-      /* less than zero?  This is a stream with samples trimmed off
-         the beginning, a normal occurrence; set the offset to zero */
-      if(accumulated<0)accumulated=0;
-
-      vf->pcmlengths[i*2]=accumulated;
+      last=_get_next_page(vf,&og,-1);
+      if(last==OV_EREAD)return(OV_EREAD);
+      if(last<0 || !_lookup_page_serialno(&og,currentno_list,currentnos)){
+	endsearched=bisect;
+	if(last>=0)next=last;
+      }else{
+	searched=last+og.header_len+og.body_len;
+      }
     }
 
-    /* get the PCM length of this link. To do this,
-       get the last page of the stream */
+    /* Bisection point found */
+
+    /* for the time being, fetch end PCM offset the simple way */
     {
-      ogg_int64_t end=vf->offsets[i+1];
-      ret=_seek_helper(vf,end);
-      if(ret){
-	/* this should not be possible */
-	vorbis_info_clear(vf->vi+i);
-	vorbis_comment_clear(vf->vc+i);
-      }else{
-	
-	while(1){
-	  ret=_get_prev_page(vf,&og);
-	  if(ret<0){
-	    /* this should not be possible */
-	    vorbis_info_clear(vf->vi+i);
-	    vorbis_comment_clear(vf->vc+i);
-	    break;
-	  }
-	  if(ogg_page_serialno(&og)==vf->serialnos[i]){
-	    if(ogg_page_granulepos(&og)!=-1){
-	      vf->pcmlengths[i*2+1]=ogg_page_granulepos(&og)-vf->pcmlengths[i*2];
-	      break;
-	    }
-	  }
-	  vf->offset=ret;
-	}
+      int testserial = serialno+1;
+      vf->offset = next;
+      while(testserial != serialno){
+	testserial = serialno;
+	vf->offset=_get_prev_page_serial(vf,&testserial,&searchgran);
       }
     }
+
+    if(vf->offset!=next){
+      ret=_seek_helper(vf,next);
+      if(ret)return(ret);
+    }
+
+    ret=_fetch_headers(vf,&vi,&vc,&next_serialno_list,&next_serialnos,NULL);
+    if(ret)return(ret);
+    serialno = vf->os.serialno;
+    dataoffset = vf->offset;
+
+    /* this will consume a page, however the next bistection always
+       starts with a raw seek */
+    pcmoffset = _initial_pcmoffset(vf,&vi);
+
+    ret=_bisect_forward_serialno(vf,next,vf->offset,end,endgran,endserial,
+				 next_serialno_list,next_serialnos,m+1);
+    if(ret)return(ret);
+    
+    if(next_serialno_list)_ogg_free(next_serialno_list);
+    
+    vf->offsets[m+1]=next;
+    vf->serialnos[m+1]=serialno;
+    vf->dataoffsets[m+1]=dataoffset;
+
+    vf->vi[m+1]=vi;
+    vf->vc[m+1]=vc;
+
+    vf->pcmlengths[m*2+1]=searchgran;
+    vf->pcmlengths[m*2+2]=pcmoffset;
+    vf->pcmlengths[m*2+3]-=pcmoffset;
+
   }
+  return(0);
 }
 
 static int _make_decode_ready(OggVorbis_File *vf){
@@ -583,11 +598,16 @@ static int _make_decode_ready(OggVorbis_File *vf){
 }
 
 static int _open_seekable2(OggVorbis_File *vf){
-  ogg_int64_t dataoffset=vf->dataoffsets[0],end;
-  ogg_page og;
+  ogg_int64_t dataoffset=vf->dataoffsets[0],end,endgran=-1;
+  int endserial=vf->os.serialno;
+  int serialno=vf->os.serialno;
 
   /* we're partially open and have a first link header state in
      storage in vf */
+
+  /* fetch initial PCM offset */
+  ogg_int64_t pcmoffset = _initial_pcmoffset(vf,vf->vi);
+
   /* we can seek, so set out learning all about this file */
   if(vf->callbacks.seek_func && vf->callbacks.tell_func){
     (vf->callbacks.seek_func)(vf->datasource,0,SEEK_END);
@@ -599,16 +619,22 @@ static int _open_seekable2(OggVorbis_File *vf){
   /* If seek_func is implemented, tell_func must also be implemented */
   if(vf->end==-1) return(OV_EINVAL);
 
-  /* We get the offset for the last page of the physical bitstream.
-     Most OggVorbis files will contain a single logical bitstream */
-  end=_get_prev_page(vf,&og);
+  /* Get the offset of the last page of the physical bitstream, or, if
+     we're lucky the last vorbis page of this link as most OggVorbis
+     files will contain a single logical bitstream */
+  end=_get_prev_page_serial(vf,&endserial,&endgran);
   if(end<0)return(end);
 
   /* now determine bitstream structure recursively */
-  if(_bisect_forward_serialno(vf,0,0,end+1,vf->serialnos+2,vf->serialnos[1],0)<0)return(OV_EREAD);  
+  if(_bisect_forward_serialno(vf,0,dataoffset,end+1,endgran,endserial,
+			      vf->serialnos+2,vf->serialnos[1],0)<0)return(OV_EREAD);  
+
+  vf->offsets[0]=0;
+  vf->serialnos[0]=serialno;
+  vf->dataoffsets[0]=dataoffset;
+  vf->pcmlengths[0]=pcmoffset;
+  vf->pcmlengths[1]-=pcmoffset;
 
-  /* the initial header memory is referenced by vf after; don't free it */
-  _prefetch_all_headers(vf,dataoffset);
   return(ov_raw_seek(vf,dataoffset));
 }
 
@@ -802,8 +828,9 @@ static int _fetch_and_process_packet(OggVorbis_File *vf,
 	  /* we're streaming */
 	  /* fetch the three header packets, build the info struct */
 	  
-	  int ret=_fetch_headers(vf,vf->vi,vf->vc,&vf->current_serialno,NULL,NULL,&og);
+	  int ret=_fetch_headers(vf,vf->vi,vf->vc,NULL,NULL,&og);
 	  if(ret)return(ret);
+	  vf->current_serialno=vf->os.serialno;
 	  vf->current_link++;
 	  link=0;
 	}
@@ -865,9 +892,7 @@ static int _ov_open1(void *f,OggVorbis_File *vf,char *initial,
 
   /* Fetch all BOS pages, store the vorbis header and all seen serial
      numbers, load subsequent vorbis setup headers */
-  if((ret=_fetch_headers(vf,vf->vi,vf->vc,&vf->current_serialno,
-                         &serialno_list,&serialno_list_size,
-                         NULL))<0){
+  if((ret=_fetch_headers(vf,vf->vi,vf->vc,&serialno_list,&serialno_list_size,NULL))<0){
     vf->datasource=NULL;
     ov_clear(vf);
   }else{
@@ -883,6 +908,7 @@ static int _ov_open1(void *f,OggVorbis_File *vf,char *initial,
     vf->dataoffsets=_ogg_calloc(1,sizeof(*vf->dataoffsets));
     vf->offsets[0]=0;
     vf->dataoffsets[0]=vf->offset;
+    vf->current_serialno=vf->os.serialno;
 
     vf->ready_state=PARTOPEN;
   }