All Posts - 太阳神上的博客

更新GCC和Glibc

　　前几天上linuxfans.org，发现sejishikong已经更新了GCC 4和Glibc2.7，于是下回了RPM包，先更新glibc，以前编译和运行Linux程序，总是抱怨glibc的版本太低，很多软件都不能运行，而这个库又极为重要，不能随便更新，稍有不慎就会系统无法使用。这次是MagicLinux的官方补丁，应该可以放心地安装了。
　　不过下载RPM包后，如何安装就成了一个问题，一般的RPM包都是rpm -ivh 完成安装，rpm -Uvh完成升级，可是glibc太重要了，Linux里几乎所有的程序都依赖于此库，能动态地更新吗？我怕直接更新有问题，就犯了一个严重的错误，居然用rpm -e glibc --nodeps来卸载，结果一下子系统里什么程序都不能使用了。完了，我只好重新启动系统，用MagicLinux的急救盘想chroot来把RPM包装上，结果根本不行。chroot说/bin/sh不存在，可是这个程序明明存在的，这下惨了。我最终想了一个方法，就是把原先的rpm包里的东西解压出来，然后全部复制到根分区里。事实证明，此方法可行！
　　后来，我在那个帖子后面找到里最方便更新glibc的方法，就是使用rpm的--aid选项，这个选项可以成功地更新glibc，而且不用重启。我按这一方法果然可行。Linux真强大，原来连安装glibc这样的库都可以不用重启。
　　之后，我启动了原来需要glibc2.6以上版本才能运行的Linux版QQ，说实话，不满意，腾讯就折腾出这样一个东西，比eva差远了。
　　后来，我接着更新了gcc，原来是gcc3，现在是gcc4，gcc4相对于gcc3，编译的速度好像并没有什么本质的上升，不过好像更严格了，而且里面的出错信息全成了中文。GCC出错信息变中文，感觉有点怪怪的，里面的话听起来总觉得有些别扭。用它编译fltk时，它还出一个很奇怪的警告：“提领类型双关的指针将破坏强重叠规则”，这句话完全不知道它说什么，感觉还有点搞笑。

 

Linux gcc Glibc Comments(0) 2008-08-19 07:37PM

一个算24点的算法

