Linux 桌面环境

两种常见 Display Server：

• X Window System：历史久导致兼容性好，但设计思路老旧，性能问题开始有所体现。官方实现：X.Org Server。
• Wayland：更简单的现代化窗口系统。比 X Window System 更高效，但兼容性仍不够好。正逐步替代 X Window System。官方实现：Weston。

X Window System

• 增强级：Unity（Gnome）等
• 常量级：Gnome（GTK），KDE（Qt）等
• 轻量级：XFCE（GTK），LXDE（GTK），LXQt（Qt）等
• 超轻量级：iceWM（层叠式），i3WM（平铺式），X.Org Server（层叠式）等

Wayland

• 增强级：Unity（Gnome）等
• 常量级：Gnome（GTK），KDE（Qt，正在适配）等
• 轻量级：Weston（层叠式），XFCE（GTK，已有适配计划），LXQt（Qt，已有适配计划）等
• 超轻量级：SwayWM（平铺式）等

简述

栈是一种常见的数据结构，由于其“后进先出”（LIFO）的特性而被广泛使用。栈的常见逻辑结构如下：

图源：@Rella 《glow》 91882132

简述

广义表是线性表的一种推广。线性表要求表中元素拥有统一的类型，而广义表无此限制。需要注意的是，广义表和线性表长度一般认为是有限的，但广义表的深度可以是无限的（即递归表）。

广义表是一种数据结构。对广义表的常见操作包括：

• 创建
• 从字符串形式创建
• 销毁
• 复制
• 取表头
• 取表尾
• 判空
• 求长度
• 求深度
• 从表头插入
• 从表头删除
• 遍历

广义表是Lisp语言的基本数据结构。后文以Common Lisp和C++给出各基本操作的示例。

名词注解

长度

指广义表中的元素个数。举例如下：

例一

1

(a, b)

该表中共有两个元素：原子项a，原子项b。因而该表的长度为2。

例二

1

(a, (b, c))

该表中共有两个元素：原子项a，广义表(b, c)。因而该表的长度为2。

深度

指广义表中子表的嵌套层数。举例如下：

例一

1

(a, b)

该表中没有子表，因而该表的深度为1。

例二

1

(a, (b, c))

该表中嵌套了一个无嵌套的子表，因而该表的深度为2。

由于高中接触过，大学本科期间又深入了些，以防忘记记一些注意事项、概念和模板之类的东西。

简单分类

数据结构

• 一维：

  • 基础：数组（Array），链表（Linked list)

  • 高级：栈（Stack），队列（Queue），双端队列（Deque），集合（Set），映射（Map）等。

• 二维：

  • 基础：树（Tree），图（Graph）

  • 高级：二叉搜索树（BST），堆（Heap），并查集（Disjoint Set），字典树（Trie）等。

• 特殊结构：

  • 位运算（Bitwise），布隆过滤器（BloomFilter）

  • 缓存（LRU）

  • ……

• ……

算法

• 分支（if-else，switch）

• 迭代（for，while）

• 递归（分治法，回溯法等）

• 搜索（深搜，广搜，A*等）

• 动态规划

• 二分查找

• 贪心

• 计算几何

• ……

文章摘录和润色于本人的笔记，难免有错漏之处。若您发现了其中的一处或几处，请在评论处指正，我将不胜感激。

什么是压制？

压制的对象

可以是一切种类的音频、视频、图像，比如说：

• 蓝光光盘（BD）中的视频或音频（m2ts格式比较多见）
• DVD光盘中的视频或音频（dat等格式比较多见）
• CD光碟中的视频或音频
• 通过Web下载的各流媒体网站的视频或音频
• 各种剪辑软件、合成软件、特效软件、DAW等渲染的视频或音频
• 图片（或者动态图片）转换为视频，例如“一图流MV”等

注意：要区分压制（Rip）和混流（Mix）。

压制是编码间转换的过程，混流是编码不变的视频轨/音频轨在容器间转换的过程。

注意：要区分编码（Encode）和容器（Container）

