[Gs-devel] RE: refine MDRC patch

[Igor V. Melichev]

Dear Mr. Toshiya Suzuki,

> From: mpsuzuki at hiroshima-u.ac.jp
> Sent: 15 ?????  2001 ?. 07:38
> To: igor at artifex.com
> Cc: gs-devel at ghostscript.com; mpsuzuki at hiroshima-u.ac.jp
> Subject: Re: [Gs-devel] RE: refine MDRC patch

> (method 1)
> >If I write this from scratch, I would do in reverse order.
> >First I would compare 2 neighbor ranges and find maximal common prefix.
> >Then I take all consecutive ranges, which correspond to the prefix,
> >and generate keys for them. This requires 1 range lookahead.
> 
> (method 2)
> >This algorithm is not optimal also. A better result may be obtained
> >if consider trees of prefixes. Actually there are 3 trees :
> 
> [detailed explanation is omitted, sorry]
> 
> >But I believe that all this is too academic and overcomplicated
> >for our simple problem, so as simple lookahead would give acceptable
> >result.

Excuse me, I said unclear. "too academic and overcomplicated"
relates to "method 2". Method 1 is not complicated, rather 
it requires more changes than your one.

> Much thanks for your comment. I think, the former method
> (making prefix and merge by lookaheaded range) could be
> implemented without changing the interface.

Yes, "method 1" don't require changes to interfaces.

> Although I think the later method improves CMap handler greatly,
> but the indepth change makes me hesitate.

Please forget about "method 2". I only wanted to explain how this
problem looks from academic point of view.

> >Of cause, I can easy construct one, on which your algorithm fails
> >(it can exceed 64K limitation for key string length, if CMap uses
> >3-byte codes), but this is not the issue. The criterion is 3d party
> >CMaps to run effectively.
> 
> I was not aware of the problem, please let me know detail.
> As far as possible, I have to fix the bug or print warning for
> opened bug. I understood your pointing out as following:
> 
>         For the range specification using 3-byte codes,
>         there can be 128 (or more) ranges with same first byte.
>         Aslike:
>         <000101> <000101> 1
>         <000102> <000102> 2
>         ...
>         <00FFFF> <00FFFF> ?
> 
>         My algorithm tried to merge all of them,
>         because they have same prefix <00>.
>         The string collecting each keys exceeds 64k limitation.
> 
> Hmm, now I think I should rewrite prefix/key generator,
> following to your idea.

Right you are.

> Soon I will make quick-fixed version of previous MDRC and publish
> it in this mailinglist, but I don't ask the official adoption of it.

OK, but please let me know whether you intend to make a better version.
I realize that non-ideal solution is better than nothing.

> If I could find same behaviour on PS printers with OEM rasterizer
> by Adobe (around me, there are Level 2 & 3), it can be some proof?

If it is based on Adobe CPSI, it would be a confirmation
of your hypothesis. In this case you can say that your method
is CPSI-compatible. Possibly it is bug-to-bug compatible.
A proof may be taken only from specs.

> Of course, I appreciate the attitude to keep the compatibility
> with Adobe official PostScript implementation, so if "relpos"
> is incompatible with Adobe, I must remove it.

My point is : 'relpos' to be removed because (1) it is not needed
for correct processing of known CMaps, and (2) it is not a
documented feature. I can change my opinion, if you
point out more reasons for including it : find 3d party CMap
which depend on it, or find a spec about it. Otherwise there
is risk that *we* will propose a not-well-reasoned extension
for Adobe PostScript, then multiple users create CMaps
depending on it, and later Adobe gets good chance to make damage
to Artifex and to the community of free users of GS by defining
a non-compatible extension in their level 4. 
Due to this we are very conservative about extensions.

I realize that your 'relpos' is pretty nice function, but 
in real world many beautiful programs go to trash. This is the life.
I've coded about 400M sources total, and about half of them was
for trash. Skilled programmers should not feel bad of such events.

Meanwhile this doesn't mean that 'relpos' to be thrown forever.
Possibly we'll need to insert it later. Please keep it
in your archive.

Igor.