缩略图设计初探 - 不会开机的男孩

第一部分简介：

最近有幸参加了一个网上的开源项目，需要我设计一个缩略图存储的方法。整个思路主要是模仿XP的实现方式，而对于Win7（或是Vista）里面将所有缩略图统一管理的模式没有采用。主要想法还是一切从简，这也就是初探的来由了。

整个缩略图的核心算法来自《Inside MoPaQ》http://shadowflare.samods.org/inside_mopaq/

核心是将文件名通过Hash散列到表中，从而达到快速查找的目的。

MPQ文件，对于大部分大学时间沉浸的游戏——War3是非常重要的，每次War3版本的更替都对这个文件做了修改。的确，对于一个计算机系的非常爱玩的我，现在才分析MPQ实在是惭愧。

对于我这个文件名，现在姑且命名为MP(MiniPic)。

这是我第一次用c++来写程序，整个程序很简单，花了差不多1个半月（我这个效率实在不行），和第一篇一样，希望各位大哥能帮忙看看。

第二部分实现：

需求

1.1 这里实现读取，修改固定大小的文件，即每个缩略图的存储空间大小一致。

1.2 根据文件名添加，查找，删除功能。

1.3 文件存储数目固定，不能动态增长。

1.4 储存文件名，使用ID形式访问。

2.存储方案

2.1 表结构设计

整个文件包括FileHeader，HashTable，BlockTable，DataHeader，Data构成。通过计算文件名的hash值，将文件名散列到HashTable中，然后根据HashTable中查找BlockTable（文件块表），在BlockTable中查找到实际文件data的位置。读入DataHeader和Data。

FileHeader HashTableItem HashTableItem …… HashTableItem

BlockTableItem BlockTableItem DataHeader Data DataHeader

Data …

2.2 内存中存储。

内存中存储FileHeader、HashTable、BlockTable、DebrisBlock,dataBuffer。

DebrisBlock是队列结构。存储因删除操作而产生的碎片。

FileHeader，HashTable，BlockTable是数组。dataBuffer数据缓存

3.实现方案

实际还需要增加功能，以下是核心部分。对于每个功能的算法也只写核心部分。

3.1 增加

3.1.1 将文件名转换为数字。这里使用的是MPQ文件算法。

DWORD HashManager::HashString( TCHAR *lpszFileName,DWORD dwHashType )
{
    BYTE *key = (BYTE *)lpszFileName;   
    DWORD seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;   
    int ch;   

    while(*key != 0)   
    {
        ch = toupper(*key++);
        //原来是char，这里处理TCHAR中的0，这里也有小问题，如果要更多的地方使用，还需要做大头小头机数据转换
         if(!*key)
        {
            ++key;
        }
        seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);   
        seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;    
    }   
    return seed1; 
}

3.1.2 插入HashTable。

在处理冲突的时候，是采用最简单的线性探查法，在判断位置相同的时候，采用增加2个Hash值的方法。虽然不能保证肯定不会出问题。但是3个相同的概率很低，大概是10的22.3次方分之一，这个是在参考《Inside MoPaQ》，中的数据，是否可靠。我无法确定。

BOOL HashManager::InsertHashTable( TCHAR *lpszString, FILETIME FileTime, LONG &HashPos, DWORD dwFlags,
                                   BOOL &isNew//设置，是否是新文件
)
{
    ASSERT( m_pHashIndexTable!= NULL );
    isNew = TRUE;
    const DWORD HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;   
    DWORD nHash = HashString(lpszString, HASH_OFFSET);   
    DWORD nHashA = HashString(lpszString, HASH_A);   
    DWORD nHashB = HashString(lpszString, HASH_B);   
    DWORD nHashStart = nHash %m_hashTableLength;   
    DWORD nHashPos = nHashStart;   
    DWORD x=m_pHashIndexTable[nHashPos].dwFlag & FILE_EXISTS;
    DWORD y = m_pHashIndexTable[nHashPos].dwFlag & FILE_DELETED;
    while( x!=0 )
    {   
        if( y==FILE_DELETED )
        {
            isNew = FALSE;
            break;
        }
        //如果有同名文件
         if (m_pHashIndexTable[nHashPos].dwHashValueA == nHashA                && m_pHashIndexTable[nHashPos].dwHashValueB == nHashB)
        {
            if( dwFlags & INSERT_CHECK_FILETIME )
            {
                if(m_pHashIndexTable[nHashPos].dwFileLastModiTime.dwHighDateTime == FileTime.dwHighDateTime
                   && m_pHashIndexTable[nHashPos].dwFileLastModiTime.dwLowDateTime == FileTime.dwLowDateTime)
                {
                  return FALSE;//说明文件真实存在,插入失败
                  }
                else
                {
                    isNew = FALSE;
                    break;
                }
            }
            if( dwFlags & INSERT_REPLACE_EXISTING )
            {
                isNew = FALSE;
                break;
            }
            else
            {
                return FALSE;
            }
        }  
        nHashPos = (nHashPos + 1) % m_hashTableLength;   
        if(nHashPos == nHashStart)    
        {   
            return FALSE;    
        }   
        x=m_pHashIndexTable[nHashPos].dwFlag & FILE_EXISTS;
        y = m_pHashIndexTable[nHashPos].dwFlag & FILE_DELETED;
    }   
    m_pHashIndexTable[nHashPos].dwFlag = FILE_EXISTS;  
    m_pHashIndexTable[nHashPos].dwHashValueA = nHashA;   
    m_pHashIndexTable[nHashPos].dwHashValueB = nHashB;   
    m_pHashIndexTable[nHashPos].iBlockIndex=nHashPos;
    if( dwFlags & INSERT_CHECK_FILETIME )
    {
        m_pHashIndexTable[nHashPos].dwFileLastModiTime.dwHighDateTime = FileTime.dwHighDateTime;
        m_pHashIndexTable[nHashPos].dwFileLastModiTime.dwLowDateTime = FileTime.dwLowDateTime;
    }
    HashPos = nHashPos;
    return TRUE;  
}

