跳转至

博客

  • 分类于 programming
  • 需要 1 分钟阅读时间

近来做 Stanford CS140e 的一些进展和思考（8）

在上一篇文章之后，我其实还是很忙，但是一直心理惦记着这件事，毕竟只剩最后的一点点就可以做完了，不做完总是觉得心痒。

今天做的部分是调度。我们目前只在 EL0 运行了一个 shell，每当触发 exception 时回到 kernel 进行处理，再回到原来的地方。但现在，我要实现一个 preemtive round-robin scheduler，就需要管理当前的所有进程，并且维护当前的进程状态，当时钟中断到来的时候，决定下一个 time slice 要执行的进程，再切换过去。这个过程当然会遇到不少的坑。

首先，我们需要判断一个进程是否可以执行了。考虑到阻塞的 IO，作者提供了一个优雅的方法：如果这个进程阻塞在 IO 上，那么，提供一个函数，在 scheduler 中调用，判断所需要的数据是否到达。这样，我们就可以一个循环把下一个 time slice 要执行的线程找到。如果找不到，就等待 interrupt 再尝试。

困难的地方在于，在启动的时候，切换到一个起始线程。并且在上下文切换的时候，在 process 1 -> kernel -> process 2 这两步过程中，有许多寄存器都需要仔细考虑如何实现。并且在这个过程中，我也发现了之前写的代码中的问题，最终修复了（目前来看是 working 了）。

我的代码实现在 这里 。下一步就要写 syscall 了。希望能在期中前抽时间赶紧把这个做完。

18:54 PM Update: 刚实现完了 sleep 的 syscall。比预想中要简单。果然找到了自己实现的调度器的 BUG。此系列大概是完结了。

2019-02-12 Update: 下一篇文章。

  • 分类于 programming
  • 需要 1 分钟阅读时间

近来做 Stanford CS140e 的一些进展和思考（7）

在上一篇文章之后，我很长时间都没有在继续我这个项目，清明节刚好闲下来了我就回来继续啃它。Stanford 那边已经结课，最后的 3-spawn 也只有一部分，剩下的部分不知道什么时候作者才会填上去了。

这次主要要写的代码就是，对异常的处理。这里的异常并不是我们编程语言中的 catch/throw，而是硬件的异常。AArch64 和 x86 一样，也有不同的特权级别的区分，前者是 EL0~EL3，后者则是 RING0 和 RING3。特权级别高可以往特权级别低转换，但是反过来，只能通过异常的方式提高特权等级，并且切换特权等级后只有固定的一些代码可能会跳转，这就是 exception handler/vectors 。这些函数可以知道是什么原因调用了他们，根据硬件规定好的文档，我们可以知道发生了什么事情，是对齐出错了呢，还是用户调用了 syscall 呢，等等。根据不同的情况，我们需要进行不同的处理。当处理完之后，我们需要考虑，跳转回用户代码的时候，回到哪里，提供什么值，不提供什么。

实现的话，需要很多步骤。首先是构造好 exception vector ，这里作者已经写好了一个宏（这里 @BenYip 遇到了一个 assembler 的 BUG），直接用宏就可以把它写出来。然后，我们需要把它加载到当前 EL 的 VBAR_ELx 寄存器中，当 CPU 抛出异常的时候，就会找到这里相应的处理器进行处理。进到这里以后，我们首先先不考虑太多上下文保存的事情--我们先保证能处理异常，恢复也是个有很多坑的步骤，作者也是在这里分成了两个 Subphase。首先还是从 ESR_ELx 中解析到错误的来源的具体内容，如果是我们在 shell 中自己调用的 brk 2 指令，我们就自己新开一个 shell ，修改了提示符以示区别。这样，我们就成功地捕捉到了这个异常。由于我们还无法恢复回去，所以我们直接死循环。

接下来我们要做的是，从异常中恢复出来。由于用户代码可能在各种地方抛出异常，异常也分同步和异步两种情况，这里有许多需要考虑的问题。为了简化，我们目前只考虑同步的 brk 2 导致的 Brk 异常。为了能恢复之后能够正常运行，我们需要把所有的寄存器都保存下来，即 TrapFrame 。保存的时候需要讲究 AArch64 平台下 SP 寄存器的对齐问题。我们也要把一些特殊的寄存器保存下来。还有一点，就是，因为 exception handler 中调用了 context_save 函数，所以此时的 lr 本身也需要进行保存，这个地方也卡了我很久。最后，再把这些一个一个地恢复到原来的样子，调整 ELR_EL1 使得退回到原来的状态时，会跳过当前的 brk 2 指令，调用它的下一调指令。这样，我们就成功地在遇到异常时，弹出一个 shell ，而且还可以回退回来。

学到了很多很多。之后大三，我们可能需要做自己的 CPU，在自己的 CPU 上跑自己的操作系统，在自己的操作系统中跑自己的编译器，在自己的编译器中编译一个数据库。希望到时我还活着吧。#flag

更新：下一篇在这里。

  • 分类于 others
  • 需要 1 分钟阅读时间

最近比较忙

最近一直没有更新我的 CS140e 系列文章，是因为最近一直忙于各种事情。等有空了再更新吧。

  • 分类于 others
  • 需要 1 分钟阅读时间

偶遇清华吴文虎教授

今天百团大战，正准备收摊的时候，天空工场那边来了一位长者，在和他们聊着什么。我很感兴趣，就上去听。老人大概已有八十高龄（后来查，是 1936 年生），但依然精神矍铄，首先和我们讲，作为工科的学生，一定在理解原理的基础上，多多去实践。他举了他自己的例子，他首先在电机系学习，后来，计算机系成立（当时还是自动控制系），他转到了计算机系，重新学起了计算机，说计算机编程学起来并没有什么难的。当年，苹果公司送过来了中国第一台 Apple-2，他们就把电脑拆了下来研究原理，又装上去继续工作。后来，他就在计算机系任教，教的正是《程序设计基础》这门课程。他十分重视实践，在第一年开课的时候就说，最关键的就是实践，安排了一些编程实验课，期中期末就是大作业。一开始有一些同学不重视实践，结果期末就挂科了。后来同学们就明白了实践的重要性，实践起来发现并没有那么难，最后就说，“吴老师，你说得对”。他又谈到了他的体育，他当年是北京长跑代表队的集训队选手，擅长一千五百米项目，他三千米只需要九分钟就能跑完。我们都感到自愧不如。我们说，现在的《程序设计基础》是徐明星老师在教，他说徐明星是他的博士生，邬晓钧也是他的博士生，他另外还有一个高徒我记不清楚了。他还是 IOI 中国队的前教练，听到我们有过一些 OI 基础，表示了赞许和鼓励。还有一些细节记不清楚了，记起来了再补充吧。

  • 分类于 programming
  • 需要 1 分钟阅读时间

〖新手向〗绕过 C++ 类的访问限制

这是一篇很水的文章，面向萌新，已经知道了的可以自觉绕道。

昨天上课，有同学问，如果用户偷偷把 private 改成 public 再和原有的库链接，是不是就可以在用户代码里更改了。这个答案是肯定的。下面我们就做个实验：

首先，创建 good_class.h 和 good_class.cpp:

class SomeClass {
private:
    int data;
public:
    int getData();
};

#include "good_class.h"

int SomeClass::getData() {
    return data;
}

然后，首先编译，

clang++ -c good_class.cpp -o good_class.o

