Arduino as Socks5 Proxy Server
Still WIP because the buffer manipulation is so f**king problematic.
Hardware: Arduino Uno + W5100 Ethernet Module
Tested working through curl.
#include <SPI.h> #include <Ethernet.h> const uint8_t MAX_CONN = 4; ////////////////////////////////////////////////////////////////////////////// //Socks5 Server // Ref: https://github.com/mfontanini/Programs-Scripts/blob/master/socks5/socks5.cpp // const uint16_t SERVER_PORT = 23; const int BUFFER_SIZE = 512; byte socks_buffer[BUFFER_SIZE]; #define METHOD_NOAUTH 0 #define METHOD_AUTH 2 #define METHOD_NOTAVAILABLE 0xff /* Responses */ #define RESP_SUCCEDED 0 #define RESP_GEN_ERROR 1 /* Address type constants */ #define ATYP_IPV4 1 #define ATYP_DNAME 3 #define ATYP_IPV6 4 /* Command constants */ #define CMD_CONNECT 1 #define CMD_BIND 2 #define CMD_UDP_ASSOCIATIVE 3 #define htons(x) ( ((x)<< 8 & 0xFF00) | \ ((x)>> 8 & 0x00FF) ) #define ntohs(x) htons(x) #define htonl(x) ( ((x)<<24 & 0xFF000000UL) | \ ((x)<< 8 & 0x00FF0000UL) | \ ((x)>> 8 & 0x0000FF00UL) | \ ((x)>>24 & 0x000000FFUL) ) #define ntohl(x) htonl(x) struct MethodIdentificationPacket { uint8_t version_; uint8_t nmethods_; } __attribute__((packed)); struct MethodSelectionPacket { uint8_t version_; uint8_t method_; MethodSelectionPacket() : version_(5) { } } __attribute__((packed)); struct SOCKS5RequestHeader { uint8_t version_; uint8_t cmd_; uint8_t rsv_; uint8_t atyp_; } __attribute__((packed)); struct SOCK5IP4RequestBody { uint32_t ip_dst_; uint16_t port_; } __attribute__((packed)); struct SOCK5DNameRequestBody { uint8_t length_; } __attribute__((packed)); struct SOCKS5Response { uint8_t version_; uint8_t cmd_; uint8_t rsv_; uint8_t atyp_; uint32_t ip_src_; uint16_t port_src_; SOCKS5Response(bool succ = true) : version_(5), cmd_(succ ? RESP_SUCCEDED : RESP_GEN_ERROR), rsv_(0), atyp_(ATYP_IPV4) { } } __attribute__((packed)); bool handle_handshake(EthernetClient* client) { MethodIdentificationPacket packet; int count = client->read((byte*)&packet, sizeof(packet)); if (count != sizeof(packet) || packet.version_ != 5) { Serial.print("wrong handshake version!"); return false; } Serial.print((int)packet.version_); Serial.print(","); Serial.println((int)packet.nmethods_); count = client->read(socks_buffer, packet.nmethods_); if (count != packet.nmethods_) { Serial.print("wrong methods length:"); Serial.println(count); return false; } MethodSelectionPacket response; for (int i = 0; i < packet.nmethods_; ++i){ if (socks_buffer[i] == METHOD_NOAUTH) { response.method_ = METHOD_NOAUTH; break; } else if (socks_buffer[i] == METHOD_AUTH) { response.method_ = METHOD_AUTH; break; } else { response.method_ = METHOD_NOTAVAILABLE; } } if (response.method_ != METHOD_NOAUTH) { Serial.print("method not supported:"); Serial.println((int)response.method_); return false; } count = client->write((byte*)&response, sizeof(response)); if (count != sizeof(response)) { Serial.println("response send failure"); } return true; } EthernetClient* connect_to_host(uint32_t ip, uint16_t port) { Serial.print("connect to "); Serial.print(ip); Serial.print("@"); Serial.println(port); EthernetClient* host_conn = new EthernetClient(); int result = host_conn->connect(ip, port); if (host_conn->connected()) { Serial.println("connected"); return host_conn; } else { Serial.print("failed to connect:"); Serial.println(result); delete host_conn; } return NULL; } void do_proxy(EthernetClient* remote, EthernetClient* client) { //TODO: set a counter to break and let others connect while (remote->connected() && client->connected()) { // see if we have any requst from client int recv = client->read(socks_buffer, sizeof(socks_buffer)); if (recv > 0) { remote->write(socks_buffer, recv); Serial.print("recv from remote: "); Serial.println(recv); } // see if we have any response from remote recv = remote->read(socks_buffer, sizeof(socks_buffer)); if (recv > 0) { client->write(socks_buffer, recv); Serial.print("recv from client: "); Serial.println(recv); } } } bool handle_request(EthernetClient* client) { SOCKS5RequestHeader header; int count = -1; while (count < 0) { count = client->read((byte*)&header, sizeof(header)); } if (header.version_ != 5 || header.cmd_ != CMD_CONNECT || header.rsv_ != 0) { Serial.println("request header mismatch"); return false; } EthernetClient* client_sock = NULL; switch(header.atyp_) { case ATYP_IPV4: { SOCK5IP4RequestBody req; count = client->read((byte*)&req, sizeof(req)); if (count != sizeof(req)) { Serial.println("SOCK5IP4RequestBody recv size mismatch"); return false; } client_sock = connect_to_host(req.ip_dst_, ntohs(req.port_)); break; } case ATYP_DNAME: break; default: return false; } if (client_sock == NULL) return false; SOCKS5Response response; response.ip_src_ = 0; response.port_src_ = SERVER_PORT; client->write((byte*)&response, sizeof(response)); do_proxy(client_sock, client); if (client_sock != NULL) { client_sock->stop(); delete client_sock; Serial.println("stopped host connection"); } } ////////////////////////////////////////////////////////////////////////////// // Enter a MAC address and IP address for your controller below. // The IP address will be dependent on your local network. // gateway and subnet are optional: byte mac[] = { 0xDE, 0xAD, 0xBE, 0xEF, 0xAA, 0xED }; IPAddress ip(192, 168, 31, 207); IPAddress myDns(192, 168, 31, 1); IPAddress gateway(192, 168, 31, 1); IPAddress subnet(255, 255, 255, 0); // telnet defaults to port 23 EthernetServer server(SERVER_PORT); EthernetClient clients[MAX_CONN]; bool clients_handshaken[MAX_CONN]; void setup() { // You can use Ethernet.init(pin) to configure the CS pin Ethernet.init(10); // Most Arduino shields //Ethernet.init(5); // MKR ETH shield //Ethernet.init(0); // Teensy 2.0 //Ethernet.init(20); // Teensy++ 2.0 //Ethernet.init(15); // ESP8266 with Adafruit Featherwing Ethernet //Ethernet.init(33); // ESP32 with Adafruit Featherwing Ethernet // initialize the Ethernet device Ethernet.begin(mac, ip, myDns, gateway, subnet); // Open serial communications and wait for port to open: Serial.begin(9600); while (!Serial) { ; // wait for serial port to connect. Needed for native USB port only } // Check for Ethernet hardware present if (Ethernet.hardwareStatus() == EthernetNoHardware) { Serial.println("Ethernet shield was not found. Sorry, can't run without hardware. :("); while (true) { delay(1); // do nothing, no point running without Ethernet hardware } } if (Ethernet.linkStatus() == LinkOFF) { Serial.println("Ethernet cable is not connected."); } // start listening for clients server.begin(); Serial.print("Chat server address:"); Serial.println(Ethernet.localIP()); } void loop() { // check for any new client connecting, and say hello (before any incoming data) EthernetClient newClient = server.accept(); if (newClient) { for (byte i = 0; i < MAX_CONN; i++) { if (!clients[i]) { Serial.print("We have a new client #"); Serial.println(i); // Once we "accept", the client is no longer tracked by EthernetServer // so we must store it into our list of clients clients[i] = newClient; clients_handshaken[i] = false; break; } } } // check for incoming data from all clients for (byte i = 0; i < MAX_CONN; i++) { if (clients[i] && clients[i].available() > 0) { if (clients_handshaken[i] == true) { Serial.println(">>>"); handle_request(&clients[i]); }else if (handle_handshake(&clients[i])) { Serial.println("==="); clients_handshaken[i] = true; handle_request(&clients[i]); } } } // stop any clients which disconnect for (byte i = 0; i < MAX_CONN; i++) { if (clients[i] && !clients[i].connected()) { Serial.print("disconnect client #"); Serial.println(i); clients[i].stop(); clients_handshaken[i] = false; } } }
第一次是一家香港公司,跟现在公司的领域很相近。笔试是3个小时的,不过里面题目难度中性,都是改编题,印象中其中一题是霍夫曼编码之类的有点好玩。反正一个半小时做完了。
后来电话面试就坑B了,一接电话是浓厚的印度英语!结果就是对方的每一个问题我都要跟他确认一下,两边都不爽。电话面试持续了45分钟左右,上来先问项目经历,然后主要问C++11特性: move, forward, 智能指针,还问了些模板什么的。另外在扯CPU的cache warm。这个电面妥妥的跪了,一方面C++11的某些细节我没有掌握,但我觉得最大的问题就是语言不通,这个怪我听力不好,但是咖喱味的英语真乃从未有过的体验,下次不敢了。
======
第二次突然一猎头在领英上找到我说有杭州的机会,那就试试。结果是X方量化。
之前一次听同事说X方面试难,如何如何厉害,也想见识一下。这里客观陈述一下
- 在线笔试。题目是牛客网的通题,都是套路题,最后两道编程对于不常刷题的人来说时间有一点赶,不过难度就是LeetCode Easy的难度;
- 面试第一轮。问各种C++的问题,但是基本是STL容器内部运作的机制,并且当我讲到C++11特性的时候(比如move)对方并没有细问,故猜测該公司用C++11的地方可能略有局限。随后一道公司自己出的算法题,考数据结构设计的。在面试官给出某种场景的前提下,我给出了个性能更好的解决方案,不过面试官也换了场景让我的方案往他预想的地方靠,最终终于实现了一统~面试官对时间复杂度的计算有要求。
- 面试第二轮。也是各种C++问题开场,难度一般。遂给了一道算法题,当时懵了竟然想到用动态规划,但是后来经提示有O(N)方法于是用了贪心法,然后面试官又小改了一下测试我是不是真的理解了。另外就是讲到C++模板还有我的项目经历,我提到之前使用过CRTP做东西,于是让我写了下CRTP长什么样。
- 面试第三轮。一个中年大叔,一进门就接了一分钟电话,然后让我做自我介绍。当时心想肯定是个领导于是开始忽悠简历,然后做了个滑动窗口最大值的原题就结束了。
- 面试第四轮。后来了解到是CTO,反正被带去吃了个午饭瞎聊然后说问个小问题。蓄水池抽样,不过可惜我当时拉肚子加上对概率不敏感,瞎凑对了抽样概率但是一直卡壳没法证明它是对的,估计让大佬失望了哈哈。
- 然后是HR面,不细说了。
最终结局是Offer隔了两天收到了,但是我与猎头都不是很满意。个人觉得面试上没有安排系统设计的问题可能是对方的一个疏忽点,也可能觉得我就是个junior而已怕把我伤了,其实可以试探一下的。
目前的教训是面试之前不能乱吃东西,第三轮到第四轮的时候肠胃就开始闹腾。第二就是还是要熟悉一下基本的概率套路,自己在这方面是弱点。第三就是下次面试之前要打听一下薪资待遇,这次还特地周末看了看书,现在想想瞎紧张个啥….
面向对象软件设计的S.O.L.I.D原则
具体示例请看原文:S.O.L.I.D: The First 5 Principles of Object Oriented Design
S.O.L.I.D 代表着:
S – Single-responsiblity principle 单一责任原则
一个类应有且仅有一个理由去变更,即一个类只应用于一个工作。
O – Open-closed principle 开闭原则
对象或实体只应该开放扩展,而不该开放修改。
我的理解是应该避免越俎代庖的事情发生,不应该在调用某类实体的地方去关心某个对象该方法的具体实现。例如有两个Shape类的继承类Circle及Square,在对各自计算面积的时候,具体计算面积的方法不是调用者需要关心的,否则每增加一种继承类都要去修改调用方法。
L – Liskov substitution principle 李斯柯夫替代原则
令q(x)是关于类型T的对象x的可证明属性。那么对于T的子类型S的对象y,q(y)也应该是可证明的。
这个是官话,简单来说就是每个子类都应该可替代他们的父类,所谓“子承父业”。
I – Interface segregation principle 接口分离原则
永远不应该强迫用户实现它不使用的接口,或不应该强迫用户依赖于他们不使用的方法。
比如不应该让一个二维平面的类去实现一个计算体积的方法。
D – Dependency Inversion Principle 依赖倒置原则
实体必须依赖于抽象,而不是具象。高级别的模块不能依赖于低级别模块,而是需要依赖于某种抽象。
比如一个Gateway类需要通过某种网络IO接收数据,它应该依赖于一种IO接口的抽象而不是具体的某种IO(比如UDP IO),否则当你想换一种IO做同样的事情时你就会很头疼。
LeetCode 403. Frog Jump
A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.
If the frog’s last jump was k units, then its next jump must be either k – 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.
思路:这个题目可以看作是动态规划。青蛙的一个状态可以表示为{当前的k,当前的位置(可以用stone的索引表示)},最初的时候状态就是{ 1, 0 }。在某一个状态下,青蛙可以尝试向前移动{k-1, k, k+1}步,如果能成功跳到那就进入了下一个状态。要注意的是这种状态的遍历是有重复的,所以需要一个东西记录已经尝试过(当然是尝试失败的,不然直接return true)的状态们,不然很容易超时。
为了避免栈溢出,下文的解法直接用stack模拟函数的栈调用。
class Solution { public: bool canCross(vector<int>& stones) { if (stones.empty()) return false; else if (stones.size() == 1) return true; // state { k, index, has_traversed } stack<tuple<int, int, bool>> states; unordered_map<int, set<int>> visited; states.push({ 1, 0, false }); while (!states.empty()) { if (std::get<2>(states.top()) == true) { // pop state (like recursive function returning) states.pop(); continue; } int last_k = std::get<0>(states.top()); int last_pos_idx = std::get<1>(states.top()); if (visited[last_k].count(last_pos_idx) > 0) { // avoid duplicated state entry states.pop(); continue; } std::get<2>(states.top()) = true; visited[last_k].insert(last_pos_idx); if (last_pos_idx == stones.size() - 1) return true; for (int step = last_k - 1; step <= last_k + 1; ++step) { if (step == 0) continue; if (last_pos_idx == 0 && step != 1) continue; // can only move 1 step at the beginning int next_stone = stones[last_pos_idx] + step; for (int j = last_pos_idx + 1; j < stones.size(); ++j) { if (stones[j] > next_stone) break; if (stones[j] == next_stone) { states.push({ step, j , false}); //Push state of the next stone } } } } return false; } };
654. Maximum Binary Tree
Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
- The root is the maximum number in the array.
- The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
- The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
Construct the maximum tree by the given array and output the root node of this tree.
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* subMaxBinTree(vector<int>::iterator begin, vector<int>::iterator end) { if (begin == end) return nullptr; auto maxElemIt = std::max_element(begin, end); TreeNode* root = new TreeNode(*maxElemIt); root->left = subMaxBinTree(begin, maxElemIt); root->right = subMaxBinTree(maxElemIt+1, end); return root; } TreeNode* constructMaximumBinaryTree(vector<int>& nums) { if (nums.empty()) return nullptr; return subMaxBinTree(nums.begin(), nums.end()); } };
Sometimes we have two classes that need to call each other’s somewhat function, for example
template <typename A> struct B { A* p_a_ = nullptr; }; template <typename B> struct A { B* p_b_ = nullptr; };
but as you can see A depends on B’s type to initialize and vise versa. If we declare the types as above we’ll not get a chance to create any instance.
There are at least two ways to resolve the issue.
I.Template template
A quick introduction about template template can be found here.
Declare either of {A, B} with template of template which accepts the other’s template argument.
template <template<typename> typename A_t> struct B { using A = A_t<B>; A* p_a_ = nullptr; }; template <typename B> struct A { B* p_b_ = nullptr; }; //and declare like this using B_t = B<A>; B_t b_instance; A<B_t> A_instance;
II.Type traits
The other resolution is create a type trait struct which acts like a bridge that links the type of each other.
template <typename foobar_tratis> struct foobar_notifier { using inst_t = typename foobar_tratis::foobar_inst_t; inst_t* inst_ = nullptr; void foobar() { std::cout << "foobar_notifier" << std::endl; } }; template <typename foobar_tratis> struct foobar_inst { using notifier_t = typename foobar_tratis::foobar_notifier_t; notifier_t* notifier_ = nullptr; void foobar() { std::cout << "foobar_inst" << std::endl; } }; struct foobar_tratis { using foobar_notifier_t = foobar_notifier<md_inst_traits>; using foobar_inst_t = foobar_inst<md_inst_traits>; }; /// and declare like this foobar_inst<foobar_tratis> inst2; foobar_notifier<foobar_tratis> notifier2;
Here I gathered some of (what I thought are) best answers to LeetCode questions:
- https://leetcode.com/problems/wiggle-subsequence/discuss/84887/C++-0ms-O(N)-dynamic-programming-solution
- an O(n) solution
- https://leetcode.com/problems/trapping-rain-water/description/
- an O(n) solution of a similar (but harder) question, found in the book <算法竞赛入门经典(第二版) pp249例8-18
- basic idea is to find a maximal height which can reserve the water for each position i, if the max height equals to the unit then no rain can be collected at i
(vice versa, from right to left)
LeetCode 89. Gray Code
Divide and conquer!
Add a leading 0 or 1 bit to your existing results so here comes two sub-results: 0{xxxxx} and 1{xxxxx}. How to merge them? Just keep the first sub group and append the second group items reversely so that there is only a 1-bit difference between the end of group 0 and “start” of group 2.
class Solution { public: vector<int> grayCode(int n) { if (n == 0) return { 0 }; vector<int> results = { 0, 1 }; for (size_t i = 1; i < n; ++i) { for (int j = results.size() - 1; j >= 0; --j) { results.push_back(results[j] + (1 << i)); } } return results; } };
突然感觉自己已经不再年轻,很多东西都是依照习惯而来。对生活失去好奇心那才是最可怕的事情,千万不能沉浸在自己的习惯里。