Electronic Joint Business

Solution for E-Business

gnu

GPerf 和完美哈希函数

GNU Gperf 工具用来生成一种 “完美的” 散列函数(perfect hash function),可以将用户提供的一组特定字符串生成散列表、散列函数和查找函数的 C/C++ 代码。 所谓完美散列函数或完美 Hash 函数,指存在这样一个 hash 函数 F,可以将一个含有 n 元素的用户特定关键字集合 N 到集合 W, N 的关键字被唯一映射到 W 的 0..k-1 范围,其中 k>=n。如果 k=n 那么 F 就是“最小化完美 hash 函数”。

最小化完美 hash 函数具有两个特性:

  • 只需要执行一次查找就能完成静态搜索结构中的关键字识别,即所谓的“完美”。
  • 为保存关键字所分配的内存刚刚可以容纳关键字集合,不会多余。即“最小化”。

Gperf 被普遍地用在多种商业编译器、研究型编译器、语言处理工具的词法分析器上,用来生成关键字识别器,包括:GNU C, GNU C++, GNU Pascal, GNU Modula 3 和 GNU indent 等等。Gperf 将从用户提供的文件中(即关键字文件,通常使用 .gperf 作为扩展名,但不做强制要求)生成 C/C++ 源代码。所有代码被定向到标准输出,然后必须重定向到类似下面的文件:

gperf  -L C++ keyfile.gperf > perfecthash.hpp

注意: -L 选项将指示 gperf 生成 C++ 代码。

Gperf 会生成一个 0..K 元素的静态查找结构和一对 C 函数的源代码。利用这些函数只需要一次查找,就可以判断给定的字符串 S 是否在集合 W 中。这两个函数是:

>>> 阅读全文

 

, , ,

ADA 语言编程 (一)

文章评价:
在上个世纪 70 年代,美国国防部 (DoD) 发现其所属的嵌入式计算机系统项目中,使用的编程语言数量逐日增多,其中很多语言十分陈旧或者需要依赖于硬件,而且没有一种语言支持安全的模块化编程,对此 DoD 感到十分担心。为此,DoD 在 1975 年成立了高级语言工作组 (HOLWG),它的使命是就是寻找或者创造某种适合国防部需要的编程语言,以便减少现有编程语言数量。该小组最终的工作成果就是 Ada 语言。由此,这类项目中使用的高级编程语言的数量从 1983 年的 450 种编程语言,减少到 37 种(1996年)。

高级语言工作组精心设计了 Steelman 语言规范,这是一系列用来述明编程语言需要满足哪些要求的文件。许多既有的语言按次规范进行了审查,但最终(1977年) 团队得出结论:没有现有的语言符合规格。

