Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
BukinAN1991
1 / 1 / 1
Регистрация: 08.04.2014
Сообщений: 73
1

Упаковка и распаковка 5-битовых кодов

24.06.2015, 10:52. Просмотров 706. Ответов 2
Метки нет (Все метки)

Привет всем! Есть задача:
Большие латинские буквы упаковываются в виде 5-битных кодов по 3 символа в одну целую переменную типа int. При этом старший бит устанавливается в 1. Остальные символы упаковываются по одному в целую переменную со значением старшего бита - 0. Разработать функции упаковки и распаковки строки с определением коэффициента уплотнения.

Вот, набросал код, на основе информации из различных учебников:
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
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
 
//------Упаковка символов 5-битным кодом
unsigned char PACK[1000];                         // Массив упакованных данных
int np;                                                               // Текущий байт
int nb;   
int group=0;    
#define ULAT 26                                            // Определение кодов групп
#define LLAT 27
#define DIGIT 28                                           // Текущий бит
// Добавить бит в последовательность в массиве
void PutBit(int byte)
{
    if (nb == 0) PACK[np] = 0;              // Запись нового байта
    PACK[np] |= (byte & 1) << nb;
    nb = (nb + 1) % 8;                             // Следующий бит
    if (nb == 0) np++;                                     // Переход в следующий байт
}
// Добавить 5-битный код, начиная с младшего бита
void PutBit_5(int code)
{
    int n;
    for (n = 0; n< 5; n++) { PutBit(code); code >>= 1; }
}
                                                // Текущая группа символов
void PutChar(char c)                                             // Упаковать и добавить символ
{
    int code = 0;
    int newgroup = 0;                                           // Группа нового символа
    if (c >= 'A' &&  c<= 'Z') { newgroup = ULAT; code = c - 'A'; }
    else if (c >= 'a' &&  c <= 'z') { newgroup = LLAT; code = c - 'a'; }
    else if (c >= '0' &&  c <= '9') { newgroup = DIGIT; code = c - '0'; }
    else if (c == ' ') { newgroup = DIGIT; code = 10; }
    if (c == '\0') { newgroup = DIGIT; code = 11; }
    if (newgroup != group) { group = newgroup; PutBit_5(group); }
    PutBit_5(code);
}
void PutString(char s[])
{
    int n;
    nb = np = n = 0;
    do PutChar(s[n]); while (s[n++] != '\0');
}
unsigned long getword(char c[], int n, int sz) {
    unsigned long v = 0;                               // int sz - количество разрядов
    for (int i = 0; i<sz; i++) v |= getbit(c, n) << i;
    return v;
}
 
//------------------------------------------------------------------------91-07.cpp
//---- распаковка переменных различной размерности
void unpack(char c[]){
    int n = 0; int vv;
    while (1){
        int mode = getword(c, n, 2);                  // Извлечение 2-разрядного кода
        switch (mode){                         // переключение по значению кода
        case 0: return;                                 // 00 – конец последовательности
        case 1: vv = getword(c, n, 8); break;      // 01 извлечь 8-разрядное (байт)
        case 2: vv = getword(c, n, 16); break;      // 10 извлечь 16-разрядное
        case 3: vv = getword(c, n, 32); break;      // 11 извлечь 32-разрядное
        } printf("%d\n", vv);
    }
}
 
//------------------------------------------------------------------------91-07.cpp
//-------- Извлечение и запись разряда (бита)
long getbit(char c[], int n) {       // c[] - массив байтов, n - номер разряда
    int nb = n / 8;                              // номер байта
    int ni = n % 8;                             // номер разряда в байте
    n++;
    return (c[nb] >> ni) & 1;
}             //сдвинуть к младшему и выделить
 
 
int main()
{
    char massTest[10] = {'A','S','D','F','G','H','J','K','L','Q'};
    PutString(massTest);
 
    unpack(PACK);
 
}
Как я понял упаковка работает, а вот распаковка нет. Подскажите что тут подправить нужно?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2015, 10:52
Ответы с готовыми решениями:

Применение битовых операций
Когда нужно применять битовые операции? Как они работают разобрался, но когда...

