Re: [Gnash-dev] Alignment in AMF data

[John Gilmore]

At Cygnus, we went through all the contortions of byte-swapping and
alignment when writing the BFD library that reads and writes object
files (for gas, gdb, binutils, etc).  Everyone had an opinion and the
bikeshed was many-colored.  Ultimately I did a series of performance
tests and determined that it only cost us 1% performance to do it in a
straightforward, portable, maintainable, and verifiably correct way,
so we adopted that.  Here's my 2c toward how gnash "ought to" handle
this.

What makes this implementation straightforward is that the conversion
routines are all totally portable ANSI C; they are independent of the
host byte order and the host alignment constraints.  What makes it
verifiable is that it runs the *same* code on every host, regardless
of its byte order or alignment restrictions.  The code has no IFDEFs
about the host byte order.  If it runs on a little-endian host, it'll
run on a big-endian host.  All that the programmer needs to declare is
what byte order and alignment are used in the *external*
representation.  This costs <1% of program runtime, despite calling a
function for every field in every structure read or written, and
copying everything out into separate structures.

[Presumably if some of this code became performance hot-spots in
e.g. the linker, we could recode particular routines to make alignment
assumptions under #ifdef; inline the low-level functions; etc.  None
of them ever did become hot spots.]

We chose to make two C/C++ structs for each structure in the data: an
external one and an internal one.  The external one contained nothing
but chars and char arrays, and laid out the byte alignment of the
fields.  We determined that no available C compilers were inserting
padding into C structures consisting of nothing but chars; (otherwise
we'd have needed to treat it as a C array and subscript out the bytes
we wanted, which would be uglier and less maintainable.)  The internal
one contained convenient datatypes for use on the host, like ints.
These two structs might well be different sizes; the code doesn't
care.  We then wrote two small boilerplate routines, one to convert an
external struct to internal, the other to do the reverse.  The rest of
the code is written to allocate and use internal structures.

The code for converting external to internal structures calls
byte-swapping routines like bfd_getl32, which gets a little-endian
32-bit quantity, and returns it as a host "bfd_vma" (an integer type
of at least 32 bits):

  
http://sourceware.org/cgi-bin/cvsweb.cgi/~checkout~/src/bfd/libbfd.c?rev=1.49&content-type=text/plain&cvsroot=src

  bfd_vma
  bfd_getl32 (const void *p)
  {
    const bfd_byte *addr = p;
    unsigned long v;

    v = (unsigned long) addr[0];
    v |= (unsigned long) addr[1] << 8;
    v |= (unsigned long) addr[2] << 16;
    v |= (unsigned long) addr[3] << 24;
    return v;
  }

Here's declarations of all of the byte-swap routines:

  
http://sourceware.org/cgi-bin/cvsweb.cgi/~checkout~/src/bfd/bfd-in.h?rev=1.139&content-type=text/plain&cvsroot=src

  bfd_uint64_t bfd_getb64 (const void *);
  bfd_uint64_t bfd_getl64 (const void *);
  bfd_int64_t bfd_getb_signed_64 (const void *);
  bfd_int64_t bfd_getl_signed_64 (const void *);
  bfd_vma bfd_getb32 (const void *);
  bfd_vma bfd_getl32 (const void *);
  bfd_signed_vma bfd_getb_signed_32 (const void *);
  bfd_signed_vma bfd_getl_signed_32 (const void *);
  bfd_vma bfd_getb16 (const void *);
  bfd_vma bfd_getl16 (const void *);
  bfd_signed_vma bfd_getb_signed_16 (const void *);
  bfd_signed_vma bfd_getl_signed_16 (const void *);
  void bfd_putb64 (bfd_uint64_t, void *);
  void bfd_putl64 (bfd_uint64_t, void *);
  void bfd_putb32 (bfd_vma, void *);
  void bfd_putl32 (bfd_vma, void *);
  void bfd_putb16 (bfd_vma, void *);
  void bfd_putl16 (bfd_vma, void *);

(For Gnash, we'd need to add ones for IEEE floats; the object-file
formats that BFD uses never needed to process floating point data.
GDB had those routines, though!)

Each struct is processed by a pair of routines to "swap it in" from
external to internal representation, or to "swap it out".  These
routines *copy* the data from one format to the other.  These routines
need to know both the size and the byte order of the external
representation of each field.  They do not need to care about
alignment, because every access to an external datum is done
byte-by-byte by the lower level routines like bfd_getl32.  Example:

  
http://sourceware.org/cgi-bin/cvsweb.cgi/~checkout~/src/bfd/elfcode.h?rev=1.91&content-type=text/plain&cvsroot=src

  /* Translate an ELF section header table entry in external format into an
     ELF section header table entry in internal format.  */

  static void
  elf_swap_shdr_in (bfd *abfd,
                          const Elf_External_Shdr *src,
                                  Elf_Internal_Shdr *dst)
  {
    int signed_vma = get_elf_backend_data (abfd)->sign_extend_vma;

    dst->sh_name = H_GET_32 (abfd, src->sh_name);
    dst->sh_type = H_GET_32 (abfd, src->sh_type);
    dst->sh_flags = H_GET_WORD (abfd, src->sh_flags);
    if (signed_vma)
      dst->sh_addr = H_GET_SIGNED_WORD (abfd, src->sh_addr);
    else
      dst->sh_addr = H_GET_WORD (abfd, src->sh_addr);
    dst->sh_offset = H_GET_WORD (abfd, src->sh_offset);
    dst->sh_size = H_GET_WORD (abfd, src->sh_size);
    dst->sh_link = H_GET_32 (abfd, src->sh_link);
    dst->sh_info = H_GET_32 (abfd, src->sh_info);
    dst->sh_addralign = H_GET_WORD (abfd, src->sh_addralign);
    dst->sh_entsize = H_GET_WORD (abfd, src->sh_entsize);
    dst->bfd_section = NULL;
    dst->contents = NULL;
  }

In BFD, this code has additional complications, because it is included
twice, once to handle ELF32, and once to handle ELF64.  And it is also
invoked for ELF object file formats for different architectures, some
of which are big-endian and some of which are little-endian.
Ultimately, H_GET_32 calls bfd_getl32 or bfd_getb32 depending on
whether the headers of this architecture's ELF files are little- or
big-endian.  H_GET_WORD calls bfd_getl32 or bfd_getl64 (or the
corresponding big-endian versions) depending whether the headers of
this ELF file are ELF32 or ELF64.

Gnash would not need those additional levels of indirection; instead,
our swap-in routines could just call "getl32" directly on each 32-bit
quantity stored in little-endian format in the external
representation, and our swap-outs would call "putl32".

        John

PS: Since that code is now GPLv3 and ours is too, and it's all owned
by the FSF, we could directly steal the low-level byte swap routines
from the Binutils if we wanted.