跳转至

博客

  • 分类于 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 啦！高德纳万岁！
  • 分类于 hardware
  • 需要 1 分钟阅读时间

华为随行 WiFi 2 mini 开箱

前段时间，我办了 4G 升级，移动送了一张副卡，有不少免费的流量，由于我的手机是 iPhone 不支持双卡，老爸就借了我他的 GlocalMe 当成 MiFi 来用，不过呢 GlocalMe 放在这里当然是大材小用了，所以我就网购了华为随行 WiFi 2 mini，把我的副卡装上一个壳放进去就可以了！把这个 MiFi 插入电脑，会弹出一个目录，里面有 Win/Mac 的驱动安装文件，打开后在网络设置里就有 HUAWEI_MOBILE 的连接了，并自动打开网络配置界面。设置一下 SSID 和密码，就能正常使用了，手机连上也很正常，手机上可以下载 HUAWEI HiLink 来配置 MiFi，挺爽的。随赠的有联通的上网卡，不过我准备在北京买个上网卡放 MiFi 里面用。

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

In macOS Sierra, Karabiner-Elements finally support complex modifications

In favor of this commit, Karabiner-Elements now supports the much welcomed yet long-lost feature, namely complex modifications that enable users to trigger complex keypress.

Now I can achieve this: 

If I press <Enter>, then:
1. If <Enter> is pressed alone, then send <Enter>.
2. If <Enter> is pressed along with other keys, then send <Control> + Other.

By adding this code to ~/.config/karabiner/karabiner.json : 

"complex_modifications": {
    "rules": [
        {
            "manipulators": [
                {
                    "description": "Change return_or_enter to left_control. (Post return_or_enter if pressed alone)",
                    "from": {
                        "key_code": "return_or_enter",
                        "modifiers": {
                            "optional": [
                                "any"
                            ]
                        }
                    },
                    "to": [
                        {
                            "key_code": "left_control"
                        }
                    ],
                    "to_if_alone": [
                        {
                            "key_code": "return_or_enter"
                        }
                    ],
                    "type": "basic"
                }
            ]
        }
    ]
},
in one of profiles.

Note: the snippet above is adopted from this example. You can explore more examples since the GUI is not updated accordingly yet.

Important: Until NOW (2017-06-15), this feature is only implemented in beta versions of Karabiner-Elements (at least 0.91.1).

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

等时圆

最近学校老师讲了一下等时圆。先从这个题讲起：

在同一个地方向不同倾角光滑斜面用不同的初速度上滑，到达最高点所用时间相等，求最高点的轨迹是什么？

A. 直线 B. 椭圆 C. 抛物线 D. 圆

当时做这个题目的第一想法是把 x 和 y 座标表示出来：

\[ \frac{1}{2}gsin\theta{}t^2=l, y=lsin\theta, x=ycot\theta \]

然后就傻眼了，并得不到 x 与 y 的关系式。当然了可以求出几个点，强行带入二次曲线通式求解。不过想了想还是用解析几何的方法去做吧：

\[ \frac{1}{2}gsin\theta{}t^2=\sqrt{x^2+y^2}, sin\theta=\frac{y}{\sqrt{x^2+y^2}} \]

这么一代入，显然是圆。但既然这是物理题，可不可以用物理方法做呢？

可以，这就是等时圆。

啥叫等时圆？

等时圆就是，在一个光滑圆环上选择任意一点，让一个小球从这个点沿着光滑直杆到圆的最低点，无论这个点在哪里（最低点不算哈），时间都是一样的。怎么证明？

很简单：设小球与最低点连线与数值方向上夹角为\(\(\theta\)\)，那么

\[ s=2Rcos\theta, \frac{1}{2}gcos\theta{}t^2=s \]

你会发现 t 与\(\(\theta\)\)无关。证明完毕。

其实也可以倒过来：从圆的最高点往各个方向下滑，到达圆周时间相等。

好了，到此为止内容都没什么，但你会想问这和前面那道题目有什么关系呢？这怎么等时圆？重力往下诶。运动可是往右上方。

Here comes the black magic :)

我们考虑向下滑到最低点的那个等时圆，在这个圆周上滑倒最低点的时间都相等。好，我们把这个图沿着竖直方向旋转 180 度形成一个球，想想这个球上每一个点到最低点时间是不是也一样？那么考虑逆过程，让小球从斜面上滑下来，我对刚才的球体再竖着切一刀，得到的平面不就是题目中那个吗？得证。

当然了最好能有动画说明，限于本人时间问题暂时不提供 ^_^

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

A good way to show git diff for compressed files

I have found a good way to track changes in .gz files: Add these to ~/.gitconfig:

[core]
  attributesFile = ~/.gitattributes
[diff "zip"]
  textconv = unzip -p
  binary = true
[diff "gz"]
  textconv = gzcat
  binary = true
[diff "bz2"]
  textconv = bzcat
  binary = true
[diff "xz"]
  textconv = xzcat
  binary = true
[diff "tar"]
  textconv = tar -O -xf
  binary = true
[diff "tar-bz2"]
  textconv = tar -O -xjf
  binary = true
[diff "tar-gz"]
  textconv = tar -O -xzf
  binary = true
[diff "tar-xz"]
  textconv = tar -O -xJf
  binary = true

[diff "odf"]
  textconv = odt2txt
[diff "pdf"]
  textconv = pdfinfo
[diff "bin"]
  textconv = hexdump -v -C

And these to ~/.gitattributes:

*.tar diff=tar
*.tar.bz2 diff=tar-bz2
*.tar.gz diff=tar-gz
*.tar.xz diff=tar-xz
*.bz2 diff=bz2
*.gz diff=gz
*.zip diff=zip
*.xz diff=xz

*.odf diff=odf
*.odt diff=odf
*.odp diff=odf
*.pdf diff=pdf
*.exe diff=bin
*.png diff=bin
*.jpg diff=bin

And then you can git diff for .gz files.

Codes are adapted from https://gist.github.com/RsrchBoy/11197048 and https://git.wiki.kernel.org/index.php/GitTips#Getting_a_plain-text_diff and https://gist.github.com/kbaird/2654115.

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

The end of senior two

Finally the end of Senior 2 arrives. I'm on the way to Senior 3. The summer vacation is rather short which is really common in China. These days I have been diving into Emacs by subscribing both emacs and emacs-devel mailing list. It contributes to my English as well. I can learn a lot of new words and expression thanks to the nice and convenient feature of looking up a word in iOS.

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

Exciting new software updates

