~ubuntu-branches/ubuntu/trusty/bmagic/trusty

<h1>bmundef.h</h1><a href="a00101.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 // Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)

<a name="l00002"></a>00002 //

<a name="l00003"></a>00003 // BM library internal header

<a name="l00004"></a>00004 //

<a name="l00005"></a>00005 // Cleaning the BM related preprocessor defines to eliminate the risks of collision

<a name="l00006"></a>00006 // with other programs. Please let me know if something is missing.

<a name="l00007"></a>00007 //

<a name="l00008"></a>00008

<a name="l00009"></a>00009 #undef BMCOUNT_INC

<a name="l00010"></a>00010 #undef BMCOUNT_DEC

<a name="l00011"></a>00011 #undef BMCOUNT_VALID

<a name="l00012"></a>00012 #undef BMCOUNT_SET

<a name="l00013"></a>00013 #undef BMCOUNT_ADJ

<a name="l00014"></a>00014 #undef BMCOUNT_INC

<a name="l00015"></a>00015 #undef BMCOUNT_DEC

<a name="l00016"></a>00016 #undef BMCOUNT_VALID

<a name="l00017"></a>00017 #undef BMCOUNT_SET

<a name="l00018"></a>00018 #undef BMCOUNT_ADJ

<a name="l00019"></a>00019 #undef BMRESTRICT

<a name="l00020"></a>00020 #undef BMFORCEINLINE

<a name="l00021"></a>00021 #undef BMGAP_PTR

<a name="l00022"></a>00022 #undef BMSET_PTRGAP

<a name="l00023"></a>00023 #undef BM_IS_GAP

<a name="l00024"></a>00024 #undef BMPTR_SETBIT0

<a name="l00025"></a>00025 #undef BMPTR_CLEARBIT0

<a name="l00026"></a>00026 #undef BMPTR_TESTBIT0

<a name="l00027"></a>00027 #undef BM_SET_MMX_GUARD

<a name="l00028"></a>00028 #undef SER_NEXT_GRP

<a name="l00029"></a>00029 #undef BM_SET_ONE_BLOCKS

<a name="l00030"></a>00030 #undef DECLARE_TEMP_BLOCK

<a name="l00031"></a>00031 #undef BM_MM_EMPTY

<a name="l00032"></a>00032 #undef BM_ASSERT

<a name="l00033"></a>00033 #undef FULL_BLOCK_ADDR

<a name="l00034"></a>00034 #undef IS_VALID_ADDR

<a name="l00035"></a>00035 #undef IS_FULL_BLOCK

<a name="l00036"></a>00036 #undef IS_EMPTY_BLOCK

<a name="l00037"></a>00037 #undef BM_INCWORD_BITCOUNT

<a name="l00038"></a>00038 #undef BM_MINISET_GAPLEN

<a name="l00039"></a>00039 #undef BM_MINISET_ARRSIZE

<a name="l00040"></a>00040

<a name="l00041"></a>00041 #undef BMVECTOPT

<a name="l00042"></a>00042 #undef VECT_XOR_ARR_2_MASK

<a name="l00043"></a>00043 #undef VECT_ANDNOT_ARR_2_MASK

<a name="l00044"></a>00044 #undef VECT_INVERT_ARR

<a name="l00045"></a>00045 #undef VECT_AND_ARR

<a name="l00046"></a>00046 #undef VECT_OR_ARR

<a name="l00047"></a>00047 #undef VECT_SUB_ARR

<a name="l00048"></a>00048 #undef VECT_XOR_ARR

<a name="l00049"></a>00049

<a name="l00050"></a>00050 #undef VECT_COPY_BLOCK

<a name="l00051"></a>00051 #undef VECT_SET_BLOCK

<a name="l00052"></a>00052

<a name="l00053"></a>00053 #undef BM_UNALIGNED_ACCESS_OK

<a name="l00054"></a>00054 #undef BM_ALIGN16

<a name="l00055"></a>00055 #undef BM_ALIGN16ATTR

<a name="l00056"></a>00056 #undef BM_x86

<a name="l00057"></a>00057

<h1>bmtrans.h</h1><a href="a00101.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 #ifndef BMTRANS__H__INCLUDED__

<a name="l00002"></a>00002 #define BMTRANS__H__INCLUDED__

<a name="l00003"></a>00003

<a name="l00004"></a>00004 /*

<a name="l00006"></a>00006

<a name="l00007"></a>00007 Permission is hereby granted, free of charge, to any person

<a name="l00008"></a>00008 obtaining a copy of this software and associated documentation

<a name="l00009"></a>00009 files (the "Software"), to deal in the Software without restriction,

<a name="l00010"></a>00010 including without limitation the rights to use, copy, modify, merge,

<a name="l00011"></a>00011 publish, distribute, sublicense, and/or sell copies of the Software,

<a name="l00012"></a>00012 and to permit persons to whom the Software is furnished to do so,

<a name="l00013"></a>00013 subject to the following conditions:

<a name="l00014"></a>00014

<a name="l00015"></a>00015 The above copyright notice and this permission notice shall be included

<a name="l00016"></a>00016 in all copies or substantial portions of the Software.

<a name="l00017"></a>00017

<a name="l00018"></a>00018 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

<a name="l00019"></a>00019 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES

<a name="l00020"></a>00020 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.

<a name="l00021"></a>00021 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,

<a name="l00022"></a>00022 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,

<a name="l00023"></a>00023 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

<a name="l00024"></a>00024 OTHER DEALINGS IN THE SOFTWARE.

<a name="l00025"></a>00025

<a name="l00026"></a>00026 For more information please visit: http://bmagic.sourceforge.net

<a name="l00027"></a>00027

<a name="l00028"></a>00028 */

<a name="l00029"></a>00029

<a name="l00030"></a>00030 namespace bm

