Text Compression

demos for beginners, by Hannah Leitheiser

back to projects

In this demo, I tried to create C programs that would print text using methods of compression to make the executable size smaller -- something like the self-extracting .exe's from the late 1990's.

For comparison, I also used a straight printf and bzip2. I ended up writing Python scripts to generate the C code, and have provided examples of the output of the script below.

The bzip2 which uses the Burrows–Wheeler transform algorithum has the lowest slope but with greater overhead (assuming you didn't have bzip2 installed) only begins to win out at 90kb of text.


Example C Code for printf

For baseline comparison. The chart shows an odd step pattern. I don't know why that is.
/* walden_printf.c 
file type  : c language source code
description: Prints a paragraph from from Walden.  
	Used as a baseline for compression
	techniques.
compile    : gcc walden_printf.c -o walden_printf
run        : ./walden_printf
author     : Hannah Leitheiser
date       : 2018APR21
note       : created with a python script. */

#include <stdio.h>

int main() {

printf("HENRY DAVID THOREAU\n\
 WALDEN\n\
\n\
I went to the woods because I wished to live deliberately, \n\
to front only the essential facts of life, and see if I could \n\
not learn what it had to teach, and not, when I came to die, \n\
discover that I had not lived. I did not wish to live what was \n\
not life, living is so dear; nor did I wish to practise resigna- \n\
tion, unless it was quite necessary. I wanted to live deep and \n\
suck out all the marrow of life, to live so sturdily and \n\
Spartan-like as to put to rout all that was not life, to cut a \n\
broad swath and shave close, to drive life into a corner, and \n\
reduce it to its lowest terms, and, if it proved to be mean, \n\
why then to get the whole and genuine meanness of it, and \n\
publish its meanness to the world; or if it were sublime, to \n\
know it by experience, and be able to give a true account \n\
of it in my next excursion.\n\
");
return 0;
}

Example C Code for Optimum Base Encoding

You'd want to optimize for speed.
/* walden_base.c 
file type  : c language source code
description: A hard-coded optimum base
	encoding of a paragraph from Walden.  The optimum
	base encoding involves counting the number
	of unique characters needed, and using that as
	a numbering system base.  Granted, for any
	practical implementation, you'd want to split 
	large text into managable blocks.
compile    : gcc walden_base.c -o walden_base
run        : ./walden_base
author     : Hannah Leitheiser
date       : 2018APR21
note       : created with a python script. */

#include <stdio.h>
#define TEXT_LENGTH 863
#define DATA_LENGTH 592
#define CHARACTER_COUNT 45
char* charset = "\n ,-.;ADEHILNORSTUVWYabcdefghiklmnopqrstuvwxy";

unsigned char data[] =
	{
	0x06, 0xa6, 0xaa, 0xb7, 0xda,
	0xfb, 0xcb, 0xfa, 0xa9, 0xe9,
	0xcd, 0x7e, 0x77, 0x11, 0x35,
	0x7d, 0xa0, 0xbd, 0x9d, 0xc0,
	0xd5, 0x01, 0xec, 0xce, 0x5c,
	0x3f, 0x43, 0xdf, 0x86, 0x8e,
	0x99, 0x19, 0x29, 0xa1, 0xcc,
	0x80, 0x2a, 0x10, 0x0e, 0x77,
	0x3a, 0x13, 0x0a, 0x9d, 0x89,
	0x64, 0x72, 0x4c, 0x34, 0xb3,
	0x11, 0x96, 0x3f, 0x93, 0xc8,
	0x6b, 0xd9, 0x6a, 0xb0, 0x7f,
	0x16, 0x0f, 0xde, 0x96, 0x05,
	0x28, 0xda, 0x7b, 0x11, 0x0f,
	0x7c, 0x12, 0xac, 0xa8, 0x6d,
	0xae, 0xde, 0xf0, 0x54, 0x2b,
	0xbb, 0xbf, 0x47, 0x18, 0x64,
	0x4e, 0xe5, 0x36, 0x76, 0x76,
	0x52, 0xc5, 0x64, 0xd9, 0xe3,
	0x47, 0x59, 0xf6, 0x3c, 0xc3,
	0x1e, 0x6e, 0x31, 0xb0, 0x23,
	0x26, 0xeb, 0xd8, 0xd8, 0x61,
	0x1d, 0xf6, 0x2b, 0xe8, 0x2c,
	0x4c, 0xf0, 0x83, 0x08, 0xd0,
	0xcc, 0xde, 0x3e, 0x85, 0x2c,
	0x54, 0xe6, 0x80, 0x2c, 0x77,
	0x08, 0x49, 0xc2, 0xdc, 0x1c,
	0xb2, 0x66, 0xe6, 0x67, 0xe2,
	0x65, 0x4a, 0xb9, 0xe6, 0xae,
	0x42, 0x92, 0xcc, 0x9c, 0xbf,
	0x97, 0x0a, 0xb6, 0x8c, 0x90,
	0xcc, 0x08, 0xd3, 0x15, 0x93,
	0xd4, 0x22, 0x72, 0xfd, 0x82,
	0x5b, 0x2a, 0x4f, 0x79, 0x3b,
	0xb7, 0xdd, 0x22, 0x83, 0x78,
	0xbb, 0x49, 0xb9, 0x2d, 0xdc,
	0x98, 0xd6, 0x50, 0x6a, 0xa2,
	0x80, 0x25, 0xf8, 0xfa, 0x96,
	0xc9, 0x27, 0xec, 0x31, 0xb8,
	0x7e, 0x5a, 0x7c, 0x05, 0x85,
	0x09, 0x34, 0x82, 0xbb, 0xeb,
	0x43, 0x2d, 0x2f, 0x30, 0xa2,
	0x0c, 0x62, 0x8a, 0x15, 0xc6,
	0x28, 0x37, 0x2b, 0xfc, 0x5b,
	0xe5, 0x92, 0x08, 0x5e, 0xfe,
	0x5f, 0xe5, 0x1d, 0x40, 0x04,
	0x83, 0xe2, 0x76, 0x43, 0x3d,
	0xf7, 0x99, 0xfd, 0x7a, 0x93,
	0x55, 0x59, 0x21, 0x4c, 0x38,
	0xf7, 0xdc, 0x16, 0x89, 0x1c,
	0x74, 0xa6, 0xc9, 0x86, 0x36,
	0x4b, 0x15, 0xe6, 0xc3, 0xea,
	0x91, 0xd3, 0xc6, 0x50, 0x4e,
	0xb3, 0x68, 0x82, 0x20, 0xd5,
	0xf2, 0x2d, 0x1c, 0x30, 0xb8,
	0x35, 0x2c, 0x87, 0xf7, 0x9e,
	0x64, 0xf0, 0x75, 0x18, 0xb5,
	0x0c, 0xe8, 0x3d, 0xeb, 0x85,
	0x68, 0xc2, 0x86, 0x0c, 0xe9,
	0x84, 0x2f, 0xc4, 0xe5, 0xf8,
	0x87, 0x32, 0x1b, 0x25, 0x72,
	0x15, 0xb7, 0x37, 0x64, 0x6c,
	0xb6, 0x80, 0x69, 0xc3, 0xca,
	0x31, 0x89, 0x9b, 0x06, 0xf2,
	0x61, 0x63, 0xce, 0xa1, 0xb0,
	0xcb, 0xa3, 0x8e, 0x57, 0xc6,
	0xa7, 0x41, 0x89, 0xfe, 0x39,
	0x69, 0x06, 0xb3, 0xd6, 0x70,
	0x2e, 0x63, 0x62, 0x79, 0xb8,
	0x87, 0x90, 0xef, 0x72, 0xff,
	0x61, 0x63, 0x2e, 0x16, 0x9d,
	0xeb, 0xb6, 0xaa, 0xb8, 0x28,
	0xb4, 0xec, 0x12, 0x13, 0xc2,
	0xac, 0x1b, 0xb9, 0x86, 0x2d,
	0x26, 0x37, 0xe6, 0xc1, 0x85,
	0xf3, 0xc8, 0xbb, 0x23, 0x96,
	0xef, 0xb2, 0x28, 0xaf, 0x0d,
	0x05, 0xd0, 0x58, 0x5a, 0xea,
	0xd3, 0x8d, 0x60, 0x06, 0xa4,
	0x5e, 0xac, 0x6a, 0x84, 0x30,
	0x62, 0xa5, 0x93, 0x0d, 0x02,
	0x86, 0x2e, 0x44, 0x17, 0xd6,
	0xb1, 0xfd, 0xff, 0x93, 0xaf,
	0x6e, 0xc8, 0xef, 0x1d, 0xa4,
	0x89, 0xf6, 0x49, 0x54, 0x48,
	0xa4, 0xd1, 0x39, 0xc5, 0x68,
	0xa5, 0xff, 0xe2, 0x1a, 0x6e,
	0xf1, 0xcd, 0xec, 0x90, 0x70,
	0xde, 0x27, 0xf4, 0xbb, 0x87,
	0xf8, 0x84, 0x85, 0x54, 0x78,
	0xbd, 0x60, 0xd3, 0xc4, 0x7e,
	0x3d, 0xf3, 0x7b, 0xf8, 0x42,
	0x9d, 0xbf, 0x0f, 0xfc, 0x41,
	0x2c, 0xee, 0x8d, 0x48, 0xfd,
	0x4a, 0x78, 0x6e, 0xe1, 0xde,
	0xac, 0x9d, 0x6c, 0xec, 0x77,
	0x85, 0x1c, 0x55, 0xca, 0xe2,
	0xd7, 0xf5, 0x70, 0xa0, 0xbf,
	0xb2, 0x5c, 0xa1, 0x28, 0xbf,
	0x23, 0xfc, 0xf4, 0x52, 0x87,
	0xfd, 0x09, 0x01, 0x19, 0x2b,
	0x0c, 0x2e, 0x7a, 0x80, 0x98,
	0x78, 0x1d, 0x21, 0x0d, 0xfa,
	0x92, 0x28, 0xf2, 0x2d, 0xf8,
	0xcc, 0x03, 0xb8, 0x7a, 0xc7,
	0xfc, 0x3f, 0xa6, 0xe3, 0xe6,
	0x58, 0x19, 0xe5, 0xa8, 0x72,
	0xaf, 0xba, 0xf1, 0xa8, 0x38,
	0x30, 0xa6, 0x43, 0x73, 0xa1,
	0x12, 0x89, 0xc6, 0x44, 0x46,
	0xde, 0x50, 0xa7, 0x0e, 0xc8,
	0x3c, 0xc7, 0x2d, 0xcf, 0x16,
	0x23, 0x16, 0x81, 0x54, 0x5f,
	0x63, 0x1c, 0xd4, 0xa4, 0x26,
	0x73, 0x5a, 0xad, 0xfb, 0x8d,
	0x1e, 0x47, 0x68, 0x45, 0x39,
	0x64, 0xad, 0x2b, 0x3c, 0x1c,
	0xec, 0x90, 0xec, 0x92, 0xf1,
	0x31, 0xc8, 	};

// Print the text stored in data.

int main() {

	for(int character=0 ; character < TEXT_LENGTH ; character++) {
		/* Take data as a large number, and divide through by
		   CHARACTER_COUNT.  The remainder will be the index
		   of the character to print. */

		unsigned int remainder = 0;
		for(int data_index=0 ; data_index < DATA_LENGTH ; data_index++) {

			unsigned int new_remainder = (data[data_index] + 0x100 * remainder) % CHARACTER_COUNT;
			data[data_index] = ((data[data_index] + 0x100 * remainder) / CHARACTER_COUNT);
			remainder = new_remainder;
			}

		printf( "%c", charset[remainder] );

		}
	return 0;
	}

Example C Code for Huffman Encoding

Probably a more compressed way to do this than with 'if' statements, but not a simplier.
/* walden_huf.c 
file type  : c language source code
description: A hard-coded single-character Huffman
    encoding of a paragraph from Walden.  The Huffman
    tree is traversed with nested if/else statements.
compile    : gcc walden_huf.c -o walden_huf
run        : ./walden_huf
author     : Hannah Leitheiser
date       : 2018APR21
note       : created with a python script. */

#include <stdio.h>
#define TEXT_LENGTH 863

unsigned char data[] =
	{
	0xAE, 0xB4, 0xE1, 0x70, 0x98,
	0x68, 0xD4, 0xD6, 0x92, 0xE4,
	0xD4, 0x61, 0xD5, 0xDA, 0xE6,
	0x11, 0xA5, 0xAF, 0x0C, 0xE0,
	0x48, 0x35, 0xE1, 0xED, 0x4D,
	0x38, 0x5E, 0x38, 0xE4, 0x23,
	0xD7, 0x4D, 0x93, 0x59, 0xE2,
	0x26, 0x6F, 0xD3, 0x9F, 0xE2,
	0xF9, 0x77, 0xCE, 0x42, 0x23,
	0xAC, 0xFB, 0x9B, 0x25, 0xA1,
	0x3F, 0x2F, 0xF6, 0x8E, 0x7F,
	0x47, 0xDF, 0xB5, 0x6C, 0xCE,
	0x36, 0x4A, 0xA9, 0x2B, 0xA4,
	0xAD, 0xAB, 0x1A, 0xCF, 0x3F,
	0xBD, 0xF5, 0xD8, 0x7B, 0x15,
	0x3E, 0x3B, 0xD2, 0x6A, 0x2D,
	0x15, 0x7E, 0x63, 0xAD, 0xCE,
	0xFF, 0x91, 0x51, 0xC8, 0xC6,
	0x72, 0xB5, 0xCE, 0x16, 0x74,
	0xB7, 0xBD, 0x14, 0x43, 0x1F,
	0x48, 0xD1, 0x8F, 0x73, 0x64,
	0xDF, 0x7C, 0x59, 0x98, 0xEB,
	0x71, 0x67, 0x73, 0x10, 0xCF,
	0x53, 0x91, 0x8B, 0xE0, 0xF3,
	0x64, 0xBC, 0x7E, 0x67, 0x17,
	0x8E, 0xE3, 0x29, 0xFD, 0x0D,
	0x63, 0xE9, 0xC8, 0x63, 0xDC,
	0x59, 0xD2, 0xD0, 0x9F, 0xDD,
	0xB4, 0xE4, 0x5E, 0x2E, 0x2C,
	0xE8, 0x88, 0xEB, 0x0D, 0x92,
	0xD0, 0x9F, 0x88, 0x63, 0xE8,
	0x87, 0xE9, 0xC2, 0xCE, 0x96,
	0x8A, 0xBF, 0x32, 0xD0, 0x9C,
	0x2A, 0x52, 0x3A, 0x76, 0x4B,
	0xFB, 0xD2, 0xBC, 0x2C, 0xD0,
	0xBC, 0x5C, 0xE4, 0x22, 0x3A,
	0xC3, 0x64, 0x6F, 0x47, 0xC7,
	0x63, 0xBE, 0x53, 0xFB, 0x09,
	0x55, 0xEB, 0xE7, 0x1B, 0x12,
	0xB9, 0x99, 0x2D, 0xBF, 0xBD,
	0x23, 0x44, 0x3F, 0x44, 0x8E,
	0x51, 0xBE, 0x2F, 0xE3, 0xFD,
	0xEB, 0xD2, 0xB3, 0x69, 0xC8,
	0x43, 0xAE, 0xFD, 0xCD, 0x92,
	0xD0, 0x9F, 0x97, 0xFF, 0x6E,
	0x3A, 0xDC, 0xE3, 0xB9, 0x62,
	0xD0, 0x4E, 0x5A, 0x3D, 0xAC,
	0x6B, 0x3C, 0xC0, 0xF4, 0xA4,
	0xA0, 0x9A, 0x8B, 0x45, 0x5F,
	0x99, 0xB2, 0x5A, 0x13, 0xF3,
	0xB2, 0x77, 0x72, 0xA5, 0xE2,
	0xD5, 0x87, 0x5B, 0x9C, 0x24,
	0xDB, 0xBD, 0x35, 0xD6, 0xBF,
	0x68, 0x68, 0xF1, 0xFA, 0x6C,
	0x8D, 0xF2, 0xD3, 0x64, 0xA4,
	0xE5, 0xA3, 0xDA, 0xC6, 0xB1,
	0xF4, 0x43, 0xF4, 0x59, 0xD2,
	0xD1, 0x57, 0xE6, 0x6C, 0x98,
	0xE5, 0xA3, 0x9C, 0x73, 0xA4,
	0xBD, 0xCE, 0xA1, 0xF5, 0x83,
	0xAD, 0xCE, 0xB1, 0xD3, 0xF3,
	0x1B, 0x4F, 0x7F, 0x33, 0x64,
	0xBD, 0x21, 0x3F, 0x2D, 0x15,
	0x79, 0x0B, 0xB2, 0x39, 0x8C,
	0xD1, 0x7E, 0x99, 0x8E, 0xB7,
	0x38, 0xA7, 0xDF, 0x2C, 0x7C,
	0x8D, 0x36, 0x48, 0xDE, 0x96,
	0x94, 0x7F, 0x74, 0xDF, 0xA6,
	0x0E, 0xE6, 0x3A, 0xDF, 0x32,
	0x2A, 0x23, 0x46, 0xF4, 0x94,
	0xFE, 0xE6, 0xC9, 0xCF, 0xCC,
	0x1E, 0xEB, 0x99, 0xC2, 0x19,
	0x58, 0xD6, 0x7A, 0x9B, 0x22,
	0x5F, 0xD3, 0x59, 0xE2, 0x19,
	0x36, 0xF1, 0xD6, 0xE2, 0x5F,
	0x5C, 0xA1, 0x7C, 0xC1, 0xEE,
	0xAB, 0xFD, 0xE9, 0x35, 0x11,
	0xB9, 0x8E, 0xB7, 0x38, 0x6F,
	0x97, 0x3B, 0x47, 0x58, 0x46,
	0xF4, 0xC1, 0xEE, 0xAB, 0xFD,
	0xE9, 0xB2, 0x6B, 0x3C, 0x44,
	0xD2, 0xD7, 0xAF, 0x13, 0x42,
	0x2A, 0x23, 0x44, 0x7D, 0x3C,
	0xEE, 0x5C, 0xED, 0x18, 0x3F,
	0x33, 0x64, 0xE1, 0xA1, 0x65,
	0x04, 0x69, 0xCE, 0xB1, 0xED,
	0x8D, 0xFE, 0x91, 0xEB, 0x8F,
	0xE6, 0x3A, 0xDC, 0xE7, 0xE3,
	0xF3, 0xB7, 0x9B, 0x22, 0x58,
	0x4F, 0xC7, 0x36, 0x99, 0x78,
	0xF8, 0xE3, 0x39, 0x2E, 0x9C,
	0x4D, 0x44, 0x69, 0x0A, 0x60,
	0xAC, 0x2F, 0xB6, 0x69, 0xED,
	0x98, 0xE5, 0x4E, 0xC4, 0xAB,
	0x6F, 0x00, 	};

unsigned int data_position = 0;

// With each call, the next bit in data[] is 
// returned.
int getbit() {
	int return_v = data[data_position / 8] & (0x80 >> (data_position % 8));
	data_position++;
        if(return_v) return 1;
        else return 0;
	}

int main() {

for (int i = 0 ; i < TEXT_LENGTH ; i++) {

 // Hoffman Encoding Tree - code automatically
 // genereated with a Python script.

 /* Character code table

 Character: " " , Frequency: 172, Code: 00
 Character: "e" , Frequency: 076, Code: 1111
 Character: "t" , Frequency: 071, Code: 1101
 Character: "o" , Frequency: 054, Code: 1001
 Character: "i" , Frequency: 050, Code: 1000
 Character: "a" , Frequency: 048, Code: 0111
 Character: "n" , Frequency: 046, Code: 0101
 Character: "s" , Frequency: 039, Code: 11101
 Character: "d" , Frequency: 032, Code: 10111
 Character: "l" , Frequency: 031, Code: 10110
 Character: "r" , Frequency: 027, Code: 10100
 Character: "h" , Frequency: 022, Code: 01100
 Character: "w" , Frequency: 020, Code: 01000
 Character: "u" , Frequency: 017, Code: 110010
 Character: "c" , Frequency: 017, Code: 110001
 Character: "," , Frequency: 017, Code: 110011
 Character: "\n", Frequency: 017, Code: 111000
 Character: "f" , Frequency: 014, Code: 101010
 Character: "v" , Frequency: 011, Code: 010011
 Character: "b" , Frequency: 009, Code: 1110011
 Character: "I" , Frequency: 009, Code: 1110010
 Character: "m" , Frequency: 008, Code: 1100000
 Character: "y" , Frequency: 007, Code: 1010110
 Character: "p" , Frequency: 007, Code: 0110111
 Character: "g" , Frequency: 005, Code: 0100101
 Character: "x" , Frequency: 003, Code: 01101100
 Character: "k" , Frequency: 003, Code: 01101000
 Character: "E" , Frequency: 003, Code: 01101001
 Character: "D" , Frequency: 003, Code: 01101010
 Character: "A" , Frequency: 003, Code: 01101011
 Character: "." , Frequency: 003, Code: 01101101
 Character: "R" , Frequency: 002, Code: 110000100
 Character: "N" , Frequency: 002, Code: 110000101
 Character: "H" , Frequency: 002, Code: 101011101
 Character: ";" , Frequency: 002, Code: 101011110
 Character: "-" , Frequency: 002, Code: 101011111
 Character: "q" , Frequency: 001, Code: 010010001
 Character: "Y" , Frequency: 001, Code: 1100001101
 Character: "W" , Frequency: 001, Code: 010010000
 Character: "V" , Frequency: 001, Code: 010010010
 Character: "U" , Frequency: 001, Code: 1100001100
 Character: "T" , Frequency: 001, Code: 1100001110
 Character: "S" , Frequency: 001, Code: 010010011
 Character: "O" , Frequency: 001, Code: 101011100
 Character: "L" , Frequency: 001, Code: 1100001111

 End character code table */

 if(getbit() == 0) {
  if(getbit() == 0) {
   printf(" ");
   }
  else {
   if(getbit() == 0) {
    if(getbit() == 0) {
     if(getbit() == 0) {
      printf("w");
      }
     else {
      if(getbit() == 0) {
       if(getbit() == 0) {
        if(getbit() == 0) {
         if(getbit() == 0) {
          printf("W");
          }
         else {
          printf("q");
          }
         }
        else {
         if(getbit() == 0) {
          printf("V");
          }
         else {
          printf("S");
          }
         }
        }
       else {
        printf("g");
        }
       }
      else {
       printf("v");
       }
      }
     }
    else {
     printf("n");
     }
    }
   else {
    if(getbit() == 0) {
     if(getbit() == 0) {
      printf("h");
      }
     else {
      if(getbit() == 0) {
       if(getbit() == 0) {
        if(getbit() == 0) {
         printf("k");
         }
        else {
         printf("E");
         }
        }
       else {
        if(getbit() == 0) {
         printf("D");
         }
        else {
         printf("A");
         }
        }
       }
      else {
       if(getbit() == 0) {
        if(getbit() == 0) {
         printf("x");
         }
        else {
         printf(".");
         }
        }
       else {
        printf("p");
        }
       }
      }
     }
    else {
     printf("a");
     }
    }
   }
  }
 else {
  if(getbit() == 0) {
   if(getbit() == 0) {
    if(getbit() == 0) {
     printf("i");
     }
    else {
     printf("o");
     }
    }
   else {
    if(getbit() == 0) {
     if(getbit() == 0) {
      printf("r");
      }
     else {
      if(getbit() == 0) {
       printf("f");
       }
      else {
       if(getbit() == 0) {
        printf("y");
        }
       else {
        if(getbit() == 0) {
         if(getbit() == 0) {
          printf("O");
          }
         else {
          printf("H");
          }
         }
        else {
         if(getbit() == 0) {
          printf(";");
          }
         else {
          printf("-");
          }
         }
        }
       }
      }
     }
    else {
     if(getbit() == 0) {
      printf("l");
      }
     else {
      printf("d");
      }
     }
    }
   }
  else {
   if(getbit() == 0) {
    if(getbit() == 0) {
     if(getbit() == 0) {
      if(getbit() == 0) {
       if(getbit() == 0) {
        printf("m");
        }
       else {
        if(getbit() == 0) {
         if(getbit() == 0) {
          printf("R");
          }
         else {
          printf("N");
          }
         }
        else {
         if(getbit() == 0) {
          if(getbit() == 0) {
           printf("U");
           }
          else {
           printf("Y");
           }
          }
         else {
          if(getbit() == 0) {
           printf("T");
           }
          else {
           printf("L");
           }
          }
         }
        }
       }
      else {
       printf("c");
       }
      }
     else {
      if(getbit() == 0) {
       printf("u");
       }
      else {
       printf(",");
       }
      }
     }
    else {
     printf("t");
     }
    }
   else {
    if(getbit() == 0) {
     if(getbit() == 0) {
      if(getbit() == 0) {
       printf("\n");
       }
      else {
       if(getbit() == 0) {
        printf("I");
        }
       else {
        printf("b");
        }
       }
      }
     else {
      printf("s");
      }
     }
    else {
     printf("e");
     }
    }
   }
  }
 }

return 0;
}