context_tree.c 10.2 KB
Newer Older
Jingning Han's avatar
Jingning Han committed
1
/*
Yaowu Xu's avatar
Yaowu Xu committed
2
 * Copyright (c) 2016, Alliance for Open Media. All rights reserved
Jingning Han's avatar
Jingning Han committed
3
 *
Yaowu Xu's avatar
Yaowu Xu committed
4
5
6
7
8
9
 * This source code is subject to the terms of the BSD 2 Clause License and
 * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
 * was not distributed with this source code in the LICENSE file, you can
 * obtain it at www.aomedia.org/license/software. If the Alliance for Open
 * Media Patent License 1.0 was not distributed with this source code in the
 * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
Jingning Han's avatar
Jingning Han committed
10
11
 */

12
13
#include "av1/encoder/context_tree.h"
#include "av1/encoder/encoder.h"
Jingning Han's avatar
Jingning Han committed
14

15
static const BLOCK_SIZE square[MAX_SB_SIZE_LOG2 - 2] = {
16
  BLOCK_8X8,     BLOCK_16X16, BLOCK_32X32, BLOCK_64X64,
17
18
19
#if CONFIG_EXT_PARTITION
  BLOCK_128X128,
#endif  // CONFIG_EXT_PARTITION
Jingning Han's avatar
Jingning Han committed
20
21
};

Yaowu Xu's avatar
Yaowu Xu committed
22
static void alloc_mode_context(AV1_COMMON *cm, int num_4x4_blk,
23
24
25
#if CONFIG_EXT_PARTITION_TYPES
                               PARTITION_TYPE partition,
#endif
Jingning Han's avatar
Jingning Han committed
26
27
28
29
30
                               PICK_MODE_CONTEXT *ctx) {
  const int num_blk = (num_4x4_blk < 4 ? 4 : num_4x4_blk);
  const int num_pix = num_blk << 4;
  int i, k;
  ctx->num_4x4_blk = num_blk;
31
32
33
#if CONFIG_EXT_PARTITION_TYPES
  ctx->partition = partition;
#endif
Jingning Han's avatar
Jingning Han committed
34
35

  for (i = 0; i < MAX_MB_PLANE; ++i) {
36
#if CONFIG_VAR_TX
Yaowu Xu's avatar
Yaowu Xu committed
37
    CHECK_MEM_ERROR(cm, ctx->blk_skip[i], aom_calloc(num_blk, sizeof(uint8_t)));
38
#endif
Jingning Han's avatar
Jingning Han committed
39
40
    for (k = 0; k < 3; ++k) {
      CHECK_MEM_ERROR(cm, ctx->coeff[i][k],
Yaowu Xu's avatar
Yaowu Xu committed
41
                      aom_memalign(32, num_pix * sizeof(*ctx->coeff[i][k])));
Jingning Han's avatar
Jingning Han committed
42
      CHECK_MEM_ERROR(cm, ctx->qcoeff[i][k],
Yaowu Xu's avatar
Yaowu Xu committed
43
                      aom_memalign(32, num_pix * sizeof(*ctx->qcoeff[i][k])));
Jingning Han's avatar
Jingning Han committed
44
      CHECK_MEM_ERROR(cm, ctx->dqcoeff[i][k],
Yaowu Xu's avatar
Yaowu Xu committed
45
                      aom_memalign(32, num_pix * sizeof(*ctx->dqcoeff[i][k])));
Jingning Han's avatar
Jingning Han committed
46
      CHECK_MEM_ERROR(cm, ctx->eobs[i][k],
Yaowu Xu's avatar
Yaowu Xu committed
47
                      aom_memalign(32, num_blk * sizeof(*ctx->eobs[i][k])));
Jingning Han's avatar
Jingning Han committed
48
    }
49
50
51
52
#if CONFIG_PVQ
    CHECK_MEM_ERROR(cm, ctx->pvq_ref_coeff[i],
                    aom_memalign(32, num_pix * sizeof(*ctx->pvq_ref_coeff[i])));
#endif
Jingning Han's avatar
Jingning Han committed
53
  }
54

55
#if CONFIG_PALETTE
56
  if (cm->allow_screen_content_tools) {
57
58
59
    for (i = 0; i < 2; ++i) {
      CHECK_MEM_ERROR(
          cm, ctx->color_index_map[i],
Yaowu Xu's avatar
Yaowu Xu committed
60
          aom_memalign(32, num_pix * sizeof(*ctx->color_index_map[i])));
61
62
    }
  }
63
#endif  // CONFIG_PALETTE
Jingning Han's avatar
Jingning Han committed
64
65
66
67
68
}

