Decoding an octet stream

Decoding an octet stream

[Florian Weimer]

What is the best way to decode an octet stream (i.e. a sequence of
unsigned eight-bit values) with Ada?  The octet stream consists of
packet markes (single octets), two-octet integers (stored with the
most significant octet first), strings (sequences of octets of a given
length) and so on.  I don't want to use Ada.Sequential_IO, because it
would mean that only one octet can be read at a time, which seems to
be quite inefficient.

Streams seem to be nice, though.  If I specify the necessary
representation clauses, I think I'll only have to write a few 'Read
and 'Write operations, and composed types will be handled correctly
almost automatically.  But is this really portable?  Are there any
targets (except supercomputers, mainframes, and embedded systems)
where Stream_Element'Size isn't equal to 8?

BTW: I'm currently reading the two-octet integers using a construct like
`First_Octet * 2**8 + Second_Octet'.  Is it possible to denote the octet
ordering using a representation clause?  For a target with a matching
octet order, more efficient code could be generated.

Re: Decoding an octet stream

[David C. Hoos, Sr.]

Florian Weimer <" "@deneb.cygnus.argh.org> wrote in message
news:877lj2q36g.fsf@deneb.cygnus.argh.org...
> What is the best way to decode an octet stream (i.e. a sequence of
> unsigned eight-bit values) with Ada?  The octet stream consists of
> packet markes (single octets), two-octet integers (stored with the
> most significant octet first), strings (sequences of octets of a given
> length) and so on.  I don't want to use Ada.Sequential_IO, because it
> would mean that only one octet can be read at a time, which seems to
> be quite inefficient.
>
> Streams seem to be nice, though.  If I specify the necessary
> representation clauses, I think I'll only have to write a few 'Read
> and 'Write operations, and composed types will be handled correctly
> almost automatically.  But is this really portable?  Are there any
> targets (except supercomputers, mainframes, and embedded systems)
> where Stream_Element'Size isn't equal to 8?
>
> BTW: I'm currently reading the two-octet integers using a construct like
> `First_Octet * 2**8 + Second_Octet'.  Is it possible to denote the octet
> ordering using a representation clause?  For a target with a matching
> octet order, more efficient code could be generated.

Here's a package I use for just that purpose.  All two- and four-byte
scalar types used in network packets have their 'read and 'write
attributes overridden by instances of these generic procedures.

------------------------------------------------------------------------
-- Byte_Ordering
-- Purpose:
-- Instantiations of the generic procedures provided by This package
-- are Read and Write procedures fully-conformant with the 'Read and
-- 'Write attributes of the type with which the procedure was
-- instantiated.
-- The procedures transform the stream to network order, according to
-- the endianness of the target host.
-- Thus, instantiations of these procedures may be used to override
-- the default stream-oriented attributes of scalar types, so that
-- their stream reads and writes are done in network order,
-- irrespective of host ordering (endianness).
------------------------------------------------------------------------

with Ada.Streams;
package Byte_Ordering is

   generic
      type Item_Type is private;
   procedure Read
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   :    out Item_type);

   generic
      type Item_Type is private;
   procedure Write
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   :        Item_type);

