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
init_rate_histogram(const vpx_codec_enc_cfg_t * cfg,const vpx_rational_t * fps)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
destroy_rate_histogram(struct rate_hist * hist)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
update_rate_histogram(struct rate_hist * hist,const vpx_codec_enc_cfg_t * cfg,const vpx_codec_cx_pkt_t * pkt)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
merge_hist_buckets(struct hist_bucket * bucket,int max_buckets,int * num_buckets)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
show_histogram(const struct hist_bucket * bucket,int buckets,int total,int scale)194 static void show_histogram(const struct hist_bucket *bucket, int buckets,
195 int total, int scale) {
196 int width1, width2;
197 int i;
198
199 if (!buckets) return;
200 assert(bucket != NULL);
201 assert(buckets > 0);
202
203 switch ((int)(log(bucket[buckets - 1].high) / log(10)) + 1) {
204 case 1:
205 case 2:
206 width1 = 4;
207 width2 = 2;
208 break;
209 case 3:
210 width1 = 5;
211 width2 = 3;
212 break;
213 case 4:
214 width1 = 6;
215 width2 = 4;
216 break;
217 case 5:
218 width1 = 7;
219 width2 = 5;
220 break;
221 case 6:
222 width1 = 8;
223 width2 = 6;
224 break;
225 case 7:
226 width1 = 9;
227 width2 = 7;
228 break;
229 default:
230 width1 = 12;
231 width2 = 10;
232 break;
233 }
234
235 for (i = 0; i < buckets; i++) {
236 int len;
237 int j;
238 float pct;
239
240 pct = (float)(100.0 * bucket[i].count / total);
241 len = HIST_BAR_MAX * bucket[i].count / scale;
242 if (len < 1) len = 1;
243 assert(len <= HIST_BAR_MAX);
244
245 if (bucket[i].low == bucket[i].high)
246 fprintf(stderr, "%*d %*s: ", width1, bucket[i].low, width2, "");
247 else
248 fprintf(stderr, "%*d-%*d: ", width1, bucket[i].low, width2,
249 bucket[i].high);
250
251 for (j = 0; j < HIST_BAR_MAX; j++) fprintf(stderr, j < len ? "=" : " ");
252 fprintf(stderr, "\t%5d (%6.2f%%)\n", bucket[i].count, pct);
253 }
254 }
255
show_q_histogram(const int counts[64],int max_buckets)256 void show_q_histogram(const int counts[64], int max_buckets) {
257 struct hist_bucket bucket[64];
258 int buckets = 0;
259 int total = 0;
260 int scale;
261 int i;
262
263 for (i = 0; i < 64; i++) {
264 if (counts[i]) {
265 bucket[buckets].low = bucket[buckets].high = i;
266 bucket[buckets].count = counts[i];
267 buckets++;
268 total += counts[i];
269 }
270 }
271
272 fprintf(stderr, "\nQuantizer Selection:\n");
273 scale = merge_hist_buckets(bucket, max_buckets, &buckets);
274 show_histogram(bucket, buckets, total, scale);
275 }
276
show_rate_histogram(struct rate_hist * hist,const vpx_codec_enc_cfg_t * cfg,int max_buckets)277 void show_rate_histogram(struct rate_hist *hist, const vpx_codec_enc_cfg_t *cfg,
278 int max_buckets) {
279 int i, scale;
280 int buckets = 0;
281
282 if (hist == NULL || cfg == NULL) return;
283
284 for (i = 0; i < RATE_BINS; i++) {
285 if (hist->bucket[i].low == INT_MAX) continue;
286 hist->bucket[buckets++] = hist->bucket[i];
287 }
288
289 fprintf(stderr, "\nRate (over %dms window):\n", cfg->rc_buf_sz);
290 scale = merge_hist_buckets(hist->bucket, max_buckets, &buckets);
291 show_histogram(hist->bucket, buckets, hist->total, scale);
292 }
293