Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.68
snayperAlfa
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
#1

Битстаффинг - C++

03.08.2011, 19:51. Просмотров 4401. Ответов 21
Метки нет (Все метки)

Всем привет. Есть такой термин - Битстаффинг. Это бит-ориетированная процедура по вставке "0" после 5-ти последовательных "1". Сейчас моя реализация вполне себе работает. Принимает вектор битов, вставляет нули в нужном месте и возвращает вектор битов. Каждый бит занимает один байт. Кто нибудь знает как это можно ускорить? Можно даже добавлять "0" в существующем векторе, но операция "vector.insert", мне кажется будет полным убийством скорости работы. У кого какие варианты есть по оптимизации?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <stdio.h>
#include <vector>
 
class Zero_Insert {
 
private: unsigned short counter;
 
public: ~Zero_Insert(void){};
 
public: Zero_Insert(void)
        {
            Reset();
        };
 
public: void Reset(void)
        {
            counter=0;
        }
 
public: void Zeros_Insertion(vector <unsigned char> & InputVector, vector <unsigned char> & OutputVector)
        {
            
                        OutputVector.reserve(InputVector.size());
 
            for(int j = 0; j < InputVector.size(); j++)
            {
                if( InputVector[j] == 1 )
                {
                    counter++;
                }
                else
                {
                    counter=0;
                }
                OutputVector.push_back(InputVector[j]);
                if(counter==5){
                    OutputVector.push_back(0);
                    counter = 0;
                }
 
            }
        }
};
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.08.2011, 19:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Битстаффинг (C++):

C\C++ Битстаффинг (Bitstuffing) - C++
Добрый день, уважаемые господа и дамы. Стоит задача реализовать битстаффинг, забитстаффить инфу на одном компе, передать на другой,...

Verilog. Битстаффинг и дестаффинг - Программируемая логика
Попытался я сымитировать битстаффинг (предупреждение появления последовательностей из 5 нулей или единиц) и возврат к исходным сигналам. ...

C\C++ Битстаффинг (Bitstuffing) - C++
Добрый день, уважаемые господа и дамы. Стоит задача реализовать битстаффинг, забитстаффить инфу на одном компе, передать на другой,...

Verilog. Битстаффинг и дестаффинг - Программируемая логика
Попытался я сымитировать битстаффинг (предупреждение появления последовательностей из 5 нулей или единиц) и возврат к исходным сигналам. ...

C\C++ Битстаффинг (Bitstuffing) - C++
Добрый день, уважаемые господа и дамы. Стоит задача реализовать битстаффинг, забитстаффить инфу на одном компе, передать на другой,...

Verilog. Битстаффинг и дестаффинг - Программируемая логика
Попытался я сымитировать битстаффинг (предупреждение появления последовательностей из 5 нулей или единиц) и возврат к исходным сигналам. ...

C\C++ Битстаффинг (Bitstuffing) - C++
Добрый день, уважаемые господа и дамы. Стоит задача реализовать битстаффинг, забитстаффить инфу на одном компе, передать на другой,...

Verilog. Битстаффинг и дестаффинг - Программируемая логика
Попытался я сымитировать битстаффинг (предупреждение появления последовательностей из 5 нулей или единиц) и возврат к исходным сигналам. ...

C\C++ Битстаффинг (Bitstuffing) - C++
Добрый день, уважаемые господа и дамы. Стоит задача реализовать битстаффинг, забитстаффить инфу на одном компе, передать на другой,...

Verilog. Битстаффинг и дестаффинг - Программируемая логика
Попытался я сымитировать битстаффинг (предупреждение появления последовательностей из 5 нулей или единиц) и возврат к исходным сигналам. ...

C\C++ Битстаффинг (Bitstuffing) - C++
Добрый день, уважаемые господа и дамы. Стоит задача реализовать битстаффинг, забитстаффить инфу на одном компе, передать на другой,...

Verilog. Битстаффинг и дестаффинг - Программируемая логика
Попытался я сымитировать битстаффинг (предупреждение появления последовательностей из 5 нулей или единиц) и возврат к исходным сигналам. ...

C\C++ Битстаффинг (Bitstuffing) - C++
Добрый день, уважаемые господа и дамы. Стоит задача реализовать битстаффинг, забитстаффить инфу на одном компе, передать на другой,...

