TheCodeWay:我的博客

        最近在工作中遇到这么一个问题：
        在游戏场景中有一个怪物生成点，这个生长点产生的怪物均匀分布在半径为R的圆形内，这个随机算法应该如何生成？看起来很简单，随手写了一个：

        但写的过程中，直觉告诉我，这么写肯定是有问题的，试想，如果以北京为例，如果所有居住在北京的人都报出自己家和天安门的距离，那么这些数据肯定不是均匀分布的，因为居住在五环附近的人数肯定要大于居住在二环附近的人数，于是用Mathamatica实验一下：

        果然，这么写是不对的，网上查了一下，这个问题还真是有人研究过，说应该把所获得的随机数开平方一下，实验一下：

        但是，这个开平方背后的数学原理究竟是什么呢？抽空翻了下概率书，原来，其中的道理并不复杂，这里涉及到概率里的一个基本概念，累计分布函数（Cumulative distribution function），简称CFD，它的定义如下：
        设有一个随机变量\(X\)，它的取值范围是从负无穷到正无穷，如果把它的值小于\(x\)的概率表达为一个函数\(F(x)\)，那么这个函数就称为\(X\)的累计分布函数
\begin{equation}
F(x)=P(X\leq x)
\end{equation}
Continue reading “如何生成一个随机的圆形” →

        密码的管理可以说是加密体系中最为性命攸关的问题，在计算机发明之前，加密方法只能使用简单的移位、查表等简单的方法，这种级别的加密算法，基本上都无法逃脱被破解的命运，比如二战中德国发明的“英格玛”可以说是前计算机时代人类所发明的最为复杂的加密方法了，但以图灵为首的盟军科学家们，仍然可以用粗暴的暴力破解法硬生生从密文中破解出原文出来。
        进入计算机时代后，加密算法的复杂度有了质的飞跃，相对应的破解难度也不断加大，到了如今，像AES这样变态的加密算法，已经比英格玛不知复杂了多少个数量级，在没有密码的情况下，想直接从密文中破解出明文，即使图灵重生也全无可能了。于是，密钥本身的管理变成了加密环节中最脆弱的环节，“如何安全的把密码告诉别人”成了一个难题，比如，如果你需要发给同事一封包含加密附件的邮件，一般都会把密码放在另外一封邮件中发送，或者用其他方式告诉他，尽管这样做也并不安全，但总比那种傻乎乎的把密码和加密附件直接放在一起强多了。
        1976年，美国的两位数学家Whitfield Diffie和Martin Hellman率先发表了一种解决该密钥传输的方法，因此这种方法被大家称为Diffie–Hellman key exchange算法，这种算法提出这么一个做法：“在加密通讯之前双方各自生成密码的一部分，然后互换后合成起来，作为最终的密码”。这就是密钥协商，维基百科上使用了一个很有趣的比喻，就是颜料的混合：
        设想这样一个场景，Alice(A)和Bob(B)，他们想在不见面的情况下秘密约定出一种颜色，但他们互相沟通的信息都会被公开，应该怎么办呢？

	Alice			Bob
	私密信息	公开信息		公开信息	私密信息
A和B首先约定好公开的一种颜色，比如黄色
A，B各自挑选出一种私密的颜色，比如橙色和兰色
A，B各自将两种颜色混合起来
双方交换混合后的颜色
A，B各自将自己的私密颜色再次混入得到的颜色中
现在A，B得到了一种相同的颜色，这种颜色是由一份黄色、一份橙色、一份兰色混合而来，但外界无法得知

        秘密在于，颜色混合是一种“不可逆”的操作，当双方交换颜色时，尽管我们知道他们交换的颜色都是由一份黄色和另一份其他颜色混合得到的，但我们还是无法或者很难得到他们的私密颜色。而DH秘钥交换的原理非常相似，也是利用了数学上的一个“不可逆”的运算，就是离散对数（Discrete logarithm）
Continue reading “一个简单的DH密钥协商算法的实现” →

这是我以前写的一篇博文，因为有朋友需要，重新贴出来

        一个程序里用到了计算线段和圆相交情况的算法，在这里记下来备忘

        设线段的两个端点分别是P1(x1,y1)和P2(x2,y2)，圆的圆心在P3(x3,y3)，半径为r，那么如果有交点P(x,y)的话
