Commit several codebook handling fixes from Tremor-Neuros

git-svn-id: https://svn.xiph.org/branches/lowmem-branch/Tremor@5616 0101bb08-14d6-0310-b084-bc0e0c8e3800

2 files changed, 58 insertions, 17 deletions

diff --git a/codebook.c b/codebook.c
index 64389f3..ca124ee 100644
--- a/codebook.c
+++ b/codebook.c
@@ -47,7 +47,7 @@ static ogg_uint32_t decpack(long entry,long used_entry,long quantvals,
 
   case 1:
     if(maptype==1){
-      /* vals are already read into temporary colum vector here */
+      /* vals are already read into temporary column vector here */
       for(j=0;j<b->dim;j++){
 	ogg_uint32_t off=entry%quantvals;
 	entry/=quantvals;
@@ -98,6 +98,12 @@ static ogg_int32_t _float32_unpack(long val,int *point){
 /* choose the smallest supported node size that fits our decode table.
    Legal bytewidths are 1/1 1/2 2/2 2/4 4/4 */
 static int _determine_node_bytes(long used, int leafwidth){
+
+  /* special case small books to size 4 to avoid multiple special
+     cases in repack */
+  if(used<2)
+    return 4;
+
   if(leafwidth==3)leafwidth=4;
   if(_ilog(3*used-6)+1 <= leafwidth*4) 
     return leafwidth/2?leafwidth/2:1;
@@ -183,17 +189,23 @@ static int _make_decode_table(codebook *s,char *lengthlist,long quantvals,
 			      oggpack_buffer *opb,int maptype){
   int i;
   ogg_uint32_t *work;
-  if(s->dec_nodeb==4)
-    work=s->dec_table=_ogg_malloc((s->used_entries*2-2)*4);
-  else
-    work=alloca((s->used_entries*2-2)*sizeof(*work));
 
-  if(_make_words(lengthlist,s->entries,work,quantvals,s,opb,maptype))return 1;
-  if(s->dec_nodeb==4) return 0;
 
+  if(s->dec_nodeb==4){
+    s->dec_table=_ogg_malloc((s->used_entries*2+1)*sizeof(*work));
+    /* +1 (rather than -2) is to accommodate 0 and 1 sized books,
+       which are specialcased to nodeb==4 */
+    if(_make_words(lengthlist,s->entries,
+		   s->dec_table,quantvals,s,opb,maptype))return 1;
+    
+    return 0;
+  }
+
+  work=alloca((s->used_entries*2-2)*sizeof(*work));
+  if(_make_words(lengthlist,s->entries,work,quantvals,s,opb,maptype))return 1;
   s->dec_table=_ogg_malloc((s->used_entries*(s->dec_leafw+1)-2)*
 			   s->dec_nodeb);
-    
+  
   if(s->dec_leafw==1){
     switch(s->dec_nodeb){
     case 1:
@@ -391,7 +403,7 @@ int vorbis_book_unpack(oggpack_buffer *opb,codebook *s){
     break;
   default:
     /* EOF */
-    return(-1);
+    goto _eofout;
   }
 
 
diff --git a/floor1.c b/floor1.c
index 65959de..1530fe7 100644
--- a/floor1.c
+++ b/floor1.c
@@ -53,6 +53,37 @@ static int ilog(unsigned int v){
   return(ret);
 }
 
+static void mergesort(ogg_uint16_t *index,ogg_uint16_t *vals,ogg_uint16_t n){
+  ogg_uint16_t i,j;
+  ogg_uint16_t *temp,*A=index,*B=_ogg_alloc(0,n*sizeof(*B));
+
+  for(i=1;i<n;i<<=1){
+    for(j=0;j+i<n;){
+      int k1=j;
+      int mid=j+i;
+      int k2=mid;
+      int end=(j+i*2<n?j+i*2:n);
+      while(k1<mid && k2<end){
+	if(vals[A[k1]]<vals[A[k2]])
+	  B[j++]=A[k1++];
+	else
+	  B[j++]=A[k2++];
+      }
+      while(k1<mid) B[j++]=A[k1++];
+      while(k2<end) B[j++]=A[k2++];
+    }
+    for(;j<n;j++)B[j]=A[j];
+    temp=A;A=B;B=temp;
+  }
+ 
+  if(B==index){
+    for(j=0;j<n;j++)B[j]=A[j];
+    _ogg_free(A);
+  }else
+    _ogg_free(B);
+}
+
+
 static int icomp(const void *a,const void *b){
   return(**(ogg_uint16_t **)a-**(ogg_uint16_t **)b);
 }
@@ -60,7 +91,6 @@ static int icomp(const void *a,const void *b){
 vorbis_info_floor *floor1_info_unpack (vorbis_info *vi,oggpack_buffer *opb){
   codec_setup_info     *ci=(codec_setup_info *)vi->codec_setup;
   int j,k,count=0,maxclass=-1,rangebits;
-  ogg_uint16_t *sortpointer[VIF_POSIT+2];
   
   vorbis_info_floor1 *info=(vorbis_info_floor1 *)_ogg_calloc(1,sizeof(*info));
   /* read partitions */
@@ -79,8 +109,11 @@ vorbis_info_floor *floor1_info_unpack (vorbis_info *vi,oggpack_buffer *opb){
     info->class[j].class_dim=oggpack_read(opb,3)+1; /* 1 to 8 */
     info->class[j].class_subs=oggpack_read(opb,2); /* 0,1,2,3 bits */
     if(oggpack_eop(opb)<0) goto err_out;
-    if(info->class[j].class_subs)
+    if(info->class[j].class_subs){
       info->class[j].class_book=oggpack_read(opb,8);
+      if(info->class[j].class_book>=ci->books)goto err_out;
+    }else
+      info->class[j].class_book=0;
     if(info->class[j].class_book>=ci->books)goto err_out;
     for(k=0;k<(1<<info->class[j].class_subs);k++){
       info->class[j].class_subbook[k]=oggpack_read(opb,8)-1;
@@ -118,12 +151,8 @@ vorbis_info_floor *floor1_info_unpack (vorbis_info *vi,oggpack_buffer *opb){
   info->posts=count+2;
 
   /* also store a sorted position index */
-  for(j=0;j<info->posts;j++)sortpointer[j]=info->postlist+j;
-  qsort(sortpointer,info->posts,sizeof(*sortpointer),icomp);
-
-  /* points from sort order back to range number */
-  for(j=0;j<info->posts;j++)
-    info->forward_index[j]=sortpointer[j]-info->postlist;
+  for(j=0;j<info->posts;j++)info->forward_index[j]=j;
+  mergesort(info->forward_index,info->postlist,info->posts);
   
   /* discover our neighbors for decode where we don't use fit flags
      (that would push the neighbors outward) */