Xun’s blog

一幅图片是由一个个的像素点组成的，作为有色光的三基色，红绿蓝（RGB）可以以一定的比例混合出任何颜色，所以一幅彩色图片的每个像素都可以用RGB三个分量来表现自己，常见的每个分量用8位，这样一个像素需要3×8=24位，而一幅图片就是一个每元素24位的二维数组。但是研究发现人眼对颜色的敏感比不上对亮度的敏感，因此可以将亮度分量从色度分量中提取出来而以较少的位来表示色度信息，从而更加有效的表示彩色空间。

因此与RGB相对，另一种颜色空间为Y:Cr:Cb，这里Y为亮度分类，即一幅彩色图片的黑白版本，由RGB加权平均得出。Cr，Cb是R，B与Y之差，为色差信息，因Cr+Cb+Cg为常数，所以Cg无需传输。

RGB与Y:Cr:Cb转换公式
Y=0.299R+0.587G+0.114B     Cb=0.564(B-Y)      Cr=0.713(R-Y)
R=Y+1.402Cr     G=Y-0.344Cb-0.714Cr         B=Y+1.772Cb

利用人眼对亮度敏感的优势，在一幅彩色图片中，我们可以交叉地使一些点只有亮度分量没有色度分量，而不被人眼察觉。

4：2：2采样（YUY2）：对于图像数组每隔一列只采样Y分量。
4：2：0采样（YV12）：每隔一列和一行只采样Y分量。

因此4：2：0采样的图像只有1/4的像素是24位的，其余3/4的像素只有Y分量的8位，即平均每像素1/4×24+3/4×8=12位，这也是为什么它在FOURCC代码中的表示为YV12。

一个视频编码器的主要功能有：
1，滤波。消除视频源中的干扰信号。
2，源模型编码。把视频变换成一种易于压缩的格式。
3，熵编码。无损压缩上一步得到的数据。

最关键的是第二步了。在这里视频编码被分为帧内编码（Intra-frame Coding）和帧间编码（Inter-frame coding），视频无非是一张张连续的图片，帧内编码就相当于压缩一张图片，因为组成一段视频的图片有一定的相似性，据此我们可以只完全编码压缩某一帧图片，该帧称为I帧，其后的帧只保存那一帧与I帧或基于I帧的某种运动预测后的图片的差别，如果是连续的场景，物体的运动预测又足够准确的话，这种差别是很小的，因此我们只需保存很小的数据量就能恢复出原图像。运动预测的一般方法：把当前帧的某个区块向各个方向移动几格，并与下一帧的对应区块进行比较（通过计算两个图像数组的均方差），保留均方差最小的那个方向做为运动矢量，用于解编码。这个过程会用到各种不同的搜索方式和大量的比较运算，是衡量一个编码器好坏的关键。

编码步骤
变换编码。因为一幅图像的各个部分的空间相关性很高，不利于直接压缩。变换编码就是把图像用一种各部分相关性弱的形式表示，这样就可以去掉一些不重要的点，来进行有损压缩。其实质就是一个24位二进制数的二维数组，从一个各值很平均的形式变到另一种各值落差很大的形式，当然这个过程应该是可逆的。通常落差很大意味着有很多值在零值附近，通过量化就可以变成一个有很多零值的稀疏矩阵。
量化过程可以理解为把数组中所有的值除以一个数N，这样小于N的数就变成了0，而那些大数需要被传输的位数也降低了，其恢复过程为整个数组乘以N，那些在除法过程中被舍弃的位数就成了不可恢复的误差了。
常见的变换编码有DCT和小波变换。
熵编码，根据统计信息将频繁出现的符号用较少的比特表示，不经常出现的符号用较多的比特表示，进而达到对数据压缩的目的，而在此之前往往会通过游程编码重新排列数组，以使更多的零排在一起。这些排在一起的零将通过（run，level）编码，用一个符号表示。
显然最直接的熵编码算法是哈夫曼编码，但实际应用中的熵编码会更加复杂。

参考书籍：Iain E.G.Richardson 视频编解码器设计

参考了一下网上的代码发现用一维数组表示棋盘结构比较高效。

具体布局是这样的。

ddddddddd
dxxxxxxxx
dxxxxxxxx
dxxxxxxxx
dxxxxxxxx
dxxxxxxxx
dxxxxxxxx
dxxxxxxxx
dxxxxxxxx
dddddddddd

d表示边界，用来中断翻转循环。也可用来表示不可下的位置。 这样棋盘的第一格位置A1=B[10](根据棋盘宽度调整)A2=B[11]……H8=B[80]。对于一个位置B[num],它的左边是B[num-1],上边是B[num-9],右下是B[num+10]换而言之它的8个方向可以通过数组