Verilog. Битстаффинг и дестаффинг - Программируемая логика
Попытался я сымитировать битстаффинг (предупреждение появления последовательностей из 5 нулей или единиц) и возврат к исходным сигналам. ...

C\C++ Битстаффинг (Bitstuffing) - C++
Добрый день, уважаемые господа и дамы. Стоит задача реализовать битстаффинг, забитстаффить инфу на одном компе, передать на другой,...

Verilog. Битстаффинг и дестаффинг - Программируемая логика
Попытался я сымитировать битстаффинг (предупреждение появления последовательностей из 5 нулей или единиц) и возврат к исходным сигналам. ...

C\C++ Битстаффинг (Bitstuffing) -

C\C++ Битстаффинг (Bitstuffing) - C++
Добрый день, уважаемые господа и дамы. Стоит задача реализовать битстаффинг, забитстаффить инфу на одном компе, передать на другой,...

Verilog. Битстаффинг и дестаффинг - Программируемая логика
Попытался я сымитировать битстаффинг (предупреждение появления последовательностей из 5 нулей или единиц) и возврат к исходным сигналам. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
21
-=ЮрА=-
Заблокирован
Автор FAQ
03.08.2011, 21:05 #2
Вот алгоритм по переводу строки символов в биты, строка bin - содерит в себе битовый массив (каждый символ строки - соотвествующий бит), дальше работа сводится к работе с char вектором - это уже дело техники
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <windows.h>
#include <stdio.h>
#include <ctype.h>
#include <conio.h>
 
char * str = (char *)malloc(sizeof(char));
char * bin = (char *)malloc(sizeof(char));
 
char * get_text(char * s, int &Len);
char * str2bin(char * s, char * bin);
char * int2bin(int val, char * bin);
 
int main()
{
    int sLen = 0;
    do
    {
        printf("Enter input string\r\n");
        str = get_text(str,sLen);bin[0] = '\0';
        printf("%s\r\n",(bin = str2bin(str,bin)));
        printf("[Y/N] - Enter new string\r\n");
    }
    while('Y' == toupper(getch()));
    return 0;
}
 
char * get_text(char * s, int &Len)
{
    if(s)
    {
        Len = 0;
        while((s[Len] = getchar()) != '\n')
            s = (char *)realloc(s,(1 + (Len = Len + 1))*sizeof(char));
        s[Len] = '\0';
    }
    return s;
}
 
char * str2bin(char * s, char * bin)
{
    int i = 0;
    while((s + i)[0] != '\0')
    {
        bin = int2bin(s[i], bin);
        i++;
    }
    return bin;
}
 
char * int2bin(int val, char * bin)
{
    int i = 0,len = strlen(bin);
    bin = (char *)realloc(bin,len + 8);
    bin[len] = '0';
    char bit;
    while(0 < val)
    {
        bit = '0';
        if(val%2 != 0)
            bit = '1';
        bin[len + 6 - i] = bit;
        val = val/2;
        i++;
    }
    bin[len + 7] = '\0';
    return bin;
}
0
Миниатюры
Битстаффинг  
snayperAlfa
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
03.08.2011, 22:45  [ТС] #3
У меня есть процедура по переводу байтов в биты. Меня интересует сам алгоритм вставки нулей. Возможно ли его ускорить каким либо способом. Сейчас у меня анализируется каждый бит входящей последовательности.
0
-=ЮрА=-
Заблокирован
Автор FAQ
03.08.2011, 23:06 #4
Вот перевод с вставкой битов, для наглядности делал вставку не 0 а 2-ка, это лего изменить
Код и скриншот работы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <windows.h>
#include <stdio.h>
#include <ctype.h>
#include <conio.h>
 
char * str = (char *)malloc(sizeof(char));
char * bin = (char *)malloc(sizeof(char));
 
char * get_text(char * s, int &Len);
char * str2bin(char * s, char * bin);
char * int2bin(int val, char * bin);
char * bitstuf(char * bin, char *ins_after, char bit);
char * inschar(char * s, int i, char ch);
 