<a name="l00031"></a>00031 {

<a name="l00032"></a>00032

<a name="l00033"></a>00033 /**

<a name="l00034"></a>00034 Mini-matrix for bit transposition purposes

<a name="l00035"></a>00035 @internal

<a name="l00036"></a>00036 */

<a name="l00037"></a>00037 template<typename T, unsigned ROWS, unsigned COLS>

<a name="l00038"></a><a class="code" href="a00087.html">00038</a> struct <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>

<a name="l00039"></a>00039 {

<a name="l00040"></a><a class="code" href="a00087.html#a5261ed0fee487db11632487086788a3c">00040</a> typedef T <a class="code" href="a00087.html#a5261ed0fee487db11632487086788a3c">value_type</a>;

<a name="l00041"></a>00041

<a name="l00042"></a><a class="code" href="a00087.html#ad8fc0d5caf424ea3624ddb56001c1ce1">00042</a> T BM_ALIGN16 value[ROWS][COLS] <a class="code" href="a00087.html#ad8fc0d5caf424ea3624ddb56001c1ce1">BM_ALIGN16ATTR</a>;

<a name="l00043"></a>00043

<a name="l00044"></a><a class="code" href="a00087.html#ae9433ff0d38fb743377d227b20990055">00044</a> enum <a class="code" href="a00087.html#ae9433ff0d38fb743377d227b20990055">params</a>

<a name="l00045"></a>00045 {

<a name="l00046"></a><a class="code" href="a00087.html#ae9433ff0d38fb743377d227b20990055a0532f32458bbaf828e0d78b8e36538cc">00046</a> <a class="code" href="a00087.html#ae9433ff0d38fb743377d227b20990055a0532f32458bbaf828e0d78b8e36538cc">n_rows</a> = ROWS,

<a name="l00047"></a><a class="code" href="a00087.html#ae9433ff0d38fb743377d227b20990055ab246fa97cb6a432dfdec4d753d7bfb61">00047</a> <a class="code" href="a00087.html#ae9433ff0d38fb743377d227b20990055ab246fa97cb6a432dfdec4d753d7bfb61">n_columns</a> = COLS

<a name="l00048"></a>00048 };

<a name="l00049"></a>00049

<a name="l00050"></a>00050

<a name="l00051"></a>00051 /// Row characteristics for transposed matrix

<a name="l00052"></a><a class="code" href="a00082.html">00052</a> struct <a class="code" href="a00082.html" title="Row characteristics for transposed matrix.">rstat</a>

<a name="l00053"></a>00053 {

<a name="l00054"></a><a class="code" href="a00082.html#a7d8796287f45647e6db5c99b37edf9ba">00054</a> unsigned <a class="code" href="a00082.html#a7d8796287f45647e6db5c99b37edf9ba">bit_count</a>;

<a name="l00055"></a><a class="code" href="a00082.html#a030c17209b79356e3074498ba9199b70">00055</a> unsigned <a class="code" href="a00082.html#a030c17209b79356e3074498ba9199b70">gap_count</a>;

<a name="l00056"></a><a class="code" href="a00082.html#ace83214da2dcbfc7c7e9d6c0bea3d702">00056</a> <a class="code" href="a00116.html#a593916a103395805070a3200720c6416" title="set representation variants">bm::set_representation</a> <a class="code" href="a00082.html#ace83214da2dcbfc7c7e9d6c0bea3d702">best_rep</a>;

<a name="l00057"></a>00057 };

<a name="l00058"></a>00058

<a name="l00059"></a><a class="code" href="a00087.html#aa11586df7bfd7ba53e15858e2d28f10b">00059</a> static unsigned <a class="code" href="a00087.html#aa11586df7bfd7ba53e15858e2d28f10b">rows</a>() { return ROWS; }

<a name="l00060"></a><a class="code" href="a00087.html#a0a2c77e2e93fd819773719788be7b6f0">00060</a> static unsigned <a class="code" href="a00087.html#a0a2c77e2e93fd819773719788be7b6f0">cols</a>() { return COLS; }

<a name="l00061"></a>00061

<a name="l00062"></a><a class="code" href="a00087.html#a4c8acc2e96ee64c814b5544036d30d62">00062</a> const T* <a class="code" href="a00087.html#a4c8acc2e96ee64c814b5544036d30d62">row</a>(unsigned row_idx) const { return value[row_idx]; }

<a name="l00063"></a><a class="code" href="a00087.html#abd030846a646b5a6e1d262ea7badf5be">00063</a> T* <a class="code" href="a00087.html#abd030846a646b5a6e1d262ea7badf5be">row</a>(unsigned row_idx) { return value[row_idx]; }

<a name="l00064"></a>00064 };

<a name="l00065"></a>00065

<a name="l00066"></a>00066

<a name="l00067"></a>00067 /*!

<a name="l00068"></a>00068 Bit array grabber - template specitialization for various basic types

<a name="l00069"></a>00069 @internal

<a name="l00070"></a>00070 */

<a name="l00071"></a>00071 template<typename T, unsigned BPC>

<a name="l00072"></a><a class="code" href="a00025.html">00072</a> struct <a class="code" href="a00025.html">bit_grabber</a>

100

<a name="l00073"></a>00073 {

101

<a name="l00074"></a>00074 static

102

<a name="l00075"></a><a class="code" href="a00025.html#ae4e83826a695d2cf8dbdc39a789bf456">00075</a> unsigned get(const T*, unsigned)

103

<a name="l00076"></a>00076 {

104

<a name="l00077"></a>00077 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(0); return 0;

105

<a name="l00078"></a>00078 }

106

<a name="l00079"></a>00079 };

107

<a name="l00080"></a>00080

108

<a name="l00081"></a>00081 template<>

109

<a name="l00082"></a><a class="code" href="a00028.html">00082</a> struct <a class="code" href="a00025.html">bit_grabber</a><unsigned, 32>

110

<a name="l00083"></a>00083 {

111

<a name="l00084"></a>00084 static

112

<a name="l00085"></a><a class="code" href="a00028.html#a68466209bbb94e443715725099b359f3">00085</a> unsigned get(const unsigned* arr, unsigned j)

113

<a name="l00086"></a>00086 {

114

<a name="l00087"></a>00087 return (((arr[0] >> j) & 1) << 0) |

115

<a name="l00088"></a>00088 (((arr[1] >> j) & 1) << 1) |

116

<a name="l00089"></a>00089 (((arr[2] >> j) & 1) << 2) |

117

<a name="l00090"></a>00090 (((arr[3] >> j) & 1) << 3) |

118

<a name="l00091"></a>00091 (((arr[4] >> j) & 1) << 4) |

119

<a name="l00092"></a>00092 (((arr[5] >> j) & 1) << 5) |

120

<a name="l00093"></a>00093 (((arr[6] >> j) & 1) << 6) |

121

<a name="l00094"></a>00094 (((arr[7] >> j) & 1) << 7) |

122

<a name="l00095"></a>00095 (((arr[8] >> j) & 1) << 8) |

123

<a name="l00096"></a>00096 (((arr[9] >> j) & 1) << 9) |

124

<a name="l00097"></a>00097 (((arr[10]>> j) & 1) << 10)|

125

<a name="l00098"></a>00098 (((arr[11]>> j) & 1) << 11)|

126

<a name="l00099"></a>00099 (((arr[12]>> j) & 1) << 12)|

127

<a name="l00100"></a>00100 (((arr[13]>> j) & 1) << 13)|

128

<a name="l00101"></a>00101 (((arr[14]>> j) & 1) << 14)|

129

<a name="l00102"></a>00102 (((arr[15]>> j) & 1) << 15)|

130

<a name="l00103"></a>00103 (((arr[16]>> j) & 1) << 16)|

131

<a name="l00104"></a>00104 (((arr[17]>> j) & 1) << 17)|

132

<a name="l00105"></a>00105 (((arr[18]>> j) & 1) << 18)|

133

<a name="l00106"></a>00106 (((arr[19]>> j) & 1) << 19)|

134

<a name="l00107"></a>00107 (((arr[20]>> j) & 1) << 20)|

135

<a name="l00108"></a>00108 (((arr[21]>> j) & 1) << 21)|

136

<a name="l00109"></a>00109 (((arr[22]>> j) & 1) << 22)|

137

<a name="l00110"></a>00110 (((arr[23]>> j) & 1) << 23)|

138

<a name="l00111"></a>00111 (((arr[24]>> j) & 1) << 24)|

139

<a name="l00112"></a>00112 (((arr[25]>> j) & 1) << 25)|

140

<a name="l00113"></a>00113 (((arr[26]>> j) & 1) << 26)|

141

<a name="l00114"></a>00114 (((arr[27]>> j) & 1) << 27)|

142

<a name="l00115"></a>00115 (((arr[28]>> j) & 1) << 28)|

143

<a name="l00116"></a>00116 (((arr[29]>> j) & 1) << 29)|

144

<a name="l00117"></a>00117 (((arr[30]>> j) & 1) << 30)|

145

<a name="l00118"></a>00118 (((arr[31]>> j) & 1) << 31);

146

<a name="l00119"></a>00119 }

147

<a name="l00120"></a>00120 };

148

<a name="l00121"></a>00121

149

<a name="l00122"></a>00122 template<>

150

<a name="l00123"></a><a class="code" href="a00027.html">00123</a> struct <a class="code" href="a00025.html">bit_grabber</a><unsigned short, 16>

151

<a name="l00124"></a>00124 {

152

<a name="l00125"></a>00125 static

153

<a name="l00126"></a><a class="code" href="a00027.html#a3dd630fb60384045851f4a9b8fbba747">00126</a> unsigned get(const unsigned short* arr, unsigned j)

154

<a name="l00127"></a>00127 {

155

<a name="l00128"></a>00128 return (((arr[0] >> j) & 1) << 0) |

156

<a name="l00129"></a>00129 (((arr[1] >> j) & 1) << 1) |

157

<a name="l00130"></a>00130 (((arr[2] >> j) & 1) << 2) |

158

<a name="l00131"></a>00131 (((arr[3] >> j) & 1) << 3) |

159

<a name="l00132"></a>00132 (((arr[4] >> j) & 1) << 4) |

160

<a name="l00133"></a>00133 (((arr[5] >> j) & 1) << 5) |

161

<a name="l00134"></a>00134 (((arr[6] >> j) & 1) << 6) |

162

<a name="l00135"></a>00135 (((arr[7] >> j) & 1) << 7) |

163

<a name="l00136"></a>00136 (((arr[8] >> j) & 1) << 8) |

164

<a name="l00137"></a>00137 (((arr[9] >> j) & 1) << 9) |

165

<a name="l00138"></a>00138 (((arr[10]>> j) & 1) << 10)|

166

<a name="l00139"></a>00139 (((arr[11]>> j) & 1) << 11)|

167

<a name="l00140"></a>00140 (((arr[12]>> j) & 1) << 12)|

168

<a name="l00141"></a>00141 (((arr[13]>> j) & 1) << 13)|

169

<a name="l00142"></a>00142 (((arr[14]>> j) & 1) << 14)|

170

<a name="l00143"></a>00143 (((arr[15]>> j) & 1) << 15);

171

<a name="l00144"></a>00144 }

172

<a name="l00145"></a>00145 };

173

<a name="l00146"></a>00146

174

<a name="l00147"></a>00147

175

<a name="l00148"></a>00148 template<>

176

<a name="l00149"></a><a class="code" href="a00026.html">00149</a> struct <a class="code" href="a00025.html">bit_grabber</a><unsigned char, 8>

177

<a name="l00150"></a>00150 {

178

<a name="l00151"></a>00151 static

179

<a name="l00152"></a><a class="code" href="a00026.html#a8753317c8359b848499c9395b3320320">00152</a> unsigned get(const unsigned char* arr, unsigned j)

180

<a name="l00153"></a>00153 {

181

<a name="l00154"></a>00154 return (((arr[0] >> j) & 1) << 0) |

182

<a name="l00155"></a>00155 (((arr[1] >> j) & 1) << 1) |

183

<a name="l00156"></a>00156 (((arr[2] >> j) & 1) << 2) |

184

<a name="l00157"></a>00157 (((arr[3] >> j) & 1) << 3) |

185

<a name="l00158"></a>00158 (((arr[4] >> j) & 1) << 4) |

186

<a name="l00159"></a>00159 (((arr[5] >> j) & 1) << 5) |

187

<a name="l00160"></a>00160 (((arr[6] >> j) & 1) << 6) |

188

<a name="l00161"></a>00161 (((arr[7] >> j) & 1) << 7);

189

<a name="l00162"></a>00162 }

190

<a name="l00163"></a>00163 };

191

<a name="l00164"></a>00164

192

<a name="l00165"></a>00165

193

<a name="l00166"></a>00166 /*!

194

<a name="l00167"></a>00167 Bit transpose matrix grabber - template specitialization for various basic types

195

<a name="l00168"></a>00168 @internal

196

<a name="l00169"></a>00169 */

197

<a name="l00170"></a>00170 template<typename T, unsigned BPC, unsigned BPS>

198

<a name="l00171"></a><a class="code" href="a00033.html">00171</a> struct <a class="code" href="a00033.html">bit_trans_grabber</a>

199

<a name="l00172"></a>00172 {

200

<a name="l00173"></a>00173 static

201

<a name="l00174"></a><a class="code" href="a00033.html#a28c57c0d9ac1055cc799afe5e888abb5">00174</a> T get(const T <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[BPC][BPS], unsigned i, unsigned j)

202

<a name="l00175"></a>00175 {

203

<a name="l00176"></a>00176 T w = 0;

204

<a name="l00177"></a>00177

205

<a name="l00178"></a>00178 // Next code hopes that compiler will completely

206

<a name="l00179"></a>00179 // eliminate ifs (all conditions are known at compile time)

207

<a name="l00180"></a>00180 // ( typically C++ compilers are smart to do that)

208

<a name="l00181"></a>00181

209

<a name="l00182"></a>00182 // 8-bit (minimum)

210

<a name="l00183"></a>00183 w |=

211

<a name="l00184"></a>00184 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[0][i] >> j) & 1) << 0) |

212

<a name="l00185"></a>00185 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[1][i] >> j) & 1) << 1) |

213

<a name="l00186"></a>00186 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[2][i] >> j) & 1) << 2) |

214

<a name="l00187"></a>00187 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[3][i] >> j) & 1) << 3) |

215

<a name="l00188"></a>00188 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[4][i] >> j) & 1) << 4) |

216

<a name="l00189"></a>00189 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[5][i] >> j) & 1) << 5) |

217

<a name="l00190"></a>00190 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[6][i] >> j) & 1) << 6) |

218

<a name="l00191"></a>00191 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[7][i] >> j) & 1) << 7);

219

<a name="l00192"></a>00192

220

<a name="l00193"></a>00193 // 16-bit

221

<a name="l00194"></a>00194 if (BPC > 8)

222

<a name="l00195"></a>00195 {

223

<a name="l00196"></a>00196 w |=

224

<a name="l00197"></a>00197 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[8][i] >> j) & 1) << 8) |

225

<a name="l00198"></a>00198 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[9][i] >> j) & 1) << 9) |

226

<a name="l00199"></a>00199 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[10][i] >> j) & 1) << 10) |

227

