Category: 木有技术

Categories
木有技术

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;
    }
  }
}

 

Categories
木有技术

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;
    }
};

 

Categories
木有技术

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;
    }
};

 

Categories
木有技术

LeetCode 402. Remove K Digits

https://leetcode.com/problems/remove-k-digits/description/
如果直接用DFS做的话轻轻松松就会stack overflow。
这道题可以用贪心法，题目换个思路说就是尽可能保证得到的数字是递增的。在拿到一个新数字时，尽可能(只要还能删)把该数字之前的比它大的数字移掉。
贪心法之所以能用是因为我们去尽量保证了a1<a2< …< x< y，如果这些个数字里要选一个删掉的话，肯定是删掉y带来的结果最好。

class Solution {
public:
	string removeKdigits(string num, int k) {
		const int digits = num.size() - k;
        char* stack = new char[num.size()]; // mem leak but I DONT CARE!
        int top = 0;
        for (int i = 0; i < num.size(); ++i)
        {
            char c = num[i];
            while (top > 0 && stack[top-1] > c && k > 0)
            {
                top--;
                k--;
            }
            stack[top++] = c;
        }
        int idx = 0;
        while (idx < digits && stack[idx] == '0')
            idx++;
        return idx == digits ? "0" : string(stack + idx, digits - idx);
	}
};

 

Categories
木有技术

LeetCode 269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
Example 1:

Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
Output:"wertf"

Example 2:

[
  "z",
  "x"
]
>Output: "zx"

Example 3:

[
  "z",
  "x",
  "z"
]
Output:""

Note:

  1. You may assume all letters are in lowercase.
  2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
  3. If the order is invalid, return an empty string.
  4. There may be multiple valid order of letters, return any one of them is fine.

 

Solution:

The solution is to build a directed map and find the topological ordering of the characters. Once the map is built, we can always find the “terminal” character which has no succeeding, i.e. the out-degree of that node would be zero. The we remove the character (the node and its edges) from the map and try to find the next such character, so on so forth.

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

For example,  the map built will be:

t: {f}
w: {e}
r: {t}
e: {r}
f: {}
class Solution {
private:
    map<char, set<char>> ch_map;
    void build(const string& w1, const string& w2)
    {
        const int len = std::min(w1.size(), w2.size());
        int i = 0;
        for (i = 0; i < len; ++i)
        {
            if (ch_map.count(w1[i]) == 0)
                ch_map[w1[i]] = set<char>();
            if (ch_map.count(w2[i]) == 0)
                ch_map[w2[i]] = set<char>();
            if (w1[i] != w2[i])
            {
                ch_map[w1[i]].insert(w2[i]);
                break;
            }
        }
        for (; i < w1.size() || i < w2.size(); ++i)
        {
            if (i < w1.size() && ch_map.count(w1[i]) == 0)
                ch_map[w1[i]] = set<char>();
            if (i < w2.size() && ch_map.count(w2[i]) == 0)
                ch_map[w2[i]] = set<char>();
        }
    }
public:
    string alienOrder(vector<string>& words) {
        if (words.empty()) return string();
        if (words.size() == 1) return words[0];
        for (int i = 0; i < words.size() - 1; ++i)
        {
            build(words[i], words[i+1]);
        }
        string result;
        result.reserve(26);
        while (!ch_map.empty())
        {
            bool found = false;
            for (auto it : ch_map)
            {
                if (it.second.empty())
                {
                    found = true;
                    result = it.first + result;
                    break;
                }
            }
            ch_map.erase(result[0]);
            if (!found) return string();  //not found
            for (auto& it : ch_map)
            {
                it.second.erase(result[0]);
            }
        }
        return result;
    }
};

 
 

Categories
木有技术

LeetCode 611. Valid Triangle Number

