Software development kits (SDKs) contain reference manuals, specifications and protocols, technical notes, sample code, and/or development tools — a complete toolset for taking full advantage of Adobe technology.
Support is available for the following SDKs and server products:
Ubuntu 的默认安装方式或许并不为所有用户所接受。譬如说吧，有的用户并不想使用 GNOME 桌面环境，也有的用户并不需要预先安装的所有软件。为了解决上述诸如此类的问题，在安装最小化的 Ubuntu 的基础上，根据各人之喜好执行定制化安装，可能是较好的折中方案。
在安装之前需要确定的一件事情是，如何选择安装 CD。根据本文的要求，下载 Alternate install CD 是比较适合的。为了便于安装，应该将下载后的 ISO 文件烧录成光盘。
首先，安装 Ubuntu 基本系统。以 Ubuntu 6.10 为例，当插入安装盘后，计算机从光盘引导系统，这时在初始安装菜单中选择“Install a command-line system”，之后与一般的安装过程并无二致。
在基本系统安装完成后，会要求重新启动一次系统，使用在安装过程中设置的帐号及密码登录。
现在，执行指令 sudo vim /etc/apt/sources.list，以便对 sources.list 文件进行编辑。在 VIM 打开文件后，将 deb http:// 或 deb-src http:// 前面包含的注释符号（#）删除。然后保存所作的修改。
为了完成后续的安装过程，需要继续执行指令 sudo apt-get update。
至此，最小化的 Ubuntu 安装已经就绪。
如果需要安装桌面环境，那么还可以执行以下的选择：
sudo apt-get install x-window-system-core。sudo apt-get install xdm/gdm/kdm[注]。最常见的图形化登录管理器包括 XDM、GDM、KDM，用户可根据自己的需要选择其中之一。sudo apt-get install ubuntu-desktop/kubuntu-desktop/xubuntu-desktop。这将分别安装 GNOME、KDE、XFCE 桌面环境。对于 GNOME、KDE、XFCE 这些桌面环境来说，为了获得更强的定制效果，也可仅安装最基本的组件，如：sudo apt-get install gnome-core/kde-core/xfce4。当然，如果不需要桌面环境，也可选择安装窗口管理器代替。那样的话，可以执行指令 sudo apt-get install fluxbox/icewm/enlightenment/fvwm。sudo apt-get install firefox/gaim/xmms。这将安装 Firefox 浏览器、Gaim 聊天程序、XMMS 音乐播放器。同样，不必拘泥于此处的示例，完全可以按自己的喜好来安装。一旦完成上述过程的安装，重启系统，将会享受到一个完全自由的系统。
注释
类似 xdm/gdm/kdm 这样的写法需要读者选择其中一项才能无误地执行命令。
2003 年 12 月 01 日
本文详细地介绍了基于嵌入式系统中的 OS 启动加载程序 ―― Boot Loader 的概念、软件设计的主要任务以及结构框架等内容。
在专用的嵌入式板子运行 GNU/Linux 系统已经变得越来越流行。一个嵌入式 Linux 系统从软件的角度看通常可以分为四个层次：
1. 引导加载程序。包括固化在固件(firmware)中的 boot 代码(可选)，和 Boot Loader 两大部分。
2. Linux 内核。特定于嵌入式板子的定制内核以及内核的启动参数。
3. 文件系统。包括根文件系统和建立于 Flash 内存设备之上文件系统。通常用 ram disk 来作为 root fs。
4. 用户应用程序。特定于用户的应用程序。有时在用户应用程序和内核层之间可能还会包括一个嵌入式图形用户界面。常用的嵌入式 GUI 有：MicroWindows 和 MiniGUI 懂。
引 导加载程序是系统加电后运行的第一段软件代码。回忆一下 PC 的体系结构我们可以知道，PC 机中的引导加载程序由 BIOS(其本质就是一段固件程序)和位于硬盘 MBR 中的 OS Boot Loader（比如，LILO 和 GRUB 等）一起组成。BIOS 在完成硬件检测和资源分配后，将硬盘 MBR 中的 Boot Loader 读到系统的 RAM 中，然后将控制权交给 OS Boot Loader。Boot Loader 的主要运行任务就是将内核映象从硬盘上读到 RAM 中，然后跳转到内核的入口点去运行，也即开始启动操作系统。
而在嵌入式系统中，通常并没有像 BIOS 那样的固件程序（注，有的嵌入式 CPU 也会内嵌一段短小的启动程序），因此整个系统的加载启动任务就完全由 Boot Loader 来完成。比如在一个基于 ARM7TDMI core 的嵌入式系统中，系统在上电或复位时通常都从地址 0x00000000 处开始执行，而在这个地址处安排的通常就是系统的 Boot Loader 程序。
本文将从 Boot Loader 的概念、Boot Loader 的主要任务、Boot Loader 的框架结构以及 Boot Loader 的安装等四个方面来讨论嵌入式系统的 Boot Loader。
简单地说，Boot Loader 就是在操作系统内核运行之前运行的一段小程序。通过这段小程序，我们可以初始化硬件设备、建立内存空间的映射图，从而将系统的软硬件环境带到一个合适的状态，以便为最终调用操作系统内核准备好正确的环境。
通常，Boot Loader 是严重地依赖于硬件而实现的，特别是在嵌入式世界。因此，在嵌入式世界里建立一个通用的 Boot Loader 几乎是不可能的。尽管如此，我们仍然可以对 Boot Loader 归纳出一些通用的概念来，以指导用户特定的 Boot Loader 设计与实现。
每 种不同的 CPU 体系结构都有不同的 Boot Loader。有些 Boot Loader 也支持多种体系结构的 CPU，比如 U-Boot 就同时支持 ARM 体系结构和MIPS 体系结构。除了依赖于 CPU 的体系结构外，Boot Loader 实际上也依赖于具体的嵌入式板级设备的配置。这也就是说，对于两块不同的嵌入式板而言，即使它们是基于同一种 CPU 而构建的，要想让运行在一块板子上的 Boot Loader 程序也能运行在另一块板子上，通常也都需要修改 Boot Loader 的源程序。
2. Boot Loader 的安装媒介（Installation Medium）
系 统加电或复位后，所有的 CPU 通常都从某个由 CPU 制造商预先安排的地址上取指令。比如，基于 ARM7TDMI core 的 CPU 在复位时通常都从地址 0x00000000 取它的第一条指令。而基于 CPU 构建的嵌入式系统通常都有某种类型的固态存储设备(比如：ROM、EEPROM 或 FLASH 等)被映射到这个预先安排的地址上。因此在系统加电后，CPU 将首先执行 Boot Loader 程序。
下图1就是一个同时装有 Boot Loader、内核的启动参数、内核映像和根文件系统映像的固态存储设备的典型空间分配结构图。
主机和目标机之间一般通过串口建立连接，Boot Loader 软件在执行时通常会通过串口来进行 I/O，比如：输出打印信息到串口，从串口读取用户控制字符等。
4. Boot Loader 的启动过程是单阶段（Single Stage）还是多阶段（Multi-Stage）
通 常多阶段的 Boot Loader 能提供更为复杂的功能，以及更好的可移植性。从固态存储设备上启动的 Boot Loader 大多都是 2 阶段的启动过程，也即启动过程可以分为 stage 1 和 stage 2 两部分。而至于在 stage 1 和 stage 2 具体完成哪些任务将在下面讨论。
5. Boot Loader 的操作模式 (Operation Mode)
大多数 Boot Loader 都包含两种不同的操作模式："启动加载"模式和"下载"模式，这种区别仅对于开发人员才有意义。但从最终用户的角度看，Boot Loader 的作用就是用来加载操作系统，而并不存在所谓的启动加载模式与下载工作模式的区别。
启动加载（Boot loading）模式：这种模式也称为"自主" （Autonomous）模式。也即 Boot Loader 从目标机上的某个固态存储设备上将操作系统加载到 RAM 中运行，整个过程并没有用户的介入。这种模式是 Boot Loader 的正常工作模式，因此在嵌入式产品发布的时侯，Boot Loader 显然必须工作在这种模式下。
下载（Downloading）模式：在这种模式下，目标机上的 Boot Loader 将通过串口连接或网络连接等通信手段从主机（Host）下载文件，比如：下载内核映像和根文件系统映像等。从主机下载的文件通常首先被 Boot Loader 保存到目标机的 RAM 中，然后再被 Boot Loader 写到目标机上的FLASH 类固态存储设备中。Boot Loader 的这种模式通常在第一次安装内核与根文件系统时被使用；此外，以后的系统更新也会使用 Boot Loader 的这种工作模式。工作于这种模式下的 Boot Loader 通常都会向它的终端用户提供一个简单的命令行接口。
像 Blob 或 U-Boot 等这样功能强大的 Boot Loader 通常同时支持这两种工作模式，而且允许用户在这两种工作模式之间进行切换。比如，Blob 在启动时处于正常的启动加载模式，但是它会延时 10 秒等待终端用户按下任意键而将 blob 切换到下载模式。如果在 10 秒内没有用户按键，则 blob 继续启动 Linux 内核。
6. BootLoader 与主机之间进行文件传输所用的通信设备及协议
最常见的情况就是，目标机上的 Boot Loader 通过串口与主机之间进行文件传输，传输协议通常是 xmodem／ymodem／zmodem 协议中的一种。但是，串口传输的速度是有限的，因此通过以太网连接并借助 TFTP 协议来下载文件是个更好的选择。
此外，在论及这个话题时，主机方所用的软件也要考虑。比如，在通过以太网连接和 TFTP 协议来下载文件时，主机方必须有一个软件用来的提供 TFTP 服务。
在讨论了 BootLoader 的上述概念后，下面我们来具体看看 BootLoader 的应该完成哪些任务。
在继续本节的讨论之前，首先我们做一个假定，那就是：假定内核映像与根文件系统映像都被加载到 RAM 中运行。之所以提出这样一个假设前提是因为，在嵌入式系统中内核映像与根文件系统映像也可以直接在 ROM 或 Flash 这样的固态存储设备中直接运行。但这种做法无疑是以运行速度的牺牲为代价的。
从操作系统的角度看，Boot Loader 的总目标就是正确地调用内核来执行。
另外，由于 Boot Loader 的实现依赖于 CPU 的体系结构，因此大多数 Boot Loader 都分为 stage1 和 stage2 两大部分。依赖于 CPU 体系结构的代码，比如设备初始化代码等，通常都放在 stage1 中，而且通常都用汇编语言来实现，以达到短小精悍的目的。而 stage2 则通常用C语言来实现，这样可以实现给复杂的功能，而且代码会具有更好的可读性和可移植性。
Boot Loader 的 stage1 通常包括以下步骤(以执行的先后顺序)：
Boot Loader 的 stage2 通常包括以下步骤(以执行的先后顺序)：
3.1.1 基本的硬件初始化
这是 Boot Loader 一开始就执行的操作，其目的是为 stage2 的执行以及随后的 kernel 的执行准备好一些基本的硬件环境。它通常包括以下步骤（以执行的先后顺序）：
1． 屏蔽所有的中断。为中断提供服务通常是 OS 设备驱动程序的责任，因此在 Boot Loader 的执行全过程中可以不必响应任何中断。中断屏蔽可以通过写 CPU 的中断屏蔽寄存器或状态寄存器（比如 ARM 的 CPSR 寄存器）来完成。
2． 设置 CPU 的速度和时钟频率。
3． RAM 初始化。包括正确地设置系统的内存控制器的功能寄存器以及各内存库控制寄存器等。
4． 初始化 LED。典型地，通过 GPIO 来驱动 LED，其目的是表明系统的状态是 OK 还是 Error。如果板子上没有 LED，那么也可以通过初始化 UART 向串口打印 Boot Loader 的 Logo 字符信息来完成这一点。
5． 关闭 CPU 内部指令／数据 cache。
3.1.2 为加载 stage2 准备 RAM 空间
为了获得更快的执行速度，通常把 stage2 加载到 RAM 空间中来执行，因此必须为加载 Boot Loader 的 stage2 准备好一段可用的 RAM 空间范围。
由于 stage2 通常是 C 语言执行代码，因此在考虑空间大小时，除了 stage2 可执行映象的大小外，还必须把堆栈空间也考虑进来。此外，空间大小最好是 memory page 大小(通常是 4KB)的倍数。一般而言，1M 的 RAM 空间已经足够了。具体的地址范围可以任意安排，比如 blob 就将它的 stage2 可执行映像安排到从系统 RAM 起始地址 0xc0200000 开始的 1M 空间内执行。但是，将 stage2 安排到整个 RAM 空间的最顶 1MB(也即(RamEnd-1MB) - RamEnd)是一种值得推荐的方法。
为了后面的叙述方便，这里把所安排的 RAM 空间范围的大小记为：stage2_size(字节)，把起始地址和终止地址分别记为：stage2_start 和 stage2_end(这两个地址均以 4 字节边界对齐)。因此：
stage2_end＝stage2_start＋stage2_size |
1． 先保存 memory page 一开始两个字的内容。
2． 向这两个字中写入任意的数字。比如：向第一个字写入 0x55，第 2 个字写入 0xaa。
3． 然后，立即将这两个字的内容读回。显然，我们读到的内容应该分别是 0x55 和 0xaa。如果不是，则说明这个 memory page 所占据的地址范围不是一段有效的 RAM 空间。
4． 再向这两个字中写入任意的数字。比如：向第一个字写入 0xaa，第 2 个字中写入 0x55。
5． 然后，立即将这两个字的内容立即读回。显然，我们读到的内容应该分别是 0xaa 和 0x55。如果不是，则说明这个 memory page 所占据的地址范围不是一段有效的 RAM 空间。
6． 恢复这两个字的原始内容。测试完毕。
为了得到一段干净的 RAM 空间范围，我们也可以将所安排的 RAM 空间范围进行清零操作。
3.1.3 拷贝 stage2 到 RAM 中
拷贝时要确定两点：(1) stage2 的可执行映象在固态存储设备的存放起始地址和终止地址；(2) RAM 空间的起始地址。
3.1.4 设置堆栈指针 sp
堆栈指针的设置是为了执行 C 语言代码作好准备。通常我们可以把 sp 的值设置为(stage2_end-4)，也即在 3.1.2 节所安排的那个 1MB 的 RAM 空间的最顶端(堆栈向下生长)。
此外，在设置堆栈指针 sp 之前，也可以关闭 led 灯，以提示用户我们准备跳转到 stage2。
经过上述这些执行步骤后，系统的物理内存布局应该如下图2所示。
3.1.5 跳转到 stage2 的 C 入口点
在上述一切都就绪后，就可以跳转到 Boot Loader 的 stage2 去执行了。比如，在 ARM 系统中，这可以通过修改 PC 寄存器为合适的地址来实现。
正如前面所说，stage2 的代码通常用 C 语言来实现，以便于实现更复杂的功能和取得更好的代码可读性和可移植性。但是与普通 C 语言应用程序不同的是，在编译和链接 boot loader 这样的程序时，我们不能使用 glibc 库中的任何支持函数。其原因是显而易见的。这就给我们带来一个问题，那就是从那里跳转进 main() 函数呢？直接把 main() 函数的起始地址作为整个 stage2 执行映像的入口点或许是最直接的想法。但是这样做有两个缺点：1)无法通过main() 函数传递函数参数；2)无法处理 main() 函数返回的情况。一种更为巧妙的方法是利用 trampoline(弹簧床)的概念。也即，用汇编语言写一段trampoline 小程序，并将这段 trampoline 小程序来作为 stage2 可执行映象的执行入口点。然后我们可以在 trampoline 汇编小程序中用 CPU 跳转指令跳入 main() 函数中去执行；而当 main() 函数返回时，CPU 执行路径显然再次回到我们的 trampoline 程序。简而言之，这种方法的思想就是：用这段 trampoline 小程序来作为 main() 函数的外部包裹(external wrapper)。
下面给出一个简单的 trampoline 程序示例(来自blob)：
.text |
可以看出，当 main() 函数返回后，我们又用一条跳转指令重新执行 trampoline 程序――当然也就重新执行 main() 函数，这也就是 trampoline(弹簧床)一词的意思所在。
3.2.1初始化本阶段要使用到的硬件设备
这通常包括：（1）初始化至少一个串口，以便和终端用户进行 I/O 输出信息；（2）初始化计时器等。
在初始化这些设备之前，也可以重新把 LED 灯点亮，以表明我们已经进入 main() 函数执行。
设备初始化完成后，可以输出一些打印信息，程序名字字符串、版本号等。
3.2.2 检测系统的内存映射（memory map）
所 谓内存映射就是指在整个 4GB 物理地址空间中有哪些地址范围被分配用来寻址系统的 RAM 单元。比如，在 SA-1100 CPU 中，从 0xC000,0000 开始的 512M 地址空间被用作系统的 RAM 地址空间，而在 Samsung S3C44B0X CPU 中，从 0x0c00,0000 到 0x1000,0000 之间的 64M 地址空间被用作系统的 RAM 地址空间。虽然 CPU 通常预留出一大段足够的地址空间给系统 RAM，但是在搭建具体的嵌入式系统时却不一定会实现 CPU 预留的全部 RAM 地址空间。也就是说，具体的嵌入式系统往往只把 CPU 预留的全部 RAM 地址空间中的一部分映射到 RAM 单元上，而让剩下的那部分预留 RAM 地址空间处于未使用状态。 由于上述这个事实，因此 Boot Loader 的 stage2 必须在它想干点什么 (比如，将存储在 flash 上的内核映像读到 RAM 空间中) 之前检测整个系统的内存映射情况，也即它必须知道 CPU 预留的全部 RAM 地址空间中的哪些被真正映射到 RAM 地址单元，哪些是处于 "unused" 状态的。
(1) 内存映射的描述
可以用如下数据结构来描述 RAM 地址空间中的一段连续(continuous)的地址范围：
typedef struct memory_area_struct { |
这段 RAM 地址空间中的连续地址范围可以处于两种状态之一：(1)used=1，则说明这段连续的地址范围已被实现，也即真正地被映射到 RAM 单元上。(2)used=0，则说明这段连续的地址范围并未被系统所实现，而是处于未使用状态。
基于上述 memory_area_t 数据结构，整个 CPU 预留的 RAM 地址空间可以用一个 memory_area_t 类型的数组来表示，如下所示：
memory_area_t memory_map[NUM_MEM_AREAS] = { |
(2) 内存映射的检测
下面我们给出一个可用来检测整个 RAM 地址空间内存映射情况的简单而有效的算法：
/* 数组初始化 */ |
在用上述算法检测完系统的内存映射情况后，Boot Loader 也可以将内存映射的详细信息打印到串口。
3.2.3 加载内核映像和根文件系统映像
(1) 规划内存占用的布局
这里包括两个方面：(1)内核映像所占用的内存范围；（2）根文件系统所占用的内存范围。在规划内存占用的布局时，主要考虑基地址和映像的大小两个方面。
对于内核映像，一般将其拷贝到从(MEM_START＋0x8000) 这个基地址开始的大约1MB大小的内存范围内(嵌入式 Linux 的内核一般都不操过 1MB)。为什么要把从 MEM_START 到 MEM_START＋0x8000 这段 32KB 大小的内存空出来呢？这是因为 Linux 内核要在这段内存中放置一些全局数据结构，如：启动参数和内核页表等信息。
而对于根文件系统映像，则一般将其拷贝到 MEM_START+0x0010,0000 开始的地方。如果用 Ramdisk 作为根文件系统映像，则其解压后的大小一般是1MB。
（2）从 Flash 上拷贝
由于像 ARM 这样的嵌入式 CPU 通常都是在统一的内存地址空间中寻址 Flash 等固态存储设备的，因此从 Flash 上读取数据与从 RAM 单元中读取数据并没有什么不同。用一个简单的循环就可以完成从 Flash 设备上拷贝映像的工作：
|
3.2.4 设置内核的启动参数
应该说，在将内核映像和根文件系统映像拷贝到 RAM 空间中后，就可以准备启动 Linux 内核了。但是在调用内核之前，应该作一步准备工作，即：设置 Linux 内核的启动参数。
Linux 2.4.x 以后的内核都期望以标记列表(tagged list)的形式来传递启动参数。启动参数标记列表以标记 ATAG_CORE 开始，以标记 ATAG_NONE 结束。每个标记由标识被传递参数的 tag_header 结构以及随后的参数值数据结构来组成。数据结构 tag 和 tag_header 定义在 Linux 内核源码的include/asm/setup.h 头文件中：
/* The list ends with an ATAG_NONE node. */ |
在嵌入式 Linux 系统中，通常需要由 Boot Loader 设置的常见启动参数有：ATAG_CORE、ATAG_MEM、ATAG_CMDLINE、ATAG_RAMDISK、ATAG_INITRD等。
比如，设置 ATAG_CORE 的代码如下：
params = (struct tag *)BOOT_PARAMS; |
其中，BOOT_PARAMS 表示内核启动参数在内存中的起始基地址，指针 params 是一个 struct tag 类型的指针。宏 tag_next() 将以指向当前标记的指针为参数，计算紧临当前标记的下一个标记的起始地址。注意，内核的根文件系统所在的设备ID就是在这里设置的。
下面是设置内存映射情况的示例代码：
for(i = 0; i < NUM_MEM_AREAS; i++) { |
可以看出，在 memory_map［］数组中，每一个有效的内存段都对应一个 ATAG_MEM 参数标记。
Linux 内核在启动时可以以命令行参数的形式来接收信息，利用这一点我们可以向内核提供那些内核不能自己检测的硬件参数信息，或者重载(override)内核自 己检测到的信息。比如，我们用这样一个命令行参数字符串"console=ttyS0,115200n8"来通知内核以 ttyS0 作为控制台，且串口采用 "115200bps、无奇偶校验、8位数据位"这样的设置。下面是一段设置调用内核命令行参数字符串的示例代码：
char *p; |
请注意在上述代码中，设置 tag_header 的大小时，必须包括字符串的终止符'\0'，此外还要将字节数向上圆整4个字节，因为 tag_header 结构中的size 成员表示的是字数。
下面是设置 ATAG_INITRD 的示例代码，它告诉内核在 RAM 中的什么地方可以找到 initrd 映象(压缩格式)以及它的大小：
params->hdr.tag = ATAG_INITRD2; |
下面是设置 ATAG_RAMDISK 的示例代码，它告诉内核解压后的 Ramdisk 有多大（单位是KB）：
params->hdr.tag = ATAG_RAMDISK; |
最后，设置 ATAG_NONE 标记，结束整个启动参数列表：
static void setup_end_tag(void) |
3.2.5 调用内核
Boot Loader 调用 Linux 内核的方法是直接跳转到内核的第一条指令处，也即直接跳转到 MEM_START＋0x8000 地址处。在跳转时，下列条件要满足：
1． CPU 寄存器的设置：
2． CPU 模式：
3． Cache 和 MMU 的设置：
如果用 C 语言，可以像下列示例代码这样来调用内核：
void (*theKernel)(int zero, int arch, u32 params_addr) = (void (*)(int, int, u32))KERNEL_RAM_BASE; |
注意，theKernel()函数调用应该永远不返回的。如果这个调用返回，则说明出错。
在 boot loader 程序的设计与实现中，没有什么能够比从串口终端正确地收到打印信息能更令人激动了。此外，向串口终端打印信息也是一个非常重要而又有效的调试手段。但是， 我们经常会碰到串口终端显示乱码或根本没有显示的问题。造成这个问题主要有两种原因：(1) boot loader 对串口的初始化设置不正确。(2) 运行在 host 端的终端仿真程序对串口的设置不正确，这包括：波特率、奇偶校验、数据位和停止位等方面的设置。
此外，有时也会碰到这样的问题，那就是：在 boot loader 的运行过程中我们可以正确地向串口终端输出信息，但当 boot loader 启动内核后却无法看到内核的启动输出信息。对这一问题的原因可以从以下几个方面来考虑：
(1) 首先请确认你的内核在编译时配置了对串口终端的支持，并配置了正确的串口驱动程序。
(2) 你的 boot loader 对串口的初始化设置可能会和内核对串口的初始化设置不一致。此外，对于诸如 s3c44b0x 这样的 CPU，CPU 时钟频率的设置也会影响串口，因此如果 boot loader 和内核对其 CPU 时钟频率的设置不一致，也会使串口终端无法正确显示信息。
(3) 最后，还要确认 boot loader 所用的内核基地址必须和内核映像在编译时所用的运行基地址一致，尤其是对于 uClinux 而言。假设你的内核映像在编译时用的基地址是 0xc0008000，但你的 boot loader 却将它加载到 0xc0010000 处去执行，那么内核映像当然不能正确地执行了。
Boot Loader 的设计与实现是一个非常复杂的过程。如果不能从串口收到那激动人心的"uncompressing linux.................. done, booting the kernel……"内核启动信息，恐怕谁也不能说："嗨，我的 boot loader 已经成功地转起来了！"。
///////////////////////////////////////////////////////////////////////////////
//
// FileName : postfix.cpp
// Version : 0.10
// Author : Luo Cong
// Date : 2005-1-6 16:00:54
// Comment :
//
///////////////////////////////////////////////////////////////////////////////
// 算法：
// 1)检查输入的下一元素。
// 2)假如是个操作数，输出。
// 3)假如是个开括号，将其压栈。
// 4)假如是个运算符，则
// i) 假如栈为空，将此运算符压栈。
// ii) 假如栈顶是开括号，将此运算符压栈。
// iii) 假如此运算符比栈顶运算符优先级高，将此运算符压入栈中。
// iv) 否则栈顶运算符出栈并输出，重复步骤4。
// 5)假如是个闭括号，栈中运算符逐个出栈并输出，直到遇到开括号。开括号出栈并丢弃。
// 6)假如输入还未完毕，跳转到步骤1。
// 7)假如输入完毕，栈中剩余的所有操作符出栈并输出它们。
#include <stdio.h>
#include "stack.h"
// 返回操作符的优先级
// +和-的优先级是一样的，*和/的优先级也是一样的，但+和-的优先级要比*和/的低。
static int GetPRI(const char optr)
{
switch (optr)
{
case '+': return 1;
case '-': return 1;
case '*': return 2;
case '/': return 2;
default : return 0;
}
}
// 在这个函数中完成对栈顶的操作符和当前操作符的优先级对比，
// 并决定是输出当前的操作符还是对当前的操作符进行入栈处理。
static void ProcessStackPRI(
CStack<char> &stack,
const char optr,
char **szPostfix
)
{
ASSERT(*szPostfix);
int i;
int nRetCode;
char chStackOptr;
int nCount = stack.GetCount();
for (i = 0; i <= nCount; ++i)
{
nRetCode = stack.top(&chStackOptr);
if (
(0 == nRetCode) || // 栈顶为空，新操作符添加到栈顶
(GetPRI(chStackOptr) < GetPRI(optr))// 栈顶操作符优先级比当前的要低
)
{
stack.push(optr);
break;
}
else
{
// 如果栈顶操作符优先级不低于当前的，则栈顶元素出栈并输出：
stack.pop();
*(*szPostfix)++ = chStackOptr;
}
}
}
static void Infix2Postfix(
const char *szInfix,
char *szPostfix
)
{
ASSERT(szPostfix);
char chOptr;
int nRetCode;
CStack<char> stack;
while (*szInfix)
{
switch (*szInfix)
{
// 忽略空格和TAB：
case ' ':
case '\t':
break;
// 对操作符进行优先级判断，以便决定是入栈还是输出：
case '+':
case '-':
case '*':
case '/':
nRetCode = stack.IsEmpty();
if (!nRetCode)
ProcessStackPRI(stack, *szInfix, &szPostfix);
else
stack.push(*szInfix); // 当栈为空时，毫无疑问操作符应该入栈
break;
// 遇到左括号时，无条件入栈，因为它的优先级是最高的
case '(':
stack.push(*szInfix);
break;
// 遇到右括号时，逐个把栈中的操作符出栈，直到遇到左括号为止
case ')':
do
{
nRetCode = stack.pop(&chOptr);
if (nRetCode && ('(' != chOptr)) // 左括号本身不输出
*szPostfix++ = chOptr;
} while (!stack.IsEmpty() && ('(' != chOptr)); // 遇到左括号为止
break;
// 其余的情况，直接输出即可
default:
*szPostfix++ = *szInfix;
break;
}
++szInfix;
}
// 如果输入的内容已经分析完毕，那么就把栈中剩余的操作符全部出栈
while (!stack.IsEmpty())
{
nRetCode = stack.pop(&chOptr);
*szPostfix++ = chOptr;
}
*szPostfix = '\0';
}
int main()
{
char *szInfix = "a+b*c+(d*e+f)*g";
char szPostfix[255];
#ifdef _DEBUG
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif
Infix2Postfix(szInfix, szPostfix);
printf("Infix : %s\n", szInfix);
printf("Postfix : %s\n", szPostfix);
}
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Code Box</title>
<style type="text/css">
pre.code {
border:1px solid #99BBE8;
padding:2px;
}
.code-box {
border:1px solid #99BBE8;
margin:5px 2px;
}
.code-box-head {
margin:0px;
height:26px;
line-height:26px;
font-size:20px;
background:url(http://w.886.cn/4gYC/120961475/120961475_1902.gif) #D3E1F1;
border-bottom:1px solid #99BBE8;
margin-bottom:0px;
padding:0px 2px;
color:#15428B;
}
.code-box-head a {
text-indent:0px;
border:1px solid #D3E1F1;
margin:2px 3px;
height:20px;
line-height:20px;
padding:0px 4px;
float:right;
font-size:12px;
text-decoration:none;
color:#7692AD
}
.code-box-head a:hover {border:1px solid #99BBE8;}
.code-box-content {
margin:0px;
background-color:#FFFFFF;
padding:2px;
color:#000066;
}
</style>
<script src='http://greatghoul.go1.icpcn.com/blogger/CodeBox.js' type='text/javascript'/></script>
</head>
<body>
<pre class="code" title="HEAD">
使用方法:
<pre class="code html" title="代码标题">
class 中code是必须的.当贴出的代码为html代码时,加上 html
转换后的代码(转换工具见文末)
</pre>
</pre>
<pre class="code">
Some Code
</pre>
</body>
</html>
I Summarized how to build android full source for x86 target.
0. My development environments
- OS : Ubuntu 8.10 Distribution ( 2.6.27-4-generic )
- CPU: Intel(R) Core(TM)2 Duo CPU T5750 @ 2.00GHz ( Samsung SENS
R60 Laptop )
- RAM: Samsung DDR Ram
- Target: Eee PC (ASUS)
1. Query of Linux distribution information
- At first, Prepare ASUS Eee 701 Lattop or Samsung nettop (NC01).
And then, confirm system information on your linux distribution
like belows.
$ uname -a
Linux invain-laptop 2.6.27-4-generic #1 SMP Wed Sep 24 01:30:51 UTC
2008 i686 GNU/Linux
$ gcc --version
gcc (Ubuntu 4.3.2-1ubuntu10) 4.3.2
Copyright (C) 2008 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There
is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.
2. repo init and Sync
- You have to download android full source for x86 architecture like
ASUS Eee PC 701.
- Eee pc dev tree is "git://android.git.kernel.org/platform/vendor/
asus/eee_701.git".
$ cd ~
$ mkdir bin_x86 && cd bin_x86
$ mkdir mydroid && cd mydroid
$ repo init -u git://android.git.kernel.org/platform/manifest.git -b
cupcake
$ repo sync
$ vi ./.repo/local_manifest.xml
$ repo sync
... A new repo command ( 1.8) is available.
... You should upgrade soon:
cp /home/invain/bin_x86/mydroid/.repo/repo/repo /home/invain/bin/
repo
Initializing project platform/vendor/asus/eee_701 ...
remote: Counting objects: 33, done.
remote: Compressing objects: 100% (31/31), done.
remote: Total 33 (delta 2), reused 33 (delta 2)
Unpacking objects: 100% (33/33), done.
From git://android.git.kernel.org/platform/vendor/asus/eee_701
* [new branch] cupcake -> korg/cupcake
* [new branch] master -> korg/master
3. Building x86 android full source
$ TARGET_ARCH=x86 TARGET_PRODUCT=eee_701 DISABLE_DEXPREOPT=true make -
j2 installer_img
build/core/product_config.mk:207: WARNING: adding test OTA key
============================================
TARGET_PRODUCT=eee_701
TARGET_BUILD_VARIANT=eng
TARGET_SIMULATOR=
TARGET_BUILD_TYPE=release
TARGET_ARCH=x86
HOST_ARCH=x86
HOST_OS=linux
HOST_BUILD_TYPE=release
BUILD_ID=
============================================
build/core/main.mk:178: implicitly installing apns-conf_sdk.xml
............... Below Omission ...................
* Toouble Shooting
$ vi external/srec/tools/thirdparty/OpenFst/fst/lib/../../fst/lib/
vector-fst.h
$ vi external/srec/tools/thirdparty/OpenFst/fst/lib/symbol-table.cpp
$ vi frameworks/base/tools/aidl/aidl.cpp --> #include
#include
and so on......
$ vi
$ ls -lh out/target/product/eee_701/
total 753M
-rw-r--r-- 1 oedev oedev 2.5M 2008-12-20 21:23 boot.img
-rw-r--r-- 1 oedev oedev 57 2008-12-20 22:15 clean_steps.mk
drwxr-xr-x 4 oedev oedev 4.0K 2008-12-20 21:32 data
drwxr-xr-x 2 oedev oedev 4.0K 2008-12-20 19:54 grub
drwxr-xr-x 4 oedev oedev 4.0K 2008-12-20 22:36 installer
-rw-r--r-- 1 oedev oedev 388M 2008-12-20 22:38 installer.img
-rw-r--r-- 1 oedev oedev 1.9M 2008-12-20 18:45 kernel
drwxr-xr-x 12 oedev oedev 4.0K 2008-12-20 22:33 obj
-rw-r--r-- 1 oedev oedev 592K 2008-12-20 21:10 ramdisk.img
drwxr-xr-x 9 oedev oedev 4.0K 2008-12-20 21:09 root
drwxr-xr-x 4 oedev oedev 4.0K 2008-12-20 19:55 symbols
drwxr-xr-x 12 oedev oedev 4.0K 2008-12-20 21:29 system
-rw-r--r-- 1 oedev oedev 355M 2008-12-20 22:34 system.img
-rw-r--r-- 1 oedev oedev 5.0M 2008-12-20 21:32 userdata.img
$ file out/target/product/eee_701/installer.img
out/target/product/eee_701/installer.img: x86 boot sector;
GRand Unified Bootloader, stage1 version 0x3; partition 2:
ID=0x83, starthead 0, startsector 10926, 783672 sectors, code offset
0x48
$ file out/target/product/eee_701/system.img
out/target/product/eee_701/system.img: Linux rev 0.0 ext2 filesystem
data
$ file out/target/product/eee_701/userdata.img
out/target/product/eee_701/userdata.img: Linux rev 0.0 ext2 filesystem
data
$ sudo mount -o loop boot.img /mnt
total 2.5M
-rw-r--r-- 1 oedev oedev 77 2008-12-20 21:23 cmdline
-rw-r--r-- 1 oedev oedev 1.9M 2008-12-20 21:23 kernel
-rw-r--r-- 1 oedev oedev 592K 2008-12-20 21:23 ramdisk
$ cat /mnt/cmndline
console=tty0 console=ttyS1,115200n8 console=tty0
androidboot.hardware=eee_701
$ cp /mnt/ramdisk /tmp/ramdisk.gz
$ cd /tmp
$ gunzip ramdisk.gz
$ cpio -iv < ramdisk
sys
init.goldfish.rc
system
data
init.rc
proc
init
default.prop
sbin
sbin/adbd
init.eee_701.rc
lib
lib/modules
lib/modules/i915.ko
lib/modules/font.ko
lib/modules/drm.ko
lib/modules/cfbcopyarea.ko
lib/modules/cfbimgblt.ko
lib/modules/bitblit.ko
lib/modules/cfbfillrect.ko
lib/modules/softcursor.ko
lib/modules/fbcon.ko
lib/modules/atl2.ko
dev
2955 blocks
$ file /tmp/init
/tmp/init: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV),
statically linked, not stripped
4. Make USB Stick Installer
$ dd if=out/target/product/eee_701/installer.img of=/dev/
5. Now. Enjoy X86 Android Platform!
End of Line.
2008 年 11 月 27 日
如何定位应用程序开发中的内存问题，一直是 inux 应用程序开发中的瓶颈所在。有一款非常优秀的 linux 下开源的内存问题检测工具：valgrind，能够极大的帮助你解决上述问题。掌握 valgrind 的使用以及工作原理，能够有效地定位进而避免应用开发中的内存问题。-----------------------------------------------
Valgrind是一套Linux下，开放源代码（GPL V2）的仿真调试工具的集合。Valgrind由内核（core）以及基于内核的其他调试工具组成。内核类似于一个框架（framework），它模拟了 一个CPU环境，并提供服务给其他工具；而其他工具则类似于插件 (plug-in)，利用内核提供的服务完成各种特定的内存调试任务。Valgrind的体系结构如下图所示：
Valgrind包括如下一些工具：
要发现Linux下的内存问题，首先一定要知道在Linux下，内存是如何被分配的？下图展示了一个典型的Linux C程序内存空间布局：
一个典型的Linux C程序内存空间由如下几部分组成：
Memcheck检测内存问题的原理如下图所示：
Memcheck 能够检测出内存问题，关键在于其建立了两个全局表。
对于进程的整个地址空间中的每一个字节(byte)，都有与之对应的 8 个 bits；对于 CPU 的每个寄存器，也有一个与之对应的 bit 向量。这些 bits 负责记录该字节或者寄存器值是否具有有效的、已初始化的值。
对于进程整个地址空间中的每一个字节(byte)，还有与之对应的 1 个 bit，负责记录该地址是否能够被读写。
检测原理：
第一步：准备好程序
为了使valgrind发现的错误更精确，如能够定位到源代码行，建议在编译时加上-g参数，编译优化选项请选择O0，虽然这会降低程序的执行效率。
这里用到的示例程序文件名为：sample.c（如下所示）,选用的编译器为gcc。
生成可执行程序 gcc –g –O0 sample.c –o sample
第二步：在valgrind下，运行可执行程序。
利用valgrind调试内存问题，不需要重新编译源程序，它的输入就是二进制的可执行程序。调用Valgrind的通用格式是：valgrind [valgrind-options] your-prog [your-prog-options]
Valgrind 的参数分为两类，一类是 core 的参数，它对所有的工具都适用；另外一类就是具体某个工具如 memcheck 的参数。Valgrind 默认的工具就是 memcheck，也可以通过“--tool=tool name”指定其他的工具。Valgrind 提供了大量的参数满足你特定的调试需求，具体可参考其用户手册。
这个例子将使用 memcheck，于是可以输入命令入下：valgrind
第三步：分析 valgrind 的输出信息。
以下是运行上述命令后的输出。
示例程序显然有两个问题，一是fun函数中动态申请的堆内存没有释放；二是对堆内存的访问越界。这两个问题均被valgrind发现。
-----------------------------------------------在Linux平台开发应用程序时，最常遇见的问题就是错误的使用内存，我们总结了常见了内存错误使用情况，并说明了如何用valgrind将其检测出来。
问题分析：
对于位于程序中不同段的变量，其初始值是不同的，全局变量和静态变量初始值为0，而局部变量和动态申请的变量，其初始值为随机值。如果程序使用了为随机值的变量，那么程序的行为就变得不可预期。
下面的程序就是一种常见的，使用了未初始化的变量的情况。数组a是局部变量，其初始值为随机值，而在初始化时并没有给其所有数组成员初始化，如此在接下来使用这个数组时就潜在有内存问题。
结果分析：
假设这个文件名为：badloop.c，生成的可执行程序为badloop。用memcheck对其进行测试，输出如下。
输出结果显示，在该程序第11行中，程序的跳转依赖于一个未初始化的变量。准确的发现了上述程序中存在的问题。
问题分析：
这种情况是指：访问了你不应该/没有权限访问的内存地址空间，比如访问数组时越界；对动态内存访问时超出了申请的内存大小范围。下面的程序就是一个 典型的数组越界问题。pt是一个局部数组变量，其大小为4，p初始指向pt数组的起始地址，但在对p循环叠加后，p超出了pt数组的范围，如果此时再对p 进行写操作，那么后果将不可预期。
结果分析：
假设这个文件名为badacc.cpp，生成的可执行程序为badacc，用memcheck对其进行测试，输出如下。
输出结果显示，在该程序的第15行，进行了非法的写操作；在第16行，进行了非法读操作。准确地发现了上述问题。
问题分析：
C 语言的强大和可怕之处在于其可以直接操作内存，C 标准库中提供了大量这样的函数，比如 strcpy, strncpy, memcpy, strcat 等，这些函数有一个共同的特点就是需要设置源地址 (src)，和目标地址(dst)，src 和 dst 指向的地址不能发生重叠，否则结果将不可预期。
下面就是一个 src 和 dst 发生重叠的例子。在 15 与 17 行中，src 和 dst 所指向的地址相差 20，但指定的拷贝长度却是 21，这样就会把之前的拷贝值覆盖。第 24 行程序类似，src(x+20) 与 dst(x) 所指向的地址相差 20，但 dst 的长度却为 21，这样也会发生内存覆盖。
结果分析：
假设这个文件名为 badlap.cpp，生成的可执行程序为 badlap，用 memcheck 对其进行测试，输出如下。
输出结果显示上述程序中第15，17，24行，源地址和目标地址设置出现重叠。准确的发现了上述问题。
问题分析：
常见的内存分配方式分三种：静态存储，栈上分配，堆上分配。全局变量属于静态存储，它们是在编译时就被分配了存储空间，函数内的局部变量属于栈上分 配，而最灵活的内存使用方式当属堆上分配，也叫做内存动态分配了。常用的内存动态分配函数包括：malloc, alloc, realloc, new等，动态释放函数包括free, delete。
一旦成功申请了动态内存，我们就需要自己对其进行内存管理，而这又是最容易犯错误的。下面的一段程序，就包括了内存动态管理中常见的错误。
常见的内存动态管理错误包括：
由于 C++ 兼容 C，而 C 与 C++ 的内存申请和释放函数是不同的，因此在 C++ 程序中，就有两套动态内存管理函数。一条不变的规则就是采用 C 方式申请的内存就用 C 方式释放；用 C++ 方式申请的内存，用 C++ 方式释放。也就是用 malloc/alloc/realloc 方式申请的内存，用 free 释放；用 new 方式申请的内存用 delete 释放。在上述程序中，用 malloc 方式申请了内存却用 delete 来释放，虽然这在很多情况下不会有问题，但这绝对是潜在的问题。
申请了多少内存，在使用完成后就要释放多少。如果没有释放，或者少释放了就是内存泄露；多释放了也会产生问题。上述程序中，指针p和pt指向的是同一块内存，却被先后释放两次。
本质上说，系统会在堆上维护一个动态内存链表，如果被释放，就意味着该块内存可以继续被分配给其他部分，如果内存被释放后再访问，就可能覆盖其他部分的信息，这是一种严重的错误，上述程序第16行中就在释放后仍然写这块内存。
结果分析：
假设这个文件名为badmac.cpp，生成的可执行程序为badmac，用memcheck对其进行测试，输出如下。
输出结果显示，第14行分配和释放函数不一致；第16行发生非法写操作，也就是往释放后的内存地址写值；第17行释放内存函数无效。准确地发现了上述三个问题。
问题描述：
内存泄露（Memory leak）指的是，在程序中动态申请的内存，在使用完后既没有释放，又无法被程序的其他部分访问。内存泄露是在开发大型程序中最令人头疼的问题，以至于有 人说，内存泄露是无法避免的。其实不然，防止内存泄露要从良好的编程习惯做起，另外重要的一点就是要加强单元测试（Unit Test），而memcheck就是这样一款优秀的工具。
下面是一个比较典型的内存泄露案例。main函数调用了mk函数生成树结点，可是在调用完成之后，却没有相应的函数：nodefr释放内存，这样内存中的这个树结构就无法被其他部分访问，造成了内存泄露。
在一个单独的函数中，每个人的内存泄露意识都是比较强的。但很多情况下，我们都会对malloc/free 或new/delete做一些包装，以符合我们特定的需要，无法做到在一个函数中既使用又释放。这个例子也说明了内存泄露最容易发生的地方：即两个部分的 接口部分，一个函数申请内存，一个函数释放内存。并且这些函数由不同的人开发、使用，这样造成内存泄露的可能性就比较大了。这需要养成良好的单元测试习 惯，将内存泄露消灭在初始阶段。
结果分析：
假设上述文件名位tree.h, tree.cpp, badleak.cpp，生成的可执行程序为badleak，用memcheck对其进行测试，输出如下。
本文介绍了valgrind的体系结构，并重点介绍了其应用最广泛的工具：memcheck。阐述了memcheck发现内存问题的基本原理，基本 使用方法，以及利用memcheck如何发现目前开发中最广泛的五大类内存问题。在项目中尽早的发现内存问题，能够极大地提高开发效率，valgrind 就是能够帮助你实现这一目标的出色工具。
Posts
All Comments
