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