static void free_mode_context(PICK_MODE_CONTEXT *ctx) {
  int i, k;
  for (i = 0; i < MAX_MB_PLANE; ++i) {
69
#if CONFIG_VAR_TX
Yaowu Xu's avatar
Yaowu Xu committed
70
    aom_free(ctx->blk_skip[i]);
71
72
    ctx->blk_skip[i] = 0;
#endif
Jingning Han's avatar
Jingning Han committed
73
    for (k = 0; k < 3; ++k) {
Yaowu Xu's avatar
Yaowu Xu committed
74
      aom_free(ctx->coeff[i][k]);
Jingning Han's avatar
Jingning Han committed
75
      ctx->coeff[i][k] = 0;
Yaowu Xu's avatar
Yaowu Xu committed
76
      aom_free(ctx->qcoeff[i][k]);
Jingning Han's avatar
Jingning Han committed
77
      ctx->qcoeff[i][k] = 0;
Yaowu Xu's avatar
Yaowu Xu committed
78
      aom_free(ctx->dqcoeff[i][k]);
Jingning Han's avatar
Jingning Han committed
79
      ctx->dqcoeff[i][k] = 0;
80
#if CONFIG_PVQ
81
82
      aom_free(ctx->pvq_ref_coeff[i]);
      ctx->pvq_ref_coeff[i] = 0;
83
#endif
Yaowu Xu's avatar
Yaowu Xu committed
84
      aom_free(ctx->eobs[i][k]);
Jingning Han's avatar
Jingning Han committed
85
86
87
      ctx->eobs[i][k] = 0;
    }
  }
hui su's avatar
hui su committed
88

89
#if CONFIG_PALETTE
hui su's avatar
hui su committed
90
  for (i = 0; i < 2; ++i) {
Yaowu Xu's avatar
Yaowu Xu committed
91
    aom_free(ctx->color_index_map[i]);
hui su's avatar
hui su committed
92
93
    ctx->color_index_map[i] = 0;
  }
94
#endif  // CONFIG_PALETTE
Jingning Han's avatar
Jingning Han committed
95
96
}

Yaowu Xu's avatar
Yaowu Xu committed
97
static void alloc_tree_contexts(AV1_COMMON *cm, PC_TREE *tree,
Jingning Han's avatar
Jingning Han committed
98
                                int num_4x4_blk) {
99
100
#if CONFIG_EXT_PARTITION_TYPES
  alloc_mode_context(cm, num_4x4_blk, PARTITION_NONE, &tree->none);
101
102
103
104
  alloc_mode_context(cm, num_4x4_blk / 2, PARTITION_HORZ, &tree->horizontal[0]);
  alloc_mode_context(cm, num_4x4_blk / 2, PARTITION_VERT, &tree->vertical[0]);
  alloc_mode_context(cm, num_4x4_blk / 2, PARTITION_VERT, &tree->horizontal[1]);
  alloc_mode_context(cm, num_4x4_blk / 2, PARTITION_VERT, &tree->vertical[1]);
105

106
  alloc_mode_context(cm, num_4x4_blk / 4, PARTITION_HORZ_A,
107
                     &tree->horizontala[0]);
108
  alloc_mode_context(cm, num_4x4_blk / 4, PARTITION_HORZ_A,
109
                     &tree->horizontala[1]);
110
  alloc_mode_context(cm, num_4x4_blk / 2, PARTITION_HORZ_A,
111
                     &tree->horizontala[2]);
112
  alloc_mode_context(cm, num_4x4_blk / 2, PARTITION_HORZ_B,
113
                     &tree->horizontalb[0]);
114
  alloc_mode_context(cm, num_4x4_blk / 4, PARTITION_HORZ_B,
115
                     &tree->horizontalb[1]);
116
  alloc_mode_context(cm, num_4x4_blk / 4, PARTITION_HORZ_B,
117
                     &tree->horizontalb[2]);
118
119
120
121
122
123
124
125
126
127
128
129
  alloc_mode_context(cm, num_4x4_blk / 4, PARTITION_VERT_A,
                     &tree->verticala[0]);
  alloc_mode_context(cm, num_4x4_blk / 4, PARTITION_VERT_A,
                     &tree->verticala[1]);
  alloc_mode_context(cm, num_4x4_blk / 2, PARTITION_VERT_A,
                     &tree->verticala[2]);
  alloc_mode_context(cm, num_4x4_blk / 2, PARTITION_VERT_B,
                     &tree->verticalb[0]);
  alloc_mode_context(cm, num_4x4_blk / 4, PARTITION_VERT_B,
                     &tree->verticalb[1]);
  alloc_mode_context(cm, num_4x4_blk / 4, PARTITION_VERT_B,
                     &tree->verticalb[2]);
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#ifdef CONFIG_SUPERTX
  alloc_mode_context(cm, num_4x4_blk, PARTITION_HORZ,
                     &tree->horizontal_supertx);
  alloc_mode_context(cm, num_4x4_blk, PARTITION_VERT, &tree->vertical_supertx);
  alloc_mode_context(cm, num_4x4_blk, PARTITION_SPLIT, &tree->split_supertx);
  alloc_mode_context(cm, num_4x4_blk, PARTITION_HORZ_A,
                     &tree->horizontala_supertx);
  alloc_mode_context(cm, num_4x4_blk, PARTITION_HORZ_B,
                     &tree->horizontalb_supertx);
  alloc_mode_context(cm, num_4x4_blk, PARTITION_VERT_A,
                     &tree->verticala_supertx);
  alloc_mode_context(cm, num_4x4_blk, PARTITION_VERT_B,
                     &tree->verticalb_supertx);
#endif  // CONFIG_SUPERTX
#else
Jingning Han's avatar
Jingning Han committed
145
  alloc_mode_context(cm, num_4x4_blk, &tree->none);
146
147
  alloc_mode_context(cm, num_4x4_blk / 2, &tree->horizontal[0]);
  alloc_mode_context(cm, num_4x4_blk / 2, &tree->vertical[0]);
148
#ifdef CONFIG_SUPERTX
Geza Lore's avatar
Geza Lore committed
149
150
151
  alloc_mode_context(cm, num_4x4_blk, &tree->horizontal_supertx);
  alloc_mode_context(cm, num_4x4_blk, &tree->vertical_supertx);
  alloc_mode_context(cm, num_4x4_blk, &tree->split_supertx);
152
#endif
Jingning Han's avatar
Jingning Han committed
153
154

  if (num_4x4_blk > 4) {
155
156
    alloc_mode_context(cm, num_4x4_blk / 2, &tree->horizontal[1]);
    alloc_mode_context(cm, num_4x4_blk / 2, &tree->vertical[1]);
Jingning Han's avatar
Jingning Han committed
157
158
159
160
  } else {
    memset(&tree->horizontal[1], 0, sizeof(tree->horizontal[1]));
    memset(&tree->vertical[1], 0, sizeof(tree->vertical[1]));
  }
161
#endif  // CONFIG_EXT_PARTITION_TYPES
Jingning Han's avatar
Jingning Han committed
162
163
164
}

