annotate tremor/sharedbook.c @ 20300:30b75e573d5c

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