3.1.3 插入BlockTable

如果DebrisBlock（空闲表）为空，则将BlockTable中的文件偏移量指向文件最后。

如果DebrisBlock不为空，则将BlockTable中的文件偏移量指向BlockTable头结点，DebrisBlock头结点出列。

3.2 查找

3.2.1 查找HashTable

LONG HashManager::GetHashTablePos( TCHAR *lpszString )
{
    const DWORD HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;   
    DWORD nHash = HashString(lpszString, HASH_OFFSET);   
    DWORD nHashA = HashString(lpszString, HASH_A);   
    DWORD nHashB = HashString(lpszString, HASH_B);   
    DWORD nHashStart = nHash % m_hashTableLength;   
    DWORD nHashPos = nHashStart; 

    DWORD x=m_pHashIndexTable[nHashPos].dwFlag & FILE_EXISTS;
    while( x != 0 )
    {    
        if(m_pHashIndexTable[nHashPos].dwHashValueA == nHashA               && m_pHashIndexTable[nHashPos].dwHashValueB == nHashB)
        {
            return nHashPos;  
        }      
        else
        {
            nHashPos = (nHashPos + 1) % m_hashTableLength; 
        }  
        if(nHashPos == nHashStart)    
             break;    
        x=m_pHashIndexTable[nHashPos].dwFlag & FILE_EXISTS;
    }
    return -1; //没有找到
}

3.3 删除

3.3.1 查找HashTable ：GetHashTablePos；

3.3.2 查找到则DebrisBlock入列文件偏移量，

3.3.3 在HashTable中Flag标记位FILE_DELETED

3.3.4 备注：这里不是真正删除。真正删除在MPFileClose()中的ManagerFileDebris进行。

BOOL    MiniPic::DeleteData(TCHAR *lpszString)
{
    ASSERT(m_isInit);
    ASSERT( m_pHashManager != NULL );
    ASSERT( lpszString != NULL );
    LONG hashTablePos;
    hashTablePos = m_pHashManager->GetHashTablePos(lpszString);
    if( hashTablePos == -1 )
    {
        return FALSE;
    }
    MINIPICDEBRIS debris;
    debris.dwBlockTableIndex = hashTablePos;
    debris.dwDebrisStartAt = m_pBlockTableManager->GetBlockTable()[hashTablePos].FileStartAt;
    m_pHashManager->DeleteHashTable(hashTablePos);
    m_debrisBlock.push_back(debris);
    DebugPrintString(L"Free data the pos is %d\n",hashTablePos);
#ifdef TEST
    if(count1>=testNum)
    {
        count1=0;
    }
    testIns[count1++]=hashTablePos;
#endif
    m_fileHeader.childFileCount--;
    return TRUE;
}

3.4 回收资源

因为在删除的时候只是在hashTable中做了一个Deleted的标记，并没有真正删除文件。若是长时间使用，则会浪费很多空间。此时需要整理。

收集空闲区域。排序，将文件尾部数据移动至最早空闲处，删除空闲处，更新hashTable。