<a name="l00200"></a>00200 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[11][i] >> j) & 1) << 11) |

228

<a name="l00201"></a>00201 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[12][i] >> j) & 1) << 12) |

229

<a name="l00202"></a>00202 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[13][i] >> j) & 1) << 13) |

230

<a name="l00203"></a>00203 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[14][i] >> j) & 1) << 14) |

231

<a name="l00204"></a>00204 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[15][i] >> j) & 1) << 15);

232

<a name="l00205"></a>00205 }

233

<a name="l00206"></a>00206

234

<a name="l00207"></a>00207 // 32-bit

235

<a name="l00208"></a>00208 if (BPC > 16)

236

<a name="l00209"></a>00209 {

237

<a name="l00210"></a>00210 w |=

238

<a name="l00211"></a>00211 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[16][i] >> j) & 1) << 16) |

239

<a name="l00212"></a>00212 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[17][i] >> j) & 1) << 17) |

240

<a name="l00213"></a>00213 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[18][i] >> j) & 1) << 18) |

241

<a name="l00214"></a>00214 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[19][i] >> j) & 1) << 19) |

242

<a name="l00215"></a>00215 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[20][i] >> j) & 1) << 20) |

243

<a name="l00216"></a>00216 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[21][i] >> j) & 1) << 21) |

244

<a name="l00217"></a>00217 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[22][i] >> j) & 1) << 22) |

245

<a name="l00218"></a>00218 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[23][i] >> j) & 1) << 23) |

246

<a name="l00219"></a>00219 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[24][i] >> j) & 1) << 24) |

247

<a name="l00220"></a>00220 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[25][i] >> j) & 1) << 25) |

248

<a name="l00221"></a>00221 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[26][i] >> j) & 1) << 26) |

249

<a name="l00222"></a>00222 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[27][i] >> j) & 1) << 27) |

250

<a name="l00223"></a>00223 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[28][i] >> j) & 1) << 28) |

251

<a name="l00224"></a>00224 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[29][i] >> j) & 1) << 29) |

252

<a name="l00225"></a>00225 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[30][i] >> j) & 1) << 30) |

253

<a name="l00226"></a>00226 (((<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[31][i] >> j) & 1) << 31);

254

<a name="l00227"></a>00227 }

255

<a name="l00228"></a>00228 return w;

256

<a name="l00229"></a>00229 }

257

<a name="l00230"></a>00230 };

258

<a name="l00231"></a>00231

259

<a name="l00232"></a>00232 /*

260

<a name="l00233"></a>00233 template<>

261

<a name="l00234"></a>00234 struct bit_trans_grabber<unsigned, 32, bm::set_block_plain_size>

262

<a name="l00235"></a>00235 {

263

<a name="l00236"></a>00236 static

264

<a name="l00237"></a>00237 unsigned get(const unsigned tmatrix[32][bm::set_block_plain_size], unsigned i, unsigned j)

265

<a name="l00238"></a>00238 {

266

<a name="l00239"></a>00239 return

267

<a name="l00240"></a>00240 (((tmatrix[0][i] >> j) & 1) << 0) |

268

<a name="l00241"></a>00241 (((tmatrix[1][i] >> j) & 1) << 1) |

269

<a name="l00242"></a>00242 (((tmatrix[2][i] >> j) & 1) << 2) |

270

<a name="l00243"></a>00243 (((tmatrix[3][i] >> j) & 1) << 3) |

271

<a name="l00244"></a>00244 (((tmatrix[4][i] >> j) & 1) << 4) |

272

<a name="l00245"></a>00245 (((tmatrix[5][i] >> j) & 1) << 5) |

273

<a name="l00246"></a>00246 (((tmatrix[6][i] >> j) & 1) << 6) |

274

<a name="l00247"></a>00247 (((tmatrix[7][i] >> j) & 1) << 7) |

275

<a name="l00248"></a>00248 (((tmatrix[8][i] >> j) & 1) << 8) |

276

<a name="l00249"></a>00249 (((tmatrix[9][i] >> j) & 1) << 9) |

277

<a name="l00250"></a>00250 (((tmatrix[10][i] >> j) & 1) << 10) |

278

<a name="l00251"></a>00251 (((tmatrix[11][i] >> j) & 1) << 11) |

279

<a name="l00252"></a>00252 (((tmatrix[12][i] >> j) & 1) << 12) |

280

<a name="l00253"></a>00253 (((tmatrix[13][i] >> j) & 1) << 13) |

281

<a name="l00254"></a>00254 (((tmatrix[14][i] >> j) & 1) << 14) |

282

<a name="l00255"></a>00255 (((tmatrix[15][i] >> j) & 1) << 15) |

283

<a name="l00256"></a>00256 (((tmatrix[16][i] >> j) & 1) << 16) |

284

<a name="l00257"></a>00257 (((tmatrix[17][i] >> j) & 1) << 17) |

285

<a name="l00258"></a>00258 (((tmatrix[18][i] >> j) & 1) << 18) |

286

<a name="l00259"></a>00259 (((tmatrix[19][i] >> j) & 1) << 19) |

287

<a name="l00260"></a>00260 (((tmatrix[20][i] >> j) & 1) << 20) |

288

<a name="l00261"></a>00261 (((tmatrix[21][i] >> j) & 1) << 21) |

289

<a name="l00262"></a>00262 (((tmatrix[22][i] >> j) & 1) << 22) |

290

<a name="l00263"></a>00263 (((tmatrix[23][i] >> j) & 1) << 23) |

291

<a name="l00264"></a>00264 (((tmatrix[24][i] >> j) & 1) << 24) |

292

<a name="l00265"></a>00265 (((tmatrix[25][i] >> j) & 1) << 25) |

293

<a name="l00266"></a>00266 (((tmatrix[26][i] >> j) & 1) << 26) |

294

<a name="l00267"></a>00267 (((tmatrix[27][i] >> j) & 1) << 27) |

295

<a name="l00268"></a>00268 (((tmatrix[28][i] >> j) & 1) << 28) |

296

<a name="l00269"></a>00269 (((tmatrix[29][i] >> j) & 1) << 29) |

297

<a name="l00270"></a>00270 (((tmatrix[30][i] >> j) & 1) << 30) |

298

<a name="l00271"></a>00271 (((tmatrix[31][i] >> j) & 1) << 31);

299

<a name="l00272"></a>00272 }

300

<a name="l00273"></a>00273 };

301

<a name="l00274"></a>00274 */

302

<a name="l00275"></a>00275

303

<a name="l00276"></a>00276

304

<a name="l00277"></a>00277

305

<a name="l00278"></a>00278 /**

306

<a name="l00279"></a>00279 Generic bit-array transposition function

307

<a name="l00280"></a>00280 T - array type (any int)

308

<a name="l00281"></a>00281 BPC - bit plain count

309

<a name="l00282"></a>00282 BPS - bit plain size

310

<a name="l00283"></a>00283

311

<a name="l00284"></a>00284 \param arr - source array start

312

<a name="l00285"></a>00285 \param arr_size - source array size

313

<a name="l00286"></a>00286 \param tmatrix - destination bit matrix

314

<a name="l00287"></a>00287

315

<a name="l00288"></a>00288 */

316

<a name="l00289"></a>00289 template<typename T, unsigned BPC, unsigned BPS>

317

<a name="l00290"></a><a class="code" href="a00116.html#a2e3af9c9f2eb481130d240ba4cd6fd68">00290</a> void <a class="code" href="a00116.html#a2e3af9c9f2eb481130d240ba4cd6fd68" title="Generic bit-array transposition function T - array type (any int) BPC - bit plain...">vect_bit_transpose</a>(const T* arr,

318

<a name="l00291"></a>00291 unsigned arr_size,

319

<a name="l00292"></a>00292 T <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[BPC][BPS])

320

<a name="l00293"></a>00293 {

321

<a name="l00294"></a>00294 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(sizeof(T)*8 == BPC);

322

<a name="l00295"></a>00295

323

<a name="l00296"></a>00296 unsigned col = 0;

324

<a name="l00297"></a>00297 for (unsigned i = 0; i < arr_size;

325

<a name="l00298"></a>00298 i+=BPC, arr+=BPC,

326

<a name="l00299"></a>00299 ++col)

327

<a name="l00300"></a>00300 {

328

<a name="l00301"></a>00301 for (unsigned j = 0; j < BPC; ++j)

329

<a name="l00302"></a>00302 {

330

<a name="l00303"></a>00303 unsigned w =

331

<a name="l00304"></a>00304 <a class="code" href="a00025.html">bm::bit_grabber<T, BPC>::get</a>(arr, j);

332

<a name="l00305"></a>00305 T* row = <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[j];

333

<a name="l00306"></a>00306 row[col] = (T)w;

334

<a name="l00307"></a>00307 } // for j

335

<a name="l00308"></a>00308 } // for i

336

<a name="l00309"></a>00309 }

337

<a name="l00310"></a>00310

338

<a name="l00311"></a>00311

339

<a name="l00312"></a>00312 /**

340

<a name="l00313"></a>00313 Restore bit array from the transposition matrix

341

<a name="l00314"></a>00314 T - array type (any int)

342

<a name="l00315"></a>00315 BPC - bit plain count

343

<a name="l00316"></a>00316 BPS - bit plain size

344

<a name="l00317"></a>00317

345

<a name="l00318"></a>00318 \param arr - dest array

346

<a name="l00319"></a>00319 \param tmatrix - source bit-slice matrix

347

<a name="l00320"></a>00320

348

<a name="l00321"></a>00321 */

349

<a name="l00322"></a>00322 template<typename T, unsigned BPC, unsigned BPS>

350

<a name="l00323"></a><a class="code" href="a00116.html#a089ac7cd17ddca4bf3c661c96f749f3f">00323</a> void <a class="code" href="a00116.html#a089ac7cd17ddca4bf3c661c96f749f3f" title="Restore bit array from the transposition matrix T - array type (any int) BPC - bit...">vect_bit_trestore</a>(const T <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[BPC][BPS],

351

<a name="l00324"></a>00324 T* arr)

352

<a name="l00325"></a>00325 {

353

<a name="l00326"></a>00326 unsigned col = 0;

354

<a name="l00327"></a>00327 for (unsigned i = 0; i < BPS; ++i)

355

<a name="l00328"></a>00328 {

356

<a name="l00329"></a>00329 for (unsigned j = 0; j < BPC; ++j, ++col)

357

<a name="l00330"></a>00330 {

358

<a name="l00331"></a>00331 arr[col] =

359

<a name="l00332"></a>00332 <a class="code" href="a00033.html">bm::bit_trans_grabber<T, BPC, BPS>::get</a>(<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>, i, j);

360

<a name="l00333"></a>00333 } // for j

361

<a name="l00334"></a>00334 } // for i

362

<a name="l00335"></a>00335 }

