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

Bitmap32.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 /// Bitmap32.cpp
00036 ///
00037 /////////////////////////////////////////////////////////////////////
00038 
00039 #include <stdio.h>
00040 #include <limits.h>
00041 #include "Bitmap32.h"
00042 
00043 const int Bitmap32::_lookupTableSize = 0x10000;
00044 
00045 int Bitmap32::_countOr = 0;
00046 int Bitmap32::_countAnd = 0;
00047 int Bitmap32::_countCount = 0;
00048 int Bitmap32::_countCreateSBitmap = 0;
00049 int Bitmap32::_countCreateCBitmap = 0;
00050 int* Bitmap32::_sBitmapLookupTable = 0;
00051 int* Bitmap32::_cBitmapLookupTable = 0;
00052 
00053 #define DEBUG_BITMAP32COUNT
00054 
00055 /////////////////////////////////////////////////////////////////////
00056 /// Initialize the counting tables
00057 /////////////////////////////////////////////////////////////////////
00058 void Bitmap32::Init()
00059 {
00060 
00061     int i;
00062 
00063     // ------ initialize sBitmapLookupTable -----------------------------
00064     _sBitmapLookupTable = new int[_lookupTableSize];
00065     memset(_sBitmapLookupTable, 0, SIZE_INT*_lookupTableSize);
00066 
00067     _sBitmapLookupTable[0] = 0;
00068     _sBitmapLookupTable[1] = 0;
00069 
00070     int curValue = 0;
00071     int curIndex = 1;
00072     for (i = 2; i < _lookupTableSize; i++)
00073     {
00074         if (i % curIndex == 0)
00075         {
00076             curValue = curValue + curIndex;
00077             curIndex *= 2;
00078         }
00079         _sBitmapLookupTable[i] = curValue;
00080     }
00081 
00082 
00083     // ------ initialize cBitmapLookupTable -----------------------------
00084     _cBitmapLookupTable = new int[_lookupTableSize];
00085     memset(_cBitmapLookupTable, 0, SIZE_UINT*_lookupTableSize);
00086 
00087     _cBitmapLookupTable[0] = 0;
00088     _cBitmapLookupTable[1] = 1;
00089 
00090     curValue = 1;
00091     curIndex = 1;
00092     for (i = 2; i < _lookupTableSize; i++)
00093     {
00094         if (i % curIndex == 0)
00095         {
00096             curIndex *= 2;
00097             curValue = curValue + curIndex;
00098         }
00099         _cBitmapLookupTable[i] = curValue;
00100     }
00101 }
00102 
00103 /////////////////////////////////////////////////////////////////////
00104 /// deallocate counting tables
00105 /////////////////////////////////////////////////////////////////////
00106 void Bitmap32::Destroy()
00107 {
00108     if (_sBitmapLookupTable != 0)
00109         delete [] _sBitmapLookupTable;
00110 
00111     if (_cBitmapLookupTable != 0)
00112         delete [] _cBitmapLookupTable;
00113 }
00114 
00115 /////////////////////////////////////////////////////////////////////
00116 /// Bitwise OR 2 bitmap32s and store the result
00117 ///
00118 /// @param b1                the first Bitmap32
00119 /// @param b2                the second Bitmap32
00120 /////////////////////////////////////////////////////////////////////
00121 void Bitmap32::Or(const Bitmap32 &b1, const Bitmap32 &b2)
00122 {
00123 
00124 #ifdef DEBUG_BITMAP32COUNT
00125     _countOr++;
00126 #endif
00127 
00128     // OR each int bitwise
00129     for (int i = 0; i < b1._memSizeInt; i++)
00130         _memory[i] = b1._memory[i] | b2._memory[i];
00131 }
00132 
00133 
00134 /////////////////////////////////////////////////////////////////////
00135 /// Bitwise AND 2 bitmaps32 and store the result
00136 ///
00137 /// @param b1                the first Bitmap32
00138 /// @param b2                the second Bitmap32
00139 /////////////////////////////////////////////////////////////////////
00140 void Bitmap32::And(const Bitmap32 &b1, const Bitmap32 &b2)
00141 {
00142 
00143 #ifdef DEBUG_BITMAP32COUNT
00144     _countAnd++;
00145 #endif
00146 
00147     // AND each int bitwise
00148     for (int i = 0; i < b1._memSizeInt; i++)
00149         _memory[i] = b1._memory[i] & b2._memory[i];
00150 
00151 }
00152 
00153 
00154 /////////////////////////////////////////////////////////////////////
00155 /// find the support of this bitmap in *number of customers*
00156 ///
00157 /// @return the number of customers that have some bit set among their 32 bits
00158 /////////////////////////////////////////////////////////////////////
00159 int Bitmap32::Count()
00160 {
00161 
00162 #ifdef DEBUG_BITMAP32COUNT
00163     _countCount++;
00164 #endif
00165 
00166     int support = 0;
00167 
00168     // we count the support
00169     for (int i = 0; i < _memSizeInt; i++)
00170         if (_memory[i] > 0)
00171             support++;
00172 
00173     return support;
00174 }
00175 
00176 /////////////////////////////////////////////////////////////////////
00177 /// Create a s-bitmap from an i-bitmap
00178 /// <p>
00179 /// Idea  : Again, we go thru each element of _memory. For each element,
00180 ///     if it is greater than 0, we look up the transformation table
00181 ///     (postProcessTable) to find the corresponding value for the s-bitmap,
00182 ///     and set the remaining SHORTs of the current custom to USHRT_MAX
00183 ///     (i.e. all 1's).
00184 /// <p>
00185 /// Note  : For example, if the bitmap is
00186 ///     [0001 | 1100 | 0011 | 1111 | 0000 | 0000] and
00187 ///     [00001111 | 00011111 | 11111111]. Refer to the paper for details.
00188 ///
00189 /// @param iBitmap           the bitmap32 from which we create s-bitmap
00190 /////////////////////////////////////////////////////////////////////
00191 void Bitmap32::CreateSBitmap(const Bitmap32 &iBitmap)
00192 {
00193 
00194 #ifdef DEBUG_BITMAP32COUNT
00195     _countCreateSBitmap++;
00196 #endif
00197 
00198     assert(_memory);
00199     assert(_memSizeInt == iBitmap._memSizeInt);
00200 
00201     // we walk the memory in terms of shorts
00202     // msib: pointer to memory of ibitmap in terms of short
00203     // ms: pointer to memory as a pointer to shorts
00204     // ss: size of the memory in short
00205     unsigned short* ms = reinterpret_cast<unsigned short*>(_memory);
00206     const unsigned short* msib =
00207         reinterpret_cast<const unsigned short*> (iBitmap._memory);
00208 
00209     // go thru each group of 2 shorts (note that 2 shorts is one customer)
00210     for (int i = 0; i < _memSizeShort; i += 2)
00211     {
00212         // _sBitmapLookupTable should take in a short and return a short
00213         // with the first 1 changed to a
00214         // 0 and all remaining bits set to 1
00215         if (msib[i + 1] > 0)
00216         {
00217             // Post-process the first short, set the other to all 1's
00218 
00219             // big endian
00220             ms[i + 1] = _sBitmapLookupTable[msib[i + 1]];
00221             ms[i] = USHRT_MAX;
00222         }
00223         else
00224         { // Set first short to 0, post-process the second
00225 
00226             ms[i + 1] = 0;
00227             ms[i] = _sBitmapLookupTable[msib[i]];
00228         }
00229     }
00230 
00231 }
00232 
00233 /////////////////////////////////////////////////////////////////////
00234 /// create a c-bitmap for compression
00235 ///
00236 /// @param iBitmap           the bitmap32 from which we create c-bitmap
00237 /////////////////////////////////////////////////////////////////////
00238 void Bitmap32::CreateCBitmap(const Bitmap32 &iBitmap)
00239 {
00240 
00241 #ifdef DEBUG_BITMAP32COUNT
00242     _countCreateCBitmap++;
00243 #endif
00244 
00245     assert(_memory);
00246     assert(_memSizeInt == iBitmap._memSizeInt);
00247 
00248     // we walk the memory in terms of shorts
00249     // msib: pointer to memory of ibitmap in terms of short
00250     // ms: pointer to memory as a pointer to shorts
00251     // ss: size of the memory in short
00252     unsigned short* ms = reinterpret_cast<unsigned short*>(_memory);
00253     const unsigned short* msib =
00254         reinterpret_cast<const unsigned short*> (iBitmap._memory);
00255 
00256     // go thru each group of 2 shorts (note that 2 shorts is one customer)
00257     for (int i = 0; i < _memSizeShort; i += 2)
00258     {
00259         // _sBitmapLookupTable should take in a short and return a short
00260         // with the first 1 changed to a
00261         // 0 and all remaining bits set to 1
00262         if (msib[i + 1] > 0)
00263         {
00264             // Post-process the first short, set the other to all 1's
00265 
00266             // big endian
00267             ms[i + 1] = _cBitmapLookupTable[msib[i + 1]];
00268             ms[i] = USHRT_MAX;
00269         }
00270         else
00271         { // Set first short to 0, post-process the second
00272 
00273             ms[i + 1] = 0;
00274             ms[i] = _cBitmapLookupTable[msib[i]];
00275         }
00276     }
00277 }

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