int main()
{
    int sLen = 0;
    do
    {
        printf("Enter input string\r\n");
        str = get_text(str,sLen);bin[0] = '\0';
        printf("\tBinary string\r\n");
        printf("%s\r\n",(bin = str2bin(str,bin)));
        printf("\tBits after bitstuf\r\n");
        printf("%s\r\n",(bin = bitstuf(bin, "11111", '2')));
        printf("[Y/N] - Enter new string\r\n");
    }
    while('Y' == toupper(getch()));
    return 0;
}
 
char * get_text(char * s, int &Len)
{
    if(s)
    {
        Len = 0;
        while((s[Len] = getchar()) != '\n')
            s = (char *)realloc(s,(1 + (Len = Len + 1))*sizeof(char));
        s[Len] = '\0';
    }
    return s;
}
 
char * str2bin(char * s, char * bin)
{
    int i = 0;
    while((s + i)[0] != '\0')
    {
        bin = int2bin(s[i], bin);
        i++;
    }
    return bin;
}
 
char * int2bin(int val, char * bin)
{
    int i = 0,len = strlen(bin);
    bin = (char *)realloc(bin,len + 8);
    bin[len] = '0';
    while(0 < val)
    {
        bin[len + 6 - i] = '0';
        if(val%2 != 0)
            bin[len + 6 - i] = '1';
        val = val/2;
        i++;
    }
    bin[len + 7] = '\0';
    return bin;
}
 
char * bitstuf(char * bin, char *ins_after, char bit)
{
    char * buf;
    int pos = 0;
    if(bin && ins_after)
    {
        buf = strstr(bin + pos,ins_after);
        while(buf)
        {
            pos = strlen(bin) - strlen(buf) + strlen(ins_after);
            bin = inschar(bin, pos, bit);
            buf = strstr(bin + pos + 2,ins_after);
        }
    }
    return bin;
}
 
