Opencv2.4.9源码分析——Extremely
randomized trees
一、原理
ET或Extra-Trees（Extremely randomized trees，极端随机树）是由PierreGeurts等人于2006年提出。该算法与随机森林算法十分相似，都是由许多决策树构成。但该算法与随机森林有两点主要的区别：
1、随机森林应用的是Bagging模型，而ET是使用所有的训练样本得到每棵决策树，也就是每棵决策树应用的是相同的全部训练样本；
2、随机森林是在一个随机子集内得到最佳分叉属性，而ET是完全随机的得到分叉值，从而实现对决策树进行分叉的。
对于第2点的不同，我们再做详细的介绍。我们仅以二叉树为例，当特征属性是类别的形式时，随机选择具有某些类别的样本为左分支，而把具有其他类别的样本作为右分支；当特征属性是数值的形式时，随机选择一个处于该特征属性的最大值和最小值之间的任意数，当样本的该特征属性值大于该值时，作为左分支，当小于该值时，作为右分支。这样就实现了在该特征属性下把样本随机分配到两个分支上的目的。然后计算此时的分叉值（如果特征属性是类别的形式，可以应用基尼指数；如果特征属性是数值的形式，可以应用均方误差）。遍历节点内的所有特征属性，按上述方法得到所有特征属性的分叉值，我们选择分叉值最大的那种形式实现对该节点的分叉。从上面的介绍可以看出，这种方法比随机森林的随机性更强。
对于某棵决策树，由于它的最佳分叉属性是随机选择的，因此用它的预测结果往往是不准确的，但多棵决策树组合在一起，就可以达到很好的预测效果。
当ET构建好了以后，我们也可以应用全部的训练样本来得到该ET的预测误差。这是因为尽管构建决策树和预测应用的是同一个训练样本集，但由于最佳分叉属性是随机选择的，所以我们仍然会得到完全不同的预测结果，用该预测结果就可以与样本的真实响应值比较，从而得到预测误差。如果与随机森林相类比的话，在ET中，全部训练样本都是OOB样本，所以计算ET的预测误差，也就是计算这个OOB误差。
在这里，我们仅仅介绍了ET算法与随机森林的不同之处，ET算法的其他内容（如预测、OOB误差的计算）与随机森林是完全相同的，具体内容请看关于随机森林的介绍。
二、源码分析
下面是ET算法的类CvERTrees，它继承于CvRTrees类：
[cpp] view plain copy 在CODE上查看代码片派生到我的代码片
class CV_EXPORTS_W CvERTrees : public CvRTrees
{
public:
CV_WRAP CvERTrees();
virtual ~CvERTrees();
virtual bool train( const CvMat* trainData, int tflag,
const CvMat* responses, const CvMat* varIdx=0,
const CvMat* sampleIdx=0, const CvMat* varType=0,
const CvMat* missingDataMask=0,
CvRTParams params=CvRTParams());
CV_WRAP virtual bool train( const cv::Mat& trainData, int tflag,
const cv::Mat& responses, const cv::Mat& varIdx=cv::Mat(),
const cv::Mat& sampleIdx=cv::Mat(), const cv::Mat& varType=cv::Mat(),
const cv::Mat& missingDataMask=cv::Mat(),
CvRTParams params=CvRTParams());
virtual bool train( CvMLData* data, CvRTParams params=CvRTParams() );
protected:
virtual std::string getName() const;
virtual bool grow_forest( const CvTermCriteria term_crit );
};
我们从CvERTrees类可以看出，它没有预测函数predict，因此，如果要进行ET的预测，调用的是它的父类CvRTrees内的predict函数。在训练样本时，CvERTrees类与CvRTrees类的训练过程是完全一致的，即在train函数内再调用grow_forest函数，而且两个类的train函数的输入参数的形式也是完全一样的。但在grow_forest函数内会有一点不同，那就是CvERTrees类中的grow_forest函数把全体训练样本都当成OOB样本，因此它不需要随机样本掩码矩阵变量sample_idx_mask_for_tree，而表示样本索引值变量的sample_idx_for_tree 保存的就是正常顺序的训练样本的索引值。
ET算法与随机森林算法最大的不同就在于节点的分叉上，而这一点是体现在CvForestERTree类上的：
[cpp] view plain copy 在CODE上查看代码片派生到我的代码片
class CV_EXPORTS CvForestERTree : public CvForestTree
{
protected:
virtual double calc_node_dir( CvDTreeNode* node );
virtual CvDTreeSplit* find_split_ord_class( CvDTreeNode* n, int vi,
float init_quality = 0, CvDTreeSplit* _split = 0, uchar* ext_buf = 0 );
virtual CvDTreeSplit* find_split_cat_class( CvDTreeNode* n, int vi,
float init_quality = 0, CvDTreeSplit* _split = 0, uchar* ext_buf = 0 );
virtual CvDTreeSplit* find_split_ord_reg( CvDTreeNode* n, int vi,
float init_quality = 0, CvDTreeSplit* _split = 0, uchar* ext_buf = 0 );
virtual CvDTreeSplit* find_split_cat_reg( CvDTreeNode* n, int vi,
float init_quality = 0, CvDTreeSplit* _split = 0, uchar* ext_buf = 0 );
virtual void split_node_data( CvDTreeNode* n );
};
CvForestERTree类定义了一些专用于ET算法的计算分叉、得到最佳分叉属性的函数，下面我们就逐一介绍这些函数。
按最佳分叉属性标注该节点的所有样本是被分配到左分支还是右分支：
[cpp] view plain copy 在CODE上查看代码片派生到我的代码片
double CvForestERTree::calc_node_dir( CvDTreeNode* node )
{
//表示特征属性的种类是属于左分支还是右分支，-1为左分支，1为右分支，如果该特征属性缺失，则为0
char* dir = (char*)data->direction->data.ptr;
//n表示该节点的样本数量，vi表示分类的最佳特征属性
int i, n = node->sample_count, vi = node->split->var_idx;
double L, R;
assert( !node->split->inversed ); //确保分叉不反转
if( data->get_var_type(vi) >= 0 ) // split on categorical var
//表示该特征属性是种类的形式
{
//开辟一块内存空间
cv::AutoBuffer
int* labels_buf = (int*)(uchar*)inn_buf;
//labels指向该特征属性中各个样本所对应的种类，get_cat_var_data函数在ER算法中被重新定义
const int* labels = data->get_cat_var_data( node, vi, labels_buf );
// subset数组的每一位表示特征属性的种类，左分支的种类位是1，右分支的是0
const int* subset = node->split->subset;
if( !data->have_priors ) //无先验概率
{
int sum = 0, sum_abs = 0;
for( i = 0; i < n; i++ ) //遍历该节点的所有样本
{
int idx = labels[i]; //表示该样本的特征属性的种类
//d为-1表示idx（特征属性的种类）属于左分支，为1表示属于右分支，如果没有该特征属性，则d为0
int d = ( ((idx >= 0)&&(!data->is_buf_16u)) || ((idx != 65535)&&(data->is_buf_16u)) ) ?
CV_DTREE_CAT_DIR(idx,subset) : 0;
//sum表示d累加求和，因为d也可能为负值，所以sum的含义为右分支比左分支多出的特征属性种类；sum_abs表示d的绝对值之和，表示的含义为被分叉的特征属性种类
sum += d; sum_abs += d & 1;
dir[i] = (char)d; //赋值
}
//L和R分别表示左右分支的特征属性的种类数量
R = (sum_abs + sum) >> 1;
L = (sum_abs - sum) >> 1;
}
else //有先验概率
{
const double* priors = data->priors_mult->data.db; //得到先验概率
double sum = 0, sum_abs = 0;
int *responses_buf = labels_buf + n;
//responses指向该节点样本的分类，即响应值
const int* responses = data->get_class_labels(node, responses_buf);
for( i = 0; i < n; i++ ) //遍历该节点的所有样本
{
int idx = labels[i]; //表示该样本的特征属性的种类
double w = priors[responses[i]]; //得到该响应值的先验概率
//d为-1表示idx（特征属性的种类）属于左分支，为1表示属于右分支，如果没有该特征属性，则d为0
int d = idx >= 0 ? CV_DTREE_CAT_DIR(idx,subset) : 0;
sum += d*w; sum_abs += (d & 1)*w; //增加了先验概率
dir[i] = (char)d;
}
//L和R分别表示左右分支的特征属性的种类数量
R = (sum_abs + sum) * 0.5;
L = (sum_abs - sum) * 0.5;
}
}
else // split on ordered var
//表示该特征属性是数值的形式
{
//得到分叉属性的值split_val，如果样本的分叉属性的值小于该值，则被分叉为左节点，否则为右节点
float split_val = node->split->ord.c;
//为该特征属性开辟一块内存空间
cv::AutoBuffer
float* val_buf = (float*)(uchar*)inn_buf; //用于存储各个样本当前特征属性的值
int* missing_buf = (int*)(val_buf + n); //表示各个样本是否缺失当前特征属性
const float* val = 0; //指向数组val_buf
const int* missing = 0; //指向数组missing_buf
// get_ord_var_data函数在ER算法中被重新定义，各个样本的vi特征属性的值存储在val_buf数组内，各个样本是否缺失该特征属性用missing_buf数组表示
data->get_ord_var_data( node, vi, val_buf, missing_buf, &val, &missing, 0 );
if( !data->have_priors ) //无先验概率
{
L = R = 0;
for( i = 0; i < n; i++ ) //遍历所有样本
{
if ( missing[i] ) //该样本缺失vi这个特征属性
dir[i] = (char)0; //方向信息赋值为0
else
{
if ( val[i] < split_val) //左分支
{
dir[i] = (char)-1; //方向信息赋值为-1
L++; //左分支计数
}
else //右分支
{
dir[i] = (char)1; //方向信息赋值为1
R++; //右分支计数
}
}
}
}
else //有先验概率
{
const double* priors = data->priors_mult->data.db; //得到先验概率
int* responses_buf = missing_buf + n;
//responses指向该节点样本的分类，即响应值
const int* responses = data->get_class_labels(node, responses_buf);
L = R = 0;
for( i = 0; i < n; i++ ) //遍历所有样本
{
if ( missing[i] ) //该样本缺失vi这个特征属性
dir[i] = (char)0;
else
{
double w = priors[responses[i]]; //得到先验概率
if ( val[i] < split_val) //左分支
{
dir[i] = (char)-1;
L += w;
}
else //右分支
{
dir[i] = (char)1;
R += w;
}
}
}
}
}
node->maxlr = MAX( L, R ); //表示左右分支最大值
return node->split->quality/(L + R); //得到规范化系数
}
特征为数值的分类树的分叉方法：
[cpp] view plain copy 在CODE上查看代码片派生到我的代码片
CvDTreeSplit* CvForestERTree::find_split_ord_class( CvDTreeNode* node, int vi, float init_quality, CvDTreeSplit* _split,
uchar* _ext_buf )
{
const float epsilon = FLT_EPSILON*2; //定义一个最小常数
const float split_delta = (1 + FLT_EPSILON) * FLT_EPSILON; //定义另一个常数
int n = node->sample_count; //该节点的样本数量
int m = data->get_num_classes(); //样本数据的分类数
//为该特征属性vi开辟一块内存空间
cv::AutoBuffer
if( !_ext_buf )
inn_buf.allocate(n*(2*sizeof(int) + sizeof(float)));
uchar* ext_buf = _ext_buf ? _ext_buf : (uchar*)inn_buf;
float* values_buf = (float*)ext_buf; //用于存储各个样本在特征属性vi的值
int* missing_buf = (int*)(values_buf + n); //表示各个样本是否缺失当前特征属性
const float* values = 0; //指向数组values_buf
const int* missing = 0; //指向数组missing_buf
//得到数组values_buf和missing_buf
data->get_ord_var_data( node, vi, values_buf, missing_buf, &values, &missing, 0 );
int* responses_buf = missing_buf + n;
//responses指向该节点样本的分类，即响应值
const int* responses = data->get_class_labels( node, responses_buf );
double lbest_val = 0, rbest_val = 0, best_val = init_quality, split_val = 0;
//得到不同分类的先验概率
const double* priors = data->have_priors ? data->priors_mult->data.db : 0;
bool is_find_split = false; //表示是否找到了分叉属性
float pmin, pmax; //分别表示样本的特征属性vi的最小值和最大值
int smpi = 0; //表示缺失特征属性的样本索引值
//得到第一个不缺失vi特征属性的样本
while ( missing[smpi] && (smpi < n) )
smpi++;
assert(smpi < n); //确保smpi的正确
//初始化pmin和pmax
pmin = values[smpi];
pmax = pmin;
for (; smpi < n; smpi++) //遍历样本，得到pmin和pmax
{
float ptemp = values[smpi]; //得到当前样本的vi的值
int ms = missing[smpi]; //当前样本是否缺失该vi值
if (ms) continue; //缺失则遍历下一个样本
if ( ptemp < pmin) //更新pmin值
pmin = ptemp;
if ( ptemp > pmax) //更新pmax值
pmax = ptemp;
}
float fdiff = pmax-pmin; //pmax与pmin的差值
//差值大于一个常数，表示前面计算的结果是有意义的，也就是得到了分叉属性if (fdiff > epsilon)
{
is_find_split = true; //表示找到了分叉属性
cv::RNG* rng = data->rng; //表示随机数
//随机数为0和1之间的任意数，split_val为pmax与pmin之间任意一个数split_val = pmin + rng->uniform(0.f, 1.f) * fdiff ;
//如果split_val太接近pmax或pmin，则split_val为一个定值
if (split_val - pmin <= FLT_EPSILON)
split_val = pmin + split_delta;
if (pmax - split_val <= FLT_EPSILON)
split_val = pmax - split_delta;
// calculate Gini index
//计算基尼指数
if ( !priors ) //样本没有先验概率
{
cv::AutoBuffer
//lc和rc分别表示分类的左、右分支
int *lc = lrc, *rc = lc + m;
int L = 0, R = 0; //表示左、右分支的样本数
// init arrays of class instance counters on both sides of the split for(int i = 0; i < m; i++ ) //数组lc和rc清零
{
lc[i] = 0;
rc[i] = 0;
}
for( int si = 0; si < n; si++ ) //遍历所有样本
{
int r = responses[si]; //该样本的响应值
float val = values[si]; //该样本的特征属性vi的值
int ms = missing[si]; //当前样本是否缺失该vi值
if (ms) continue; //缺失则遍历下一个样本
if ( val < split_val ) //左分支
{
lc[r]++;
L++;
}
else //右分支
{
rc[r]++;
R++;
}
}
//得到分类后的基尼指数best_val
for (int i = 0; i < m; i++)
{
lbest_val += lc[i]*lc[i];
rbest_val += rc[i]*rc[i];
}
best_val = (lbest_val*R + rbest_val*L) / ((double)(L*R));
}
else //样本有先验概率
{
cv::AutoBuffer
double *lc = lrc, *rc = lc + m;
double L = 0, R = 0;
// init arrays of class instance counters on both sides of the split for(int i = 0; i < m; i++ )
{
lc[i] = 0;
rc[i] = 0;
}
for( int si = 0; si < n; si++ )
{
int r = responses[si];
float val = values[si];
int ms = missing[si];
double p = priors[r]; //得到先验概率
if (ms) continue;
if ( val < split_val ) //左分支
{
lc[r] += p;
L += p;
}
else //右分支
{
rc[r] += p;
R += p;
}
}
for (int i = 0; i < m; i++)
{
lbest_val += lc[i]*lc[i];
rbest_val += rc[i]*rc[i];
}
best_val = (lbest_val*R + rbest_val*L) / (L*R);
}
}
CvDTreeSplit* split = 0;
if( is_find_split ) //表明得到了分叉属性
{
split = _split ? _split : data->new_split_ord( 0, 0.0f, 0, 0, 0.0f ); //实例化split变量
split->var_idx = vi; //特征属性
split->ord.c = (float)split_val; //特征属性的值
split->ord.split_point = -1;
split->inversed = 0;
split->quality = (float)best_val; //基尼指数
}
return split; //返回
}
特征为类的分类树的分叉方法：
[cpp] view plain copy 在CODE上查看代码片派生到我的代码片
CvDTreeSplit* CvForestERTree::find_split_cat_class( CvDTreeNode* node, int vi, float init_quality, CvDTreeSplit* _split,
uchar* _ext_buf )
{
int ci = data->get_var_type(vi); //得到该节点的特征属性的形式
int n = node->sample_count; //得到该节点的样本数量
int cm = data->get_num_classes(); //得到样本数据的分类数
int vm = data->cat_count->data.i[ci]; //得到该特征属性vi的类别数量
double best_val = init_quality;
CvDTreeSplit *split = 0;
if ( vm > 1 ) //如果该特征属性vi的类别大于1个
{
//开辟内存空间
cv::AutoBuffer
if( !_ext_buf )
inn_buf.allocate(2*n);
int* ext_buf = _ext_buf ? (int*)_ext_buf : (int*)inn_buf;
//labels指向该特征属性中各个样本所对应的种类，get_cat_var_data函数在ER算法中被重新定义
const int* labels = data->get_cat_var_data( node, vi, ext_buf );
//responses指向该节点样本的分类，即响应值
const int* responses = data->get_class_labels( node, ext_buf + n );
//得到分类的先验概率
const double* priors = data->have_priors ? data->priors_mult->data.db : 0;
// create random class mask
cv::AutoBuffer
for (int i = 0; i < vm; i++)
{
valid_cidx[i] = -1; //初始化数组valid_cidx
}
for (int si = 0; si < n; si++) //遍历所有样本
{
int c = labels[si]; //当前样本在vi中的分类类别
//分类不符合条件，则遍历下一个样本
if ( ((c == 65535) && data->is_buf_16u) || ((c<0) && (!data->is_buf_16u)) )
continue;
valid_cidx[c]++; //分类计数
}
int valid_ccount = 0; //表示有效分类类别的数量
for (int i = 0; i < vm; i++) //遍历所有分类
if (valid_cidx[i] >= 0) //如果当前分类有样本
{
// valid_cidx表示有效分类的索引
valid_cidx[i] = valid_ccount;
valid_ccount++;
}
if (valid_ccount > 1) //表示该节点可以被分叉
{
CvRNG* rng = forest->get_rng(); //表示随机数
//得到一个小于valid_ccount的任意整数
int l_cval_count = 1 + cvRandInt(rng) % (valid_ccount-1);
//表示有效分类的掩码矢量，每个元素对应一个分类，其中前l_cval_count个元素被置1，后面的元素为0。置换后为1的样本将被分配到左分支，为0的样本将被分配到右分支
CvMat* var_class_mask = cvCreateMat( 1, valid_ccount, CV_8UC1 );
CvMat submask; //表示前l_cval_count个元素的掩码子集
//矩阵var_class_mask清零
memset(var_class_mask->data.ptr, 0, valid_ccount*CV_ELEM_SIZE(var_class_mask->type));
//submask指向var_class_mask的列
cvGetCols( var_class_mask, &submask, 0, l_cval_count );
cvSet( &submask, cvScalar(1) ); //置1
//遍历所有有效分类，每次置换任意两个元素，从而实现了打乱分类的目的
for (int i = 0; i < valid_ccount; i++)
{
uchar temp;
int i1 = cvRandInt( rng ) % valid_ccount;
int i2 = cvRandInt( rng ) % valid_ccount;
CV_SW AP( var_class_mask->data.ptr[i1], var_class_mask->data.ptr[i2], temp );
}
split = _split ? _split : data->new_split_cat( 0, -1.0f );
split->var_idx = vi; //得到该特征属性
memset( split->subset, 0, (data->max_c_count + 31)/32 * sizeof(int)); //清零
// calculate Gini index
//计算基尼指数
double lbest_val = 0, rbest_val = 0;
if( !priors ) //没有先验概率
{
cv::AutoBuffer
int *lc = lrc, *rc = lc + cm; //分别表示左、右分支
int L = 0, R = 0; //分别表示左、右分支样本数
// init arrays of class instance counters on both sides of the split
for(int i = 0; i < cm; i++ ) //数组lc和rc清零
{
lc[i] = 0;
rc[i] = 0;
}
for( int si = 0; si < n; si++ ) //遍历所有样本
{
int r = responses[si]; //该样本的响应值
int var_class_idx = labels[si]; //该样本的特征属性vi的类别索引
//如果var_class_idx不符合条件，则遍历下一个样本
if ( ((var_class_idx == 65535) && data->is_buf_16u) || ((var_class_idx<0) && (!data->is_buf_16u)) )
continue;
//表示类别对应于有效分类类别的索引
int mask_class_idx = valid_cidx[var_class_idx];
if (var_class_mask->data.ptr[mask_class_idx])
// submask子集内的元素，是为1
{
lc[r]++; //左分支
L++;
//左分支相应的位被置1
split->subset[var_class_idx >> 5] |= 1 << (var_class_idx & 31);
}
else // submask子集以外的元素，是为0
{
rc[r]++; //右分支
R++;
}
}
//计算基尼指数
for (int i = 0; i < cm; i++)
{
lbest_val += lc[i]*lc[i];
rbest_val += rc[i]*rc[i];
}
best_val = (lbest_val*R + rbest_val*L) / ((double)(L*R)); //基尼指数}
else //有先验概率
{
cv::AutoBuffer
int *lc = lrc, *rc = lc + cm;
double L = 0, R = 0;
// init arrays of class instance counters on both sides of the split
for(int i = 0; i < cm; i++ )
{
lc[i] = 0;
rc[i] = 0;
}
for( int si = 0; si < n; si++ )
{
int r = responses[si];
int var_class_idx = labels[si];
if ( ((var_class_idx == 65535) && data->is_buf_16u) || ((var_class_idx<0) && (!data->is_buf_16u)) )
continue;
double p = priors[si]; //得到先验概率
int mask_class_idx = valid_cidx[var_class_idx];
if (var_class_mask->data.ptr[mask_class_idx]) //左分支
{
lc[r]+=(int)p;
L+=p;
split->subset[var_class_idx >> 5] |= 1 << (var_class_idx & 31);
}
else //右分支
{
rc[r]+=(int)p;
R+=p;
}
}
for (int i = 0; i < cm; i++)
{
lbest_val += lc[i]*lc[i];
rbest_val += rc[i]*rc[i];
}
best_val = (lbest_val*R + rbest_val*L) / (L*R);
}
split->quality = (float)best_val; //基尼指数
cvReleaseMat(&var_class_mask); //释放变量
}
}
return split; //返回值
}
特征为数值的回归树的分叉方法：
[cpp] view plain copy 在CODE上查看代码片派生到我的代码片
CvDTreeSplit* CvForestERTree::find_split_ord_reg( CvDTreeNode* node, int vi, float init_quality, CvDTreeSplit* _split,
uchar* _ext_buf )
{
const float epsilon = FLT_EPSILON*2; //定义一个很小的常数
const float split_delta = (1 + FLT_EPSILON) * FLT_EPSILON; //定义另一个常数
int n = node->sample_count; //该节点的样本数量
cv::AutoBuffer
if( !_ext_buf )
inn_buf.allocate(n*(2*sizeof(int) + 2*sizeof(float)));
uchar* ext_buf = _ext_buf ? _ext_buf : (uchar*)inn_buf;
float* values_buf = (float*)ext_buf; //用于存储各个样本在特征属性vi的值
int* missing_buf = (int*)(values_buf + n); //表示各个样本是否缺失当前特征属性
const float* values = 0; //指向数组values_buf
const int* missing = 0; //指向数组missing_buf
//得到数组values_buf和missing_buf
data->get_ord_var_data( node, vi, values_buf, missing_buf, &values, &missing, 0 );
float* responses_buf = (float*)(missing_buf + n);
int* sample_indices_buf = (int*)(responses_buf + n);
//responses指向该节点样本的响应值
const float* responses = data->get_ord_responses( node, responses_buf, sample_indices_buf );
double best_val = init_quality, split_val = 0, lsum = 0, rsum = 0;
int L = 0, R = 0;
bool is_find_split = false; //表示是否找到了分叉属性
float pmin, pmax; //分别表示样本的特征属性vi的最小值和最大值
int smpi = 0; //表示缺失特征属性的样本索引值
while ( missing[smpi] && (smpi < n) ) //得到第一个不缺失vi特征属性的样本smpi++;
assert(smpi < n); //确保smpi的正确
//初始化pmin和pmax
pmin = values[smpi];
pmax = pmin;
for (; smpi < n; smpi++) //遍历样本，得到pmin和pmax
{
float ptemp = values[smpi]; //得到当前样本的vi的值
int m = missing[smpi]; //当前样本是否缺失该vi值
if (m) continue; //缺失则遍历下一个样本
if ( ptemp < pmin) //更新pmin值
pmin = ptemp;
if ( ptemp > pmax) //更新pmax值
pmax = ptemp;
}
float fdiff = pmax-pmin; //pmax与pmin的差值
//差值大于一个常数，表示前面计算的结果是有意义的，也就是得到了分叉属性
if (fdiff > epsilon)
{
is_find_split = true; //表示找到了分叉属性
cv::RNG* rng = data->rng; //表示随机数
//随机数为0和1之间的任意数，split_val为pmax与pmin之间任意一个数
split_val = pmin + rng->https://www.doczj.com/doc/da15294890.html,niform(0.f, 1.f) * fdiff ;
//如果split_val太接近pmax或pmin，则split_val为一个定值
if (split_val - pmin <= FLT_EPSILON)
split_val = pmin + split_delta;
if (pmax - split_val <= FLT_EPSILON)
split_val = pmax - split_delta;
for (int si = 0; si < n; si++) //遍历所有样本，计算均方误差
{
float r = responses[si]; //当前样本的响应值
float val = values[si]; //当前样本的特征属性vi的值
int m = missing[si]; //当前样本是否缺失该vi值
if (m) continue; //缺失则遍历下一个样本
if (val < split_val) //左分支
{
lsum += r;
L++;
}
else //右分支
{
rsum += r;
R++;
}
}
best_val = (lsum*lsum*R + rsum*rsum*L)/((double)L*R); //得到均方误差
}
CvDTreeSplit* split = 0;
if( is_find_split ) //表明得到了分叉属性
{
split = _split ? _split : data->new_split_ord( 0, 0.0f, 0, 0, 0.0f ); //实例化split变量split->var_idx = vi; //特征属性
split->ord.c = (float)split_val; //特征属性的值
split->ord.split_point = -1;
split->inversed = 0;
split->quality = (float)best_val; //适合回归树的均方误差值
}
return split; //返回
}
特征为类的回归树的分叉方法：
[cpp] view plain copy 在CODE上查看代码片派生到我的代码片
CvDTreeSplit* CvForestERTree::find_split_cat_reg( CvDTreeNode* node, int vi, float init_quality, CvDTreeSplit* _split,
uchar* _ext_buf )
{
int ci = data->get_var_type(vi); //得到该节点的特征属性的形式
int n = node->sample_count; //得到该节点的样本数量
int vm = data->cat_count->data.i[ci]; //得到该特征属性vi的类别数量
double best_val = init_quality;
CvDTreeSplit *split = 0;
float lsum = 0, rsum = 0;
if ( vm > 1 ) //如果该特征属性vi的类别大于1个
{
int base_size = vm*sizeof(int); //开辟内存空间
cv::AutoBuffer
if( !_ext_buf )
inn_buf.allocate(base_size + n*(2*sizeof(int) + sizeof(float)));
uchar* base_buf = (uchar*)inn_buf;
uchar* ext_buf = _ext_buf ? _ext_buf : base_buf + base_size;
int* labels_buf = (int*)ext_buf;
//labels指向该特征属性中各个样本所对应的种类，get_cat_var_data函数在ER算法中被重新定义
const int* labels = data->get_cat_var_data( node, vi, labels_buf );
float* responses_buf = (float*)(labels_buf + n);
int* sample_indices_buf = (int*)(responses_buf + n);
//responses指向该节点样本的分类，即响应值
const float* responses = data->get_ord_responses( node, responses_buf, sample_indices_buf );
// create random class mask
int *valid_cidx = (int*)base_buf; //表示该特征属性vi的有效类别的索引
for (int i = 0; i < vm; i++)
{
valid_cidx[i] = -1; //初始化数组valid_cidx
}
for (int si = 0; si < n; si++) //遍历所有样本
{
int c = labels[si]; //当前样本在vi中的分类类别
//分类不符合条件，则遍历下一个样本
if ( ((c == 65535) && data->is_buf_16u) || ((c<0) && (!data->is_buf_16u)) )
continue;
valid_cidx[c]++; //分类计数
}
int valid_ccount = 0; //表示有效分类类别的数量
for (int i = 0; i < vm; i++) //遍历所有分类
if (valid_cidx[i] >= 0) //如果当前分类有样本
{
// valid_cidx表示有效分类的索引
valid_cidx[i] = valid_ccount;
valid_ccount++;
}
if (valid_ccount > 1) //表示该节点可以被分叉
{
CvRNG* rng = forest->get_rng(); //表示随机数
//得到一个小于valid_ccount的任意整数
int l_cval_count = 1 + cvRandInt(rng) % (valid_ccount-1);
//表示有效分类的掩码矢量，每个元素对应一个分类，其中前l_cval_count个元素被置1，后面的元素为0。置换后为1的样本将被分配到左分支，为0的样本将被分配到右分支
CvMat* var_class_mask = cvCreateMat( 1, valid_ccount, CV_8UC1 );
CvMat submask; //表示前l_cval_count个元素的掩码子集
//矩阵var_class_mask清零
memset(var_class_mask->data.ptr, 0, valid_ccount*CV_ELEM_SIZE(var_class_mask->type));
//submask指向var_class_mask的列
cvGetCols( var_class_mask, &submask, 0, l_cval_count );
cvSet( &submask, cvScalar(1) ); //置1
//遍历所有有效分类，每次置换任意两个元素，从而实现了打乱分类的目的
for (int i = 0; i < valid_ccount; i++)
{
uchar temp;
int i1 = cvRandInt( rng ) % valid_ccount;
int i2 = cvRandInt( rng ) % valid_ccount;
CV_SW AP( var_class_mask->data.ptr[i1], var_class_mask->data.ptr[i2], temp );
}
split = _split ? _split : data->new_split_cat( 0, -1.0f);
split->var_idx = vi; //得到该特征属性
memset( split->subset, 0, (data->max_c_count + 31)/32 * sizeof(int)); //清零
int L = 0, R = 0;
for( int si = 0; si < n; si++ ) //遍历所有样本
{
float r = responses[si]; //当前样本的响应值
int var_class_idx = labels[si]; //当前样本在特征属性vi中的类别
//如果var_class_idx不符合条件，则遍历下一个样本
if ( ((var_class_idx == 65535) && data->is_buf_16u) || ((var_class_idx<0) && (!data->is_buf_16u)) )
continue;
//表示类别对应于有效分类类别的索引
int mask_class_idx = valid_cidx[var_class_idx];
if (var_class_mask->data.ptr[mask_class_idx])
// submask子集内的元素，是为1
{
lsum += r;
L++;
//左分支相应的位被置1
split->subset[var_class_idx >> 5] |= 1 << (var_class_idx & 31);
}
else // submask子集以外的元素，是为0
{
rsum += r;
R++;
}
}
best_val = (lsum*lsum*R + rsum*rsum*L)/((double)L*R); //计算均方误差
split->quality = (float)best_val; //适合回归树的均方误差值
cvReleaseMat(&var_class_mask); //释放内存
}
}
return split; //返回
}
把节点分叉，并完成相关的运算：
[cpp] view plain copy 在CODE上查看代码片派生到我的代码片
void CvForestERTree::split_node_data( CvDTreeNode* node )
{
//n为该节点的样本数，scount为训练的所有样本数，nl和nr分别表示左分支和右分支的样本数
int vi, i, n = node->sample_count, nl, nr, scount = data->sample_count;
//样本的方向信息，即属于哪个分支，-1为左分支，1为右分支，0为缺失
char* dir = (char*)data->direction->data.ptr;
CvDTreeNode *left = 0, *right = 0;
int new_buf_idx = data->get_child_buf_idx( node );
CvMat* buf = data->buf;
size_t length_buf_row = data->get_length_subbuf();
cv::AutoBuffer
//用替代分叉属性完成对该节点的分叉，即把该节点分叉为左分支或右分支
complete_node_dir(node);
//遍历该节点的所有样本
for( i = nl = nr = 0; i < n; i++ )
{
//得到该样本的方向信息，这里的方向信息是左分支为0，右分支为1
int d = dir[i];
nr += d; //累加d，含义是计算右分支的样本数
nl += d^1; //d与1异或，并累加，含义是计算左分支的样本数}
bool split_input_data; //分叉以后的标识
//定义左右分支的节点变量
node->left = left = data->new_node( node, nl, new_buf_idx, node->offset );
node->right = right = data->new_node( node, nr, new_buf_idx, node->offset + nl );
//判断目前决策树的深度和左右分支的样本数，如果满足要求，则该标识为1，否则为0
split_input_data = node->depth + 1 < data->params.max_depth &&
(node->left->sample_count > data->params.min_sample_count ||
node->right->sample_count > data->params.min_sample_count);
cv::AutoBuffer
// split ordered vars
//遍历样本的所有形式是数值的特征属性，对特征属性是数值形式的进行分叉
for( vi = 0; vi < data->var_count; vi++ )
{
int ci = data->get_var_type(vi);
//如果是类形式的特征属性，则继续下一个特征属性的循环
if (ci >= 0) continue;
//n1表示该节点在特征属性vi下的样本数量
int n1 = node->get_num_valid(vi), nr1 = 0;
float* values_buf = (float*)(uchar*)inn_buf; //用于存储各个样本当前特征属性的值
int* missing_buf = (int*)(values_buf + n); //表示各个样本是否缺失当前特征属性
const float* values = 0; //指向数组values_buf
const int* missing = 0; //指向数组missing_buf
// get_ord_var_data函数在ER算法中被重新定义，各个样本的vi特征属性的值存
储在values_buf数组内，各个样本是否缺失该特征属性用missing_buf数组表示data->get_ord_var_data( node, vi, values_buf, missing_buf, &values, &missing, 0 );
//遍历该节点的所有样本，得到右分支中特征属性是数值形式的样本数量
for( i = 0; i < n; i++ )
nr1 += ((!missing[i]) & dir[i]);
//设置该特征属性vi下的左右分支的样本数
left->set_num_valid(vi, n1 - nr1);
right->set_num_valid(vi, nr1);
}
// split categorical vars, responses and cv_labels using new_idx relocation table
//遍历样本的所有形式是类的特征属性，对特征属性是类形式的进行分叉
for( vi = 0; vi < data->get_work_var_count() + data->ord_var_count; vi++ )
{
int ci = data->get_var_type(vi);
//如果是数值形式的特征属性，则继续下一个特征属性的循环
if (ci < 0) continue;
int n1 = node->get_num_valid(vi), nr1 = 0;
// src_lbls指向该特征属性中各个样本所对应的种类，get_cat_var_data函数在ER 算法中被重新定义
const int* src_lbls = data->get_cat_var_data(node, vi, (int*)(uchar*)inn_buf);
for(i = 0; i < n; i++)
temp_buf[i] = src_lbls[i]; //赋值
if (data->is_buf_16u)
{
unsigned short *ldst = (unsigned short *)(buf->data.s + left->buf_idx*length_buf_row +
ci*scount + left->offset);
unsigned short *rdst = (unsigned short *)(buf->data.s + right->buf_idx*length_buf_row +
ci*scount + right->offset);
for( i = 0; i < n; i++ ) //遍历所有样本
{
int d = dir[i]; //得到方向信息
int idx = temp_buf[i]; //得到该样本的特征属性的种类
if (d) //右分支
{
*rdst = (unsigned short)idx;
rdst++; //指向下一个地址
nr1 += (idx != 65535); //右分支计数
}
目录 第1章需求分析 (1) 第2章概要设计 (1) 系统的主要功能 (1) 系统模块功能结构 (1) 运行环境要求 (2) 数据结构设计 (2) 第3章详细设计 (3) 模块设计 (3) 算法流程图 (3) 第4章系统源代码 (4) 第5章系统测试及调试 (4) 运行结果及分析 (4) 系统测试结论 (5) 第6章总结与体会 (6) 第7章参考文献 (6) 附录 (7)
第1章需求分析 通过模拟文件系统的实现，深入理解操作系统中文件系统的理论知识, 加深对教材中的重要算法的理解。同时通过编程实现这些算法,更好地掌握操作系统的原理及实现方法,提高综合运用各专业课知识的能力；掌握操作系统结构、实现机理和各种典型算法，系统地了解操作系统的设计和实现思路，并了解操作系统的发展动向和趋势。 模拟二级文件管理系统的课程设计目的是通过研究Linux的文件系统结构，模拟设计一个简单的二级文件系统，第一级为主目录文件，第二级为用户文件。 第2章概要设计 系统的主要功能 1) 系统运行时根据输入的用户数目创建主目录 2) 能够实现下列命令： Login 用户登录 Create 建立文件 Read 读取文件 Write 写入文件 Delete 删除文件 Mkdir 建立目录 Cd 切换目录 Logout 退出登录 系统模块功能结构
运行环境要求 操作系统windows xp ，开发工具vc++ 数据结构设计 用户结构：账号与密码结构 typedef struct users { char name[8]; char pwd[10]; }users; 本系统有8个默认的用户名,前面是用户名,后面为密码,用户登陆时只要输入正确便可进入系统,否则提示失败要求重新输入。 users usrarray[8] = { "usr1","usr1", "usr2","usr2", "usr3","usr3", "usr4","usr4",
Ext2数据块分配 跟索引节点一样，Ext2也对磁盘数据块进行分配与释放。在详细分析相关代码之前，先引出两个重要的预备，一个是数据块寻址，一个是文件的洞 1 数据块寻址 每个非空的普通文件都由一组数据块组成。这些块或者由文件内的相对位置（它们的文件块号）来标识，或者由磁盘分区内的位置（它们的逻辑块号）来标识。 从文件内的偏移量f 导出相应数据块的逻辑块号需要两个 步骤： 1. 从偏移量f导出文件的块号，即在偏移量f处的字符所在的块索引。 2. 把文件的块号转化为相应的逻辑块号。 因为Unix文件不包含任何控制字符，因此，导出文件的第f 个字符所在的文件块号当容易的，只是用f除以文件系统块
的大小，并取整即可。 例如，让我们假定块的大小为4KB。如果f小于4096，那么这个字符就在文件的第一数据块中，其文件的块号为O。如果f等于或大于4096而小于8192，则这个字符就在文件块号为1的数据块中，以此类推。 得到了文件的块号是第一步。但是，由于Ext2文件的数据块在磁盘上不必是相邻的，因此把文件的块号转化为相应的逻辑块号可不是这么直截了当的了。 因此，Ext2文件系统必须提供一种方法，用这种方法可以在磁盘上建立每个文件块号与相应逻辑块号之间的关系。在索引节点内部部分实现了这种映射（回到了 AT&T Unix的早期版本）。这种映射也涉及一些包含额外指针的专用块，这些块用来处理大型文件的索引节点的扩展。 ext2磁盘索引节点ext2_inode的i_block字段是一个有EXT2_N_BLOCKS个元素且包含逻辑块号的数组。在下面的讨论中， 我们假定EXT2_N_BLOCKS的默认值为15（实际上到2.6.18这个值都一直是15）。如图所示，这个数组表示一个大型数据结构的初始化部分。
研究 Xmodem 协议必看的 11个问题 Xmodem 协议作为串口数据传输主要的方式之一,恐怕只有做过 bootloader 的才有机会接触一下, 网上有关该协议的内容要么是英语要么讲解不详细。笔者以前写 bootloader 时研究过 1k-Xmodem ,参考了不少相关资料。这里和大家交流一下我对 Xmodem 的理解,多多指教! 1. Xmodem 协议是什么? XMODEM协议是一种串口通信中广泛用到的异步文件传输协议。分为标准Xmodem 和 1k-Xmodem 两种,前者以 128字节块的形式传输数据,后者字节块为 1k 即 1024字节,并且每个块都使用一个校验和过程来进行错误检测。在校验过程中如果接收方关于一个块的校验和与它在发送方的校验和相同时,接收方就向发送方发送一个确认字节 (ACK。由于 Xmodem 需要对每个块都进行认可, 这将导致性能有所下降, 特别是延时比较长的场合, 这种协议显得效率更低。 除了 Xmodem ,还有 Ymodem , Zmodem 协议。他们的协议内容和 Xmodem 类似,不同的是 Ymodem 允许批处理文件传输,效率更高; Zmodem 则是改进的了Xmodem ,它只需要对损坏的块进行重发,其它正确的块不需要发送确认字节。减少了通信量。 2. Xmodem 协议相关控制字符 SOH 0x01 STX 0x02 EOT 0x04 ACK 0x06 NAK 0x15
CAN 0x18 CTRLZ 0x1A 3.标准 Xmodem 协议(每个数据包含有 128字节数据帧格式 _______________________________________________________________ | SOH | 信息包序号 | 信息包序号的补码 | 数据区段 | 校验和 | |_____|____________|___________________|__________|____________| 4. 1k-Xmodem (每个数据包含有 1024字节数据帧格式 _______________________________________________________________ | STX | 信息包序号 | 信息包序号的补码 | 数据区段 | 校验和 | |_____|____________|___________________|__________|____________| 5.数据包说明 对于标准 Xmodem 协议来说,如果传送的文件不是 128的整数倍,那么最后一个数据包的有效内容肯定小于帧长,不足的部分需要用 CTRL- Z(0x1A来填充。这里可能有人会问,如果我传送的是 bootloader 工程生成的 .bin 文件, mcu 收到后遇到0x1A 字符会怎么处理?其实如果传送的是文本文件,那么接收方对于接收的内容是很容易识别的,因为 CTRL-Z 不是前 128个 ascii 码, 不是通用可见字符, 如果是二进制文件, mcu 其实也不会把它当作代码来执行。哪怕是 excel 文件等,由于其内部会有些结构表示各个字段长度等,所以不会读取多余的填充字符。否则 Xmodem太弱了。对于 1k-Xmodem ,同上理。 6.如何启动传输?
Linux 0.11文件系统的源码阅读总结 1.minix文件系统 对于linux 0.11内核的文件系统的开发，Linus主要参考了Andrew S.Tanenbaum 所写的《MINIX操作系统设计与实现》，使用的是其中的1.0版本的MINIX文件系统。而高速缓冲区的工作原理参见M.J.Bach的《UNIX操作系统设计》第三章内容。 通过对源代码的分析，我们可以将minix文件系统分为四个部分，如下如1-1。 ●高速缓冲区的管理程序。主要实现了对硬盘等块设备进行数据高速存取的函数。 ●文件系统的底层通用函数。包括文件索引节点的管理、磁盘数据块的分配和释放 以及文件名与i节点的转换算法。 ●有关对文件中的数据进行读写操作的函数。包括字符设备、块设备、管道、常规 文件的读写操作，由read_write.c函数进行总调度。 ●涉及到文件的系统调用接口的实现，这里主要涉及文件的打开、关闭、创建以及 文件目录等系统调用，分布在namei和inode等文件中。 图1-1 文件系统四部分之间关系图
1.1超级块 首先我们了解一下MINIX文件系统的组成，主要包括六部分。对于一个360K软盘，其各部分的分布如下图1-2所示： 图 1-2 建有MINIX文件系统的一个360K软盘中文件系统各部分的布局示意图 注释1：硬盘的一个扇区是512B，而文件系统的数据块正好是两个扇区。 注释2：引导块是计算机自动加电启动时可由ROM BIOS自动读入得执行代码和数据。 注释3：逻辑块一般是数据块的2幂次方倍数。MINIX文件系统的逻辑块和数据块同等大小 对于硬盘块设备，通常会划分几个分区，每个分区所存放的不同的文件系统。硬盘的第一个扇区是主引导扇区，其中存放着硬盘引导程序和分区表信息。分区表中得信息指明了硬盘上每个分区的类型、在硬盘中其实位置参数和结束位置参数以及占用的扇区总数。其结构如下图1-3所示。 图1-3 硬盘设备上的分区和文件系统 对于可以建立不同的多个文件系统的硬盘设备来说，minix文件系统引入超级块进行管理硬盘的文件系统结构信息。其结构如下图1-4所示。其中，s_ninodes表示设备上得i节点总数，s_nzones表示设备上的逻辑块为单位的总逻辑块数。s_imap_blocks 和s_zmap_blocks分别表示i节点位图和逻辑块位图所占用的磁盘块数。 s_firstdatazone表示设备上数据区开始处占用的第一个逻辑块块号。s_log_zone_size 是使用2为底的对数表示的每个逻辑块包含的磁盘块数。对于MINIX1.0文件系统该值为0，因此其逻辑块的大小就等于磁盘块大小。s_magic是文件系统魔幻数，用以指明文件系统的类型。对于MINIX1.0文件系统，它的魔幻数是0x137f。
认识文件系统 物联网学院平震宇
文件系统 文件系统是一套实现了数据的存储、分级组织、访问和获取等操作的抽象数据类型，一种存储和组织计算机文件和数据的方法，它使得对其访问和查找变得容易。 Linux 最早的文件系统是Minix，但是专门为Linux 设计的文件系统——扩展文件系统第二版 (EXT2)被设计出来并添加到Linux中，这对Linux产生了重大影响。EXT2文件系统功能强大、易扩充、性能上进行了全面优化，也是所有Linux发布和安装的标准文件系统类型。
虚拟文件系统 Linux支持ext，ext2，xia，minix，umsdos，msdes，fat32 ，ntfs,proc，stub，ncp，hpfs，affs 以及 ufs 等多种文件系统。 Linux 对所有的文件系统采用统一的文件界面，用户通过文件的操作界面来实现对不同文件系统的操作。对于用户来说，我们不要去关心不同文件系统的具体操作过程，而只是对一个虚拟的文件操作界面来进行操作，这个操作界面就是 Linux 的虚拟文件系统(VFS ) 。 VFS 作为 Linux内核中的一个软件层，用于给用户空间的程序提供文件系统接口，同时也提供了内核中的一个抽象功能，允许不同的文件系统很好地共存。VFS 使 Linux 同时安装、支持许多不同类型的文件系统成为可能。VFS 拥有关于各种特殊文件系统的公共界面，如超级块、inode、文件操作函数入口等。实际文件系统的细节，统一由 VFS 的公共界面来索引，它们对系统核心和用户进程来说是透明的。
Linux上有许多可用的文件系统。每个文件系统都有其特定的用途，以便于特定用户解决不同的问题。 ?要求文件系统在频繁的文件操作（例如，新建，删 除，截断）下能够保持较高的读写性能，要求低碎 片化。 ?Linux下的日志文件系统能保持数据的完整性，但消 耗过多系统资源,的弱点使之不能成为嵌入式系统中 的主流应用。并且这些都是专门为硬盘这类的存储 设备优化，对于flash这类的存储介质并不适用。
---《计算机网络与控制》论文 LWIP协议栈的分析
摘要 近些年来，随着互联网和通讯技术的迅猛发展，除了计算机之外，大量的嵌入式设备也需求接入网络。目前，互联网中使用的通讯协议基本是TCP/IP协议族，可运行于不同的网络上，本文研究的就是嵌入式TCP/IP协议栈LWIP。文章首先分析了LWIP的整体结构和协议栈的实现，再介绍协议栈的内存管理，最后讲解协议栈应用程序接口。 关键词: 嵌入式系统;协议；LWIP；以太网 Abstract With the rapid development of internet and communication technology, Not only computers but also embeded equipments are need to connect networks. At present, the basic communication protocol using in internet is TCP/IP, it can run in different network. This paper analyses the Light-Weight TCP/IP. The process model of a protocol implementation and processing of every layer are described first, and then gives the detailed management of Buffer and memory. At last, a reference lwIP API is given. Key words: Embedded System, Protocol, Light weight TCP/IP,Ethernet 引言
EXT3文件系统 EXT2和EXT3是许多Linux操作系统发行版本的默认文件系统。EXT基于UFS，是一种快速、稳定的文件系统。 随着Linux系统在关键业务中的应用，Linux文件系统的弱点也渐渐显露出来了；其中EXT2文件系统是非日志式文件系统，这在关键行业的应用是一个致命的弱点，EXT3文件系统弥补了这一缺点。 EXT3文件系统是直接从EXT2文件系统发展而来，目前EXT3文件系统已经非常稳定可靠。它完全兼容EXT2文件系统。用户可以平滑地过渡到一个日志功能健全的文件系统中来。这实际上了也是EXT3日志文件系统初始设计的初衷。 Ext3文件系统属于一种日志文件系统，是对Ext2系统的扩展。Ext3系统兼容Ext2文件系统，二者之间的相互转换并不复杂。 Ext2是 GNU/Linux 系统中标准的文件系统，其簇快取层的优良设计使得Ext2系统存取文件的性能非常好，尤其是针对中小型的文件更显优势。 Ext3是一种日志式文件系统，日志文件系统比传统的文件系统安全，因为它用独立的日志文件跟踪磁盘内容的变化。就像关系型数据库（RDBMS），日志文件系统可以用事务处理的方式，提交或撤消文件系统的变化。由于文件系统都有快取层参与运作，不使用时必须将文件系统卸下，以便将快取层的资料写回磁盘中。因此每当系统要关机时，必须将其所有的文件系统全部关闭后才能进行关机。 如果在文件系统尚未关闭前就关机 (如停电) 时，下次重开机后会造成文件系统的资料不一致，故（所以）这时必须做文件系统的重整工作，将不一致与错误的地方修复。然而这一重整的工作是相当耗时的，特别是容量大的文件系统，而且也不能百分之百保证所有的资料都不会流失。 为了克服此问题，使用（便出现了）所谓的日志式文件系统 (Journal File System) 。此类文件系统最大的特色是，它会将整个磁盘的写入动作完整记录在磁盘的某个区域上，以便有需要时可以回溯追踪。 由于资料的写入动作包含许多的细节，如改变文件标头资料、搜寻磁盘可写入空间、一个个写入资料区段等等，每一个细节进行到一半若被中断，就会造成文件系统的不一致，因而需要重整。 然而在日志式文件系统中，由于详细纪录了每个细节，故当在某个过程中被中断时，系统可以根据这些记录直接回溯并重整被中断的部分，而不必花时间去检查其他的部分，故重整的工作速度相当快，几乎不需要花时间。 EXT3日志文件系统的特点 1、高可用性 系统使用了EXT3文件系统后，即使在非正常关机后，系统也不需要检查文件系统。宕机发生后，恢复EXT3文件系统的时间只要数十秒钟。 2、数据的完整性: EXT3文件系统能够极大地提高文件系统的完整性，避免了意外宕机对文件系统的破
、概述 1、目的 在移植之前，先将源代码大概的阅读一遍，主要是了解文件系统的结构、 各个函数的功能和接口、与移植相关的代码等等。 2、准备工作 在官方网站下载了0.07c 版本的源代码，利用记事本进行阅读。 二、源代码的结构 1、源代码组成 源代码压缩包解压后，共两个文件夹，doc是说明，src里就是代码。src文件夹里共五个文件和一个文件夹。文件夹是option，还有OOreadme.txt、 diskio.c、diskio.h、ff.c、ff.h、integer.h。对比网上的文章，版本已经不同了，已经没有所谓的tff.c 和tff.h 了，估计现在都采用条件编译解决这个问题了，当然文件更少，可能编译选项可能越复杂。 2、00readme.txt 的说明 Low level disk I/O module is not included in this archive because the FatFs module is only a generic file system layer and not depend on any specific storage device. You have to provide a low level disk I/O module that written to control your storage device .主要是说不包含底层10代码，这是个通用文 件系统可以在各种介质上使用。我们移植时针对具体存储设备提供底层代码。 接下来做了版权声明-可以自由使用和传播。 然后对版本的变迁做了说明。 3、源代码阅读次序
先读integer.h,了解所用的数据类型，然后是ff.h, 了解文件系统所用的数据结构和各种函数声明，然后是diskio.h，了解与介质相关的数据结构和操作函数。再把ff.c和diskio.c两个文件所实现的函数大致扫描一遍。最后根据用户应用层程序调用函数的次序仔细阅读相关代码。 三、源代码阅读 1、integer.h 头文件 这个文件主要是类型声明。以下是部分代码。 typedef intINT; typedef unsigned int UINT; typedef signed charCHAR;/* These types must be 8-bit integer */ 都是用typedef 做类型定义。移植时可以修改这部分代码,特别是某些定义与你所在工程的类型定义有冲突的时候。 2、ff.h 头文件 以下是部分代码的分析 #include “ intege使用i n teger.h 的类型定义 #ifndef _FATFS #define _FATFS 0x007版本号007c, 0.07c #define _WORD_ACCESS 0如//果定义为1,则可以使用word 访问。 中间有一些看着说明很容易弄清楚意思。这里就不例举了。 #define _CODE_PAGE 936 /* The _CODE_PAGE specifies the OEM code page to be used on the target system. /936 -Simplified Chinese GBK (DBCS, OEM, WindoW跟据这个中国应该是936.
Ext2格式分析 1、Ext2磁盘数据结构 任何Ext2分区中的第一个块从不受Ext2文件系统的管理，因为这一块是为分区的引导扇区所保留的。Ext2分区的其余部分被分成块组（block group），每个块组的分布图如图所示。正如你从图中所看到的，一些数据结构正好可以放在一块中，而另一些可能需要更多的块。在Ext2文件系统中的所有块组大小相同并被顺序存放，因此，内核可以从块组的整数索引很容易地得到磁盘中一个块组的位置： 由于内核尽可能地把属于同一个文件的数据块存放在同一块组中，所以块组减少了文件碎片。块组中的每个块包含下列信息之一： 1.文件系统的超级块的一个拷贝 2.一组块组描述符的拷贝 3.一个数据块位图 4.一个索引节点位图 5.一个索引节点表 6.属于文件的一大块数据，即数据块 如果一个块中不包含任何有意义的信息，就说这个块是空闲的。 从上图中可以看出，超级块与组描述符被复制到每个块组中。 其实呢，只有块组0中所包含超级块和组描述符才由内核使用，而其余的超级块和组描述符都保持不变；事实上，内核甚至不考虑它们。当e2fsck程序对Ext2文件系统的状态执行一致性检查时，就引用存放在块组0中的超级块和组描述符，然后把它们拷贝到其他所有的块组中。如果出现数据损坏，并且块组0 中的主超级块和主描述符变为无效，那么，系
统管理员就可以命令e2fsck引用存放在某个块组（除了第一个块组）中的超级块和组描述符的旧拷贝。通常情况下，这些多余的拷贝所存放的信息足以让e2fsck把Ext2分区带回到一个一致的状态。 那么有多少块组呢？这取决于分区的大小和块的大小。其主要限制在于块位图，因为块位图必须存放在一个单独的块中。块位图用来标识一个组中块的占用和空闲状况。所以，每组中至多可以有8×b个块，b是以字节为单位的块大小。例如，一个块是 1024 Byte，那么，一个块的位图就有8192个位，一个块组正好就对应8192个块(位图中的一个bit描述一个块)。 Ext2超块(super Block) Ext2超块中包含了描叙文件系统基本尺寸和形态的信息，是用定义在include／Linux ／ext2_fs．h中ext2_supe_block数据结构描述的。文件系统管理器利用它们来使用和维护文件系统。通常安装文件系统时只读取数据块组0中的超块，但是为防止文件系统被破坏，每个数据块组都包含了它的拷贝。超块中的主要信息如下： Magic Number：文件系统安装软件用来检验是否是一个真正的EXl2文件系统超块。当前Exl2版本中为0xEF53。 Block Size：以字节记数的文件系统块大小，如1024字节。 Blocks per Group：每个组中块数目。当文件系统创建时此块大小被固定下来。 Free Blocks：文件系统中的空闲块数。 Free Inodes：文件系统中空闲Inode数。 First Inode：文件系统中第一个Inode号。EX配根文件系统中第一个Inode将是指向‘／’目录的人口。 ExT2组描述符(Group Descript) 每个数据块组都拥有一个描叙结构的组描叙符，它是定义在include／Linux／ext2一fs．h中的ext2一group—desc结构。组描叙符放置在一起形成了组描叙符表。每个数据块组在超块拷贝后包含整个组描叙符表。象超块一样，所有数据块组中的组描叙符表被复制到每个数据块组中以防文件系统崩溃。EX配文件系统仅使用第一个拷贝(在数据块组0中)。组描叙符主要包含以下信息： Blocks Bitm印：对应此数据块组的块分配位图的块号，在块分配和回收时使用。 Inode Bitmap：对应此数据块组的Inode分配位图的块号，在Inode分配和回收时使用。 Inode Table：对应数据块组的Inode表的起始块号。每个Inode用下面的EX佗Inode 结构来表示。
文件系统结构分析 1嵌入式文件系统 1.1嵌入式文件系统体系结构 在嵌入式系统中，文件系统是嵌入式系统的一个组成模块，它是作为系统的一个 可加载选项提供给用户，由用户决定是否需要加载它。同时，它还需要满足结构紧 凑、代码量小、支持多种存储设备、可伸缩、可剪裁、可移植等特点。基于上面的要 求，嵌入式文件系统在设计和实现时就要把它作为一个独立的模块来整体考虑。特别 是对文件系统内部资源的管理要做到独立性。 由于嵌入式文件系统是作为嵌入式系统的一个可选加载项提供给用户的，当 用户针对其应用的特殊要求对嵌入式系统进行配置时没有选择加载文件系统，但 是用户还是需要使用到系统I/O。由于这种情况的出现就决定了嵌入式系统中的文件 系统不再具有I/O设备的管理功能。系统I/O的管理和使用接口的提供将由 I/O管理 模块完成，文件系统作为一个独立的自包含模块存在。 基于以上考虑，嵌入式文件系统的体系结构如图1所示。 1卩 硬件 图1嵌入式文件系统体系结构 在嵌入式文件系统的最上层是文件系统 API。文件系统的一切功能都是通过这一层提供给用户的。同时，在整个文件系统中也只有这一层对用户是可见的。 在这一层中所提供的所有功能接口都将严格的遵循 POSIX标准。 文件系统核心层是实现文件系统主要功能的模块。在这一层中，文件系统要把
用户的功能操作转化成对文件系统的抽象对象的操作。这些操作将通过下面的功能模块最终落实到物理介质上面。如果文件系统需要支持多种具体的文件系统格式的话，这一层还可以进一步细分成虚拟文件系统和逻辑文件系统。 块高速缓存的存在是为了提高文件系统的性能。在这一层中缓存着以前访问过的块设备数据。文件系统通过一定的算法来高效的管理这些数据，以提高缓冲的性能。同时，它的存在使下层的数据操作对上层的文件操作透明，提高了文件系统的模块性。 1.2 嵌入式文件系统体系的功能与特点 文件系统是操作系统的重要组成部分，用于控制对存储设备的存取。它提供对文件和目录的分层组织形式、数据缓冲（对于实时系统，允许绕过缓冲）以及对文件存取权限的控制。 嵌入式系统所使用的文件系统除了要提供通用文件系统的功能外，还由于嵌入式操作系统的特殊性而具有其自身的一些特点。嵌入式文件系统的设计应该满足如下目标： 1.实现按名存取。和桌面操作系统类似，用户对文件的操作是通过其“文件名”来完成的。因此，用户只需知道待操作文件的文件名，就可以方便的访问数据，而不必关心文件在物理设备上是如何存放的，以及如何对文件的打开、关闭操作进行处理等细节。所有与文件相关的管理工作都由文件系统组件隐式完成。 2.与实时系统相适应。嵌入式应用大多数都具有实时性需求。实时系统不仅 要求计算结果地准确无误，而且要求特定的指令要在限定的时间内完成，这就对文件系统提出了很高的要求。在通用操作系统中，往往采取分页和虚拟存储器管理的机制来满足规定的指令时间。然而嵌入式实时操作系统一般都不具有虚拟存储器管理机制，且各种外部设备的性能差异较大，控制文件系统的实时性变得非常困难。为了尽可能提高文件系统的实时性，除了选取高速存储介质作为嵌入式系统的外设外，还应该根据设备的特点设置一定大小的高速缓冲，以提高数据存取的相应速度。 3.支持多任务环境。面对日益复杂的计算环境，应用常常采取“分而治之” 的方法，将解决方案划分为多个任务，每个任务完成相对单一的功能。实时操作系统的设计目标之一就是对多任务的支持。从应用的层面上看，多任务可以对文件进行并发读操作，在实时内核进程间同步与通信机制支持下进行写操作。此外，文件系统内部实现也应该具备较好的可重入性，即利用同步机制对全局数据结构 进行必要的保护。 4.支持多种逻辑文件系统标准。随着操作系统技术的发展，出现了多种成熟的桌面文件系统标准，如 Windows下的FAT系列，Linux中的ext系列等。将这些成熟标
竭诚为您提供优质文档/双击可除lwip各层协议栈详解 篇一：lwip协议栈源码分析 lwip源码分析 -----caoxw 1lwip的结构 lwip（lightweightinternetprotocol）的主要模块包括：配置模块、初始化模块、netif模块、mem（memp）模块、netarp模块、ip模块、udp模块、icmp模块、igmp模块、dhcp模块、tcp模块、snmp模块等。下面主要对我们需要关心的协议处理进行说明和梳理。配置模块： 配置模块通过各种宏定义的方式对系统、子模块进行了配置。比如，通过宏，配置了mem管理模块的参数。该配置模块还通过宏，配置了协议栈所支持的协议簇，通过宏定制的方式，决定了支持那些协议。主要的文件是opt.h。 初始化模块： 初始化模块入口的文件为tcpip.c，其初始化入口函数为： voidtcpip_init(void(*initfunc)(void*),void*arg)
该入口通过调用lwip_init()函数，初始化了所有的子模块，并启动了协议栈管理进程。同时，该函数还带有回调钩子及其参数。可以在需要的地方进行调用。 协议栈数据分发管理进程负责了输入报文的处理、超时处理、api函数以及回调的处理，原型如下： staticvoidtcpip_thread(void*arg) netif模块： netif模块为协议栈与底层驱动的接口模块，其将底层的一个网口设备描述成协议栈的一个接口设备（netinterface）。该模块的主要文件为netif.c。其通过链表的方式描述了系统中的所有网口设备。 netif的数据结构描述了网口的参数，包括ip地址、mac 地址、link状态、网口号、收发函数等等参数。一个网口设备的数据收发主要通过该结构进行。 mem（memp）模块： mem模块同一管理了协议栈使用的内容缓冲区，并管理pbuf结构以及报文的字段处理。主要的文件包括mem.c、memp.c、pbuf.c。 netarp模块： netarp模块是处理arp协议的模块，主要源文件为etharp.c。其主要入口函数为： err_tethernet_input(structpbuf*p,structnetif*netif)
ext2文件系统 总体存储布局 我们知道，一个磁盘可以划分成多个分区，每个分区必须先用格式化工具（例如某种mkfs命令）格式化成某种格式的文件系统，然后才能存储文件，格式化的过程会在磁盘上写一些管理存储布局的信息。下图是一个磁盘分区格式化成ext2文件系统后的存储布局。 图 29.2. ext2文件系统的总体存储布局 文件系统中存储的最小单位是块（Block），一个块究竟多大是在格式化时确定的，例如mke2fs 的-b选项可以设定块大小为1024、2048或4096字节。而上图中启动块（Boot Block）的大小是确定的，就是1KB，启动块是由PC标准规定的，用来存储磁盘分区信息和启动信息，任何文件系统都不能使用启动块。启动块之后才是ext2文件系统的开始，ext2文件系统将整个分区划成若干个同样大小的块组（Block Group），每个块组都由以下部分组成。 超级块（Super Block） 描述整个分区的文件系统信息，例如块大小、文件系统版本号、上次mount的时间等等。超级块在每个块组的开头都有一份拷贝。 块组描述符表（GDT，Group Descriptor Table） 由很多块组描述符组成，整个分区分成多少个块组就对应有多少个块组描述符。每个块组描述符（Group Descriptor）存储一个块组的描述信息，例如在这个块组中从哪里开始是inode表，从哪里开始是数据块，空闲的inode和数据块还有多少个等等。和超级块类似，块组描述符表在每个块组的开头也都有一份拷贝，这些信息是非常重要的，一旦超级块意外损坏就会丢失整个分区的数据，一旦块组描述符意外损坏就会丢失整个块组的数据，因此它们都有多份拷贝。通常内核只用到第0个块组中的拷贝，当执行e2fsck检查文件系统一致性时，第0个块组中的超级块和块组描述符表就会拷贝到其它块组，这样当第0个块组的开头意外损坏时就可以用其它拷贝来恢复，从而减少损失。 块位图（Block Bitmap） 一个块组中的块是这样利用的：数据块（Data Block）存储所有文件的数据，比如某个分区的块大小是1024字节，某个文件是2049字节，那么就需要三个数据块来存，即使第三个块只存了一
ext2文件系统下数据进行数据恢复 摘要 ext2文件系统下数据进行数据恢复 --------------------------------------------------------------------- 本系的 BBS 系统真是多灾多难 (嗯 .... 其实是因为我的疏忽，才会这么多灾多难 ....) ，继这几日系统时间不正确，造成许多人的 ID 被误砍后，又一次因系统设定上的问题，将 BBS 的重要备份档给杀了。这件事是学弟发现后告诉我的，当我上站来一见到他的mail, 当真是欲哭无泪，差点没去撞墙。 那时已是周六晚 11:00 左右，我一边想着要编一套说辞向大家解释无法替大家进行数据恢复旧信件与设定了，一边还在想是否能够挽回局面。大家知道， UNIX like 的系统是很难像 M$ 的系统一样，做到 undelete 的，所有网管前辈都曾再三警告我们，要小心! 小心! 砍档之前三思而后行，砍了之后再后悔也没用。虽然我已渐渐做到砍档三思而后行，但之次误砍事件是系统在背景中定时执行的，等到我找出原因时已是数据被砍后一个多小时。我凭着一点点的印象，想起在网络上，有人讨论过在 Linux ext2 filesystem中 undelete 的可能性，但我所见到的多半是负面的答案，但好象真的有人做过这件事，于是我第一个所做的，就是马上将该数据原来所在的 partition mount成 read-only, 禁止任何的写入动作，不是怕再有数据被误砍 (因为已没什么可砍的了) ，而是怕有新数据写进来，新资料可能会覆盖到旧资料原本存在的磁区 (block) 。我们现在唯一个指望，就是企图将数据原来存在的磁区一个个找回来，并且「希望」这些磁区上的旧资料都还在，然后将这些磁区串成一个数据。终于被我找到了!! 原来这方面的技术文件就存在我自己的系统中 :-)) /usr/doc/HOWTO/mini/Ext2fs-Undeletion.gz 于是我就按照这份文件的指示一步步来，总算将一个长达 8MB 的压缩档数据恢复了 99%, 还有一个长达 1.1 MB 的压缩档完整无缺地救了回来。感谢上帝、 Linux 的设计者、写那篇文件的作者、曾经讨论过此技术的人、以及 Linux 如此优秀的 ext2 filesystem, 让我有机会抢救过去。现在，我将我的抢救步骤做一个整理让大家参考，希望有派得上用场的时候 (喔! 不，最好是希望大家永远不要有机会用到以下的步数 :-))) 在此严正声明!! 写这篇文章的目的，是给那些处于万不得已情况下的人们，有一个挽回的机会，并不意味着从此我们就可以大意，砍档不需要三思。前面提到，我有一个数据无法100% 救回，事实上，长达 8MB 的数据能救回 99% 已是幸运中的幸运，一般的情况下若能救回 70% - 80% 已经要愉笑了。所以，不要指望 undelete 能救回一切。预防胜于治疗! 请大
LwIP协议栈源码详解 ——TCP/IP协议的实现 Created by.. 老衲五木 at.. UESTC Contact me.. for_rest@https://www.doczj.com/doc/da15294890.html, 540535649@https://www.doczj.com/doc/da15294890.html,
前言 最近一个项目用到LwIP，恰好看到网上讨论的人比较多，所以有了写这篇学习笔记的冲动，一是为了打发点发呆的时间，二是为了吹过的那些NB。往往决定做一件事是简单的，而坚持做完这件事却是漫长曲折的，但终究还是写完了，时间开销大概为四个月，内存开销无法估计。。 这篇文章覆盖了LwIP协议大部分的内容，但是并不全面。它主要讲解了LwIP协议最重要也是最常被用到的部分，包括内存管理，底层网络接口管理，ARP层，IP层，TCP层，API 层等，这些部分是LwIP的典型应用中经常涉及到的。而LwIP协议的其他部分，包括UDP，DHCP,DNS,IGMP,SNMP,PPP等不具有使用共性的部分，这篇文档暂时未涉及。 原来文章是发在空间中的，每节每节依次更新，后来又改发为博客，再后来就干脆懒得发了。现在终于搞定，于是将所有文章汇总。绞尽脑汁的想写一段空前绝后，人见人爱的序言，但越写越觉得像是猫儿抓的一样。就这样，PS:由于本人文笔有限，情商又低，下里巴人一枚，所以文中的很多语句可能让您很纠结，您可以通过邮箱与我联系。共同探讨才是进步的关键。 最后，欢迎读者以任何方式使用与转载，但请保留作者相关信息，酱紫！码字。。。世界上最痛苦的事情莫过于此。。。 ——老衲五木
目录 1 移植综述------------------------------------------------------------------------------------------------------4 2 动态内存管理------------------------------------------------------------------------------------------------6 3 数据包pbuf--------------------------------------------------------------------------------------------------9 4 pbuf释放---------------------------------------------------------------------------------------------------13 5 网络接口结构-----------------------------------------------------------------------------------------------16 6 以太网数据接收--------------------------------------------------------------------------------------------20 7 ARP表-----------------------------------------------------------------------------------------------------23 8 ARP表查询-----------------------------------------------------------------------------------------------26 9 ARP层流程-----------------------------------------------------------------------------------------------28 10 IP层输入-------------------------------------------------------------------------------------------------31 11 IP分片重装1--------------------------------------------------------------------------------------------34 12 IP分片重装2--------------------------------------------------------------------------------------------37 13 ICMP处理-----------------------------------------------------------------------------------------------40 14 TCP建立与断开----------------------------------------------------------------------------------------43 15 TCP状态转换-------------------------------------------------------------------------------------------46 16 TCP控制块----------------------------------------------------------------------------------------------49 17 TCP建立流程-------------------------------------------------------------------------------------------53 18 TCP状态机----------------------------------------------------------------------------------------------56 19 TCP输入输出函数1-----------------------------------------------------------------------------------60 20 TCP输入输出函数2-----------------------------------------------------------------------------------63 21 TCP滑动窗口-------------------------------------------------------------------------------------------66 22 TCP超时与重传----------------------------------------------------------------------------------------69 23 TCP慢启动与拥塞避免-------------------------------------------------------------------------------73 24 TCP快速恢复重传和Nagle算法-------------------------------------------------------------------76 25 TCP坚持与保活定时器-------------------------------------------------------------------------------80 26 TCP定时器----------------------------------------------------------------------------------------------84 27 TCP终结与小结----------------------------------------------------------------------------------------88 28 API实现及相关数据结构-----------------------------------------------------------------------------91 29 API消息机制--------------------------------------------------------------------------------------------94 30 API函数及编程实例-----------------------------------------------------------------------------------97