/* *  Copyright (c) 2014 The WebM project authors. All Rights Reserved. * *  Use of this source code is governed by a BSD-style license *  that can be found in the LICENSE file in the root of the source *  tree. An additional intellectual property rights grant can be found *  in the file PATENTS.  All contributing project authors may *  be found in the AUTHORS file in the root of the source tree. */ #include <assert.h>#include <stdlib.h>#include <limits.h>#include <stdio.h>#include <math.h> #include "vpx_config.h"#include "./rate_hist.h" #define RATE_BINS 100#define HIST_BAR_MAX 40 struct hist_bucket {  int low;  int high;  int count;}; struct rate_hist {  int64_t *pts;  int *sz;  int samples;  int frames;  struct hist_bucket bucket[RATE_BINS];  int total;}; struct rate_hist *init_rate_histogram(const vpx_codec_enc_cfg_t *cfg,                                      const vpx_rational_t *fps) {  int i;  struct rate_hist *hist = calloc(1, sizeof(*hist));   if (hist == NULL || cfg == NULL || fps == NULL || fps->num == 0 ||      fps->den == 0) {    destroy_rate_histogram(hist);    return NULL;  }   // Determine the number of samples in the buffer. Use the file's framerate  // to determine the number of frames in rc_buf_sz milliseconds, with an  // adjustment (5/4) to account for alt-refs  hist->samples = cfg->rc_buf_sz * 5 / 4 * fps->num / fps->den / 1000;   // prevent division by zero  if (hist->samples == 0) hist->samples = 1;   hist->frames = 0;  hist->total = 0;   hist->pts = calloc(hist->samples, sizeof(*hist->pts));  hist->sz = calloc(hist->samples, sizeof(*hist->sz));  for (i = 0; i < RATE_BINS; i++) {    hist->bucket[i].low = INT_MAX;    hist->bucket[i].high = 0;    hist->bucket[i].count = 0;  }   return hist;} void destroy_rate_histogram(struct rate_hist *hist) {  if (hist) {    free(hist->pts);    free(hist->sz);    free(hist);  }} void update_rate_histogram(struct rate_hist *hist,                           const vpx_codec_enc_cfg_t *cfg,                           const vpx_codec_cx_pkt_t *pkt) {  int i;  int64_t then = 0;  int64_t avg_bitrate = 0;  int64_t sum_sz = 0;  const int64_t now = pkt->data.frame.pts * 1000 *                      (uint64_t)cfg->g_timebase.num /                      (uint64_t)cfg->g_timebase.den;   int idx;   if (hist == NULL || cfg == NULL || pkt == NULL) return;   idx = hist->frames++ % hist->samples;  hist->pts[idx] = now;  hist->sz[idx] = (int)pkt->data.frame.sz;   if (now < cfg->rc_buf_initial_sz) return;   if (!cfg->rc_target_bitrate) return;   then = now;   /* Sum the size over the past rc_buf_sz ms */  for (i = hist->frames; i > 0 && hist->frames - i < hist->samples; i--) {    const int i_idx = (i - 1) % hist->samples;     then = hist->pts[i_idx];    if (now - then > cfg->rc_buf_sz) break;    sum_sz += hist->sz[i_idx];  }   if (now == then) return;   avg_bitrate = sum_sz * 8 * 1000 / (now - then);  idx = (int)(avg_bitrate * (RATE_BINS / 2) / (cfg->rc_target_bitrate * 1000));  if (idx < 0) idx = 0;  if (idx > RATE_BINS - 1) idx = RATE_BINS - 1;  if (hist->bucket[idx].low > avg_bitrate)    hist->bucket[idx].low = (int)avg_bitrate;  if (hist->bucket[idx].high < avg_bitrate)    hist->bucket[idx].high = (int)avg_bitrate;  hist->bucket[idx].count++;  hist->total++;} static int merge_hist_buckets(struct hist_bucket *bucket, int max_buckets,                              int *num_buckets) {  int small_bucket = 0, merge_bucket = INT_MAX, big_bucket = 0;  int buckets;  int i;   assert(bucket != NULL);  assert(num_buckets != NULL);   buckets = *num_buckets;   /* Find the extrema for this list of buckets */  big_bucket = small_bucket = 0;  for (i = 0; i < buckets; i++) {    if (bucket[i].count < bucket[small_bucket].count) small_bucket = i;    if (bucket[i].count > bucket[big_bucket].count) big_bucket = i;  }   /* If we have too many buckets, merge the smallest with an adjacent   * bucket.   */  while (buckets > max_buckets) {    int last_bucket = buckets - 1;     /* merge the small bucket with an adjacent one. */    if (small_bucket == 0)      merge_bucket = 1;    else if (small_bucket == last_bucket)      merge_bucket = last_bucket - 1;    else if (bucket[small_bucket - 1].count < bucket[small_bucket + 1].count)      merge_bucket = small_bucket - 1;    else      merge_bucket = small_bucket + 1;     assert(abs(merge_bucket - small_bucket) <= 1);    assert(small_bucket < buckets);    assert(big_bucket < buckets);    assert(merge_bucket < buckets);     if (merge_bucket < small_bucket) {      bucket[merge_bucket].high = bucket[small_bucket].high;      bucket[merge_bucket].count += bucket[small_bucket].count;    } else {      bucket[small_bucket].high = bucket[merge_bucket].high;      bucket[small_bucket].count += bucket[merge_bucket].count;      merge_bucket = small_bucket;    }     assert(bucket[merge_bucket].low != bucket[merge_bucket].high);     buckets--;     /* Remove the merge_bucket from the list, and find the new small     * and big buckets while we're at it     */    big_bucket = small_bucket = 0;    for (i = 0; i < buckets; i++) {      if (i > merge_bucket) bucket[i] = bucket[i + 1];       if (bucket[i].count < bucket[small_bucket].count) small_bucket = i;      if (bucket[i].count > bucket[big_bucket].count) big_bucket = i;    }  }   *num_buckets = buckets;  return bucket[big_bucket].count;} static void show_histogram(const struct hist_bucket *bucket, int buckets,                           int total, int scale) {  const char *pat1, *pat2;  int i;   assert(bucket != NULL);   switch ((int)(log(bucket[buckets - 1].high) / log(10)) + 1) {    case 1:    case 2:      pat1 = "%4d %2s: ";      pat2 = "%4d-%2d: ";      break;    case 3:      pat1 = "%5d %3s: ";      pat2 = "%5d-%3d: ";      break;    case 4:      pat1 = "%6d %4s: ";      pat2 = "%6d-%4d: ";      break;    case 5:      pat1 = "%7d %5s: ";      pat2 = "%7d-%5d: ";      break;    case 6:      pat1 = "%8d %6s: ";      pat2 = "%8d-%6d: ";      break;    case 7:      pat1 = "%9d %7s: ";      pat2 = "%9d-%7d: ";      break;    default:      pat1 = "%12d %10s: ";      pat2 = "%12d-%10d: ";      break;  }   for (i = 0; i < buckets; i++) {    int len;    int j;    float pct;     pct = (float)(100.0 * bucket[i].count / total);    len = HIST_BAR_MAX * bucket[i].count / scale;    if (len < 1) len = 1;    assert(len <= HIST_BAR_MAX);     if (bucket[i].low == bucket[i].high)      fprintf(stderr, pat1, bucket[i].low, "");    else      fprintf(stderr, pat2, bucket[i].low, bucket[i].high);     for (j = 0; j < HIST_BAR_MAX; j++) fprintf(stderr, j < len ? "=" : " ");    fprintf(stderr, "\t%5d (%6.2f%%)\n", bucket[i].count, pct);  }} void show_q_histogram(const int counts[64], int max_buckets) {  struct hist_bucket bucket[64];  int buckets = 0;  int total = 0;  int scale;  int i;   for (i = 0; i < 64; i++) {    if (counts[i]) {      bucket[buckets].low = bucket[buckets].high = i;      bucket[buckets].count = counts[i];      buckets++;      total += counts[i];    }  }   fprintf(stderr, "\nQuantizer Selection:\n");  scale = merge_hist_buckets(bucket, max_buckets, &buckets);  show_histogram(bucket, buckets, total, scale);} void show_rate_histogram(struct rate_hist *hist, const vpx_codec_enc_cfg_t *cfg,                         int max_buckets) {  int i, scale;  int buckets = 0;   if (hist == NULL || cfg == NULL) return;   for (i = 0; i < RATE_BINS; i++) {    if (hist->bucket[i].low == INT_MAX) continue;    hist->bucket[buckets++] = hist->bucket[i];  }   fprintf(stderr, "\nRate (over %dms window):\n", cfg->rc_buf_sz);  scale = merge_hist_buckets(hist->bucket, max_buckets, &buckets);  show_histogram(hist->bucket, buckets, hist->total, scale);}