huffmancoding.cpp

huffman编码,请多多指教^_^~多多指教多多指教

    //read file's signature
    cout << "Reading file's signature..." << flush;
    readSignature();

    //Create output file
    ofstream outputfile(outFile.c_str(),ios::out | ios::binary);

    if(!outputfile.is_open())
        throw runtime_error( "Cannot create the output file!");

    outputfile.close();

    //insert nonzero counts into mergingTree's heap
    // and set other variables
    cout << "Done\nSetting necessary variables for decompressing..." << flush;

    int nonzeros = 0;
    for(int i = 0; i < 256; i++)
    {
        if(counts[i] != 0)
        {
            nonzeros++;
            mergingType tmp(i,counts[i]);
            codeTree->insertNode(tmp);
        }
    }

    //get file's size and precent to show the progress
    unsigned long inputfilesize = fileSize(),
        currpos = 0, percent, outputfilesize = 0;
    inputfilesize -= ( (nonzeros * 8) + 5 );
    percent = inputfilesize / 100;
    int curper = 0;

    //create mergingTree's tree
    // and also get a copy of mergingTree's root
    codeTree->createTree();
    codeTree->createHuffmanArrays();
    mergingTreeNode< mergingType > *rootCopy, *tmp;
    rootCopy = codeTree->getRootCopy();
    tmp = rootCopy;

    //each time the file's buffer is empty
    // these variables are hold to keep track
    // of the last operation and continue it's job
    int tmpj,tmpk;
    bool middle = false;

    cout << "Done\nDecoding file...\n0 % (0) Bytes." << flush;

    //if we reach to the end of file
    // the readDone variable sets to true
    while(!readDone)
    {
        readFile(); //read 1000 bytes to file's buffer
        bool done = false; //to check if we reach to one leaf or not
        int i = 0,j = 0,k = 0; //counters

        //go through file's buffer
        for(i = 0; i < fileBufferSize2; i++, currpos++)
        {
            //check each bit
            for(j = 0, k = 128; j < 8; j++, k /= 2)
            {
                //check if we continue track of the last 
                // character of the file's buffer
                if(middle) 
                { //so restore the variables
                    middle = false;
                    j = tmpj;
                    k = tmpk;
                }

                //if all bits are done and the rest is
                // the zeros we filled with zero
                // so break and do not continue
                if( (readDone && (zeros == (9 - j))) &&
                    ( i == (fileBufferSize2 - 1)) )
                {
                    done = true; 
                    break;
                }

                done = false;

                //if current bit is 0
                if( (fileBuffer2[i] & k) == 0 )
                {
                    //if this is a leaf
                    if( tmp->leftPtr == NULL )
                    {
                        done = true;
                        //if file's buffer is full so write it to file
                        if(fileBufferSize == 1000)
                            writeTheFile();
                        //write character to buffer
                        fileBuffer[fileBufferSize++] = (tmp->data).data;
                        outputfilesize++;
                        tmp = rootCopy->leftPtr;
                    }
                    else //go to left (for zeros we go to left)
                        tmp = tmp->leftPtr;
                }
                else
                {
                    //if this is a leaf
                    if( tmp->rightPtr == NULL )
                    {
                        done = true; //for leaves
                        //if file's buffer is full so write it to file
                        if(fileBufferSize == 1000)
                            writeTheFile();
                        //write character to buffer
                        fileBuffer[fileBufferSize++] = (tmp->data).data;
                        outputfilesize++;
                        tmp = rootCopy ->rightPtr;//go to right
                    }
                    else //go to right (for zeros we go to right)
                        tmp = tmp->rightPtr;
                }
            }

            //if done one percent
            if( (currpos % percent) ==  0 )
            {
                cout << '\r' << ++curper << " % ("
                    << currpos << ") Bytes.";
            }
        }
        //we didn't write the last character
        if( (zeros == 0) && readDone )
            fileBuffer[fileBufferSize++] = (tmp->data).data;

        if(done) //nothing to continue
        {
            fileBufferSize2 = 0; //reset file's buffer size
            middle = false; //no need
        }
        else
        {
            if(j != 8) //if we're at the middle of character
            {
                //backup variables
                middle = true;
                tmpj = j - 1;
                tmpk = k * 2;
                fileBuffer2[0] = fileBuffer2[fileBufferSize2];
                fileBufferSize2 = 1;
            }
            else //we've done all the bits
            {
                fileBufferSize2 = 0; //reset file's buffer size
                middle = false; //no need
            }
        }
    }
    //show the 100% progress
    if(fileBufferSize != 0)
        writeTheFile();
    cout << '\r' << "100 % ("
        << inputfilesize << ") Bytes.";
    cout << "\nOutpuf file size: " << outputfilesize;
    cout << "\nCompression operation completed successfully.";

    //release dynamic memory
    cout << "\nReleasing memory..." << flush;

    delete [] fileBuffer2;
    delete [] fileBuffer;
    delete [] counts;
    delete codeTree;
    cout << "Done";

    time( &finish );
    unsigned long elapsed_time = (unsigned long)difftime( finish, start );

    cout << "\nProgress took:\n" 
        << (elapsed_time / 3600) << " hours, ";
    elapsed_time %= 3600;

    cout << (elapsed_time / 60) << " minutes, ";
    elapsed_time %= 60;

    cout << elapsed_time << " seconds." << endl;
}