363

<a name="l00336"></a>00336

364

<a name="l00337"></a>00337

365

<a name="l00338"></a>00338

366

<a name="l00339"></a>00339 /*!

367

<a name="l00340"></a>00340 \brief Compute pairwise Row x Row Humming distances on plains(rows) of

368

<a name="l00341"></a>00341 the transposed bit block

369

<a name="l00342"></a>00342 \param tmatrix - bit-block transposition matrix (bit-plains)

370

<a name="l00343"></a>00343 \param distance - pairwise NxN Humming distance matrix (diagonal is popcnt)

371

<a name="l00344"></a>00344

372

<a name="l00345"></a>00345 @ingroup bitfunc

373

<a name="l00346"></a>00346 */

374

<a name="l00347"></a>00347 template<typename T, unsigned BPC, unsigned BPS>

375

<a name="l00348"></a><a class="code" href="a00121.html#ga3fe02492f64cd8a9dfbb1a00ec71c0ae">00348</a> void <a class="code" href="a00121.html#ga3fe02492f64cd8a9dfbb1a00ec71c0ae" title="Compute pairwise Row x Row Humming distances on plains(rows) of the transposed bit...">tmatrix_distance</a>(const T <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[BPC][BPS],

376

<a name="l00349"></a>00349 unsigned distance[BPC][BPC])

377

<a name="l00350"></a>00350 {

378

<a name="l00351"></a>00351 for (unsigned i = 0; i < BPC; ++i)

379

<a name="l00352"></a>00352 {

380

<a name="l00353"></a>00353 const T* r1 = <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[i];

381

<a name="l00354"></a>00354 const T* r1_end = r1 + BPS;

382

<a name="l00355"></a>00355 distance[i][i] =

383

<a name="l00356"></a>00356 <a class="code" href="a00121.html#gab30df14a61f036d690c091878feaff1c" title="Bitcount for bit string.">bm::bit_block_calc_count</a>((<a class="code" href="a00116.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>*)r1, (<a class="code" href="a00116.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>*)r1_end);

384

<a name="l00357"></a>00357

385

<a name="l00358"></a>00358 for (unsigned j = i + 1; j < BPC; ++j)

386

<a name="l00359"></a>00359 {

387

<a name="l00360"></a>00360 r1 = <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[i];

388

<a name="l00361"></a>00361 r1_end = r1 + BPS;

389

<a name="l00362"></a>00362 unsigned count = 0;

390

<a name="l00363"></a>00363

391

<a name="l00364"></a>00364 {

392

<a name="l00365"></a>00365 const T* r2 = <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[i];

393

<a name="l00366"></a>00366 const T* r2_end = r2 + BPS;

394

<a name="l00367"></a>00367 const <a class="code" href="a00116.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* r3 = (<a class="code" href="a00116.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>*)(<a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[j]);

395

<a name="l00368"></a>00368 do {

396

<a name="l00369"></a>00369 <a class="code" href="a00121.html#ga967f6a5264f47d8adb93f6bdf8cdc129">BM_INCWORD_BITCOUNT</a>(count, r2[0] ^ r3[0]);

397

<a name="l00370"></a>00370 <a class="code" href="a00121.html#ga967f6a5264f47d8adb93f6bdf8cdc129">BM_INCWORD_BITCOUNT</a>(count, r2[1] ^ r3[1]);

398

<a name="l00371"></a>00371 <a class="code" href="a00121.html#ga967f6a5264f47d8adb93f6bdf8cdc129">BM_INCWORD_BITCOUNT</a>(count, r2[2] ^ r3[2]);

399

<a name="l00372"></a>00372 <a class="code" href="a00121.html#ga967f6a5264f47d8adb93f6bdf8cdc129">BM_INCWORD_BITCOUNT</a>(count, r2[3] ^ r3[3]);

400

<a name="l00373"></a>00373 r2 += 4;

401

<a name="l00374"></a>00374 r3 += 4;

402

<a name="l00375"></a>00375 } while (r2 < r2_end);

403

<a name="l00376"></a>00376 }

404

<a name="l00377"></a>00377 distance[i][j] = count;

405

<a name="l00378"></a>00378 } // for j

406

<a name="l00379"></a>00379 } // for i

407

<a name="l00380"></a>00380 }

408

<a name="l00381"></a>00381

409

<a name="l00382"></a>00382

410

<a name="l00383"></a>00383

411

<a name="l00384"></a><a class="code" href="a00116.html#ae34de9206be7a8aa05db9d5dc38bfc90">00384</a> const unsigned char <a class="code" href="a00116.html#ae34de9206be7a8aa05db9d5dc38bfc90">ibpc_uncompr</a> = 0; ///!< plain uncompressed

412

<a name="l00385"></a><a class="code" href="a00116.html#aaca6d3c887b5b7b66a78e95471f9a326">00385</a> const unsigned char <a class="code" href="a00116.html#aaca6d3c887b5b7b66a78e95471f9a326" title="!&lt; plain uncompressed">ibpc_all_zero</a>= 1; ///!< plain ALL ZERO

413

<a name="l00386"></a><a class="code" href="a00116.html#aa6f59be0b838db693e0f081bcaf750f0">00386</a> const unsigned char <a class="code" href="a00116.html#aa6f59be0b838db693e0f081bcaf750f0" title="!&lt; plain ALL ZERO">ibpc_all_one</a> = 2; ///!< plain ALL ONE

414

<a name="l00387"></a><a class="code" href="a00116.html#a748d4095c39c9372a590b431e0ec17fe">00387</a> const unsigned char <a class="code" href="a00116.html#a748d4095c39c9372a590b431e0ec17fe" title="!&lt; plain ALL ONE">ibpc_equiv</a> = 3; ///!< plain is equal to plain M

415

<a name="l00388"></a><a class="code" href="a00116.html#aa61bf7691d32a9bc7c65c05bb62657e5">00388</a> const unsigned char <a class="code" href="a00116.html#aa61bf7691d32a9bc7c65c05bb62657e5" title="!&lt; plain is equal to plain M">ibpc_close</a> = 4; ///!< plain is close to plain M

416

<a name="l00389"></a>00389

417

<a name="l00390"></a><a class="code" href="a00116.html#ae4f14f0c2c5a9ee277808d36fd94693f">00390</a> const unsigned char <a class="code" href="a00116.html#ae4f14f0c2c5a9ee277808d36fd94693f" title="!&lt; plain is close to plain M">ibpc_end</a> = 8; ///!< ibpc limiter

418

<a name="l00391"></a>00391

419

<a name="l00392"></a>00392

420

<a name="l00393"></a>00393 /*!

421

<a name="l00394"></a>00394 \brief Make a compression descriptor vector for bit-plains

422

<a name="l00395"></a>00395

423

<a name="l00396"></a>00396 \param distance - pairwise distance matrix

424

<a name="l00397"></a>00397 \param pc_vector - OUT compression descriptor vector

425

426

<a name="l00399"></a>00399 pc_vector[] format:

427

<a name="l00400"></a>00400 each element (pc_vector[i]) describes the plain compression:

428

<a name="l00401"></a>00401 first 3 bits - compression code:

429

<a name="l00402"></a>00402 0 - plain uncompressed

430

<a name="l00403"></a>00403 1 - plain is ALL ZERO (000000...)

431

<a name="l00404"></a>00404 2 - plain is ALL ONE (111111...)

432

<a name="l00405"></a>00405 3 - plain is equal to another plain J (5 high bits (max 31))

433

<a name="l00406"></a>00406 4 - plain is close (but not equal) to plain J

434

<a name="l00407"></a>00407 next 5 bits - number of plain used as a XOR expression

435

<a name="l00408"></a>00408 ( compression codes: 3,4 )

436

437

<a name="l00410"></a>00410

438

<a name="l00411"></a>00411 @ingroup bitfunc

439

<a name="l00412"></a>00412 */

440

<a name="l00413"></a>00413 template<typename T, unsigned BPC, unsigned BPS>

441

<a name="l00414"></a><a class="code" href="a00121.html#gabdc11d48fda6a69873eefd219c4b7e75">00414</a> void <a class="code" href="a00121.html#gabdc11d48fda6a69873eefd219c4b7e75" title="!&lt; ibpc limiter">bit_iblock_make_pcv</a>(

442

<a name="l00415"></a>00415 const unsigned distance[BPC][BPC],

443

<a name="l00416"></a>00416 unsigned char* pc_vector)

444

