diff options
author | Matt A. Tobin <email@mattatobin.com> | 2020-04-07 23:30:51 -0400 |
---|---|---|
committer | wolfbeast <mcwerewolf@wolfbeast.com> | 2020-04-14 13:26:42 +0200 |
commit | 277f2116b6660e9bbe7f5d67524be57eceb49b8b (patch) | |
tree | 4595f7cc71418f71b9a97dfaeb03a30aa60f336a /third_party/aom/tools/txfm_analyzer | |
parent | d270404436f6e84ffa3b92af537ac721bf10d66e (diff) | |
download | UXP-277f2116b6660e9bbe7f5d67524be57eceb49b8b.tar UXP-277f2116b6660e9bbe7f5d67524be57eceb49b8b.tar.gz UXP-277f2116b6660e9bbe7f5d67524be57eceb49b8b.tar.lz UXP-277f2116b6660e9bbe7f5d67524be57eceb49b8b.tar.xz UXP-277f2116b6660e9bbe7f5d67524be57eceb49b8b.zip |
Move aom source to a sub-directory under media/libaom
There is no damned reason to treat this differently than any other media lib given its license and there never was.
Diffstat (limited to 'third_party/aom/tools/txfm_analyzer')
-rw-r--r-- | third_party/aom/tools/txfm_analyzer/txfm_gen_code.cc | 580 | ||||
-rw-r--r-- | third_party/aom/tools/txfm_analyzer/txfm_graph.cc | 943 | ||||
-rw-r--r-- | third_party/aom/tools/txfm_analyzer/txfm_graph.h | 161 |
3 files changed, 0 insertions, 1684 deletions
diff --git a/third_party/aom/tools/txfm_analyzer/txfm_gen_code.cc b/third_party/aom/tools/txfm_analyzer/txfm_gen_code.cc deleted file mode 100644 index 7c5400b91..000000000 --- a/third_party/aom/tools/txfm_analyzer/txfm_gen_code.cc +++ /dev/null @@ -1,580 +0,0 @@ -/* - * Copyright (c) 2018, Alliance for Open Media. All rights reserved - * - * 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. - */ - -#include <stdio.h> -#include <stdlib.h> -#include <math.h> -#include <float.h> -#include <string.h> - -#include "tools/txfm_analyzer/txfm_graph.h" - -typedef enum CODE_TYPE { - CODE_TYPE_C, - CODE_TYPE_SSE2, - CODE_TYPE_SSE4_1 -} CODE_TYPE; - -int get_cos_idx(double value, int mod) { - return round(acos(fabs(value)) / PI * mod); -} - -char *cos_text_arr(double value, int mod, char *text, int size) { - int num = get_cos_idx(value, mod); - if (value < 0) { - snprintf(text, size, "-cospi[%2d]", num); - } else { - snprintf(text, size, " cospi[%2d]", num); - } - - if (num == 0) - printf("v: %f -> %d/%d v==-1 is %d\n", value, num, mod, value == -1); - - return text; -} - -char *cos_text_sse2(double w0, double w1, int mod, char *text, int size) { - int idx0 = get_cos_idx(w0, mod); - int idx1 = get_cos_idx(w1, mod); - char p[] = "p"; - char n[] = "m"; - char *sgn0 = w0 < 0 ? n : p; - char *sgn1 = w1 < 0 ? n : p; - snprintf(text, size, "cospi_%s%02d_%s%02d", sgn0, idx0, sgn1, idx1); - return text; -} - -char *cos_text_sse4_1(double w, int mod, char *text, int size) { - int idx = get_cos_idx(w, mod); - char p[] = "p"; - char n[] = "m"; - char *sgn = w < 0 ? n : p; - snprintf(text, size, "cospi_%s%02d", sgn, idx); - return text; -} - -void node_to_code_c(Node *node, const char *buf0, const char *buf1) { - int cnt = 0; - for (int i = 0; i < 2; i++) { - if (fabs(node->inWeight[i]) == 1 || fabs(node->inWeight[i]) == 0) cnt++; - } - if (cnt == 2) { - int cnt2 = 0; - printf(" %s[%d] =", buf1, node->nodeIdx); - for (int i = 0; i < 2; i++) { - if (fabs(node->inWeight[i]) == 1) { - cnt2++; - } - } - if (cnt2 == 2) { - printf(" apply_value("); - } - int cnt1 = 0; - for (int i = 0; i < 2; i++) { - if (node->inWeight[i] == 1) { - if (cnt1 > 0) - printf(" + %s[%d]", buf0, node->inNodeIdx[i]); - else - printf(" %s[%d]", buf0, node->inNodeIdx[i]); - cnt1++; - } else if (node->inWeight[i] == -1) { - if (cnt1 > 0) - printf(" - %s[%d]", buf0, node->inNodeIdx[i]); - else - printf("-%s[%d]", buf0, node->inNodeIdx[i]); - cnt1++; - } - } - if (cnt2 == 2) { - printf(", stage_range[stage])"); - } - printf(";\n"); - } else { - char w0[100]; - char w1[100]; - printf( - " %s[%d] = half_btf(%s, %s[%d], %s, %s[%d], " - "cos_bit);\n", - buf1, node->nodeIdx, cos_text_arr(node->inWeight[0], COS_MOD, w0, 100), - buf0, node->inNodeIdx[0], - cos_text_arr(node->inWeight[1], COS_MOD, w1, 100), buf0, - node->inNodeIdx[1]); - } -} - -void gen_code_c(Node *node, int stage_num, int node_num, TYPE_TXFM type) { - char *fun_name = new char[100]; - get_fun_name(fun_name, 100, type, node_num); - - printf("\n"); - printf( - "void av1_%s(const int32_t *input, int32_t *output, int8_t cos_bit, " - "const int8_t* stage_range) " - "{\n", - fun_name); - printf(" assert(output != input);\n"); - printf(" const int32_t size = %d;\n", node_num); - printf(" const int32_t *cospi = cospi_arr(cos_bit);\n"); - printf("\n"); - - printf(" int32_t stage = 0;\n"); - printf(" int32_t *bf0, *bf1;\n"); - printf(" int32_t step[%d];\n", node_num); - - const char *buf0 = "bf0"; - const char *buf1 = "bf1"; - const char *input = "input"; - - int si = 0; - printf("\n"); - printf(" // stage %d;\n", si); - printf(" apply_range(stage, input, %s, size, stage_range[stage]);\n", input); - - si = 1; - printf("\n"); - printf(" // stage %d;\n", si); - printf(" stage++;\n"); - if (si % 2 == (stage_num - 1) % 2) { - printf(" %s = output;\n", buf1); - } else { - printf(" %s = step;\n", buf1); - } - - for (int ni = 0; ni < node_num; ni++) { - int idx = get_idx(si, ni, node_num); - node_to_code_c(node + idx, input, buf1); - } - - printf(" range_check_buf(stage, input, bf1, size, stage_range[stage]);\n"); - - for (int si = 2; si < stage_num; si++) { - printf("\n"); - printf(" // stage %d\n", si); - printf(" stage++;\n"); - if (si % 2 == (stage_num - 1) % 2) { - printf(" %s = step;\n", buf0); - printf(" %s = output;\n", buf1); - } else { - printf(" %s = output;\n", buf0); - printf(" %s = step;\n", buf1); - } - - // computation code - for (int ni = 0; ni < node_num; ni++) { - int idx = get_idx(si, ni, node_num); - node_to_code_c(node + idx, buf0, buf1); - } - - if (si != stage_num - 1) { - printf( - " range_check_buf(stage, input, bf1, size, stage_range[stage]);\n"); - } - } - printf(" apply_range(stage, input, output, size, stage_range[stage]);\n"); - printf("}\n"); -} - -void single_node_to_code_sse2(Node *node, const char *buf0, const char *buf1) { - printf(" %s[%2d] =", buf1, node->nodeIdx); - if (node->inWeight[0] == 1 && node->inWeight[1] == 1) { - printf(" _mm_adds_epi16(%s[%d], %s[%d])", buf0, node->inNodeIdx[0], buf0, - node->inNodeIdx[1]); - } else if (node->inWeight[0] == 1 && node->inWeight[1] == -1) { - printf(" _mm_subs_epi16(%s[%d], %s[%d])", buf0, node->inNodeIdx[0], buf0, - node->inNodeIdx[1]); - } else if (node->inWeight[0] == -1 && node->inWeight[1] == 1) { - printf(" _mm_subs_epi16(%s[%d], %s[%d])", buf0, node->inNodeIdx[1], buf0, - node->inNodeIdx[0]); - } else if (node->inWeight[0] == 1 && node->inWeight[1] == 0) { - printf(" %s[%d]", buf0, node->inNodeIdx[0]); - } else if (node->inWeight[0] == 0 && node->inWeight[1] == 1) { - printf(" %s[%d]", buf0, node->inNodeIdx[1]); - } else if (node->inWeight[0] == -1 && node->inWeight[1] == 0) { - printf(" _mm_subs_epi16(__zero, %s[%d])", buf0, node->inNodeIdx[0]); - } else if (node->inWeight[0] == 0 && node->inWeight[1] == -1) { - printf(" _mm_subs_epi16(__zero, %s[%d])", buf0, node->inNodeIdx[1]); - } - printf(";\n"); -} - -void pair_node_to_code_sse2(Node *node, Node *partnerNode, const char *buf0, - const char *buf1) { - char temp0[100]; - char temp1[100]; - // btf_16_sse2_type0(w0, w1, in0, in1, out0, out1) - if (node->inNodeIdx[0] != partnerNode->inNodeIdx[0]) - printf(" btf_16_sse2(%s, %s, %s[%d], %s[%d], %s[%d], %s[%d]);\n", - cos_text_sse2(node->inWeight[0], node->inWeight[1], COS_MOD, temp0, - 100), - cos_text_sse2(partnerNode->inWeight[1], partnerNode->inWeight[0], - COS_MOD, temp1, 100), - buf0, node->inNodeIdx[0], buf0, node->inNodeIdx[1], buf1, - node->nodeIdx, buf1, partnerNode->nodeIdx); - else - printf(" btf_16_sse2(%s, %s, %s[%d], %s[%d], %s[%d], %s[%d]);\n", - cos_text_sse2(node->inWeight[0], node->inWeight[1], COS_MOD, temp0, - 100), - cos_text_sse2(partnerNode->inWeight[0], partnerNode->inWeight[1], - COS_MOD, temp1, 100), - buf0, node->inNodeIdx[0], buf0, node->inNodeIdx[1], buf1, - node->nodeIdx, buf1, partnerNode->nodeIdx); -} - -Node *get_partner_node(Node *node) { - int diff = node->inNode[1]->nodeIdx - node->nodeIdx; - return node + diff; -} - -void node_to_code_sse2(Node *node, const char *buf0, const char *buf1) { - int cnt = 0; - int cnt1 = 0; - if (node->visited == 0) { - node->visited = 1; - for (int i = 0; i < 2; i++) { - if (fabs(node->inWeight[i]) == 1 || fabs(node->inWeight[i]) == 0) cnt++; - if (fabs(node->inWeight[i]) == 1) cnt1++; - } - if (cnt == 2) { - if (cnt1 == 2) { - // has a partner - Node *partnerNode = get_partner_node(node); - partnerNode->visited = 1; - single_node_to_code_sse2(node, buf0, buf1); - single_node_to_code_sse2(partnerNode, buf0, buf1); - } else { - single_node_to_code_sse2(node, buf0, buf1); - } - } else { - Node *partnerNode = get_partner_node(node); - partnerNode->visited = 1; - pair_node_to_code_sse2(node, partnerNode, buf0, buf1); - } - } -} - -void gen_cospi_list_sse2(Node *node, int stage_num, int node_num) { - int visited[65][65][2][2]; - memset(visited, 0, sizeof(visited)); - char text[100]; - char text1[100]; - char text2[100]; - int size = 100; - printf("\n"); - for (int si = 1; si < stage_num; si++) { - for (int ni = 0; ni < node_num; ni++) { - int idx = get_idx(si, ni, node_num); - int cnt = 0; - Node *node0 = node + idx; - if (node0->visited == 0) { - node0->visited = 1; - for (int i = 0; i < 2; i++) { - if (fabs(node0->inWeight[i]) == 1 || fabs(node0->inWeight[i]) == 0) - cnt++; - } - if (cnt != 2) { - { - double w0 = node0->inWeight[0]; - double w1 = node0->inWeight[1]; - int idx0 = get_cos_idx(w0, COS_MOD); - int idx1 = get_cos_idx(w1, COS_MOD); - int sgn0 = w0 < 0 ? 1 : 0; - int sgn1 = w1 < 0 ? 1 : 0; - - if (!visited[idx0][idx1][sgn0][sgn1]) { - visited[idx0][idx1][sgn0][sgn1] = 1; - printf(" __m128i %s = pair_set_epi16(%s, %s);\n", - cos_text_sse2(w0, w1, COS_MOD, text, size), - cos_text_arr(w0, COS_MOD, text1, size), - cos_text_arr(w1, COS_MOD, text2, size)); - } - } - Node *node1 = get_partner_node(node0); - node1->visited = 1; - if (node1->inNode[0]->nodeIdx != node0->inNode[0]->nodeIdx) { - double w0 = node1->inWeight[0]; - double w1 = node1->inWeight[1]; - int idx0 = get_cos_idx(w0, COS_MOD); - int idx1 = get_cos_idx(w1, COS_MOD); - int sgn0 = w0 < 0 ? 1 : 0; - int sgn1 = w1 < 0 ? 1 : 0; - - if (!visited[idx1][idx0][sgn1][sgn0]) { - visited[idx1][idx0][sgn1][sgn0] = 1; - printf(" __m128i %s = pair_set_epi16(%s, %s);\n", - cos_text_sse2(w1, w0, COS_MOD, text, size), - cos_text_arr(w1, COS_MOD, text1, size), - cos_text_arr(w0, COS_MOD, text2, size)); - } - } else { - double w0 = node1->inWeight[0]; - double w1 = node1->inWeight[1]; - int idx0 = get_cos_idx(w0, COS_MOD); - int idx1 = get_cos_idx(w1, COS_MOD); - int sgn0 = w0 < 0 ? 1 : 0; - int sgn1 = w1 < 0 ? 1 : 0; - - if (!visited[idx0][idx1][sgn0][sgn1]) { - visited[idx0][idx1][sgn0][sgn1] = 1; - printf(" __m128i %s = pair_set_epi16(%s, %s);\n", - cos_text_sse2(w0, w1, COS_MOD, text, size), - cos_text_arr(w0, COS_MOD, text1, size), - cos_text_arr(w1, COS_MOD, text2, size)); - } - } - } - } - } - } -} - -void gen_code_sse2(Node *node, int stage_num, int node_num, TYPE_TXFM type) { - char *fun_name = new char[100]; - get_fun_name(fun_name, 100, type, node_num); - - printf("\n"); - printf( - "void %s_sse2(const __m128i *input, __m128i *output, int8_t cos_bit) " - "{\n", - fun_name); - - printf(" const int32_t* cospi = cospi_arr(cos_bit);\n"); - printf(" const __m128i __zero = _mm_setzero_si128();\n"); - printf(" const __m128i __rounding = _mm_set1_epi32(1 << (cos_bit - 1));\n"); - - graph_reset_visited(node, stage_num, node_num); - gen_cospi_list_sse2(node, stage_num, node_num); - graph_reset_visited(node, stage_num, node_num); - for (int si = 1; si < stage_num; si++) { - char in[100]; - char out[100]; - printf("\n"); - printf(" // stage %d\n", si); - if (si == 1) - snprintf(in, 100, "%s", "input"); - else - snprintf(in, 100, "x%d", si - 1); - if (si == stage_num - 1) { - snprintf(out, 100, "%s", "output"); - } else { - snprintf(out, 100, "x%d", si); - printf(" __m128i %s[%d];\n", out, node_num); - } - // computation code - for (int ni = 0; ni < node_num; ni++) { - int idx = get_idx(si, ni, node_num); - node_to_code_sse2(node + idx, in, out); - } - } - - printf("}\n"); -} -void gen_cospi_list_sse4_1(Node *node, int stage_num, int node_num) { - int visited[65][2]; - memset(visited, 0, sizeof(visited)); - char text[100]; - char text1[100]; - int size = 100; - printf("\n"); - for (int si = 1; si < stage_num; si++) { - for (int ni = 0; ni < node_num; ni++) { - int idx = get_idx(si, ni, node_num); - Node *node0 = node + idx; - if (node0->visited == 0) { - int cnt = 0; - node0->visited = 1; - for (int i = 0; i < 2; i++) { - if (fabs(node0->inWeight[i]) == 1 || fabs(node0->inWeight[i]) == 0) - cnt++; - } - if (cnt != 2) { - for (int i = 0; i < 2; i++) { - if (fabs(node0->inWeight[i]) != 1 && - fabs(node0->inWeight[i]) != 0) { - double w = node0->inWeight[i]; - int idx = get_cos_idx(w, COS_MOD); - int sgn = w < 0 ? 1 : 0; - - if (!visited[idx][sgn]) { - visited[idx][sgn] = 1; - printf(" __m128i %s = _mm_set1_epi32(%s);\n", - cos_text_sse4_1(w, COS_MOD, text, size), - cos_text_arr(w, COS_MOD, text1, size)); - } - } - } - Node *node1 = get_partner_node(node0); - node1->visited = 1; - } - } - } - } -} - -void single_node_to_code_sse4_1(Node *node, const char *buf0, - const char *buf1) { - printf(" %s[%2d] =", buf1, node->nodeIdx); - if (node->inWeight[0] == 1 && node->inWeight[1] == 1) { - printf(" _mm_add_epi32(%s[%d], %s[%d])", buf0, node->inNodeIdx[0], buf0, - node->inNodeIdx[1]); - } else if (node->inWeight[0] == 1 && node->inWeight[1] == -1) { - printf(" _mm_sub_epi32(%s[%d], %s[%d])", buf0, node->inNodeIdx[0], buf0, - node->inNodeIdx[1]); - } else if (node->inWeight[0] == -1 && node->inWeight[1] == 1) { - printf(" _mm_sub_epi32(%s[%d], %s[%d])", buf0, node->inNodeIdx[1], buf0, - node->inNodeIdx[0]); - } else if (node->inWeight[0] == 1 && node->inWeight[1] == 0) { - printf(" %s[%d]", buf0, node->inNodeIdx[0]); - } else if (node->inWeight[0] == 0 && node->inWeight[1] == 1) { - printf(" %s[%d]", buf0, node->inNodeIdx[1]); - } else if (node->inWeight[0] == -1 && node->inWeight[1] == 0) { - printf(" _mm_sub_epi32(__zero, %s[%d])", buf0, node->inNodeIdx[0]); - } else if (node->inWeight[0] == 0 && node->inWeight[1] == -1) { - printf(" _mm_sub_epi32(__zero, %s[%d])", buf0, node->inNodeIdx[1]); - } - printf(";\n"); -} - -void pair_node_to_code_sse4_1(Node *node, Node *partnerNode, const char *buf0, - const char *buf1) { - char temp0[100]; - char temp1[100]; - if (node->inWeight[0] * partnerNode->inWeight[0] < 0) { - /* type0 - * cos sin - * sin -cos - */ - // btf_32_sse2_type0(w0, w1, in0, in1, out0, out1) - // out0 = w0*in0 + w1*in1 - // out1 = -w0*in1 + w1*in0 - printf( - " btf_32_type0_sse4_1_new(%s, %s, %s[%d], %s[%d], %s[%d], %s[%d], " - "__rounding, cos_bit);\n", - cos_text_sse4_1(node->inWeight[0], COS_MOD, temp0, 100), - cos_text_sse4_1(node->inWeight[1], COS_MOD, temp1, 100), buf0, - node->inNodeIdx[0], buf0, node->inNodeIdx[1], buf1, node->nodeIdx, buf1, - partnerNode->nodeIdx); - } else { - /* type1 - * cos sin - * -sin cos - */ - // btf_32_sse2_type1(w0, w1, in0, in1, out0, out1) - // out0 = w0*in0 + w1*in1 - // out1 = w0*in1 - w1*in0 - printf( - " btf_32_type1_sse4_1_new(%s, %s, %s[%d], %s[%d], %s[%d], %s[%d], " - "__rounding, cos_bit);\n", - cos_text_sse4_1(node->inWeight[0], COS_MOD, temp0, 100), - cos_text_sse4_1(node->inWeight[1], COS_MOD, temp1, 100), buf0, - node->inNodeIdx[0], buf0, node->inNodeIdx[1], buf1, node->nodeIdx, buf1, - partnerNode->nodeIdx); - } -} - -void node_to_code_sse4_1(Node *node, const char *buf0, const char *buf1) { - int cnt = 0; - int cnt1 = 0; - if (node->visited == 0) { - node->visited = 1; - for (int i = 0; i < 2; i++) { - if (fabs(node->inWeight[i]) == 1 || fabs(node->inWeight[i]) == 0) cnt++; - if (fabs(node->inWeight[i]) == 1) cnt1++; - } - if (cnt == 2) { - if (cnt1 == 2) { - // has a partner - Node *partnerNode = get_partner_node(node); - partnerNode->visited = 1; - single_node_to_code_sse4_1(node, buf0, buf1); - single_node_to_code_sse4_1(partnerNode, buf0, buf1); - } else { - single_node_to_code_sse2(node, buf0, buf1); - } - } else { - Node *partnerNode = get_partner_node(node); - partnerNode->visited = 1; - pair_node_to_code_sse4_1(node, partnerNode, buf0, buf1); - } - } -} - -void gen_code_sse4_1(Node *node, int stage_num, int node_num, TYPE_TXFM type) { - char *fun_name = new char[100]; - get_fun_name(fun_name, 100, type, node_num); - - printf("\n"); - printf( - "void %s_sse4_1(const __m128i *input, __m128i *output, int8_t cos_bit) " - "{\n", - fun_name); - - printf(" const int32_t* cospi = cospi_arr(cos_bit);\n"); - printf(" const __m128i __zero = _mm_setzero_si128();\n"); - printf(" const __m128i __rounding = _mm_set1_epi32(1 << (cos_bit - 1));\n"); - - graph_reset_visited(node, stage_num, node_num); - gen_cospi_list_sse4_1(node, stage_num, node_num); - graph_reset_visited(node, stage_num, node_num); - for (int si = 1; si < stage_num; si++) { - char in[100]; - char out[100]; - printf("\n"); - printf(" // stage %d\n", si); - if (si == 1) - snprintf(in, 100, "%s", "input"); - else - snprintf(in, 100, "x%d", si - 1); - if (si == stage_num - 1) { - snprintf(out, 100, "%s", "output"); - } else { - snprintf(out, 100, "x%d", si); - printf(" __m128i %s[%d];\n", out, node_num); - } - // computation code - for (int ni = 0; ni < node_num; ni++) { - int idx = get_idx(si, ni, node_num); - node_to_code_sse4_1(node + idx, in, out); - } - } - - printf("}\n"); -} - -void gen_hybrid_code(CODE_TYPE code_type, TYPE_TXFM txfm_type, int node_num) { - int stage_num = get_hybrid_stage_num(txfm_type, node_num); - - Node *node = new Node[node_num * stage_num]; - init_graph(node, stage_num, node_num); - - gen_hybrid_graph_1d(node, stage_num, node_num, 0, 0, node_num, txfm_type); - - switch (code_type) { - case CODE_TYPE_C: gen_code_c(node, stage_num, node_num, txfm_type); break; - case CODE_TYPE_SSE2: - gen_code_sse2(node, stage_num, node_num, txfm_type); - break; - case CODE_TYPE_SSE4_1: - gen_code_sse4_1(node, stage_num, node_num, txfm_type); - break; - } - - delete[] node; -} - -int main(int argc, char **argv) { - CODE_TYPE code_type = CODE_TYPE_SSE4_1; - for (int txfm_type = TYPE_DCT; txfm_type < TYPE_LAST; txfm_type++) { - for (int node_num = 4; node_num <= 64; node_num *= 2) { - gen_hybrid_code(code_type, (TYPE_TXFM)txfm_type, node_num); - } - } - return 0; -} diff --git a/third_party/aom/tools/txfm_analyzer/txfm_graph.cc b/third_party/aom/tools/txfm_analyzer/txfm_graph.cc deleted file mode 100644 index a24906100..000000000 --- a/third_party/aom/tools/txfm_analyzer/txfm_graph.cc +++ /dev/null @@ -1,943 +0,0 @@ -/* - * Copyright (c) 2018, Alliance for Open Media. All rights reserved - * - * 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. - */ - -#include "tools/txfm_analyzer/txfm_graph.h" - -#include <stdio.h> -#include <stdlib.h> -#include <math.h> - -typedef struct Node Node; - -void get_fun_name(char *str_fun_name, int str_buf_size, const TYPE_TXFM type, - const int txfm_size) { - if (type == TYPE_DCT) - snprintf(str_fun_name, str_buf_size, "fdct%d_new", txfm_size); - else if (type == TYPE_ADST) - snprintf(str_fun_name, str_buf_size, "fadst%d_new", txfm_size); - else if (type == TYPE_IDCT) - snprintf(str_fun_name, str_buf_size, "idct%d_new", txfm_size); - else if (type == TYPE_IADST) - snprintf(str_fun_name, str_buf_size, "iadst%d_new", txfm_size); -} - -void get_txfm_type_name(char *str_fun_name, int str_buf_size, - const TYPE_TXFM type, const int txfm_size) { - if (type == TYPE_DCT) - snprintf(str_fun_name, str_buf_size, "TXFM_TYPE_DCT%d", txfm_size); - else if (type == TYPE_ADST) - snprintf(str_fun_name, str_buf_size, "TXFM_TYPE_ADST%d", txfm_size); - else if (type == TYPE_IDCT) - snprintf(str_fun_name, str_buf_size, "TXFM_TYPE_DCT%d", txfm_size); - else if (type == TYPE_IADST) - snprintf(str_fun_name, str_buf_size, "TXFM_TYPE_ADST%d", txfm_size); -} - -void get_hybrid_2d_type_name(char *buf, int buf_size, const TYPE_TXFM type0, - const TYPE_TXFM type1, const int txfm_size0, - const int txfm_size1) { - if (type0 == TYPE_DCT && type1 == TYPE_DCT) - snprintf(buf, buf_size, "_dct_dct_%dx%d", txfm_size1, txfm_size0); - else if (type0 == TYPE_DCT && type1 == TYPE_ADST) - snprintf(buf, buf_size, "_dct_adst_%dx%d", txfm_size1, txfm_size0); - else if (type0 == TYPE_ADST && type1 == TYPE_ADST) - snprintf(buf, buf_size, "_adst_adst_%dx%d", txfm_size1, txfm_size0); - else if (type0 == TYPE_ADST && type1 == TYPE_DCT) - snprintf(buf, buf_size, "_adst_dct_%dx%d", txfm_size1, txfm_size0); -} - -TYPE_TXFM get_inv_type(TYPE_TXFM type) { - if (type == TYPE_DCT) - return TYPE_IDCT; - else if (type == TYPE_ADST) - return TYPE_IADST; - else if (type == TYPE_IDCT) - return TYPE_DCT; - else if (type == TYPE_IADST) - return TYPE_ADST; - else - return TYPE_LAST; -} - -void reference_dct_1d(double *in, double *out, int size) { - const double kInvSqrt2 = 0.707106781186547524400844362104; - for (int k = 0; k < size; k++) { - out[k] = 0; // initialize out[k] - for (int n = 0; n < size; n++) { - out[k] += in[n] * cos(PI * (2 * n + 1) * k / (2 * size)); - } - if (k == 0) out[k] = out[k] * kInvSqrt2; - } -} - -void reference_dct_2d(double *in, double *out, int size) { - double *tempOut = new double[size * size]; - // dct each row: in -> out - for (int r = 0; r < size; r++) { - reference_dct_1d(in + r * size, out + r * size, size); - } - - for (int r = 0; r < size; r++) { - // out ->tempOut - for (int c = 0; c < size; c++) { - tempOut[r * size + c] = out[c * size + r]; - } - } - for (int r = 0; r < size; r++) { - reference_dct_1d(tempOut + r * size, out + r * size, size); - } - delete[] tempOut; -} - -void reference_adst_1d(double *in, double *out, int size) { - for (int k = 0; k < size; k++) { - out[k] = 0; // initialize out[k] - for (int n = 0; n < size; n++) { - out[k] += in[n] * sin(PI * (2 * n + 1) * (2 * k + 1) / (4 * size)); - } - } -} - -void reference_hybrid_2d(double *in, double *out, int size, int type0, - int type1) { - double *tempOut = new double[size * size]; - // dct each row: in -> out - for (int r = 0; r < size; r++) { - if (type0 == TYPE_DCT) - reference_dct_1d(in + r * size, out + r * size, size); - else - reference_adst_1d(in + r * size, out + r * size, size); - } - - for (int r = 0; r < size; r++) { - // out ->tempOut - for (int c = 0; c < size; c++) { - tempOut[r * size + c] = out[c * size + r]; - } - } - for (int r = 0; r < size; r++) { - if (type1 == TYPE_DCT) - reference_dct_1d(tempOut + r * size, out + r * size, size); - else - reference_adst_1d(tempOut + r * size, out + r * size, size); - } - delete[] tempOut; -} - -void reference_hybrid_2d_new(double *in, double *out, int size0, int size1, - int type0, int type1) { - double *tempOut = new double[size0 * size1]; - // dct each row: in -> out - for (int r = 0; r < size1; r++) { - if (type0 == TYPE_DCT) - reference_dct_1d(in + r * size0, out + r * size0, size0); - else - reference_adst_1d(in + r * size0, out + r * size0, size0); - } - - for (int r = 0; r < size1; r++) { - // out ->tempOut - for (int c = 0; c < size0; c++) { - tempOut[c * size1 + r] = out[r * size0 + c]; - } - } - for (int r = 0; r < size0; r++) { - if (type1 == TYPE_DCT) - reference_dct_1d(tempOut + r * size1, out + r * size1, size1); - else - reference_adst_1d(tempOut + r * size1, out + r * size1, size1); - } - delete[] tempOut; -} - -unsigned int get_max_bit(unsigned int x) { - int max_bit = -1; - while (x) { - x = x >> 1; - max_bit++; - } - return max_bit; -} - -unsigned int bitwise_reverse(unsigned int x, int max_bit) { - x = ((x >> 16) & 0x0000ffff) | ((x & 0x0000ffff) << 16); - x = ((x >> 8) & 0x00ff00ff) | ((x & 0x00ff00ff) << 8); - x = ((x >> 4) & 0x0f0f0f0f) | ((x & 0x0f0f0f0f) << 4); - x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2); - x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1); - x = x >> (31 - max_bit); - return x; -} - -int get_idx(int ri, int ci, int cSize) { return ri * cSize + ci; } - -void add_node(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int in, double w) { - int outIdx = get_idx(stage_idx, node_idx, node_num); - int inIdx = get_idx(stage_idx - 1, in, node_num); - int idx = node[outIdx].inNodeNum; - if (idx < 2) { - node[outIdx].inNode[idx] = &node[inIdx]; - node[outIdx].inNodeIdx[idx] = in; - node[outIdx].inWeight[idx] = w; - idx++; - node[outIdx].inNodeNum = idx; - } else { - printf("Error: inNode is full"); - } -} - -void connect_node(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int in0, double w0, int in1, double w1) { - int outIdx = get_idx(stage_idx, node_idx, node_num); - int inIdx0 = get_idx(stage_idx - 1, in0, node_num); - int inIdx1 = get_idx(stage_idx - 1, in1, node_num); - - int idx = 0; - // if(w0 != 0) { - node[outIdx].inNode[idx] = &node[inIdx0]; - node[outIdx].inNodeIdx[idx] = in0; - node[outIdx].inWeight[idx] = w0; - idx++; - //} - - // if(w1 != 0) { - node[outIdx].inNode[idx] = &node[inIdx1]; - node[outIdx].inNodeIdx[idx] = in1; - node[outIdx].inWeight[idx] = w1; - idx++; - //} - - node[outIdx].inNodeNum = idx; -} - -void propagate(Node *node, int stage_num, int node_num, int stage_idx) { - for (int ni = 0; ni < node_num; ni++) { - int outIdx = get_idx(stage_idx, ni, node_num); - node[outIdx].value = 0; - for (int k = 0; k < node[outIdx].inNodeNum; k++) { - node[outIdx].value += - node[outIdx].inNode[k]->value * node[outIdx].inWeight[k]; - } - } -} - -int64_t round_shift(int64_t value, int bit) { - if (bit > 0) { - if (value < 0) { - return -round_shift(-value, bit); - } else { - return (value + (1 << (bit - 1))) >> bit; - } - } else { - return value << (-bit); - } -} - -void round_shift_array(int32_t *arr, int size, int bit) { - if (bit == 0) { - return; - } else { - for (int i = 0; i < size; i++) { - arr[i] = round_shift(arr[i], bit); - } - } -} - -void graph_reset_visited(Node *node, int stage_num, int node_num) { - for (int si = 0; si < stage_num; si++) { - for (int ni = 0; ni < node_num; ni++) { - int idx = get_idx(si, ni, node_num); - node[idx].visited = 0; - } - } -} - -void estimate_value(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int estimate_bit) { - if (stage_idx > 0) { - int outIdx = get_idx(stage_idx, node_idx, node_num); - int64_t out = 0; - node[outIdx].value = 0; - for (int k = 0; k < node[outIdx].inNodeNum; k++) { - int64_t w = round(node[outIdx].inWeight[k] * (1 << estimate_bit)); - int64_t v = round(node[outIdx].inNode[k]->value); - out += v * w; - } - node[outIdx].value = round_shift(out, estimate_bit); - } -} - -void amplify_value(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int amplify_bit) { - int outIdx = get_idx(stage_idx, node_idx, node_num); - node[outIdx].value = round_shift(round(node[outIdx].value), -amplify_bit); -} - -void propagate_estimate_amlify(Node *node, int stage_num, int node_num, - int stage_idx, int amplify_bit, - int estimate_bit) { - for (int ni = 0; ni < node_num; ni++) { - estimate_value(node, stage_num, node_num, stage_idx, ni, estimate_bit); - amplify_value(node, stage_num, node_num, stage_idx, ni, amplify_bit); - } -} - -void init_graph(Node *node, int stage_num, int node_num) { - for (int si = 0; si < stage_num; si++) { - for (int ni = 0; ni < node_num; ni++) { - int outIdx = get_idx(si, ni, node_num); - node[outIdx].stageIdx = si; - node[outIdx].nodeIdx = ni; - node[outIdx].value = 0; - node[outIdx].inNodeNum = 0; - if (si >= 1) { - connect_node(node, stage_num, node_num, si, ni, ni, 1, ni, 0); - } - } - } -} - -void gen_B_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N, int star) { - for (int i = 0; i < N / 2; i++) { - int out = node_idx + i; - int in1 = node_idx + N - 1 - i; - if (star == 1) { - connect_node(node, stage_num, node_num, stage_idx + 1, out, out, -1, in1, - 1); - } else { - connect_node(node, stage_num, node_num, stage_idx + 1, out, out, 1, in1, - 1); - } - } - for (int i = N / 2; i < N; i++) { - int out = node_idx + i; - int in1 = node_idx + N - 1 - i; - if (star == 1) { - connect_node(node, stage_num, node_num, stage_idx + 1, out, out, 1, in1, - 1); - } else { - connect_node(node, stage_num, node_num, stage_idx + 1, out, out, -1, in1, - 1); - } - } -} - -void gen_P_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N) { - int max_bit = get_max_bit(N - 1); - for (int i = 0; i < N; i++) { - int out = node_idx + bitwise_reverse(i, max_bit); - int in = node_idx + i; - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, 1, in, 0); - } -} - -void gen_type1_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N) { - int max_bit = get_max_bit(N); - for (int ni = 0; ni < N / 2; ni++) { - int ai = bitwise_reverse(N + ni, max_bit); - int out = node_idx + ni; - int in1 = node_idx + N - ni - 1; - connect_node(node, stage_num, node_num, stage_idx + 1, out, out, - sin(PI * ai / (2 * 2 * N)), in1, cos(PI * ai / (2 * 2 * N))); - } - for (int ni = N / 2; ni < N; ni++) { - int ai = bitwise_reverse(N + ni, max_bit); - int out = node_idx + ni; - int in1 = node_idx + N - ni - 1; - connect_node(node, stage_num, node_num, stage_idx + 1, out, out, - cos(PI * ai / (2 * 2 * N)), in1, -sin(PI * ai / (2 * 2 * N))); - } -} - -void gen_type2_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N) { - for (int ni = 0; ni < N / 4; ni++) { - int out = node_idx + ni; - connect_node(node, stage_num, node_num, stage_idx + 1, out, out, 1, out, 0); - } - - for (int ni = N / 4; ni < N / 2; ni++) { - int out = node_idx + ni; - int in1 = node_idx + N - ni - 1; - connect_node(node, stage_num, node_num, stage_idx + 1, out, out, - -cos(PI / 4), in1, cos(-PI / 4)); - } - - for (int ni = N / 2; ni < N * 3 / 4; ni++) { - int out = node_idx + ni; - int in1 = node_idx + N - ni - 1; - connect_node(node, stage_num, node_num, stage_idx + 1, out, out, - cos(-PI / 4), in1, cos(PI / 4)); - } - - for (int ni = N * 3 / 4; ni < N; ni++) { - int out = node_idx + ni; - connect_node(node, stage_num, node_num, stage_idx + 1, out, out, 1, out, 0); - } -} - -void gen_type3_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int idx, int N) { - // TODO(angiebird): Simplify and clarify this function - - int i = 2 * N / (1 << (idx / 2)); - int max_bit = - get_max_bit(i / 2) - 1; // the max_bit counts on i/2 instead of N here - int N_over_i = 2 << (idx / 2); - - for (int nj = 0; nj < N / 2; nj += N_over_i) { - int j = nj / (N_over_i); - int kj = bitwise_reverse(i / 4 + j, max_bit); - // printf("kj = %d\n", kj); - - // I_N/2i --- 0 - int offset = nj; - for (int ni = 0; ni < N_over_i / 4; ni++) { - int out = node_idx + offset + ni; - int in = out; - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, 1, in, 0); - } - - // -C_Kj/i --- S_Kj/i - offset += N_over_i / 4; - for (int ni = 0; ni < N_over_i / 4; ni++) { - int out = node_idx + offset + ni; - int in0 = out; - double w0 = -cos(kj * PI / i); - int in1 = N - (offset + ni) - 1 + node_idx; - double w1 = sin(kj * PI / i); - connect_node(node, stage_num, node_num, stage_idx + 1, out, in0, w0, in1, - w1); - } - - // S_kj/i --- -C_Kj/i - offset += N_over_i / 4; - for (int ni = 0; ni < N_over_i / 4; ni++) { - int out = node_idx + offset + ni; - int in0 = out; - double w0 = -sin(kj * PI / i); - int in1 = N - (offset + ni) - 1 + node_idx; - double w1 = -cos(kj * PI / i); - connect_node(node, stage_num, node_num, stage_idx + 1, out, in0, w0, in1, - w1); - } - - // I_N/2i --- 0 - offset += N_over_i / 4; - for (int ni = 0; ni < N_over_i / 4; ni++) { - int out = node_idx + offset + ni; - int in = out; - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, 1, in, 0); - } - } - - for (int nj = N / 2; nj < N; nj += N_over_i) { - int j = nj / N_over_i; - int kj = bitwise_reverse(i / 4 + j, max_bit); - - // I_N/2i --- 0 - int offset = nj; - for (int ni = 0; ni < N_over_i / 4; ni++) { - int out = node_idx + offset + ni; - int in = out; - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, 1, in, 0); - } - - // C_kj/i --- -S_Kj/i - offset += N_over_i / 4; - for (int ni = 0; ni < N_over_i / 4; ni++) { - int out = node_idx + offset + ni; - int in0 = out; - double w0 = cos(kj * PI / i); - int in1 = N - (offset + ni) - 1 + node_idx; - double w1 = -sin(kj * PI / i); - connect_node(node, stage_num, node_num, stage_idx + 1, out, in0, w0, in1, - w1); - } - - // S_kj/i --- C_Kj/i - offset += N_over_i / 4; - for (int ni = 0; ni < N_over_i / 4; ni++) { - int out = node_idx + offset + ni; - int in0 = out; - double w0 = sin(kj * PI / i); - int in1 = N - (offset + ni) - 1 + node_idx; - double w1 = cos(kj * PI / i); - connect_node(node, stage_num, node_num, stage_idx + 1, out, in0, w0, in1, - w1); - } - - // I_N/2i --- 0 - offset += N_over_i / 4; - for (int ni = 0; ni < N_over_i / 4; ni++) { - int out = node_idx + offset + ni; - int in = out; - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, 1, in, 0); - } - } -} - -void gen_type4_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int idx, int N) { - int B_size = 1 << ((idx + 1) / 2); - for (int ni = 0; ni < N; ni += B_size) { - gen_B_graph(node, stage_num, node_num, stage_idx, node_idx + ni, B_size, - (ni / B_size) % 2); - } -} - -void gen_R_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N) { - int max_idx = 2 * (get_max_bit(N) + 1) - 3; - for (int idx = 0; idx < max_idx; idx++) { - int s = stage_idx + max_idx - idx - 1; - if (idx == 0) { - // type 1 - gen_type1_graph(node, stage_num, node_num, s, node_idx, N); - } else if (idx == max_idx - 1) { - // type 2 - gen_type2_graph(node, stage_num, node_num, s, node_idx, N); - } else if ((idx + 1) % 2 == 0) { - // type 4 - gen_type4_graph(node, stage_num, node_num, s, node_idx, idx, N); - } else if ((idx + 1) % 2 == 1) { - // type 3 - gen_type3_graph(node, stage_num, node_num, s, node_idx, idx, N); - } else { - printf("check gen_R_graph()\n"); - } - } -} - -void gen_DCT_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N) { - if (N > 2) { - gen_B_graph(node, stage_num, node_num, stage_idx, node_idx, N, 0); - gen_DCT_graph(node, stage_num, node_num, stage_idx + 1, node_idx, N / 2); - gen_R_graph(node, stage_num, node_num, stage_idx + 1, node_idx + N / 2, - N / 2); - } else { - // generate dct_2 - connect_node(node, stage_num, node_num, stage_idx + 1, node_idx, node_idx, - cos(PI / 4), node_idx + 1, cos(PI / 4)); - connect_node(node, stage_num, node_num, stage_idx + 1, node_idx + 1, - node_idx + 1, -cos(PI / 4), node_idx, cos(PI / 4)); - } -} - -int get_dct_stage_num(int size) { return 2 * get_max_bit(size); } - -void gen_DCT_graph_1d(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int dct_node_num) { - gen_DCT_graph(node, stage_num, node_num, stage_idx, node_idx, dct_node_num); - int dct_stage_num = get_dct_stage_num(dct_node_num); - gen_P_graph(node, stage_num, node_num, stage_idx + dct_stage_num - 2, - node_idx, dct_node_num); -} - -void gen_adst_B_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_idx) { - int size = 1 << (adst_idx + 1); - for (int ni = 0; ni < size / 2; ni++) { - int nOut = node_idx + ni; - int nIn = nOut + size / 2; - connect_node(node, stage_num, node_num, stage_idx + 1, nOut, nOut, 1, nIn, - 1); - // printf("nOut: %d nIn: %d\n", nOut, nIn); - } - for (int ni = size / 2; ni < size; ni++) { - int nOut = node_idx + ni; - int nIn = nOut - size / 2; - connect_node(node, stage_num, node_num, stage_idx + 1, nOut, nOut, -1, nIn, - 1); - // printf("ndctOut: %d nIn: %d\n", nOut, nIn); - } -} - -void gen_adst_U_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_idx, int adst_node_num) { - int size = 1 << (adst_idx + 1); - for (int ni = 0; ni < adst_node_num; ni += size) { - gen_adst_B_graph(node, stage_num, node_num, stage_idx, node_idx + ni, - adst_idx); - } -} - -void gen_adst_T_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, double freq) { - connect_node(node, stage_num, node_num, stage_idx + 1, node_idx, node_idx, - cos(freq * PI), node_idx + 1, sin(freq * PI)); - connect_node(node, stage_num, node_num, stage_idx + 1, node_idx + 1, - node_idx + 1, -cos(freq * PI), node_idx, sin(freq * PI)); -} - -void gen_adst_E_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_idx) { - int size = 1 << (adst_idx); - for (int i = 0; i < size / 2; i++) { - int ni = i * 2; - double fi = (1 + 4 * i) * 1.0 / (1 << (adst_idx + 1)); - gen_adst_T_graph(node, stage_num, node_num, stage_idx, node_idx + ni, fi); - } -} - -void gen_adst_V_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_idx, int adst_node_num) { - int size = 1 << (adst_idx); - for (int i = 0; i < adst_node_num / size; i++) { - if (i % 2 == 1) { - int ni = i * size; - gen_adst_E_graph(node, stage_num, node_num, stage_idx, node_idx + ni, - adst_idx); - } - } -} -void gen_adst_VJ_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num) { - for (int i = 0; i < adst_node_num / 2; i++) { - int ni = i * 2; - double fi = (1 + 4 * i) * 1.0 / (4 * adst_node_num); - gen_adst_T_graph(node, stage_num, node_num, stage_idx, node_idx + ni, fi); - } -} -void gen_adst_Q_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num) { - // reverse order when idx is 1, 3, 5, 7 ... - // example of adst_node_num = 8: - // 0 1 2 3 4 5 6 7 - // --> 0 7 2 5 4 3 6 1 - for (int ni = 0; ni < adst_node_num; ni++) { - if (ni % 2 == 0) { - int out = node_idx + ni; - connect_node(node, stage_num, node_num, stage_idx + 1, out, out, 1, out, - 0); - } else { - int out = node_idx + ni; - int in = node_idx + adst_node_num - ni; - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, 1, in, 0); - } - } -} -void gen_adst_Ibar_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num) { - // reverse order - // 0 1 2 3 --> 3 2 1 0 - for (int ni = 0; ni < adst_node_num; ni++) { - int out = node_idx + ni; - int in = node_idx + adst_node_num - ni - 1; - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, 1, in, 0); - } -} - -int get_Q_out2in(int adst_node_num, int out) { - int in; - if (out % 2 == 0) { - in = out; - } else { - in = adst_node_num - out; - } - return in; -} - -int get_Ibar_out2in(int adst_node_num, int out) { - return adst_node_num - out - 1; -} - -void gen_adst_IbarQ_graph(Node *node, int stage_num, int node_num, - int stage_idx, int node_idx, int adst_node_num) { - // in -> Ibar -> Q -> out - for (int ni = 0; ni < adst_node_num; ni++) { - int out = node_idx + ni; - int in = node_idx + - get_Ibar_out2in(adst_node_num, get_Q_out2in(adst_node_num, ni)); - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, 1, in, 0); - } -} - -void gen_adst_D_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num) { - // reverse order - for (int ni = 0; ni < adst_node_num; ni++) { - int out = node_idx + ni; - int in = out; - if (ni % 2 == 0) { - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, 1, in, 0); - } else { - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, -1, in, - 0); - } - } -} - -int get_hadamard_idx(int x, int adst_node_num) { - int max_bit = get_max_bit(adst_node_num - 1); - x = bitwise_reverse(x, max_bit); - - // gray code - int c = x & 1; - int p = x & 1; - int y = c; - - for (int i = 1; i <= max_bit; i++) { - p = c; - c = (x >> i) & 1; - y += (c ^ p) << i; - } - return y; -} - -void gen_adst_Ht_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num) { - for (int ni = 0; ni < adst_node_num; ni++) { - int out = node_idx + ni; - int in = node_idx + get_hadamard_idx(ni, adst_node_num); - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, 1, in, 0); - } -} - -void gen_adst_HtD_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num) { - for (int ni = 0; ni < adst_node_num; ni++) { - int out = node_idx + ni; - int in = node_idx + get_hadamard_idx(ni, adst_node_num); - double inW; - if (ni % 2 == 0) - inW = 1; - else - inW = -1; - connect_node(node, stage_num, node_num, stage_idx + 1, out, in, inW, in, 0); - } -} - -int get_adst_stage_num(int adst_node_num) { - return 2 * get_max_bit(adst_node_num) + 2; -} - -int gen_iadst_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num) { - int max_bit = get_max_bit(adst_node_num); - int si = 0; - gen_adst_IbarQ_graph(node, stage_num, node_num, stage_idx + si, node_idx, - adst_node_num); - si++; - gen_adst_VJ_graph(node, stage_num, node_num, stage_idx + si, node_idx, - adst_node_num); - si++; - for (int adst_idx = max_bit - 1; adst_idx >= 1; adst_idx--) { - gen_adst_U_graph(node, stage_num, node_num, stage_idx + si, node_idx, - adst_idx, adst_node_num); - si++; - gen_adst_V_graph(node, stage_num, node_num, stage_idx + si, node_idx, - adst_idx, adst_node_num); - si++; - } - gen_adst_HtD_graph(node, stage_num, node_num, stage_idx + si, node_idx, - adst_node_num); - si++; - return si + 1; -} - -int gen_adst_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num) { - int hybrid_stage_num = get_hybrid_stage_num(TYPE_ADST, adst_node_num); - // generate a adst tempNode - Node *tempNode = new Node[hybrid_stage_num * adst_node_num]; - init_graph(tempNode, hybrid_stage_num, adst_node_num); - int si = gen_iadst_graph(tempNode, hybrid_stage_num, adst_node_num, 0, 0, - adst_node_num); - - // tempNode's inverse graph to node[stage_idx][node_idx] - gen_inv_graph(tempNode, hybrid_stage_num, adst_node_num, node, stage_num, - node_num, stage_idx, node_idx); - delete[] tempNode; - return si; -} - -void connect_layer_2d(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int dct_node_num) { - for (int first = 0; first < dct_node_num; first++) { - for (int second = 0; second < dct_node_num; second++) { - // int sIn = stage_idx; - int sOut = stage_idx + 1; - int nIn = node_idx + first * dct_node_num + second; - int nOut = node_idx + second * dct_node_num + first; - - // printf("sIn: %d nIn: %d sOut: %d nOut: %d\n", sIn, nIn, sOut, nOut); - - connect_node(node, stage_num, node_num, sOut, nOut, nIn, 1, nIn, 0); - } - } -} - -void connect_layer_2d_new(Node *node, int stage_num, int node_num, - int stage_idx, int node_idx, int dct_node_num0, - int dct_node_num1) { - for (int i = 0; i < dct_node_num1; i++) { - for (int j = 0; j < dct_node_num0; j++) { - // int sIn = stage_idx; - int sOut = stage_idx + 1; - int nIn = node_idx + i * dct_node_num0 + j; - int nOut = node_idx + j * dct_node_num1 + i; - - // printf("sIn: %d nIn: %d sOut: %d nOut: %d\n", sIn, nIn, sOut, nOut); - - connect_node(node, stage_num, node_num, sOut, nOut, nIn, 1, nIn, 0); - } - } -} - -void gen_DCT_graph_2d(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int dct_node_num) { - int dct_stage_num = get_dct_stage_num(dct_node_num); - // put 2 layers of dct_node_num DCTs on the graph - for (int ni = 0; ni < dct_node_num; ni++) { - gen_DCT_graph_1d(node, stage_num, node_num, stage_idx, - node_idx + ni * dct_node_num, dct_node_num); - gen_DCT_graph_1d(node, stage_num, node_num, stage_idx + dct_stage_num, - node_idx + ni * dct_node_num, dct_node_num); - } - // connect first layer and second layer - connect_layer_2d(node, stage_num, node_num, stage_idx + dct_stage_num - 1, - node_idx, dct_node_num); -} - -int get_hybrid_stage_num(int type, int hybrid_node_num) { - if (type == TYPE_DCT || type == TYPE_IDCT) { - return get_dct_stage_num(hybrid_node_num); - } else if (type == TYPE_ADST || type == TYPE_IADST) { - return get_adst_stage_num(hybrid_node_num); - } - return 0; -} - -int get_hybrid_2d_stage_num(int type0, int type1, int hybrid_node_num) { - int stage_num = 0; - stage_num += get_hybrid_stage_num(type0, hybrid_node_num); - stage_num += get_hybrid_stage_num(type1, hybrid_node_num); - return stage_num; -} - -int get_hybrid_2d_stage_num_new(int type0, int type1, int hybrid_node_num0, - int hybrid_node_num1) { - int stage_num = 0; - stage_num += get_hybrid_stage_num(type0, hybrid_node_num0); - stage_num += get_hybrid_stage_num(type1, hybrid_node_num1); - return stage_num; -} - -int get_hybrid_amplify_factor(int type, int hybrid_node_num) { - return get_max_bit(hybrid_node_num) - 1; -} - -void gen_hybrid_graph_1d(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int hybrid_node_num, int type) { - if (type == TYPE_DCT) { - gen_DCT_graph_1d(node, stage_num, node_num, stage_idx, node_idx, - hybrid_node_num); - } else if (type == TYPE_ADST) { - gen_adst_graph(node, stage_num, node_num, stage_idx, node_idx, - hybrid_node_num); - } else if (type == TYPE_IDCT) { - int hybrid_stage_num = get_hybrid_stage_num(type, hybrid_node_num); - // generate a dct tempNode - Node *tempNode = new Node[hybrid_stage_num * hybrid_node_num]; - init_graph(tempNode, hybrid_stage_num, hybrid_node_num); - gen_DCT_graph_1d(tempNode, hybrid_stage_num, hybrid_node_num, 0, 0, - hybrid_node_num); - - // tempNode's inverse graph to node[stage_idx][node_idx] - gen_inv_graph(tempNode, hybrid_stage_num, hybrid_node_num, node, stage_num, - node_num, stage_idx, node_idx); - delete[] tempNode; - } else if (type == TYPE_IADST) { - int hybrid_stage_num = get_hybrid_stage_num(type, hybrid_node_num); - // generate a adst tempNode - Node *tempNode = new Node[hybrid_stage_num * hybrid_node_num]; - init_graph(tempNode, hybrid_stage_num, hybrid_node_num); - gen_adst_graph(tempNode, hybrid_stage_num, hybrid_node_num, 0, 0, - hybrid_node_num); - - // tempNode's inverse graph to node[stage_idx][node_idx] - gen_inv_graph(tempNode, hybrid_stage_num, hybrid_node_num, node, stage_num, - node_num, stage_idx, node_idx); - delete[] tempNode; - } -} - -void gen_hybrid_graph_2d(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int hybrid_node_num, int type0, - int type1) { - int hybrid_stage_num = get_hybrid_stage_num(type0, hybrid_node_num); - - for (int ni = 0; ni < hybrid_node_num; ni++) { - gen_hybrid_graph_1d(node, stage_num, node_num, stage_idx, - node_idx + ni * hybrid_node_num, hybrid_node_num, - type0); - gen_hybrid_graph_1d(node, stage_num, node_num, stage_idx + hybrid_stage_num, - node_idx + ni * hybrid_node_num, hybrid_node_num, - type1); - } - - // connect first layer and second layer - connect_layer_2d(node, stage_num, node_num, stage_idx + hybrid_stage_num - 1, - node_idx, hybrid_node_num); -} - -void gen_hybrid_graph_2d_new(Node *node, int stage_num, int node_num, - int stage_idx, int node_idx, int hybrid_node_num0, - int hybrid_node_num1, int type0, int type1) { - int hybrid_stage_num0 = get_hybrid_stage_num(type0, hybrid_node_num0); - - for (int ni = 0; ni < hybrid_node_num1; ni++) { - gen_hybrid_graph_1d(node, stage_num, node_num, stage_idx, - node_idx + ni * hybrid_node_num0, hybrid_node_num0, - type0); - } - for (int ni = 0; ni < hybrid_node_num0; ni++) { - gen_hybrid_graph_1d( - node, stage_num, node_num, stage_idx + hybrid_stage_num0, - node_idx + ni * hybrid_node_num1, hybrid_node_num1, type1); - } - - // connect first layer and second layer - connect_layer_2d_new(node, stage_num, node_num, - stage_idx + hybrid_stage_num0 - 1, node_idx, - hybrid_node_num0, hybrid_node_num1); -} - -void gen_inv_graph(Node *node, int stage_num, int node_num, Node *invNode, - int inv_stage_num, int inv_node_num, int inv_stage_idx, - int inv_node_idx) { - // clean up inNodeNum in invNode because of add_node - for (int si = 1 + inv_stage_idx; si < inv_stage_idx + stage_num; si++) { - for (int ni = inv_node_idx; ni < inv_node_idx + node_num; ni++) { - int idx = get_idx(si, ni, inv_node_num); - invNode[idx].inNodeNum = 0; - } - } - // generate inverse graph of node on invNode - for (int si = 1; si < stage_num; si++) { - for (int ni = 0; ni < node_num; ni++) { - int invSi = stage_num - si; - int idx = get_idx(si, ni, node_num); - for (int k = 0; k < node[idx].inNodeNum; k++) { - int invNi = node[idx].inNodeIdx[k]; - add_node(invNode, inv_stage_num, inv_node_num, invSi + inv_stage_idx, - invNi + inv_node_idx, ni + inv_node_idx, - node[idx].inWeight[k]); - } - } - } -} diff --git a/third_party/aom/tools/txfm_analyzer/txfm_graph.h b/third_party/aom/tools/txfm_analyzer/txfm_graph.h deleted file mode 100644 index 2e3c9551e..000000000 --- a/third_party/aom/tools/txfm_analyzer/txfm_graph.h +++ /dev/null @@ -1,161 +0,0 @@ -/* - * Copyright (c) 2018, Alliance for Open Media. All rights reserved - * - * 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. - */ - -#ifndef AOM_TOOLS_TXFM_ANALYZER_TXFM_GRAPH_H_ -#define AOM_TOOLS_TXFM_ANALYZER_TXFM_GRAPH_H_ - -struct Node { - Node *inNode[2]; - int inNodeNum; - int inNodeIdx[2]; - double inWeight[2]; - double value; - int nodeIdx; - int stageIdx; - int visited; -}; - -#define PI (3.141592653589793238462643383279502884) -#define STAGENUM (10) -#define NODENUM (32) -#define COS_MOD (128) - -typedef enum { - TYPE_DCT = 0, - TYPE_ADST, - TYPE_IDCT, - TYPE_IADST, - TYPE_LAST -} TYPE_TXFM; - -TYPE_TXFM get_inv_type(TYPE_TXFM type); -void get_fun_name(char *str_fun_name, int str_buf_size, const TYPE_TXFM type, - const int txfm_size); - -void get_txfm_type_name(char *str_fun_name, int str_buf_size, - const TYPE_TXFM type, const int txfm_size); -void get_hybrid_2d_type_name(char *buf, int buf_size, const TYPE_TXFM type0, - const TYPE_TXFM type1, const int txfm_size0, - const int txfm_size1); -unsigned int get_max_bit(unsigned int x); -unsigned int bitwise_reverse(unsigned int x, int max_bit); -int get_idx(int ri, int ci, int cSize); - -int get_dct_stage_num(int size); -void reference_dct_1d(double *in, double *out, int size); -void reference_dct_2d(double *in, double *out, int size); -void connect_node(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int in0, double w0, int in1, double w1); -void propagate(Node *node, int stage_num, int node_num, int stage); -void init_graph(Node *node, int stage_num, int node_num); -void graph_reset_visited(Node *node, int stage_num, int node_num); -void gen_B_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N, int star); -void gen_P_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N); - -void gen_type1_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N); -void gen_type2_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N); -void gen_type3_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int idx, int N); -void gen_type4_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int idx, int N); - -void gen_R_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N); - -void gen_DCT_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int N); - -void gen_DCT_graph_1d(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int dct_node_num); -void connect_layer_2d(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int dct_node_num); - -void gen_DCT_graph_2d(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int dct_node_num); - -void gen_adst_B_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_idx); - -void gen_adst_U_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_idx, int adst_node_num); -void gen_adst_T_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, double freq); - -void gen_adst_E_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_idx); - -void gen_adst_V_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_idx, int adst_node_num); - -void gen_adst_VJ_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num); -void gen_adst_Q_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num); -void gen_adst_Ibar_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num); - -void gen_adst_D_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num); - -int get_hadamard_idx(int x, int adst_node_num); -void gen_adst_Ht_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num); - -int gen_adst_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num); -int gen_iadst_graph(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int adst_node_num); -void reference_adst_1d(double *in, double *out, int size); - -int get_adst_stage_num(int adst_node_num); -int get_hybrid_stage_num(int type, int hybrid_node_num); -int get_hybrid_2d_stage_num(int type0, int type1, int hybrid_node_num); -int get_hybrid_2d_stage_num_new(int type0, int type1, int hybrid_node_num0, - int hybrid_node_num1); -int get_hybrid_amplify_factor(int type, int hybrid_node_num); -void gen_hybrid_graph_1d(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int hybrid_node_num, int type); -void gen_hybrid_graph_2d(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int hybrid_node_num, int type0, - int type1); -void gen_hybrid_graph_2d_new(Node *node, int stage_num, int node_num, - int stage_idx, int node_idx, int hybrid_node_num0, - int hybrid_node_num1, int type0, int type1); - -void reference_hybrid_2d(double *in, double *out, int size, int type0, - int type1); - -void reference_hybrid_2d_new(double *in, double *out, int size0, int size1, - int type0, int type1); -void reference_adst_dct_2d(double *in, double *out, int size); - -void gen_code(Node *node, int stage_num, int node_num, TYPE_TXFM type); - -void gen_inv_graph(Node *node, int stage_num, int node_num, Node *invNode, - int inv_stage_num, int inv_node_num, int inv_stage_idx, - int inv_node_idx); - -TYPE_TXFM hybrid_char_to_int(char ctype); - -int64_t round_shift(int64_t value, int bit); -void round_shift_array(int32_t *arr, int size, int bit); -void estimate_value(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int estimate_bit); -void amplify_value(Node *node, int stage_num, int node_num, int stage_idx, - int node_idx, int estimate_bit); -void propagate_estimate_amlify(Node *node, int stage_num, int node_num, - int stage_idx, int amplify_bit, - int estimate_bit); -#endif // AOM_TOOLS_TXFM_ANALYZER_TXFM_GRAPH_H_ |