帅云霓's blog

今天不小心看了电视的一个游戏栏目，叫超市大赢家，规则是在有限时间里面，装满一购物车的商品，使其总价格最高。作为电视节目自然是要在法律法规的范围内尽量争取收视率的。那么，游戏节目的收视率，自然同娱乐性和不确定性相关的。

在计算科学上，有一个难题叫“背包问题”。它的定义：我们有n种物品，物品j的体积为V_j，价格为p_j。我们假定所有物品的重量和价格都是非负的。背包所能容纳的最大体积为V。

如果每个物品只能选择0或1个，这叫做0-1背包问题；如果物品可以选择n个以内，叫做有界背包问题；如果物品可以无限选择，那么这叫做无界背包问题。

显然地，这个电视游戏节目的本质，就是求一个无界背包问题的最优解。购物车的体积是有限的——它就是背包问题的背包。

那么，让程序员去玩这个游戏，是不是稳操胜券呢？

答案是悲观的。因为，这个问题是一个NP完全问题！换句话说，它不能找到时间复杂度为多项式的算法。

由于背包问题的这个性质，它在密码学中有相当的应用价值。

VISIO画的。不知道怎么弄上来。

先放在附件，回头请某人吃饭看能不能从他嘴里问出来。

顺便在此求人品希望下周考试顺利................................................................

一弯月如勾 一语似还羞 一颦思美人 一影上西楼

一江绕洲头 一身立寒秋 一刀斩雷破 一枪挑风喉 一骑踏关雄如铁 一掌击水遏飞舟 一舞长缨苍龙束 一羽苍天竟自由 一胸意气点江山 一生粪土万户侯

一风扫环宇 一病天知否 一声汽笛肠欲断 一抛热泪何无由 一哭心痛失骄杨 一飏直上重霄九 一雨倾盆驱虎豹 一眼向洋小寰球 一邦六亿尽尧舜 一抹瘟神退九州 一挥长征从头越 一心只为百姓谋

一波碎月影 一转离清幽 一夜尽去心中病 一剪寸断金闺愁 一朝遍览烽烟地 一腔热血写春秋

31.
Q: 异常和中断有什么区别？
A: 中断是异常的一种，占用0号异常。中断是异步发生的，一般由硬件事件触发(如某GPIO引脚的电平跳变)，和指令执行阶段无关。而异常是指令触发发生的，也就是同步发生的。

32.
Q: 什么叫“精确异常”？
A: "精确异常" 的原文是precise exception。precise这个词其实有“穷讲究”的意思。在这里指的就是：当异常发生时，已经执行完memory阶段操作的指令均有效，未执行到该阶段的指令，在流水线中一律丢弃。该异常的触发者为该条指令。

33.
Q: 对于TLB miss/Address error这样的异常，实际上为什么不会写入指令中的地址呢？
A: 因为这个时候指令只执行完ALU阶段，还没到Memory，所以被丢弃了。从处理器设计的角度来看，这种非法指令本身也不该生效。

34.
Q: 发生异常的时候，是不是会进入内核态？
A: 是的。当然如果原本就在内核态，那么还是会在内核态。一般来说，操作系统通用的进入内核，是通过一条syscall指令，产生类型为0x08的异常来实现的。

35.
Q: 我想知道，breakpoint, syscall和trap三种异常都是特殊指令触发的，它们有什么区别？
A: 一般说来，syscall指令是用于一般性的系统调用进入内核，类似于x86的调用门。
breakpoint是程序错误处理，例如，mips的除法指令，如果除数为0，会造成不确定的结果。编译器在对除法表达式进行处理的时候，就做一个判断，如果除数为0，则执行指令：break 0x07。如果运行时出现了除以0，那么，break 0x07这条指令会抛出一个breakpoint异常，子类型为0x07——这样，程序员在debug的时候看见这个异常信息，就可以判断，程序中除数出现了0。

20.
Q: CP0是干嘛的？
A: CP0是协处理器0，Co-Processor 0的缩写，MIPS最多可以支持4个协处理器，其中CP0是强制要求实现的，用于处理器的状态控制等。它包括MMU、异常控制、Cache控制等功能。

21.
Q: MIPS的其他协处理器都有什么呢？
A: 这个和具体厂商的实现有关系了。CP1是浮点协处理器，是可选的，CP2和CP3是厂家自定义的。

22.
Q: CP0里面都有哪些寄存器？一般用在什么场合？
A: CP0有32个寄存器，一般操作系统的内核才会接触到它们。主要有MMU类、异常控制类、断点控制类等。

