codebook.c 13.7 KB
Newer Older
Monty's avatar
 
Monty committed
1 2
/********************************************************************
 *                                                                  *
Monty's avatar
 
Monty committed
3
 * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE.   *
Monty's avatar
 
Monty committed
4 5 6
 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
Monty's avatar
 
Monty committed
7
 *                                                                  *
Ralph Giles's avatar
Ralph Giles committed
8
 * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2015             *
9
 * by the Xiph.Org Foundation http://www.xiph.org/                  *
10
 *                                                                  *
Monty's avatar
 
Monty committed
11 12 13 14 15 16 17
 ********************************************************************

 function: basic codebook pack/unpack/code/decode operations

 ********************************************************************/

#include <stdlib.h>
Monty's avatar
 
Monty committed
18
#include <string.h>
Monty's avatar
 
Monty committed
19
#include <math.h>
Monty's avatar
 
Monty committed
20
#include <ogg/ogg.h>
Monty's avatar
 
Monty committed
21
#include "vorbis/codec.h"
Monty's avatar
 
Monty committed
22
#include "codebook.h"
Monty's avatar
 
Monty committed
23
#include "scales.h"
Monty's avatar
 
Monty committed
24
#include "misc.h"
Monty's avatar
 
Monty committed
25
#include "os.h"
Monty's avatar
 
Monty committed
26

Monty's avatar
 
Monty committed
27 28
/* packs the given codebook into the bitstream **************************/

Monty's avatar
 
Monty committed
29
int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
Monty's avatar
 
Monty committed
30 31 32 33
  long i,j;
  int ordered=0;

  /* first the basic parameters */
Monty's avatar
 
Monty committed
34 35 36
  oggpack_write(opb,0x564342,24);
  oggpack_write(opb,c->dim,16);
  oggpack_write(opb,c->entries,24);
Monty's avatar
 
Monty committed
37 38 39

  /* pack the codewords.  There are two packings; length ordered and
     length random.  Decide between the two now. */
Monty's avatar
Monty committed
40

Monty's avatar
 
Monty committed
41
  for(i=1;i<c->entries;i++)
Monty's avatar
 
Monty committed
42
    if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break;
Monty's avatar
 
Monty committed
43
  if(i==c->entries)ordered=1;
Monty's avatar
Monty committed
44

Monty's avatar
 
Monty committed
45 46 47 48 49 50
  if(ordered){
    /* length ordered.  We only need to say how many codewords of
       each length.  The actual codewords are generated
       deterministically */

    long count=0;
Monty's avatar
 
Monty committed
51 52
    oggpack_write(opb,1,1);  /* ordered */
    oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
Monty's avatar
 
Monty committed
53 54

    for(i=1;i<c->entries;i++){
55 56
      char this=c->lengthlist[i];
      char last=c->lengthlist[i-1];
Monty's avatar
 
Monty committed
57
      if(this>last){
58
        for(j=last;j<this;j++){
59
          oggpack_write(opb,i-count,ov_ilog(c->entries-count));
60 61
          count=i;
        }
Monty's avatar
 
Monty committed
62 63
      }
    }
64
    oggpack_write(opb,i-count,ov_ilog(c->entries-count));
Monty's avatar
Monty committed
65

Monty's avatar
 
Monty committed
66 67 68
  }else{
    /* length random.  Again, we don't code the codeword itself, just
       the length.  This time, though, we have to encode each length */
Monty's avatar
 
Monty committed
69
    oggpack_write(opb,0,1);   /* unordered */
Monty's avatar
Monty committed
70

Monty's avatar
 
Monty committed
71 72 73
    /* algortihmic mapping has use for 'unused entries', which we tag
       here.  The algorithmic mapping happens as usual, but the unused
       entry has no codeword. */
Monty's avatar
 
Monty committed
74
    for(i=0;i<c->entries;i++)
Monty's avatar
 
Monty committed
75 76 77
      if(c->lengthlist[i]==0)break;

    if(i==c->entries){
Monty's avatar
 
Monty committed
78
      oggpack_write(opb,0,1); /* no unused entries */
Monty's avatar
 
Monty committed
79
      for(i=0;i<c->entries;i++)
80
        oggpack_write(opb,c->lengthlist[i]-1,5);
Monty's avatar
 
Monty committed
81
    }else{
Monty's avatar
 
Monty committed
82
      oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
Monty's avatar
 
Monty committed
83
      for(i=0;i<c->entries;i++){
84 85 86 87 88 89
        if(c->lengthlist[i]==0){
          oggpack_write(opb,0,1);
        }else{
          oggpack_write(opb,1,1);
          oggpack_write(opb,c->lengthlist[i]-1,5);
        }
Monty's avatar
 
Monty committed
90 91
      }
    }
Monty's avatar
 
Monty committed
92 93 94
  }

  /* is the entry number the desired return value, or do we have a
Monty's avatar
 
Monty committed
95
     mapping? If we have a mapping, what type? */
