00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef WIFI_TRACES_SIMILARITY_HXX_
00023 # define WIFI_TRACES_SIMILARITY_HXX_
00024
00025 # include "similarity.hh"
00026
00027 # include <boost/tuple/tuple_comparison.hpp>
00028
00029 # include <wipal/wifi/frame/filter/non_noisy_prism.hh>
00030 # include <wipal/wifi/frame/filter/uniquely_identifiable.hh>
00031
00032 namespace wifi
00033 {
00034
00035 namespace traces
00036 {
00037
00039 namespace similarity_helpers
00040 {
00041
00042 template <class I>
00043 void
00044 info(unsigned i, const I& t)
00045 {
00046
00047 (void) i;
00048 (void) t;
00049
00050 # ifdef WP_ENABLE_INFO
00051 std::cerr << "INFO: Trace " << i << " is " << t->file_name()
00052 << std::endl;
00053 # endif // WP_ENABLE_INFO
00054 }
00055
00056 template <class Result, class Intersector, class I1, class I2>
00057 unsigned
00058 score(Result& r, Intersector& i, const I1& lhs, const I2& rhs)
00059 {
00060 unsigned count = 0;
00061
00062 typename Intersector::const_iterator it = i.begin();
00063 while (it != i.end() and
00064 it.rhs_uframe_count() < similarity_score_limit)
00065 {
00066 ++it;
00067 ++count;
00068 }
00069 if (it != i.end() and count > 0)
00070 --count;
00071
00072 r.insert(boost::make_tuple(count, lhs, rhs));
00073 # ifdef WP_ENABLE_INFO
00074 std::cerr << "INFO: Score for " << lhs->file_name()
00075 << " and " << rhs->file_name()
00076 << " is " << count << '.' << std::endl;
00077 # endif // WP_ENABLE_INFO
00078
00079 return count;
00080 }
00081
00082 template <class U, class HT, template <class, class, class> class I,
00083 class C>
00084 std::set< boost::tuple<unsigned, typename C::iterator,
00085 typename C::iterator> >
00086 ignore_prism(C& traces,
00087 addr_mapping& mapping,
00088 tool::endian::endianness endianness)
00089 {
00090 using frame::filter::uniquely_identifiable;
00091
00092 typedef typename C::iterator trace_iterator;
00093 typedef typename C::value_type::const_iterator frame_iterator;
00094 typedef uniquely_identifiable<U, frame_iterator, HT> ui;
00095 typedef typename ui::const_iterator ui_iterator;
00096 typedef I<ui_iterator, ui_iterator, tool::bottom> intersector;
00097 typedef typename intersector::const_iterator i_iterator;
00098
00099 typedef std::set< boost::tuple<unsigned, typename C::iterator,
00100 typename C::iterator> >
00101 result;
00102
00103 result r;
00104
00105 if (traces.empty())
00106 return r;
00107
00108 trace_iterator t = traces.begin();
00109 trace_iterator lhs, rhs;
00110
00111 while (lhs = t++, rhs = t, rhs != traces.end())
00112 {
00113 info(1, lhs);
00114
00115 ui lhs_u (lhs->begin(), lhs->end(),
00116 mapping, endianness);
00117 intersector i (lhs_u.begin(), lhs_u.end(),
00118 lhs_u.begin(), lhs_u.end());
00119 do
00120 {
00121 info(2, rhs);
00122
00123 ui rhs_u (rhs->begin(), rhs->end(),
00124 mapping, endianness);
00125
00126 i.reset_rhs(rhs_u.begin(), rhs_u.end());
00127 score(r, i, lhs, rhs);
00128 }
00129 while (++rhs != traces.end());
00130 }
00131 return r;
00132 }
00133
00134 template <class U, class HT, template <class, class, class> class I,
00135 class C>
00136 std::set< boost::tuple<unsigned, typename C::iterator,
00137 typename C::iterator> >
00138 filter_prism(C& traces,
00139 addr_mapping& mapping,
00140 tool::endian::endianness endianness)
00141 {
00142 using frame::filter::non_noisy_prism;
00143 using frame::filter::uniquely_identifiable;
00144
00145 typedef typename C::iterator trace_iterator;
00146 typedef typename C::value_type::const_iterator frame_iterator;
00147 typedef non_noisy_prism<frame_iterator> nnp;
00148 typedef typename nnp::const_iterator nnp_iterator;
00149 typedef uniquely_identifiable<U, nnp_iterator, HT> ui;
00150 typedef typename ui::const_iterator ui_iterator;
00151 typedef I<ui_iterator, ui_iterator, tool::bottom> intersector;
00152 typedef typename intersector::const_iterator i_iterator;
00153
00154 typedef std::set< boost::tuple<unsigned, typename C::iterator,
00155 typename C::iterator> >
00156 result;
00157
00158 result r;
00159
00160 if (traces.empty())
00161 return r;
00162
00163 trace_iterator t = traces.begin();
00164 trace_iterator lhs, rhs;
00165
00166 while (lhs = t++, rhs = t, rhs != traces.end())
00167 {
00168 info(1, lhs);
00169
00170 nnp lhs_n (lhs->begin(), lhs->end());
00171 ui lhs_u (lhs_n.begin(), lhs_n.end(),
00172 mapping, endianness);
00173 intersector i (lhs_u.begin(), lhs_u.end(),
00174 lhs_u.begin(), lhs_u.end());
00175 do
00176 {
00177 info(2, rhs);
00178
00179 nnp rhs_n (rhs->begin(), rhs->end());
00180 ui rhs_u (rhs_n.begin(), rhs_n.end(),
00181 mapping, endianness);
00182
00183 i.reset_rhs(rhs_u.begin(), rhs_u.end());
00184 score(r, i, lhs, rhs);
00185 }
00186 while (++rhs != traces.end());
00187 }
00188 return r;
00189 }
00190
00191 }
00192
00193
00194 template <class U, class P, template <class, class, class> class I,
00195 class C>
00196 std::set< boost::tuple<unsigned, typename C::iterator,
00197 typename C::iterator> >
00198 similarity(C& traces,
00199 addr_mapping& mapping,
00200 bool filter_noisy_prism,
00201 tool::endian::endianness endianness)
00202 {
00203 return filter_noisy_prism?
00204 similarity_helpers::filter_prism<U, P, I>(traces, mapping, endianness):
00205 similarity_helpers::ignore_prism<U, P, I>(traces, mapping, endianness);
00206 }
00207
00208 }
00209
00210 }
00211
00212 #endif // ! WIFI_TRACES_SIMILARITY_HXX_