<a name="l00417"></a>00417 {

445

<a name="l00418"></a>00418 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(pc_vector);

446

<a name="l00419"></a>00419

447

<a name="l00420"></a>00420 for (unsigned i = 0; i < BPC; ++i)

448

<a name="l00421"></a>00421 {

449

<a name="l00422"></a>00422 unsigned char pc = <a class="code" href="a00116.html#ae34de9206be7a8aa05db9d5dc38bfc90">ibpc_uncompr</a>;

450

<a name="l00423"></a>00423 unsigned row_bitcount = distance[i][i];

451

<a name="l00424"></a>00424

452

<a name="l00425"></a>00425 const unsigned total_possible_max = sizeof(T)*8*BPS;

453

<a name="l00426"></a>00426 switch (row_bitcount)

454

<a name="l00427"></a>00427 {

455

<a name="l00428"></a>00428 case 0:

456

<a name="l00429"></a>00429 pc_vector[i] = <a class="code" href="a00116.html#aaca6d3c887b5b7b66a78e95471f9a326" title="!&lt; plain uncompressed">ibpc_all_zero</a>;

457

<a name="l00430"></a>00430 continue;

458

<a name="l00431"></a>00431 case total_possible_max:

459

<a name="l00432"></a>00432 pc_vector[i] = <a class="code" href="a00116.html#aa6f59be0b838db693e0f081bcaf750f0" title="!&lt; plain ALL ZERO">ibpc_all_one</a>;

460

<a name="l00433"></a>00433 continue;

461

<a name="l00434"></a>00434 }

462

<a name="l00435"></a>00435

463

<a name="l00436"></a>00436 // Dense-populated set, leave it as is

464

<a name="l00437"></a>00437 if (row_bitcount > total_possible_max/2)

465

<a name="l00438"></a>00438 {

466

<a name="l00439"></a>00439 pc_vector[i] = <a class="code" href="a00116.html#ae34de9206be7a8aa05db9d5dc38bfc90">ibpc_uncompr</a>;

467

<a name="l00440"></a>00440 continue;

468

<a name="l00441"></a>00441 }

469

<a name="l00442"></a>00442

470

<a name="l00443"></a>00443 // scan for the closest neighbor

471

<a name="l00444"></a>00444 //

472

<a name="l00445"></a>00445 unsigned rmin = ~0;

473

<a name="l00446"></a>00446 unsigned rmin_idx = 0;

474

<a name="l00447"></a>00447 for (unsigned j = i + 1; j < BPC; ++j)

475

<a name="l00448"></a>00448 {

476

<a name="l00449"></a>00449 unsigned d = distance[i][j];

477

<a name="l00450"></a>00450 if (d < rmin) // new minimum - closest plain

478

<a name="l00451"></a>00451 {

479

<a name="l00452"></a>00452 if (d == 0) // plain is complete duplicate of j

480

<a name="l00453"></a>00453 {

481

<a name="l00454"></a>00454 pc = <a class="code" href="a00116.html#a748d4095c39c9372a590b431e0ec17fe" title="!&lt; plain ALL ONE">ibpc_equiv</a> | (j << 3);

482

<a name="l00455"></a>00455 break;

483

<a name="l00456"></a>00456 }

484

<a name="l00457"></a>00457 rmin = d; rmin_idx = j;

485

<a name="l00458"></a>00458 }

486

<a name="l00459"></a>00459 } // for j

487

<a name="l00460"></a>00460

488

<a name="l00461"></a>00461 if ((pc == 0) && rmin_idx && (rmin < row_bitcount)) // neighbor found

489

<a name="l00462"></a>00462 {

490

<a name="l00463"></a>00463 pc = <a class="code" href="a00116.html#aa61bf7691d32a9bc7c65c05bb62657e5" title="!&lt; plain is equal to plain M">ibpc_close</a> | (rmin_idx << 3);

491

<a name="l00464"></a>00464 }

492

<a name="l00465"></a>00465 pc_vector[i] = pc;

493

<a name="l00466"></a>00466 } // for i

494

<a name="l00467"></a>00467 }

495

<a name="l00468"></a>00468

496

<a name="l00469"></a>00469

497

<a name="l00470"></a>00470 /*!

498

<a name="l00471"></a>00471 \brief Compute number of ibpc codes in pc_vector

499

<a name="l00472"></a>00472 */

500

<a name="l00473"></a>00473 inline

501

<a name="l00474"></a><a class="code" href="a00116.html#adfae226f696ef821c7d351216c00fe0d">00474</a> void <a class="code" href="a00116.html#adfae226f696ef821c7d351216c00fe0d" title="Compute number of ibpc codes in pc_vector.">bit_iblock_pcv_stat</a>(const unsigned char* BMRESTRICT pc_vector,

502

<a name="l00475"></a>00475 const unsigned char* BMRESTRICT pc_vector_end,

503

<a name="l00476"></a>00476 unsigned* BMRESTRICT pc_vector_stat

504

<a name="l00477"></a>00477 )

505

<a name="l00478"></a>00478 {

506

<a name="l00479"></a>00479 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(pc_vector_stat);

507

<a name="l00480"></a>00480 // pc_vector_stat MUST be assigned to 0 before

508

<a name="l00481"></a>00481 do

509

<a name="l00482"></a>00482 {

510

<a name="l00483"></a>00483 unsigned ibpc = *pc_vector & 7;

511

<a name="l00484"></a>00484 ++(pc_vector_stat[ibpc]);

512

<a name="l00485"></a>00485 } while (++pc_vector < pc_vector_end);

513

<a name="l00486"></a>00486 }

514

<a name="l00487"></a>00487

515

<a name="l00488"></a>00488

516

<a name="l00489"></a>00489

517

<a name="l00490"></a>00490 /**

518

<a name="l00491"></a>00491 \brief Matrix reduction based on transformation pc vector

519

<a name="l00492"></a>00492 */

520

<a name="l00493"></a>00493 inline

521

<a name="l00494"></a><a class="code" href="a00116.html#a62808b64adfcf2a7e610a4f713f470c0">00494</a> void <a class="code" href="a00116.html#a62808b64adfcf2a7e610a4f713f470c0" title="Matrix reduction based on transformation pc vector.">bit_iblock_reduce</a>(

522

<a name="l00495"></a>00495 const unsigned <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[<a class="code" href="a00116.html#a3428cf384446982017ba9ee68152d238">bm::set_block_plain_cnt</a>][<a class="code" href="a00116.html#a35780565f6d8f2831ebff8877d3ba662">bm::set_block_plain_size</a>],

523

<a name="l00496"></a>00496 const unsigned char* BMRESTRICT pc_vector,

524

<a name="l00497"></a>00497 const unsigned char* BMRESTRICT pc_vector_end,

525

<a name="l00498"></a>00498 unsigned tmatrix_out[<a class="code" href="a00116.html#a3428cf384446982017ba9ee68152d238">bm::set_block_plain_cnt</a>][bm::set_block_plain_size])

526

<a name="l00499"></a>00499 {

527

<a name="l00500"></a>00500 ::memset(tmatrix_out, 0, sizeof(tmatrix_out));

528

<a name="l00501"></a>00501

529

<a name="l00502"></a>00502 unsigned row = 0;

530

<a name="l00503"></a>00503 do

531

<a name="l00504"></a>00504 {

532

<a name="l00505"></a>00505 unsigned ibpc = *pc_vector & 7;

533

<a name="l00506"></a>00506 unsigned n_row = *pc_vector >> 3;

534

<a name="l00507"></a>00507

535

<a name="l00508"></a>00508 switch(ibpc)

536

<a name="l00509"></a>00509 {

537

<a name="l00510"></a>00510 case <a class="code" href="a00116.html#ae34de9206be7a8aa05db9d5dc38bfc90">bm::ibpc_uncompr</a>:

538

<a name="l00511"></a>00511 {

539

<a name="l00512"></a>00512 const unsigned* r1 = <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[row];

540

<a name="l00513"></a>00513 unsigned* r_out = tmatrix_out[row];

541

<a name="l00514"></a>00514 for (unsigned i = 0; i < bm::set_block_plain_size; ++i)

542

<a name="l00515"></a>00515 {

543

<a name="l00516"></a>00516 r_out[i] = r1[i];

544

<a name="l00517"></a>00517 }

545

<a name="l00518"></a>00518 }

546

<a name="l00519"></a>00519 break;

547

<a name="l00520"></a>00520 case <a class="code" href="a00116.html#aaca6d3c887b5b7b66a78e95471f9a326" title="!&lt; plain uncompressed">bm::ibpc_all_zero</a>:

548

<a name="l00521"></a>00521 break;

549

<a name="l00522"></a>00522 case <a class="code" href="a00116.html#aa6f59be0b838db693e0f081bcaf750f0" title="!&lt; plain ALL ZERO">bm::ibpc_all_one</a>:

550

<a name="l00523"></a>00523 break;

551

<a name="l00524"></a>00524 case <a class="code" href="a00116.html#a748d4095c39c9372a590b431e0ec17fe" title="!&lt; plain ALL ONE">bm::ibpc_equiv</a>:

552

<a name="l00525"></a>00525 break;

553

<a name="l00526"></a>00526 case <a class="code" href="a00116.html#aa61bf7691d32a9bc7c65c05bb62657e5" title="!&lt; plain is equal to plain M">bm::ibpc_close</a>:

554

<a name="l00527"></a>00527 {

555

<a name="l00528"></a>00528 const unsigned* r1 = <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[row];

556

<a name="l00529"></a>00529 const unsigned* r2 = <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>[n_row];

557

<a name="l00530"></a>00530 unsigned* r_out = tmatrix_out[row];

558

<a name="l00531"></a>00531 for (unsigned i = 0; i < bm::set_block_plain_size; ++i)

559

<a name="l00532"></a>00532 {

560

<a name="l00533"></a>00533 r_out[i] = r1[i] ^ r2[i];

561

<a name="l00534"></a>00534 } // for

562

<a name="l00535"></a>00535 }

563

<a name="l00536"></a>00536 break;

564

<a name="l00537"></a>00537 default:

565

<a name="l00538"></a>00538 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(0);

566

<a name="l00539"></a>00539 break;

567

<a name="l00540"></a>00540 } // switch

568

<a name="l00541"></a>00541 ++row;

569

<a name="l00542"></a>00542 } while (++pc_vector < pc_vector_end);

570

<a name="l00543"></a>00543

571

<a name="l00544"></a>00544 }

572

<a name="l00545"></a>00545

573

<a name="l00546"></a>00546 /**

574

<a name="l00547"></a>00547 \brief Transposed Matrix reduction based on transformation pc vector

575

<a name="l00548"></a>00548 */

576

<a name="l00549"></a>00549 template<class TMatrix>

577

<a name="l00550"></a><a class="code" href="a00116.html#a336ed7eb10da60438793f0ecff0fb7b1">00550</a> void <a class="code" href="a00116.html#a336ed7eb10da60438793f0ecff0fb7b1" title="Transposed Matrix reduction based on transformation pc vector.">tmatrix_reduce</a>(TMatrix& <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>,

578

<a name="l00551"></a>00551 const unsigned char* pc_vector,

579

<a name="l00552"></a>00552 const unsigned effective_cols)

580