然后，修改 good_class.cpp 并写一个 evil_user.cpp

class SomeClass {
public:
    int data;
public:
    int getData();
};

#include <stdio.h>
#include "good_class.h"

int main() {
    SomeClass a;
    a.data = 37;
    printf("%d\n", a.getData());
    return 0;
}

编译：

clang++ good_class.o evil_user.cpp -o evil

然后 evil 如愿地输出了 37 。

一些提醒：

  1. C++ 的访问控制十分的弱，仅仅是编译期。所以是很容易绕过的。
  2. 对于不想泄露源代码的库，不要导出 C++ 的类和函数。选择导出 C 函数，结构体用 incomplete type 或者干脆 void * 。

扩展阅读： L 叔的通过虚函数表访问私有函数 。

  • 分类于 programming
  • 需要 1 分钟阅读时间

近来做 Stanford CS140e 的一些进展和思考（6）

在上一篇文章之后，作者终于更新了测试的用例，我的程序终于可以成功跑过所有测试，也成功在树莓派跑起来。不过，我的代码中很多地方的错误处理比较偷懒，往往直接 panic ，显然并不友好。同时，我想到了使用 cargo-fuzz 来进行自动化测试，果然，使用这个很快就修复了不少我没想到的会出错的地方，比如乘法溢出，目录项没有正确结束等等。目前还发现一个 timeout 的问题，研究发现大概是文件的 cluster chain 中出现了环，导致一直读取文件而没有停止。要解决这个问题，我目前想到的是 Floyd 的判圈算法，但还没上实现。等过几天，新的 Assignment 3 出了以后，再继续更新。希望作者少点跳票，多点勤奋，哈哈哈哈哈

更新：下一篇在这里。

  • 分类于 programming
  • 需要 1 分钟阅读时间

近来做 Stanford CS140e 的一些进展和思考（5）

在上一篇文章之后，作者多次延期跳票之后（again），终于放出了 Assignment 2 Phase 3: Saddle Up 。这次，我们要做的变成了把已经写好的（错漏百出）的 fat32 的驱动搬到树莓派里面去，然后实现一些基本的 shell 命令： ls cat cd 等等。作者首先更新了老版本的新的测试样例，放了一些映像然后提供了预期的结果，结果发现，这里的 fat32 有一些不同，主要的就是 bytes_per_sector 不是 512 了，意味着物理的扇区和逻辑扇区并不一致。同时， sectors_per_cluster 也不是 1 了，需要考虑多个扇区的情况。同时， read_cluster 传入的 offset 也可能不再是第一个 sector 中的，所以需要做一个处理。对于物理和逻辑扇区的问题，作者推荐的方案是，把 fat32 之外的扇区保持不变，把其内的扇区视为逻辑扇区。这样，其它代码都可以透明地工作，而不用到处更改，这就体现了封装的威力。接着，作者提供了一个写好了的 libsd 和一些导出的函数，使用这些函数即可。不过，在错误处理和 timeout 上也遇到了一些坑。后面，把东西搬到树莓派上运行，问题就出现了：读取了第一个扇区（即 MBR 所在的扇区）之后，直接就死掉了。想了半天都没找到方案，突然想起可以利用 panic! 对错误语句进行二分查找。查找了大概有七八个小时之后，终于发现，问题出现在读取一个 u32 类型的变量上。我起初怀疑是栈出了问题，所以放到堆上分配，然而还是不行。忽然想起以前遇到的对齐问题，在 AArch64 架构上，可能为了简化，读取的 u32 必须对齐到四个字节上。于是找了找 Rust 中的对齐方面的文档，找到了 #[repr(align=4)] 这种表示方法，代替了原来的 #[repr(packed)] ，并且把数据先拷贝到对齐后的栈上的对应数据结构，然后再读取对应的项。果然，这个问题就解决了。然后又发现我的盘中会出现 lfn 项并不是从后往前的情况，于是我又修改了一下相关的代码。现在，终于可以成功地 ls cat cd 。

不过还是要吐槽一下，作者的测试用的映像文件中，会出现 0xE5 表示这个项已经被删除的情况，但是似乎作者的代码并没有处理这个，所以在预期的输出中出现了一些明显不正确的结果，导致我的代码跑测试并不能通过。而且，作者的代码在一些情况下会把文件的后缀漏掉。作者后来更新了几次测试的文件，不过这个问题只解决了一部分，并没有完全解决。坐等作者继续放出新的测试文件吧。

更新：下一篇在这里。

  • 分类于 programming
  • 需要 1 分钟阅读时间

近来做 Stanford CS140e 的一些进展和思考（4）

在上一篇文章之后，作者多次延期跳票之后，终于放出了 Assignment 2 Phase 2:32-bit Lipids ，这两天就把只读 FAT32 写完了（不过封装得并不好，许多地方利用了 pub(super) 把变量可以访问的范围控制到 vfat 中，然后直接读，只有少数需要特殊处理的进行了函数的封装）。首先当然是研究了半天 MBR 和 FAT32 的结构，拿了不同来源的 FAT 结构说明进行对比和验证，最后终于把格式搞清楚了，先实现了 MasterBootRecord ，这个其实很好实现，以前也有接触过 MBR ，本身也很简单。然后就是根据 MBR 找到第一个 FAT32 的分区，根据偏移找到分区的开头，开头的第一个扇区就是 EBPB 数据结构，里面保存了 FAT32 分区的各种信息。根据里面的信息，可以找到 FAT 表的位置和数量，还有数据部分的 Cluster 的位置和数量。接着，解析一下 FAT 表，实际上是一个与 Cluster 一一对应的链表结构，用特殊的数据代表链表的尾和空、坏扇区。利用这些，和 EBPB 中根目录所在的第一个 Cluster ，先在 VFat 里面实现了读取一个 Cluster 链的内容的函数，利用这个函数读取一个一个的目录项，解析目录项，把长文件名的项合并到一个之中，然后对应地丢到 Entry 对象中，目录则可以枚举子目录项，根据名字比较去找子目录或者子文件夹，文件则实现了 io::Read和 io::Seek 使得可以读取文件的内容。实现好了这些以后，就拿了 raspbian-strech-lite.img 作为硬盘映像，从文件里读取文件信息，成功地把 config.txt 读取出来。

其中还是遇到许多困难，如各种偏移的计算，如何处理跨 Cluster 和跨 Sector 的读写，等等，有不少的坑在其中，花了两天的空余时间才差不多完善了这个功能。还有就是利用 Rust 现有的功能完成 C 里面很轻易就可以实现的指针操作，也花了不少时间。

更新：下一篇在这里。

  • 分类于 programming
  • 需要 1 分钟阅读时间

近来做 Stanford CS140e 的一些进展和思考（3）

由于 Assignment 2: File System 延期发布，所以中间那段时间转向 MIT 6.828 稍微研究了一下。前几天放出了新的任务，在上一篇文章之后，我又有了一些进展：实现了从内存中读取 ATAGS(ARM Tags) 信息的代码，从而可以获得内存大小的信息，根据这个信息，实现了 bump 和 bin 两种内存分配器，并且把二者之一注册为全局内存分配器，利用上更新了的 std 就可以使用需要动态分配内存的相关工具了。利用这个，我实现了 shell 输入历史的回溯，把输入历史保存在一个动态增长的数组中，再特殊处理上下键，把当前的行替换为历史。

