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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.68
snayperAlfa
2 / 2 / 0
Регистрация: 13.08.2008
Сообщений: 84
03.08.2011, 19:51     Битстаффинг #1
Всем привет. Есть такой термин - Битстаффинг. Это бит-ориетированная процедура по вставке "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;
                }
 
            }
        }
};
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.08.2011, 19:51     Битстаффинг
Посмотрите здесь:

C\C++ Битстаффинг (Bitstuffing) C++
Verilog. Битстаффинг и дестаффинг

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
-=ЮрА=-
Заблокирован
Автор 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;
}
Миниатюры
Битстаффинг  
snayperAlfa
2 / 2 / 0
Регистрация: 13.08.2008
Сообщений: 84
03.08.2011, 22:45  [ТС]     Битстаффинг #3
У меня есть процедура по переводу байтов в биты. Меня интересует сам алгоритм вставки нулей. Возможно ли его ускорить каким либо способом. Сейчас у меня анализируется каждый бит входящей последовательности.
-=ЮрА=-
Заблокирован
Автор 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;
}
Миниатюры
Битстаффинг  
-=ЮрА=-
Заблокирован
Автор 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)
snayperAlfa
2 / 2 / 0
Регистрация: 13.08.2008
Сообщений: 84
04.08.2011, 00:40  [ТС]     Битстаффинг #6
Надо будет проверить на время выполнения.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.08.2011, 12:18     Битстаффинг #7
"Каждый бит занимает один байт."
Ну молодец...
snayperAlfa
2 / 2 / 0
Регистрация: 13.08.2008
Сообщений: 84
04.08.2011, 13:58  [ТС]     Битстаффинг #8
Цитата Сообщение от Deviaphan Посмотреть сообщение
"Каждый бит занимает один байт."
Ну молодец...
Есть варианты?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.08.2011, 15:20     Битстаффинг #9
Цитата Сообщение от snayperAlfa Посмотреть сообщение
Есть варианты?
Разумеется есть. 1 бит занимает 1 бит. Иначе он не бит.
Тебе же битстаффинг не для красоты нужен, а для передачи данных, так ведь? А передавать данные ты будешь побитово. Т.е. после каждых установленных битов будешь передавать дополнительный нулевой. Если ты ты заменишь биты байтами, то вместо последовательности b11 у тебя будет b0000000100000001.

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

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

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

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

 Комментарий модератора 
Уважительно относитесь к другим участникам форума.
Правила форума
snayperAlfa
2 / 2 / 0
Регистрация: 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
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.08.2011, 16:28     Битстаффинг #12
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
memmove
Работает с байтами, а не битами.

Добавлено через 2 минуты
Цитата Сообщение от snayperAlfa Посмотреть сообщение
В итоге все перелается побайтово.
Я не об этом, а о том, что модифицированные данные должны оставаться набором битов, а не изменением битов в байты. Т.е. vector <boost:uint8_t> не подходит. Или ты его потом байты обратно в биты преобразовывать будешь? Производительность пострадает, да.
-=ЮрА=-
Заблокирован
Автор 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 то подправлю...
snayperAlfa
2 / 2 / 0
Регистрация: 13.08.2008
Сообщений: 84
04.08.2011, 17:02  [ТС]     Битстаффинг #14
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Вектор битов как получаешь, вбиваешь строку, вводишь число, как я вижу у тебя твои вектора битов имеют размерность <unsigned char>, выходит это вектор байтов - каждый байт которого соответсвет логическому 0 или 1...
Совершенно верно! Биты получаются из байтов в другом методе: http://www.cyberforum.ru/cpp/thread337347.html

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

Использование strstr может оказаться дольше простого перебора байтов?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.08.2011, 17:05     Битстаффинг #15
Цитата Сообщение от snayperAlfa Посмотреть сообщение
Совершенно верно! Биты получаются из байтов в другом методе
И тебя не смущает, что у тебя все байты равны 0 или 1? Ещё раз мой пост с 1 страницы перечитай. А лучше дважды.
-=ЮрА=-
Заблокирован
Автор FAQ
04.08.2011, 17:17     Битстаффинг #16
Цитата Сообщение от snayperAlfa Посмотреть сообщение
Использование strstr может оказаться дольше простого перебора байтов?
Однозначно нет,
Цитата Сообщение от snayperAlfa Посмотреть сообщение
memcpy() использовать нельзя. од будет запускаться на ARM архитектуре и могут быть грабли с BigEndian / LittleEndian
- граблей не будет,функция выполняет копирование внутри отведенного блока памяти, это никак не отразиться на порядке следования битов.
snayperAlfa
2 / 2 / 0
Регистрация: 13.08.2008
Сообщений: 84
04.08.2011, 17:53  [ТС]     Битстаффинг #17
Цитата Сообщение от Deviaphan Посмотреть сообщение
Я не об этом, а о том, что модифицированные данные должны оставаться набором битов, а не изменением битов в байты. Т.е. vector <boost:uint8_t> не подходит. Или ты его потом байты обратно в биты преобразовывать будешь? Производительность пострадает, да.
Потом этот вектор битов будет дополнен до кратности 8, преобразован в байты (размер вектора байтов будет в 8 раз меньше вектора битов). А потом еще парочка таких преобразований байты-биты, потому что буду выполняться побайтные операции кодирования.

Добавлено через 1 минуту
Цитата Сообщение от Deviaphan Посмотреть сообщение
И тебя не смущает, что у тебя все байты равны 0 или 1? Ещё раз мой пост с 1 страницы перечитай. А лучше дважды.
Пока что нет, ибо не вижу другого способа.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.08.2011, 17:57     Битстаффинг #18
оК. Если хочешь использовать std::vector, используй std::vector<bool>. Он прям сразу битами и есть. Разумеется, максимальную производительность ты получишь только при ручной реализации. Желательно на асме. На плюсах перенос знака нельзя нормально сделать.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
04.08.2011, 22:56     Битстаффинг #19
Цитата Сообщение от Deviaphan Посмотреть сообщение
используй std::vector<bool>
Можно bitset попробовать.
snayperAlfa
2 / 2 / 0
Регистрация: 13.08.2008
Сообщений: 84
04.08.2011, 23:00  [ТС]     Битстаффинг #20
bitset будет медленнее
Yandex
Объявления
04.08.2011, 23:00     Битстаффинг
Ответ Создать тему
Опции темы

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