////////////////////////////////////////////////////////////
//read 1000 bytes to file's buffer
void HuffmanCoding::readFile()
{
    //open input file
    ifstream file(inFile.c_str(),ios::in | ios::binary);

    if(!file.is_open())
        throw runtime_error( "Cannot open the input file!");


    //continue from last character
    file.seekg(readChars);

    for(; (fileBufferSize2 < 1000) && (!file.eof()); fileBufferSize2++)
        fileBuffer2[fileBufferSize2] = file.get();


    if(file.eof())
    {
        readDone = true;
        fileBufferSize2 -= 2; //skip EOF and zeros characters
    }

    //save the position of file's pointer
    readChars = file.tellg();
    file.close(); //close the file
}

////////////////////////////////////////////////////////////
//  (used in compress operation)
//write file's signature in this format:
// first [number of variables]
// then for each variable [character] [count]
void HuffmanCoding::writeSignature()
{
    //count the nonzero counts
    int cnt = 0;
    for(int i = 0; i < 256; i++)
        if(counts[i] != 0)
            cnt++;

    //create the output file
    ofstream outputfile(outFile.c_str(),ios::out | ios::binary);

    if(!outputfile.is_open())
        throw runtime_error( "Cannot open the output file!");

    //write count
    outputfile.write( reinterpret_cast< const char * >( &cnt ),
        sizeof( cnt ) );

    //write characters and counts
    for(int j = 0; j < 256; j++)
    {
        if(counts[j] != 0)
        {
            outputfile.write( reinterpret_cast< const char * >( &j ),
                sizeof( j ) );
            outputfile.write( reinterpret_cast< const char * >( &counts[j] ),
                sizeof( counts[j] ) );
        }
    }

    //close the file
    outputfile.close();
}

////////////////////////////////////////////////////////////
//read file's signature (used in decompress operation)
void HuffmanCoding::readSignature()
{
    //open input file
    ifstream inputfile(inFile.c_str(),ios::in | ios::binary);

    if(!inputfile.is_open())
        throw runtime_error( "Cannot open the input file!");

    //read count
    int cnt;
    inputfile.read( reinterpret_cast< char * >( &cnt ),
        sizeof( cnt ) );

    //read characters and counts
    int j;
    for(int i = 0; i < cnt; i++)
    {
        inputfile.read( reinterpret_cast< char * >( &j ),
            sizeof( j ) );
        inputfile.read( reinterpret_cast< char * >( &counts[j] ),
            sizeof( counts[j] ) );
    }

    readChars = inputfile.tellg();


    //go to the end of file
    inputfile.seekg(-1,ios::end);
    //read zeros count
    zeros = inputfile.get();

    //close the file
    inputfile.close();
}

////////////////////////////////////////////////////////////
//return file's size
unsigned long HuffmanCoding::fileSize()
{
    //open file
    ifstream inputfile(inFile.c_str(),ios::in | ios::binary);

    if(!inputfile.is_open())
        throw runtime_error( "Cannot open the input file!");

    //go to the end of file
    inputfile.seekg(-1,ios::end);

    //save current location
    ios::off_type tmp = inputfile.tellg();
    return tmp;
}

#endif

/***************************************************************************\
|                                                                           |
|                                                                           |
|                                                                           |
|                             Alireza Noori