这个过程也不是没有踩坑。一开始代码放出来了，但是题目说明还没出，我就自己按照代码做了 ATAGS 和 bump 分配器，后来做完了，看到说明出了以后，发现理解还是有偏差，把代码更改了并修复了分配器的 BUG。看到 bin 分配器的时候，我按照网上的 buddy memory allocation 实现了一个内存分配器，原理看起来简单实现起来还是有很多细节问题，后来按照新放出的单元测试，修修补补才写得差不多可用了。同时，原来的 bootloader 因为用了新的 std 而缺失了 alloc 不能编译，我就把 kernel 下的相关文件软连接过去，调了数次后把问题解决。此时， kernel 文件大小已经有 40K，按照 115200 Baudrate 发送需要几秒才能传输过去，我就调到了 230400 Baudrate，果然现在的传输速度就有所提升，可以接受了。等之后写了 EMMC(SD card) 的驱动和 FAT32 的文件系统后，就可以实现更多的 shell 的功能了。中间还遇到一个问题，就是如果给 kernel 开启了 bin 分配器，使用 exit 回到 bootloader 就无法传新的 kernel 上去了，结果发现是因为 bin 中用到的侵入式 LinkedList 实现覆盖了部分 bootloader 的代码，换回不能回收内存的 bump 分配器即可，反正目前远远还用不了那么多内存。

之后还要在 aarch64 上用 MMU 实现虚拟内存，之前在 MIT 6.828 里被页表整得脑子眩晕，希望到时我还活着吧（逃

更新：下一篇在这里。

  • 分类于 programming
  • 需要 1 分钟阅读时间

近来做 Stanford CS140e 的一些进展和思考（2）

在上一篇文章之后，我又有了一些进展：UART ，简易的shell ，修复了之前写的 xmodem 中的 BUG，一个可以从 UART 接收一个 kernel 写入到内存中再跳转过去的 bootloader 。

首先是 UART ，就是通过两个 GPIO pin 进行数据传输，首先在 memory mapped IO 上进行相应的初始化，然后包装了 io::Read 和 io::Write （这里实现一开始有 BUG，后来修复了），然后很快地完成了一个仅仅能 echo 的 kernel 。

然后实现了 CONSOLE ，一个对 MiniUart 和单例封装，就可以用 kprint!/kprintln! 宏来输出到 UART ，接着实现了一个 echo 的 shell ，读入一行输出一行。然后实现退格键和方向键，这里的难点在于要控制光标并且用读入的或者空格覆盖掉屏幕上已经显示而不应该显示的内容。接着，利用 skeleton 中的 Command 做了一个简单的 echo 命令。

接着，利用之前编写的 tty ，配合上新编写的 bootloader ，实现通过 UART 把新的 kernel 通过 XMODEM 协议发送到设备，写入 0x80000 启动地址并且调转到新加载的 kernel 中执行。

最后，又实现了 uptime （输出设备启动到现在的时间）和 exit （跳转回 bootloader ，可以上传新的 kernel ）。并添加了 TUNA 作为 shell 启动时输出的 BANNER 。

整个过程挺虐的，踩了很多的坑，由于很多东西都没有，输入输出目前也只有 UART ，写了 UART 后又遇到 XMODEM 难以调试的问题。十分感谢 #tuna 上的 @BenYip 及时地指出了代码的几处问题，节省了我许多时间。

更新：下一篇在这里。

  • 分类于 programming
  • 需要 2 分钟阅读时间

近来做 Stanford CS140e 的一些进展和思考

最近，受各路安利，剁手买下了 这个淘宝商家的树莓派的套餐 C ，还买了许多 LED 灯泡、杜邦线和电阻，开始按照 CS 140e 学习 Rust 并且用 Rust 编译写一个简易的操作系统。Assignment 0 的目标就是编写一个向 GPIO 16 连接的 LED 灯闪烁。首先当然就是愉快地按照教程下载 bootloader，下载交叉编译工具链，顺带装一个 Raspbian 到机器上，随时可以当成一个低性能的 ARM/ARM64（实际上，Raspbian 只用了 armv7l，没有用 64bit）机器来用，以后如果配上 @scateu 团购的 Motorola Laptop Dock 的话就是一个几百块的笔记本了。把课程上的文件丢上去，可以看到绿色的活动指示灯闪烁，后面又把 CP2102 模块连上去，又能看到 Blink on, Blink off 的输出。然后按照要求，自己先码一段 C 语言，实现 blinky:

#define GPIO_BASE (0x3F000000 + 0x200000)

volatile unsigned *GPIO_FSEL1 = (volatile unsigned *)(GPIO_BASE + 0x04);
volatile unsigned *GPIO_SET0  = (volatile unsigned *)(GPIO_BASE + 0x1C);
volatile unsigned *GPIO_CLR0  = (volatile unsigned *)(GPIO_BASE + 0x28);

static void spin_sleep_us(unsigned int us) {
  for (unsigned int i = 0; i < us * 6; i++) {
    asm volatile("nop");
  }
}

static void spin_sleep_ms(unsigned int ms) {
  spin_sleep_us(ms * 1000);
}

int main(void) {
  // STEP 1: Set GPIO Pin 16 as output.
  *GPIO_FSEL1 = 0b001 << 18;
  // STEP 2: Continuously set and clear GPIO 16.
  while (1) {
    *GPIO_SET0 = 1 << 16;
    spin_sleep_ms(1000);
    *GPIO_CLR0 = 1 << 16;
    spin_sleep_ms(1000);
  }
}

其中大部分代码都已经给出了，自己要实现也只是查询一下 BCM2837 SoC 的 GPIO 文档，按照文档把该做的内存操作和位运算都写一下即可。最后发现，闪烁的频率特别慢，几秒钟才闪烁一次。毕竟是按照 CPU 的 clock speed 进行粗略的计时，而生成的代码也不是很高效，没有 inline。接着则是用 Rust 再实现一下上面这部分的代码：

#![feature(compiler_builtins_lib, lang_items, asm, pointer_methods)]
#![no_builtins]
#![no_std]

extern crate compiler_builtins;

pub mod lang_items;

const GPIO_BASE: usize = 0x3F000000 + 0x200000;

const GPIO_FSEL1: *mut u32 = (GPIO_BASE + 0x04) as *mut u32;
const GPIO_SET0: *mut u32 = (GPIO_BASE + 0x1C) as *mut u32;
const GPIO_CLR0: *mut u32 = (GPIO_BASE + 0x28) as *mut u32;

#[inline(never)]
fn spin_sleep_ms(ms: usize) {
    for _ in 0..(ms * 600) {
        unsafe { asm!("nop" :::: "volatile"); }
    }
}

#[no_mangle]
pub unsafe extern "C" fn kmain() {
    // STEP 1: Set GPIO Pin 16 as output.
    GPIO_FSEL1.write_volatile(1 << 18);
    // STEP 2: Continuously set and clear GPIO 16.
    loop {
        GPIO_SET0.write_volatile(1 << 16);
        spin_sleep_ms(1000);
        GPIO_CLR0.write_volatile(1 << 16);
        spin_sleep_ms(1000);
    }
}

这边和上面一样，很多东西都已经给出了，只是重新改写一下而已。不过，这边的实测结果则是，一秒钟会闪烁很多下，看了下汇编，生成的循环比较紧凑，所以也没有达到想要的效果，不过后面到我实现了 Timer 的读取之后，就很精准了。

