Subversion Repositories tendra.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 7u83 1 
<!-- Crown Copyright (c) 1998 -->
2 
<HTML>
3 
<HEAD>
4 
<TITLE>TDF expansions of offsets</TITLE>
5 
</HEAD>
6 
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000FF" VLINK="#400080" ALINK="#FF0000">
7 
<A NAME=S87>
8 
<H1>TDF Guide, Issue 4.0 </H1>
9 
<A HREF="guide15.html">
10 
<H3>January 1998</H3>
11 
<IMG SRC="../images/next.gif" ALT="next section"></A>
12 
<A HREF="guide13.html">
13 
<IMG SRC="../images/prev.gif" ALT="previous section"></A>
14 
<A HREF="guide1.html"><IMG SRC="../images/top.gif" ALT="current document"></A>
15 
<A HREF="../index.html"><IMG SRC="../images/home.gif" ALT="TenDRA home page">
16 
</A>
17 
<IMG SRC="../images/no_index.gif" ALT="document index"><P>
18 
<HR>
19 
<DL>
20 
<DT><A HREF="#S88"><B>12.1 </B> - Bitfield offsets</A><DD>
21 
</DL>
22 
<HR>
23 
<H1>12  <A NAME=0>TDF expansions of offsets</H1>
24 
Consider the C structure defined by:<P>
25 
<PRE>
26 
<I>typedef struct{ int i; double d; char c;} mystruct;</I>
27 
</PRE>
28 
Given that sh_int, sh_char and sh_double are the SHAPEs for int, char
29 
and double, the SHAPE of <I>mystruct</I> is constructed by:<P>
30 
<PRE>
31 
SH_mystruct = compound(S_c)
32 
where:
33 
S_c = offset_add(O_c, shape_offset(sh_char))
34 
where:
35 
O_c = offset_pad(alignment(sh_char), S_d)
36 
where:
37 
S_d = offset_add(O_d, shape_offset(sh_double))
38 
where:
39 
O_d = offset_pad(alignment(sh_double), S_i)
40 
where<A NAME=footnote84 HREF="footnote.html#84">*</A>:
41 
</PRE>
42 
S_i = offset_add(O_i, shape_offset(sh_int)) and: O_i = offset_zero(alignment(sh_int))
43 
 
44 
Each of S_c, S_d and S_i gives the minimum &quot;size&quot; of the
45 
space required to upto and including the field c, d and i respectively.
46 
Each of O_c, O_d and O_i gives the OFFSET &quot;displacement&quot;
47 
from a pointer to a <I>mystruct</I> required to select the fields
48 
c, d and i respectively. The C program fragment:<P>
49 
<PRE>
50 
mystruct s;
51 
.... s.d = 1.0; ...
52 
</PRE>
53 
would translate to something like:<P>
54 
<PRE>
55 
variable(empty, tag_s, make_value(compound(S_c)),
56 
	sequence( ...
57 
	 assign(add_to_ptr(obtain_tag(tag_s), O_d), 1.0)
58 
	 ...
59 
	)
60 
)
61 
 
62 
</PRE>
63 
Each of the OFFSET expressions above are ideal candidates for tokenisation;
64 
a producer would probably define tokens for each of them and use
65 
exp_apply_token to expand them at each of their uses.<P>
66 
From the definition, we find that:<P>
67 
<PRE>
68 
S_c = shape_offset(SH_mystruct)
69 
i.e. an OFFSET(alignment(sh_int) xc8  alignment(sh_char) xc8  alignment(sh_double), {})
70 
</PRE>
71 
This would not be the OFFSET required to describe <I>sizeof(mystruct)
72 
</I>in C, since this is defined to be the difference between successive
73 
elements an array of <I>mystruct</I>s. The <I>sizeof</I> OFFSET would
74 
have to pad S_c to the alignment of SH_mystruct:<P>
75 
<PRE>
76 
offset_pad(alignment(SH_mystruct), S_c)
77 
</PRE>
78 
This is the OFFSET that one would use to compute the displacement
79 
of an element of an array of <I>mystruct</I>s using offset_mult with
80 
the index.<P>
81 
The most common use of OFFSETs is in add_to_ptr to compute the address
82 
of a structure or array element. Looking again at its signature in
83 
a slightly different form:<P>
84 
<PRE>
85 
<I>	arg1</I>: 	EXP POINTER(<I>y </I><I>xc8 </I><I> A</I>)
86 
<I>	arg2</I>: 	EXP OFFSET(<I>y, z</I>)
87 
		   -&gt; EXP POINTER(<I>z</I>)
88 
	... for any ALIGNMENT <I>A</I>