<a name="l00553"></a>00553 {

581

<a name="l00554"></a>00554 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(pc_vector);

582

<a name="l00555"></a>00555

583

<a name="l00556"></a>00556 typedef typename TMatrix::value_type value_type;

584

<a name="l00557"></a>00557

585

<a name="l00558"></a>00558 const unsigned char* pc_vector_end = pc_vector + tmatrix.rows();

586

<a name="l00559"></a>00559 unsigned row = 0;

587

<a name="l00560"></a>00560 unsigned cols = effective_cols ? effective_cols : tmatrix.cols();

588

<a name="l00561"></a>00561

589

<a name="l00562"></a>00562 do

590

<a name="l00563"></a>00563 {

591

<a name="l00564"></a>00564 unsigned ibpc = *pc_vector & 7;

592

<a name="l00565"></a>00565 switch(ibpc)

593

<a name="l00566"></a>00566 {

594

<a name="l00567"></a>00567 case <a class="code" href="a00116.html#ae34de9206be7a8aa05db9d5dc38bfc90">bm::ibpc_uncompr</a>:

595

<a name="l00568"></a>00568 case <a class="code" href="a00116.html#aaca6d3c887b5b7b66a78e95471f9a326" title="!&lt; plain uncompressed">bm::ibpc_all_zero</a>:

596

<a name="l00569"></a>00569 case <a class="code" href="a00116.html#aa6f59be0b838db693e0f081bcaf750f0" title="!&lt; plain ALL ZERO">bm::ibpc_all_one</a>:

597

<a name="l00570"></a>00570 case <a class="code" href="a00116.html#a748d4095c39c9372a590b431e0ec17fe" title="!&lt; plain ALL ONE">bm::ibpc_equiv</a>:

598

<a name="l00571"></a>00571 break;

599

<a name="l00572"></a>00572 case <a class="code" href="a00116.html#aa61bf7691d32a9bc7c65c05bb62657e5" title="!&lt; plain is equal to plain M">bm::ibpc_close</a>:

600

<a name="l00573"></a>00573 {

601

<a name="l00574"></a>00574 unsigned n_row = *pc_vector >> 3;

602

<a name="l00575"></a>00575 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(n_row > row);

603

<a name="l00576"></a>00576

604

<a name="l00577"></a>00577 value_type* r1 = tmatrix.row(row);

605

<a name="l00578"></a>00578 const value_type* r2 = tmatrix.row(n_row);

606

<a name="l00579"></a>00579 for (unsigned i = 0; i < cols; ++i)

607

<a name="l00580"></a>00580 {

608

<a name="l00581"></a>00581 r1[i] ^= r2[i];

609

<a name="l00582"></a>00582 } // for

610

<a name="l00583"></a>00583 }

611

<a name="l00584"></a>00584 break;

612

<a name="l00585"></a>00585 default:

613

<a name="l00586"></a>00586 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(0);

614

<a name="l00587"></a>00587 break;

615

<a name="l00588"></a>00588 } // switch

616

<a name="l00589"></a>00589 ++row;

617

<a name="l00590"></a>00590 } while (++pc_vector < pc_vector_end);

618

<a name="l00591"></a>00591 }

619

<a name="l00592"></a>00592

620

<a name="l00593"></a>00593 /**

621

<a name="l00594"></a>00594 \brief Transposed Matrix restore based on transformation pc vector

622

<a name="l00595"></a>00595 */

623

<a name="l00596"></a>00596 template<class TMatrix>

624

<a name="l00597"></a><a class="code" href="a00116.html#ab7544e494744b2c0b265ab7d81f766b8">00597</a> void <a class="code" href="a00116.html#ab7544e494744b2c0b265ab7d81f766b8" title="Transposed Matrix restore based on transformation pc vector.">tmatrix_restore</a>(TMatrix& <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>,

625

<a name="l00598"></a>00598 const unsigned char* pc_vector,

626

<a name="l00599"></a>00599 const unsigned effective_cols)

627

<a name="l00600"></a>00600 {

628

<a name="l00601"></a>00601 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(pc_vector);

629

<a name="l00602"></a>00602

630

<a name="l00603"></a>00603 typedef typename TMatrix::value_type value_type;

631

<a name="l00604"></a>00604

632

<a name="l00605"></a>00605 unsigned cols = effective_cols ? effective_cols : tmatrix.cols();

633

<a name="l00606"></a>00606 for (int row = tmatrix.rows()-1; row >= 0; --row)

634

<a name="l00607"></a>00607 {

635

<a name="l00608"></a>00608 unsigned ibpc = pc_vector[row] & 7;

636

<a name="l00609"></a>00609 int n_row = pc_vector[row] >> 3;

637

<a name="l00610"></a>00610

638

<a name="l00611"></a>00611 value_type* r1 = tmatrix.row(row);

639

<a name="l00612"></a>00612

640

<a name="l00613"></a>00613 switch(ibpc)

641

<a name="l00614"></a>00614 {

642

<a name="l00615"></a>00615 case <a class="code" href="a00116.html#ae34de9206be7a8aa05db9d5dc38bfc90">bm::ibpc_uncompr</a>:

643

<a name="l00616"></a>00616 break;

644

<a name="l00617"></a>00617 case <a class="code" href="a00116.html#aaca6d3c887b5b7b66a78e95471f9a326" title="!&lt; plain uncompressed">bm::ibpc_all_zero</a>:

645

<a name="l00618"></a>00618 for (unsigned i = 0; i < cols; ++i)

646

<a name="l00619"></a>00619 r1[i] = 0;

647

<a name="l00620"></a>00620 break;

648

<a name="l00621"></a>00621 case <a class="code" href="a00116.html#aa6f59be0b838db693e0f081bcaf750f0" title="!&lt; plain ALL ZERO">bm::ibpc_all_one</a>:

649

<a name="l00622"></a>00622 for (unsigned i = 0; i < cols; ++i)

650

<a name="l00623"></a>00623 r1[i] = ~0;

651

<a name="l00624"></a>00624 break;

652

<a name="l00625"></a>00625 case <a class="code" href="a00116.html#a748d4095c39c9372a590b431e0ec17fe" title="!&lt; plain ALL ONE">bm::ibpc_equiv</a>:

653

<a name="l00626"></a>00626 {

654

<a name="l00627"></a>00627 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(n_row > row);

655

<a name="l00628"></a>00628 const value_type* r2 = tmatrix.row(n_row);

656

<a name="l00629"></a>00629 for (unsigned i = 0; i < cols; ++i)

657

<a name="l00630"></a>00630 r1[i] = r2[i];

658

<a name="l00631"></a>00631 }

659

<a name="l00632"></a>00632 break;

660

<a name="l00633"></a>00633 case <a class="code" href="a00116.html#aa61bf7691d32a9bc7c65c05bb62657e5" title="!&lt; plain is equal to plain M">bm::ibpc_close</a>:

661

<a name="l00634"></a>00634 {

662

<a name="l00635"></a>00635 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(n_row > row);

663

<a name="l00636"></a>00636 const value_type* r2 = tmatrix.row(n_row);

664

<a name="l00637"></a>00637 for (unsigned i = 0; i < cols; ++i)

665

<a name="l00638"></a>00638 r1[i] ^= r2[i];

666

<a name="l00639"></a>00639 }

667

<a name="l00640"></a>00640 break;

668

<a name="l00641"></a>00641 default:

669

<a name="l00642"></a>00642 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(0);

670

<a name="l00643"></a>00643 break;

671

<a name="l00644"></a>00644 } // switch

672

<a name="l00645"></a>00645 } // for

673

<a name="l00646"></a>00646

674

<a name="l00647"></a>00647 }

675

<a name="l00648"></a>00648

676

<a name="l00649"></a>00649

677

<a name="l00650"></a>00650

678

<a name="l00651"></a>00651 /**

679

<a name="l00652"></a>00652 \brief Copy GAP block body to bit block with DGap transformation

680

<a name="l00653"></a>00653 \internal

681

<a name="l00654"></a>00654 */

682

<a name="l00655"></a>00655 template<typename GT, typename BT>

683

<a name="l00656"></a><a class="code" href="a00116.html#a76724fb233f93c15146641482311ce28">00656</a> void <a class="code" href="a00116.html#a76724fb233f93c15146641482311ce28" title="Copy GAP block body to bit block with DGap transformation.">gap_2_bitblock</a>(const GT* BMRESTRICT gap_buf,

684

<a name="l00657"></a>00657 BT* BMRESTRICT block,

685

<a name="l00658"></a>00658 unsigned block_size)

686

<a name="l00659"></a>00659 {

687

<a name="l00660"></a>00660 GT* dgap_buf = (GT*) block;

688

<a name="l00661"></a>00661 BT* block_end = block + block_size;

689

<a name="l00662"></a>00662

690

<a name="l00663"></a>00663 GT* dgap_end = gap_2_dgap<GT>(gap_buf, dgap_buf, false);

691

<a name="l00664"></a>00664 GT* block_end2 = (GT*) block_end;

692

<a name="l00665"></a>00665

693

<a name="l00666"></a>00666 // zero the tail memory

694

<a name="l00667"></a>00667 for ( ;dgap_end < block_end2; ++dgap_end)

695

<a name="l00668"></a>00668 {

696

<a name="l00669"></a>00669 *dgap_end = 0;

697

<a name="l00670"></a>00670 }

698

<a name="l00671"></a>00671 }

699

<a name="l00672"></a>00672

700

<a name="l00673"></a>00673 /**

701

<a name="l00674"></a>00674 @brief Compute t-matrix rows statistics used for compression

702

<a name="l00675"></a>00675

703

<a name="l00676"></a>00676 @param tmatrix - transposed matrix

704

<a name="l00677"></a>00677 @param pc_vector - row content vector

705

<a name="l00678"></a>00678 @param rstat - output row vector

706

<a name="l00679"></a>00679

707

<a name="l00680"></a>00680 @internal

708

<a name="l00681"></a>00681 */

709

<a name="l00682"></a>00682 template<class TMatrix>

710

<a name="l00683"></a><a class="code" href="a00116.html#a3788dd32c39556f0aef90b50e5a5e62c">00683</a> void <a class="code" href="a00116.html#a3788dd32c39556f0aef90b50e5a5e62c" title="Compute t-matrix rows statistics used for compression.">compute_tmatrix_rstat</a>(const TMatrix& <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>,

711

<a name="l00684"></a>00684 const unsigned char* pc_vector,

712

<a name="l00685"></a>00685 typename TMatrix::rstat* rstat,

713

<a name="l00686"></a>00686 unsigned effective_cols)

714

