yield

今天看 C# 发现这样一种用法:

class IntManager
{
	int[] arr = { 0, 1, 2, 3 };
	public IEnumerator<int> GetEnumerator()
	{
		for (int i = 0; i<4; i++)
		{
			yield return arr[i];
		}
	}
}

是的……对我这样孤陋寡闻的人来说,这就是这么神奇……居然可以这样写出迭代器!

而且根据一些资料来看,这个迭代器是随用随取的,也就是说如果资源不在内存上,那就可以需要多少取多少,不会一次性全部取回来,非常方便。

以前我只知道 yield 用在 coroutine 上。不过把这两个一结合,我就发现了神奇的现象……Tcl 的 yield 其实也不过是这样而已。

proc y {} { 
    set i 0
    while 1 {
        yield [incr i]
    }
}
coroutine coro y ;; -> 1,这里会调用一次 y 所以是 1
coro ;; -> 2
coro ;; -> 3
coro ;; -> 4

没错,这还是一个……嗯,我们不如来研究一些好玩的。

proc fibo {} {
    ;# 第一次 yield 之前可以尝试做一些初始化工作
    yield ;# 然后用 yield 返回结果,这里自然是不需要的
    set a 0
    set b 1
    while 1 {
        ;# a,b = b,a+b
        set t $b
        set b [expr $a+$t]
        set a $t
        yield $a
    }
}
coroutine next fibo
next ;; -> 1
next ;; -> 1
next ;; -> 2
-> 就是 1,1,2,3,5,8,13,21,34,55,...

实际上用这个求这个数列的效率不高,因为求过一次数据就丢弃了,不如以前写过的一个缓存版本快。但是这个版本不会爆栈(相比递归版本),因为根本只有一个栈帧和循环版的效率理论上来说差不多,没测试。

给初中生的电学科普

在百度贴吧上看见了一个类似的话题,试着自己又写了一篇。(可能是浪费时间的行径 =_=||)行文风格参考了 The Theoretical Minimum 这本书。

继续阅读

Debian 和 Fedora 的包管理

元包和软件组

安装一批软件,Debian 使用了元包(meta-package),而 Fedora 选择了 groupinstall。

Debian 的元包支持起来比较方便,不需要对包管理进行特殊的修改,但是有个问题,假如删除了元包依赖的任何一个包,那么元包就会被删除,被依赖的所有包都会标记成 orphan。

autoremove 和 clean_requirements_on_remove

Debian 的 autoremove 功能很早就有了,Fedora 一直没有这个功能,像 package-cleanup 之类的比 apt-get 难用一百倍。

后来 yum 有了 clean_requirements_on_remove,在 remove 的同时找出他依赖的不再有用的包并删除。这一点我觉得比 apt-get 好,毕竟这个要手动再调用一次。(aptitude 则和 yum 行为一样)

另一点是 autoremove 比较危险,尤其是 meta package 的大量使用容易导致整个系统被炸飞……而 yum 则安全许多。

CSAPP 2.1:字节序、大端与小端

终于比较认真地读了一下 CSAPP 的一点点,顺便做点记录,也算是以往经验的小小总结吧。诸如 [DCL13-C] 的标注,是 CERT C 安全编码标准的编号(看来我写的代码还是不错的嘛)。

大端、小端是机器中两种表示数据的方法(字节序),大端法是把最高有效数字排在低地址,小端法是把最高有效数字排在高地址。举例来说,0x12345678 这个数字,在小端机器中会被存储为 78 56 34 12(低->高),相反在大端机器中是 12 34 56 78(低->高)。

以程序验证:

#include <stdio.h>
#include <stdlib.h>

void show_bytes(const void *bytes, size_t len)
{
	const unsigned char *bytes_; // [DCL00-C], [INT07-C]
	size_t i;

	bytes_ = bytes;
	for (i = 0; i < len; i++)
	{
		printf(" %.2X", bytes_[i]);
	}
	printf("\n");
}

int main(void) {
	int val = 0x12345678;
	show_bytes(&val, sizeof(val));
	return EXIT_SUCCESS;
}

运行该程序,输出 78 56 34 12,说明我的机器就是小端的。

