对于链接器来说，所有的全局符号可分为两种：强符号（Strong symbols），弱符号（Weak symbols）。gcc的attribute中有个attribute((weak))，就是用来声明这个符号是弱符号的。gcc手册中这样写道：

The weak attribute causes the declaration to be emitted as a weak symbol rather than a global. This is primarily useful in defining library functions which can be overridden in user code, though it can also be used with non-function declarations. Weak symbols are supported for ELF targets, and also for a.out targets when using the GNU assembler and linker.
对于这个gcc扩展，这里作了一个简洁的介绍。我们来看更通用的情况。;)

一般来说，函数和已初始化的变量是强符号，而未初始化的变量是弱符号。对于它们，下列三条规则适用：

1. 同名的强符号只能有一个。
2. 有一个强符号和多个同名的弱符号是可以的，但定义会选择强符号的。
3. 有多个弱符号时，链接器可以选择其中任意一个。

这三条规则看起来很好理解，其实不然，尤其是当这些弱符号类型和强符号不同时！表面上看起来正确的程序会导致严重的错误！考虑下面这个csapp中的例子：

===a.c===
int x=7;
int y=5;
p1() {}

===b.c===
double x;
p2() {}

我们把它们一起编译，并且在p2()函数中给x赋值，你会发现，y也改变了！ 虽然x被看作是double，但其定义会取a.c中的int x，也就是说，在b.c中会把a.c中的int x当double来用！这当然是错误！之所以会这样，就是因为上面的规则2。避免这种错误的一个方法是，给gcc加上-fno-common选项。

关于弱符号，man手册中这样解释到：

When a weak defined symbol is linked with a normal defined symbol, the normal defined symbol is used with no error. When a weak undefined symbol is linked and the symbol is not defined, the value of the weak symbol becomes zero with no error.
因此，我们也可以看出：强弱符号和声明没任何关系。弱符号不会有static的storage duration。同名的多个弱符号的定义不应该出现在同一个翻译单元中，如果出现，链接器会选择第一个。

今天被问到如何求一个整数的平方根，不知，速查之，得下面一程序：

unsigned int sqrt(unsigned int n){
    unsigned int a;
    for (a=0;n>=(2a)+1;n-=(2a++)+1);
    return a;
}

Ken Thompson曾被问道如果他能重新设计UNIX他将做什么修改，他回答说：“我会在creat命令后加上个e。”

—《Unix痛恨者手册》
如果我们用上面类似的话来问Dennis M. Ritchie，他或许会说，“我会重新造个关键字来替换static。” 呵呵，读者不必当真，这个是玩笑的话。但足以反映static的不足了，它的含义和它的字面意思并不那么吻合，可以这么说，它是C语言中的一个小的瑕疵。

让我们一起来看一看static究竟是如何偏离它的字面意思的。谈static，必须要明白scope，duration，linkage这三个概念。

在C语言中，一个变量或函数有三个属性：scope，duration和linkage。

scope是由它的位置来决定的，scope分为四种：file scope，function scope，block scope和function prototype scope。局部变量的scope就是函数体（function scope）或者局部块（block scope），即使它是static storage。函数和全局变量的scope肯定是整个文件（file scope）。

duration是存活时间，它分两种：automatic和static（这个static不是关键字static）。它是由前面的修饰符和位置共同决定。局部变量默认的storage是auto，如果前面什么都没加。register指定的变量的duration和auto其实一样，也是automatic的。函数的duration都是static的。全局变量也是。局部变量加了static/extern关键字的duration才是static。

linkage最复杂，它要视多种情况而定。linkage分三种：external linkage，internal linkage和no linkage。函数形参的linkage一定是none，局部变量的linkage也都是none的，除非加了extern关键字。对于全局变量/函数，加了static关键字就是internal，否则就可能是external。

这里还有更让人困惑的就是定义和声明，no linkage的是变量其声明就是定义。而external的变量或函数可以有多个声明，但只有一个是定义。internal的变量或函数在本文件内也必须只有一个定义。尽管如此，但有这样一条原则不会改变：对于所有东西来说，带有初始化的一定是定义（如果我们把函数体看作是对函数的”初始化”）。