https://leetcode.com/problems/valid-triangle-number/description/
有点类似3Sum的题目。形成三角形的充要条件是最小两边之和大于第三边。可以先给数组排序，然后确定一个最大边，然后在它左边找另外两边。
时间复杂度是O(n*log(n) + n^2) = O(n^2)

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int count = 0;
        for (int i = nums.size() - 1; i >= 0; --i)
        {
            // two sum (x + y) > nums[i]
            int j = 0;
            int k = i - 1;
            while (j < k)
            {
                if (nums[j] + nums[k] <= nums[i])
                {
                    j++;
                    continue;
                }
                count += (k - j);
                k--;
            }
        }
        return count;
    }
};

 
 

Categories
木有技术

LeetCode 523. Continuous Subarray Sum

https://leetcode.com/problems/continuous-subarray-sum/description/
这道题跟https://leetcode.com/problems/subarray-sum-equals-k/description/ 其实是很像的，但本题的特点就是corner case非常多…

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if (k < 0)
            k = -1 * k;
        else if (k == 0)
        {
            // check if there's continuous zeroes
            bool has_zero = false;
            for (int num : nums)
            {
                if (num == 0)
                {
                    if (has_zero == true)
                        return true;
                    has_zero = true;
                }
                else
                    has_zero = false;
            }
            return false;
        }
        if (k == 1 && nums.size() > 1)  // tricky but...
            return true;
        int sum = 0;
        unordered_set<int> sum_records;
        vector<int> targets = {k};
        int last_num = INT32_MAX;
        sum_records.insert(0);
        for (int num : nums)
        {
            sum += num;
            sum_records.insert(sum);
            if (last_num == 0 && num == 0)
                return true;    // n = 0
            while (targets.back() + k <= sum)
                targets.push_back(targets.back() + k);  // prvents calculating dup multiplies
            for (int target : targets)
            {
                if (num != target && sum_records.count(sum - target) > 0)
                    return true;
            }
            last_num = num;
        }
        return false;
    }
};

 

Categories
木有技术

LeetCode 23. Merge k Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/description/
Use max heap, the time complexity is O( log(k) * N )

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())
            return nullptr;
        auto comparor = [](ListNode* lhs, ListNode* rhs) {
            return lhs->val > rhs->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(comparor)> pri_queue(comparor);
        // perpare queue with K items
        for(auto& list : lists)
        {
            if (list != nullptr)
                pri_queue.push(list);
        }
        ListNode* head = new ListNode(-1);
        ListNode* prev = head;
        ListNode* current = nullptr;
        while (!pri_queue.empty())
        {
            current = pri_queue.top();
            prev->next = current;
            ListNode* next = current->next;
            pri_queue.pop();
            if (next != nullptr)
                pri_queue.push(next);
            prev = current;
        }
        return head->next;
    }
};

 

Categories
木有技术

LeetCode 222. Count Complete Tree Nodes

https://leetcode.com/problems/count-complete-tree-nodes/description/
简单的二分法分治，探测（子）树的左右侧是否相等即可。
（下面代码没实现）想要更快的话，其实自从第一次算出左侧的深度后，后面的左测深度直接可以通过减法求出，不用再去探测一次了。

/**
 * 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:
    int countLevel(TreeNode* root, bool to_left) {
        int count = 0;
        while (root != nullptr)
        {
            count++;
            root = to_left ? root->left : root->right;
        }
        return count;
    }
    int countNodes(TreeNode* root) {
        if (root == nullptr)
            return 0;
        int lvl_left = countLevel(root, true);
        int lvl_right = countLevel(root, false);
        if (lvl_left == lvl_right)
        {
            // finally
            return (1 << lvl_left) - 1; // 2^n - 1
        }
        else
        {
            return 1 + countNodes(root->left) + countNodes(root->right);
        }
    }
};

 

Categories
木有技术

Linux Performance Observability Tools


Source(Crash Dump Analysis): http://d3s.mff.cuni.cz/teaching/crash_dump_analysis/slides/08-linux.pdf