53
53
<a name="l00026"></a>00026 <span class="comment"></span>
54
54
<a name="l00027"></a>00027 <span class="comment">*/</span>
55
55
<a name="l00028"></a>00028
56
<a name="l00029"></a>00029
57
<a name="l00030"></a>00030
58
<a name="l00031"></a>00031 <span class="keyword">namespace </span>bm
59
<a name="l00032"></a>00032 {
60
<a name="l00033"></a>00033 <span class="comment"></span>
61
<a name="l00034"></a>00034 <span class="comment">/*! </span>
62
<a name="l00035"></a>00035 <span class="comment"> @brief SSE2 reinitialization guard class</span>
63
<a name="l00036"></a>00036 <span class="comment"></span>
64
<a name="l00037"></a>00037 <span class="comment"> SSE2 requires to call _mm_empty() if we are intermixing</span>
65
<a name="l00038"></a>00038 <span class="comment"> MMX integer commands with floating point arithmetics.</span>
66
<a name="l00039"></a>00039 <span class="comment"> This class guards critical code fragments where SSE2 integer</span>
67
<a name="l00040"></a>00040 <span class="comment"> is used.</span>
68
<a name="l00041"></a>00041 <span class="comment"></span>
69
<a name="l00042"></a>00042 <span class="comment"> @ingroup SSE2</span>
70
<a name="l00043"></a>00043 <span class="comment">*/</span>
71
<a name="l00044"></a><a class="code" href="a00081.html">00044</a> <span class="keyword">class </span><a class="code" href="a00081.html" title="SSE2 reinitialization guard class.">sse_empty_guard</a>
72
<a name="l00045"></a>00045 {
73
<a name="l00046"></a>00046 <span class="keyword">public</span>:
74
<a name="l00047"></a><a class="code" href="a00081.html#a231af2137d8bd3aefc374982804ace24">00047</a> <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a> <a class="code" href="a00081.html#a231af2137d8bd3aefc374982804ace24">sse_empty_guard</a>()
75
<a name="l00048"></a>00048 {
76
<a name="l00049"></a>00049 _mm_empty();
77
<a name="l00050"></a>00050 }
78
<a name="l00051"></a>00051
79
<a name="l00052"></a><a class="code" href="a00081.html#a5d197a685ce1f87a1cc01b047960377b">00052</a> <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a> <a class="code" href="a00081.html#a5d197a685ce1f87a1cc01b047960377b">~sse_empty_guard</a>()
80
<a name="l00053"></a>00053 {
81
<a name="l00054"></a>00054 _mm_empty();
82
<a name="l00055"></a>00055 }
83
<a name="l00056"></a>00056 };
84
<a name="l00057"></a>00057
85
<a name="l00058"></a>00058
86
<a name="l00059"></a>00059 <span class="comment"></span>
87
<a name="l00060"></a>00060 <span class="comment">/*! </span>
88
<a name="l00061"></a>00061 <span class="comment"> @brief XOR array elements to specified mask</span>
89
<a name="l00062"></a>00062 <span class="comment"> *dst = *src ^ mask</span>
90
<a name="l00063"></a>00063 <span class="comment"></span>
91
<a name="l00064"></a>00064 <span class="comment"> @ingroup SSE2</span>
92
<a name="l00065"></a>00065 <span class="comment">*/</span>
93
<a name="l00066"></a>00066 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
94
<a name="l00067"></a><a class="code" href="a00118.html#ga75c6ddeb0d8a279caa92341878309b50">00067</a> <span class="keywordtype">void</span> <a class="code" href="a00118.html#ga75c6ddeb0d8a279caa92341878309b50" title="XOR array elements to specified mask dst = *src ^ mask.">sse2_xor_arr_2_mask</a>(__m128i* BMRESTRICT dst,
95
<a name="l00068"></a>00068 <span class="keyword">const</span> __m128i* BMRESTRICT src,
96
<a name="l00069"></a>00069 <span class="keyword">const</span> __m128i* BMRESTRICT src_end,
97
<a name="l00070"></a>00070 <a class="code" href="a00110.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a> mask)
98
<a name="l00071"></a>00071 {
99
<a name="l00072"></a>00072 __m128i xmm2 = _mm_set_epi32(mask, mask, mask, mask);
100
<a name="l00073"></a>00073 <span class="keywordflow">do</span>
101
<a name="l00074"></a>00074 {
102
<a name="l00075"></a>00075 __m128i xmm1 = _mm_load_si128(src);
103
<a name="l00076"></a>00076
104
<a name="l00077"></a>00077 xmm1 = _mm_xor_si128(xmm1, xmm2);
105
<a name="l00078"></a>00078 _mm_store_si128(dst, xmm1);
106
<a name="l00079"></a>00079 ++dst;
107
<a name="l00080"></a>00080 ++src;
108
<a name="l00081"></a>00081
109
<a name="l00082"></a>00082 } <span class="keywordflow">while</span> (src < src_end);
110
<a name="l00083"></a>00083 }
111
<a name="l00084"></a>00084
112
<a name="l00085"></a>00085 <span class="comment"></span>
113
<a name="l00086"></a>00086 <span class="comment">/*! </span>
114
<a name="l00087"></a>00087 <span class="comment"> @brief Inverts array elements and NOT them to specified mask</span>
115
<a name="l00088"></a>00088 <span class="comment"> *dst = ~*src & mask</span>
116
<a name="l00089"></a>00089 <span class="comment"></span>
117
<a name="l00090"></a>00090 <span class="comment"> @ingroup SSE2</span>
118
<a name="l00091"></a>00091 <span class="comment">*/</span>
119
<a name="l00092"></a>00092 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
120
<a name="l00093"></a><a class="code" href="a00118.html#gab7b21f448684c4d84927792661e67ed5">00093</a> <span class="keywordtype">void</span> <a class="code" href="a00118.html#gab7b21f448684c4d84927792661e67ed5" title="Inverts array elements and NOT them to specified mask dst = ~*src &amp; mask.">sse2_andnot_arr_2_mask</a>(__m128i* BMRESTRICT dst,
121
<a name="l00094"></a>00094 <span class="keyword">const</span> __m128i* BMRESTRICT src,
122
<a name="l00095"></a>00095 <span class="keyword">const</span> __m128i* BMRESTRICT src_end,
123
<a name="l00096"></a>00096 <a class="code" href="a00110.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a> mask)
124
<a name="l00097"></a>00097 {
125
<a name="l00098"></a>00098 __m128i xmm2 = _mm_set_epi32(mask, mask, mask, mask);
126
<a name="l00099"></a>00099 <span class="keywordflow">do</span>
127
<a name="l00100"></a>00100 {
128
<a name="l00101"></a>00101 <span class="comment">//_mm_prefetch((const char*)(src)+1024, _MM_HINT_NTA);</span>
129
<a name="l00102"></a>00102 <span class="comment">//_mm_prefetch((const char*)(src)+1088, _MM_HINT_NTA);</span>
130
<a name="l00103"></a>00103
131
<a name="l00104"></a>00104 __m128i xmm1 = _mm_load_si128(src);
132
<a name="l00105"></a>00105
133
<a name="l00106"></a>00106 xmm1 = _mm_andnot_si128(xmm1, xmm2); <span class="comment">// xmm1 = (~xmm1) & xmm2 </span>
134
<a name="l00107"></a>00107 _mm_store_si128(dst, xmm1);
135
<a name="l00108"></a>00108 ++dst;
136
<a name="l00109"></a>00109 ++src;
137
<a name="l00110"></a>00110
138
<a name="l00111"></a>00111 } <span class="keywordflow">while</span> (src < src_end);
139
<a name="l00112"></a>00112 }
140
<a name="l00113"></a>00113 <span class="comment"></span>
141
<a name="l00114"></a>00114 <span class="comment">/*! </span>
142
<a name="l00115"></a>00115 <span class="comment"> @brief AND array elements against another array</span>
143
<a name="l00116"></a>00116 <span class="comment"> *dst &= *src</span>
144
<a name="l00117"></a>00117 <span class="comment"></span>
145
<a name="l00118"></a>00118 <span class="comment"> @ingroup SSE2</span>
146
<a name="l00119"></a>00119 <span class="comment">*/</span>
147
<a name="l00120"></a>00120 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
148
<a name="l00121"></a><a class="code" href="a00118.html#ga795b544f311409a55da4ee61a3cd939a">00121</a> <span class="keywordtype">void</span> <a class="code" href="a00118.html#ga795b544f311409a55da4ee61a3cd939a" title="AND array elements against another array dst &amp;= *src.">sse2_and_arr</a>(__m128i* BMRESTRICT dst,
149
<a name="l00122"></a>00122 <span class="keyword">const</span> __m128i* BMRESTRICT src,
150
<a name="l00123"></a>00123 <span class="keyword">const</span> __m128i* BMRESTRICT src_end)
151
<a name="l00124"></a>00124 {
152
<a name="l00125"></a>00125 __m128i xmm1, xmm2;
153
<a name="l00126"></a>00126 <span class="keywordflow">do</span>
154
<a name="l00127"></a>00127 {
155
<a name="l00128"></a>00128 _mm_prefetch((<span class="keyword">const</span> <span class="keywordtype">char</span>*)(src)+512, _MM_HINT_NTA);
156
<a name="l00129"></a>00129
157
<a name="l00130"></a>00130 xmm1 = _mm_load_si128(src++);
158
<a name="l00131"></a>00131 xmm2 = _mm_load_si128(dst);
159
<a name="l00132"></a>00132 xmm1 = _mm_and_si128(xmm1, xmm2);
160
<a name="l00133"></a>00133 _mm_store_si128(dst++, xmm1);
161
<a name="l00134"></a>00134
162
<a name="l00135"></a>00135 xmm1 = _mm_load_si128(src++);
163
<a name="l00136"></a>00136 xmm2 = _mm_load_si128(dst);
164
<a name="l00137"></a>00137 xmm1 = _mm_and_si128(xmm1, xmm2);
165
<a name="l00138"></a>00138 _mm_store_si128(dst++, xmm1);
166
<a name="l00139"></a>00139
167
<a name="l00140"></a>00140 xmm1 = _mm_load_si128(src++);
168
<a name="l00141"></a>00141 xmm2 = _mm_load_si128(dst);
169
<a name="l00142"></a>00142 xmm1 = _mm_and_si128(xmm1, xmm2);
170
<a name="l00143"></a>00143 _mm_store_si128(dst++, xmm1);
171
<a name="l00144"></a>00144
172
<a name="l00145"></a>00145 xmm1 = _mm_load_si128(src++);
173
<a name="l00146"></a>00146 xmm2 = _mm_load_si128(dst);
174
<a name="l00147"></a>00147 xmm1 = _mm_and_si128(xmm1, xmm2);
175
<a name="l00148"></a>00148 _mm_store_si128(dst++, xmm1);
176
<a name="l00149"></a>00149
177
<a name="l00150"></a>00150 } <span class="keywordflow">while</span> (src < src_end);
178
<a name="l00151"></a>00151
179
<a name="l00152"></a>00152 }
180
<a name="l00153"></a>00153
181
<a name="l00154"></a>00154 <span class="comment"></span>
182
<a name="l00155"></a>00155 <span class="comment">/*! </span>
183
<a name="l00156"></a>00156 <span class="comment"> @brief OR array elements against another array</span>
184
<a name="l00157"></a>00157 <span class="comment"> *dst |= *src</span>
185
<a name="l00158"></a>00158 <span class="comment"></span>
186
<a name="l00159"></a>00159 <span class="comment"> @ingroup SSE2</span>
187
<a name="l00160"></a>00160 <span class="comment">*/</span>
188
<a name="l00161"></a>00161 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
189
<a name="l00162"></a><a class="code" href="a00118.html#ga3a7d61e4e8ad8791ab38fd1c3436aa67">00162</a> <span class="keywordtype">void</span> <a class="code" href="a00118.html#ga3a7d61e4e8ad8791ab38fd1c3436aa67" title="OR array elements against another array dst |= *src.">sse2_or_arr</a>(__m128i* BMRESTRICT dst,
190
<a name="l00163"></a>00163 <span class="keyword">const</span> __m128i* BMRESTRICT src,
191
<a name="l00164"></a>00164 <span class="keyword">const</span> __m128i* BMRESTRICT src_end)
192
<a name="l00165"></a>00165 {
193
<a name="l00166"></a>00166 __m128i xmm1, xmm2;
194
<a name="l00167"></a>00167 <span class="keywordflow">do</span>
195
<a name="l00168"></a>00168 {
196
<a name="l00169"></a>00169 _mm_prefetch((<span class="keyword">const</span> <span class="keywordtype">char</span>*)(src)+512, _MM_HINT_NTA);
197
<a name="l00170"></a>00170
198
<a name="l00171"></a>00171 xmm1 = _mm_load_si128(src++);
199
<a name="l00172"></a>00172 xmm2 = _mm_load_si128(dst);
200
<a name="l00173"></a>00173 xmm1 = _mm_or_si128(xmm1, xmm2);
201
<a name="l00174"></a>00174 _mm_store_si128(dst++, xmm1);
202
<a name="l00175"></a>00175
203
<a name="l00176"></a>00176 xmm1 = _mm_load_si128(src++);
204
<a name="l00177"></a>00177 xmm2 = _mm_load_si128(dst);
205
<a name="l00178"></a>00178 xmm1 = _mm_or_si128(xmm1, xmm2);
206
<a name="l00179"></a>00179 _mm_store_si128(dst++, xmm1);
56
<a name="l00029"></a>00029 <span class="preprocessor">#include "<a class="code" href="a00087.html">bm.h</a>"</span>
57
<a name="l00030"></a>00030 <span class="preprocessor">#include "<a class="code" href="a00093.html">bmfunc.h</a>"</span>
58
<a name="l00031"></a>00031 <span class="preprocessor">#include "<a class="code" href="a00092.html">bmdef.h</a>"</span>
59
<a name="l00032"></a>00032
60
<a name="l00033"></a>00033 <span class="preprocessor">#include <stdlib.h></span>
61
<a name="l00034"></a>00034 <span class="preprocessor">#include <algorithm></span>
62
<a name="l00035"></a>00035
63
<a name="l00036"></a>00036
64
<a name="l00037"></a>00037 <span class="keyword">namespace </span>bm
65
<a name="l00038"></a>00038 {
66
<a name="l00039"></a>00039 <span class="comment"></span>
67
<a name="l00040"></a>00040 <span class="comment">/*!</span>
68
<a name="l00041"></a>00041 <span class="comment"> Class implements algorithm for random subset generation.</span>
69
<a name="l00042"></a>00042 <span class="comment"></span>
70
<a name="l00043"></a>00043 <span class="comment"> Implemented method tries to be fair, but doesn't guarantee</span>
71
<a name="l00044"></a>00044 <span class="comment"> true randomeness.</span>
72
<a name="l00045"></a>00045 <span class="comment"></span>
73
<a name="l00046"></a>00046 <span class="comment"> Performace note: </span>
74
<a name="l00047"></a>00047 <span class="comment"> Class holds temporary buffers and variables, so it is recommended to</span>
75
<a name="l00048"></a>00048 <span class="comment"> re-use instances over multiple calls.</span>
76
<a name="l00049"></a>00049 <span class="comment"></span>
77
<a name="l00050"></a>00050 <span class="comment"> \ingroup setalgo</span>
78
<a name="l00051"></a>00051 <span class="comment">*/</span>
79
<a name="l00052"></a>00052 <span class="keyword">template</span><<span class="keyword">class</span> BV>
80
<a name="l00053"></a><a class="code" href="a00079.html">00053</a> <span class="keyword">class </span><a class="code" href="a00079.html">random_subset</a>
81
<a name="l00054"></a>00054 {
82
<a name="l00055"></a>00055 <span class="keyword">public</span>:
83
<a name="l00056"></a>00056 <a class="code" href="a00079.html#ab47431e0fe23053d0dc5d3799822c109">random_subset</a>();
84
<a name="l00057"></a>00057 <a class="code" href="a00079.html#a6cd4b5521110aad7f8c8511b88d11bff">~random_subset</a>();
85
<a name="l00058"></a>00058 <span class="comment"></span>
86
<a name="l00059"></a>00059 <span class="comment"> /// Get random subset of input vector</span>
87
<a name="l00060"></a>00060 <span class="comment"> ///</span>
88
<a name="l00061"></a>00061 <span class="comment"> /// @param bv_out - destination vector</span>
89
<a name="l00062"></a>00062 <span class="comment"> /// @param bv_in - input vector</span>
90
<a name="l00063"></a>00063 <span class="comment"> /// @param count - number of bits to pick</span>
91
<a name="l00064"></a>00064 <span class="comment"> ///</span>
92
<a name="l00065"></a>00065 <span class="comment"></span> <span class="keywordtype">void</span> <a class="code" href="a00079.html#addbc2e7ae5308fed4c92da441b236ce4" title="Get random subset of input vector.">sample</a>(BV& bv_out, <span class="keyword">const</span> BV& bv_in, <span class="keywordtype">unsigned</span> count);
93
<a name="l00066"></a>00066
94
<a name="l00067"></a>00067
95
<a name="l00068"></a>00068 <span class="keyword">private</span>:
96
<a name="l00069"></a>00069 <span class="keyword">typedef</span>
97
<a name="l00070"></a>00070 <span class="keyword">typename</span> BV::blocks_manager_type blocks_manager_type;
98
<a name="l00071"></a>00071
99
<a name="l00072"></a>00072 <span class="keyword">private</span>:
100
<a name="l00073"></a>00073 <span class="keywordtype">void</span> get_subset(BV& bv_out,
101
<a name="l00074"></a>00074 <span class="keyword">const</span> BV& bv_in,
102
<a name="l00075"></a>00075 <span class="keywordtype">unsigned</span> bv_in_count,
103
<a name="l00076"></a>00076 <span class="keywordtype">unsigned</span> count);
104
<a name="l00077"></a>00077
105
<a name="l00078"></a>00078 <span class="keywordtype">unsigned</span> find_max_block();
106
<a name="l00079"></a>00079
107
<a name="l00080"></a>00080 <span class="keywordtype">void</span> get_random_subset(<a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_out,
108
<a name="l00081"></a>00081 <span class="keyword">const</span> <a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_src,
109
<a name="l00082"></a>00082 <span class="keywordtype">unsigned</span> count);
110
<a name="l00083"></a>00083 <span class="keyword">static</span>
111
<a name="l00084"></a>00084 <span class="keywordtype">unsigned</span> process_word(<a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_out,
112
<a name="l00085"></a>00085 <span class="keyword">const</span> <a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_src,
113
<a name="l00086"></a>00086 <span class="keywordtype">unsigned</span> i,
114
<a name="l00087"></a>00087 <span class="keywordtype">unsigned</span> count);
115
<a name="l00088"></a>00088
116
<a name="l00089"></a>00089 <span class="keyword">static</span>
117
<a name="l00090"></a>00090 <span class="keywordtype">void</span> get_random_array(<a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_out,
118
<a name="l00091"></a>00091 <a class="code" href="a00115.html#ac654d6319039a86546d235a236fc7cf6">bm::gap_word_t</a>* <a class="code" href="a00120.html#gaae3ae537760044543f842363e4614e82" title="Unpacks word into list of ON bit indexes.">bit_list</a>,
119
<a name="l00092"></a>00092 <span class="keywordtype">unsigned</span> bit_list_size,
120
<a name="l00093"></a>00093 <span class="keywordtype">unsigned</span> count);
121
<a name="l00094"></a>00094
122
<a name="l00095"></a>00095
123
<a name="l00096"></a>00096 <span class="keyword">private</span>:
124
<a name="l00097"></a>00097 <a class="code" href="a00079.html#ab47431e0fe23053d0dc5d3799822c109">random_subset</a>(<span class="keyword">const</span> <a class="code" href="a00079.html">random_subset</a>&);
125
<a name="l00098"></a>00098 <a class="code" href="a00079.html">random_subset</a>& operator=(<span class="keyword">const</span> <a class="code" href="a00079.html">random_subset</a>&);
126
<a name="l00099"></a>00099 <span class="keyword">private</span>:
127
<a name="l00100"></a>00100 <span class="keywordtype">unsigned</span>* block_counts_;
128
<a name="l00101"></a>00101 <span class="keywordtype">unsigned</span> <span class="keywordtype">short</span>* block_bits_take_;
129
<a name="l00102"></a>00102 <span class="keywordtype">unsigned</span> blocks_;
130
<a name="l00103"></a>00103 <a class="code" href="a00115.html#ac654d6319039a86546d235a236fc7cf6">bm::gap_word_t</a> bit_list_[<a class="code" href="a00115.html#ad0b8714080144ac70197840ff96752b7">bm::gap_max_bits</a>];
131
<a name="l00104"></a>00104 <span class="keywordtype">unsigned</span>* block_candidates_;
132
<a name="l00105"></a>00105 <span class="keywordtype">unsigned</span> candidates_count_;
133
<a name="l00106"></a>00106 <a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* sub_block_;
134
<a name="l00107"></a>00107 };
135
<a name="l00108"></a>00108
136
<a name="l00109"></a>00109 <span class="comment"></span>
137
<a name="l00110"></a>00110 <span class="comment">///////////////////////////////////////////////////////////////////</span>
138
<a name="l00111"></a>00111 <span class="comment"></span>
139
<a name="l00112"></a>00112
140
<a name="l00113"></a>00113
141
<a name="l00114"></a>00114 <span class="keyword">template</span><<span class="keyword">class</span> BV>
142
<a name="l00115"></a><a class="code" href="a00079.html#ab47431e0fe23053d0dc5d3799822c109">00115</a> <a class="code" href="a00079.html#ab47431e0fe23053d0dc5d3799822c109">random_subset<BV>::random_subset</a>()
143
<a name="l00116"></a>00116 : block_counts_(new unsigned[bm::<a class="code" href="a00115.html#a505011007f54598794e0b9477c0b0b11">set_total_blocks</a>]),
144
<a name="l00117"></a>00117 block_bits_take_(new bm::<a class="code" href="a00115.html#ac654d6319039a86546d235a236fc7cf6">gap_word_t</a>[bm::<a class="code" href="a00115.html#a505011007f54598794e0b9477c0b0b11">set_total_blocks</a>]),
145
<a name="l00118"></a>00118 block_candidates_(new unsigned[bm::<a class="code" href="a00115.html#a505011007f54598794e0b9477c0b0b11">set_total_blocks</a>]),
146
<a name="l00119"></a>00119 candidates_count_(0),
147
<a name="l00120"></a>00120 sub_block_(new bm::<a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">word_t</a>[bm::<a class="code" href="a00115.html#a91319dbc0d0e1bf3a3efc4d92bac7972">set_block_size</a>])
148
<a name="l00121"></a>00121 {
149
<a name="l00122"></a>00122 }
150
<a name="l00123"></a>00123
151
<a name="l00124"></a>00124 <span class="keyword">template</span><<span class="keyword">class</span> BV>
152
<a name="l00125"></a><a class="code" href="a00079.html#a6cd4b5521110aad7f8c8511b88d11bff">00125</a> <a class="code" href="a00079.html#a6cd4b5521110aad7f8c8511b88d11bff">random_subset<BV>::~random_subset</a>()
153
<a name="l00126"></a>00126 {
154
<a name="l00127"></a>00127 <span class="keyword">delete</span> [] block_counts_;
155
<a name="l00128"></a>00128 <span class="keyword">delete</span> [] block_bits_take_;
156
<a name="l00129"></a>00129 <span class="keyword">delete</span> [] block_candidates_;
157
<a name="l00130"></a>00130 <span class="keyword">delete</span> [] sub_block_;
158
<a name="l00131"></a>00131 }
159
<a name="l00132"></a>00132
160
<a name="l00133"></a>00133 <span class="keyword">template</span><<span class="keyword">class</span> BV>
161
<a name="l00134"></a><a class="code" href="a00079.html#addbc2e7ae5308fed4c92da441b236ce4">00134</a> <span class="keywordtype">void</span> <a class="code" href="a00079.html#addbc2e7ae5308fed4c92da441b236ce4" title="Get random subset of input vector.">random_subset<BV>::sample</a>(BV& bv_out,
162
<a name="l00135"></a>00135 <span class="keyword">const</span> BV& bv_in,
163
<a name="l00136"></a>00136 <span class="keywordtype">unsigned</span> count)
164
<a name="l00137"></a>00137 {
165
<a name="l00138"></a>00138 <span class="keywordflow">if</span> (count == 0)
166
<a name="l00139"></a>00139 {
167
<a name="l00140"></a>00140 bv_out.clear(<span class="keyword">true</span>);
168
<a name="l00141"></a>00141 <span class="keywordflow">return</span>;
169
<a name="l00142"></a>00142 }
170
<a name="l00143"></a>00143
171
<a name="l00144"></a>00144 <span class="keywordtype">unsigned</span> bcnt = bv_in.count();
172
<a name="l00145"></a>00145 <span class="keywordflow">if</span> (count >= bcnt)
173
<a name="l00146"></a>00146 {
174
<a name="l00147"></a>00147 bv_out = bv_in;
175
<a name="l00148"></a>00148 <span class="keywordflow">return</span>;
176
<a name="l00149"></a>00149 }
177
<a name="l00150"></a>00150 <span class="keywordflow">if</span> (count > bcnt/2)
178
<a name="l00151"></a>00151 {
179
<a name="l00152"></a>00152 <span class="comment">// build the complement vector and subtract it</span>
180
<a name="l00153"></a>00153 BV tmp_bv;
181
<a name="l00154"></a>00154 <span class="keywordtype">unsigned</span> delta_count = bcnt - count;
182
<a name="l00155"></a>00155
183
<a name="l00156"></a>00156 get_subset(tmp_bv, bv_in, bcnt, delta_count);
184
<a name="l00157"></a>00157 bv_out = bv_in;
185
<a name="l00158"></a>00158 bv_out -= tmp_bv;
186
<a name="l00159"></a>00159 <span class="keywordflow">return</span>;
187
<a name="l00160"></a>00160 }
188
<a name="l00161"></a>00161
189
<a name="l00162"></a>00162 get_subset(bv_out, bv_in, bcnt, count);
190
<a name="l00163"></a>00163 }
191
<a name="l00164"></a>00164
192
<a name="l00165"></a>00165 <span class="keyword">template</span><<span class="keyword">class</span> BV>
193
<a name="l00166"></a>00166 <span class="keywordtype">void</span> <a class="code" href="a00079.html">random_subset<BV>::get_subset</a>(BV& bv_out,
194
<a name="l00167"></a>00167 <span class="keyword">const</span> BV& bv_in,
195
<a name="l00168"></a>00168 <span class="keywordtype">unsigned</span> bcnt,
196
<a name="l00169"></a>00169 <span class="keywordtype">unsigned</span> count)
197
<a name="l00170"></a>00170 {
198
<a name="l00171"></a>00171 bv_out.clear(<span class="keyword">true</span>);
199
<a name="l00172"></a>00172 bv_out.resize(bv_in.size());
200
<a name="l00173"></a>00173
201
<a name="l00174"></a>00174 <span class="keyword">const</span> blocks_manager_type& bman_in = bv_in.get_blocks_manager();
202
<a name="l00175"></a>00175 blocks_manager_type& bman_out = bv_out.get_blocks_manager();
203
<a name="l00176"></a>00176
204
<a name="l00177"></a>00177 <a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* tmp_block = bman_out.check_allocate_tempblock();
205
<a name="l00178"></a>00178 candidates_count_ = 0;
206
<a name="l00179"></a>00179
207
207
<a name="l00180"></a>00180
208
<a name="l00181"></a>00181 xmm1 = _mm_load_si128(src++);
209
<a name="l00182"></a>00182 xmm2 = _mm_load_si128(dst);
210
<a name="l00183"></a>00183 xmm1 = _mm_or_si128(xmm1, xmm2);
211
<a name="l00184"></a>00184 _mm_store_si128(dst++, xmm1);
212
<a name="l00185"></a>00185
213
<a name="l00186"></a>00186 xmm1 = _mm_load_si128(src++);
214
<a name="l00187"></a>00187 xmm2 = _mm_load_si128(dst);
215
<a name="l00188"></a>00188 xmm1 = _mm_or_si128(xmm1, xmm2);
216
<a name="l00189"></a>00189 _mm_store_si128(dst++, xmm1);
217
<a name="l00190"></a>00190
218
<a name="l00191"></a>00191 } <span class="keywordflow">while</span> (src < src_end);
219
<a name="l00192"></a>00192 }
220
<a name="l00193"></a>00193
221
<a name="l00194"></a>00194 <span class="comment"></span>
222
<a name="l00195"></a>00195 <span class="comment">/*! </span>
223
<a name="l00196"></a>00196 <span class="comment"> @brief OR array elements against another array</span>
224
<a name="l00197"></a>00197 <span class="comment"> *dst ^= *src</span>
225
<a name="l00198"></a>00198 <span class="comment"></span>
226
<a name="l00199"></a>00199 <span class="comment"> @ingroup SSE2</span>
227
<a name="l00200"></a>00200 <span class="comment">*/</span>
228
<a name="l00201"></a>00201 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
229
<a name="l00202"></a><a class="code" href="a00118.html#gaf1a5ad26557cc4d71d7421c35a8445fe">00202</a> <span class="keywordtype">void</span> <a class="code" href="a00118.html#gaf1a5ad26557cc4d71d7421c35a8445fe" title="OR array elements against another array dst ^= *src.">sse2_xor_arr</a>(__m128i* BMRESTRICT dst,
230
<a name="l00203"></a>00203 <span class="keyword">const</span> __m128i* BMRESTRICT src,
231
<a name="l00204"></a>00204 <span class="keyword">const</span> __m128i* BMRESTRICT src_end)
232
<a name="l00205"></a>00205 {
233
<a name="l00206"></a>00206 __m128i xmm1, xmm2;
234
<a name="l00207"></a>00207 <span class="keywordflow">do</span>
235
<a name="l00208"></a>00208 {
236
<a name="l00209"></a>00209 _mm_prefetch((<span class="keyword">const</span> <span class="keywordtype">char</span>*)(src)+512, _MM_HINT_NTA);
237
<a name="l00210"></a>00210
238
<a name="l00211"></a>00211 xmm1 = _mm_load_si128(src++);
239
<a name="l00212"></a>00212 xmm2 = _mm_load_si128(dst);
240
<a name="l00213"></a>00213 xmm1 = _mm_xor_si128(xmm1, xmm2);
241
<a name="l00214"></a>00214 _mm_store_si128(dst++, xmm1);
242
<a name="l00215"></a>00215
243
<a name="l00216"></a>00216 xmm1 = _mm_load_si128(src++);
244
<a name="l00217"></a>00217 xmm2 = _mm_load_si128(dst);
245
<a name="l00218"></a>00218 xmm1 = _mm_xor_si128(xmm1, xmm2);
246
<a name="l00219"></a>00219 _mm_store_si128(dst++, xmm1);
247
<a name="l00220"></a>00220
248
<a name="l00221"></a>00221 xmm1 = _mm_load_si128(src++);
249
<a name="l00222"></a>00222 xmm2 = _mm_load_si128(dst);
250
<a name="l00223"></a>00223 xmm1 = _mm_xor_si128(xmm1, xmm2);
251
<a name="l00224"></a>00224 _mm_store_si128(dst++, xmm1);
252
<a name="l00225"></a>00225
253
<a name="l00226"></a>00226 xmm1 = _mm_load_si128(src++);
254
<a name="l00227"></a>00227 xmm2 = _mm_load_si128(dst);
255
<a name="l00228"></a>00228 xmm1 = _mm_xor_si128(xmm1, xmm2);
256
<a name="l00229"></a>00229 _mm_store_si128(dst++, xmm1);
257
<a name="l00230"></a>00230
258
<a name="l00231"></a>00231 } <span class="keywordflow">while</span> (src < src_end);
259
<a name="l00232"></a>00232 }
260
<a name="l00233"></a>00233
261
<a name="l00234"></a>00234
262
<a name="l00235"></a>00235 <span class="comment"></span>
263
<a name="l00236"></a>00236 <span class="comment">/*! </span>
264
<a name="l00237"></a>00237 <span class="comment"> @brief AND-NOT (SUB) array elements against another array</span>
265
<a name="l00238"></a>00238 <span class="comment"> *dst &= ~*src</span>
266
<a name="l00239"></a>00239 <span class="comment"></span>
267
<a name="l00240"></a>00240 <span class="comment"> @ingroup SSE2</span>
268
<a name="l00241"></a>00241 <span class="comment">*/</span>
269
<a name="l00242"></a>00242 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
270
<a name="l00243"></a><a class="code" href="a00118.html#gac99f3b138f8a5e8ffb1296b129f618f0">00243</a> <span class="keywordtype">void</span> <a class="code" href="a00118.html#gac99f3b138f8a5e8ffb1296b129f618f0" title="AND-NOT (SUB) array elements against another array dst &amp;= ~*src.">sse2_sub_arr</a>(__m128i* BMRESTRICT dst,
271
<a name="l00244"></a>00244 <span class="keyword">const</span> __m128i* BMRESTRICT src,
272
<a name="l00245"></a>00245 <span class="keyword">const</span> __m128i* BMRESTRICT src_end)
273
<a name="l00246"></a>00246 {
274
<a name="l00247"></a>00247 __m128i xmm1, xmm2;
275
<a name="l00248"></a>00248 <span class="keywordflow">do</span>
276
<a name="l00249"></a>00249 {
277
<a name="l00250"></a>00250 _mm_prefetch((<span class="keyword">const</span> <span class="keywordtype">char</span>*)(src)+512, _MM_HINT_NTA);
278
<a name="l00251"></a>00251
279
<a name="l00252"></a>00252 xmm1 = _mm_load_si128(src++);
280
<a name="l00253"></a>00253 xmm2 = _mm_load_si128(dst);
281
<a name="l00254"></a>00254 xmm1 = _mm_andnot_si128(xmm1, xmm2);
282
<a name="l00255"></a>00255 _mm_store_si128(dst++, xmm1);
283
<a name="l00256"></a>00256
284
<a name="l00257"></a>00257 xmm1 = _mm_load_si128(src++);
285
<a name="l00258"></a>00258 xmm2 = _mm_load_si128(dst);
286
<a name="l00259"></a>00259 xmm1 = _mm_andnot_si128(xmm1, xmm2);
287
<a name="l00260"></a>00260 _mm_store_si128(dst++, xmm1);
288
<a name="l00261"></a>00261
289
<a name="l00262"></a>00262 xmm1 = _mm_load_si128(src++);
290
<a name="l00263"></a>00263 xmm2 = _mm_load_si128(dst);
291
<a name="l00264"></a>00264 xmm1 = _mm_andnot_si128(xmm1, xmm2);
292
<a name="l00265"></a>00265 _mm_store_si128(dst++, xmm1);
293
<a name="l00266"></a>00266
294
<a name="l00267"></a>00267 xmm1 = _mm_load_si128(src++);
295
<a name="l00268"></a>00268 xmm2 = _mm_load_si128(dst);
296
<a name="l00269"></a>00269 xmm1 = _mm_andnot_si128(xmm1, xmm2);
297
<a name="l00270"></a>00270 _mm_store_si128(dst++, xmm1);
298
<a name="l00271"></a>00271
299
<a name="l00272"></a>00272 } <span class="keywordflow">while</span> (src < src_end);
300
<a name="l00273"></a>00273 }
301
<a name="l00274"></a>00274 <span class="comment"></span>
302
<a name="l00275"></a>00275 <span class="comment">/*! </span>
303
<a name="l00276"></a>00276 <span class="comment"> @brief SSE2 block memset</span>
304
<a name="l00277"></a>00277 <span class="comment"> *dst = value</span>
305
<a name="l00278"></a>00278 <span class="comment"></span>
306
<a name="l00279"></a>00279 <span class="comment"> @ingroup SSE2</span>
307
<a name="l00280"></a>00280 <span class="comment">*/</span>
308
<a name="l00281"></a>00281
309
<a name="l00282"></a>00282 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
310
<a name="l00283"></a><a class="code" href="a00118.html#ga302f4fcd0abf355957b305d16d04f452">00283</a> <span class="keywordtype">void</span> <a class="code" href="a00118.html#ga302f4fcd0abf355957b305d16d04f452" title="SSE2 block memset dst = value.">sse2_set_block</a>(__m128i* BMRESTRICT dst,
311
<a name="l00284"></a>00284 __m128i* BMRESTRICT dst_end,
312
<a name="l00285"></a>00285 <a class="code" href="a00110.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a> value)
313
<a name="l00286"></a>00286 {
314
<a name="l00287"></a>00287 __m128i xmm0 = _mm_set_epi32 (value, value, value, value);
315
<a name="l00288"></a>00288 <span class="keywordflow">do</span>
316
<a name="l00289"></a>00289 {
317
<a name="l00290"></a>00290 _mm_store_si128(dst, xmm0);
318
<a name="l00291"></a>00291 <span class="comment">/* </span>
319
<a name="l00292"></a>00292 <span class="comment"> _mm_store_si128(dst+1, xmm0);</span>
320
<a name="l00293"></a>00293 <span class="comment"> _mm_store_si128(dst+2, xmm0);</span>
321
<a name="l00294"></a>00294 <span class="comment"> _mm_store_si128(dst+3, xmm0);</span>
322
<a name="l00295"></a>00295 <span class="comment"></span>
323
<a name="l00296"></a>00296 <span class="comment"> _mm_store_si128(dst+4, xmm0);</span>
324
<a name="l00297"></a>00297 <span class="comment"> _mm_store_si128(dst+5, xmm0);</span>
325
<a name="l00298"></a>00298 <span class="comment"> _mm_store_si128(dst+6, xmm0);</span>
326
<a name="l00299"></a>00299 <span class="comment"> _mm_store_si128(dst+7, xmm0);</span>
327
<a name="l00300"></a>00300 <span class="comment"></span>
328
<a name="l00301"></a>00301 <span class="comment"> dst += 8;</span>
329
<a name="l00302"></a>00302 <span class="comment">*/</span>
330
<a name="l00303"></a>00303 } <span class="keywordflow">while</span> (++dst < dst_end);
331
<a name="l00304"></a>00304
332
<a name="l00305"></a>00305 _mm_sfence();
333
<a name="l00306"></a>00306 }
334
<a name="l00307"></a>00307
208
<a name="l00181"></a>00181 <span class="comment">// compute bit-counts in all blocks</span>
209
<a name="l00182"></a>00182 <span class="comment">//</span>
210
<a name="l00183"></a>00183 <span class="keywordtype">unsigned</span> block_count = blocks_ = bv_in.count_blocks(block_counts_);
211
<a name="l00184"></a>00184 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i <= block_count; ++i)
212
<a name="l00185"></a>00185 {
213
<a name="l00186"></a>00186 <span class="keywordflow">if</span> (block_counts_[i])
214
<a name="l00187"></a>00187 {
215
<a name="l00188"></a>00188 <span class="keywordtype">float</span> block_percent =
216
<a name="l00189"></a>00189 ((float)(block_counts_[i]+1)) / (<span class="keywordtype">float</span>)bcnt;
217
<a name="l00190"></a>00190 <span class="keywordtype">float</span> bits_to_take = ((float)count) * block_percent;
218
<a name="l00191"></a>00191 bits_to_take += 0.99f;
219
<a name="l00192"></a>00192
220
<a name="l00193"></a>00193 <span class="keywordtype">unsigned</span> t = (unsigned)bits_to_take;
221
<a name="l00194"></a>00194 block_bits_take_[i] = (<a class="code" href="a00115.html#ac654d6319039a86546d235a236fc7cf6">bm::gap_word_t</a>)t;
222
<a name="l00195"></a>00195
223
<a name="l00196"></a>00196 <span class="keywordflow">if</span> (block_bits_take_[i] == 0)
224
<a name="l00197"></a>00197 {
225
<a name="l00198"></a>00198 block_bits_take_[i] = 1;
226
<a name="l00199"></a>00199 }
227
<a name="l00200"></a>00200 <span class="keywordflow">else</span>
228
<a name="l00201"></a>00201 <span class="keywordflow">if</span> (block_bits_take_[i] > block_counts_[i])
229
<a name="l00202"></a>00202 block_bits_take_[i] = block_counts_[i];
230
<a name="l00203"></a>00203
231
<a name="l00204"></a>00204 <a class="code" href="a00092.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(bman_in.get_block(i));
232
<a name="l00205"></a>00205 }
233
<a name="l00206"></a>00206 <span class="keywordflow">else</span>
234
<a name="l00207"></a>00207 {
235
<a name="l00208"></a>00208 block_bits_take_[i] = 0;
236
<a name="l00209"></a>00209 }
237
<a name="l00210"></a>00210 } <span class="comment">// for i</span>
238
<a name="l00211"></a>00211
239
<a name="l00212"></a>00212 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> take_count = 0; count; count -= take_count)
240
<a name="l00213"></a>00213 {
241
<a name="l00214"></a>00214 <span class="keywordtype">unsigned</span> i = find_max_block();
242
<a name="l00215"></a>00215 take_count = block_bits_take_[i];
243
<a name="l00216"></a>00216 <span class="keywordflow">if</span> (take_count > count)
244
<a name="l00217"></a>00217 take_count = count;
245
<a name="l00218"></a>00218 <span class="keywordflow">if</span> (take_count == 0)
246
<a name="l00219"></a>00219 <span class="keywordflow">continue</span>;
247
<a name="l00220"></a>00220 <span class="keyword">const</span> <a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_src = bman_in.get_block(i);
248
<a name="l00221"></a>00221 <a class="code" href="a00092.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(blk_src);
249
<a name="l00222"></a>00222
250
<a name="l00223"></a>00223 <span class="comment">// allocate target block</span>
251
<a name="l00224"></a>00224 <a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_out = bman_out.get_block(i);
252
<a name="l00225"></a>00225 <span class="keywordflow">if</span> (blk_out != 0)
253
<a name="l00226"></a>00226 {
254
<a name="l00227"></a>00227 blk_out = bman_out.deoptimize_block(i);
255
<a name="l00228"></a>00228 }
256
<a name="l00229"></a>00229 <span class="keywordflow">else</span>
257
<a name="l00230"></a>00230 {
258
<a name="l00231"></a>00231 blk_out = bman_out.get_allocator().alloc_bit_block();
259
<a name="l00232"></a>00232 bman_out.set_block(i, blk_out);
260
<a name="l00233"></a>00233 }
261
<a name="l00234"></a>00234 <span class="keywordflow">if</span> (take_count == block_counts_[i])
262
<a name="l00235"></a>00235 {
263
<a name="l00236"></a>00236 <span class="comment">// copy the whole src block</span>
264
<a name="l00237"></a>00237 <span class="keywordflow">if</span> (<a class="code" href="a00092.html#a862d6f92b4de3ddb94fd367a800512eb">BM_IS_GAP</a>(bman_in, blk_src, i))
265
<a name="l00238"></a>00238 {
266
<a name="l00239"></a>00239 <a class="code" href="a00119.html#ga4862f4dcdcb7c0575e2e2db9e5f2a849" title="GAP block to bitblock conversion.">gap_convert_to_bitset</a>(blk_out, <a class="code" href="a00092.html#a6a7c8b8ee3f3b60ab907c1699acb7aa0">BMGAP_PTR</a>(blk_src));
267
<a name="l00240"></a>00240 }
268
<a name="l00241"></a>00241 <span class="keywordflow">else</span>
269
<a name="l00242"></a>00242 {
270
<a name="l00243"></a>00243 <a class="code" href="a00120.html#ga9090de87d53e7f25eff96c8259b3485c" title="Bitblock copy operation.">bm::bit_block_copy</a>(blk_out, blk_src);
271
<a name="l00244"></a>00244 }
272
<a name="l00245"></a>00245 block_bits_take_[i] = 0; <span class="comment">// exclude block from any farther picking</span>
273
<a name="l00246"></a>00246 <span class="keywordflow">continue</span>;
274
<a name="l00247"></a>00247 }
275
<a name="l00248"></a>00248 <a class="code" href="a00120.html#gaada8b13c35acd8df90129b45edcfc5de" title="Bitblock memset operation.">bit_block_set</a>(blk_out, 0);
276
<a name="l00249"></a>00249
277
<a name="l00250"></a>00250 <span class="keywordflow">if</span> (block_counts_[i] < 4096) <span class="comment">// use array shuffle</span>
278
<a name="l00251"></a>00251 {
279
<a name="l00252"></a>00252 <span class="keywordtype">unsigned</span> arr_len;
280
<a name="l00253"></a>00253 <span class="comment">// convert source block to bit-block</span>
281
<a name="l00254"></a>00254 <span class="keywordflow">if</span> (<a class="code" href="a00092.html#a862d6f92b4de3ddb94fd367a800512eb">BM_IS_GAP</a>(bman_in, blk_src, i))
282
<a name="l00255"></a>00255 {
283
<a name="l00256"></a>00256 arr_len = <a class="code" href="a00119.html#ga5cd7e0cfee401da1b8f702151c083b27" title="Convert gap block into array of ints corresponding to 1 bits.">gap_convert_to_arr</a>(bit_list_,
284
<a name="l00257"></a>00257 <a class="code" href="a00092.html#a6a7c8b8ee3f3b60ab907c1699acb7aa0">BMGAP_PTR</a>(blk_src),
285
<a name="l00258"></a>00258 <a class="code" href="a00115.html#a9b1715d6d9164d56172e75bbbd0e3000">bm::gap_equiv_len</a>);
286
<a name="l00259"></a>00259 }
287
<a name="l00260"></a>00260 <span class="keywordflow">else</span> <span class="comment">// bit-block</span>
288
<a name="l00261"></a>00261 {
289
<a name="l00262"></a>00262 arr_len = <a class="code" href="a00120.html#gaf24d85761f60877c2260f8160593f732" title="Convert bit block into an array of ints corresponding to 1 bits.">bit_convert_to_arr</a>(bit_list_,
290
<a name="l00263"></a>00263 blk_src,
291
<a name="l00264"></a>00264 <a class="code" href="a00115.html#ad0b8714080144ac70197840ff96752b7">bm::gap_max_bits</a>,
292
<a name="l00265"></a>00265 <a class="code" href="a00115.html#a9b1715d6d9164d56172e75bbbd0e3000">bm::gap_equiv_len</a>,
293
<a name="l00266"></a>00266 0);
294
<a name="l00267"></a>00267 }
295
<a name="l00268"></a>00268 <a class="code" href="a00092.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(arr_len);
296
<a name="l00269"></a>00269 get_random_array(blk_out, bit_list_, arr_len, take_count);
297
<a name="l00270"></a>00270 }
298
<a name="l00271"></a>00271 <span class="keywordflow">else</span> <span class="comment">// dense block</span>
299
<a name="l00272"></a>00272 {
300
<a name="l00273"></a>00273 <span class="comment">// convert source block to bit-block</span>
301
<a name="l00274"></a>00274 <span class="keywordflow">if</span> (<a class="code" href="a00092.html#a862d6f92b4de3ddb94fd367a800512eb">BM_IS_GAP</a>(bman_in, blk_src, i))
302
<a name="l00275"></a>00275 {
303
<a name="l00276"></a>00276 <a class="code" href="a00119.html#ga4862f4dcdcb7c0575e2e2db9e5f2a849" title="GAP block to bitblock conversion.">gap_convert_to_bitset</a>(tmp_block, <a class="code" href="a00092.html#a6a7c8b8ee3f3b60ab907c1699acb7aa0">BMGAP_PTR</a>(blk_src));
304
<a name="l00277"></a>00277 blk_src = tmp_block;
305
<a name="l00278"></a>00278 }
306
<a name="l00279"></a>00279
307
<a name="l00280"></a>00280 <span class="comment">// pick random bits source block to target</span>
308
<a name="l00281"></a>00281 get_random_subset(blk_out, blk_src, take_count);
309
<a name="l00282"></a>00282 }
310
<a name="l00283"></a>00283
311
<a name="l00284"></a>00284 block_bits_take_[i] = 0; <span class="comment">// exclude block from any farther picking</span>
312
<a name="l00285"></a>00285 }
313
<a name="l00286"></a>00286 }
314
<a name="l00287"></a>00287
315
<a name="l00288"></a>00288 <span class="keyword">template</span><<span class="keyword">class</span> BV>
316
<a name="l00289"></a>00289 <span class="keywordtype">void</span> random_subset<BV>::get_random_subset(<a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_out,
317
<a name="l00290"></a>00290 <span class="keyword">const</span> <a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_src,
318
<a name="l00291"></a>00291 <span class="keywordtype">unsigned</span> take_count)
319
<a name="l00292"></a>00292 {
320
<a name="l00293"></a>00293 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> rounds = 0; take_count && rounds < 10; ++rounds)
321
<a name="l00294"></a>00294 {
322
<a name="l00295"></a>00295 <span class="comment">// pick random scan start and scan direction</span>
323
<a name="l00296"></a>00296 <span class="comment">//</span>
324
<a name="l00297"></a>00297 <span class="keywordtype">unsigned</span> i = rand() % <a class="code" href="a00115.html#a91319dbc0d0e1bf3a3efc4d92bac7972">bm::set_block_size</a>;
325
<a name="l00298"></a>00298 <span class="keywordtype">unsigned</span> new_count;
326
<a name="l00299"></a>00299
327
<a name="l00300"></a>00300 <span class="keywordflow">for</span> (; i < <a class="code" href="a00115.html#a91319dbc0d0e1bf3a3efc4d92bac7972">bm::set_block_size</a> && take_count; ++i)
328
<a name="l00301"></a>00301 {
329
<a name="l00302"></a>00302 <span class="keywordflow">if</span> (blk_src[i] && (blk_out[i] != blk_src[i]))
330
<a name="l00303"></a>00303 {
331
<a name="l00304"></a>00304 take_count -= new_count =
332
<a name="l00305"></a>00305 process_word(blk_out, blk_src, i, take_count);
333
<a name="l00306"></a>00306 }
334
<a name="l00307"></a>00307 } <span class="comment">// for i</span>
335
335
<a name="l00308"></a>00308
336
<a name="l00309"></a>00309 <span class="comment"></span>
337
<a name="l00310"></a>00310 <span class="comment">/*! </span>
338
<a name="l00311"></a>00311 <span class="comment"> @brief SSE2 block copy</span>
339
<a name="l00312"></a>00312 <span class="comment"> *dst = *src</span>
340
<a name="l00313"></a>00313 <span class="comment"></span>
341
<a name="l00314"></a>00314 <span class="comment"> @ingroup SSE2</span>
342
<a name="l00315"></a>00315 <span class="comment">*/</span>
343
<a name="l00316"></a>00316 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
344
<a name="l00317"></a><a class="code" href="a00118.html#ga571dd54af5c555cad9dfa6bef4561777">00317</a> <span class="keywordtype">void</span> <a class="code" href="a00118.html#ga571dd54af5c555cad9dfa6bef4561777" title="SSE2 block copy dst = *src.">sse2_copy_block</a>(__m128i* BMRESTRICT dst,
345
<a name="l00318"></a>00318 <span class="keyword">const</span> __m128i* BMRESTRICT src,
346
<a name="l00319"></a>00319 <span class="keyword">const</span> __m128i* BMRESTRICT src_end)
347
<a name="l00320"></a>00320 {
348
<a name="l00321"></a>00321 __m128i xmm0, xmm1, xmm2, xmm3;
349
<a name="l00322"></a>00322 <span class="keywordflow">do</span>
350
<a name="l00323"></a>00323 {
351
<a name="l00324"></a>00324 _mm_prefetch((<span class="keyword">const</span> <span class="keywordtype">char</span>*)(src)+512, _MM_HINT_NTA);
352
<a name="l00325"></a>00325
353
<a name="l00326"></a>00326 xmm0 = _mm_load_si128(src+0);
354
<a name="l00327"></a>00327 xmm1 = _mm_load_si128(src+1);
355
<a name="l00328"></a>00328 xmm2 = _mm_load_si128(src+2);
356
<a name="l00329"></a>00329 xmm3 = _mm_load_si128(src+3);
357
<a name="l00330"></a>00330
358
<a name="l00331"></a>00331 _mm_store_si128(dst+0, xmm0);
359
<a name="l00332"></a>00332 _mm_store_si128(dst+1, xmm1);
360
<a name="l00333"></a>00333 _mm_store_si128(dst+2, xmm2);
361
<a name="l00334"></a>00334 _mm_store_si128(dst+3, xmm3);
362
<a name="l00335"></a>00335
363
<a name="l00336"></a>00336 xmm0 = _mm_load_si128(src+4);
364
<a name="l00337"></a>00337 xmm1 = _mm_load_si128(src+5);
365
<a name="l00338"></a>00338 xmm2 = _mm_load_si128(src+6);
366
<a name="l00339"></a>00339 xmm3 = _mm_load_si128(src+7);
367
<a name="l00340"></a>00340
368
<a name="l00341"></a>00341 _mm_store_si128(dst+4, xmm0);
369
<a name="l00342"></a>00342 _mm_store_si128(dst+5, xmm1);
370
<a name="l00343"></a>00343 _mm_store_si128(dst+6, xmm2);
371
<a name="l00344"></a>00344 _mm_store_si128(dst+7, xmm3);
372
<a name="l00345"></a>00345
373
<a name="l00346"></a>00346 src += 8;
374
<a name="l00347"></a>00347 dst += 8;
375
<a name="l00348"></a>00348
376
<a name="l00349"></a>00349 } <span class="keywordflow">while</span> (src < src_end);
377
<a name="l00350"></a>00350 }
378
<a name="l00351"></a>00351 <span class="comment"></span>
379
<a name="l00352"></a>00352 <span class="comment">/*! </span>
380
<a name="l00353"></a>00353 <span class="comment"> @brief Invert array elements</span>
381
<a name="l00354"></a>00354 <span class="comment"> *dst = ~*dst</span>
382
<a name="l00355"></a>00355 <span class="comment"> or</span>
383
<a name="l00356"></a>00356 <span class="comment"> *dst ^= *dst </span>
384
<a name="l00357"></a>00357 <span class="comment"></span>
385
<a name="l00358"></a>00358 <span class="comment"> @ingroup SSE2</span>
386
<a name="l00359"></a>00359 <span class="comment">*/</span>
387
<a name="l00360"></a>00360 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
388
<a name="l00361"></a><a class="code" href="a00118.html#ga8d506147673d88005f92caee7f5dd23a">00361</a> <span class="keywordtype">void</span> <a class="code" href="a00118.html#ga8d506147673d88005f92caee7f5dd23a" title="Invert array elements dst = ~*dst or dst ^= *dst.">sse2_invert_arr</a>(<a class="code" href="a00110.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* first, <a class="code" href="a00110.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* last)
389
<a name="l00362"></a>00362 {
390
<a name="l00363"></a>00363 __m128i xmm1 = _mm_set_epi32(0xFFFFFFFF, 0xFFFFFFFF,
391
<a name="l00364"></a>00364 0xFFFFFFFF, 0xFFFFFFFF);
392
<a name="l00365"></a>00365 __m128i* wrd_ptr = (__m128i*)first;
393
<a name="l00366"></a>00366
394
<a name="l00367"></a>00367 <span class="keywordflow">do</span>
395
<a name="l00368"></a>00368 {
396
<a name="l00369"></a>00369 _mm_prefetch((<span class="keyword">const</span> <span class="keywordtype">char</span>*)(wrd_ptr)+512, _MM_HINT_NTA);
397
<a name="l00370"></a>00370
398
<a name="l00371"></a>00371 __m128i xmm0 = _mm_load_si128(wrd_ptr);
399
<a name="l00372"></a>00372 xmm0 = _mm_xor_si128(xmm0, xmm1);
400
<a name="l00373"></a>00373 _mm_store_si128(wrd_ptr, xmm0);
401
<a name="l00374"></a>00374 ++wrd_ptr;
402
<a name="l00375"></a>00375 } <span class="keywordflow">while</span> (wrd_ptr < (__m128i*)last);
403
<a name="l00376"></a>00376 }
404
<a name="l00377"></a>00377
405
<a name="l00378"></a>00378 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
406
<a name="l00379"></a><a class="code" href="a00110.html#ac0c75fb7b3dc61602843ac4e1b9b7ef5">00379</a> __m128i <a class="code" href="a00110.html#ac0c75fb7b3dc61602843ac4e1b9b7ef5">sse2_and</a>(__m128i a, __m128i b)
407
<a name="l00380"></a>00380 {
408
<a name="l00381"></a>00381 <span class="keywordflow">return</span> _mm_and_si128(a, b);
409
<a name="l00382"></a>00382 }
410
<a name="l00383"></a>00383
411
<a name="l00384"></a>00384 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
412
<a name="l00385"></a><a class="code" href="a00110.html#adea798a9a95a04845c33876087a2f46b">00385</a> __m128i <a class="code" href="a00110.html#adea798a9a95a04845c33876087a2f46b">sse2_or</a>(__m128i a, __m128i b)
336
<a name="l00309"></a>00309 } <span class="comment">// for</span>
337
<a name="l00310"></a>00310 <span class="comment">// if masked scan did not produce enough results..</span>
338
<a name="l00311"></a>00311 <span class="comment">//</span>
339
<a name="l00312"></a>00312 <span class="keywordflow">if</span> (take_count)
340
<a name="l00313"></a>00313 {
341
<a name="l00314"></a>00314 <span class="comment">// Find all vacant bits: do logical (src SUB out)</span>
342
<a name="l00315"></a>00315 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i < <a class="code" href="a00115.html#a91319dbc0d0e1bf3a3efc4d92bac7972">bm::set_block_size</a>; ++i)
343
<a name="l00316"></a>00316 {
344
<a name="l00317"></a>00317 sub_block_[i] = blk_src[i] & ~blk_out[i];
345
<a name="l00318"></a>00318 }
346
<a name="l00319"></a>00319 <span class="comment">// now transform vacant bits to array, then pick random elements</span>
347
<a name="l00320"></a>00320 <span class="comment">//</span>
348
<a name="l00321"></a>00321 <span class="keywordtype">unsigned</span> arr_len = <a class="code" href="a00120.html#gaf24d85761f60877c2260f8160593f732" title="Convert bit block into an array of ints corresponding to 1 bits.">bit_convert_to_arr</a>(bit_list_,
349
<a name="l00322"></a>00322 sub_block_,
350
<a name="l00323"></a>00323 <a class="code" href="a00115.html#ad0b8714080144ac70197840ff96752b7">bm::gap_max_bits</a>,
351
<a name="l00324"></a>00324 <a class="code" href="a00115.html#ad0b8714080144ac70197840ff96752b7">bm::gap_max_bits</a>,
352
<a name="l00325"></a>00325 0);
353
<a name="l00326"></a>00326 <a class="code" href="a00092.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(arr_len);
354
<a name="l00327"></a>00327 get_random_array(blk_out, bit_list_, arr_len, take_count);
355
<a name="l00328"></a>00328 }
356
<a name="l00329"></a>00329 }
357
<a name="l00330"></a>00330
358
<a name="l00331"></a>00331 <span class="keyword">template</span><<span class="keyword">class</span> BV>
359
<a name="l00332"></a>00332 <span class="keywordtype">unsigned</span> random_subset<BV>::process_word(<a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_out,
360
<a name="l00333"></a>00333 <span class="keyword">const</span> <a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_src,
361
<a name="l00334"></a>00334 <span class="keywordtype">unsigned</span> i,
362
<a name="l00335"></a>00335 <span class="keywordtype">unsigned</span> count)
363
<a name="l00336"></a>00336 {
364
<a name="l00337"></a>00337 <span class="keywordtype">unsigned</span> new_bits, mask;
365
<a name="l00338"></a>00338
366
<a name="l00339"></a>00339 <span class="keywordflow">do</span>
367
<a name="l00340"></a>00340 {
368
<a name="l00341"></a>00341 mask = rand();
369
<a name="l00342"></a>00342 mask ^= mask << 16;
370
<a name="l00343"></a>00343 } <span class="keywordflow">while</span> (mask == 0);
371
<a name="l00344"></a>00344
372
<a name="l00345"></a>00345 <span class="keywordtype">unsigned</span> src_rand = blk_src[i] & mask;
373
<a name="l00346"></a>00346 new_bits = src_rand & ~blk_out[i];
374
<a name="l00347"></a>00347
375
<a name="l00348"></a>00348 <span class="keywordflow">if</span> (new_bits)
376
<a name="l00349"></a>00349 {
377
<a name="l00350"></a>00350 <span class="keywordtype">unsigned</span> new_count = <a class="code" href="a00120.html#gaef40342b0c318391df3db2b891acf7c1">bm::word_bitcount</a>(new_bits);
378
<a name="l00351"></a>00351
379
<a name="l00352"></a>00352 <span class="comment">// check if we accidentally picked more bits than needed</span>
380
<a name="l00353"></a>00353 <span class="keywordflow">if</span> (new_count > count)
381
<a name="l00354"></a>00354 {
382
<a name="l00355"></a>00355 <a class="code" href="a00092.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(count);
383
<a name="l00356"></a>00356
384
<a name="l00357"></a>00357 <span class="keywordtype">unsigned</span> <span class="keywordtype">char</span> blist[64];
385
<a name="l00358"></a>00358 <span class="keywordtype">unsigned</span> arr_size = <a class="code" href="a00120.html#ga3c81f6bff8866ec3ed0a94903eee96b7" title="Unpacks word into list of ON bit indexes (quad-bit based).">bm::bit_list_4</a>(new_bits, blist);
386
<a name="l00359"></a>00359 <a class="code" href="a00092.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(arr_size == new_count);
387
<a name="l00360"></a>00360 std::random_shuffle(blist, blist + arr_size);
388
<a name="l00361"></a>00361 <span class="keywordtype">unsigned</span> value = 0;
389
<a name="l00362"></a>00362 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> j = 0; j < count; ++j)
390
<a name="l00363"></a>00363 {
391
<a name="l00364"></a>00364 value |= (1 << blist[j]);
392
<a name="l00365"></a>00365 }
393
<a name="l00366"></a>00366 new_bits = value;
394
<a name="l00367"></a>00367 new_count = count;
395
<a name="l00368"></a>00368
396
<a name="l00369"></a>00369 <a class="code" href="a00092.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>(<a class="code" href="a00120.html#gaef40342b0c318391df3db2b891acf7c1">bm::word_bitcount</a>(new_bits) == count);
397
<a name="l00370"></a>00370 <a class="code" href="a00092.html#aa44515fab0ace8928d1cb82009a95bf8">BM_ASSERT</a>((new_bits & ~blk_src[i]) == 0);
398
<a name="l00371"></a>00371 }
399
<a name="l00372"></a>00372
400
<a name="l00373"></a>00373 blk_out[i] |= new_bits;
401
<a name="l00374"></a>00374 <span class="keywordflow">return</span> new_count;
402
<a name="l00375"></a>00375 }
403
<a name="l00376"></a>00376
404
<a name="l00377"></a>00377 <span class="keywordflow">return</span> 0;
405
<a name="l00378"></a>00378 }
406
<a name="l00379"></a>00379
407
<a name="l00380"></a>00380
408
<a name="l00381"></a>00381 <span class="keyword">template</span><<span class="keyword">class</span> BV>
409
<a name="l00382"></a>00382 <span class="keywordtype">void</span> random_subset<BV>::get_random_array(<a class="code" href="a00115.html#a17fd5ba52db3ddda05e6f8dd5000a1a4">bm::word_t</a>* blk_out,
410
<a name="l00383"></a>00383 <a class="code" href="a00115.html#ac654d6319039a86546d235a236fc7cf6">bm::gap_word_t</a>* <a class="code" href="a00120.html#gaae3ae537760044543f842363e4614e82" title="Unpacks word into list of ON bit indexes.">bit_list</a>,
411
<a name="l00384"></a>00384 <span class="keywordtype">unsigned</span> bit_list_size,
412
<a name="l00385"></a>00385 <span class="keywordtype">unsigned</span> count)
413
413
<a name="l00386"></a>00386 {
414
<a name="l00387"></a>00387 <span class="keywordflow">return</span> _mm_or_si128(a, b);
415
<a name="l00388"></a>00388 }
416
<a name="l00389"></a>00389
417
<a name="l00390"></a>00390
418
<a name="l00391"></a>00391 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
419
<a name="l00392"></a><a class="code" href="a00110.html#a6f5de19ee3e1be05037908b4777c4da8">00392</a> __m128i <a class="code" href="a00110.html#a6f5de19ee3e1be05037908b4777c4da8">sse2_xor</a>(__m128i a, __m128i b)
420
<a name="l00393"></a>00393 {
421
<a name="l00394"></a>00394 <span class="keywordflow">return</span> _mm_xor_si128(a, b);
422
<a name="l00395"></a>00395 }
423
<a name="l00396"></a>00396
424
<a name="l00397"></a>00397 <a class="code" href="a00089.html#a938734d014fb68dd8b2251fe8ec2b025">BMFORCEINLINE</a>
425
<a name="l00398"></a><a class="code" href="a00110.html#ab3e6d46fcba1bc2a1a5390c10f571382">00398</a> __m128i <a class="code" href="a00110.html#ab3e6d46fcba1bc2a1a5390c10f571382">sse2_sub</a>(__m128i a, __m128i b)
426
<a name="l00399"></a>00399 {
427
<a name="l00400"></a>00400 <span class="keywordflow">return</span> _mm_andnot_si128(b, a);
428
<a name="l00401"></a>00401 }
429
<a name="l00402"></a>00402
430
<a name="l00403"></a>00403
431
<a name="l00404"></a>00404
432
<a name="l00405"></a>00405 } <span class="comment">// namespace</span>
433
<a name="l00406"></a>00406
434
<a name="l00407"></a>00407
435
<a name="l00408"></a>00408
436
<a name="l00409"></a>00409 <span class="preprocessor">#endif</span>
414
<a name="l00387"></a>00387 std::random_shuffle(bit_list, bit_list + bit_list_size);
415
<a name="l00388"></a>00388 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i < count; ++i)
416
<a name="l00389"></a>00389 {
417
<a name="l00390"></a>00390 <a class="code" href="a00120.html#ga2becf9a16ec20ab124ca8938e34b4aa8" title="Set 1 bit in a block.">bm::set_bit</a>(blk_out, bit_list[i]);
418
<a name="l00391"></a>00391 }
419
<a name="l00392"></a>00392 }
420
<a name="l00393"></a>00393
421
<a name="l00394"></a>00394 <span class="keyword">template</span><<span class="keyword">class</span> BV>
422
<a name="l00395"></a>00395 <span class="keywordtype">unsigned</span> random_subset<BV>::find_max_block()
423
<a name="l00396"></a>00396 {
424
<a name="l00397"></a>00397 <span class="keywordflow">if</span> (candidates_count_)
425
<a name="l00398"></a>00398 {
426
<a name="l00399"></a>00399 <span class="keywordflow">return</span> block_candidates_[--candidates_count_];
427
<a name="l00400"></a>00400 }
428
<a name="l00401"></a>00401
429
<a name="l00402"></a>00402 <span class="keywordtype">unsigned</span> candidate = 0;
430
<a name="l00403"></a>00403 <span class="keywordtype">unsigned</span> max_i = 0;
431
<a name="l00404"></a>00404 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i <= blocks_; ++i)
432
<a name="l00405"></a>00405 {
433
<a name="l00406"></a>00406 <span class="keywordflow">if</span> (block_bits_take_[i] == 0) <span class="keywordflow">continue</span>;
434
<a name="l00407"></a>00407 <span class="keywordflow">if</span> (block_bits_take_[i] == candidate)
435
<a name="l00408"></a>00408 {
436
<a name="l00409"></a>00409 block_candidates_[candidates_count_++] = i;
437
<a name="l00410"></a>00410 }
438
<a name="l00411"></a>00411 <span class="keywordflow">else</span>
439
<a name="l00412"></a>00412 {
440
<a name="l00413"></a>00413 <span class="keywordtype">unsigned</span> diff = abs((<span class="keywordtype">int</span>)block_bits_take_[i] - (<span class="keywordtype">int</span>)candidate);
441
<a name="l00414"></a>00414 <span class="keywordtype">double</span> d = (double)diff / (<span class="keywordtype">double</span>)candidate;
442
<a name="l00415"></a>00415
443
<a name="l00416"></a>00416 <span class="keywordflow">if</span> (d < 0.20f) <span class="comment">// delta is statistically insignificant</span>
444
<a name="l00417"></a>00417 {
445
<a name="l00418"></a>00418 block_candidates_[candidates_count_++] = i;
446
<a name="l00419"></a>00419 }
447
<a name="l00420"></a>00420 <span class="keywordflow">else</span>
448
<a name="l00421"></a>00421 <span class="keywordflow">if</span> (block_bits_take_[i] > candidate)
449
<a name="l00422"></a>00422 {
450
<a name="l00423"></a>00423 candidate = block_bits_take_[i];
451
<a name="l00424"></a>00424 max_i = i;
452
<a name="l00425"></a>00425 candidates_count_ = 0;
453
<a name="l00426"></a>00426 block_candidates_[candidates_count_++] = i;
454
<a name="l00427"></a>00427 }
455
<a name="l00428"></a>00428 }
456
<a name="l00429"></a>00429 }
457
<a name="l00430"></a>00430
458
<a name="l00431"></a>00431 <span class="keywordflow">if</span> (candidates_count_ > 1)
459
<a name="l00432"></a>00432 {
460
<a name="l00433"></a>00433 std::random_shuffle(block_candidates_, block_candidates_ + candidates_count_);
461
<a name="l00434"></a>00434 <span class="keywordflow">return</span> find_max_block();
462
<a name="l00435"></a>00435 }
463
<a name="l00436"></a>00436 <span class="keywordflow">return</span> max_i;
464
<a name="l00437"></a>00437 }
465
<a name="l00438"></a>00438
466
<a name="l00439"></a>00439
467
<a name="l00440"></a>00440 } <span class="comment">// namespace</span>
468
<a name="l00441"></a>00441
469
<a name="l00442"></a>00442 <span class="preprocessor">#include "<a class="code" href="a00101.html">bmundef.h</a>"</span>
470
<a name="l00443"></a>00443
471
<a name="l00444"></a>00444 <span class="preprocessor">#endif</span>
437
472
</pre></div></div>
438
<hr size="1"/><address style="text-align: right;"><small>Generated on Sun Nov 22 10:49:35 2009 for BitMagic by
473
<hr size="1"/><address style="text-align: right;"><small>Generated on Fri Jan 8 20:09:19 2010 for BitMagic by
439
474
<a href="http://www.doxygen.org/index.html">
440
475
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.1 </small></address>