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