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