sharedbook.c

在x86平台上运行不可信任代码的sandbox。

  c->valuelist=_book_unquantize(s,n,sortindex);
  c->dec_index=_ogg_malloc(n*sizeof(*c->dec_index));

  for(n=0,i=0;i<s->entries;i++)
    if(s->lengthlist[i]>0)
      c->dec_index[sortindex[n++]]=i;
  
  c->dec_codelengths=_ogg_malloc(n*sizeof(*c->dec_codelengths));
  for(n=0,i=0;i<s->entries;i++)
    if(s->lengthlist[i]>0)
      c->dec_codelengths[sortindex[n++]]=s->lengthlist[i];

  c->dec_firsttablen=_ilog(c->used_entries)-4; /* this is magic */
  if(c->dec_firsttablen<5)c->dec_firsttablen=5;
  if(c->dec_firsttablen>8)c->dec_firsttablen=8;

  tabn=1<<c->dec_firsttablen;
  c->dec_firsttable=_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
  c->dec_maxlength=0;

  for(i=0;i<n;i++){
    if(c->dec_maxlength<c->dec_codelengths[i])
      c->dec_maxlength=c->dec_codelengths[i];
    if(c->dec_codelengths[i]<=c->dec_firsttablen){
      ogg_uint32_t orig=bitreverse(c->codelist[i]);
      for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++)
	c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1;
    }
  }

  /* now fill in 'unused' entries in the firsttable with hi/lo search
     hints for the non-direct-hits */
  {
    ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen);
    long lo=0,hi=0;

    for(i=0;i<tabn;i++){
      ogg_uint32_t word=i<<(32-c->dec_firsttablen);
      if(c->dec_firsttable[bitreverse(word)]==0){
	while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
	while(    hi<n && word>=(c->codelist[hi]&mask))hi++;
	
	/* we only actually have 15 bits per hint to play with here.
           In order to overflow gracefully (nothing breaks, efficiency
           just drops), encode as the difference from the extremes. */
	{
	  unsigned long loval=lo;
	  unsigned long hival=n-hi;

	  if(loval>0x7fff)loval=0x7fff;
	  if(hival>0x7fff)hival=0x7fff;
	  c->dec_firsttable[bitreverse(word)]=
	    0x80000000UL | (loval<<15) | hival;
	}
      }
    }
  }
  

  return(0);
 err_out:
  vorbis_book_clear(c);
  return(-1);
}

static float _dist(int el,float *ref, float *b,int step){
  int i;
  float acc=0.f;
  for(i=0;i<el;i++){
    float val=(ref[i]-b[i*step]);
    acc+=val*val;
  }
  return(acc);
}

int _best(codebook *book, float *a, int step){
  encode_aux_threshmatch *tt=book->c->thresh_tree;

#if 0
  encode_aux_nearestmatch *nt=book->c->nearest_tree;
  encode_aux_pigeonhole *pt=book->c->pigeon_tree;
#endif
  int dim=book->dim;
  int k,o;
  /*int savebest=-1;
    float saverr;*/

  /* do we have a threshhold encode hint? */
  if(tt){
    int index=0,i;
    /* find the quant val of each scalar */
    for(k=0,o=step*(dim-1);k<dim;k++,o-=step){

      i=tt->threshvals>>1;
      if(a[o]<tt->quantthresh[i]){

	for(;i>0;i--)
	  if(a[o]>=tt->quantthresh[i-1])
	    break;
	
      }else{

	for(i++;i<tt->threshvals-1;i++)
	  if(a[o]<tt->quantthresh[i])break;

      }

      index=(index*tt->quantvals)+tt->quantmap[i];
    }
    /* regular lattices are easy :-) */
    if(book->c->lengthlist[index]>0) /* is this unused?  If so, we'll
					use a decision tree after all
					and fall through*/
      return(index);
  }

#if 0
  /* do we have a pigeonhole encode hint? */
  if(pt){
    const static_codebook *c=book->c;
    int i,besti=-1;
    float best=0.f;
    int entry=0;

    /* dealing with sequentialness is a pain in the ass */
    if(c->q_sequencep){
      int pv;
      long mul=1;
      float qlast=0;
      for(k=0,o=0;k<dim;k++,o+=step){
	pv=(int)((a[o]-qlast-pt->min)/pt->del);
	if(pv<0 || pv>=pt->mapentries)break;
	entry+=pt->pigeonmap[pv]*mul;
	mul*=pt->quantvals;
	qlast+=pv*pt->del+pt->min;
      }
    }else{
      for(k=0,o=step*(dim-1);k<dim;k++,o-=step){
	int pv=(int)((a[o]-pt->min)/pt->del);
	if(pv<0 || pv>=pt->mapentries)break;
	entry=entry*pt->quantvals+pt->pigeonmap[pv];
      }
    }

    /* must be within the pigeonholable range; if we quant outside (or
       in an entry that we define no list for), brute force it */
    if(k==dim && pt->fitlength[entry]){
      /* search the abbreviated list */
      long *list=pt->fitlist+pt->fitmap[entry];
      for(i=0;i<pt->fitlength[entry];i++){
	float this=_dist(dim,book->valuelist+list[i]*dim,a,step);
	if(besti==-1 || this<best){
	  best=this;
	  besti=list[i];
	}
      }

      return(besti); 
    }
  }

  if(nt){
    /* optimized using the decision tree */
    while(1){
      float c=0.f;
      float *p=book->valuelist+nt->p[ptr];
      float *q=book->valuelist+nt->q[ptr];
      
      for(k=0,o=0;k<dim;k++,o+=step)
	c+=(p[k]-q[k])*(a[o]-(p[k]+q[k])*.5);
      
      if(c>0.f) /* in A */
	ptr= -nt->ptr0[ptr];
      else     /* in B */
	ptr= -nt->ptr1[ptr];
      if(ptr<=0)break;
    }
    return(-ptr);
  }
#endif 

  /* brute force it! */
  {
    const static_codebook *c=book->c;
    int i,besti=-1;
    float best=0.f;
    float *e=book->valuelist;
    for(i=0;i<book->entries;i++){
      if(c->lengthlist[i]>0){
	float this=_dist(dim,e,a,step);
	if(besti==-1 || this<best){
	  best=this;
	  besti=i;
	}
      }
      e+=dim;
    }

    /*if(savebest!=-1 && savebest!=besti){
      fprintf(stderr,"brute force/pigeonhole disagreement:\n"
	      "original:");
      for(i=0;i<dim*step;i+=step)fprintf(stderr,"%g,",a[i]);
      fprintf(stderr,"\n"
	      "pigeonhole (entry %d, err %g):",savebest,saverr);
      for(i=0;i<dim;i++)fprintf(stderr,"%g,",
				(book->valuelist+savebest*dim)[i]);
      fprintf(stderr,"\n"
	      "bruteforce (entry %d, err %g):",besti,best);
      for(i=0;i<dim;i++)fprintf(stderr,"%g,",
				(book->valuelist+besti*dim)[i]);
      fprintf(stderr,"\n");
      }*/
    return(besti);
  }
}

long vorbis_book_codeword(codebook *book,int entry){
  if(book->c) /* only use with encode; decode optimizations are
                 allowed to break this */
    return book->codelist[entry];
  return -1;
}

long vorbis_book_codelen(codebook *book,int entry){
  if(book->c) /* only use with encode; decode optimizations are
                 allowed to break this */
    return book->c->lengthlist[entry];
  return -1;
}

#ifdef _V_SELFTEST

/* Unit tests of the dequantizer; this stuff will be OK
   cross-platform, I simply want to be sure that special mapping cases
   actually work properly; a bug could go unnoticed for a while */

#include <stdio.h>

/* cases:

   no mapping
   full, explicit mapping
   algorithmic mapping

   nonsequential
   sequential
*/

static long full_quantlist1[]={0,1,2,3,    4,5,6,7, 8,3,6,1};
static long partial_quantlist1[]={0,7,2};

/* no mapping */
static_codebook test1={
  4,16,
  NULL,
  0,
  0,0,0,0,
  NULL,
  NULL,NULL
};
static float *test1_result=NULL;
  
/* linear, full mapping, nonsequential */
static_codebook test2={
  4,3,
  NULL,
  2,
  -533200896,1611661312,4,0,
  full_quantlist1,
  NULL,NULL
};
static float test2_result[]={-3,-2,-1,0, 1,2,3,4, 5,0,3,-2};

/* linear, full mapping, sequential */
static_codebook test3={
  4,3,
  NULL,
  2,
  -533200896,1611661312,4,1,
  full_quantlist1,
  NULL,NULL
};
static float test3_result[]={-3,-5,-6,-6, 1,3,6,10, 5,5,8,6};

/* linear, algorithmic mapping, nonsequential */
static_codebook test4={
  3,27,
  NULL,
  1,
  -533200896,1611661312,4,0,
  partial_quantlist1,
  NULL,NULL
};
static float test4_result[]={-3,-3,-3, 4,-3,-3, -1,-3,-3,
			      -3, 4,-3, 4, 4,-3, -1, 4,-3,
			      -3,-1,-3, 4,-1,-3, -1,-1,-3, 
			      -3,-3, 4, 4,-3, 4, -1,-3, 4,
			      -3, 4, 4, 4, 4, 4, -1, 4, 4,
			      -3,-1, 4, 4,-1, 4, -1,-1, 4,
			      -3,-3,-1, 4,-3,-1, -1,-3,-1,
			      -3, 4,-1, 4, 4,-1, -1, 4,-1,
			      -3,-1,-1, 4,-1,-1, -1,-1,-1};

/* linear, algorithmic mapping, sequential */
static_codebook test5={
  3,27,
  NULL,
  1,
  -533200896,1611661312,4,1,
  partial_quantlist1,
  NULL,NULL
};
static float test5_result[]={-3,-6,-9, 4, 1,-2, -1,-4,-7,
			      -3, 1,-2, 4, 8, 5, -1, 3, 0,
			      -3,-4,-7, 4, 3, 0, -1,-2,-5, 
			      -3,-6,-2, 4, 1, 5, -1,-4, 0,
			      -3, 1, 5, 4, 8,12, -1, 3, 7,
			      -3,-4, 0, 4, 3, 7, -1,-2, 2,
			      -3,-6,-7, 4, 1, 0, -1,-4,-5,
			      -3, 1, 0, 4, 8, 7, -1, 3, 2,
			      -3,-4,-5, 4, 3, 2, -1,-2,-3};

void run_test(static_codebook *b,float *comp){
  float *out=_book_unquantize(b,b->entries,NULL);
  int i;

  if(comp){
    if(!out){
      fprintf(stderr,"_book_unquantize incorrectly returned NULL\n");
      exit(1);
    }

    for(i=0;i<b->entries*b->dim;i++)
      if(fabs(out[i]-comp[i])>.0001){
	fprintf(stderr,"disagreement in unquantized and reference data:\n"
		"position %d, %g != %g\n",i,out[i],comp[i]);
	exit(1);
      }

  }else{
    if(out){
      fprintf(stderr,"_book_unquantize returned a value array: \n"
	      " correct result should have been NULL\n");
      exit(1);
    }
  }
}

int main(){
  /* run the nine dequant tests, and compare to the hand-rolled results */
  fprintf(stderr,"Dequant test 1... ");
  run_test(&test1,test1_result);
  fprintf(stderr,"OK\nDequant test 2... ");
  run_test(&test2,test2_result);
  fprintf(stderr,"OK\nDequant test 3... ");
  run_test(&test3,test3_result);
  fprintf(stderr,"OK\nDequant test 4... ");
  run_test(&test4,test4_result);
  fprintf(stderr,"OK\nDequant test 5... ");
  run_test(&test5,test5_result);
  fprintf(stderr,"OK\n\n");
  
  return(0);
}

#endif