Monty's avatar
 
Monty committed
96
  oggpack_write(opb,c->maptype,4);
Monty's avatar
 
Monty committed
97 98 99 100 101 102 103
  switch(c->maptype){
  case 0:
    /* no mapping */
    break;
  case 1:case 2:
    /* implicitly populated value mapping */
    /* explicitly populated value mapping */
Monty's avatar
Monty committed
104

Monty's avatar
 
Monty committed
105 106 107 108
    if(!c->quantlist){
      /* no quantlist?  error */
      return(-1);
    }
Monty's avatar
Monty committed
109

Monty's avatar
 
Monty committed
110
    /* values that define the dequantization */
Monty's avatar
 
Monty committed
111 112 113 114
    oggpack_write(opb,c->q_min,32);
    oggpack_write(opb,c->q_delta,32);
    oggpack_write(opb,c->q_quant-1,4);
    oggpack_write(opb,c->q_sequencep,1);
Monty's avatar
Monty committed
115

Monty's avatar
 
Monty committed
116 117 118 119
    {
      int quantvals;
      switch(c->maptype){
      case 1:
120 121 122 123
        /* a single column of (c->entries/c->dim) quantized values for
           building a full value list algorithmically (square lattice) */
        quantvals=_book_maptype1_quantvals(c);
        break;
Monty's avatar
 
Monty committed
124
      case 2:
125 126 127
        /* every value (c->entries*c->dim total) specified explicitly */
        quantvals=c->entries*c->dim;
        break;
Monty's avatar
 
Monty committed
128
      default: /* NOT_REACHABLE */
129
        quantvals=-1;
Monty's avatar
 
Monty committed
130
      }
Monty's avatar
 
Monty committed
131

Monty's avatar
 
Monty committed
132 133
      /* quantized values */
      for(i=0;i<quantvals;i++)
134
        oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
Monty's avatar
 
Monty committed
135

Monty's avatar
 
Monty committed
136 137 138 139 140
    }
    break;
  default:
    /* error case; we don't have any other map types now */
    return(-1);
Monty's avatar
 
Monty committed
141
  }
Monty's avatar
 
Monty committed
142

Monty's avatar
 
Monty committed
143 144 145 146 147
  return(0);
}

/* unpacks a codebook from the packet buffer into the codebook struct,
   readies the codebook auxiliary structures for decode *************/
148
static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
Monty's avatar
 
Monty committed
149
  long i,j;
150
  static_codebook *s=_ogg_calloc(1,sizeof(*s));
Monty's avatar
 
Monty committed
151
  s->allocedp=1;
Monty's avatar
 
Monty committed
152 153

  /* make sure alignment is correct */
Monty's avatar
 
Monty committed
154
  if(oggpack_read(opb,24)!=0x564342)goto _eofout;
Monty's avatar
 
Monty committed
155 156

  /* first the basic parameters */
Monty's avatar
 
Monty committed
157 158
  s->dim=oggpack_read(opb,16);
  s->entries=oggpack_read(opb,24);
Monty's avatar
 
Monty committed
159
  if(s->entries==-1)goto _eofout;
Monty's avatar
 
Monty committed
160

161
  if(ov_ilog(s->dim)+ov_ilog(s->entries)>24)goto _eofout;
162

Monty's avatar
 
Monty committed
163
  /* codeword ordering.... length ordered or unordered? */
