/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: 2025-08-28 07:12

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