豌豆

SM4分组密码算法，原名SMS4，国家密码管理局于2012年3月21日发布,相关标准为“GM/T 0002-2012《SM4分组密码算法》（原SMS4分组密码算法）”。它是一种分组对称加密算法，分组长度和密钥长度均为 128bit ,加密算法与密码扩展算法均采用 32 轮非线性迭代结构， Sbox 为固定的 8bit 输入 8bit 输出的置换。 数据加/解密的算法结构相同，只是轮密钥的使用顺序相反，解密轮密钥是加密轮密钥的逆序。

SBox

在密码学中，Sbox（Substitution-box，替换盒）是对称密钥加密算法执行替换计算的基本结构。SBox接受一个特定位数的输入，通过查表将其转换为特定位数的输出。SM4 给定的 SBox 如下：

例如，对于输入 EF， 通过查表输出为 第 E 行，第 F 列，84

继续阅读

SOCKS 是一种网络传输协议，主要用于客户端与外网服务器之间通讯的中间代理传递 。SOCKS是 "SOCKetS" 的缩写。目前其最新的版本是5，相比于前一个版本，其新增了 IPv6, UDP 及 验证。
根据OSI模型，SOCKS是会话层的协议，位于表示层与传输层之间。

协议详情

一个 socks5 连接的过程主要有两部分，协商与请求,如果协商后需要验证，则还包含验证的部分。

(1) 认证方法协商

客户端向服务端发出连接认证方法协商请求

• VER 是 SOCKS 的版本，此处是 0x05
• NMETHODS 是 METHODS 部分数据的长度，即客户端支持的认证方式的 count
• METHODS 是客户端支持的认证方式列表，每个方法占一个字节
  • 0x00 不需要认证
  • 0x01 GSSAPI
  • 0x02 用户名密码认证
  • 0x03 - 0x7F 由 IANA分配(保留)
  • 0x80 - 0xFE 私人方法(保留)
  • 0xFF 无可接受的方法

服务器回应协商，从客户端提供的方法中选择一个并通知客户端：

• VER 是SOCKS的版本号，此处应为 0x05
• METHOD 是服务端选中的方法。如果不支持客户端提供的所有方法，则返回 0xFF

(2) 认证

继续阅读

当前的一个项目想使用 Electron 做个 Demo 来进行测试，在调用 C++ 时遇到了一些坑，踩坑的过程中发现网上踩这些坑的人还不少，踩完坑在这里顺手记录一下。

x86 OR x64

lib 的位数与 node.js 的位数必须一致，而和操作系统的位数无关，当然，32位的操作系统是无法运行64位的应用程序 的。

ps: 如何查文件是32位还是64位

• 记得自己下载安装的是什么版本(废话)
• Windows 下：可以使用 vs 自带的 SDK Tools， 执行命令：

继续阅读

一 链表倒置

链表倒置是链表的基本操作之一。

题目 一 Reverse Linked List

LeetCode 206 Reverse Linked List

Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?

题目提示可以用 迭代 或 递归 两种方法来解。

• 迭代方法
  如图： 两个指针 head p 分别指向 表头，欲倒置的元素. 为了使下一个欲倒置的元素不会 野 掉， 还需要一个指针 tmp 来保护它
  1. p->next 指向 head
  2. head->next 指向 tmp
  3. head = p, p = tmp, tmp 保护下一个欲倒置的元素

  代码：

  class Solution { public: ListNode* reverseList(ListNode* head) { if(!head) return NULL; if(!head->next) return head; ListNode *p,*tmp; p = head->next; tmp = p->next; head->next = NULL; while(p1){ p->next = head; head = p; p = tmp; if(tmp) tmp = tmp->next; } return head; } };

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  class Solution { public:     ListNode* reverseList(ListNode* head) {         if(!head) return NULL;         if(!head->next) return head;           ListNode *p,*tmp;         p = head->next;         tmp = p->next;         head->next = NULL;           while(p1){             p->next = head;             head = p;             p = tmp;             if(tmp)                 tmp = tmp->next;         }           return head;     } };