<a name="l00687"></a>00687 {

715

<a name="l00688"></a>00688 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(rstat);

716

<a name="l00689"></a>00689 typedef typename TMatrix::value_type value_type;

717

<a name="l00690"></a>00690

718

<a name="l00691"></a>00691 unsigned cols = effective_cols ? effective_cols : tmatrix.cols();

719

<a name="l00692"></a>00692 //unsigned cols = tmatrix.cols();

720

<a name="l00693"></a>00693 unsigned rows = tmatrix.rows();

721

<a name="l00694"></a>00694

722

<a name="l00695"></a>00695 for (unsigned i = 0; i < rows; ++i)

723

<a name="l00696"></a>00696 {

724

<a name="l00697"></a>00697 unsigned ibpc = pc_vector[i] & 7;

725

<a name="l00698"></a>00698 switch(ibpc)

726

<a name="l00699"></a>00699 {

727

<a name="l00700"></a>00700 case <a class="code" href="a00116.html#aaca6d3c887b5b7b66a78e95471f9a326" title="!&lt; plain uncompressed">bm::ibpc_all_zero</a>:

728

<a name="l00701"></a>00701 case <a class="code" href="a00116.html#aa6f59be0b838db693e0f081bcaf750f0" title="!&lt; plain ALL ZERO">bm::ibpc_all_one</a>:

729

<a name="l00702"></a>00702 case <a class="code" href="a00116.html#a748d4095c39c9372a590b431e0ec17fe" title="!&lt; plain ALL ONE">bm::ibpc_equiv</a>:

730

<a name="l00703"></a>00703 rstat[i].bit_count = rstat[i].gap_count = 0;

731

<a name="l00704"></a>00704 rstat[i].best_rep = <a class="code" href="a00116.html#a593916a103395805070a3200720c6416a11f970b705c57a0572043e5cc5e2e333" title="Simple bitset.">bm::set_bitset</a>;

732

<a name="l00705"></a>00705 break;

733

<a name="l00706"></a>00706 case <a class="code" href="a00116.html#ae34de9206be7a8aa05db9d5dc38bfc90">bm::ibpc_uncompr</a>:

734

<a name="l00707"></a>00707 case <a class="code" href="a00116.html#aa61bf7691d32a9bc7c65c05bb62657e5" title="!&lt; plain is equal to plain M">bm::ibpc_close</a>:

735

<a name="l00708"></a>00708 {

736

<a name="l00709"></a>00709 const value_type* r1 = tmatrix.row(i);

737

<a name="l00710"></a>00710 const value_type* r1_end = r1 + cols;

738

<a name="l00711"></a>00711 // TODO: find how to deal with the potentially incorrect type-cast

739

<a name="l00712"></a>00712 <a class="code" href="a00116.html#ae2222be6fd45b4bab5100ce70e3b4f88">bm::bit_count_change32</a>((<a class="code" href="a00116.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>*)r1, (<a class="code" href="a00116.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>*)r1_end,

740

<a name="l00713"></a>00713 &rstat[i].bit_count, &rstat[i].gap_count);

741

<a name="l00714"></a>00714

742

<a name="l00715"></a>00715 const unsigned bitset_size = sizeof(value_type) * cols;

743

<a name="l00716"></a>00716 const unsigned total_possible_max_bits = sizeof(value_type)*8*cols;

744

<a name="l00717"></a>00717

745

<a name="l00718"></a>00718 rstat[i].best_rep =

746

<a name="l00719"></a>00719 <a class="code" href="a00121.html#ga20610fae6b0de84957b74ed17429667f" title="Choose best representation for a bit-block.">bm::best_representation</a>(rstat[i].bit_count,

747

<a name="l00720"></a>00720 total_possible_max_bits,

748

<a name="l00721"></a>00721 rstat[i].gap_count,

749

<a name="l00722"></a>00722 bitset_size);

750

<a name="l00723"></a>00723

751

<a name="l00724"></a>00724 }

752

<a name="l00725"></a>00725 break;

753

<a name="l00726"></a>00726 default:

754

<a name="l00727"></a>00727 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(0);

755

<a name="l00728"></a>00728 break;

756

<a name="l00729"></a>00729 } // switch

757

<a name="l00730"></a>00730

758

<a name="l00731"></a>00731 } // for

759

<a name="l00732"></a>00732 }

760

<a name="l00733"></a>00733

761

<a name="l00734"></a>00734

762

<a name="l00735"></a>00735

763

<a name="l00736"></a>00736 /**

764

<a name="l00737"></a>00737 \brief Compute effective right column border of the t-matrix

765

<a name="l00738"></a>00738 \internal

766

<a name="l00739"></a>00739 */

767

<a name="l00740"></a>00740 template<typename TM>

768

<a name="l00741"></a><a class="code" href="a00116.html#af92597461aff2926f9adcbf51bac98f9">00741</a> unsigned <a class="code" href="a00116.html#af92597461aff2926f9adcbf51bac98f9" title="Compute effective right column border of the t-matrix.">find_effective_columns</a>(const TM& <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a>)

769

<a name="l00742"></a>00742 {

770

<a name="l00743"></a>00743 // TODO: need optimization in order not to scan the whole space

771

<a name="l00744"></a>00744 unsigned col = 1;

772

<a name="l00745"></a>00745 for (unsigned i = 0; i < tmatrix.rows(); ++i)

773

<a name="l00746"></a>00746 {

774

<a name="l00747"></a>00747 const typename TM::value_type* row = tmatrix.value[i];

775

<a name="l00748"></a>00748 for (unsigned j = 0; j < tmatrix.cols(); ++j)

776

<a name="l00749"></a>00749 {

777

<a name="l00750"></a>00750 if (row[j] != 0 && j > col)

778

<a name="l00751"></a>00751 {

779

<a name="l00752"></a>00752 col = j;

780

<a name="l00753"></a>00753 }

781

<a name="l00754"></a>00754 }

782

<a name="l00755"></a>00755 }

783

<a name="l00756"></a>00756 return col;

784

<a name="l00757"></a>00757 }

785

<a name="l00758"></a>00758

786

<a name="l00759"></a>00759

787

<a name="l00760"></a>00760 /**

788

<a name="l00761"></a>00761 \brief Bit-plain splicing of a GAP block

789

<a name="l00762"></a>00762

790

<a name="l00763"></a>00763 GT - gap word type

791

<a name="l00764"></a>00764 BT - block word type

792

<a name="l00765"></a>00765 BLOCK_SIZE - bit block size in words (works as a transposition basis)

793

<a name="l00766"></a>00766

794

<a name="l00767"></a>00767 @internal

795

<a name="l00768"></a>00768 */

796

<a name="l00769"></a>00769 template<typename GT, typename BT, unsigned BLOCK_SIZE>

797

<a name="l00770"></a><a class="code" href="a00069.html">00770</a> class <a class="code" href="a00069.html" title="Bit-plain splicing of a GAP block.">gap_transpose_engine</a>

798

