1 /********************************************************************
3 * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE. *
4 * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
5 * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE. *
6 * PLEASE READ THESE TERMS DISTRIBUTING. *
8 * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-2000 *
9 * by Monty <monty@xiph.org> and The XIPHOPHORUS Company *
10 * http://www.xiph.org/ *
12 ********************************************************************
14 function: basic codebook pack/unpack/code/decode operations
15 last mod: $Id: codebook.c,v 1.1 2000/01/11 16:12:30 xiphmont Exp $
17 ********************************************************************/
20 #include "vorbis/codec.h"
21 #include "vorbis/codebook.h"
24 /**** pack/unpack helpers ******************************************/
25 static int ilog(unsigned int v){
34 static long _float24_pack(double val){
42 exp= floor(log(val)/log(2));
43 mant=rint(ldexp(val,17-exp));
44 exp=(exp+VQ_FEXP_BIAS)<<18;
46 return(sign|exp|mant);
49 static double _float24_unpack(long val){
50 double mant=val&0x3ffff;
51 double sign=val&0x800000;
52 double exp =(val&0x7c0000)>>18;
54 return(ldexp(mant,exp-17-VQ_FEXP_BIAS));
57 /* given a list of word lengths, generate a list of codewords. Works
58 for length ordered or unordered, always assigns the lowest valued
60 long *_make_words(long *l,long n){
63 long *r=malloc(n*sizeof(long));
64 memset(marker,0,sizeof(marker));
68 long entry=marker[[i]];
70 /* when we claim a node for an entry, we also claim the nodes
71 below it (pruning off the imagined tree that may have dangled
72 from it) as well as blocking the use of any nodes directly
76 if(length<32 && (entry>>length)){
77 /* error condition; the lengths must specify an overpopulated tree */
83 /* Look to see if the next shorter marker points to the node
84 above. if so, update it and repeat. */
86 for(j=length;j>0;j--){
89 /* have to jump branches */
93 marker[j]=marker[j-1]<<1;
94 break; /* invariant says next upper marker would already
95 have been moved if it was on the same path */
101 /* prune the tree; the implicit invariant says all the longer
102 markers were dangling from our just-taken node. Dangle them
103 from our *new* node. */
104 for(j=length+1;j<33;j++)
105 marker[j]=marker[j-1]<<1;
108 /* bitreverse the words because our bitwise packer/unpacker is LSb
122 /* unpack the quantized list of values for encode/decode ***********/
123 static double *_book_unquantize(codebook *b){
125 double mindel=float24_unpack(b->q_min);
126 double delta=float24_unpack(b->q_delta);
127 double *r=malloc(sizeof(double)*b->entries*b->dim);
129 for(j=0;j<b->entries;j++){
131 for(k=0;k<b->dim;k++){
132 double val=b->quantlist[j*b->dim+k]*delta+last+mindel;
134 if(b->q_sequencep)last=val;
140 /**** Defend the abstraction ****************************************/
142 /* some elements in the codebook structure are assumed to be pointers
143 to static/shared storage (the pointers are duped, and free below
144 does not touch them. The fields are unused by decode):
152 codebook *vorbis_book_dup(const codebook *b){
153 codebook *r=malloc(1,sizeof(codebook));
154 memcpy(r,b,sizeof(codebook));
156 /* handle non-flat storage */
158 r->valuelist=malloc(sizeof(double)*b->dim*b->entries);
159 memcpy(r->valuelist,b->valuelist,sizeof(double)*b->dim*b->entries);
162 r->codelist=malloc(sizeof(long)*b->entries);
163 memcpy(r->codelist,b->codelist,sizeof(long)**b->entries);
166 /* encode tree is assumed to be static storage; don't free it */
169 long aux=b->decode_tree->aux;
170 r->decode_tree=malloc(sizeof(decode_aux));
171 r->decode_tree->aux=aux;
172 r->decode_tree->ptr0=malloc(sizeof(long)*aux);
173 r->decode_tree->ptr1=malloc(sizeof(long)*aux);
175 memcpy(r->decode_tree->ptr0,b->decode_tree->ptr0,sizeof(long)*aux);
176 memcpy(r->decode_tree->ptr1,b->decode_tree->ptr1,sizeof(long)*aux);
181 void vorbis_book_free(codebook *b){
184 free(b->decode_tree->ptr0);
185 free(b->decode_tree->ptr1);
186 memset(b->decode_tree,0,sizeof(decode_aux));
187 free(b->decode_tree);
189 if(b->valuelist)free(b->valuelist);
190 if(b->codelist)free(b->codelist);
191 memset(b,0,sizeof(codebook));
196 /* packs the given codebook into the bitstream
197 side effects: populates the valuelist and codeword members ***********/
198 int vorbis_book_pack(codebook *c,oggpack_buffer *b){
202 /* first the basic parameters */
203 _oggpack_write(b,0x564342,24);
204 _oggpack_write(b,c->dim,16);
205 _oggpack_write(b,c->entries,24);
207 /* pack the codewords. There are two packings; length ordered and
208 length random. Decide between the two now. */
210 for(i=1;i<c->entries;i++)
211 if(c->lengthlist[i]<c->lengthlist[i-1])break;
212 if(i==c->entries)ordered=1;
215 /* length ordered. We only need to say how many codewords of
216 each length. The actual codewords are generated
220 _oggpack_write(b,1,1); /* ordered */
221 _oggpack_write(b,c->lengthlist[0]-1,5); /* 1 to 32 */
223 for(i=1;i<c->entries;i++){
224 long this=c->lengthlist[i];
225 long last=c->lengthlist[i-1];
227 for(j=last;j<this;j++){
228 _oggpack_write(b,i-count,ilog(c->entries-count));
233 _oggpack_write(b,i-count,ilog(count));
236 /* length random. Again, we don't code the codeword itself, just
237 the length. This time, though, we have to encode each length */
238 _oggpack_write(b,0,1); /* unordered */
239 for(i=0;i<c->entries;i++)
240 _oggpack_write(b,c->lengthlist[i]-1,5);
243 /* is the entry number the desired return value, or do we have a
245 if(codebook->quantlist){
246 /* we have a mapping. bundle it out. */
247 _oggpack_write(b,1,1);
249 /* values that define the dequantization */
250 _oggpack_write(b,c->q_min,24);
251 _oggpack_write(b,c->q_delta,24);
252 _oggpack_write(b,c->q_quant-1,4);
253 _oggpack_write(b,c->q_sequencep,1);
255 /* quantized values */
256 for(i=0;i<c->entries*c->dim;i++)
257 _oggpack_write(b,c->quantlist[i],c->q_quant);
261 _oggpack_write(b,0,1);
264 c->codelist=_make_words(c->lengthlist,c->entries);
265 c->valuelist=_book_unquantize(c);
270 /* unpacks a codebook from the packet buffer into the codebook struct,
271 readies the codebook auxiliary structures for decode *************/
272 codebook *vorbis_book_unpack(oggpack_buffer *b){
273 codebook *c=calloc(1,sizeof(codebook));
275 /* make sure alignment is correct */
276 if(_oggpack_read(b,24)!=0x564342)goto _eofout;
278 /* first the basic parameters */
279 c->dim=_oggpack_read(b,16);
280 c->entries=_oggpack_read(b,24);
281 if(c->entries==-1)goto _eofout;
283 /* codeword ordering.... length ordered or unordered? */
284 switch(_oggpack_read(b,1)){
287 c->lengthlist=malloc(sizeof(long)*c->entries);
288 for(i=0;i<c->entries;i++){
289 long num=_oggpack_read(b,5);
290 if(num==-1)goto _eofout;
291 c->lengthlist[i]=num+1;
298 long length=_oggpack_read(b,5)+1;
299 c->lengthlist=malloc(sizeof(long)*c->entries);
301 for(i=0;i<c->entries){
302 long num=_oggpack_read(b,ilog(c->entries-i));
303 if(num==-1)goto _eofout;
304 for(j=0;j<num;j++,i++)
305 c->lengthlist[i]=length;
315 /* now we generate the codewords for the given lengths */
316 c->codelist=_make_words(c->lengthlist,c->entries);
317 if(c->codelist==NULL)goto _errout;
319 /* ...and the decode helper tree from the codewords */
322 decode_aux *t=c->decode_tree=malloc(sizeof(decode_aux));
323 long *ptr0=c->decode_tree->ptr0=calloc(c->entries*2,sizeof(long));
324 long *ptr1=c->decode_tree->ptr1=calloc(c->entries*2,sizeof(long));
325 c->decode_tree->aux=c->entries*2;
327 for(i=0;i<c->entries;i++){
329 for(j=0;j<c->lengthlist[i]-1;j++){
330 int bit=(c->codelist[i]>>j)&1;
341 if(!((c->codelist[i]>>j)&1))
347 /* no longer needed */
348 free(c->lengthlist);c->lengthlist=NULL;
349 free(c->codelist);c->codelist=NULL;
351 /* Do we have a mapping to unpack? */
352 if(_oggpack_read(b,1)){
354 /* values that define the dequantization */
355 c->q_min=_oggpack_read(b,24);
356 c->q_delta=_oggpack_read(b,24);
357 c->q_quant=_oggpack_read(b,4)+1;
358 c->q_sequencep=_oggpack_read(b,1);
360 /* quantized values */
361 c->quantlist=malloc(sizeof(double)*c->entries*c->dim);
362 for(i=0;i<c->entries*c->dim;i++)
363 c->quantlist[i]=_oggpack_read(b,c->q_quant);
364 if(c->quantlist[i-1]==-1)goto _eofout;
365 vorbis_book_unquantize(c);
366 free(c->quantlist);c->quantlist=NULL;
374 if(c->lengthlist)free(c->lengthlist);c->lengthlist=NULL;
375 if(c->quantlist)free(c->quantlist);c->quantlist=NULL;
381 /* returns the number of bits ***************************************/
382 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
383 _oggpack_write(b,book->codelist[a],book->lengthlist[a]);
384 return(book->lengthlist[a]);
387 /* returns the number of bits and *modifies a* to the entry value *****/
388 int vorbis_book_encodev(codebook *book, double *a, oggpack_buffer *b){
389 encode_aux *t=book->encode_tree;
395 double *p=book->valuelist+t->p[ptr];
396 double *q=book->valuelist+t->q[ptr];
399 c+=(p[k]-q[k])*(a[k]-(p[k]+q[k])*.5);
407 memcpy(a,book->valuelist-ptr*dim,dim*sizeof(double));
408 return(vorbis_book_encode(book,-ptr,b));
411 /* returns the entry number or -1 on eof ****************************/
412 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
414 decode_aux *t=book->decode_tree;
416 switch(__oggpack_read1(b)){
430 /* returns the entry number or -1 on eof ****************************/
431 long vorbis_book_decodev(codebook *book, double *a, oggpack_buffer *b){
432 long entry=vorbis_book_decode(book,b);
433 if(entry==-1)return(-1);
434 memcpy(a,b->valuelist+entry*b->dim,sizeof(double)*b->dim);