Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!corton!chorus!nocturne.chorus.fr!jloup
From: jloup@nocturne.chorus.fr (Jean-Loup Gailly)
Newsgroups: comp.compression
Subject: Re: Response to Jean's criticism of proposed standard.
Keywords: data compression proposed interface standard memory typing
Message-ID: <11134@chorus.fr>
Date: 21 Jun 91 20:14:23 GMT
References: <866@spam.ua.oz>
Sender: jloup@chorus.fr
Reply-To: jloup@nocturne.chorus.fr (Jean-Loup Gailly)
Organization: Chorus systemes, Saint Quentin en Yvelines, France
Lines: 70

In article <866@spam.ua.oz>, ross@spam.ua.oz.au (Ross Williams) writes
in response to my earlier comments:

> Can't we just make all the PCs go away?

Agreed. All but one (mine).

> One  problem  here  is  that   many  algorithms  allocate  heap  items
> incrementally as  they build their data  model. It seems silly  for an
> algorithm that is told that it can have three megabytes to make 100000
> allocation calls only to later find out that it only has to process 1K
> of  data! If  the standard  has to  be changed  so that  the algorithm
> allocates its own memory  then I am in favour of allowing  it to do so
> incrementally, but  to ensure that  it does not  use more than  it has
> been allowed.

I also agree that incremental allocation is important for some algorithms.
But I don't think that you need a bullet proof protection against
algorithms which do not follow the rules. If you cannot prove from
the source of your algorithm that the amount of required memory is bounded by
a certain value you are in trouble anyway. Even in your original proposal
you could not guard against malicious use of the stack or heap without
checking the source code.

> I agree with your analysis and propose the following:
> 
>    1. The identity record specifies the maximum amount of memory to be
>       used.
>    2. This memory may be allocated from the heap only. (However, the
>       procedure can still use up to 1024 bytes of other memory.)

I think you mean that the memory must not be allocated before the
"Initialize data structures" call and must be deallocated no later
than the "Destroy data structures" call. This is sufficient to
disallow static data. There is no need to make an explicit reference
to "heap". I am not convinced that you must disallow stack usage.
Many architectures do not have small limits on the stack size, and
stack space is cheaper than heap space. Of course the part of
the data structures which must live across compression calls must
be in the heap and accessed through the MEMORY parameter, but temporary
data could be on the stack. (For example the LZW uncompress requires a stack
to reverse the bytes of a code string.)

>    4. The memory parameter will become an INOUT generic pointer in which
>       the algorithm should place a reference to the root of its
>       data structure during an init call.

Please allow this pointer to have a meaningful type for strongly
typed languages. In other words, the type may be different for
different algorithms. In C terminology allow (struct foo *) instead of
(void *).

> Jean: Thanks  for your  comments. Do  you agree  with the  proposal as
> given above?

Yes. In particular it is nice to allow incremental allocation.

Jean-loup
jloup@chorus.fr

PS: My only strong disagreement is to be named Jean :-) Hyphenated
french names must not be split.

> PS: Please don't  think I'm a typeless troglodyte.  My SAKDC algorithm
> is written in Ada and is  full of rock-solid highly typed abstractions
> using great  big heap based data  structures. It's just that  my brain
> has been warped by coding in C recently.

I have myself fallen from the Ada language design team down to earth (C++) :-)
But I'd like to get your SAKDC.