end Byte_Ordering;
with System;
package body Byte_Ordering is

   type U8  is mod 2 ** 8;
   for U8'Size use 8;

   type U8_Array   is array (Integer range <>) of U8;

   --=======================
   -- Private subprograms ==
   --=======================

   ----------
   -- Swap --
   ----------

   procedure Swap
     (The_Item : in out U8_Array)
   is
      The_Bytes : array (1 .. The_Item'Size / U8'Size) of U8;
      for The_Bytes'Address use The_Item'Address;
      Temp : U8;
   begin
      for B in 1 .. The_Bytes'Last / 2 loop
         Temp := The_Bytes (B);
         The_Bytes (B) := The_Bytes (The_Bytes'Last - B + 1);
         The_Bytes (The_Bytes'Last - B + 1) := temp;
      end loop;
   end Swap;

   --======================
   -- Public subprograms ==
   --======================

   ----------
   -- Read --
   ----------

   procedure Read
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   :    out Item_type)
   is
      The_Bytes : U8_Array (1 .. Item'Size / U8'Size);
      for The_Bytes'Address use Item'Address;
      use type System.Bit_Order;
   begin
      U8_Array'Read (Stream, The_Bytes);
      if System.Default_Bit_Order = System.Low_Order_First then
         Swap (The_Bytes);
      end if;
   end Read;

   -----------
   -- Write --
   -----------

   procedure Write
     (Stream : access Ada.Streams.Root_Stream_Type'Class;
      Item   :        Item_Type)
   is
      Item_Copy : Item_type := Item;
      The_Bytes : U8_Array (1 .. Item_Copy'Size / U8'Size);
      for The_Bytes'Address use Item'Address;
      use type System.Bit_Order;
   begin
      if System.Default_Bit_Order = System.Low_Order_First then
         Swap (The_Bytes);
      end if;

      U8_Array'Write (Stream, The_Bytes);
   end Write;

end Byte_Ordering;

Re: Decoding an octet stream

[Florian Weimer]

"David C. Hoos, Sr." <david.c.hoos.sr@ada95.com> writes:

>       if System.Default_Bit_Order = System.Low_Order_First then
>          Swap (The_Bytes);
>       end if;

Does this really work?  I thought that System.Default_Bit_Order
hasn't got to do anything with octet ordering issues (aka endianess).
After all, there are more than just two methods of combining four octets
to a 32 bit integer (for example).

Re: Decoding an octet stream

[Robert Dewar]

In article <3844A51A.1B629776@research.canon.com.au>,
  Geoff Bull <geoff@research.canon.com.au> wrote:
> What patent? (searching for in/williams gets > 7000 hits!)
> I guess a patent number is a bit much to expect,
> but can you provide some keywords to search for,
> or say which aspects of David's package may infringe?

This is the patent on using a canonical form to deal with
communication between little-endian and big-endian machines.

> Also, don't patents now expire 20 years from the filing date
> rather than 17 years from the grant date?


This was granted quite some time ago, very likely it has
expired by now.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Decoding an octet stream

[David C. Hoos, Sr.]

Robert Dewar <robert_dewar@my-deja.com> wrote in message
news:821rc5$bim$1@nnrp1.deja.com...
> In article <81u247$kc3$1@hobbes2.crc.com>,
>   "David C. Hoos, Sr." <david.c.hoos.sr@ada95.com> wrote:
> > Here's a package I use for just that purpose.  All two- and
> four-byte
> > scalar types used in network packets have their 'read and
> 'write
> > attributes overridden by instances of these generic
> procedures.
>
> David, doesn't this infringe on the patent, or has 17
> years gone by now (I have not kept track, the patent holder
> is I believe Mark Williams).

What patent, pray tell?

I admit to not having thought much about patents in recent years.

But, from my previous employment with a company that was fanatic
about patenting everything in sight, and the education I received
in their attempts to obtain a patent on one of my electronic
component designs, one principle that seems applicable here is
that what is "obvious to one skilled in the art" is not patentable.

Nevertheless, I am eager to learn what patent might be infringed
by this small, and to my thinking, "obvious to one skilled in the
art," snippet of code.  If it does infringe, I shudder to think
what other infringements might be buried in the hundreds of thousands
of lines of code I've written over 41 hears of 'practicing the art.

David C. Hoos, Sr.
--
The primary purpose of the DATA statement is to give names to
constants; instead of referring to pi as 3.141592653589793 at every
appearance, the variable PI can be given that value with a DATA
statement and used instead of the longer form of the constant.  This
also simplifies modifying the program, should the value of pi change.
                -- FORTRAN manual for Xerox Computers

Re: Decoding an octet stream

[swhalen]

David C. Hoos, Sr. <david.c.hoos.sr@ada95.com> wrote:
: Robert Dewar <robert_dewar@my-deja.com> wrote in message
:>
:> David, doesn't this infringe on the patent, or has 17
:> years gone by now (I have not kept track, the patent holder
:> is I believe Mark Williams).

: What patent, pray tell?

: I admit to not having thought much about patents in recent years.

: But, from my previous employment with a company that was fanatic
: about patenting everything in sight, and the education I received
: in their attempts to obtain a patent on one of my electronic
: component designs, one principle that seems applicable here is
: that what is "obvious to one skilled in the art" is not patentable.

: Nevertheless, I am eager to learn what patent might be infringed
: by this small, and to my thinking, "obvious to one skilled in the
: art," snippet of code.  If it does infringe, I shudder to think
: what other infringements might be buried in the hundreds of thousands
: of lines of code I've written over 41 hears of 'practicing the art.

From the U.S. Patent Office server (http://www.uspto.gov/):

United States Patent
4,956,809
George , et al.
September 11, 1990

Method for canonical ordering of binary data for portable operating systems 

Abstract:

A method for making files compatible between different computers
having different binary structures while using the same operating
system by keeping all files in a standardized canonical order when
they move to or from external data storage or communication means. The
method includes converting all binary data accessed from a file or
communications channel from the canonical order to the natural order
of the host computer before using the binary data in the host computer
and converting all binary data which is to be sent to a file or
communications channel from the natural order of the host computer to
the canonical order before sending the binary data.

Inventors:

George; Johann (Holland Landing, CA); Thompson; Trevor
J. (New Providence, NJ); Conroy; David G. (Maynard, MA);
            Tudor; Frederick H. (Evanston, IL)
Assignee: 
    
Mark Williams Company (Chicago, IL) 

Filed:    December 29, 1988

...

I'll try to supress my disgust at how far the patent process
has strayed from reality in the few years you've not been paying
attention, but suffice to say our Patent Office has no clue as
to what consitutes "prior art" or is "obvious" (at least in the
software field). 

Many patents have been issued in the last few years that have been
used widely in the past and/or were obvious to me many years ago,
and I've only been programming for about 30 years...

Steve

-- 
{===--------------------------------------------------------------===}
                Steve Whalen     swhalen@netcom.com
{===--------------------------------------------------------------===}

Re: Decoding an octet stream

[Larry Kilgallen]

In article <8233fm$ngf$1@nntp3.atl.mindspring.net>, swhalen@netcom.com writes:

> Abstract:
> 
> A method for making files compatible between different computers
> having different binary structures while using the same operating
> system by keeping all files in a standardized canonical order when
> they move to or from external data storage or communication means. The
> method includes converting all binary data accessed from a file or
> communications channel from the canonical order to the natural order
> of the host computer before using the binary data in the host computer
> and converting all binary data which is to be sent to a file or
> communications channel from the natural order of the host computer to
> the canonical order before sending the binary data.

That abstract could also be used to describe ASN.1 BER encoding.

Does the detailed description indicate what part is novel ?

Larry Kilgallen

Re: Decoding an octet stream

[Robert Dewar]

In article <822o4d$ehh$1@birch.prod.itd.earthlink.net>,
  "David C. Hoos, Sr." <david.c.hoos.sr@ada95.com> wrote:
> But, from my previous employment with a company that was
> fanatic about patenting everything in sight, and the education
> I received in their attempts to obtain a patent on one of my
> electronic component designs, one principle that seems
> applicable here is that what is "obvious to one skilled in the
> art" is not patentable.

You would be surprised how difficult it can be to prove that
something is obvious. In particular, there tends to be an
assumption that if there is no prior art, then how can it be
so obvious. Case law would surprise you here!

I quite agree this is indeed obvious :-)

> Nevertheless, I am eager to learn what patent might be
> infringed by this small, and to my thinking, "obvious to one
> skilled in the art," snippet of code.

If my memory serves right, and I am not sure (where is Greg
Aharonian when we need him :-) :-) Mark Williams holds the
patent on the idea of converting to a common canonical format as
a solution for big-endian to little-endian conversion. But it
was a while ago and may have expired. I heard about it in the
context of actual litigation, so it is not just a paper patent!