23.
Q: 这几类寄存器各有哪些呢？
A: MMU相关的，有Index,Random, EntryLo0, EntryLo1, Context, EntryHi, MageMask和Wirds几个。具体用途介绍MMU的时候会提到。
异常控制相关的有Status, Cause, EPC, BadVaddr等。
断点控制的有Count, Compare, WatchLo, WatchHi等。
此外，还有PRId，用于确定CPU的类型；
LLAddr, 用于原子锁指令；
Config, 用于配置处理器。

24.
Q: 对CP0寄存器如何访问呢？
A: 有专门的指令访问。32bit读：
mfc0 rs, /*Move from co-processor 0*/
64bit读：
dmfc0 rs, /*Double move from co-processor 0*/
32bit写：
mtc0 rs, /*Move to co-processor 0*/
64bit写：
dmtc0 rs, /*Double move to co-processor 0*/

25.
Q: 对于CP0寄存器，如果只想修改其中的几个bit，该怎样做？
A: 只能先读取到GPR中，修改后写回。
如：
mfc0 t0, SR
nop
and t0, BIT_MASK_ALPHA
or t0, BIT_MASK_BETA
mtc0 t0, SR
nop

26.
Q: 为什么要在mfc和mtc后面插入一个nop指令？
A: 这是为了避免CP0 hazard，简单地说就是执行完mfc或mtc指令之后，有可能要等待一条指令的时间，数据才真正读取或写入到寄存器之中，在这个过程中如果修改相应寄存器会导致错误的结果。

27.
Q: 为什么会有hazard现象？

11.
Q: MIPS的内存空间有多大？
A: 在32-bit模式下是4GB，用户态可以使用的空间是2GB。

12.
Q: 用户态是使用哪部分内存？
A: 虚拟地址0x00000000-0x7fffffff的2GB，叫做user space, mapped & cached.

13.
Q: 什么是用户态，还有哪些别的状态呢？
A: MIPS除了用户态还有内核态，在内核态下可以访问全部资源，但用户态只能访问部分，如CP0、MMU等，用户态是不可以访问的。

14.
Q: 那么，怎样从用户态进入内核态呢？
A: 一般的正常渠道是执行syscall指令。另外还有trap/brackpoint等指令，会引发相应的异常，进入内核态。当然程序错误引起的异常(如非对齐地址访问、未映射的地址访问)也会引发异常，进入内核态。

15.
Q: 在内核态下可以访问多大的内存空间呢？
A: 4GB，但是从0x80000000到0xBFFFFFFF有特殊用途。0x80000000到0x9FFFFFFF，和0xA0000000到0xBFFFFFFF这两段地址，硬件上指向同一段物理地址，0x00000000到0x1fffffff。

16.
Q: 为什么要这样做？
A: 0xA0000000到0xBFFFFFFF是不经过Cache访问的，可以保证在上电时就可用，并且，作为硬件IO寄存器映射地址时，不会被cache 扰乱。MIPS的上电启动地址，0xBFC00000就在这段内存中。而0x80000000到0x9FFFFFFF这段地址是经过Cache映射的，内核代码段和堆栈往往放在这一段内存，以保证访问和执行速度。

17.
Q: 我的硬件工程师将bootrom连接到总线的0xBFC00000地址了，为什么系统不能启动？
A: 0xBFC00000是逻辑地址(程序中的地址)，对应的物理地址(将逻辑分析仪连接在总线上，捕捉到的地址)是0x1FC00000。

18.
Q: 那么，0xC0000000到0xFFFFFFFF的地址空间是干嘛的？
A: 可以作为内核使用的内存，比如kmalloc之类的函数分配使用。这段内存是通过MMU和TLB映射的。

19.

最近问我MIPS体系结构相关问题的人越来越多，在这里小结一下。
一般在职业有段者水平的MIPS体系结构问题，都能在这里找到答案。

1.
Q: MIPS有多少一般用途的寄存器？
A: 32个。

2.
Q: 我在看反汇编代码的时候，看到一些寄存器名叫zero, a1, a2...还有sp, ra这样的名字。为什么给他们起这些名字呢？
A: MIPS的通用寄存器中，按照编译器的通常的约定，某些寄存器是做专门用途的，比如sp就是堆栈指针，ra是函数调用的返回地址等等。当然你也可以不按照这些约定编程，例如用$2存放堆栈指针，$3存放返回地址，但这样的程序，和标准库链接就不能工作了。

3.
Q: 为什么MIPS的SP寄存器也是通用寄存器呢？而且MIPS似乎没有专门的压栈/出栈指令啊。
A: 这是MIPS这样的RISC处理器，同x86为代表的CISC处理器的重大区别之一。RISC没有专门的硬件实现的堆栈寄存器/指令，改为软件实现，在函数入口堆栈指针递减，堆栈向低地址生长，返回处恢复堆栈值，销毁堆栈帧。