　　最近，我用Lua写了一个算24点的算法，这个算法的思想很简单，就是不断穷举表达式，然后计算每个表达式的值是否为24。如果为24，则输出。问题的难点在于如何穷举表达式，我的做法是将要处理的数和另外穷举出的运算符组成一个含有七个元素的数组（四个操作数，三个操作符），然后遍历这个数据的全排列，将每个排列看成一个逆波兰式，如果计算成功，则将逆波兰式再转成中辍表达式输出。这个算法有一个明显的缺点，它会产生很多冗余的式子（即形式不同，但运算实质相同）。

  1. #!/usr/bin/env lua
  2.  
  3. -- used for store four points
  4. array={}
  5.  
  6. -- reverse the whole array from first to last
  7. function array.reverse(this,first,last)
  8.         first = first or 1
  9.         last = last or table.maxn(this)
  10.         while first < last do
  11.                 this[first],this[last]=this[last],this[first]
  12.                 first=first+1
  13.                 last=last-1
  14.         end
  15. end
  16.  
  17. -- this algorithm is modified from the C++ STL
  18. -- change array to next permutation and returns true
  19. -- return false if the current is the last permutation
  20. function array.next_permutation(this,first,last)
  21.         local len=table.maxn(this)
  22.         if len==0 or len==1  then
  23.                 return false
  24.         end
  25.  
  26.         first = first or 1
  27.         last = last or len
  28.        
  29.         local i=last
  30.         while true do
  31.                 local ii=i
  32.                 i=i-1
  33.                 if this[i] < this[ii] then
  34.                         local j=last
  35.                         while this[i] >= this[j] do
  36.                                 j=j-1
  37.                         end
  38.                         this[i],this[j]=this[j],this[i]
  39.                         this:reverse(ii,last)
  40.                         return true
  41.                 end
  42.  
  43.                 if i==first then
  44.                         return false
  45.                 end
  46.         end
  47. end
  48.  
  49. -- show the array with space seperated
  50. function array.show(this)
  51.         for _,i in ipairs(this) do
  52.                 io.write(i,' ')
  53.         end
  54.         io.write('\n')
  55. end
  56.  
  57. optable={"+","-","*","/"}
  58. opfuncs={}
  59. opfuncs["+"]=function(a,b)
  60.         return a+b
  61. end
  62.  
  63. opfuncs["-"]=function(a,b)
  64.         return a-b
  65. end
  66.  
  67. opfuncs["*"]=function(a,b)
  68.         return a*b
  69. end
  70.  
  71. opfuncs["/"]=function(a,b)
  72.         if b==0 then
  73.                 return nil
  74.         else
  75.                 return a/b
  76.         end
  77. end
  78.  
  79.  
  80. -- stack class for calculation
  81. function Stack()
  82.         local stack={}
  83.         stack.push=table.insert
  84.         stack.pop=table.remove
  85.         stack.size=table.maxn
  86.         stack.bottom=function(this)
  87.                 return this[1]
  88.         end
  89.         return stack
  90. end
  91.  
  92. -- calculate from polish notation
  93. function array.eval(toeval)
  94.         local stack=Stack()
  95.         for _,v in ipairs(toeval) do
  96.                 local op=opfuncs[v]
  97.                 if op then
  98.                         if stack:size() <2 then
  99.                                 return nil
  100.                         end
  101.                         local b=stack:pop()
  102.                         local a=stack:pop()
  103.                         local result=op(a,b)
  104.                         if result then
  105.                                 stack:push(result)
  106.                         else
  107.                                 return nil
  108.                         end
  109.                 else
  110.                         stack:push(tonumber(v))
  111.                 end
  112.         end
  113.  
  114.         return stack:bottom()
  115. end
  116.  
  117. -- precedence table, "n" is number
  118. precedence={
  119.         ["+"] = 1;
  120.         ["-"] = 1;
  121.         ["*"] = 2;
  122.         ["/"] = 2;
  123.         ["n"] = 3;
  124. }
  125.  
  126. -- convert from polish expression to normal expression
  127. function array.show_expr(this)
  128.         local strStack=Stack()
  129.         local typeStack=Stack()
  130.        
  131.         for _,v in ipairs(this) do
  132.                 if opfuncs[v] then
  133.                         local b=strStack:pop()
  134.                         local a=strStack:pop()
  135.  
  136.                         local bp=precedence[typeStack:pop()]
  137.                         local ap=precedence[typeStack:pop()]
  138.                         local vp=precedence[v]
  139.                        
  140.                         if ap<=vp then
  141.                                 a="("..a..")"
  142.                         end
  143.  
  144.                         if bp<=vp then
  145.                                 b="("..b..")"
  146.                         end
  147.  
  148.                         strStack:push(a..v..b)
  149.                         typeStack:push(v)
  150.                 else
  151.                         strStack:push(v)
  152.                         typeStack:push("n")
  153.                 end
  154.         end
  155.         print(strStack:bottom())
  156. end
  157.  
  158.  
  159. -- get table copy(contains its methods)
  160. function array.copy(this)
  161.         local copy={}
  162.         for index,value in pairs(this) do
  163.                 copy[index]=value
  164.         end
  165.         return copy
  166. end
  167.  
  168. -- the main method to calculate 24 points
  169. function array.calc(this)
  170.         local order=1
  171.         for i=1,4 do
  172.                 for j=i,4 do
  173.                         for k=j,4 do
  174.                                 local toeval=this:copy()
  175.                                 table.insert(toeval,optable[i])
  176.                                 table.insert(toeval,optable[j])
  177.                                 table.insert(toeval,optable[k])
  178.                                 table.sort(toeval)                       
  179.                                 while true do
  180.                                         if tostring(toeval:eval())=="24" then
  181.                                                 io.write(order,": ")
  182.                                                 toeval:show_expr()
  183.                                                 order=order+1
  184.                                         end
  185.  
  186.                                         if not toeval:next_permutation() then
  187.                                                 break
  188.                                         end
  189.                                 end
  190.                         end
  191.                 end
  192.         end
  193. end
  194.  
  195. for i=1,4 do
  196.         if not arg[i] then
  197.                 io.stderr:write("Please input at least four arguments!\n")
  198.                 return 1
  199.         end
  200.  
  201.         local num=tonumber(arg[i])
  202.         if not num then
  203.                 io.stderr:write("Arguments must be numbers\n")
  204.                 return 2
  205.         end
  206.        
  207.         if num<1 or num > 13 then
  208.                 io.stderr:write("Number must in [1,13]\n")
  209.                 return 3
  210.         end
  211.  
  212.         if math.floor(num)~=num then
  213.                 io.stderr:write("Number must be an integer!\n")
  214.                 return 4
  215.         end
  216.  
  217.         table.insert(array,arg[i])
  218. end
  219.  
  220. array:calc()
  1.  

    2.  

     

