rate_hist.c

   1 /*
   2  * Copyright (c) 2016, Alliance for Open Media. All rights reserved
   3  *
   4  * This source code is subject to the terms of the BSD 2 Clause License and
   5  * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
   6  * was not distributed with this source code in the LICENSE file, you can
   7  * obtain it at www.aomedia.org/license/software. If the Alliance for Open
   8  * Media Patent License 1.0 was not distributed with this source code in the
   9  * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
  10  */
  11
  12 #include <assert.h>
  13 #include <stdlib.h>
  14 #include <limits.h>
  15 #include <stdio.h>
  16 #include <math.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
  38 struct rate_hist *init_rate_histogram(const aom_codec_enc_cfg_t *cfg,
  39                                       const aom_rational_t *fps) {
  40   int i;
  41   struct rate_hist *hist = malloc(sizeof(*hist));
  42
  43   // Determine the number of samples in the buffer. Use the file's framerate
  44   // to determine the number of frames in rc_buf_sz milliseconds, with an
  45   // adjustment (5/4) to account for alt-refs
  46   hist->samples = cfg->rc_buf_sz * 5 / 4 * fps->num / fps->den / 1000;
  47
  48   // prevent division by zero
  49   if (hist->samples == 0) 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
  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
  73 void update_rate_histogram(struct rate_hist *hist,
  74                            const aom_codec_enc_cfg_t *cfg,
  75                            const aom_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) return;
  89
  90   if (!cfg->rc_target_bitrate) return;
  91
  92   then = now;
  93
  94   /* Sum the size over the past rc_buf_sz ms */
  95   for (i = hist->frames; i > 0 && hist->frames - i < hist->samples; i--) {
  96     const int i_idx = (i - 1) % hist->samples;
  97
  98     then = hist->pts[i_idx];
  99     if (now - then > cfg->rc_buf_sz) break;
 100     sum_sz += hist->sz[i_idx];
 101   }
 102
 103   if (now == then) return;
 104
 105   avg_bitrate = sum_sz * 8 * 1000 / (now - then);
 106   idx = (int)(avg_bitrate * (RATE_BINS / 2) / (cfg->rc_target_bitrate * 1000));
 107   if (idx < 0) idx = 0;
 108   if (idx > RATE_BINS - 1) idx = RATE_BINS - 1;
 109   if (hist->bucket[idx].low > avg_bitrate)
 110     hist->bucket[idx].low = (int)avg_bitrate;
 111   if (hist->bucket[idx].high < avg_bitrate)
 112     hist->bucket[idx].high = (int)avg_bitrate;
 113   hist->bucket[idx].count++;
 114   hist->total++;
 115 }
 116
 117 static int merge_hist_buckets(struct hist_bucket *bucket, int max_buckets,
 118                               int *num_buckets) {
 119   int small_bucket = 0, merge_bucket = INT_MAX, big_bucket = 0;
 120   int buckets = *num_buckets;
 121   int i;
 122
 123   /* Find the extrema for this list of buckets */
 124   big_bucket = small_bucket = 0;
 125   for (i = 0; i < buckets; i++) {
 126     if (bucket[i].count < bucket[small_bucket].count) small_bucket = i;
 127     if (bucket[i].count > bucket[big_bucket].count) big_bucket = i;
 128   }
 129
 130   /* If we have too many buckets, merge the smallest with an adjacent
 131    * bucket.
 132    */
 133   while (buckets > max_buckets) {
 134     int last_bucket = buckets - 1;
 135
 136     /* merge the small bucket with an adjacent one. */
 137     if (small_bucket == 0)
 138       merge_bucket = 1;
 139     else if (small_bucket == last_bucket)
 140       merge_bucket = last_bucket - 1;
 141     else if (bucket[small_bucket - 1].count < bucket[small_bucket + 1].count)
 142       merge_bucket = small_bucket - 1;
 143     else
 144       merge_bucket = small_bucket + 1;
 145
 146     assert(abs(merge_bucket - small_bucket) <= 1);
 147     assert(small_bucket < buckets);
 148     assert(big_bucket < buckets);
 149     assert(merge_bucket < buckets);
 150
 151     if (merge_bucket < small_bucket) {
 152       bucket[merge_bucket].high = bucket[small_bucket].high;
 153       bucket[merge_bucket].count += bucket[small_bucket].count;
 154     } else {
 155       bucket[small_bucket].high = bucket[merge_bucket].high;
 156       bucket[small_bucket].count += bucket[merge_bucket].count;
 157       merge_bucket = small_bucket;
 158     }
 159
 160     assert(bucket[merge_bucket].low != bucket[merge_bucket].high);
 161
 162     buckets--;
 163
 164     /* Remove the merge_bucket from the list, and find the new small
 165      * and big buckets while we're at it
 166      */
 167     big_bucket = small_bucket = 0;
 168     for (i = 0; i < buckets; i++) {
 169       if (i > merge_bucket) bucket[i] = bucket[i + 1];
 170
 171       if (bucket[i].count < bucket[small_bucket].count) small_bucket = i;
 172       if (bucket[i].count > bucket[big_bucket].count) big_bucket = i;
 173     }
 174   }
 175
 176   *num_buckets = buckets;
 177   return bucket[big_bucket].count;
 178 }
 179
 180 static void show_histogram(const struct hist_bucket *bucket, int buckets,
 181                            int total, int scale) {
 182   const char *pat1, *pat2;
 183   int i;
 184
 185   switch ((int)(log(bucket[buckets - 1].high) / log(10)) + 1) {
 186     case 1:
 187     case 2:
 188       pat1 = "%4d %2s: ";
 189       pat2 = "%4d-%2d: ";
 190       break;
 191     case 3:
 192       pat1 = "%5d %3s: ";
 193       pat2 = "%5d-%3d: ";
 194       break;
 195     case 4:
 196       pat1 = "%6d %4s: ";
 197       pat2 = "%6d-%4d: ";
 198       break;
 199     case 5:
 200       pat1 = "%7d %5s: ";
 201       pat2 = "%7d-%5d: ";
 202       break;
 203     case 6:
 204       pat1 = "%8d %6s: ";
 205       pat2 = "%8d-%6d: ";
 206       break;
 207     case 7:
 208       pat1 = "%9d %7s: ";
 209       pat2 = "%9d-%7d: ";
 210       break;
 211     default:
 212       pat1 = "%12d %10s: ";
 213       pat2 = "%12d-%10d: ";
 214       break;
 215   }
 216
 217   for (i = 0; i < buckets; i++) {
 218     int len;
 219     int j;
 220     float pct;
 221
 222     pct = (float)(100.0 * bucket[i].count / total);
 223     len = HIST_BAR_MAX * bucket[i].count / scale;
 224     if (len < 1) len = 1;
 225     assert(len <= HIST_BAR_MAX);
 226
 227     if (bucket[i].low == bucket[i].high)
 228       fprintf(stderr, pat1, bucket[i].low, "");
 229     else
 230       fprintf(stderr, pat2, bucket[i].low, bucket[i].high);
 231
 232     for (j = 0; j < HIST_BAR_MAX; j++) fprintf(stderr, j < len ? "=" : " ");
 233     fprintf(stderr, "\t%5d (%6.2f%%)\n", bucket[i].count, pct);
 234   }
 235 }
 236
 237 void show_q_histogram(const int counts[64], int max_buckets) {
 238   struct hist_bucket bucket[64];
 239   int buckets = 0;
 240   int total = 0;
 241   int scale;
 242   int i;
 243
 244   for (i = 0; i < 64; i++) {
 245     if (counts[i]) {
 246       bucket[buckets].low = bucket[buckets].high = i;
 247       bucket[buckets].count = counts[i];
 248       buckets++;
 249       total += counts[i];
 250     }
 251   }
 252
 253   fprintf(stderr, "\nQuantizer Selection:\n");
 254   scale = merge_hist_buckets(bucket, max_buckets, &buckets);
 255   show_histogram(bucket, buckets, total, scale);
 256 }
 257
 258 void show_rate_histogram(struct rate_hist *hist, const aom_codec_enc_cfg_t *cfg,
 259                          int max_buckets) {
 260   int i, scale;
 261   int buckets = 0;
 262
 263   for (i = 0; i < RATE_BINS; i++) {
 264     if (hist->bucket[i].low == INT_MAX) continue;
 265     hist->bucket[buckets++] = hist->bucket[i];
 266   }
 267
 268   fprintf(stderr, "\nRate (over %dms window):\n", cfg->rc_buf_sz);
 269   scale = merge_hist_buckets(hist->bucket, max_buckets, &buckets);
 270   show_histogram(hist->bucket, buckets, hist->total, scale);
 271 }