Archive for 编程

suricata 源码阅读2-yaml配置文件加载

FinalizeRunMode,检查了一下daemon和运行的模式是否匹配,然后模式保存到全局变量run_mode中。 StartInternalRunMode,这个是判断是否是一些打印相关的模式,如果是这些模式,调用相关的方法,这些方法就不看了。比如列出模式,打印软件帮助等这类的模式。 GlobalsInitPreConfig,先调用TimeInit,初始化了一个当前时间的自旋锁current_time_spinlock,具体干啥的还不知道,调用tzset设置时区变量。之后调用SupportFastPatternForSigMatchTypes,初始化sm_fp_support_smlist_list,是个链表,默认保存了DETECT_SM_LIST_PMATCH,优先级为3,具体不知道这个是干啥的。之后调用SCThresholdConfGlobalInit,我看主要是初始化了解析Thresholding的正则表达式。 LoadYamlConfig,加载配置文件,调用ConfYamlLoadFile,这个里边主要利用了yaml库解析配置文件,没查这个库具体函数,函数名很容易知道是干啥的。保存了一下配置文件的目录,主要是调用ConfYamlParse,把配置读入ConfNode结构的树里边,有父节点,然后是个链表。所以也不单纯是个树。没太仔细看具体解析流程,单纯就是读到树里了。 typedef struct ConfNode_ { char *name; char *val; int is_seq; /**< Flag that sets this nodes value as final. */ int final; struct ConfNode_ *parent; TAILQ_HEAD(, ConfNode_) head; TAILQ_ENTRY(ConfNode_) next; } ConfNode; ConfDump模式单纯就是把刚读如的链表树再打印一下。 查了一下“vlan.use-for-tracking”的值,这个参数看了一下配置文件介绍,基本用不到。 ConfGetBool获取配置中的bool值,先调用ConfGetValue获取值,里面通过ConfGetNode通过name找到node,key通过“.”进行分割,然后ConfNodeLookupChild查找当前等级的链表。看到这里发现,用c实现个json解析啥的好像也不太难啊。 SetupUserMode(&suricata);这个是设置非system模式的情况下,把日志和数据目录设置到当前目录,函数没跟进取,暂时不看了,这些模式不是看的重点。 SCLogLoadConfig应该是设置日志了,通过verbose设置等级,verbose通过参数有几个v来设置,等级为SC_LOG_NOTICE + verbose,看了一下SCLogLevel, 最高可以有5个v。获取logging.outputs的配置保存到outputs,SCLogAllocLogInitData初始化SCLogInitData,这个数据结构主要保存日志等级,格式,写到什么地方等信息。获取配置文件里"logging.default-log-level"配置的日志等级,然后跟参数里的比较,取等级最低的,保存到global_log_level。如果等级跟配置文件一致,使用配置文件的format。将outputs配置文件保存到变量,这些主要是日志的方式,console/file/syslog,没有细看,看了一下file的,这个用的多,调用SCLogInitFileOPIface,append模式打开文件,方式里面有个锁变量,注释说用来切割日志时候用的,然后调用OutputRegisterFileRotationFlag,把需要分割日志的这个flag都保存到output_file_rotation_flags里了,这个也是个链表。这里暂时有个疑问,我看flag初始化的时候没设置值,不知道后面会不会设置,还是我漏了。这里保存的是指针,可能不是漏了。日志等级还比较了outputs里的等级,取最低等级。然后调用SCLogInitLogModule,这个在之前调用过,之前可能是终端输出,现在可以配置文件了。 LogVersion,打印版本。 UtilCpuPrintSummary,打印cpu个数信息。 ParseInterfacesList,这里是看启动参数是否设置网口,如果设置会在配置里加一个xxx.live-interface的配置项,没设置就调用LiveBuildDeviceList,参数是模式,也是配置文件里的顶级名称,使用这个参数获取配置,如果interface为default,则忽略,这个是默认配置,其他情况调用LiveRegisterDeviceName,把接口插入队列,这个跟参数解析一致。所以看起来好像启动参数不加网口也可以啊。
Read more...

suricata 源码阅读1-初始化操作