举例说明如下：

• H.264是一种视频编码，aac是一种音频编码。
• mp4是一种视频容器，wav是·一种音频容器。
• avi既是一种视频编码也是一种视频容器。
• mp3既是一种音频编码也是一种音频容器。

压制的目标

对视频、音频等的压制，不全面地、概括地来说，有以下几点主要目标：

• 使音频/视频的编码符合要求。例如符合视频网站点播视频的要求、直播网站直播串流的要求、流水线中剪辑代理的要求等。
• 使音频/视频的数据总量（可以理解为音频/视频的体积）或音频/视频在单位时间内的数据量（可以理解为音频/视频的码率）符合要求。例如符合蓝光光盘的码率要求、窄带（依照2010年新的标准为4Mbps以下）情况下视频点播的要求等。
• 尽可能地保留音频/视频中的有效信息。可以理解为视频画面中物体的轮廓、音频的频段细节等。
• 去除或降低音频/视频中的干扰信息。可以理解为视频画面中的噪点、音频中的杂音等。

long 与 long long

long 一般占用4~8字节，long long 至少 占用8个字节。不同的平台和编译器，长度可能不同。

sizeof() 运算符

注意 sizeof() 属于运算符的一种，这个运算符用于测量括号内的变量（或类型）占用的字节数量。多数情况下，这一数量在编译时确定，因此 sizeof() 的运行结果是一个编译时常量。但也有例外，如C99标准引入的变长数组特性。该类数组的size需在程序运行时、数组开辟后确定。

由于是编译时常量，括号内如果是表达式，则表达式不会被执行。

1
2
3

int a = 1; // a = 1
int b = sizeof(a++); // b = 4
// a = 1, a++ 没有执行

浮点数精度问题

老生长谈的话题了。由于误差，以下的逻辑判断结果都是成立（1）：

1
2

(0.1 + 0.1 + 0.1) != 0.3; // 1;
1 + (1e123 - 1e123) != (1 + 1e123) - 1e123; // 1;

没有 body 的 for 循环

可以写成如下形式：

1
2
3

for(i = 0; i < 10; i++) {
    ;
}

或者如下形式：

1

for(i = 0; i < 10; i++);

图片来源：@Lifeline 88401620

增补（感谢@oyiadin）：本系列笔记将添加《Games 101：现代计算机图形学入门》、《Games 102：几何建模与处理》、“龙书”（《Introduction to 3D Game Programming with DirectX 12》）三个额外来源的笔记。大段的非CMU课程的笔记会在显著位置标识。

Lecture 1

什么是计算机图形学

计算机图形学：利用计算机合成视觉信息或利用计算机合成/操控感官信息的学科。

计算机图形学的应用

• 影视

• 动画

• 游戏

• 数据可视化

• 工业设计，平面设计

• 数字绘画

• 虚拟现实

  相同的内容后续整理VR课笔记时不再赘述。

  • 虚拟现实（VR）：指所看到的一切均为虚拟的，比如虚拟现实游戏、虚拟现实视频等。

  • 增强现实（AR）：指看到的是真实的现实 + 虚拟的、对当前现实进行分析处理或修改等生成的虚拟事物，比如Apple ARkit。

  • 混合现实（MR）：VR + AR，使用类似VR的手段，达到AR这种结合当前现实与虚拟事物的效果，比如Hololens。

• 制造业（3D打印）

• 模拟

• 排版与字体设计

  • “The Quick Brown Fox Jumps Over The Lazy Dog”：一句有意义的英文句子，内含全部的26个英文字母，常用来对字体（字形、字号、间距等）进行测试。

  • “Lorem ipsum dolor sit amet, consectetur adipisicing elit.”：又叫“乱数假文”或者“哑元文本”。主要的目的为测试文章或文字在不同字型、版型下看起来的效果。更多资料请查阅：https://cn.lipsum.com/。

• ……

计算机图形学与计算机视觉的区别

计算机图形学：将数据转化为图形。也就是“画出来”。