89 
</PRE>
90 
one sees that <I>arg2</I> can measure an OFFSET from a value of a
91 
&quot;smaller&quot; alignment than the value pointed at by <I>arg1</I>.
92 
If <I>arg2</I> were O_d, for example, then <I>arg1</I> could be a
93 
pointer to any structure of the form struct {int i, double d,...}
94 
not just <I>mystruct</I>. The general principle is that an OFFSET
95 
to a field constructed in this manner is independent of any fields
96 
after it, corresponding to normal usage in both languages and machines.
97 
A producer for a language which conflicts with this would have to
98 
produce less obvious TDF, perhaps by re-ordering the fields, padding
99 
the offsets by later alignments or taking maxima of the sizes of the
100 
fields. <P>
101 
<P>
102 
<A NAME=S88>
103 
<HR><H2>12.1. <A NAME=12>Bitfield offsets</H2>
104 
Bitfield offsets are governed by rather stricter rules. In order to
105 
extract or assign a bitfield, we have to find an integer variety which
106 
entirely contains the bitfield. Suppose that we wished to extract
107 
a bitfield by:<P>
108 
<PRE>
109 
bitfield_contents(v, p:POINTER(X), b:OFFSET(Y, B))
110 
</PRE>
111 
Y must be an alignment(I) where I is some integer SHAPE, contained
112 
in X. Further, this has to be equivalent to:<P>
113 
<PRE>
114 
bitfield_contents(v, add_ptr(p, d:OFFSET(Y,Y)), b':OFFSET(Y, B))
115 
</PRE>
116 
for some d and b' such that:<P>
117 
<PRE>
118 
offset_pad(v, shape_offset(I)) &gt;= b'
119 
and
120 
offset_add(offset_pad(v, offset_mult(d, sizeof(I)), b') = b
121 
</PRE>
122 
Clearly, we have a limitation on the length of bitfields to the maximum
123 
integer variety available; in addition, we cannot have a bitfield
124 
which overlaps two such varieties.<P>
125 
The difficulties inherent in this may be illustrated by attempting
126 
to construct an array of bitfields using the nof constructor. Assuming
127 
a standard architecture, we find that we cannot usefully define an
128 
object of SHAPE nof(N, bitfield(bfvar_bits(b, M))) without padding
129 
this shape out to some integer variety which can contain M bits. In
130 
addition, they can only be usefully indexed (using bitfield_contents)either
131 
if M is some power of 2 or M*N is less than the length of the maximum
132 
integer variety. Thus a producer must be sure that these conditions
133 
hold if he is to generate and index this object simply. Even here
134 
he is in some dificulty, since he does not know the representational
135 
varieties of the integers available to him; also it is difficult for
136 
him to ensure that the alignment of the entire array is in some sense
137 
minimal. Similar difficulties occur with bitfields in structures -
138 
they are not restricted to arrays.<P>
139 
The solution to this conundrum in its full generality requires knowledge
140 
of the available representational varieties. Particular languages
141 
have restrictions which means that sub-optimal solutions will satisfy
142 
its specification on the use of bitfields. For example, C is satisfied
143 
with bitfields of maximum length 32 and simple alignment constraints.
144 
However, for the general optimal solution, I can see no reasonable
145 
alternative to the installer defining some tokens to produce bitfield
146 
offsets which are guaranteed to obey the alignment rules and also
147 
give optimal packing of fields and alignments of the total object
148 
for the platform in question. I believe that three tokens are sufficient
149 
to do this; these are analogous to the constructors offset_zero, offset_pad
150 
and offset_mult with ordinary alignments and their signatures could
151 
be: <P>
152 
<PRE>
153 
~Bitfield_offset_zero:
154 
	<I>n</I>:	NAT
155 
	<I>issigned</I>:	BOOL
156 
		   -&gt; EXP OFFSET(A, bfvar_bits(<I>issigned</I>, <I>n</I>))
157 
	Here the result is a zero offset to the bitfield with `minimum' integer variety alignment A.
158 
</PRE>
159 
<P>
160 
<PRE>
161 
~Bitfield_offset_pad:
162 
	<I>n</I>:	NAT
163 
	<I>issigned</I>:	BOOL
164 
	<I>sh</I>:	SHAPE
165 
		   -&gt; EXP OFFSET(alignment(<I>sh</I>) xc8  A, bfvar_bits(<I>issigned</I>,
166 
<I>n</I>))
167 
	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
168 
<I>sh</I> with the alignment of the maximum integer variety if there are not enough bits left at the end of
169 
<I>sh.</I>
170 
</PRE>
171 
<P>
172 
<PRE>
173 
~Bitfield_offset_mult:
174 
	<I>n</I>:	NAT
175 
	<I>issigned</I>:	BOOL
176 
	<I>ind</I>:	EXP INTEGER(v)
177 
		   -&gt; EXP OFFSET(A, bfvar_bits(<I>issigned</I>, <I>n</I>))
178 
	Here the result is an offset which gives the displacement of<I> ind</I><I>th
179 
</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
180 
<I>n</I> is a power of 2 or <I>ind</I>*<I>n</I> &lt;= length of the maximum integer variety.
181 
</PRE>
182 
<P>
183 
These tokens can be expressed in TDF if the lengths of the available
184 
varieties are known, i.e., they are installer defined
185 
<A NAME=footnote85 HREF="footnote.html#85">*</A>. They ought to be
186 
used in place of offset_zero, offset_pad and offset_mult whereever
187 
the alignment or shape (required to construct a SHAPE or an argument
188 
to the bitfield constructs) is a pure bitfield. The constructor nof
189 
should never be used on a pure bitfield; instead it should be replaced
190 
by:<P>
191 
<PRE>
192 
S = compound(~Bitfield_offset_mult(M, b, N))
193 
</PRE>
194 
to give a shape, S, representing an array of N M-bit bitfields. This
195 
may not be just N*M bits; for example ~Bitfield_offset_mult may be
196 
implemented to pack an array of 3-bit bitfields as 10 fields to a
197 
32-bit word. In any case, one would expect that normal rules for offset
198 
arithmetic are preserved, e.g.<P>
199 
<PRE>
200 
offset_add(~Bitfield_offset_pad(M, b, S), size(bitfield(bfvar_bits(b, N))) )
201 
   =  ~Bitfield_offset_mult(M, b, N+1)
202 
 
203 
where size(X) = offset_pad(alignment(X), shape_offset(X))
204 
 
205 
</PRE>
206 
<HR>
207 
<P><I>Part of the <A HREF="../index.html">TenDRA Web</A>.<BR>Crown
208 
Copyright &copy; 1998.</I></P>
209 
</BODY>
210 
</HTML>