Tech

入了一个树莓派

published on

之前玩DroidQuest,把大学里没怎么听的数字逻辑全搞明白了,突然很有兴趣想动手弄点东西玩。遂入手树莓派一枚。现在只要200块出头。

照片

拿到后刷上Arch Linux,跑起来正常,可以准备买电子元件接GPIO玩了。如果能够找到4个方向运动的轮子,真想复刻一个DroidQuest里面的机器人玩哈哈。

说起来raspberry-pi的好处还是社区比较大,各种尝试都有人做,虽然做法各种粗糙,我不止一次看到3.3v的GPIO外直接接5v的设备,所以照着例子来还得小心。

Read More...

开始玩 DroidQuest

published on

这两天通过知乎发现一个神游戏:Robot Odyssey,有人在用java写了一个复刻版,叫DroidQuest。

抱着体验的态度玩了一下上瘾了啊……

游戏大概就是说,你需要借助3个机器人探索下水道恩,通过总共5个level,机器人里面长这样:

robot-inside

恩,结果就是需要通过连数字电路的方式来控制机器人,机器人里面有传感器,喷射器,天线,爪子可以供你使用,下面还有电池和开关。图中是来自游戏的tutor自带的电路,激活了爪子抓取功能,同时靠一个锁存器实现左右运动的功能…..

你还可以自己在实验室做芯片,为了过第三关的一个地方,我设计了一个遥控芯片:你可以通过控制一个机器人的天线发射信号,然后另一个机器人接收了之后再运动,这样手工操作通过了不少需要专门设计电路的地方- -

所以我现在刚刚到达了第四关。按网上的说法,第四关开始会非常有挑战,如果有幸打过去了,一定要写攻略。不过估计之前得好好学习下数字电路了…

下面是我打level2和level3时手工绘制的大地图(缩略过):

level2

level3

顺便讲一下自己做的简易chip:

  • 首先是做了一个1-bit counter:一个输入一个输出,每当输入从0变成1时输出翻转,也就是上边沿改状态
  • 然后两个1-bit counter串起来可以做成2-bit counter,再译码输出成4个信号
  • 这四个信号接机器人四个方向,同时要求天线为1的时候再运动
  • 最后就可以用另一个机器人的天线来控制这个机器人运动/停止/转向了…

如有别的在玩的人看到了,欢迎交流

Read More...

tutor真是不好读

published on

之前参加了一次Topcoder的SRM,把500pt的题目给做了。期间小心翼翼地绕开了无数trick,最后还是挂了。不过在那一次之后,我就学到了一个教训,对a除以b取下整的时候要注意负数的情况。当然这个教训不是本文的重点,我写这个事是因为比赛后我决定把这个教训记下来,但是一直没有写,直到这两天有了新的教训。想想再拖下去不像样,于是就这么写了。这个故事告诉大家,如果没有截止日期,那么什么事都很难做下去。

那么新的教训是来自哪呢?在于我最近开始研究os也就是操作系统要怎么写了。这件事得追溯到我上学的时候,在学校的二手书店里买了一本《自己动手写操作系统》,当然那个时候我兴趣广泛,这本书看了几章弄不明白就放到一边去了。我说兴趣广泛不是为了能力不足而辩解,这只是一个伏笔。我前几天在亚马逊上闲逛,看到一个日本人写的《30天自制操作系统》kindle版,立马对其产生了兴趣,于是买了下来,顺便把学校买的书从箱子中找了出来,兴致勃勃的准备开始折腾一下。

为不了解的人介绍一下,这两本书都是指南类型的书,就是有经验的人写过你说如果你要做一件事,可以先做什么,接着做什么,然后怎么样,你按照这样的步骤就可以完成这样复杂的工程了。

开始真是顺风顺水,照着书上的思路顺利的把bootloader给搞定了,但是从保护模式开始,就令人吐血了。我又懒得参考人家的代码,两本书开始讲gtd的时候,我实在是把握不住了。于是我开始了在互联网上的探索,发现了一系列优质的指南资源,比如osdev.org。通过长时间的研究,我大致把握住了下面几点:

  • cr0寄存器有一位表示是否进入保护模式
  • 保护模式下端寄存器存放的是selector,是通过gtdr这个寄存器指向的table里面的信息来将虚拟地址映射到物理内存地址的,然后gtd中间每一项有base limit flag等字段来描述这个段的信息