164
  switch((int)oggpack_read(opb,1)){
165 166 167 168 169 170
  case 0:{
    long unused;
    /* allocated but unused entries? */
    unused=oggpack_read(opb,1);
    if((s->entries*(unused?1:5)+7)>>3>opb->storage-oggpack_bytes(opb))
      goto _eofout;
Monty's avatar
 
Monty committed
171
    /* unordered */
172
    s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
Monty's avatar
 
Monty committed
173 174

    /* allocated but unused entries? */
175
    if(unused){
Monty's avatar
 
Monty committed
176 177 178
      /* yes, unused entries */

      for(i=0;i<s->entries;i++){
179 180 181 182 183 184
        if(oggpack_read(opb,1)){
          long num=oggpack_read(opb,5);
          if(num==-1)goto _eofout;
          s->lengthlist[i]=num+1;
        }else
          s->lengthlist[i]=0;
Monty's avatar
 
Monty committed
185 186 187 188
      }
    }else{
      /* all entries used; no tagging */
      for(i=0;i<s->entries;i++){
189 190 191
        long num=oggpack_read(opb,5);
        if(num==-1)goto _eofout;
        s->lengthlist[i]=num+1;
Monty's avatar
 
Monty committed
192
      }
Monty's avatar
 
Monty committed
193
    }
Monty's avatar
Monty committed
194

Monty's avatar
 
Monty committed
195
    break;
196
  }
Monty's avatar
 
Monty committed
197 198 199
  case 1:
    /* ordered */
    {
Monty's avatar
 
Monty committed
200
      long length=oggpack_read(opb,5)+1;
201
      if(length==0)goto _eofout;
202
      s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
Monty's avatar
 
Monty committed
203

Monty's avatar
 
Monty committed
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 208 209 210
        if(length>32 || num>s->entries-i ||
           (num>0 && (num-1)>>(length-1)>1)){
          goto _errout;
        }
211
        if(length>32)goto _errout;
212
        for(j=0;j<num;j++,i++)
213 214
          s->lengthlist[i]=length;
        length++;
Monty's avatar
 
Monty committed
215 216 217 218 219
      }
    }
    break;
  default:
    /* EOF */
220
    goto _eofout;
Monty's avatar
 
Monty committed
221
  }
Monty's avatar
Monty committed
222

Monty's avatar
 
Monty committed
223
  /* Do we have a mapping to unpack? */
Monty's avatar
 
Monty committed
224
  switch((s->maptype=oggpack_read(opb,4))){
Monty's avatar
 
Monty committed
225 226 227 228 229 230
  case 0:
    /* no mapping */
    break;
  case 1: case 2:
    /* implicitly populated value mapping */
    /* explicitly populated value mapping */
Monty's avatar
 
Monty committed
231

Monty's avatar
 
Monty committed
232 233 234 235
    s->q_min=oggpack_read(opb,32);
    s->q_delta=oggpack_read(opb,32);
    s->q_quant=oggpack_read(opb,4)+1;
    s->q_sequencep=oggpack_read(opb,1);
236
    if(s->q_sequencep==-1)goto _eofout;
Monty's avatar
 
Monty committed
237

Monty's avatar
 
Monty committed
238
    {
239
      int quantvals=0;
Monty's avatar
 
Monty committed
240 241
      switch(s->maptype){
      case 1:
242 243
        quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
        break;
Monty's avatar
 
Monty committed
244
      case 2:
245 246
        quantvals=s->entries*s->dim;
        break;
Monty's avatar
 
Monty committed
247
      }
Monty's avatar
Monty committed
248

Monty's avatar
 
Monty committed
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);
Monty's avatar
 
Monty committed
253
      for(i=0;i<quantvals;i++)
254
        s->quantlist[i]=oggpack_read(opb,s->q_quant);
Monty's avatar
Monty committed
255

256
      if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
Monty's avatar
 
Monty committed
257 258 259 260
    }
    break;
  default:
    goto _errout;
Monty's avatar
 
Monty committed
261 262 263
  }

  /* all set */
264
  return(s);
Monty's avatar
Monty committed
265

Monty's avatar
 
Monty committed
266 267
 _errout:
 _eofout:
268 269
  vorbis_staticbook_destroy(s);
  return(NULL);
Monty's avatar
 
Monty committed
270 271
}

Monty's avatar
 
Monty committed
272
/* returns the number of bits ************************************************/
Monty's avatar
 
Monty committed
273
int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
274
  if(a<0 || a>=book->c->entries)return(0);
Monty's avatar
 
Monty committed
275
  oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
Monty's avatar
 
Monty committed
276
  return(book->c->lengthlist[a]);
Monty's avatar
 
Monty committed
277 278
}

Monty's avatar
 
Monty committed
279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294
/* the 'eliminate the decode tree' optimization actually requires the
   codewords to be MSb first, not LSb.  This is an annoying inelegancy
   (and one of the first places where carefully thought out design
   turned out to be wrong; Vorbis II and future Ogg codecs should go
   to an MSb bitpacker), but not actually the huge hit it appears to
   be.  The first-stage decode table catches most words so that
   bitreverse is not in the main execution path. */