dir[] = {1, -1, 8, -8, 9, -9, 10, -10, 0};来快速的访问。

对于有些点，比如左上角的A1，你下了之后，只有可能在右，下，右下，三个方向翻转对方的子。为了更高效的判断，可以建立一个方向蒙版。

dirmask[91] = {
0,0,0,0,0,0,0,0,0,
0,81,81,87,87,87,87,22,22,
0,81,81,87,87,87,87,22,22,
0,121,121,255,255,255,255,182,182,
0,121,121,255,255,255,255,182,182,
0,121,121,255,255,255,255,182,182,
0,121,121,255,255,255,255,182,182,
0,41,41,171,171,171,171,162,162,
0,41,41,171,171,171,171,162,162,
0,0,0,0,0,0,0,0,0,0
};

它的每一项和棋盘一一对应。但是用一个8位无符号整数来表示。8位中每一位表示一个方向。比如右用第0位表示，下用第4位表示，右下用第6位表示（对应dir数组），所以左上角的A1对应的方向蒙码是2^0+2^4+2^6=81。以此类推。

当然这是8X8无障碍位置的棋盘。对于比赛棋盘我们可以这样处理。

if(B[num]==NOT_AVAILABLE);
dirmask[num] = 0;//把NOT_AVAILABLE的位置设为0
for (int k = 0; k< 8; k++) //对于它的8个邻居把向它的那个方向的位取零
{
int t;
if(k%2==0)  t=k+1;else t=k-1;
if ((num + dir[k])>0&&(num + dir[k])<dirmask.length)
dirmask[num+dir[k]]&=((~(1<<t)));
}

最后我们在测试某一个位置是否可下时，只需取那个位置的蒙版值dirmask[num] ，测试它每个位置的值，即与1,2,4,8,16,32,64,128与一下，结果为零的方向就不用考虑了。

黑白棋又称othello，revers貌似是最简单的棋类了。

具体规则及战术见http://www.othello.cn/

所谓易于入门难于精通，大概是得了暴雪的真传。

这种棋20几天前我对它一无所知，现在也是入门级水平，只是当初发现有一个黑白棋编程大赛，我又无所事事，实在无聊，就决定碰一碰运气报名参加了。事先还腾了点时间补一下java和Eclipse方面的知识。

胡乱google了一气之后，找了几个网站，细究之下，发现黑白棋编程的要点就以下2个。

1：估值函数。评判一局面的有利程度。

2：搜索算法。怎样往后看。

具体的讲就是，在N个选择中徘徊的时候，计算我下在这里，对手可能下在哪里，我又可能下在哪里，最后的结果对谁有利（一开始靠估值函数判断，临近结束就看谁的子多了）。有点晕，这位老兄讲得比我清楚。http://blacwet.51.net/programming.htm

原理大家都差不多，拼的就是效率，特别是终局搜索的时候，谁快几步就可以先决定胜负。

顶级的黑白棋程序都可以搜20几步，但人家是用c++写的，关键的地方还用MMX汇编，估值的时候查查事先计算好的各种Table和Pattern速度当然是异常的快。

我一开始踌躇满志，下了据说是顶级的zebra源代码，看了半天未果。又上了一个国外看上去挺权威的网站，下了一堆paper狂啃，居然还翻出了两篇李开复早年的论文，顿时觉得很有前途，便找了几篇去图书馆打印了，心情激动地看了一个下午。勉强懂了一点，但是都不实用，因为比赛用的棋盘大小未定，中间还会放一些障碍。

比如很有用的Edge Table是这样的，一条边不管是横的还是直的都是八个格（对于8X8的棋盘），每个格有3种情况，所以边上所有会出现的情况共有3的8次方，所以可以建一个3的8次方这样大的表，把每一种情况遇到后的对策或各种值（我的行动力，对手的行动力）放到表里，实战的时候就不用动态的去计算，查查表就可以得到结果，这样可以节省很多时间，因为这是一个经常会发生的动作。具体查表的方法可以是这样，对与这8个格，第一个格赋予3的0次方的权值，第二个赋予3的一次方权值，直到第八个赋予3的7次方。当一个格子上是白子的时候用1去乘以她的权值，当是黑子的时候用2去乘以她的权值，无子的时候用0乘以她的权值，然后把所有的值加起来，就是一个Index，可以想见所有的情况都可以在那张3的8次方大小的表里找到一一对应的位置。非常好的想法，非常高效。只可惜根据比赛的规则我们每个格有4中情况，而格的大小未定万一是一张非常规的大盘，结果就非常恐怖。

