Modified Huffman -i.4

International Conference on Computer Systems and Technologies - CompSysTech’07

MFC-program SFFViewer intended for visualization of FAX files compressed to SFF format Galina Istatkova Abstract: MFC program SFFViewer, intended for reading, decompressing and visualization of fax document compressed with modified Huffman code and saved in SFF file format, is described. Two C++ classes – CSFFFile and CSFFPage, in which the most part of functionality is collected, are discussed in more details. The code of three methods of CSFFPage, intended for Huffman data decompression, creation of CBitmap object, needed for one page of document visualization, saving the graphic image of fax document’s page in BMP file, are given and commented. The design of the program allows the same structure to be applied for viewer program development of other type of compressed graphic images. Key words: Modified Huffman code decompressing, C++ Visual, Computer Graphic, Object-oriented programming.

INTRODUCTION With the low cost of fax modems in the past couple of years, a great many of today's faxed documents never touch actual paper; they are sent and received purely as electronic images between two computers. Structured Fax File (SFF) is one of the files’ formats intended for a representation and an exchanging fax images between computers. It consists of information defining the page structure and compressed data of the fax document. Data compression was a concern for faxes from the beginning because scanned image data tends to be rather large. Statistical evidence showed that the typical page was composed of many small black images (runs of pixels) and fewer long white runs. By using a modified Huffman encoding scheme [1] (Modified Huffman coding combines the variable length of Huffman codes with the run-length encoding scheme), the statistical probability of run lengths could be used to achieved a reasonable compression ratio: frequently occurring run lengths were assigned the shortest codes and infrequently occurring run lengths were assigned the longest codes. The statistical information used for encoding fax images is a fixed table so that it does not have be transmitted with each page (of course, being fixed information it will not always be optimal for all images). The encoding of the runs of pixels as Huffman (minimum redundancy) codes presents a problem for writing an efficient decoder since the codes do not fall neatly on byte boundaries. The codes are also designed to not need separators (prefix codes); each code is uniquely decodable. The codes can be decoded by picking up one bit at a time and traversing the Huffman binary tree; branching left for a zero and right for a one. This solution is the most obvious one from the creation of the codes, but is definitely not the most efficient. The nature of Huffman codes allows a more elegant solution to this problem. Since the codes are designed to be unique sequences of bits when decoded from start to finish, it’s possible to construct a table for decoding each code in one iteration instead of one iteration per bit. By using the code as an address to index into the table, the bit sequence might be decoded in one step. The SFFViewer program developed with Visual Microsoft C++ is intended to read, to decompress and to render fax pages from SFF files. The program was designed using object-oriented approach and the most important functionality is collected in two classes CSFFFile and CSFFPage. The class CSFFPage is intended to process one page from SFF file and objects of this class are embedded in CSFFFFile class. Because the most interesting algorithms – decompressing Huffman data, rendering fax pages, saving pages in BMP file format, are implemented in CSFFFile and CSFFPage classes, describing of these classes is the main goal of this report. MODIFIED HUFFMAN CODE DECOMPRESSING ALGORITHM Compressed fax page - Huffman data, are saved in the array of bytes and the pointers to every line of Huffman data in the array of doubles: - I.4-1 -

International Conference on Computer Systems and Technologies - CompSysTech’07 //Huffman data CDWordArray indexes; //indexes in the data of the lines LPBYTE data; //allocated with malloc, because we use realloc

Decompressing algorithm for one line of Huffman data is implemented as the method of SFFPage class: void CSFFPage::SetPixels (BYTE* row, int index) const { int rowSize = indexes[index + 1] - indexes[index];// Length of Huffman record if (rowSize == 0) return; //empty line BYTE* inbuf = data + indexes[index];// pointer to input Huffman record int scanSize = GetWidth (PIXEL);// Scan row size // Data for Huffman decoding int iOff = 0; // pixel's offset to current code word in Huffman record int iBit = 0 ; // iOff*8 + iBit short sCode = 0; // length in pixels for current code word unsigned char lBit, rBit; // left and right byte mask for zero filling register unsigned char *p; register int x;//number of pixels have been set to output buffer after decoding register int iLen;//number of bytes for filling x = 0; while (x < scanSize ) { sCode = ClimbWhite(inbuf, &iBit, &iOff,rowSize); if (sCode < 0) break; x += sCode; sCode = ClimbBlack(inbuf, &iBit, &iOff,rowSize); if (sCode < 0) break; /* Draw the black run */ lBit = 0xff << (8 - (x & 7)); rBit = 0xff >> ((x + sCode) & 7); iLen = ((x+sCode)>>3) - (x >> 3) - 1; if (iLen < 0) { lBit |= rBit; rBit = 0xff; } p = &row[x >> 3]; *p++ &= lBit; while (iLen > 0) { *p++ = 0; iLen--; } *p &= rBit; x += sCode; }

} // end of while