static void free_tree_contexts(PC_TREE *tree) {
165
166
167
168
169
170
171
172
173
#if CONFIG_EXT_PARTITION_TYPES
  int i;
  for (i = 0; i < 3; i++) {
    free_mode_context(&tree->horizontala[i]);
    free_mode_context(&tree->horizontalb[i]);
    free_mode_context(&tree->verticala[i]);
    free_mode_context(&tree->verticalb[i]);
  }
#endif  // CONFIG_EXT_PARTITION_TYPES
Jingning Han's avatar
Jingning Han committed
174
175
176
177
178
  free_mode_context(&tree->none);
  free_mode_context(&tree->horizontal[0]);
  free_mode_context(&tree->horizontal[1]);
  free_mode_context(&tree->vertical[0]);
  free_mode_context(&tree->vertical[1]);
179
#ifdef CONFIG_SUPERTX
Geza Lore's avatar
Geza Lore committed
180
181
182
  free_mode_context(&tree->horizontal_supertx);
  free_mode_context(&tree->vertical_supertx);
  free_mode_context(&tree->split_supertx);
183
184
185
186
187
188
189
#if CONFIG_EXT_PARTITION_TYPES
  free_mode_context(&tree->horizontala_supertx);
  free_mode_context(&tree->horizontalb_supertx);
  free_mode_context(&tree->verticala_supertx);
  free_mode_context(&tree->verticalb_supertx);
#endif  // CONFIG_EXT_PARTITION_TYPES
#endif  // CONFIG_SUPERTX
Jingning Han's avatar
Jingning Han committed
190
191
192
193
194
195
}