SuricataMain是入口函数,先调用SCInstanceInit,把SCInstance变量数据清0,不知道为啥以及memset0了,还要变量名再置0一次。SCInstance就是suricata进程相关的一些变量,其中一个有意思的事是还保存了执行命令的文件名,看这个感觉可能直接改二进制的名也没问题的。run_mode设置为RUNMODE_UNKNOWN。 之后调用InitGlobal,主要设置suricata_context变量,这个变量在rust-context.h文件定义,全是操作函数,具体赋值的函数还没有看,这个先过了。 在InitGlobal里调用rs_init,这个看了一下好像是给rust调用用的,sc赋值给rust里的sc,这样在rust里可能就能试用context的函数了,我看在core.rs中都是contxt里的函数声明。具体c和rust怎么交互的,我还需要再看看。粗略看了一下,协议判断好像都在rust里写的。 然后初始化engine_stage为0,这个变量为原子变量,原子操作都定义在util-atomic.h,没细看怎么实现的,先知道干啥的吧。这个变量注释说的是表明引擎是在初始化还是在处理数据包了,总共包括三个状态SURICATA_INIT,SURICATA_RUNTIME and SURICATA_FINALIZE。 SCLogInitLogModule,初始化日志模块。没细看,参数传的NULL,使用默认日志系统。info等级打印到console,可以设置正则过滤,这几个设置项都可以通过环境变量设置。 之后ParseSizeInit,初始化了一个正则匹配器parse_regex,这个正则表达式不知道干啥的,看后面好像是把字符串“10kB,10GB”类似的转换成具体的大小数据,可能是配置文件之类的解析,先过了。 之后RunModeRegisterRunModes,跟函数名一个意思,注册的模块还没看。看配置文件就知道四五种,没想到还挺多。注册到数组runmodes。找了几个看看,发现就是list-runmodes里的模式,把对应的模式和具体模式的方法进行注册。每种模式都是调用RunModeRegisterNewRunMode注册到runmodes数组保存。RunModeFunc是对应的模式函数,这个先没看,等用到再看 之后ConfInit,初始化配置模块,ConfNode是一个列表,里面是kv键值对。起始就是初始化一个链表。 到这InitGlobal就结束了。 ParseCommandLine解析命令行参数,列出了所有参数,pfring或pfring-int参数启动pfring,设置run_mode为RUNMODE_PFRING, 如果后面跟参数,设置pcap_dev,这个应该是网口名了。LiveRegisterDeviceName就是把网口插入到一个链表里,相当于注册了。变量名pre_live_devices。capture-plugin还能设置插件名,这个模式RUNMODE_PLUGIN,可能dpdk得插件实现。netmap参数只能设置一次,看来只能在一个网口使用,而且还不能多个模式。 suricata --list-app-layer-protos 列出七层协议 suricata --list-runmodes 列出模式 list-keywords 关键字 -l设置日志目录 -i和af-packet都走af-packet,-i如果支持,默认也走af-packet。 这些参数在help里都有,暂时不看了,到时候回来看具体设置了什么参数,因为我看的代码比较新,之前版本的还有没有的参数。
Read more...

python使用matplotlib作图横坐标日期显示不全的问题

临时看个问题,对matplotlib没有了解,基本纯网上搜了搜。暂时先记录一下。 是使用 pandas读了一个excel表,然后加了index字段,是个日期,数据保存在变量df里,可以直接调用df.plot()进行画图,我是有点震惊的。这是因为这几个库联用的多嘛。画出来的图横坐标日期不能全显示,然后想全显示出来。 第一反应就是日期太长了,然后找可以调整角度的函数,用xticks修改角度,不好用。然后发现xticks可以指定横坐标显示位置,显示映射啥的。 x=np.arange(0,12,1)生成一个选择的映射,label传入全部十二个日期。然后就显示全面了。plt.xticks(x, mon, rotation=90) xticks参数还可以指定Text类型的参数,进行文本样式的设置。 最近让搞R语言,在看R语言画图的功能。因为看我对python的matplotlib,numpy,pandas这些库都没经验,领导之前会用R,就让我直接写R了。感觉搞这些工具,但不会统计的东西,搞起来总感觉是在隔靴子挠痒。
Read more...

gcc分支预测工具简单使用-gcov