Algorithm Algorithm 24 Comments(0) 2008-06-29 01:13AM

重新编译Linux内核

　　最近我们在搞系统软件课程设计，一共有七个实验，其中第一个不用实际做东西，也就是一共有六个实验需要做，我一周多一点就完成了三个实验，现在只剩下三个了。我估计这个学期还没结束就可以全部搞定了。其中有一个实验是要为Linux添加新的系统调用，这其中就需要重新编译Linux内核。
　　虽然我用Linux也有不短的时间了，但是重新编译内核还是头一回。我下载的版本是Linux 2.6.25，这个内核比我原来的内核还新一些。我照着网上说的，先make xconfig，Linux内核就会利用源代码中一个基于Qt 3.x的源码配置器的源代码还编译生成一个源码配置器，这个源码配置器还很复杂，选项很多。我先按照它的默认设置。生成了一个配置文件。然后敲入make，然后开始编译了，Linux内核编译的时间非常长，大概有一个小时吧。（其实Qt 4.4更长，达四个多小时）。
　　编译完内核，就会在源代码根目录下生成一个叫vmlinux的文件，那就是Linux的内核了，再make bzImage，这时将会生成一个bz2格式压缩的内核，除了内核本身处，还得编译内核的模块，make modules就行了，然后再写make modules_install就可以了。说起来简单，做起来其实有一番麻烦的。即使我每一步都小心翼翼，总是有一些问题。事实上，从网上搜索到的很多都不能完全照搬，例如很多网上资料说到先make dep，但是我输入这一命令时，程序却提醒我已经不必了。而且我下载的安装将已经非常智能了，我原先以为还要手工做初始化内存盘映像，还要手工复制内核并修改grub的配置文件，现在已经都不需要了，程序会自动生成初始化内存盘映像和复制文件，还会自动将新的内核加入grub的引导菜单。
　　现在想起来网上的资料真是很乱，搜来搜去也就那几篇，而且转贴的网站一般都有一堆恶心的广告，排版又非常差。
　　

Linux kernel linux Comments(0) 2008-05-19 02:14PM

GCC对标准C的一个奇妙扩展：词法定界

 

   最近在写Tenshi的解释器，觉得解释器也算是一个比较特殊的程序。如果能用gcc编译器提供的一些扩展，可能会提高程序的可读性与效率，至于移植性，由于gcc本身就是移植性很好的编译器，所以不大担心其在其它平台在的使用。我认真看了一下GCC的使用手册，重点看了一些GCC对C语言的一些扩展，有很多很有用，如把标签作为普通值，然后用goto任意跳转，还有designator来初始化结构体与共用体，case的范围扩展等等。其中有一个很有趣，就是GCC可以对C语言进行词法定界。

  据文档说，对此，编译器使用的方法叫“trampoline”，并给出了trampoline的pdf说明文档的地址，我已下载，准备好好看一下，了解一下它的奇妙之处。

测试代码如下： 

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef const char * (*GetName)();
  5.  
  6. struct Person{
  7.         const char *name;
  8.         GetName getName;
  9. };
  10.  
  11. typedef struct Person Person;
  12.  
  13. Person *NewPerson(const char *name){
  14.         Person *person=(Person*)malloc(sizeof(Person));
  15.         person->name=name;
  16.         const char *getname(){
  17.                 return person->name;
  18.         }
  19.         person->getName=getname;
  20.         return person;
  21. }
  22.  
  23. int main(){
  24.         Person *moligaloo=NewPerson("Moligaloo");
  25.         printf("%s",moligaloo->getName());
  26.         free(moligaloo);
  27.         return 0;
  28. }
  29.  
  30.  
  31.  

 

C gcc extension Lexical Scoping Comments(1) 2008-05-11 07:26PM

