From: Joel Holdsworth Date: Mon, 16 Jul 2012 19:45:19 +0000 (+0100) Subject: Added subsampling for fast lookup X-Git-Tag: pulseview-0.1.0~317 X-Git-Url: https://sigrok.org/gitweb/?p=pulseview.git;a=commitdiff_plain;h=4ceab49abb3c0160cfefdefa6a9c84284d30f850 Added subsampling for fast lookup --- diff --git a/CMakeLists.txt b/CMakeLists.txt index e0edfbc3..2d62dfcb 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -46,6 +46,7 @@ set(sigrok-qt2_RESOURCES ) set(sigrok-qt2_TEST_SOURCES + test/logicdatasnapshot.cpp test/test.cpp datasnapshot.cpp logicdatasnapshot.cpp diff --git a/logicdatasnapshot.cpp b/logicdatasnapshot.cpp index e29a866e..8f7e9922 100644 --- a/logicdatasnapshot.cpp +++ b/logicdatasnapshot.cpp @@ -18,25 +18,142 @@ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ -#include "logicdatasnapshot.h" +#include "extdef.h" #include +#include +#include + +#include + +#include "logicdatasnapshot.h" using namespace std; +const int LogicDataSnapshot::MipMapScalePower = 4; +const int LogicDataSnapshot::MipMapScaleFactor = 1 << MipMapScalePower; +const uint64_t LogicDataSnapshot::MipMapDataUnit = 64*1024; // bytes + LogicDataSnapshot::LogicDataSnapshot( const sr_datafeed_logic &logic) : - DataSnapshot(logic.unitsize) + DataSnapshot(logic.unitsize), + _last_append_sample(0) { + memset(_mip_map, 0, sizeof(_mip_map)); append_payload(logic); } +LogicDataSnapshot::~LogicDataSnapshot() +{ + BOOST_FOREACH(MipMapLevel &l, _mip_map) + free(l.data); +} + void LogicDataSnapshot::append_payload( const sr_datafeed_logic &logic) { assert(_unit_size == logic.unitsize); + const uint64_t prev_length = _data_length; append_data(logic.data, logic.length); + + // Generate the first mip-map from the data + append_payload_to_mipmap(); +} + +void LogicDataSnapshot::reallocate_mip_map(MipMapLevel &m) +{ + const uint64_t new_data_length = ((m.length + MipMapDataUnit - 1) / + MipMapDataUnit) * MipMapDataUnit; + if(new_data_length > m.data_length) + { + m.data_length = new_data_length; + m.data = realloc(m.data, new_data_length * _unit_size); + } +} + +void LogicDataSnapshot::append_payload_to_mipmap() +{ + MipMapLevel &m0 = _mip_map[0]; + uint64_t prev_length; + const uint8_t *src_ptr; + uint8_t *dest_ptr; + uint64_t accumulator; + unsigned int diff_counter; + + // Expand the data buffer to fit the new samples + prev_length = m0.length; + m0.length = _data_length / MipMapScaleFactor; + + // Break off if there are no new samples to compute + if(m0.length == prev_length) + return; + + reallocate_mip_map(m0); + + dest_ptr = (uint8_t*)m0.data + prev_length * _unit_size; + + // Iterate through the samples to populate the first level mipmap + accumulator = 0; + diff_counter = MipMapScaleFactor; + const uint8_t *end_src_ptr = (uint8_t*)_data + + m0.length * _unit_size * MipMapScaleFactor; + for(src_ptr = (uint8_t*)_data + + prev_length * _unit_size * MipMapScaleFactor; + src_ptr < end_src_ptr;) + { + // Accumulate transitions which have occurred in this sample + accumulator = 0; + diff_counter = MipMapScaleFactor; + while(diff_counter-- > 0) + { + const uint64_t sample = *(uint64_t*)src_ptr; + accumulator |= _last_append_sample ^ sample; + _last_append_sample = sample; + src_ptr += _unit_size; + } + + *(uint64_t*)dest_ptr = accumulator; + dest_ptr += _unit_size; + } + + // Compute higher level mipmaps + for(int level = 1; level < ScaleStepCount; level++) + { + MipMapLevel &m = _mip_map[level]; + const MipMapLevel &ml = _mip_map[level-1]; + + // Expand the data buffer to fit the new samples + prev_length = m.length; + m.length = ml.length / MipMapScaleFactor; + + // Break off if there are no more samples to computed + if(m.length == prev_length) + break; + + reallocate_mip_map(m); + + // Subsample the level lower level + src_ptr = (uint8_t*)ml.data + + _unit_size * prev_length * MipMapScaleFactor; + const uint8_t *end_dest_ptr = + (uint8_t*)m.data + _unit_size * m.length; + for(dest_ptr = (uint8_t*)m.data + + _unit_size * prev_length; + dest_ptr < end_dest_ptr; + dest_ptr += _unit_size) + { + accumulator = 0; + diff_counter = MipMapScaleFactor; + while(diff_counter-- > 0) + { + accumulator |= *(uint64_t*)src_ptr; + src_ptr += _unit_size; + } + + *(uint64_t*)dest_ptr = accumulator; + } + } } uint64_t LogicDataSnapshot::get_sample(uint64_t index) const diff --git a/logicdatasnapshot.h b/logicdatasnapshot.h index e6fee52b..c49d05d5 100644 --- a/logicdatasnapshot.h +++ b/logicdatasnapshot.h @@ -25,14 +25,36 @@ class LogicDataSnapshot : public DataSnapshot { +private: + struct MipMapLevel + { + uint64_t length; + uint64_t data_length; + void *data; + }; + +private: + static const int ScaleStepCount = 10; + static const int MipMapScalePower; + static const int MipMapScaleFactor; + static const uint64_t MipMapDataUnit; + public: typedef std::pair EdgePair; public: LogicDataSnapshot(const sr_datafeed_logic &logic); + virtual ~LogicDataSnapshot(); + void append_payload(const sr_datafeed_logic &logic); +private: + void reallocate_mip_map(MipMapLevel &m); + + void append_payload_to_mipmap(); + +public: uint64_t get_sample(uint64_t index) const; /** @@ -48,4 +70,10 @@ public: void get_subsampled_edges(std::vector &edges, int64_t start, int64_t end, int64_t quantization_length, int sig_index); + +private: + struct MipMapLevel _mip_map[ScaleStepCount]; + uint64_t _last_append_sample; + + friend class LogicDataSnapshotTest; }; diff --git a/test/logicdatasnapshot.cpp b/test/logicdatasnapshot.cpp new file mode 100644 index 00000000..67e7dc10 --- /dev/null +++ b/test/logicdatasnapshot.cpp @@ -0,0 +1,104 @@ +/* + * This file is part of the sigrok project. + * + * Copyright (C) 2012 Joel Holdsworth + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include + +#include "../logicdatasnapshot.h" + +void push_logic(LogicDataSnapshot &s, unsigned int length, uint8_t value) +{ + sr_datafeed_logic logic; + logic.unitsize = 1; + logic.length = length; + logic.data = new uint8_t[length]; + memset(logic.data, value, length * logic.unitsize); + s.append_payload(logic); + delete[] (uint8_t*)logic.data; +} + +BOOST_AUTO_TEST_CASE(LogicDataSnapshotTest) +{ + // Create an empty LogicDataSnapshot object + sr_datafeed_logic logic; + logic.length = 0; + logic.unitsize = 1; + logic.data = NULL; + + LogicDataSnapshot s(logic); + + BOOST_CHECK(s.get_sample_count() == 0); + for(int i = 0; i < LogicDataSnapshot::ScaleStepCount; i++) + { + const LogicDataSnapshot::MipMapLevel &m = s._mip_map[i]; + BOOST_CHECK_EQUAL(m.length, 0); + BOOST_CHECK_EQUAL(m.data_length, 0); + BOOST_CHECK(m.data == NULL); + } + + // Push 8 samples of all zeros + push_logic(s, 8, 0); + + BOOST_CHECK(s.get_sample_count() == 8); + + // There should not be enough samples to have a single mip map sample + for(int i = 0; i < LogicDataSnapshot::ScaleStepCount; i++) + { + const LogicDataSnapshot::MipMapLevel &m = s._mip_map[i]; + BOOST_CHECK_EQUAL(m.length, 0); + BOOST_CHECK_EQUAL(m.data_length, 0); + BOOST_CHECK(m.data == NULL); + } + + // Push 8 samples of 0x11s to bring the total up to 16 + push_logic(s, 8, 0x11); + + // There should now be enough data for exactly one sample + // in mip map level 0, and that sample should be 0 + const LogicDataSnapshot::MipMapLevel &m0 = s._mip_map[0]; + BOOST_CHECK_EQUAL(m0.length, 1); + BOOST_CHECK_EQUAL(m0.data_length, LogicDataSnapshot::MipMapDataUnit); + BOOST_REQUIRE(m0.data != NULL); + BOOST_CHECK_EQUAL(((uint8_t*)m0.data)[0], 0x11); + + // The higher levels should still be empty + for(int i = 1; i < LogicDataSnapshot::ScaleStepCount; i++) + { + const LogicDataSnapshot::MipMapLevel &m = s._mip_map[i]; + BOOST_CHECK_EQUAL(m.length, 0); + BOOST_CHECK_EQUAL(m.data_length, 0); + BOOST_CHECK(m.data == NULL); + } + + // Push 240 samples of all zeros to bring the total up to 256 + push_logic(s, 240, 0); + + BOOST_CHECK_EQUAL(m0.length, 16); + BOOST_CHECK_EQUAL(m0.data_length, LogicDataSnapshot::MipMapDataUnit); + + BOOST_CHECK_EQUAL(((uint8_t*)m0.data)[1], 0x11); + for(int i = 2; i < m0.length; i++) + BOOST_CHECK_EQUAL(((uint8_t*)m0.data)[i], 0); + + const LogicDataSnapshot::MipMapLevel &m1 = s._mip_map[1]; + BOOST_CHECK_EQUAL(m1.length, 1); + BOOST_CHECK_EQUAL(m1.data_length, LogicDataSnapshot::MipMapDataUnit); + BOOST_REQUIRE(m1.data != NULL); + BOOST_CHECK_EQUAL(((uint8_t*)m1.data)[0], 0x11); +} diff --git a/test/test.cpp b/test/test.cpp index acb3c963..2c278c04 100644 --- a/test/test.cpp +++ b/test/test.cpp @@ -20,18 +20,3 @@ #define BOOST_TEST_MAIN #include - -#include "../logicdatasnapshot.h" - -BOOST_AUTO_TEST_CASE(LogicDataSnapshotTest) -{ - // Create an empty LogicDataSnapshot object - sr_datafeed_logic logic; - logic.length = 0; - logic.unitsize = 1; - logic.data = NULL; - - LogicDataSnapshot s(logic); - - BOOST_CHECK(s.get_sample_count() == 0); -}