linux内核使用许多likely和unlikely宏,这两个宏的内容为: #define likely(x) (__builtin_expect(!!(x), 1)) #define unlikely(x) (__builtin_expect(!!(x), 0)) 是用来告诉编译器,当前判断条件是否常用或者不常用。编译器根据提示,生成的二进制的代码流程会有相应改变,以达到让cpu尽可能的顺序执行的目的。gcc官方文档里说,使用-fprofile-arcs来进行实际的性能测试,说程序员对自己的程序的预测一般都是错误的。 然后我搜到是用gcov去做,使用了一下确实很直观。编译的时候,参数加上“-fprofile-arcs -ftest-coverage”。然后运行会生成 .gcda .gcno文件。用gcov source.c会生成相应代码的.gcov文件。vim编辑这些文件,就能看到源码形式的,每一行都执行了多少次。 这里说个疑问,前边说预测不准确,我当时看到那里还说真的是不准确。我之前就感觉明明会大概率走这个分支,然后加上提示后,速度却变慢了。但是当我用gcov去做完统计之后,发现确实很大很大概率走的那个分支,但是不知道为啥会变慢。我O2开反汇编发现内容是一样的,也可能是我测试的时候没开O2也许有不同。
Read more...

从一个多线程的bug,看内存屏障相关内容

最近看c底层相关的指令,操作,编码,多线程,磁盘文件读写相关的看的比较多。不经理永远不知道这里边的东西有多少,还有很多不易理解的。由于时间仓猝,本来想好好整理一下,作为一个总结,但还是决定只是记一个笔记,而且内容来自搜索引擎,有一部分不是看的官方文档解释等,可能不正确,而且没有写全。以后无聊的时候想起来再搞吧(感觉用不到以后不会再搞了) 先说为什么写这个文章,我碰到一个问题。多线程读写文件,然后单线程读取,线上后读取结果不一致。之前有过分步的测试,是没有问题的。 然后我排查原因,先从读入手,发现数据有问题,然后转到看写。写先通过单独打印几条日志,和对写入的数据错误判断,在某个函数。这时候,我打开编译的debug模式,就是能打印更详细的日志,然后发现问题没了,数据正常了。然后我就玩起了编译参数。发现打印日志就没事,不打印就出问题了,然后我就想到是编译器给我优化过头了,那时候还是开始02的优化。因为那个函数不涉及多线程的操作。然后我去掉 -DNDEBUG参数,然后用assert()判断出是哪一行出了问题。然后实验了几个方法,发现都是可以的,于是网上搜索资料,大体比较了一下这集中方式,选了一种。 1,把变量声明称volatile,主要功能是,编译器不会优化掉这个变量,然后变量的值不会存到寄存器,保证从内存中读取。看我的程序具体也看不出来,除非反汇编代码看看。也懒得看了。 2,__sync_synchronize (...),This builtin issues a full memory barrier. 内存栅栏,这个是个硬件栅栏,效率相比下边不太高。 Memory Barrier (Memory Fence)分为两种,一种软件的,只对编译器起作用,一种是硬件的,看文章说是总线信号控制的,这个计算机组成结构没学好,也懒得细看。 下面几种跟linux内核中的相对应,没看源码,不知道对不对 #define mb() __asm__ __volatile__("mfence":::"memory")这个跟__sync_synchronize一个作用,是硬件的栅栏。 #define rmb() __asm__ __volatile__("lfence":::"memory")不允许将barrier之前的内存读取指令移到barrier之后 (release barrier) #define wmb() __asm__ __volatile__("sfence":::"memory")不允许将barrier之后的内存读取指令移到barrier之前(acquire barrier) #define barrier() __asm__ __volatile__("":::"memory") barrier()是软栅栏, rmb wmb好像分单处理器和多处理器不一样,单处理器为软栅栏。 期间写的程序也有好多cas操作,atomic原子操作,编译器主要用的gcc的,然后直接用的gcc的,官方地址: https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html
Read more...

C语言差错调试工具3-perf简介

