1.strtolԴ?源码?
2.充分理解Linux GCC 链接生成的Map文件
strtolԴ??
哈弗曼压缩
#include <string.h>
#include <stdlib.h>
#include<iostream.h>
#include<fstream.h>
#define MaxNodes
#define MaxBufSize
#define MaxBits
struct Node
{
unsigned char b;
int count;
int parent,lch,rch;
char bits[MaxBits];
}Nodes[MaxNodes];
ifstream ifile;
ofstream ofile;
char *fname=new char();
unsigned char c;
char buf[MaxBufSize];
int flen;
int NodesNum;
void decompress();
void compress();
void charCount();
void initNodes();
void creatHuffTree();
void huffCoding();
void sortByCount();
int FindMin(int curlen);
void comToFile();
void decomToFile();
void clearSDS();
void locChar(int loc,int i);
void main()
{
char choice;
while(1)
{
cout<<" ------------------------------------------------------"<<endl;
cout<<" # 0.退出 #"<<endl;
cout<<" # 1.压缩 #"<<endl;
cout<<" # 2.解压 #"<<endl;
cout<<" ------------------------------------------------------"<<endl;
do
{
cout<<"请选择："<<endl;
cin>>choice;
if(choice!='0' && choice!='1' && choice!='2')
{
cout<<"输入出错！请重新输入！源码"<<endl;
}
}
while(choice!='0' && choice!='1' && choice!='2');
switch(choice)
{
case '0':cout<<"成功退出！源码"<<endl;exit(0); break;
case '1':compress();break;
case '2':decompress();break;
}
}
}
void compress()
{
cout<<"请输入待压缩的源码文件名：";
cin>>fname;
ifile.open(fname,ios::nocreate|ios::binary);
if(!ifile)
{
cout<<"文件不存在!"<<endl;
return;
}
charCount();
initNodes();
sortByCount();
creatHuffTree();
huffCoding();
cout<<"请输入压缩后的文件名：";
cin>>fname;
ofile.open(fname,ios::binary);
ofile.write((char*)&NodesNum,sizeof(NodesNum));
ofile.write((char*)&flen,sizeof(flen));
for(int i=0;i<NodesNum;i++)
{
ofile.write((char*)&Nodes[i].b,sizeof(Nodes[i].b));
ofile.write((char*)&Nodes[i].count,sizeof(Nodes[i].count));
}
comToFile();
ifile.close();
ofile.close();
clearSDS();
}
void decompress()
{
clearSDS();//不加此句，关闭程序再解压，源码会提示BUF出错
cout<<"请输入待解压的源码乐视源码文件名：";
cin>>fname;
ifile.open(fname,ios::nocreate|ios::binary);
if(!ifile)
{
cout<<"文件不存在!"<<endl;
return;
}
ifile.read((char*)&NodesNum,sizeof(NodesNum));
ifile.read((char*)&flen,sizeof(flen));
cout<<NodesNum<<" "<<flen<<endl;
for(int i=0;i<NodesNum;i++)
{
ifile.read((char*)&Nodes[i].b,sizeof(Nodes[i].b));
ifile.read((char*)&Nodes[i].count,sizeof(Nodes[i].count));
}
creatHuffTree();
cout<<"请输入解压后的文件名：";
cin>>fname;
ofile.open(fname);
decomToFile();
ifile.close();
ofile.close();
clearSDS();
}
void clearSDS()//SDS is short for Shared Data Structure
{
NodesNum=flen=c=0;
for(int i=0;i<MaxNodes;i++)
{
Nodes[i].b=0;
Nodes[i].count=0;
Nodes[i].parent=Nodes[i].lch=Nodes[i].rch=-1;
buf[i]=0;
for(int j=0;j<MaxBits;j++) Nodes[i].bits[j]=0;
}
}
void comToFile()
{
ifile.clear();
ifile.seekg(0);
char tbuf[]="";
while(ifile.get(c))
{
for(int i=0;i<NodesNum;i++)
{
if(c==Nodes[i].b)
{
strcat(buf,Nodes[i].bits);
break;
}
}
while(strlen(buf)>=8)
{
memcpy(tbuf,buf,8);
c=(char)strtol (tbuf,NULL,2);
memmove(buf,buf+8,strlen(buf)+1-8);
ofile.write((char*)&c,sizeof(c));
}
}
if(strlen(buf)>0)//剩余
{
strcat(buf,"");//最多接7个0即可
memcpy(tbuf,buf,8);
c=(char)strtol (tbuf,NULL,2);
ofile.write((char*)&c,sizeof(c));
}
}
void decomToFile()
{
while (ifile.get(c)) //while(!ifile.eof()),老样子
{ //ifile.read((char*)&c,sizeof(c));
char tbuf[]="";
char rbuf[]="";
itoa((int)c,rbuf,2);
strcpy(tbuf+8-strlen(rbuf),rbuf);
memmove(buf+strlen(buf),tbuf,8);//末尾会多一个tbuf，无碍
while(strlen(buf)>&&flen>0) locChar(2*NodesNum-2,源码0);
}
while(strlen(buf)>0&&flen>0) locChar(2*NodesNum-2,0);
}
void locChar(int loc,int i)//递归得出字符
{
if((Nodes[loc].lch==-1)&&(Nodes[loc].rch==-1))
{
ofile.write((char*)&Nodes[loc].b,sizeof(Nodes[loc].b));
flen--;
//memmove(buf,buf+i,strlen(buf)-i+1);
//memmove(buf,buf+i,-i);//Very improtant code modified at here!
memcpy(buf,buf+i,-i);//Same result Like the line Above!Maybe not effective
return;
}
else
{
switch( buf[i])
{
case '0': loc=Nodes[loc].lch;break;
case '1': loc=Nodes[loc].rch;break;
default: cout<<"buf中出错！"<<endl;break;
}
i++;
locChar(loc,源码i);
}
}
void charCount()//统计字符出现次数
{
while(ifile.get(c))
{
Nodes[c].count++;
flen++;//得出文件长度
}
}
void initNodes()//初始化
{
for(int i=0;i<MaxNodes;i++)
{
if(Nodes[i].count!=0)
Nodes[i].b=(unsigned char)i;
else Nodes[i].b=0;
Nodes[i].parent=Nodes[i].lch=Nodes[i].rch=-1;
}
}
void creatHuffTree()//建树
{
int t=2*NodesNum-1;
for(int i=NodesNum;i<t;i++)
{
int loc=FindMin(i);
Nodes[i].count=Nodes[loc].count;
Nodes[loc].parent=i;
Nodes[i].lch=loc;
loc=FindMin(i);
Nodes[i].count+=Nodes[loc].count;
Nodes[loc].parent=i;
Nodes[i].rch=loc;
}
Nodes[t-1].parent=-1;
}
int FindMin(int curlen)//找没有父结点，且Count最小的源码节点
{
int loc=curlen-1;//找不到，返回最后一个，源码最后一个不在查找范围
for(int i=0;i<curlen;i++)
{
if(Nodes[i].count<=Nodes[loc].count)
{
if(Nodes[i].parent==-1)
loc=i;
}
}
return loc;
}
void huffCoding()//根据树来编码
{
int Pid,源码t;//Parent id
for(int i=0;i<NodesNum;i++)
{
t=i;
while(Nodes[t].parent!=-1)
{
Pid=Nodes[t].parent;
if(Nodes[Pid].lch==t) //置左分支编码0
{ //函数原型：void *memmove( void *dest, const void *src, size_t count );
memmove(Nodes[i].bits+1,Nodes[i].bits,strlen(Nodes[i].bits)+1);
Nodes[i].bits[0]='0';
}
else //置右分支编码1
{
memmove(Nodes[i].bits+1,Nodes[i].bits,strlen(Nodes[i].bits)+1);
Nodes[i].bits[0]='1';
}
t=Pid;
}
}
}
//降序
void sortByCount()
{
Node tempNode;
for(int i=0;i<MaxNodes;i++)
for(int j=MaxNodes-1;j>i;j--)
{
if(Nodes[i].count<Nodes[j].count)
{
tempNode=Nodes[i];
Nodes[i]=Nodes[j];
Nodes[j]=tempNode;
}
}
for(i=0;i<MaxNodes;i++) if(Nodes[i].count==0) break;
NodesNum=i;//关键得出有效叶子结点个数NodesNum
}
充分理解Linux GCC 链接生成的Map文件
简单来说，map文件就是源码通过编译器编译之后，生成的源码程序、数据及IO空间信息的源码一种映射文件，里面包含函数大小，源码入口地址等一些重要信息。从map文件我们可以了解到：
生成map文件是链接器ld的功能，有两种方式可以生成map文件：
使用GNU binutils，必须通过设置正确的提交订单 源码标志来显式地请求生成映Map文件。使用LD将Map打印到输出到output.map:
作为一个简单程序的例子，你可以使用以下命令链接编译单元:
为什么要了解Map文件：
在本文中，我想突出说明链接器Map文件是多么简单，以及它可以教给我们关于正在处理的程序的一些知识。
固件工程师很少在调试时使用构建过程生成的Map文件。然而，答案有时就在这个Map文件中。
Map文件提供了有价值的信息，可以帮助您理解和优化内存。我强烈建议为在生产环境中运行的任何固件保存该文件。
Map文件是整个程序的符号表。让我们深入研究它，看看它有多简单，以及如何有效地使用它。我将尝试用一些例子来说明，这些例子都是用GNU binutils来描述的。
LED闪烁程序：
还有什么比我们的老朋友LED闪烁程序示例解释一下Map文件的基础知识更好的呢?
为了了解Map文件，我们使用Nordic SDK中的obs源码编译LED闪烁程序来编译，并修改它以添加对atoi的调用。然后，我们将使用Map文件来分析这两个程序之间的差异。
下面就是示例的main.c文件：
编译：
生成的Map文件有多行 ，尽管它只是在闪烁发光二极管。这么多行不可能看不见，里面一定有一些重要的信息……
现在让我们修改程序，添加对atoi的调用，我们不直接使用整数作为延迟函数的参数，而是将其编码为字符串并使用atoi解码，然后作为参数传给延时函数。
经过编译，整个程序从字节变成了字节。
我们能够想到调用atoi会带来更多的代码，但是%程序大小的增加是巨大的!
深入研究Map文件：
在下面的部分中，我将使用代码片段来解释Map文件的不同部分。
Archives linked：
下面是Map文件的第一行内容：
上述信息的格式如下：
上面内容的意思是crt0这个文件中会调用exit函数，exit函数在exit.o这个目标文件中，挪车 源码exit.o目标文件是被链接在libc_nano.a这个库文件里的。
为什么是这样，不在本文的讨论范围内，但是你的工具链(这里是GNU工具链)确实提供了一些标准库。它们可用于提供atoi等标准功能，在这个例子中，我指定链接器使用nano.spec文件，这就是为什么标准函数都来自libc_nano.a。
现在，比较两个生成的map文件，发现的第一个区别是程序中包含了一些其他的存档成员:atoi，它本身需要_strtol_r，_strtol_r本身又需要_ctype_:
现在，我们对实际包含在程序中的文件以及它们存在的原因有了更好的理解。让我们来看看这个文件里面还有什么!
Memory configuration：
Map文件中最直接的信息是实际的内存区域，这些区域具有位置、大小和访问权限:
Linker script and memory map：
内存配置之后是Linker script and memory map，这个很有趣，linux 修改源码因为它给出了程序中符号的详细信息。在我们的例子中，它首先指示text区域的大小及其内容(text是我们编译的代码，而data是程序数据)。
在这里，中断向量(在.isr_vector下)出现在可执行文件的开头，定义在gcc_startup_nrf.S中:
这些行给出了每个函数的地址和大小。在上面，你可以读取bsp_board_led_invert的地址，它来自boards.c.o(如你所猜测的，board.c的编译单元)，在text区域中它的大小为0x字节。这样，我们就可以定位程序中使用的每个函数。
我的常量字符串_delay_ms_str在程序初始化时显然包含在程序中，只读数据作为rodata保存在链接器脚本中指定的FLASH区域中(存储在Flash中，而不是复制在RAM中，因为它是常量)。我可以在这行下面找到:
我还注意到_ctype_的包含在text区域中增加了0x字节的只读数据
标准库是开源的（ 链接），我们很容易就能找出它占用那么多空间的原因。我深入到atoi的内部（可重入版本的atoi_r，见下文），它是直接调用的strtol_r：
对于strtol_r，它实际上比仅仅将字符转换为整数更复杂，因为还使用ctype来执行类型检查。ctype的工作方式是使用一个表，其中ASCII符号类型存储在一个数组中。下面是ctype的主要部分，并附上我的注释:
有趣的是，atoi的添加不仅增加了代码的大小(text区域)，还增加了数据的大小(data区域)。分析两个Map文件，我可以很容易地发现之前被链接器丢弃的数据:
现在你可能已经注意到函数名以_r结尾，例如在调用strtol_r时，该后缀表示可重入性。有关可重入性的文档可以在 newlib源代码中找到。总而言之，即使同一函数已经在另一个进程中执行，也可以调用可重入函数，而不会干涉执行。从文档中可以看到如下描述：
Each function which uses the global reentrancy structure uses the global variable _impure_ptr, which points to a reentrancy structure.
在我们的例子中，我们需要新的全局变量来调用可重入函数:atoi_r。
最后要记住的一点信息是:初始化变量必须保存在Flash中，但它们在Map文件中会出现在RAM中，因为它们在进入主函数之前被复制到RAM中。在这里，符号__data_start__和__data_end__跟踪RAM中用于保存初始化变量的区域，这些值存储在Flash中，起始位置为0xd0:
Discarded sections：
如果链接器没有找到对函数和变量的任何引用，编译后包含在程序中的函数和变量并不总是最终二进制文件的一部分，它们将会被删除但是仍然会出现在Map文件的Discarded input sections 部分。例如，下面是一些定义在boards.c中的函数，它们永远不会被调用并因此被丢弃:
Common symbols：
这个部分没有出现在我们的Map文件中，但它值得一提。
Common symbols（通用符号）是可以在代码中的任何地方使用的非常量全局变量（non-constant global variables）。您可能知道，使用全局变量通常不是一个好的实践，因为它们使代码更难维护。确实如此，作用域是全局的，每个外部模块可以修改任何全局变量的值，访问时必须考虑到这一点。将变量隔离到一个模块中，使用static关键字，通常更好地确保创建变量的模块完全负责其状态。
现在，如果您希望使程序更安全并防止访问某些全局变量，请查看Map文件部分。如果某些变量不需要声明为全局变量，您可能希望将它们转换为静态变量。
Map文件有几种可能的用法：大多数时候，一个地址后面对应着一个函数，我们希望通过这个地址去了解一些问题。例如，它可以是硬故障处理程序（Hard Fault handler）中的程序计数器（Program Counter）。其他时候，你也会遇到调试一些不明确的行为，最终发现你的程序意外地写入了一个出界数组（数组越界）。当有了ELF文件时，arm-none-eabi-nm对于这些事情也非常有用，它提供了按大小排序符号的选项。
但有些时候，它甚至在你有可执行文件之前就很有用了……
Debugging a linking error：
Map文件是在构建代码(.o文件)链接在一起的时候生成的，这意味着它可以有助于解决链接过程中出现的错误。我记得在几个Flash页面中包含一个引导加载程序，在某些情况下，我想使用atoi，但引导加载程序不再编译，因为没有更多的可用空间。
使用前面的示例，假设我现在只有0x字节的Flash。编译第一个示例时，如果没有atoi，就不会出现问题，但是第二个例子会溢出我们的Flash:
是不是很讨厌？atoi只是一个很简单的函数而已，居然就出现这种问题。但正如我们前面所提到的，使用libc_nano.a需要比预期更多的Flash空间。
让我们来实现自己版本的atoi，其实也没那么难。以下是编译后的结果(config CUSTOM_ATOI):
这个方法是不是很好？现在可以将代码塞进0x字节的Flash,以满足我们的(假)需求。
分析Map文件可以让我们了解很多正在编写的代码，这是改进固件的第一步。
可以使用一些工具来解析Map文件并获得程序的汇总视图，后面有时间和大家好好聊聊。