接下来就是痛苦的学习 Rust 的过程，Assignment 1 上来就是解答关于 Rust 语言的一些问题，在过程中被 Rust 十分严格的 Lifetime 和 Borrow checker 弄得想死，好歹最后还是让测试都通过了。接下来就是真正地提供一些封装硬件接口的 API，然后利用这些 API 去实现更多功能，首先是利用栈上分配的空间模拟一个变长数组的 API：stack-vec ，然后是把底层的直接操作硬件的内存操作封装成类型安全的 volatile ，然后实现一个简单的支持断点续传的传文件的协议 xmodem ，又做了一个辅助电脑上使用 TTY+XMODEM 的小工具 ttywrite ，然后就开始撸硬件了：时钟 timer ，针对 GPIO pin 的类型安全的状态机 GPIO 。目前只实现到这里，然后做出了一个准确一秒闪烁的 blinky（令人惊讶的是，因为这里的 kernel 直接从文件头开始就是代码，最后的 binary 异常地小，而之前的代码从文件的偏移 0x8000 开始。目前看来，是因为之前的代码是整个文件加载到 0x0000 上，而代码默认了从 0x8000 开始，所以除了最开头的一个跳转指令，中间留了许多空余的空间。而这里的代码是直接被 bootloader 加载到了 0x80000 处并且跳转到这里执行，所以省去了许多空间）：

fn blinky() {
    let mut pin16 = Gpio::new(16);
    let mut pin_out16 = pin16.into_output();

    loop {
        pin_out16.set();
        spin_sleep_ms(1000);
        pin_out16.clear();
        spin_sleep_ms(1000);
    }
}

#[no_mangle]
pub extern "C" fn kmain() {
    // FIXME: Start the shell.
    blinky();
}

目前只做到这里。后面还有大把的坑要踩，难写的 Rust 还得继续啃下去。我的代码都以 diff 的形式放在了 jiegec/cs140e ，写得并不美观。接下来就是实现 UART 了，终于要实现串口通信了。

2018-01-06 更新： 下一篇文章已经更新 。

  • 分类于 programming
  • 需要 1 分钟阅读时间

再次吐槽 VS 关于 scanf 和 scanf_s 的问题

继上次的吐槽后，今天再次遇到同学因为 scanf 在 VS 下的 deprecation error 感到十分迷茫，在知乎上求助又因为拍照的原因被说，我就在此再次吐槽一下 VS 这对初学者很不友善很不友善的两点。

一点就是上面提到的这个，另一点就是程序结束后任意键以退出这一功能要做得更加醒目一点。前者由于大多数新手在学习 C/C++ 的时候都会跟着书上或者网上的代码敲一遍输入输出的代码，很容易就会撞到这个问题。后者则会让新手习惯性地以为程序闪退了，没有出结果，而不知道其实是程序执行结束后关闭而已。

  • 分类于 programming
  • 需要 2 分钟阅读时间

我正在使用的两个 Emacs 的 Patch

我在本地对 emacs.rb 进行了修改：

diff --git a/Formula/emacs.rb b/Formula/emacs.rb
index d0138cd..de3c5ff 100644
--- a/Formula/emacs.rb
+++ b/Formula/emacs.rb
@@ -4,6 +4,14 @@ class Emacs < Formula
   url "https://ftp.gnu.org/gnu/emacs/emacs-25.3.tar.xz"
   sha256 "253ac5e7075e594549b83fd9ec116a9dc37294d415e2f21f8ee109829307c00b"

+  patch do
+    url "https://gist.githubusercontent.com/aatxe/260261daf70865fbf1749095de9172c5/raw/214b50c62450be1cbee9f11cecba846dd66c7d06/patch-multicolor-font.diff"
+  end
+
+  patch do
+    url "https://debbugs.gnu.org/cgi/bugreport.cgi?filename=0001-Fix-child-frame-placement-issues-bug-29953.patch;bug=29953;att=1;msg=8"
+  end
+
   bottle do
     sha256 "d5ce62eb55d64830264873a363a99f3de58c35c0bd1602cb7fd0bc37137b0c9d" => :high_sierra
     sha256 "4d7ff7f96c9812a9f58cd45796aef789a1b5d26c58e3e68ecf520fab34af524d" => :sierra

主要涉及到两个 Patch：

  1. 启用对 Multicolor font，比如 Emoji 的支持。由于一些 ethic problems 暂时在 Emacs 中被禁用了，所以自己启用回来。
  2. 打上我前几天上报的 BUG #29953 的修复。已经在上游 Merge 到 emacs-26 分支中，这个修复会在下一个版本中。

有了第一个，就可以正常显示 Emoji（对不起，RMS）；有了第二个，就解决了 pyim 和 lsp-ui-peek 用 child-frame 显示的一些问题了。

另外还有一个我自己在用的 recoll.rb ： 

# Documentation: https://docs.brew.sh/Formula-Cookbook.html
#                http://www.rubydoc.info/github/Homebrew/brew/master/Formula
# PLEASE REMOVE ALL GENERATED COMMENTS BEFORE SUBMITTING YOUR PULL REQUEST!

class Recoll < Formula
  desc "Recoll is a desktop full-text search tool."
  homepage "https://www.lesbonscomptes.com/recoll/"
  url "https://www.lesbonscomptes.com/recoll/recoll-1.23.5.tar.gz"
  sha256 "9b6b6941efc3e87c8325e95a69a5d0a37c022c3c45773c71dccd0fb3f364475f"

  depends_on "xapian"
  depends_on "qt"
  depends_on "aspell"

  def install
    inreplace "Makefile.in",
      "-Wl,--no-undefined -Wl,--warn-unresolved-symbols", "--no-undefined --warn-unresolved-symbols"

    system "./configure", "--disable-dependency-tracking",
                          "--disable-silent-rules",
                          "--without-x",
                          "--disable-x11mon",
                          "--with-aspell",
                          "--enable-recollq",
                          "--disable-webkit", # requires qtwebkit, which is not bundled with qt5
                          "--prefix=#{prefix}"
    system "make", "install"

    mkdir libexec
    mv bin/"recoll.app", libexec/"recoll.app"
  end

  test do
    # `test do` will create, run in and delete a temporary directory.
    #
    # This test will fail and we won't accept that! For Homebrew/homebrew-core
    # this will need to be a test that verifies the functionality of the
    # software. Run the test with `brew test recoll`. Options passed
    # to `brew install` such as `--HEAD` also need to be provided to `brew test`.
    #
    # The installed folder is not in the path, so use the entire path to any
    # executables being tested: `system "#{bin}/program", "do", "something"`.
    system "false"
  end
end

  • 分类于 networking
  • 需要 2 分钟阅读时间

NAT64 初尝试

最近宿舍里有线网络的 IPv4 总是拿不到地址，只能连无线网，不禁对计算机系学生的可怕的设备数量有了深刻的认识。不过，作为一个有道德（误）的良好青年，还是不要给已经枯竭的 IPv4 地址填堵了，还是赶紧玩玩 IPv6 的网络吧。然后在 TUNA 群里受青年千人续本达 (@heroxbd) 的安利，本地搭建一下 NAT64+DNS64 的环境。不过考虑到宿舍还是拿不到有线的 IPv4 地址，我就先利用苹果先前在强制 iOS 的应用支持 NAT64 网络的同时，在 macOS 上为了方便开发者调试，提供的便捷的建立 NAT64 网络的能力。

