残剑

Stop walking today and you'll have to run tomorrow!

Base64编码解码算法

| Comments

Base64使用ascii码子集的64个字符,即大小写的26个英文字母,0~9,+,/。编码基于3个字符,每个字符用8位二进制表示,一共24位,再分为4四组,每组6位表示一个Base64值(例如0就是A,27就是b)。Base64值如下:

1
2
3
4
5
6
7
8
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f',
'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
'w', 'x', 'y', 'z', '0', '1', '2', '3',
'4', '5', '6', '7', '8', '9', '+', '/',

如果被加密的字符串每3个一组,还剩1或2个字符,使用特殊字符”=“补齐。例如编码只有2个字符“me”,m的ascii是109,e的是101,用二进制表示分别是01101101、01100101,连接起来就是0110110101100101,再按6位分为一组:011011、010110、010100(不足6位补0),ascii分别是27、22、 20,即Base64值为bWU,不足4字用=补齐,因此bWU=就me的Base64值。

Minilzo无损压缩库测试例子(二)

| Comments

在minilzo无损压缩库中提供了一个测试例子(文件名为testmini.c),对该示例作一个分析。如果我们要使用该库中的四个基本函数,首先必须包含以下的头文件。

1
#include "minilzo.h"

其中,lzo_init()函数包含在以下的头文件中。

1
#include "lzoconf.h"

lzoconf.h已包含在minilzo.h中,所以在写测试例子时只需包含minilzo.h头文件即可。

将原始数据存放在in中且定义其长度为IN_LEN,压缩后的数据存放在out中且定义其长度为OUT_LEN。因为输入块可能是不可压缩的,所以我们必须提供多一点的输出空间。

1
2
3
4
5
6
7
8
9
10
11
#if defined(__LZO_STRICT_16BIT)
#define IN_LEN      (8*1024u)
#elif defined(LZO_ARCH_I086) && !defined(LZO_HAVE_MM_HUGE_ARRAY)
#define IN_LEN      (60*1024u)
#else
#define IN_LEN      (128*1024ul)
#endif
#define OUT_LEN     (IN_LEN + IN_LEN / 16 + 64 + 3)

static unsigned char __LZO_MMODEL in  [ IN_LEN ];
static unsigned char __LZO_MMODEL out [ OUT_LEN ];

Minilzo无损压缩库介绍(一)

| Comments

在网络上传输大批量数据的时候,网络的传输速度是固定的(比如100 Mb的以太网实际测量的传输速度大概在10 MB/s左右),而想要在固定时间内传输更多容量的数据,最常见的解决方案是——在传输之前通过一定的算法把数据的容量压缩,然后通过网络传输,对端接收到数据之后再通过相应的算法进行解压还原。如果“压缩的时间 + 压缩后数据的传输时间 + 解压缩的时间 < 未压缩数据的传输时间”,就相当于提高了单位时间内的传输能力,拓宽了网络传输的带宽。

minilzo库使用介绍

lzo是一个开源的无损压缩c语言库,其优点是压缩/解压缩比较迅速且占用内存小等特点。具体可查看 这里,提供了比较全的lzo库和一个minilzo库。minilzo库提供了1个c文件和3个头文件,解压后的目录树如下:

1
2
3
4
5
6
7
8
9
10
minilzo-2.06$ tree
.
├── COPYING
├── lzoconf.h
├── lzodefs.h
├── Makefile
├── minilzo.c
├── minilzo.h
├── README.LZO
└── testmini.c

PF_NETLINK应用实例:NETLINK_KOBJECT_UEVENT的实现

| Comments

udev的文档介绍:

  1. dynamic replacement for /dev。作为devfs的替代者,传统的devfs不能动态分配major和minor的值,而major和minor非常有限,很快就会用完了。udev能够像DHCP动态分配IP地址一样去动态分配major和minor。

  2. device naming。提供设备命名持久化的机制。传统设备命名方式不具直观性,像/dev/hda1这样的名字肯定没有boot_disk这样的名字直观。udev能够像DNS解析域名一样去给设备指定一个有意义的名称。

  3. API to access info about current system devices 。提供了一组易用的API去操作sysfs,避免重复实现同样的代码。

求两个整数的最大公约数

| Comments

辗转相除法又名欧几里德算法(Euclidean algorithm),用于求两个正整数的最大公因子的算法。它是已知最古老的算法,可追溯至公元前300年。它首次出现于欧几里德的《几何原本》中,而在中国则可以追溯至东汉出现的《九章算术》。

设两数为a、b(b<a),求它们的最大公约数的步骤如下:用b除a,得a=bq…r1(0≤r1)。若r1=0,则(a,b)=b;若r1≠0,则再用r1除b,得b=r1q…r2(0≤r2)。若r2=0,则(a,b)=r1,若r2≠0,则继续用r2除r1,…如此下去,直到能整除为止。其最后一个非零余数即为(a,b)。

Linux下C语言伪随机数编程

| Comments

在日常生活中,我们经常会遇到随机数(比如丢骰子,抓阄,抽签等等),那么在程序中如何实现随机数呢?现在很多操作系统内核都会提供相应的api,通过获取一些计算机运行时的原始信息(如内存,电压,物理信号等等,它们的值在一个时间段可以保证是唯一的)来生成随机数。下文介绍如何使用rand、srand来生成伪随机数。

rand产生伪随机数

Linux中rand()会返回一随机数值,范围在0至RAND_MAX 间,其中RAND_MAX定义在stdlib.h,其值为2147483647。

以下例子利用rand函数生成随机数。

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

#define LOOP_TIMES    5

int main(int argc, char *argv[])
{
    int i;

    for(i=0; i< LOOP_TIMES; i++)
        printf("%d ", rand());

    printf("\n");

    return 0;
}

运行结果:

$ ./rand
1804289383 846930886 1681692777 1714636915 1957747793 
$ ./rand
1804289383 846930886 1681692777 1714636915 1957747793

从以上的结果可以看出,rand两次产生的随机数是一样的,之所以这样是因为“在调用rand函数产生随机数前没有先利用srand()设好随机数种子”。如果未设随机数种子,rand()在调用时会自动设随机数种子为1。

Linux下PDF文件的操作与转换

| Comments

在Linux中常常涉及到多种文档格式(如doc、txt、html、rtf等等),为了方便文件传递,就可能需要在各种格式之间进行转换。下面介绍几个命令行下的工具,用于将pdf文件转换成其它我们需要的文件格式。

Pdftk

如果说PDF是电子纸张,那么pdftk就是电子起钉器、打孔机、粘合剂、解密指环和X光镜片。pdftk是一个简单的工具,可以对PDF文档进行各种日常操作,让你简单而自由地操作PDF。它不需要Acrobat,并且可以运行在Linux,Windows,Mac OS X,FreeBSD和Solaris上。在Debian/Ubuntu中你可以通过apt安装pdftk:

$ sudo aptitude install pdftk

内核中关于isdigit和min(max)的实现

| Comments

isdigit、min、max等函数或宏定义是我们平时最常使用的,但往往没有更多的去思考它们的效率及其副作用。下面让我们来看看,内核是如何实现它们的。

isdigit

在标准C中,isdigit函数可以用来判断字符是否为0~9之间的数字。比如:

int a = isdigit('1');
int b = isdigit('a');
int c = isdigit(3);

可以使用宏定义去实现这个简单的函数,如下所示:

#define isdigit(c) ((c) >= '0' && (c) <= '9')