KDE4的体验

   最近，我从网上下载了以KDE 4为桌面环境的Kubuntu 8.04。其实之前我也用过其它版本的Kubuntu，但是印象不是很好，那个宽屏的分辨率的问题一直还是存在的。上次的Kubuntu 7.10，它也自带了KDE 4，但是分辨率太差，而且软件也极少。所以用了它的LiveCD一看就决定不装了。
  后来，我觉得KDE 4毕竟是KDE 3的下一代版本，而且还有很多新的特性，又看到Ubuntu又有新的版本了，看来很多KDE 4的一些基本问题（如分辨率）也应该得到解决了吧。于是我从网上下载了Kubuntu 8.04的带KDE 4的版本。
  总的来说，第一印象不错。分辨率的问题得到了解决，我随便测试了一些程序，运行得还不错，就把原来装Ubuntu 7.10的分区装成了Kubuntu 8.04。从登录界面到桌面所花的时间很少。比Magic Linux 的KDE3 还要快多了。它的控件大多以圆角矩形为主，灰色的金属基调，默认的桌面空无一物，而下方的任务栏则大得很，点KMenu，新的菜单是KDE 4的一大特色，但是从网上的评论来看并不是很好，很多人非常不喜欢，其实我也不喜欢。同样的是经典的KMenu的替代品，一个叫KBFX的程序就好用得多。
  Kubuntu的汉化问题刚开始有问题，明明从网上下载了一堆中文支持语言包，可是进入后还是英文界面，从网上一查才知道还得用apt-get命令装一个东西才能解决。新的系统默认自带了文泉驿字体。文泉驿的正黑体不是很好，但点阵宋体很不错。所有的中文字体里，它数是最清晰的了。不过它的英文字体看上去马马虎虎。虽然能看，但还不到看着舒服的感觉。

Linux KDE4 Comments(0) 2008-04-28 05:42PM

更新的防止游戏修改的算法

　　上次我把程序发给了另外一个高中同学，他似乎并没有花多少时间就找出来了。但是看他给我的描述，似乎找到不是真正的存放关键数据的内存。还是给廖传政同学修改的差不多，由于要通过画矩形来显示结果，所以必定要提供一个变量来表示真实的数据。如果放在一个函数的局部变量里，由于局部变量是存放在栈中的，只要调用堆栈相同就可以找到。所以放在堆空间更好，但是我却忽略了一点。如下：

  1. void *p=malloc(100);
  2. free(p);
  3. p=malloc(100)

　　这个式子中，p在free前后的值很多情况下是相同的，这样，即使在堆空间，也可能完全相同。为了防止这种情况，我又使用了随机得到一个堆内存的方法，为了防止栈空间也相同，我同样使用了随机层次的递归，这样一来，我觉得应该会提高破解的难度。更新的代码如下：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5.  
  6. #include <SDL/SDL.h>
  7.  
  8. SDL_Surface *screen = NULL;
  9. int blood;
  10.  
  11. int *encode;
  12. int *decode;
  13. SDL_Rect *rects;
  14.  
  15. int index_of(int array[],size_t size,int value){
  16.     int index;
  17.     for(index=0;index<size;index++){
  18.         if(array[index]==value)
  19.             return index;
  20.     }
  21.     return -1;
  22. }
  23.  
  24.  
  25. void begin_game(){
  26.     srand(time(NULL));
  27.     encode=(int *)malloc(1024*sizeof(int));
  28.     decode=(int *)malloc(1024*sizeof(int));
  29.     rects=(SDL_Rect *)malloc(1024*sizeof(SDL_Rect));
  30.    
  31.     int i,r;
  32.     for(i=0;i<101;i++){
  33.         r=rand()%101;
  34.         if(index_of(encode,i,r)==-1)
  35.             encode[i]=r;
  36.         else{
  37.             i--;
  38.             continue;
  39.         }           
  40.     }
  41.    
  42.     for(i=0;i<101;i++){
  43.         decode[i]=index_of(encode,101,i);
  44.     }   
  45.    
  46.     blood=encode[100];
  47. }
  48.  
  49. void end_game(){
  50.     free(encode);
  51.     free(decode);
  52.     free(rects);
  53. }
  54.  
  55. void draw (int layer){
  56.     if(layer>0)
  57.         return draw(--layer);
  58.    
  59.     Uint32 color;   
  60.     color=SDL_MapRGB(screen->format,0,0,0);
  61.     SDL_FillRect (screen, NULL, color);   
  62.     color = SDL_MapRGB (screen->format, 0xFF, 0, 0);
  63.    
  64.     SDL_Rect *rect=&rects[rand()%1024];
  65.     rect->w = decode[blood]*5;
  66.     rect->h = 20;
  67.     rect->x = 100;
  68.     rect->y = 100;
  69.     SDL_FillRect (screen, rect, color);
  70.  
  71.     SDL_Flip (screen);
  72.     SDL_Delay (10);
  73. }
  74.  
  75.  
  76.  
  77.  
  78. int main (int argc, char *argv[]){
  79.     char *msg;
  80.     int done;
  81.    
  82.     SDL_Init (SDL_INIT_VIDEO);
  83.     atexit (SDL_Quit);
  84.  
  85.     screen = SDL_SetVideoMode (640, 480, 16, SDL_SWSURFACE | SDL_DOUBLEBUF);
  86.     SDL_WM_SetCaption ("SDL MultiMedia Application", NULL);
  87.     begin_game();
  88.    
  89.  
  90.     done = 0;
  91.     SDL_Event event;
  92.    
  93.     while (!done){
  94.         SDL_WaitEvent (&event);
  95.         switch (event.type){
  96.             case SDL_KEYDOWN:{
  97.                 switch(event.key.keysym.sym){
  98.                     case SDLK_UP:blood = decode[blood]+10>100 ? blood : encode[decode[blood]+10];break;
  99.                     case SDLK_DOWN:blood = decode[blood]-10<0 ? blood : encode[decode[blood]-10];break;
  100.                 }
  101.             }
  102.                 break;
  103.             case SDL_QUIT:
  104.                 done = 1;
  105.                 break;
  106.             default:
  107.                 break;
  108.         }
  109.         draw (rand()%10);
  110.     }
  111.    
  112.     end_game();
  113.  
  114.     return 0;
  115. }
  116.  