static ogg_uint32_t bitreverse(ogg_uint32_t x){
  x=    ((x>>16)&0x0000ffff) | ((x<<16)&0xffff0000);
  x=    ((x>> 8)&0x00ff00ff) | ((x<< 8)&0xff00ff00);
  x=    ((x>> 4)&0x0f0f0f0f) | ((x<< 4)&0xf0f0f0f0);
  x=    ((x>> 2)&0x33333333) | ((x<< 2)&0xcccccccc);
  return((x>> 1)&0x55555555) | ((x<< 1)&0xaaaaaaaa);
}

Monty's avatar
 
Monty committed
295
STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
Monty's avatar
 
Monty committed
296 297
  int  read=book->dec_maxlength;
  long lo,hi;
Monty's avatar
 
Monty committed
298
  long lok = oggpack_look(b,book->dec_firsttablen);
Monty's avatar
Monty committed
299

Monty's avatar
 
Monty committed
300 301
  if (lok >= 0) {
    long entry = book->dec_firsttable[lok];
Monty's avatar
 
Monty committed
302 303 304 305 306 307
    if(entry&0x80000000UL){
      lo=(entry>>15)&0x7fff;
      hi=book->used_entries-(entry&0x7fff);
    }else{
      oggpack_adv(b, book->dec_codelengths[entry-1]);
      return(entry-1);
Monty's avatar
 
Monty committed
308
    }
Monty's avatar
 
Monty committed
309 310 311
  }else{
    lo=0;
    hi=book->used_entries;
Monty's avatar
 
Monty committed
312
  }
Monty's avatar
Monty committed
313

314 315 316 317 318 319
  /* Single entry codebooks use a firsttablen of 1 and a
     dec_maxlength of 1.  If a single-entry codebook gets here (due to
     failure to read one bit above), the next look attempt will also
     fail and we'll correctly kick out instead of trying to walk the
     underformed tree */

Monty's avatar
 
Monty committed
320
  lok = oggpack_look(b, read);
Monty's avatar
Monty committed
321

Monty's avatar
 
Monty committed
322 323 324
  while(lok<0 && read>1)
    lok = oggpack_look(b, --read);
  if(lok<0)return -1;
Monty's avatar
Monty committed
325

Monty's avatar
 
Monty committed
326 327 328
  /* bisect search for the codeword in the ordered list */
  {
    ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
Monty's avatar
Monty committed
329

Monty's avatar
 
Monty committed
330
    while(hi-lo>1){
Monty's avatar
 
Monty committed
331
      long p=(hi-lo)>>1;
Monty's avatar
Monty committed
332
      long test=book->codelist[lo+p]>testword;
Monty's avatar
 
Monty committed
333 334
      lo+=p&(test-1);
      hi-=p&(-test);
335
      }
Monty's avatar
Monty committed
336

Monty's avatar
 
Monty committed
337 338 339
    if(book->dec_codelengths[lo]<=read){
      oggpack_adv(b, book->dec_codelengths[lo]);
      return(lo);
Monty's avatar
 
Monty committed
340 341
    }
  }
Monty's avatar
Monty committed
342

Monty's avatar
 
Monty committed
343
  oggpack_adv(b, read);
344

Monty's avatar
 
Monty committed
345 346 347
  return(-1);
}

Monty's avatar
 
Monty committed
348 349 350
/* Decode side is specced and easier, because we don't need to find
   matches using different criteria; we simply read and map.  There are
   two things we need to do 'depending':
Monty's avatar
Monty committed
351

Monty's avatar
 
Monty committed
352 353 354 355 356
   We may need to support interleave.  We don't really, but it's
   convenient to do it here rather than rebuild the vector later.

   Cascades may be additive or multiplicitive; this is not inherent in
   the codebook, but set in the code using the codebook.  Like
Monty's avatar
Monty committed
357
   interleaving, it's easiest to do it here.
Monty's avatar
 
Monty committed
358 359 360
   addmul==0 -> declarative (set the value)
   addmul==1 -> additive
   addmul==2 -> multiplicitive */
Monty's avatar
 
Monty committed
361

Monty's avatar
 
Monty committed
362
/* returns the [original, not compacted] entry number or -1 on eof *********/
Monty's avatar
 
Monty committed
363
long vorbis_book_decode(codebook *book, oggpack_buffer *b){
364 365 366 367 368 369
  if(book->used_entries>0){
    long packed_entry=decode_packed_entry_number(book,b);
    if(packed_entry>=0)
      return(book->dec_index[packed_entry]);
  }

Monty's avatar
 
Monty committed
370
  /* if there's no dec_index, the codebook unpacking isn't collapsed */
371
  return(-1);
Monty's avatar
 
Monty committed
372 373
}