从这里我们可以看出，static关键字影响了两种属性：duration，linkage。虽然说linkage和duration就是有那么点儿关系，可这个static的作用还是些许模糊。再加之和上面提到的其它一些东西混合，使得正确理解static/extern关键字更加困难。

It’s really a pain from past, for C.

懒得写了，这里只给出密钥和公钥生成的程序。在此基础上完成加密解密就留给你作为课后作业吧！值得一提的是，用valgrind检查这个程序内存泄漏为0，可能的泄漏也为0，很干净利落。;-)

rsa-use-openssl.c

gets太臭名昭著了，因为它是缓冲区溢出的最大祸根之一。连Linux Programmer’s Manual里都说：“Never use gets().”。没错，你几乎就没有能正确使用它的方法，因为它根本就不关心缓冲区到底够不够，只是一股脑地往里写数据。 如果你写了带gets的程序，gcc甚至会提示：“ warning: the `gets’ function is dangerous and should not be used.”。

可是，如果我们仔细想想，究竟有没有正确使用gets的时候？答案是肯定的。那怎么才能正确使用gets呢？其实也很简单，我们只要设置保卫页面（guard pages）来对付溢出就可以了。在Linux上，我们可以这么做：

include

include

include

int main(void){
int pagesize;
void p;
char buf;
size_t buflen = 4;

pagesize = getpagesize();
p = mmap(NULL, 2*pagesize, PROT_READ, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (p == MAP_FAILED) {
    perror("mmap");
    return -1;
}
if (mprotect(p, pagesize, PROT_READ|PROT_WRITE)){
    perror("mprotect");
    munmap(p, 2*pagesize);
    return -1;
}
buf = (char*)p + pagesize - buflen;

ifdef DEBUG

printf("buf=%p, p=%pn", buf, p);

endif

gets(buf);
puts(buf);
munmap(p, 2*pagesize);
return 0;

}

这时，如果写入的数据超出我们的缓冲区，程序就会收到SIGSEGV而退出。

这学期开了一门网络安全课，应老师要求，最近要做RSA加密算法。前一篇文章中已经提到，我是用Python来实现的整个程序，而且速度上嘛，比用C实现的慢了很多。我还不清楚到底是寻找素数的算法存在问题，还是Python本身的问题。

关于RSA算法的讲解，最好的莫过于wikipedia上的RSA词条。里面已经非常详细地说明了，这里就不再赘述。整个算法中要用到的数学算法有：Extended Euclidean algorithm，Miller-Rabin primality test。当然，你还需要Modulo operation的知识。

整个算法最关键的是找到合适的P，Q，以及求D。前者尤为关键，它几乎决定了整个程序的运行速度。所以，找到一个搜索大素数的好算法是核心问题。关于求D，我并没有使用Extended Euclidean algorithm，而是用了蛮力求解，没关系，这影响不大，关键还是刚才说的那个。

寻找素数的算法我使用了Miller-Rabin primality test，参考了gmp库源代码中nextprime的实现。但速度上仍然远不如C的实现。详细代码如下：

!/usr/bin/env python

import random
import string
import math
import sys

DEBUG = False

def nextprime(n):
i = n + 1 - n%2
while not probably_prime(i):
i+=2
return i

#i = n + 1 - n%2
#m = 2*n
#while i  0):
    r.append(n % 2)
    n = n / 2
return r

def test(a, n):
“””
Returns:

  - True, if n is complex.
  - False, if n is probably prime.
"""
b = toBinary(n - 1)
d = 1
for i in xrange(len(b) - 1, -1, -1):
    x = d
    d = (d * d) % n
    if d == 1 and x != 1 and x != n - 1:
        return True
    if b[i] == 1:
        d = (d * a) % n
if d != 1:
    return True # Complex
return False # Prime

def MillerRabin(n, s = 15):
“””
Returns:

    - True, if n is probably prime.
    - False, if n is complex.
"""
for j in xrange(1, s + 1):
    a = random.randint(1, n - 1)
    if (test(a, n)):
        return False # n is complex
return True # n is prime

def probably_prime(n):
return MillerRabin(n)

def gcd(m, n):
while n:
m, n = n, m % n
return m

def genkey(bits=100):
BIG_NUM = []
P_INT = 0
Q_INT = 0
global P, Q, X, N, D, E

for i in range(bits):
    BIG_NUM.append(random.choice('0123456789'))

P_INT = int(''.join(BIG_NUM))

for i in range(bits):
    BIG_NUM[i] = random.choice('0123456789')

Q_INT = int(''.join(BIG_NUM))

if DEBUG:
    print "p=%d"%P_INT
    print "q=%d"%Q_INT

P = nextprime(P_INT)
Q = nextprime(Q_INT)

if DEBUG:
    print "next prime to p is %d"%P
    print "next prime to q is %d"%Q

N = P*Q
if DEBUG:
    print "n=%d"%N

X = (P-1)*(Q-1)
if DEBUG:
    print "x=%d"%X

while True:
    if gcd(X, E)==1:
        break
    E+=2

if DEBUG:
    print "e=%d"%E

n = 1
while (n*X+1)%E!=0:
    n+=1
D = (n*X+1)/E

if DEBUG:
    print "d=%d"%D

def rsa_encrypt(msg):
enc = []
for c in msg:
enc.append(pow(ord(c), E, N))
return enc

def rsa_decrypt(cmsg):
dec = []
tmp = []
for ec in cmsg:
tmp.append(pow(ec, D, N))
for c in tmp:
dec.append(“%c”%c)
return dec

X = N = D = P = Q = 0
E= 65537

if name==”main“:
DEBUG = True

argc = len(sys.argv)
if argc==1:
    genkey()
elif argc==2:
    genkey(string.atoi(sys.argv[1]))
else:
    sys.exit(-1)

msg = raw_input()
enc = rsa_encrypt(msg)
if DEBUG:
    print enc
dec = rsa_decrypt(enc)
print ''.join(dec)

最近在做RSA加密算法，急需要对大数（很大的数，一般来说是十进制500位以上的数字）进行加法和乘法操作。这就需要对如此大的数操作很快才可以。自然而然，我就想到了Python，它天生就支持大数操作。所以我的RSA也是用Python实现的。

简单地搜了一下网上的一些实现，用C的基本上都采用了gmp库，很牛的一个数字计算的库，接口很方便，而且效率也很乐观。下载一个其中一个还算漂亮的实现，速度超快。相比之下，我的Python程序就慢成马了，难以容忍，优化了一下循环，替换了一个判断素数的算法，效率还是低得出奇。无奈之下，向Herbert求救，在他的提示下，对C和Python的大数操作benchmark了一番。

我用的源代码如下：（声明：C代码编写仓促，很是丑陋，勿模仿！）

include

include

include

include

include

void timediff(struct timeval a,struct timeval b,struct timeval* result)
{
(result)->tv_sec = (a)->tv_sec - (b)->tv_sec;
(result)->tv_usec = (a)->tv_usec - (b)->tv_usec;

if((result)->tv_usec tv_sec;
    (result)->tv_usec += 1000000;
}

}

int main(void)
{
int i;
mpz_t p, q, r;
struct timeval before, after, diff;
char p_str[1024] = {‘1’,};
char q_str[1024] = {‘1’,};

mpz_init(p);
mpz_init(q);
mpz_init(r);
srand(time(NULL));

for(i=1;i<1024;i++)
    p_str[i] = (int)(2.0*rand()/(RAND_MAX+1.0)) + 48;

for(i=1;i<1024;i++)
    q_str[i] = (int)(2.0*rand()/(RAND_MAX+1.0)) + 48;
mpz_set_str(p, p_str, 10);
mpz_set_str(q, q_str, 10);

gettimeofday(&before, NULL);
mpz_add(r, p, q);
gettimeofday(&after, NULL);
timediff(&after, &before, &diff);
printf("add needs time:");
printf("n%-15s : %ld","Seconds", diff.tv_sec);
printf("n%-15s : %ld","Microseconds", diff.tv_usec);
puts("");

gettimeofday(&before, NULL);
mpz_mul(r, p ,q);
gettimeofday(&after, NULL);
timediff(&after, &before, &diff);
printf("multiply needs time:");
printf("n%-15s : %ld","Seconds", diff.tv_sec);
printf("n%-15s : %ld","Microseconds", diff.tv_usec);
puts("");

mpz_clear(r);
mpz_clear(q);
mpz_clear(p);
return 0;

}

!/usr/bin/env python

import time
import string
import random

p = q = r = 0
BIG_NUM = []

for i in range(1024):
BIG_NUM.append(random.choice(‘0123456789’))

p = int(‘’.join(BIG_NUM))

for i in range(1024):
BIG_NUM[i] = random.choice(‘0123456789’)

q = int(‘’.join(BIG_NUM))

before = time.time()
r = p+q
after = time.time()

print r

print “Add needs time: %f us”%((after - before)1000.01000.0)

before = time.time()
r = p*q
after = time.time()

print r

print “Multiply needs time: %f us”%((after - before)1000.01000.0)

实验结果如下：
(C version, compiled with gcc -O9)
$ ./bench
add needs time:
Seconds : 0
Microseconds : 5
multiply needs time:
Seconds : 0
Microseconds : 11

(Python version)
$ ./bench.py
Add needs time: 15.020370 us
Multiply needs time: 207.901001 us

-_-b 刚才搞错进制了。。。 1 second=1000*1000 microseconds 这下对了。Python确实比C慢。抑或是真正的问题出在这里？而不在我的算法？

顺便也在这里问一下：有没有什么好的寻找大素数的算法？？
（整个RSA实现会在以后的文章中贴出。）

SIGKILL和SIGSTOP都是既不能被捕捉，也不能被忽略的，他们是用来给系统管理用的。鉴于此，一般来说用SIGKILL结束一个进程是一个坏主意，因为受害进程将没有时间来做善后工作。所以，你应该优先考虑SIGTERM，然后才是SIGKILL。这也是为什么kill(1)和killall(1)默认发送SIGTERM的原因。同样，这也是关机时init首先发送SIGTERM，然后发送SIGKILL的原因。

一个例外是init进程，它是可以忽略SIGKILL的。僵尸进程也有点儿特别，它们是等待其父进程收养的进程，因此也无法被KILL掉。（想想电视上就知道，僵尸都是杀不死的。^_^）

SIGABRT是中止一个程序，它可以被捕捉，但不能被阻塞。处理函数返回后，所以打开的文件描述符将会被关闭，流也会被flush。程序会结束，有可能的话还会core dump。 当程序调用abort(3)时，该进程会向自己发送SIGABRT信号。所以，SIGABRT一般用于信号中一些关键的处理，assert失败时也会使用它。你不应该去捕捉SIGSEGV和SIGABRT信号，如果收到这种信号，说明进程处于一个不确定的状态，很可能会直接挂起。

初学gcc的人通常会遇到这种警告：

$ echo -n -e “t” | gcc -xc -E -

1 “<stdin>”

1 “<built-in>”

1 “<command line>”

1 “<stdin>”

<stdin>:1:2: warning: no newline at end of file

一些聪明的人很快就可以修复这个警告，在文件结尾回车一下就行了。可以很少会有人去仔细探究，为什么gcc会给出这么一个警告？

原因其实也很简单，因为标准规定如此。C99第5.1.1.2节这样写道：

Each instance of a backslash character () immediately
followed by a new-line character is deleted, splicing
physical source lines to form logical source lines.
Only the last backslash on any physical source line
shall be eligible for being part of such a splice. A
source file that is not empty shall end in a new-line
character, which shall not be immediately preceded by
a backslash character before any such splicing takes
place.
C99 Rationale中进一步指出：
A backslash immediately before a newline has long been used to continue string literals, as well as preprocessing command lines. In the interest of easing machine generation of C, and of transporting code to machines with restrictive physical line lengths, the C89 Committee generalized this mechanism to permit any token to be continued by interposing a backslash/newline sequence.
这么规定的初衷有两个：一是为了每一行都要以换行结束。二是，因为行尾的表示连接下一行，如果一个文件最后一行行尾有，那么，紧跟它也被包含进来的下一个源文件的第一行就会被连接！而如果一个文件以一个空行结束就会避免这种情况的发生。

我们再来看看JC大哥非技术方面值得我们学习的地方吧。这里面，最值得提的就是JC老大退学的事乐。这件事有下面两种传说。一种是说：他不满意大学里面的教授，他曾经说过，最讨厌大学里面填鸭子式的教学，“那些教授为什么不给些项目我们做呢？他给我们一个项目，想做成怎么样，我们就一定做到”，终于最后他忍无可忍，在两个学期后就退学了！（天哪，你们美国都填鸭啊！那我们中国岂不是在喂猪了？）另一种说法是：他考试的时候，说卷子做的太简单了，能不能难一点儿的？老师说不行，别的同学有意见！然后他就不爽了，一怒之下就退学了。当然了，他因此和他的父母产生了隔阂，而他的父母后来看到他比他老子还牛，比他那老老实实念完大学的兄弟还牛N倍的时候也就开始支持他的工作乐。这是后话。在我看来，JC大哥对待大学的态度是非常正确的，在这里引用一下来教训一下悲哀的国人！

JC认为：“如果你是为了正确的理由上学，那么学校将是一个很好的学习知识的场所，大学可以提供极为丰富的信息。‘我现在回想起自己的大学生活，觉得浪费了很多宝贵的时光，我当时应该使用他们的图形工作站和其它设备学习知识’。如果你只是为了获得一个学位，以便找到一份满意的工作，那么我并不支持；但是如果是为了结识聪明人、拓展知识面和学习新知识，那么我完全支持。我并不认为大学是不好的地方，但我并不支持这样的观点——‘你必须上大学，这是唯一的成功之路’。原因很简单，它并不是唯一的成功之路。我认为，对于一些年轻、迅速发展的行业，例如互连网和游戏设计而言，才能和工作经验比学位更加重要，我在招聘的时候从不问别人‘你是否有学位？’我更关心的是‘你做过什么? 能做什么？’。”
（每个被中国教育毒害过的人都应该好好读读上面JC老大的话，然后深刻反思一下自己。）

JC另一点很值得我们学习就是他对待金钱的态度了，这 一点他和Gates差不多。Gates就不说了，人家是世界首富同时也是世界最大的慈善家，Gates夫妇现在已经捐献了他们所有财富的70%！再对比丁x、陈xx这些中国顶级富翁，实在是让人觉得汗颜呀。JC认为，现在他已经拥有了足够的财富，足以维持自己的生活，不必听命于任何人，也不需要想法赚更多的钱，因此没有任何人、任何公司对他产生严重的影响。再想想中国的很多贪官，本来已经很富有，但他们仍然屈从于拥有更多财物的诱惑，不惜使用不正当的手段，最终锒铛入狱……自食其果的说～～！

JC的传奇就讲到这里乐，想知道更多关于此牛的故事就请买一本《Masters of DOOM》读读吧！静下心来，我们掩卷沉思一下：为什么我们不能成为牛人？牛人牛肯定也是有原因的，JC老大本身就是美国梦的样本，他结婚前可是每天坚持编程14个小时！牛是用时间砸出来的！你能做到你也照样牛！恩，这是乐观的结论。悲观一点儿，当然了，有些牛人牛也是靠天分的，比如Bill Joy和Donald Knuth这等牛。哎，不得不承认，有些东西还真是先天的，再努力也改变不了……