一直在找一款好用一点的笔记管理软件，这个信息泛滥的年代东记一点西记一点可不是一个好习惯。试过AutoHotKey+notepad和以前的EverNote最后还是觉得OneNote比较顺手。直到这次EverNote出了3.0版。

首先在内容收集方面，它可以方便的截取IE和FireFox的上的内容。还有一个Universal Clipper可以通过剪切板来采集任何程序的文本图片。

内容管理上，它支持标签。这个太喜欢了，有趣的东西总应该有很多面，因此固定的分类是很难的，而多加几个标签则是很容易的，而且更便于浏览了。

另外还有针对图片的文字识别，瞬间过滤式的关键字搜索，手写涂鸦等比较新奇的功能。

当然3.0最大的变化是引入了帐户，要使用EverNote必须先申请一个帐号，然后你所有的笔记都会被同步到EverNote的网站上。你甚至可以不安装EverNote的客户端，而只用网页版的EverNote。

目前为止这些功能都是免费的，还有什么好说的呢，简直已经完美了。

EverNote 3.0现在Beta测试中，需要邀请的请留言。

Google toolbar一直是我的装机必备。而自定义按钮是它一个尤为有用的功能，这个小功能虽然简单却省了我不少时间，比如去图书馆查书、上射手网下字幕、以及查看Gmail邮件这些常用的操作现在都在鼠标一点间可以实现了，的确让人心情愉悦。但是美中不足的是对于这些非常个人化的信息Google并没有提供一个方法来备份，每次重装系统后我们都不得不重新去收集这些按钮，很不方便。这些信息无非就是一个Base16编码的图标和几个链接数据量非常小，完全可以存储到对应的Google帐号里，这样也可以鼓励大家登陆Google工具条增加产品粘合度。

既然如此，我只好自己动手了。因为Toolbar的自定义按钮信息IE和FireFox是共享的，所以它们显然是存储在某个公共的位置或注册表里。打开Filemon和Regmon过滤关键字IEXPLORE.EXE并选上Log Opens，Log Writes，Log Successes。然后在IE里生成一个自定义按钮，比如用百度的搜索框：）查看*mon们的捕获结果，可以很快发现Toolbar把信息藏在了两个地方，一个是%USERPROFILE%\Local Settings\Application Data\Google\Custom Buttons存放着一些XML格式的文件。另一个在注册表位置HKEY_CURRENT_USER\Software\Google\Google Toolbar\4.0\Options\Custom Buttons上，是一些跟前面那些XML相关的信息。经过测试只要保存了这两处的信息，就可以成功恢复所有的自定义按钮。

最后我写了一个脚本来自动执行以上操作。

@echo===================================================
@echo backup.bat 备份Google工具栏自定义按钮
@echo ===================================================
xcopy “%USERPROFILE%\Local Settings\Application Data\Google\Custom Buttons” %CD%\data\file /G /I /E /Q  /K
REGEDIT /E %CD%\data\gtb.reg “HKEY_CURRENT_USER\Software\Google\Google Toolbar\4.0\Options\Custom Buttons”

@echo=====================================================================
@echo install.bat 恢复Google工具栏自定义按钮，同目录下要有运行backup.bat生成的data文件夹.
@echo====================================================================
xcopy “%CD%\data\file” “%USERPROFILE%\Local Settings\Application Data\Google\Custom Buttons”  /G /I /E /Q  /K
REGEDIT  /s  /I “%CD%\data\gtb.reg”  “HKEY_CURRENT_USER\Software\Google\Google Toolbar\4.0\Options\Custom Buttons”

http://cid-ffe377e867258d1b.skydrive.live.com/self.aspx/Public/gtoolbarbackup.zip

   第一步当然是去掉每次开机都会弹出的“管理您的服务器”界面，直接选上左下角那个 “在登陆时不要显示此页”的小框就OK了。

不能玩3D游戏？

1. 打开显卡硬件加速。桌面右键->属性->设置->高级->疑难解答，把硬件加速的水平条拖到完全那边。
2. 开始->运行->输入dxdiag，稍等片刻打开“显示”标签，把DirectDraw加速，Direct3D加速，AGP纹理加速都启用，可以看到Win2003已经安装了DirectX9.0c，大部分的PC游戏都可以玩了。
3. 为桌面应用优化一下性能。我的电脑右键->属性->高级->高级，把处理器和内存的性能都为程序优化，然后顺手把错误报告禁用了。

安全设置。Windows 2003的默认安全级别很高，一个显然的道理系统越安全使用越不方便，接下来要做到大部分是降低系统的安全性。

