Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed
A Public Domain Tool for producing TDF
-------------------------------------
1. Introduction
The basic idea is to produce the TDF bit encoding using language
constructions directly related to the TDF constructors given in the
specification document. These constructions have been produced
automatically from the document and so updating them in view of further
revisions of TDF is a relatively painless exercise.
There are macros for all of the non-primitive constructors with
names given by prefixing the constructor name with o_ ; eg to output the
EXP make_top, you simply call the macro o_make_top. A constructor with a
number of parameters will correspond to a macro with that number of
parameters. The expansion of the macro will check that each parameter
outputs the correct TDF SORT.
There are also procedures for outputing primitive SORTS; eg out_tdfbool(b)
outputs b as as a TDFBOOL. I have only provided output procedures
for primitive SORTs which have simple representations in C eg
out_tdfint32(x) outputs the 32 bit integer x as a TDFINT.
To give a flavour of the intended use of the tool, in order to produce
the TDF for an assignment, one does:
o_assign(LHS, RHS)
where LHS and RHS are pieces of code which will output the EXPs for the
source and destination of the assignment. For example, LHS for a simple
variable as destination could be:
o_obtain_tag(o_make_tag(out_tdfint32(A)))
where A is the number chosen by the compiler for the variable. Of course,
it is unlikely that a compiler would do this directly. LHS will usually be
some conditional code which might choose this expansion from its analysis
of the program being compiled. Both LHS and RHS (in common with all the
parameters of the o_ macros) are statements (not expessions!) whose
sequencing is controlled by the macro.
The expansion of o_assign (see encodings.h) is:
#define o_assign(p_arg1,p_arg2)\
{ out_basic_int(e_assign, 7);\
p_arg1; ASSERT_SORT(s_exp); \
p_arg2; ASSERT_SORT(s_exp); \
SET_RSORT(s_exp);\
}
The encoding for the EXP assign (ie 6)is given by e_assign (in enc_nos.h)
while s_exp (also in enc_nos.h) is a number chosen to represent the sort of
an EXP. The procedure out_basic_int (in PD_streams.c) is the most primitive
output routine. The macros ASSERT_SORT and SET_RSORT are defined in
asserts.h and used to implement the SORT checking.
2. Stream Mechanisms
The TDF encoding is constructed in streams, represented by the type TDF
given in PD_streams.h.
Each of the output macros and procedures operate on one of these streams
given by TDF * current_TDF. For example, the out_basic_int(e_assign, 7) in
o_assign above will add 7 bits to current_TDF to encode e_assign.
We have:
typedef struct { Chunk * first; Chunk * last;
unsigned int no; unsigned int sort;} TDF;
The no and sort fields are used to provide the SORT checking mechanism. The
first field points to the start of current stream given by a list of
Chunks; the last field is the final Chunk in this list, ie the one where the
next bits of output will go.
A Chunk is given by:
typedef struct chunk_struct
{ struct chunk_struct *next;
short int usage;
unsigned char offst; unsigned char aligned;
unsigned char data[DATA_SIZE];
} Chunk;
The output bits will go into the data field where usage ( <= DATA_SIZE ) is
the index of the next character to be written to and offst is the bit
position within this character starting from the most significant end (ie
offst=0 => no bits written yet into character). The next field is the next
Chunk in the stream, terminated by (Chunk*)0; if the the next field is 0
then this Chunk will be pointed to be the last field of the corresponding
TDF structure.
The a non-zero aligned field indicates that the start of the chunk data must be
on a byte boundary in the final CAPSULE.
Note that the initial Chunks of a stream may not be completely filled; ie
usage can less than DATA_SIZE (and offst need no be zero) for any Chunk in
the chain.
I have not provided any routines for compressing the Chunks into a
contiguous area of mainstore; however the routine make_tdf_file will output
a TDF stream to a file. If the contents of the TDF stream is a CAPSULE then
this would be a .j file.
3. Creating and changing streams.
It is usually necessary to have several streams of TDF being produced at
the same time. For example, tagdef and tagdec UNITs are often conveniently
constructed in parallel; for example, there would usually be at least one
for each UNIT being produced in the CAPSULE being compiled. We simply
change the stream in current_TDF. For some constructions, the macros
given below are very convenient - in any case the same pattern should be
used.
To create a new stream of output in a variable of type TDF , use the macro
NEW_STREAM given in PD_streams.h:
#define NEW_STREAM(ptrtoTDF, make_stream)\
{ TDF * hold_;\
hold_ = current_TDF;\
current_TDF = ptrtoTDF;\
current_TDF->first = current_TDF->last = create_chunk();\
make_stream;\
current_TDF = hold_;\
}
Here ptrtoTDF is some TDF* where the new stream is to be produced and
make_stream is code to produce the bits of the stream. NEW_STREAM will park
the current stream while the new stream is being produced, re-instating it
after it is finished. For example:
TDF new_stream;
NEW_STREAM( & new_stream, o_make_top)
will produce a stream containing make_top in new_stream, leaving the
current stream unchanged. To add more to new_stream later, one would do:
CONT_STREAM( & new_stream, more_bits)
Notice that NEW_STREAM(x,y) is just the same as:
CONT_STREAM(x,
current_TDF->first = current_TDF->last = create_chunk(); y)
Having constructed a new stream, it can be appended onto the current stream
using the procedure:
void append_TDF(TDF * tdf, Bool free_it)
Here, free_it says whether the Chunks of tdf can be freed and reused. For
example, append_tdf( & new_stream, 1) will append new_stream onto
current_TDF, allowing the Chunks of new_stream to be resused (see
create_chunk and free_chunk in PD_streams.c). The variable new_stream can
then only be used as another output stream using NEW_STREAM.
If one wished to copy new_stream onto the end of the current stream leaving
its Chunks intact, use free_it = 0.
A similar, more specialised, method of appending is given by:
void append_bytestream(TDF * tdf, Bool free_it)
which makes tdf into a BYTESTREAM and appends it onto current_TDF. This
would only be used for encoding a UNIT.
4. Encodings
The encoding macros of those construction which have encoding numbers
output the encoding number for the construction in the number of bits
appropriate to its SORT using:
void out_basic_int(long num, int bts)
num is output to current_TDF in bts bits. This is the most primitive output
routine and all the others use it, eg out_tdfint32 does the appropriate
number of out_basic_int(oct_digit, 4).
The encoding numbers of each construction given by the o_ macros in
encodings.h may be found in enc_nos.h
The parameters of a construction are output after the encoding number, so
that many constructions are sequences of encoding numbers and the encodings
of primitive sorts, implicitly bracketed by the signatures of the
constructions involved.
There are five procedures provided to give primitive encodings in
PD_streams.c:
void out_tdfint32(unsigned long n);
- outputs n as a TDFINT - assumes long is 32 bits.
void out_extendable_int(unsigned long num, unsigned int bts);
- outputs num as extentable encoding in bts bits (see spec 7.3.3)
void out_tdfbool(Bool b);
- outputs b as a TDFBOOL
void out_tdfstring_bytes (unsigned char * s, unsigned int k,
unsigned int n);
- outputs s as a TDFSTRING with k elements of size k bits.
void out_tdfident_bytes (unsigned char * s)
- outputs s as a TDFIDENT, putting in the appropriate alignments
necessary.
Other will be required for total generality; for example, it will become
necessary to create TDFINTs of size greater than 32 bits.
A procedure which can output a TDF stream (usually it would be a complete
CAPSULE - a .j file) is given by:
void make_tdf_file(TDF * s, FILE * out_file)
This is in mke_tdf_file.c
5. LISTs and OPTIONs
Many of the TDF constructors have LIST parameters with special encoding
giving the number of elements in the LIST. The o_ macros take account of
these by invoking the macro TDF_LIST. With the use of the LIST_ELEM macro,
the number of elements are counted as they are output and used to provide
the prefix of the encoding of the LIST. For example, a sequence S1; S2; S3
would be encoded:
o_sequence( {LIST_ELEM(S1); LIST_ELEM(S2)}, S3)
The SORT checking is not foolproof here; in a LIST there must be no output
other than that in the parameter of a LIST_ELEM. In the above example, the
SORTS of S1 and S2 will be checked to see that they are EXPs, but there is
no check to see that nothing has been output between LIST_ELEM(S1) and
LIST_ELEM(S2).
The mechanism for this is quite simple. The macro call of TDF_LIST in
o_sequence (for example) creates a new stream into which the list elements
will be output; each LIST_ELEM will increment the no field of the stream;
the final number will be output to the original stream and the new stream
appended to it.
A similar mechanism is used for OPTIONal parameters. This time the o_ macro
invokes TDF_OPTION and the actual parameter has the choice of either
outputing nothing or something of the correct SORT using the OPTION macro.
For example, a procedure application has an optional var_param parameter;
with a empty option we have:
o_apply_proc(Shape, Proc, Pars, {})
while with a real var_param V:
o_apply_proc(Shape, Proc, Pars, OPTION(V))
6. BITSTREAMs
Most of the constructors which use BITSTREAMs are handled transparently by
their o_ macros. For example, a shape_cond would be encoded:
o_shape_cond(C, S1, S2)
where S1 and S2 simply output SHAPEs normally. The _cond constructors all
invoke the macro TDF_COND which provides new streams for both E1 and E2.
The number of bits in each is computed using:
long bits_in_TDF(TDF *tdf);
and give the prefix TDFINT for the bitstreams required by the _cond
construction.
Similarly all the _apply_token constructors work in the same fashion, this
time using the TOK_APP macro. Here, of course, there is no SORT check
possible on the parameter applied to the token. An EXP token, T, with two
parameters, P1 and P2,is applied using: o_exp_apply_token(T, {P1; P2}) ie
the token parameters are simply output sequentially.
The other BITSTREAMs are all derived from token_definition which is rather
peculiar in that the SORT of the body parameter depends on its result_sort
parameter. The o_token_definition macro is to be found in PD_streams.h
rather than in encodings.h and its SORT is described as s_bitstream rather
than s_token_definition as one might expect. Otherwise, it can used in the
same way as the other o_ macros. Note that the SORT of the body parameter
is not checked to be consistent with its result_sort parameter.
7. Summary
Files:
encodings.h
- contains all the o_ macros except for o_token_definition.
enc_nos.h
- contains the e_ encoding numbers an s_ sort numbers.
PD_streams.h
- declares the stream procedures, the primitive encodings and the
stream changing and creation macros, together with
o_token_definition.
PD_streams.c
- defines the stream procedures and primitive encodings.
asserts.h
- defines the macros which control the SORT checking;
can be modified to eliminate SORT checking.
proto_def.h
- defines the macro proto to allow prototypes in declarations.
All output will be directed at:
TDF * current_TDF;
Primitive encoding procedures:
void out_basic_int(unsigned long num, unsigned int bts);
void out_extendable_int(unsigned long num, unsigned int bts);
void out_tdfint32(unsigned long n);
void out_tdfstring_bytes(unsigned char * s, unsigned int k,
unsigned int n);
void out_tdfbool(Bool b);
Stream handling procedures:
void append_TDF(TDF * tdf, Bool free_it);
void append_bytestream(TDF *tdf, Bool free_it);
long bits_in_TDF(TDF *tdf);
Chunk handling procedures:
Chunk * create_chunk();
void free_chunk(Chunk * x);
Stream macros:
NEW_STREAM(ptrtoTDF, make_stream)
CONT_STREAM(ptrtoTDF, make_stream)
These are used by the o_ macros:
TDF_COND(code_, sort_, exp_, arg1, arg2)
TDF_LIST(x, sort_)
- an actual x parameter will contain only LIST_ELEM(...)s
TDF_OPTION(x, sort_)
- an actual x parameter will have no output or one OPTION(...)
TOK_APP(num_, sort_, tok_, pars_)
8. Appendix
There are four other files included which may be useful. They are:
decodings.c
- contains d_X procedures, where X is a TDF non-primitive SORT;
when used with readstream.c, the d_ procedures will give a
diagnostic print of TDF in the above stream format.
readstream.c
- defines the primitive decoding and printing for stream format.
readstream.h
- declares the primitive decodings.
mke_tdf_file.c
- usually used to output the completed CAPSULE as a .j file.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Please direct any comments or complaints to:
Ian Currie, DRA, Malvern
E-mail: currie@uk.mod.hermes