AVI - The Gr8 Ответов: 2

Код C для сжатия и распаковки входного файла

Привет,

Я проблема, с которой сталкиваются.
Мне нужно написать функцию компания() это считывает текстовый файл символов ASCII и записывает в сжатом виде эти символы в другой файл.

Логика сжатия для comp() должна использовать тот факт, что ASCII использует только нижние (наименее значимые) семь битов 8-битного байта. Логика сжатия должна просто выдавить 8 - й бит. Ниже описаны алгоритмы для реализации этой логики сжатия в comp().

Алгоритм:

Программа должна рассматривать выходные данные как поток битов, и 7 битов данных из каждого входного байта должны просто передаваться в выходной битовый поток, а 8-й бит отбрасывается. 7 битов данных должны быть отправлены в выходной поток в порядке возрастания значимости: бит 0 (наименее значимый) первым, бит 1 следующим и так далее.
Конечно, выходные данные на самом деле представляют собой последовательность байтов, поэтому логический выходной битовый поток должен быть упакован в выходные байты. Битовый поток упаковывается в байты путем присвоения битов возрастающей позиции бита (возрастающей значимости) внутри байта и перехода к следующему байту, когда верхний бит был заполнен текущим байтом. В конце файла, если в текущем байте есть пустые позиции битов, то перед выводом байта заполните их нулями.

Например, файл, состоящий из байтов 53 7F 63 4B, должен быть "сжат" в файл, содержащий D3 FF 78 09. (Этот файл слишком мал, чтобы получить что-либо от этой простой техники сжатия.

---------
Другая функция разложение(), который будет считывать сжатый файл (может быть создан функцией comp())
и распакует его. Программа должна просто воспроизвести файл ASCII, из которого были получены ее входные данные (предполагая, что исходный файл был допустимым файлом ASCII с 8-м битом всегда 0).

2 Ответов

Рейтинг:
1

Andrew Brock

Если это не задание, а алгоритм не задан конкретно, я бы предложил взглянуть на кодирование Хаффмана[^].

Если это установленный алгоритм для вас, то мы обычно не делаем вашу домашнюю работу, но вот идет

#include <stdio.h>
#include <string.h>

//comp()
void Compress(unsigned char *szOut, const char *szMessage) {
	unsigned long long nBuffer = 0; //This is enough to store 8 uncompressed characters or 9 compressed. We will only use 8 tho.
	char nBitsInBuffer = 0;
	while (*szMessage != 0) {
		nBuffer |= (unsigned long long)(*szMessage++ & 0x7F) << nBitsInBuffer;
		nBitsInBuffer += 7;
		if (nBitsInBuffer == 7 * 8) { //We have 8 chars in the buffer, dump them
			while (nBitsInBuffer > 0) {
				*szOut++ = nBuffer & 0xFF;
				nBuffer >>= 8;
				nBitsInBuffer -= 8;
			}
			//The following should be redundant, but just to be safe
			nBitsInBuffer = 0;
			nBuffer = 0;
		}
	}
	//Write out whatever is left in the buffer
	while (nBitsInBuffer > 0) {
		*szOut++ = nBuffer & 0xFF;
		nBuffer >>= 8;
		nBitsInBuffer -= 8;
	}
}

//uncomp()
//nCompressedLen is the number of bytes in the compressed buffer.
//NOTE: the compressed buffer does not have a NULL terminating character
void Uncompress(char *szOut, const unsigned char *szCompressed, unsigned nCompressedLen) {
	unsigned long long nBuffer = 0; //This is enough to store 8 uncompressed characters or 9 compressed. We will only use 8 tho.
	char nBitsInBuffer = 0;
	while (nCompressedLen) {
		while (nCompressedLen && nBitsInBuffer < 7 * 8) {
			nBuffer |= (unsigned long long)*szCompressed++ << nBitsInBuffer;
			nBitsInBuffer += 8;
			--nCompressedLen;
		}
		while (nBitsInBuffer > 0) {
			*szOut++ = nBuffer & 0x7F;
			nBuffer >>= 7;
			nBitsInBuffer -= 7;
		}
		//The following should be redundant, but just to be safe
		nBitsInBuffer = 0;
		nBuffer = 0;
	}
}

int main() {
	//char szMessage[] = "\x53\x7F\x63\x4B";
	char szMessage[] = "hello world. this is a compressed long string";
	static const unsigned nCompressedSize = sizeof(szMessage) * 7 / 8; //This does not include the NULL terminating character from the string
	unsigned char pCompressedBytes[nCompressedSize];
	char szUncompressed[sizeof(szMessage)];
	printf("     Message: %s\n", szMessage);
	Compress(pCompressedBytes, szMessage);
	printf("  Compressed: ");
	for (int nByte = 0; nByte < nCompressedSize; ++nByte) {
		printf("%02X ", pCompressedBytes[nByte]);
	}
	printf("\n");
	Uncompress(szUncompressed, pCompressedBytes, nCompressedSize);
	szUncompressed[sizeof(szMessage) - 1] = 0; //We need to terminate the string. The NULL terminator is not stored in the compressed bytes
	printf("Uncompressed: %s\n", szUncompressed);
	//Now just verify that we ended up with the same message we started with
	if (strcmp(szMessage, szUncompressed) == 0) {
		printf("Compression works\n");
	} else {
		printf("Compression failed\n");
	}
	return 0;
}


Он работает, используя 64-битное целое число в качестве буфера для битов, чтобы поместить 8 несжатых символов или 7 сжатых символов в 1 целое число. Это действительно упрощает дело, поскольку мы можем использовать стандартные побитовые операции над целым числом. Компилятор преобразует побитовую математику в математику, с которой может работать компьютер x86 (т. е. преобразует ее в 2 32 - битных числа)

Я дал основные объяснения. Остальное вы можете выяснить сами.

Espen Harlinn

Хорошее усилие, 5+

Рейтинг:
1

Richard MacCutchan

Не совсем трудная проблема; в чем заключается ваш вопрос?

Member 13751349

Можно ли сжать строку до 6 бит вместо 7 бит?

Richard MacCutchan

Подумайте об этом.

CPallini

Бить старую лошадь? :-)

Richard MacCutchan

Да, я знаю, но просто отвечал на сообщение выше, которое пришло сегодня.

ManKirat Kaur

какой использовать алгоритм?