> If it does infringe, I shudder to think
> what other infringements might be buried in the hundreds of
> thousands of lines of code I've written over 41 hears of
> 'practicing the art.

Yes, indeed, and that is why software patents are so worrisome.
In some cases you cannot avoid infringing however much diligence
you put into avoiding infringement, because at some stages in
the process the patent can still be confidential, yet still
protected retroactively.

Bob Duff asked me in a private email how come I was so insistent
on enforcing patents. But that's a misintepretation of my
position, my concern is more that people should be aware of the
threat that software patents pose to innovation and advancement
of science (phrase chosen intentionally to echo the commerce
clause). This is of course a bit off topic for comp.lang.ada,
so probably followups should go to one of the many groups that
discuss software patents. Sorry to drift off topic!




Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Decoding an octet stream

[Robert Dewar]

In article <822o4d$ehh$1@birch.prod.itd.earthlink.net>,
  "David C. Hoos, Sr." <david.c.hoos.sr@ada95.com> wrote:
> But, from my previous employment with a company that was
> fanatic about patenting everything in sight, and the education
> I received in their attempts to obtain a patent on one of my
> electronic component designs, one principle that seems
> applicable here is that what is "obvious to one skilled in the
> art" is not patentable.

You would be surprised how difficult it can be to prove that
something is obvious. In particular, there tends to be an
assumption that if there is no prior art, then how can it be
so obvious. Case law would surprise you here!

I quite agree this is indeed obvious :-)

> Nevertheless, I am eager to learn what patent might be
> infringed by this small, and to my thinking, "obvious to one
> skilled in the art," snippet of code.

If my memory serves right, and I am not sure (where is Greg
Aharonian when we need him :-) :-) Mark Williams holds the
patent on the idea of converting to a common canonical format as
a solution for big-endian to little-endian conversion. But it
was a while ago and may have expired. I heard about it in the
context of actual litigation, so it is not just a paper patent!

> If it does infringe, I shudder to think
> what other infringements might be buried in the hundreds of
> thousands of lines of code I've written over 41 hears of
> 'practicing the art.

Yes, indeed, and that is why software patents are so worrisome.
In some cases you cannot avoid infringing however much diligence
you put into avoiding infringement, because at some stages in
the process the patent can still be confidential, yet still
protected retroactively.

Bob Duff asked me in a private email how come I was so insistent
on enforcing patents. But that's a misintepretation of my
position, my concern is more that people should be aware of the
threat that software patents pose to innovation and advancement
of science (phrase chosen intentionally to echo the commerce
clause). This is of course a bit off topic for comp.lang.ada,
so probably followups should go to one of the many groups that
discuss software patents. Sorry to drift off topic!




Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Decoding an octet stream

[Kenneth Almquist]

kilgallen@eisner.decus.org (Larry Kilgallen) wrote:
> That abstract could also be used to describe ASN.1 BER encoding.
>
> Does the detailed description indicate what part is novel ?

The detailed description can be obtained from the USPTO web site [1].

The patent covers binary data stored on secondary storage devices on
systems running a portable operating system such as UNIX.  According
to the patent, the prior art consists of writing conversion programs
for every pair of CPU architectures, which must be run when data is
moved from one system to another when the systems have different CPU
architectures.  The allegedly novel idea is to write the data in a
cannonical format, making it unnecessary to run conversion programs
when moving files or file systems.
Kenneth Almquist


[1] The URL is <http://164.195.100.11/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1='4,956,809'.WKU.&OS=PN/4,956,809&RS=PN/4,956,809>

Re: Decoding an octet stream

[Robert Dewar]

In article <81u247$kc3$1@hobbes2.crc.com>,
  "David C. Hoos, Sr." <david.c.hoos.sr@ada95.com> wrote:
> Here's a package I use for just that purpose.  All two- and
four-byte
> scalar types used in network packets have their 'read and
'write
> attributes overridden by instances of these generic
procedures.

David, doesn't this infringe on the patent, or has 17
years gone by now (I have not kept track, the patent holder
is I believe Mark Williams).


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Decoding an octet stream

[Geoff Bull]

Robert Dewar wrote:
> 
> In article <81u247$kc3$1@hobbes2.crc.com>,
>   "David C. Hoos, Sr." <david.c.hoos.sr@ada95.com> wrote:
> > Here's a package I use for just that purpose.  All two- and
> four-byte
> > scalar types used in network packets have their 'read and
> 'write
> > attributes overridden by instances of these generic
> procedures.
> 
> David, doesn't this infringe on the patent, or has 17
> years gone by now (I have not kept track, the patent holder
> is I believe Mark Williams).
> 
What patent? (searching for in/williams gets > 7000 hits!)
I guess a patent number is a bit much to expect, 
but can you provide some keywords to search for,
or say which aspects of David's package may infringe?

Also, don't patents now expire 20 years from the filing date
rather than 17 years from the grant date?

Re: Decoding an octet stream

[Florian Weimer]

swhalen@netcom.com writes:

> I'll try to supress my disgust at how far the patent process
> has strayed from reality in the few years you've not been paying
> attention, but suffice to say our Patent Office has no clue as
> to what consitutes "prior art" or is "obvious" (at least in the
> software field). 

RFC 951 (the BOOTP protocol) mentions the term `standard network byte
order' as early as in 1985.  Of course, ntohl() and friends are just
another example of prior art.  According to Stevens' `UNIX Network
Programming', they already appeared in the VAX implementation of 4.2BSD
for the first time -- in 1983.  The Patent Office obviously didn't check
the prior art references of the patent application: the NFS documentation
is explicitly mentioned, and the XDR specification (RFC 1014, Jun 1987)
is more elaborated and deals with the same issues.  (And Sun considered
it to be their intellectual property afterwards, as it seems. ;)

BTW: The thread drifted quite far away from its original subject.
Perhaps I may ask again: Is it reasonable to assume that
Storage_Element'Size equals 8 (although the standard doesn't
require this, of course)?  And, looking at David's code, does
System.Default_Bit_Order really reflect the byte-ordering?

Re: Decoding an octet stream

[Robert Dewar]

In article <3845F5DB.4535A4BF@research.canon.com.au>,
  Geoff Bull <geoff@research.canon.com.au> wrote:
> If you can produce evidence of prior art, a patent is
> invalid.

Yes, that's true, but the mistake people often make is to assume
that prior art means something informal, like "known before",
but it is much more complex and delicate, there are many
litigated cases, where one would think that there was clearly
prior art, in that lots of people knew about it and used it
publicly, but still it does not meet the legal qualification
as prior art.

> This particular patent covers an idea present
> in Sun's XDR. As you can see from the following, XDR
> dates back to 1986, so it seems "the patent" (not being
> filed until 1988) is invalid.

Many patents that seem invalid to lay people who do not know
patent case law well turn out to be valid in legal terms, or
at least valid enough to extract settlements.

P.S. Once again, I ask where is Greg, now that we are discussing
something he really knows.

I still find this off topic for Ada, but I hesitate to set
followups to a more appropriate group, since I suspect that most
of the people contributing won't know where to go :-)


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Decoding an octet stream

[Robert Dewar]

In article <87bt8a2uvr.fsf@deneb.cygnus.argh.org>,
  " "@deneb.cygnus.argh.org (Florian Weimer) wrote:
> Perhaps I may ask again: Is it reasonable to assume that
> Storage_Element'Size equals 8 (although the standard doesn't
> require this, of course)?  And, looking at David's code, does
> System.Default_Bit_Order really reflect the byte-ordering?

System.Default_Bit_Order has nothing whatsoever to do with
byte ordering, and changing it does not affect byte ordering.
This is a common misconception. Of course usually bit order
and byte order should be the same or you get into trouble
(this means incidentally that if you change it from the
default, you are definitely likely to get into trouble :-)

As to whether it is reasonable to assume 8, obviously this is
not true of all machines, e.g. I assume it is 32 on the SHARC,
and it is 24 on the original Intermetrics validation.

But for most normal machines it will be 8.



Sent via Deja.com http://www.deja.com/
Before you buy.

Stupid patent tricks (was: Decoding an octet stream)

[Ted Dennison]

In article <3845FE4E.E54C9EEE@research.canon.com.au>,
  Geoff Bull <geoff@research.canon.com.au> wrote:
> Kenneth Almquist wrote:
> >
> > The allegedly novel idea is to write the data in a
> > cannonical format, making it unnecessary to run conversion programs
> > when moving files or file systems.
>
> Not quite, as that would involve magic!
> I read it that the patent claims as novel the idea of
> transmitting data in a canonical format, so that the
> sender doesn't need to know the binary representation
> required by the receiver.
>
> This patent would cover any program that, for example,
> exchanges data in standard "network" order.
>
> As I said, I think XDR predates it, can anybody verify that?

The first edition ISO ASN.1 standard I have at my desk is dated 1987,
which places it 3 years before the patent was supposedly granted. (ISO
8824:1987(E) and 8825:1987(E))

--
T.E.D.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Decoding an octet stream

[Ted Dennison]

In article <87bt8a2uvr.fsf@deneb.cygnus.argh.org>,
  " "@deneb.cygnus.argh.org (Florian Weimer) wrote:
> swhalen@netcom.com writes:

> Perhaps I may ask again: Is it reasonable to assume that
> Storage_Element'Size equals 8 (although the standard doesn't
> require this, of course)?  And, looking at David's code, does

