🚀 go-pugleaf

In article <1992Sep8.143846.3667@Princeton.EDU>
dmlaur@ernie.Princeton.EDU (David M. Laur) writes:

>Am I correct in computing the worst case expansion of an input file
>under RunLengthEncode followed by ASCII85Encode to be
>
>   (worst output size) = (input data size) (4/3) (5/4)
>
>i.e.  for data of the form "abbabbabbabb ..." the RLE algorithm
>requires two bytes for each 'a' (right?)

No. There is nothing that requires you to encode repeated characters
as a repetition. You can encode the entire input as literal text,
producing an expansion of 128/127. This is the worst case. Use the
repetition encoding only when there is an advantage in doing so.

>Secondly, is there something wonderfully magic about the number 85
>that makes the encoding algorithm Very Easy(tm)?

I'm not aware of any tricks that apply specifically to multiplying and
dividing by 85. The choice of 85 as a base derives from it being the
smallest integer n such than n^5 >= 2^32.
-- 
Ed Taft      taft@adobe.com      ...decwrl!adobe!taft

taft@adobe.com (Ed Taft) writes:
> dmlaur@ernie.Princeton.EDU (David M. Laur) writes:
> >Secondly, is there something wonderfully magic about the number 85
> >that makes the encoding algorithm Very Easy(tm)?
> 
> I'm not aware of any tricks that apply specifically to multiplying and
> dividing by 85. The choice of 85 as a base derives from it being the
> smallest integer n such than n^5 >= 2^32.

No, 85 is not particularly easy, it's just the largest "safe" value for this
application.  Base-85 representation is customarily used for representing
arbitrary binary files as ASCII text so that they can be mailed around on
Usenet.  It happens that there are 85 printable ASCII characters that have
exact EBCDIC equivalents.  If you try to use all 95 ASCII characters, you
run the risk of your file getting mangled in an ASCII <=> EBCDIC conversion
performed by some mail gateway.  (And of course, using any ASCII control
characters or characters with the 8th bit set is hopeless...)

At least, that was *my* understanding of the design.  The fact that 5
base-85 characters can represent 32 bits is convenient but it's not really
the driving force.

				regards, tom lane

ps: any further discussion should probably move to comp.compression.

In article <1992Sep8.205244.17495@adobe.com>, taft@adobe.com (Ed Taft) writes:
|> In article <1992Sep8.143846.3667@Princeton.EDU>
|> dmlaur@ernie.Princeton.EDU (David M. Laur) writes:
[...]
|> >Secondly, is there something wonderfully magic about the number 85
|> >that makes the encoding algorithm Very Easy(tm)?
|> 
|> I'm not aware of any tricks that apply specifically to multiplying and
|> dividing by 85. The choice of 85 as a base derives from it being the
|> smallest integer n such than n^5 >= 2^32.

However, it so happens that there are some tricks to aid multiplication
and division by 85, in the absence of decent integer multiply or divide
hardware, based on the fact that 85 = (2^8-1)/3. For multiplication

  y = (x<<2)+x ; z = (y<<4)+y   /* would be two instructions on an ARM */

makes z == 85*x. For division use 1/85 = 3/2^8 + 3/2^16 + 3/2^24 + ...;
details left as an exercise for the reader (as they say in all the best
books).

Chris Thompson
Cambridge University Computing Service
JANET:    cet1@uk.ac.cam.phx
Internet: cet1@phx.cam.ac.uk