If this isn't an assignment, and the algorithm isnt set in concrete, i would suggest taking a look at
huffman coding[
^].
If it is a set algorithm for you to implement then we generally don't do your homework but here goes
#include <stdio.h>
#include <string.h>
void Compress(unsigned char *szOut, const char *szMessage) {
unsigned long long nBuffer = 0;
char nBitsInBuffer = 0;
while (*szMessage != 0) {
nBuffer |= (unsigned long long)(*szMessage++ & 0x7F) << nBitsInBuffer;
nBitsInBuffer += 7;
if (nBitsInBuffer == 7 * 8) {
while (nBitsInBuffer > 0) {
*szOut++ = nBuffer & 0xFF;
nBuffer >>= 8;
nBitsInBuffer -= 8;
}
nBitsInBuffer = 0;
nBuffer = 0;
}
}
while (nBitsInBuffer > 0) {
*szOut++ = nBuffer & 0xFF;
nBuffer >>= 8;
nBitsInBuffer -= 8;
}
}
void Uncompress(char *szOut, const unsigned char *szCompressed, unsigned nCompressedLen) {
unsigned long long nBuffer = 0;
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;
}
nBitsInBuffer = 0;
nBuffer = 0;
}
}
int main() {
char szMessage[] = "hello world. this is a compressed long string";
static const unsigned nCompressedSize = sizeof(szMessage) * 7 / 8;
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;
printf("Uncompressed: %s\n", szUncompressed);
if (strcmp(szMessage, szUncompressed) == 0) {
printf("Compression works\n");
} else {
printf("Compression failed\n");
}
return 0;
}
It works by using a 64bit integer as a buffer for the bits in order to fit 8 uncompressed characters or 7 compressed characters into the 1 integer. This really simplifies things as we can use standard bitwise operations on the integer. The compiler will convert the bitwise math into math that a x86 computer can work with (i.e. convert it into 2 32 bit numbers)
I have given basic explanations. You can figure out the rest.