I don't. My code figures it out by doing the following:
   Bytes_Per_Element : constant := (Ada.Streams.Stream_Element'Size + 7)
/ 8;


It only really comes up when you need to convert between stream elements
and bytes for some reason though. I suppose if you are writing your own
'Write routine using Unchecked_Conversion instead of other 'Write's it
also would be an issue. Then you would need to do something
like this ("Instance" is the type you are converting):

   Bytes_Per_Element  : constant := (Ada.Streams.Stream_Element'Size +
7) / 8;
   Bytes_Per_Instance : constant Natural := (Instance'Size + 7) / 8;
   Elements_Per_Instance : constant Ada.Streams.Stream_Element_Offset :=
     Ada.Streams.Stream_Element_Offset(
       (Bytes_Per_Instance + (Bytes_Per_Element - 1)) /
Bytes_Per_Element);
   subtype Instance_Array is Ada.Streams.Stream_Element_Array (1 ..
Elements_Per_Instance);

   function From_Instance is new Unchecked_Conversion
     (Source => Instance,
      Target => Instance_Array);

   function To_Instance is new Unchecked_Conversion
     (Source => Instance_Array,
      Target => Instance);


Otherwise you will be working entirely in stream_element_array's anyway.

--
T.E.D.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Decoding an octet stream

[Lutz Donnerhacke]

* Geoff Bull wrote:
>Florian Weimer wrote:
>> Perhaps I may ask again: Is it reasonable to assume that
>> Storage_Element'Size equals 8 (although the standard doesn't
>> require this, of course)?  
>
>I would think this is the equivalent of assuming that a 
>C char is 8 bits. Not strictly true, but a perfectly
>reasonable thing to do, so long as you are aware of the
>consequences.

A DSP in the next labor has Storage_Element'Size = 32.
sizeof(char) is required by the C standard to be equal to one every time.
So we have (for this compiler) sizeof(char) == sizeof(short) == sizeof(int)
== sizeof(long) == 1.

Re: Decoding an octet stream

[swhalen]

Geoff Bull <geoff@research.canon.com.au> wrote:
: If you can produce evidence of prior art, a patent is
: invalid. This particular patent covers an idea present
: in Sun's XDR. As you can see from the following, XDR
: dates back to 1986, so it seems "the patent" (not being
: filed until 1988) is invalid. Does anybody know when
: XDR actually became public knowledge?

...

: I still don't understand what constitutes "obvious" in
: the patent law sense, but, at least in retrospect, the
: Mark Williams patent is obvious.

: Cheers
: Geoff

(standard disclaimer: I Am Not a Lawyer, etc.)

Part of the problem is that it doesn't matter that _I_ know that this
is prior art and/or obvious. Only if I was sued by the patent holder
(or some other way got myself into court with lawyers and the whole
bit), would I have "standing" to _force_ the Patent Office to "listen"
to why I thought this particular application was obvious / prior art
...

In this case even though the general technique of creating a common
intermediate data format to reduce conversion hassles was done (even
by me!) as far back as the '70's, this patent was granted in the
context of "operating systems".

One would have to prove to the Patent Office that it was "obvious" to
extend such device / context independent data formats to operating
systems, and I'd have to prove what I'd done and when (I doubt I could
find the old code now, etc...).

This problem would go away if the Patent Office would take "our" word
for it, and we could just write in say "hey, kill that Patent, I did
that back <whenever> ...".  Unfortunately (but understandably) you have
to "prove" what you say, and some of what is getting patented now is
so obvious that nobody would have bothered to write papers about it or
otherwise document "it", because "it" was just a standard part of the
"art" of systems design or programming "back then".

The real problem is that these things get patented in the first place.
The Patent Office just doesn't have enough of the right kind of 
people examining these applications (and companies are patenting
everything in site as a defensive legal strategy).

Steve 

-- 
{===--------------------------------------------------------------===}
                Steve Whalen     swhalen@netcom.com
{===--------------------------------------------------------------===}

Re: Decoding an octet stream

[Larry Kilgallen]

In article <825g04$qri$1@nntp9.atl.mindspring.net>, swhalen@netcom.com writes:

> Part of the problem is that it doesn't matter that _I_ know that this
> is prior art and/or obvious. Only if I was sued by the patent holder
> (or some other way got myself into court with lawyers and the whole
> bit), would I have "standing" to _force_ the Patent Office to "listen"
> to why I thought this particular application was obvious / prior art
> ...

But when you do get called into court you merely have to prove there
is prior art, not that the prior art you cite is the exact prior art
you considered when you used the technique.

I recall a newspaper ad searching for something like "prior art"
regarding a lawsuit over the song "Let's Go" by the Routers. The
lawyers in question were looking for people who knew of a certain
rhythmic hand-clap and song being used by cheerleaders before year
X, where the rhythm was:

	. .   ...   ....   oo

and the cogniscenti will recognize that the dots above are handclaps
whereas the "oo" in the recorded version are the words "let's go",
and the "prior art" in this copyright case might presumably use
the name of a team or some other slogan for the "oo".

Since then, Al Gore has invented the Internet, so asking others for
evidence of prior art is cheaper than placing newspaper ads.

Larry Kilgallen

Re: Decoding an octet stream

[tmoran]

> Storage_Element'Size equals 8 (although the standard doesn't
  On a related note, last spring I had occasion to compare the
sizes as given by 8*stream_element_count(TYPE) vs TYPE'size of
a bunch of objects in a couple of (Windows-targeted) compilers.
About 30% of the time the two size measures disagreed.  The
compilers did not always agree with each other, either as to
when the two size measures disagreed, or what the size values
were when they disagreed.  These were compiler-default sizes,
no rep clauses or pragmas.

Re: Decoding an octet stream

[Geoff Bull]

swhalen@netcom.com wrote:
> From the U.S. Patent Office server (http://www.uspto.gov/):
> 
> United States Patent 4,956,809
> George , et al. September 11, 1990
> 
> Method for canonical ordering of binary data for
> portable operating systems
> Assignee: Mark Williams Company (Chicago, IL)
> Filed:    December 29, 1988

> our Patent Office has no clue as to what consitutes
> "prior art" or is "obvious" (at least in the software 
> field).
> 
> Many patents have been issued in the last few years
> that have been used widely in the past and/or were
> obvious to me many years ago, and I've only been
> programming for about 30 years...

If you can produce evidence of prior art, a patent is
invalid. This particular patent covers an idea present
in Sun's XDR. As you can see from the following, XDR
dates back to 1986, so it seems "the patent" (not being
filed until 1988) is invalid. Does anybody know when
XDR actually became public knowledge?

From /usr/include/rpc/xdr.h :

/*
 * Copyright (c) 1986 - 1991, 1994 by Sun Microsystems, Inc.
 * All rights reserved.
 */

/*
 * xdr.h, External Data Representation Serialization Routines.
 *
 */

I still don't understand what constitutes "obvious" in
the patent law sense, but, at least in retrospect, the
Mark Williams patent is obvious.

Cheers
Geoff

Re: Decoding an octet stream

[Geoff Bull]

Kenneth Almquist wrote:
> 
> The allegedly novel idea is to write the data in a
> cannonical format, making it unnecessary to run conversion programs
> when moving files or file systems.

Not quite, as that would involve magic!
I read it that the patent claims as novel the idea of
transmitting data in a canonical format, so that the
sender doesn't need to know the binary representation
required by the receiver.

This patent would cover any program that, for example,
exchanges data in standard "network" order.

As I said, I think XDR predates it, can anybody verify that?

This patent illustrates the (ridiculous?) need to do patent
searches for *everything*. Unfortuneately, I couldn't find
this patent even after Robert gave me the name "Mark Williams".
(I thought MW would be the inventor, and not the name of
the company the patent was assigned to :-( ). And to think,
I get paid to do patent searching!

Geoff

Re: Decoding an octet stream

[Geoff Bull]

Florian Weimer wrote:
> 
> Perhaps I may ask again: Is it reasonable to assume that
> Storage_Element'Size equals 8 (although the standard doesn't
> require this, of course)?  

I would think this is the equivalent of assuming that a 
C char is 8 bits. Not strictly true, but a perfectly
reasonable thing to do, so long as you are aware of the
consequences.

>And, looking at David's code, does
> System.Default_Bit_Order really reflect the byte-ordering?

Look in the reference manual!
When the concept of byte order has any meaning, 
the answer is yes.

13.5.3 Bit Ordering
(5)
     If Word_Size = Storage_Unit, the default bit ordering is
implementation defined. If
     Word_Size > Storage_Unit, the default bit ordering is the same as
the ordering of storage
     elements in a word, when interpreted as an integer

Re: Decoding an octet stream

[swhalen]

Larry Kilgallen <kilgallen@eisner.decus.org> wrote:

: But when you do get called into court you merely have to prove there
: is prior art, not that the prior art you cite is the exact prior art
: you considered when you used the technique.

...

As Robert mentioned in another post, in technical areas you have to
"prove" in a legal sense, "when" the prior art existed, that what you
say is prior art is in fact the the "same" as what is patented (or an
obvious extension), etc. The proof requirements for "prior art" and
"obviousness" is quite hard to do in software, because software is
generally not a well documented field compared to many.

One reason so many stupid patents are being granted is that much of
the prior art is "documented" only in the source code of old software
(often proprietary) that is not accessable to the Patent Office.

Steve

-- 
{===--------------------------------------------------------------===}
                Steve Whalen     swhalen@netcom.com
{===--------------------------------------------------------------===}

Re: Decoding an octet stream

[Geoff Bull]

Larry Kilgallen wrote:
> 
> Since then, Al Gore has invented the Internet, so asking others for
> evidence of prior art is cheaper than placing newspaper ads.
> 
Not always!
I have been told of cases where people found via internet want $$$$
before they will tell what they know.
Still, a few hundred bucks is much better than triple damages.

Re: Decoding an octet stream

[Robert Dewar]

In article <87puwsmizb.fsf@deneb.cygnus.argh.org>,
  " "@deneb.cygnus.argh.org (Florian Weimer) wrote:
> "David C. Hoos, Sr." <david.c.hoos.sr@ada95.com> writes:
>
> >       if System.Default_Bit_Order = System.Low_Order_First
then
> >          Swap (The_Bytes);
> >       end if;
>
> Does this really work?  I thought that
System.Default_Bit_Order
> hasn't got to do anything with octet ordering issues (aka
endianess).
> After all, there are more than just two methods of combining
four octets
> to a 32 bit integer (for example).

Well yes, but as we all know there are only two methods worth
bothering about. And in practice bit ordering and byte ordering
have to be the same, otherwise you get non-contiguous data
fields (this is why changing the default on bit_order, which
does NOT result in changing the byte order, is highly dubious
on a byte addressed machine, and hence not required to be
implemented).

In the latest version of GNAT we allow the non-default bit order
to be specified, but we insist that all record representation
clauses for such a record either lie within a single byte, or
correspond to an integral number of bytes (in the latter case
we warn that the byte order will NOT be modified).




>


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Decoding an octet stream

[Robert Dewar]

In article <827a95$4ti$1@nntp3.atl.mindspring.net>,
  swhalen@netcom.com wrote:
> The proof requirements for "prior art" and
> "obviousness" is quite hard to do in software, because
> software is generally not a well documented field compared to
> many.

Yes, indeed, prior art is only valid from a legal point of view
if publication requirements are met. It is not good enough to
say "everyone knows this, and point to programs in which it has
been used", your burden is to point to appropriate publication
of the ideas. There have been a number of litigated cases in
which of course there was prior art, and indeed lots and lots
of programmers were aware of the technique and it was widely
used, but no one actually "published" the idea in a legal
sense, until someone came along and patented the idea.

Sound horrible? yes indeed!


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Decoding an octet stream

[Geoff Bull]

swhalen@netcom.com wrote:

> One reason so many stupid patents are being granted is that much of
> the prior art is "documented" only in the source code of old software
> (often proprietary) that is not accessable to the Patent Office.

Another reason is that some companies hand out quotas, e.g. 5
patents per engineer per year.

Re: Decoding an octet stream

[Robert Dewar]

In article <3847C033.364CEB11@acenet.com.au>,
  Geoff Bull <gbull@acenet.com.au> wrote:
> Another reason is that some companies hand out quotas, e.g. 5
> patents per engineer per year.

That's an excuse for a large number of patent *applications*
it is NOT an excuse for a large number of patents granted!!


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Decoding an octet stream

[Kenneth Almquist]

Geoff Bull <geoff@research.canon.com.au> wrote:
> Kenneth Almquist wrote:
>> 
>> The allegedly novel idea is to write the data in a
>> cannonical format, making it unnecessary to run conversion programs
>> when moving files or file systems.
>
> Not quite, as that would involve magic!

No magic.  Conversion code is still required, but it is executed
every time you read or write the data from/to secondary storage.
It is not executed when you move the secondary storage media from
one system to another.

> I read it that the patent claims as novel the idea of
> transmitting data in a canonical format, so that the
> sender doesn't need to know the binary representation
> required by the receiver.

On rereading the patent, I have to agree with your reading.  The
description talks about files and file systems, which makes it appear
that the authors were primarily thinking of data stored on hard disks,
but in certain places the language is general enough ("auxiliary
storage or communications", "data source", "data destination") that
network communications would be covered.

> This patent would cover any program that, for example,
> exchanges data in standard "network" order.
>
> As I said, I think XDR predates it, can anybody verify that?

I don't know what the relevant date is, because the patent is dated
1990, but is a "continuation" (whatever that is) of a 1986 patent
application, which is in turn a "continuation" of an abandoned 1982
patent application.  In any case, using "network order" when transmitting
data of a network has been around almost as long as networks have.

The patent comes closer to being original when applying to data files,
but I think that the Common Object File Format (COFF) is prior art.
COFF was in use prior to 1986, but I'm not sure if it was around in
1982.  COFF is a format for UNIX files containing machine code, and
machine code is of course hardware dependent.  However, all the other
binary data in these files is stored in a machine-independent manner.
In addition, the library routines developed for processing COFF files
were placed in a library (libld.a), and as I recall the documentation
specificly pointed out that these would be useful for other applications
that wanted to write other types of machine-independent binary files.
Thus we have (1) data in a cannonical format, (2) stored on secondary
storage devices, and (3) used on UNIX, which is a UNIX-like operating
system.
				Kenneth Almquist

Re: Decoding an octet stream

[Ed Falis]

"Richard D Riehle" <laoXhai@ix.netcom.com> wrote in message

>The original
> phrase, "Al Gore rhythm," was clearly the source for our cherished
> computer argot, "algorithm."

You know, I first noticed while in an odd state of consciousness in 1971,
that life was a bit like a cartoon.  For some reason, it seems to have kept
getting more like one since then.  I think this thread fits ;-)

- Ed

Re: Decoding an octet stream

[Richard D Riehle]

In article <1999Dec2.081944.1@eisner>,
	kilgallen@eisner.decus.org (Larry Kilgallen) wrote:

>Since then, Al Gore has invented the Internet, so asking others for
>evidence of prior art is cheaper than placing newspaper ads.

Actually, we all know, even Mr. Gore knows, that his claims were
a bit inflated.  However, it should be obvious to everyone that
that the word "algorithm" derives from the Vice-president's skill
on the dance floor combined with his technical acumen.  The original
phrase, "Al Gore rhythm," was clearly the source for our cherished
computer argot, "algorithm."

Richard Riehle
http://www.adaworks.com 
 

Re: Decoding an octet stream

[Ted Dennison]

In article <FMCF6y.K5@sd.aonix.com>,
  "Ed Falis" <falis@ma.aonix.com> wrote:
>
> "Richard D Riehle" <laoXhai@ix.netcom.com> wrote in message
>
> >The original
> > phrase, "Al Gore rhythm," was clearly the source for our cherished
> > computer argot, "algorithm."
>
> You know, I first noticed while in an odd state of consciousness in
> 1971, that life was a bit like a cartoon.  For some reason, it seems
>  to have kept getting more like one since then.  I think this thread

I just hope Porky Pig comes out and ends this thread before it becomes
even more of a groaner. :-)