计算机视觉：将图形转化为数据。也就是“看到”。

计算机图形学需要哪些基础

• 表示方法（编码）

• 采样与混叠

• 数学方法（表示动态和三位形体）

• 光线

• 透视

• ……

对正方体建个模？

• 如何表示

  • 顶点：利用坐标

  • 边：利用边的两个顶点唯一确定

• 如何绘制

  • 三维图形转化为二维图形：小孔成像模型

    设相机坐标为 $(a,b,c)$ ，待确定点的坐标为 $(x,y,z)$ 。要得到该点在二维平面上的坐标，可进行如下算法步骤：

    1. $(x,y,z)$ 与 $(a,b,c)$ 相减，得到原三维点与摄像机的相对位置；

    2. 将其中的 $(x,y)$ 与 $z$ 相除，得到 $(\frac{x}{z},\frac{y}{z})$，即是所求的 $(u,v)$。

  • 连线。这就要细说到电脑如何绘制直线。

Lecture 1

实验

Lab1：数据实验，用位运算方式实现计算器

Lab2：炸弹实验，学会GDB

Lab3：攻击实验，代码注入和ROP

Lab4：缓存实验，写个缓存模拟器并优化

Lab5：Shell实验，写一个完整的Linux Shell

Lab6：Malloc实验，写自己的Malloc库

Lab7：代理实验，写自己的Web Proxy

Lecture 2

比特、字节和整数

• long double数据类型：在传统的32位架构或64位架构中是没有的。但在x86-64架构中占10或16字节（内存对齐）。

• 32位架构的指针为32位（4字节），64位架构的指针为64位（8字节）。

• 布尔代数：和 或 非 异或

• 位运算符 & | ~ ^，逻辑运算符 && || !

• 逻辑运算的短路特性

• 逻辑位移和算数位移：

  • 在位移运算符之前的数（比如$x<<y$中的$x$）是无符号数的话，位移运算对应的汇编指令为逻辑位移。若是有符号数，该运算对应的汇编指令是算数位移。
  • 对于左移：二者都是在右侧补0。
  • 对于右移：逻辑位移补0，算数位移补最高有效位（符号位）。如：令$x=10100000_{(2)}$，右移3位，逻辑位移结果$x>>3=00010100_{(2)}$，算数位移结果$x>>3=11110100_{(2)}$。

• 位移数小于0（即$x<<y$中的$y$小于0）或大于数据类型占用的长度（如char类型中y大于8）是未定义的操作。结果和编译情况依编译器和架构变化。

• 正数原码转十进制：求2的幂次加和即可。

$$ B2U(X) = \sum^{w-1}_{i=0}{x_i \cdot 2^i} $$

• 补码转十进制：注意符号位。也可写成公式。

$$ B2T(X) = -x_{w-1} \cdot 2^{w-1} + \sum^{w-2}_{i=0}{x_i \cdot 2^i} $$

• 补码计算举例：将补码$101101_{(2)}$化为十进制。

$$ 依据公式，\\ 101101_{2} = 2^{0} \cdot 1 + 2^{1} \cdot 0 + 2^{2} \cdot 1 + 2^{3} \cdot 1 + 2^{4} \cdot 0 + 2^{5} \cdot (-1) \\ = 1 + 0 + 4 + 8 + 0 - 32 = -19 $$

• 无符号数最大值$2^w - 1$，最小值$0$。有符号数最大值$2^{w-1} - 1$，最小值$-2^{w-1}$。

图源：Miv4t - 《MACHiNERY》，Pid：77186528

Windows 下的 cat 和 grep

ls、cat、grep这三个命令，往往是Linux初学者最先了解、日常使用Linux时不可或缺的。对于Windows系统而言，同样有三个命令可以完成上述工作：dir、type与findstr。

例如，用type显示文件内容：

或者用findstr结合管道匹配先前程序输出内容中的字符串：

也可以结合正则表达式：

当然，如果你不满足于系统命令的显示效果，你也可以尝试下面两款开源于Github的工具：

