Miskcoo's Space

博客搬家及主题更换

2020 真是糟糕的一年,从寒假离校到现在已经在家里半年了。六月本该返校毕业,但是北京疫情突然反弹,返校被临时叫停。 闲暇之余打开博客,发现服务器时常因内存不足而导致数据库服务停止。看来是时候将这个博客从 WordPress 搬迁到静态的框架上了。 在 GitHub 上逛了一圈,发现了一个不错的 Jekyll 主题 Huxpro。 在修改了部分样式之后我就开始了整个博客的搬迁。 由于原来...

NonTrivialMIPS

十级双发射顺序MIPS32处理器

前一段时间我和几个同学参加了名为“龙芯杯”的比赛,这个比赛是自己设计一个CPU,在其上设计SoC,运行操作系统等… 是一个系统类的比赛。我主要负责写CPU除Cache外的部分,我们最终设计了一个有十级流水的双发射顺序执行的MIPS32处理器。在龙芯的实验板上达到了123MHz的主频,同时还具有较高的IPC。代码现在已经在GitHub上开源。 我来说说这个流水线的设计,除去各种数据旁路,流水...

TrivialDB

一个简单的SQL引擎

TrivialDB是一个简单的数据库管理系统,我们实现了大部分常见的SQL语句和类型。同时支持多表连接、复杂表达式运算、多主键约束、外键约束、CHECK约束、UNIQUE和DEFAULT约束、聚集查询、利用B+树索引的查询优化,同时,我们支持任意长度的VARCHAR类型。 项目地址是 https://github.com/miskcoo/TrivialDB,这是这学期一门课程的大作业。 ...

FPGA Console

硬件实现的VT220兼容终端

这是和HarryChen在这学期数字逻辑课上做的项目。主要是利用FPGA模拟一个终端。项目放在https://github.com/miskcoo/fpga-virtual-console上。 现在大部分的操作系统都是内置有虚拟终端,就像Linux下的xterm、gnome-terminal。但是,在最初控制台和计算机是相互独立的。控制台一般是由键盘和屏幕组成,键盘将用户输入传入计算机,计...

程序设计训练

数独、国际跳棋、人物信息检索系统

这次程序设计训练小学期一共有三个大作业,分别是数独、在线国际跳棋和人物信息检索系统。这里是简单的一些介绍,代码放在 https://github.com/miskcoo/programming-training。 Week 1: Sudoku Game 简介 Sudoku 是一款利用 Qt 实现的数独游戏,提供了多达 10 个难度的关卡选择,同时还有丰富的功能来帮助玩家更加高效地求解数...

Vim里一些好用的插件

我主要是想要把一些用过的好用的插件记下来,万一哪天换了系统还可以在这里找回来。 Vim-Latex 这是一款帮助编辑Latex的插件,里面集成了很多环境的快捷输入方式,例如输入EFI就会自动变成如下 1 2 3 4 5 \begin{figure}[h] \centerline{\psfig{figure=<+eps file+>}} \caption{&l...

较短步数复原魔方的算法

这其实是我们上学期程序设计课的一个大作业,我很早就想把它记录下来了,可是实在太懒了就拖到了这个学期。本来作业是要求复原魔方就好了,但是后来发现没有图形界面的话似乎调试很困难,就顺便写了一个 UI,刚好还学了一下 OpenGL。最开始我是写了能够找到最优解的 Krof 算法,但是估计是我写得比较丑再加上状态空间实在太大了(大约在搜索到第 15 步还是 16 步的时候状态数就到百亿级别了,而我 ...

上帝的指纹 — Mandelbrot集合的绘制

曼德博集合(Mandelbrot Set)是一个在复平面上的点集。有人认为 Mandelbrot 集合是“人类有史以来做出的最奇异、最瑰丽的几何图形”,曾被称为“上帝的指纹”。 Mandelbrot 集合是一个分形(fractal),将它无限放大都能够有精妙的细节在内,而这瑰丽的图案仅仅由一个简单的公式生成。 Mandelbrot 集合的定义是由法国数学家 Adrien Douady...

CodeChef上一道有趣的网络流题目

这是一道2016年二月CodeChef上的一道题目,叫做Call Center Schedule。 题目大意是这样的: 一个电话公司有 $P$ 个员工,一个星期有 $D$ 天,每天需要工作 $H$ 个小时。每个员工在每个小时只能做参加会议和与客户通话两件事情中的一件,或者不做。 现在要为安排一个和客户通话的时间表,要求满足 每个人每天最多花费 $N$ 个小时在...

Tarjan算法寻找有向图的强连通分量

在图论中,一个有向图被成为是强连通的(strongly connected)当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连通子图(这里指点数极大)被称为强连通分量(strongly connected component)。 比如说这个有向图中,点 $1, 2, 4, 5, 6, 7, 8$ 和相应边组成的子图就是一个...