1 /*
2 * Copyright © 2018-2023, VideoLAN and dav1d authors
3 * Copyright © 2018-2023, Two Orioles, LLC
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright notice, this
10 * list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
20 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #include "config.h"
29
30 #include <stdlib.h>
31
32 #include "common/attributes.h"
33
34 #include "src/intra_edge.h"
35 #include "src/levels.h"
36
37 struct ModeSelMem {
38 EdgeBranch *nwc[3 /* 64x64, 32x32, 16x16 */];
39 EdgeTip *nt;
40 };
41
42 /* Because we're using 16-bit offsets to refer to other nodes those arrays
43 * are placed in a struct to ensure they're consecutive in memory. */
44 static struct {
45 EdgeBranch branch_sb128[1 + 4 + 16 + 64];
46 EdgeTip tip_sb128[256];
47 EdgeBranch branch_sb64[1 + 4 + 16];
48 EdgeTip tip_sb64[64];
49 } ALIGN(nodes, 16);
50
51 const EdgeNode *dav1d_intra_edge_tree[2] = {
52 (EdgeNode*)nodes.branch_sb128, (EdgeNode*)nodes.branch_sb64
53 };
54
init_edges(EdgeNode * const node,const enum BlockLevel bl,const enum EdgeFlags edge_flags)55 static COLD void init_edges(EdgeNode *const node,
56 const enum BlockLevel bl,
57 const enum EdgeFlags edge_flags)
58 {
59 node->o = edge_flags;
60 node->h[0] = edge_flags | EDGE_ALL_LEFT_HAS_BOTTOM;
61 node->v[0] = edge_flags | EDGE_ALL_TOP_HAS_RIGHT;
62
63 if (bl == BL_8X8) {
64 EdgeTip *const nt = (EdgeTip *) node;
65
66 node->h[1] = edge_flags & (EDGE_ALL_LEFT_HAS_BOTTOM |
67 EDGE_I420_TOP_HAS_RIGHT);
68 node->v[1] = edge_flags & (EDGE_ALL_TOP_HAS_RIGHT |
69 EDGE_I420_LEFT_HAS_BOTTOM |
70 EDGE_I422_LEFT_HAS_BOTTOM);
71
72 nt->split[0] = (edge_flags & EDGE_ALL_TOP_HAS_RIGHT) |
73 EDGE_I422_LEFT_HAS_BOTTOM;
74 nt->split[1] = edge_flags | EDGE_I444_TOP_HAS_RIGHT;
75 nt->split[2] = edge_flags & (EDGE_I420_TOP_HAS_RIGHT |
76 EDGE_I420_LEFT_HAS_BOTTOM |
77 EDGE_I422_LEFT_HAS_BOTTOM);
78 } else {
79 EdgeBranch *const nwc = (EdgeBranch *) node;
80
81 node->h[1] = edge_flags & EDGE_ALL_LEFT_HAS_BOTTOM;
82 node->v[1] = edge_flags & EDGE_ALL_TOP_HAS_RIGHT;
83
84 nwc->h4 = EDGE_ALL_LEFT_HAS_BOTTOM;
85 nwc->v4 = EDGE_ALL_TOP_HAS_RIGHT;
86 if (bl == BL_16X16) {
87 nwc->h4 |= edge_flags & EDGE_I420_TOP_HAS_RIGHT;
88 nwc->v4 |= edge_flags & (EDGE_I420_LEFT_HAS_BOTTOM |
89 EDGE_I422_LEFT_HAS_BOTTOM);
90 }
91 }
92 }
93
94 #define PTR_OFFSET(a, b) ((uint16_t)((uintptr_t)(b) - (uintptr_t)(a)))
95
init_mode_node(EdgeBranch * const nwc,const enum BlockLevel bl,struct ModeSelMem * const mem,const int top_has_right,const int left_has_bottom)96 static COLD void init_mode_node(EdgeBranch *const nwc,
97 const enum BlockLevel bl,
98 struct ModeSelMem *const mem,
99 const int top_has_right,
100 const int left_has_bottom)
101 {
102 init_edges(&nwc->node, bl,
103 (top_has_right ? EDGE_ALL_TOP_HAS_RIGHT : 0) |
104 (left_has_bottom ? EDGE_ALL_LEFT_HAS_BOTTOM : 0));
105 if (bl == BL_16X16) {
106 for (int n = 0; n < 4; n++) {
107 EdgeTip *const nt = mem->nt++;
108 nwc->split_offset[n] = PTR_OFFSET(nwc, nt);
109 init_edges(&nt->node, bl + 1,
110 ((n == 3 || (n == 1 && !top_has_right)) ? 0 :
111 EDGE_ALL_TOP_HAS_RIGHT) |
112 (!(n == 0 || (n == 2 && left_has_bottom)) ? 0 :
113 EDGE_ALL_LEFT_HAS_BOTTOM));
114 }
115 } else {
116 for (int n = 0; n < 4; n++) {
117 EdgeBranch *const nwc_child = mem->nwc[bl]++;
118 nwc->split_offset[n] = PTR_OFFSET(nwc, nwc_child);
119 init_mode_node(nwc_child, bl + 1, mem,
120 !(n == 3 || (n == 1 && !top_has_right)),
121 n == 0 || (n == 2 && left_has_bottom));
122 }
123 }
124 }
125
dav1d_init_intra_edge_tree(void)126 COLD void dav1d_init_intra_edge_tree(void) {
127 // This function is guaranteed to be called only once
128 struct ModeSelMem mem;
129
130 mem.nwc[BL_128X128] = &nodes.branch_sb128[1];
131 mem.nwc[BL_64X64] = &nodes.branch_sb128[1 + 4];
132 mem.nwc[BL_32X32] = &nodes.branch_sb128[1 + 4 + 16];
133 mem.nt = nodes.tip_sb128;
134 init_mode_node(nodes.branch_sb128, BL_128X128, &mem, 1, 0);
135 assert(mem.nwc[BL_128X128] == &nodes.branch_sb128[1 + 4]);
136 assert(mem.nwc[BL_64X64] == &nodes.branch_sb128[1 + 4 + 16]);
137 assert(mem.nwc[BL_32X32] == &nodes.branch_sb128[1 + 4 + 16 + 64]);
138 assert(mem.nt == &nodes.tip_sb128[256]);
139
140 mem.nwc[BL_128X128] = NULL;
141 mem.nwc[BL_64X64] = &nodes.branch_sb64[1];
142 mem.nwc[BL_32X32] = &nodes.branch_sb64[1 + 4];
143 mem.nt = nodes.tip_sb64;
144 init_mode_node(nodes.branch_sb64, BL_64X64, &mem, 1, 0);
145 assert(mem.nwc[BL_64X64] == &nodes.branch_sb64[1 + 4]);
146 assert(mem.nwc[BL_32X32] == &nodes.branch_sb64[1 + 4 + 16]);
147 assert(mem.nt == &nodes.tip_sb64[64]);
148 }
149