Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 6k 阅读时长 ≈ 5 分钟

By Long Luo

Startup

1
2
3
4
5
% gdb -help         	print startup help, show switches
*% gdb object      	normal debug 
*% gdb object core 	core debug (must specify core file)
%% gdb object pid  	attach to running process
% gdb        		use file command to load object

Help

1
2
3
4
5
6
7
*(gdb) help        	list command classes
(gdb) help running      list commands in one command class
(gdb) help run        	bottom-level help for a command "run" 
(gdb) help info         list info commands (running program state)
(gdb) help info line    help for a particular info command
(gdb) help show         list show commands (gdb state)
(gdb) help show commands        specific help for a show comma

Breakpoints

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
*(gdb) break main       set a breakpoint on a function
*(gdb) break 101        set a breakpoint on a line number
*(gdb) break basic.c:101        set breakpoint at file and line (or function)
*(gdb) info breakpoints        show breakpoints
*(gdb) delete 1         delete a breakpoint by number
(gdb) delete        	delete all breakpoints (prompted)
(gdb) clear             delete breakpoints at current line
(gdb) clear function    delete breakpoints at function
(gdb) clear line        delete breakpoints at line
(gdb) disable 2         turn a breakpoint off, but don't remove it
(gdb) enable 2          turn disabled breakpoint back on
(gdb) tbreak function|line        set a temporary breakpoint
(gdb) commands break-no ... end   set gdb commands with breakpoint
(gdb) ignore break-no count       ignore bpt N-1 times before activation
(gdb) condition break-no expression         break only if condition is true
(gdb) condition 2 i == 20         example: break on breakpoint 2 if i equals 20
(gdb) watch expression        set software watchpoint on variable
(gdb) info watchpoints        show current watchpoints

Running the program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
*(gdb) run        	run the program with current arguments
*(gdb) run args redirection        run with args and redirection
(gdb) set args args...        set arguments for run 
(gdb) show args        show current arguments to run
*(gdb) cont            continue the program
*(gdb) step            single step the program; step into functions
(gdb) step count       singlestep \fIcount\fR times
*(gdb) next            step but step over functions 
(gdb) next count       next \fIcount\fR times
*(gdb) CTRL-C          actually SIGINT, stop execution of current program 
*(gdb) attach process-id        attach to running program
*(gdb) detach        detach from running program
*(gdb) finish        finish current function's execution
(gdb) kill           kill current executing program

Stack backtrace

1
2
3
4
5
6
*(gdb) bt        	print stack backtrace
(gdb) frame        	show current execution position
(gdb) up        	move up stack trace  (towards main)
(gdb) down        	move down stack trace (away from main)
*(gdb) info locals      print automatic variables in frame
(gdb) info args         print function parameters

Browsing source

1
2
3
4
5
6
7
8
9
10
11
12
13
*(gdb) list 101        	list 10 lines around line 101
*(gdb) list 1,10        list lines 1 to 10
*(gdb) list main  	list lines around function 
*(gdb) list basic.c:main        list from another file basic.c
*(gdb) list -        	list previous 10 lines
(gdb) list *0x22e4      list source at address
(gdb) cd dir        	change current directory to \fIdir\fR
(gdb) pwd          	print working directory
(gdb) search regexpr    forward current for regular expression
(gdb) reverse-search regexpr        backward search for regular expression
(gdb) dir dirname       add directory to source path
(gdb) dir        	reset source path to nothing
(gdb) show directories        show source path

Browsing Data

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
*(gdb) print expression        print expression, added to value history
*(gdb) print/x expressionR        print in hex
(gdb) print array[i]@count        artificial array - print array range
(gdb) print $        	print last value
(gdb) print *$->next    print thru list
(gdb) print $1        	print value 1 from value history
(gdb) print ::gx        force scope to be global
(gdb) print 'basic.c'::gx        global scope in named file (>=4.6)
(gdb) print/x &main     print address of function
(gdb) x/countFormatSize address        low-level examine command
(gdb) x/x &gx        	print gx in hex
(gdb) x/4wx &main       print 4 longs at start of \fImain\fR in hex
(gdb) x/gf &gd1         print double
(gdb) help x        	show formats for x
*(gdb) info locals      print local automatics only
(gdb) info functions regexp         print function names
(gdb) info variables  regexp        print global variable names
*(gdb) ptype name        print type definition
(gdb) whatis expression       print type of expression
*(gdb) set variable = expression        assign value
(gdb) display expression        display expression result at stop
(gdb) undisplay        delete displays
(gdb) info display     show displays
(gdb) show values      print value history (>= gdb 4.0)
(gdb) info history     print value history (gdb 3.5)