perf工具应该都听说过,我也试了一把,感觉很好很强大。 先使用sudo perf stat ./a.out命令,查看一下性能统计信息。结果展示为: Performance counter stats for './a.out': 2,740.62 msec task-clock # 3.903 CPUs utilized 39 context-switches # 0.014 K/sec 2 cpu-migrations # 0.001 K/sec 128,974 page-faults # 0.047 M/sec 10,394,863,898 cycles # 3.793 GHz 14,055,693,753 instructions # 1.35 insn per cycle 2,865,438,627 branches # 1045.545 M/sec 17,411,072 branch-misses # 0.61% of all branches 0.702237190 seconds time elapsed 2.533414000 seconds user 0.208445000 seconds sys 因为程序基本跑内存的,这里cpu使用比较高,就是开始的时候读了文件。四个线程高达3.9的使用率 context-switches 是进程上下文切换,这个不知道为啥,可能我系统跑的东西太多了。 CPU-migrations 这个是cpu迁移次数,没办法避免吧,程序跑的多,或者需要cpu绑定。 page-faults 这个感觉有点高,不知道为啥,我这还没涉及文件读写相关,已经这么高了。 branch-misses 这个感觉也比较高,看看使用分支预测改善一下,能不能好。这个需要对比一下。 获取程序的cpu运行时间统计,sudo perf record -e cpu-clock ./a.out,命令会生成perf.data文件,使用perf report查看报告 下边还有个直接展示的高级货,叫做火焰图。用perl写的,感觉好强大,以后可以稍微研究一下怎么生成的。 需要先clone下代码来:git clone --depth=1 https://github.com/brendangregg/FlameGraph.git 上一步收集信息的时候必须加-g参数,用来收集堆栈信息,不然后边生成图像的时候会报错。 sudo perf record -g ./a.out 数据解析 sudo perf script -i perf.data &> perf.unfold 数据折叠 ./stackcollapse-perf.pl perf.unfold &> perf.folded 图像生成 ./flamegraph.pl perf.folded > perf.svg 生成的图片用chrome查看是有效果的,我用ubuntu自带的图片查看软件,发现不能交互。 我发现对于递归程序,展示的不太友好,虽然能从调用栈中获取到递归深度,但是调用的函数差不多都放到递归最里边了,可能是取样的问题嘛,,
Read more...

C语言差错调试工具1-Callgrind,cachegrind

Callgrind是valgrind的一个工具,能够分析程序运行效率,帮助找到程序瓶颈。 命令tool知道使用的valgrind的工具, valgrind --tool=callgrind ./a.out 运行完之后会生成一个callgrind.out.PID文件,然后执行下面命令进行分析 callgrind_annotate callgrind.out.PID 这个命令能够展示每个调用函数对应的执行指令的次数,展示已经排序,可以优先优化最顶部的函数。 cachegrind也是valgrind的一个工具,主要分析内存使用情况的,比如cpu cache的使用等。 简单使用命令: valgrind --tool=cachegrind ./a.out ==12810== ==12810== I refs: 13,413,053,205 ==12810== I1 misses: 3,851 ==12810== LLi misses: 3,552 ==12810== I1 miss rate: 0.00% ==12810== LLi miss rate: 0.00% ==12810== ==12810== D refs: 4,991,204,111 (3,140,940,594 rd + 1,850,263,517 wr) ==12810== D1 misses: 49,675,548 ( 38,504,518 rd + 11,171,030 wr) ==12810== LLd misses: 29,710,307 ( 19,488,129 rd + 10,222,178 wr) ==12810== D1 miss rate: 1.0% ( 1.2% + 0.6% ) ==12810== LLd miss rate: 0.6% ( 0.6% + 0.6% ) ==12810== ==12810== LL refs: 49,679,399 ( 38,508,369 rd + 11,171,030 wr) ==12810== LL misses: 29,713,859 ( 19,491,681 rd + 10,222,178 wr) ==12810== LL miss rate: 0.2% ( 0.1% + 0.6% ) 看着好像程序我的程序允许的比预期的缓存命中高很多,看官方文档说的。On a modern machine, an L1 miss will typically cost around 10 cycles, an LL miss can cost as much as 200 cycles, and a mispredicted branch costs in the region of 10 to 30 cycles. Detailed cache and branch profiling can be very useful for understanding how your program interacts with the machine and thus how to make it faster.现代机器,L1缓存丢失通常花费10个cpu周期,LL丢失花费200个周期,分支预测错误花费10-30个周期,所以这部分性能分析很重要啊。 LL指的是最后一级的cpu缓存,许多cpu架构可能有多级缓存,L1和LL具有代表性,所以只分析了这两种。 程序还是会生成一个cachegrind.out.PID文件,同样可以具体分析每个函数的内存使用情况 cg_annotate cachegrind.out.12810 这俩工具在官方手册上,每个一章进行介绍,具体也没研究,先初步了解一下
Read more...

c语言差错调试工具1-Valgrind