char * inschar(char * s, int i, char ch)
{
    int sLen;
    if(s)
    {
        sLen = strlen(s);
        s = (char *)realloc(s,(sLen + 1)*sizeof(char));
        memcpy((void *)&s[i + 1],(void *)&s[i],sLen - i);
        s[sLen + 1] = '\0';
        s[i] = ch;
    }
    return s;
}
0
Миниатюры
Битстаффинг  
-=ЮрА=-
Заблокирован
Автор FAQ
03.08.2011, 23:12 #5
Вкратце суть алгоритма вставки, в исходной двоичной строке bin, нахожу подстроку ins_after (для твоего конкретного примера это "11111", затем в цикле ищу вхождение данной подстроки в bin. Если ins_after присутствует в bin(напремер в позиции pos), то расширяю bin на 1 символ и функцией memcpy сдвигаю все оставшиеся символы с позиции pos + strlen(ins_after) в bin на 1 вправо, затем делаю запись вставляемого бита bit в позицию pos + strlen(ins_after)
0
snayperAlfa
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
04.08.2011, 00:40  [ТС] #6
Надо будет проверить на время выполнения.
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.08.2011, 12:18 #7
"Каждый бит занимает один байт."
Ну молодец...
0
snayperAlfa
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
04.08.2011, 13:58  [ТС] #8
Цитата Сообщение от Deviaphan Посмотреть сообщение
"Каждый бит занимает один байт."
Ну молодец...
Есть варианты?
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.08.2011, 15:20 #9
Цитата Сообщение от snayperAlfa Посмотреть сообщение
Есть варианты?
Разумеется есть. 1 бит занимает 1 бит. Иначе он не бит.
Тебе же битстаффинг не для красоты нужен, а для передачи данных, так ведь? А передавать данные ты будешь побитово. Т.е. после каждых установленных битов будешь передавать дополнительный нулевой. Если ты ты заменишь биты байтами, то вместо последовательности b11 у тебя будет b0000000100000001.

Это бит-ориетированная процедура по вставке "0" после 5-ти последовательных "1"
Т.е. тебе нужно работать с битами. Конкретно: выполнять битовый сдвиг и переносы битов. Ни о каких массивах char даже речи быть не может (уж не говоря о восьмикратном увеличении объёма данных).

Добавлено через 8 минут
Если весь поток байтов известен сразу, то его можно проанализировать и узнать, сколько битов потребуется добавить и сколько памяти потребуется для хранения дополненного потока. После добавления нулевых битов длина в битах может не быть кратной 8.
0
-=ЮрА=-
Заблокирован
Автор FAQ
04.08.2011, 16:11 #10
Цитата Сообщение от Deviaphan Посмотреть сообщение
Т.е. тебе нужно работать с битами. Конкретно: выполнять битовый сдвиг и переносы битов. Ни о каких массивах char даже речи быть не может (уж не говоря о восьмикратном увеличении объёма данных).
Ввёл строку для наглядности.
перенос осуществляется memmove вставка простым присваиванием.

Цитата Сообщение от Deviaphan Посмотреть сообщение
Если весь поток байтов известен сразу, то его можно проанализировать и узнать, сколько битов потребуется добавить и сколько памяти потребуется для хранения дополненного потока. После добавления нулевых битов длина в битах может не быть кратной 8.
- Если бы да кабы, да известен данные например осуществляет пользователь в окно, столько сколько ему нужно...

snayperAlfa, дай исходные данные для своей задачи, надо с битами буду только с битами работать, в ущерб наглядности...

 Комментарий модератора 
Уважительно относитесь к другим участникам форума.
Правила форума
0
snayperAlfa
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
04.08.2011, 16:16  [ТС] #11
Deviaphan После вставки нулей, последовательность дополняется "0" до кратности 8. После бит-стаффинга идет еще куча операций. В итоге все перелается побайтово.

-=ЮрА=-
Ну собственно исходные данные не изменились с первого сообщения. Есть vector <boost:uint8_t>. Байты внутри могут принимать значение 1 либо 0. Нужно провести операцию по вставке 0 после 5-ти встреченных подряд 1. Вернуть это всё в тот же самый вектор, либо в новый вектор.


memcpy() использовать нельзя. од будет запускаться на ARM архитектуре и могут быть грабли с BigEndian / LittleEndian
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.08.2011, 16:28 #12
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
memmove
Работает с байтами, а не битами.

Добавлено через 2 минуты
Цитата Сообщение от snayperAlfa Посмотреть сообщение
В итоге все перелается побайтово.
Я не об этом, а о том, что модифицированные данные должны оставаться набором битов, а не изменением битов в байты. Т.е. vector <boost:uint8_t> не подходит. Или ты его потом байты обратно в биты преобразовывать будешь? Производительность пострадает, да.
0
-=ЮрА=-
Заблокирован
Автор FAQ
04.08.2011, 16:45 #13
Цитата Сообщение от snayperAlfa Посмотреть сообщение
у собственно исходные данные не изменились с первого сообщения.
Вектор битов как получаешь, вбиваешь строку, вводишь число, как я вижу у тебя твои вектора битов имеют размерность <unsigned char>, выходит это вектор байтов - каждый байт которого соответсвет логическому 0 или 1...
Цитата Сообщение от snayperAlfa Посмотреть сообщение
<unsigned char> & InputVector, vector <unsigned char> & OutputVector
Цитата Сообщение от snayperAlfa Посмотреть сообщение
if( InputVector[j] == 1 )
* * * * * * * * * * * * * * * * {
* * * * * * * * * * * * * * * * * * * * counter++;
* * * * * * * * * * * * * * * * }
* * * * * * * * * * * * * * * * else
* * * * * * * * * * * * * * * * {
* * * * * * * * * * * * * * * * * * * * counter=0;
* * * * * * * * * * * * * * * * }
Тогда ты не думал что проще искать как у меня реализовано strstr, чем накапливать 5-re в counter? Если весь косяк в memcpy то подправлю...
0
snayperAlfa
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
04.08.2011, 17:02  [ТС] #14
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Вектор битов как получаешь, вбиваешь строку, вводишь число, как я вижу у тебя твои вектора битов имеют размерность <unsigned char>, выходит это вектор байтов - каждый байт которого соответсвет логическому 0 или 1...
Совершенно верно! Биты получаются из байтов в другом методе: http://www.cyberforum.ru/cpp/thread337347.html

Я пока что еще вкуриваю в твой код

Использование strstr может оказаться дольше простого перебора байтов?
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.08.2011, 17:05 #15
Цитата Сообщение от snayperAlfa Посмотреть сообщение
Совершенно верно! Биты получаются из байтов в другом методе
И тебя не смущает, что у тебя все байты равны 0 или 1? Ещё раз мой пост с 1 страницы перечитай. А лучше дважды.
0
Yandex
Объявления
04.08.2011, 17:05
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru