misc/libtremor/tremor/sharedbook.c
author nemo
Mon, 25 Feb 2013 12:29:39 -0500
branchicegun
changeset 8574 684169401a2f
parent 7859 519d5bc91dd3
permissions -rw-r--r--
More fiddling w/ sliding
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
7859
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
     1
/********************************************************************
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
     2
 *                                                                  *
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
     3
 * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
     4
 *                                                                  *
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
     5
 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
     6
 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
     7
 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
     8
 *                                                                  *
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
     9
 * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2002    *
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    10
 * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    11
 *                                                                  *
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    12
 ********************************************************************
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    13
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    14
 function: basic shared codebook operations
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    15
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    16
 ********************************************************************/
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    17
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    18
#include <stdlib.h>
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    19
#include <math.h>
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    20
#include <string.h>
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    21
#include "ogg.h"
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    22
#include "misc.h"
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    23
#include "ivorbiscodec.h"
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    24
#include "codebook.h"
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    25
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    26
/**** pack/unpack helpers ******************************************/
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    27
int _ilog(unsigned int v){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    28
  int ret=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    29
  while(v){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    30
    ret++;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    31
    v>>=1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    32
  }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    33
  return(ret);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    34
}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    35
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    36
/* 32 bit float (not IEEE; nonnormalized mantissa +
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    37
   biased exponent) : neeeeeee eeemmmmm mmmmmmmm mmmmmmmm 
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    38
   Why not IEEE?  It's just not that important here. */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    39
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    40
#define VQ_FEXP 10
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    41
#define VQ_FMAN 21
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    42
#define VQ_FEXP_BIAS 768 /* bias toward values smaller than 1. */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    43
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    44
static ogg_int32_t _float32_unpack(long val,int *point){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    45
  long   mant=val&0x1fffff;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    46
  int    sign=val&0x80000000;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    47
  long   exp =(val&0x7fe00000L)>>VQ_FMAN;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    48
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    49
  exp-=(VQ_FMAN-1)+VQ_FEXP_BIAS;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    50
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    51
  if(mant){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    52
    while(!(mant&0x40000000)){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    53
      mant<<=1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    54
      exp-=1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    55
    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    56
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    57
    if(sign)mant= -mant;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    58
  }else{
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    59
    sign=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    60
    exp=-9999;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    61
  }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    62
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    63
  *point=exp;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    64
  return mant;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    65
}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    66
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    67
/* given a list of word lengths, generate a list of codewords.  Works
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    68
   for length ordered or unordered, always assigns the lowest valued
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    69
   codewords first.  Extended to handle unused entries (length 0) */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    70
ogg_uint32_t *_make_words(long *l,long n,long sparsecount){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    71
  long i,j,count=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    72
  ogg_uint32_t marker[33];
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    73
  ogg_uint32_t *r=(ogg_uint32_t *)_ogg_malloc((sparsecount?sparsecount:n)*sizeof(*r));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    74
  memset(marker,0,sizeof(marker));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    75
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    76
  for(i=0;i<n;i++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    77
    long length=l[i];
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    78
    if(length>0){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    79
      ogg_uint32_t entry=marker[length];
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    80
      
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    81
      /* when we claim a node for an entry, we also claim the nodes
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    82
	 below it (pruning off the imagined tree that may have dangled
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    83
	 from it) as well as blocking the use of any nodes directly
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    84
	 above for leaves */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    85
      
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    86
      /* update ourself */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    87
      if(length<32 && (entry>>length)){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    88
	/* error condition; the lengths must specify an overpopulated tree */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    89
	_ogg_free(r);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    90
	return(NULL);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    91
      }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    92
      r[count++]=entry;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    93
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    94
      /* Look to see if the next shorter marker points to the node
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    95
	 above. if so, update it and repeat.  */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    96
      {
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    97
	for(j=length;j>0;j--){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    98
	  
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
    99
	  if(marker[j]&1){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   100
	    /* have to jump branches */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   101
	    if(j==1)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   102
	      marker[1]++;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   103
	    else
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   104
	      marker[j]=marker[j-1]<<1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   105
	    break; /* invariant says next upper marker would already
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   106
		      have been moved if it was on the same path */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   107
	  }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   108
	  marker[j]++;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   109
	}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   110
      }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   111
      
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   112
      /* prune the tree; the implicit invariant says all the longer
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   113
	 markers were dangling from our just-taken node.  Dangle them
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   114
	 from our *new* node. */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   115
      for(j=length+1;j<33;j++)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   116
	if((marker[j]>>1) == entry){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   117
	  entry=marker[j];
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   118
	  marker[j]=marker[j-1]<<1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   119
	}else
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   120
	  break;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   121
    }else
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   122
      if(sparsecount==0)count++;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   123
  }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   124
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   125
  /* bitreverse the words because our bitwise packer/unpacker is LSb
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   126
     endian */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   127
  for(i=0,count=0;i<n;i++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   128
    ogg_uint32_t temp=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   129
    for(j=0;j<l[i];j++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   130
      temp<<=1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   131
      temp|=(r[count]>>j)&1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   132
    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   133
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   134
    if(sparsecount){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   135
      if(l[i])
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   136
	r[count++]=temp;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   137
    }else
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   138
      r[count++]=temp;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   139
  }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   140
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   141
  return(r);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   142
}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   143
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   144
/* there might be a straightforward one-line way to do the below
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   145
   that's portable and totally safe against roundoff, but I haven't
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   146
   thought of it.  Therefore, we opt on the side of caution */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   147
long _book_maptype1_quantvals(const static_codebook *b){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   148
  /* get us a starting hint, we'll polish it below */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   149
  int bits=_ilog(b->entries);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   150
  int vals=b->entries>>((bits-1)*(b->dim-1)/b->dim);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   151
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   152
  while(1){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   153
    long acc=1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   154
    long acc1=1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   155
    int i;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   156
    for(i=0;i<b->dim;i++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   157
      acc*=vals;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   158
      acc1*=vals+1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   159
    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   160
    if(acc<=b->entries && acc1>b->entries){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   161
      return(vals);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   162
    }else{
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   163
      if(acc>b->entries){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   164
	vals--;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   165
      }else{
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   166
	vals++;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   167
      }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   168
    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   169
  }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   170
}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   171
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   172
/* different than what _book_unquantize does for mainline:
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   173
   we repack the book in a fixed point format that shares the same
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   174
   binary point.  Upon first use, we can shift point if needed */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   175
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   176
/* we need to deal with two map types: in map type 1, the values are
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   177
   generated algorithmically (each column of the vector counts through
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   178
   the values in the quant vector). in map type 2, all the values came
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   179
   in in an explicit list.  Both value lists must be unpacked */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   180
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   181
ogg_int32_t *_book_unquantize(const static_codebook *b,int n,int *sparsemap,
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   182
			      int *maxpoint){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   183
  long j,k,count=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   184
  if(b->maptype==1 || b->maptype==2){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   185
    int quantvals;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   186
    int minpoint,delpoint;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   187
    ogg_int32_t mindel=_float32_unpack(b->q_min,&minpoint);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   188
    ogg_int32_t delta=_float32_unpack(b->q_delta,&delpoint);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   189
    ogg_int32_t *r=(ogg_int32_t *)_ogg_calloc(n*b->dim,sizeof(*r));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   190
    int *rp=(int *)_ogg_calloc(n*b->dim,sizeof(*rp));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   191
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   192
    *maxpoint=minpoint;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   193
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   194
    /* maptype 1 and 2 both use a quantized value vector, but
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   195
       different sizes */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   196
    switch(b->maptype){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   197
    case 1:
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   198
      /* most of the time, entries%dimensions == 0, but we need to be
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   199
	 well defined.  We define that the possible vales at each
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   200
	 scalar is values == entries/dim.  If entries%dim != 0, we'll
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   201
	 have 'too few' values (values*dim<entries), which means that
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   202
	 we'll have 'left over' entries; left over entries use zeroed
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   203
	 values (and are wasted).  So don't generate codebooks like
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   204
	 that */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   205
      quantvals=_book_maptype1_quantvals(b);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   206
      for(j=0;j<b->entries;j++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   207
	if((sparsemap && b->lengthlist[j]) || !sparsemap){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   208
	  ogg_int32_t last=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   209
	  int lastpoint=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   210
	  int indexdiv=1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   211
	  for(k=0;k<b->dim;k++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   212
	    int index= (j/indexdiv)%quantvals;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   213
	    int point=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   214
	    int val=VFLOAT_MULTI(delta,delpoint,
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   215
				 abs(b->quantlist[index]),&point);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   216
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   217
	    val=VFLOAT_ADD(mindel,minpoint,val,point,&point);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   218
	    val=VFLOAT_ADD(last,lastpoint,val,point,&point);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   219
	    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   220
	    if(b->q_sequencep){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   221
	      last=val;	  
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   222
	      lastpoint=point;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   223
	    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   224
	    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   225
	    if(sparsemap){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   226
	      r[sparsemap[count]*b->dim+k]=val;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   227
	      rp[sparsemap[count]*b->dim+k]=point;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   228
	    }else{
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   229
	      r[count*b->dim+k]=val;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   230
	      rp[count*b->dim+k]=point;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   231
	    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   232
	    if(*maxpoint<point)*maxpoint=point;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   233
	    indexdiv*=quantvals;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   234
	  }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   235
	  count++;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   236
	}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   237
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   238
      }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   239
      break;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   240
    case 2:
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   241
      for(j=0;j<b->entries;j++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   242
	if((sparsemap && b->lengthlist[j]) || !sparsemap){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   243
	  ogg_int32_t last=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   244
	  int         lastpoint=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   245
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   246
	  for(k=0;k<b->dim;k++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   247
	    int point=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   248
	    int val=VFLOAT_MULTI(delta,delpoint,
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   249
				 abs(b->quantlist[j*b->dim+k]),&point);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   250
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   251
	    val=VFLOAT_ADD(mindel,minpoint,val,point,&point);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   252
	    val=VFLOAT_ADD(last,lastpoint,val,point,&point);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   253
	    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   254
	    if(b->q_sequencep){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   255
	      last=val;	  
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   256
	      lastpoint=point;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   257
	    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   258
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   259
	    if(sparsemap){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   260
	      r[sparsemap[count]*b->dim+k]=val;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   261
	      rp[sparsemap[count]*b->dim+k]=point;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   262
	    }else{
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   263
	      r[count*b->dim+k]=val;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   264
	      rp[count*b->dim+k]=point;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   265
	    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   266
	    if(*maxpoint<point)*maxpoint=point;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   267
	  }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   268
	  count++;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   269
	}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   270
      }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   271
      break;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   272
    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   273
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   274
    for(j=0;j<n*b->dim;j++)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   275
      if(rp[j]<*maxpoint)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   276
	r[j]>>=*maxpoint-rp[j];
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   277
	    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   278
    _ogg_free(rp);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   279
    return(r);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   280
  }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   281
  return(NULL);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   282
}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   283
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   284
void vorbis_staticbook_clear(static_codebook *b){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   285
  if(b->quantlist)_ogg_free(b->quantlist);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   286
  if(b->lengthlist)_ogg_free(b->lengthlist);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   287
  memset(b,0,sizeof(*b));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   288
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   289
}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   290
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   291
void vorbis_staticbook_destroy(static_codebook *b){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   292
  vorbis_staticbook_clear(b);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   293
  _ogg_free(b);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   294
}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   295
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   296
void vorbis_book_clear(codebook *b){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   297
  /* static book is not cleared; we're likely called on the lookup and
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   298
     the static codebook belongs to the info struct */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   299
  if(b->valuelist)_ogg_free(b->valuelist);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   300
  if(b->codelist)_ogg_free(b->codelist);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   301
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   302
  if(b->dec_index)_ogg_free(b->dec_index);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   303
  if(b->dec_codelengths)_ogg_free(b->dec_codelengths);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   304
  if(b->dec_firsttable)_ogg_free(b->dec_firsttable);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   305
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   306
  memset(b,0,sizeof(*b));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   307
}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   308
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   309
static ogg_uint32_t bitreverse(ogg_uint32_t x){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   310
  x=    ((x>>16)&0x0000ffffUL) | ((x<<16)&0xffff0000UL);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   311
  x=    ((x>> 8)&0x00ff00ffUL) | ((x<< 8)&0xff00ff00UL);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   312
  x=    ((x>> 4)&0x0f0f0f0fUL) | ((x<< 4)&0xf0f0f0f0UL);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   313
  x=    ((x>> 2)&0x33333333UL) | ((x<< 2)&0xccccccccUL);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   314
  return((x>> 1)&0x55555555UL) | ((x<< 1)&0xaaaaaaaaUL);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   315
}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   316
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   317
static int sort32a(const void *a,const void *b){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   318
  return (**(ogg_uint32_t **)a>**(ogg_uint32_t **)b)-
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   319
    (**(ogg_uint32_t **)a<**(ogg_uint32_t **)b);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   320
}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   321
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   322
/* decode codebook arrangement is more heavily optimized than encode */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   323
int vorbis_book_init_decode(codebook *c,const static_codebook *s){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   324
  int i,j,n=0,tabn;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   325
  int *sortindex;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   326
  memset(c,0,sizeof(*c));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   327
  
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   328
  /* count actually used entries */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   329
  for(i=0;i<s->entries;i++)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   330
    if(s->lengthlist[i]>0)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   331
      n++;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   332
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   333
  c->entries=s->entries;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   334
  c->used_entries=n;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   335
  c->dim=s->dim;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   336
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   337
  if(n>0){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   338
    /* two different remappings go on here.  
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   339
       
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   340
       First, we collapse the likely sparse codebook down only to
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   341
       actually represented values/words.  This collapsing needs to be
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   342
       indexed as map-valueless books are used to encode original entry
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   343
       positions as integers.
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   344
       
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   345
       Second, we reorder all vectors, including the entry index above,
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   346
       by sorted bitreversed codeword to allow treeless decode. */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   347
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   348
    /* perform sort */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   349
    ogg_uint32_t *codes=_make_words(s->lengthlist,s->entries,c->used_entries);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   350
    ogg_uint32_t **codep=(ogg_uint32_t **)alloca(sizeof(*codep)*n);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   351
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   352
    if(codes==NULL)goto err_out;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   353
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   354
    for(i=0;i<n;i++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   355
      codes[i]=bitreverse(codes[i]);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   356
      codep[i]=codes+i;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   357
    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   358
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   359
    qsort(codep,n,sizeof(*codep),sort32a);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   360
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   361
    sortindex=(int *)alloca(n*sizeof(*sortindex));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   362
    c->codelist=(ogg_uint32_t *)_ogg_malloc(n*sizeof(*c->codelist));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   363
    /* the index is a reverse index */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   364
    for(i=0;i<n;i++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   365
      int position=codep[i]-codes;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   366
      sortindex[position]=i;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   367
    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   368
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   369
    for(i=0;i<n;i++)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   370
      c->codelist[sortindex[i]]=codes[i];
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   371
    _ogg_free(codes);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   372
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   373
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   374
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   375
    c->valuelist=_book_unquantize(s,n,sortindex,&c->binarypoint);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   376
    c->dec_index=(int *)_ogg_malloc(n*sizeof(*c->dec_index));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   377
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   378
    for(n=0,i=0;i<s->entries;i++)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   379
      if(s->lengthlist[i]>0)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   380
	c->dec_index[sortindex[n++]]=i;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   381
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   382
    c->dec_codelengths=(char *)_ogg_malloc(n*sizeof(*c->dec_codelengths));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   383
    for(n=0,i=0;i<s->entries;i++)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   384
      if(s->lengthlist[i]>0)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   385
	c->dec_codelengths[sortindex[n++]]=s->lengthlist[i];
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   386
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   387
    c->dec_firsttablen=_ilog(c->used_entries)-4; /* this is magic */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   388
    if(c->dec_firsttablen<5)c->dec_firsttablen=5;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   389
    if(c->dec_firsttablen>8)c->dec_firsttablen=8;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   390
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   391
    tabn=1<<c->dec_firsttablen;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   392
    c->dec_firsttable=(ogg_uint32_t *)_ogg_calloc(tabn,sizeof(*c->dec_firsttable));
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   393
    c->dec_maxlength=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   394
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   395
    for(i=0;i<n;i++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   396
      if(c->dec_maxlength<c->dec_codelengths[i])
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   397
	c->dec_maxlength=c->dec_codelengths[i];
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   398
      if(c->dec_codelengths[i]<=c->dec_firsttablen){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   399
	ogg_uint32_t orig=bitreverse(c->codelist[i]);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   400
	for(j=0;j<(1<<(c->dec_firsttablen-c->dec_codelengths[i]));j++)
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   401
	  c->dec_firsttable[orig|(j<<c->dec_codelengths[i])]=i+1;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   402
      }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   403
    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   404
    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   405
    /* now fill in 'unused' entries in the firsttable with hi/lo search
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   406
       hints for the non-direct-hits */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   407
    {
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   408
      ogg_uint32_t mask=0xfffffffeUL<<(31-c->dec_firsttablen);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   409
      long lo=0,hi=0;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   410
      
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   411
      for(i=0;i<tabn;i++){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   412
	ogg_uint32_t word=i<<(32-c->dec_firsttablen);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   413
	if(c->dec_firsttable[bitreverse(word)]==0){
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   414
	  while((lo+1)<n && c->codelist[lo+1]<=word)lo++;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   415
	  while(    hi<n && word>=(c->codelist[hi]&mask))hi++;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   416
	  
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   417
	  /* we only actually have 15 bits per hint to play with here.
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   418
	     In order to overflow gracefully (nothing breaks, efficiency
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   419
	     just drops), encode as the difference from the extremes. */
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   420
	  {
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   421
	    unsigned long loval=lo;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   422
	    unsigned long hival=n-hi;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   423
	    
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   424
	    if(loval>0x7fff)loval=0x7fff;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   425
	    if(hival>0x7fff)hival=0x7fff;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   426
	    c->dec_firsttable[bitreverse(word)]=
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   427
	      0x80000000UL | (loval<<15) | hival;
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   428
	  }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   429
	}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   430
      }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   431
    }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   432
  }
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   433
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   434
  return(0);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   435
 err_out:
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   436
  vorbis_book_clear(c);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   437
  return(-1);
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   438
}
519d5bc91dd3 revert tremor back to a version before koda broke it ;p
Xeli
parents:
diff changeset
   439