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 = calloc(1, sizeof(*hist));
  41
  42   if (hist == NULL || cfg == NULL || fps == NULL || fps->num == 0 ||
  43       fps->den == 0) {
  44     destroy_rate_histogram(hist);
  45     return NULL;
  46   }
  47
  48   // Determine the number of samples in the buffer. Use the file's framerate
  49   // to determine the number of frames in rc_buf_sz milliseconds, with an
  50   // adjustment (5/4) to account for alt-refs
  51   hist->samples = cfg->rc_buf_sz * 5 / 4 * fps->num / fps->den / 1000;
  52
  53   // prevent division by zero
  54   if (hist->samples == 0) hist->samples = 1;
  55
  56   hist->frames = 0;
  57   hist->total = 0;
  58
  59   hist->pts = calloc(hist->samples, sizeof(*hist->pts));
  60   hist->sz = calloc(hist->samples, sizeof(*hist->sz));
  61   for (i = 0; i < RATE_BINS; i++) {
  62     hist->bucket[i].low = INT_MAX;
  63     hist->bucket[i].high = 0;
  64     hist->bucket[i].count = 0;
  65   }
  66
  67   return hist;
  68 }
  69
  70 void destroy_rate_histogram(struct rate_hist *hist) {
  71   if (hist) {
  72     free(hist->pts);
  73     free(hist->sz);
  74     free(hist);
  75   }
  76 }
  77
  78 void update_rate_histogram(struct rate_hist *hist,
  79                            const vpx_codec_enc_cfg_t *cfg,
  80                            const vpx_codec_cx_pkt_t *pkt) {
  81   int i;
  82   int64_t then = 0;
  83   int64_t avg_bitrate = 0;
  84   int64_t sum_sz = 0;
  85   const int64_t now = pkt->data.frame.pts * 1000 *
  86                       (uint64_t)cfg->g_timebase.num /
  87                       (uint64_t)cfg->g_timebase.den;
  88
  89   int idx;
  90
  91   if (hist == NULL || cfg == NULL || pkt == NULL) return;
  92
  93   idx = hist->frames++ % hist->samples;
  94   hist->pts[idx] = now;
  95   hist->sz[idx] = (int)pkt->data.frame.sz;
  96
  97   if (now < cfg->rc_buf_initial_sz) return;
  98
  99   if (!cfg->rc_target_bitrate) return;
 100
 101   then = now;
 102
 103   /* Sum the size over the past rc_buf_sz ms */
 104   for (i = hist->frames; i > 0 && hist->frames - i < hist->samples; i--) {
 105     const int i_idx = (i - 1) % hist->samples;
 106
 107     then = hist->pts[i_idx];
 108     if (now - then > cfg->rc_buf_sz) break;
 109     sum_sz += hist->sz[i_idx];
 110   }
 111
 112   if (now == then) return;
 113
 114   avg_bitrate = sum_sz * 8 * 1000 / (now - then);
 115   idx = (int)(avg_bitrate * (RATE_BINS / 2) / (cfg->rc_target_bitrate * 1000));
 116   if (idx < 0) idx = 0;
 117   if (idx > RATE_BINS - 1) idx = RATE_BINS - 1;
 118   if (hist->bucket[idx].low > avg_bitrate)
 119     hist->bucket[idx].low = (int)avg_bitrate;
 120   if (hist->bucket[idx].high < avg_bitrate)
 121     hist->bucket[idx].high = (int)avg_bitrate;
 122   hist->bucket[idx].count++;
 123   hist->total++;
 124 }
 125
 126 static int merge_hist_buckets(struct hist_bucket *bucket, int max_buckets,
 127                               int *num_buckets) {
 128   int small_bucket = 0, merge_bucket = INT_MAX, big_bucket = 0;
 129   int buckets;
 130   int i;
 131
 132   assert(bucket != NULL);
 133   assert(num_buckets != NULL);
 134
 135   buckets = *num_buckets;
 136
 137   /* Find the extrema for this list of buckets */
 138   big_bucket = small_bucket = 0;
 139   for (i = 0; i < buckets; i++) {
 140     if (bucket[i].count < bucket[small_bucket].count) small_bucket = i;
 141     if (bucket[i].count > bucket[big_bucket].count) big_bucket = i;
 142   }
 143
 144   /* If we have too many buckets, merge the smallest with an adjacent
 145    * bucket.
 146    */
 147   while (buckets > max_buckets) {
 148     int last_bucket = buckets - 1;
 149
 150     /* merge the small bucket with an adjacent one. */
 151     if (small_bucket == 0)
 152       merge_bucket = 1;
 153     else if (small_bucket == last_bucket)
 154       merge_bucket = last_bucket - 1;
 155     else if (bucket[small_bucket - 1].count < bucket[small_bucket + 1].count)
 156       merge_bucket = small_bucket - 1;
 157     else
 158       merge_bucket = small_bucket + 1;
 159
 160     assert(abs(merge_bucket - small_bucket) <= 1);
 161     assert(small_bucket < buckets);
 162     assert(big_bucket < buckets);
 163     assert(merge_bucket < buckets);
 164
 165     if (merge_bucket < small_bucket) {
 166       bucket[merge_bucket].high = bucket[small_bucket].high;
 167       bucket[merge_bucket].count += bucket[small_bucket].count;
 168     } else {
 169       bucket[small_bucket].high = bucket[merge_bucket].high;
 170       bucket[small_bucket].count += bucket[merge_bucket].count;
 171       merge_bucket = small_bucket;
 172     }
 173
 174     assert(bucket[merge_bucket].low != bucket[merge_bucket].high);
 175
 176     buckets--;
 177
 178     /* Remove the merge_bucket from the list, and find the new small
 179      * and big buckets while we're at it
 180      */
 181     big_bucket = small_bucket = 0;
 182     for (i = 0; i < buckets; i++) {
 183       if (i > merge_bucket) bucket[i] = bucket[i + 1];
 184
 185       if (bucket[i].count < bucket[small_bucket].count) small_bucket = i;
 186       if (bucket[i].count > bucket[big_bucket].count) big_bucket = i;
 187     }
 188   }
 189
 190   *num_buckets = buckets;
 191   return bucket[big_bucket].count;
 192 }
 193
 194 static void show_histogram(const struct hist_bucket *bucket, int buckets,
 195                            int total, int scale) {
 196   int width1, width2;
 197   int i;
 198
 199   if (!buckets) return;
 200   assert(bucket != NULL);
 201   assert(buckets > 0);
 202
 203   switch ((int)(log(bucket[buckets - 1].high) / log(10)) + 1) {
 204     case 1:
 205     case 2:
 206       width1 = 4;
 207       width2 = 2;
 208       break;
 209     case 3:
 210       width1 = 5;
 211       width2 = 3;
 212       break;
 213     case 4:
 214       width1 = 6;
 215       width2 = 4;
 216       break;
 217     case 5:
 218       width1 = 7;
 219       width2 = 5;
 220       break;
 221     case 6:
 222       width1 = 8;
 223       width2 = 6;
 224       break;
 225     case 7:
 226       width1 = 9;
 227       width2 = 7;
 228       break;
 229     default:
 230       width1 = 12;
 231       width2 = 10;
 232       break;
 233   }
 234
 235   for (i = 0; i < buckets; i++) {
 236     int len;
 237     int j;
 238     float pct;
 239
 240     pct = (float)(100.0 * bucket[i].count / total);
 241     len = HIST_BAR_MAX * bucket[i].count / scale;
 242     if (len < 1) len = 1;
 243     assert(len <= HIST_BAR_MAX);
 244
 245     if (bucket[i].low == bucket[i].high)
 246       fprintf(stderr, "%*d %*s: ", width1, bucket[i].low, width2, "");
 247     else
 248       fprintf(stderr, "%*d-%*d: ", width1, bucket[i].low, width2,
 249               bucket[i].high);
 250
 251     for (j = 0; j < HIST_BAR_MAX; j++) fprintf(stderr, j < len ? "=" : " ");
 252     fprintf(stderr, "\t%5d (%6.2f%%)\n", bucket[i].count, pct);
 253   }
 254 }
 255
 256 void show_q_histogram(const int counts[64], int max_buckets) {
 257   struct hist_bucket bucket[64];
 258   int buckets = 0;
 259   int total = 0;
 260   int scale;
 261   int i;
 262
 263   for (i = 0; i < 64; i++) {
 264     if (counts[i]) {
 265       bucket[buckets].low = bucket[buckets].high = i;
 266       bucket[buckets].count = counts[i];
 267       buckets++;
 268       total += counts[i];
 269     }
 270   }
 271
 272   fprintf(stderr, "\nQuantizer Selection:\n");
 273   scale = merge_hist_buckets(bucket, max_buckets, &buckets);
 274   show_histogram(bucket, buckets, total, scale);
 275 }
 276
 277 void show_rate_histogram(struct rate_hist *hist, const vpx_codec_enc_cfg_t *cfg,
 278                          int max_buckets) {
 279   int i, scale;
 280   int buckets = 0;
 281
 282   if (hist == NULL || cfg == NULL) return;
 283
 284   for (i = 0; i < RATE_BINS; i++) {
 285     if (hist->bucket[i].low == INT_MAX) continue;
 286     hist->bucket[buckets++] = hist->bucket[i];
 287   }
 288
 289   fprintf(stderr, "\nRate (over %dms window):\n", cfg->rc_buf_sz);
 290   scale = merge_hist_buckets(hist->bucket, max_buckets, &buckets);
 291   show_histogram(hist->bucket, buckets, hist->total, scale);
 292 }