Valgrind可以模拟cpu执行你的程序,然后给出内存使用或者程序错误信息。之前只使用过gdb来调试程序逻辑错误,现在准备多看几个,包括性能方面的调试。 安装直接使用的apt源安装的,使用也比较简单。直接valgrind ./a.out允许程序,运行过程中会给出程序建议。 这个程序我有一个一百万长度的uint64的数组,提示了"Invalid write of size 8"的错误,Warning: client switching stacks? SP change: 0x6c55ef0 --> 0x64b4c60 to suppress, use: --max-stackframe=8000144 or greater 我搜了一下发现说是栈空间消耗太大,我改成calloc,两个错误提示都没了。 ==15130== HEAP SUMMARY: ==15130== in use at exit: 457,122,934 bytes in 4,659,095 blocks ==15130== total heap usage: 4,659,118 allocs, 23 frees, 457,166,878 bytes allocated ==15130== ==15130== LEAK SUMMARY: ==15130== definitely lost: 48,850,904 bytes in 177,241 blocks ==15130== indirectly lost: 400,271,992 bytes in 4,481,851 blocks ==15130== possibly lost: 8,000,000 bytes in 1 blocks ==15130== still reachable: 38 bytes in 2 blocks ==15130== suppressed: 0 bytes in 0 blocks ==15130== Rerun with --leak-check=full to see details of leaked memory 最后有内存统计信息,malloc后没有free的内存都会在统计。下面这段解释是我摘自网上的,我感觉不太准确(可能是valgrind检测的就不太准确),但是个参考。 Memcheck将内存泄露分为两种,一种是可能的内存泄露(Possibly lost),另外一种是确定的内存泄露(Definitely lost)。 Possibly lost 是指仍然存在某个指针能够访问某块内存,但该指针指向的已经不是该内存首地址。Definitely lost 是指已经不能够访问这块内存。而Definitely lost又分为两种:直接的(direct)和间接的(indirect)。直接和间接的区别就是,直接是没有任何指针指向该内存,间接是指指向该内存的指针都位于内存泄露处。在上述的例子中,根节点是directly lost,而其他节点是indirectly lost。 possibly lost: 8,000,000 bytes in 1 blocks这个就是我那个一百万的数组malloc后没有free释放的,然后我free后,这行就没了。但我指针没修改,是个多线程的内存申请,但是只检测出一个来。四个线程没一个都malloc了。 Valgrind User Manual写的很详细,好多功能,一时半会也试不完。先体验一把,有需求再说。
Read more...

linux系统调用sendfile和splice简单分析