首先在设置中按住 Option 键打开 Sharing，点击 Internet Sharing，勾上 Create NAT64 Network 然后把网络共享给设备。然后在手机上关掉 Wi-Fi 和 Cellular，发现还能正常上网。此时可以打开 Wireshark 验证我们的成果了：

在手机上打开浏览器，浏览千度，得到如下的 Wireshark 截图： baidu-nat64

这里，2001:2:0:aab1::1 是本机在这个子网中的地址，2001:2::aab1:cda2:5de:87f6:fd78 是我的 iOS 设备的地址，然后 iOS 向 macOS 发出了 DNS 请求，macOS 发送 DNS 请求后得到 baidu.com 的 IPv4 地址之一为 111.13.101.208 ： baidu-dns

上图中，我们可以看到， baidu.com 的 AAAA 记录是 2001:2:0:1baa::6f0d:65d0 ，这个就是 DNS64 转译的地址，前面为网关的 prefix ，后面就是对应的 IPv4 地址： 0x6f=111, 0x0d=13, 0x65=101, 0xd0=208 ，当客户端向这个地址发包的时候，网关发现前缀符合条件，把最后的这部分 IPv4 地址取出来，自己把包发送到真实的地址上去，再把返回来的包再转为 IPv6 的地址返还给客户端。可以验证，剩下的几个地址也符合这个转译规则。

这就实现了：利用一台连接着 IPv6 和 IPv4 两种网络的网关，可以使得 IPv6 这个网络通过网关访问 IPv4。通过配置，也可以使得 IPv4 访问 IPv6 中的地址（即 Stateful 和 Stateless 的区分，需要手动配置映射）。

好处：作为比较成熟的 IPv4 到 IPv6 过渡方案之一，可以让自己组建的 IPv6 网络访问一些仅 IPv4 的网站。 坏处：依赖于 DNS64，必须要经过一层翻译，一些应用或协议可能写死了 IPv4 的地址，该方法可能会失效。

  • 分类于 programming
  • 需要 1 分钟阅读时间

有趣的 Java 日期格式化问题

今天在群里看到有人说，Java 的日期格式化有问题，如果用 YYYY-MM-dd ，今天的日期就会显示 2018-12-31 。我立马在本地用 Java REPL (aka Groovy) 跑了一下，果然如此：

$ date = new Date()
===> Sun Dec 31 10:51:26 CST 2017
$ import java.text.SimpleDateFormat
===> java.text.SimpleDateFormat
$ new SimpleDateFormat("YYYY-MM-dd").format(date)
===> 2018-12-31

解决方案是，把格式换为 yyyy-MM-dd ，确实就可以了。于是我就去研究了一下文档： Class SimpleDateFormat ，发现了问题：

y 代表 year ，而 Y 代表 week year 。根据 week year ，因为今年最后的一个星期在明年的部分更多，于是这个星期被归在了明年，所以这一周属于 2018，这就可以解释之前的那个输出问题了。

  • 分类于 devops
  • 需要 1 分钟阅读时间

在 macOS 上试用 Gentoo/Prefix

前几天参加了许朋程主讲的 Tunight，对 Gentoo 有了一定的了解，不过看到如此复杂的安装过程和长久的编译时间，又看看我的 CPU，只能望而却步了。不过，有 Gentoo/Prefix 这个工具，使得我们可以在其它的操作系统（如 macOS,Solaris 等）上在一个 $EPREFIX 下跑 Portage，也就是把 Portage 运行在别的操作系统，当作一个包管理器，并且可以和别的操作系统并存。

首先还是祭出官网：Project:Prefix。

首先设定好环境变量 $EPREFIX ，之后所有的东西都会安装到这个目录下，把 bootstrap-prefix.sh 下载到 $EPREFIX ，然后 ./bootstrap-prefix.sh ，会进行一系列的问题，一一回答即可。建议在运行前设置好 GENTOO_MIRRORS=http://mirrors.tuna.tsinghua.edu.cn/gentoo 由于 TUNA 没有对 gentoo_prefix 做镜像，只能把 distfiles 切换到 TUNA 的镜像上。

然后。。。

stage1...

stage2..

stage3.

emerge -e @world BOOM

经过 n 次跑挂以后，终于搞完了 stage3，然后 SHELL=bash ./bootstrap-prefix.sh $EPREFIX startscript 生成 startprefix ，在外面的 SHELL 中向切进来的时候运行这个即可。

然后就可以使用Gentoo/Prefix了。注意！此时的 $PATH 仅限于 $EPREFIX 下几个目录和 /usr/bin /bin 所以很多东西都会出问题（Emacs, Vim, Fish etc）。小心不要把自己的目录什么的搞挂了。

然后就可以假装试用 Gentoo 了！

哈哈哈哈哈哈哈

死于编译 libgcrypt 和 llvm。

  • 分类于 programming
  • 需要 1 分钟阅读时间

LSP 和 C++

之前时间，巨硬发布了 LSP（Language Server Protocol），目的是解决目前 IDE 和各语言的 m+n 问题。想法很好，不过直到最近，终于有我觉得可以用的工具出来了，并且已经代替了我在使用的其它的插件。

由于我最近主要就是做做程设作业，做做 OJ 这些，主要就是和 C++ 打交道。所以我当然就开始找一些比较成熟的 C++的 LSP server。有一个 Sourcegraph 维护的 langserver.org ，上面有着目前的各个语言和编辑器/IDE 的支持情况，我刚才提到的 cquery 也会加入到这个列表里去。从这个列表里可以看到，我用的比较多的 Python 和 Haskell 都已经有不错的的 LSP server，我已经开始在本地体验 pyls 和 hie 了，感觉做得挺不错的。

回到 C++，我的主力编辑器是 Emacs，其次是 CLion，而 Emacs 上的LSP 支持 lsp-mode也在快速发展，与之配合的lsp-ui 也出现了很多很棒的功能。

下面开始编译并配置cquery：

git clone https://github.com/jacobdufault/cquery --recursive
cd cquery
./waf configure # to use system clang, append --use-system-clang
./waf build

然后配置 Emacs：

