glxhyt

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  15 随笔 :: 0 文章 :: 4 评论 :: 0 Trackbacks

2013年5月19日 #

http://www.who1753.com/100-bugs-in-c-cpp-opensource-projects/

俄罗斯OOO Program Verification Systems公司用自己的静态源码分析产品PVS-Studio对一些知名的C/C++开源项目,诸如Apache Http ServerChromiumClangCMakeMySQL等的源码进行了分析,找出了100个典型的Bugs。个人觉得这份列表对C/C++ 程序员有一定参考意义。与其说事后用静态工具分析,倒不如在编码时就提高自知自觉,避免这份列表上的错误发生在你的代码中,因此这里将部分摘录一些Bugs(Bug编号这里不连续,为的是对应原文的编号)并做简要说明。原文将这份Bug列表分为了几类,这里也将沿用这个思路。

一、数组和字符串处理错误

数组和字符串处理错误是C/C++程序中最多的一类缺陷类型。这也可以看作是我们为拥有高效地底层内存操作能力而付出的代价。

[#1] Wolfenstein 3D项目 -"只有部分对象被clear了"

1
2
3
4
5
6
7
8
void CG_RegisterItemVisuals( int itemNum )
{
       
      itemInfo_t *itemInfo;
      
      memset( itemInfo, 0, sizeof( &itemInfo ) ); 
      
}

这里的Bug出现在memset那一行。代码的真实意图是clear iteminfo这块内存,但调用memset时,第三个参数传入的却是sizeof(&iteminfo),要知道 sizeof(&itemInfo) != sizeof(itemInfo_t),前者只是一个指针的大小罢了。正确的写法是:

memset(itemInfo, 0, sizeof(itemInfo_t)); 或memset(itemInfo, 0, sizeof(*itemInfo));

[#2] Wolfenstein 3D项目 -"只有部分Matrix被clear了"

ID_INLINE mat3_t::mat3_t( float src[ 3 ][ 3 ] ) {
memcpy( mat, src, sizeof( src ) );
}

这里的Bug出现在memcpy一行。程序的原意是将clear src[3][3]这个二维数组。但这里有个坑:那就是作为函数形式参数的数组名已经退化为指针了,对其sizeof只能得到一个指针的长度,因此这里的 memcpy只是copy了一个指针的长度,没有copy全。这里的代码是C++代码,原文中给出了正确的改正方法 – 传reference:

ID_INLINE mat3_t::mat3_t( float (&src)[3][3] )
{
memcpy( mat, src, sizeof( src ) );
}

[#4] ReactOS项目 – "错误地计算一个字符串的长度"

static const PCHAR Nv11Board = "NV11 (GeForce2) Board";
static const PCHAR Nv11Chip = "Chip Rev B2";
static const PCHAR Nv11Vendor = "NVidia Corporation";

BOOLEAN
IsVesaBiosOk(…)
{

if (!(strncmp(Vendor, Nv11Vendor, sizeof(Nv11Vendor))) &&
!(strncmp(Product, Nv11Board, sizeof(Nv11Board))) &&
!(strncmp(Revision, Nv11Chip, sizeof(Nv11Chip))) &&
(OemRevision == 0×311))

}

Bug处在IsVesaBiosOK中那一串strncmp调用中,代码将一个指针的size传入strncmp作为第三个参数,导致 strncmp实际只是比较了字符串的前4 or 8个字节,而不是字符串的全部内容。

[#6] CPU Identifying Tool项目 – 数组越界

#define FINDBUFFLEN 64  // Max buffer find/replace size

int WINAPI Sticky (…)
{

static char findWhat[FINDBUFFLEN] = {'\0'};

findWhat[FINDBUFFLEN] = '\0';

}

bug出在"findWhat[FINDBUFFLEN] = ‘\0′;”这一行。数组的最大长度为FINDBUFFLEN,但下标的最大值应该是FINDBUFFLEN-1,而不是FINDBUFFLEN。因此这 行代码显然应该改为findWhat[FINDBUFFLEN-1] = '\0';

[#7] Wolfenstein 3D项目 – 数组越界

typedef struct bot_state_s
{

char teamleader[32]; //netname of the team leader

}  bot_state_t;

void BotTeamAI( bot_state_t *bs ) {

bs->teamleader[sizeof( bs->teamleader )] = '\0';

}

"sizeof( bs->teamleader )]"这行的结果值已经超出了数组的最大边界,正确的代码是:

bs->teamleader[
sizeof(bs->teamleader) / sizeof(bs->teamleader[0]) – 1
] = '\0';

[#8] Miranda IM项目 – 只Copy了部分字符串

struct _textrangew
{
CHARRANGE chrg;
LPWSTR lpstrText;
} TEXTRANGEW;

const wchar_t* Utils::extractURLFromRichEdit(…)
{

::CopyMemory(tr.lpstrText, L"mailto:", 7);

}

这里的bug在于L"mailto:"是宽字符串,宽字符串中的每个字符占2或4个字节(依Compiler使用的字符集编码而定),因此这里只 copy 7个字节显然是不够的,应该是7 * sizeof(wchar_t)。

[#9] CMake项目 – 循环內的数组越界

static const struct {
DWORD   winerr;
int     doserr;
} doserrors[] =
{

};

static void
la_dosmaperr(unsigned long e)
{

for (i = 0; i < sizeof(doserrors); i++)
{
if (doserrors[i].winerr == e)
{
errno = doserrors[i].doserr;
return;
}
}

}

作者原本意图la_dosmaperr中for循环的次数等于数组的元素个数,但sizeof(doserrors)返回的却是数组占用的字节个数,这远远大于数组元素个数,因此造成数组越界。正确的写法:

for (i = 0; i < sizeof(doserrors) / sizeof(*doserrors); i++)

[#10] CPU Identifying Tool项目 – 打印到自身的字符串

char * OSDetection ()
{

sprintf(szOperatingSystem,
"%sversion %d.%d %s (Build %d)",
szOperatingSystem,
osvi.dwMajorVersion,
osvi.dwMinorVersion,
osvi.szCSDVersion,
osvi.dwBuildNumber & 0xFFFF);

sprintf (szOperatingSystem, "%s%s(Build %d)",
szOperatingSystem, osvi.szCSDVersion,
osvi.dwBuildNumber & 0xFFFF);

}

通过sprintf,szOperatingSystem字符串将自己打印到自己里面,这是十分危险的,将导致无法预知的错误结果,可能会导致栈溢出等严重问题。

[#12] Notepad++项目 – 数组局部clear

#define CONT_MAP_MAX 50
int _iContMap[CONT_MAP_MAX];

DockingManager::DockingManager()
{

memset(_iContMap, -1, CONT_MAP_MAX);

}

代码的原本试图将数组_iContMap清零,但memset的第三个参数CONT_MAP_MAX并不能代表数组的真正大小,而只是数组的元素个数而已,显然其忘记乘以sizeof(int)了。

二、未定义行为

在C/C++的语言规范中,我们常常能看到“xx is undefined”。规范中并没有明确表明这类错误是什么样子的,只是说取决于Compiler的实现,也许Compiler会给出正确的结果,但这么使用却是不可移植的。

[#1] Chromium项目 – 智能指针的误用

void AccessibleContainsAccessible(…)
{

auto_ptr<VARIANT> child_array(new VARIANT[child_count]);

}

这里的问题在于使用new[]分配的内存,在智能指针释放时却用了delete,这将会导致未定义行为。看看autoptr的destructor就知道了:

~auto_ptr() {
delete _Myptr;
}

我们可以找一些更合适的类来fix这个问题,比如boost::scopedarray。

[#2] IPP Sample项目 – 经典未定义行为

template<typename T, Ipp32s size> void HadamardFwdFast(…)
{
Ipp32s *pTemp;

for(j=0;j<4;j++) {
a[0] = pTemp[0*4] + pTemp[1*4];
a[1] = pTemp[0*4] – pTemp[1*4];
a[2] = pTemp[2*4] + pTemp[3*4];
a[3] = pTemp[2*4] – pTemp[3*4];
pTemp = pTemp++;

}

}

很多人一眼就看到了"pTemp = pTemp++"这行,对于这个代码编译器会产生两种结果截然不同的翻译:

pTemp = pTemp + 1;
pTemp = pTemp;

TMP = pTemp;
pTemp = pTemp + 1;
pTemp = TMP;

到底是哪种呢?依赖于编译器的实现,甚至是优化级别的设定。

三、与运算优先级相关的错误

[#1] MySQL工程 – !和&的运算优先级

int ha_innobase::create(…)
{

if (srv_file_per_table
&& !mysqld_embedded
&& (!create_info->options & HA_LEX_CREATE_TMP_TABLE)) {

}

这段代码原意是想测试create_info->options变量中几个bit位的值是否set了,即!(create_info->options & HA_LEX_CREATE_TMP_TABLE),但由于!的运算优先级高于&,实际逻辑变成了(!create_info->options) & HA_LEX_CREATE_TMP_TABLE了。如果想要这段代码如期工作,就不要吝啬小括号了。

[#2] Emule工程 – *和++的运算优先级

STDMETHODIMP
CCustomAutoComplete::Next(…, ULONG *pceltFetched)
{

if (pceltFetched != NULL)
*pceltFetched++;

}

显然作者原意是想对pceltFetched所指向的long型变量进行++操作,但由于*和++的运算优先级没有搞对,导致实际上执行了*(pceltFetched++)的操作,而不是(*pceltFetched)++操作。

[#3] Chromium项目 – &和!=的运算优先级

#define FILE_ATTRIBUTE_DIRECTORY 0×00000010

bool GetPlatformFileInfo(PlatformFile file, PlatformFileInfo* info) {

info->is_directory =
file_info.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY != 0;

}

这个程序员的意图是通过测试file_info.dwFileAttributes的几个bit位的值来判定是否是目录,逻辑上应该是(file_info.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) != 0,但由于!=优先级高于&,原代码中无括号,结果逻辑变成了file_info.dwFileAttributes & (FILE_ATTRIBUTE_DIRECTORY != 0),导致is_directory将永远求值为true。

[#4] BCmenu项目 – if和else弄混

void BCMenu::InsertSpaces(void)
{
if(IsLunaMenuStyle())
if(!xp_space_accelerators) return;
else
if(!original_space_accelerators) return;

}

这又是C语言的一个“大坑”,无奈这个BCMenu项目的程序员掉坑里了。虽然从代码缩进上来看,else似乎是与最外层的if配对使用,但实际这段代码的效果是:

if(IsLunaMenuStyle())
{
if(!xp_space_accelerators) {
return;
} else {
if(!original_space_accelerators) return;
}
}

这显然不是程序员原意,看来括号必要时还是不能省略的。修改后的代码如下:

if(IsLunaMenuStyle()) {
if(!xp_space_accelerators) return;
} else {
if(!original_space_accelerators) return;
}

四、格式化输出错误

[#1] ReactOS项目 – 错误地输出WCHAR字符

static void REGPROC_unescape_string(WCHAR* str)
{

default:
fprintf(stderr,
"Warning! Unrecognized escape sequence: \\%c'\n",
str[str_idx]);

}

%c是用来格式化输出非宽字符的,这里用来输出WCHAR显然会得到错误的结果,fix solution是将%c换位%C。

[#2] Intel AMT SDK项目 – 缺少%s 【VS2010,运行可能会崩溃】

void addAttribute(…)
{

int index = _snprintf(temp, 1023,
"%02x%02x:%02x%02x:%02x%02x:%02x%02x:"
"%02x%02x:02x%02x:%02x%02x:%02x%02x",
value[0],value[1],value[2],value[3],value[4],
value[5],value[6],value[7],value[8],
value[9],value[10],value[11],value[12],
value[13],value[14],value[15]);

}

 

不解释了,自己慢慢数和对照吧。

[#3] Intel AMT SDK项目 – 未使用的参数

bool GetUserValues(…)
{

printf("Error: illegal value. Aborting.\n", tmp);
return false;
}

然tmp是多余的。

五、书写错误

[#1] Miranda IM项目 – 在if中赋值

void CIcqProto::handleUserOffline(BYTE *buf, WORD wLen)
{

else if (wTLVType = 0×29 && wTLVLen == sizeof(DWORD))

}

“wTLVType = 0×29”显然是笔误,应该是“wTLVType == 0×29”才对。

[#3] Clang项目 – 对象名书写错误

static Value *SimplifyICmpInst(…) {

case Instruction::Shl: {
bool NUW =
LBO->hasNoUnsignedWrap() && LBO->hasNoUnsignedWrap();
bool NSW =
LBO->hasNoSignedWrap() && RBO->hasNoSignedWrap();

}

从最后一行先后使用了LBO和RBO来看,前面只用了LBO的那行很可能是有问题的,正确的应该是:

bool NUW =
LBO->hasNoUnsignedWrap() && RBO->hasNoUnsignedWrap();

[#6] G3D Content Pak项目 – 一对括号放错了地方

bool Matrix4::operator==(const Matrix4& other) const {
if (memcmp(this, &other, sizeof(Matrix4) == 0)) {
return true;
}

}

由于括号放错了地方,导致memcmp最后的参数变成了sizeof(Matrix4) == 0,这行代码的正确写法应该是:

if (memcmp(this, &other, sizeof(Matrix4)) == 0) {

[#8] Apache Http Server项目 – 多余的sizeof

PSECURITY_ATTRIBUTES GetNullACL(void)
{
PSECURITY_ATTRIBUTES sa;
sa  = (PSECURITY_ATTRIBUTES)
LocalAlloc(LPTR, sizeof(SECURITY_ATTRIBUTES));
sa->nLength = sizeof(sizeof(SECURITY_ATTRIBUTES));

}

最后一行显然是笔误,sizeof(sizeof(SECURITY_ATTRIBUTES))应该写为sizeof(SECURITY_ATTRIBUTES)才对。

[#10] Notepad++项目 – 在本来应该用&的地方使用了&&

TCHAR GetASCII(WPARAM wParam, LPARAM lParam)
{

result=ToAscii(wParam,
(lParam >> 16) && 0xff, keys,&dwReturnedValue,0);

}

(lParam >> 16) && 0xff没有什么意义,求值结果总是true。这里的代码应该是(lParam >> 16) & 0xff。

[#12] Fennec Media Project项目 – 额外的分号

int settings_default(void)
{

for(i=0; i<16; i++);
for(j=0; j<32; j++)
{
settings.conversion.equalizer_bands.boost[i][j] = 0.0;
settings.conversion.equalizer_bands.preamp[i]   = 0.0;
}
}

这又是一个实际逻辑与代码缩进不符的例子。作者的原意是这样的:

for(i=0; i<16; i++)
{
for(j=0; j<32; j++)
{
settings.conversion.equalizer_bands.boost[i][j] = 0.0;
settings.conversion.equalizer_bands.preamp[i]   = 0.0;
}
}

但实际执行代码逻辑却是:

for(i=0; i<16; i++)
{
;
}

for(j=0; j<32; j++)
{
settings.conversion.equalizer_bands.boost[i][j] = 0.0;
settings.conversion.equalizer_bands.preamp[i]   = 0.0;
}

这一切都是那个;导致的。

六、对基本函数和类的误用

[#2] TortoiseSVN项目 – remove函数的误用

STDMETHODIMP CShellExt::Initialize(….)
{

ignoredprops = UTF8ToWide(st.c_str());
// remove all escape chars ('\\')
std::remove(ignoredprops.begin(), ignoredprops.end(), '\\');
break;

}

作者意图删除所有'\\',但他用错了函数,remove函数只是交换元素的位置,将要删除的元素交换到尾部trash,并且返回指向trash首地址的iterator。正确的做法应该是"v.erase(remove(v.begin(), v.end(), 2), v.end())"。

[#5] Pixie项目 – 在循环中使用alloca函数

inline  void  triangulatePolygon(…) {

for (i=1;i<nloops;i++) {

do {

do {

CTriVertex  *snVertex =
(CTriVertex *)alloca(2*sizeof(CTriVertex));

} while(dVertex != loops[0]);

} while(sVertex != loops[i]);

}

}

alloca函数在栈上分配内存,因此在循环中使用alloca可能会很快导致栈溢出。

七、无意义的代码

[#1] IPP Samples项目 – 不完整的条件

void lNormalizeVector_32f_P3IM(Ipp32f *vec[3],
Ipp32s* mask, Ipp32s len)
{
Ipp32s  i;
Ipp32f  norm;

for(i=0; i<len; i++) {
if(mask<0) continue;
norm = 1.0f/sqrt(vec[0][i]*vec[0][i]+
vec[1][i]*vec[1][i]+vec[2][i]*vec[2][i]);
vec[0][i] *= norm; vec[1][i] *= norm; vec[2][i] *= norm;
}
}

mask是Ipp32s类型指针,这样if (mask< 0)这句代码显然没啥意义,正确的代码应该是:

if (mask[i] < 0) continue;

[#2] QT项目 – 重复的检查

Q3TextCustomItem* Q3TextDocument::parseTable(…)
{

while (end < length
&& !hasPrefix(doc, length, end, QLatin1String("</td"))
&& !hasPrefix(doc, length, end, QLatin1String("<td"))
&& !hasPrefix(doc, length, end, QLatin1String("</th"))
&& !hasPrefix(doc, length, end, QLatin1String("<th"))
&& !hasPrefix(doc, length, end, QLatin1String("<td"))
&& !hasPrefix(doc, length, end, QLatin1String("</tr"))
&& !hasPrefix(doc, length, end, QLatin1String("<tr"))
&& !hasPrefix(doc, length, end, QLatin1String("</table"))) {


}

这里对"<td"做了两次check。

八、总是True或False的条件

[#1] Shareaza项目 – char类型的值范围

void CRemote::Output(LPCTSTR pszName)
{


CHAR* pBytes = new CHAR[ nBytes ];
hFile.Read( pBytes, nBytes );

if ( nBytes > 3 && pBytes[0] == 0xEF &&
pBytes[1] == 0xBB && pBytes[2] == 0xBF )
{
pBytes += 3;
nBytes -= 3;
bBOM = true;
}

}

表达式"pBytes[0] == 0xEF"总是False。char类型的值范围是-128~127 < 0xEF,因此这个表达式总是False,导致整个if condition总是为False,与预期逻辑不符。

[#3] VirtualDub项目 – 无符号类型总是>=0

typedef unsigned short wint_t;

void lexungetc(wint_t c) {
if (c < 0)
return;
g_backstack.push_back(c);
}

c是unsigned short类型,永远不会小于0,也就是说if (c < 0)永远为False。

[#8] MySQL项目 – 条件错误

enum enum_mysql_timestamp_type
str_to_datetime(…)
{

else if (str[0] != ‘a’ || str[0] != 'A')
continue; /* Not AM/PM */

}

if (str[0] != ‘a’ || str[0] != 'A')这个条件永远为真。也许这块本意是想用&&。

九、代码漏洞

导致漏洞的代码错误实际上也都是笔误、不正确的条件以及不正确的数组操作等。但这里还是想将一些特定错误划归为一类,因为入侵者可以利用这些错误来攻击你的代码,获取其利益。

[#1] Ultimate TCP/IP项目 – 空字符串的错误检查

char *CUT_CramMd5::GetClientResponse(LPCSTR ServerChallenge)
{

if (m_szPassword != NULL)
{

if (m_szPassword != '\0')
{

}

第二个if condition check意图检查m_szPassword是否为空字符串,但却错误的将指针与'\0'进行比较,正确的代码应该是这样的:

if (*m_szPassword != '\0')

[#2] Chromium项目 – NULL指针的处理

bool ChromeFrameNPAPI::Invoke(…)
{
ChromeFrameNPAPI* plugin_instance =
ChromeFrameInstanceFromNPObject(header);
if (!plugin_instance &&
(plugin_instance->automation_client_.get()))
return false;

}

一旦plugin_instance为NULL,!plugin_instance为True,代码对&&后面的子条件求值,引用plugin_instance将导致程序崩溃。正确的做法应该是:

if (plugin_instance &&
(plugin_instance->automation_client_.get()))
return false;

[#5] Apache httpd Server项目 – 不完整的缓冲区clear

#define MEMSET_BZERO(p,l)       memset((p), 0, (l))

void apr__SHA256_Final(…, SHA256_CTX* context) {

MEMSET_BZERO(context, sizeof(context));

}

这个错误前面提到过,sizeof(context)只是指针的大小,将之改为sizeof(*context)就OK了。

[#7] PNG Library项目 – 意外的指针clear

png_size_t
png_check_keyword(png_structp png_ptr, png_charp key,
png_charpp new_key)
{

if (key_len > 79)
{
png_warning(png_ptr, "keyword length must be 1 – 79 characters");
new_key[79] = '\0';
key_len = 79;
}

}

new_key的类型为png_charpp,顾名思义,这是一个char**类型,但代码中new_key[79] = ‘\0′这句显然是要给某个char赋值,但new_key[n]得到的应该是一个地址,给一个地址赋值为’\0′显然是有误的。正确的写法应该是(*new_key)[79] = '\0'。

[#10] Miranda IM项目 – 保护没生效

void Append( PCXSTR pszSrc, int nLength )
{

UINT nOldLength = GetLength();
if (nOldLength < 0)
{
// protects from underflow
nOldLength = 0;
}

}

nOldLength椒UINT类型,其值永远不会小于0,因此if (nOldLength < 0)这行成了摆设。

[#12] Ultimate TCP/IP项目 – 不正确的循环结束条件

void CUT_StrMethods::RemoveSpaces(LPSTR szString) {

size_t loop, len = strlen(szString);
// Remove the trailing spaces
for(loop = (len-1); loop >= 0; loop–) {
if(szString[loop] != ' ')
break;
}

}

环中的结束条件loop >= 0将永远为True,因为loop变量的类型是size_t是unsigned类型,永远不会小于0。

十、拷贝粘贴

和笔误不同,程序员们决不因该低估拷贝粘贴问题,这类问题发生了太多。程序员们花费了大量时间在这些问题的debug上。

[#1] Fennec Media Project项目 – 处理数组元素时出错

void* tag_write_setframe(char *tmem,
const char *tid, const string dstr)
{

if(lset)
{
fhead[11] = '\0';
fhead[12] = '\0';
fhead[13] = '\0';
fhead[13] = '\0';
}

}

 

咋看一下,fhead[13]做了两次赋值,似乎没啥问题。但仔细想一下,最后那行程序员的原意极可能是想写fhead[14] = '\0'。问题就在这里了。

[#2] MySQL项目 – 处理数组元素时出错

static int rr_cmp(uchar *a,uchar *b)
{
if (a[0] != b[0])
return (int) a[0] – (int) b[0];
if (a[1] != b[1])
return (int) a[1] – (int) b[1];
if (a[2] != b[2])
return (int) a[2] – (int) b[2];
if (a[3] != b[3])
return (int) a[3] – (int) b[3];
if (a[4] != b[4])
return (int) a[4] – (int) b[4];
if (a[5] != b[5])
return (int) a[1] – (int) b[5];
if (a[6] != b[6])
return (int) a[6] – (int) b[6];
return (int) a[7] – (int) b[7];
}

 

编写这类代码时,我猜绝大多数人会选择Copy-Paste,然后再逐行修改,问题就发生在修改过程中,上面的代码中当处理a[5] != b[5]时就忘记修改一个下标了:return (int) a[1] – (int) b[5];显然这里的正确代码应该是return (int) a[5] – (int) b[5]。

[#3] TortoiseSVN项目 文件名不正确

BOOL GetImageHlpVersion(DWORD &dwMS, DWORD &dwLS)
{
return(GetInMemoryFileVersion(("DBGHELP.DLL"),
dwMS,
dwLS)) ;
}

BOOL GetDbgHelpVersion(DWORD &dwMS, DWORD &dwLS)
{
return(GetInMemoryFileVersion(("DBGHELP.DLL"),
dwMS,
dwLS)) ;
}

GetImageHlpVersion和GetDbgHelpVersion都使用了"DBGHELP.DLL"文件,显然GetImageHlpVersion写错文件名了。应该用"IMAGEHLP.DLL"就对了。

[#4] Clang项目 – 等同的函数体

MapTy PerPtrTopDown;
MapTy PerPtrBottomUp;

void clearBottomUpPointers() {
PerPtrTopDown.clear();
}

void clearTopDownPointers() {
PerPtrTopDown.clear();
}

我们看到虽然两个函数名不同,但是函数体的内容是相同的,显然又是copy-paste惹的祸。做如下修改即可:

void clearBottomUpPointers() {
PerPtrBottomUp.clear();
}

 

十一、Null指针的校验迟了

这里的“迟了”的含义是先使用指针,然后再校验指针是否为NULL。

[#1] Quake-III-Arena项目 – 校验迟了

void Item_Paint(itemDef_t *item) {
vec4_t red;
menuDef_t *parent = (menuDef_t*)item->parent;
red[0] = red[3] = 1;
red[1] = red[2] = 0;
if (item == NULL) {
return;
}

}

 

校验item是否为NULL前已经使用过item了,一旦item真的为NULL,那程序必然崩溃。

十二、其他杂项

[#1] Image Processing 项目 – 八进制数

inline
void elxLuminocity(const PixelRGBus& iPixel,
LuminanceCell< PixelRGBus >& oCell)
{
oCell._luminance = uint16(0.2220f*iPixel._red +
0.7067f*iPixel._blue + 0.0713f*iPixel._green);
oCell._pixel = iPixel;
}

inline
void elxLuminocity(const PixelRGBi& iPixel,
LuminanceCell< PixelRGBi >& oCell)
{
oCell._luminance = 2220*iPixel._red +
7067*iPixel._blue + 0713*iPixel._green;
oCell._pixel = iPixel;
}

第二个函数,程序员原意是使用713这个十进制整数,但0713 != 713,在C中,0713是八进制的表示法,Compiler会认为这是个八进制数。

[#2] IPP Sample工程 – 一个变量用于两个loop中

JERRCODE CJPEGDecoder::DecodeScanBaselineNI(void)
{

for(c = 0; c < m_scan_ncomps; c++)
{
block = m_block_buffer + (DCTSIZE2*m_nblock*(j+(i*m_numxMCU)));

// skip any relevant components
for(c = 0; c < m_ccomp[m_curr_comp_no].m_comp_no; c++)
{
block += (DCTSIZE2*m_ccomp

[/c]

.m_nblocks);
}

}

变量c用在了两个loop中,这会导致只有部分数据被处理,或外部循环中止。

[#3] Notepad++项目 – 怪异的条件表达式

int Notepad_plus::getHtmlXmlEncoding(….) const
{

if (langT != L_XML && langT != L_HTML && langT == L_PHP)
return -1;

}

代码中的那行if条件等价于 if (langT == L_PHP),显然似乎不是作者原意,猜测正确的代码应该是这样的:

int Notepad_plus::getHtmlXmlEncoding(….) const
{

if (langT != L_XML && langT != L_HTML && langT != L_PHP)
return -1;

}

posted @ 2013-05-19 21:10 郭龙 阅读(626) | 评论 (1)编辑 收藏

字符串匹配:

---willamette

在匹配串中寻找模式串是否出现,注意和最长公共子序列相区别(LCS: Longest Common Substring)

最简单的Brute Force算法:

首先将匹配串和模式串左对齐,然后从左向右一个一个进行比较,如果不成功则模式串向右移动一个单位。

速度最慢。

那么,怎么改进呢?

我们注意到Brute Force算法是每次移动一个单位,一个一个单位移动显然太慢,是不是可以找到一些办法,让每次能够让模式串多移动一些位置呢?

当然是可以的。

我们也注意到,Brute Force是很不intelligent的,每次匹配不成功的时候,前面匹配成功的信息都被当作废物丢弃了,当然,就如现在的变废为宝一样,我们也同样可以将前面匹配成功的信息利用起来,极大地减少计算机的处理时间,节省成本。^_^

首先介绍的就是KMP算法。

原始论文:Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977.

这个算法实在是太有名了,大学上的算法课程除了最笨的Brute Force算法,然后就介绍了KMP算法。也难怪,呵呵。谁让Knuth D.E.这么world famous呢,不仅拿了图灵奖,而且还写出了计算机界的Bible <The Art of Computer Programming>(业内人士一般简称TAOCP).稍稍提一下,有个叫H.A.Simon的家伙,不仅拿了Turing Award,顺手拿了个Nobel Economics Award,做了AI的爸爸,还是Chicago Univ的Politics PhD,可谓全才。

KMP的思想是这样的:

利用不匹配字符的前面那一段字符的最长前后缀来尽可能地跳过最大的距离

比如

模式串ababac这个时候我们发现在c处不匹配,然后我们看c前面那串字符串的最大相等前后缀,然后再来移动

下面的两个都是模式串,没有写出来匹配串

原始位置ababac

移动之后 ababac

因为后缀是已经匹配了的,而前缀和后缀是相等的,所以直接把前缀移动到原来后缀处,再从原来的c处,也就是现在的第二个b处进行比较。这就是KMP。

当然,有市场就有竞争,字符串匹配这么大一个市场,不可能让BF和KMP全部占了,于是又出现了几个强劲的对手。

第一个登场的是Horspool算法。

论文:Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506

Horspool算法的思想很简单的。不过有个创新之处就是模式串是从右向左进行比较的。很好很强大,为后来的算法影响很大。

匹配串:abcbcsdxzcxx

模式串:cbcac

这个时候我们从右向左进行对暗号,c-c,恩对上了,第二个b-a,不对啊,我们应该怎么办?难道就这么放弃么。于是,模式串从不匹配的那个字符开始从右向左寻找匹配串中不匹配的字符b的位置,结果发现居然有,赶快对上赶快对上,别耽误了。

匹配串:abcbcsdxzcxx

模式串: cbcac

然后继续从最右边的字符从右向左进行比较。这时候,我们发现了,d-c不匹配啊,而且模式穿里面没有噢,没办法,只好移动一个模式串长度的单位了。

匹配串:abcbcsdxzcxx

模式串: cbcac

第二个上来的是Boyer-Moore算法。

是一个很复杂的算法,当然,虽然理论上时间复杂度和KMP差不多,但是实际上却比KMP快数倍,可见实践是检验真理的唯一标准。

原始论文:R.S.Boyer, J.S.Moore, A fast string searching algorithm , Communications of the ACM,20(10):762-772 ,1977

分为两步预处理,第一个是bad-character heuristics,也就是当出现错误匹配的时候,移位,基本上就是做的Horspool那一套。

第二个就是good-suffix heuristics,当出现错误匹配的时候,我还要从不匹配点向左看啊,以前匹配的那段子字符串是不是在模式串本身中还有重复的啊,有重复的话,那么我就直接把重复的那段和匹配串中已经匹配的那一段对齐就是了。再比较

匹配串:abaccbabbazz

模式串:cbadcba

我们看到已经匹配好了cba,但是c-d不匹配,这个时候我们发现既可以采用bad-character heuristics,也可以使用good-suffix heuristics(模式串:cbadcba),在这种情况下,邪不压正。毅然投奔good。移动得到

匹配串:abaccbabbazz

模式串: cbadcba

可是,我们有时候也发现,已经匹配好的那一部分其实并没有再有重复了的啊。这个时候,我们发现已经匹配好的那串字符串有一部分在开头重新出现了,那么,赶快,对齐吧。

匹配串:abacccbbbazz

模式串:cbadccb

然后得到

匹配串:abacccbbbazz

模式串: cbadccb

当两种Good-Suffix出现的时候,取移动距离最大的那个。

最后一个是Sunday算法,实际上比Boyer-Moore还快,呵呵。长江后浪推前浪。

原始论文:Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990

看原始论文的题目,D.M. Sunday貌似是故意想气气Boyer-Moore两位大牛似的。呵呵。不过实际上的确Sunday算法的确比BM算法要快,而且更简单。

Sunday的算法思想和Horspool有些相似,但是。当出现不匹配的时候,却不是去找匹配串中不匹配的字符在模式串的位置,而是直接找最右边对齐的右一位的那个字符在模式串的位置。

比如:

匹配串:abcbczdxzc

模式串:zbcac

恩,这里我们看到b-a没有对上,我们就看匹配串中的z在模式串的位置,然后,嘿嘿。

匹配串:abcbczdxzc

模式串: zbcac

如果模式串中的没有那个字符怎么办呢?很简单,跳过去呗。

匹配串:abcbcedxzcs

模式串:zbcac

e不在模式串中出现

那么我们就

匹配串:abcbcedxzcs

模式串: zbcac

 

实际上,现在还有很多很多字符串匹配算法,这里只是简单介绍了一下最常使用的五种算法,更多算法可以参考一下http://www.inf.fh-flensburg.de/lang/algorithmen/algo.htm,8过这个是德文网站,有的网页没有英文版的哦。

posted @ 2013-05-19 16:58 郭龙 阅读(682) | 评论 (0)编辑 收藏

2012年5月15日 #

1:指针问题:
错误代码:
//A.cpp
T gTemp;
void GetA(T *p)
{
   p = &gTemp;
}

//B.cpp
T iInfo;
GetA(&iInfo);
或者
T *piInfo;
GetA(piInfo);

正确的是
//A.cpp
T gTemp;
T* GetA()
{
  return &gTemp;
}

//B.cpp
T *piInfo = GetA();

解决方案:
<<你必须知道的495个C语言问题>>
5.4 我有个函数,它应该接受并初始化一个指针 void f(int *ip) { static int dummy = 5; ip = &dummy;} 但是当我如下调用时: int *ip; f(ip); 调用者的指针却没有任何变化。 你确定函数初始化的是你希望它初始化的东西吗?请记住在 C 中, 参数是通过值传递的。被调函数仅仅修改了传入的指针副本。你需要传入指针的地址 (函数变成接受指针的指针), 或者让函数返回指针。


同理下面也是错误的
void Swap(T* rht, T* lht)
{
T *pTemp = rht;
rht = lht;
lht = pTemp;
}

2: 计算算法时间问题

start = beginTime();
for (int i = 0; i < 100; ++ i)
   for (int j = 0; j < 1000; ++ j)
{
      //转化函数:
      A......
      //算法
      B.......
}

End = beginTime();

错误地方:A....花费2毫秒

   结果测试出现很大问题:
   A....花费两毫秒
   100*1000*2 = 200s = 3.3分钟

 修改方案:
 
   //转化函数:
   A......
   放在外面进行转化
   

   start = beginTime();
   for (int j = 0; j < 1000; ++ j)
   {
      //转化函数:
     A......
   }

   for (int i = 0; i < 100; ++ i)
      for (int j = 0; j < 1000; ++ j)
   {
      //算法
      B.......
   }

  End = beginTime();

3: Hash 算法

4:for(u_short i = 100; i >= 0; --i)
   修改:
     for (u_short i = 100; i > 0; --i)
     for(int i = 100; i >= 0; --i)

5:读写文件, 发送消息,最好定义一个头,那样
   容易知道读取的是什么,读取的是否错误
 // 消息头
 struct TMSG_HEADER
 {
  char    cMsgID;   // 消息标识

  TMSG_HEADER(char MsgID = INVALID_MSG)
   : cMsgID(MsgID)
  {
  }
 };


 // 请求传送的文件名
 // 客户端传给服务器端的是全路径名称
 // 服务器传回给客户端的是文件名
 struct TMSG_FILENAME : public TMSG_HEADER
 {
  char szFileName[256];  // 保存文件名的字符数组

  TMSG_FILENAME()
   : TMSG_HEADER(MSG_FILENAME)
  {
  }
 };

 // 传送文件长度
 struct TMSG_FILELENGTH : public TMSG_HEADER
 {
  long lLength;

  TMSG_FILELENGTH(long length)
   : TMSG_HEADER(MSG_FILELENGTH), lLength(length)
  {

  }
 };


累了,以后再写吧,↖(^ω^)↗
posted @ 2012-05-15 23:27 郭龙 阅读(465) | 评论 (3)编辑 收藏

2012年2月6日 #

2012 目标

1.
学一种脚本语言 python
学习一下数据结构, 练习编程之美

2.
学习网络通信
看书自学

3.
研读CppUnit自动化测试
学习交叉编译环境


复习去年学习的Linux知识 C/C++知识
复习工作中总结点点滴滴

posted @ 2012-02-06 23:09 郭龙 阅读(230) | 评论 (0)编辑 收藏

2011年11月27日 #

     摘要: 回调函数应用 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->  1#include <iostream>  2using namespace std; &...  阅读全文
posted @ 2011-11-27 21:05 郭龙 阅读(358) | 评论 (0)编辑 收藏

     摘要: 越来越感到自己基础差了今天看到 李先静老师 系统程序员成长计划 那本书上写道 编写通用的链表的于是自己练习写了一下,主要是 void* --> int*  int*--> void*没想到指针的生命周期,整晕了,调试了好久。  typedef struct tagNode_t{    struct tagNode_t...  阅读全文
posted @ 2011-11-27 16:02 郭龙 阅读(272) | 评论 (0)编辑 收藏

2009年04月18日 星期六 下午 08:21
有时会遇到一种很特殊的调试需求,对当前正在运行的其它进程进行调试(正是我今天遇到的情形)。这种情况有可能发生在那些无法直接在调试器中运行的进程身上,例如有的进程 只能在系统启动时运行。另外如果需要对进程产生的子进程进行调试的话,也只能采用这种方式。GDB可以对正在执行的程序进行调度,它允许开发人员中断程序 并查看其状态,之后还能让这个程序正常地继续执行。

GDB提供了两种方式来调试正在运行的进程:一种是在GDB命令行上指定进程的PID,另一种是在GDB中使用“attach”命令。例如,开发人员可以先启动debugme程序,让其开始等待用户的输入。示例如下:

#./debugme
Enter a string to count words:


接下去在另一个虚拟控制台中用下面的命令查出该进程对应的进程号:

# ps -ax | grep debugme
555 pts/1 S 0:00 ./debugme


得到进程的PID后,就可以使用GDB对其进行调试了:

# gdb debugme 555
GNU gdb Red Hat Linux (5.3post-0.20021129.18rh)
Attaching to program: /home/xiaowp/debugme, process 555
Reading symbols from /lib/libc.so.6...done.
……


在上面的输出信息中,以Attaching to program开始的行表明GDB已经成功地附加在PID为555的进程上了。另外一种连接到其它进程的方法是先用file命令加载调试时所需的符号表,然后再通过“attaché”命令进行连接:

(gdb) file /home/xiaowp/debugme
Reading symbols from /home/xiaowp/debugme...done.
(gdb) attach 555
……


如果想知道程序现在运行到了哪里,同样可以使用“backtrace”命令。当然也可以使用“step”命令对程序进行单步调试。

在完成调试之后,不要忘记用detach命令断开连接,让被调试的进程可以继续正常运行。
posted @ 2011-11-27 00:22 郭龙 阅读(431) | 评论 (0)编辑 收藏

2011年11月26日 #

[转自]http://www.wutianqi.com/?p=1822

二维数组和二级指针的传递问题

再次看这篇文章,感觉说的好多都是废话,在文章最前面补充一句话:
[]的优先级高于*”,大家可以带着这句话看下面的~~~
========================
再一次的见证了自己的基础不牢靠。。。幸好发现得早,看见网上说,华为的一个面试题就考了这个方面的。

借那道华为的面试题引出问题,题目:

char **p, a[16][8]; 问:p=a是否会导致程序在以后出现问题?为什么?

可能有一部分朋友会回答正确,这里他们认为,a[]是一级指针,a[][]就是二级指针。那这个到底对不对呢?

OK,用事实说话:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Author: Tanky Woo
// Blog:    www.WuTianQi.com
// Note:   验证二维数组与二级指针的传递问题
#include <iostream> 
using namespace std; 
 
void Test(char **p) 
{ 
    cout << p[0][0] << endl; 
} 
 
int main() 
{ 
    char a[2][3]; 
    Test(a); 
    return 0; 
}

结果报错:

1
2
// error C2664: “Test”: 不能将参数 1 从“char [2][3]”转换为“char  **”
//                          与指向的类型无关;转换要求 reinterpret_cast、C  样式转换或函数样式转换

于是乎,我看了下《C专家编程》里10.5节—使用指针向函数传递一个多维数组

方法一:

函数是:

1
void fun1(int arr[2][3]);

这种方法导致只能处理2行3列的int型数组。

方法二:

可以省略第一维的长度。

函数是:

1
void fun2(int arr[][3]);

这种方法的限制略微宽松了一些,但是还是只能处理每行是3个整数长度的数组。

函数也可以写成:

1
void fun2_2(int (*arrr)[3]);

方法三:

创建一个一维数组,数组中的元素是指向其他东西的指针。也可以说是二级指针。

函数是:

1
int fun3(int **arr);

注意:只有把二维数组改为一个指向向量的指针数组的前提下才可以这么做!

比如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream> 
using namespace std; 
 
void test(char **ptr) 
{ 
    cout << *ptr << endl; 
} 
 
int main() 
{ 
    char *p[3] = {"abc", "def", "ghi"}; 
    test(p); 
    return 0; 
}

在《C专家编程》10.3节的小启发里讲的很透彻:(以下这段文字及对比一定要认真分析!)

数组和指针参数是如何被编译器修改的?

数组名被改写成一个指针参数”规则并不是递归定义的。数组的数组会被改写成“数组的指针”,而不是“指针的指针”:

实参 所匹配的形参

数组的数组 char c[8][10]; char (*)[10]; 数组指针

指针数组 char *c[10]; char **c; 指针的指针

数组指针(行指针) char (*c)[10]; char (*c)[10]; 不改变

指针的指针 char **c; char **c; 不改变

我在CSDN上专门为这个问题提问过:

http://topic.csdn.net/u/20101221/12/da817bda-4e88-44df-bdf8-40e8f44aacb8.html?2076366575

最后我总结下讨论结果:

只要实参的类型与形参的类型一致(或可转换)就行。

为什么这么说呢?

piaojun_pj朋友给了一段代码,分析得很给力:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// VectorTest.cpp : 定义控制台应用程序的入口点。 
// 
 
#include "stdafx.h" 
#include <iostream> 
using namespace std; 
 
int _tmain(int argc, _TCHAR* argv[]) 
{ 
    int arr1[3]; 
    int arr2[3]; 
    int arr3[3]; 
    int * ptr; 
    // ptr1是一个指向 int [3] 的指针,即ptr的类型和&arr1的类型是一样的,注意:arr1指向的内存区域定长 
    int ptr1[3][3]={{1,2,3},{1,2,3},{1,2,3}}; 
    // ptr2是一个指向 int * 的指针,即ptr2的类型和&ptr是一样的,注意:ptr指向的内存区域不定长 
    int * ptr2[3]={arr1,arr2,arr3}; 
    // ptr3是一个指向 int [3] 的指针,即ptr3的类型和&arr1的类型是一样的,注意:arr1指向的内存区域定长 
    int(* ptr3)[3]=&arr1; 
    ptr3=ptr1; // 没错,他们的类型相同 
    // ptr3=ptr2;//error 无法从“int *[3]”转换为“int (*)[3] 
    // ptr4是一个指向 int * 的指针,即ptr4的类型和&ptr是一样的,注意:ptr指向的内存区域不定长 
    int ** ptr4; 
    //ptr4=&arr1; //error 无法从“int (*)[3]”转换为“int ** 
    ptr4=ptr2; // 没错,他们的类型相同 
    //ptr4=ptr3; // error 无法从“int (*)[3]”转换为“int ** 
    return 0; 
}
posted @ 2011-11-26 23:41 郭龙 阅读(390) | 评论 (0)编辑 收藏

2011年11月21日 #

     摘要:     入职一年了,这一年自己学到许多,但是忘记也很多,于是决定定下心来整理以前学到的,并且继续学习        二维数组和二级指针,这真是头疼的问题,困扰了我好几次,       先转一下wanpengcoder的二维数组和二级指针 ...  阅读全文
posted @ 2011-11-21 23:55 郭龙 阅读(5564) | 评论 (0)编辑 收藏

2010年10月31日 #

      由于自己以前是学数学的,许多计算机知识都不懂,所以学许多东西
时候感觉的很累.......于是记录一下最近学习经历,一致勉励自己,继续努力,继续奋斗!   

     C++程序设计看到了异常,感觉真是受益匪浅,许多东西讲的很深,于是反复看,
并结合effect c++(看了两遍,还是有许多东西不懂)
 
     Linux_c编程一战式学习据说是将Linux最好的书之一,看了文件,进程,线程,信号
     感觉讲的却是很好,许多知识反复看了两遍,才看懂....

     看到了一段时候又买了UNIX环境高级编程,看了几十页,正在继续......

      在这其中又把林锐的c/c++ 高质量编程看了两遍,觉得指针,内存那块
 讲的太好了,\(^o^)/~
   
      没事随手看看C语言程序设计现代方法,和编程之美,很不错了C
  语言书,和算法书。
 
  
posted @ 2010-10-31 22:48 郭龙 阅读(393) | 评论 (0)编辑 收藏

仅列出标题  下一页