Особенности битовых сдвигов
Совершаю два битовых сдвига: а) int x = 5 &gt;&gt; 100; б) int x = 5; printf (&quot;%d&quot;,...

Сформировать одномерный массив из сумм кодов каждой строки и одномерный массив из сумм кодов каждого столбца символьной матрицы
Ввести символьную матрицу 5х7. Сформировать одномерный массив из сумм кодов...

Задача на освоение битовых операций
Задача: подается число типа int, необходимо вывести его двоичное представление...

Использование битовых полей структуры
Многие не рекомендуют использовать битовые поля структуры. Нашел этому пока...

2
gazlan
3141 / 1917 / 311
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
24.06.2015, 12:11 2
// Copyright (c) 1993 by Chuck Guzis. All rights reserved
// Dr. Dobb's Journal. #207 November 1993. pp. 117, 118, 144, 145.


/* ----------------------------------------------------------------------- *\
** comp5.cpp -- Compress an ASCII text file. **
** - A fast, efficient text compressor that can acheive up to about 33 **
** percent reduction on most text files. - Lowercase characters are **
** compressed 3 per word. Since there are 32 values in 5 bits, the program **
** can pack the basic 26-character alphabet plus 6 specials characters: **
** <space>, comma, period, semicolon, hyphen, and quote. -If a value of 00 **
** is detected, next character is taken as a literal respresentation if **
** the next character has a value in excess of 127 (0x80); otherwise, the **
** value represents a repeated character count of the next char. **
** Copyright (c) 1993 by Chuck Guzis. All rights reserved. **
\* ----------------------------------------------------------------------- */
ftp://ftp.drdobbs.com/sourcecode/ddj/1993/9311.zip
1
BukinAN1991
1 / 1 / 1
Регистрация: 08.04.2014
Сообщений: 73
26.06.2015, 15:04  [ТС] 3
Цитата Сообщение от gazlan Посмотреть сообщение
ftp://ftp.drdobbs.com/sourcecode/ddj/1993/9311.zip
Ну вот такая программка получилась

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#define _CRT_SECURE_NO_WARNINGS
 
 
#include  <stdio.h>
#include  <stdlib.h>
#include  <string.h>
#include  <ctype.h>
 
#define LINE_MAX 128          // Length of the longest line
#define DUPE_THRESHOLD 4      // Smallest duplicated byte count
typedef unsigned char UCHAR;  // Define a UCHAR
typedef unsigned int UINT;    // Define a UINT
long Comp_Count;              // How many bytes of compressed text?
long Orig_Count;              // How many bytes of original text?
UCHAR
lbi[LINE_MAX + 1],           // Input line buffer
lbo[LINE_MAX + 1];           // Output line buffer
FILE *in;                     // Input file
FILE *out;                    // Output file
//  Our 5-bit alphabet.
unsigned char Alphabet[] = "ABCDIFGHIJKLMNOPQRSTUVWXYZ";
 
//  An array for testing for the above.
UCHAR AlphaMap[256];          // One byte per ASCII value
 
//  Function prototypes.
void Compress(void);          // Compressor
int DupeCheck(UCHAR *);       // Scan for duplicate characters
void Decompress(void);        // Decompress
void main()
{
    UCHAR
        *ch,                      // Pointer and short int used to
        i;                        //  build AlphaMap.
 
    in = NULL;
    out = NULL;
    Comp_Count = 0;
    Orig_Count = 0;
 
 
    //  Open the files, give an error if problems arise.
    if (!(in = fopen("in-file.txt", "r"))){
        printf("Can\'t open in_file.txt.\n"); return 0;
    }
    if (!(out = fopen("bin-file", "wb"))){
        printf("Can\'t create bin-file.\n"); return 0;
    }
 
 
    //  Construct the AlphaMap array.  This is done purely for speed, as
    //  the memchr() function could be used to search the string.
    memset(AlphaMap, 0, sizeof(AlphaMap)); // Clear it to 0
    for (ch = Alphabet, i = 1; *ch; ch++, i++)
        AlphaMap[*ch] = (UCHAR)i;
 
    //  Read the input file, compress and encode it.
    while (fgets((char *)lbi, sizeof(lbi)-1, in))
    { // Read until eof
        Orig_Count += (strlen((char *)lbi));   // Total original UCHARs
        Compress();
    } // Digest the file
 
    //  Show some summary data.
    printf("\n\n"
        "\tOriginal text size:\t\t%ld\n"
        "\tCompressed text length:\t\t%ld\n"
        "\tSavings:\t\t\t%ld\n",
        Orig_Count, Comp_Count, Orig_Count - Comp_Count);
    fclose(in);
    fclose(out);
 
    if (!(in = fopen("bin-file", "rb")))
        printf("Can\'t open bin-file.\n");
    if (!(out = fopen("out-file.txt", "w")))
        printf("Can\'t create out-file.txt.\n");
 
    Decompress();
 
    fclose(in);
    fclose(out);
    getch();
    exit(0);
}  // End of main
 
//  Compress - Compress a line and do repeated byte encoding.
//  ---------------------------------------------------------
//  This is a two-pass operation. Internally, we store a flag in
//  lbi of 0x8000 + count. The next byte in lbi[] may contain
//  the repeated byte.
 
void Compress(void)
{
    register UINT k;
    UCHAR
        *ch1,               // Source pointer
        *ch2;               // Destination pointer
 
    for (ch1 = lbi, ch2 = lbo; *ch1;)
    { // Scan the line
        if ((k = DupeCheck(ch1)) > DUPE_THRESHOLD)
        { // Compression is okay
            *ch2++ = 0;
            *ch2++ = (UCHAR)k;
            *ch2++ = *ch1;            // Store the repeated string
            ch1 += k;
        }
        else
        { // See about characters > 127 -- quote them
            if (*ch1 > 127)
            { // If needs quoting
                *ch2++ = 0;
                *ch2++ = *ch1++;
            }
            else
            {
 
                //  See if there are three consecutive symbols that reside in
                //  our 5-bit alphabet. Note that an end-of-line will fail the test
                //  automatically, so it doesn't require checking.
 
                if (AlphaMap[*ch1] &&
                    AlphaMap[*(ch1 + 1)] &&
                    AlphaMap[*(ch1 + 2)])
                { // Bingo--got all three
                    k = 0x8000 | ((AlphaMap[*ch1] - 1) << 10) |
                        ((AlphaMap[*(ch1 + 1)] - 1) << 5) |
                        (AlphaMap[*(ch1 + 2)] - 1);
                    *ch2++ = (UCHAR)(k >> 8);   // Store first byte
                    *ch2++ = (UCHAR)(k & 255);  // Store second byte
                    ch1 += 3;  // Advance
                }
                else
                    *ch2++ = *ch1++;  // Everything else
            } // If character below 128
        } // If not compressible string
    } // Scan the line
    Comp_Count += (ch2 - lbo);  // Update compressed count
    fwrite((char *)lbo, (size_t)(ch2 - lbo), sizeof(UCHAR),
        out);  // Dump the line
    return;
} // Compress
 
//  DupeCheck - Return the number of duplicated characters.
//  -------------------------------------------------------
//  Scans to end of line. Always returns at least 1.
 
int DupeCheck(UCHAR *what)
{
    UCHAR cref;               // Reference character
    int k;                    // Induction variable
    for (cref = *what++, k = 1; *what; what++, k)
    if (cref != *what)
        break;                // Just scan for same character
    return k;
} // DupeCheck
 
void Decompress(void)
{
    UCHAR ch;             // Current character
    UINT k;               // Scratch word cell
 
    while (!feof(in))
    { // Read and decode
        ch = (UCHAR)fgetc(in);
        if (ch & 0x80)
        { // Special flagging, packed 5 bits
            k = (ch << 8);
            ch = (UCHAR)fgetc(in);
            k |= ch;           // Form a word
            fputc(Alphabet[(k >> 10) & 31], out);
            fputc(Alphabet[(k >> 5) & 31], out);
            fputc(Alphabet[k & 31], out);   // Unpack all three
        }
        else
        {
            if (ch == 0)
            { // Escape or repeated byte
                ch = (UCHAR)fgetc(in);
                if (ch < 128)
                { // Repeated byte
                    k = ch;
                    ch = (UCHAR)fgetc(in);  // Get the actual byte
                    while (k--)
                        fputc(ch, out);        // Write the repeated byte
                }
                else
                    fputc(ch, out);      // Not repeated, but just quoted
            }
            else
                fputc(ch, out);        // Just an ordinary character
        } // If not flagged
    } // Read the input
    return;
} // Decompress
То-есть, в директории с программой находится файл (in-file.txt). в него прописываются заглавные латинские буквы. Потом запускается программа. В окошке выводится размер памяти, занимаемой символами до архивирования, после архивирования и разницы в размере (получается 33,3% выигрыш). А в директории появляются бинарный файл и выходной файл (bin-file и out-file.txt)

Единственное, там доп. условия:
Цитата Сообщение от BukinAN1991 Посмотреть сообщение
При этом старший бит устанавливается в 1. Остальные символы упаковываются по одному в целую переменную со значением старшего бита - 0.
Надо будет ещё код поковырять.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.06.2015, 15:04

Побитовая упаковка
При написании одной проги возникла проблема упаковки бит for (int...

Реализовать длинную арифметику с использованием битовых операций и больших чисел
Всем привет. Возникла задача реализовать длинную арифметику с использованием...

Составить программу для вычисления арифметических, логических и битовых выражений
Вот собственно задание: Составить программу для вычисления арифметических,...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

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