Blame | Last modification | View Log | RSS feed
<!-- Crown Copyright (c) 1998 -->
<HTML>
<HEAD>
<TITLE>TDF expansions of offsets</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000FF" VLINK="#400080" ALINK="#FF0000">
<A NAME=S87>
<H1>TDF Guide, Issue 4.0 </H1>
<A HREF="guide15.html">
<H3>January 1998</H3>
<IMG SRC="../images/next.gif" ALT="next section"></A>
<A HREF="guide13.html">
<IMG SRC="../images/prev.gif" ALT="previous section"></A>
<A HREF="guide1.html"><IMG SRC="../images/top.gif" ALT="current document"></A>
<A HREF="../index.html"><IMG SRC="../images/home.gif" ALT="TenDRA home page">
</A>
<IMG SRC="../images/no_index.gif" ALT="document index"><P>
<HR>
<DL>
<DT><A HREF="#S88"><B>12.1 </B> - Bitfield offsets</A><DD>
</DL>
<HR>
<H1>12 <A NAME=0>TDF expansions of offsets</H1>
Consider the C structure defined by:<P>
<PRE>
<I>typedef struct{ int i; double d; char c;} mystruct;</I>
</PRE>
Given that sh_int, sh_char and sh_double are the SHAPEs for int, char
and double, the SHAPE of <I>mystruct</I> is constructed by:<P>
<PRE>
SH_mystruct = compound(S_c)
where:
S_c = offset_add(O_c, shape_offset(sh_char))
where:
O_c = offset_pad(alignment(sh_char), S_d)
where:
S_d = offset_add(O_d, shape_offset(sh_double))
where:
O_d = offset_pad(alignment(sh_double), S_i)
where<A NAME=footnote84 HREF="footnote.html#84">*</A>:
</PRE>
S_i = offset_add(O_i, shape_offset(sh_int)) and: O_i = offset_zero(alignment(sh_int))
Each of S_c, S_d and S_i gives the minimum "size" of the
space required to upto and including the field c, d and i respectively.
Each of O_c, O_d and O_i gives the OFFSET "displacement"
from a pointer to a <I>mystruct</I> required to select the fields
c, d and i respectively. The C program fragment:<P>
<PRE>
mystruct s;
.... s.d = 1.0; ...
</PRE>
would translate to something like:<P>
<PRE>
variable(empty, tag_s, make_value(compound(S_c)),
sequence( ...
assign(add_to_ptr(obtain_tag(tag_s), O_d), 1.0)
...
)
)
</PRE>
Each of the OFFSET expressions above are ideal candidates for tokenisation;
a producer would probably define tokens for each of them and use
exp_apply_token to expand them at each of their uses.<P>
From the definition, we find that:<P>
<PRE>
S_c = shape_offset(SH_mystruct)
i.e. an OFFSET(alignment(sh_int) xc8 alignment(sh_char) xc8 alignment(sh_double), {})
</PRE>
This would not be the OFFSET required to describe <I>sizeof(mystruct)
</I>in C, since this is defined to be the difference between successive
elements an array of <I>mystruct</I>s. The <I>sizeof</I> OFFSET would
have to pad S_c to the alignment of SH_mystruct:<P>
<PRE>
offset_pad(alignment(SH_mystruct), S_c)
</PRE>
This is the OFFSET that one would use to compute the displacement
of an element of an array of <I>mystruct</I>s using offset_mult with
the index.<P>
The most common use of OFFSETs is in add_to_ptr to compute the address
of a structure or array element. Looking again at its signature in
a slightly different form:<P>
<PRE>
<I> arg1</I>: EXP POINTER(<I>y </I><I>xc8 </I><I> A</I>)
<I> arg2</I>: EXP OFFSET(<I>y, z</I>)
-> EXP POINTER(<I>z</I>)
... for any ALIGNMENT <I>A</I>
</PRE>
one sees that <I>arg2</I> can measure an OFFSET from a value of a
"smaller" alignment than the value pointed at by <I>arg1</I>.
If <I>arg2</I> were O_d, for example, then <I>arg1</I> could be a
pointer to any structure of the form struct {int i, double d,...}
not just <I>mystruct</I>. The general principle is that an OFFSET
to a field constructed in this manner is independent of any fields
after it, corresponding to normal usage in both languages and machines.
A producer for a language which conflicts with this would have to
produce less obvious TDF, perhaps by re-ordering the fields, padding
the offsets by later alignments or taking maxima of the sizes of the
fields. <P>
<P>
<A NAME=S88>
<HR><H2>12.1. <A NAME=12>Bitfield offsets</H2>
Bitfield offsets are governed by rather stricter rules. In order to
extract or assign a bitfield, we have to find an integer variety which
entirely contains the bitfield. Suppose that we wished to extract
a bitfield by:<P>
<PRE>
bitfield_contents(v, p:POINTER(X), b:OFFSET(Y, B))
</PRE>
Y must be an alignment(I) where I is some integer SHAPE, contained
in X. Further, this has to be equivalent to:<P>
<PRE>
bitfield_contents(v, add_ptr(p, d:OFFSET(Y,Y)), b':OFFSET(Y, B))
</PRE>
for some d and b' such that:<P>
<PRE>
offset_pad(v, shape_offset(I)) >= b'
and
offset_add(offset_pad(v, offset_mult(d, sizeof(I)), b') = b
</PRE>
Clearly, we have a limitation on the length of bitfields to the maximum
integer variety available; in addition, we cannot have a bitfield
which overlaps two such varieties.<P>
The difficulties inherent in this may be illustrated by attempting
to construct an array of bitfields using the nof constructor. Assuming
a standard architecture, we find that we cannot usefully define an
object of SHAPE nof(N, bitfield(bfvar_bits(b, M))) without padding
this shape out to some integer variety which can contain M bits. In
addition, they can only be usefully indexed (using bitfield_contents)either
if M is some power of 2 or M*N is less than the length of the maximum
integer variety. Thus a producer must be sure that these conditions
hold if he is to generate and index this object simply. Even here
he is in some dificulty, since he does not know the representational
varieties of the integers available to him; also it is difficult for
him to ensure that the alignment of the entire array is in some sense
minimal. Similar difficulties occur with bitfields in structures -
they are not restricted to arrays.<P>
The solution to this conundrum in its full generality requires knowledge
of the available representational varieties. Particular languages
have restrictions which means that sub-optimal solutions will satisfy
its specification on the use of bitfields. For example, C is satisfied
with bitfields of maximum length 32 and simple alignment constraints.
However, for the general optimal solution, I can see no reasonable
alternative to the installer defining some tokens to produce bitfield
offsets which are guaranteed to obey the alignment rules and also
give optimal packing of fields and alignments of the total object
for the platform in question. I believe that three tokens are sufficient
to do this; these are analogous to the constructors offset_zero, offset_pad
and offset_mult with ordinary alignments and their signatures could
be: <P>
<PRE>
~Bitfield_offset_zero:
<I>n</I>: NAT
<I>issigned</I>: BOOL
-> EXP OFFSET(A, bfvar_bits(<I>issigned</I>, <I>n</I>))
Here the result is a zero offset to the bitfield with `minimum' integer variety alignment A.
</PRE>
<P>
<PRE>
~Bitfield_offset_pad:
<I>n</I>: NAT
<I>issigned</I>: BOOL
<I>sh</I>: SHAPE
-> EXP OFFSET(alignment(<I>sh</I>) xc8 A, bfvar_bits(<I>issigned</I>,
<I>n</I>))
Here the result is the shape_offset of <I>sh</I> padded with the `minimum' alignment A so that it can accomodate the bitfield. Note that this may involve padding
<I>sh</I> with the alignment of the maximum integer variety if there are not enough bits left at the end of
<I>sh.</I>
</PRE>
<P>
<PRE>
~Bitfield_offset_mult:
<I>n</I>: NAT
<I>issigned</I>: BOOL
<I>ind</I>: EXP INTEGER(v)
-> EXP OFFSET(A, bfvar_bits(<I>issigned</I>, <I>n</I>))
Here the result is an offset which gives the displacement of<I> ind</I><I>th
</I> element of an array of <I>n</I>-bit bitfields with `minimum' alignment A. Note that this will correspond to a normal multiplication only if
<I>n</I> is a power of 2 or <I>ind</I>*<I>n</I> <= length of the maximum integer variety.
</PRE>
<P>
These tokens can be expressed in TDF if the lengths of the available
varieties are known, i.e., they are installer defined
<A NAME=footnote85 HREF="footnote.html#85">*</A>. They ought to be
used in place of offset_zero, offset_pad and offset_mult whereever
the alignment or shape (required to construct a SHAPE or an argument
to the bitfield constructs) is a pure bitfield. The constructor nof
should never be used on a pure bitfield; instead it should be replaced
by:<P>
<PRE>
S = compound(~Bitfield_offset_mult(M, b, N))
</PRE>
to give a shape, S, representing an array of N M-bit bitfields. This
may not be just N*M bits; for example ~Bitfield_offset_mult may be
implemented to pack an array of 3-bit bitfields as 10 fields to a
32-bit word. In any case, one would expect that normal rules for offset
arithmetic are preserved, e.g.<P>
<PRE>
offset_add(~Bitfield_offset_pad(M, b, S), size(bitfield(bfvar_bits(b, N))) )
= ~Bitfield_offset_mult(M, b, N+1)
where size(X) = offset_pad(alignment(X), shape_offset(X))
</PRE>
<HR>
<P><I>Part of the <A HREF="../index.html">TenDRA Web</A>.<BR>Crown
Copyright © 1998.</I></P>
</BODY>
</HTML>