Add txfm_gen_code.cc and txfm_graph.cc The txfm_graph.cc generates adst/dct butterfly graph. The txfm_gen_code.cc use the butterfly graph to generate txfm SIMD optimization directly Now these files stand alone from the cmake build system One can build this tool by the following command temporarily. g++ -o txfm_gen_code txfm_gen_code.cc txfm_graph.cc -I. Will add these files into the cmake build system in the future. Change-Id: Ia504fd7a296fe9442d3434ba3a8d6b5e64554e25
diff --git a/tools/txfm_analyzer/txfm_gen_code.cc b/tools/txfm_analyzer/txfm_gen_code.cc new file mode 100644 index 0000000..672ae03 --- /dev/null +++ b/tools/txfm_analyzer/txfm_gen_code.cc
@@ -0,0 +1,569 @@ +/* + * 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 "./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 cnt1 = 0; + printf(" %s[%d] =", buf1, node->nodeIdx); + 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++; + } + } + printf(";\n"); + } else { + char w0[100]; + char w1[100]; + printf( + " %s[%d] = half_btf(%s, %s[%d], %s, %s[%d], " + "cos_bit[stage_idx]);\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 %s(const int32_t *input, int32_t *output, const int8_t* cos_bit, " + "const int8_t* stage_range) " + "{\n", + fun_name); + printf(" const int32_t size = %d;\n", node_num); + printf(" const int32_t *cospi;\n"); + printf("\n"); + + printf(" int32_t stage_idx = 0;\n"); + printf(" int32_t *buf0, *buf1;\n"); + printf(" int32_t step[%d];\n", node_num); + + const char *buf0 = "buf0"; + const char *buf1 = "buf1"; + const char *input = "input"; + + int si = 0; + printf("\n"); + printf(" // stage %d;\n", si); + printf(" range_check(stage_idx, input, %s, size, stage_range[stage_idx]);\n", + input); + + si = 1; + printf("\n"); + printf(" // stage %d;\n", si); + printf(" stage_idx++;\n"); + printf(" cospi = cospi_arr[cos_bit[stage_idx] - cos_bit_min];\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(stage_idx, input, buf1, size, stage_range[stage_idx]);\n"); + + for (int si = 2; si < stage_num; si++) { + printf("\n"); + printf(" // stage %d\n", si); + printf(" stage_idx++;\n"); + printf(" cospi = cospi_arr[cos_bit[stage_idx] - cos_bit_min];\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); + } + + printf( + " range_check(stage_idx, input, buf1, size, " + "stage_range[stage_idx]);\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/tools/txfm_analyzer/txfm_graph.cc b/tools/txfm_analyzer/txfm_graph.cc new file mode 100644 index 0000000..22fe326 --- /dev/null +++ b/tools/txfm_analyzer/txfm_graph.cc
@@ -0,0 +1,942 @@ +/* + * 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 "./txfm_graph.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/tools/txfm_analyzer/txfm_graph.h b/tools/txfm_analyzer/txfm_graph.h new file mode 100644 index 0000000..76a9bc7 --- /dev/null +++ b/tools/txfm_analyzer/txfm_graph.h
@@ -0,0 +1,161 @@ +/* + * 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 TOOLS_TXFM_ANALYZER_H_ +#define TOOLS_TXFM_ANALYZER_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 // TOOLS_TXFM_ANALYZER_H_