API tools faq
paste
Guest User

Untitled

a guest
Jan 15th, 2025
200
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.46 KB | None | 0 0
raw download clone embed print report
  1. /*
  2.  * solution.cpp
  3.  *
  4.  * Example solution.
  5.  * This is (almost) how blocks are actually compressed in TON.
  6.  * Normally, blocks are stored using vm::std_boc_serialize with mode=31.
  7.  * Compression algorithm takes a block, converts it to mode=2 (which has less extra information) and compresses it using lz4.
  8.  */
  9. #include <iostream>
  10. #include "td/utils/lz4.h"
  11. #include "td/utils/base64.h"
  12. #include "vm/boc.h"
  13. #include "td/utils/buffer.h"      // td::BufferSlice, td::Slice, td::MutableSlice
  14. #include "td/utils/misc.h"        // td::buffer_to_hex
  15. #include "td/utils/Slice.h"
  16. #include "vm/cellslice.h"  
  17. #include "td/utils/Gzip.h"
  18. #include "td/utils/ByteFlow.h"
  19.  //#include "zlib.h"
  20. #include <limits>
  21.  
  22.  
  23. using namespace std;
  24. int counter = 0, counter2 = 0, counter3 = 0, counter4 = 0;
  25. int coun = 0;
  26. map<int, td::Ref<vm::Cell>> used_ref;
  27. map<string, int> num;
  28. map<string, bool> used_st;
  29. map<int, bool> used_int;
  30. map<int, string> datas, refs, cells_info;
  31. int coun1 = 0, coun2 = 0;
  32. int num_sp = 0;
  33. int la = 0, co = 0;
  34. void dfs_encode(td::Ref<vm::Cell> v) {
  35.     if (used_st[v->get_hash().to_hex()]) {
  36.         return;
  37.     }
  38.     used_st[v->get_hash().to_hex()] = 1;
  39.     bool b = true;
  40.     vm::CellSlice cellslice_v = vm::load_cell_slice_special(v, b);
  41.     vm::CellBuilder cell_build;
  42.     int num_data = cellslice_v.size();
  43.     string s = "";
  44.     for (int i = 0; i < num_data / 8; i++) {
  45.         char ch = cellslice_v.fetch_long(8);
  46.         s += ch;
  47.     }
  48.     if (cellslice_v.size() != 0) {
  49.         int pl = pow(2, cellslice_v.size());
  50.         int val = 0;
  51.         for (int i = 0; i < num_data % 8; i++) {
  52.             int val2 = abs(cellslice_v.fetch_long(1));
  53.             val *= 2;
  54.             val += val2;
  55.         }
  56.         val += pl;
  57.         u_char ch = val;
  58.         s += ch;
  59.     }
  60.     int cur_counter = counter;
  61.     counter++;
  62.     datas[cur_counter] = s;
  63.     int num_cit = cellslice_v.size_refs();
  64.     s = "";
  65.     if (cellslice_v.is_special()) {
  66.         num_sp++;
  67.     }
  68.     u_char ch = num_cit + 8 * cellslice_v.is_special();
  69.     s += ch;
  70.     ch = (num_data / 8) * 2;
  71.     if (num_data % 8 != 0) {
  72.         ch++;
  73.     }
  74.     s += ch;
  75.     cells_info[cur_counter] = s;
  76.     s = "";
  77.     for (int i = 0; i < num_cit; i++) {
  78.         td::Ref<vm::Cell> son = cellslice_v.fetch_ref();
  79.         if (used_st[son->get_hash().to_hex()]) {
  80.             //cout << cur_counter << " " << i << endl;
  81.             int val = num[son->get_hash().to_hex()];
  82.             if (val - la >= 0 && val - la < 16) {
  83.                 val = val - la;
  84.                 la = num[son->get_hash().to_hex()];
  85.                 u_char ch = val + 128;
  86.                 s += ch;
  87.             }
  88.             else {
  89.                 co++;
  90.                 u_char ch = val / 256;
  91.                 s += ch;
  92.                 ch = val % 256;
  93.                 s += ch;
  94.             }
  95.             ch = cells_info[cur_counter][0];
  96.             ch += (16 << i);
  97.             cells_info[cur_counter][0] = ch;
  98.         }
  99.         else {
  100.             dfs_encode(son);
  101.         }
  102.     }
  103.     refs[cur_counter] = s;
  104.     num[v->get_hash().to_hex()] = cur_counter;
  105.     return;
  106. }
  107. td::Ref<vm::Cell> dfs_decode(int v) {
  108.     if (used_int[v]) {
  109.         return used_ref[v];
  110.     }
  111.     used_int[v] = 1;
  112.     vm::CellBuilder cell_build;
  113.     string s;
  114.     //cout << v << " " << (int)(u_char)cells_info[v][0] << " " << (int)(u_char)cells_info[v][1] << endl;
  115.     for (int i = 0; i < ((int)(u_char)(cells_info[v][1]) + 1) / 2; i++) {
  116.         if (i == ((int)(u_char)(cells_info[v][1]) + 1) / 2 - 1 && (int)(u_char)cells_info[v][1] % 2 == 1) {
  117.             int t = (int)(u_char)datas[v][i];
  118.             vector<bool> vec;
  119.             while (t > 1) {
  120.                 vec.push_back(t % 2);
  121.                 t /= 2;
  122.             }
  123.             reverse(vec.begin(), vec.end());
  124.             for (auto j : vec) {
  125.                 if (j == 0) {
  126.                     cell_build.store_zeroes(1);
  127.                 }
  128.                 else {
  129.                     cell_build.store_ones(1);
  130.                 }
  131.             }
  132.             continue;
  133.         }
  134.         s = "";
  135.         s += datas[v][i];
  136.         cell_build.store_bytes(s);
  137.     }
  138.     //cout << v << " " << (int)(u_char)cells_info[v][0] << endl;
  139.     coun++;
  140.     for (int i = 0; i < (int)(u_char)cells_info[v][0] % 8; i++) {
  141.         int son = (int)(u_char)refs[v][i * 2] * 256 + (int)(u_char)refs[v][i * 2 + 1];
  142.         if (son == 255 * 257) {
  143.             son = coun;
  144.         }
  145.         else {
  146.             if (son >= 128 * 256) {
  147.                 son = la + son / 256 - 128;
  148.                 la = son;
  149.             }
  150.         }
  151.         cell_build.store_ref(dfs_decode(son));
  152.     }
  153.     used_ref[v] = cell_build.finalize(((int)(u_char)cells_info[v][0] % 16) / 8);
  154.     bool b = true;
  155.     return used_ref[v];
  156. }
  157. string enc(string s) {
  158.     td::BufferSlice buf(s);
  159.     buf = td::gzencode(buf, 100.0);
  160.     string ans = "";
  161.     for (int i = 0; i < buf.size(); i++) {
  162.         ans += buf[i];
  163.     }
  164.     return ans;
  165. }
  166. string dec(string s) {
  167.     td::BufferSlice buf(s);
  168.     buf = td::gzdecode(buf);
  169.     string ans = "";
  170.     for (int i = 0; i < buf.size(); i++) {
  171.         ans += buf[i];
  172.     }
  173.     return ans;
  174. }
  175. bool comp(int a, int b) {
  176.     if ((int)(u_char)cells_info[a][1] != (int)(u_char)cells_info[b][1]) {
  177.         return (int)(u_char)cells_info[a][1] > (int)(u_char)cells_info[b][1];
  178.     }
  179.     return a > b;
  180. }
  181. string encode(td::Ref<vm::Cell> root) {
  182.     counter = 0;
  183.     dfs_encode(root);
  184.     string code = "";
  185.     vector<bool> is_sp(counter, 0);
  186.     string codes[13];
  187.     u_char ch = counter / 256;
  188.     codes[0] += ch;
  189.     ch = counter % 256;
  190.     codes[0] += ch;
  191.     int coun = 0;
  192.     for (int i = 0; i < counter; i++) {
  193.         if ((int)(u_char)(cells_info[i][0] % 16) / 8 == 1) {
  194.             is_sp[i] = 1;
  195.         }
  196.         codes[0] += cells_info[i];
  197.         //cout << i << " " << (int)(u_char)cells_info[i][0] << " " << (int)(u_char)cells_info[i][1] << " " << datas[i].size() << endl;
  198.     }
  199.     vector<int> vec;
  200.     vec.clear();
  201.     for (int i = 0; i < counter; i++) {
  202.         if (!is_sp[i]) {
  203.             vec.push_back(i);
  204.         }
  205.     }
  206.     int non_sp_pos = 0;
  207.     sort(vec.begin(), vec.end(), comp);
  208.     for (int i = 0; i < counter; i++) {
  209.         int save_i = i;
  210.         if (!is_sp[i]) {
  211.             i = vec[non_sp_pos];
  212.             non_sp_pos++;
  213.         }
  214.         if (datas[i].size() >= 1 && is_sp[i]) {
  215.             codes[1] += datas[i][0];
  216.         }
  217.         else if (datas[i].size() >= 1) {
  218.             codes[6] += datas[i][0];
  219.         }
  220.         if (datas[i].size() >= 2 && is_sp[i]) {
  221.             codes[2] += datas[i][1];
  222.         }
  223.         else if (datas[i].size() >= 2) {
  224.             codes[7] += datas[i][1];
  225.         }
  226.         if (is_sp[i]) {
  227.             for (int j = 2; j < datas[i].size() - 2; j++) {
  228.                 codes[3] += datas[i][j];
  229.             }
  230.         }
  231.         else {
  232.             for (int j = 2; j < datas[i].size(); j++) {
  233.                 codes[8] += datas[i][j];
  234.             }
  235.         }
  236.         if (is_sp[i]) {
  237.             codes[4] += (int)(u_char)datas[i][datas[i].size() - 2];
  238.             codes[5] += (int)(u_char)datas[i][datas[i].size() - 1];
  239.         }
  240.         i = save_i;
  241.     }
  242.     //cout << (double)(enc(code2).size() + enc(code3).size()) / (double)(enc(code2 + code3).size()) << endl;
  243.     //cout << (double)(enc(code3).size() + enc(code4).size()) / (double)(enc(code3 + code4).size()) << endl;
  244.     for (int i = 0; i < counter; i++) {
  245.         for (int j = 0; j < refs[i].size(); j++) {
  246.             if ((int)(u_char)refs[i][j] >= 128) {
  247.                 codes[9] += refs[i][j];
  248.             }
  249.             else {
  250.                 codes[9] += refs[i][j];
  251.                 codes[10] += refs[i][j + 1];
  252.                 j++;
  253.             }
  254.         }
  255.     }
  256.     code = "";
  257.     code += (u_char)11;
  258.     for (int i = 0; i < 11; i++) {
  259.         code += (u_char)(enc(codes[i]).size() / 256 / 256);
  260.         code += (u_char)((enc(codes[i]).size() % (256 * 256)) / 256);
  261.         code += (u_char)(enc(codes[i]).size() % 256);
  262.     }
  263.     for (int i = 0; i < 11; i++) {
  264.         code += enc(codes[i]);
  265.     }
  266.     return code;
  267. }
  268. td::Ref<vm::Cell> decode(string code) {
  269.     string code2 = "";
  270.     int num = (u_char)code[0];
  271.     int pos = 1 + num * 3;
  272.     int pos2 = 0;
  273.     for (int i = 0; i < num; i++) {
  274.         string cur_decode = "";
  275.         int cur_len = (u_char)code[i * 3 + 1] * 256 * 256 + (u_char)code[i * 3 + 2] * 256 + (u_char)code[i * 3 + 3];
  276.         for (int j = 0; j < cur_len; j++) {
  277.             cur_decode += code[pos];
  278.             pos++;
  279.         }
  280.         if (i == num - 1) {
  281.             pos2 = code2.size();
  282.         }
  283.         code2 += dec(cur_decode);
  284.     }
  285.     code = code2;
  286.     cells_info.clear();
  287.     datas.clear();
  288.     refs.clear();
  289.     int n = (int)(u_char)code[0] * 256 + (int)(u_char)code[1];
  290.     vector<bool> is_sp(n, 0);
  291.     pos = 2;
  292.     int sp_num = 0;
  293.     int num_sp = 0;
  294.     for (int i = 0; i < n; i++) {
  295.         u_char ch = code[pos];
  296.         if ((ch % 16) / 8 == 1) {
  297.             is_sp[i] = 1;
  298.             num_sp++;
  299.         }
  300.         cells_info[i] += ch;
  301.         ch = code[pos + 1];
  302.         cells_info[i] += ch;
  303.         pos += 2;
  304.     }
  305.     for (int i = 0; i < n; i++) {
  306.         if (!is_sp[i]) {
  307.             continue;
  308.         }
  309.         if (((int)(u_char)(cells_info[i][1]) + 1) / 2 > 0) {
  310.             datas[i] += code[pos];
  311.             pos++;
  312.         }
  313.     }
  314.     for (int i = 0; i < n; i++) {
  315.         if (!is_sp[i]) {
  316.             continue;
  317.         }
  318.         if (((int)(u_char)(cells_info[i][1]) + 1) / 2 > 1) {
  319.             datas[i] += code[pos];
  320.             pos++;
  321.         }
  322.     }
  323.     for (int i = 0; i < n; i++) {
  324.         if (!is_sp[i]) {
  325.             continue;
  326.         }
  327.         for (int j = 2; j < ((int)(u_char)(cells_info[i][1]) + 1) / 2 - 2; j++) {
  328.             datas[i] += code[pos];
  329.             pos++;
  330.         }
  331.     }
  332.     for (int i = 0; i < n; i++) {
  333.         if (!is_sp[i]) {
  334.             continue;
  335.         }
  336.         datas[i] += code[pos];
  337.         pos++;
  338.     }
  339.     for (int i = 0; i < n; i++) {
  340.         if (!is_sp[i]) {
  341.             continue;
  342.         }
  343.         datas[i] += code[pos];
  344.         pos++;
  345.     }
  346.     vector<int> vec;
  347.     vec.clear();
  348.     for (int i = 0; i < n; i++) {
  349.         if (!is_sp[i]) {
  350.             vec.push_back(i);
  351.         }
  352.     }
  353.     int non_sp_pos = 0;
  354.     sort(vec.begin(), vec.end(), comp);
  355.     for (int i = 0; i < n; i++) {
  356.         if (is_sp[i]) {
  357.             continue;
  358.         }
  359.         int save_i = i;
  360.         i = vec[non_sp_pos];
  361.         non_sp_pos++;
  362.         if (((int)(u_char)(cells_info[i][1]) + 1) / 2 > 0) {
  363.             datas[i] += code[pos];
  364.             pos++;
  365.         }
  366.         i = save_i;
  367.     }
  368.     non_sp_pos = 0;
  369.     for (int i = 0; i < n; i++) {
  370.         if (is_sp[i]) {
  371.             continue;
  372.         }
  373.         int save_i = i;
  374.         i = vec[non_sp_pos];
  375.         non_sp_pos++;
  376.         if (((int)(u_char)(cells_info[i][1]) + 1) / 2 > 1) {
  377.             datas[i] += code[pos];
  378.             pos++;
  379.         }
  380.         i = save_i;
  381.     }
  382.     non_sp_pos = 0;
  383.     for (int i = 0; i < n; i++) {
  384.         if (is_sp[i]) {
  385.             continue;
  386.         }
  387.         int save_i = i;
  388.         i = vec[non_sp_pos];
  389.         non_sp_pos++;
  390.         for (int j = 2; j < ((int)(u_char)(cells_info[i][1]) + 1) / 2; j++) {
  391.             datas[i] += code[pos];
  392.             pos++;
  393.         }
  394.         i = save_i;
  395.     }
  396.     //cout << pos << endl;
  397.     int cur_coun = 0;
  398.     for (int i = 0; i < n; i++) {
  399.         for (int j = 0; j < (int)(u_char)(cells_info[i][0]) % 8; j++) {
  400.             if ((int)(u_char)cells_info[i][0] % (16 << (j + 1)) < (16 << j)) {
  401.                 u_char ch = 255;
  402.                 refs[i] += ch;
  403.                 refs[i] += ch;
  404.             }
  405.             else {
  406.                 if ((int)(u_char)code[pos] >= 128) {
  407.                     refs[i] += code[pos];
  408.                     u_char ch = 0;
  409.                     refs[i] += ch;
  410.                     pos++;
  411.                 }
  412.                 else {
  413.                     refs[i] += code[pos];
  414.                     pos++;
  415.                     refs[i] += code[pos2];
  416.                     pos2++;
  417.                 }
  418.             }
  419.         }
  420.     }
  421.     //cout << cur_coun << endl;
  422.     la = 0;
  423.     return dfs_decode(0);
  424. }
  425. td::BufferSlice compress(td::Slice data) {
  426.     td::Ref<vm::Cell> root = vm::std_boc_deserialize(data).move_as_ok();
  427.     td::BufferSlice serialized(encode(root));
  428.     return serialized;
  429. }
  430.  
  431. td::BufferSlice decompress(td::Slice data) {
  432.     td::BufferSlice serialized(data);
  433.     string code = "";
  434.     for (int i = 0; i < serialized.size(); i++) {
  435.         code += serialized[i];
  436.     }
  437.     td::Ref<vm::Cell> root = decode(code);
  438.     return vm::std_boc_serialize(root, 31).move_as_ok();
  439. }
  440.  
  441. int main() {
  442.     std::string mode;
  443.     std::cin >> mode;
  444.     //CHECK(mode == "compress" || mode == "decompress");
  445.  
  446.     std::string base64_data;
  447.     std::cin >> base64_data;
  448.     //CHECK(!base64_data.empty());
  449.     //td::BufferSlice data2(td::base64_decode(base64_data).move_as_ok());
  450.     //std::cout << "Decoded = " << td::buffer_to_hex(data2) << "\n\n";
  451.  
  452.     td::BufferSlice data(td::base64_decode(base64_data).move_as_ok());
  453.     /*if (decompress(compress(data)) == data) {
  454.         cout << 57 << endl;
  455.     }*/
  456.     if (mode == "compress") {
  457.         data = compress(data);
  458.     }
  459.     else {
  460.         data = decompress(data);
  461.     }
  462.     //cout << data.size() << endl;
  463.     std::cout << td::base64_encode(data) << std::endl;
  464. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!