Add RCS ID tags en masse
[platform/upstream/libvorbis.git] / lib / framing.c
1 /********************************************************************
2  *                                                                  *
3  * THIS FILE IS PART OF THE Ogg Vorbis SOFTWARE CODEC SOURCE CODE.  *
4  * USE, DISTRIBUTION AND REPRODUCTION OF THIS SOURCE IS GOVERNED BY *
5  * THE GNU PUBLIC LICENSE 2, WHICH IS INCLUDED WITH THIS SOURCE.    *
6  * PLEASE READ THESE TERMS DISTRIBUTING.                            *
7  *                                                                  *
8  * THE OggSQUISH SOURCE CODE IS (C) COPYRIGHT 1994-1999             *
9  * by 1999 Monty <monty@xiph.org> and The XIPHOPHORUS Company       *
10  * http://www.xiph.org/                                             *
11  *                                                                  *
12  ********************************************************************
13
14  function: code raw Vorbis packets into framed vorbis stream and
15            decode vorbis streams back into raw packets
16  author: Monty <xiphmont@mit.edu>
17  modifications by: Monty
18  last modification date: Jul 10 1999
19
20  note: The CRC code is directly derived from public domain code by
21  Ross Williams (ross@guest.adelaide.edu.au).  See framing.txt for
22  details.
23
24  ********************************************************************/
25
26 static const char rcsid[] = "$Id";
27
28 #include <stdlib.h>
29 #include <string.h>
30 #include "codec.h"
31
32 /* A complete description of Vorbis framing exists in docs/framing.txt */
33
34 /* helper to initialize lookup for direct-table CRC */
35 static unsigned size32 _vorbis_crc_entry(unsigned long index){
36   int           i;
37   unsigned long r;
38
39   r = index << 24;
40   for (i=0; i<8; i++)
41     if (r & 0x80000000UL)
42       r = (r << 1) ^ 0x04c11db7; /* The same as the ethernet generator
43                                     polynomial, although we use an
44                                     unreflected alg and an init/final
45                                     of 0, not 0xffffffff */
46     else
47        r<<=1;
48  return (r & 0xffffffffUL);
49 }
50
51 int vorbis_stream_init(vorbis_stream_state *vs,int serialno){
52   int i;
53   if(vs){
54     memset(vs,0,sizeof(vorbis_stream_state));
55     vs->body_storage=16*1024;
56     vs->body_data=malloc(vs->body_storage*sizeof(char));
57
58     vs->lacing_storage=1024;
59     vs->lacing_vals=malloc(vs->lacing_storage*sizeof(int));
60     vs->pcm_vals=malloc(vs->lacing_storage*sizeof(size64));
61
62     /* initialize the crc_lookup table */
63     for (i=0;i<256;i++)
64       vs->crc_lookup[i]=_vorbis_crc_entry((unsigned long)i);
65
66     vs->serialno=serialno;
67
68     return(0);
69   }
70   return(-1);
71
72
73 /* _clear does not free vs, only the non-flat storage within */
74 int vorbis_stream_clear(vorbis_stream_state *vs){
75   if(vs){
76     if(vs->body_data)free(vs->body_data);
77     if(vs->lacing_vals)free(vs->lacing_vals);
78     if(vs->pcm_vals)free(vs->pcm_vals);
79
80     memset(vs,0,sizeof(vorbis_stream_state));    
81   }
82   return(0);
83
84
85 int vorbis_stream_destroy(vorbis_stream_state *vs){
86   if(vs){
87     vorbis_stream_clear(vs);
88     free(vs);
89   }
90   return(0);
91
92
93 /* Helpers for vorbis_stream_encode; this keeps the structure and
94    what's happening fairly clear */
95
96 /* checksum the page */
97 /* Direct table CRC; note that this will be faster in the future if we
98    perform the checksum silmultaneously with other copies */
99
100 static void _vs_checksum(vorbis_stream_state *vs,vorbis_page *vg){
101   unsigned size32 crc_reg=0;
102   unsigned size32 *lookup=vs->crc_lookup;
103   int i;
104
105   for(i=0;i<vg->header_len;i++)
106     crc_reg=(crc_reg<<8)^lookup[((crc_reg >> 24)&0xff)^vg->header[i]];
107   for(i=0;i<vg->body_len;i++)
108     crc_reg=(crc_reg<<8)^lookup[((crc_reg >> 24)&0xff)^vg->body[i]];
109   
110   vg->header[22]=crc_reg&0xff;
111   vg->header[23]=(crc_reg>>8)&0xff;
112   vg->header[24]=(crc_reg>>16)&0xff;
113   vg->header[25]=(crc_reg>>24)&0xff;
114 }
115
116 /* submit data to the internal buffer of the framing engine */
117 int vorbis_stream_encode(vorbis_stream_state *vs,vorbis_packet *vp){
118   int lacing_vals=vp->bytes/255+1,i;
119
120   /* make sure we have the buffer storage */
121   if(vs->body_storage<=vs->body_fill+vp->bytes){
122     vs->body_storage+=(vp->bytes+1024);
123     vs->body_data=realloc(vs->body_data,vs->body_storage);
124   }
125   if(vs->lacing_storage<=vs->lacing_fill+lacing_vals){
126     vs->lacing_storage+=(lacing_vals+32);
127     vs->lacing_vals=realloc(vs->lacing_vals,vs->lacing_storage*sizeof(int));
128     vs->pcm_vals=realloc(vs->pcm_vals,vs->lacing_storage*sizeof(size64));
129   }
130
131   /* Copy in the submitted packet.  Yes, the copy is a waste; this is
132      the liability of overly clean abstraction for the time being.  It
133      will actually be fairly easy to eliminate the extra copy in the
134      future */
135
136   memcpy(vs->body_data+vs->body_fill,vp->packet,vp->bytes);
137   vs->body_fill+=vp->bytes;
138
139   /* Store lacing vals for this packet */
140   for(i=0;i<lacing_vals-1;i++){
141     vs->lacing_vals[vs->lacing_fill+i]=255;
142     vs->pcm_vals[vs->lacing_fill+i]=vp->pcm_pos;
143   }
144   vs->lacing_vals[vs->lacing_fill+i]=(vp->bytes)%255;
145   vs->pcm_vals[vs->lacing_fill+i]=vp->pcm_pos;
146
147   /* flag the first segment as the beginning of the packet */
148   vs->lacing_vals[vs->lacing_fill]|= 0x100;
149
150   vs->lacing_fill+=lacing_vals;
151
152   if(vp->e_o_s)vs->e_o_s=1;
153
154   return(0);
155 }
156
157 /* This constructs pages from buffered packet segments.  The pointers
158 returned are to static buffers; do not free. The returned buffers are
159 good only until the next call (using the same vs) */
160
161 int vorbis_stream_page(vorbis_stream_state *vs, vorbis_page *vg){
162   int i;
163
164   if(vs->body_returned){
165     /* advance packet data according to the body_returned pointer. We
166        had to keep it around to return a pointer into the buffer last
167        call */
168
169     vs->body_fill-=vs->body_returned;
170     memmove(vs->body_data,vs->body_data+vs->body_returned,
171             vs->body_fill*sizeof(char));
172     vs->body_returned=0;
173   }
174
175   if((vs->e_o_s&&vs->lacing_fill) || 
176      vs->body_fill > 4096 || 
177      vs->lacing_fill>=255){
178     int vals=0,bytes=0;
179     int maxvals=(vs->lacing_fill>255?255:vs->lacing_fill);
180     long acc=0;
181
182     /* construct a page */
183     /* decide how many segments to include */
184     for(vals=0;vals<maxvals;vals++){
185       if(acc>4096)break;
186       acc+=vs->lacing_vals[vals]&0x0ff;
187     }
188
189     /* construct the header in temp storage */
190     memcpy(vs->header,"OggS",4);
191
192     /* stream structure version */
193     vs->header[4]=0x00;
194
195     if(vs->b_o_s==0){ 
196       /* Ah, this is the first page */
197       vs->header[5]=0x00;
198     }else{
199       if(vs->lacing_vals[0]&0x100){
200         /* The first packet segment is the beginning of a packet */
201         vs->header[5]=0x01;
202       }else{
203         vs->header[5]=0x02;
204       }
205     }
206     vs->b_o_s=1;
207
208     /* 64 bits of PCM position */
209     {
210       size64 pcm_pos=vs->pcm_vals[vals-1];
211
212       for(i=6;i<14;i++){
213         vs->header[i]=(pcm_pos&0xff);
214         pcm_pos>>=8;
215       }
216     }
217
218     /* 32 bits of stream serial number */
219     {
220       long serialno=vs->serialno;
221       for(i=14;i<18;i++){
222         vs->header[i]=(serialno&0xff);
223         serialno>>=8;
224       }
225     }
226
227     /* 32 bits of page counter (we have both counter and page header
228        because this val can roll over) */
229     {
230       long pageno=vs->pageno++;
231       for(i=18;i<22;i++){
232         vs->header[i]=(pageno&0xff);
233         pageno>>=8;
234       }
235     }
236
237     /* zero for computation; filled in later */
238     vs->header[22]=0;
239     vs->header[23]=0;
240     vs->header[24]=0;
241     vs->header[25]=0;
242
243     /* segment table */
244     vs->header[26]=vals&0xff;
245     for(i=0;i<vals;i++)
246       bytes+=vs->header[i+27]=(vs->lacing_vals[i]&0xff);
247       
248     /* advance the lacing data and set the body_returned pointer */
249
250     vs->lacing_fill-=vals;
251     memmove(vs->lacing_vals,vs->lacing_vals+vals,vs->lacing_fill*sizeof(int));
252     memmove(vs->pcm_vals,vs->pcm_vals+vals,vs->lacing_fill*sizeof(size64));
253     vs->body_returned=bytes;
254
255     /* set pointers in the vorbis_page struct */
256     vg->header=vs->header;
257     vg->header_len=vs->headerbytes=vals+27;
258     vg->body=vs->body_data;
259     vg->body_len=bytes;
260
261     /* calculate the checksum */
262
263     _vs_checksum(vs,vg);
264
265     return(1);
266   }
267
268   /* not enough data to construct a page and not end of stream */
269   return(0);
270 }
271
272 int vorbis_stream_eof(vorbis_stream_state *vs){
273   return vs->e_o_s;
274 }
275
276 /* DECODING PRIMITIVES: packet streaming layer **********************/
277
278 /* Accepts data for decoding; syncs and frames the bitstream, then
279    decodes pages into packets.  Works through errors and dropouts,
280    reporting holes/errors in the bitstream when the missing/corrupt
281    packet is requested by vorbis_stream_packet(). Call with size=-1
282    for EOS */
283
284 /* all below:  <0 error, 0 not enough data, >0 success */
285
286 int vorbis_stream_decode(vorbis_stream_state *vs,char *stream,int size){
287   /* beginning a page? ie, no header started yet?*/
288   if vs->
289   
290   
291
292
293 }
294
295 size64 vorbis_stream_pcmpos(vorbis_stream_state *vs){
296 }
297
298 size64 vorbis_stream_pageno(vorbis_stream_state *vs){
299 }
300
301 int vorbis_stream_skippage(vorbis_stream_state *vs){
302 }
303
304 int vorbis_stream_clearbuf(vorbis_stream_state *vs){
305 }
306
307 int vorbis_stream_packet(vorbis_stream_state *vs,vorbis_packet *vp){
308 }
309
310 #ifdef _V_SELFTEST
311 #include <stdio.h>
312
313 void test_pack(vorbis_stream_state *vs,int *pl, int **headers){
314   unsigned char *data=malloc(1024*1024); /* for scripted test cases only */
315   long inptr=0;
316   long outptr=0;
317   long pcm_pos=0;
318   int i,j,packets,pageno=0;
319
320   for(packets=0;;packets++)if(pl[packets]==-1)break;
321
322   for(i=0;i<packets;i++){
323     /* construct a test packet */
324     vorbis_packet vp;
325     int len=pl[i];
326     
327     vp.packet=data+inptr;
328     vp.bytes=len;
329     vp.e_o_s=(pl[i+1]<0?1:0);
330     vp.pcm_pos=pcm_pos;
331
332     pcm_pos+=1024;
333
334     for(j=0;j<len;j++)data[inptr++]=i+j;
335
336     /* submit the test packet */
337     vorbis_stream_encode(vs,&vp);
338
339     /* retrieve any finished pages */
340     {
341       vorbis_page vg;
342       
343       while(vorbis_stream_page(vs,&vg)){
344         /* We have a page.  Check it carefully */
345
346         fprintf(stderr,"%d, ",pageno);
347
348         if(headers[pageno]==NULL){
349           fprintf(stderr,"coded too many pages!\n");
350           exit(1);
351         }
352
353         /* Test data */
354         for(j=0;j<vg.body_len;j++)
355         if(vg.body[j]!=(data+outptr)[j]){
356           fprintf(stderr,"body data mismatch at pos %ld: %x!=%x!\n\n",
357                   outptr+j,(data+outptr)[j],vg.body[j]);
358           exit(1);
359         }
360         outptr+=vg.body_len;
361
362         /* Test header */
363         for(j=0;j<vg.header_len;j++){
364           if(vg.header[j]!=headers[pageno][j]){
365             fprintf(stderr,"header content mismatch at pos %ld:\n",j);
366             for(j=0;j<headers[pageno][26]+27;j++)
367               fprintf(stderr," (%d)%02x:%02x",j,headers[pageno][j],vg.header[j]);
368             fprintf(stderr,"\n");
369             exit(1);
370           }
371         }
372         if(vg.header_len!=headers[pageno][26]+27){
373           fprintf(stderr,"header length incorrect! (%ld!=%d)\n",
374                   vg.header_len,headers[pageno][26]+27);
375           exit(1);
376         }
377         pageno++;
378       }
379     }
380   }
381   free(data);
382   if(headers[pageno]!=NULL){
383     fprintf(stderr,"did not write last page!\n");
384     exit(1);
385   }
386   if(inptr!=outptr){
387     fprintf(stderr,"packet data incomplete!\n");
388     exit(1);
389   }
390   fprintf(stderr,"ok.\n");
391 }
392
393 int main(void){
394   vorbis_stream_state vs;
395
396   /* Exercise each code path in the framing code.  Also verify that
397      the checksums are working.  */
398
399   {
400     /* 17, 254, 255, 256, 500, 510, 600 byte, pad */
401     int packets[]={17, 254, 255, 256, 500, 510, 600, -1};
402     int head1[] = {0x4f,0x67,0x67,0x53,0,0,
403                    0x00,0x18,0x00,0x00,0x00,0x00,0x00,0x00,
404                    0x01,0x02,0x03,0x04,0,0,0,0,
405                    0x7e,0xea,0x18,0xd0,
406                    14,
407                    17,254,255,0,255,1,255,245,255,255,0,
408                    255,255,90};
409     int *headret[]={head1,NULL};
410     
411     vorbis_stream_init(&vs,0x04030201);
412     fprintf(stderr,"testing basic page encoding... ");
413     test_pack(&vs,packets,headret);
414     vorbis_stream_clear(&vs);
415   }
416
417   {
418     /* nil packets; beginning,middle,end */
419     int packets[]={0,17, 254, 255, 0, 256, 0, 500, 510, 600, 0, -1};
420
421     int head1[] = {0x4f,0x67,0x67,0x53,0,0,
422                    0x00,0x28,0x00,0x00,0x00,0x00,0x00,0x00,
423                    0x01,0x02,0x03,0x04,0,0,0,0,
424                    0xcf,0x70,0xa4,0x1b,
425                    18,
426                    0,17,254,255,0,0,255,1,0,255,245,255,255,0,
427                    255,255,90,0};
428     int *headret[]={head1,NULL};
429     
430     vorbis_stream_init(&vs,0x04030201);
431     fprintf(stderr,"testing basic nil packets... ");
432     test_pack(&vs,packets,headret);
433     vorbis_stream_clear(&vs);
434   }
435
436   {
437     /* starting new page with first segment */
438     int packets[]={4345,259,255,-1};
439
440     int head1[] = {0x4f,0x67,0x67,0x53,0,0,
441                    0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
442                    0x01,0x02,0x03,0x04,0,0,0,0,
443                    0xe7,0xdc,0x6d,0x09,
444                    17,
445                    255,255,255,255,255,255,255,255,
446                    255,255,255,255,255,255,255,255,255};
447
448     int head2[] = {0x4f,0x67,0x67,0x53,0,0x02,
449                    0x00,0x08,0x00,0x00,0x00,0x00,0x00,0x00,
450                    0x01,0x02,0x03,0x04,1,0,0,0,
451                    0x5f,0x54,0x07,0x69,
452                    5,
453                    10,255,4,255,0};
454     int *headret[]={head1,head2,NULL};
455     
456     vorbis_stream_init(&vs,0x04030201);
457     fprintf(stderr,"testing single-packet page span... ");
458     test_pack(&vs,packets,headret);
459     vorbis_stream_clear(&vs);
460   }
461
462   {
463     /* starting new page with first segment */
464     int packets[]={100,4345,259,255,-1};
465
466     int head1[] = {0x4f,0x67,0x67,0x53,0,0x00,
467                    0x00,0x04,0x00,0x00,0x00,0x00,0x00,0x00,
468                    0x01,0x02,0x03,0x04,0,0,0,0,
469                    0x6f,0xac,0x43,0x67,
470                    17,
471                    100,255,255,255,255,255,255,255,255,
472                    255,255,255,255,255,255,255,255};
473
474     int head2[] = {0x4f,0x67,0x67,0x53,0,0x02,
475                    0x00,0x0c,0x00,0x00,0x00,0x00,0x00,0x00,
476                    0x01,0x02,0x03,0x04,1,0,0,0,
477                    0xe7,0xa3,0x34,0x53,
478                    6,
479                    255,10,255,4,255,0};
480     int *headret[]={head1,head2,NULL};
481     
482     vorbis_stream_init(&vs,0x04030201);
483     fprintf(stderr,"testing multi-packet page span... ");
484     test_pack(&vs,packets,headret);
485     vorbis_stream_clear(&vs);
486   }
487
488
489   /* page with the 255 segment limit */
490   {
491
492     int packets[]={10,10,10,10,10,10,10,10,
493                    10,10,10,10,10,10,10,10,
494                    10,10,10,10,10,10,10,10,
495                    10,10,10,10,10,10,10,10,
496                    10,10,10,10,10,10,10,10,
497                    10,10,10,10,10,10,10,10,
498                    10,10,10,10,10,10,10,10,
499                    10,10,10,10,10,10,10,10,
500                    10,10,10,10,10,10,10,10,
501                    10,10,10,10,10,10,10,10,
502                    10,10,10,10,10,10,10,10,
503                    10,10,10,10,10,10,10,10,
504                    10,10,10,10,10,10,10,10,
505                    10,10,10,10,10,10,10,10,
506                    10,10,10,10,10,10,10,10,
507                    10,10,10,10,10,10,10,10,
508                    10,10,10,10,10,10,10,10,
509                    10,10,10,10,10,10,10,10,
510                    10,10,10,10,10,10,10,10,
511                    10,10,10,10,10,10,10,10,
512                    10,10,10,10,10,10,10,10,
513                    10,10,10,10,10,10,10,10,
514                    10,10,10,10,10,10,10,10,
515                    10,10,10,10,10,10,10,10,
516                    10,10,10,10,10,10,10,10,
517                    10,10,10,10,10,10,10,10,
518                    10,10,10,10,10,10,10,10,
519                    10,10,10,10,10,10,10,10,
520                    10,10,10,10,10,10,10,10,
521                    10,10,10,10,10,10,10,10,
522                    10,10,10,10,10,10,10,10,
523                    10,10,10,10,10,10,10,50,-1};
524
525     int head1[] = {0x4f,0x67,0x67,0x53,0,0x00,
526                    0x00,0xf8,0x03,0x00,0x00,0x00,0x00,0x00,
527                    0x01,0x02,0x03,0x04,0,0,0,0,
528                    0xb1,0xd0,0xab,0xbc,
529                    255,
530                    10,10,10,10,10,10,10,10,
531                    10,10,10,10,10,10,10,10,
532                    10,10,10,10,10,10,10,10,
533                    10,10,10,10,10,10,10,10,
534                    10,10,10,10,10,10,10,10,
535                    10,10,10,10,10,10,10,10,
536                    10,10,10,10,10,10,10,10,
537                    10,10,10,10,10,10,10,10,
538                    10,10,10,10,10,10,10,10,
539                    10,10,10,10,10,10,10,10,
540                    10,10,10,10,10,10,10,10,
541                    10,10,10,10,10,10,10,10,
542                    10,10,10,10,10,10,10,10,
543                    10,10,10,10,10,10,10,10,
544                    10,10,10,10,10,10,10,10,
545                    10,10,10,10,10,10,10,10,
546                    10,10,10,10,10,10,10,10,
547                    10,10,10,10,10,10,10,10,
548                    10,10,10,10,10,10,10,10,
549                    10,10,10,10,10,10,10,10,
550                    10,10,10,10,10,10,10,10,
551                    10,10,10,10,10,10,10,10,
552                    10,10,10,10,10,10,10,10,
553                    10,10,10,10,10,10,10,10,
554                    10,10,10,10,10,10,10,10,
555                    10,10,10,10,10,10,10,10,
556                    10,10,10,10,10,10,10,10,
557                    10,10,10,10,10,10,10,10,
558                    10,10,10,10,10,10,10,10,
559                    10,10,10,10,10,10,10,10,
560                    10,10,10,10,10,10,10,10,
561                    10,10,10,10,10,10,10};
562
563     int head2[] = {0x4f,0x67,0x67,0x53,0,0x01,
564                    0x00,0xfc,0x03,0x00,0x00,0x00,0x00,0x00,
565                    0x01,0x02,0x03,0x04,1,0,0,0,
566                    0xb1,0x1e,0x4f,0x41,
567                    1,
568                    50};
569     int *headret[]={head1,head2,NULL};
570     
571     vorbis_stream_init(&vs,0x04030201);
572     fprintf(stderr,"testing max packet segments... ");
573     test_pack(&vs,packets,headret);
574     vorbis_stream_clear(&vs);
575   }
576
577   {
578     /* packet that overspans over an entire page */
579
580     int packets[]={100,9000,259,255,-1};
581
582     int head1[] = {0x4f,0x67,0x67,0x53,0,0x00,
583                    0x00,0x04,0x00,0x00,0x00,0x00,0x00,0x00,
584                    0x01,0x02,0x03,0x04,0,0,0,0,
585                    0x6f,0xac,0x43,0x67,
586                    17,
587                    100,255,255,255,255,255,255,255,255,
588                    255,255,255,255,255,255,255,255};
589
590     int head2[] = {0x4f,0x67,0x67,0x53,0,0x02,
591                    0x00,0x04,0x00,0x00,0x00,0x00,0x00,0x00,
592                    0x01,0x02,0x03,0x04,1,0,0,0,
593                    0x65,0x4e,0xbd,0x96,
594                    17,
595                    255,255,255,255,255,255,255,255,
596                    255,255,255,255,255,255,255,255,255};
597
598     int head3[] = {0x4f,0x67,0x67,0x53,0,0x02,
599                    0x00,0x0c,0x00,0x00,0x00,0x00,0x00,0x00,
600                    0x01,0x02,0x03,0x04,2,0,0,0,
601                    0x84,0x86,0x86,0xf4,
602                    7,
603                    255,255,75,255,4,255,0};
604     int *headret[]={head1,head2,head3,NULL};
605     
606     vorbis_stream_init(&vs,0x04030201);
607     fprintf(stderr,"testing very large packets... ");
608     test_pack(&vs,packets,headret);
609     vorbis_stream_clear(&vs);
610   }
611
612   {
613     /* nil page.  why not? */
614
615     int packets[]={100,4080,-1};
616
617     int head1[] = {0x4f,0x67,0x67,0x53,0,0x00,
618                    0x00,0x04,0x00,0x00,0x00,0x00,0x00,0x00,
619                    0x01,0x02,0x03,0x04,0,0,0,0,
620                    0x6f,0xac,0x43,0x67,
621                    17,
622                    100,255,255,255,255,255,255,255,255,
623                    255,255,255,255,255,255,255,255};
624
625     int head2[] = {0x4f,0x67,0x67,0x53,0,0x02,
626                    0x00,0x04,0x00,0x00,0x00,0x00,0x00,0x00,
627                    0x01,0x02,0x03,0x04,1,0,0,0,
628                    0x71,0xc8,0x17,0x8c,
629                    1,0};
630
631     int *headret[]={head1,head2,NULL};
632     
633     vorbis_stream_init(&vs,0x04030201);
634     fprintf(stderr,"testing nil page... ");
635     test_pack(&vs,packets,headret);
636     vorbis_stream_clear(&vs);
637   }
638
639   
640
641   return(0);
642 }
643
644 #endif