注意,在这里我稍微修改了一下 CSAPP 上的例程。有如下修改:

  1. 将 byte_pointer 修改为了 const void *:任何指针都能被隐式转换为 void * 而没有警告,方便使用。另外加上 const 确保不会误修改传入数据。[DCL13-C]
  2. 将 len 的类型修改为了 size_t:对 len 来说有符号是毫无意义的,len 不可能小于 0。实际上,在运行中如果传入负数将会溢出(指针都无符号)。[INT01-C]
  3. 这里的计数器 i 并不是通常的 int 类型,而是与和它比较的 len 一致,关于这一点可以看 CS:APP (中文版)的第 53 页关于 FreeBSD getpeername 漏洞的讨论。[INT02-C]

那么如何判断大小端呢?在运行时可以用类似上面的方法这样判断:

bool bigendian()
{
	static int val = 0x12345678;
	if (*(((char *)&val)+3) == 0x78) // warning: magic number 3
	{
		return true;
	}
	return false;
}

或者用 union:

union
{
	int val;
	char ch[4];
} _bigendianstub;

bool bigendian() // requires C99-compliant compilers; stdbool.h must be included
{
	_bigendianstub.val = 0x12345678;
	if (_bigendianstub.ch[3] == 0x78)
	{
		return true;
	}
	return false;
}

一般来说,在一个机器中只能是大端或小端,而操作系统也必然与之对应,于是可以直接在编译时确定:

const char ch[4] = { 0x00, 0xff, 0xff, 0xff }; // [DCL00-C]
#define LITTLEENDIAN ((*(int*)ch)<0) // [PRE02-C]
#define BIGENDIAN (!LITTLEENDIAN) // [PRE02-C]

这里比较流氓,直接把数字写到数据段里面去了,然后利用了 int 最高位表示符号的特点解决问题。相当于直接把 0x00FFFFFF 当作 int,显然我们发现,在大端机器中这个数字表示 0x00FFFFFF,在小端机器中这个数字表示 -256。

当然,以上不过是示例而已,在真实环境中,我们有编译器提供的宏来确定。gcc 的相关宏是 __BYTE_ORDER。

说了这么多,大小端究竟有什么影响呢?主要影响就是与其他机器交互了。个人电脑基本都是小端,而网络字节序则是大端,意味着我们要在发送数据时进行转换。操作系统提供了 ntoh(network to host)、hton (host to network)系列函数可以实现这个目的。但是在大端机器上,这两个函数显然无法得到小端结果!因此我们自己实现一套,以下是完整的测试代码:

#include <stdio.h>
#include <stdlib.h>

const char ch[4] = { 0x00, 0xff, 0xff, 0xff };
#define LITTLEENDIAN ((*(int*)ch)<0)
#define BIGENDIAN (!LITTLEENDIAN)

void show_bytes(const void *bytes, size_t len)
{
	const unsigned char *bytes_;
	size_t i;

	bytes_ = bytes;
	for (i = 0; i < len; i++)
	{
		printf(" %.2X", bytes_[i]);
	}
	printf("\n");
}

int swap_byteorder(int orig)
{
	int ret;
	char *ptrf, *ptrl;

	ret = orig;
	ptrf = (char*)&ret;
	ptrl = ((char*)&ret)+3; // warning: magic number 3
	for (; ptrf < ptrl; ptrf++, ptrl--)
	{
		int t;
		t = *ptrf;
		*ptrf = *ptrl;
		*ptrl = t;
	}
	return ret;
}

inline int tobe(int orig) // requires C99-compliant compilers
{
	if(BIGENDIAN) return orig;
	return swap_byteorder(orig);
}

inline int tole(int orig) // requires C99-compliant compilers
{
	if(LITTLEENDIAN) return orig;
	return swap_byteorder(orig);
}

int main(void) 
{
	int orig, le, be;

	orig = 0x12345678;
	le = tole(orig);
	be = tobe(orig);
	printf("original (%s):", LITTLEENDIAN?"little endian":"big endian");
	show_bytes(&orig, sizeof(int));
	printf("little endian:");
	show_bytes(&le, sizeof(int));
	printf("big endian:");
	show_bytes(&be, sizeof(int));
	return EXIT_SUCCESS;
}

只实现了 int 的大小端转换,实际上其余类型乃至任意类型的大小端转换都很容易实现,故从略。

提醒:字符串(特指 char[])没有大小端转换,每个 char 就是一个字节,从低地址端开始排列(想想「字节序」这个名称)。实际上我们上面的一切都是依赖这个的。另外还依赖了「64 位、32 位系统 int 都是 4 字节」。如果需要很好的可移植性,这些还不够。以上关于字节序的讨论有一个直接推论:跨机器交换文件应当尽量使用文本文件,二进制文件必须设计良好、经过大量测试才能使用。

