/src/libvpx/vp9/encoder/vp9_subexp.c

Source (jump to first uncovered line)
/*
 *  Copyright (c) 2013 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 "vpx_dsp/bitwriter.h"

#include "vp9/common/vp9_common.h"
#include "vp9/common/vp9_entropy.h"
#include "vp9/encoder/vp9_cost.h"
#include "vp9/encoder/vp9_subexp.h"

static const uint8_t update_bits[255] = {
  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  6,  6,  6,
  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  8,  8,  8,  8,  8,  8,
  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
  8,  8,  8,  8,  8,  8,  8,  10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
  10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11,
  11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
  11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
  11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
  11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
  11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
  11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
  11, 11, 11, 11, 11, 11, 11, 0,
};
#define MIN_DELP_BITS 5

static int recenter_nonneg(int v, int m) {
  if (v > (m << 1))
    return v;
  else if (v >= m)
    return ((v - m) << 1);
  else
    return ((m - v) << 1) - 1;
}

static int remap_prob(int v, int m) {
  int i;
  static const uint8_t map_table[MAX_PROB - 1] = {
    // generated by:
    //   map_table[j] = split_index(j, MAX_PROB - 1, MODULUS_PARAM);
    20,  21,  22,  23,  24,  25,  0,   26,  27,  28,  29,  30,  31,  32,  33,
    34,  35,  36,  37,  1,   38,  39,  40,  41,  42,  43,  44,  45,  46,  47,
    48,  49,  2,   50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,
    3,   62,  63,  64,  65,  66,  67,  68,  69,  70,  71,  72,  73,  4,   74,
    75,  76,  77,  78,  79,  80,  81,  82,  83,  84,  85,  5,   86,  87,  88,
    89,  90,  91,  92,  93,  94,  95,  96,  97,  6,   98,  99,  100, 101, 102,
    103, 104, 105, 106, 107, 108, 109, 7,   110, 111, 112, 113, 114, 115, 116,
    117, 118, 119, 120, 121, 8,   122, 123, 124, 125, 126, 127, 128, 129, 130,
    131, 132, 133, 9,   134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144,
    145, 10,  146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 11,
    158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 12,  170, 171,
    172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 13,  182, 183, 184, 185,
    186, 187, 188, 189, 190, 191, 192, 193, 14,  194, 195, 196, 197, 198, 199,
    200, 201, 202, 203, 204, 205, 15,  206, 207, 208, 209, 210, 211, 212, 213,
    214, 215, 216, 217, 16,  218, 219, 220, 221, 222, 223, 224, 225, 226, 227,
    228, 229, 17,  230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241,
    18,  242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 19,
  };
  v--;
  m--;
  assert(m >= 0);
  if ((m << 1) <= MAX_PROB)
    i = recenter_nonneg(v, m) - 1;
  else
    i = recenter_nonneg(MAX_PROB - 1 - v, MAX_PROB - 1 - m) - 1;

  assert(i >= 0 && (size_t)i < sizeof(map_table));
  i = map_table[i];
  return i;
}

static int prob_diff_update_cost(vpx_prob newp, vpx_prob oldp) {
  int delp = remap_prob(newp, oldp);
  return update_bits[delp] << VP9_PROB_COST_SHIFT;
}

static void encode_uniform(vpx_writer *w, int v) {
  const int l = 8;
  const int m = (1 << l) - 191;
  if (v < m) {
    vpx_write_literal(w, v, l - 1);
  } else {
    vpx_write_literal(w, m + ((v - m) >> 1), l - 1);
    vpx_write_literal(w, (v - m) & 1, 1);
  }
}

static INLINE int write_bit_gte(vpx_writer *w, int word, int test) {
  vpx_write_literal(w, word >= test, 1);
  return word >= test;
}

static void encode_term_subexp(vpx_writer *w, int word) {
  if (!write_bit_gte(w, word, 16)) {
    vpx_write_literal(w, word, 4);
  } else if (!write_bit_gte(w, word, 32)) {
    vpx_write_literal(w, word - 16, 4);
  } else if (!write_bit_gte(w, word, 64)) {
    vpx_write_literal(w, word - 32, 5);
  } else {
    encode_uniform(w, word - 64);
  }
}

void vp9_write_prob_diff_update(vpx_writer *w, vpx_prob newp, vpx_prob oldp) {
  const int delp = remap_prob(newp, oldp);
  encode_term_subexp(w, delp);
}

int64_t vp9_prob_diff_update_savings_search(const unsigned int *ct,
                                            vpx_prob oldp, vpx_prob *bestp,
                                            vpx_prob upd) {
  const int64_t old_b = cost_branch256(ct, oldp);
  int64_t bestsavings = 0;
  vpx_prob newp, bestnewp = oldp;
  const int step = *bestp > oldp ? -1 : 1;
  const int upd_cost = vp9_cost_one(upd) - vp9_cost_zero(upd);

  if (old_b > upd_cost + (MIN_DELP_BITS << VP9_PROB_COST_SHIFT)) {
    for (newp = *bestp; newp != oldp; newp += step) {
      const int64_t new_b = cost_branch256(ct, newp);
      const int64_t update_b = prob_diff_update_cost(newp, oldp) + upd_cost;
      const int64_t savings = old_b - new_b - update_b;
      if (savings > bestsavings) {
        bestsavings = savings;
        bestnewp = newp;
      }
    }
  }
  *bestp = bestnewp;
  return bestsavings;
}

int64_t vp9_prob_diff_update_savings_search_model(const unsigned int *ct,
                                                  const vpx_prob oldp,
                                                  vpx_prob *bestp, vpx_prob upd,
                                                  int stepsize) {
  int64_t i, old_b, new_b, update_b, savings, bestsavings;
  int64_t newp;
  const int64_t step_sign = *bestp > oldp ? -1 : 1;
  const int64_t step = stepsize * step_sign;
  const int64_t upd_cost = vp9_cost_one(upd) - vp9_cost_zero(upd);
  const vpx_prob *newplist, *oldplist;
  vpx_prob bestnewp;
  oldplist = vp9_pareto8_full[oldp - 1];
  old_b = cost_branch256(ct + 2 * PIVOT_NODE, oldp);
  for (i = UNCONSTRAINED_NODES; i < ENTROPY_NODES; ++i)
    old_b += cost_branch256(ct + 2 * i, oldplist[i - UNCONSTRAINED_NODES]);

  bestsavings = 0;
  bestnewp = oldp;

  assert(stepsize > 0);

  if (old_b > upd_cost + (MIN_DELP_BITS << VP9_PROB_COST_SHIFT)) {
    for (newp = *bestp; (newp - oldp) * step_sign < 0; newp += step) {
      if (newp < 1 || newp > 255) continue;
      newplist = vp9_pareto8_full[newp - 1];
      new_b = cost_branch256(ct + 2 * PIVOT_NODE, (vpx_prob)newp);
      for (i = UNCONSTRAINED_NODES; i < ENTROPY_NODES; ++i)
        new_b += cost_branch256(ct + 2 * i, newplist[i - UNCONSTRAINED_NODES]);
      update_b = prob_diff_update_cost((vpx_prob)newp, oldp) + upd_cost;
      savings = old_b - new_b - update_b;
      if (savings > bestsavings) {
        bestsavings = savings;
        bestnewp = (vpx_prob)newp;
      }
    }
  }

  *bestp = bestnewp;
  return bestsavings;
}

void vp9_cond_prob_diff_update(vpx_writer *w, vpx_prob *oldp,
                               const unsigned int ct[2]) {
  const vpx_prob upd = DIFF_UPDATE_PROB;
  vpx_prob newp = get_binary_prob(ct[0], ct[1]);
  const int64_t savings =
      vp9_prob_diff_update_savings_search(ct, *oldp, &newp, upd);
  assert(newp >= 1);
  if (savings > 0) {
    vpx_write(w, 1, upd);
    vp9_write_prob_diff_update(w, newp, *oldp);
    *oldp = newp;
  } else {
    vpx_write(w, 0, upd);
  }
}

Coverage Report

Created: 2024-09-06 07:53

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Copyright (c) 2013 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		#include "vpx_dsp/bitwriter.h"
11
12		#include "vp9/common/vp9_common.h"
13		#include "vp9/common/vp9_entropy.h"
14		#include "vp9/encoder/vp9_cost.h"
15		#include "vp9/encoder/vp9_subexp.h"
16
17		static const uint8_t update_bits[255] = {
18		5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6,
19		6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 8, 8, 8, 8, 8, 8,
20		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
21		8, 8, 8, 8, 8, 8, 8, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
22		10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
23		10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
24		10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11,
25		11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
26		11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
27		11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
28		11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
29		11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
30		11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
31		11, 11, 11, 11, 11, 11, 11, 0,
32		};
33	28.2M	#define MIN_DELP_BITS 5
34
35	203M	static int recenter_nonneg(int v, int m) {
36	203M	if (v > (m << 1))
37	51.7M	return v;
38	151M	else if (v >= m)
39	69.3M	return ((v - m) << 1);
40	82.0M	else
41	82.0M	return ((m - v) << 1) - 1;
42	203M	}
43
44	203M	static int remap_prob(int v, int m) {
45	203M	int i;
46	203M	static const uint8_t map_table[MAX_PROB - 1] = {
47		// generated by:
48		// map_table[j] = split_index(j, MAX_PROB - 1, MODULUS_PARAM);
49	203M	20, 21, 22, 23, 24, 25, 0, 26, 27, 28, 29, 30, 31, 32, 33,
50	203M	34, 35, 36, 37, 1, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
51	203M	48, 49, 2, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,
52	203M	3, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 4, 74,
53	203M	75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 5, 86, 87, 88,
54	203M	89, 90, 91, 92, 93, 94, 95, 96, 97, 6, 98, 99, 100, 101, 102,
55	203M	103, 104, 105, 106, 107, 108, 109, 7, 110, 111, 112, 113, 114, 115, 116,
56	203M	117, 118, 119, 120, 121, 8, 122, 123, 124, 125, 126, 127, 128, 129, 130,
57	203M	131, 132, 133, 9, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144,
58	203M	145, 10, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 11,
59	203M	158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 12, 170, 171,
60	203M	172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 13, 182, 183, 184, 185,
61	203M	186, 187, 188, 189, 190, 191, 192, 193, 14, 194, 195, 196, 197, 198, 199,
62	203M	200, 201, 202, 203, 204, 205, 15, 206, 207, 208, 209, 210, 211, 212, 213,
63	203M	214, 215, 216, 217, 16, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227,
64	203M	228, 229, 17, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241,
65	203M	18, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 19,
66	203M	};
67	203M	v--;
68	203M	m--;
69	203M	assert(m >= 0);
70	203M	if ((m << 1) <= MAX_PROB)
71	118M	i = recenter_nonneg(v, m) - 1;
72	84.9M	else
73	84.9M	i = recenter_nonneg(MAX_PROB - 1 - v, MAX_PROB - 1 - m) - 1;
74
75	203M	assert(i >= 0 && (size_t)i < sizeof(map_table));
76	203M	i = map_table[i];
77	203M	return i;
78	203M	}
79
80	202M	static int prob_diff_update_cost(vpx_prob newp, vpx_prob oldp) {
81	202M	int delp = remap_prob(newp, oldp);
82	202M	return update_bits[delp] << VP9_PROB_COST_SHIFT;
83	202M	}
84
85	42.4k	static void encode_uniform(vpx_writer *w, int v) {
86	42.4k	const int l = 8;
87	42.4k	const int m = (1 << l) - 191;
88	42.4k	if (v < m) {
89	17.8k	vpx_write_literal(w, v, l - 1);
90	24.6k	} else {
91	24.6k	vpx_write_literal(w, m + ((v - m) >> 1), l - 1);
92	24.6k	vpx_write_literal(w, (v - m) & 1, 1);
93	24.6k	}
94	42.4k	}
95
96	815k	static INLINE int write_bit_gte(vpx_writer *w, int word, int test) {
97	815k	vpx_write_literal(w, word >= test, 1);
98	815k	return word >= test;
99	815k	}
100
101	554k	static void encode_term_subexp(vpx_writer *w, int word) {
102	554k	if (!write_bit_gte(w, word, 16)) {
103	372k	vpx_write_literal(w, word, 4);
104	372k	} else if (!write_bit_gte(w, word, 32)) {
105	101k	vpx_write_literal(w, word - 16, 4);
106	101k	} else if (!write_bit_gte(w, word, 64)) {
107	36.9k	vpx_write_literal(w, word - 32, 5);
108	42.4k	} else {
109	42.4k	encode_uniform(w, word - 64);
110	42.4k	}
111	554k	}
112
113	554k	void vp9_write_prob_diff_update(vpx_writer *w, vpx_prob newp, vpx_prob oldp) {
114	554k	const int delp = remap_prob(newp, oldp);
115	554k	encode_term_subexp(w, delp);
116	554k	}
117
118		int64_t vp9_prob_diff_update_savings_search(const unsigned int *ct,
119		vpx_prob oldp, vpx_prob *bestp,
120	20.3M	vpx_prob upd) {
121	20.3M	const int64_t old_b = cost_branch256(ct, oldp);
122	20.3M	int64_t bestsavings = 0;
123	20.3M	vpx_prob newp, bestnewp = oldp;
124	20.3M	const int step = *bestp > oldp ? -1 : 1;
125	20.3M	const int upd_cost = vp9_cost_one(upd) - vp9_cost_zero(upd);
126
127	20.3M	if (old_b > upd_cost + (MIN_DELP_BITS << VP9_PROB_COST_SHIFT)) {
128	89.1M	for (newp = *bestp; newp != oldp; newp += step) {
129	86.7M	const int64_t new_b = cost_branch256(ct, newp);
130	86.7M	const int64_t update_b = prob_diff_update_cost(newp, oldp) + upd_cost;
131	86.7M	const int64_t savings = old_b - new_b - update_b;
132	86.7M	if (savings > bestsavings) {
133	693k	bestsavings = savings;
134	693k	bestnewp = newp;
135	693k	}
136	86.7M	}
137	2.39M	}
138	20.3M	*bestp = bestnewp;
139	20.3M	return bestsavings;
140	20.3M	}
141
142		int64_t vp9_prob_diff_update_savings_search_model(const unsigned int *ct,
143		const vpx_prob oldp,
144		vpx_prob *bestp, vpx_prob upd,
145	7.91M	int stepsize) {
146	7.91M	int64_t i, old_b, new_b, update_b, savings, bestsavings;
147	7.91M	int64_t newp;
148	7.91M	const int64_t step_sign = *bestp > oldp ? -1 : 1;
149	7.91M	const int64_t step = stepsize * step_sign;
150	7.91M	const int64_t upd_cost = vp9_cost_one(upd) - vp9_cost_zero(upd);
151	7.91M	const vpx_prob newplist, oldplist;
152	7.91M	vpx_prob bestnewp;
153	7.91M	oldplist = vp9_pareto8_full[oldp - 1];
154	7.91M	old_b = cost_branch256(ct + 2 * PIVOT_NODE, oldp);
155	71.2M	for (i = UNCONSTRAINED_NODES; i < ENTROPY_NODES; ++i)
156	63.2M	old_b += cost_branch256(ct + 2 * i, oldplist[i - UNCONSTRAINED_NODES]);
157
158	7.91M	bestsavings = 0;
159	7.91M	bestnewp = oldp;
160
161	7.91M	assert(stepsize > 0);
162
163	7.91M	if (old_b > upd_cost + (MIN_DELP_BITS << VP9_PROB_COST_SHIFT)) {
164	118M	for (newp = bestp; (newp - oldp) step_sign < 0; newp += step) {
165	115M	if (newp < 1 \|\| newp > 255) continue;
166	115M	newplist = vp9_pareto8_full[newp - 1];
167	115M	new_b = cost_branch256(ct + 2 * PIVOT_NODE, (vpx_prob)newp);
168	1.04G	for (i = UNCONSTRAINED_NODES; i < ENTROPY_NODES; ++i)
169	927M	new_b += cost_branch256(ct + 2 * i, newplist[i - UNCONSTRAINED_NODES]);
170	115M	update_b = prob_diff_update_cost((vpx_prob)newp, oldp) + upd_cost;
171	115M	savings = old_b - new_b - update_b;
172	115M	if (savings > bestsavings) {
173	2.85M	bestsavings = savings;
174	2.85M	bestnewp = (vpx_prob)newp;
175	2.85M	}
176	115M	}
177	2.51M	}
178
179	7.91M	*bestp = bestnewp;
180	7.91M	return bestsavings;
181	7.91M	}
182
183		void vp9_cond_prob_diff_update(vpx_writer w, vpx_prob oldp,
184	4.47M	const unsigned int ct[2]) {
185	4.47M	const vpx_prob upd = DIFF_UPDATE_PROB;
186	4.47M	vpx_prob newp = get_binary_prob(ct[0], ct[1]);
187	4.47M	const int64_t savings =
188	4.47M	vp9_prob_diff_update_savings_search(ct, *oldp, &newp, upd);
189	4.47M	assert(newp >= 1);
190	4.47M	if (savings > 0) {
191	26.9k	vpx_write(w, 1, upd);
192	26.9k	vp9_write_prob_diff_update(w, newp, *oldp);
193	26.9k	*oldp = newp;
194	4.45M	} else {
195	4.45M	vpx_write(w, 0, upd);
196	4.45M	}
197	4.47M	}