summaryrefslogtreecommitdiffhomepage
path: root/vorbis/lib/codebook.c
diff options
context:
space:
mode:
Diffstat (limited to 'vorbis/lib/codebook.c')
-rw-r--r--vorbis/lib/codebook.c461
1 files changed, 0 insertions, 461 deletions
diff --git a/vorbis/lib/codebook.c b/vorbis/lib/codebook.c
deleted file mode 100644
index 78672e2..0000000
--- a/vorbis/lib/codebook.c
+++ /dev/null
@@ -1,461 +0,0 @@
-/********************************************************************
- * *
- * THIS FILE IS PART OF THE OggVorbis SOFTWARE CODEC SOURCE CODE. *
- * 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. *
- * *
- * THE OggVorbis SOURCE CODE IS (C) COPYRIGHT 1994-2015 *
- * by the Xiph.Org Foundation http://www.xiph.org/ *
- * *
- ********************************************************************
-
- function: basic codebook pack/unpack/code/decode operations
-
- ********************************************************************/
-
-#include <stdlib.h>
-#include <string.h>
-#include <math.h>
-#include <ogg/ogg.h>
-#include "vorbis/codec.h"
-#include "codebook.h"
-#include "scales.h"
-#include "misc.h"
-#include "os.h"
-
-/* packs the given codebook into the bitstream **************************/
-
-int vorbis_staticbook_pack(const static_codebook *c,oggpack_buffer *opb){
- long i,j;
- int ordered=0;
-
- /* first the basic parameters */
- oggpack_write(opb,0x564342,24);
- oggpack_write(opb,c->dim,16);
- oggpack_write(opb,c->entries,24);
-
- /* pack the codewords. There are two packings; length ordered and
- length random. Decide between the two now. */
-
- for(i=1;i<c->entries;i++)
- if(c->lengthlist[i-1]==0 || c->lengthlist[i]<c->lengthlist[i-1])break;
- if(i==c->entries)ordered=1;
-
- if(ordered){
- /* length ordered. We only need to say how many codewords of
- each length. The actual codewords are generated
- deterministically */
-
- long count=0;
- oggpack_write(opb,1,1); /* ordered */
- oggpack_write(opb,c->lengthlist[0]-1,5); /* 1 to 32 */
-
- for(i=1;i<c->entries;i++){
- char this=c->lengthlist[i];
- char last=c->lengthlist[i-1];
- if(this>last){
- for(j=last;j<this;j++){
- oggpack_write(opb,i-count,ov_ilog(c->entries-count));
- count=i;
- }
- }
- }
- oggpack_write(opb,i-count,ov_ilog(c->entries-count));
-
- }else{
- /* length random. Again, we don't code the codeword itself, just
- the length. This time, though, we have to encode each length */
- oggpack_write(opb,0,1); /* unordered */
-
- /* algortihmic mapping has use for 'unused entries', which we tag
- here. The algorithmic mapping happens as usual, but the unused
- entry has no codeword. */
- for(i=0;i<c->entries;i++)
- if(c->lengthlist[i]==0)break;
-
- if(i==c->entries){
- oggpack_write(opb,0,1); /* no unused entries */
- for(i=0;i<c->entries;i++)
- oggpack_write(opb,c->lengthlist[i]-1,5);
- }else{
- oggpack_write(opb,1,1); /* we have unused entries; thus we tag */
- for(i=0;i<c->entries;i++){
- if(c->lengthlist[i]==0){
- oggpack_write(opb,0,1);
- }else{
- oggpack_write(opb,1,1);
- oggpack_write(opb,c->lengthlist[i]-1,5);
- }
- }
- }
- }
-
- /* is the entry number the desired return value, or do we have a
- mapping? If we have a mapping, what type? */
- oggpack_write(opb,c->maptype,4);
- switch(c->maptype){
- case 0:
- /* no mapping */
- break;
- case 1:case 2:
- /* implicitly populated value mapping */
- /* explicitly populated value mapping */
-
- if(!c->quantlist){
- /* no quantlist? error */
- return(-1);
- }
-
- /* values that define the dequantization */
- 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);
-
- {
- int quantvals;
- switch(c->maptype){
- case 1:
- /* 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;
- case 2:
- /* every value (c->entries*c->dim total) specified explicitly */
- quantvals=c->entries*c->dim;
- break;
- default: /* NOT_REACHABLE */
- quantvals=-1;
- }
-
- /* quantized values */
- for(i=0;i<quantvals;i++)
- oggpack_write(opb,labs(c->quantlist[i]),c->q_quant);
-
- }
- break;
- default:
- /* error case; we don't have any other map types now */
- return(-1);
- }
-
- return(0);
-}
-
-/* unpacks a codebook from the packet buffer into the codebook struct,
- readies the codebook auxiliary structures for decode *************/
-static_codebook *vorbis_staticbook_unpack(oggpack_buffer *opb){
- long i,j;
- static_codebook *s=_ogg_calloc(1,sizeof(*s));
- s->allocedp=1;
-
- /* make sure alignment is correct */
- if(oggpack_read(opb,24)!=0x564342)goto _eofout;
-
- /* first the basic parameters */
- s->dim=oggpack_read(opb,16);
- s->entries=oggpack_read(opb,24);
- if(s->entries==-1)goto _eofout;
-
- if(ov_ilog(s->dim)+ov_ilog(s->entries)>24)goto _eofout;
-
- /* codeword ordering.... length ordered or unordered? */
- switch((int)oggpack_read(opb,1)){
- 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;
- /* unordered */
- s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
-
- /* allocated but unused entries? */
- if(unused){
- /* yes, unused entries */
-
- for(i=0;i<s->entries;i++){
- 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;
- }
- }else{
- /* all entries used; no tagging */
- for(i=0;i<s->entries;i++){
- long num=oggpack_read(opb,5);
- if(num==-1)goto _eofout;
- s->lengthlist[i]=num+1;
- }
- }
-
- break;
- }
- case 1:
- /* ordered */
- {
- long length=oggpack_read(opb,5)+1;
- if(length==0)goto _eofout;
- s->lengthlist=_ogg_malloc(sizeof(*s->lengthlist)*s->entries);
-
- for(i=0;i<s->entries;){
- long num=oggpack_read(opb,ov_ilog(s->entries-i));
- if(num==-1)goto _eofout;
- if(length>32 || num>s->entries-i ||
- (num>0 && (num-1)>>(length-1)>1)){
- goto _errout;
- }
- if(length>32)goto _errout;
- for(j=0;j<num;j++,i++)
- s->lengthlist[i]=length;
- length++;
- }
- }
- break;
- default:
- /* EOF */
- goto _eofout;
- }
-
- /* Do we have a mapping to unpack? */
- switch((s->maptype=oggpack_read(opb,4))){
- case 0:
- /* no mapping */
- break;
- case 1: case 2:
- /* implicitly populated value mapping */
- /* explicitly populated value mapping */
-
- 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);
- if(s->q_sequencep==-1)goto _eofout;
-
- {
- int quantvals=0;
- switch(s->maptype){
- case 1:
- quantvals=(s->dim==0?0:_book_maptype1_quantvals(s));
- break;
- case 2:
- quantvals=s->entries*s->dim;
- break;
- }
-
- /* quantized values */
- if(((quantvals*s->q_quant+7)>>3)>opb->storage-oggpack_bytes(opb))
- goto _eofout;
- s->quantlist=_ogg_malloc(sizeof(*s->quantlist)*quantvals);
- for(i=0;i<quantvals;i++)
- s->quantlist[i]=oggpack_read(opb,s->q_quant);
-
- if(quantvals&&s->quantlist[quantvals-1]==-1)goto _eofout;
- }
- break;
- default:
- goto _errout;
- }
-
- /* all set */
- return(s);
-
- _errout:
- _eofout:
- vorbis_staticbook_destroy(s);
- return(NULL);
-}
-
-/* returns the number of bits ************************************************/
-int vorbis_book_encode(codebook *book, int a, oggpack_buffer *b){
- if(a<0 || a>=book->c->entries)return(0);
- oggpack_write(b,book->codelist[a],book->c->lengthlist[a]);
- return(book->c->lengthlist[a]);
-}
-
-/* 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);
-}
-
-STIN long decode_packed_entry_number(codebook *book, oggpack_buffer *b){
- int read=book->dec_maxlength;
- long lo,hi;
- long lok = oggpack_look(b,book->dec_firsttablen);
-
- if (lok >= 0) {
- long entry = book->dec_firsttable[lok];
- 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);
- }
- }else{
- lo=0;
- hi=book->used_entries;
- }
-
- /* 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 */
-
- lok = oggpack_look(b, read);
-
- while(lok<0 && read>1)
- lok = oggpack_look(b, --read);
- if(lok<0)return -1;
-
- /* bisect search for the codeword in the ordered list */
- {
- ogg_uint32_t testword=bitreverse((ogg_uint32_t)lok);
-
- while(hi-lo>1){
- long p=(hi-lo)>>1;
- long test=book->codelist[lo+p]>testword;
- lo+=p&(test-1);
- hi-=p&(-test);
- }
-
- if(book->dec_codelengths[lo]<=read){
- oggpack_adv(b, book->dec_codelengths[lo]);
- return(lo);
- }
- }
-
- oggpack_adv(b, read);
-
- return(-1);
-}
-
-/* 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':
-
- 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
- interleaving, it's easiest to do it here.
- addmul==0 -> declarative (set the value)
- addmul==1 -> additive
- addmul==2 -> multiplicitive */
-
-/* returns the [original, not compacted] entry number or -1 on eof *********/
-long vorbis_book_decode(codebook *book, oggpack_buffer *b){
- if(book->used_entries>0){
- long packed_entry=decode_packed_entry_number(book,b);
- if(packed_entry>=0)
- return(book->dec_index[packed_entry]);
- }
-
- /* if there's no dec_index, the codebook unpacking isn't collapsed */
- return(-1);
-}
-
-/* returns 0 on OK or -1 on eof *************************************/
-/* decode vector / dim granularity gaurding is done in the upper layer */
-long vorbis_book_decodevs_add(codebook *book,float *a,oggpack_buffer *b,int n){
- 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;
-
- 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;o+j<n && j<step;j++)
- a[o+j]+=t[j][i];
- }
- return(0);
-}
-
-/* decode vector / dim granularity gaurding is done in the upper layer */
-long vorbis_book_decodev_add(codebook *book,float *a,oggpack_buffer *b,int n){
- if(book->used_entries>0){
- int i,j,entry;
- float *t;
-
- for(i=0;i<n;){
- entry = decode_packed_entry_number(book,b);
- if(entry==-1)return(-1);
- t = book->valuelist+entry*book->dim;
- for(j=0;i<n && j<book->dim;)
- a[i++]+=t[j++];
- }
- }
- return(0);
-}
-
-/* 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) */
-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;
-
- for(i=0;i<n;){
- entry = decode_packed_entry_number(book,b);
- if(entry==-1)return(-1);
- t = book->valuelist+entry*book->dim;
- for (j=0;i<n && j<book->dim;){
- a[i++]=t[j++];
- }
- }
- }else{
- int i;
-
- for(i=0;i<n;){
- a[i++]=0.f;
- }
- }
- return(0);
-}
-
-long vorbis_book_decodevv_add(codebook *book,float **a,long offset,int ch,
- oggpack_buffer *b,int n){
-
- long i,j,entry;
- int chptr=0;
- if(book->used_entries>0){
- int m=(offset+n)/ch;
- for(i=offset/ch;i<m;){
- entry = decode_packed_entry_number(book,b);
- if(entry==-1)return(-1);
- {
- const float *t = book->valuelist+entry*book->dim;
- for (j=0;i<m && j<book->dim;j++){
- a[chptr++][i]+=t[j];
- if(chptr==ch){
- chptr=0;
- i++;
- }
- }
- }
- }
- }
- return(0);
-}