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