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 17030 2010-03-25 06:52:55Z xiphmont $
15
16 ********************************************************************/
17
18#include <stdlib.h>
19#include <string.h>
20#include <math.h>
21#include <ogg/ogg.h>
22#include "vorbis/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
30int 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 *************/
149static_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    /* unordered */
168    s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
169
170    /* allocated but unused entries? */
171    if(oggpack_read(opb,1)){
172      /* yes, unused entries */
173
174      for(i=0;i<s->entries;i++){
175        if(oggpack_read(opb,1)){
176          long num=oggpack_read(opb,5);
177          if(num==-1)goto _eofout;
178          s->lengthlist[i]=num+1;
179        }else
180          s->lengthlist[i]=0;
181      }
182    }else{
183      /* all entries used; no tagging */
184      for(i=0;i<s->entries;i++){
185        long num=oggpack_read(opb,5);
186        if(num==-1)goto _eofout;
187        s->lengthlist[i]=num+1;
188      }
189    }
190
191    break;
192  case 1:
193    /* ordered */
194    {
195      long length=oggpack_read(opb,5)+1;
196      s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
197
198      for(i=0;i<s->entries;){
199        long num=oggpack_read(opb,_ilog(s->entries-i));
200        if(num==-1)goto _eofout;
201        if(length>32)goto _errout;
202        for(j=0;j<num && i<s->entries;j++,i++)
203          s->lengthlist[i]=length;
204        length++;
205      }
206    }
207    break;
208  default:
209    /* EOF */
210    goto _eofout;
211  }
212
213  /* Do we have a mapping to unpack? */
214  switch((s->maptype=oggpack_read(opb,4))){
215  case 0:
216    /* no mapping */
217    break;
218  case 1: case 2:
219    /* implicitly populated value mapping */
220    /* explicitly populated value mapping */
221
222    s->q_min=oggpack_read(opb,32);
223    s->q_delta=oggpack_read(opb,32);
224    s->q_quant=oggpack_read(opb,4)+1;
225    s->q_sequencep=oggpack_read(opb,1);
226    if(s->q_sequencep==-1)goto _eofout;
227
228    {
229      int quantvals=0;
230      switch(s->maptype){
231      case 1:
232        quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
233        break;
234      case 2:
235        quantvals=s->entries*s->dim;
236        break;
237      }
238
239      /* quantized values */
240      s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
241      for(i=0;i<quantvals;i++)
242        s->quantlist[i]=oggpack_read(opb,s->q_quant);
243
244      if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
245    }
246    break;
247  default:
248    goto _errout;
249  }
250
251  /* all set */
252  return(s);
253
254 _errout:
255 _eofout:
256  vorbis_staticbook_destroy(s);
257  return(NULL);
258}
259
260/* returns the number of bits ************************************************/
261int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
262  if(a<0 || a>=book->c->entries)return(0);
263  oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
264  return(book->c->lengthlist[a]);
265}
266
267/* the 'eliminate the decode tree' optimization actually requires the
268   codewords to be MSb first, not LSb.  This is an annoying inelegancy
269   (and one of the first places where carefully thought out design
270   turned out to be wrong; Vorbis II and future Ogg codecs should go
271   to an MSb bitpacker), but not actually the huge hit it appears to
272   be.  The first-stage decode table catches most words so that
273   bitreverse is not in the main execution path. */
274
275static ogg_uint32_t bitreverse(ogg_uint32_t x){
276  x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
277  x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
278  x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
279  x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
280  return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
281}
282
283STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
284  int  read=book->dec_maxlength;
285  long lo,hi;
286  long lok = oggpack_look(b,book->dec_firsttablen);
287
288  if (lok >= 0) {
289    long entry = book->dec_firsttable[lok];
290    if(entry&0x80000000UL){
291      lo=(entry>>15)&0x7fff;
292      hi=book->used_entries-(entry&0x7fff);
293    }else{
294      oggpack_adv(b, book->dec_codelengths[entry-1]);
295      return(entry-1);
296    }
297  }else{
298    lo=0;
299    hi=book->used_entries;
300  }
301
302  lok = oggpack_look(b, read);
303
304  while(lok<0 && read>1)
305    lok = oggpack_look(b, --read);
306  if(lok<0)return -1;
307
308  /* bisect search for the codeword in the ordered list */
309  {
310    ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
311
312    while(hi-lo>1){
313      long p=(hi-lo)>>1;
314      long test=book->codelist[lo+p]>testword;
315      lo+=p&(test-1);
316      hi-=p&(-test);
317      }
318
319    if(book->dec_codelengths[lo]<=read){
320      oggpack_adv(b, book->dec_codelengths[lo]);
321      return(lo);
322    }
323  }
324
325  oggpack_adv(b, read);
326
327  return(-1);
328}
329
330/* Decode side is specced and easier, because we don't need to find
331   matches using different criteria; we simply read and map.  There are
332   two things we need to do 'depending':
333
334   We may need to support interleave.  We don't really, but it's
335   convenient to do it here rather than rebuild the vector later.
336
337   Cascades may be additive or multiplicitive; this is not inherent in
338   the codebook, but set in the code using the codebook.  Like
339   interleaving, it's easiest to do it here.
340   addmul==0 -> declarative (set the value)
341   addmul==1 -> additive
342   addmul==2 -> multiplicitive */
343
344/* returns the [original, not compacted] entry number or -1 on eof *********/
345long vorbis_book_decode(codebook *book, oggpack_buffer *b){
346  if(book->used_entries>0){
347    long packed_entry=decode_packed_entry_number(book,b);
348    if(packed_entry>=0)
349      return(book->dec_index[packed_entry]);
350  }
351
352  /* if there's no dec_index, the codebook unpacking isn't collapsed */
353  return(-1);
354}
355
356/* returns 0 on OK or -1 on eof *************************************/
357long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
358  if(book->used_entries>0){
359    int step=n/book->dim;
360    long *entry = alloca(sizeof(*entry)*step);
361    float **t = alloca(sizeof(*t)*step);
362    int i,j,o;
363
364    for (i = 0; i < step; i++) {
365      entry[i]=decode_packed_entry_number(book,b);
366      if(entry[i]==-1)return(-1);
367      t[i] = book->valuelist+entry[i]*book->dim;
368    }
369    for(i=0,o=0;i<book->dim;i++,o+=step)
370      for (j=0;j<step;j++)
371        a[o+j]+=t[j][i];
372  }
373  return(0);
374}
375
376long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
377  if(book->used_entries>0){
378    int i,j,entry;
379    float *t;
380
381    if(book->dim>8){
382      for(i=0;i<n;){
383        entry = decode_packed_entry_number(book,b);
384        if(entry==-1)return(-1);
385        t     = book->valuelist+entry*book->dim;
386        for (j=0;j<book->dim;)
387          a[i++]+=t[j++];
388      }
389    }else{
390      for(i=0;i<n;){
391        entry = decode_packed_entry_number(book,b);
392        if(entry==-1)return(-1);
393        t     = book->valuelist+entry*book->dim;
394        j=0;
395        switch((int)book->dim){
396        case 8:
397          a[i++]+=t[j++];
398        case 7:
399          a[i++]+=t[j++];
400        case 6:
401          a[i++]+=t[j++];
402        case 5:
403          a[i++]+=t[j++];
404        case 4:
405          a[i++]+=t[j++];
406        case 3:
407          a[i++]+=t[j++];
408        case 2:
409          a[i++]+=t[j++];
410        case 1:
411          a[i++]+=t[j++];
412        case 0:
413          break;
414        }
415      }
416    }
417  }
418  return(0);
419}
420
421long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
422  if(book->used_entries>0){
423    int i,j,entry;
424    float *t;
425
426    for(i=0;i<n;){
427      entry = decode_packed_entry_number(book,b);
428      if(entry==-1)return(-1);
429      t     = book->valuelist+entry*book->dim;
430      for (j=0;j<book->dim;)
431        a[i++]=t[j++];
432    }
433  }else{
434    int i,j;
435
436    for(i=0;i<n;){
437      for (j=0;j<book->dim;)
438        a[i++]=0.f;
439    }
440  }
441  return(0);
442}
443
444long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
445                              oggpack_buffer *b,int n){
446
447  long i,j,entry;
448  int chptr=0;
449  if(book->used_entries>0){
450    for(i=offset/ch;i<(offset+n)/ch;){
451      entry = decode_packed_entry_number(book,b);
452      if(entry==-1)return(-1);
453      {
454        const float *t = book->valuelist+entry*book->dim;
455        for (j=0;j<book->dim;j++){
456          a[chptr++][i]+=t[j];
457          if(chptr==ch){
458            chptr=0;
459            i++;
460          }
461        }
462      }
463    }
464  }
465  return(0);
466}
467