• 递归方法
  思想和上面一样，只不过代码的写法不同：
  class Solution { public: ListNode* reverseList(ListNode* head) { if(!head || !head->next){ return head; } ListNode* p = reverseList(head->next); head->next->next = head; head->next = NULL; return p; } };

  1 2 3 4 5 6 7 8 9 10 11 12 13

  class Solution { public:     ListNode* reverseList(ListNode* head) {         if(!head || !head->next){             return head;         }           ListNode* p = reverseList(head->next);         head->next->next = head;         head->next = NULL;         return p;     } };

  

  递归的方法代码简洁高效，在很多链表题目中都会用到它，所以特别重要。例如下一题

继续阅读

例题 一 : Triangle

LeetCode 120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

分析：

设三角形共有 $N$ 行， $r$ 为三角形的行， $c$ 为三角形的列。从点 $P(r,c)$ 出发，每向下走一步有两个点$P_1(r+1,c), P_2(r+1, c+1)$ 可以选择 ,如果每次都选值小的点$min(P1, P2)$，则最后得到的点的值之和即是最优解。令 $M(r,c)$ 为从 $P(r,c)$ 开始到下面的列的各条路径中，最佳路径的数字之和。

解法一：

这是一个典型的递归问题。

$$M(r,c) = \begin{cases}  P(r,c), & \text{if r = N }\\  min(M(r+1,c), M(r+1,c+1)) + P(r,c),& \text{others}\\ \end{cases}$$

由此写出代码：

代码没有问题，在 "Run Code" 时可以得出正确的结果。但是 "Submit" 却会给出 "Time Limit Exceeded",超时！

如果我们推算这个解法的时间复杂度的话，可以得到 $O(2^n)$ .这不超时就有鬼了。我们需要改进这个算法。

继续阅读

提示：本文中的 Demo 已 push 到 github，可忽略本文直接到 我的github 中查看代码。

Qt 提供了 QuickControl TreeView 。但是比较奇葩的是该控件不能直接使用，而需要用户自己扩展实现。
官方给出了一个示例如下：

它声明了一个 TreeView控件，该控件有 2 列，分别为 Name 和 Permissions,还有一个名为 fileSystemModel 的 model 。对用户来说，这里的 model 是一个关键性的对象，它需要用户使用 C++ 实现 ，并注册到 qml 中供 TreeView 使用。按官方的说法， model 是一个 为 tree view 提供数据的属性，它包含了 tree view 将要展示的数据。
用户的 model 必须继承于 QAbstractItemModel 类。
该类是一个抽象类，在运行中，treeview 从该类中获取用户数据，再在UI上展示。该类有如下纯虚函数，必须在子类中实现：

继续阅读

为满足需求：

项目编译前需要预处理一些自定义命令，如生成代码文件，拷贝成果文件等。

解决该问题有两种方案：

add_custom_command prebuild

vcxproj 可以自定义生成事件，如：

继续阅读

关于 C++ 多线程编程一的些基本知识可以参考本博客的《C++11/14 新特性(多线程)》 ，《Unix线程基础》。本章不是多线程编程教程，而是个人经验的一些总结。这些经验有一些可能是不正确的，希望在今后的编程中实践、改进。

线程同步的四项基本原则：

1. 最低限度地共享对象。对象尽量不要暴露给别的线程，如果需要暴露，优先考虑 immutable对象。否则尽量使用同步措施来充分地保护它
2. 尽量使用高级地并发编程构件，如 任务队列、生产者消费者模式等
3. 只用非递归的互斥器和条件变量，慎用读写锁，尽量少用信号量
4. 除了使用 atomic 整数外，不要自己编写 lock-free 代码，也不要用"内核级"同步原语

互斥器 Mutex

mutex 是最常用的同步原语，它保护一个临界区，任何时候最多只能有一个线程能够访问 mutex 保护的域。使用 mutex 主要是为了保护共享数据。一般原则有：

• 使用 RAII手法封装 mutex 的创建、销毁、加锁、解锁操作，充分保证锁的有效期等于其作用域，而不会因为中途返回或异常而忘记解锁。这类似于 Java 的synchronized 或 C# 的 using 语句。
• 使用非递归的 mutex
• 尽量不要人为地调用 lock() 和 unlock()函数，将这些操作交给栈上的 guard 对象，利用其构造与析构函数。
• 不要跨线程地加解锁，避免在不同的函数中分别加锁\解锁，避免在不同的语句分支中加锁\解锁
• 每当构造 guard 对象时，需要考虑栈上已有的锁，防止因加锁顺序不同而导致死锁
• 避免跨进程的 mutex, 进程间通讯尽量使用 TCP sockets

只使用非递归地 mutex

继续阅读