零拷贝不是一个新技术了,之前一直接触不到这么底层的技术,最近看的比较多,所以从代码上研究了一下。 在应用程序做数据传输等操作涉及系统调用,而为了提高性能,就是从减少系统调用次数和减少内核空间和用户空间的数据拷贝次数入手的。 具体的我也没看代码,都是从网上总结学来的。 像mmap方式,是减少了内核空间和用户空间的数据拷贝,使用映射还是指针的能够共享内核空间。但涉及比如把一个文件内容通过网络发送的操作,还涉及内核空间的数据拷贝。 sendfile和splice就是解决内核空间的数据copy的,我看linux手册是page buffer指针的复制,所以没有做数据的copy。指针是通过pipe buffer存储的。 ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count); ssize_t sendfile64(int out_fd, int in_fd, loff_t *offset, size_t count); 这俩的区别是sendfile64适合传送大文件,offset类型也决定了适合做大文件的偏移用。但不仅仅是这里,看源码,sendfile指定offset之后,会设置复制的最大值为MAX_NON_LFS,这个值我没找,但是类型初步判断加文档判断来说,最大不到2G(看文档是不到2G).(后来还是去找了,#define MAX_NON_LFS ((1UL<<31) - 1), 文档写的是0x7ffff000 (2,147,479,552) ) 我看了一下函数实现的源码,尽量只看流程,不去细看实现,看看优化能注意的点。 通过看源码,发现最好是不指定offset这个参数,因为指定这个参数后,会多两次的内核函数调用,涉及用户空间和内核空间的数据拷贝,get_user,put_user,copy_from_user。然后统一调用do_sendfile函数。而如果offset为NULL的时候,在do_sendfile函数里,是通过文件的offset来复制数据的。所以尽量不指定offset是最好的,但如果提前设置文件offset还要涉及系统调用,具体权衡就不知道了。 在do_sendfile里没啥可以细讲的,流程大部分能猜到什么意思。主要最后调用do_splice_direct。 这里有个疑问就是,为什么offset要用指针类型,而不能直接传一个数字,我猜可能是历史遗留问题吧,可能接口没办法变动了。 do_splice_direct函数跟splice是在一个文件,可以差不多猜到,俩的实现原理是一样的了。 do_splice_direct里splice_desc sd定义输出文件的信息。 然后调用了splice_direct_to_actor,这里有一个pipe = current->splice_pipe;这个pipe是在linux的进程管理的pcb(task_struct)中,这里边有一个splice_pipe,用来存储splice()上一次使用的过的pipe。这里是判断如果current->splice_pipe不存在,就新创建一个,然后缓存到current->splice_pipe。然后调用do_splice_to,流程跟splice复制文件到pipe的流程差不多。 splice里直接调用do_splice,这里分三种情况,in和out都有pipe时,调用splice_pipe_to_pipe;in为pipe时调用do_splice_from,out为pipe时调用do_splice_to。这俩单个的也涉及offset的用户空间和内核空间复制的问题。 do_splice_from我直接看的default_file_splice_write,调用splice_from_pipe。里边初始化splice_desc sd,存了要写的文件信息,调用__splice_from_pipe,splice_from_pipe_feed里是将pip内容关联复制到文件。 do_splice_to也是直接看default_file_splice_read,初始化一个结构体splice_pipe_desc spd,看起来是存储pagebuffer信息的,具体看不太懂,也没去查,初始化spd空间,kernel_readv应该是用来吧in的page buffer内容的指针存入spd了,nr_pages_max = PIPE_DEF_BUFFERS这个值是16(看文档在内核版本2.6.35之后,可以通过fcntl的F_GETPIPE_SZ和F_SETPIPE_SZ进行设置),好像是最大页数,最后调用splice_to_pipe(pipe, &spd);好像就是从spd里刚保存的页信息关联复制数据到pipe。 vmsplice支持从用户空间复制数据到pipe,反方向的复制也支持,但是是内存数据的真复制。 tee复制管道内容,从一个复制到另一个 总结一下就是,文件的传输使用sendfile比较好,他会缓存pipe,并且少一次的系统调用。如果用splice,需要先从一个文件到pipe,然后pipe到另一个文件,虽然也没有真正复制,但是系统调用是两次。 splice可以实现类似代理服务器数据转发的功能,使用一个pipe连接两个socket。 上边说的都是PIPESIZE。在Linux 2.6.11之前,PIPESIZE和PIPEBUF实际上是一样的。在这之后,Linux重新实现了一个管道缓存,并将它与写操作的PIPEBUF实现成了不同的概念,形成了一个默认长度为65536字节的PIPESIZE,而PIPEBUF只影响相关读写操作的原子性,一般为page大小,内核每次操作量。PIPESIZE的最大值在/proc/sys/fs/pipe-max-size里进行设置。从Linux 2.6.35之后,在fcntl系统调用方法中实现了F_GETPIPE_SZ和F_SETPIPE_SZ操作,来分别查看当前管道容量和设置管道容量。
Read more...

写了一个二维泊松圆盘采样的c语言程序

照着别人写的js库,重新写了一个c版本的,也学了一下其中的算法。为什么需要松圆盘采样这个算法进行采样,是因为存随机其实也不是纯随机,随机分布不均匀。而这样生成的伪随机(psuedorandom)数列,很大程度保证了随机的均匀性。 开始以为很难,边写边学发现其实原理不太难。 基本思想就是,初始点可以给定或者随机。 第二步根据初始点,按照一定角度生成不同方向的新点,其中这个角度是关键。通过三角函数,保证生成的新点到初始点的距离为r。 第三步判断新生成点跟周围两个区域的点的距离,保证距离大于r。如果点不合法,则改变角度,重新生成。有一个重试次数保证重新生成上限,如果达到上限还没有找到一个新点,就说明这个点有问题,进行删除。如果合法,生成的点作为一个选择点并插入队列,作为下一次判断的初始点 第四步,队列中有其他生成点,继续上边第二第三步,直到没有生成点可以用。 期间我看js版本生成随机数的时候用的自己写的伪随机生成数,然后我就看了一下用的库,发现里边用了一个Thomas Wang写的 hash生成随机数,又简单看了一下。都是位操作,也懒得找原理看。先记一下,以后用到再看原理吧。
Read more...

1 2 3 4 5 Next Page 最后一页