peco

项目链接：https://github.com/peco/peco

peco可以实现对管道输入的文本进行快速搜索、排序、多行选择等功能，使用Golang编写。目前仍不支持中文编码（GBK），且不支持默认的Windows Powershell终端（你需要使用传统的命令提示符，或者更先进的终端程序，比如Hyper或者Windows Terminal）。该项目仍在活跃开发中，合理的使用可以提升效率。

图源：《ソード・アート・オンライン（刀剑神域）》第一季第二集 CM

博客一直在慢速更新…之前一直忙于各种事情，学校的课、比赛、不断接触和学习新的东西，因此没什么机会静下心来好好整理、记录我学到的东西，也就没有办法一并记下我对某些问题的理解和思考。

之前一度认为，“有写博客文章的时间，还不如好好学点新的东西”。但是自从领悟到我和舍友之间记忆力和知识熟练程度的差距之后，终于肯下定决心好好写自己的博客了——我比不上他们，我真的不是那种过目不忘的人，所以只能通过不断的复习和总结才能勉强记住些东西。

有人说，初学者是“什么都不会，同时自己不知道自己会什么”，稍有学识的普通人是“自己会些东西，但是自己觉得自己会的很多”，而大神则是“自己会很多东西，但是自己觉得自己学的不多而且不知道自己已经会了什么”。

可能我还是初学者吧。

git push 反复输密码很烦？

有的时候可能会遇到一种极端情况：假设你要编写脚本，比如：自动化运维脚本。其中涉及到一些对 git 仓库的操作，而且需要密码，比如：在自动脚本中让部署机器拉取私有仓库，或是让部署机器将构建后的代码使用某个 github 账号推送到某个 git 仓库。这个时候需要用户手动输入用户名和密码，但是我们往往不能手动输入——比如公用的 docker build machine，根本不允许用户在构建过程中进行交互。

图源：《三色绘恋》 游戏背景图

最近又学到了一些零零碎碎的 Linux、Windows 命令，和一些可能今后会用得着的小技巧，怕自己忘记，所以把它们写在博客里面提醒一下自己，免得到时候再花费大量时间去百度、Google 找文章。

Linux 下查看进程树？

查看进程有好几种方式，top、htop 这种可视化的，还有 ps 这种纯文本输出的程序都可以做到。但是如果想要查看某一进程的父进程或者子进程PID该怎么办？可以借助另一个程序，pstree。参数很灵活，可以根据需要启用或关闭。程序截图如下：

WinHex 的替代品？

WinHex是很强大的一个二进制文件查看和编辑工具（尤其是做 CTF 杂项题的时候 :）。虽然说现在全网随便搜搜就有破解版（Cracked Version）可以用，但是多了解几个 WinHex 的替代品，有备无患。

EditPlus

说起来很巧，这个神器还是我在学校图书馆电脑上发现的。本来以为这东西只能编辑编辑文本，做 Notepad++ 的小弟，没想到这还能打开二进制文件查看16进制数据（emmm，不能编辑），而且…还支持 Windows ARM。

打开文件之后，点击 Edit->Hex Viewer 即可查看十六进制数据。

图源：《终将成为你》BD-1 声优特典 背景图

常见光盘种类

CD

Compact Disc，又叫做“小型镭射盘”、“激光唱片”，通过激光来读写数据。单层容量大概 700MB。其中一般存储的是音乐，但也有存储视频、相片、软件（多数是游戏）的 CD。常见分类如下：

1. 按存储内容分类：
   • CD-DA: 音乐 CD
   • CD-I: 交互式 CD（游戏CD）
   • VCD: 视频 CD
   • CD+G: 带有专辑图片和歌词的音乐 CD
   • Photo CD: 图片 CD
2. 按读写情况分类：
   • CD-ROM: 只读光盘。光盘背面的凹槽为厂家印制。
   • CD-R: 一次性写入光盘。 光盘背面的凹槽为刻录机烧制。
   • CD-RW: 可读写光盘。