--
T.E.D.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Decoding an octet stream

[Stefan Skoglund]

Robert Dewar wrote:
> Yes, indeed, and that is why software patents are so worrisome.
> In some cases you cannot avoid infringing however much diligence
> you put into avoiding infringement, because at some stages in
> the process the patent can still be confidential, yet still
> protected retroactively.

A far bit of the patents gotten today by big corporations is simply
insurance against litigation. MS and IBM striked a deal where
IBM and MS will have access each other patents for a pretty long time.

If you don't have the patents you could be toast which i think
contradicts
against one of the main reasons behind patents.

> position, my concern is more that people should be aware of the
> threat that software patents pose to innovation and advancement
> of science (phrase chosen intentionally to echo the commerce
> clause). This is of course a bit off topic for comp.lang.ada,
> so probably followups should go to one of the many groups that
> discuss software patents. Sorry to drift off topic!

You aren't joking. Last year we had a small thing in the papers about
not so rich swedish institutions who were worried about their
abilities to continue doing state-funded research (usage of some patent
in research could be an patent infringement and).

That small instituion was Karolinska institutet.

Numeric types

[Mario Amado Alves]

The manual defines "numeric types" as the set of integer and real types
(cf. e.g. 3.5).

Now, is it a codeable type, viz. is it possible to have a generic formal
parameter of numeric type, meaning inheriting all numeric operations ("+", 
"*", ...)? E.g.:

  generic
    type Numeric_Type is ...; -- what here?
  package Blob is
    -- ...
  end Blob;

  package body Blob is
    -- code using numeric operations ("+", "*", etc.), e.g.:
    function Blib(A, B, C: Numeric_Type) return Numeric_Type is
    begin
      return(A + B * C);      
    end Blib;
  end Blob;