Just got a piece of great news: GHC 8.0.1 is out! See the announcement [here][http://article.gmane.org/gmane.comp.lang.haskell.ghc.devel/11928].

So excited! And Emacs 25 release will be out soon. Using Emacs 25.0.94 now. Many new features available. See [this][http://puntoblogspot.blogspot.com/2016/05/emacs-251-news.html] for more information.

Recently I have finally started to use mu4e and gnus. What makes it truly great is that they integrate org, bbdb and so on.

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

Having a bad cold. Really annoying.

Okay, here comes the interesting links:

https://glyph.twistedmatrix.com/2015/11/editor-malware.html

http://kitchingroup.cheme.cmu.edu/blog/2016/04/07/Writing-hy-code-from-hy-code/

https://github.com/holomorph/transmission

https://github.com/bergey/org-babel-diagrams

http://ess.r-project.org/

http://projects.haskell.org/diagrams/

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

Tips on git shallow clone

Just learned a new tip on git shallow clone. As you know, some repository are really really large, such as emacs and linux. Cloning is slow and unstable. And there is no way to pause and resume a git clone. So I use shallow clone to clone them. But what if I want to clone other branches?

From here: http://stackoverflow.com/a/27393574/2148614

git remote set-branches origin '*'
  • 分类于 others
  • 需要 10 分钟阅读时间

Listen and write down subtitles of Cameron's speech

Here is the subtitle: 

We meet in a week that could change the United Kingdom for ever. Indeed, it could end the United Kingdom as we know it. On Thursday, Scotland votes, of the future of our country is at stake. On Friday, people could be living in a different country with a different place in the world and the different future ahead of it. This is the decision that could break up our family of nations and rips Scotland from rest of the United Kingdom. And we must be very clear, there is no going back from this. No re-run. This is a once and for all decision. If Scots vote 'yes', the U.K. will split and we will go on separate ways forever. When people vote on Thursday, they are not just voting for themselves, but for their children and grandchildren and the generations beyond. So I want to speak very directly to the people this country today about what is at stake. I believe I speak for millions of people across England, Wales, and North Ireland and many in Scotland too who would be utterly heart-broken by the break-up of the United Kingdom, utterly heart-broken to wake up on Friday morning, to the end of the country we love, to know that Scots will no longer join with the English, welsh-man, Irish, in the army, navy, and air force. [???] U.K. white celebrations and commemorations [???] U.K.'s fourteen teams in the Olympics to the British lines. The United Kingdom, would be no more, no U.K. pension, no U.K. passports, no U.K. pound. The greatest example of the [???] in the world have ever known of openness of people of different nationalities and face coming together as one, would be no more. It would be the end of the country that lodged the enlightenment(?) and abolished the slavery and drove the industrial revolution and defeated fascism. The end of a country that people around the world respect and admire. The end of a country that all of us call home. And you know what, we built this home together. It's only become Great Britain, because of the greatness of Scotland because of the thinkers the writers the artists the leaders the soldiers and inventors that make this country what it is. It's Alexander Fleming and David Hume J.K. Rowling Andy Murray and all the millions of people who play the part in this extraordinarily success story. The Scots who let the charge on pensions and the [???] and social justice we did all this together. For the people of Scotland to walk away now, we will be like painstakingly building a home and then [???] the door and throwing away the keys. So I would say that everyone voting on Thursday, please remember this is just [???] country. This is the United Kingdom. This is our country. And you know what makes it a truly great country, it is not a [???]. It is our values. British values. Fan of freedom, justice. The values that say wherever you are whoever you are, your life has dignity and worth. The values that say we don't work on by when the people are sick. We do not ask for your credit card in the hospital. We don't turn our backs when you get old and frail. We don't turn a blind eye or cold heart to people around the world from repair and cry and for help. This is what Britain means. This is what makes our country 'Yes the greatest on Earth'! And it is why millions of us could not bear to see that country ending for good for ever on Friday. Now i know that many people across Scotland were planning to vote yes. I understand why this might sound appealing. It is the promise of something different. I also know that the people who running the 'yes' campaign painting a picture of Scotland that is better than everywhere. And they can be good painting the picture. But when something looks too good to be true, that is usually because it is. And it's my duty to be clear about the lightly consequences of a 'yes' vote. Independence, would not be a trial separation but would be a painful divorce. As a Prime Minister, I have to tell you what that would mean. It would mean we no longer share the same currency. It would mean the arm forces we built up together over centuries being splitted up for ever. It would mean our pension funds being sliced up at some cost. It would mean the borders we have would become international and may no longer be so easily crossed. It would mean the automatic support that you currently get from British embassies when you are traveling around world the that would come to end. It would mean over half of Scottish [???] suddenly from one day to the next begin provided by banks in a foreign country. It would mean the interest rates in Scotland are no longer set by the bank with England's robust ability and security that promises. And it would mean for many banks that remain in Scotland, if they ever gotten to travel, it will be Scotish taxpayers and Scottish taxpayers and loan, that will bare the costs. It would mean that we no longer pull exhausted across the whole of out United Kingdom to pay for institutions [???] national health service or our welfare system. This is what guess work, there are no question marks, no maybe this, or maybe that. The nationalists want to break up U.K. funding on pensions, the U.K. funding on health care, the U.K. funding and comprehensive protection on national security. These are the facts. This is what would happen and end to the things that we should share together. And people in Scotland must know these facts before they make this once and for all decision. And one of the consequences is not to scare [???]. It is like warning a friend about the decision that they might take that will affect the rest of their lives and the lives of their children. I [???] this because I don't want the people of the Scotland to be sold a dream that disappears. Now I know that some people say we have heard about the risks and uncertainties, but we still want change. And look, the United Kingdom is not a perfect country. The country is, of course, constantly changing and improve people's lives. No one is content when there are still children living in poverty. No one is content when there are people struggling and the young people not reaching their full potential. And yes, of course, every political party is different, but all of us, all of us, conservatives, labor, [???], nationalists, we are all on a constant mission to change our country for the better. The question is, how to you get that change. And for me, it is simple. You don't get the change you want, by ripping your country apart. You don't get change by underlying your economy and damaging your businesses and diminishing your place in the world. But you can't get real concrete change on Thursday. If you vote 'no', businesses usual is not on the [???] paper. The status clown is gone. The campaign has swepted away. There is no going back to the way things were. A vote for 'no', means real change. If we [???] that change in practical terms, with a plan and a process. If we gotta know vote on Thursday that will trigger a major unpresidentive program of devolution with the [???] powers for the Scottish [???]. Major new powers will protest spending. Some welfare services will have agreed that time table for that stronger Scottish [???], a timetable for bringing that new powers that will go ahead in frozen [???]. White paper by November put into draft [???] by January, this is the timetable that is now agreed by all the main political parties in [???]. And I am prepared to work with all the main parties to deliver this during 2015. So a 'no' vote actually means faster, fairly, safer and better change. And this is vital point. Scotland is not a observer in this fairs of this country. Scotland is shaping and changing the United Kingdom for the better. Also did they [???] at any point in the last three hundred years. And Scotland will continue to help shape the constitution of our country. And Scottish people who enjoys the [???]  without losing the U.K. pension, the U.K. pound and the U.K. passport. Real change is Scotland's for the taking. The [???] and make [???] decisions but with this security and being in the United Kingdom and with idol risks of [???] alone. It is the both well or both worse. The Scotland's identity is your [???] strong Scottish culture, strong Scottish art, and strong [???] Scotland. And in the last fifteen years, you built a strong British [???]. Not all [???] institutions but a permanent one. So the vote on Thursday, it is not about whether Scotland is a nation. Scotland is a proud strong successful nation. The vote on Thursday is about two competing nations for Scotland's future. And that's the nationalist's vision. Narrowing down, going alone, breaking all ties with the United Kingdom. Or there is the patriotic vision, they strongs Scottish nation allied to the rest of the United Kingdom with its own strong Scottish Parliament. And it's hard. And with the benefit of working together in the U.K on [???] on pensions on health care funding, currency and interest rates. It is really the best of both wills. And it's the best way to get real change and secure a better future for your children and your grandchildren which all this vital debate is all about. [Clap Drink Water] And speaking of family, there is quite simply how I feel about all of this. We're a family. The United Kingdom is not one nation. We are four nations in a single country. That could be difficult but it is wonderful. Scotland, England, Welsh, North Ireland, different nations with individual identities competing with each other, even in time in raging each other. But It still mean so much stronger together. We're a family of nations. And why should the generations of that family be forced to choose whether to identiy only with their emperor or only with London. Why should they have to choose which embassy they want to go to when they are in trouble abroad. Or pack that passport when they go to see friends, loved ones and family. A family is not a compromise or second best. It is the magical identity that makes us more together than we can ever be apart. So please, do not break this family apart. In human relations, it is almost no good thing to turn away from each other to put up walls or score new lines on the map. Why should we take one Great Britain and turn it into separate smaller nations. What is that an answer to? How will that help ambitious young people who wanna make the mock on the world. Or [???] just want security. Or the family relying on jobs that will made in the U.K. Let no one fool you, that 'yes' is a positive vision. It is about dividing people. It is about closing doors. It is about making forigners our friends and family. That is not a optimistic vision. [Clap] The optimistic vision is about our family of nations staying together. Therefore, each other in the hard times, coming through the better times, we're just pulled through the great reception together. If we're not moving forward together, the road had been longer but it is finally lead upwards. And that's why I ask you to vote 'no' to walking away. Vote 'no' & you are voting for a bigger and broader and better future of Scotland. And you are investing in the future for your children and grandchildren. So this is our message to the people of Scotland: we want you to stay. Head hard and sow we want you to stay. Please don't mix up the temporary and permanent. Please don't think I am frustrated with politics right now and I just walk out of the door and never come back. If you don't like me, I won't be here for ever. If you don't like this government, it won't last for ever. But if you leave the United Kingdom, that will be for ever. Yes, the different parts of the U.K. do not always see eye to eye. Yes we need change, we'll deliver it. But to get that change together bright future would don't need to tear our country apart. [Yeah and Clap] In two days' time, this long campaign will be to an end. And you stand on the [???] of the billing board. I hope you ask yourself this: will my family and I truly be better off? By going alone? Will we really be more save and secure? Do I really want to turn my back on the rest of Britain? And why it is that so many people across the world asking why would Scotland want to do that? Why? And if you don't know the answers of these questions, then please vote 'no'. At the end of the day, all the eyes on this campaign can be rejuiced to a single fact. We are better together. As you reach your final decision, please, please, don't let anyone tell you you can't be a pride Scot and a pribe Brit. [Clap] Please, don't lose faith in what this country is and what we can be. Don't forget what a great United Kingdom you are a part of. Don't turn you back to what is the best family in the nations in the world. And the best hope for your family in this world. So please from all of us, vote to stick together, vote to stay, vote to save our United Kingdom. Thank you. [Clap and The End].

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

Logo is a lisp dialect

Most of us have learnt how to use PCLogo to draw some graphics. Logo is a dialect of Lisp in fact, so most of us used a Lisp dialect at a early time! For some people, it is earlier than C++. Cool.

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

I'm here to share some interesting links. I do not have much time writing the blog now.

Recently I have been working on CodeFalling/MacGesture on Github. If you are interested in it, go and have a look.

Here are the links to share: https://twitter.com/PoolpOrg/status/694593152670437376 https://github.com/wellle/targets.vim http://thecodelesscode.com/case/225 https://twitter.com/zhangyuze320602/status/706457155763712000

I have done reading the biography of Steve Jobs. Great book.

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

Using chinese pyim

Recently i have been using tumashu's chinese-pyim. It's great to write Chinese right in Emacs. But as the personal dict is empty, this must be a hard time for me to build it. And i have found several bugs, too. After all, this project is great. I have donated some money to it.