// This function sets up a tree of contexts such that at each square
// partition level. There are contexts for none, horizontal, vertical, and
// split.  Along with a block_size value and a selected block_size which
// represents the state of our search.
Yaowu Xu's avatar
Yaowu Xu committed
196
void av1_setup_pc_tree(AV1_COMMON *cm, ThreadData *td) {
Jingning Han's avatar
Jingning Han committed
197
  int i, j;
198
199
200
201
#if CONFIG_EXT_PARTITION
  const int leaf_nodes = 256;
  const int tree_nodes = 256 + 64 + 16 + 4 + 1;
#else
Jingning Han's avatar
Jingning Han committed
202
203
  const int leaf_nodes = 64;
  const int tree_nodes = 64 + 16 + 4 + 1;
204
#endif  // CONFIG_EXT_PARTITION
Jingning Han's avatar
Jingning Han committed
205
206
207
208
209
210
  int pc_tree_index = 0;
  PC_TREE *this_pc;
  PICK_MODE_CONTEXT *this_leaf;
  int square_index = 1;
  int nodes;

Yaowu Xu's avatar
Yaowu Xu committed
211
  aom_free(td->leaf_tree);
212
  CHECK_MEM_ERROR(cm, td->leaf_tree,
Yaowu Xu's avatar
Yaowu Xu committed
213
214
                  aom_calloc(leaf_nodes, sizeof(*td->leaf_tree)));
  aom_free(td->pc_tree);
215
  CHECK_MEM_ERROR(cm, td->pc_tree,
Yaowu Xu's avatar
Yaowu Xu committed
216
                  aom_calloc(tree_nodes, sizeof(*td->pc_tree)));
Jingning Han's avatar
Jingning Han committed
217
218
219
220
221
222

  this_pc = &td->pc_tree[0];
  this_leaf = &td->leaf_tree[0];

  // 4x4 blocks smaller than 8x8 but in the same 8x8 block share the same
  // context so we only need to allocate 1 for each 8x8 block.
223
224
225
226
  for (i = 0; i < leaf_nodes; ++i) {
#if CONFIG_EXT_PARTITION_TYPES
    alloc_mode_context(cm, 1, PARTITION_NONE, &td->leaf_tree[i]);
#else
Jingning Han's avatar
Jingning Han committed
227
    alloc_mode_context(cm, 1, &td->leaf_tree[i]);
228
229
#endif
  }
Jingning Han's avatar
Jingning Han committed
230
231
232
233
234
235
236

  // Sets up all the leaf nodes in the tree.
  for (pc_tree_index = 0; pc_tree_index < leaf_nodes; ++pc_tree_index) {
    PC_TREE *const tree = &td->pc_tree[pc_tree_index];
    tree->block_size = square[0];
    alloc_tree_contexts(cm, tree, 4);
    tree->leaf_split[0] = this_leaf++;
237
    for (j = 1; j < 4; j++) tree->leaf_split[j] = tree->leaf_split[0];
Jingning Han's avatar
Jingning Han committed
238
239
240
241
  }

  // Each node has 4 leaf nodes, fill each block_size level of the tree
  // from leafs to the root.
242
  for (nodes = leaf_nodes >> 2; nodes > 0; nodes >>= 2) {
Jingning Han's avatar
Jingning Han committed
243
244
245
246
    for (i = 0; i < nodes; ++i) {
      PC_TREE *const tree = &td->pc_tree[pc_tree_index];
      alloc_tree_contexts(cm, tree, 4 << (2 * square_index));
      tree->block_size = square[square_index];
247
      for (j = 0; j < 4; j++) tree->split[j] = this_pc++;
Jingning Han's avatar
Jingning Han committed
248
249
250
251
      ++pc_tree_index;
    }
    ++square_index;
  }
Geza Lore's avatar
Geza Lore committed
252
253
254
255
256
257
258

  // Set up the root node for the largest superblock size
  i = MAX_MIB_SIZE_LOG2 - MIN_MIB_SIZE_LOG2;
  td->pc_root[i] = &td->pc_tree[tree_nodes - 1];
  td->pc_root[i]->none.best_mode_index = 2;
  // Set up the root nodes for the rest of the possible superblock sizes
  while (--i >= 0) {
259
    td->pc_root[i] = td->pc_root[i + 1]->split[0];
Geza Lore's avatar
Geza Lore committed
260
261
    td->pc_root[i]->none.best_mode_index = 2;
  }
Jingning Han's avatar
Jingning Han committed
262
263
}

Yaowu Xu's avatar
Yaowu Xu committed
264
void av1_free_pc_tree(ThreadData *td) {
265
266
267
268
269
#if CONFIG_EXT_PARTITION
  const int leaf_nodes = 256;
  const int tree_nodes = 256 + 64 + 16 + 4 + 1;
#else
  const int leaf_nodes = 64;
Jingning Han's avatar
Jingning Han committed
270
  const int tree_nodes = 64 + 16 + 4 + 1;
271
#endif  // CONFIG_EXT_PARTITION
Jingning Han's avatar
Jingning Han committed
272
273
274
  int i;

  // Set up all 4x4 mode contexts
275
  for (i = 0; i < leaf_nodes; ++i) free_mode_context(&td->leaf_tree[i]);
Jingning Han's avatar
Jingning Han committed
276
277

  // Sets up all the leaf nodes in the tree.
278
  for (i = 0; i < tree_nodes; ++i) free_tree_contexts(&td->pc_tree[i]);
Jingning Han's avatar
Jingning Han committed
279

Yaowu Xu's avatar
Yaowu Xu committed
280
  aom_free(td->pc_tree);
Jingning Han's avatar
Jingning Han committed
281
  td->pc_tree = NULL;
Yaowu Xu's avatar
Yaowu Xu committed
282
  aom_free(td->leaf_tree);
Jingning Han's avatar
Jingning Han committed
283
284
  td->leaf_tree = NULL;
}