001 /**
002 * Copyright (C) 2010 - Francesc Auli-Llinas
003 *
004 * This program is free software: you can redistribute it and/or modify it under the terms of the
005 * GNU General Public License as published by the Free Software Foundation, either version 3 of the License,
006 * or (at your option) any later version.
007 *
008 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even
009 * the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
010 * for more details.
011 *
012 * You should have received a copy of the GNU General Public License along with this program.
013 * If not, see <http://www.gnu.org/licenses/>.
014 */
015
016 /**
017 * FAST algorithm for the layer bounded transmission.
018 *
019 * Please cite the following paper when using it:
020 * F. Auli-Llinas, A. Bilgin, and M.W. Marcellin, "FAST Rate Allocation through
021 * Steepest Descent for JPEG2000 Video Transmission," IEEE Trans. Image Process., vol. 20, no. 4, pp. 1166-1173, Apr. 2011.
022 *
023 * @version 1.5 - April 17, 2009
024 */
025 public class FASTbounded{
026
027 //Configuration parameters
028 static int firstFrame = 0;
029 static int lastFrame = 0;
030 static float[][][] layersConfig = null; //configuration of quality layers. Indexes mean [frame][layer][0 is the numBytes,
031 //1 is the DL slope, 2 is the MSE]
032 static int avBytesTX = 0; //average number of bytes per frame (i.e. frame transmitted by a constant bit-rate policy)
033 static int buffUpBound = 0; //the upper bound of the buffer, in bytes
034 static int buffLowBound = 0; //the lower bound of the buffer, in bytes
035 static int[] layersTX = null; //last transmitted layer for each frame
036 static int numFrames = 0; //number of frames of the sequence
037 static float maxBytesTX = 0f; //channel capacity
038 static int criteria = 1; //1 - minimize overall distortion, 2 - minimize maximum frame's distortion
039
040 //Helpers - lists of worst/best frames
041 static int[] worstFrames = null; //sorted list of frames upon the DL slope of the currently transmitted layer (first is the frame
042 //index with the lowest DL slope)
043 static int[] bestFrames = null; //sorted list of frames upon the DL slope of the next available layer to be transmitted (first is the
044 //frame index with the highest DL slope)
045 static int[] worstFramesLUT = null; //lookup table for worstFrames: index 0 in this array contains the position of firstFrame in the
046 //worstFrames list
047 static int[] bestFramesLUT = null; //lookup table for bestFrames: index 0 in this array contains the position of firstFrame in the
048 //bestFrames list
049 static int[] lessQS = null; //temporal structure used by the QuickSort algorithm
050 static int[] greaterQS = null; //temporal structure used by the QuickSort algorithm
051 //Helpers - smart buffer control
052 static int numPointsBUFF = 0; //number of frames in which the buffer state turns from empting to filling, or the other way
053 static int[] pointsBUFF = null; //frames in which the buffer state turns from empting to filling, or the other way
054 static int[] bytesPointsBUFF = null; //number of buffer bytes in these frames
055 static boolean[] trendsBUFF = null; //trend of the buffer until reaching that point (false means buffer is emptying)
056
057
058 /**
059 * Main function.
060 *
061 * @param P_firstFrame first transmitted frame (inclusive)
062 * @param P_lastFrame last transmitted frame (inclusive)
063 * @param P_layersConfig configuration of quality layers
064 * @param P_avBytesTX average number of bytes per frame
065 * @param P_buffUpBound the upper bound of the buffer, in bytes
066 * @param P_buffLowBound the lower bound of the buffer, in bytes
067 * @param P_layersTX solution
068 * @throws Exception when no solution is reached
069 */
070 public static void FASTbounded(int P_firstFrame, int P_lastFrame, float[][][] P_layersConfig, int P_avBytesTX,
071 int P_buffUpBound, int P_buffLowBound, int[] P_layersTX) throws Exception{
072
073 //Parameters
074 firstFrame = P_firstFrame;
075 lastFrame = P_lastFrame;
076 layersConfig = P_layersConfig;
077 avBytesTX = P_avBytesTX;
078 buffUpBound = P_buffUpBound;
079 buffLowBound = P_buffLowBound;
080 if(buffUpBound < 0){ //Infinite buffer size
081 buffUpBound = Integer.MAX_VALUE;
082 buffLowBound = Integer.MIN_VALUE;
083 }
084 layersTX = P_layersTX;
085 numFrames = lastFrame - firstFrame + 1;
086 maxBytesTX = avBytesTX * numFrames;
087
088 //Initialize helpers and some needed variables
089 worstFrames = new int[numFrames];
090 bestFrames = new int[numFrames];
091 worstFramesLUT = new int[numFrames];
092 bestFramesLUT = new int[numFrames];
093 lessQS = new int[numFrames];
094 greaterQS = new int[numFrames];
095 numPointsBUFF = 0;
096 pointsBUFF = new int[numFrames];
097 bytesPointsBUFF = new int[numFrames];
098 trendsBUFF = new boolean[numFrames];
099 int bytesTX = 0; //number of total bytes currently transmitted
100 float reachMSE = 0f; //current overall MSE
101 for(int frame = firstFrame; frame <= lastFrame; frame++){
102 bytesTX += layersConfig[frame][ layersTX[frame] ][0];
103 reachMSE += layersConfig[frame][ layersTX[frame] ][2];
104 }
105
106 //Sort lists
107 sortWorstFrames();
108 sortBestFrames();
109 //Start the monitoring of the buffer occupancy
110 fillBufferState();
111
112 //FAST algorithm
113 float lastReachMSE = 0f;
114 do{
115 lastReachMSE = reachMSE;
116
117 //Remove layers while the buffer constraints are not violated
118 int firstFrameI = 0;
119 int frameI = 0;
120 do{
121 frameI = firstFrameI;
122 while( (frameI < worstFrames.length) &&
123 (layersTX[ worstFrames[frameI] ]-1 <= 0)
124 ){
125 frameI++;
126 }
127 if(frameI < worstFrames.length){
128 int seekFrame = worstFrames[frameI];
129 layersTX[seekFrame]--;
130 updateBufferState(seekFrame, (int) layersConfig[seekFrame][ layersTX[seekFrame] ][0] -
131 (int) layersConfig[seekFrame][ layersTX[seekFrame]+1 ][0]);
132 if(!bufferViolation()){
133 bytesTX = bytesTX - (int) layersConfig[seekFrame][ layersTX[seekFrame]+1 ][0] +
134 (int) layersConfig[seekFrame][ layersTX[seekFrame] ][0];
135 reachMSE = reachMSE - (int) layersConfig[seekFrame][ layersTX[seekFrame]+1 ][2] +
136 (int) layersConfig[seekFrame][ layersTX[seekFrame] ][2];
137 resortWorstFrame(frameI);
138 }else{
139 layersTX[seekFrame]++;
140 updateBufferState(seekFrame,
141 (int) layersConfig[seekFrame][ layersTX[seekFrame] ][0] -
142 (int) layersConfig[seekFrame][ layersTX[seekFrame]-1 ][0]);
143 firstFrameI = frameI + 1;
144 }
145 }
146 }while(frameI < worstFrames.length);
147
148 //Add layers following the path of steepest slope
149 firstFrameI = 0;
150 do{
151 frameI = firstFrameI;
152 while( (frameI < bestFrames.length) &&
153 ( (layersConfig[ bestFrames[frameI] ][ layersTX[ bestFrames[frameI] ] ][1] == 0f) ||
154 (layersTX[ bestFrames[frameI] ]+1 >= layersConfig[ bestFrames[frameI] ].length) ||
155 (bytesTX -
156 (int) layersConfig[ bestFrames[frameI] ][ layersTX[ bestFrames[frameI] ] ][0] +
157 (int) layersConfig[ bestFrames[frameI] ][ layersTX[ bestFrames[frameI] ]+1 ][0]
158 > maxBytesTX) //max channel capacity
159 ) ){
160 frameI++;
161 }
162 if(frameI < bestFrames.length){
163 int seekFrame = bestFrames[frameI];
164 layersTX[seekFrame]++;
165 updateBufferState(seekFrame,
166 (int) layersConfig[seekFrame][ layersTX[seekFrame] ][0] -
167 (int) layersConfig[seekFrame][ layersTX[seekFrame]-1 ][0]);
168 if(!bufferViolation()){
169 bytesTX = bytesTX - (int) layersConfig[seekFrame][ layersTX[seekFrame]-1 ][0] +
170 (int) layersConfig[seekFrame][ layersTX[seekFrame] ][0];
171 reachMSE = reachMSE - (int) layersConfig[seekFrame][ layersTX[seekFrame]-1 ][2] +
172 (int) layersConfig[seekFrame][ layersTX[seekFrame] ][2];
173 resortBestFrame(frameI);
174 }else{
175 layersTX[seekFrame]--;
176 updateBufferState(seekFrame,
177 (int) layersConfig[seekFrame][ layersTX[seekFrame] ][0] -
178 (int) layersConfig[seekFrame][ layersTX[seekFrame]+1 ][0]);
179 firstFrameI = frameI + 1;
180 }
181 }
182 }while(frameI < bestFrames.length);
183
184 }while(lastReachMSE != reachMSE); //conservative policy
185 //}while(lastReachMSE > reachMSE); //conservative policy
186 //}while((lastReachMSE / (float)numFrames) - reachMSE / ((float)numFrames) > 0.01f); //heuristic
187 }
188
189 /**
190 * Constructs the sorted list of worstFrames.
191 */
192 private static void sortWorstFrames(){
193 //Initialize the list
194 for(int frame = 0; frame < worstFrames.length; frame++){
195 worstFrames[frame] = worstFramesLUT[frame] = frame + firstFrame;
196 }
197 //Sort the list
198 QSWorstFrames(0, worstFrames.length-1);
199 }
200
201 /**
202 * Recursive QuickSort algorithm for the list of worstFrames.
203 *
204 * @param begin
205 * @param end
206 */
207 static private void QSWorstFrames(int begin, int end){
208 int numLess = 0;
209 int numGreater = 0;
210 int pivot = (begin+end) / 2; //somewhat random, but sufficiently good in average
211 int pivotValue = worstFrames[pivot];
212 float pivotSlope = layersConfig[ pivotValue ][ layersTX[ pivotValue ] ][criteria];
213 for(int i = begin; i < pivot; i++){
214 float currSlope = layersConfig[ worstFrames[i] ][ layersTX[ worstFrames[i] ] ][criteria];
215 if(currSlope < pivotSlope){
216 worstFramesLUT[ worstFrames[i] - firstFrame ] = begin + numLess;
217 lessQS[numLess++] = worstFrames[i];
218 }else
219 if(currSlope > pivotSlope){
220 worstFramesLUT[ worstFrames[i] - firstFrame ] = begin + numGreater;
221 greaterQS[numGreater++] = worstFrames[i];
222 }else
223 if(worstFrames[i] < pivotValue){
224 worstFramesLUT[ worstFrames[i] - firstFrame ] = begin + numLess;
225 lessQS[numLess++] = worstFrames[i];
226 }else{
227 worstFramesLUT[ worstFrames[i] - firstFrame ] = begin + numGreater;
228 greaterQS[numGreater++] = worstFrames[i];
229 }
230 }
231 for(int i = pivot+1; i <= end; i++){
232 float currSlope = layersConfig[ worstFrames[i] ][ layersTX[ worstFrames[i] ] ][criteria];
233 if(currSlope < pivotSlope){
234 worstFramesLUT[ worstFrames[i] - firstFrame ] = begin + numLess;
235 lessQS[numLess++] = worstFrames[i];
236 }else
237 if(currSlope > pivotSlope){
238 worstFramesLUT[ worstFrames[i] - firstFrame ] = begin + numGreater;
239 greaterQS[numGreater++] = worstFrames[i];
240 }else
241 if(worstFrames[i] < pivotValue){
242 worstFramesLUT[ worstFrames[i] - firstFrame ] = begin + numLess;
243 lessQS[numLess++] = worstFrames[i];
244 }else{
245 worstFramesLUT[ worstFrames[i] - firstFrame ] = begin + numGreater;
246 greaterQS[numGreater++] = worstFrames[i];
247 }
248 }
249 System.arraycopy(lessQS, 0, worstFrames, begin, numLess);
250 worstFrames[begin + numLess] = pivotValue;
251 System.arraycopy(greaterQS, 0, worstFrames, begin + numLess + 1, numGreater);
252
253 //Update greaters LUT now that we known the final number of numLess
254 pivot = begin + numLess;
255 for(int i = pivot + 1; i <= end; i++){
256 worstFramesLUT[ worstFrames[i] - firstFrame ] += numLess + 1;
257 }
258 worstFramesLUT[ pivotValue - firstFrame ] = pivot;
259
260 if(begin + 1 < pivot){
261 QSWorstFrames(begin, pivot);
262 }
263 if(pivot + 1 < end){
264 QSWorstFrames(pivot + 1, end);
265 }
266 }
267
268 /**
269 * Sorts the specified frame in both lists.
270 *
271 * @param seekFrameI the index in the list belonging to the frame that have to be resorted
272 */
273 private static void resortWorstFrame(int seekFrameI) throws Exception{
274 int seekFrame = worstFrames[seekFrameI];
275
276 //Resort the sought frame within the list worstFrames
277 //bisection search
278 int up = worstFrames.length - 1;
279 int down = seekFrameI;
280 int mid = (up + down) / 2;
281 while((mid > down) && (mid < up)){
282 if(layersConfig[ worstFrames[mid] ][ layersTX[ worstFrames[mid] ] ][criteria] <
283 layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]){
284 down = mid;
285 }else if(layersConfig[ worstFrames[mid] ][ layersTX[ worstFrames[mid] ] ][criteria] >
286 layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]){
287 up = mid;
288 }else if(worstFrames[mid] < seekFrame){ //the second order of the list is by frame number
289 //(it could be avoided but, curiosously, it achieves better results this way)
290 down = mid;
291 }else{
292 up = mid;
293 }
294 mid = (up + down) / 2;
295 }
296 if( ((mid == down) && (mid+1 < worstFrames.length)) &&
297 ( (layersConfig[ worstFrames[mid+1] ][ layersTX[ worstFrames[mid+1] ] ][criteria] < layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]) ||
298 ( (layersConfig[ worstFrames[mid+1] ][ layersTX[ worstFrames[mid+1] ] ][criteria] == layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]) &&
299 (worstFrames[mid+1] < seekFrame) )
300 )){
301 mid++;
302 }else
303 if( (layersConfig[ worstFrames[mid] ][ layersTX[ worstFrames[mid] ] ][criteria] > layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]) ||
304 ( (layersConfig[ worstFrames[mid] ][ layersTX[ worstFrames[mid] ] ][criteria] == layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]) &&
305 (worstFrames[mid] > seekFrame))
306 ){
307 mid--;
308 }
309 //Update frames between seekFrameI and mid in worstFramesLUT
310 for(int i = seekFrameI + 1; i <= mid; i++){
311 worstFramesLUT[ worstFrames[i] - firstFrame ]--;
312 }
313 //Move
314 System.arraycopy(worstFrames, seekFrameI + 1, worstFrames, seekFrameI, mid - seekFrameI);
315 worstFrames[mid] = seekFrame;
316 worstFramesLUT[seekFrame - firstFrame] = mid;
317
318 //Resort the sought frame within the list of bestFrames
319 int seekFrameI2 = bestFramesLUT[seekFrame - firstFrame];
320 //bisection search
321 up = seekFrameI2;
322 down = 0;
323 int mid2 = (up + down) / 2;
324 float midDLSlope = 0f;
325 float seekFrameDLSlope = layersTX[seekFrame] + 1 < layersConfig[seekFrame].length ?
326 layersConfig[seekFrame][ layersTX[seekFrame] + 1 ][criteria]:
327 -Float.MAX_VALUE;
328 while((mid2 > down) && (mid2 < up)){
329 midDLSlope = layersTX[ bestFrames[mid2] ] + 1 < layersConfig[ bestFrames[mid2] ].length ?
330 layersConfig[ bestFrames[mid2] ][ layersTX[ bestFrames[mid2] ] + 1 ][criteria]:
331 -Float.MAX_VALUE;
332 if(midDLSlope > seekFrameDLSlope){
333 down = mid2;
334 }else if(midDLSlope < seekFrameDLSlope){
335 up = mid2;
336 }else if(bestFrames[mid2] < seekFrame){ //the second order of the list is by frame number (it could be avoided but,
337 //curiosously, it achieves better results this way)
338 down = mid2;
339 }else{
340 up = mid2;
341 }
342 mid2 = (up + down) / 2;
343 }
344 if(mid2 == down){
345 midDLSlope = layersTX[ bestFrames[mid2] ] + 1 < layersConfig[ bestFrames[mid2] ].length ?
346 layersConfig[ bestFrames[mid2] ][ layersTX[ bestFrames[mid2] ] + 1 ][criteria]:
347 -Float.MAX_VALUE;
348 if( (midDLSlope > seekFrameDLSlope) ||
349 ( (midDLSlope == seekFrameDLSlope) &&
350 (bestFrames[mid2] < seekFrame))
351 ){
352 mid2++;
353 }
354 }else if(mid2 > 0){
355 midDLSlope = layersTX[ bestFrames[mid2-1] ] + 1 < layersConfig[ bestFrames[mid2-1] ].length ?
356 layersConfig[ bestFrames[mid2-1] ][ layersTX[ bestFrames[mid2-1] ] + 1 ][criteria]:
357 -Float.MAX_VALUE;
358 if( (midDLSlope < seekFrameDLSlope) ||
359 ( (midDLSlope == seekFrameDLSlope) &&
360 (bestFrames[mid2-1] > seekFrame))
361 ){
362 mid2--;
363 }
364 }
365 //Update frames between mid2 and seekFrameI2 in bestFramesLUT
366 for(int i = mid2; i < seekFrameI2; i++){
367 bestFramesLUT[ bestFrames[i] - firstFrame ]++;
368 }
369 //Move
370 System.arraycopy(bestFrames, mid2, bestFrames, mid2 + 1, seekFrameI2 - mid2);
371 bestFrames[mid2] = seekFrame;
372 bestFramesLUT[seekFrame - firstFrame] = mid2;
373 }
374
375 /**
376 * Constructs the sorted list of bestFrames.
377 */
378 private static void sortBestFrames(){
379 //Initialize the list
380 for(int frame = 0; frame < bestFrames.length; frame++){
381 bestFrames[frame] = bestFramesLUT[frame] = frame + firstFrame;
382 }
383 //Sort the list
384 QSBestFrames(0, bestFrames.length-1);
385 }
386
387 /**
388 * Recursive QuickSort algorithm for the list of bestFrames.
389 *
390 * @param begin
391 * @param end
392 */
393 static private void QSBestFrames(int begin, int end){
394 int numLess = 0;
395 int numGreater = 0;
396 int pivot = (begin+end) / 2; //somewhat random, but sufficiently good in average
397 int pivotValue = bestFrames[pivot];
398 float pivotSlope = layersTX[pivotValue] + 1 < layersConfig[pivotValue].length ?
399 layersConfig[pivotValue][ layersTX[pivotValue] + 1 ][criteria]:
400 -Float.MAX_VALUE;
401 for(int i = begin; i < pivot; i++){
402 float currSlope = layersTX[bestFrames[i]] + 1 < layersConfig[bestFrames[i]].length ?
403 layersConfig[bestFrames[i]][ layersTX[bestFrames[i]] + 1 ][criteria]:
404 -Float.MAX_VALUE;
405 if(currSlope > pivotSlope){
406 bestFramesLUT[ bestFrames[i] - firstFrame ] = begin + numLess;
407 lessQS[numLess++] = bestFrames[i];
408 }else
409 if(currSlope < pivotSlope){
410 bestFramesLUT[ bestFrames[i] - firstFrame ] = begin + numGreater;
411 greaterQS[numGreater++] = bestFrames[i];
412 }else
413 if(bestFrames[i] < pivotValue){
414 bestFramesLUT[ bestFrames[i] - firstFrame ] = begin + numLess;
415 lessQS[numLess++] = bestFrames[i];
416 }else{
417 bestFramesLUT[ bestFrames[i] - firstFrame ] = begin + numGreater;
418 greaterQS[numGreater++] = bestFrames[i];
419 }
420 }
421 for(int i = pivot+1; i <= end; i++){
422 float currSlope = layersTX[bestFrames[i]] + 1 < layersConfig[bestFrames[i]].length ?
423 layersConfig[bestFrames[i]][ layersTX[bestFrames[i]] + 1 ][criteria]:
424 -Float.MAX_VALUE;
425 if(currSlope > pivotSlope){
426 bestFramesLUT[ bestFrames[i] - firstFrame ] = begin + numLess;
427 lessQS[numLess++] = bestFrames[i];
428 }else
429 if(currSlope < pivotSlope){
430 bestFramesLUT[ bestFrames[i] - firstFrame ] = begin + numGreater;
431 greaterQS[numGreater++] = bestFrames[i];
432 }else
433 if(bestFrames[i] < pivotValue){
434 bestFramesLUT[ bestFrames[i] - firstFrame ] = begin + numLess;
435 lessQS[numLess++] = bestFrames[i];
436 }else{
437 bestFramesLUT[ bestFrames[i] - firstFrame ] = begin + numGreater;
438 greaterQS[numGreater++] = bestFrames[i];
439 }
440 }
441 System.arraycopy(lessQS, 0, bestFrames, begin, numLess);
442 bestFrames[begin + numLess] = pivotValue;
443 System.arraycopy(greaterQS, 0, bestFrames, begin + numLess + 1, numGreater);
444
445 //Update greaters LUT now that we known the final number of numLess
446 pivot = begin + numLess;
447 for(int i = pivot + 1; i <= end; i++){
448 bestFramesLUT[ bestFrames[i] - firstFrame ] += numLess + 1;
449 }
450 bestFramesLUT[ pivotValue - firstFrame ] = pivot;
451
452 if(begin + 1 < pivot){
453 QSBestFrames(begin, pivot);
454 }
455 if(pivot + 1 < end){
456 QSBestFrames(pivot + 1, end);
457 }
458 }
459
460 /**
461 * Sorts the specified frame in the list.
462 *
463 * @param seekFrameI the index in the list belonging to the frame that have to be resorted
464 */
465 private static void resortBestFrame(int seekFrameI) throws Exception{
466 int seekFrame = bestFrames[seekFrameI];
467
468 //Resort the bestFrames list
469 //bisection search
470 int up = bestFrames.length - 1;
471 int down = seekFrameI;
472 int mid = (up + down) / 2;
473 float midDLSlope = 0f;
474 float seekFrameDLSlope = layersTX[seekFrame] + 1 < layersConfig[seekFrame].length ?
475 layersConfig[seekFrame][ layersTX[seekFrame] + 1 ][criteria]:
476 -Float.MAX_VALUE;
477 while((mid > down) && (mid < up)){
478 midDLSlope = layersTX[ bestFrames[mid] ] + 1 < layersConfig[ bestFrames[mid] ].length ?
479 layersConfig[ bestFrames[mid] ][ layersTX[ bestFrames[mid] ] + 1 ][criteria]:
480 -Float.MAX_VALUE;
481 if(midDLSlope > seekFrameDLSlope){
482 down = mid;
483 }else if(midDLSlope < seekFrameDLSlope){
484 up = mid;
485 }else if(bestFrames[mid] < seekFrame){ //the second order of the list is by frame number (it could be avoided but,
486 //curiosously, it achieves better results this way)
487 down = mid;
488 }else{
489 up = mid;
490 }
491 mid = (up + down) / 2;
492 }
493 if((mid == down) && (mid+1 < bestFrames.length)){
494 midDLSlope = layersTX[ bestFrames[mid+1] ] + 1 < layersConfig[ bestFrames[mid+1] ].length ?
495 layersConfig[ bestFrames[mid+1] ][ layersTX[ bestFrames[mid+1] ] + 1 ][criteria]:
496 -Float.MAX_VALUE;
497 if( (midDLSlope > seekFrameDLSlope) ||
498 ((midDLSlope == seekFrameDLSlope) &&
499 (bestFrames[mid+1] < seekFrame))
500 ){
501 mid++;
502 }
503 }else{
504 midDLSlope = layersTX[ bestFrames[mid] ] + 1 < layersConfig[ bestFrames[mid] ].length ?
505 layersConfig[ bestFrames[mid] ][ layersTX[ bestFrames[mid] ] + 1 ][criteria]:
506 -Float.MAX_VALUE;
507 if( (midDLSlope < seekFrameDLSlope) ||
508 ((midDLSlope == seekFrameDLSlope) &&
509 (bestFrames[mid] > seekFrame))
510 ){
511 mid--;
512 }
513 }
514 //Update frames between seekFrameI and mid in worstFramesLUT
515 for(int i = seekFrameI + 1; i <= mid; i++){
516 bestFramesLUT[ bestFrames[i] - firstFrame ]--;
517 }
518 //Move
519 System.arraycopy(bestFrames, seekFrameI + 1, bestFrames, seekFrameI, mid - seekFrameI);
520 bestFrames[mid] = seekFrame;
521 bestFramesLUT[seekFrame - firstFrame] = mid;
522
523 //Resort the worstFrames list
524 int seekFrameI2 = worstFramesLUT[seekFrame - firstFrame];
525 //bisection search
526 up = seekFrameI2;
527 down = 0;
528 int mid2 = (up + down) / 2;
529 while((mid2 > down) && (mid2 < up)){
530 if(layersConfig[ worstFrames[mid2] ][ layersTX[ worstFrames[mid2] ] ][criteria] < layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]){
531 down = mid2;
532 }else if(layersConfig[ worstFrames[mid2] ][ layersTX[ worstFrames[mid2] ] ][criteria] > layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]){
533 up = mid2;
534 }else if(worstFrames[mid2] < seekFrame){ //the second order of the list is by frame number (it could be avoided but,
535 //curiosously, it achieves better results this way)
536 down = mid2;
537 }else{
538 up = mid2;
539 }
540 mid2 = (up + down) / 2;
541 }
542 if( (mid2 == down) &&
543 ( (layersConfig[ worstFrames[mid2] ][ layersTX[ worstFrames[mid2] ] ][criteria] < layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]) ||
544 ( (layersConfig[ worstFrames[mid2] ][ layersTX[ worstFrames[mid2] ] ][criteria] == layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]) &&
545 (worstFrames[mid2] < seekFrame) ) )
546 ){
547 mid2++;
548 }else
549 if( (mid2 > 0) &&
550 ( (layersConfig[ worstFrames[mid2-1] ][ layersTX[ worstFrames[mid2-1] ] ][criteria] > layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]) ||
551 ( (layersConfig[ worstFrames[mid2-1] ][ layersTX[ worstFrames[mid2-1] ] ][criteria] == layersConfig[seekFrame][ layersTX[seekFrame] ][criteria]) &&
552 (worstFrames[mid2-1] > seekFrame)))
553 ){
554 mid2--;
555 }
556 //Update frames between mid2 and seekFrameI2 in worstFramesLUT
557 for(int i = mid2; i < seekFrameI2; i++){
558 worstFramesLUT[ worstFrames[i] - firstFrame ]++;
559 }
560 //Move
561 System.arraycopy(worstFrames, mid2, worstFrames, mid2 + 1, seekFrameI2 - mid2);
562 worstFrames[mid2] = seekFrame;
563 worstFramesLUT[seekFrame - firstFrame] = mid2;
564 }
565
566 /**
567 * This function monitors the delivery policy by filling the structure bytesBUFF, within the specified range of frames.
568 */
569 private static void fillBufferState(){
570 numPointsBUFF = 0;
571 int currBytesBUFF = avBytesTX - (int) layersConfig[firstFrame][ layersTX[firstFrame] ][0];
572 boolean currTrend = currBytesBUFF > 0;
573 int currFrame = firstFrame + 1;
574 while(currFrame <= lastFrame){
575 if(currTrend){ //buffer filling
576 while((currFrame <= lastFrame) && (avBytesTX - (int) layersConfig[currFrame][ layersTX[currFrame] ][0] > 0)){
577 currBytesBUFF += avBytesTX - (int) layersConfig[currFrame][ layersTX[currFrame] ][0];
578 currFrame++;
579 }
580 }else{ //buffer emptying
581 while((currFrame <= lastFrame) && (avBytesTX - (int) layersConfig[currFrame][ layersTX[currFrame] ][0] <= 0)){
582 currBytesBUFF += avBytesTX - (int) layersConfig[currFrame][ layersTX[currFrame] ][0];
583 currFrame++;
584 }
585 }
586 pointsBUFF[numPointsBUFF] = currFrame - 1;
587 bytesPointsBUFF[numPointsBUFF] = currBytesBUFF;
588 trendsBUFF[numPointsBUFF] = currTrend;
589 numPointsBUFF++;
590 currTrend = !currTrend;
591 }
592 }
593
594 /**
595 * This function checks, within the range of frames, if the buffer's size has been exceeded.
596 *
597 * @return true if a buffer's violation occurs
598 */
599 private static boolean bufferViolation(){
600 boolean buffViolation = false;
601 int point = 0;
602 while((point < numPointsBUFF) && (bytesPointsBUFF[point] >= buffLowBound) && (bytesPointsBUFF[point] <= buffUpBound)){
603 point++;
604 }
605 if(point < numPointsBUFF){
606 buffViolation = true;
607 }
608 return(buffViolation);
609 }
610
611 /**
612 * Update the buffer state from the specified frame to the end of the sequence.
613 *
614 * @param updateFrame the frame that has changed
615 * @param bytesDiff the difference in bytes from the previously transmitted layer and the current one
616 * @throws Exception when the specified frame is not in the range [firstFrame, lastFrame]
617 */
618 private static void updateBufferState(int updateFrame, int bytesDiff) throws Exception{
619 //Find the point in the smart buffer
620 int up = numPointsBUFF;
621 int down = 0;
622 int mid = (up + down) / 2;
623 while((mid > down) && (mid < up)){
624 if(pointsBUFF[mid] < updateFrame){
625 down = mid;
626 }else{
627 up = mid;
628 }
629 mid = (up + down) / 2;
630 }
631 if(updateFrame > pointsBUFF[mid]){
632 mid++;
633 }else
634 if((mid > 0) && (updateFrame >= pointsBUFF[mid-1])){
635 mid--;
636 }
637 int currPointBUFF = mid;
638
639 //Update the smart buffer
640 boolean currTrendBUFF = trendsBUFF[currPointBUFF];
641
642 if( ( (trendsBUFF[currPointBUFF]) && (avBytesTX - (int) layersConfig[updateFrame][ layersTX[updateFrame] ][0] <= 0)) ||
643 ( (!trendsBUFF[currPointBUFF]) && (avBytesTX - (int) layersConfig[updateFrame][ layersTX[updateFrame] ][0] > 0))
644 ){
645 //Buffer changes trend, several checks needed
646 if(updateFrame != pointsBUFF[currPointBUFF]){
647 if(currPointBUFF == 0){
648 if(updateFrame == firstFrame){
649 insertPointsBUFF(currPointBUFF, 1);
650 pointsBUFF[currPointBUFF] = updateFrame;
651 bytesPointsBUFF[currPointBUFF] = avBytesTX - (int) layersConfig[updateFrame][ layersTX[updateFrame] ][0];
652 trendsBUFF[currPointBUFF] = !currTrendBUFF;
653 currPointBUFF++;
654 }else{
655 int tmpBytesBUFF = computeBytesBUFF(updateFrame - 1); //necessary before introducing new points
656
657 insertPointsBUFF(currPointBUFF, 2);
658 pointsBUFF[currPointBUFF] = updateFrame - 1;
659 bytesPointsBUFF[currPointBUFF] = tmpBytesBUFF;
660 trendsBUFF[currPointBUFF] = currTrendBUFF;
661 pointsBUFF[currPointBUFF+1] = updateFrame;
662 bytesPointsBUFF[currPointBUFF+1] =
663 tmpBytesBUFF +
664 avBytesTX - (int) layersConfig[updateFrame][ layersTX[updateFrame] ][0];
665 trendsBUFF[currPointBUFF+1] = !currTrendBUFF;
666 currPointBUFF += 2;
667 }
668 }else
669 if(pointsBUFF[currPointBUFF-1] == updateFrame-1){
670 pointsBUFF[currPointBUFF-1] = updateFrame;
671 bytesPointsBUFF[currPointBUFF-1] += avBytesTX - (int) layersConfig[updateFrame][ layersTX[updateFrame] ][0];
672 }else{
673 int tmpBytesBUFF = computeBytesBUFF(updateFrame - 1); //necessary before introducing new points
674
675 insertPointsBUFF(currPointBUFF, 2);
676 pointsBUFF[currPointBUFF] = updateFrame - 1;
677 bytesPointsBUFF[currPointBUFF] = tmpBytesBUFF;
678 trendsBUFF[currPointBUFF] = currTrendBUFF;
679 pointsBUFF[currPointBUFF+1] = updateFrame;
680 bytesPointsBUFF[currPointBUFF+1] =
681 tmpBytesBUFF +
682 avBytesTX - (int) layersConfig[updateFrame][ layersTX[updateFrame] ][0];
683 trendsBUFF[currPointBUFF+1] = !currTrendBUFF;
684 currPointBUFF += 2;
685 }
686 }else{ //updateFrame is a point within pointsBUFF
687 if(currPointBUFF == 0){
688 if(updateFrame == firstFrame){
689 deletePointsBUFF(currPointBUFF, 1);
690 }else{
691 pointsBUFF[currPointBUFF] = updateFrame - 1;
692 bytesPointsBUFF[currPointBUFF] = computeBytesBUFF(updateFrame - 1);
693 currPointBUFF++;
694 }
695 }else
696 if(pointsBUFF[currPointBUFF-1] == updateFrame-1){
697 if(currPointBUFF < numPointsBUFF - 1){
698 deletePointsBUFF(currPointBUFF-1, 2);
699 currPointBUFF--;
700 }else{ //Last point
701 deletePointsBUFF(currPointBUFF, 1);
702 pointsBUFF[currPointBUFF-1] = updateFrame;
703 bytesPointsBUFF[currPointBUFF-1] =
704 bytesPointsBUFF[currPointBUFF-1] +
705 avBytesTX - (int) layersConfig[updateFrame][ layersTX[updateFrame] ][0];
706 }
707 }else{
708 pointsBUFF[currPointBUFF] = updateFrame - 1;
709 bytesPointsBUFF[currPointBUFF] = computeBytesBUFF(updateFrame - 1);
710 currPointBUFF++;
711 if(currPointBUFF == numPointsBUFF){ //Last point
712 numPointsBUFF++;
713 pointsBUFF[currPointBUFF] = updateFrame;
714 bytesPointsBUFF[currPointBUFF] =
715 bytesPointsBUFF[currPointBUFF-1] +
716 avBytesTX - (int) layersConfig[updateFrame][ layersTX[updateFrame] ][0];
717 trendsBUFF[currPointBUFF] = !currTrendBUFF;
718 currPointBUFF++;
719 }
720 }
721 }
722 }
723
724 //Update following pointsBUFF
725 for(;currPointBUFF < numPointsBUFF; currPointBUFF++){
726 bytesPointsBUFF[currPointBUFF] -= bytesDiff;
727 }
728 }
729
730 /**
731 * Inserts news points in the smart buffer control.
732 *
733 * @param currPointBUFF point in which new points will be inserted
734 * @param numPoints number of points to be inserted
735 */
736 private static void insertPointsBUFF(int currPointBUFF, int numPoints){
737 System.arraycopy(pointsBUFF, currPointBUFF, pointsBUFF, currPointBUFF+numPoints, numPointsBUFF-currPointBUFF);
738 System.arraycopy(bytesPointsBUFF, currPointBUFF, bytesPointsBUFF, currPointBUFF+numPoints, numPointsBUFF-currPointBUFF);
739 System.arraycopy(trendsBUFF, currPointBUFF, trendsBUFF, currPointBUFF+numPoints, numPointsBUFF-currPointBUFF);
740 numPointsBUFF += numPoints;
741 }
742
743 /**
744 * Deletes one point in the smart buffer control.
745 *
746 * @param currPointBUFF point to be removed
747 * @param numPoints number of points to be removed
748 */
749 private static void deletePointsBUFF(int currPointBUFF, int numPoints){
750 System.arraycopy(pointsBUFF, currPointBUFF+numPoints, pointsBUFF, currPointBUFF, numPointsBUFF-currPointBUFF-numPoints);
751 System.arraycopy(bytesPointsBUFF, currPointBUFF+numPoints, bytesPointsBUFF, currPointBUFF, numPointsBUFF-currPointBUFF-numPoints);
752 System.arraycopy(trendsBUFF, currPointBUFF+numPoints, trendsBUFF, currPointBUFF, numPointsBUFF-currPointBUFF-numPoints);
753 numPointsBUFF -= numPoints;
754 }
755
756 /**
757 * Computes the number of bytes in the buffer when the specified frame is transmitted.
758 *
759 * @param targetFrame
760 * @return the number of bytes in the buffer in the moment the targetFrame is transmitted
761 */
762 private static int computeBytesBUFF(int targetFrame){
763 //Find the point in the smart buffer
764 int up = numPointsBUFF;
765 int down = 0;
766 int mid = (up + down) / 2;
767 while((mid > down) && (mid < up)){
768 if(pointsBUFF[mid] < targetFrame){
769 down = mid;
770 }else{
771 up = mid;
772 }
773 mid = (up + down) / 2;
774 }
775 if(targetFrame > pointsBUFF[mid]){
776 mid++;
777 }else
778 if((mid > 0) && (targetFrame >= pointsBUFF[mid-1])){
779 mid--;
780 }
781 int currPointBUFF = mid;
782
783 int bytesBUFF = 0;
784 int frame = firstFrame;
785 if(currPointBUFF != 0){
786 bytesBUFF = bytesPointsBUFF[currPointBUFF-1];
787 frame = pointsBUFF[currPointBUFF-1] + 1;
788 }
789 for(; frame <= targetFrame; frame++){
790 bytesBUFF += avBytesTX - (int) layersConfig[frame][ layersTX[frame] ][0];
791 }
792 return(bytesBUFF);
793 }
794 }
|