(use-package lsp-mode
  :ensure t
  :diminish
  lsp-mode
  :commands
  (lsp-mode)
  :config
  (lsp-define-stdio-client
   lsp-pyls
   "python"
   #'get-project-root
   '("/usr/local/bin/pyls")))

(use-package lsp-ui
  :commands
  lsp-ui-mode
  :init
  (add-hook 'lsp-mode-hook 'lsp-ui-mode))

(use-package cquery
  :load-path
  "path_to_cquery/emacs"
  :config
  (setq
     cquery-executable "path_to_cquery/build/app"
     cquery-resource-dir "path_to_cquery/clang_resource_dir"))

接下来，需要配置 基于 Clang 的 工具都需要的 Compilation Database。Sacrasm 对这个有一个非常完整的总结 ，可以查看里面的方法。我这里推荐在 CMake 项目中用 CMake 自带的，加上nickdiego/compiledb-generator 应付基于Makefile/Autotools的项目。如果都不适用，就按照cquery的README写一个简单的.cquery文件即可，不需要Bear那种必须关闭SIP的方案。

然后就可以享受很多功能了！还是挺好用的。

  • 分类于 programming
  • 需要 3 分钟阅读时间

Nginx 的内存池实现

今晚参加了 Tunight，会长给我们讲了 Nginx 的一些内部运作的机制和原理。中间的时候，会长展示的代码中用到了线程池方面的一些函数，但是大多地方只有调用 ngx_pcalloc 而没有看到相应的对象释放的过程，于是在演示的最后，会长应大家要求对 Nginx 魔幻的内存池实现做了现场代码分析。

在分析的中途遇到了很多坑，最后才终于理清了内存池的工作原理。这里直接解释结论吧。以下代码均摘自 Nginx 1.13.7，代码都可以在官方仓库找到。

首先分析一下创建一个内存池的函数： 

ngx_pool_t *
ngx_create_pool(size_t size, ngx_log_t *log)
{
    ngx_pool_t  *p;

    p = ngx_memalign(NGX_POOL_ALIGNMENT, size, log);
    if (p == NULL) {
        return NULL;
    }

    p->d.last = (u_char *) p + sizeof(ngx_pool_t);
    p->d.end = (u_char *) p + size;
    p->d.next = NULL;
    p->d.failed = 0;

    size = size - sizeof(ngx_pool_t);
    p->max = (size < NGX_MAX_ALLOC_FROM_POOL) ? size : NGX_MAX_ALLOC_FROM_POOL;

    p->current = p;
    p->chain = NULL;
    p->large = NULL;
    p->cleanup = NULL;
    p->log = log;

    return p;
}

现在开始分段分析这个函数：在这里，一个内存池用一个 ngx_pool_t (aka struct ngx_pool_s) 类型的数据进行包装，所有的关于内存池的操作都基于相应的内存池对象。 ngx_log_t 表示输出信息的对象，与内存池无关，后面也不会讨论它。

    p = ngx_memalign(NGX_POOL_ALIGNMENT, size, log);
    if (p == NULL) {
        return NULL;
    }

    p->d.last = (u_char *) p + sizeof(ngx_pool_t);
    p->d.end = (u_char *) p + size;
    p->d.next = NULL;
    p->d.failed = 0;

这里通过调用 ngx_memalign 分配一段（能对齐就对齐，不能对齐就放弃的）以 size 为大小的内存，做为这个内存池第一个块的内存，这个块的头是完整的，其中 p->d.last 和 p->d.end 分别表示可用于分配对象的内存段的开始和结束，在用 p->d.next 连接起来的链表中，每个链表实际上只有 d 是存储了数据，后面的各个域都不再使用。这里的 p->d.failed 涉及到链表的优化，在以后会接触到。

    size = size - sizeof(ngx_pool_t);
    p->max = (size < NGX_MAX_ALLOC_FROM_POOL) ? size : NGX_MAX_ALLOC_FROM_POOL;

    p->current = p;
    p->chain = NULL;
    p->large = NULL;
    p->cleanup = NULL;
    p->log = log;

    return p;

这里的 size 计算出实际用于对象分配的内存大小， p->max 存储了当前这个块最大能容纳的对象的大小， p->current 会和上面的 p->d.failed 合在一起对链表进行优化。 p->chain 与其他功能关系较密切，不会在本文中展开，而 p->cleanup 允许外部注册一些清理函数，实现起来并不难。

接下来，由于 ngx_pnalloc 和 ngx_pcalloc 都和 ngx_palloc 相近，这里只对 ngx_palloc 进行分析：

void *
ngx_palloc(ngx_pool_t *pool, size_t size)
{
#if !(NGX_DEBUG_PALLOC)
    if (size <= pool->max) {
        return ngx_palloc_small(pool, size, 1);
    }
#endif

    return ngx_palloc_large(pool, size);
}

这里分了两种情况，如果要分配的内存大于一个块的最大值，那么这段内存必须要单独分配单独维护，所以调用了 ngx_palloc_large ，下面对其分析：

static void *
ngx_palloc_large(ngx_pool_t *pool, size_t size)
{
    void              *p;
    ngx_uint_t         n;
    ngx_pool_large_t  *large;

    p = ngx_alloc(size, pool->log);
    if (p == NULL) {
        return NULL;
    }

    n = 0;

    for (large = pool->large; large; large = large->next) {
        if (large->alloc == NULL) {
            large->alloc = p;
            return p;
        }

        if (n++ > 3) {
            break;
        }
    }

    large = ngx_palloc_small(pool, sizeof(ngx_pool_large_t), 1);
    if (large == NULL) {
        ngx_free(p);
        return NULL;
    }

    large->alloc = p;
    large->next = pool->large;
    pool->large = large;

    return p;
}

这里的 ngx_alloc 就是对 malloc 的简单封装，直接分配一段内存，然后向 pool->large 中以 ngx_pool_large_t 组成的链表中插入。这里有一个小优化：因为 ngx_pool_large_t 本身也要占用内存，为了复用已经被释放的 ngx_pool_large_t ，尝试链表的前几项，如果几项中都没有空的位置，因为 ngx_pool_large_t 本身是一个很小的对象，自然可以复用自己在内存池中分配对象的方法 ngx_palloc_small ，然后把它加入到 pool->large 的链表的第一向前。如果很大的内存都在分配后很快释放，这种方法可以复用很多的 ngx_pool_large_t 。

接下来分析 ngx_palloc_small ：

static ngx_inline void *
ngx_palloc_small(ngx_pool_t *pool, size_t size, ngx_uint_t align)
{
    u_char      *m;
    ngx_pool_t  *p;

    p = pool->current;

    do {
        m = p->d.last;

        if (align) {
            m = ngx_align_ptr(m, NGX_ALIGNMENT);
        }

        if ((size_t) (p->d.end - m) >= size) {
            p->d.last = m + size;

            return m;
        }

        p = p->d.next;

    } while (p);

    return ngx_palloc_block(pool, size);
}

首先，从 pool->current 遍历（这样做的原因下面会提到）已有的各个块，寻找有没有哪个块能容纳下现在需要的大小，如果能就可以调整 p->d.last 返回，否则就分配一个新的块到内存池中，再从新的块中分配需要的大小的内存。需要一提的是，在设计中，小的对象是随着整个内存池的销毁而被一起释放的，不会在中途被释放，而大的对象尽量要用完即释放。接下来分析 ngx_palloc_block ：

static void *
ngx_palloc_block(ngx_pool_t *pool, size_t size)
{
    u_char      *m;
    size_t       psize;
    ngx_pool_t  *p, *new;

    psize = (size_t) (pool->d.end - (u_char *) pool);

    m = ngx_memalign(NGX_POOL_ALIGNMENT, psize, pool->log);
    if (m == NULL) {
        return NULL;
    }

    new = (ngx_pool_t *) m;

    new->d.end = m + psize;
    new->d.next = NULL;
    new->d.failed = 0;

    m += sizeof(ngx_pool_data_t);
    m = ngx_align_ptr(m, NGX_ALIGNMENT);
    new->d.last = m + size;

    for (p = pool->current; p->d.next; p = p->d.next) {
        if (p->d.failed++ > 4) {
            pool->current = p->d.next;
        }
    }

    p->d.next = new;

    return m;
}

为了节省内存，结构体中并没有记录实际分配的内存块的大小，于是根据第一个块的大小分配当前的块，虽然这里用的也是一个类型为 ngx_pool_t 结构体，实际上只用到了 new->d 中的内容维护块组成的链表和块内的分配情况。然后从 pool->current 开始找块的链表的结尾，找到节尾后把当前的块加到结尾的后面，然后把刚才需要分配的小对象的地址返回。与此同时，由于调用这个函数的时候，一定是当前的对象在已有的从 pool->current 开始的块中都放不下了，我们给这些块的 p->d.failed 进行自增，意思是说这个块在分配新的对象的时候又一次放不下了，如果放不下的次数比较多，我们可以认为这个块已经装得比较满了，那么，我们把 pool->current 设为它的后继，以后在分配新的对象的时候就会自动跳过这些比较满的块，从而提高了效率。

ngx_int_t
ngx_pfree(ngx_pool_t *pool, void *p)
{
    ngx_pool_large_t  *l;

    for (l = pool->large; l; l = l->next) {
        if (p == l->alloc) {
            ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, pool->log, 0,
                           "free: %p", l->alloc);
            ngx_free(l->alloc);
            l->alloc = NULL;

            return NGX_OK;
        }
    }

    return NGX_DECLINED;
}

从 ngx_pfree 的实现可以看出，只有大的对象才会要求尽快释放，小的对象和没有被手动释放的大的对象都会随着内存池生命周期的结束而一起释放。如 ngx_destroy_pool 中的实现：

void
ngx_destroy_pool(ngx_pool_t *pool)
{
    ngx_pool_t          *p, *n;
    ngx_pool_large_t    *l;
    ngx_pool_cleanup_t  *c;

    for (c = pool->cleanup; c; c = c->next) {
        if (c->handler) {
            ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, pool->log, 0,
                           "run cleanup: %p", c);
            c->handler(c->data);
        }
    }

#if (NGX_DEBUG)

    /*
     * we could allocate the pool->log from this pool
     * so we cannot use this log while free()ing the pool
     */

    for (l = pool->large; l; l = l->next) {
        ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, pool->log, 0, "free: %p", l->alloc);
    }

    for (p = pool, n = pool->d.next; /* void */; p = n, n = n->d.next) {
        ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, pool->log, 0,
                       "free: %p, unused: %uz", p, p->d.end - p->d.last);

        if (n == NULL) {
            break;
        }
    }

