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 = 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
destroy_rate_histogram(struct rate_hist * hist)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
update_rate_histogram(struct rate_hist * hist,const vpx_codec_enc_cfg_t * cfg,const vpx_codec_cx_pkt_t * pkt)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
merge_hist_buckets(struct hist_bucket * bucket,int max_buckets,int * num_buckets)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
show_histogram(const struct hist_bucket * bucket,int buckets,int total,int scale)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
show_q_histogram(const int counts[64],int max_buckets)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
show_rate_histogram(struct rate_hist * hist,const vpx_codec_enc_cfg_t * cfg,int max_buckets)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