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  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
120static 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
188static 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
247void 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
268void 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