заменить дублирующиеся байты

127
19 февраля 2021, 01:00

Есть последовательность байтов, которая может содержать определенные пары байтов. Надо эти пары найти и заменить на одинарные.

пример входной последовательности:

{ 0x7f, 0x10, 0x7f, 0x7f, 0x10, 0x7f, 0x7f, 0x7f, 0x7f, 0x11, 0x7f, 0x7f };

ожидаемая выходная:

{ 0x7f, 0x10, 0x7f, 0x10, 0x7f, 0x7f, 0x11, 0x7f };

Решено так:

const unsigned char _ssp_stx = 0x7f;
//--------------------------------------------------------------------------
void stx_shrink(std::vector<char>& data)
{
    std::vector<char> result;
    result.reserve(data.size());
    bool stx_lock { false };
    for (int i = 0; i < data.size(); ++i)
    {
        if (stx_lock == true)
        {
            stx_lock = false;
            if ((unsigned char)data[i] == _ssp_stx)
                continue;
        }
        if ((unsigned char)data[i] == _ssp_stx)
            stx_lock = true;
        result.push_back(data[i]);
    }
    data = result;
}
int main()
{
    std::vector<char> test = { 0x7f, 0x10, 0x7f, 0x7f, 0x10, 0x7f, 0x7f, 0x7f, 0x7f, 0x11, 0x7f, 0x7f };
    stx_shrink(test);
    return 0;
}

Можно ли решить с меньшей сложностью и избавиться от одного-двух ифов в цикле?

По итогу я пришел к такому варианту (версия @Qwertiy):

void stx_shrink(vector<char>& data)
{
    if (data.size() < 2) return;
    size_t i = 0;
    size_t j = 0;
    for (; i < data.size() - 1; ++i, ++j)
    {
        if (i != j)
            data[j] = data[i];
        if (data[i] == _ssp_stx && data[i + 1] == _ssp_stx)
            ++i;
    }
    if (i == data.size() - 1)
        data[j++] = data[i];
    data.resize(j);
}
Answer 1

Я бы сделал гораздо проще и без создания нового вектора (заодно поменял тип _ssp_stx, чтобы каждый раз не приводить, если требуется, можно вернуть приведение):

const char _ssp_stx = 0x7f;
void stx_shrink(vector<char> &a)
{
  if (a.size() < 2) return;
  unsigned i = -1U, q = -1U, n = a.size() - 1;
  while (++q < n)
    if ((a[++i] = a[q]) == _ssp_stx && a[q+1] == _ssp_stx)
      ++q;
  if (q == n)
    a[++i] = a[q];
  a.resize(i+1);
}

Код полностью (вместе с проверкой): https://ideone.com/Zv6Vjy

#include <iostream>
#include <vector>
using namespace std;
const char _ssp_stx = 0x7f;
void stx_shrink(vector<char> &a)
{
  if (a.size() < 2) return;
  unsigned i = -1U, q = -1U, n = a.size() - 1;
  while (++q < n)
    if ((a[++i] = a[q]) == _ssp_stx && a[q+1] == _ssp_stx)
      ++q;
  if (q == n)
    a[++i] = a[q];
  a.resize(i+1);
}
int main()
{
  vector<char> a = { 0x7f, 0x10, 0x7f, 0x7f, 0x10, 0x7f, 0x7f, 0x7f, 0x7f, 0x11, 0x7f, 0x7f };
  vector<char> b = { 0x7f, 0x10, 0x10, 0x10, 0x10, 0x7f };
  vector<char> c = { 0x7f, 0x10, 0x10, 0x10, 0x7f, 0x7f };
  vector<char> d = { 0x7f, 0x7f, 0x10, 0x10, 0x10, 0x7f };
  vector<char> e = { 0x7f, 0x7f, 0x10, 0x10, 0x7f, 0x7f };
  vector<char> f = { 0x7f, 0x7f };
  vector<char> g = { 0x7f, 0x7f, 0x7f };
  vector<char> h = { 0x7f, 0x7f, 0x7f, 0x7f };
  vector<char> i = { 0x7f, 0x7f, 0x7f, 0x7f, 0x7f };
  vector<char> j = { 0x7f, 0x7f, 0x7f, 0x7f, 0x7f, 0x7f };
  stx_shrink(a);   for (char x : a) cout << hex << (unsigned)x << ' ';   cout << endl;
  stx_shrink(b);   for (char x : b) cout << hex << (unsigned)x << ' ';   cout << endl;
  stx_shrink(c);   for (char x : c) cout << hex << (unsigned)x << ' ';   cout << endl;
  stx_shrink(d);   for (char x : d) cout << hex << (unsigned)x << ' ';   cout << endl;
  stx_shrink(e);   for (char x : e) cout << hex << (unsigned)x << ' ';   cout << endl;
  stx_shrink(f);   for (char x : f) cout << hex << (unsigned)x << ' ';   cout << endl;
  stx_shrink(g);   for (char x : g) cout << hex << (unsigned)x << ' ';   cout << endl;
  stx_shrink(h);   for (char x : h) cout << hex << (unsigned)x << ' ';   cout << endl;
  stx_shrink(i);   for (char x : i) cout << hex << (unsigned)x << ' ';   cout << endl;
  stx_shrink(j);   for (char x : j) cout << hex << (unsigned)x << ' ';   cout << endl;
  return 0;
}
Answer 2

Конечные автоматы может быть?

#include <iostream>
#include <ios>
#include <array>
#include <vector>
enum State{
    Start,
    State1,
    State2
};
enum Symbol{
    B,
    Other
};