BOOL MiniPic::ManagerFileDebris( LPVOID lpBuffer, const UINT count )
{
    ASSERT( lpBuffer != NULL );
    ASSERT( m_MPFile != NULL );
    if( m_debrisBlock.empty() )
    {
        return TRUE;
    }
    MINIPICDATAITEMHEADER dataItemHeader;
    m_debrisBlock.sort();

    /*
首先将比较Debris block末尾，若是处在文件的最后，则将Debris block末尾数据出列。并向前移动fileEndPointer     保证Debris block要小于文件末尾。
确认Debris block是否为空。
将末尾文件数据移动到Debris block的首部位置，fileEndPointer--，并将Debris block首部数据出列。
    在判断条件1，2*/
    //查找Debris。
    while( !m_debrisBlock.empty() )
   {
        while( m_debrisBlock.back().dwDebrisStartAt + count                   + sizeof(MINIPICDATAITEMHEADER) == m_fileDataEndPointer )//处理文件末尾的空闲区域
         {
            m_fileDataEndPointer -= count + sizeof(MINIPICDATAITEMHEADER);
            m_pHashManager->ClearHashTable( m_debrisBlock.back().dwBlockTableIndex );//New add
            m_debrisBlock.pop_back();
            if( m_debrisBlock.empty() )
            {
                break;
            }
        }
        if( !m_debrisBlock.empty() )
        {
            if( 0xFFFFFFFF == m_MPFile->Seek( m_fileDataEndPointer - count - sizeof(MINIPICDATAITEMHEADER), 
                FILE_BEGIN ))//指向最后文件块开始处
              {
                return FALSE;
            }
            m_MPFile->Read( &dataItemHeader, sizeof(MINIPICDATAITEMHEADER) );
            m_MPFile->Read( lpBuffer, count );
            if( 0xFFFFFFFF == m_MPFile->Seek( m_debrisBlock.front().dwDebrisStartAt, FILE_BEGIN ) )
            {
                return FALSE;
            }
            m_MPFile->Write( &dataItemHeader, sizeof(MINIPICDATAITEMHEADER) );
            m_MPFile->Write( lpBuffer, count );
            m_fileDataEndPointer -= count+sizeof(MINIPICDATAITEMHEADER);
            m_pBlockTableManager->SetBlockTableFileStartAt( dataItemHeader.dwBlockTableIndex,
            m_debrisBlock.front().dwDebrisStartAt );
            //将原来指向空此间的HashTable标记位空。
              m_pHashManager->ClearHashTable( m_debrisBlock.front().dwBlockTableIndex );
            m_debrisBlock.pop_front();
            DebugPrintString(L"find freedata set in it ,and the pos is %d\n",dataItemHeader.dwBlockTableIndex);
        }
    }
    m_fileHeader.bfSize = m_fileDataEndPointer;
    return TRUE;
}

第三部分使用

BOOL      MPFileOpen( LPCTSTR lpFileName );

void          MPFileClose();                            

BOOL      MPFileAddFile( LPCVOID lpBuffer, TCHAR *lpszString, const DWORD fileSize,

                 const FILETIME LastModiTime, LONG &lIndex, DWORD dwFlags

);

BOOL       MPFileReadFile( LPVOID lpBuffer, TCHAR *lpszString );

BOOL       MPFileDeleteFile(TCHAR *lpszString);

void           MPFileFlushData();

BOOL       MPFileReadFileByIndex( LPVOID lpBuffer, const DWORD index );

BOOL       MPFileGetFileName( TCHAR *FileNameBuffer, const  size_t count,

                                                        const DWORD index

);

BOOL        MPFileReName( LPCTSTR lpNewFileName, LPCTSTR lpOldFileName);

第四部分未解决问题

没有实现动态增长，处理文件的最大值有限。没有对文件正确性做足够保证。没有加入CRC or MD5校验。没有设定返回的错误码只有TRUE,FALSE，不利于识别错误问题。算法的有些地方效率不高。还需改进。数据的大小没有做限制，插入过多数据会溢出。

第五部分疑问

在处理非常多的数据时，是否该将文件压缩？许多管理文件系统都加入了最近访问文件列表，这些在有大量文件读入时效率高，是否可以设计类似结构？如何处理异常，特别是在写入时产生的异常，导致文件写入错误。如何能够更好的解决类似问题？在发生异常的时候，如何能够做到高效的完全释放资源？把HashTable，BlockTable放置到文件末尾，方便文件以后动态扩展。但是具体的如何扩容hashTable，可能不好办。在文件头部分增加一个Flag，标示文件的状态。（在读入的时候标记位0，最后如果没有异常则标记位1，那么如果在这个文件出现了问题，那么就可以通过检测这个Flag来判断文件异常），若是设计的更好，可以通过这个检测那部分有问题，而对问题修正。我之前谈到的异常情况，导致有的文件没有即时更新。我的想法是来自IE浏览器，他会记录上次出错的位置，那么这时候就可以启动恢复程序。要是MP文件的Flag是正常，那么就说明问题不在MP文件处理，可能是别的地方异常导致结束，那么就可以重新查找，根据文件创建的时间来判断是否文件变化过，那么这样就比重新生成要快多了。我这里应该提供用来恢复的接口，这个由外部程序调用它。第六部分写给自己

如果仔细看的话，这个并不是很复杂的东西，只是实现了最基本最简单的内容，但是自己做的依然很不完整。问题依然很多。这也映射出自己学习不仔细，编程依然马虎。很多问题都想的不周全。这也进一步说明自己基础不扎实。

我相信我这里肯定还有不少问题，希望大家有时间给小弟看看，与此同时我也会不断改进，把这个做到自己的极限。

第一部分简介：

第二部分实现：

第三部分 使用

第四部分 未解决问题

第五部分 疑问

Comments

第三部分使用

第四部分未解决问题

第五部分疑问