4.
Q: MIPS的堆栈用软件实现，那么，MIPS的函数调用开销会更大吗？
A: 这是x86为首的CISC支持者，经常诟病RISC的一点。但是，实际上，我们知道，MIPS使用了4个GPR(一般用途寄存器)来传递前4个Word的函数参数，而x86只有EAX一个寄存器用于传递函数参数。所以，如果函数的参数小于或等于4个word，那就不需要使用栈。我们知道，大多数函数的参数都在4 个word以内。——所以，这一点不比太担心。另外，写太多参数的函数时，建议使用结构体传递这些参数。

5.
Q: MIPS的lh, lb这样的指令，会改变寄存器里的前2个/1个字节，还是后2个/1个字节？
A:一般来说是低位。

6.
Q: MIPS是大端(Big-endian)的，还是小端的(Little-endian)？

虽然年纪不大，但吃程序这碗饭已经有年头了。今天和同事一起给人面试，同事问candidate的一个问题，让另一个“面试官”——我，也被雷到了：

“咱们聊聊霍夫曼编码。”

本来平时贫嘴话痨的我立刻闭嘴以避免出丑，魂游天外地做完了剩下的面试，回到座位上问谷歌老师。谷歌老师带我去找维基老师。

维基老师说：

“In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. …… Huffman coding uses a specific method for choosing the representation for each symbol, resulting in a prefix code (sometimes called “prefix-free codes”) (that is, the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol) that expresses the most common characters using shorter strings of bits than are used for less common source symbols. Huffman was able to design the most efficient compression method of this type: no other mapping of individual source symbols to unique strings of bits will produce a smaller average output size when the actual symbol frequencies agree with those used to create the code. A method was later found to do this in linear time if input probabilities (also known as weights) are sorted.……Blah blah……”

看到这一大堆洋文，我又被雷了一下。这些东西是什么意思呢？幸好，有图有真相：
http://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/350px-Huffman_tree_2.svg.png

闲聊哈希表 （上）
经典数据结构教科书中，“表”是数据结构的一个大家族。其中，有顺序表（数组）、单向链表、双向链表、循环链表等等。我们今天聊的不是这些，而是“表”中的异类——哈希表(Hash Table)。

为什么会有哈希表这种数据结构呢？让我们用一个通俗的例子来理解：
大家一定都查过字典吧，我们知道，《新华字典》是按照读音排序的，可以理解为一个以读音为key，按升序排列的数据库。对于读音已知的字，可以通过“二分查找法”，很快地查找到要找的字，其时间复杂度为O(log2n)。但是，对于不知道读音的字怎么办呢？如果使用“顺序查找”，一页一页地翻字典，假设一本新华字典600页，每翻查一页的时间开销为0.5分钟，那么，每查到一个字耗费的时间t的数学期望值E(t) = 600 * 0.5min / 2 =150min，也就是查一个字需要两个半小时！当然，这是难以接受的！
为了解决这个问题，《新华字典》的编辑们，很快就想出了解决办法，那就是在字典的前面加入一个“检字表”，如“四角号码检字表”“部首检字表”等，其特点是以每个字的字形为依据，计算出一个索引值，并映射到对应的页数。比如“法”字，按四角号码检字法，其索引值为34131，再根据这个数值，就可以找到相应的字了。在这种情况下，查找算法的时间复杂度接近于O(1)。换句话说，字典再厚，也不会明显地影响到查字典的效率了。

好，让我们回到计算机的世界中来。
哈希表的最大特点，是数据存储位置（偏移量）和数据记录的内容相关，存在着一个函数换算关系：
Offset = Hash (Key)

VLAN的划分不一定必须基于端口(port based)，还可以基于协议。
如下的例子，以太网的首部格式如下：
0 12 14
DA/SA Type Blah blah

那么，当type为不同的值的时候，可以对应不同的VLAN。可以将一系列的值classify到一个group，然后给这个group绑定一个vlan id.
Type Value Groupid
IP 0800 A
ARP 0806 A
Red 1234 B
Green 5678 C
Blue abcd B

Groupid VLAN
A 123
B 456
C 789

这样，当type字段为0x0800的一个frame进入这个Port后，在交换机内部会打上VLAN ID为123的tag。
同理，0x1234的frame对应tag 456。

这个Groupid和VLAN tag的绑定关系可以在不同port上不一样，比如，port1是上表的对应关系，port2可以配置另外的对应关系，如Group B对应VLAN 987。

当然，这只是802.1q允许这样实现，不代表LSW必须实现这样的功能。