Welcome to MSDN Blogs Sign in | Join | Help

STS: A palindromic word I will remember

Continuing searching palindromic sqaure numbers finds a new record number, a 55 digit parlindromic square:

 1373512530649258635292477609^ 2 = 1886536671850530641991373196913731991460350581766356881

Quite a few records for other palindromic sequences have also been broken my multi-core searching algorithm. Check http://www.worldofnumbers.com/palrecs.htm for details.

But the focus of this posting is really about a simple palindromic acronym: STS, which stands for Science Talent Search. It is a science/math competition for high-school seniors sponsored by Intel.

STS has just announced their 40 finalists for the year of 2007 (http://www.societyforscience.org/sts/), and our son is the lucky one from Washington state. His research paper is titled: Explicit Equations in the Plane for Elliptic Curves Given as Space Quartics.

Congratulations to all the winners and thanks Intel for promoting science/math in schools.

Posted by fyuan | 1 Comments

A 53-digit Palindromic Square Number

Six years ago I wrote a program to search for palindromic square numbers and other palindromic numbers and found some new palindromic numbers. But with increasing length, the search became longer and longer so I finally gave it up.

Recently I got a new powerful machine with dual quad-core CPUs, so I brought it home during the Christmas and New Year holiday season. I modified my old search program to take advantage of multi-cores in the machine. The search program has tons of parallelism inside. Although the original code was written as incremental loops for performance reason, it is not hard to change it to run on multi-core system. The result is almost 8 fold improvement in speed, on top of CPU speed gain for the last six years.

With the multi-core version, I tried continuing the old quest again and find quite a few record breaking palindromic numbers during the holiday season. But I did not try to break the 52-digit palindromic square number record held by Pete Leadbetter since May 20, 2001 until last night. Before leaving work, I started searching for 53 digit paradromic sqaures and this morning we have a new record, a 53-digit palindromic square number:

122063831551139898460740721 ^ 2 = 14899578972945056149893218681239894165054927987599841

Other palindromic number records can be found at:

http://www.worldofnumbers.com/palrecs.htm

Go MultiCore!

Posted by fyuan | 1 Comments

XpsStat: A program for gathering statistics information of XPS documents

In the Winhec presentation on XPS document performance optimization, a simple program XpsStat is introduced to analyze XPS documents. 

Given an XPS document, XpsStat generates four or five tables in HTML format:

  • Container Summary Table: information about each type of parts in the document.
  • FixedPage / Remote Resource Dictionary Table: information about each fixed page / remote resource dictionary in the document.
  • Font Resource Table: information about each font resource in the document
  • Image Resource Table: information about each image resource in the document
  • Container Part Table (optional): information about each part in the document

The program has three command line options:

  • /x Generate report in XML format instead of the default HTML format
  • /a Generate the optional Container Part Table
  • /d Extract fonts to external files, unobfuscated.

The program is written using .Net 3.0 XPS related API and some direct parsing of ZIP container. It supports both interleaved and non-interleaved XPS files.

Here is the binary: http://blog.fengyuan.com/XpsStat.exe

Here is what the Container Summary Table the program will generate for XPS Specification 1.0 in XPS format:

Container Summary
Type Count Piece Uncompressed Compressed Compression
Size Percent Average Size Percent Average
fixedpage+xml 453 453 116,521,006 96.74 % 257,220 5,912,474 75.13 % 13,051 94.93 %
package.relationships+xml 434 434 573,558 0.48 % 1,321 164,871 2.09 % 379 71.25 %
properties+xml 1 1 673 0.00 % 673 342 0.00 % 342 49.18 %
fixeddocument+xml 1 1 289,702 0.24 % 289,702 13,756 0.17 % 13,756 95.25 %
opentype 20 20 1,647,572 1.37 % 82,378 576,144 7.32 % 28,807 65.03 %
image 492 492 1,042,993 0.87 % 2,119 992,681 12.61 % 2,017 4.82 %
fixeddocumentsequence+xml 1 1 320 0.00 % 320 160 0.00 % 160 50.00 %
documentstructure+xml 1 1 179,194 0.15 % 179,194 13,154 0.17 % 13,154 92.66 %
/Documents/1/ 1 1 0 0.00 % 0 0 0.00 % 0 NaN %
/[Content_Types].xml 1 1 1,023 0.00 % 1,023 331 0.00 % 331 67.64 %
/Documents/1/_rels/ 1 1 0 0.00 % 0 0 0.00 % 0 NaN %
/Documents/1/Pages/ 1 1 0 0.00 % 0 0 0.00 % 0 NaN %
/Resources/Images/ 1 1 0 0.00 % 0 0 0.00 % 0 NaN %
/Documents/1/Pages/_rels/ 1 1 0 0.00 % 0 0 0.00 % 0 NaN %
/Documents/1/Structure/ 1 1 0 0.00 % 0 0 0.00 % 0 NaN %
ZIP Structure 195,978 0.16 % 195,978 195,978 2.49 % 195,978 0.00 %
Summary 1,410 1,410 120,452,019 100.00 % 85,426 7,869,891 100.00 % 5,581 93.47 %

Posted by fyuan | 5 Comments
Filed under: ,

XPS Performance

There will be two XPS related sessions at Winhec 2007 tomorrow, focusing on Performance Optimization for XPS Document.

The techincal presentation (CLN-T371 ) will be at 8:30am to 9:30am in Room 502AB. Shortly after that (9:45 to 10:45), there will be a chalk talk (CLN-C372) in Room 409A on the same topic.

The focus of the talk will be on how to generate the better XPS so that XPS documents can be consumed efficiently. So we will go into great deails about how to measure XPS document for performance and ideas on how to generate better XPS. But we will cover XPS performance issues in general. So even if you're just consuming XPS documents, this presentation should still be very much relevant to you. The reason is that this presentation is written from the viewpoint of a XPS consumer.

I'm pretty sure that you will either learn something useful from the presentation and chalk talk, or you can teach the community something about XPS.

Optimization XPS document is just part of the story in the whole world of XPS performance. The rest of the story includes performance of XPS filter pipeline, the design and configuration of XPS filters, the performance of XPS rendering (either host based or in printer firmware).

Talking about performance and learning, Zoran (www.zoran.com) has an encouraging demo at Winhec showing that their host-based rendering engine is able to achive print-engine-limited printing speed (HP Color LaserJet 4700, 31 ppm), for normal office type text documents with some vector graphics and images.

One final note, I was told that people tend to need lots of coffee for morning session after evening party.

See you tomorrow.

 

Posted by fyuan | 1 Comments
Filed under: ,

XPS at Winhec 2007

Today (May 15, 2007) is the first day of Winhec 2007.

If you're application developers, printer/scanner/multi-functional device vendors, you may be interested in the following XPS related sessions.

  • CLN-T370 XPSDrv: Best Practice using Print Verifier, May 15, 3:15pm-4:15pm 515B, Manski & Ashwin
  • CLN-C369 (Chalk Talk) Print Verifier and XPSDrv Driver Development, May 15, 4:30pm-5:30pm 409A, Erhan
  • CLN-T375 HP Photo: Implementation Guidelines, May 16 11:00am-noon, 408AB, Bill Crow
  • CLN-T371 Performance Optimization for XPS Documents, May 17, 8:30am-9:30am 502AB, Feng
  • CLN-C372 (Chalk Talk) XPS Document Optimization and Best Practice, May 17 9:45am-10:45am, 409A, Rod

In the self-paced hands-lab, there is a XPSDrv related lab. 

The following exhibitors are showing their XPS related technologies:

We're here at Winhec, talk to us.

Posted by fyuan | 1 Comments
Filed under: ,

A Simple XPS Decoder in C++

If you write programs in C#, Windows Presentation Foundation in .Net 3.0 provides quite nice API to write, generate and manipulate XPS documents. You can get the same feature if you work with managed C++ in .Net 3.0. Even if you work with .Net 2.0, you can get the basic ZIP stream decoding/encoding support.

But if you want to write code in unmamanged world, especially outside of the XPS filter pipeline, there is not enough sample code there. I'm going to write a simple XPS decoder in C++, based on the zlib compression library (http://www.zlib.net/zlib123-dll.zip).

#include <windows.h>

#include <stdio.h>

#include <tchar.h>

 

#include "MemFile.h"

#include "zip.h"

#include "zlib.h"

 

#pragma comment(lib, "zdll.lib")

 

HANDLE  CreateDirFile(char * pName, DWORD len, HRESULT & hr);

 

class CXps : CMemoryMappedFile

{

    const CEndCentralDir     * m_pEndCentralDir;

    const CCentralFileHeader * m_pFileHeader;

 

public:

    HRESULT LoadXps(const wchar_t * pFileName);

    HRESULT DecodePiece(const BYTE * pCur, DWORD compressedSize);

    HRESULT ExtractAllStreams();

};

The code uses zlib.h and zdll.lib for decompression. It opens up an XPS container as a memory-mapped file, wrapped in the CXps class. The CXps class has a pointer to end central directory, and a pointer to the first central file header.

HRESULT CXps::LoadXps(const wchar_t * pFileName)

{

    m_pEndCentralDir = NULL;

    m_pFileHeader;

 

    if (! Open(pFileName))

    {

        return E_INVALIDARG;

    }

 

    const BYTE * pCur = m_View + m_nFileSize - (sizeof(CEndCentralDir) - 1);

 

    while (pCur > m_View)

    {

        DWORD signature = * (DWORD *) pCur;

 

        if (signature == sig_EndCentralDir)

        {

            m_pEndCentralDir = (const CEndCentralDir *) pCur;

            m_pFileHeader    = (const CCentralFileHeader *) (m_View + m_pEndCentralDir->m_offsetCentralDic);

 

            return S_OK;

        }

       

        pCur --;

    }

 

    return E_FAIL;

}

The LoadXps method opens up an XPS file and locates its end central directory by reading backward from the end of the ZIP file.

HRESULT CXps::ExtractAllStreams()

{

    HRESULT hr = S_OK;

 

    const CCentralFileHeader * pFile = m_pFileHeader;

 

    for (int i = 0; SUCCEEDED(hr) && (i < m_pEndCentralDir->m_entryCentralDic); i ++)

    {

        hr = DecodePiece(m_View + pFile->m_offsetLocalHeader, pFile->m_compressedSize);

 

        pFile = (const CCentralFileHeader *) (pFile->m_Data + pFile->m_nFileName + pFile->m_nExtraField + pFile->m_nFileComment);

    }

  

    return hr;

}

 

 

int XpsExtract(const wchar_t * pFileName)

{

    CXps xpsFile;

 

    HRESULT hr = xpsFile.LoadXps(pFileName);

 

    if (SUCCEEDED(hr))

    {

        hr = xpsFile.ExtractAllStreams();

    }

 

    printf("\nhr = %x\n", hr);

 

    return 0;

}

The ExtractAllStreams method tries to extract every pieces in the XPS container to an file on the disk by calling DecodePiece method. The main routine XpsExtract is responsible for calling the loading routine and the main extracting routine.

The most complicated routine here is DecodePiece:

HRESULT CXps::DecodePiece(const BYTE * pCur, DWORD compressedSize)

{

    HRESULT hr = S_OK;

 

    const CLocalFileHeader * pHeader = (const CLocalFileHeader *) pCur;

 

    char * pName = new char[pHeader->m_nFileName + 1];

 

    if (pName == NULL)

    {

        return E_OUTOFMEMORY;

    }

 

    memcpy(pName, pHeader->m_Data, pHeader->m_nFileName);

    pName[pHeader->m_nFileName] = 0;

 

    printf("\n%8d %8d %-60s", pHeader->m_uncompressedSize, compressedSize, pName);

 

    HANDLE hFile = CreateDirFile(pName, pHeader->m_nFileName, hr);

 

    delete pName;

 

    if (FAILED(hr))

    {

        printf("\nUnable to open file\n");

 

        return hr;

    }

 

    pCur = pHeader->m_Data + pHeader->m_nFileName + pHeader->m_nExtraField;

   

    if (pHeader->m_compression != 0)

    {

        BYTE * pOutput = new BYTE[pHeader->m_uncompressedSize];

 

        if (pOutput == NULL)

        {

            return E_OUTOFMEMORY;

        }

 

        z_stream stream;

 

        memset(&stream, 0, sizeof(stream));

 

        stream.avail_in  = compressedSize;

        stream.avail_out = pHeader->m_uncompressedSize;

        stream.next_in   = (Bytef *) pCur;

        stream.next_out  = pOutput;

 

        int result = inflateInit2(& stream, -MAX_WBITS);

 

        if (result == Z_OK)

        {

            result = inflate(& stream, Z_SYNC_FLUSH);

        }

 

        DWORD dwWritten;

 

        WriteFile(hFile, pOutput, pHeader->m_uncompressedSize, & dwWritten, NULL);

 

        delete [] pOutput;

    }

    else

    {

        DWORD dwWritten;

 

        WriteFile(hFile, pCur, pHeader->m_uncompressedSize, & dwWritten, NULL);

    }

 

    CloseHandle(hFile);

 

    return hr;

}

 

DecocePiece has two parameters: a pointer to local file header structure, and compressed size. Note the compressed size may not be stored in the local file header, so it's better to pass it in from the end of the container. From the header structure, we can get its name and call CreateDirFile to create a corresponding file on the disk, making sure the proper directory path is created. The ZLIB decompression routine inflate, together with its preparation routine inflateInit2 are called when the piece is actually compressed. The result uncompressed streams are then written to disk.

The structures not shown here can be easily created by following ZIP specification at http://www.pkware.com/documents/casestudies/APPNOTE.TXT. The CreateDirFile routine is a simple wrapper around CreateFile and CreateDirectory.

The program is implicitly linked with ZLIB1 ZDLL.

Posted by fyuan | 8 Comments
Filed under: ,

Another Ph.D for Bill Gates

On April 19th, Bill Gates has been awarded a honorary Ph.D degree by Tsinghua University (http://en.wikipedia.org/wiki/Tsinghua_University), the best engineering school in China.

Posted by fyuan | 1 Comments

Something useful from 'junk' mails

With a high school junior in the house, we're receiving tons of 'junk' mails from colleges these days. They usually pile up on the desk until we have time to read and discard them.

Today, my wife found something useful, or rather something we have been anxtiously waiting for, an acceptance letter from RSI (Research Science Institute) summer camp at MIT (http://www.cee.org/rsi/) for our son. He is going back to the hot Boston for the summer after attending the PROMYS math summer camp (http://www.promys.org/) at Boston University last year.

Posted by fyuan | 2 Comments

XPS document with 100,000 pages?

Once a simple document format like XPS is created, it takes on a life of its own. Seeing the beauty of XPS, people are converting documents from differenent sources to XPS. People are trying to create XPS document with 10,000 pages, and even pushing for 100,000 pages.

But if you're using Microsoft XPS Document Writer to create XPS document with more than 32,700 odd pages, you may run into a bug in the current implementation. The problem lies in the limitation of 32-bit ZIP file directory structure. The solution is to switch to 64-bit ZIP64 file directory structure.

If you're blocked by this issue, here is a simple-minded piece of code which tries to repair such XPS file.

 int ZipRepair(const wchar_t * pFileName)

{

HANDLE hFile = CreateFile(pFileName, GENERIC_READ | GENERIC_WRITE,

    FILE_SHARE_READ, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);