Main Page | Modules | Namespace List | Data Structures | File List | Data Fields | Globals

SeqBitmap.cpp

Go to the documentation of this file.
00001 /*
00002  
00003 Copyright (c) 2004, Cornell University
00004 All rights reserved.
00005  
00006 Redistribution and use in source and binary forms, with or without
00007 modification, are permitted provided that the following conditions are met:
00008  
00009    - Redistributions of source code must retain the above copyright notice,
00010        this list of conditions and the following disclaimer.
00011    - Redistributions in binary form must reproduce the above copyright
00012        notice, this list of conditions and the following disclaimer in the
00013        documentation and/or other materials provided with the distribution.
00014    - Neither the name of Cornell University nor the names of its
00015        contributors may be used to endorse or promote products derived from
00016        this software without specific prior written permission.
00017  
00018 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
00019 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00020 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00021 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
00022 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
00023 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
00024 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00025 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
00026 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
00027 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
00028 THE POSSIBILITY OF SUCH DAMAGE.
00029  
00030 */
00031 
00032 
00033 /////////////////////////////////////////////////////////////////////
00034 ///
00035 /// SeqBitmap.cpp
00036 ///
00037 /////////////////////////////////////////////////////////////////////
00038 
00039 #include <ostream>
00040 #include <fstream>
00041 #include <stdio.h>
00042 #include "SeqBitmap.h"
00043 
00044 using namespace std;
00045 
00046 /////////////////////////////////////////////////////////////////////
00047 /// @addtogroup BitmapProcessingGroup
00048 /** @{ */
00049 
00050 /// number of different bitmaps in SeqBitmap
00051 const int NUM_BITMAP = 5;
00052 
00053 /// the size of each customer data in each bitmap
00054 const int BITMAP_LENGTH[5] =
00055     {
00056         4, 8, 16, 32, 64
00057     };
00058 
00059 int const SeqBitmap::_lookupTableSize = 0x100;
00060 int* SeqBitmap::_numOnesLookupTable = 0;
00061 int* SeqBitmap::_compress4LookupTable = 0;
00062 unsigned char** SeqBitmap::_compress8Table = 0;
00063 
00064 // Variables used to gather usage statistics
00065 int SeqBitmap::_countOr = 0;
00066 int SeqBitmap::_countAnd = 0;
00067 int SeqBitmap::_countCount = 0;
00068 int SeqBitmap::_countCountZeros = 0;
00069 int SeqBitmap::_countCountSmaller = 0;
00070 int SeqBitmap::_countCreateSBitmap = 0;
00071 int SeqBitmap::_countCreateCBitmap = 0;
00072 
00073 unsigned int* SeqBitmap:: _memory4 = 0;
00074 unsigned int* SeqBitmap::_memory8 = 0;
00075 unsigned short* SeqBitmap::_memory16 = 0;
00076 unsigned int* SeqBitmap::_memory32 = 0;
00077 unsigned int* SeqBitmap::_memory64 = 0;
00078 
00079 // Bitmap sizes within this SeqBitmap
00080 int SeqBitmap::_size4 = 0;
00081 int SeqBitmap::_size8 = 0;
00082 int SeqBitmap::_size16 = 0;
00083 int SeqBitmap::_size32 = 0;
00084 int SeqBitmap::_size64 = 0;
00085 
00086 #define DEBUG_SEQBITMAPCOUNT
00087 
00088 /////////////////////////////////////////////////////////////////////
00089 /// Initialize the lookup tables to be used by this SeqBitmap
00090 /////////////////////////////////////////////////////////////////////
00091 void SeqBitmap::Init()
00092 {
00093     Bitmap4::Init();
00094     Bitmap8::Init();
00095     Bitmap16::Init();
00096     Bitmap32::Init();
00097     Bitmap64::Init();
00098 
00099 
00100     // -- lookup table for compression
00101     int bitLookUp[8] = {128, 64, 32, 16, 8, 4, 2, 1};
00102     int i, j, k;
00103 
00104     _numOnesLookupTable = new int[_lookupTableSize];
00105     // loop over all 256 entries in the table
00106     for (i = 0; i < _lookupTableSize; i++)
00107     {
00108 
00109         // bit loops over the 8 different bits
00110         _numOnesLookupTable[i] = 0;
00111         for (j = 0; j < 8; j++)
00112         {
00113             if (i & bitLookUp[j])
00114                 _numOnesLookupTable[i]++;
00115         }
00116     }
00117 
00118 
00119     // If compress4LookupTable = 0 -> all bits in char equal to 0
00120     //                           1 -> first four bits equal to 0
00121     //                           2 -> second four bits
00122     //        3 ->
00123     // loop over all 256 entries in the table
00124 
00125     _compress4LookupTable = new int[_lookupTableSize];
00126     _compress4LookupTable[0] = 0;
00127 
00128     for (i = 1; i < _lookupTableSize; i++)
00129     {
00130 
00131         // Or the first 4 bits together;
00132         // if the result is 0 then all 4 bits must be 0
00133         if ( (i&0xf) == 0)
00134             _compress4LookupTable[i] = 1;
00135         else if ( (i&0xf0) == 0 )
00136             // Or the second 4 bits together;
00137             // if the result is 0 then all 4 bits must be 0
00138             _compress4LookupTable[i] = 2;
00139         else
00140             _compress4LookupTable[i] = 3;
00141 
00142     }
00143 
00144 
00145     // compress8Table
00146     _compress8Table = new unsigned char * [_lookupTableSize];
00147 
00148     unsigned char value;
00149     int temp;
00150     int pos;
00151     for (i = 0; i < _lookupTableSize; i++)
00152     {
00153         _compress8Table[i] = new unsigned char[_lookupTableSize];
00154         for (j = 0; j < _lookupTableSize; j++)
00155         {
00156             value = 0;
00157             pos = 0;
00158 
00159             for (k = 0; k < 8; k++)
00160             {
00161                 if (i & bitLookUp[k])
00162                 {
00163                     temp = (bitLookUp[k] & j) << k;
00164                     value |= temp >> pos;
00165                     pos++;
00166                 }
00167             }
00168 
00169 
00170             _compress8Table[i][j] = value;
00171         }
00172 
00173     }
00174 }
00175 
00176 /////////////////////////////////////////////////////////////////////
00177 /// Initialize all SeqBitmap memory for duration of program
00178 ///
00179 /// @param size4             total space required for all bitmap_4's
00180 /// @param size8             total space required for all bitmap_8's
00181 /// @param size16            total space required for all bitmap_16's
00182 /// @param size32            total space required for all bitmap_32's
00183 /// @param size64            total space required for all bitmap_64's
00184 /////////////////////////////////////////////////////////////////////
00185 void SeqBitmap::MemAlloc(
00186     int size4,
00187     int size8,
00188     int size16,
00189     int size32,
00190     int size64)
00191 {
00192 
00193     _size4 = size4;
00194     _size8 = size8;
00195     _size16 = size16;
00196     _size32 = size32;
00197     _size64 = size64;
00198 
00199     _memory4 = new unsigned int[size4];
00200     _memory8 = new unsigned int[size8];
00201     _memory16 = new unsigned short[size16];
00202     _memory32 = new unsigned int[size32];
00203     _memory64 = new unsigned int[size64];
00204 }
00205 
00206 /////////////////////////////////////////////////////////////////////
00207 /// Delete all of SeqBitmap's memory
00208 /////////////////////////////////////////////////////////////////////
00209 void SeqBitmap::MemDealloc()
00210 {
00211     delete [] _memory4;
00212     delete [] _memory8;
00213     delete [] _memory16;
00214     delete [] _memory32;
00215     delete [] _memory64;
00216 }
00217 
00218 
00219 
00220 void SeqBitmap::Destroy()
00221 {
00222     Bitmap4::Destroy();
00223     Bitmap8::Destroy();
00224     Bitmap16::Destroy();
00225     Bitmap32::Destroy();
00226     Bitmap64::Destroy();
00227 
00228     if (_numOnesLookupTable != 0)
00229         delete [] _numOnesLookupTable;
00230 
00231     if (_compress4LookupTable != 0)
00232         delete [] _compress4LookupTable;
00233 
00234     if (_compress8Table != 0)
00235     {
00236         for (int i = 0; i < _lookupTableSize; i++)
00237             if (_compress8Table[i] != 0)
00238                 delete [] _compress8Table[i];
00239         delete [] _compress8Table;
00240     }
00241 }
00242 
00243 /////////////////////////////////////////////////////////////////////
00244 /// Bitwise OR 2 SeqBitmaps and store the result
00245 ///
00246 /// @param b1                the first SeqBitmap
00247 /// @param b2                the second SeqBitmap
00248 /////////////////////////////////////////////////////////////////////
00249 void SeqBitmap::Or(const SeqBitmap &b1, const SeqBitmap &b2)
00250 {
00251 
00252 #ifdef DEBUG_SEQBITMAPCOUNT
00253     _countOr++;
00254 #endif
00255 
00256     // OR all sizes of bitmaps within this SeqBitmap
00257     if (b1._bitmap4 != 0)
00258         _bitmap4->Or(*b1._bitmap4, *b2._bitmap4);
00259 
00260     if (b1._bitmap8 != 0)
00261         _bitmap8->Or(*b1._bitmap8, *b2._bitmap8);
00262 
00263     if (b1._bitmap16 != 0)
00264         _bitmap16->Or(*b1._bitmap16, *b2._bitmap16);
00265 
00266     if (b1._bitmap32 != 0)
00267         _bitmap32->Or(*b1._bitmap32, *b2._bitmap32);
00268 
00269     if (b1._bitmap64 != 0)
00270         _bitmap64->Or(*b1._bitmap64, *b2._bitmap64);
00271 }
00272 
00273 
00274 /////////////////////////////////////////////////////////////////////
00275 /// Bitwise AND 2 SeqBitmaps and store the result
00276 ///
00277 /// @param b1                the first SeqBitmap
00278 /// @param b2                the second SeqBitmap
00279 /////////////////////////////////////////////////////////////////////
00280 void SeqBitmap::And(const SeqBitmap &b1, const SeqBitmap &b2)
00281 {
00282 #ifdef DEBUG_SEQBITMAPCOUNT
00283     _countAnd++;
00284 #endif
00285 
00286     // AND all bitmap sizes stored within this SeqBitmap
00287     if (b1._bitmap4 != 0)
00288         _bitmap4->And(*b1._bitmap4, *b2._bitmap4);
00289 
00290     if (b1._bitmap8 != 0)
00291         _bitmap8->And(*b1._bitmap8, *b2._bitmap8);
00292 
00293     if (b1._bitmap16 != 0)
00294         _bitmap16->And(*b1._bitmap16, *b2._bitmap16);
00295 
00296     if (b1._bitmap32 != 0)
00297         _bitmap32->And(*b1._bitmap32, *b2._bitmap32);
00298 
00299     if (b1._bitmap64 != 0)
00300         _bitmap64->And(*b1._bitmap64, *b2._bitmap64);
00301 }
00302 
00303 
00304 /////////////////////////////////////////////////////////////////////
00305 /// find the support of this bitmap
00306 /////////////////////////////////////////////////////////////////////
00307 int SeqBitmap::Count()
00308 {
00309 #ifdef DEBUG_SEQBITMAPCOUNT
00310     _countCount++;
00311 #endif
00312 
00313     int count = 0;
00314 
00315     // Add the counts together for all of the bitmap sizes
00316     if (_bitmap4 != 0)
00317         count += _bitmap4->Count();
00318 
00319     if (_bitmap8 != 0)
00320         count += _bitmap8->Count();
00321 
00322     if (_bitmap16 != 0)
00323         count += _bitmap16->Count();
00324 
00325     if (_bitmap32 != 0)
00326         count += _bitmap32->Count();
00327 
00328     if (_bitmap64 != 0)
00329         count += _bitmap64->Count();
00330 
00331     return count;
00332 }
00333 
00334 
00335 /////////////////////////////////////////////////////////////////////
00336 /// create a s-bitmap from an i-bitmap
00337 ///
00338 /// @param iBitmap           the i-bitmap to copy
00339 /////////////////////////////////////////////////////////////////////
00340 void SeqBitmap::CreateSBitmap(const SeqBitmap &iBitmap)
00341 {
00342 #ifdef DEBUG_SEQBITMAPCOUNT
00343     _countCreateSBitmap++;
00344 #endif
00345 
00346     if (iBitmap._bitmap4 != 0)
00347         _bitmap4->CreateSBitmap(*iBitmap._bitmap4);
00348 
00349     if (iBitmap._bitmap8 != 0)
00350         _bitmap8->CreateSBitmap(*iBitmap._bitmap8);
00351 
00352     if (iBitmap._bitmap16 != 0)
00353         _bitmap16->CreateSBitmap(*iBitmap._bitmap16);
00354 
00355     if (iBitmap._bitmap32 != 0)
00356         _bitmap32->CreateSBitmap(*iBitmap._bitmap32);
00357 
00358     if (iBitmap._bitmap64 != 0)
00359         _bitmap64->CreateSBitmap(*iBitmap._bitmap64);
00360 
00361 }
00362 
00363 /////////////////////////////////////////////////////////////////////
00364 /// create a cbitmap from an i-bitmap
00365 ///
00366 /// @param iBitmap           the bitmap from which we create s-bitmap
00367 /////////////////////////////////////////////////////////////////////
00368 void SeqBitmap::CreateCBitmap(const SeqBitmap &iBitmap)
00369 {
00370 #ifdef DEBUG_SEQBITMAPCOUNT
00371     _countCreateCBitmap++;
00372 #endif
00373 
00374     if (iBitmap._bitmap4 != 0)
00375         _bitmap4->CreateCBitmap(*iBitmap._bitmap4);
00376 
00377     if (iBitmap._bitmap8 != 0)
00378         _bitmap8->CreateCBitmap(*iBitmap._bitmap8);
00379 
00380     if (iBitmap._bitmap16 != 0)
00381         _bitmap16->CreateCBitmap(*iBitmap._bitmap16);
00382 
00383     if (iBitmap._bitmap32 != 0)
00384         _bitmap32->CreateCBitmap(*iBitmap._bitmap32);
00385 
00386     if (iBitmap._bitmap64 != 0)
00387         _bitmap64->CreateCBitmap(*iBitmap._bitmap64);
00388 
00389 }
00390 
00391 
00392 /////////////////////////////////////////////////////////////////////
00393 /// Print bitmap to an output stream
00394 ///
00395 /// @param testFile           output file stream
00396 /////////////////////////////////////////////////////////////////////
00397 void SeqBitmap::PrintBitmap(ofstream &testFile)
00398 {
00399     char buf[256];
00400     if (_bitmap4 != 0)
00401     {
00402         sprintf(buf, " 4 bits  ");
00403         testFile << buf << " " << _bitmap4->_memSizeInt << " : ";
00404 
00405         for (int i = 0; i < _bitmap4->_memSizeInt; i++)
00406         {
00407             sprintf(buf, "%x  ", _bitmap4->_memory[i]);
00408             testFile << buf;
00409         }
00410         testFile << endl;
00411         testFile << _bitmap4->Count() << endl;
00412     }
00413 
00414     if (_bitmap8 != 0)
00415     {
00416         sprintf(buf, " 8 bits  ");
00417         testFile << buf << " " << _bitmap8->_memSizeInt << " : ";
00418 
00419         for (int i = 0; i < _bitmap8->_memSizeInt; i++)
00420         {
00421             sprintf(buf, "%x  ", _bitmap8->_memory[i]);
00422             testFile << buf;
00423         }
00424         testFile << endl;
00425         testFile << _bitmap8->Count() << endl;
00426     }
00427 
00428     if (_bitmap16 != 0)
00429     {
00430         sprintf(buf, "16 bits  ");
00431         testFile << buf << " " << _bitmap16->_memSizeShort << " : ";
00432 
00433         for (int i = 0; i < _bitmap16->_memSizeShort; i++)
00434         {
00435             sprintf(buf, "%x  ", _bitmap16->_memory[i]);
00436             testFile << buf;
00437         }
00438         testFile << endl;
00439         testFile << _bitmap16->Count() << endl;
00440     }
00441 
00442     if (_bitmap32 != 0)
00443     {
00444         sprintf(buf, "32 bits  ");
00445         testFile << buf << " " << _bitmap32->_memSizeInt << " : ";
00446 
00447         for (int i = 0; i < _bitmap32->_memSizeInt; i++)
00448         {
00449             sprintf(buf, "%x  ", _bitmap32->_memory[i]);
00450             testFile << buf;
00451         }
00452         testFile << endl;
00453     }
00454 
00455     if (_bitmap64 != 0)
00456     {
00457         sprintf(buf, "64 bits  ");
00458         testFile << buf << " " << _bitmap64->_memSizeInt << " : ";
00459         for (int i = 0; i < _bitmap64->_memSizeInt; i++)
00460         {
00461             sprintf(buf, "%x  ", _bitmap64->_memory[i]);
00462             testFile << buf;
00463         }
00464         testFile << endl;
00465     }
00466 
00467 }
00468 
00469 
00470 /////////////////////////////////////////////////////////////////////
00471 /// Returns the sizes to allocate for the new compressed f1 bitmap.
00472 /// This will only be called by an OR bitmap during compression
00473 /////////////////////////////////////////////////////////////////////
00474 void SeqBitmap::CountSmaller(
00475     int &size4,
00476     int &size8,
00477     int &size16,
00478     int &size32,
00479     int &size64,
00480     ostream& debugFile)
00481 {
00482 
00483 #ifdef DEBUG_SEQBITMAPCOUNT
00484     _countCountSmaller++;
00485 #endif
00486 
00487     // debugFile << "CountSmaller is called " << endl;
00488     // debugFile << "\tBitmap4 "<< endl;
00489 
00490     if (_bitmap4 != 0)
00491     {
00492         //  debugFile << "\t\tBitmap 4 is not empty" << endl;
00493         size4 = _bitmap4->Count();
00494     }
00495     else
00496     {
00497         //  debugFile << "\t\tBitmap 4 is empty" << endl;
00498         size4 = 0;
00499     }
00500     if (size4 % 2 != 0)
00501         size4++;
00502 
00503     // debugFile << "\t\t" << size4 <<endl;
00504 
00505     size8 = 0;
00506     size16 = 0;
00507     size32 = 0;
00508     size64 = 0;
00509 
00510     int i, count;
00511     unsigned char * memChar;
00512 
00513     // count in bitmap8
00514 
00515     // debugFile << "\tBitmap4 "<< endl;
00516     if (_bitmap8 != 0)
00517     {
00518         //  debugFile << "\t\tBitmap 8 is not empty" << endl;
00519         memChar = reinterpret_cast<unsigned char *>(_bitmap8->_memory);
00520 
00521         //  debugFile << "\t\t\t" << _bitmap8->_memSizeInt * 4 << endl;
00522 
00523         for (i = 0; i < _bitmap8->_memSizeInt*4; i++)
00524         {
00525 
00526             // debugFile << "\t\t\t\t" << memChar[i] << " ";
00527             // debugFile << "\t\t\t\t" << _numOnesLookupTable[memChar[i]] << endl;
00528 
00529             count = _numOnesLookupTable[memChar[i]];
00530             if (count > 4)
00531                 size8++;
00532             else if (count > 0)
00533                 size4++;
00534         }
00535         if (size4 % 2 != 0)
00536             size4++;
00537     }
00538     // else
00539     //  debugFile << "\t\tBitmap 8 is empty" << endl;
00540 
00541     // count in bitmap16
00542     if (_bitmap16 != 0)
00543     {
00544         //  debugFile << "\t\tBitmap 16 is not empty" << endl;
00545         memChar = reinterpret_cast<unsigned char *>(_bitmap16->_memory);
00546         for (i = 0; i < _bitmap16->_memSizeShort*2; i += 2)
00547         {
00548             count = _numOnesLookupTable[memChar[i]];
00549             count += _numOnesLookupTable[memChar[i + 1]];
00550             if (count > 8)
00551                 size16++;
00552             else if (count > 4)
00553                 size8++;
00554             else if (count > 0)
00555                 size4++;
00556         }
00557         if (size4 % 2 != 0)
00558             size4++;
00559     }
00560     // else
00561     //  debugFile << "\t\tBitmap 16 is empty" << endl;
00562 
00563     // count in bitmap32
00564     if (_bitmap32 != 0)
00565     {
00566         //  debugFile << "\t\tBitmap 32 is not empty" << endl;
00567         memChar = reinterpret_cast<unsigned char *>(_bitmap32->_memory);
00568         for (i = 0; i < _bitmap32->_memSizeInt*4; i += 4)
00569         {
00570             count = _numOnesLookupTable[memChar[i]];
00571             count += _numOnesLookupTable[memChar[i + 1]];
00572             count += _numOnesLookupTable[memChar[i + 2]];
00573             count += _numOnesLookupTable[memChar[i + 3]];
00574 
00575             if (count > 16)
00576                 size32++;
00577             else if (count > 8)
00578                 size16++;
00579             else if (count > 4)
00580                 size8++;
00581             else if (count > 0)
00582                 size4++;
00583         }
00584         if (size4 % 2 != 0)
00585             size4++;
00586     }
00587     // else
00588     //  debugFile << "\t\tBitmap 32 is  empty" << endl;
00589 
00590     // count in bitmap64
00591     if (_bitmap64 != 0)
00592     {
00593         //  debugFile << "\t\tBitmap 64 is not empty" << endl;
00594         memChar = reinterpret_cast<unsigned char *>(_bitmap64->_memory);
00595         for (i = 0; i < _bitmap64->_memSizeInt * 4; i += 8)
00596         {
00597             count = _numOnesLookupTable[memChar[i]];
00598             count += _numOnesLookupTable[memChar[i + 1]];
00599             count += _numOnesLookupTable[memChar[i + 2]];
00600             count += _numOnesLookupTable[memChar[i + 3]];
00601             count += _numOnesLookupTable[memChar[i + 4]];
00602             count += _numOnesLookupTable[memChar[i + 5]];
00603             count += _numOnesLookupTable[memChar[i + 6]];
00604             count += _numOnesLookupTable[memChar[i + 7]];
00605             if (count > 32)
00606                 size64++;
00607             else if (count > 16)
00608                 size32++;
00609             else if (count > 8)
00610                 size16++;
00611             else if (count > 4)
00612                 size8++;
00613             else if (count > 0)
00614                 size4++;
00615         }
00616         if (size4 % 2 != 0)
00617             size4++;
00618     }
00619     // else
00620     //  debugFile << "\t\tBitmap 64 is empty" << endl;
00621 
00622     // debugFile << "\tsize4 " << size4<<endl;
00623     // debugFile << "\tsize8 " << size8<<endl;
00624     // debugFile << "\tsize16 " << size16<<endl;
00625     // debugFile << "\tsize32 " << size32<<endl;
00626     // debugFile << "\tsize64 " << size64<<endl;
00627 }
00628 
00629 /////////////////////////////////////////////////////////////////////
00630 /// Compress the Bitmap4 component of a SeqBitmap to a compressed SeqBitmap
00631 ///
00632 /// @param refBitmap            The bitmap specifying which bits can be
00633 ///                                 compressed
00634 /// @param compBitmap           The bitmap to compress
00635 /// @param pos4                 The end position of the Bitmap4 in the
00636 ///                                 compressed SeqBitmap
00637 /////////////////////////////////////////////////////////////////////
00638 void SeqBitmap::Compress4(
00639     SeqBitmap *refBitmap,
00640     SeqBitmap *compBitmap,
00641     int &pos4)
00642 {
00643 
00644     // we don't have to compress it
00645     if (_bitmap4 == 0)
00646         return ;
00647 
00648     int i;
00649 
00650     unsigned char copy = 0;
00651     bool upper4Bits = true;
00652     pos4 = 0;
00653 
00654     unsigned char* refMemChar =
00655         reinterpret_cast<unsigned char*>(refBitmap->_bitmap4->_memory);
00656     unsigned char* compMemChar =
00657         reinterpret_cast<unsigned char*>(compBitmap->_bitmap4->_memory);
00658     unsigned char* resultMemChar =
00659         reinterpret_cast<unsigned char*>(_bitmap4->_memory);
00660 
00661     // go over each character
00662     for (i = 0; i < refBitmap->_bitmap4->_memSizeInt*4; i++)
00663     {
00664         // check to see which of the 4 bits chunks have ones
00665         switch (_compress4LookupTable[refMemChar[i]])
00666         {
00667         case 1:
00668             // only the first four bits have ones
00669             if (upper4Bits)
00670             {
00671                 copy = (compMemChar[i] & 0xf0);
00672                 upper4Bits = false;
00673             }
00674             else
00675             {
00676                 // now copy "copy" over to the output bitmap
00677                 copy |= (compMemChar[i] >> 4);
00678                 resultMemChar[pos4] = copy;
00679                 pos4++;
00680                 upper4Bits = true;
00681             }
00682             break;
00683         case 2:
00684             // only the second four bits have ones
00685             if (upper4Bits)
00686             {
00687                 copy = (compMemChar[i] << 4);
00688                 upper4Bits = false;
00689             }
00690             else
00691             {
00692                 // now copy "copy" over to the output bitmap
00693                 copy |= (compMemChar[i] & 0xf);
00694                 resultMemChar[pos4] = copy;
00695                 pos4++;
00696                 upper4Bits = true;
00697             }
00698             break;
00699         case 3:
00700             resultMemChar[pos4] = compMemChar[i];
00701             pos4++;
00702             break;
00703         default:
00704             break;
00705         }
00706     }
00707 
00708     // copy one remaining set of 4 bits from "copy"
00709     if (!upper4Bits)
00710     {
00711         resultMemChar[pos4] = copy;
00712         pos4++;
00713     }
00714 }
00715 
00716 
00717 /////////////////////////////////////////////////////////////////////
00718 /// Compress the Bitmap8 component of a SeqBitmap to a compressed SeqBitmap
00719 ///
00720 /// @param refBitmap            The bitmap specifying which bits can be
00721 ///                                 compressed
00722 /// @param compBitmap           The bitmap to compress
00723 /// @param pos4                 The end position of the Bitmap4 in the
00724 ///                                 compressed SeqBitmap
00725 /// @param pos8                 The end position of the Bitmap8 in the
00726 ///                                 compressed SeqBitmap
00727 /////////////////////////////////////////////////////////////////////
00728 void SeqBitmap::Compress8(
00729     SeqBitmap *refBitmap,
00730     SeqBitmap *compBitmap,
00731     int &pos4,
00732     int &pos8)
00733 {
00734 
00735     // this bitmap will be gone
00736     if (_bitmap4 == 0 && _bitmap8 == 0)
00737         return ;
00738 
00739     unsigned char* refMemChar8 =
00740         reinterpret_cast<unsigned char*>(refBitmap->_bitmap8->_memory);
00741     unsigned char* compMemChar8 =
00742         reinterpret_cast<unsigned char*>(compBitmap->_bitmap8->_memory);
00743     unsigned char* resultMemChar4 = 0;
00744     unsigned char* resultMemChar8 = 0;
00745     pos8 = 0;
00746 
00747     if (_bitmap4 != 0)
00748         resultMemChar4 = reinterpret_cast<unsigned char*>(_bitmap4->_memory);
00749 
00750     if (_bitmap8 != 0)
00751         resultMemChar8 = reinterpret_cast<unsigned char*>(_bitmap8->_memory);
00752 
00753 
00754 
00755     // When an 8->4 compression is performed,
00756     // can only add the 4 bits to _bitmap4 when a group
00757     // of two 4 bit chunks exists
00758     unsigned char copy = 0;
00759     bool upper4Bits = true;
00760     int i, numOnes;
00761 
00762     for (i = 0; i < refBitmap->_bitmap8->_memSizeInt*4; i++)
00763     {
00764         numOnes = _numOnesLookupTable[refMemChar8[i]];
00765 
00766         if (numOnes > 4)
00767         {
00768             // Copy the current character into the current position of memChar8
00769             resultMemChar8[pos8] = compMemChar8[i];
00770             pos8++;
00771         }
00772         else if (numOnes > 0)
00773         {
00774             // numOnes is between 1 and 4, need to compress to 4
00775             // The compressed 4 bit chunk is the current f1 slice passed
00776             // into the generated lookup table.
00777             // Create the compressed 4 bit chunk, copy it into either the
00778             // lower or upper half of copy (depending on the current state
00779             // of Lower)
00780 
00781 
00782 
00783             if (upper4Bits)
00784             {
00785                 copy = (_compress8Table[refMemChar8[i]][compMemChar8[i]]
00786                         & 0xf0);
00787                 upper4Bits = false;
00788             }
00789             else
00790             {
00791                 // now copy "copy" over to the output bitmap
00792                 copy |= (_compress8Table[refMemChar8[i]][compMemChar8[i]]
00793                          >> 4);
00794                 resultMemChar4[pos4] = copy;
00795                 pos4++;
00796                 upper4Bits = true;
00797             }
00798         }
00799     }
00800 
00801     // copy one remaining set of 4 bits from "copy"
00802     if (!upper4Bits)
00803     {
00804         resultMemChar4[pos4] = copy;
00805         pos4++;
00806     }
00807 }
00808 
00809 
00810 /////////////////////////////////////////////////////////////////////
00811 /// Compress the Bitmap16 component of a SeqBitmap to a compressed SeqBitmap
00812 ///
00813 /// @param refBitmap            The bitmap specifying which bits can be
00814 ///                                 compressed
00815 /// @param compBitmap           The bitmap to compress
00816 /// @param pos4                 The end position of the Bitmap4 in the
00817 ///                                 compressed SeqBitmap
00818 /// @param pos8                 The end position of the Bitmap8 in the
00819 ///                                 compressed SeqBitmap
00820 /// @param pos16                The end position of the Bitmap16 in the
00821 ///                                 compressed SeqBitmap
00822 /////////////////////////////////////////////////////////////////////
00823 void SeqBitmap::Compress16(
00824     SeqBitmap *refBitmap,
00825     SeqBitmap *compBitmap,
00826     int &pos4,
00827     int &pos8,
00828     int &pos16)
00829 {
00830 
00831 
00832     if (_bitmap4 == 0 && _bitmap8 == 0 && _bitmap16 == 0)
00833         return ;
00834 
00835     pos16 = 0;
00836 
00837 
00838     unsigned char* refMemChar16 =
00839         reinterpret_cast<unsigned char*>(refBitmap->_bitmap16->_memory);
00840     unsigned char* compMemChar16 =
00841         reinterpret_cast<unsigned char*>(compBitmap->_bitmap16->_memory);
00842     unsigned char* resultMemChar4 = 0;
00843     unsigned char* resultMemChar8 = 0;
00844     unsigned char* resultMemChar16 = 0;
00845 
00846     if (_bitmap4 != 0)
00847         resultMemChar4 = reinterpret_cast<unsigned char*>(_bitmap4->_memory);
00848 
00849     if (_bitmap8 != 0)
00850         resultMemChar8 = reinterpret_cast<unsigned char*>(_bitmap8->_memory);
00851 
00852     if (_bitmap16 != 0)
00853         resultMemChar16 = reinterpret_cast<unsigned char*>(_bitmap16->_memory);
00854 
00855     // When an 8->4 compression is performed,
00856     // can only add the 4 bits to _bitmap4 when a group of two 4 bit
00857     // chunks exists
00858     int i, numOnesChar1, numOnesChar2, numOnes;
00859     unsigned char copy = 0;
00860     bool upper4Bits = true;
00861 
00862 
00863     // Go through every other character
00864     // 16 is an array of shorts instead of int
00865     for (i = 0; i < refBitmap->_bitmap16->_memSizeShort*2; i += 2)
00866     {
00867         numOnesChar1 = _numOnesLookupTable[refMemChar16[i + 1]];
00868         numOnesChar2 = _numOnesLookupTable[refMemChar16[i]];
00869         numOnes = numOnesChar1 + numOnesChar2;
00870 
00871         if (numOnes > 8)
00872         {
00873             // Copy over the slice of 16 bits to the new _bitmap16
00874             resultMemChar16[pos16 + 1] = compMemChar16[i + 1];
00875             resultMemChar16[pos16] = compMemChar16[i];
00876             pos16 += 2;
00877         }
00878         else if (numOnes > 4)
00879         {
00880             // Compress 16 bits down to 8 bits
00881             // First, compress both chars in the 16 bit slice
00882 
00883             unsigned char slice1 = _compress8Table[refMemChar16[i + 1]]
00884                                    [compMemChar16[i + 1]];
00885             unsigned char slice2 = _compress8Table[refMemChar16[i]]
00886                                    [compMemChar16[i]];
00887 
00888             slice1 |= (slice2 >> numOnesChar1);
00889 
00890             resultMemChar8[pos8] = slice1;
00891             pos8++;
00892         }
00893         else if (numOnes > 0)
00894         {
00895             // numOnes is between 1 and 4
00896             // Compress 16 bits down to 4 bits
00897             // First, compress both chars in the 16 bit slice
00898 
00899             unsigned char slice1 = _compress8Table[refMemChar16[i + 1]]
00900                                    [compMemChar16[i + 1]];
00901             unsigned char slice2 = _compress8Table[refMemChar16[i]]
00902                                    [compMemChar16[i]];
00903 
00904             slice1 |= (slice2 >> numOnesChar1);
00905 
00906             // At this point slice1 must only take up the first four
00907             // bit positions in the char
00908             if (upper4Bits)
00909             {
00910                 copy = (slice1 & 0xf0);
00911                 upper4Bits = false;
00912             }
00913             else
00914             {
00915                 // now copy "copy" over to the output bitmap
00916                 copy |= (slice1 >> 4);
00917                 resultMemChar4[pos4] = copy;
00918                 pos4++;
00919                 upper4Bits = true;
00920             }
00921         }
00922     }
00923 
00924     // copy one remaining set of 4 bits from "copy"
00925     if (!upper4Bits)
00926     {
00927         resultMemChar4[pos4] = copy;
00928         pos4++;
00929     }
00930 }
00931 
00932 
00933 /////////////////////////////////////////////////////////////////////
00934 /// Compress the Bitmap32 component of a SeqBitmap to a compressed SeqBitmap
00935 ///
00936 /// @param refBitmap            The bitmap specifying which bits can be
00937 ///                                 compressed
00938 /// @param compBitmap           The bitmap to compress
00939 /// @param pos4                 The end position of the Bitmap4 in the
00940 ///                                 compressed SeqBitmap
00941 /// @param pos8                 The end position of the Bitmap8 in the
00942 ///                                 compressed SeqBitmap
00943 /// @param pos16                 The end position of the Bitmap16 in the
00944 ///                                 compressed SeqBitmap
00945 /// @param pos32                 The end position of the Bitmap32 in the
00946 ///                                 compressed SeqBitmap
00947 /////////////////////////////////////////////////////////////////////
00948 void SeqBitmap::Compress32(
00949     SeqBitmap *refBitmap,
00950     SeqBitmap *compBitmap,
00951     int &pos4,
00952     int &pos8,
00953     int &pos16,
00954     int &pos32)
00955 {
00956 
00957     if (_bitmap4 == 0 && _bitmap8 == 0 && _bitmap16 == 0 && _bitmap32 == 0)
00958         return ;
00959 
00960 
00961     unsigned char* refMemChar32 =
00962         reinterpret_cast<unsigned char*>(refBitmap->_bitmap32->_memory);
00963     unsigned char* compMemChar32 =
00964         reinterpret_cast<unsigned char*>(compBitmap->_bitmap32->_memory);
00965     unsigned char* resultMemChar4 = 0;
00966     unsigned char* resultMemChar8 = 0;
00967     unsigned char* resultMemChar16 = 0;
00968     unsigned char* resultMemChar32 = 0;
00969 
00970     if (_bitmap4 != 0)
00971         resultMemChar4 = reinterpret_cast<unsigned char*>(_bitmap4->_memory);
00972 
00973     if (_bitmap8 != 0)
00974         resultMemChar8 = reinterpret_cast<unsigned char*>(_bitmap8->_memory);
00975 
00976     if (_bitmap16 != 0)
00977         resultMemChar16 = reinterpret_cast<unsigned char*>(_bitmap16->_memory);
00978 
00979     if (_bitmap32 != 0)
00980         resultMemChar32 = reinterpret_cast<unsigned char*>(_bitmap32->_memory);
00981 
00982 
00983     // When an 8->4 compression is performed, can only add the 4 bits to
00984     // _bitmap4 when a group of two 4 bit chunks exists
00985     int i, numOnesChar1, numOnesChar2, numOnesChar3, numOnesChar4, numOnes;
00986     unsigned char copy = 0;
00987     bool upper4Bits = true;
00988 
00989     pos32 = 0;
00990 
00991     // Go through every 4th character
00992     for (i = 0; i < refBitmap->_bitmap32->_memSizeInt*4; i += 4)
00993     {
00994         numOnesChar1 = _numOnesLookupTable[refMemChar32[i + 3]];
00995         numOnesChar2 = _numOnesLookupTable[refMemChar32[i + 2]];
00996         numOnesChar3 = _numOnesLookupTable[refMemChar32[i + 1]];
00997         numOnesChar4 = _numOnesLookupTable[refMemChar32[i]];
00998 
00999         numOnes = numOnesChar1 + numOnesChar2 + numOnesChar3 + numOnesChar4;
01000 
01001         if (numOnes > 16)
01002         {
01003             // Copy over the slice of 32 bits to the new _bitmap32
01004             resultMemChar32[pos32 + 3] = compMemChar32[i + 3];
01005             resultMemChar32[pos32 + 2] = compMemChar32[i + 2];
01006             resultMemChar32[pos32 + 1] = compMemChar32[i + 1];
01007             resultMemChar32[pos32] = compMemChar32[i];
01008             pos32 += 4;
01009         }
01010         else if (numOnes > 8)
01011         {
01012             // Compress 32 bits down to 16 bits
01013             // Create the 4 8-bit slices based on the lookup table
01014             unsigned short slice1 = (_compress8Table[refMemChar32[i + 3]]
01015                                      [compMemChar32[i + 3]] << 8);
01016             unsigned short slice2 = (_compress8Table[refMemChar32[i + 2]]
01017                                      [compMemChar32[i + 2]] << 8);
01018             unsigned short slice3 = (_compress8Table[refMemChar32[i + 1]]
01019                                      [compMemChar32[i + 1]] << 8);
01020             unsigned short slice4 = (_compress8Table[refMemChar32[i]]
01021                                      [compMemChar32[i]] << 8);
01022 
01023             slice3 |= (slice4 >> numOnesChar3);
01024             slice2 |= (slice3 >> numOnesChar2);
01025             slice1 |= (slice2 >> numOnesChar1);
01026 
01027             // Put slice 1 and slice 2 into _bitmap16
01028             resultMemChar16[pos16 + 1] = (slice1 & 0xff00) >> 8;
01029             resultMemChar16[pos16] = (slice1 & 0xff);
01030             pos16 += 2;
01031 
01032         }
01033         else if (numOnes > 4)
01034         {
01035             // Compress 32 bits down to 8 bits
01036             // Create the 4 8-bit slices based on the lookup table
01037             unsigned char slice1 = _compress8Table[refMemChar32[i + 3]]
01038                                    [compMemChar32[i + 3]];
01039             unsigned char slice2 = _compress8Table[refMemChar32[i + 2]]
01040                                    [compMemChar32[i + 2]];
01041             unsigned char slice3 = _compress8Table[refMemChar32[i + 1]]
01042                                    [compMemChar32[i + 1]];
01043             unsigned char slice4 = _compress8Table[refMemChar32[i]]
01044                                    [compMemChar32[i]];
01045 
01046             // Shift these slices based on the # of ones
01047             slice3 |= (slice4 >> numOnesChar3);
01048             slice2 |= (slice3 >> numOnesChar2);
01049             slice1 |= (slice2 >> numOnesChar1);
01050 
01051 
01052             // Put slice 1 into _bitmap8
01053             resultMemChar8[pos8] = slice1;
01054             pos8++;
01055         }
01056         else if (numOnes > 0)
01057         {
01058 
01059             // numOnes is between 1 and 4
01060             // Compress 32 bits down to 4 bits
01061             // Create the 4 8-bit slices based on the lookup table
01062             unsigned char slice1 = _compress8Table[refMemChar32[i + 3]]
01063                                    [compMemChar32[i + 3]];
01064             unsigned char slice2 = _compress8Table[refMemChar32[i + 2]]
01065                                    [compMemChar32[i + 2]];
01066             unsigned char slice3 = _compress8Table[refMemChar32[i + 1]]
01067                                    [compMemChar32[i + 1]];
01068             unsigned char slice4 = _compress8Table[refMemChar32[i]]
01069                                    [compMemChar32[i]];
01070 
01071             // Shift these slices based on the # of ones
01072             slice3 |= (slice4 >> numOnesChar3);
01073             slice2 |= (slice3 >> numOnesChar2);
01074             slice1 |= (slice2 >> numOnesChar1);
01075 
01076             // At this point slice1 must only take up the first four bit
01077             // positions in the char
01078             if (upper4Bits)
01079             {
01080                 copy = (slice1 & 0xf0);
01081                 upper4Bits = false;
01082             }
01083             else
01084             {
01085                 // now copy "copy" over to the output bitmap
01086                 copy |= (slice1 >> 4);
01087                 resultMemChar4[pos4] = copy;
01088                 pos4++;
01089                 upper4Bits = true;
01090             }
01091         }
01092     }
01093 
01094     // copy one remaining set of 4 bits from "copy"
01095     if (!upper4Bits)
01096     {
01097         resultMemChar4[pos4] = copy;
01098         pos4++;
01099     }
01100 }
01101 
01102 /////////////////////////////////////////////////////////////////////
01103 /// Compress the Bitmap64 component of a SeqBitmap to a compressed SeqBitmap
01104 ///
01105 /// @param refBitmap            The bitmap specifying which bits can be
01106 ///                                 compressed
01107 /// @param compBitmap           The bitmap to compress
01108 /// @param pos4                 The end position of the Bitmap4 in the
01109 ///                                 compressed SeqBitmap
01110 /// @param pos8                 The end position of the Bitmap8 in the
01111 ///                                 compressed SeqBitmap
01112 /// @param pos16                 The end position of the Bitmap16 in the
01113 ///                                 compressed SeqBitmap
01114 /// @param pos32                 The end position of the Bitmap32 in the
01115 ///                                 compressed SeqBitmap
01116 /// @param pos64                 The end position of the Bitmap64 in the
01117 ///                                 compressed SeqBitmap
01118 /////////////////////////////////////////////////////////////////////
01119 void SeqBitmap::Compress64(
01120     SeqBitmap *refBitmap,
01121     SeqBitmap *compBitmap,
01122     int &pos4,
01123     int &pos8,
01124     int &pos16,
01125     int &pos32,
01126     int &pos64)
01127 {
01128 
01129     if (_bitmap4 == 0 &&
01130             _bitmap8 == 0 &&
01131             _bitmap16 == 0 &&
01132             _bitmap32 == 0 &&
01133             _bitmap64 == 0)
01134         return ;
01135 
01136     unsigned char* refMemChar64 =
01137         reinterpret_cast<unsigned char*>(refBitmap->_bitmap64->_memory);
01138     unsigned char* compMemChar64 =
01139         reinterpret_cast<unsigned char*>(compBitmap->_bitmap64->_memory);
01140     unsigned char* resultMemChar4 = 0;
01141     unsigned char* resultMemChar8 = 0;
01142     unsigned char* resultMemChar16 = 0;
01143     unsigned char* resultMemChar32 = 0;
01144     unsigned char* resultMemChar64 = 0;
01145 
01146     if (_bitmap4 != 0)
01147         resultMemChar4 = reinterpret_cast<unsigned char*>(_bitmap4->_memory);
01148 
01149     if (_bitmap8 != 0)
01150         resultMemChar8 = reinterpret_cast<unsigned char*>(_bitmap8->_memory);
01151 
01152     if (_bitmap16 != 0)
01153         resultMemChar16 = reinterpret_cast<unsigned char*>(_bitmap16->_memory);
01154 
01155     if (_bitmap32 != 0)
01156         resultMemChar32 = reinterpret_cast<unsigned char*>(_bitmap32->_memory);
01157 
01158     if (_bitmap64 != 0)
01159         resultMemChar64 = reinterpret_cast<unsigned char*>(_bitmap64->_memory);
01160 
01161 
01162     // When an 8->4 compression is performed, can only add the 4 bits
01163     // to _bitmap4 when a group of two 4 bit chunks exists
01164     int i, numOnesChar1, numOnesChar2, numOnesChar3, numOnesChar4,
01165     numOnesChar5, numOnesChar6, numOnesChar7, numOnesChar8, numOnes;
01166     unsigned char copy = 0;
01167     bool upper4Bits = true;
01168 
01169     pos64 = 0;
01170 
01171 
01172     // Go through every 8th character
01173     for (i = 0; i < refBitmap->_bitmap64->_memSizeInt*4; i += 8)
01174     {
01175         numOnesChar1 = _numOnesLookupTable[refMemChar64[i + 3]];
01176         numOnesChar2 = _numOnesLookupTable[refMemChar64[i + 2]];
01177         numOnesChar3 = _numOnesLookupTable[refMemChar64[i + 1]];
01178         numOnesChar4 = _numOnesLookupTable[refMemChar64[i]];
01179         numOnesChar5 = _numOnesLookupTable[refMemChar64[i + 7]];
01180         numOnesChar6 = _numOnesLookupTable[refMemChar64[i + 6]];
01181         numOnesChar7 = _numOnesLookupTable[refMemChar64[i + 5]];
01182         numOnesChar8 = _numOnesLookupTable[refMemChar64[i + 4]];
01183 
01184         numOnes = numOnesChar1 +
01185                   numOnesChar2 +
01186                   numOnesChar3 +
01187                   numOnesChar4 +
01188                   numOnesChar5 +
01189                   numOnesChar6 +
01190                   numOnesChar7 +
01191                   numOnesChar8;
01192 
01193         if (numOnes > 32)
01194         {
01195             // Copy over the slice of 64 bits to the new _bitmap32
01196             resultMemChar64[pos64 + 3] = compMemChar64[i + 3];
01197             resultMemChar64[pos64 + 2] = compMemChar64[i + 2];
01198             resultMemChar64[pos64 + 1] = compMemChar64[i + 1];
01199             resultMemChar64[pos64] = compMemChar64[i];
01200             resultMemChar64[pos64 + 7] = compMemChar64[i + 7];
01201             resultMemChar64[pos64 + 6] = compMemChar64[i + 6];
01202             resultMemChar64[pos64 + 5] = compMemChar64[i + 5];
01203             resultMemChar64[pos64 + 4] = compMemChar64[i + 4];
01204             pos64 += 8;
01205         }
01206         else if (numOnes > 16)
01207         {
01208             // Compress 64 bits down to 32 bits
01209             // Create the 8 8-bit slices based on the lookup table
01210             unsigned int slice1 = _compress8Table[refMemChar64[i + 3]]
01211                                   [compMemChar64[i + 3]] << 24;
01212             unsigned int slice2 = _compress8Table[refMemChar64[i + 2]]
01213                                   [compMemChar64[i + 2]] << 24;
01214             unsigned int slice3 = _compress8Table[refMemChar64[i + 1]]
01215                                   [compMemChar64[i + 1]] << 24;
01216             unsigned int slice4 = _compress8Table[refMemChar64[i]]
01217                                   [compMemChar64[i]] << 24;
01218             unsigned int slice5 = _compress8Table[refMemChar64[i + 7]]
01219                                   [compMemChar64[i + 7]] << 24;
01220             unsigned int slice6 = _compress8Table[refMemChar64[i + 6]]
01221                                   [compMemChar64[i + 6]] << 24;
01222             unsigned int slice7 = _compress8Table[refMemChar64[i + 5]]
01223                                   [compMemChar64[i + 5]] << 24;
01224             unsigned int slice8 = _compress8Table[refMemChar64[i + 4]]
01225                                   [compMemChar64[i + 4]] << 24;
01226 
01227             // Shift these slices based on the # of ones
01228             slice7 |= (slice8 >> numOnesChar7);
01229             slice6 |= (slice7 >> numOnesChar6);
01230             slice5 |= (slice6 >> numOnesChar5);
01231             slice4 |= (slice5 >> numOnesChar4);
01232             slice3 |= (slice4 >> numOnesChar3);
01233             slice2 |= (slice3 >> numOnesChar2);
01234             slice1 |= (slice2 >> numOnesChar1);
01235 
01236             // Put slices 1-4 into _bitmap32
01237             resultMemChar32[pos32 + 3] = (slice1 & 0xff000000) >> 24;
01238             resultMemChar32[pos32 + 2] = (slice1 & 0xff0000) >> 16;
01239             resultMemChar32[pos32 + 1] = (slice1 & 0xff00) >> 8;
01240             resultMemChar32[pos32] = (slice1 & 0xff);
01241             pos32 += 4;
01242         }
01243         else if (numOnes > 8)
01244         {
01245             // Compress 64 bits down to 16 bits
01246             // Create the 8 8-bit slices based on the lookup table
01247             unsigned short slice1 = _compress8Table[refMemChar64[i + 3]]
01248                                     [compMemChar64[i + 3]] << 8;
01249             unsigned short slice2 = _compress8Table[refMemChar64[i + 2]]
01250                                     [compMemChar64[i + 2]] << 8;
01251             unsigned short slice3 = _compress8Table[refMemChar64[i + 1]]
01252                                     [compMemChar64[i + 1]] << 8;
01253             unsigned short slice4 = _compress8Table[refMemChar64[i]]
01254                                     [compMemChar64[i]] << 8;
01255             unsigned short slice5 = _compress8Table[refMemChar64[i + 7]]
01256                                     [compMemChar64[i + 7]] << 8;
01257             unsigned short slice6 = _compress8Table[refMemChar64[i + 6]]
01258                                     [compMemChar64[i + 6]] << 8;
01259             unsigned short slice7 = _compress8Table[refMemChar64[i + 5]]
01260                                     [compMemChar64[i + 5]] << 8;
01261             unsigned short slice8 = _compress8Table[refMemChar64[i + 4]]
01262                                     [compMemChar64[i + 4]] << 8;
01263 
01264             // Shift these slices based on the # of ones
01265             slice7 |= (slice8 >> numOnesChar7);
01266             slice6 |= (slice7 >> numOnesChar6);
01267             slice5 |= (slice6 >> numOnesChar5);
01268             slice4 |= (slice5 >> numOnesChar4);
01269             slice3 |= (slice4 >> numOnesChar3);
01270             slice2 |= (slice3 >> numOnesChar2);
01271             slice1 |= (slice2 >> numOnesChar1);
01272 
01273             // Put slice 1 and slice 2 into _bitmap16
01274             resultMemChar16[pos16 + 1] = (slice1 & 0xff00) >> 8;
01275             resultMemChar16[pos16] = (slice1 & 0xff);
01276             pos16 += 2;
01277         }
01278         else if (numOnes > 4)
01279         {
01280             // Compress 64 bits down to 8 bits
01281             // Create the 8 8-bit slices based on the lookup table
01282             unsigned char slice1 = _compress8Table[refMemChar64[i + 3]]
01283                                    [compMemChar64[i + 3]];
01284             unsigned char slice2 = _compress8Table[refMemChar64[i + 2]]
01285                                    [compMemChar64[i + 2]];
01286             unsigned char slice3 = _compress8Table[refMemChar64[i + 1]]
01287                                    [compMemChar64[i + 1]];
01288             unsigned char slice4 = _compress8Table[refMemChar64[i]]
01289                                    [compMemChar64[i]];
01290             unsigned char slice5 = _compress8Table[refMemChar64[i + 7]]
01291                                    [compMemChar64[i + 7]];
01292             unsigned char slice6 = _compress8Table[refMemChar64[i + 6]]
01293                                    [compMemChar64[i + 6]];
01294             unsigned char slice7 = _compress8Table[refMemChar64[i + 5]]
01295                                    [compMemChar64[i + 5]];
01296             unsigned char slice8 = _compress8Table[refMemChar64[i + 4]]
01297                                    [compMemChar64[i + 4]];
01298 
01299             // Shift these slices based on the # of ones
01300             slice7 |= (slice8 >> numOnesChar7);
01301             slice6 |= (slice7 >> numOnesChar6);
01302             slice5 |= (slice6 >> numOnesChar5);
01303             slice4 |= (slice5 >> numOnesChar4);
01304             slice3 |= (slice4 >> numOnesChar3);
01305             slice2 |= (slice3 >> numOnesChar2);
01306             slice1 |= (slice2 >> numOnesChar1);
01307 
01308             // Put slice 1 into _bitmap8
01309             resultMemChar8[pos8] = slice1;
01310             pos8++;
01311         }
01312         else if (numOnes > 0)
01313         {
01314             // numOnes is between 1 and 4
01315             // Compress 64 bits down to 4 bits
01316             // Create the 8 8-bit slices based on the lookup table
01317             unsigned char slice1 = _compress8Table[refMemChar64[i + 3]]
01318                                    [compMemChar64[i + 3]];
01319             unsigned char slice2 = _compress8Table[refMemChar64[i + 2]]
01320                                    [compMemChar64[i + 2]];
01321             unsigned char slice3 = _compress8Table[refMemChar64[i + 1]]
01322                                    [compMemChar64[i + 1]];
01323             unsigned char slice4 = _compress8Table[refMemChar64[i]]
01324                                    [compMemChar64[i]];
01325             unsigned char slice5 = _compress8Table[refMemChar64[i + 7]]
01326                                    [compMemChar64[i + 7]];
01327             unsigned char slice6 = _compress8Table[refMemChar64[i + 6]]
01328                                    [compMemChar64[i + 6]];
01329             unsigned char slice7 = _compress8Table[refMemChar64[i + 5]]
01330                                    [compMemChar64[i + 5]];
01331             unsigned char slice8 = _compress8Table[refMemChar64[i + 4]]
01332                                    [compMemChar64[i + 4]];
01333 
01334             // Shift these slices based on the # of ones
01335             slice7 |= (slice8 >> numOnesChar7);
01336             slice6 |= (slice7 >> numOnesChar6);
01337             slice5 |= (slice6 >> numOnesChar5);
01338             slice4 |= (slice5 >> numOnesChar4);
01339             slice3 |= (slice4 >> numOnesChar3);
01340             slice2 |= (slice3 >> numOnesChar2);
01341             slice1 |= (slice2 >> numOnesChar1);
01342 
01343             // At this point slice1 must only take up the first four bit
01344             // positions in the char
01345             if (upper4Bits)
01346             {
01347                 copy = slice1;
01348                 upper4Bits = false;
01349             }
01350             else
01351             {
01352                 // now copy "copy" over to the output bitmap
01353                 copy |= (slice1 >> 4);
01354                 resultMemChar4[pos4] = copy;
01355                 pos4++;
01356                 upper4Bits = true;
01357             }
01358 
01359         }
01360     }
01361 
01362 
01363     // copy one remaining set of 4 bits from "copy"
01364     if (!upper4Bits)
01365     {
01366         resultMemChar4[pos4] = (copy & 0xf0);
01367         pos4++;
01368     }
01369 
01370 }
01371 
01372 void SeqBitmap::printSizes(ostream& out)
01373 {
01374     int size4, size8, size16, size32, size64;
01375     if (_bitmap4)
01376     {
01377         size4 = _bitmap4->getIntSize() * 8;
01378     }
01379     else
01380     {
01381         size4 = 0;
01382     }
01383     if (_bitmap8)
01384     {
01385         size8 = _bitmap8->getIntSize() * 4;
01386     }
01387     else
01388     {
01389         size8 = 0;
01390     }
01391     if (_bitmap16)
01392     {
01393         size16 = _bitmap16->getIntSize() * 2;
01394     }
01395     else
01396     {
01397         size16 = 0;
01398     }
01399     if (_bitmap32)
01400     {
01401         size32 = _bitmap32->getIntSize() * 1;
01402     }
01403     else
01404     {
01405         size32 = 0;
01406     }
01407     if (_bitmap64)
01408     {
01409         size64 = _bitmap64->getIntSize() / 2;
01410     }
01411     else
01412     {
01413         size64 = 0;
01414     }
01415 
01416     out << size4 << " "
01417     << size8 << " "
01418     << size16 << " "
01419     << size32 << " "
01420     << size64 << endl;
01421 }
01422 
01423 /** @} */

Generated on Thu Mar 11 12:01:52 2004 for SPAM by doxygen 1.3.4