<a name="l00771"></a>00771 {

799

<a name="l00772"></a>00772 public:

800

<a name="l00773"></a>00773 /// cryptic calculation of equivalent size for the transpose matrix

801

<a name="l00774"></a>00774 /// based on BLOCK_SIZE and sizeof(GT)(16)

802

<a name="l00775"></a>00775 ///

803

<a name="l00776"></a>00776 /// matrix[size_of_gap*8][(Size_block_in_bytes / size_of_gap) / number_of_planes)]

804

<a name="l00777"></a>00777 typedef

805

<a name="l00778"></a>00778 <a class="code" href="a00087.html" title="Mini-matrix for bit transposition purposes.">tmatrix</a><GT, sizeof(GT)*8,

806

<a name="l00779"></a>00779 (((BLOCK_SIZE * sizeof(unsigned)) / (sizeof(GT))) / (sizeof(GT) * 8))>

807

<a name="l00780"></a><a class="code" href="a00069.html#aebedc43b623e92c51d273654aa437dbb">00780</a> <a class="code" href="a00069.html#aebedc43b623e92c51d273654aa437dbb" title="cryptic calculation of equivalent size for the transpose matrix based on BLOCK_SIZE...">tmatrix_type</a>;

808

<a name="l00781"></a>00781

809

<a name="l00782"></a><a class="code" href="a00069.html#af5cb0321f7461d6c072dd13ac5b77a3a">00782</a> <a class="code" href="a00069.html#af5cb0321f7461d6c072dd13ac5b77a3a">gap_transpose_engine</a>() : <a class="code" href="a00069.html#acaded7f30ccbc5585749bdb03a441ab0">eff_cols_</a>(0)

810

<a name="l00783"></a>00783 {}

811

<a name="l00784"></a>00784

812

<a name="l00785"></a>00785 /// Transpose GAP block through a temp. block of aligned(!) memory

813

<a name="l00786"></a>00786 ///

814

<a name="l00787"></a><a class="code" href="a00069.html#aa574587865df9a653c25b3b14e52e356">00787</a> void <a class="code" href="a00069.html#aa574587865df9a653c25b3b14e52e356" title="Transpose GAP block through a temp.">transpose</a>(const GT* BMRESTRICT gap_buf,

815

<a name="l00788"></a>00788 BT* BMRESTRICT tmp_block)

816

<a name="l00789"></a>00789 {

817

<a name="l00790"></a>00790 const unsigned arr_size = BLOCK_SIZE * sizeof(unsigned) / sizeof(GT);

818

<a name="l00791"></a>00791

819

<a name="l00792"></a>00792 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(sizeof(<a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>.value) == tmatrix_type::n_columns *

820

<a name="l00793"></a>00793 tmatrix_type::n_rows * sizeof(GT));

821

<a name="l00794"></a>00794

822

<a name="l00795"></a>00795 // load all GAP as D-GAP(but not head word) into aligned bit-block

823

<a name="l00796"></a>00796 <a class="code" href="a00116.html#a76724fb233f93c15146641482311ce28" title="Copy GAP block body to bit block with DGap transformation.">gap_2_bitblock</a>(gap_buf, tmp_block, BLOCK_SIZE);

824

<a name="l00797"></a>00797

825

<a name="l00798"></a>00798 // transpose

826

<a name="l00799"></a>00799 vect_bit_transpose<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>

827

<a name="l00800"></a>00800 ((GT*)tmp_block, arr_size, <a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>.value);

828

<a name="l00801"></a>00801

829

<a name="l00802"></a>00802 // calculate number of non-zero columns

830

<a name="l00803"></a>00803 <a class="code" href="a00069.html#acaded7f30ccbc5585749bdb03a441ab0">eff_cols_</a> = <a class="code" href="a00116.html#af92597461aff2926f9adcbf51bac98f9" title="Compute effective right column border of the t-matrix.">find_effective_columns</a>(<a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>);

831

<a name="l00804"></a>00804 }

832

<a name="l00805"></a>00805

833

<a name="l00806"></a>00806 /// Transpose array of shorts

834

<a name="l00807"></a>00807 ///

835

<a name="l00808"></a><a class="code" href="a00069.html#a429f1a0070d6d8b59a4dfb0f047219ea">00808</a> void <a class="code" href="a00069.html#aa574587865df9a653c25b3b14e52e356" title="Transpose GAP block through a temp.">transpose</a>(const GT* BMRESTRICT garr,

836

<a name="l00809"></a>00809 unsigned garr_size,

837

<a name="l00810"></a>00810 BT* BMRESTRICT tmp_block)

838

<a name="l00811"></a>00811 {

839

<a name="l00812"></a>00812 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(garr_size);

840

<a name="l00813"></a>00813

841

<a name="l00814"></a>00814 <a class="code" href="a00121.html#gaada8b13c35acd8df90129b45edcfc5de" title="Bitblock memset operation.">bit_block_set</a>(tmp_block, 0);

842

<a name="l00815"></a>00815 ::memcpy(tmp_block, garr, sizeof(GT)*garr_size);

843

<a name="l00816"></a>00816

844

<a name="l00817"></a>00817 const unsigned arr_size = BLOCK_SIZE * sizeof(unsigned) / sizeof(GT);

845

<a name="l00818"></a>00818 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(sizeof(<a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>.value) == tmatrix_type::n_columns *

846

<a name="l00819"></a>00819 tmatrix_type::n_rows * sizeof(GT));

847

<a name="l00820"></a>00820 // transpose

848

<a name="l00821"></a>00821 vect_bit_transpose<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>

849

<a name="l00822"></a>00822 ((GT*)tmp_block, arr_size, <a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>.value);

850

<a name="l00823"></a>00823

851

<a name="l00824"></a>00824 // calculate number of non-zero columns

852

<a name="l00825"></a>00825 <a class="code" href="a00069.html#acaded7f30ccbc5585749bdb03a441ab0">eff_cols_</a> = <a class="code" href="a00116.html#af92597461aff2926f9adcbf51bac98f9" title="Compute effective right column border of the t-matrix.">find_effective_columns</a>(<a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>);

853

<a name="l00826"></a>00826

854

<a name="l00827"></a>00827 }

855

<a name="l00828"></a>00828

856

<a name="l00829"></a><a class="code" href="a00069.html#a1964c71e595184b1f3b0a85713ec6e54">00829</a> void <a class="code" href="a00069.html#a1964c71e595184b1f3b0a85713ec6e54">compute_distance_matrix</a>()

857

<a name="l00830"></a>00830 {

858

<a name="l00831"></a>00831 <a class="code" href="a00121.html#ga3fe02492f64cd8a9dfbb1a00ec71c0ae" title="Compute pairwise Row x Row Humming distances on plains(rows) of the transposed bit...">tmatrix_distance</a><typename tmatrix_type::value_type,

859

<a name="l00832"></a>00832 tmatrix_type::n_rows, tmatrix_type::n_columns>

860

<a name="l00833"></a>00833 (<a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>.value, <a class="code" href="a00069.html#ac0b8879d3154afe10fcd8a4725f3cbc1">distance_</a>);

861

<a name="l00834"></a>00834

862

<a name="l00835"></a>00835 // make compression descriptor vector and statistics vector

863

<a name="l00836"></a>00836 <a class="code" href="a00121.html#gabdc11d48fda6a69873eefd219c4b7e75" title="!&lt; ibpc limiter">bit_iblock_make_pcv</a><unsigned char,

864

<a name="l00837"></a>00837 tmatrix_type::n_rows, tmatrix_type::n_columns>

865

<a name="l00838"></a>00838 (<a class="code" href="a00069.html#ac0b8879d3154afe10fcd8a4725f3cbc1">distance_</a>, <a class="code" href="a00069.html#a6fdb1d059dd9e18596740159132e7a16">pc_vector_</a>);

866

<a name="l00839"></a>00839

867

<a name="l00840"></a>00840 <a class="code" href="a00116.html#adfae226f696ef821c7d351216c00fe0d" title="Compute number of ibpc codes in pc_vector.">bit_iblock_pcv_stat</a>(<a class="code" href="a00069.html#a6fdb1d059dd9e18596740159132e7a16">pc_vector_</a>,

868

<a name="l00841"></a>00841 <a class="code" href="a00069.html#a6fdb1d059dd9e18596740159132e7a16">pc_vector_</a> + tmatrix_type::n_rows,

869

<a name="l00842"></a>00842 <a class="code" href="a00069.html#a443d2f744a1bb123907ce7db644deb13">pc_vector_stat_</a>);

870

<a name="l00843"></a>00843 }

871

<a name="l00844"></a>00844

872

<a name="l00845"></a><a class="code" href="a00069.html#a2a0802867d2c823b5949020e90444946">00845</a> void <a class="code" href="a00069.html#a2a0802867d2c823b5949020e90444946">reduce</a>()

873

<a name="l00846"></a>00846 {

874

<a name="l00847"></a>00847 <a class="code" href="a00116.html#a336ed7eb10da60438793f0ecff0fb7b1" title="Transposed Matrix reduction based on transformation pc vector.">tmatrix_reduce</a>(<a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>, <a class="code" href="a00069.html#a6fdb1d059dd9e18596740159132e7a16">pc_vector_</a>, <a class="code" href="a00069.html#acaded7f30ccbc5585749bdb03a441ab0">eff_cols_</a>);

875

<a name="l00848"></a>00848 <a class="code" href="a00116.html#a3788dd32c39556f0aef90b50e5a5e62c" title="Compute t-matrix rows statistics used for compression.">compute_tmatrix_rstat</a>(<a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>, <a class="code" href="a00069.html#a6fdb1d059dd9e18596740159132e7a16">pc_vector_</a>, <a class="code" href="a00069.html#ab6cfa9ccf0fbdc192ecbbd289d9df117">rstat_vector_</a>, <a class="code" href="a00069.html#acaded7f30ccbc5585749bdb03a441ab0">eff_cols_</a>);

876

<a name="l00849"></a>00849 }

877

<a name="l00850"></a>00850

878

<a name="l00851"></a><a class="code" href="a00069.html#a622ccf60bb1ae740f974d45e5b5a5597">00851</a> void <a class="code" href="a00069.html#a622ccf60bb1ae740f974d45e5b5a5597">restore</a>()

879

<a name="l00852"></a>00852 {

880

<a name="l00853"></a>00853 <a class="code" href="a00116.html#ab7544e494744b2c0b265ab7d81f766b8" title="Transposed Matrix restore based on transformation pc vector.">tmatrix_restore</a>(<a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>, <a class="code" href="a00069.html#a6fdb1d059dd9e18596740159132e7a16">pc_vector_</a>, <a class="code" href="a00069.html#acaded7f30ccbc5585749bdb03a441ab0">eff_cols_</a>);

881

<a name="l00854"></a>00854 }

882

<a name="l00855"></a>00855

883

<a name="l00856"></a>00856

884

<a name="l00857"></a>00857 /// Restore GAP block from the transposed matrix

885

<a name="l00858"></a>00858 ///

886

<a name="l00859"></a><a class="code" href="a00069.html#a5d7e91d9440a38520f180c15bed36250">00859</a> void <a class="code" href="a00069.html#a5d7e91d9440a38520f180c15bed36250" title="Restore GAP block from the transposed matrix.">trestore</a>(GT gap_head,

887

<a name="l00860"></a>00860 GT* BMRESTRICT gap_buf,

888

<a name="l00861"></a>00861 BT* BMRESTRICT tmp_block)

889

<a name="l00862"></a>00862 {

890

<a name="l00863"></a>00863 <a class="code" href="a00093.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(sizeof(<a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>.value) == tmatrix_type::n_columns *

891

<a name="l00864"></a>00864 tmatrix_type::n_rows * sizeof(GT));

892

<a name="l00865"></a>00865

893

<a name="l00866"></a>00866 // restore into a temp buffer

894

<a name="l00867"></a>00867 GT* gap_tmp = (GT*)tmp_block;

895

<a name="l00868"></a>00868 //*gap_tmp++ = gap_head;

896

<a name="l00869"></a>00869

897

<a name="l00870"></a>00870 vect_bit_trestore<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>(<a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>.value, gap_tmp);

898

<a name="l00871"></a>00871

899

<a name="l00872"></a>00872 // D-Gap to GAP block recalculation

900

<a name="l00873"></a>00873 gap_tmp = (GT*)tmp_block;

901

<a name="l00874"></a>00874 dgap_2_gap<GT>(gap_tmp, gap_buf, gap_head);

902

<a name="l00875"></a>00875 }

903

<a name="l00876"></a>00876

904

<a name="l00877"></a>00877 public:

905

<a name="l00878"></a>00878 // GT gap_head_;

906

<a name="l00879"></a><a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">00879</a> <a class="code" href="a00069.html#aebedc43b623e92c51d273654aa437dbb" title="cryptic calculation of equivalent size for the transpose matrix based on BLOCK_SIZE...">tmatrix_type</a> <a class="code" href="a00069.html#a78bbc8d39f794aa7587363c237153471">tmatrix_</a>;

907

<a name="l00880"></a><a class="code" href="a00069.html#acaded7f30ccbc5585749bdb03a441ab0">00880</a> unsigned <a class="code" href="a00069.html#acaded7f30ccbc5585749bdb03a441ab0">eff_cols_</a>;

908

<a name="l00881"></a><a class="code" href="a00069.html#ac0b8879d3154afe10fcd8a4725f3cbc1">00881</a> unsigned <a class="code" href="a00069.html#ac0b8879d3154afe10fcd8a4725f3cbc1">distance_</a>[tmatrix_type::n_rows][tmatrix_type::n_rows];

909

<a name="l00882"></a><a class="code" href="a00069.html#a6fdb1d059dd9e18596740159132e7a16">00882</a> unsigned char <a class="code" href="a00069.html#a6fdb1d059dd9e18596740159132e7a16">pc_vector_</a>[tmatrix_type::n_rows];

910

<a name="l00883"></a><a class="code" href="a00069.html#a443d2f744a1bb123907ce7db644deb13">00883</a> unsigned <a class="code" href="a00069.html#a443d2f744a1bb123907ce7db644deb13">pc_vector_stat_</a>[<a class="code" href="a00116.html#ae4f14f0c2c5a9ee277808d36fd94693f" title="!&lt; plain is close to plain M">bm::ibpc_end</a>];

911

<a name="l00884"></a><a class="code" href="a00069.html#ab6cfa9ccf0fbdc192ecbbd289d9df117">00884</a> typename <a class="code" href="a00082.html" title="Row characteristics for transposed matrix.">tmatrix_type::rstat</a> <a class="code" href="a00069.html#ab6cfa9ccf0fbdc192ecbbd289d9df117">rstat_vector_</a>[tmatrix_type::n_rows];

912

<a name="l00885"></a>00885 };

913

<a name="l00886"></a>00886

914

<a name="l00887"></a>00887

915

<a name="l00888"></a>00888 } // namespace bm

916

<a name="l00889"></a>00889

917

<a name="l00890"></a>00890 #endif

918

</pre></div></div>

<hr size="1"/><address style="text-align: right;">Generated on Fri Jan 8 20:09:19 2010 for BitMagic by

919

<hr size="1"/><address style="text-align: right;">Generated on Tue Mar 23 20:47:55 2010 for BitMagic by

920

921

922

</body>

Older »