Monty's avatar
 
Monty committed
374
/* returns 0 on OK or -1 on eof *************************************/
375
/* decode vector / dim granularity gaurding is done in the upper layer */
Monty's avatar
 
Monty committed
376
long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
377 378 379 380 381
  if(book->used_entries>0){
    int step=n/book->dim;
    long *entry = alloca(sizeof(*entry)*step);
    float **t = alloca(sizeof(*t)*step);
    int i,j,o;
Monty's avatar
Monty committed
382

383 384 385 386 387 388 389
    for (i = 0; i < step; i++) {
      entry[i]=decode_packed_entry_number(book,b);
      if(entry[i]==-1)return(-1);
      t[i] = book->valuelist+entry[i]*book->dim;
    }
    for(i=0,o=0;i<book->dim;i++,o+=step)
      for (j=0;j<step;j++)
390
        a[o+j]+=t[j][i];
Monty's avatar
 
Monty committed
391 392
  }
  return(0);
Monty's avatar
 
Monty committed
393 394
}

395
/* decode vector / dim granularity gaurding is done in the upper layer */
Monty's avatar
 
Monty committed
396
long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
397 398 399
  if(book->used_entries>0){
    int i,j,entry;
    float *t;
Monty's avatar
Monty committed
400

401 402
    if(book->dim>8){
      for(i=0;i<n;){
403 404 405 406 407
        entry = decode_packed_entry_number(book,b);
        if(entry==-1)return(-1);
        t     = book->valuelist+entry*book->dim;
        for (j=0;j<book->dim;)
          a[i++]+=t[j++];
408 409 410
      }
    }else{
      for(i=0;i<n;){
411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434
        entry = decode_packed_entry_number(book,b);
        if(entry==-1)return(-1);
        t     = book->valuelist+entry*book->dim;
        j=0;
        switch((int)book->dim){
        case 8:
          a[i++]+=t[j++];
        case 7:
          a[i++]+=t[j++];
        case 6:
          a[i++]+=t[j++];
        case 5:
          a[i++]+=t[j++];
        case 4:
          a[i++]+=t[j++];
        case 3:
          a[i++]+=t[j++];
        case 2:
          a[i++]+=t[j++];
        case 1:
          a[i++]+=t[j++];
        case 0:
          break;
        }
435
      }
Monty's avatar
Monty committed
436
    }
437 438 439
  }
  return(0);
}
Monty's avatar
 
Monty committed
440

441 442 443
/* unlike the others, we guard against n not being an integer number
   of <dim> internally rather than in the upper layer (called only by
   floor0) */
444 445 446 447
long vorbis_book_decodev_set(codebook *book,float *a,oggpack_buffer *b,int n){
  if(book->used_entries>0){
    int i,j,entry;
    float *t;
Monty's avatar
Monty committed
448

Monty's avatar
 
Monty committed
449
    for(i=0;i<n;){
Monty's avatar
 
Monty committed
450
      entry = decode_packed_entry_number(book,b);
Monty's avatar
 
Monty committed
451 452
      if(entry==-1)return(-1);
      t     = book->valuelist+entry*book->dim;
453
      for (j=0;i<n && j<book->dim;){
454
        a[i++]=t[j++];
455
      }
Monty's avatar
 
Monty committed
456
    }
Monty's avatar
 
Monty committed
457
  }else{
Timothy B. Terriberry's avatar
Timothy B. Terriberry committed
458
    int i;
Monty's avatar
Monty committed
459

Monty's avatar
 
Monty committed
460
    for(i=0;i<n;){
461
      a[i++]=0.f;
Monty's avatar
 
Monty committed
462
    }
Monty's avatar
 
Monty committed
463 464 465 466 467
  }
  return(0);
}

long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
468
                              oggpack_buffer *b,int n){
469

Monty's avatar
 
Monty committed
470
  long i,j,entry;
Monty's avatar
 
Monty committed
471
  int chptr=0;
472 473 474 475 476
  if(book->used_entries>0){
    for(i=offset/ch;i<(offset+n)/ch;){
      entry = decode_packed_entry_number(book,b);
      if(entry==-1)return(-1);
      {
477 478 479 480 481 482 483 484
        const float *t = book->valuelist+entry*book->dim;
        for (j=0;j<book->dim;j++){
          a[chptr++][i]+=t[j];
          if(chptr==ch){
            chptr=0;
            i++;
          }
        }
Monty's avatar
 
Monty committed
485
      }
Monty's avatar
 
Monty committed
486 487 488 489
    }
  }
  return(0);
}