Input argument – index, defines the line of Huffman data to be decompressed. This line is passed in bytes array inbuf to external functions ClimbWhite and ClimBlack implemented in procedural form of the library, in which the black and white tables (tables with codes for black and white runs) needed for decompressing are defined. In one - I.4-2 -

International Conference on Computer Systems and Technologies - CompSysTech’07

iteration of outer while cycle, two codes – for one white and one black runs, are decompressed. This approach could be applied because Huffman data for fax images always start with white run, followed by the black one. After decompression, the black run is written to the output buffer, is given by pointer row. The output buffer is used for creation of bitmapped image of fax image, in which black runs are corresponded to bits set in 0. The length of the black runs is returned by ClimBlack and the length of the white runs is returned by ClimWhite. To set bits in 1 for white runs isn’t necessary because the output buffer for bitmapped image of fax page is filled with 0xFF. The method SetPixels is used as the base operation in creation and rendering of bitmapped images of fax pages. CREATION OF BITMAPPED IMAGE OF FAX DOCUMENT PAGES Bitmapped graphics format (BMP or DIB) is used internally by the Microsoft Windows graphics subsystem (GDI), and used commonly as a simple graphics file format. MFC library contains class CBitmap, intended especially for working with bitmapped images and allowed programmers to create and visualize BMP images very easy [2]. The algorithm of the fax page bitmapped image creation might be parted in few steps: 1. The buffer size’s calculation. 2. Allocate memory needed for creation bitmapped image. 3. Filling buffer with 0xFF. 4. Creation bitmapped image in buffer, using SetPixels. 5. Create CBitmap object and fill it with bitmapped images of fax page from the buffer. This algorithm is implemented as the method of CFFPage class, code of which is given below: CBitmap* CSFFPage::GetBitmap () const { int width = GetWidth (PIXEL); int height = GetHeight(PIXEL); int bytesInRow = ( width % 16 )?( (width / 16 + 1) * 2):(width / 16* 2); BYTE* buf = (BYTE*)malloc (bytesInRow * height); memset (buf, 0xFF, bytesInRow * height); for (int i = 0; i < height; i++) { SetPixels (buf + i * bytesInRow, i); } CBitmap *pBmp = new CBitmap; pBmp->CreateBitmap (bytesInRow * 8, height, 1, 1, buf); free (buf); return pBmp; }

