]> 4ch.mooo.com Git - 16.git/blob - src/lib/dl/ext/vorbis/codebook.c
meh did some cleanings and i will work on mapread to mm thingy sometime soon! oops...
[16.git] / src / lib / dl / ext / vorbis / codebook.c
1 /********************************************************************
2  *                                                                  *
3  * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
5  * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
6  * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
7  *                                                                  *
8  * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2009             *
9  * by the Xiph.Org Foundation http://www.xiph.org/                  *
10  *                                                                  *
11  ********************************************************************
12
13  function: basic codebook pack/unpack/code/decode operations
14  last mod: $Id: codebook.c 17553 2010-10-21 17:54:26Z tterribe $
15
16  ********************************************************************/
17
18 #include <stdlib.h>
19 #include <string.h>
20 #include <math.h>
21 #include <ext/libogg/ogg.h>
22 #include "codec.h"
23 #include "codebook.h"
24 #include "scales.h"
25 #include "misc.h"
26 #include "os.h"
27
28 /* packs the given codebook into the bitstream **************************/
29
30 int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
31   long i,j;
32   int ordered=0;
33
34   /* first the basic parameters */
35   oggpack_write(opb,0x564342,24);
36   oggpack_write(opb,c->dim,16);
37   oggpack_write(opb,c->entries,24);
38
39   /* pack the codewords.  There are two packings; length ordered and
40      length random.  Decide between the two now. */
41
42   for(i=1;i<c->entries;i++)
43     if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break;
44   if(i==c->entries)ordered=1;
45
46   if(ordered){
47     /* length ordered.  We only need to say how many codewords of
48        each length.  The actual codewords are generated
49        deterministically */
50
51     long count=0;
52     oggpack_write(opb,1,1);  /* ordered */
53     oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
54
55     for(i=1;i<c->entries;i++){
56       long this=c->lengthlist[i];
57       long last=c->lengthlist[i-1];
58       if(this>last){
59         for(j=last;j<this;j++){
60           oggpack_write(opb,i-count,_ilog(c->entries-count));
61           count=i;
62         }
63       }
64     }
65     oggpack_write(opb,i-count,_ilog(c->entries-count));
66
67   }else{
68     /* length random.  Again, we don't code the codeword itself, just
69        the length.  This time, though, we have to encode each length */
70     oggpack_write(opb,0,1);   /* unordered */
71
72     /* algortihmic mapping has use for 'unused entries', which we tag
73        here.  The algorithmic mapping happens as usual, but the unused
74        entry has no codeword. */
75     for(i=0;i<c->entries;i++)
76       if(c->lengthlist[i]==0)break;
77
78     if(i==c->entries){
79       oggpack_write(opb,0,1); /* no unused entries */
80       for(i=0;i<c->entries;i++)
81         oggpack_write(opb,c->lengthlist[i]-1,5);
82     }else{
83       oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
84       for(i=0;i<c->entries;i++){
85         if(c->lengthlist[i]==0){
86           oggpack_write(opb,0,1);
87         }else{
88           oggpack_write(opb,1,1);
89           oggpack_write(opb,c->lengthlist[i]-1,5);
90         }
91       }
92     }
93   }
94
95   /* is the entry number the desired return value, or do we have a
96      mapping? If we have a mapping, what type? */
97   oggpack_write(opb,c->maptype,4);
98   switch(c->maptype){
99   case 0:
100     /* no mapping */
101     break;
102   case 1:case 2:
103     /* implicitly populated value mapping */
104     /* explicitly populated value mapping */
105
106     if(!c->quantlist){
107       /* no quantlist?  error */
108       return(-1);
109     }
110
111     /* values that define the dequantization */
112     oggpack_write(opb,c->q_min,32);
113     oggpack_write(opb,c->q_delta,32);
114     oggpack_write(opb,c->q_quant-1,4);
115     oggpack_write(opb,c->q_sequencep,1);
116
117     {
118       int quantvals;
119       switch(c->maptype){
120       case 1:
121         /* a single column of (c->entries/c->dim) quantized values for
122            building a full value list algorithmically (square lattice) */
123         quantvals=_book_maptype1_quantvals(c);
124         break;
125       case 2:
126         /* every value (c->entries*c->dim total) specified explicitly */
127         quantvals=c->entries*c->dim;
128         break;
129       default: /* NOT_REACHABLE */
130         quantvals=-1;
131       }
132
133       /* quantized values */
134       for(i=0;i<quantvals;i++)
135         oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
136
137     }
138     break;
139   default:
140     /* error case; we don't have any other map types now */
141     return(-1);
142   }
143
144   return(0);
145 }
146
147 /* unpacks a codebook from the packet buffer into the codebook struct,
148    readies the codebook auxiliary structures for decode *************/
149 static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
150   long i,j;
151   static_codebook *s=_ogg_calloc(1,sizeof(*s));
152   s->allocedp=1;
153
154   /* make sure alignment is correct */
155   if(oggpack_read(opb,24)!=0x564342)goto _eofout;
156
157   /* first the basic parameters */
158   s->dim=oggpack_read(opb,16);
159   s->entries=oggpack_read(opb,24);
160   if(s->entries==-1)goto _eofout;
161
162   if(_ilog(s->dim)+_ilog(s->entries)>24)goto _eofout;
163
164   /* codeword ordering.... length ordered or unordered? */
165   switch((int)oggpack_read(opb,1)){
166   case 0:{
167     long unused;
168     /* allocated but unused entries? */
169     unused=oggpack_read(opb,1);
170     if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb))
171       goto _eofout;
172     /* unordered */
173     s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
174
175     /* allocated but unused entries? */
176     if(unused){
177       /* yes, unused entries */
178
179       for(i=0;i<s->entries;i++){
180         if(oggpack_read(opb,1)){
181           long num=oggpack_read(opb,5);
182           if(num==-1)goto _eofout;
183           s->lengthlist[i]=num+1;
184         }else
185           s->lengthlist[i]=0;
186       }
187     }else{
188       /* all entries used; no tagging */
189       for(i=0;i<s->entries;i++){
190         long num=oggpack_read(opb,5);
191         if(num==-1)goto _eofout;
192         s->lengthlist[i]=num+1;
193       }
194     }
195
196     break;
197   }
198   case 1:
199     /* ordered */
200     {
201       long length=oggpack_read(opb,5)+1;
202       if(length==0)goto _eofout;
203       s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
204
205       for(i=0;i<s->entries;){
206         long num=oggpack_read(opb,_ilog(s->entries-i));
207         if(num==-1)goto _eofout;
208         if(length>32 || num>s->entries-i ||
209            (num>0 && (num-1)>>(length-1)>1)){
210           goto _errout;
211         }
212         if(length>32)goto _errout;
213         for(j=0;j<num;j++,i++)
214           s->lengthlist[i]=length;
215         length++;
216       }
217     }
218     break;
219   default:
220     /* EOF */
221     goto _eofout;
222   }
223
224   /* Do we have a mapping to unpack? */
225   switch((s->maptype=oggpack_read(opb,4))){
226   case 0:
227     /* no mapping */
228     break;
229   case 1: case 2:
230     /* implicitly populated value mapping */
231     /* explicitly populated value mapping */
232
233     s->q_min=oggpack_read(opb,32);
234     s->q_delta=oggpack_read(opb,32);
235     s->q_quant=oggpack_read(opb,4)+1;
236     s->q_sequencep=oggpack_read(opb,1);
237     if(s->q_sequencep==-1)goto _eofout;
238
239     {
240       int quantvals=0;
241       switch(s->maptype){
242       case 1:
243         quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
244         break;
245       case 2:
246         quantvals=s->entries*s->dim;
247         break;
248       }
249
250       /* quantized values */
251       if((quantvals*s->q_quant+7>>3)>opb->storage-oggpack_bytes(opb))
252         goto _eofout;
253       s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
254       for(i=0;i<quantvals;i++)
255         s->quantlist[i]=oggpack_read(opb,s->q_quant);
256
257       if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
258     }
259     break;
260   default:
261     goto _errout;
262   }
263
264   /* all set */
265   return(s);
266
267  _errout:
268  _eofout:
269   vorbis_staticbook_destroy(s);
270   return(NULL);
271 }
272
273 /* returns the number of bits ************************************************/
274 int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
275   if(a<0 || a>=book->c->entries)return(0);
276   oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
277   return(book->c->lengthlist[a]);
278 }
279
280 /* the 'eliminate the decode tree' optimization actually requires the
281    codewords to be MSb first, not LSb.  This is an annoying inelegancy
282    (and one of the first places where carefully thought out design
283    turned out to be wrong; Vorbis II and future Ogg codecs should go
284    to an MSb bitpacker), but not actually the huge hit it appears to
285    be.  The first-stage decode table catches most words so that
286    bitreverse is not in the main execution path. */
287
288 static ogg_uint32_t bitreverse(ogg_uint32_t x){
289   x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
290   x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
291   x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
292   x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
293   return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
294 }
295
296 STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
297   int  read=book->dec_maxlength;
298   long lo,hi;
299   long lok = oggpack_look(b,book->dec_firsttablen);
300
301   if (lok >= 0) {
302     long entry = book->dec_firsttable[lok];
303     if(entry&0x80000000UL){
304       lo=(entry>>15)&0x7fff;
305       hi=book->used_entries-(entry&0x7fff);
306     }else{
307       oggpack_adv(b, book->dec_codelengths[entry-1]);
308       return(entry-1);
309     }
310   }else{
311     lo=0;
312     hi=book->used_entries;
313   }
314
315   lok = oggpack_look(b, read);
316
317   while(lok<0 && read>1)
318     lok = oggpack_look(b, --read);
319   if(lok<0)return -1;
320
321   /* bisect search for the codeword in the ordered list */
322   {
323     ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
324
325     while(hi-lo>1){
326       long p=(hi-lo)>>1;
327       long test=book->codelist[lo+p]>testword;
328       lo+=p&(test-1);
329       hi-=p&(-test);
330       }
331
332     if(book->dec_codelengths[lo]<=read){
333       oggpack_adv(b, book->dec_codelengths[lo]);
334       return(lo);
335     }
336   }
337
338   oggpack_adv(b, read);
339
340   return(-1);
341 }
342
343 /* Decode side is specced and easier, because we don't need to find
344    matches using different criteria; we simply read and map.  There are
345    two things we need to do 'depending':
346
347    We may need to support interleave.  We don't really, but it's
348    convenient to do it here rather than rebuild the vector later.
349
350    Cascades may be additive or multiplicitive; this is not inherent in
351    the codebook, but set in the code using the codebook.  Like
352    interleaving, it's easiest to do it here.
353    addmul==0 -> declarative (set the value)
354    addmul==1 -> additive
355    addmul==2 -> multiplicitive */
356
357 /* returns the [original, not compacted] entry number or -1 on eof *********/
358 long vorbis_book_decode(codebook *book, oggpack_buffer *b){
359   if(book->used_entries>0){
360     long packed_entry=decode_packed_entry_number(book,b);
361     if(packed_entry>=0)
362       return(book->dec_index[packed_entry]);
363   }
364
365   /* if there's no dec_index, the codebook unpacking isn't collapsed */
366   return(-1);
367 }
368
369 /* returns 0 on OK or -1 on eof *************************************/
370 long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
371   if(book->used_entries>0){
372     int step=n/book->dim;
373     long *entry = alloca(sizeof(*entry)*step);
374     float **t = alloca(sizeof(*t)*step);
375     int i,j,o;
376
377     for (i = 0; i < step; i++) {
378       entry[i]=decode_packed_entry_number(book,b);
379       if(entry[i]==-1)return(-1);
380       t[i] = book->valuelist+entry[i]*book->dim;
381     }
382     for(i=0,o=0;i<book->dim;i++,o+=step)
383       for (j=0;j<step;j++)
384         a[o+j]+=t[j][i];
385   }
386   return(0);
387 }
388
389 long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
390   if(book->used_entries>0){
391     int i,j,entry;
392     float *t;
393
394     if(book->dim>8){
395       for(i=0;i<n;){
396         entry = decode_packed_entry_number(book,b);
397         if(entry==-1)return(-1);
398         t     = book->valuelist+entry*book->dim;
399         for (j=0;j<book->dim;)
400           a[i++]+=t[j++];
401       }
402     }else{
403       for(i=0;i<n;){
404         entry = decode_packed_entry_number(book,b);
405         if(entry==-1)return(-1);
406         t     = book->valuelist+entry*book->dim;
407         j=0;
408         switch((int)book->dim){
409         case 8:
410           a[i++]+=t[j++];
411         case 7:
412           a[i++]+=t[j++];
413         case 6:
414           a[i++]+=t[j++];
415         case 5:
416           a[i++]+=t[j++];
417         case 4:
418           a[i++]+=t[j++];
419         case 3:
420           a[i++]+=t[j++];
421         case 2:
422           a[i++]+=t[j++];
423         case 1:
424           a[i++]+=t[j++];
425         case 0:
426           break;
427         }
428       }
429     }
430   }
431   return(0);
432 }
433
434 long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
435   if(book->used_entries>0){
436     int i,j,entry;
437     float *t;
438
439     for(i=0;i<n;){
440       entry = decode_packed_entry_number(book,b);
441       if(entry==-1)return(-1);
442       t     = book->valuelist+entry*book->dim;
443       for (j=0;j<book->dim;)
444         a[i++]=t[j++];
445     }
446   }else{
447     int i,j;
448
449     for(i=0;i<n;){
450       for (j=0;j<book->dim;)
451         a[i++]=0.f;
452     }
453   }
454   return(0);
455 }
456
457 long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
458                               oggpack_buffer *b,int n){
459
460   long i,j,entry;
461   int chptr=0;
462   if(book->used_entries>0){
463     for(i=offset/ch;i<(offset+n)/ch;){
464       entry = decode_packed_entry_number(book,b);
465       if(entry==-1)return(-1);
466       {
467         const float *t = book->valuelist+entry*book->dim;
468         for (j=0;j<book->dim;j++){
469           a[chptr++][i]+=t[j];
470           if(chptr==ch){
471             chptr=0;
472             i++;
473           }
474         }
475       }
476     }
477   }
478   return(0);
479 }