(翻到后面才发现好多内容都是作业……)

Debian 安装后的配置

以下内容以 Jessie 和标准 GNOME 桌面为例。

切换到网络源

如果是 DVD 安装,那先确保有网络,然后切换到网络源上。如果你不幸是开源驱动不支持的 BCM 用户并且安装的时候没有提供固件,请看下面的安装网卡驱动,然后再回来。

编辑 /etc/apt/sources.list:

deb http://security.debian.org/ jessie/updates main non-free contrib
deb-src http://security.debian.org/ jessie/updates main non-free contrib

deb http://ftp.cn.debian.org/debian/ jessie main non-free contrib
deb-src http://ftp.cn.debian.org/debian/ jessie main non-free contrib

deb http://ftp.cn.debian.org/debian/ jessie-updates main non-free contrib
deb-src http://ftp.cn.debian.org/debian/ jessie-updates main non-free contrib

注意我开启了 main、non-free 和 contrib,如果你对非自由软件不适请自行删减。

这个源速度一般,可考虑用中科大的源

安装 VPN

安装 VPN(以 PPTP 为例)。

sudo apt-get install network-manager-pptp-gnome

安装 Broadcom 网卡驱动

这是不幸买到 BCM 的用户的必修课。

如果是用 DVD 安装好系统(但是没提供固件),那么恭喜你,你已经有了准备条件。

安装好当前内核的 linux-headers。

从另外一个机器上下下来 broadcom-sta-dkms,然后安装。

开启模块:

modprobe -r b44 b43 b43legacy ssb brcmsmac
modprobe wl

搞定。

更新到最新系统

因为我是先从 Wheezy 安装的,所以又体验了一把更新系统。

首先把 sources.list 修改到欲更新到的版本的列表,如 wheezy 更新到 jessie,就把所有的 wheezy 替换成 jessie。

然后 apt-get dist-upgrade。

然后删掉已移除的包。aptitude purge '~c'。

重启 (*),搞定。

(*) 如果你是不幸的 BCM 用户,请一定记得安装好新内核的 linux-headers,切记。最好在重启前就构建好新的 wl 模块。如果不小心忘了,可以暂时撤退到旧内核上,从 grub 中可以选择。

Fedora VPN connection

firewall-cmd --direct --add-rule ipv4 filter INPUT 0 -p gre -j ACCEPT
firewall-cmd --direct --add-rule ipv6 filter INPUT 0 -p gre -j ACCEPT
firewall-cmd --reload

 

Do this if you are experiencing connection failures... (source Ask Fedora)

Fedora Copr

Fedora Copr is a build system (like OBS) where you can easily set up your own software repository, but unlike OBS, it's specifically for Fedora.

DNF, a package manager introduced in Fedora 21, has built-in support for Fedora Copr. When you want to get Rust programming language installed, for example, just do this:

dnf copr enable fabiand/rust-binary
dnf install rust-binary

In case a software you want is not in the official repository, search Fedora Copr for it, chances are that it's already there.

神奇的电子产品

如果在几年前我玩 Arduino 的话,估计我不会这么惊讶,不过学了好多原理之后,就对这玩意里面的很多东西感到惊奇了……

电压怎么就神奇的反转了,波形怎么就神奇的变化了,传感器怎么就能输出信号了,这些信息怎么就被芯片截获了,之类的,越是玩下去,就越想知道这小小的黑盒子到底是怎么制造的……

Tcl 现代方法:变量与作用域

Tcl 是个很老很老的语言了,而且最让人叹惋的是,这语言一开始就饱受关注,然后就被广泛使用了,从此作出大的改动已经不太可能了。变量与作用域问题就是 Tcl 时代限制在这方面的体现。

继续阅读

C++11 的 decltype 一种用法

#include <string>
#include <iostream>
using namespace std;

class clsA
{
public:
    int value()
    {
        return 1;
    }
};

class clsB
{
public:
    string value()
    {
        return "yes/no";
    }
};

template<class Type>
auto foo(Type x) -> decltype(x.value())
{
    return x.value();
}

int main(void)
{
    clsA oa;
    clsB ob;
    cout << foo(oa) << foo(ob) << endl;
    return 0;
}