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 }