1 /* 2 * Copyright (c) 2014 The WebM project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 #include <assert.h> 12 #include <stdlib.h> 13 #include <limits.h> 14 #include <stdio.h> 15 #include <math.h> 16 17 #include "./rate_hist.h" 18 19 #define RATE_BINS 100 20 #define HIST_BAR_MAX 40 21 22 struct hist_bucket { 23 int low; 24 int high; 25 int count; 26 }; 27 28 struct rate_hist { 29 int64_t *pts; 30 int *sz; 31 int samples; 32 int frames; 33 struct hist_bucket bucket[RATE_BINS]; 34 int total; 35 }; 36 37 struct rate_hist *init_rate_histogram(const vpx_codec_enc_cfg_t *cfg, 38 const vpx_rational_t *fps) { 39 int i; 40 struct rate_hist *hist = malloc(sizeof(*hist)); 41 42 // Determine the number of samples in the buffer. Use the file's framerate 43 // to determine the number of frames in rc_buf_sz milliseconds, with an 44 // adjustment (5/4) to account for alt-refs 45 hist->samples = cfg->rc_buf_sz * 5 / 4 * fps->num / fps->den / 1000; 46 47 // prevent division by zero 48 if (hist->samples == 0) 49 hist->samples = 1; 50 51 hist->frames = 0; 52 hist->total = 0; 53 54 hist->pts = calloc(hist->samples, sizeof(*hist->pts)); 55 hist->sz = calloc(hist->samples, sizeof(*hist->sz)); 56 for (i = 0; i < RATE_BINS; i++) { 57 hist->bucket[i].low = INT_MAX; 58 hist->bucket[i].high = 0; 59 hist->bucket[i].count = 0; 60 } 61 62 return hist; 63 } 64 65 void destroy_rate_histogram(struct rate_hist *hist) { 66 if (hist) { 67 free(hist->pts); 68 free(hist->sz); 69 free(hist); 70 } 71 } 72 73 void update_rate_histogram(struct rate_hist *hist, 74 const vpx_codec_enc_cfg_t *cfg, 75 const vpx_codec_cx_pkt_t *pkt) { 76 int i; 77 int64_t then = 0; 78 int64_t avg_bitrate = 0; 79 int64_t sum_sz = 0; 80 const int64_t now = pkt->data.frame.pts * 1000 * 81 (uint64_t)cfg->g_timebase.num / 82 (uint64_t)cfg->g_timebase.den; 83 84 int idx = hist->frames++ % hist->samples; 85 hist->pts[idx] = now; 86 hist->sz[idx] = (int)pkt->data.frame.sz; 87 88 if (now < cfg->rc_buf_initial_sz) 89 return; 90 91 then = now; 92 93 /* Sum the size over the past rc_buf_sz ms */ 94 for (i = hist->frames; i > 0 && hist->frames - i < hist->samples; i--) { 95 const int i_idx = (i - 1) % hist->samples; 96 97 then = hist->pts[i_idx]; 98 if (now - then > cfg->rc_buf_sz) 99 break; 100 sum_sz += hist->sz[i_idx]; 101 } 102 103 if (now == then) 104 return; 105 106 avg_bitrate = sum_sz * 8 * 1000 / (now - then); 107 idx = (int)(avg_bitrate * (RATE_BINS / 2) / (cfg->rc_target_bitrate * 1000)); 108 if (idx < 0) 109 idx = 0; 110 if (idx > RATE_BINS - 1) 111 idx = RATE_BINS - 1; 112 if (hist->bucket[idx].low > avg_bitrate) 113 hist->bucket[idx].low = (int)avg_bitrate; 114 if (hist->bucket[idx].high < avg_bitrate) 115 hist->bucket[idx].high = (int)avg_bitrate; 116 hist->bucket[idx].count++; 117 hist->total++; 118 } 119 120 static int merge_hist_buckets(struct hist_bucket *bucket, 121 int max_buckets, int *num_buckets) { 122 int small_bucket = 0, merge_bucket = INT_MAX, big_bucket = 0; 123 int buckets = *num_buckets; 124 int i; 125 126 /* Find the extrema for this list of buckets */ 127 big_bucket = small_bucket = 0; 128 for (i = 0; i < buckets; i++) { 129 if (bucket[i].count < bucket[small_bucket].count) 130 small_bucket = i; 131 if (bucket[i].count > bucket[big_bucket].count) 132 big_bucket = i; 133 } 134 135 /* If we have too many buckets, merge the smallest with an adjacent 136 * bucket. 137 */ 138 while (buckets > max_buckets) { 139 int last_bucket = buckets - 1; 140 141 /* merge the small bucket with an adjacent one. */ 142 if (small_bucket == 0) 143 merge_bucket = 1; 144 else if (small_bucket == last_bucket) 145 merge_bucket = last_bucket - 1; 146 else if (bucket[small_bucket - 1].count < bucket[small_bucket + 1].count) 147 merge_bucket = small_bucket - 1; 148 else 149 merge_bucket = small_bucket + 1; 150 151 assert(abs(merge_bucket - small_bucket) <= 1); 152 assert(small_bucket < buckets); 153 assert(big_bucket < buckets); 154 assert(merge_bucket < buckets); 155 156 if (merge_bucket < small_bucket) { 157 bucket[merge_bucket].high = bucket[small_bucket].high; 158 bucket[merge_bucket].count += bucket[small_bucket].count; 159 } else { 160 bucket[small_bucket].high = bucket[merge_bucket].high; 161 bucket[small_bucket].count += bucket[merge_bucket].count; 162 merge_bucket = small_bucket; 163 } 164 165 assert(bucket[merge_bucket].low != bucket[merge_bucket].high); 166 167 buckets--; 168 169 /* Remove the merge_bucket from the list, and find the new small 170 * and big buckets while we're at it 171 */ 172 big_bucket = small_bucket = 0; 173 for (i = 0; i < buckets; i++) { 174 if (i > merge_bucket) 175 bucket[i] = bucket[i + 1]; 176 177 if (bucket[i].count < bucket[small_bucket].count) 178 small_bucket = i; 179 if (bucket[i].count > bucket[big_bucket].count) 180 big_bucket = i; 181 } 182 } 183 184 *num_buckets = buckets; 185 return bucket[big_bucket].count; 186 } 187 188 static void show_histogram(const struct hist_bucket *bucket, 189 int buckets, int total, int scale) { 190 const char *pat1, *pat2; 191 int i; 192 193 switch ((int)(log(bucket[buckets - 1].high) / log(10)) + 1) { 194 case 1: 195 case 2: 196 pat1 = "%4d %2s: "; 197 pat2 = "%4d-%2d: "; 198 break; 199 case 3: 200 pat1 = "%5d %3s: "; 201 pat2 = "%5d-%3d: "; 202 break; 203 case 4: 204 pat1 = "%6d %4s: "; 205 pat2 = "%6d-%4d: "; 206 break; 207 case 5: 208 pat1 = "%7d %5s: "; 209 pat2 = "%7d-%5d: "; 210 break; 211 case 6: 212 pat1 = "%8d %6s: "; 213 pat2 = "%8d-%6d: "; 214 break; 215 case 7: 216 pat1 = "%9d %7s: "; 217 pat2 = "%9d-%7d: "; 218 break; 219 default: 220 pat1 = "%12d %10s: "; 221 pat2 = "%12d-%10d: "; 222 break; 223 } 224 225 for (i = 0; i < buckets; i++) { 226 int len; 227 int j; 228 float pct; 229 230 pct = (float)(100.0 * bucket[i].count / total); 231 len = HIST_BAR_MAX * bucket[i].count / scale; 232 if (len < 1) 233 len = 1; 234 assert(len <= HIST_BAR_MAX); 235 236 if (bucket[i].low == bucket[i].high) 237 fprintf(stderr, pat1, bucket[i].low, ""); 238 else 239 fprintf(stderr, pat2, bucket[i].low, bucket[i].high); 240 241 for (j = 0; j < HIST_BAR_MAX; j++) 242 fprintf(stderr, j < len ? "=" : " "); 243 fprintf(stderr, "\t%5d (%6.2f%%)\n", bucket[i].count, pct); 244 } 245 } 246 247 void show_q_histogram(const int counts[64], int max_buckets) { 248 struct hist_bucket bucket[64]; 249 int buckets = 0; 250 int total = 0; 251 int scale; 252 int i; 253 254 for (i = 0; i < 64; i++) { 255 if (counts[i]) { 256 bucket[buckets].low = bucket[buckets].high = i; 257 bucket[buckets].count = counts[i]; 258 buckets++; 259 total += counts[i]; 260 } 261 } 262 263 fprintf(stderr, "\nQuantizer Selection:\n"); 264 scale = merge_hist_buckets(bucket, max_buckets, &buckets); 265 show_histogram(bucket, buckets, total, scale); 266 } 267 268 void show_rate_histogram(struct rate_hist *hist, 269 const vpx_codec_enc_cfg_t *cfg, int max_buckets) { 270 int i, scale; 271 int buckets = 0; 272 273 for (i = 0; i < RATE_BINS; i++) { 274 if (hist->bucket[i].low == INT_MAX) 275 continue; 276 hist->bucket[buckets++] = hist->bucket[i]; 277 } 278 279 fprintf(stderr, "\nRate (over %dms window):\n", cfg->rc_buf_sz); 280 scale = merge_hist_buckets(hist->bucket, max_buckets, &buckets); 281 show_histogram(hist->bucket, buckets, hist->total, scale); 282 } 283