本文是西交折磨水课计组的复习背诵笔记，用的是王换招老师的课本。
都是 PPT 题型
SigExt），写
ADD 指令周期。常用进制/幂次对照
\(2^6=64=40H\)
\(2^{8}=256=100H\)
\(2^{10}=1024=400H\)
\(2^{13}=8192=2000H\)
本提纲是计算机网络课程的复习背诵，根据西交的考点截取了内容。这个课程使用 Tanenbaum, Andrew S. 的著名课本。
这次考的不难，居然没有 TCP 拥塞控制。
计算机网络是一组通过单一技术相互连接的自主计算机集合
分布式系统强调整体性
[Personal | Local | Metropolitan | Wide] Area Networks、internetworks
按其他标准
子网：一组路由器和通信线路的集合，主要负责将数据包从源主机移动到目的主机
花了一周多，用 Verilog 写完一个 CPU（Github Repository: HeliumCPUv2-MIPS32），想看看自己究竟写了多少行，但是居然没有什么简单的做法。Github 也没有相关统计，怎么办呢？
查了查 Stackoverflow：Count number of lines in a git repository，确实给了一些做法。然后我学了学 Bash 的一些用法，采用了下面的方法。
首先，git ls-files 会给出仓库里没有 Ignore
的文件，我们把它用管道和 xargs 传给
wc。wc 即 "Word Count"，-l
选项可以打印出行数；xargs
相当于将管道进来的输入作为命令行参数传给调用的命令。
1 | git ls-files | xargs wc -l |
那么就可以得到一些结果
1 | 6 .gitignore |
它几乎把所有的行数都统计进来了，其中也包括一些没忽略的生成的文件（如数据段
dmem.data），并不能算写的代码，那么，可以把
git ls-files 出来的结果再正则一下，比如只统计
.v 文件
1 | git ls-files | grep ".*\.v" | xargs wc -l |
输出就干净多了，数的行数也正确
1 | 52 common/dbg_mems/dbg_dmem.v |
这是计算机组成课的实验项目，当然，也是学 CS 底层绕不过去的项目。我曾经试过一个 RISC-V 流水线 CPU 的实践，就跟着 Patterson 教授经典的教材 Computer Organization and Design RISC-V Edition，可惜当时动力不是十分充足，做的东西有点烂尾。我觉得到了需要做作业的时候，我大概就有动力了。
可惜 XJTU 的计组不出意料地食古不化，使用 MIPS。无所谓了，反正得写吧。做好的项目已经开源了，如果有小伙伴需要一点参考，那可以看看我是怎么组织这些 Verilog 代码的：
Github Repository: HeliumCPUv2-MIPS32
1 | . # 根目录，包含 Makefile 等文件 |
老师提供的是一个古早版本的 Modelsim，在 Win7 安装才不会出 bug 的那种。说实话，我不想用。有更多的好用或免费的解决方案放在这里呢：
笔者使用的是 Icarus Verilog，它比较简单；Verilator 也非常不错，可以使用 C++ 写 Testbench。如果想要 IDE，或者买了赛灵思的板子，那推荐使用 Verilator，也是免费的。
Icarus Verilog 是命令行工具，配合 VSCode 使用很香。VSCode 还有查看波形的插件 WaveTrace，但超过 8 个波形要收费，如果有需求可以使用 GTKWave。至于怎么安装这些环境，以及怎么跑通我的代码，在 Github 的仓库中有说明。
Github repository: SocketSnake
I started this Rust project days ago before my assignment for computer networks was due. And also, I though that I shall practice coding after reading half through the book Programming Rust by Jim Blandy, Jason Orendorff. Then the snake was born out of nowhere.
The project is build for personal practice, especially around networks and rust features. Nevertheless, We shall consider if someone would acually play it, right? Or a step forward, if somebody would learn from the project? Thus I write this blog in case of oblivion.
Everything starts from a easy ground. For building a local version of
the game, while considering that it may be migrated to a networked
version, we implements a Client thread and a
Server thread. The Client thread is
responsible for listening a keyboard action, and convert then into a
Ctrl signal (which is a enum type), and send
it to the Server with a std::mpsc channel; The
Server thread will host an instance of the game
(YardSim), and push the screen buffer YardBuf
(which is a Vec<Vec<TUIBlock>>) to the
Client, who is in charge of rendering the game.
graph TB
subgraph Client
Renderer(Render)
Keyboard(KeyboarCtrlListener)
end
subgraph Server
YardSim(YardSim)--BufferPipe-->Renderer
Keyboard--CtrlPipe-->YardSim
end
Moreover, to implement the multiplayer game via network, we shall
develop more modules. The ServerWrapper thread consists the
Server thread, so do the ClientWrapper do.
graph TB
subgraph ClientWrapper1
subgraph Client
Renderer(Render)
Keyboard(KeyboarCtrlListener)
end
Keyboard--CtrlPipe-->TCPSocket1(TCPSocket)
UDPSocket1(UDPSocket)--BufferPipe-->Renderer
end
subgraph ClientWrapper2
TCPSocket2(TCPSocket)
UDPSocket2(UDPSocket)
end
subgraph ClientWrapperN
TCPSocketN(TCPSocket)
UDPSocketN(UDPSocket)
end
subgraph ServerWrapper
TCPSocket1-.Connect.-TCPListener(TCPListener)
TCPSocket2-.Connect.-TCPListener
TCPSocketN-.Connect.-TCPListener
TCPListener-.FireUp.-ClientHandler1
TCPListener-.FireUp.-ClientHandler2
TCPListener-.FireUp.-ClientHandlerN
TCPSocket1==TCPStream==>ClientHandler1
TCPSocket2==TCPStream==>ClientHandler2
TCPSocketN==TCPStream==>ClientHandlerN
ClientHandler1[ClientHandler1]--CtrlPipe-->YardSim
ClientHandler2[ClientHandler2]--CtrlPipe-->YardSim
ClientHandlerN[ClientHandlerN]--CtrlPipe-->YardSim
subgraph Server
YardSim(YardSim)
end
ServerUDPSocket(UDPSocket Multicast)==Buffer==>UDPSocket1
ServerUDPSocket==Buffer==>UDPSocket2
ServerUDPSocket==Buffer==>UDPSocketN
YardSim--BufferPipe-->ServerUDPSocket
end
我在之前打数模的时候学了一点复杂网络，虽然学的很浅，感觉还是挺有意思的。
但这个考试完全打消了我对这个学科的喜爱，或者说觉得它不应该作为有考试的课程。这场考试完全就是背诵结论，弄得我毫无兴趣。现在陷入了人生的大思考。
考卷结构大概是 20 分名词解释（10 题），40 分填空（40 个空），余下的证明和计算。我有一个证明题没弄对，填空一堆不记得了，经验公式也不太好推出来，烦躁。
这个课本来是大四下的课，所以像这样背多分，不容易挂，也没人有意见，但是我基本上就惨了，祈求老师能给我分高一点吧。
还是把考前搞的提纲粘出来，要好好背。也有好多考了提纲里没有，要好好看课件。
随机变量 \(X\)，观测值 \(x\)，分布函数 CDF \(F(x)=P\{X\le x\}\)，概率密度函数 PDF \(f(x)=F'(x)\)
若 \(Y=g(X)\)，且 \(\int g(x)f(x)\ \mathrm d x\) 绝对收敛，则 \(E[Y]=\int g(x)f(x)\ \mathrm d x\)
今天刚考了优化方法，感觉还可以，但是据说改卷很严，我好像也感受到要是一严我就裂开了。唉，听天由命吧。
考前看到有之前上了的同学给这个课的评价，瘆得慌，博文链接在下面：
https://www.cnblogs.com/betelgeu/p/14999087.html
虽然他觉得罗老师不行，但是我们对罗老师印象其实挺好的，挠头。
不过呢，这个博主发的考试回忆还是挺准的，打消了不知道题型带来的考试懵逼感。
把考前复习整理的放在下面吧
\(n\) 维实向量集合 \(\mathbb R^n\) 上，\(\forall x=(x_1,x_2,\cdots,x_n)^\intercal\in\mathbb R^n\)，\(y=(y_1,y_2,\cdots,y_n)^\intercal\in \mathbb R^n\)的标准内积： \[ \left<x,y\right>=x^\intercal y=\sum_{i=1}^n x_iy_i \]
范数的定义：满足以下条件的函数 \(f:\mathbb R^n\to\mathbb R\) 称为范数
多图警告！
2021年初，心想买一个随处用的鼠标，正好 Anywhere 3 出来，搭载了 Master 3 上一样的电磁滚轮。十分心动！所以就买下来了。
白色鼠标十分讨人欢喜，用到现在也不觉得用脏了，而且有时候撞到什么东西也很难留下划痕。虽然他很贵，但我觉得一点也不娇贵，是个趁手的东西。电池续航很久，根本意识不到需要充电，即使需要充电，Type C 也十分方便。它最拿手的卖点就是电磁滚轮，真的爽到会让人觉得天下只有这一种滚轮，才能配的上鼠标的使用者。
然而它其实也有一些小缺点，比如回报率只有 125 Hz，比如没有滚轮左右摆动。但是这都不痛不痒，最致命的缺点，便是：
这意味着我这小半年在图书馆用鼠标都畏畏缩缩的，因为这个高频的噪声不止让别人难受，我自己听了也难受。导致这个鼠标只是每天被我带去图书馆，摆在桌上做吉祥物，然后用触摸板......
我一直想给它换个微动，但是又胆小，怕伤害了它的精致。直到有一天，终于忍不住了，要是它再不闭嘴，它就不是我爱的宝。
于是上淘宝买了凯华的静音红点（微动）和底部的鼠标脚垫，因为需要揭开脚垫才能拧螺丝。本来想去工程坊借焊台，但是感觉买个垃圾电烙铁也不贵，备着吧，就开始在寝室搞了。
Today we virtually participated the regional of 2018 Nanjing, and I have done my first non-trivial string problem, introducing a new algorithm called Extended-KMP. Thus I bet it notable on by blog.
Given two strings s and t, count the number of tuples \((i, j, k)\) such that
- \(1\le i\le j\le |s|\)
- \(1\le k\le |t|\)
- \(j − i + 1 > k\)
- The \(i\)-th character of \(s\) to the \(j\)-th character of \(s\), concatenated with the first character of \(t\) to the \(k\)-th character of \(t\), is a palindrome.
\(2\le |s|\le 10^6\), \(1\le |t|<|s|\)
The problem is to find and count the number of cases that there is two adjacent substrings \(s^{(1)}\), \(s^{(2)}\) in \(s\) and another \(t^{(1)}\) in \(t\), provided that \(s^{(2)}\) is a palindrome, and \(s^{(1)}\) is reversely matched with \(t^{(1)}\).
So let's reverse the string \(s\). Then use the famous Manacher algorithm on \(s\) (when there is a longest palindrome \(s_x\cdots s_y\), let \(p_{x+y}=\lfloor(y-x+1)/2\rfloor\)) and count every occurrence centered at \(i=\lceil(x+y)/2\rceil\).
Let \(s^j\) be the suffix of \(s\) starting from \(j\). We should firstly find the longest common prefix of suffix \(s^j\) and \(t\), and sum up the length of these prefixes around \(i\). Precisely, all of the prefixes starting from \(i+1\) to \(i+p_{x+y}\) should be counted. Using prefix sum, we could get that value in \(O(1)\) at every symmetrical center.
It must be noted that \(j-i+1>k\), then \(s_2\) must not be empty.
Dealing with bounds and indexes of strings is tricky, so be careful.
考完九天出分，作文不太高吧。但也不想再考这个了，应该做点更有用的东西，不能魔怔。学 GRE 给我最有用的帮助，无外乎词汇量大大增加了，看文章稍微快一点了。但实际上，不会的单词还是得查，也许和我不懂很多汉语成语的意义是一个道理吧。报个 GRE 确实还是有帮助的，否则自己的嘤语水平怎么提升呢（笑）
看看这备考的一个半月我都在干什么
上个月十八号脑子一热，报了这个月底 GRE，1665 RMB 比托福雅思还是便宜一点。当时兴致勃勃说别人准备三个月那我自学一个半月应该没什么问题，现在一个月快过去了，我觉得很有问题。
这一个月中间有十一假期，但是我这个月也做了不少别的事（花了很多时间写课程作业、报 BGA 和 IGSP），所以也不算用了很多时间。要你命三千小程序统计我背了 41 小时单词，算上别的做模拟、看书和用 Excel 背单词，满打满算也就准备了 70 个小时吧。但是 GRE 的标准准备时间差不多是 400 小时，笑死。
刷了快两遍 3000 了，还是有一半不认识，做题不认识词比较艰难。国庆做的模拟，Verbal 一个 Section 大概错 10/20 个，Quantitive 偶尔粗心（或者题没印好）错。作文看了范文，还没自己写过，我感觉半小时我没法有那么多 Development。
这两天又忙活了两天博客，修 \(\LaTeX\) 修炸脑袋。
感觉这些东西还是很有用的：