Is this possible to code properly? And how would we write "zero" in this
idiom (or any other literal for that matter)? It must be a commonality of
"0" and "0.0". This would perhaps work:

  function Zero return Numeric_Type is
  begin
    return(Numeric_Type'Value("0"));
  exception
    when others =>
      return(Numeric_Type'Value("0.0"));
  end Zero;

but it sounds like a dirty trick. An attribute 'Zero would be nice...

But I am afraid the idiom is just not possible. Please confirm. Perhaps
with class wide programming... I will have to go through Chapter 12 of
Cohen's bookin once more; perhaps I will be able to answer my onw questions
before the end of the year. But from the class hierachy of the types
involved, viz:

    scalar
       discrete
          integer
          ...
       real
       ...

I think it cannot be done. A numeric class should have the interset
fo integer and real operations but leaving out some discrete operations
like 'Pos and 'Val. The manual itself warns:

"The classes ``numeric'' and ``nonlimited'' represent other classification 
dimensions and do not fit into the above strictly hierarchical picture. "
(3.2)

But what "classes" are exactly refered to here? Numeric_IO?

Thanks in advance for any suggestions.

| |,| | | |RuaFranciscoTaborda24RcD 2815-249CharnecaCaparica 351+212976751
|M|A|R|I|O|                                                  mob 939354005
|A|M|A|D|O|DepartmentoDeInformaticaFCT/UNL 2825-114 Caparica 351+212958536
|A|L|V|E|S|                                                  fax 212948541
| | | | | |                 maa@di.fct.unl.pt                FCT 212948300



 Sent via Deja.com http://www.deja.com/
 Before you buy.

Re: Numeric types

[Tucker Taft]

Mario Amado Alves wrote:
> 
> The manual defines "numeric types" as the set of integer and real types
> (cf. e.g. 3.5).
> 
> Now, is it a codeable type, viz. is it possible to have a generic formal
> parameter of numeric type, meaning inheriting all numeric operations ("+",
> "*", ...)? E.g.:
> 
>   generic
>     type Numeric_Type is ...; -- what here?

generic
  type Numeric_Type is private;
  with function "+"(Left, Right : Numeric_Type) return Numeric_Type is <>;
  with function "*"(...
  ...
  Zero : in Numeric_Type;
package blob is ...
 
> Is this possible to code properly? And how would we write "zero" in this
> idiom (or any other literal for that matter)? It must be a commonality of
> "0" and "0.0". This would perhaps work:
> 
>   function Zero return Numeric_Type is
>   begin
>     return(Numeric_Type'Value("0"));
>   exception
>     when others =>
>       return(Numeric_Type'Value("0.0"));
>   end Zero;
> 
> but it sounds like a dirty trick. An attribute 'Zero would be nice...

Just make zero a generic formal parameter.
You could also create a generic "signature" for a numeric type,
and then take any instantiation of that signature.  E.g.:

   generic
       type Num is private;
       with function "+"(...   -- as above
       Zero : in Num;
       One : in Num;
       with function Image(N : Num) return String;
       with function Value(S : String) return Num;
   package Numeric_Signature is end;

   generic
       with package Num_Pkg is new Numeric_Signature(<>);
   package Blob is
       use Num_Pkg;
       ...

   package Integer_Num is new Numeric_Signature(Integer, Zero => 0, One => 1,
     Integer'Image, Integer'Value);

   package Integer_Blob is new Blob(Num_Pkg => Integer_Num);

> But I am afraid the idiom is just not possible. Please confirm. Perhaps
> with class wide programming... 

Generics are pretty powerful.  The concept of a generic
signature can help reduce the number of parameters
passed to each generic.

> ...
> Thanks in advance for any suggestions.
> 
> | |,| | | |RuaFranciscoTaborda24RcD 2815-249CharnecaCaparica 351+212976751
> |M|A|R|I|O|                                                  mob 939354005
> |A|M|A|D|O|DepartmentoDeInformaticaFCT/UNL 2825-114 Caparica 351+212958536
> |A|L|V|E|S|                                                  fax 212948541
> | | | | | |                 maa@di.fct.unl.pt                FCT 212948300
-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA

Re: Decoding an octet stream

[Brian Rogoff]

On Wed, 8 Dec 1999, Robert Dewar wrote:
> In article <82hgq5$p7p$1@nntp4.atl.mindspring.net>,
>   Richard D Riehle <laoXhai@ix.netcom.com> wrote:
> > was clearly the source for our cherished
> > computer argot, "algorithm."
> 
> I trust everyone knows that the word algorithm is
> an ignorant back formation from the proper arabic
> derived word (algorism), influenced (inappropriately)
> by the greek "arithmos". A very annoying bit of cultural
> myopia.

Actually, Richard's joke is even closer, since algorithm does come from 
someone's name; if I'm not mistaken a Persian mathematician named
al-Khuwarizmi whose name was Latinized to algorismus. 

-- Brian

Re: Decoding an octet stream

[Robert Dewar]

In article <82hgq5$p7p$1@nntp4.atl.mindspring.net>,
  Richard D Riehle <laoXhai@ix.netcom.com> wrote:
> was clearly the source for our cherished
> computer argot, "algorithm."


I trust everyone knows that the word algorithm is
an ignorant back formation from the proper arabic
derived word (algorism), influenced (inappropriately)
by the greek "arithmos". A very annoying bit of cultural
myopia.

Richard's joke still works nicely

Al-Gore-ism

  idiotic claim, as in someone claiming to have invented the
  internet who did not even know of its existence when it first
  appeared

:-)



Sent via Deja.com http://www.deja.com/
Before you buy.