当然这些内容对于本文来说是无关紧要的,有意思的地方在于所有这些文章全部简单的描述了一个gtdr之后就给出了类似下面这么一个代码:

   LGDT  [gdtr]
reloadSegments:
   ; Reload CS register containing code selector:
   JMP   0x08:reload_CS ; 0x08 points at the new code selector
.reload_CS:
   ; Reload data segment registers:
   MOV   AX, 0x10 ; 0x10 points at the new data selector
   MOV   DS, AX
   MOV   ES, AX
   MOV   FS, AX
   MOV   GS, AX
   MOV   SS, AX

总之这之后一切就设定好了。我就特别悲伤的对着这段代码研究了很久,先是好不容易理解了这一坨代码其实是设置段寄存器:把cs改成0x08,把其余的改成0x10。这些描述给我留下了无尽的谜团,比如到底是如何通过gtd寻址的,在没有修改cs之前的代码怎么执行的,如果在这些指令执行到一半,我在中间干点别的事情,那么是处于什么情况。这些疑惑一直困扰着我,简直就不能接着干下去。当然这些疑点最终还是被我搞明白了。

导致我写这篇文章的是搞清楚gtd地址翻译的方法。一开始我看到描述符里有一个base字段,我就非常努力的想理解其含义。首先我是这样想的:如果我的链接器认为,程序将会加载到0x40000000这个地址,那么它里面的指令就都是根据这个地址来的,比如一个全局变量,可能就在0x41000000,而实际在物理内存中可能就是在0x010000000那么假如我的base写的是0x40000000,对应到物理地址就应该减去base了。但我又有些犹豫,觉得按照各种指南中模糊的描述来看,也有可能是加上base。这个疑问很麻烦,除非写一个内核代码来测试,但在那之前,我有幸找到了答案。便是通过Intel® 64 and IA-32 Architectures Software Developer Manuals,终极文档。里面写的清清楚楚:

The base address plus the offset thus forms a linear addressin the processor’s linear address space.

还附带了若干图例,把整个一套相关的内容都解释了,堪称完美,让我瞬间为自己到处找tutor和看别人笔记浪费的无数时间感到可惜。这样细想一下,原来不是通过减去0x40000000,而是加上0xC0000000来实现的。于是我得到了一个教训:有问题记得看手册

我必须要说一件事,写指南是一件很麻烦的事情。尤其是为初学者所写的指南,我已经在计算机别的领域有怎么也还算丰富的经验,然而初次涉及内核的开发,依然面对了重重的困难。作为一个有经验的作者,往往不容易回忆起自己刚开始摸索一件事物的时候面对的重重困难。可以回想你开始学习编程的时候,各种各样眼花缭乱的交错的概念理解起来多么困难。

而如果是一个像我这样希望对每一步的细节都非常清楚的读者,恐怕只能寄希望于作者多多花费心血讲解细节,亦或是及时指出可靠的参考材料。一个指南假如仅能通过复制粘贴然后改改其中参数的方法来使用,那么其学习价值恐怕很难得到保证。

所以我希望有志于编写指南传播经验的同学可以谨慎地进行自己的工作,让阅读的人能更好的理解。我如果有机会写点什么指南的话,必将朝着让大家理解的方向多努力。

Read More...

对长期纠结的PL和CC相关内容做一个小结 2013

published on

回顾一下在编程语言和编译原理方面的各种纠结,没有什么记录,凭记忆写。

我从高中毕业开始使用C++,到现在挺多年了。语法是靠高中看数据结构的书看会的,后来到了大学里面喜欢泡图书馆,大一时靠读了不少C++的经典奠定的基础,像是Effective C++,Exceptional C++等系列,有蹭着和学软件工程的同学讨论项目,自己翻一翻设计模式什么的书,学会了一点怎么用C++写项目,算是我第一个用着很熟悉的语言了(之前用过VB Pascal,均仅限于学习写所要的程序的必要的知识部分)。