#endif

    for (l = pool->large; l; l = l->next) {
        if (l->alloc) {
            ngx_free(l->alloc);
        }
    }

    for (p = pool, n = pool->d.next; /* void */; p = n, n = n->d.next) {
        ngx_free(p);

        if (n == NULL) {
            break;
        }
    }
}

这个函数首先调用了一系列用户定义的 pool->cleanup 链表中的函数，允许自定义回收一些特定的资源。然后对每一个 pool->large 链表中的内容分别释放，最后再把各个块中所有的内存整块释放。注意 ngx_large_block_t 也是存在块中的，所以顺序不能反了。

  • 分类于 programming
  • 需要 1 分钟阅读时间

在 Jupyter Notebook 中运行 C++ 代码

刚刚在 HN 上看到了这么一个文章：Interactive Workflows for C++ with Jupyter HN ，终于可以在 Jupyter Notebook 里跑 C++代码了，很开心，于是开始自己研究了起来怎么本地跑。

首先当然是更新一波 jupyter，安装一波 cling：

pip3 install -U jupyter
brew install cling

然后根据官方教程里的要求执行：

cd /usr/local/share/cling/Jupyter/kernel
pip3 install -e .
jupyter kernelspec install cling-cpp11
jupyter kernelspec install cling-cpp14
jupyter kernelspec install cling-cpp17
jupyter kernelspec install cling-cpp1z

结果发现找不到jupyter-kernelspec，遂重装了一下jupyter-client这个包，果然就可以了。打开一个 notebook 测试：

jupyter notebook

然后创建一个 C++14 的 Notebook，结果发现一直 Kernel rebooting，错误信息是说找不到../Cellar/cling/0.5/lib/libclingJupyter.dylib。这一看就是路径处理的问题，当前目录肯定不是/usr/local，肯定出现了什么问题，然后研究发现cling-kernel.py中对cling判断是否是个连接，如果是连接则按照连接去找cling的安装目录，但是！没有考虑到这个连接是个相对路径的问题（Homebrew 你背锅吗）。于是我愉快地改了代码并提交了PR。修复了以后就可以用了。

以下是一个小小的例子： 

>> jupyter console --kernel cling-cpp14
Jupyter console 5.2.0

cling-X


In [1]: #include <stdio.h>
Out[1]:

In [2]: char *s = "Hello, world!";
input_line_4:2:12: warning: ISO C++11 does not allow conversion from string literal to 'char *' [-Wwritable-strings]
 char *s = "Hello, world!";
           ^
Out[2]:

In [3]: printf("%s",s);
Hello, world!Out[3]:
(int) 13

Okay，大功告成！

  • 分类于 others
  • 需要 2 分钟阅读时间

用 CPUID 获取评测机器的 CPU

受用 CPUID 检测各大 OJ 测评机所用的 CPU（以及日常黑 BZOJ）的启发，我决定去测试一下徐老师自己写的 OJ（名为 Tyche）所跑的机器是什么 CPU。于是我改造一下代码，用以下代码测评：

