jitter buffer: check for buffer overflow only when zero-copy is off
[speexdsp.git] / libspeex / jitter.c
1 /* Copyright (C) 2002 Jean-Marc Valin 
2    File: speex_jitter.h
3
4    Adaptive jitter buffer for Speex
5
6    Redistribution and use in source and binary forms, with or without
7    modification, are permitted provided that the following conditions
8    are met:
9    
10    - Redistributions of source code must retain the above copyright
11    notice, this list of conditions and the following disclaimer.
12    
13    - Redistributions in binary form must reproduce the above copyright
14    notice, this list of conditions and the following disclaimer in the
15    documentation and/or other materials provided with the distribution.
16    
17    - Neither the name of the Xiph.org Foundation nor the names of its
18    contributors may be used to endorse or promote products derived from
19    this software without specific prior written permission.
20    
21    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24    A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
25    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32
33 */
34
35 /*
36 TODO:
37 - Add short-term estimate
38 - Defensive programming
39   + warn when last returned < last desired (begative buffering)
40   + warn if update_delay not called between get() and tick() or is called twice in a row
41 - Linked list structure for holding the packets instead of the current fixed-size array
42   + return memory to a pool
43   + allow pre-allocation of the pool
44   + optional max number of elements
45 - Statistics
46   + drift
47   + loss
48   + late
49   + jitter
50   + buffering delay
51 */
52 #ifdef HAVE_CONFIG_H
53 #include "config.h"
54 #endif
55
56
57 #include "arch.h"
58 #include <speex/speex.h>
59 #include <speex/speex_bits.h>
60 #include <speex/speex_jitter.h>
61 #include "os_support.h"
62
63 #ifndef NULL
64 #define NULL 0
65 #endif
66
67 #define SPEEX_JITTER_MAX_BUFFER_SIZE 200   /**< Maximum number of packets in jitter buffer */
68
69 #define TSUB(a,b) ((spx_int32_t)((a)-(b)))
70
71 #define GT32(a,b) (((spx_int32_t)((a)-(b)))>0)
72 #define GE32(a,b) (((spx_int32_t)((a)-(b)))>=0)
73 #define LT32(a,b) (((spx_int32_t)((a)-(b)))<0)
74 #define LE32(a,b) (((spx_int32_t)((a)-(b)))<=0)
75
76 #define ROUND_DOWN(x, step) ((x)<0 ? ((x)-(step)+1)/(step)*(step) : (x)/(step)*(step)) 
77
78 #define MAX_TIMINGS 20
79 #define MAX_BUFFERS 3
80 #define TOP_DELAY 20
81
82 /** Buffer that keeps the time of arrival of the latest packets */
83 struct TimingBuffer {
84    int filled;                         /**< Number of entries occupied in "timing" and "counts"*/
85    int curr_count;                     /**< Number of packet timings we got (including those we discarded) */
86    spx_int16_t timing[MAX_TIMINGS];    /**< Sorted list of all timings ("latest" packets first) */
87    spx_int16_t counts[MAX_TIMINGS];    /**< Order the packets were put in (will be used for short-term estimate) */
88 };
89
90 static void tb_init(struct TimingBuffer *tb)
91 {
92    tb->filled = 0;
93    tb->curr_count = 0;
94 }
95
96 /* Add the timing of a new packet to the TimingBuffer */
97 static void tb_add(struct TimingBuffer *tb, spx_int16_t timing)
98 {
99    int pos;
100    /* Discard packet that won't make it into the list because they're too early */
101    if (tb->filled >= MAX_TIMINGS && timing >= tb->timing[tb->filled-1])
102    {
103       tb->curr_count++;
104       return;
105    }
106    
107    /* Find where the timing info goes in the sorted list */
108    pos = 0;
109    /* FIXME: Do bisection instead of linear search */
110    while (pos<tb->filled && timing >= tb->timing[pos])
111    {
112       pos++;
113    }
114    
115    speex_assert(pos <= tb->filled && pos < MAX_TIMINGS);
116    
117    /* Shift everything so we can perform the insertion */
118    if (pos < tb->filled)
119    {
120       int move_size = tb->filled-pos;
121       if (tb->filled == MAX_TIMINGS)
122          move_size -= 1;
123       SPEEX_COPY(&tb->timing[pos+1], &tb->timing[pos], move_size);
124       SPEEX_COPY(&tb->counts[pos+1], &tb->counts[pos], move_size);
125    }
126    /* Insert */
127    tb->timing[pos] = timing;
128    tb->counts[pos] = tb->curr_count;
129    
130    tb->curr_count++;
131    if (tb->filled<MAX_TIMINGS)
132       tb->filled++;
133 }
134
135
136
137 /** Jitter buffer structure */
138 struct JitterBuffer_ {
139    spx_uint32_t pointer_timestamp;                             /**< Timestamp of what we will *get* next */
140    spx_uint32_t last_returned_timestamp;                       /**< Useful for getting the next packet with the same timestamp (for fragmented media) */
141    spx_uint32_t next_stop;                                     /**< Estimated time the next get() will be called */
142    
143    spx_int32_t buffered;                                       /**< Amount of data we think is still buffered by the application (timestamp units)*/
144    
145    JitterBufferPacket packets[SPEEX_JITTER_MAX_BUFFER_SIZE];   /**< Packets stored in the buffer */
146    spx_uint32_t arrival[SPEEX_JITTER_MAX_BUFFER_SIZE];         /**< Packet arrival time (0 means it was late, even though it's a valid timestamp) */
147    
148    void (*destroy) (void *);                                   /**< Callback for destroying a packet */
149
150    spx_int32_t delay_step;                                     /**< Size of the steps when adjusting buffering (timestamp units) */
151    spx_int32_t concealment_size;                               /**< Size of the packet loss concealment "units" */
152    int reset_state;                                            /**< True if state was just reset        */
153    int buffer_margin;                                          /**< How many frames we want to keep in the buffer (lower bound) */
154    int late_cutoff;                                            /**< How late must a packet be for it not to be considered at all */
155    int interp_requested;                                       /**< An interpolation is requested by speex_jitter_update_delay() */
156    int auto_adjust;                                            /**< Whether to automatically adjust the delay at any time */
157    
158    struct TimingBuffer _tb[MAX_BUFFERS];                       /**< Don't use those directly */
159    struct TimingBuffer *timeBuffers[MAX_BUFFERS];              /**< Storing arrival time of latest frames so we can compute some stats */
160    int window_size;                                            /**< Total window over which the late frames are counted */
161    int subwindow_size;                                         /**< Sub-window size for faster computation  */
162    int max_late_rate;                                          /**< Absolute maximum amount of late packets tolerable (in percent) */
163    int latency_tradeoff;                                       /**< Latency equivalent of losing one percent of packets */
164    int auto_tradeoff;                                          /**< Latency equivalent of losing one percent of packets (automatic default) */
165    
166    int lost_count;                                             /**< Number of consecutive lost packets  */
167 };
168
169 /** Based on available data, this computes the optimal delay for the jitter buffer. 
170    The optimised function is in timestamp units and is:
171    cost = delay + late_factor*[number of frames that would be late if we used that delay]
172    @param tb Array of buffers
173    @param late_factor Equivalent cost of a late frame (in timestamp units) 
174  */
175 static spx_int16_t compute_opt_delay(JitterBuffer *jitter)
176 {
177    int i;
178    spx_int16_t opt=0;
179    spx_int32_t best_cost=0x7fffffff;
180    int late = 0;
181    int pos[MAX_BUFFERS];
182    int tot_count;
183    float late_factor;
184    int penalty_taken = 0;
185    int best = 0;
186    int worst = 0;
187    spx_int32_t deltaT;
188    struct TimingBuffer *tb;
189    
190    tb = jitter->_tb;
191    
192    /* Number of packet timings we have received (including those we didn't keep) */
193    tot_count = 0;
194    for (i=0;i<MAX_BUFFERS;i++)
195       tot_count += tb[i].curr_count;
196    if (tot_count==0)
197       return 0;
198    
199    /* Compute cost for one lost packet */
200    if (jitter->latency_tradeoff != 0)
201       late_factor = jitter->latency_tradeoff * 100.0f / tot_count;
202    else
203       late_factor = jitter->auto_tradeoff * jitter->window_size/tot_count;
204    
205    /*fprintf(stderr, "late_factor = %f\n", late_factor);*/
206    for (i=0;i<MAX_BUFFERS;i++)
207       pos[i] = 0;
208    
209    /* Pick the TOP_DELAY "latest" packets (doesn't need to actually be late 
210       for the current settings) */
211    for (i=0;i<TOP_DELAY;i++)
212    {
213       int j;
214       int next=-1;
215       int latest = 32767;
216       /* Pick latest amoung all sub-windows */
217       for (j=0;j<MAX_BUFFERS;j++)
218       {
219          if (pos[j] < tb[j].filled && tb[j].timing[pos[j]] < latest)
220          {
221             next = j;
222             latest = tb[j].timing[pos[j]];
223          }
224       }
225       if (next != -1)
226       {
227          spx_int32_t cost;
228          
229          if (i==0)
230             worst = latest;
231          best = latest;
232          latest = ROUND_DOWN(latest, jitter->delay_step);
233          pos[next]++;
234          
235          /* Actual cost function that tells us how bad using this delay would be */
236          cost = -latest + late_factor*late;
237          /*fprintf(stderr, "cost %d = %d + %f * %d\n", cost, -latest, late_factor, late);*/
238          if (cost < best_cost)
239          {
240             best_cost = cost;
241             opt = latest;
242          }
243       } else {
244          break;
245       }
246       
247       /* For the next timing we will consider, there will be one more late packet to count */
248       late++;
249       /* Two-frame penalty if we're going to increase the amount of late frames (hysteresis) */
250       if (latest >= 0 && !penalty_taken)
251       {
252          penalty_taken = 1;
253          late+=2;
254       }
255    }
256    
257    deltaT = best-worst;
258    /* This is a default "automatic latency tradeoff" when none is provided */
259    jitter->auto_tradeoff = 1 + deltaT/TOP_DELAY;
260    /*fprintf(stderr, "auto_tradeoff = %d (%d %d %d)\n", jitter->auto_tradeoff, best, worst, i);*/
261    
262    /* FIXME: Compute a short-term estimate too and combine with the long-term one */
263    
264    /* Prevents reducing the buffer size when we haven't really had much data */
265    if (tot_count < TOP_DELAY && opt > 0)
266       return 0;
267    return opt;
268 }
269
270
271 /** Initialise jitter buffer */
272 JitterBuffer *jitter_buffer_init(int step_size)
273 {
274    JitterBuffer *jitter = (JitterBuffer*)speex_alloc(sizeof(JitterBuffer));
275    if (jitter)
276    {
277       int i;
278       spx_int32_t tmp;
279       for (i=0;i<SPEEX_JITTER_MAX_BUFFER_SIZE;i++)
280          jitter->packets[i].data=NULL;
281       jitter->delay_step = step_size;
282       jitter->concealment_size = step_size;
283       /*FIXME: Should this be 0 or 1?*/
284       jitter->buffer_margin = 0;
285       jitter->late_cutoff = 50;
286       jitter->destroy = NULL;
287       jitter->latency_tradeoff = 0;
288       jitter->auto_adjust = 1;
289       tmp = 4;
290       jitter_buffer_ctl(jitter, JITTER_BUFFER_SET_MAX_LATE_RATE, &tmp);
291       jitter_buffer_reset(jitter);
292    }
293    return jitter;
294 }
295
296 /** Reset jitter buffer */
297 void jitter_buffer_reset(JitterBuffer *jitter)
298 {
299    int i;
300    for (i=0;i<SPEEX_JITTER_MAX_BUFFER_SIZE;i++)
301    {
302       if (jitter->packets[i].data)
303       {
304          if (jitter->destroy)
305             jitter->destroy(jitter->packets[i].data);
306          else
307             speex_free(jitter->packets[i].data);
308          jitter->packets[i].data = NULL;
309       }
310    }
311    /* Timestamp is actually undefined at this point */
312    jitter->pointer_timestamp = 0;
313    jitter->next_stop = 0;
314    jitter->reset_state = 1;
315    jitter->lost_count = 0;
316    jitter->buffered = 0;
317    jitter->auto_tradeoff = 32000;
318    
319    for (i=0;i<MAX_BUFFERS;i++)
320    {
321       tb_init(&jitter->_tb[i]);
322       jitter->timeBuffers[i] = &jitter->_tb[i];
323    }
324    /*fprintf (stderr, "reset\n");*/
325 }
326
327 /** Destroy jitter buffer */
328 void jitter_buffer_destroy(JitterBuffer *jitter)
329 {
330    jitter_buffer_reset(jitter);
331    speex_free(jitter);
332 }
333
334 /** Take the following timing into consideration for future calculations */
335 static void update_timings(JitterBuffer *jitter, spx_int32_t timing)
336 {
337    if (timing < -32767)
338       timing = -32767;
339    if (timing > 32767)
340       timing = 32767;
341    /* If the current sub-window is full, perform a rotation and discard oldest sub-widow */
342    if (jitter->timeBuffers[0]->curr_count >= jitter->subwindow_size)
343    {
344       int i;
345       /*fprintf(stderr, "Rotate buffer\n");*/
346       struct TimingBuffer *tmp = jitter->timeBuffers[MAX_BUFFERS-1];
347       for (i=MAX_BUFFERS-1;i>=1;i--)
348          jitter->timeBuffers[i] = jitter->timeBuffers[i-1];
349       jitter->timeBuffers[0] = tmp;
350       tb_init(jitter->timeBuffers[0]);
351    }
352    tb_add(jitter->timeBuffers[0], timing);
353 }
354
355 /** Compensate all timings when we do an adjustment of the buffering */
356 static void shift_timings(JitterBuffer *jitter, spx_int16_t amount)
357 {
358    int i, j;
359    for (i=0;i<MAX_BUFFERS;i++)
360    {
361       for (j=0;j<jitter->timeBuffers[i]->filled;j++)
362          jitter->timeBuffers[i]->timing[j] += amount;
363    }
364 }
365
366
367 /** Put one packet into the jitter buffer */
368 void jitter_buffer_put(JitterBuffer *jitter, const JitterBufferPacket *packet)
369 {
370    int i,j;
371    int late;
372    /*fprintf (stderr, "put packet %d %d\n", timestamp, span);*/
373    
374    /* Cleanup buffer (remove old packets that weren't played) */
375    if (!jitter->reset_state)
376    {
377       for (i=0;i<SPEEX_JITTER_MAX_BUFFER_SIZE;i++)
378       {
379          /* Make sure we don't discard a "just-late" packet in case we want to play it next (if we interpolate). */
380          if (jitter->packets[i].data && LE32(jitter->packets[i].timestamp + jitter->packets[i].span, jitter->pointer_timestamp))
381          {
382             /*fprintf (stderr, "cleaned (not played)\n");*/
383             if (jitter->destroy)
384                jitter->destroy(jitter->packets[i].data);
385             else
386                speex_free(jitter->packets[i].data);
387             jitter->packets[i].data = NULL;
388          }
389       }
390    }
391    
392    /*fprintf(stderr, "arrival: %d %d %d\n", packet->timestamp, jitter->next_stop, jitter->pointer_timestamp);*/
393    /* Check if packet is late (could still be useful though) */
394    if (!jitter->reset_state && LT32(packet->timestamp, jitter->next_stop))
395    {
396       update_timings(jitter, ((spx_int32_t)packet->timestamp) - ((spx_int32_t)jitter->next_stop) - jitter->buffer_margin);
397       late = 1;
398    } else {
399       late = 0;
400    }
401    
402    /* Only insert the packet if it's not hopelessly late (i.e. totally useless) */
403    if (jitter->reset_state || GE32(packet->timestamp+packet->span+jitter->delay_step, jitter->pointer_timestamp))
404    {
405
406       /*Find an empty slot in the buffer*/
407       for (i=0;i<SPEEX_JITTER_MAX_BUFFER_SIZE;i++)
408       {
409          if (jitter->packets[i].data==NULL)
410             break;
411       }
412       
413       /*No place left in the buffer, need to make room for it by discarding the oldest packet */
414       if (i==SPEEX_JITTER_MAX_BUFFER_SIZE)
415       {
416          int earliest=jitter->packets[0].timestamp;
417          i=0;
418          for (j=1;j<SPEEX_JITTER_MAX_BUFFER_SIZE;j++)
419          {
420             if (!jitter->packets[i].data || LT32(jitter->packets[j].timestamp,earliest))
421             {
422                earliest = jitter->packets[j].timestamp;
423                i=j;
424             }
425          }
426          if (jitter->destroy)
427             jitter->destroy(jitter->packets[i].data);
428          else
429             speex_free(jitter->packets[i].data);
430          jitter->packets[i].data=NULL;
431          if (jitter->lost_count>20)
432          {
433             jitter_buffer_reset(jitter);
434          }
435          /*fprintf (stderr, "Buffer is full, discarding earliest frame %d (currently at %d)\n", timestamp, jitter->pointer_timestamp);*/      
436       }
437    
438       /* Copy packet in buffer */
439       if (jitter->destroy)
440       {
441          jitter->packets[i].data = packet->data;
442       } else {
443          jitter->packets[i].data=(char*)speex_alloc(packet->len);
444          for (j=0;j<packet->len;j++)
445             jitter->packets[i].data[j]=packet->data[j];
446       }
447       jitter->packets[i].timestamp=packet->timestamp;
448       jitter->packets[i].span=packet->span;
449       jitter->packets[i].len=packet->len;
450       jitter->packets[i].sequence=packet->sequence;
451       jitter->packets[i].user_data=packet->user_data;
452       if (jitter->reset_state || late)
453          jitter->arrival[i] = 0;
454       else
455          jitter->arrival[i] = jitter->next_stop;
456    }
457    
458    
459 }
460
461 /** Get one packet from the jitter buffer */
462 int jitter_buffer_get(JitterBuffer *jitter, JitterBufferPacket *packet, spx_int32_t desired_span, spx_int32_t *start_offset)
463 {
464    int i;
465    unsigned int j;
466    int incomplete = 0;
467    spx_int16_t opt;
468    
469    if (start_offset != NULL)
470       *start_offset = 0;
471
472    /* Syncing on the first call */
473    if (jitter->reset_state)
474    {
475       int found = 0;
476       /* Find the oldest packet */
477       spx_uint32_t oldest=0;
478       for (i=0;i<SPEEX_JITTER_MAX_BUFFER_SIZE;i++)
479       {
480          if (jitter->packets[i].data && (!found || LT32(jitter->packets[i].timestamp,oldest)))
481          {
482             oldest = jitter->packets[i].timestamp;
483             found = 1;
484          }
485       }
486       if (found)
487       {
488          jitter->reset_state=0;         
489          jitter->pointer_timestamp = oldest;
490          jitter->next_stop = oldest;
491       } else {
492          packet->timestamp = 0;
493          packet->span = jitter->interp_requested;
494          return JITTER_BUFFER_MISSING;
495       }
496    }
497    
498
499    jitter->last_returned_timestamp = jitter->pointer_timestamp;
500          
501    if (jitter->interp_requested != 0)
502    {
503       packet->timestamp = jitter->pointer_timestamp;
504       packet->span = jitter->interp_requested;
505       
506       /* Increment the pointer because it got decremented in the delay update */
507       jitter->pointer_timestamp += jitter->interp_requested;
508       packet->len = 0;
509       /*fprintf (stderr, "Deferred interpolate\n");*/
510       
511       jitter->interp_requested = 0;
512       
513       jitter->buffered = packet->span - desired_span;
514
515       return JITTER_BUFFER_INSERTION;
516    }
517    
518    /* Searching for the packet that fits best */
519    
520    /* Search the buffer for a packet with the right timestamp and spanning the whole current chunk */
521    for (i=0;i<SPEEX_JITTER_MAX_BUFFER_SIZE;i++)
522    {
523       if (jitter->packets[i].data && jitter->packets[i].timestamp==jitter->pointer_timestamp && GE32(jitter->packets[i].timestamp+jitter->packets[i].span,jitter->pointer_timestamp+desired_span))
524          break;
525    }
526    
527    /* If no match, try for an "older" packet that still spans (fully) the current chunk */
528    if (i==SPEEX_JITTER_MAX_BUFFER_SIZE)
529    {
530       for (i=0;i<SPEEX_JITTER_MAX_BUFFER_SIZE;i++)
531       {
532          if (jitter->packets[i].data && LE32(jitter->packets[i].timestamp, jitter->pointer_timestamp) && GE32(jitter->packets[i].timestamp+jitter->packets[i].span,jitter->pointer_timestamp+desired_span))
533             break;
534       }
535    }
536    
537    /* If still no match, try for an "older" packet that spans part of the current chunk */
538    if (i==SPEEX_JITTER_MAX_BUFFER_SIZE)
539    {
540       for (i=0;i<SPEEX_JITTER_MAX_BUFFER_SIZE;i++)
541       {
542          if (jitter->packets[i].data && LE32(jitter->packets[i].timestamp, jitter->pointer_timestamp) && GT32(jitter->packets[i].timestamp+jitter->packets[i].span,jitter->pointer_timestamp))
543             break;
544       }
545    }
546    
547    /* If still no match, try for earliest packet possible */
548    if (i==SPEEX_JITTER_MAX_BUFFER_SIZE)
549    {
550       int found = 0;
551       spx_uint32_t best_time=0;
552       int best_span=0;
553       int besti=0;
554       for (i=0;i<SPEEX_JITTER_MAX_BUFFER_SIZE;i++)
555       {
556          /* check if packet starts within current chunk */
557          if (jitter->packets[i].data && LT32(jitter->packets[i].timestamp,jitter->pointer_timestamp+desired_span) && GE32(jitter->packets[i].timestamp,jitter->pointer_timestamp))
558          {
559             if (!found || LT32(jitter->packets[i].timestamp,best_time) || (jitter->packets[i].timestamp==best_time && GT32(jitter->packets[i].span,best_span)))
560             {
561                best_time = jitter->packets[i].timestamp;
562                best_span = jitter->packets[i].span;
563                besti = i;
564                found = 1;
565             }
566          }
567       }
568       if (found)
569       {
570          i=besti;
571          incomplete = 1;
572          /*fprintf (stderr, "incomplete: %d %d %d %d\n", jitter->packets[i].timestamp, jitter->pointer_timestamp, chunk_size, jitter->packets[i].span);*/
573       }
574    }
575
576    /* If we find something */
577    if (i!=SPEEX_JITTER_MAX_BUFFER_SIZE)
578    {
579       spx_int32_t offset;
580       
581       /* We (obviously) haven't lost this packet */
582       jitter->lost_count = 0;
583       
584       /* In this case, 0 isn't as a valid timestamp */
585       if (jitter->arrival[i] != 0)
586       {
587          update_timings(jitter, ((spx_int32_t)jitter->packets[i].timestamp) - ((spx_int32_t)jitter->arrival[i]) - jitter->buffer_margin);
588       }
589       
590       
591       /* Copy packet */
592       if (jitter->destroy)
593       {
594          packet->data = jitter->packets[i].data;
595       } else {
596          if (jitter->packets[i].len > packet->len)
597          {
598             speex_warning_int("jitter_buffer_get(): packet too large to fit. Size is", jitter->packets[i].len);
599          } else {
600             packet->len = jitter->packets[i].len;
601          }
602          for (j=0;j<packet->len;j++)
603             packet->data[j] = jitter->packets[i].data[j];
604          /* Remove packet */
605          speex_free(jitter->packets[i].data);
606       }
607       jitter->packets[i].data = NULL;
608       /* Set timestamp and span (if requested) */
609       offset = (spx_int32_t)jitter->packets[i].timestamp-(spx_int32_t)jitter->pointer_timestamp;
610       if (start_offset != NULL)
611          *start_offset = offset;
612       else if (offset != 0)
613          speex_warning_int("jitter_buffer_get() discarding non-zero start_offset", offset);
614       
615       packet->timestamp = jitter->packets[i].timestamp;
616       jitter->last_returned_timestamp = packet->timestamp;
617       
618       packet->span = jitter->packets[i].span;
619       packet->sequence = jitter->packets[i].sequence;
620       packet->user_data = jitter->packets[i].user_data;
621       /* Point to the end of the current packet */
622       jitter->pointer_timestamp = jitter->packets[i].timestamp+jitter->packets[i].span;
623
624       jitter->buffered = packet->span - desired_span;
625       
626       if (start_offset != NULL)
627          jitter->buffered += *start_offset;
628       
629       return JITTER_BUFFER_OK;
630    }
631    
632    
633    /* If we haven't found anything worth returning */
634    
635    /*fprintf (stderr, "not found\n");*/
636    jitter->lost_count++;
637    /*fprintf (stderr, "m");*/
638    /*fprintf (stderr, "lost_count = %d\n", jitter->lost_count);*/
639    
640    opt = compute_opt_delay(jitter);
641    
642    /* Should we force an increase in the buffer or just do normal interpolation? */   
643    if (opt < 0)
644    {
645       /* Need to increase buffering */
646       
647       /* Shift histogram to compensate */
648       shift_timings(jitter, -opt);
649       
650       packet->timestamp = jitter->pointer_timestamp;
651       packet->span = -opt;
652       /* Don't move the pointer_timestamp forward */
653       packet->len = 0;
654       
655       jitter->buffered = packet->span - desired_span;
656       return JITTER_BUFFER_INSERTION;
657       /*jitter->pointer_timestamp -= jitter->delay_step;*/
658       /*fprintf (stderr, "Forced to interpolate\n");*/
659    } else {
660       /* Normal packet loss */
661       packet->timestamp = jitter->pointer_timestamp;
662       
663       desired_span = ROUND_DOWN(desired_span, jitter->concealment_size);
664       packet->span = desired_span;
665       jitter->pointer_timestamp += desired_span;
666       packet->len = 0;
667       
668       jitter->buffered = packet->span - desired_span;
669       return JITTER_BUFFER_MISSING;
670       /*fprintf (stderr, "Normal loss\n");*/
671    }
672
673
674 }
675
676 int jitter_buffer_get_another(JitterBuffer *jitter, JitterBufferPacket *packet)
677 {
678    int i, j;
679    for (i=0;i<SPEEX_JITTER_MAX_BUFFER_SIZE;i++)
680    {
681       if (jitter->packets[i].data && jitter->packets[i].timestamp==jitter->last_returned_timestamp)
682          break;
683    }
684    if (i!=SPEEX_JITTER_MAX_BUFFER_SIZE)
685    {
686       /* Copy packet */
687       packet->len = jitter->packets[i].len;
688       if (jitter->destroy)
689       {
690          packet->data = jitter->packets[i].data;
691       } else {
692          for (j=0;j<packet->len;j++)
693             packet->data[j] = jitter->packets[i].data[j];
694          /* Remove packet */
695          speex_free(jitter->packets[i].data);
696       }
697       jitter->packets[i].data = NULL;
698       packet->timestamp = jitter->packets[i].timestamp;
699       packet->span = jitter->packets[i].span;
700       packet->sequence = jitter->packets[i].sequence;
701       packet->user_data = jitter->packets[i].user_data;
702       return JITTER_BUFFER_OK;
703    } else {
704       packet->data = NULL;
705       packet->len = 0;
706       packet->span = 0;
707       return JITTER_BUFFER_MISSING;
708    }
709 }
710
711 /* Let the jitter buffer know it's the right time to adjust the buffering delay to the network conditions */
712 static int _jitter_buffer_update_delay(JitterBuffer *jitter, JitterBufferPacket *packet, spx_int32_t *start_offset)
713 {
714    spx_int16_t opt = compute_opt_delay(jitter);
715    /*fprintf(stderr, "opt adjustment is %d ", opt);*/
716    
717    if (opt < 0)
718    {
719       shift_timings(jitter, -opt);
720       
721       jitter->pointer_timestamp += opt;
722       jitter->interp_requested = -opt;
723       /*fprintf (stderr, "Decision to interpolate %d samples\n", -opt);*/
724    } else if (opt > 0)
725    {
726       shift_timings(jitter, -opt);
727       jitter->pointer_timestamp += opt;
728       /*fprintf (stderr, "Decision to drop %d samples\n", opt);*/
729    }
730    
731    return opt;
732 }
733
734 /* Let the jitter buffer know it's the right time to adjust the buffering delay to the network conditions */
735 int jitter_buffer_update_delay(JitterBuffer *jitter, JitterBufferPacket *packet, spx_int32_t *start_offset)
736 {
737    /* If the programmer calls jitter_buffer_update_delay() directly, 
738       automatically disable auto-adjustment */
739    jitter->auto_adjust = 0;
740
741    return _jitter_buffer_update_delay(jitter, packet, start_offset);
742 }
743
744 /** Get pointer timestamp of jitter buffer */
745 int jitter_buffer_get_pointer_timestamp(JitterBuffer *jitter)
746 {
747    return jitter->pointer_timestamp;
748 }
749
750 void jitter_buffer_tick(JitterBuffer *jitter)
751 {
752    /* Automatically-adjust the buffering delay if requested */
753    if (jitter->auto_adjust)
754       _jitter_buffer_update_delay(jitter, NULL, NULL);
755    
756    if (jitter->buffered >= 0)
757    {
758       jitter->next_stop = jitter->pointer_timestamp - jitter->buffered;
759    } else {
760       jitter->next_stop = jitter->pointer_timestamp;
761       speex_warning_int("jitter buffer sees negative buffering, your code might be broken. Value is ", jitter->buffered);
762    }
763    jitter->buffered = 0;
764 }
765
766 void jitter_buffer_remaining_span(JitterBuffer *jitter, spx_uint32_t rem)
767 {
768    /* Automatically-adjust the buffering delay if requested */
769    if (jitter->auto_adjust)
770       _jitter_buffer_update_delay(jitter, NULL, NULL);
771    
772    if (jitter->buffered < 0)
773       speex_warning_int("jitter buffer sees negative buffering, your code might be broken. Value is ", jitter->buffered);
774    jitter->next_stop = jitter->pointer_timestamp - rem;
775 }
776
777
778 /* Used like the ioctl function to control the jitter buffer parameters */
779 int jitter_buffer_ctl(JitterBuffer *jitter, int request, void *ptr)
780 {
781    int count, i;
782    switch(request)
783    {
784       case JITTER_BUFFER_SET_MARGIN:
785          jitter->buffer_margin = *(spx_int32_t*)ptr;
786          break;
787       case JITTER_BUFFER_GET_MARGIN:
788          *(spx_int32_t*)ptr = jitter->buffer_margin;
789          break;
790       case JITTER_BUFFER_GET_AVALIABLE_COUNT:
791          count = 0;
792          for (i=0;i<SPEEX_JITTER_MAX_BUFFER_SIZE;i++)
793          {
794             if (jitter->packets[i].data && LE32(jitter->pointer_timestamp, jitter->packets[i].timestamp))
795             {
796                count++;
797             }
798          }
799          *(spx_int32_t*)ptr = count;
800          break;
801       case JITTER_BUFFER_SET_DESTROY_CALLBACK:
802          jitter->destroy = (void (*) (void *))ptr;
803          break;
804       case JITTER_BUFFER_GET_DESTROY_CALLBACK:
805          *(void (**) (void *))ptr = jitter->destroy;
806          break;
807       case JITTER_BUFFER_SET_DELAY_STEP:
808          jitter->delay_step = *(spx_int32_t*)ptr;
809          break;
810       case JITTER_BUFFER_GET_DELAY_STEP:
811          *(spx_int32_t*)ptr = jitter->delay_step;
812          break;
813       case JITTER_BUFFER_SET_CONCEALMENT_SIZE:
814          jitter->concealment_size = *(spx_int32_t*)ptr;
815          break;
816       case JITTER_BUFFER_GET_CONCEALMENT_SIZE:
817          *(spx_int32_t*)ptr = jitter->concealment_size;
818          break;
819       case JITTER_BUFFER_SET_MAX_LATE_RATE:
820          jitter->max_late_rate = *(spx_int32_t*)ptr;
821          jitter->window_size = 100*TOP_DELAY/jitter->max_late_rate;
822          jitter->subwindow_size = jitter->window_size/MAX_BUFFERS;
823          break;
824       case JITTER_BUFFER_GET_MAX_LATE_RATE:
825          *(spx_int32_t*)ptr = jitter->max_late_rate;
826          break;
827       case JITTER_BUFFER_SET_LATE_COST:
828          jitter->latency_tradeoff = *(spx_int32_t*)ptr;
829          break;
830       case JITTER_BUFFER_GET_LATE_COST:
831          *(spx_int32_t*)ptr = jitter->latency_tradeoff;
832          break;
833       default:
834          speex_warning_int("Unknown jitter_buffer_ctl request: ", request);
835          return -1;
836    }
837    return 0;
838 }
839