在大二的样子,出于学习算法的目的也要考虑编译方面的算法,于是在图书馆了翻了不少相关的书,诸如传说中的三件套:龙书,虎书,鲸书,当然还有一些其他的玩意。比较喜欢的是虎书,所以借过好几次,慢慢的读。看的是虎书的C语言版,不过这就是按照ML语言版改写过来的,对象都是申请了之后不考虑释放的,里面实现的语言的语法也是参考者ML来的。我从那里面学到了不少东西,而且第一次注意到写程序还可以使用immutable的数据结构。也喜欢上了ML的语法。

再后来因为自己写游戏的原因,学习了lua语言,反反复复的用,把大部分特性都搞的差不多明白了,后来干脆把源码也全部看了一遍。lua这条线的话,后来发现了LuaJit这样一个玩意,遂对Jit产生了兴趣,在网上找了一些paper和code看了一下,之后又读了intel和amd x86-64芯片的手册,可是最后还是没有自己去写一个。

因为经常和lua拿来放在一起讨论的Google所做的JavaScript引擎v8,所以其相应的代码也拖下来读了一些,结果学了不少C/C++中的宏的使用技巧。

另外在学校的图书馆里找到了一本转本讲垃圾收集的书,里面对各种方法的各种讨论让我大开眼界,每一种现在用的收集策略都讨论了各种优化方法。我才意识到,原来这东西有这么多人研究啊。后来在LuaJit的Wiki上也发现一篇讲gc的内容,看起来还在等人赞助他加进去。

之后因为看两大名作SICP和CSAPP的缘故,接触到了Scheme,当然这不是最早接触的Lisp,最开始是高中的时候开始学着用Emacs,那是就摸索着写了一点Emacs Lisp。所以用Scheme的时候没有什么语法不适应的障碍,反而看SICP学了不少函数式编程的知识,当时触动特别的大,因为是第一次直接的接触到函数式编程相关的内容。

后面因为黑客与画家的原因看过一点Common Lisp,实在是不喜欢就弃了。所以Lisp这条路线基本一直是喜欢scheme的。scheme这条线下来,先是发现了有continuation和cps这样的东西,但是靠网上依稀的资料不是很明白,直到后面看了EOPL和PLAI,自己写解释器,慢慢就搞明白了。看到Y-combinator,然后自己推导过后,也学会了。后面也专门看过用Scheme的实际项目:Lilypond,可惜量太大,实在没耐心分析到最后。宏是最后在Cousera上选了一门Programming Language的课,听讲义学的。我个人绝对是听觉型的学习者,特别喜欢听老师讲,但老师太难找了,还是不得不努力的看了不少书。

Scheme这边发展后后面,对于怎么实现函数式语言的优化编译器又产生了性质,还找了一些书和paper,讲怎么写函数式语言的编译器,或者诸如对于动态语言,怎么通过尽量的静态分析,可以消除大部分运行时的类型检查。

还有一条线是考虑学一点实用的语言,于是看了Python和Ruby,Python没怎么看书,就随便看看tutor,看看别人的程序,然后慢慢居然也用熟了,Ruby正儿八经看了影印版的The Ruby Programming Language,最后还是没记住多少,学语言果然还是靠多写。再想想看个速度快点的,于是学了Go,看了tutor,最后还是没怎么用。一般还是C++/Python使用最多。

再有一条线就是几度尝试Haskell,尝试着看了一些资料,Tutor或者书。觉得实在是一门麻烦的语言,平时用来解决一般的问题都要采用这样的思路没必要,故没能更近一步。

然后再回到C++吧,后来网上看过不少C++11的资料,然后看到了公开课cppgm,可惜知道的比较晚,人家已经开始了,看到其使用的材料的是C++的标准。想到自己从没看过C++的标准,于是网上搞了一份,不过一直没什么机会想起来把他看下去。

最后是最近在Coursera上搞了一门PL的课,认真学了一点ML的语法,复习了scheme/Racket,学会了在scheme中怎么写宏,然后又复习了一点ruby的语法,发现忘了不少。期间还有纠结在要不要去学scala,要不要自己再写一个新语言的编译器,啊这些恐怕要留待明年继续纠结了。

写完了之后总觉得还漏了些什么,诸如LLVM之类的,反正估计永远都难