By Long Luo

挖坑

网络抓包常用命令

详细解析和Demo版本：就是要你懂抓包–WireShark之命令行版tshark

```shell 用tcpdump抓取并保存包： sudo tcpdump -i eth0 port 3306 -w plantegg.cap

抓到的包存储在plantegg.cap中，可以用作wireshark、tshark详细分析 如果明确知道目的ip、端口等可以通过指定条件来明确只抓取某个连接的包

抓取详细SQL语句： sudo tshark -i eth0 -Y “mysql.command==3” -T fields -e mysql.query sudo tshark -i eth0 -R mysql.query -T fields -e mysql.query

sudo tshark -i any -f ‘port 8527’ -s 0 -l -w - |strings

#parse 8507/4444 as mysql protocol, default only parse 3306 as mysql. sudo tshark -i eth0 -d tcp.port==8507,mysql -T fields -e mysql.query ‘port 8507’ sudo tshark -i any -c 50 -d tcp.port==4444,mysql -Y ” ((tcp.port eq 4444 ) )” -o tcp.calculate_timestamps:true -T fields -e frame.number -e frame.time_epoch -e frame.time_delta_displayed -e ip.src -e tcp.srcport -e tcp.dstport -e ip.dst -e tcp.time_delta -e tcp.stream -e tcp.len -e mysql.query

sudo tshark -i eth0 -R “ip.addr==11.163.182.137” -d tcp.port==3306,mysql -T fields -e mysql.query ‘port 3306’ sudo tshark -i eth0 -R “tcp.srcport==62877” -d tcp.port==3001,mysql -T fields -e tcp.srcport -e mysql.query ‘port 3001’

如果MySQL开启了SSL，那么抓包后的内容tshark/wireshark分析不到MySQL的具体内容，可以强制关闭：connectionProperties里加上useSSL=false

查看SQL具体内容 sudo tshark -r gege_plantegg.cap -Y “mysql.query or ( tcp.stream==1)” -o tcp.calculate_timestamps:true -T fields -e frame.number -e frame.time_epoch -e frame.time_delta_displayed -e ip.src -e tcp.srcport -e tcp.dstport -e ip.dst -e tcp.time_delta -e frame.time_delta_displayed -e tcp.stream -e tcp.len -e mysql.query

按mysql查询分析响应时间 对于rt分析，要注意一个query多个response情况（response结果多，分包了），分析这种rt的时候只看query之后的第一个response，其它连续response需要忽略掉。

以上抓包结果文件可以用tshark进行详细分析

分析MySQL rt，倒数第四列基本就是rt tshark -r gege_plantegg.pcap -Y ” ((tcp.srcport eq 3306 ) and tcp.len>0 )” -o tcp.calculate_timestamps:true -T fields -e frame.number -e frame.time_epoch -e frame.time_delta_displayed -e ip.src -e tcp.srcport -e tcp.dstport -e ip.dst -e tcp.time_delta -e tcp.stream -e tcp.len -e tcp.analysis.ack_rtt

或者排序一下 tshark -r 213_php.cap -Y “mysql.query or ( tcp.srcport==3306)” -o tcp.calculate_timestamps:true -T fields -e frame.number -e frame.time_epoch -e frame.time_delta_displayed -e ip.src -e tcp.srcport -e tcp.dstport -e ip.dst -e tcp.time_delta -e tcp.stream -e tcp.len -e mysql.query |sort -nk9 -nk1

MySQL响应时间直方图【第八列的含义– Time since previous frame in this TCP stream: seconds】： tshark -r gege_plantegg.pcap -Y “mysql.query or (tcp.srcport3306 and tcp.len>60)” -o tcp.calculate_timestamps:true -T fields -e frame.number -e frame.time_epoch -e frame.time_delta_displayed -e ip.src -e tcp.srcport -e tcp.dstport -e ip.dst -e tcp.time_delta -e tcp.stream -e tcp.len | awk ’BEGIN {sum0=0;sum3=0;sum10=0;sum30=0;sum50=0;sum100=0;sum300=0;sum500=0;sum1000=0;sumo=0;count=0;sum=0} {rt=$8; if(rt>=0.000) sum=sum+rt; count=count+1; if(rt<=0.000) sum0=sum0+1; else if(rt<0.003) sum3=sum3+1 ; else if(rt<0.01) sum10=sum10+1; else if(rt<0.03) sum30=sum30+1; else if(rt<0.05) sum50=sum50+1; else if(rt < 0.1) sum100=sum100+1; else if(rt < 0.3) sum300=sum300+1; else if(rt < 0.5) sum500=sum500+1; else if(rt < 1) sum1000=sum1000+1; else sum=sum+1 ;} END{printf “————-3ms:http response分析响应时间 tshark -nr 213_php.cap -o tcp.calculate_timestamps:true -Y”http.request or http.response” -T fields -e frame.number -e frame.time_epoch -e frame.time_delta_displayed -e ip.src -e ip.dst -e tcp.stream -e http.request.full_uri -e http.response.code -e http.response.phrase | sort -nk6 -nk1

分析rtt、丢包、deplicate等等，可以得到整体网络状态 $ tshark -r retrans.cap -q -z io,stat,1,“AVG(tcp.analysis.ack_rtt)tcp.analysis.ack_rtt”,“COUNT(tcp.analysis.retransmission) tcp.analysis.retransmission”,“COUNT(tcp.analysis.fast_retransmission) tcp.analysis.fast_retransmission”,“COUNT(tcp.analysis.duplicate_ack) tcp.analysis.duplicate_ack”,“COUNT(tcp.analysis.lost_segment) tcp.analysis.lost_segment”,“MIN(tcp.window_size)tcp.window_size”

=================================================================================== | IO Statistics | | | | Duration: 89.892365 secs | | Interval: 2 secs | | | | Col 1: AVG(tcp.analysis.ack_rtt)tcp.analysis.ack_rtt | | 2: COUNT(tcp.analysis.retransmission) tcp.analysis.retransmission | | 3: COUNT(tcp.analysis.fast_retransmission) tcp.analysis.fast_retransmission | | 4: COUNT(tcp.analysis.duplicate_ack) tcp.analysis.duplicate_ack | | 5: COUNT(tcp.analysis.lost_segment) tcp.analysis.lost_segment | | 6: AVG(tcp.window_size)tcp.window_size | |———————————————————————————| | |1 |2 |3 |4 |5 |6 | | | Interval | AVG | COUNT | COUNT | COUNT | COUNT | AVG | | |————————————————————-| | | 0 <> 2 | 0.001152 | 0 | 0 | 0 | 0 | 4206 | | | 2 <> 4 | 0.002088 | 0 | 0 | 0 | 1 | 6931 | | | 4 <> 6 | 0.001512 | 0 | 0 | 0 | 0 | 7099 | | | 6 <> 8 | 0.002859 | 0 | 0 | 0 | 0 | 7171 | | | 8 <> 10 | 0.001716 | 0 | 0 | 0 | 0 | 6472 | | | 10 <> 12 | 0.000319 | 0 | 0 | 0 | 2 | 5575 | | | 12 <> 14 | 0.002030 | 0 | 0 | 0 | 0 | 6922 | | | 14 <> 16 | 0.003371 | 0 | 0 | 0 | 2 | 5884 | | | 16 <> 18 | 0.000138 | 0 | 0 | 0 | 1 | 3480 | | | 18 <> 20 | 0.000999 | 0 | 0 | 0 | 4 | 6665 | | | 20 <> 22 | 0.000682 | 0 | 0 | 41 | 2 | 5484 | | | 22 <> 24 | 0.002302 | 2 | 0 | 19 | 0 | 7127 | | | 24 <> 26 | 0.000156 | 1 | 0 | 22 | 0 | 3042 | | | 26 <> 28 | 0.000000 | 1 | 0 | 19 | 1 | 152 | | | 28 <> 30 | 0.001498 | 1 | 0 | 24 | 0 | 5615 | | | 30 <> 32 | 0.000235 | 0 | 0 | 44 | 0 | 1880 | | 1 =================================================================================== 2 | IO Statistics | 3 | | 4 | Duration: 89.892365 secs | 5 | Interval: 2 secs | 6 | | 7 | Col 1: AVG(tcp.analysis.ack_rtt)tcp.analysis.ack_rtt | 8 | 2: COUNT(tcp.analysis.retransmission) tcp.analysis.retransmission | 9 | 3: COUNT(tcp.analysis.fast_retransmission) tcp.analysis.fast_retransmission | 10 | 4: COUNT(tcp.analysis.duplicate_ack) tcp.analysis.duplicate_ack | 11 | 5: COUNT(tcp.analysis.lost_segment) tcp.analysis.lost_segment | 12 | 6: AVG(tcp.window_size)tcp.window_size | 13 |———————————————————————————| 14 | |1 |2 |3 |4 |5 |6 | | 15 | Interval | AVG | COUNT | COUNT | COUNT | COUNT | AVG | | 16 |————————————————————-| | 17 | 0 <> 2 | 0.001152 | 0 | 0 | 0 | 0 | 4206 | | 18 | 2 <> 4 | 0.002088 | 0 | 0 | 0 | 1 | 6931 | | 19 | 4 <> 6 | 0.001512 | 0 | 0 | 0 | 0 | 7099 | | 20 | 6 <> 8 | 0.002859 | 0 | 0 | 0 | 0 | 7171 | | 21 | 8 <> 10 | 0.001716 | 0 | 0 | 0 | 0 | 6472 | | 22 | 10 <> 12 | 0.000319 | 0 | 0 | 0 | 2 | 5575 | | 23 | 12 <> 14 | 0.002030 | 0 | 0 | 0 | 0 | 6922 | | 24 | 14 <> 16 | 0.003371 | 0 | 0 | 0 | 2 | 5884 | | 25 | 16 <> 18 | 0.000138 | 0 | 0 | 0 | 1 | 3480 | | 26 | 18 <> 20 | 0.000999 | 0 | 0 | 0 | 4 | 6665 | | 27 | 20 <> 22 | 0.000682 | 0 | 0 | 41 | 2 | 5484 | | 28 | 22 <> 24 | 0.002302 | 2 | 0 | 19 | 0 | 7127 | | 29 | 24 <> 26 | 0.000156 | 1 | 0 | 22 | 0 | 3042 | | 30 | 26 <> 28 | 0.000000 | 1 | 0 | 19 | 1 | 152 | | 31 | 28 <> 30 | 0.001498 | 1 | 0 | 24 | 0 | 5615 | | 32 | 30 <> 32 | 0.000235 | 0 | 0 | 44 | 0 | 1880 | |

#tshark tshark -r ./mysql-compress.cap -o tcp.calculate_timestamps:true -T fields -e mysql.caps.cp -e frame.number -e frame.time_epoch -e frame.time_delta_displayed -e ip.src -e tcp.srcport -e tcp.dstport -e ip.dst -e tcp.time_delta -e frame.time_delta_displayed -e tcp.stream -e tcp.len -e mysql.query

#用tcpdump抓取并保存包： sudo tcpdump -i eth0 port 3306 -w plantegg.cap

#每隔3秒钟生成一个新文件，总共生成5个文件后（15秒后）终止抓包，然后包名也按时间规范好了 sudo tcpdump -t -s 0 tcp port 3306 -w ‘dump_%Y-%m-%d_%H:%M:%S.pcap’ -G 3 -W 5 -Z root

#每隔30分钟生成一个包并压缩 nohup sudo tcpdump -i eth0 -t -s 0 tcp and port 3306 -w ‘dump_%Y-%m-%d_%H:%M:%S.pcap’ -G 1800 -W 48 -Z root -z gzip &

#file size 1000M nohup sudo tcpdump -i eth0 -t -s 0 tcp and port 3306 -w ‘dump_’ -C 1000 -W 300 -Z root -z gzip &

#port range sudo tcpdump -i enp44s0f0 -t -s 0 portrange 3000-3100 -w ‘dump_%Y-%m-%d_%H:%M:%S.pcap’ -G 60 -W 100 -Z root

#subnet sudo tcpdump -i enp44s0f0 -t -s 0 net 192.168.0.1/28 -w ‘dump_%Y-%m-%d_%H:%M:%S.pcap’ -G 60 -W 100 -Z root

#抓取详细SQL语句, 快速确认client发过来的具体SQL内容： sudo tshark -i any -f ‘port 8527’ -s 0 -l -w - |strings sudo tshark -i eth0 -d tcp.port==3306,mysql -T fields -e mysql.query ‘port 3306’ sudo tshark -i eth0 -R “ip.addr==11.163.182.137” -d tcp.port==3306,mysql -T fields -e mysql.query ‘port 3306’ sudo tshark -i eth0 -R “tcp.srcport==62877” -d tcp.port==3001,mysql -T fields -e tcp.srcport -e mysql.query ‘port 3001’

#query time sudo tshark -i eth0 -Y ” ((tcp.port eq 3306 ) and tcp.len>0 )” -o tcp.calculate_timestamps:true -T fields -e frame.number -e frame.time_epoch -e frame.time_delta_displayed -e ip.src -e tcp.srcport -e tcp.dstport -e ip.dst -e tcp.time_delta -e tcp.stream -e tcp.len -e mysql.query

#如果MySQL开启了SSL，那么抓包后的内容tshark/wireshark分析不到MySQL的具体内容，可以强制关闭：connectionProperties里加上useSSL=false

tshark -r ./manager.cap -o tcp.calculate_timestamps:true -Y ” tcp.analysis.retransmission ” -T fields -e tcp.stream -e frame.number -e frame.time -e ip.src -e tcp.srcport -e tcp.dstport -e ip.dst | sort

#MySQL响应时间直方图【第八列的含义– Time since previous frame in this TCP stream: seconds】： tshark -r gege_plantegg.pcap -Y “mysql.query or (tcp.srcport3306 and tcp.len>60)” -o tcp.calculate_timestamps:true -T fields -e frame.number -e frame.time_epoch -e frame.time_delta_displayed -e ip.src -e tcp.srcport -e tcp.dstport -e ip.dst -e tcp.time_delta -e tcp.stream -e tcp.len | awk ‘BEGIN {sum0=0;sum3=0;sum10=0;sum30=0;sum50=0;sum100=0;sum300=0;sum500=0;sum1000=0;sumo=0;count=0;sum=0} {rt=$8; if(rt>=0.000) sum=sum+rt; count=count+1; if(rt<=0.000) sum0=sum0+1; else if(rt<0.003) sum3=sum3+1 ; else if(rt<0.01) sum10=sum10+1; else if(rt<0.03) sum30=sum30+1; else if(rt<0.05) sum50=sum50+1; else if(rt < 0.1) sum100=sum100+1; else if(rt < 0.3) sum300=sum300+1; else if(rt < 0.5) sum500=sum500+1; else if(rt < 1) sum1000=sum1000+1; else sum=sum+1 ;} END{printf “————-3ms:%s 10ms:%s 30ms:%s 50ms:%s 100ms:%s 300ms:%s 500ms:%s 1000ms:%s >1s:%s————-: %.6f ” , sum3,sum10,sum30,sum50,sum100,sum300,sum500,sum1000,sumo,sum/count;}’

#分析MySQL rt，倒数第四列基本就是rt tshark -r gege_plantegg.pcap -Y ” ((tcp.srcport eq 3306 ) and tcp.len>0 )” -o tcp.calculate_timestamps:true -T fields -e frame.number -e frame.time_epoch -e frame.time_delta_displayed -e ip.src -e tcp.srcport -e tcp.dstport -e ip.dst -e tcp.time_delta -e tcp.stream -e tcp.len -e tcp.analysis.ack_rtt

#或者排序一下 tshark -r 213_php.cap -Y “mysql.query or ( tcp.srcport==3306)” -o tcp.calculate_timestamps:true -T fields -e frame.number -e frame.time_epoch -e frame.time_delta_displayed -e ip.src -e tcp.srcport -e tcp.dstport -e ip.dst -e tcp.time_delta -e tcp.stream -e tcp.len -e mysql.query |sort -nk9 -nk1

#将 tls key和抓包文件合并 editcap –inject-secrets tls,key.log in.pcap out.pcap #把包长截掉，只保留前面54，可以脱敏包内容 editcap -s 54 old.pcap new.pcap

参考文献

1. The Most Useful Linux Commands For Network And Systems Administrators
2. 7 Linux networking commands that every sysadmin should know
3. Mastering Linux Networking Commands: A Comprehensive Guide
4. Linux Networking Commands with Examples

By Long Luo

最近在 YouTube 上看了 Freya Holmér 的 贝塞尔曲线之美 的视频，这个视频做的非常好，通俗易懂地解释了贝塞尔曲线的实现原理，通过结合代码，大致了解了 Bezier Curve<sup>1</sup> 的数学原理。

之前用过 TI 的一个开发板，里面有个屏保的程序，可以在开发板的屏幕上 屏保 ，用的是 Bresneham<sup>2</sup> 算法，源码如下 。Bresneham 算法先挖个坑，后续会填上，今天这篇文章主要还是分析贝塞尔曲线(Bezier Curve)。

贝塞尔曲线是什么？

贝塞尔曲线是由法国工程师 Pierre Bézier<sup>3</sup> 在 1962 年提出的数学概念，它以其优雅的曲线特性和广泛的应用领域而闻名。

我写了一个贝塞尔(Bezier Curve) 曲线的在线交互式动画，传送门如下：

http://www.longluo.me/projects/bezier/

贝塞尔曲线的数学原理

这一章节待完善！！！

贝塞尔曲线通过控制点来定义曲线的形状，这些控制点决定了曲线在起始点和结束点之间的路径。通过调整控制点的位置，可以改变曲线的形状、弯曲度和方向。贝塞尔曲线的绘制基于插值的概念，它通过在控制点之间进行插值计算，得到平滑的曲线。

\(P_1(x_1, y_1)\) 和 \(P_2(x_2, y_2)\) ，

\[ \begin{cases} x = x_1 + t (x_2 - x_1) \\ y = y_1 + t (y_2 - y_1) \end{cases} \]

贝塞尔曲线的数学表达方式是通过多项式来定义的。在一维空间中，\(n\) 次贝塞尔曲线的公式为：

\[ B(t) = P_0 + (P_1 - P_0)t= (1-t)P_0 + tP_1, t\in [0,1] \]

\[ B(t) = \sum_{i=0}^{n} \binom{n}{i}P_i(1 - t)^{n-i}t^i = \binom{n}{0}P_0(1-t)^{n}t^0 + \binom{n}{1}P_1(1-t)^{n-1}t^1 + \cdots + \binom{n}{n-1}P_{n-1}(1-t)^{n-1}t^{n-1} + \binom{n}{n}P_{n}(1-t)^{n}t^{n}, t\in[0,1] \]

一般地， n 个控制点的贝塞尔曲线的递归版本为：

\[ P_0^{n} = (1 - t)P_0^{n-1} + tP_1^{n-1}, t\in [0,1] \]

贝塞尔曲线的应用场合

计算机图形学：贝塞尔曲线被广泛应用于计算机图形学中的曲线绘制和造型。它可以用来绘制平滑的曲线、实现曲线的动画效果，以及创建复杂的几何形状。

平面设计和艺术：贝塞尔曲线在平面设计和艺术创作中也有广泛应用。设计师可以利用贝塞尔曲线的灵活性和精确性，绘制出符合设计要求的曲线和形状。

工程和建筑设计：贝塞尔曲线在工程和建筑设计中用于绘制道路、河流、管道等具有曲线特征的结构。它可以帮助工程师和建筑师准确地描述和模拟复杂的曲线路径。

贝塞尔曲线的缺点

尽管贝塞尔曲线在许多场合下都有广泛应用，但也存在一些不适用的情况。以下是一些例子：

1. 高度精确的曲线：贝塞尔曲线是由有限个控制点所定义的，当需要绘制极其精确的曲线时，可能无法满足需求；
2. 曲率变化较大的曲线：贝塞尔曲线的控制点数量决定了曲线的平滑程度。在曲率变化较大的情况下，可能需要增加更多的控制点来准确描述曲线的形状；
3. 特殊曲线类型：某些特殊曲线类型，如圆或椭圆等，可能有更适合的数学表示方法，而不是使用贝塞尔曲线。

总结

贝塞尔曲线能够帮助我们创建平滑、灵活的曲线，适用于计算机图形学、平面设计、工程和建筑设计等领域。

参考文献

Bezier https://h14s.p5r.org/2013/01/bezier.html

By Long Luo

This article is the solution Data Structures: Thought Process from HashMap to HashMap + Array of Problem 380. Insert Delete GetRandom O(1).

Intuition

It’s easy to think of using a Hash Table to achieve \(O(1)\) time complexity for \(\texttt{insert}\) and \(\texttt{remove}\) operations. However, we need \(O(1)\) time complexity to complete the \(\texttt{getRandom}\) operation.

The Array structure can complete the operation of obtaining random elements in \(O(1)\) time complexity, but it can’t completed the \(\texttt{insert}\) and \(\texttt{remove}\) operations in \(O(1)\) time complexity.

So How?

Aha!!!

By Long Luo

今天 LeetCode 第320场周赛 中第一题是 2475. 数组中不等三元组的数目 ，本文是该题的题解，同时发表在 这里 。

参考了 @灵茶山艾府 的题解 非暴力做法 ，实际上我们可以不用先排序，而是先用 \(\texttt{HashMap}\) 统计数组 \(\textit{num}\) 元素频率。

之后遍历 \(\texttt{HashMap}\) ，结果为：

\[ \sum_{j = 0}^{n} (map[0] + \cdots + map[i]) \times map[j] \times (map[k] + \cdots + map[n - 1]) \]

，其中 \(n\) 为 \(\textit{nums}\) 的长度。

证明如下：

对于数组中的元素 \(x\) ，可以得到：

• 小于 \(x\) 的数有 \(a\) 个；
• 等于 \(x\) 的数有 \(b\) 个；
• 大于 \(x\) 的数有 \(c\) 个。

那么 \(x\) 对最终答案的贡献是 \(abc\) 。

即使 \(x\) 是三元组中的最大或最小值，由于 \(i, j, k\) 的对称性，很明显其实和 \(x\) 是中间值都是同一个答案。

证毕！

By Long Luo

This article is the solution It is Literally a Graph: DFS and Union Find of Problem 947. Most Stones Removed with Same Row or Column .

Intuition

We can find that this is a graph theory problem with analysis.

Imagine the stone on the 2D coordinate plane as the vertex of the graph, If the x-coord or the y-coord of two stones are the same, there is an edge between them.

This can be show as follows:

According to the rule that stones can be removed, we should remove those points that are in the same row or column with other points as late as possible. That is, the more points in the same row or column with point A, the later point A should be removed. In this way, we can delete as many points as possible through point A.

It can be found that all vertices in a connected graph can be deleted to only one vertex.

Since these vertices are in a connected graph, all vertices of the connected graph can be traversed by DFS or BFS.

Therefore: the maximum number of stones that can be removed = the number of all stones - the number of connected components.