const std::array<std::array<State, 2>, 3> Table = {{
    {State1, Start},
    {State2, Start},
    {State1, Start}
}};
const unsigned char ssp_ptx = 0x7f;
Symbol getSymbol(unsigned char c){
    if (c == ssp_ptx){
        return Symbol::B;
    }else{
        return Symbol::Other;
    }
}
static State curState = State::Start;
State nextState(unsigned char c){
    auto symbol = getSymbol(c);
    return Table[curState][symbol];
}
std::vector<char> stx_shrink(const std::vector<char>& data){
    std::vector<char> ret;
    ret.reserve(data.size());
    for (const auto& c: data){
        curState = nextState(static_cast<unsigned char>(c));
        if (curState != State::State2){
            ret.push_back(c);
        }
    }
    return ret;
}
int main()
{
    std::vector<char> test = { 0x7f, 0x10, 0x7f, 0x7f, 0x10, 0x7f, 0x7f, 0x7f, 0x7f, 0x11, 0x7f, 0x7f };
    auto result = stx_shrink(test);
    std::cout << std::hex;
    for (const auto& c: result){
         std::cout << "0x" << static_cast<unsigned int>(c) << " ";
    }
    std::cout << std::endl;
    return 0;
}

Версия без лишнего вектора result и с возможность запуска в многопоточном режиме. По мотивам ответа Qwertiy

#include <iostream>
#include <ios>
#include <array>
#include <vector>
enum State{
    Start,
    State1,
    State2
};
enum Symbol{
    B,
    Other
};

const std::array<std::array<State, 2>, 3> Table = {{
    {State1, Start},
    {State2, Start},
    {State1, Start}
}};
const unsigned char ssp_ptx = 0x7f;
Symbol getSymbol(unsigned char c){
    if (c == ssp_ptx){
        return Symbol::B;
    }else{
        return Symbol::Other;
    }
}

State nextState(const State curState, unsigned char c){
    auto symbol = getSymbol(c);
    return Table[curState][symbol];
}
void stx_shrink(std::vector<char>& data){
    State curState = State::Start;
    std::size_t i = 0, j = 0;
    for (const auto& c: data){
        curState = nextState(curState, static_cast<unsigned char>(c));
        if (curState != State::State2)
            data[i++] = data[j++];
        else
            ++j;
    }
    data.resize(i);
}
int main()
{
    std::vector<char> test = { 0x7f, 0x10, 0x7f, 0x7f, 0x10, 0x7f, 0x7f, 0x7f, 0x7f, 0x11, 0x7f, 0x7f };
    stx_shrink(test);
    std::cout << std::hex;
    for (const auto& c: test){
         std::cout << "0x" << static_cast<unsigned int>(c) << " ";
    }
    std::cout << std::endl;
    return 0;
}
Answer 3

Ну вот и мой вариант, использует тот же вектор, копирует блоками, а не побайтно:

template<typename T>
size_t shrink_range( const size_t     range   
                            T * const where
                    , const T * const begin
                    , const T * const end   )
{
    const auto shrinked_range = (range / 2) + (range % 2);
    const auto shrink_count   = range - shrinked_range;
    const auto count = static_cast<size_t>(end - begin) - shrink_count;
    std::memmove(where, begin, count * sizeof(T));
    return count;
}
void stx_shrink(std::vector<char> & sequence, const char value)
{
   auto begin = std::data(sequence);
   auto where = begin;
   const auto end = begin + std::size(sequence);
   size_t total = 0;
   size_t range = 0;
   for(auto i = begin; i < end; ++i)
   {
       if(value == *i)
       {
           ++range;
       }
       else
       {
           if(range > 1)
           {
               const auto count = shrink_range(range, where, begin, i);
               where += count;
               total += count;
               begin = i;
           }
           range = 0;
       }
   }
   const auto count = shrink_range(range, where, begin, end);
   total += count;
   sequence.resize(total);
}
Answer 4

Ищем по паре одинаковых байт, и удаляем первый из них:

const unsigned char ch { 0x7 };
std::vector<char> v {0x6, 0x3, 0x7, 0x7, 0x21, 0x7, 0x2, 0x7, 0x7, 0x22, 0x7, 0x7};
auto it = std::begin(v);
for (;;) {
    it = std::search_n(it, std::end(v), 2, ch);
    if(it != std::end(v)) {
        it = v.erase(it);
        continue;
    }
    break;
}
//0x6 0x3 0x7 0x21 0x7 0x2 0x7 0x22 0x7 
for(auto ch : v)std::cout << std::hex << "0x" << (int)ch << " ";
READ ALSO
Перемещение содержимого файла

Перемещение содержимого файла

Необходимо организовать перемещение содержимого файла блокамиНапример скопировать первые 20 байт в другой файл, а в исходном их удалить

112
Создать QIODevice (QSerialPort) в отдельном потоке

Создать QIODevice (QSerialPort) в отдельном потоке

Класс QSerialPort, насколько я понимаю, не предназначен для работы с QThreadПоэтому делаю класс наследник который сможет работать с QThread, в котором...

148
map перезаписывает элемент а не добавляет

map перезаписывает элемент а не добавляет

Метод map перезаписывает элемент а не добавляет новый, пробовал и методом emplace и pair, в чем ошибка подскажите?

113
Как работает istream&amp; параметр?

Как работает istream& параметр?

Помогите разобраться нубу с тем, как работает istream&, конкретно интересует следующая конструкция:

114