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