#include <stdint.h>
#include <iostream>
#include <time.h>
#include <cpuid.h>
#include <sys/time.h>
static void cpuid(uint32_t func, uint32_t sub, uint32_t data[4]) {
    __cpuid_count(func, sub, data[0], data[1], data[2], data[3]);
}
int main() {
    uint32_t data[4];
    char str[48];
    for(int i = 0; i < 3; ++i) {
        cpuid(0x80000002 + i, 0, data);
        for(int j = 0; j < 4; ++j)
            reinterpret_cast<uint32_t*>(str)[i * 4 + j] = data[j];
    }

    struct timeval stop, start;
    gettimeofday(&start, NULL);
    while(1) {
        gettimeofday(&stop, NULL);
        if(stop.tv_usec - start.tv_usec > (str[##EDITME##] - 32) * 10000)
            break;
    }
}

经过测试，usleep()和clock()都被封杀，但是gettimeofday()存活了下来。然后我就不断地C-a上面的###EDITME###，根据评测出来的时间推算出字符串，然后得到以下结果：

0 ~ 7 : PADDING
8 73 I
9 110 n
10 116 t
11 101 e
12 108 l
13 40 (
14 82 R
15 41 )
16 32 SPC
17 67 C
18 111 o
19 114 r
20 101 e
21 40 (
22 84 T
23 77 M
24 41 )
25 32 SPC
26 105 i
27 51 3
28 45 -
29 50 2
30 49 1
31 50 2
32 48 0
33 32 SPC
34 67 C
35 80 P
36 85 U
37 32 SPC
38 64 @
39 32 SPC
40 51 3
41 46 .
42 51 3
43 48 0
44 71 G
45 72 H
46 122 z

连起来就是这个 CPU：

Intel(R) Core(TM) i3-2120 CPU @ 3.30GHz

相比之下，还是比 BZOJ 好哈哈哈（又黑 BZOJ）。后来有大神在群里建议，可以用字符串比较的方式，对了就让题目 AC，不对就 WA。这个方法更加适合手里已经知道了一些常见 CPUID 的返回字符串，这里就是这样。

  • 分类于 others
  • 需要 1 分钟阅读时间

一个代替 Pulse Secure 客户端的工具

清华的校外 VPN 服务使用的是 Pulse Secure，所以在外网我们需要在客户端上安装 Pulse Secure 才能使用内网的 info 和网络学堂等网站。但是 Pulse Secure 一是非自由软件二界面难看，所以我找到了一个代替它的工具：OpenConnect.

安装后，输入以下命令：

sudo openconnect --user 你的学号 sslvpn.tsinghua.edu.cn --juniper --reconnect-timeout 60 --servercert sha256:398c6bccf414f7d71b6dc8d59b8e3b16f6d410f305aed7e30ce911c3a4064b31

然后输入你的 info 密码即可。

  • 分类于 programming
  • 需要 1 分钟阅读时间

分析一个我第一次见的素数测试函数

今天逛到这个连接，发现其中的第四种素数判定方法很有意思：

#include<stdio.h>
#include<math.h>
int p[8]={4,2,4,2,4,6,2,6};
int prime(int n)
{
    int i=7,j,q;
    if(n==1)return 0;
    if(n==2||n==5||n==3)return 1;
    if(n%2==0||n%3==0||n%5==0)return 0;
    q=(int)sqrt(n);
    for(;i<=q;){
        for(j=0;j<8;j++){
            if(n%i==0)return 0;
            i+=p[j];
        }
        if(n%i==0)return 0;
    }
    return 1;
}
void main()
{
    int n;
    scanf("%d",&n);
    if(prime(n))puts("Yes");
    else puts("No");
}

仔细研究发现，这里利用的是这样的原理：

  1. 判断是不是 1, 2, 3, 5 及其倍数
  2. 从 7 开始，不断考虑其是否是素数，那么，这个 p 是什么回事呢？

首先把 p 的各个元素加起来，和为 30，然后就可以发现一个规律： 7 为质数，7+2=9 不是质数，7+4=11 为质数，11+2=13 为质数，13+2=15 为合数，15+2=17 为质数，17+2=19 为质数，19+2=21 为合数，21+2=23 为质数，23+2=25 为合数，25+2=27 为合数，27+2=29 为质数，29+1=31 为质数，31+2=33 为合数，33+2=35 为合数，35+2=37 为质数。 观察以上所有的合数，都含有 2 或者 3 或者 5 的因子，而 30 又是 2,3,5 的公倍数，也就是说，后面的素数模 30 的余数不可能是上面这些合数，而剩下的素数才可能是真正的素数，于是跳过了很多素数的判断。

至于这个函数的性能如何，还需要进一步测试来进行判断。

  • 分类于 programming
  • 需要 1 分钟阅读时间

关于 scanf 和 scanf_s 的问题

最近作为程设基础的小教员，收到很多同学的求助，关于scanf和scanf_s的问题已经遇到了两次，特此写一篇博文来叙述一下这个问题。

一开始，有同学问我， 

char a;
scanf("%c",&a);
为什么会报错？我说，vs 默认强制要求使用 scanf_s 函数，于是我建议这位同学把这个错误信息关掉了。嗯。经过百度，这位同学的问题解决了。

后来，又有一位同学问我， 

char a;
scanf_s("%c",&a);
程序为什么会崩溃？我想了想，如果 scanf_s 和 scanf 是一样的行为，这段代码是没问题的。但 scanf_s 既然安全，必然是在字符串方面做了处理。这里的 char*勉强也算一个？网上一查，果然，应该写成scanf_s("%c",&a,1);，字符串则要写成scanf_s("%s",str,sizeof(str))，来保证缓冲区不会溢出。

但是，这样解决这个问题又面临着不同的选择：

  1. 学习scanf_s和scanf的不同，把所有scanf换成scanf_s并做相应的修改。 这样当然符合了语言进化的潮流，也会让 vs 闭嘴。但是，scanf_s 只有在 C11 标准中有，而且，根据cpprefrence.com 上关于 scanf 的描述，只有在__STDC_LIB_EXT1__被定义且在#include<stdio.h>之前#define __STDC_WANT_LIB_EXT1__才能确保使用scanf_s能使用，当然在 vs 较新版本中是默认可以使用的。但是，程设基础的作业是要丢到 oj 上的，而 oj 上的编译器不一定支持这些，所以这个选项不行。
  2. 坚持用scanf，自己按照题目要求保证缓冲区不溢出，同时让 vs 闭嘴。 网上已有教程，已经讲的很全面了，大家可以根据这个教程把 vs 教训一顿。为了能在 oj 里跑，建议用里面的方法五到八。（个人最推荐在文件头添加#define _CRT_SECURE_NO_WARNINGS）

以后再遇到这个问题，我就丢这个连接上来就好了咯。yeah！

  • 分类于 others
  • 需要 1 分钟阅读时间

一个搞笑的伸展树的 Wiki

光哲同学在群里发了这个链接，特别搞笑，特此分享： 伸展树 - 百度百科

伸展树（Spaly Tree，事实上在国内 IO 界常常被称作 Tajarn 发明的 Spaly Tree，与此同理的还有 Terap），也叫分裂树，是一种二叉排序树，它能在 O(n log n) 内完成插入、查找和删除操作。它由 Daniel Sleator 和 Robert Tajarn 发现，后者对其进行了改造。它的优势可以不断伸展枝干（一个月 2~3 次），从而使树冠散开，提高光合作用效率。木材坚硬，是重要的经济类乔木。与其他植物不同的是，伸展树可以进行出芽生殖，繁殖速度极快。

  • 分类于 others
  • 需要 1 分钟阅读时间

回顾昨天的酒井知识竞赛

昨天晚上，我作为蒟蒻组的一员在三教 2102 参加了酒井知识竞赛，并因此鸽掉了 TUNA 和 Lab mU 的迎新会 hhh，不过运气好拿到了二等奖的好成绩，获得 Paperang 便携打印机一台。中间遇到了好一些网络方面的知识，这对于没有记忆 OSI 模型的我无疑有巨大的难度。下面是几道比较有印象的题目：

  1. 以下哪个不是编程语言？ A. J B. L C. R D. K 这题不难，R 肯定对，J 见过，K 略微有印象，选 B
  2. IPv6 链路层地址解析的协议是？ A. ARP B. Neighbour Solicitation C. Neighbour Advertisement D. Neighbour Discovery 对于一个没研究过 IPv6 的人来说这只好蒙了。。。ARP 是 IPv4 时代的，ND(Neighbour Discovery 则是 IPv6 时代的新产物，把 ARP 和 ICMP 等协议的功能都包含了进来，并且有新的功能。之前样题里还出现过问 IPv6 中去掉了 Unicast,Anycast,Multicast,Broadcast 中的哪种，答案是 Broadcast。
  3. 第一个把程序错误称做 bug 的是？ 选项太多忘了，答案是 Grace Hopper，因为当时一只飞蛾意外飞入了机器导致了故障，后来慢慢就流传下来了。
  4. 以下不是网络操作系统的是？ A. Windows NT B. OS/2 warp C. DOS D. Netware 当时我没见过 D，于是就选了。。。然后就挂了，Netware 是 Novell 开发的系统，OS/2 warp 当然是历史悠久的系统啦，而 DOS=Disk Operating System 所以没有“网络”二字。。。晕倒
  5. 以下是用作局域网的协议是？ A. TCP/IP B. IPX/SPX C. NetBEUI D. RS-232-C TCP/IP 当然不仅限于局域网，RS-232-C 是接口，当时蒙了 B 结果就对了，白白拿了 50 分哈哈哈。IPX/SPX 是 Novell 设计用在 Netware 系统上的局域网协议，NetBEUI 则是 NetBIOS 的一个历史遗留的一个“别称”。
  6. 姚期智的夫人给谁取了中文名？ 当然是 Donald Ervin Knuth 啦！高德纳万岁！