Object File manipulation

1
2
3
4
5
(gdb) file object      		load new file for debug (sym+exec)
(gdb) file             		discard sym+exec file info
(gdb) symbol-file object        load only symbol table
(gdb) exec-file object 		specify object to run (not sym-file)
(gdb) core-file core   		post-mortem debugging

Signal Control

1
2
3
4
5
6
7
8
9
10
(gdb) info signals        	print signal setup
(gdb) handle signo actions      set debugger actions for signal
(gdb) handle INT print          print message when signal occurs
(gdb) handle INT noprint        don't print message
(gdb) handle INT stop        	stop program when signal occurs
(gdb) handle INT nostop         don't stop program
(gdb) handle INT pass        	allow program to receive signal
(gdb) handle INT nopass         debugger catches signal; program doesn't
(gdb) signal signo        	continue and send signal to program
(gdb) signal 0        		continue and send no signal to program

Machine-level Debug

1
2
3
4
5
6
7
8
9
10
11
12
13
(gdb) info registers        	print registers sans floats
(gdb) info all-registers        print all registers
(gdb) print/x $pc        	print one register
(gdb) stepi        		single step at machine level
(gdb) si        		single step at machine level
(gdb) nexti        		single step (over functions) at machine level
(gdb) ni        		single step (over functions) at machine level
(gdb) display/i $pc        	print current instruction in display
(gdb) x/x &gx        		print variable gx in hex
(gdb) info line 22        	print addresses for object code for line 22
(gdb) info line *0x2c4e         print line number of object code at address
(gdb) x/10i main        	disassemble first 10 instructions in \fImain\fR
(gdb) disassemble addr          dissassemble code for function around addr

History Display

1
2
3
4
5
6
7
8
9
(gdb) show commands        	print command history (>= gdb 4.0)
(gdb) info editing       	print command history (gdb 3.5)
(gdb) ESC-CTRL-J        	switch to vi edit mode from emacs edit mode
(gdb) set history expansion on       turn on c-shell like history
(gdb) break class::member       set breakpoint on class member. may get menu
(gdb) list class::member        list member in class
(gdb) ptype class               print class members
(gdb) print *this        	print contents of this pointer
(gdb) rbreak regexpr     	useful for breakpoint on overloaded member name

Miscellaneous

1
2
3
4
5
(gdb) define command ... end        define user command
*(gdb) RETURN        		repeat last command
*(gdb) shell command args       execute shell command 
*(gdb) source file        	load gdb commands from file
*(gdb) quit        		quit gdb

Also see this: pdf

参考文献

GDB Cheat Sheet https://bytes.usc.edu/cs104/wiki/gdb/

Gdb Cheat Sheet https://web.stanford.edu/~ouster/cs111-spring23/gdb/

GDB的那些奇淫技巧 https://evilpan.com/2020/09/13/gdb-tips/

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 9.5k 阅读时长 ≈ 9 分钟

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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

By Long Luo

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

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

贝塞尔曲线是什么？

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

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

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

Bezier Curve

贝塞尔曲线的数学原理

这一章节待完善！！！

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

\(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. 特殊曲线类型：某些特殊曲线类型，如圆或椭圆等，可能有更适合的数学表示方法，而不是使用贝塞尔曲线。

总结

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

参考文献

  1. Bézier Curve↩︎

  2. Bresneham↩︎

  3. Pierre Bézier↩︎

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 2 分钟

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!!!

阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

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\) 是中间值都是同一个答案。

证毕！

阅读全文 »
0%