rate_hist.c

   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
  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
  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 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
 123 static 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
 191 static 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
 250 void 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
 271 void 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 }