X-Git-Url: https://sigrok.org/gitweb/?p=pulseview.git;a=blobdiff_plain;f=logicdatasnapshot.cpp;h=5d6505535fe35f81274ece384ad9557b3687c75f;hp=8f7e9922bb50b3ccf74815d2c2200b00fbefe329;hb=b36d8550c43e11d3b86cf7ace35483c8957835a3;hpb=4ceab49abb3c0160cfefdefa6a9c84284d30f850 diff --git a/logicdatasnapshot.cpp b/logicdatasnapshot.cpp index 8f7e9922..5d650553 100644 --- a/logicdatasnapshot.cpp +++ b/logicdatasnapshot.cpp @@ -22,6 +22,7 @@ #include #include +#include #include #include @@ -32,6 +33,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( @@ -54,7 +56,6 @@ void LogicDataSnapshot::append_payload( { 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 @@ -83,7 +84,7 @@ void LogicDataSnapshot::append_payload_to_mipmap() // Expand the data buffer to fit the new samples prev_length = m0.length; - m0.length = _data_length / MipMapScaleFactor; + m0.length = _sample_count / MipMapScaleFactor; // Break off if there are no new samples to compute if(m0.length == prev_length) @@ -159,7 +160,7 @@ void LogicDataSnapshot::append_payload_to_mipmap() 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); } @@ -167,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; i++) + while(index + block_length <= end) { - const bool sample = get_sample(i) & sig_mask; + //----- Continue to search -----// + level = min_level; + fast_forward = true; - // 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_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; + + // 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, 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; +}