1. 解除开机必须按ctrl+alt+del限制。 Win+R运行gpedit.msc ->计算机配置->Windows设置->安全设置->本地策略->安全选项->启用交互式登录：不需要按ctrl+alt+del。
2. 降低IE的安全级别。打开IE，工具->internet选项->安全->自定义级别，下拉选择安全级-中，按重置。
3. 如果装系统时没有设密码，可以按下ctrl+alt+del更改你的密码。
4. 免去每次关机都要给一个理由的烦恼。 Win+R运行gpedit.msc ->计算机配置 ->管理模板->系统->禁用显示“关闭事件跟踪程序”。
5. 开机不用输密码自动登录。rundll32 netplwiz.dll,UsersRunDll ->去掉“要使用本机，用户必须输入用户名和密码”选项旁边的勾。确定后输入用来默认登陆的用户名和密码。或者去微软PowerToy下载页面下载TweakUI来设置，建议安装TweakUI，这个小软件可以很方便的完成许多设置。

界面美化。因为是一个服务器系统，server 2003并不太注重界面的华丽，虽然我很喜欢这种简洁，但如果你想找回xp上的亲切感到话，其实只要打开出于性能考虑被默认禁止的Themes服务，server 2003完全可以在界面上和XP一模一样。

1. 运行Services.msc 找到Themes服务，双击，修改启动类型为自动，应用。这时可以按启动按钮启动Themes服务了。
2. 在桌面右键->属性->外观，可以看到在“窗口和按钮”下拉框里，除了Windows经典样式，多出了一个Windows XP样式。当然那些第三方的破解主题如UXTheme也是一样可以安装的。
3. 打开ClearType，去XP系统拷贝雅黑字体。在外观->效果这里可以打开ClearType。字体目录一般在C:\Windows\Fonts。再喜欢简洁的话，这个也一点要用上，Windows平台的文本显示，是我不能放弃它的一个很重要的原因。

还有一些默认被禁止的服务可能要按需手动打开。

1. IMAPI CD-Burning COM Service。Windows 2003自带的刻盘功能，可以在右键菜单的“发送到”里找到。
2. Windows Image Acquisition (WIA) 。照相机，摄像头，扫描仪等会用到的服务。

【参考资源】 http://win2k3.msfn.org/

每天拎着笔记本在宿舍和实验室之间奔波，需要不停地修改ip地址，很麻烦。所以写了两个脚本来自动设置。

宿舍通过DHCP服务器动态分配IP
rem ipdom.bat
netsh interface ip set address “本地连接”  source=dhcp
netsh interface ip set dns name = “本地连接”  source=dhcp

实验室需要指定静态的IP
rem iplab.bat
netsh interface ip set address “本地连接”  source=static  IP addr=172.1.15.119 mask=255.255.0.0  gateway=172.1.96.10
netsh interface ip add dns name = “本地连接”  addr = 172.1.0.1

一直对微软那个把盗版软件比作一条盘起来的毒蛇的广告记忆深刻，的确我们很难保证那些从各种渠道获得的盗版软件没有被人中途植入木马，很有可能我们在享受免费的同时主动地向别人敞开大门。如果一般的用户层软件带毒还要过杀毒软件这关的话（虽然我对杀毒软件这种事后补漏的防护手段的保护能力持怀疑态度，不停的让用户升级病毒库是一个很好的营销模式，但显然不是一种很有效的杀毒方式。）我们对操作系统安装盘里植入的系统级木马则毫无抵抗能力，如果你的网络驱动程序直接操作网卡把你的信息发往互联网你又如何能察觉。对于一个可以破解Windows正版保护机制的黑客，他其他方面的能力你也不用太怀疑，当然我只是假设有这种可能性，我相信一个真正的黑客是有道德有信仰的。但提高一点警惕总是没有错的。在你的系统上运行一下Sysinternals的sigcheck或把autoruns的Verify Code Signatures功能打开，看看有没有被修改过的系统文件。我的某OEM版XP上结果很触目惊心（好的，我承认我用了盗版，恳请盖子大叔鄙视），一堆没有通过验证的文件里，赫然有着TCPIP.SYS，这可是微软实现TCP/IP协议的驱动，原则上所有访问互联网的程序都要经过它，可是居然被修改了！我不知道修改版的会有哪些不一样（有时间IDA一下试试），但显然不会是修补了某个漏洞提升了安全性。

所以有钱还是支持一下正版吧，就算道德上的内疚可以无视，出于对自己网络生活安全的保护，我们也应该远离盗版。如果你像我一样还没有决定完全投入Linux怀抱，又是一个买不起正版Windows的穷学生的话，一个好消息微软向中国学生提供免费的Windows 2003标准版了。

