| 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 "size" 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 "displacement"
|
|
|
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 |
-> 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 |
"smaller" 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)) >= 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 |
-> 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 |
-> 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 |
-> 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> <= 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 © 1998.</I></P>
|
|
|
209 |
</BODY>
|
|
|
210 |
</HTML>
|