The bitmapped image of fax page created in the buffer buf is saved to CBitmap object with the method of CBitmap class CreateBitmap( int nWidth, int nHeight, UINT nPlanes, UINT nBitcount, const void* lpBits ). This method initializes a device-dependent memory bitmap that has the specified width, height, and bit pattern. For monochrome bitmap, the parameters nplanes (the number of color planes), nBitcount (the number of bit for every color) are set in 1. Although the created bitmap cannot be directly selected in a display device for rendering, it can be selected as the current bitmap for a memory device context by using CDC::SelectObject method in OnDraw function of CView class, which is intended to render images in MFC object-oriented program. VISUALIZATION OF BITMAPPED IMAGES OF FAX DOCUMENTS The part of OnDraw method code, used for visualization fax page images, saved in CBitmap object is given below: void CSFFViewerView::OnDraw(CDC* pDC) { // Select CBitmap object for currently selected page of fax document

- I.4-3 -

International Conference on Computer Systems and Technologies - CompSysTech’07 CBitmap* pbitmapold = m_pcdcMemory ->SelectObject(m_ppageBmp); // Copy the bitmapped images into the destination rectangle in display context pDC->StretchBlt (ptBitmap.x,ptBitmap.y,distsize.cx,distsize.cy, m_pcdcMemory, 0, 0,m_sourcesize.cx,m_sourcesize.cy, SRCCOPY); //Deselect object m_pcdcMemory -> SelectObject(pbitmapold); }

The main window of SFFViewer program with bitmapped image of one page of the decompressed SFF file is given on fig. 1.

Fig.1. Main window of SFFViewer program with one decompressed page. It’s possible to select the mode for rendering the fax pages. Sometimes, it’s needed a page to be visualized as a mirror image or to be rotated on 180 grades. Elementary zoom operation is implemented, too. All these options as well as the number of the page in fax document could be selected using toolbars with icons, images of which explain the sense of the operations. SAVING FAX DOCUMENT PAGES IN BMP FILES Sometimes it’s would be useful for the customers to save bitmapped fax images to BMP files, for example to process it with the graphic editors and compress to the other format or for other purposes. This operation is implemented as the method WriteBitMap(CFile* pFile) of class CSFFPage. Code of this method is given below: BOOL CSFFPage::WriteBitMap(CFile* pFile) { // Create DIB (Device independent Bitmap) for this page

- I.4-4 -

International Conference on Computer Systems and Technologies - CompSysTech’07 // and fills the BITMAPINFOHEADER, BITMAPFILEHEADER structures int width = GetWidth (PIXEL); int height = GetHeight(PIXEL); //! Rows in DIB must be padded to 4-byte boundary int bytesInRow = ( width % 32 )?( (width / 32 + 1) * 4):(width / 32* 4); BYTE* buf = (BYTE*)malloc (bytesInRow * height); memset (buf, 0xFF, bytesInRow * height); int i,j; // Allocate temporary buffer for mirror row in X-direction BYTE* tmp = (BYTE*)malloc (bytesInRow); BYTE* curbuf; if (m_nAngle)//m_nAngle=180 -> first row in Dib is the top row of page { for ( i = 0; i < height; i++) { curbuf = buf + i * bytesInRow; SetPixels (curbuf, i); //Makes byte's mirror in X-direction for ( j = 0; j < bytesInRow; j++) { tmp[j] = curbuf[bytesInRow-j-1]; } // Makes bits mirror in X-direction DoMirror( tmp, bytesInRow ); memcpy(curbuf,tmp,bytesInRow); } } else // m_nAngle=0 -> first row in Dib is the bottom row of page { for ( i = height-1; i >=0; i--) SetPixels (buf + (height-i-1) * bytesInRow, i); } free (tmp); // Set two entries to color table DWORD black = 0x0000;// RGBQUAD black = { 0,0,0,0}; RGBQUAD white = { 255,255,255,0}; // Set BITMAPFILEHEADER structure BITMAPFILEHEADER bmfh; bmfh.bfType = 0x4d42; // 'BM' int nSizeHdr = sizeof(BITMAPINFOHEADER) + sizeof(RGBQUAD) * 2; bmfh.bfSize = sizeof(BITMAPFILEHEADER) + nSizeHdr + bytesInRow * height; bmfh.bfReserved1 = bmfh.bfReserved2 = 0; bmfh.bfOffBits = sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER) + sizeof(RGBQUAD) * 2; // Set BITMAPINFOHEADER structure BITMAPINFOHEADER bi; bi.biSize = sizeof(BITMAPINFOHEADER); bi.biWidth = width; bi.biHeight = height; bi.biPlanes = 1; bi.biBitCount = 1; bi.biCompression = BI_RGB; bi.biSizeImage = 0; bi.biXPelsPerMeter = (long)((float)lineLength /(float) GetHRes ()/2.54f*100.0f); bi.biYPelsPerMeter=(long)((float)indexes.GetUpperBound()/ (float)GetVRes()/2.54f*100.0f); bi.biClrUsed = 2; bi.biClrImportant = 2;

- I.4-5 -

International Conference on Computer Systems and Technologies - CompSysTech’07 try {

}

pFile->Write((LPVOID) pFile->Write((LPVOID) pFile->Write((LPVOID) pFile->Write((LPVOID)

&bmfh, sizeof(BITMAPFILEHEADER)); &bi, sizeof(BITMAPINFOHEADER)); &black, sizeof(DWORD)); &white, sizeof(DWORD));

pFile->Write((LPVOID) buf, bytesInRow * height); } catch(CException* pe) { pe->Delete(); AfxMessageBox("write error"); free (buf); return FALSE; } free (buf); return TRUE;

Because BMP files are not compressed, so they are typically much larger than compressed image file formats for the same image. If BMP file is needed to be transferring on the Internet, it must be converted to JPEG, GIF or PNG formats. CONCLUSIONS AND FUTURE WORK Statistical codes with variable length are considered to be the most efficient, but because codes aren’t in byte boundaries it’s very difficult to develop fast and efficient decompressing algorithm. The approach applied in SFFViewer program that uses decoding tables instead of binary tree allows development of fast decompressing algorithm. Rendering of the fax document pages is performed as fast as if they would be saved in the decompressing form. SFFViewer program has MFC SDI structure and was designed using object-oriented approach, what allows the same structure to be used for development the MFC program for other types of compressed images such as well known GIF or PNG, as well as for new developed ones. The reusability of the most part of the code is the reason SFFViewer might be used in e-learning as the example for development decompressing programs as well as for studying Huffman code, C++, objectoriented programming and computer graphics. The other direction for the future work is to use bitmapped images in memory for image processing. REFERENCES [1] Huffman D. A., "A method for the construction of minimum-redundancy codes", Proceedings of the I.R.E., 1952, pp 1098-1102, 1952. [2] Kruglinski David, Inside Visual ++ 6.0, Microsoft Press, 1999. ABOUT THE AUTHOR Research associate Galina Istatkova, Institute of Computer and Communication Systems, Bulgarian Academy of Science. Phone: (359 2) 76 77 01, GSM – +359 898 89 30 59, E-mail: [email protected].

- I.4-6 -