X-Git-Url: http://git.code-monkey.de/?p=pulseview.git;a=blobdiff_plain;f=pv%2Fdata%2Flogicsegment.cpp;h=b9e57caa9e797725ed5532e226353cef527b7649;hp=707f797d294accad64b5ee12f1ecd1551049344d;hb=aa78b2df0c9cc94becf8621380c8da741a120d17;hpb=97cb532f668dd78a5100abb07d7500cbd36b6198 diff --git a/pv/data/logicsegment.cpp b/pv/data/logicsegment.cpp index 707f797..b9e57ca 100644 --- a/pv/data/logicsegment.cpp +++ b/pv/data/logicsegment.cpp @@ -25,6 +25,7 @@ #include #include #include +#include #include "logic.hpp" #include "logicsegment.hpp" @@ -52,7 +53,9 @@ LogicSegment::LogicSegment(pv::data::Logic& owner, uint32_t segment_id, unsigned int unit_size, uint64_t samplerate) : Segment(segment_id, samplerate, unit_size), owner_(owner), - last_append_sample_(0) + last_append_sample_(0), + last_append_accumulator_(0), + last_append_extra_(0) { memset(mip_map_, 0, sizeof(mip_map_)); } @@ -64,6 +67,183 @@ LogicSegment::~LogicSegment() free(l.data); } +template +void LogicSegment::downsampleTmain(const T*&in, T &acc, T &prev) +{ + // Accumulate one sample at a time + for (uint64_t i = 0; i < MipMapScaleFactor; i++) { + T sample = *in++; + acc |= prev ^ sample; + prev = sample; + } +} + +template <> +void LogicSegment::downsampleTmain(const uint8_t*&in, uint8_t &acc, uint8_t &prev) +{ + // Handle 8 bit samples in 32 bit steps + uint32_t prev32 = prev | prev << 8 | prev << 16 | prev << 24; + uint32_t acc32 = acc; + const uint32_t *in32 = (const uint32_t*)in; + for (uint64_t i = 0; i < MipMapScaleFactor; i += 4) { + uint32_t sample32 = *in32++; + acc32 |= prev32 ^ sample32; + prev32 = sample32; + } + // Reduce result back to uint8_t +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + prev = (prev32 >> 24) & 0xff; // MSB is last +#elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ + prev = prev32 & 0xff; // LSB is last +#else +#error Endianness unknown +#endif + acc |= acc32 & 0xff; + acc |= (acc32 >> 8) & 0xff; + acc |= (acc32 >> 16) & 0xff; + acc |= (acc32 >> 24) & 0xff; + in = (const uint8_t*)in32; +} + +template <> +void LogicSegment::downsampleTmain(const uint16_t*&in, uint16_t &acc, uint16_t &prev) +{ + // Handle 16 bit samples in 32 bit steps + uint32_t prev32 = prev | prev << 16; + uint32_t acc32 = acc; + const uint32_t *in32 = (const uint32_t*)in; + for (uint64_t i = 0; i < MipMapScaleFactor; i += 2) { + uint32_t sample32 = *in32++; + acc32 |= prev32 ^ sample32; + prev32 = sample32; + } + // Reduce result back to uint16_t +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + prev = (prev32 >> 16) & 0xffff; // MSB is last +#elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ + prev = prev32 & 0xffff; // LSB is last +#else +#error Endian unknown +#endif + acc |= acc32 & 0xffff; + acc |= (acc32 >> 16) & 0xffff; + in = (const uint16_t*)in32; +} + +template +void LogicSegment::downsampleT(const uint8_t *in_, uint8_t *&out_, uint64_t len) +{ + const T *in = (const T*)in_; + T *out = (T*)out_; + T prev = last_append_sample_; + T acc = last_append_accumulator_; + + // Try to complete the previous downsample + if (last_append_extra_) { + while (last_append_extra_ < MipMapScaleFactor && len > 0) { + T sample = *in++; + acc |= prev ^ sample; + prev = sample; + last_append_extra_++; + len--; + } + if (!len) { + // Not enough samples available to complete downsample + last_append_sample_ = prev; + last_append_accumulator_ = acc; + return; + } + // We have a complete downsample + *out++ = acc; + acc = 0; + last_append_extra_ = 0; + } + + // Handle complete blocks of MipMapScaleFactor samples + while (len >= MipMapScaleFactor) { + downsampleTmain(in, acc, prev); + len -= MipMapScaleFactor; + // Output downsample + *out++ = acc; + acc = 0; + } + + // Process remainder, not enough for a complete sample + while (len > 0) { + T sample = *in++; + acc |= prev ^ sample; + prev = sample; + last_append_extra_++; + len--; + } + + // Update context + last_append_sample_ = prev; + last_append_accumulator_ = acc; + out_ = (uint8_t *)out; +} + +void LogicSegment::downsampleGeneric(const uint8_t *in, uint8_t *&out, uint64_t len) +{ + // Downsample using the generic unpack_sample() + // which can handle any width between 1 and 8 bytes + uint64_t prev = last_append_sample_; + uint64_t acc = last_append_accumulator_; + + // Try to complete the previous downsample + if (last_append_extra_) { + while (last_append_extra_ < MipMapScaleFactor && len > 0) { + const uint64_t sample = unpack_sample(in); + in += unit_size_; + acc |= prev ^ sample; + prev = sample; + last_append_extra_++; + len--; + } + if (!len) { + // Not enough samples available to complete downsample + last_append_sample_ = prev; + last_append_accumulator_ = acc; + return; + } + // We have a complete downsample + pack_sample(out, acc); + out += unit_size_; + acc = 0; + last_append_extra_ = 0; + } + + // Handle complete blocks of MipMapScaleFactor samples + while (len >= MipMapScaleFactor) { + // Accumulate one sample at a time + for (uint64_t i = 0; i < MipMapScaleFactor; i++) { + const uint64_t sample = unpack_sample(in); + in += unit_size_; + acc |= prev ^ sample; + prev = sample; + } + len -= MipMapScaleFactor; + // Output downsample + pack_sample(out, acc); + out += unit_size_; + acc = 0; + } + + // Process remainder, not enough for a complete sample + while (len > 0) { + const uint64_t sample = unpack_sample(in); + in += unit_size_; + acc |= prev ^ sample; + prev = sample; + last_append_extra_++; + len--; + } + + // Update context + last_append_sample_ = prev; + last_append_accumulator_ = acc; +} + inline uint64_t LogicSegment::unpack_sample(const uint8_t *ptr) const { #ifdef HAVE_UNALIGNED_LITTLE_ENDIAN_ACCESS @@ -152,8 +332,8 @@ void LogicSegment::append_payload(void *data, uint64_t data_size) lock_guard lock(mutex_); - uint64_t prev_sample_count = sample_count_; - uint64_t sample_count = data_size / unit_size_; + const uint64_t prev_sample_count = sample_count_; + const uint64_t sample_count = data_size / unit_size_; append_samples(data, sample_count); @@ -169,7 +349,7 @@ void LogicSegment::append_payload(void *data, uint64_t data_size) } void LogicSegment::get_samples(int64_t start_sample, - int64_t end_sample, uint8_t* dest) const + int64_t end_sample, uint8_t* dest) const { assert(start_sample >= 0); assert(start_sample <= (int64_t)sample_count_); @@ -183,134 +363,10 @@ void LogicSegment::get_samples(int64_t start_sample, get_raw_samples(start_sample, (end_sample - start_sample), dest); } -SegmentLogicDataIterator* LogicSegment::begin_sample_iteration(uint64_t start) -{ - return (SegmentLogicDataIterator*)begin_raw_sample_iteration(start); -} - -void LogicSegment::continue_sample_iteration(SegmentLogicDataIterator* it, uint64_t increase) -{ - Segment::continue_raw_sample_iteration((SegmentRawDataIterator*)it, increase); -} - -void LogicSegment::end_sample_iteration(SegmentLogicDataIterator* it) -{ - Segment::end_raw_sample_iteration((SegmentRawDataIterator*)it); -} - -void LogicSegment::reallocate_mipmap_level(MipMapLevel &m) -{ - lock_guard lock(mutex_); - - 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; - - // Padding is added to allow for the uint64_t write word - m.data = realloc(m.data, new_data_length * unit_size_ + - sizeof(uint64_t)); - } -} - -void LogicSegment::append_payload_to_mipmap() -{ - MipMapLevel &m0 = mip_map_[0]; - uint64_t prev_length; - uint8_t *dest_ptr; - SegmentRawDataIterator* it; - 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_mipmap_level(m0); - - dest_ptr = (uint8_t*)m0.data + prev_length * unit_size_; - - // Iterate through the samples to populate the first level mipmap - uint64_t start_sample = prev_length * MipMapScaleFactor; - uint64_t end_sample = m0.length * MipMapScaleFactor; - - it = begin_raw_sample_iteration(start_sample); - for (uint64_t i = start_sample; i < end_sample;) { - // Accumulate transitions which have occurred in this sample - accumulator = 0; - diff_counter = MipMapScaleFactor; - while (diff_counter-- > 0) { - const uint64_t sample = unpack_sample(it->value); - accumulator |= last_append_sample_ ^ sample; - last_append_sample_ = sample; - continue_raw_sample_iteration(it, 1); - i++; - } - - pack_sample(dest_ptr, accumulator); - dest_ptr += unit_size_; - } - end_raw_sample_iteration(it); - - // Compute higher level mipmaps - for (unsigned 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 be computed - if (m.length == prev_length) - break; - - reallocate_mipmap_level(m); - - // Subsample the lower level - const uint8_t* src_ptr = (uint8_t*)ml.data + - unit_size_ * prev_length * MipMapScaleFactor; - const uint8_t *const 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 |= unpack_sample(src_ptr); - src_ptr += unit_size_; - } - - pack_sample(dest_ptr, accumulator); - } - } -} - -uint64_t LogicSegment::get_unpacked_sample(uint64_t index) const -{ - assert(index < sample_count_); - - assert(unit_size_ <= 8); // 8 * 8 = 64 channels - uint8_t data[8]; - - get_raw_samples(index, 1, data); - uint64_t sample = unpack_sample(data); - - return sample; -} - void LogicSegment::get_subsampled_edges( vector &edges, uint64_t start, uint64_t end, - float min_length, int sig_index) + float min_length, int sig_index, bool first_change_only) { uint64_t index = start; unsigned int level; @@ -335,7 +391,8 @@ void LogicSegment::get_subsampled_edges( // Store the initial state last_sample = (get_unpacked_sample(start) & sig_mask) != 0; - edges.emplace_back(index++, last_sample); + if (!first_change_only) + edges.emplace_back(index++, last_sample); while (index + block_length <= end) { //----- Continue to search -----// @@ -461,13 +518,172 @@ void LogicSegment::get_subsampled_edges( index = final_index; last_sample = final_sample; + + if (first_change_only) + break; } // Add the final state - const bool end_sample = get_unpacked_sample(end) & sig_mask; - if (last_sample != end_sample) - edges.emplace_back(end, end_sample); - edges.emplace_back(end + 1, end_sample); + if (!first_change_only) { + const bool end_sample = get_unpacked_sample(end) & sig_mask; + if (last_sample != end_sample) + edges.emplace_back(end, end_sample); + edges.emplace_back(end + 1, end_sample); + } +} + +void LogicSegment::get_surrounding_edges(vector &dest, + uint64_t origin_sample, float min_length, int sig_index) +{ + if (origin_sample >= sample_count_) + return; + + // Put the edges vector on the heap, it can become quite big until we can + // use a get_subsampled_edges() implementation that searches backwards + vector* edges = new vector; + + // Get all edges to the left of origin_sample + get_subsampled_edges(*edges, 0, origin_sample, min_length, sig_index, false); + + // If we don't specify "first only", the first and last edge are the states + // at samples 0 and origin_sample. If only those exist, there are no edges + if (edges->size() == 2) { + delete edges; + return; + } + + // Dismiss the entry for origin_sample so that back() gives us the + // real last entry + edges->pop_back(); + dest.push_back(edges->back()); + edges->clear(); + + // Get first edge to the right of origin_sample + get_subsampled_edges(*edges, origin_sample, sample_count_, min_length, sig_index, true); + + // "first only" is specified, so nothing needs to be dismissed + if (edges->size() == 0) { + delete edges; + return; + } + + dest.push_back(edges->front()); + + delete edges; +} + +void LogicSegment::reallocate_mipmap_level(MipMapLevel &m) +{ + lock_guard lock(mutex_); + + 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; + + // Padding is added to allow for the uint64_t write word + m.data = realloc(m.data, new_data_length * unit_size_ + + sizeof(uint64_t)); + } +} + +void LogicSegment::append_payload_to_mipmap() +{ + MipMapLevel &m0 = mip_map_[0]; + uint64_t prev_length; + uint8_t *dest_ptr; + SegmentDataIterator* it; + 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_mipmap_level(m0); + + dest_ptr = (uint8_t*)m0.data + prev_length * unit_size_; + + // Iterate through the samples to populate the first level mipmap + const uint64_t start_sample = prev_length * MipMapScaleFactor; + const uint64_t end_sample = m0.length * MipMapScaleFactor; + uint64_t len_sample = end_sample - start_sample; + it = begin_sample_iteration(start_sample); + while (len_sample > 0) { + // Number of samples available in this chunk + uint64_t count = get_iterator_valid_length(it); + // Reduce if less than asked for + count = std::min(count, len_sample); + uint8_t *src_ptr = get_iterator_value(it); + // Submit these contiguous samples to downsampling in bulk + if (unit_size_ == 1) + downsampleT(src_ptr, dest_ptr, count); + else if (unit_size_ == 2) + downsampleT(src_ptr, dest_ptr, count); + else if (unit_size_ == 4) + downsampleT(src_ptr, dest_ptr, count); + else if (unit_size_ == 8) + downsampleT(src_ptr, dest_ptr, count); + else + downsampleGeneric(src_ptr, dest_ptr, count); + len_sample -= count; + // Advance iterator, should move to start of next chunk + continue_sample_iteration(it, count); + } + end_sample_iteration(it); + + // Compute higher level mipmaps + for (unsigned 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 be computed + if (m.length == prev_length) + break; + + reallocate_mipmap_level(m); + + // Subsample the lower level + const uint8_t* src_ptr = (uint8_t*)ml.data + + unit_size_ * prev_length * MipMapScaleFactor; + const uint8_t *const 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 |= unpack_sample(src_ptr); + src_ptr += unit_size_; + } + + pack_sample(dest_ptr, accumulator); + } + } +} + +uint64_t LogicSegment::get_unpacked_sample(uint64_t index) const +{ + assert(index < sample_count_); + + assert(unit_size_ <= 8); // 8 * 8 = 64 channels + uint8_t data[8]; + + get_raw_samples(index, 1, data); + + return unpack_sample(data); } uint64_t LogicSegment::get_subsample(int level, uint64_t offset) const @@ -480,7 +696,7 @@ uint64_t LogicSegment::get_subsample(int level, uint64_t offset) const uint64_t LogicSegment::pow2_ceil(uint64_t x, unsigned int power) { - const uint64_t p = 1 << power; + const uint64_t p = UINT64_C(1) << power; return (x + p - 1) / p * p; }