libhb/sync.c

   1 /* $Id: sync.c,v 1.38 2005/04/14 21:57:58 titer Exp $
   2
   3    This file is part of the HandBrake source code.
   4    Homepage: <http://handbrake.fr/>.
   5    It may be used under the terms of the GNU General Public License. */
   6
   7 #include "hb.h"
   8 #include "hbffmpeg.h"
   9 #include <stdio.h>
  10 #include "samplerate.h"
  11
  12 #ifdef INT64_MIN
  13 #undef INT64_MIN /* Because it isn't defined correctly in Zeta */
  14 #endif
  15 #define INT64_MIN (-9223372036854775807LL-1)
  16
  17 #define AC3_SAMPLES_PER_FRAME 1536
  18
  19 typedef struct
  20 {
  21     hb_lock_t * mutex;
  22     int         ref;        /* Reference count to tell us when it's unused */
  23     int         count_frames;
  24     int64_t     audio_passthru_slip;
  25     int64_t     video_pts_slip;
  26     int64_t     pts_offset;
  27
  28     /* Frame based point-to-point support */
  29     int64_t     audio_pts_thresh;
  30     int         start_found;
  31     hb_cond_t * next_frame;
  32     int         pts_count;
  33     int64_t   * first_pts;
  34 } hb_sync_common_t;
  35
  36 typedef struct
  37 {
  38     int          index;
  39     int64_t      next_start;    /* start time of next output frame */
  40     int64_t      next_pts;     /* start time of next input frame */
  41     int64_t      first_drop;   /* PTS of first 'went backwards' frame dropped */
  42     int          drop_count;   /* count of 'time went backwards' drops */
  43
  44     /* Raw */
  45     SRC_STATE  * state;
  46     SRC_DATA     data;
  47
  48     /* AC-3 */
  49     int          ac3_size;
  50     uint8_t    * ac3_buf;
  51 } hb_sync_audio_t;
  52
  53 typedef struct
  54 {
  55     /* Video */
  56     int        first_frame;
  57     int64_t    pts_skip;
  58     int64_t    next_start;    /* start time of next output frame */
  59     int64_t    next_pts;      /* start time of next input frame */
  60     int64_t    first_drop;    /* PTS of first 'went backwards' frame dropped */
  61     int        drop_count;    /* count of 'time went backwards' drops */
  62     int        drops;         /* frames dropped to make a cbr video stream */
  63     int        dups;          /* frames duplicated to make a cbr video stream */
  64     int        video_sequence;
  65     int        count_frames_max;
  66     int        chap_mark;     /* to propagate chapter mark across a drop */
  67     hb_buffer_t * cur;        /* The next picture to process */
  68
  69     /* Statistics */
  70     uint64_t   st_counts[4];
  71     uint64_t   st_dates[4];
  72     uint64_t   st_first;
  73 } hb_sync_video_t;
  74
  75 struct hb_work_private_s
  76 {
  77     hb_job_t * job;
  78     hb_sync_common_t * common;
  79     union
  80     {
  81         hb_sync_video_t video;
  82         hb_sync_audio_t audio;
  83     } type;
  84 };
  85
  86 /***********************************************************************
  87  * Local prototypes
  88  **********************************************************************/
  89 static void getPtsOffset( hb_work_object_t * w );
  90 static int  checkPtsOffset( hb_work_object_t * w );
  91 static void InitAudio( hb_job_t * job, hb_sync_common_t * common, int i );
  92 static void InsertSilence( hb_work_object_t * w, int64_t d );
  93 static void UpdateState( hb_work_object_t * w );
  94 static void UpdateSearchState( hb_work_object_t * w, int64_t start );
  95 static hb_buffer_t * OutputAudioFrame( hb_audio_t *audio, hb_buffer_t *buf,
  96                                        hb_sync_audio_t *sync );
  97
  98 /***********************************************************************
  99  * hb_work_sync_init
 100  ***********************************************************************
 101  * Initialize the work object
 102  **********************************************************************/
 103 int hb_sync_init( hb_job_t * job )
 104 {
 105     hb_title_t        * title = job->title;
 106     hb_chapter_t      * chapter;
 107     int                 i;
 108     uint64_t            duration;
 109     hb_work_private_t * pv;
 110     hb_sync_video_t   * sync;
 111     hb_work_object_t  * w;
 112
 113     pv = calloc( 1, sizeof( hb_work_private_t ) );
 114     sync = &pv->type.video;
 115     pv->common = calloc( 1, sizeof( hb_sync_common_t ) );
 116     pv->common->ref++;
 117     pv->common->mutex = hb_lock_init();
 118     pv->common->audio_pts_thresh = 0;
 119     pv->common->next_frame = hb_cond_init();
 120     pv->common->pts_count = 1 + hb_list_count( title->list_audio );
 121     pv->common->first_pts = malloc( sizeof(int64_t) * pv->common->pts_count );
 122     for ( i = 0; i < pv->common->pts_count; i++ )
 123         pv->common->first_pts[i] = INT64_MAX;
 124     if ( job->frame_to_start || job->pts_to_start )
 125     {
 126         pv->common->start_found = 0;
 127     }
 128     else
 129     {
 130         pv->common->start_found = 1;
 131     }
 132
 133     w = hb_get_work( WORK_SYNC_VIDEO );
 134     w->private_data = pv;
 135     w->fifo_in = job->fifo_raw;
 136     w->fifo_out = job->fifo_sync;
 137
 138     pv->job            = job;
 139     pv->common->pts_offset   = INT64_MIN;
 140     sync->first_frame = 1;
 141
 142     if( job->pass == 2 )
 143     {
 144         /* We already have an accurate frame count from pass 1 */
 145         hb_interjob_t * interjob = hb_interjob_get( job->h );
 146         sync->count_frames_max = interjob->frame_count;
 147     }
 148     else
 149     {
 150         /* Calculate how many video frames we are expecting */
 151         if ( job->pts_to_stop )
 152         {
 153             duration = job->pts_to_stop + 90000;
 154         }
 155         else if( job->frame_to_stop )
 156         {
 157             /* Set the duration to a rough estimate */
 158             duration = ( job->frame_to_stop / ( title->rate / title->rate_base ) ) * 90000;
 159         }
 160         else
 161         {
 162             duration = 0;
 163             for( i = job->chapter_start; i <= job->chapter_end; i++ )
 164             {
 165                 chapter   = hb_list_item( title->list_chapter, i - 1 );
 166                 duration += chapter->duration;
 167             }
 168             duration += 90000;
 169             /* 1 second safety so we're sure we won't miss anything */
 170         }
 171         sync->count_frames_max = duration * title->rate / title->rate_base / 90000;
 172     }
 173     hb_list_add( job->list_work, w );
 174
 175     hb_log( "sync: expecting %d video frames", sync->count_frames_max );
 176
 177     /* Initialize libsamplerate for every audio track we have */
 178     if ( ! job->indepth_scan )
 179     {
 180         for( i = 0; i < hb_list_count( title->list_audio ) && i < 8; i++ )
 181         {
 182             InitAudio( job, pv->common, i );
 183         }
 184     }
 185
 186     return 0;
 187 }
 188
 189 /***********************************************************************
 190  * Close Video
 191  ***********************************************************************
 192  *
 193  **********************************************************************/
 194 void syncVideoClose( hb_work_object_t * w )
 195 {
 196     hb_work_private_t * pv = w->private_data;
 197     hb_job_t          * job   = pv->job;
 198     hb_sync_video_t   * sync = &pv->type.video;
 199
 200     if( sync->cur )
 201     {
 202         hb_buffer_close( &sync->cur );
 203     }
 204
 205     hb_log( "sync: got %d frames, %d expected",
 206             pv->common->count_frames, sync->count_frames_max );
 207
 208     /* save data for second pass */
 209     if( job->pass == 1 )
 210     {
 211         /* Preserve frame count for better accuracy in pass 2 */
 212         hb_interjob_t * interjob = hb_interjob_get( job->h );
 213         interjob->frame_count = pv->common->count_frames;
 214         interjob->last_job = job->sequence_id;
 215         interjob->total_time = sync->next_start;
 216     }
 217
 218     if (sync->drops || sync->dups )
 219     {
 220         hb_log( "sync: %d frames dropped, %d duplicated",
 221                 sync->drops, sync->dups );
 222     }
 223
 224     hb_lock( pv->common->mutex );
 225     if ( --pv->common->ref == 0 )
 226     {
 227         hb_unlock( pv->common->mutex );
 228         hb_lock_close( &pv->common->mutex );
 229         free( pv->common );
 230     }
 231     else
 232     {
 233         hb_unlock( pv->common->mutex );
 234     }
 235
 236     free( pv );
 237     w->private_data = NULL;
 238 }
 239
 240 /***********************************************************************
 241  * syncVideoWork
 242  ***********************************************************************
 243  *
 244  **********************************************************************/
 245 int syncVideoWork( hb_work_object_t * w, hb_buffer_t ** buf_in,
 246               hb_buffer_t ** buf_out )
 247 {
 248     hb_buffer_t * cur, * next, * sub = NULL;
 249     hb_work_private_t * pv = w->private_data;
 250     hb_job_t          * job = pv->job;
 251     hb_subtitle_t     * subtitle;
 252     hb_sync_video_t   * sync = &pv->type.video;
 253     int i;
 254
 255     *buf_out = NULL;
 256     next = *buf_in;
 257     *buf_in = NULL;
 258
 259     /* Wait for start of point-to-point encoding */
 260     if( !pv->common->start_found )
 261     {
 262         hb_sync_video_t   * sync = &pv->type.video;
 263
 264         if( next->size == 0 )
 265         {
 266             *buf_out = next;
 267             pv->common->start_found = 1;
 268             hb_cond_broadcast( pv->common->next_frame );
 269
 270             /*
 271              * Push through any subtitle EOFs in case they
 272              * were not synced through.
 273              */
 274             for( i = 0; i < hb_list_count( job->list_subtitle ); i++)
 275             {
 276                 subtitle = hb_list_item( job->list_subtitle, i );
 277                 if( subtitle->config.dest == PASSTHRUSUB )
 278                 {
 279                     hb_fifo_push( subtitle->fifo_out, hb_buffer_init( 0 ) );
 280                 }
 281             }
 282             return HB_WORK_DONE;
 283         }
 284         if ( pv->common->count_frames < job->frame_to_start ||
 285              next->start < job->pts_to_start )
 286         {
 287             // Flush any subtitles that have pts prior to the
 288             // current frame
 289             for( i = 0; i < hb_list_count( job->list_subtitle ); i++)
 290             {
 291                 subtitle = hb_list_item( job->list_subtitle, i );
 292                 while( ( sub = hb_fifo_see( subtitle->fifo_raw ) ) )
 293                 {
 294                     if ( sub->start > next->start )
 295                         break;
 296                     sub = hb_fifo_get( subtitle->fifo_raw );
 297                     hb_buffer_close( &sub );
 298                 }
 299             }
 300             hb_lock( pv->common->mutex );
 301             // Tell the audio threads what must be dropped
 302             pv->common->audio_pts_thresh = next->start;
 303             hb_cond_broadcast( pv->common->next_frame );
 304             hb_unlock( pv->common->mutex );
 305
 306             UpdateSearchState( w, next->start );
 307             hb_buffer_close( &next );
 308
 309             return HB_WORK_OK;
 310         }
 311         hb_lock( pv->common->mutex );
 312         pv->common->start_found = 1;
 313         pv->common->count_frames = 0;
 314         hb_cond_broadcast( pv->common->next_frame );
 315         hb_unlock( pv->common->mutex );
 316         sync->st_first = 0;
 317     }
 318
 319     /* Wait till we can determine the initial pts of all streams */
 320     if( pv->common->pts_offset == INT64_MIN )
 321     {
 322         pv->common->first_pts[0] = next->start;
 323         hb_lock( pv->common->mutex );
 324         while( pv->common->pts_offset == INT64_MIN )
 325         {
 326             // Full fifos will make us wait forever, so get the
 327             // pts offset from the available streams if full
 328             if ( hb_fifo_is_full( job->fifo_raw ) )
 329             {
 330                 getPtsOffset( w );
 331                 hb_cond_broadcast( pv->common->next_frame );
 332             }
 333             else if ( checkPtsOffset( w ) )
 334                 hb_cond_broadcast( pv->common->next_frame );
 335             else
 336                 hb_cond_timedwait( pv->common->next_frame, pv->common->mutex, 200 );
 337         }
 338         hb_unlock( pv->common->mutex );
 339     }
 340
 341     if( !sync->cur )
 342     {
 343         sync->cur = next;
 344         if( sync->cur->size == 0 )
 345         {
 346             /* we got an end-of-stream as our first video packet?
 347              * Feed it downstream & signal that we're done.
 348              */
 349             *buf_out = hb_buffer_init( 0 );
 350
 351             pv->common->start_found = 1;
 352             hb_cond_broadcast( pv->common->next_frame );
 353
 354             /*
 355              * Push through any subtitle EOFs in case they
 356              * were not synced through.
 357              */
 358             for( i = 0; i < hb_list_count( job->list_subtitle ); i++)
 359             {
 360                 subtitle = hb_list_item( job->list_subtitle, i );
 361                 if( subtitle->config.dest == PASSTHRUSUB )
 362                 {
 363                     hb_fifo_push( subtitle->fifo_out, hb_buffer_init( 0 ) );
 364                 }
 365             }
 366             return HB_WORK_DONE;
 367         }
 368         return HB_WORK_OK;
 369     }
 370     cur = sync->cur;
 371     /* At this point we have a frame to process. Let's check
 372         1) if we will be able to push into the fifo ahead
 373         2) if the next frame is there already, since we need it to
 374            compute the duration of the current frame*/
 375     if( next->size == 0 )
 376     {
 377         hb_buffer_close( &next );
 378
 379         cur->start = sync->next_start;
 380         cur->stop = cur->start + 90000. / ((double)job->vrate / (double)job->vrate_base);
 381
 382         /* Push the frame to the renderer */
 383         hb_fifo_push( job->fifo_sync, cur );
 384         sync->cur = NULL;
 385
 386         /* we got an end-of-stream. Feed it downstream & signal that
 387          * we're done. Note that this means we drop the final frame of
 388          * video (we don't know its duration). On DVDs the final frame
 389          * is often strange and dropping it seems to be a good idea. */
 390         *buf_out = hb_buffer_init( 0 );
 391
 392         /*
 393          * Push through any subtitle EOFs in case they were not synced through.
 394          */
 395         for( i = 0; i < hb_list_count( job->list_subtitle ); i++)
 396         {
 397             subtitle = hb_list_item( job->list_subtitle, i );
 398             if( subtitle->config.dest == PASSTHRUSUB )
 399             {
 400                 if( subtitle->source == VOBSUB )
 401                     hb_fifo_push( subtitle->fifo_sync, hb_buffer_init( 0 ) );
 402                 else
 403                     hb_fifo_push( subtitle->fifo_out, hb_buffer_init( 0 ) );
 404             }
 405         }
 406         pv->common->start_found = 1;
 407         hb_cond_broadcast( pv->common->next_frame );
 408         return HB_WORK_DONE;
 409     }
 410
 411     /* Check for end of point-to-point frame encoding */
 412     if( job->frame_to_stop && pv->common->count_frames > job->frame_to_stop )
 413     {
 414         // Drop an empty buffer into our output to ensure that things
 415         // get flushed all the way out.
 416         hb_buffer_close( &sync->cur );
 417         hb_buffer_close( &next );
 418         *buf_out = hb_buffer_init( 0 );
 419         hb_log( "sync: reached %d frames, exiting early",
 420                 pv->common->count_frames );
 421         return HB_WORK_DONE;
 422     }
 423
 424     /* Check for end of point-to-point pts encoding */
 425     if( job->pts_to_stop && sync->next_start >= job->pts_to_stop )
 426     {
 427         // Drop an empty buffer into our output to ensure that things
 428         // get flushed all the way out.
 429         hb_log( "sync: reached pts %"PRId64", exiting early",
 430                 sync->cur->start );
 431         hb_buffer_close( &sync->cur );
 432         hb_buffer_close( &next );
 433         *buf_out = hb_buffer_init( 0 );
 434         return HB_WORK_DONE;
 435     }
 436
 437     if( sync->first_frame )
 438     {
 439         /* This is our first frame */
 440         if ( cur->start > pv->common->pts_offset )
 441         {
 442             /*
 443              * The first pts from a dvd should always be zero but
 444              * can be non-zero with a transport or program stream since
 445              * we're not guaranteed to start on an IDR frame. If we get
 446              * a non-zero initial PTS extend its duration so it behaves
 447              * as if it started at zero so that our audio timing will
 448              * be in sync.
 449              */
 450             hb_log( "sync: first pts is %"PRId64, cur->start );
 451             cur->start = pv->common->pts_offset;
 452         }
 453         sync->first_frame = 0;
 454     }
 455
 456     /*
 457      * since the first frame is always 0 and the upstream reader code
 458      * is taking care of adjusting for pts discontinuities, we just have
 459      * to deal with the next frame's start being in the past. This can
 460      * happen when the PTS is adjusted after data loss but video frame
 461      * reordering causes some frames with the old clock to appear after
 462      * the clock change. This creates frames that overlap in time which
 463      * looks to us like time going backward. The downstream muxing code
 464      * can deal with overlaps of up to a frame time but anything larger
 465      * we handle by dropping frames here.
 466      */
 467     hb_lock( pv->common->mutex );
 468     if ( (int64_t)( next->start - pv->common->video_pts_slip - cur->start ) <= 0 )
 469     {
 470         if ( sync->first_drop == 0 )
 471         {
 472             sync->first_drop = next->start;
 473         }
 474         ++sync->drop_count;
 475         if (next->start - cur->start > 0)
 476         {
 477             sync->pts_skip += next->start - cur->start;
 478             pv->common->video_pts_slip -= next->start - cur->start;
 479         }
 480         hb_unlock( pv->common->mutex );
 481         if ( next->new_chap )
 482         {
 483             // don't drop a chapter mark when we drop the buffer
 484             sync->chap_mark = next->new_chap;
 485         }
 486         hb_buffer_close( &next );
 487         return HB_WORK_OK;
 488     }
 489     hb_unlock( pv->common->mutex );
 490     if ( sync->first_drop )
 491     {
 492         hb_log( "sync: video time didn't advance - dropped %d frames "
 493                 "(delta %d ms, current %"PRId64", next %"PRId64", dur %d)",
 494                 sync->drop_count, (int)( cur->start - sync->first_drop ) / 90,
 495                 cur->start, next->start, (int)( next->start - cur->start ) );
 496         sync->first_drop = 0;
 497         sync->drop_count = 0;
 498     }
 499
 500     /*
 501      * Track the video sequence number localy so that we can sync the audio
 502      * to it using the sequence number as well as the PTS.
 503      */
 504     sync->video_sequence = cur->sequence;
 505
 506     /*
 507      * Look for a subtitle for this frame.
 508      *
 509      * If found then it will be tagged onto a video buffer of the correct time and
 510      * sent in to the render pipeline. This only needs to be done for VOBSUBs which
 511      * get rendered, other types of subtitles can just sit in their raw_queue until
 512      * delt with at muxing.
 513      */
 514     for( i = 0; i < hb_list_count( job->list_subtitle ); i++)
 515     {
 516         subtitle = hb_list_item( job->list_subtitle, i );
 517
 518         /*
 519          * Rewrite timestamps on subtitles that need it (on raw queue).
 520          */
 521         if( subtitle->source == CC608SUB ||
 522             subtitle->source == CC708SUB ||
 523             subtitle->source == SRTSUB )
 524         {
 525             /*
 526              * Rewrite timestamps on subtitles that came from Closed Captions
 527              * since they are using the MPEG2 timestamps.
 528              */
 529             while( ( sub = hb_fifo_see( subtitle->fifo_raw ) ) )
 530             {
 531                 /*
 532                  * Rewrite the timestamps as and when the video
 533                  * (cur->start) reaches the same timestamp as a
 534                  * closed caption (sub->start).
 535                  *
 536                  * What about discontinuity boundaries - not delt
 537                  * with here - Van?
 538                  *
 539                  * Bypass the sync fifo altogether.
 540                  */
 541                 if( sub->size <= 0 )
 542                 {
 543                     sub = hb_fifo_get( subtitle->fifo_raw );
 544                     hb_fifo_push( subtitle->fifo_out, sub );
 545                     sub = NULL;
 546                     break;
 547                 } else {
 548                     /*
 549                      * Sync the subtitles to the incoming video, and use
 550                      * the matching converted video timestamp.
 551                      *
 552                      * Note that it doesn't appear that we need to convert
 553                      * timestamps, I guess that they were already correct,
 554                      * so just push them through for rendering.
 555                      *
 556                      */
 557                     if( sub->start < cur->start )
 558                     {
 559                         sub = hb_fifo_get( subtitle->fifo_raw );
 560                         hb_fifo_push( subtitle->fifo_out, sub );
 561                     } else {
 562                         sub = NULL;
 563                         break;
 564                     }
 565                 }
 566             }
 567         }
 568
 569         if( subtitle->source == VOBSUB )
 570         {
 571             hb_buffer_t * sub2;
 572             while( ( sub = hb_fifo_see( subtitle->fifo_raw ) ) )
 573             {
 574                 if( sub->size == 0 )
 575                 {
 576                     /*
 577                      * EOF, pass it through immediately.
 578                      */
 579                     break;
 580                 }
 581
 582                 /* If two subtitles overlap, make the first one stop
 583                    when the second one starts */
 584                 sub2 = hb_fifo_see2( subtitle->fifo_raw );
 585                 if( sub2 && sub->stop > sub2->start )
 586                 {
 587                     sub->stop = sub2->start;
 588                 }
 589
 590                 // hb_log("0x%x: video seq: %lld  subtitle sequence: %lld",
 591                 //       sub, cur->sequence, sub->sequence);
 592
 593                 if( sub->sequence > cur->sequence )
 594                 {
 595                     /*
 596                      * The video is behind where we are, so wait until
 597                      * it catches up to the same reader point on the
 598                      * DVD. Then our PTS should be in the same region
 599                      * as the video.
 600                      */
 601                     sub = NULL;
 602                     break;
 603                 }
 604
 605                 if( sub->stop > cur->start ) {
 606                     /*
 607                      * The stop time is in the future, so fall through
 608                      * and we'll deal with it in the next block of
 609                      * code.
 610                      */
 611
 612                     /*
 613                      * There is a valid subtitle, is it time to display it?
 614                      */
 615                     if( sub->stop > sub->start)
 616                     {
 617                         /*
 618                          * Normal subtitle which ends after it starts,
 619                          * check to see that the current video is between
 620                          * the start and end.
 621                          */
 622                         if( cur->start > sub->start &&
 623                             cur->start < sub->stop )
 624                         {
 625                             /*
 626                             * We should be playing this, so leave the
 627                             * subtitle in place.
 628                             *
 629                             * fall through to display
 630                             */
 631                             if( ( sub->stop - sub->start ) < ( 2 * 90000 ) )
 632                             {
 633                                 /*
 634                                  * Subtitle is on for less than three
 635                                  * seconds, extend the time that it is
 636                                  * displayed to make it easier to read.
 637                                  * Make it 3 seconds or until the next
 638                                  * subtitle is displayed.
 639                                  *
 640                                  * This is in response to Indochine which
 641                                  * only displays subs for 1 second -
 642                                  * too fast to read.
 643                                  */
 644                                 sub->stop = sub->start + ( 2 * 90000 );
 645
 646                                 sub2 = hb_fifo_see2( subtitle->fifo_raw );
 647
 648                                 if( sub2 && sub->stop > sub2->start )
 649                                 {
 650                                     sub->stop = sub2->start;
 651                                 }
 652                             }
 653                         }
 654                         else
 655                         {
 656                             /*
 657                              * Defer until the play point is within
 658                              * the subtitle
 659                              */
 660                             sub = NULL;
 661                         }
 662                     }
 663                     else
 664                     {
 665                         /*
 666                          * The end of the subtitle is less than the start,
 667                          * this is a sign of a PTS discontinuity.
 668                          */
 669                         if( sub->start > cur->start )
 670                         {
 671                             /*
 672                              * we haven't reached the start time yet, or
 673                              * we have jumped backwards after having
 674                              * already started this subtitle.
 675                              */
 676                             if( cur->start < sub->stop )
 677                             {
 678                                 /*
 679                                  * We have jumped backwards and so should
 680                                  * continue displaying this subtitle.
 681                                  *
 682                                  * fall through to display.
 683                                  */
 684                             }
 685                             else
 686                             {
 687                                 /*
 688                                  * Defer until the play point is
 689                                  * within the subtitle
 690                                  */
 691                                 sub = NULL;
 692                             }
 693                         } else {
 694                             /*
 695                             * Play this subtitle as the start is
 696                             * greater than our video point.
 697                             *
 698                             * fall through to display/
 699                             */
 700                         }
 701                     }
 702                         break;
 703                 }
 704                 else
 705                 {
 706
 707                     /*
 708                      * The subtitle is older than this picture, trash it
 709                      */
 710                     sub = hb_fifo_get( subtitle->fifo_raw );
 711                     hb_buffer_close( &sub );
 712                 }
 713             }
 714
 715             /* If we have a subtitle for this picture, copy it */
 716             /* FIXME: we should avoid this memcpy */
 717             if( sub )
 718             {
 719                 if( sub->size > 0 )
 720                 {
 721                     if( subtitle->config.dest == RENDERSUB )
 722                     {
 723                         if ( cur->sub == NULL )
 724                         {
 725                             /*
 726                              * Tack onto the video buffer for rendering
 727                              */
 728                             cur->sub         = hb_buffer_init( sub->size );
 729                             cur->sub->x      = sub->x;
 730                             cur->sub->y      = sub->y;
 731                             cur->sub->width  = sub->width;
 732                             cur->sub->height = sub->height;
 733                             memcpy( cur->sub->data, sub->data, sub->size );
 734                         }
 735                     } else {
 736                         /*
 737                          * Pass-Through, pop it off of the raw queue,
 738                          */
 739                         sub = hb_fifo_get( subtitle->fifo_raw );
 740                         hb_fifo_push( subtitle->fifo_sync, sub );
 741                     }
 742                 } else {
 743                     /*
 744                     * EOF - consume for rendered, else pass through
 745                     */
 746                     if( subtitle->config.dest == RENDERSUB )
 747                     {
 748                         sub = hb_fifo_get( subtitle->fifo_raw );
 749                         hb_buffer_close( &sub );
 750                     } else {
 751                         sub = hb_fifo_get( subtitle->fifo_raw );
 752                         hb_fifo_push( subtitle->fifo_sync, sub );
 753                     }
 754                 }
 755             }
 756         }
 757     } // end subtitles
 758
 759     /*
 760      * Adjust the pts of the current frame so that it's contiguous
 761      * with the previous frame. The start time of the current frame
 762      * has to be the end time of the previous frame and the stop
 763      * time has to be the start of the next frame.  We don't
 764      * make any adjustments to the source timestamps other than removing
 765      * the clock offsets (which also removes pts discontinuities).
 766      * This means we automatically encode at the source's frame rate.
 767      * MP2 uses an implicit duration (frames end when the next frame
 768      * starts) but more advanced containers like MP4 use an explicit
 769      * duration. Since we're looking ahead one frame we set the
 770      * explicit stop time from the start time of the next frame.
 771      */
 772     *buf_out = cur;
 773     sync->cur = cur = next;
 774     cur->sub = NULL;
 775     sync->next_pts = cur->start;
 776     int64_t duration = cur->start - sync->pts_skip - (*buf_out)->start;
 777     sync->pts_skip = 0;
 778     if ( duration <= 0 )
 779     {
 780         hb_log( "sync: invalid video duration %"PRId64", start %"PRId64", next %"PRId64"",
 781                 duration, (*buf_out)->start, next->start );
 782     }
 783
 784     (*buf_out)->start = sync->next_start;
 785     sync->next_start += duration;
 786     (*buf_out)->stop = sync->next_start;
 787
 788     if ( sync->chap_mark )
 789     {
 790         // we have a pending chapter mark from a recent drop - put it on this
 791         // buffer (this may make it one frame late but we can't do any better).
 792         (*buf_out)->new_chap = sync->chap_mark;
 793         sync->chap_mark = 0;
 794     }
 795
 796     /* Update UI */
 797     UpdateState( w );
 798
 799     return HB_WORK_OK;
 800 }
 801
 802 // sync*Init does nothing because sync has a special initializer
 803 // that takes care of initializing video and all audio tracks
 804 int syncVideoInit( hb_work_object_t * w, hb_job_t * job)
 805 {
 806     return 0;
 807 }
 808
 809 hb_work_object_t hb_sync_video =
 810 {
 811     WORK_SYNC_VIDEO,
 812     "Video Synchronization",
 813     syncVideoInit,
 814     syncVideoWork,
 815     syncVideoClose
 816 };
 817
 818 /***********************************************************************
 819  * Close Audio
 820  ***********************************************************************
 821  *
 822  **********************************************************************/
 823 void syncAudioClose( hb_work_object_t * w )
 824 {
 825     hb_work_private_t * pv    = w->private_data;
 826     hb_sync_audio_t   * sync  = &pv->type.audio;
 827
 828     if( w->audio->config.out.codec == HB_ACODEC_AC3 )
 829     {
 830         free( sync->ac3_buf );
 831     }
 832     else
 833     {
 834         src_delete( sync->state );
 835     }
 836
 837     hb_lock( pv->common->mutex );
 838     if ( --pv->common->ref == 0 )
 839     {
 840         hb_unlock( pv->common->mutex );
 841         hb_lock_close( &pv->common->mutex );
 842         free( pv->common );
 843     }
 844     else
 845     {
 846         hb_unlock( pv->common->mutex );
 847     }
 848
 849     free( pv );
 850     w->private_data = NULL;
 851 }
 852
 853 int syncAudioInit( hb_work_object_t * w, hb_job_t * job)
 854 {
 855     return 0;
 856 }
 857
 858 /***********************************************************************
 859  * SyncAudio
 860  ***********************************************************************
 861  *
 862  **********************************************************************/
 863 static int syncAudioWork( hb_work_object_t * w, hb_buffer_t ** buf_in,
 864                        hb_buffer_t ** buf_out )
 865 {
 866     hb_work_private_t * pv = w->private_data;
 867     hb_job_t        * job = pv->job;
 868     hb_sync_audio_t * sync = &pv->type.audio;
 869     hb_buffer_t     * buf;
 870     //hb_fifo_t       * fifo;
 871     int64_t start;
 872
 873     *buf_out = NULL;
 874     buf = *buf_in;
 875     *buf_in = NULL;
 876     /* if the next buffer is an eof send it downstream */
 877     if ( buf->size <= 0 )
 878     {
 879         hb_buffer_close( &buf );
 880         *buf_out = hb_buffer_init( 0 );
 881         return HB_WORK_DONE;
 882     }
 883
 884     /* Wait for start frame if doing point-to-point */
 885     hb_lock( pv->common->mutex );
 886     while ( !pv->common->start_found )
 887     {
 888         if ( buf->start < pv->common->audio_pts_thresh )
 889         {
 890             hb_buffer_close( &buf );
 891             hb_unlock( pv->common->mutex );
 892             return HB_WORK_OK;
 893         }
 894         while ( !pv->common->start_found &&
 895                 buf->start >= pv->common->audio_pts_thresh )
 896         {
 897             hb_cond_timedwait( pv->common->next_frame, pv->common->mutex, 200 );
 898         }
 899     }
 900     if ( buf->start < pv->common->audio_pts_thresh )
 901     {
 902         hb_buffer_close( &buf );
 903         hb_unlock( pv->common->mutex );
 904         return HB_WORK_OK;
 905     }
 906     hb_unlock( pv->common->mutex );
 907
 908     /* Wait till we can determine the initial pts of all streams */
 909     if( pv->common->pts_offset == INT64_MIN )
 910     {
 911         pv->common->first_pts[sync->index+1] = buf->start;
 912         hb_lock( pv->common->mutex );
 913         while( pv->common->pts_offset == INT64_MIN )
 914         {
 915             // Full fifos will make us wait forever, so get the
 916             // pts offset from the available streams if full
 917             if (hb_fifo_is_full(w->fifo_in))
 918             {
 919                 getPtsOffset( w );
 920                 hb_cond_broadcast( pv->common->next_frame );
 921             }
 922             else if ( checkPtsOffset( w ) )
 923                 hb_cond_broadcast( pv->common->next_frame );
 924             else
 925                 hb_cond_timedwait( pv->common->next_frame, pv->common->mutex, 200 );
 926         }
 927         hb_unlock( pv->common->mutex );
 928     }
 929
 930     if( job->frame_to_stop && pv->common->count_frames >= job->frame_to_stop )
 931     {
 932         hb_buffer_close( &buf );
 933         *buf_out = hb_buffer_init( 0 );
 934         return HB_WORK_DONE;
 935     }
 936
 937     if( job->pts_to_stop && sync->next_start >= job->pts_to_stop )
 938     {
 939         hb_buffer_close( &buf );
 940         *buf_out = hb_buffer_init( 0 );
 941         return HB_WORK_DONE;
 942     }
 943
 944     hb_lock( pv->common->mutex );
 945     start = buf->start - pv->common->audio_passthru_slip;
 946     hb_unlock( pv->common->mutex );
 947     if ( (int64_t)( start - sync->next_pts ) < 0 )
 948     {
 949         // audio time went backwards.
 950         // If our output clock is more than a half frame ahead of the
 951         // input clock drop this frame to move closer to sync.
 952         // Otherwise drop frames until the input clock matches the output clock.
 953         if ( sync->first_drop || sync->next_start - start > 90*15 )
 954         {
 955             // Discard data that's in the past.
 956             if ( sync->first_drop == 0 )
 957             {
 958                 sync->first_drop = sync->next_pts;
 959             }
 960             ++sync->drop_count;
 961             hb_buffer_close( &buf );
 962             return HB_WORK_OK;
 963         }
 964         sync->next_pts = start;
 965     }
 966     if ( sync->first_drop )
 967     {
 968         // we were dropping old data but input buf time is now current
 969         hb_log( "sync: audio %d time went backwards %d ms, dropped %d frames "
 970                 "(next %"PRId64", current %"PRId64")", w->audio->id,
 971                 (int)( sync->next_pts - sync->first_drop ) / 90,
 972                 sync->drop_count, sync->first_drop, sync->next_pts );
 973         sync->first_drop = 0;
 974         sync->drop_count = 0;
 975         sync->next_pts = start;
 976     }
 977     if ( start - sync->next_pts >= (90 * 70) )
 978     {
 979         if ( start - sync->next_pts > (90000LL * 60) )
 980         {
 981             // there's a gap of more than a minute between the last
 982             // frame and this. assume we got a corrupted timestamp
 983             // and just drop the next buf.
 984             hb_log( "sync: %d minute time gap in audio %d - dropping buf"
 985                     "  start %"PRId64", next %"PRId64,
 986                     (int)((start - sync->next_pts) / (90000*60)),
 987                     w->audio->id, start, sync->next_pts );
 988             hb_buffer_close( &buf );
 989             return HB_WORK_OK;
 990         }
 991         /*
 992          * there's a gap of at least 70ms between the last
 993          * frame we processed & the next. Fill it with silence.
 994          * Or in the case of DCA, skip some frames from the
 995          * other streams.
 996          */
 997         if( w->audio->config.out.codec == HB_ACODEC_DCA )
 998         {
 999             hb_log( "sync: audio gap %d ms. Skipping frames. Audio %d"
1000                     "  start %"PRId64", next %"PRId64,
1001                     (int)((start - sync->next_pts) / 90),
1002                     w->audio->id, start, sync->next_pts );
1003             hb_lock( pv->common->mutex );
1004             pv->common->audio_passthru_slip += (start - sync->next_pts);
1005             pv->common->video_pts_slip += (start - sync->next_pts);
1006             hb_unlock( pv->common->mutex );
1007             *buf_out = buf;
1008             return HB_WORK_OK;
1009         }
1010         hb_log( "sync: adding %d ms of silence to audio %d"
1011                 "  start %"PRId64", next %"PRId64,
1012                 (int)((start - sync->next_pts) / 90),
1013                 w->audio->id, start, sync->next_pts );
1014         InsertSilence( w, start - sync->next_pts );
1015         *buf_out = buf;
1016         return HB_WORK_OK;
1017     }
1018
1019     /*
1020      * When we get here we've taken care of all the dups and gaps in the
1021      * audio stream and are ready to inject the next input frame into
1022      * the output stream.
1023      */
1024     *buf_out = OutputAudioFrame( w->audio, buf, sync );
1025     return HB_WORK_OK;
1026 }
1027
1028 hb_work_object_t hb_sync_audio =
1029 {
1030     WORK_SYNC_AUDIO,
1031     "AudioSynchronization",
1032     syncAudioInit,
1033     syncAudioWork,
1034     syncAudioClose
1035 };
1036
1037 static void InitAudio( hb_job_t * job, hb_sync_common_t * common, int i )
1038 {
1039     hb_work_object_t  * w;
1040     hb_work_private_t * pv;
1041     hb_title_t        * title = job->title;
1042     hb_sync_audio_t   * sync;
1043
1044     pv = calloc( 1, sizeof( hb_work_private_t ) );
1045     sync = &pv->type.audio;
1046     sync->index = i;
1047     pv->job    = job;
1048     pv->common = common;
1049     pv->common->ref++;
1050
1051     w = hb_get_work( WORK_SYNC_AUDIO );
1052     w->private_data = pv;
1053     w->audio = hb_list_item( title->list_audio, i );
1054     w->fifo_in = w->audio->priv.fifo_raw;
1055
1056     if( w->audio->config.out.codec == HB_ACODEC_AC3 ||
1057         w->audio->config.out.codec == HB_ACODEC_DCA )
1058     {
1059         w->fifo_out = w->audio->priv.fifo_out;
1060     }
1061     else
1062     {
1063         w->fifo_out = w->audio->priv.fifo_sync;
1064     }
1065
1066     if( w->audio->config.out.codec == HB_ACODEC_AC3 )
1067     {
1068         /* Have a silent AC-3 frame ready in case we have to fill a
1069            gap */
1070         AVCodec        * codec;
1071         AVCodecContext * c;
1072         short          * zeros;
1073
1074         codec = avcodec_find_encoder( CODEC_ID_AC3 );
1075         c     = avcodec_alloc_context();
1076
1077         c->bit_rate    = w->audio->config.in.bitrate;
1078         c->sample_rate = w->audio->config.in.samplerate;
1079         c->channels    = HB_INPUT_CH_LAYOUT_GET_DISCRETE_COUNT( w->audio->config.in.channel_layout );
1080
1081         if( hb_avcodec_open( c, codec ) < 0 )
1082         {
1083             hb_log( "sync: avcodec_open failed" );
1084             return;
1085         }
1086
1087         zeros          = calloc( AC3_SAMPLES_PER_FRAME *
1088                                  sizeof( short ) * c->channels, 1 );
1089         sync->ac3_size = w->audio->config.in.bitrate * AC3_SAMPLES_PER_FRAME /
1090                              w->audio->config.in.samplerate / 8;
1091         sync->ac3_buf  = malloc( sync->ac3_size );
1092
1093         if( avcodec_encode_audio( c, sync->ac3_buf, sync->ac3_size,
1094                                   zeros ) != sync->ac3_size )
1095         {
1096             hb_log( "sync: avcodec_encode_audio failed" );
1097         }
1098
1099         free( zeros );
1100         hb_avcodec_close( c );
1101         av_free( c );
1102     }
1103     else
1104     {
1105         /* Initialize libsamplerate */
1106         int error;
1107         sync->state = src_new( SRC_SINC_MEDIUM_QUALITY,
1108             HB_AMIXDOWN_GET_DISCRETE_CHANNEL_COUNT(
1109                 w->audio->config.out.mixdown), &error );
1110         sync->data.end_of_input = 0;
1111     }
1112     hb_list_add( job->list_work, w );
1113 }
1114
1115 static hb_buffer_t * OutputAudioFrame( hb_audio_t *audio, hb_buffer_t *buf,
1116                                        hb_sync_audio_t *sync )
1117 {
1118     int64_t start = sync->next_start;
1119     int64_t duration = buf->stop - buf->start;
1120
1121     sync->next_pts += duration;
1122
1123     if( audio->config.in.samplerate == audio->config.out.samplerate ||
1124         audio->config.out.codec == HB_ACODEC_AC3 ||
1125         audio->config.out.codec == HB_ACODEC_DCA )
1126     {
1127         /*
1128          * If we don't have to do sample rate conversion or this audio is
1129          * pass-thru just send the input buffer downstream after adjusting
1130          * its timestamps to make the output stream continuous.
1131          */
1132     }
1133     else
1134     {
1135         /* Not pass-thru - do sample rate conversion */
1136         int count_in, count_out;
1137         hb_buffer_t * buf_raw = buf;
1138         int channel_count = HB_AMIXDOWN_GET_DISCRETE_CHANNEL_COUNT(audio->config.out.mixdown) *
1139                             sizeof( float );
1140
1141         count_in  = buf_raw->size / channel_count;
1142         /*
1143          * When using stupid rates like 44.1 there will always be some
1144          * truncation error. E.g., a 1536 sample AC3 frame will turn into a
1145          * 1536*44.1/48.0 = 1411.2 sample frame. If we just truncate the .2
1146          * the error will build up over time and eventually the audio will
1147          * substantially lag the video. libsamplerate will keep track of the
1148          * fractional sample & give it to us when appropriate if we give it
1149          * an extra sample of space in the output buffer.
1150          */
1151         count_out = ( duration * audio->config.out.samplerate ) / 90000 + 1;
1152
1153         sync->data.input_frames = count_in;
1154         sync->data.output_frames = count_out;
1155         sync->data.src_ratio = (double)audio->config.out.samplerate /
1156                                (double)audio->config.in.samplerate;
1157
1158         buf = hb_buffer_init( count_out * channel_count );
1159         sync->data.data_in  = (float *) buf_raw->data;
1160         sync->data.data_out = (float *) buf->data;
1161         if( src_process( sync->state, &sync->data ) )
1162         {
1163             /* XXX If this happens, we're screwed */
1164             hb_log( "sync: audio %d src_process failed", audio->id );
1165         }
1166         hb_buffer_close( &buf_raw );
1167
1168         buf->size = sync->data.output_frames_gen * channel_count;
1169         duration = ( sync->data.output_frames_gen * 90000 ) /
1170                    audio->config.out.samplerate;
1171     }
1172     buf->frametype = HB_FRAME_AUDIO;
1173     buf->start = start;
1174     buf->stop  = start + duration;
1175     sync->next_start = start + duration;
1176     return buf;
1177 }
1178
1179 static void InsertSilence( hb_work_object_t * w, int64_t duration )
1180 {
1181     hb_work_private_t * pv = w->private_data;
1182     hb_sync_audio_t *sync = &pv->type.audio;
1183     hb_buffer_t     *buf;
1184     hb_fifo_t       *fifo;
1185
1186     // to keep pass-thru and regular audio in sync we generate silence in
1187     // AC3 frame-sized units. If the silence duration isn't an integer multiple
1188     // of the AC3 frame duration we will truncate or round up depending on
1189     // which minimizes the timing error.
1190     const int frame_dur = ( 90000 * AC3_SAMPLES_PER_FRAME ) /
1191                           w->audio->config.in.samplerate;
1192     int frame_count = ( duration + (frame_dur >> 1) ) / frame_dur;
1193
1194     while ( --frame_count >= 0 )
1195     {
1196         if( w->audio->config.out.codec == HB_ACODEC_AC3 )
1197         {
1198             buf        = hb_buffer_init( sync->ac3_size );
1199             buf->start = sync->next_pts;
1200             buf->stop  = buf->start + frame_dur;
1201             memcpy( buf->data, sync->ac3_buf, buf->size );
1202             fifo = w->audio->priv.fifo_out;
1203         }
1204         else
1205         {
1206             buf = hb_buffer_init( AC3_SAMPLES_PER_FRAME * sizeof( float ) *
1207                                      HB_AMIXDOWN_GET_DISCRETE_CHANNEL_COUNT(
1208                                          w->audio->config.out.mixdown) );
1209             buf->start = sync->next_pts;
1210             buf->stop  = buf->start + frame_dur;
1211             memset( buf->data, 0, buf->size );
1212             fifo = w->audio->priv.fifo_sync;
1213         }
1214         buf = OutputAudioFrame( w->audio, buf, sync );
1215         hb_fifo_push( fifo, buf );
1216     }
1217 }
1218
1219 static void UpdateState( hb_work_object_t * w )
1220 {
1221     hb_work_private_t * pv = w->private_data;
1222     hb_sync_video_t   * sync = &pv->type.video;
1223     hb_state_t state;
1224
1225     if( !pv->common->count_frames )
1226     {
1227         sync->st_first = hb_get_date();
1228         pv->job->st_pause_date = -1;
1229         pv->job->st_paused = 0;
1230     }
1231     pv->common->count_frames++;
1232
1233     if( hb_get_date() > sync->st_dates[3] + 1000 )
1234     {
1235         memmove( &sync->st_dates[0], &sync->st_dates[1],
1236                  3 * sizeof( uint64_t ) );
1237         memmove( &sync->st_counts[0], &sync->st_counts[1],
1238                  3 * sizeof( uint64_t ) );
1239         sync->st_dates[3]  = hb_get_date();
1240         sync->st_counts[3] = pv->common->count_frames;
1241     }
1242
1243 #define p state.param.working
1244     state.state = HB_STATE_WORKING;
1245     p.progress  = (float) pv->common->count_frames / (float) sync->count_frames_max;
1246     if( p.progress > 1.0 )
1247     {
1248         p.progress = 1.0;
1249     }
1250     p.rate_cur   = 1000.0 *
1251         (float) ( sync->st_counts[3] - sync->st_counts[0] ) /
1252         (float) ( sync->st_dates[3] - sync->st_dates[0] );
1253     if( hb_get_date() > sync->st_first + 4000 )
1254     {
1255         int eta;
1256         p.rate_avg = 1000.0 * (float) sync->st_counts[3] /
1257             (float) ( sync->st_dates[3] - sync->st_first - pv->job->st_paused);
1258         eta = (float) ( sync->count_frames_max - sync->st_counts[3] ) /
1259             p.rate_avg;
1260         p.hours   = eta / 3600;
1261         p.minutes = ( eta % 3600 ) / 60;
1262         p.seconds = eta % 60;
1263     }
1264     else
1265     {
1266         p.rate_avg = 0.0;
1267         p.hours    = -1;
1268         p.minutes  = -1;
1269         p.seconds  = -1;
1270     }
1271 #undef p
1272
1273     hb_set_state( pv->job->h, &state );
1274 }
1275
1276 static void UpdateSearchState( hb_work_object_t * w, int64_t start )
1277 {
1278     hb_work_private_t * pv = w->private_data;
1279     hb_sync_video_t   * sync = &pv->type.video;
1280     hb_state_t state;
1281     uint64_t now;
1282     double avg;
1283
1284     now = hb_get_date();
1285     if( !pv->common->count_frames )
1286     {
1287         sync->st_first = now;
1288         pv->job->st_pause_date = -1;
1289         pv->job->st_paused = 0;
1290     }
1291     pv->common->count_frames++;
1292
1293 #define p state.param.working
1294     state.state = HB_STATE_SEARCHING;
1295     if ( pv->job->frame_to_start )
1296         p.progress  = (float) pv->common->count_frames /
1297                       (float) pv->job->frame_to_start;
1298     else if ( pv->job->pts_to_start )
1299         p.progress  = (float) start / (float) pv->job->pts_to_start;
1300     else
1301         p.progress = 0;
1302     if( p.progress > 1.0 )
1303     {
1304         p.progress = 1.0;
1305     }
1306     if (now > sync->st_first)
1307     {
1308         int eta;
1309
1310         if ( pv->job->frame_to_start )
1311         {
1312             avg = 1000.0 * (double)pv->common->count_frames / (now - sync->st_first);
1313             eta = ( pv->job->frame_to_start - pv->common->count_frames ) / avg;
1314         }
1315         else if ( pv->job->pts_to_start )
1316         {
1317             avg = 1000.0 * (double)start / (now - sync->st_first);
1318             eta = ( pv->job->pts_to_start - start ) / avg;
1319         }
1320         p.hours   = eta / 3600;
1321         p.minutes = ( eta % 3600 ) / 60;
1322         p.seconds = eta % 60;
1323     }
1324     else
1325     {
1326         p.rate_avg = 0.0;
1327         p.hours    = -1;
1328         p.minutes  = -1;
1329         p.seconds  = -1;
1330     }
1331 #undef p
1332
1333     hb_set_state( pv->job->h, &state );
1334 }
1335
1336 static void getPtsOffset( hb_work_object_t * w )
1337 {
1338     hb_work_private_t * pv = w->private_data;
1339     int           i ;
1340     int64_t       first_pts = INT64_MAX;
1341
1342     for( i = 0; i < pv->common->pts_count; i++ )
1343     {
1344         if ( pv->common->first_pts[i] < first_pts )
1345             first_pts = pv->common->first_pts[i];
1346     }
1347     pv->common->audio_passthru_slip = pv->common->pts_offset = first_pts;
1348     return;
1349 }
1350
1351 static int checkPtsOffset( hb_work_object_t * w )
1352 {
1353     hb_work_private_t * pv = w->private_data;
1354     int           i ;
1355
1356     for( i = 0; i < pv->common->pts_count; i++ )
1357     {
1358         if ( pv->common->first_pts[i] == INT64_MAX )
1359             return 0;
1360     }
1361     getPtsOffset( w );
1362     return 1;
1363 }