\begin{equation}
\overrightarrow{P}=\vec{P_1}+u(\vec{P_2}-\vec{P_1})\tag1
\end{equation}
        其中，u在0到1之间，转换成各个坐标
\begin{equation}
\begin{cases}
x=&x_1+u(x_2-x_1)\\
y=&y_1+u(y_2-y_1)
\end{cases}\tag2
\end{equation}
        由于P也在圆上，所以
\begin{equation}
(x-x_3)^2+(y-y_3)^2=r^2\tag3
\end{equation}
        联立上面的公式，可以得到
\begin{equation}
Au^2+Bu+C=0\tag4
\end{equation}
        其中
\begin{equation}
\begin{cases}
A=&(x_2-x_1)^2+(y_2-y_1)^2\\
B=&2((x_2-x_1)(x_1-x_3)+(y_2-y_1)(y_1-y_3))\\
C=&x_3^2+y_3^2+x_1^2+y_1^2-2(x_3x_1+y_3y_1)-r^2
\end{cases}\tag5
\end{equation}
        解一元二次方程，可以得到
\begin{equation}
u=\frac{-B\pm\sqrt{B^2-4AC}}{2A}\tag6
\end{equation}
        根据B²-4AC的结果，可以判断线段所在直线和圆的相交情况

• 如果小于0，表示没有交点
• 如果等于0，表示相切，只有一个交点
• 如果大于0，表示有两个交点

        针对P1和P2之间的线段，根据计算出的u值，有5种结果

• 如果线段和圆没有交点，而且都在圆的外面的话，则u的两个解都是小于0或者大于1的
• 如果线段和圆没有交点，而且都在圆的里面的话，u的两个解符号相反，一个小于0，一个大于1
• 如果线段和圆只有一个交点，则u值中有一个是在0和1之间，另一个不是
• 如果线段和圆有两个交点，则u值得两个解都在0和1之间
• 如果线段和圆相切，则u值只有1个解，且在0和1之间

        刚在微博上看到一道很有意思的数学问题，原题是：如果椭圆游泳池有一英尺宽的边缘，问：边缘外围是否仍为椭圆？这个问题背后还有个八卦故事，数学家Steven Strogatz是非线性动力学大师级人物，广为人知的是他和自己的高中数学老师Don Joffray有着深厚的友谊，这位老师是把他带入数学殿堂的引路人，一次他在接受采访时，Strogatz讲到自己和这位老师的故事，他们即使在毕业后也一直保持着联系，一开始是他写信请教老师问题，但转折点就是这个“elliptical pool”问题，老师第一次被问住了，反而是他给老师解释，这令他激动不已。
        有趣的问题就是这样，看起来足够简单，却要费一番脑筋才能想清楚。这里先定义一个概念，“一英尺宽的边缘”的数学含义，是指在椭圆的每个点的法线方向上扩展一定的长度，微博上另一位博主给出了一个很相像的动态图来描述，这里直接借用一下：

        这个问题有两种解决思路，一种是纯粹从数学公式入手，这里给出一个解法，首先对于任意一个椭圆，用参数函数表达：
\begin{equation}
x=a\cos\theta,\quad
y=b\sin\theta,\quad
0\le\theta\le 2\pi\tag1
\end{equation}
        利用微分知识可知，对于平面上任意一个连续的曲线函数，如果其参数方程表达为x=x(t),y=y(t),那么在任意点P₀点处的法线方程可以表达为
\begin{equation}
\frac{y-y_0}{x-x_0}=-\frac{x'(t_0)}{y'(t_0)}\tag2
\end{equation}
        所以对于椭圆上任意一点(x₀,y₀),它的法线方程是
\begin{equation}
\frac{y-y_0}{x-x_0}=\frac{a\sin\theta}{b\cos\theta}\tag3
\end{equation}
        假设轮廓的宽度为K,那么椭圆上的点(x,y)对应的外廓的点（x’,y’)的方程为