Algorithm Algorithm Comments(0) 2008-04-25 10:32PM

防止游戏修改的一个小算法

　　前几天我看到廖传政又在修改游戏，于是就给他较劲，故意编个游戏来让他修改不了。据他说，假如要让血槽不动，一般是找到内存变化的地方，然后锁定就是了。从这一点出发，我想到如果表示内存变化的那个地方完全没的规律，那么就比较难以查找了。
　　我的想法是，真实的数据不能直接放在内存中，而是代之以一个神秘的数值，这个神秘的数值也完全零乱，也就是说血条上升或下降时，这个值会变化，但不一定也是上升或是下降，也是就他们之间不存在简单的线性关系，更进一步说，如果把这个神秘数与真实数的对应关系是一个函数的话，那这个函数是非线性的，其实光线性还不够，而且要是找不出单调的区间。但是它们之间又要可逆，就是要找出一个可逆的非单调函数。
　　我的基本思想是，假如要加密的是0到100之间的整数，那么就先生成把0到100随机存放到一个encode数组，作为加密的数组，例如一个真实数56，它所对应的加密数就是encode[56]，然后产生一个解密数组，分别存放0到100在encode数组中的索引，也就是for any i in 0..100,encode[decode[i]]=i。如果把encode看成是一个函数，那它的逆函数就是decode。
　　真正在内存里保存的数都是那个“神秘数”，而真实数都得通过decode数组才能读出，通过encode来写，由于加密和解密的部分都只是几次寻址操作，所以效率并不低，而且我们只对关键的数值进行加密。其它不管。
　　这个算法我给他做了以后，他算是半个成功了，因为找到了那个显示血槽对象的相关内存，但是真正存放数据的地方却没有找到。本来游戏是用Irrlicht写的3D，很占内存和CPU，下面是我用SDL改写的，完全只保留了最基本的演示：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5.  
  6. #include <SDL/SDL.h>
  7.  
  8. SDL_Surface *screen = NULL;
  9. int blood;
  10.  
  11. int *encode;
  12. int *decode;
  13.  
  14. int index_of(int array[],size_t size,int value){
  15.     int index;
  16.     for(index=0;index<size;index++){
  17.         if(array[index]==value)
  18.             return index;
  19.     }
  20.     return -1;
  21. }
  22.  
  23.  
  24. void begin_game(){
  25.     srand(time(NULL));
  26.     encode=(int *)malloc(1024*sizeof(int));
  27.     decode=(int *)malloc(1024*sizeof(int));
  28.    
  29.     int i,r;
  30.     for(i=0;i<101;i++){