From: Joel Holdsworth Date: Sun, 22 Jul 2012 07:21:30 +0000 (+0100) Subject: Implemented O(log(N)) wave plotting X-Git-Tag: pulseview-0.1.0~316 X-Git-Url: https://sigrok.org/gitweb/?p=pulseview.git;a=commitdiff_plain;h=0b02e0578cf750906b20848d98e73b21c23eda42 Implemented O(log(N)) wave plotting --- diff --git a/logicdatasnapshot.cpp b/logicdatasnapshot.cpp index 8f7e9922..e751b9d1 100644 --- a/logicdatasnapshot.cpp +++ b/logicdatasnapshot.cpp @@ -32,6 +32,7 @@ using namespace std; const int LogicDataSnapshot::MipMapScalePower = 4; const int LogicDataSnapshot::MipMapScaleFactor = 1 << MipMapScalePower; +const float LogicDataSnapshot::LogMipMapScaleFactor = logf(MipMapScaleFactor); const uint64_t LogicDataSnapshot::MipMapDataUnit = 64*1024; // bytes LogicDataSnapshot::LogicDataSnapshot( @@ -167,41 +168,153 @@ uint64_t LogicDataSnapshot::get_sample(uint64_t index) const void LogicDataSnapshot::get_subsampled_edges( std::vector &edges, int64_t start, int64_t end, - int64_t quantization_length, int sig_index) + float min_length, int sig_index) { + int64_t index; + int level; + assert(start >= 0); - assert(end < get_sample_count()); + assert(end <= get_sample_count()); assert(start <= end); - assert(quantization_length > 0); + assert(min_length > 0); assert(sig_index >= 0); assert(sig_index < SR_MAX_NUM_PROBES); + const int min_level = max((int)floorf(logf(min_length) / + LogMipMapScaleFactor) - 1, 0); const uint64_t sig_mask = 1 << sig_index; // Add the initial state bool last_sample = get_sample(start) & sig_mask; edges.push_back(pair(start, last_sample)); - for(int64_t i = start + 1; i < end; i++) + index = start + 1; + for(index = start + 1; index < end;) { - const bool sample = get_sample(i) & sig_mask; + level = min_level; - // Check if we hit an edge - if(sample != last_sample) + if(min_length < MipMapScaleFactor) + { + // Search individual samples up to the beginning of + // the next first level mip map block + const uint64_t final_sample = min(end, + pow2_ceil(index, MipMapScalePower)); + + for(index; + index < final_sample && + (index & ~(~0 << MipMapScalePower)) != 0; + index++) + { + const bool sample = + (get_sample(index) & sig_mask) != 0; + if(sample != last_sample) + break; + } + } + else + { + // If resolution is less than a mip map block, + // round up to the beginning of the mip-map block + // for this level of detail + const int min_level_scale_power = + (level + 1) * MipMapScalePower; + index = pow2_ceil(index, min_level_scale_power); + } + + // Slide right and zoom out at the beginnings of mip-map + // blocks until we encounter a change + while(1) + { + const int level_scale_power = + (level + 1) * MipMapScalePower; + const uint64_t offset = index >> level_scale_power; + assert(offset >= 0); + + // Check if we reached the last block at this level, + // or if there was a change in this block + if(offset >= _mip_map[level].length || + (*(uint64_t*)((uint8_t*)_mip_map[level].data + + _unit_size * offset) & sig_mask)) + break; + + if((offset & ~(~0 << MipMapScalePower)) == 0) + { + // If we are now at the beginning of a higher + // level mip-map block ascend one level + if(!_mip_map[level + 1].data) + break; + + level++; + } + else + { + // Slide right to the beginning of the next mip + // map block + index = pow2_ceil(index, level_scale_power); + } + } + + // Zoom in, and slide right until we encounter a change, + // and repeat until we reach min_level + while(1) + { + assert(_mip_map[level].data); + + const int level_scale_power = + (level + 1) * MipMapScalePower; + const uint64_t offset = index >> level_scale_power; + assert(offset >= 0); + + // Check if we reached the last block at this level, + // or if there was a change in this block + if(offset >= _mip_map[level].length || + (*(uint64_t*)((uint8_t*)_mip_map[level].data + + _unit_size * offset) & sig_mask)) + { + // Zoom in unless we reached the minimum zoom + if(level == min_level) + break; + + level--; + } + else + { + // Slide right to the beginning of the next mip map block + index = pow2_ceil(index, level_scale_power); + } + } + + // If individual samples within the limit of resolution, + // do a linear search for the next transition within the block + if(min_length < MipMapScaleFactor) + { + for(index; index < end; index++) + { + const bool sample = + (get_sample(index) & sig_mask) != 0; + if(sample != last_sample) + break; + } + } + + if(index < end) { // Take the last sample of the quanization block - const int64_t final_index = - min((i - (i % quantization_length) + - quantization_length - 1), end); + const int64_t block_length = (int64_t)max(min_length, 1.0f); + const int64_t rem = index % block_length; + const int64_t final_index = min(index + (rem == 0 ? 0 : + block_length - rem), end); // Store the final state const bool final_sample = get_sample(final_index) & sig_mask; edges.push_back(pair( final_index, final_sample)); - // Continue to sampling - i = final_index; + // Continue to sample + index = final_index; last_sample = final_sample; + + index++; } } @@ -209,3 +322,8 @@ void LogicDataSnapshot::get_subsampled_edges( edges.push_back(pair(end, get_sample(end) & sig_mask)); } + +int64_t LogicDataSnapshot::pow2_ceil(int64_t x, int power) +{ + return ((x >> power) + 1) << power; +} diff --git a/logicdatasnapshot.h b/logicdatasnapshot.h index c49d05d5..b68a9921 100644 --- a/logicdatasnapshot.h +++ b/logicdatasnapshot.h @@ -37,6 +37,7 @@ private: static const int ScaleStepCount = 10; static const int MipMapScalePower; static const int MipMapScaleFactor; + static const float LogMipMapScaleFactor; static const uint64_t MipMapDataUnit; public: @@ -63,13 +64,17 @@ public: * @param[out] edges The vector to place the edges into. * @param[in] start The start sample index. * @param[in] end The end sample index. - * @param[in] quantization_length The minimum period of time that + * @param[in] min_length The minimum number of samples that * can be resolved at this level of detail. * @param[in] sig_index The index of the signal. **/ void get_subsampled_edges(std::vector &edges, int64_t start, int64_t end, - int64_t quantization_length, int sig_index); + float min_length, int sig_index); + +private: + + static inline int64_t pow2_ceil(int64_t x, int power); private: struct MipMapLevel _mip_map[ScaleStepCount]; diff --git a/logicsignal.cpp b/logicsignal.cpp index 79a27ddd..69d58cb1 100644 --- a/logicsignal.cpp +++ b/logicsignal.cpp @@ -33,8 +33,6 @@ using namespace boost; using namespace std; -const float Log2 = logf(2.0f); - const float LogicSignal::Margin = 10.0f; const float LogicSignal::EdgeColour[3] = {0.50f, 0.50f, 0.50f}; @@ -90,13 +88,11 @@ void LogicSignal::paint(QGLWidget &widget, const QRect &rect, const double samples_per_pixel = samplerate * scale; const double start = samplerate * (offset - start_time); const double end = start + samples_per_pixel * rect.width(); - const int64_t quantization_length = 1LL << (int64_t)floorf( - max(logf((float)samples_per_pixel) / Log2, 0.0f)); snapshot->get_subsampled_edges(edges, min(max((int64_t)floor(start), (int64_t)0), last_sample), min(max((int64_t)ceil(end), (int64_t)0), last_sample), - quantization_length, _probe_index); + samples_per_pixel, _probe_index); // Paint the edges const unsigned int edge_point_count = (edges.size() - 2) * 2; diff --git a/test/logicdatasnapshot.cpp b/test/logicdatasnapshot.cpp index 67e7dc10..c05b13f9 100644 --- a/test/logicdatasnapshot.cpp +++ b/test/logicdatasnapshot.cpp @@ -22,6 +22,8 @@ #include "../logicdatasnapshot.h" +using namespace std; + void push_logic(LogicDataSnapshot &s, unsigned int length, uint8_t value) { sr_datafeed_logic logic; @@ -43,6 +45,8 @@ BOOST_AUTO_TEST_CASE(LogicDataSnapshotTest) LogicDataSnapshot s(logic); + //----- Test LogicDataSnapshot::push_logic -----// + BOOST_CHECK(s.get_sample_count() == 0); for(int i = 0; i < LogicDataSnapshot::ScaleStepCount; i++) { @@ -101,4 +105,26 @@ BOOST_AUTO_TEST_CASE(LogicDataSnapshotTest) BOOST_CHECK_EQUAL(m1.data_length, LogicDataSnapshot::MipMapDataUnit); BOOST_REQUIRE(m1.data != NULL); BOOST_CHECK_EQUAL(((uint8_t*)m1.data)[0], 0x11); + + //----- Test LogicDataSnapshot::get_subsampled_edges -----// + + // Test a full view at full zoom. + vector edges; + s.get_subsampled_edges(edges, 0, 255, 1, 0); + BOOST_REQUIRE_EQUAL(edges.size(), 4); + + BOOST_CHECK_EQUAL(edges[0].first, 0); + BOOST_CHECK_EQUAL(edges[1].first, 8); + BOOST_CHECK_EQUAL(edges[2].first, 16); + BOOST_CHECK_EQUAL(edges[3].first, 255); + + // Test a subset at high zoom + edges.clear(); + s.get_subsampled_edges(edges, 6, 17, 0.05f, 0); + BOOST_REQUIRE_EQUAL(edges.size(), 4); + + BOOST_CHECK_EQUAL(edges[0].first, 6); + BOOST_CHECK_EQUAL(edges[1].first, 8); + BOOST_CHECK_EQUAL(edges[2].first, 16); + BOOST_CHECK_EQUAL(edges[3].first, 17); }