\begin{equation}
\begin{aligned}
x’ &=a\cos\theta+K\frac{b\cos\theta}{\sqrt{(b\cos\theta)^2+(a\sin\theta)^2}}\\
y’ &=b\sin\theta+K\frac{a\sin\theta}{\sqrt{(b\cos\theta)^2+(a\sin\theta)^2}}
\end{aligned}
\tag4
\end{equation}
        如果这个轮廓是一个椭圆的话，那么必然(x’,y’)满足椭圆方程
\begin{equation}
(\frac{x’}{a+K})^2+(\frac{y’}{b+K})^2=1\tag5
\end{equation}
        把公式4代入5中既可发现只有在a=b时公式才成立，所这个轮廓不是椭圆。
        当然，如果只是想知道答案的话，可以不用这么麻烦，还有一种思路就是利用极端情况。设想一下这个椭圆极其“扁”，那么它的形状像是两条紧紧贴在一起的线段，不难想象，如果在这个椭圆外扩展一个宽度，那么新的轮廓的的上下边缘类似于两条分开的平行线段，但两端却无法平滑连在一起，这个形状类似于一个圆角的矩形，显然不是椭圆，下面是一个用Mathematica模拟的动态图

      整理旧硬盘时发现以前写的两个captcha库，我以前曾经有一段时间专门负责游戏中anti-robot的工作，利用captcha是必不可少的一个手段，这两个项目都是在实际项目中使用过的，所以稳定性很高。我花了点时间上传到github上了，希望能够帮到仍旧还想利用这个方法的人。
      captcha的原理是在服务器端生成一张包含只有人类才能识别的图片，然后在客户端显示，我写的第一个库libcapt也是利用了同样的原理，将字符串通过一定的变形、扭曲，并增加了噪音和背景色差之后显示，在服务器端的调用方法如下

      其中Question结构里是一块256×64大小16bit的图片内容，四个共用户选择的答案和一个正确的答案，另外这个库还提供了一份字体文件的产生工具和测试工具captUtil。

      源码下载地址如下

	https://github.com/thejinchao/libcapt

      另外一个库libWaveCapt使用了比较有趣的方式，生成一块包含波纹信息的图片，然后让用户选择波纹的中心。这个库使用了libnoise这个开源库，libnoise能够产生随机噪图案，是一个很有意思的库，可惜已经很久不更新了。libWaveCapt同样提供了captUtil供测试使用

      源码下载地址如下

	https://github.com/thejinchao/libWaveCapt

        CloudFlare最近推出了UniversalSSL功能，向所有CloudFlare用户(包括免费用户)提供SSL加密功能。不得不说，这绝对是一项造福人类的好事情，要知道，购买正式的SSL证书起码要支付每年400+美刀的费用，这也是为什么只有少数网站才会提供高大上的HTTPS服务的原因，CloudFlare此举无疑为未来互联网的全面加密时代吹响了号角。
        当然，这个博客没有任何必需要加密传输的内容，我只是实验一下，结果还是很不错的。大家可能注意到我博客右侧多出一个“加密链接”的按钮，通过这个按钮或者直接在浏览器中通过输入“https://www.thecodeway.com”来访问我这个博客的https版本。下图是CloudFlare提供的SSL加密的几种模式，可以看出其原理很简单，它并不是为每个网站提供一份加密证书，而是通过云服务器，将流经用户和服务器之间数据加密。

        我使用的是其中的Full SSL模式，也就是首先要在服务器上配置自签名的SSL证书，通过下列指令创建证书。

Continue reading “CloudFlare免费SSL证书使用” →

这篇文章转自http://graphics.stanford.edu/~seander/bithacks.html，作者收集了一系列巧妙的bit运算技巧，并亲自验证通过，转载于此并做了部分精简

·获得整数的符号

·不用分支计算绝对值(abs)

·不用分支计算最大或者最小值

·判断是否是2的幂方

Continue reading “Bit运算技巧汇集（上）” →

        这个系列的最后，我提供给大家一个简易的jpeg压缩算法的代码，这份代码用C++编写，以开源方式提供，放在了github上，可以到下面这个网址下载

	http://github.com/thejinchao/jpeg_encoder

        使用方法很简单，像下面这样就可以了

        这份代码只是为了配合这个系列的文章，所以没有考虑优化，如果你想在实际工程中使用jpeg的压缩算法，还是使用被广泛应用的libjpeg或者OpenJpeg。