不过Server版的系统当日常桌面使用还是有诸多不便的，比如live系列的应用程序无法安装，不能玩3D游戏。这些问题通过一些设置和小技巧都可以解决，而且Server版的系统稳定简洁，没有花哨的东西，很实用。我个人感觉Windows Server比XP无论在开机速度还是程序响应上都要快很多，对它非常满意。以下是我让Windows server 2003更适合桌面使用所做的配置，都记录下来放在一起，希望能为有需要的人节省一点时间。

链接Windows Server 2003的桌面化改造（二）

工具：live帐号，微软学生中心帐户各一只。
edu.cn结尾的邮箱一个。
教育网接入，身份验证用，下载ISO安装文件不限接入方式。
激活帐号后就可以开始下载了，windows server 2003 SE和Visual Studio 2008 pro还需免费申请一个正版序列号。
https://downloads.channel8.msdn.com/

更多信息http://www.cnbeta.com/articles/49766.htm

Technorati 标签: Windows server 2003

1985年，Miller和Koblitz分别独立提出了该想法。

Koblitz的论文见http://links.jstor.org/sici?sici=0025-5718%28198701%2948%3A177%3C203%3AECC%3E2.0.CO%3B2-E

椭圆曲线方程的图像并不是椭圆，取这个名字是因为它的形式和求椭圆弧线长度时用到的积分很像。

ECC因其密钥短加密速度快逐渐成为RSA的热门接替者。根据NSA的数据ECC用313位密钥的获得的安全性和RSA用4096位密钥相当，并且有着更快的性能。

可用于加密的椭圆曲线主要是模p的椭圆曲线，这种曲线上的点有这样一种性质，任意给出椭圆E上的两点P,Q可以很容易的计算出第三点R，反之则很难，并且R也在E上，如果把这种运算定义为加法运算则意味着E上的加法运算时封闭的。

如E：y^2≡x^3+4x+4(mod 5)

该E上的点是有限的，无论x取什么值，模5后都只能等于0，1，2，3，4中之一。代入x解对应的二次剩余方程即可求出对应的y。

但并非对于所有的x取值都有相应的y，当x≡3(mod 5)时，y^2≡43≡3(mod 5)无解。而x≡1(mod 5)时，y^2≡9≡4(mod 5)，解得y=2或3，所以(1,2),(1,3)为椭圆上的点。

椭圆曲线上的明文嵌入。

E：y^2≡x^3+bx+c(mod p)为椭圆曲线。

为了加密明文m（已表示为数字），把m作为x代入椭圆方程，但是因为只有1/2的机率，x^3+bx+c是模p二次剩余，有对应的y。这样的加密成功率是不能接受的，所以m需进行一定的处理，才能使m作为E上一点的X坐标值被嵌入椭圆。

Koblitz的方法是

取k，使（m+1)k<p

x=mk+j(0<=j<k)

对于j的不同取值计算x^3+bx+c是否为模p二次剩余，如果是则以点(x,y)嵌入椭圆曲线成功，如果所有的取值都非模p二次剩余则嵌入失败，但这种可能性只有（1/2)^k。

恢复数据只需要做m=[x/k]，即使m等于x/k的整数部分。

ElGamal加密系统的椭圆曲线实现。

如果A要发消息给B

B选择一条椭圆曲线E(mod p)，并取其上的一点P，和一个随机数a，计算出Q=aP，把（E,P,Q)作为公钥发送给A，保留a为私钥。

A得到B的公钥后，把消息m表示为E上的一点x（可以用Koblitz方法），并取一随机数k，计算y1=kP，y2=x+kQ，把（y1，y2）发送给B。

B通过x=y2-ay1=x+kQ-akP=x+kaP-akP,解密消息。

整个系统的秘密在于P和Q的关系。因为y1和y2是分别通过P和Q计算出来了所以它们之间的关系是P和Q之间的关系的延续，k只是作为这种关系的掩盖，并在解密过程中被消去。

椭圆曲线算法的作用在于确保在不知道a的情况下没有可能通过P和Q计算出他们之间的关系。

在这个领域我可能的研究方向：

1）并非所有的椭圆曲线都适合用于加密，选取一条安全的椭圆曲线确保安全性的第一步，这方面有很多工作可以做。

2）椭圆曲线上的明文嵌入，Koblitz的方法虽然简洁明了，但效率不高，有改进的空间。

3）标量乘法效率优化。

参考的书：

Wade Trappe, Introduction to Cryptography with Coding Theory (SE),第三章 Basic Number Theroy和第十六章 Elliptic curves