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