X-Git-Url: https://sigrok.org/gitweb/?p=pulseview.git;a=blobdiff_plain;f=logicdatasnapshot.cpp;h=5d6505535fe35f81274ece384ad9557b3687c75f;hp=032d9c81e464f2dd3311fd31a076a83073aa34a1;hb=b36d8550c43e11d3b86cf7ace35483c8957835a3;hpb=2858b391af20bd46c9a7da17195ec8d58bcd12c3 diff --git a/logicdatasnapshot.cpp b/logicdatasnapshot.cpp index 032d9c81..5d650553 100644 --- a/logicdatasnapshot.cpp +++ b/logicdatasnapshot.cpp @@ -18,31 +18,149 @@ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ -#include "logicdatasnapshot.h" +#include "extdef.h" #include +#include +#include +#include + +#include + +#include "logicdatasnapshot.h" 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( 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); 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 = _sample_count / 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 { assert(_data); - assert(index >= 0 && index < _data_length); + assert(index >= 0 && index < _sample_count); return *(uint64_t*)((uint8_t*)_data + index * _unit_size); } @@ -50,45 +168,188 @@ 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 = start; + int level; + bool last_sample; + bool fast_forward; + 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 uint64_t sig_mask = 1 << sig_index; + const int64_t block_length = (int64_t)max(min_length, 1.0f); + const int min_level = max((int)floorf(logf(min_length) / + LogMipMapScaleFactor) - 1, 0); + const uint64_t sig_mask = 1ULL << sig_index; - // Add the initial state - bool last_sample = get_sample(start) & sig_mask; - edges.push_back(pair(start, last_sample)); + // Store the initial state + last_sample = (get_sample(start) & sig_mask) != 0; + edges.push_back(pair(index++, last_sample)); - for(int64_t i = start + 1; i < end - 1; i++) + while(index + block_length <= end) { - const bool sample = get_sample(i) & sig_mask; + //----- Continue to search -----// + level = min_level; + fast_forward = true; + + if(min_length < MipMapScaleFactor) + { + // Search individual samples up to the beginning of + // the next first level mip map block + const uint64_t final_index = min(end, + pow2_ceil(index, MipMapScalePower)); + + for(index; + index < final_index && + (index & ~(~0 << MipMapScalePower)) != 0; + index++) + { + const bool sample = + (get_sample(index) & sig_mask) != 0; - // Check if we hit an edge - if(sample != last_sample) + // If there was a change we cannot fast forward + if(sample != last_sample) { + fast_forward = false; + break; + } + } + } + else { - // Take the last sample of the quanization block - const int64_t final_index = - min((i - (i % quantization_length) + - quantization_length - 1), 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; - last_sample = final_sample; + // 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); + if(index >= end) + break; + + // We can fast forward only if there was no change + const bool sample = + (get_sample(index) & sig_mask) != 0; + fast_forward = last_sample == sample; + } + + if(fast_forward) { + + // Fast forward: This involves zooming out to higher + // levels of the mip map searching for changes, then + // zooming in on them to find the point where the edge + // begins. + + // 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 || + (get_subsample(level, 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(level + 1 >= ScaleStepCount || + !_mip_map[level + 1].data) + break; + + level++; + } else { + // Slide right to the beginning of the + // next mip map block + index = pow2_ceil(index + 1, + 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 || + (get_subsample(level, 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 + 1, + 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; + } + } } + + //----- Store the edge -----// + + // Take the last sample of the quanization block + const int64_t final_index = index + block_length; + if(index + block_length > end) + break; + + // Store the final state + const bool final_sample = + (get_sample(final_index - 1) & sig_mask) != 0; + edges.push_back(pair(index, final_sample)); + + index = final_index; + last_sample = final_sample; } // Add the final state - edges.push_back(pair(end - 1, - get_sample(end - 1) & sig_mask)); + edges.push_back(pair(end, + get_sample(end) & sig_mask)); +} + +uint64_t LogicDataSnapshot::get_subsample(int level, uint64_t offset) const +{ + assert(level >= 0); + assert(_mip_map[level].data); + return *(uint64_t*)((uint8_t*)_mip_map[level].data + + _unit_size * offset); +} + +int64_t LogicDataSnapshot::pow2_ceil(int64_t x, unsigned int power) +{ + const int64_t p = 1 << power; + return ((x < 0) ? x : (x + p - 1)) / p * p; }