最终 HOLWG 提出了开发一种新的编程语言的建议,并且雇佣了四个承包商分别进行有关方案开发,代号分别是红 (Benjamin Brosgol 所领导的Intermetrics)、 绿 (Jean Ichbiah 所领导的 CII Honeywell Bull)、 蓝 (John Goodenough 所领导的 SofTech) 和黄 (Jay Spitzen 所领导的SRI International。1978 年 4 月公开审查之后 红和绿这两个方案进入了下一阶段。在 1979 年 5 月,最终选择了 Jean Ichbiah 所领导的 CII Honeywell Bull 所实现的“绿”方案,并定名为 Ada — — 这是为了纪念 Augusta-Ada-Lovelace 伯爵夫人。该方案受到了上世纪 70 年代 Ichbiah 和他的小组所开发 LIS 编程语言的影响。

由于 Ada 以安全性为第一(safety-critical) 的特性 ,因而 Ada 除了在军事上得以应用,也应用到了那些软件 bug 会产生严重后果的商业项目中,例如航空和空中交通管制、 商业火箭 (例如阿丽亚娜 4 和 5),卫星和其他空间系统、 铁路运输和银行。例如,波音 777 的线传飞控系统软件就是 Ada 编写的。加拿大的自动化空中交通系统是由 100 万行的 Ada (源代码计数) 构成的。得益于 Ada 的高级分布式处理、 分布式的 Ada 数据库和面向对象的设计,Ada 也用在其他的空中交通系统,如英国的下一代 iFACTS 空中交通管制系统是用 SPARK Ada 设计和开发的, 同时它也运用于法国 TGV 高速铁路系统中的 TVM in-cab 信号系统,以及巴黎、 伦敦、 香港和纽约地铁信号系统。

标准
1983 年该语言成为了 ANSI 标准 (ANSI/MIL-STD 1815A), 该版本未做更多的修改就在 1987 年成为了 ISO 标准 (ISO-8652:1987)。该版本就是我们知道的 Ada 83,(按 ANSI 接受为标准的时间),有时也按 ISO 接受为标准的日期称为 Ada 87。

>>> 阅读全文

 

, , , ,

阅读 Grub 源代码 (一) X86 汇编及 GAS 语法

文章评价:

简介
本文的例子采用 AT&T 汇编语法编写,并用 GNU AS 编译的。该语法的主要优点是它与 GCC 内嵌汇编保持着语法兼容性。不过,这并不是表示 X86 操作符唯一语法。例如,NASM、MASM 就使用了完全不同的语法来表示助记符,操作数和寻址模式及其他高级汇编特性。 AT&T 的语法是类 Unix 系统上的标准,但其他使用 Intel 语法的汇编器,比如 GAS 本身,两种语法都可以接受。

GAS 是 GNU 项目的一部分,它具有可以自由使用、适用于多种操作系统、和 GNC 编译器 (gcc) 和 GNU 链接器 (ld) 等编程工具接口良好等等特点。

如果使用安装了 Linux 操作系统的电脑,通常默认就安装了 GAS。如果使用的是 Windows 操作系统,则可以安装 Cygwin 或者 MinGW 来获得 GAS 和其他编程工具。

GAS 指令一般都采用“ 助记符 源,目的地 ”的格式。例如,下面的 mov 指令:

>>> 阅读全文

 

, , , , , ,

用 autoconf 和 automake 生成 makefile

文章评价:
在 Unix/Linux 上编写程序的人大都遇到过 Makefile,尤其是使用 C/C++ 语言的开发者。用 make 来开发和编译程式的确很方便,可是要编写一个 Makefile 就不那么简单了。而且介绍 Makefile 的资料并不多,GNU Make 那份打印出来要几百页的文件,光看完序言就是花不少时间,难怪许多人谈 Unix 编程而色变。

本文将介绍如何利用 GNU Autoconf 及 Automake 这两套软件来帮助我们“自动”生成 Makefile 文件,让开发出来的软件可以像 Apache,MySQL 等常见应用一样,只要输入 “ ./configure ”, “ make ”,“ make install” 就可以把编译结果安装到系统中。

如果您有心开发开源软件,或主要是在 Unix/Linux 系统下编写程序。希望这份介绍文件能帮助您轻松地进入 Unix/Linux 编程的殿堂。

简介
Makefile 基本上就是“目标”(target), “依赖”(dependencies) 和“动作”三者所组成的一连串规则。而 make 就会根据 Makefile 的规则来决定如何编译 (compile) 和链接 (link) 程序。实际上,make 可做的不只是编译和链接程序,例如 FreeBSD 的 port collection 中,Makefile 可以自动去下载原始程式包,解压缩 (extract) ,打补丁 (patch),然后运行设定并编译,最后安装至系统中。

Makefile 基本构造虽然简单,但如能妥善运用这些规则就也可以玩出许多不同的花样。却也因此,许多人刚开始学习写 Makefile 时会感到没有规范可循,每个人写出来的 Makefile 长得都不太一样,不知道从何下手,而且常常会受限于自己的开发环境,只要环境参数不同或路径被修改一下,可能就需要跟着修改 Makefile。虽然有 GNU Makefile Conventions (GNU Makefile 惯例) 订出一些使用 GNU 程序设计时撰写 Makefile 的一些标准和规范,但是内容很长而且很复杂, 并且经常调整。为了减轻程序设计师维护 Makefile 的负担, GNU 推出了 Automake 这个工具。

>>> 阅读全文

 

, , , ,

Gnu Binutils 命令小结

我们知道, gcc(gnu collect compiler)是一组编译工具的总称,包括c,c++等等,它主要完成的工作任务是“预处理”和“编译”,以及提供了与编译器紧密相关的运行库的支持,如libgcc_s.so、libstdc++.so等。

而binutils提供了一系列用来创建、管理和维护二进制目标文件的工具程序,binutils与gcc是紧密相集成的,没有binutils的话,gcc是不能正常工作的。 Binutils提供了一下的工具,主要有:
addr2line 把程序地址转换为文件名和行号。在命令行中给它一个地址和一个可执行文件名,它就会使用这个可执行文件的调试信息指出在给出的地址上是哪个文件以及行号。

ar建立、修改、提取归档文件。归档文件是包含多个文件内容的一个大文件,其结构保证了可以恢复原始文件内容。

as主要用来编译GNU C编译器gcc输出的汇编文件,产生的目标文件由连接器ld连接。

c++filt 连接器使用它来过滤 C++ 和 Java 符号,防止重载函数冲突。

>>> 阅读全文

 

, ,

详解GNU Make (二) 高级用法

在上一篇文章中,我们了解了 makefile 的基本结构和一些常见用法,在这篇文章中我们会更深入地了解一些“高级用法”,这些用法在实际的例子中相当常见,可以极大地提高 makefile 的编写效率。

Makefile 里有什么?
Makefile 里主要包含了五个东西:显式规则、隐晦规则、变量定义、文件指示和注释。

  • 显式规则。显式规则说明了如何生成一个或多的的目标文件。这是由 Makefile 的编写者显示地指出:要生成的文件、文件的依赖文件和生成命令。
  • 隐晦规则。由于 make 有自动推导的功能,所以隐晦规则可以让编写者比较简略地编写 Makefile,这是 make 所支持的。
  • 变量定义。在 Makefile 中我们可以定义一系列的变量,变量一般都是字符串,有点 C 语言中的宏,当 Makefile 被执行时,其中的变量都会被扩展到相应的引用位置上。
  • 文件指示。其包括了三个部分:一是在 Makefile 中引用另一个 Makefile,类似 C 语言中的 #include;二是指根据某些情况指定 Makefile 中的有效部分,类似 C 语言中的条件编译 #if ;三是定义多行的命令。有关这一部分的内容,我会在后续的部分中讲述。
  • 注释。Makefile 中只有行注释,和 UNIX 的 Shell 脚本一样,其注释是用“#”字符, 类似 C/C++ 中的“//”。如果要在 Makefile 中使用“#”字符,可以用反斜杆进行转义:“\#”。

最后要注意的是,在 Makefile 中的命令,必须要以 Tab 键开始。

Makefile 的文件名

默认的情况下,make 命令会在当前目录下按顺序找寻文件名为 “GNUmakefile”、“makefile”、“Makefile” 的文件,找到了就解释这个文件。在这三个文件名中,最好使用 “Makefile” 这个文件名,因为,这个文件名第一个字符为大写比较显目。最好不要用 “GNUmakefile”,这个文件是 GNU 的 make 识别的。有另外一些 make 只对全小写的 “makefile” 文件名敏感,但是基本上大多数的 make 都支持 “makefile” 和 “Makefile” 这两种默认文件名。

>>> 阅读全文

 

, , , , , ,

详解GNU Make (一) 基本规则

文章评价:
一个较大的项目会有许许多多源文件,一般我们会按类型、功能、模块等类别分别放在若干个目录中,makefile 提供了一系列的规则用于指定哪些文件需要先编译,哪些文件需要后编译,哪些文件需要重新编译,甚至于进行更复杂的功能操作,因为 makefile 就像一个 Shell 脚本一样,其中也可以执行操作系统的命令。

因此,makefile 关系着整个项目的编译规则,带来的好处就是“自动化编译”。一旦写好 makefile,你只需要运行 make 命令,整个工程完全自动编译,极大地提高了软件开发的效率。

负责解释 makefile 中指令的工具是 make。一般来说,大多数的 C/C++ 编译器都提供这个工具,最常见的有:Visual C++ 的 nmake,GNU 的 make。但是不同产商的 make 各不兼容,makefile 语法也略有不同。这里我们以应用最为广泛的 GNU make 来做讲解。

Makefile 介绍
我们先引用 GNU 的 make 使用手册中的一个例子,假设我们的工程有 8 个 C 文件和 3 个头文件,要如何编写 Makefile 来实现自动编译和链接这几个文件。我们的要求是:
1)如果这个工程没有编译过,那么我们的所有 C 文件都要编译并被链接。
2)如果这个工程的某几个 C 文件被修改,那么我们只编译被修改的 C 文件,并链接目标程序。
3)如果这个工程的头文件被改变了,那么我们需要编译引用了这几个头文件的 C 文件,并链接目标程序。

所有这些要求,只需要一个 makefile 就可以完成了。make 命令会自动智能地根据当前的文件修改的情况来确定哪些文件需要重编译,从而自己编译所需要的文件和链接目标程序。

>>> 阅读全文

 

, , , , ,