diff options
Diffstat (limited to 'third_party/aom/tools/txfm_analyzer/txfm_graph.cc')
| -rw-r--r-- | third_party/aom/tools/txfm_analyzer/txfm_graph.cc | 943 |
1 files changed, 943 insertions, 0 deletions
diff --git a/third_party/aom/tools/txfm_analyzer/txfm_graph.cc b/third_party/aom/tools/txfm_analyzer/txfm_graph.cc new file mode 100644 index 000000000..a24906100 --- /dev/null +++ b/third_party/aom/tools/txfm_analyzer/txfm_graph.cc @@ -0,0 +1,943 @@ +/* + * 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]); + } + } + } +} |