4动态链接
4.1概述
在静态链接阶段，链接器为PE文件生成了导入表，导出表，符号表，并调整了Call指令后面的操作数，在程序调用的时候，能够直接地或者间接地定位到IAT中的某个位置，在PE文件中，该位置包含符号的名称，当PE文件加载到内存以后，该位置应该修正为符号的地址。这些已有的信息和已经完成的工作是后续动态链接的基础。
动态链接的任务是：在程序的加载或者运行阶段，执行各个模块的基址重定位工作，并将IAT中的符号名称修正为动态链接库中被调用的符号的地址。
动态链接分为隐式动态链接和显式动态链接，无论是隐式动态链接还是显式动态链接，都会涉及到对WindowsAPI函数：LoadLibrary()，GetProcAddress()，FreeLibrary()的调用。它们之间的区别是：在执行隐式动态链接的时候，由Windows加载器负责完成对这些Windows API的调用；而在显式动态链接的时候，这些Windows API函数必须由程序员编写代码主动地调用。
隐式动态链接在程序加载到内存的时候完成，而显式动态链接则将这一过程推迟到程序运行的过程中。
动态链接的流程如下图所示：
由上图可以看出，动态链接的两个主要任务：动态链接库加载完毕以后的基址重定位，以及对导入表中函数名称的修正，即：将函数名称转换成函数的地址。
4.2程序加载及基址重定位
PE文件具有段结构，包含的主要的段有：代码段，数据段，导入表，导出表，符号表，基址重定位表等。当PE文件存储在文件中或者被加载到内存中的时候，这些段都需要遵循某个对齐规则。
PE中规定了三类对齐：数据在内存中的对齐，数据在文件中的对齐，资源数据在资源文件中的对齐。
数据在内存中的对齐。在内存中，PE文件以内存页的大小作为对齐粒度。在Windows操作系统中，内存以分页的方式进行管理。在32位Windows下，内存页的大小是4KB；在64位Windows下，内存页的大小是8KB。当PE文件被加载到内存以后，各段的起始地址必须是内存页大小的整数倍。
数据在文件中的对齐。在文件中，PE文件以一个扇区的大小作为对齐粒度。一个扇区的大小为512字节，十六进制表示为200h。在文件存储中，各段的地址偏移必须是200h的整数倍。
资源数据在资源文件中的对齐。在资源文件中，资源字节码以4字节作为对齐粒度。
由于在内存中PE文件以4KB作为对齐粒度，而在文件中以512字节作为对齐粒度，因此当PE文件被加载到内存以后，PE文件的尺寸要大于该文件在硬盘上的尺寸。在执行加载的时候，操作系统会读取PE文件的头信息，去除不需要加载到内存的部分，如：调试信息等，然后操作系统将整个PE文件映射到内存空间中。在将PE文件加载到内存以后，PE文件的结构和布局不会被改变。因此，PE文件在硬盘上的数据结构与在内存中的数据结构是相同的。具体的对比情况如下图所示：
当PE文件被windows加载器加载到内存以后，在内存中的版本被称为模块，每一个模块的起始内存地址被称为HMODULE。通过这个HMODULE可以获得该模块的数据内容。
当可执行程序被加载到内存以后，Windows会查询PE文件中的相关信息，获得该可执行程序所依赖的动态链接库，然后Windows将这些动态链接库也加载到内存中。如果某个要被加载地动态链接库已经位于内存中，那么操作系统就增加这个动态链接库的引用计数。当可执行程序和它所依赖的动态链接库都被加载到内存以后，Windows加载器开始执行基址重定位工作。Windows加载器加载可执行程序以及动态链接库的流程如下图所示：
当可执行文件以及它所依赖的动态链接库文件被加载到内存以后，如果该文件被加载的内存位置不是基于默认内存地址的位置（可执行程序是0x00400000h，动态链接库是0x10000000），那么windows加载器就必须执行基址重定位工作。该工作是在基址重定位表的支持下完成的。对于每一个需要进行重定位的内存地址，加载器都会给它加上一个差值作为修正。该差值为模块当前加载到内存的地址 – 模块默认加载位置的地址。具体的操作流程如下图所示：
当完成基址重定位工作以后，导出地址表（EAT）中的地址也被修正完毕。在PE文件中，这些地址是基于默认加载位置的地址，如果当前加载位置发生了变化，那么这些地址是要被修正的。参见2.4.7节。
4.3符号解析
符号解析是动态链接中最重要的一环，在该阶段，加载器读取PE文件中的导入地址表（IAT）的信息，取得每一个函数的名称，然后用该函数的名称去相关动态链接库中查询函数的地址，用获得的地址替换该函数名称。这一步工作是将函数名称替换为函数地址的过程。具体过程如下图所示：
由于一个可执行程序可能会依赖多个动态链接库，那么在导入表数组中就会包含多个数组元素，所以在符号解析的时候是一个循环处理。加载器对导入表数组执行循环，取得每一个数组元素，然后根据获得的Dll名称查找到相关的动态链接库的位置。获得了相关动态链接库的信息以后，加载器从导入地址表中取得一个符号的名称，以该符号名称为条件去对应的动态链接库中查询。经过对符号名称表，名称序号对应表，以及符号地址表的查询，最后获得符号的地址，将此地址写回到导入地址表原来符号名称的位置。
嗯，那个恭喜你，看完了。为了写这个东西，也把我累的够呛，哈哈。
本文链接：http://www.cnblogs.com/wolf-lifeng/p/3197842.html，转载请注明。
最长公共子串(Longest Common Substring)是一个非常经典的面试题目，在实际的程序中也有很高的实用价值，所以把该问题的解法总结在本文重。不过不单单只是写出该问题的基本解决代码而已，关键还是享受把学习算法一步步的优化，让时间和空间复杂度一步步的减少的惊喜。
概览
最长公共子串问题的基本表述为：
给定两个字符串，求出它们之间最长的相同子字符串的长度。
最直接的解法自然是找出两个字符串的所有子字符串进行比较看他们是否相同，然后取得相同最长的那个。对于一个长度为n的字符串，它有n(n+1)/2 个非空子串。所以假如两个字符串的长度同为n，通过比较各个子串其算法复杂度大致为O(n4)。这还没有考虑字符串比较所需的时间。简单想想其实并不需要取出所有的子串，而只要考虑每个子串的开始位置就可以，这样可以把复杂度减到O(n3)。
但这个问题最好的解决办法是动态规划法，在后边会更加详细介绍这个问题使用动态规划法的契机：有重叠的子问题。进而可以通过空间换时间，让复杂度优化到O(n2)，代价是空间复杂度从O(1)一下子提到了O(n2)。
从时间复杂度的角度讲，对于最长公共子串问题，O(n2)已经是目前我所知最优的了，也是面试时所期望达到的。但是对于空间复杂度O(n2)并不算什么，毕竟算法上时间比空间更重要，但是如果可以省下一些空间那这个算法就会变得更加美好。所以进一步的可以把空间复杂度减少到O(n)，这是相当美好了。但有一天无意间让我发现了一个算法可以让该问题的空间复杂度减少回原来的O(1)，而时间上如果幸运还可以等于O(n)。
暴力解法 – 所得即所求
对于该问题，直观的思路就是问题要求什么就找出什么。要子串，就找子串；要相同，就比较每个字符；要最长就记录最长。所以很容易就可以想到如下的解法。
2 {
3 size_t size1 = str1.size();
4 size_t size2 = str2.size();
5 if (size1 == 0 || size2 == 0) return 0;
6
7 // the start position of substring in original string
8 int start1 = -1;
9 int start2 = -1;
10 // the longest length of common substring
11 int longest = 0;
12
13 // record how many comparisons the solution did;
14 // it can be used to know which algorithm is better
15 int comparisons = 0;
16
17 for (int i = 0; i < size1; ++i)
18 {
19 for (int j = 0; j < size2; ++j)
20 {
21 // find longest length of prefix
22 int length = 0;
23 int m = i;
24 int n = j;
25 while(m < size1 && n < size2)
26 {
27 ++comparisons;
28 if (str1[m] != str2[n]) break;
29
30 ++length;
31 ++m;
32 ++n;
33 }
34
35 if (longest < length)
36 {
37 longest = length;
38 start1 = i;
39 start2 = j;
40 }
41 }
42 }
43 #ifdef IDER_DEBUG
44 cout<< "(first, second, comparisions) = ("
45 << start1 << ", " << start2 << ", " << comparisons
46 << ")" << endl;
47
没有评论:
发表评论