UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

ASN.1-C compiler for automatic protocol implementation Yang, Yueli 1988

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1988_A6_7 Y36.pdf [ 5.25MB ]
Metadata
JSON: 831-1.0051939.json
JSON-LD: 831-1.0051939-ld.json
RDF/XML (Pretty): 831-1.0051939-rdf.xml
RDF/JSON: 831-1.0051939-rdf.json
Turtle: 831-1.0051939-turtle.txt
N-Triples: 831-1.0051939-rdf-ntriples.txt
Original Record: 831-1.0051939-source.json
Full Text
831-1.0051939-fulltext.txt
Citation
831-1.0051939.ris

Full Text

ASN.l-C COMPILER FOR AUTOMATIC PROTOCOL IMPLEMENTATION By YUELI YANG B.Eng., Tsinghua University, China, 1985 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E DEGREE OF MASTER OF SCIENCE in T H E FACULTY OF GRADUATE STUDIES (DEPARTMENT OF COMPUTER SCIENCE) We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH COLUMBIA October 1988 © Yueli Yang, 1988 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of Computer S c i e n c e The University of British Columbia Vancouver, Canada Date October 15, 1988 DE-6 (2/88) A b s t r a c t One of the basic requirements of communication protocols in a heterogeneous computer network is a standard external data-transfer representation. Abstract Syntax Notation One (ASN.l) has been widely used in international standard specifications. Its transfer-syntax of Basic Encoding Rules (BER) is applied as the standard external data representation. This thesis presents an efficient BER implementation, called the ED library. The ED library includes a number of encoding and decoding routines that may be used as primitive functions to compose encoders and decoders for arbitrarily complicated ASN.l data-types. The Performance of the ED library is measured and discussed. Based on the ED library, an ASN.l-C compiler, called CASN1, is designed and implemented to release communication software programmers from the arduous work of translating protocol-defined data-types and constructing their encoders and decoders. Given an ASN.l protocol specification, CASN1 automatically translates the input ASN.l modules into C and generates the BER encoders and decoders for the protocol denned data-types. This thesis discusses the design principles, user interface, internal structures, and the implementation and of CASN1. Example applications are given. Both the ED library and CASN1 are implemented in C on UNIX 4.2 BSD using the YACC and LEX tools. ii C o n t e n t s Abstract " Contents i " List of Tables vi List of Figures vii Acknowledgement ix 1 Introduction 1 1.1 Motivation 1 1.2 An Example of using ASN.l and BER 4 1.3 Related Work 8 1.3.1 BBN Message Transfer Protocols Project 9 1.3.2 The ISODE Data Service . ; 11 1.3.3 Ean Encoder and Decoder 14 1.3.4 Thesis Statements 14 1.4 Thesis Organization 16 2 The OSI A S N . l and B E R 17 2.1 Abstract Syntax Notation One (ASN.l) 17 2.2 Basic Encoding Rules (BER) 21 2.3 Differences between X.409 and ISO ASN.l /BER 23 3 Data Type Translation between A S N . l and C 24 3.1 Primitive Types 24 3.2 Bit String and Octet String Types 26 3.3 Object Identifier Type 27 3.4 Any Type 27 3.5 Sequence and Set Types 27 3.6 Sequence of and Set of Types 28 iii 3.7 Choice Type 29 3.8 UTC Time and Generalized Time Types 30 3.9 External Type 30 3.10 Defined Tagged Types 31 4 The ED Library Design and Implementation 33 4.1 The ED Library Design 33 4.1.1 The ED Library Utility Routines 34 4.1.2 Primitive Type Encoding and Decoding 35 4.1.3 Structured Type Encoding and Decoding 35 4.1.4 Tagged Type Encoding and Decoding 37 4.1.5 Special Feature of Decoding 38 4.1.6 The ANY Type Encoding and Decoding 39 4.1.7 The REAL Type Encoding and Decoding 39 4.2 The ED Library Implementation 39 4.2.1 The ED Library Data Structures , 40 4.2.2 The ED Library Routines 42 4.2.3 The ED Library Sub-memory System 44 4.3 Using the ED Library Routines . 46 5 The CASN1 Design and Implementation 47 5.1 The CASN1 Design 48 5.1.1 The Interfaces of CASN1 48 5.1.2 The Functions of CASN1 50 5.1.3 Modification to ASN.l Syntax 53 5.2 The CASN1 Implementation 55 5.2.1 The First pass 56 5.2.2 The Second pass 57 5.2.3 The Third pass 58 5.3 Using the CASN1 Output 61 6 Performance and Applications 64 6.1 The ED Library Performance . 64 6.2 Results of CASN1 Applications 75 6.2.1 The ISO Virtual Terminal Protocol 75 6.2.2 The CCITT X.266 Presentation Protocol 75 6.2.3 The OSI X.500 Directory Protocol 76 6.2.4 The ASN.l/Estelle Integration Project 76 7 Conclusions and Future Research 77 7.1 Conclusions 77 7.2 Future Work 78 iv Bibliography 80 A B N F of A S N . l Syntax Rules 82 B B N F of C A S N 1 Syntax Rules 90 C Example of Structured Type Encoding and Decoding 100 D Example of C H O I C E Type Encoding and Decoding 106 E Example of Using C A S N 1 and E D Library 112 v List o f Tables 3.1 Data-Type Translation between A S N . l and C 25 4.1 The E D Library Primitive Class Routines 36 6.1 The E D Library Performance 66 6.2 O C T E T STRING Encode Octet Complexity 67 6.3 B A S I C V T P I T E M Encode Octet Complexity 67 6.4 PERSONNELRECORD Encode Octet Complexity 67 vi List of Figures 1.1 Communicate Using an External Data Representation 2 1.2 w r i t e , c 5 1.3 read.c 5 1.4 ed.write.c 6 1.5 ed_read.c 6 1.6 Execution Script of the Example 7 1.7 BBN X.409 Compiler and Parser 10 1.8 BBN Data Encoding and Decoding 11 1.9 ISODE ASN.l Compiler 13 1.10 Interface of Encoder and Decoder 15 2.1 An Example of Data Encoding 21 2.2 Structure of BER Transfer Syntax 22 3.1 C Structure B I T S and O C T S Definition 26 3.2 C Structure 0 I D Definition 2 7 3.3 C Structure LIST Definition 2 8 3.4 C Structure TIME Definition 3 0 3.5 C Structure E X T Definition 3 1 4.1 Function of Encoding and Decoding Routine 34 4.2 C Structure I0P Definition 4 0 4.3 C Structure IDX Definition 41 4.4 The ED Library Stack Definition 4 2 5.1 The Interfaces of CASN1 4 9 5.2 BNF of OPERATION Definition and ERROR Definition 5 4 5.3 Using CASN1 Output 6 3 6.1 O C T E T STRING Encode Octet Complexity 6 8 6.2 B A S I C V T P I T E M Encode Octet Complexity 6 9 6.3 PERSONNELRECORD Encode Octet Complexity 7 0 6.4 O C T E T STRING Encode/Decode Time Complexity 7 2 vii 6.5 PERSONNELRECORD Encode/Decode Time Complexity 73 6.6 B A S I C V T P I T E M Encode/Decode Time Complexity 74 viii A c k n o w l e d g e m e n t Some moments in our lives seem eternal, whether in time, or in depth. The years I spent in Vancouver were full of such moments. It is not within the following limited lines that I will be able to do justice to all of them. First of all, I would like to sincerely thank my supervisor Dr. Gerald W. Neufeld for many things, especially for suggesting the thesis topic, for fruitful discussions and wonderful guidance, and for being a continuous source of advice and encouragement during the course of this research and my stay in Vancouver. This thesis would not be what it is without the help from many friends. Thanks to B. Hilpert and E. Lau for their help in discussing and debugging CASNl; to D. Ouimet, M. Goldberg and S. Ng for providing comments by using this package in their theses and research; and to I. Chan and J. Demco for their help in collecting information about the related works. Thanks to Dr. Samuel T. Chanson for being the second reader of this thesis and to L. Liang, B. Brachman, B. Hilpert, M. Goldberg, and H. Kreyszig for reading, commenting and correcting grammar errors in many drafts of this thesis. Thanks to the Department of Computer Science at the University of British Columbia for providing the computing equipment to facilitate this research and for providing financial support in the form of teaching and research assistantships during my M.Sc graduate studies. And last, special thanks should go to my dear husband Luping and my parents. Without their consistent support and invaluable love, I would never be able to conquer the obstacles that seemed insurmountable. — ix Chapter 1 I n t r o d u c t i o n As the introduction to the thesis, this chapter presents the motivation of the thesis re-search, discusses the related work, and specifies the thesis statements. An outline of the thesis organization is given in the last section of this chapter. 1.1 M o t i v a t i o n In a heterogeneous computer communication network, computers may differ in their internal data representations. For example, characters may be coded in ASCII, EBCDIC, or in a graphical character set; integers may vary in length from 8 to 64 bits; bytes may be addressed from left to right or from right to left within a word. Also, programming languages may differ in their representation of numbers or data structures. Therefore, when transferring data between different types of computers or various application entities implemented in different programming languages, the specification of the data structure has to be transferred as well. In an open system environment, it is impractical to provide a separate data representation transformation mechanism for each possible pair of computer types, as this would lead to N * (N — 1) translators for N different types of computers, without considering language differences. As shown in Figure 1.1, a practical scheme may be to define a network-wide external data 1 CHAPTER 1. INTRODUCTION 2 representation for data transfer1. Senders encode message data from local representations into the external representation before sending messages out to the network. Receivers decode the received message data from the external representation into their local representations before processing the messages. With such an external data representation, only 2*N translators (one to and one from the local representation for each of the computers or languages) are needed. Application Entity Application Entity Local Representation Local Representation Presentation Entity Data External Transfer Representation Presentation Entity Figure 1.1: Communicate Using an External Data Representation The purpose of the presentation-layer in the OSI model2 is to overcome the differences of data representation in heterogeneous computer systems. It functions between the local data representations and the external data representations. The presentation-layer provides facilities to represent application-layer data in a way that is independent of both computers and application languages. It also provides protocols to enhance the session-layer service by providing external representations for data transfer, as well as mechanisms to define and to select these representations. 1 T H s figure is from [19]. 2 The OSI seven-layer model (Open System Interconnection reference model) is defined by ISO (the Internation Standards Organization). Interested readers may refer to "Computer Networks", the second edition by A. S. Tanenbaum, Prentice-Hall, 1988. CHAPTER 1. INTRODUCTION 3 The languages defined in the Courier protocol developed at Xerox and in the eXternal Data Representation (XDR) developed by Sun Microsystems, Inc. are examples of such external data representations. The Abstract Syntax Notation One (ASN.l), denned by ISO, has been used in many international standards to specify communication protocols. The Basic Encode Rules (BER), also denned by ISO, are used to encode data of ASN.l types into a transfer syntax (octet sequence) which is also a external data representation3. ASN.l is an abstract syntax notation (or a language) for defining both complex types and the values of these types without worrying about how the instances of these types are represented during data transfer. It can be used in defining the abstract-syntax of information, particularly in specifying standards for application protocols. The BER is used to transform the data-values of ASN.l types into an octet-sequence for data transfer. Originally, ASN.l and BER were denned in CCITT recommendation X.409 [4] in 1984. In 1985, the ISO 8824 standard (draft) [7] first defined the ASN.l syntax independent of its encoding rules. Meanwhile, the ISO 8825 standard (draft) [9] defined BER as one of the ASN.l encoding/decoding rules. Both ISO 8824 and ISO 8825 are technically aligned with the relevant parts of CCITT X.409. ASN.l and BER have been refined several times in 1985, 1986, and 1987 and their final versions were published in December 1987. At the same time, their first addendum — extensions to ASN.l [8] and to ASN.l Basic Encoding Rules [10] were also published. 3Abstract-syntax is a formal syntax notation which specifies information independent of the information representation. Transfer-syntax is a syntax notation which represents information in octet sequences. In this thesis, the terminology transfer-syntax, external data-representation, and octet-sequence have the same meaning and are used interchangeably. CHAPTER 1. INTRODUCTION 4 1.2 An Example of using A S N . l and B E R As a formal notation, ASN.l can be applied whenever it is necessary to define information in an abstract-syntax. It is particularly applicable to application protocol specifications that have complex data types. BER translate the data-values of ASN.l types into a transfer-syntax before transmitting the data over the network. The following is an example of using BER to transfer data of ASN.l INTEGER type in a heterogeneous environment. In the Department of Computer Science at University of British Columbia, there are three different types of machines connected by an Ethernet: machine grads is a SUN 3/260, ugly is a SUN 2/50 and ean is a VAX 11/750. They all run the version of UNIX 4.2 BSD 4 operating system. Since the SUN and VAX adopt different data representations internally, the three machines on the Ethernet constitute a heterogeneous environment at the machine-level. The executable code of write.c and read.c are stored in the files write and read respec-tively. Read reads ten integers 0,1,2, . . . ,9 from stdin and write displays them on stdout. The files ed_read and ed_write contain the executable code of ed.write.c and ed_read.c respectively. They are almost identical to read.c and write.c, except they transform the data into ASN.l transfer-syntax during data transfer. Encode_int() and Decode_int() in the files ed_write.c and ed_read.c are the encoder and decoder5 of ASN.l INTEGER type. The four programs are shown in Figures 1.2, 1.3, 1.4, and 1.5 respectively, and are compiled and installed on each of the three machines. 4 UNIX is a trade mark of Bell Laboratories and 4.2 BSD is a version of the UNIX operating system distributed by the University of California, at Berkeley.. 5Encode transforms a data-value from local representation into the ASN.l octet-sequence according to BER. Decode refers to the inverse of encode. The terms encode routine, encoding routine and encoder are used inter-changeably in this thesis to refer to the encode function. Similarly, decode routine, decoding routine and decoder are used interchangeably to refer to the decode function. CHAPTER 1. INTRODUCTION 5 m a i n O /* w r i t e . c */ •C l o n g i ; f o r ( i = 0; i < 8; i++) { i f ( f w r i t e ( ( c h a r *) & i , s i z e o f ( i ) , 1, stdout) != 1) -[ f p r i n t f ( s t d e r r , " f a i l e d ! \ n " ) ; Q x i t ( l ) ; } } Figure 1.2: w r i t e . c m a i n O / * r e a d . c * / -C l o n g i , j ; f o r ( j = 0; j < 8; j++) { i f ( f r e a d ( ( c h a r *) fti, s i z e o f ( i ) , 1, s t d i n ) != 1) { f p r i n t f ( s t d e r r , " f a i l e d ! \ n " ) ; e x i t ( l ) ; } p r i n t * ( " 5 U " , i ) ; } p r i n t f ( " \ n " ) ; Figure 1.3: r e a d . c C H A P T E R 1. I N T R O D U C T I O N 6 mainO /* ed.write.c */ •C long i , len; byte *b; f o r ( i = 0; i < 8; i++) { b = serlDX (Encode_int(UNIVERSAL, PRIMITIVE, C0DE_INTEGER, fti), &b, &len); i f ( f w r i t e ( ( c h a r *) b, s i z e o f ( * b ) , l e n , stdout) != l e n ) { f p r i n t f ( s t d e r r , " f a i l e d ! \ n " ) ; e x i t ( l ) ; > > } Figure 1.4: ed_write.c mainO /* ed_read.c */ •C long i , j ; byte bClO], *c; for (j = 0; j < 8; j++) { i f (fread((char *) b, sizeof(byte), 3, stdin) != 3) { f p r i n t f ( s t d e r r , "failed!\n"); e x i t ( l ) ; } c = b; Decode.int(UNIVERSAL, PRIMITIVE, C0DE_INTEGER, ftc, &i); printfC'/x ", i ) ; > p r i n t f ( " \ n " ) ; Figure 1.5: ed_read.c CHAPTER 1. mTRODUCTION 7 (1) rsh grads write I rsh grads read 0 1 2 3 4 5 6 7 (2) rsh grads write I rsh ugly read 0 1 2 3 4 5 6 7 (3) rsh grads write I rsh ean read 0 1000000 2000000 3000000 4000000 5000000 6000000 7000000 (4) rsh grads ed.write | rsh ean ed.read 0 1 2 3 4 5 6 7 (5) rsh grads ed_write I rsh ugly ed_read 0 1 2 3 4 5 6 7 (6) rsh grads ed_write I rsh grads ed.read 0 1 2 3 4 5 6 7 Figure 1.6: Execution Script of the Example CHAPTER 1. INTRODUCTION 8 Figure 1.6 is the execution script. Executions (1) and (2) show the correct data transfer between machines of the same type (two SUN's) without using an external data representation. Execution (3) shows the transfer error when passing data between two different machines (VAX and SUN) without using an external data representation. Execution (4) shows that the problem is overcome with ASN.l as the external data representation. Executions (5) and (6) demonstrate that ed_write() and ed_read() can also be used when communicating with the same kind of machine, although it may not always be necessary. The above example also demonstrates the steps of using ASN.l and BER in data transfer: 1. Define data in ASN.l syntax. According to ASN.l, integer X is denned as: X ::= INTEGER. 2. Translate the type-definition from ASN.l into an application programming language. In our example, the application programming language is C. So, the type-definition is trans-lated to: typedef int X. 3. Write the encoder and decoder for the data type according to BER. In our example, the encoder is Encode_int() and the decoder is Decode_int(). 4. Write communication programs to manage data transfer over the communication network. 1.3 Related Work As a formal abstract-syntax notation, ASN.l has been widely used in many international standards. To implement communication protocols in a heterogeneous computer network en-vironment, one of the basic requirements is data encoding and decoding; i.e., converting data-values between the local representations and the external transfer representation. As a result, a considerable amount of work has been done in implementing BER and ASN.l compilers. This CHAPTER 1. INTRODUCTION 9 section briefly discusses some related work. Readers are assumed to have some knowledge of ASN.l to appreciate this section. Naive readers can refer to Chapter 2 for a summary of ASN.l and BER. For detailed information on the related work, interested readers should refer to the relevant documents cited in the bibliography. 1.3.1 B B N M e s s a g e T r a n s f e r P r o t o c o l s P r o j e c t In 1984, A. R. Pope and D. P. Deutsch at Bolt Beranek and Newman Inc. implemented an X.409 presentation-layer data-transfer system in C on UNIX [14]. It is part of a project on message transfer protocols for the National Bureau of Standards (NBS). Their X.409 presentation-layer data-transfer system is a collection of tools that process type-notation, value-notation, and data encoding/decoding. In particular, these tools en-code/decode PDUs (Protocol Data Units) between the local representation and the external standard transfer-syntax representation. The tools include a compiler which compiles X.409 modules of type-notations into data structures, called type tables. A type table is essentially a tree. Its hierarchy corresponds directly to the manner in which constructor types6 are composed. The tree nodes correspond to individual primitive7 or constructor types and tree edges denote the composition of complex constructor types from simpler ones. The type tables are used to process the value-notations and data encoding/decoding. The tools also include a parser which parses X.409 value-notations and translates them into data structures, called value tables. Similar to the type tables, each value table is also organized as a tree, corresponding to the structure of the value's type. The tree nodes represent 6 Counstructor types which is the same as structured types are defined in Section 2.1 7Primitive types are also defined in Section 2.1 CHAPTER 1. INTRODUCTION 10 the values of primitive or constructor types and tree edges denote the data-value composition. The v a l u e t a b l e s are used in data encoding and decoding. Both the type t a b l e and the value t a b l e are C data structures. They are stored in a file which may be included by user programs. Figure 1.7 shows the process of compiling X.409 type-notations and parsing X.409 value-notations. type notations X.409 Specification J value notations Parser Value Tables Lexical Figure 1.7: BBN X.409 Compiler and Parser Two functions are passed to the parser as parameters: 1. The type t a b l e describes the data structure of the input value-notation and directs the parsing. 2. The l e x i c a l does the lexical analysis of the value-notation and provides tokens to the parser. A presentation-layer data value represented by a value t a b l e can be encoded by the rou-tine encode_value() to produce a BER octet-sequence. A presentation-layer data-value in CHAPTER 1. INTRODUCTION 11 its encoded form (i.e., BER octet-sequence) can be decoded by the routine decode_value() to produce a value table. The type table of the value is passed to encode_value() and decode .value () as one of the parameters to guide the encoding/decoding process. Figure 1.8 shows the process of data encoding and decoding. Value Table Type Table (Sender) Same Type Table Transfer Syntax Type Table Value Table (Reciver) (Communication Link) Figure 1.8: BBN Data Encoding and Decoding 1.3.2 T h e I S O D E D a t a Service The ISODE (ISO Development Environment) is a system developed by the Wollongong Group and the Northrop Co. [13]. It is an implementation of some ISO protocols in C on UNIX as well as on several other systems. The software includes implementations of the OSI Association Control Service, Remote Operation Service, Reliable Transfer Service, and abstract-syntax and transfer mechanisms. It also includes the implementation of the OSI presentation-layer service, session-layer service, and transport-layer service. Some application programs and user interfaces are also implemented using their software. CHAPTER 1. TNTRODUCTION 12 The libpsap library implements presentation-layer abstract-syntax for the machine indepen-dent exchange of data structures. It manipulates two objects: presentation-elements PE and presentation-streams PS. PE is used to represent an arbitrarily complex data structure in a machine-independent form. Several routines have been implemented to translate between the machine-independent representation PE and machine-specific objects, such as integers, strings, and the like. A PS is an object to represent an I/O path of a PE data structure, such as a communication port or a file pointer. The three programs rosy, posy and pepy together function as an ASN.l compiler. Figure 1.9 shows the organization of the ISODE ASN.l compiler. The remote operation module is an ASN.l module-definition with extensions to remote oper-ation specifications. Rosy reads the description of a remote operation module and produces the corresponding C-stubs and C-defmitions which are used in accessing the remote operation ser-vices. It also produces an abstract-syntax module which is simply a copy of the type-definitions in the remote operation module. Posy reads the description of an abstract-syntax module (possi-bly produced by rosy) and produces the corresponding C structure-definitions and an augmented abstract-syntax module. The C structure-definitions are used by the remote operation invoker and performer. The run-time environment is responsible for mapping these data structures to the abstract-syntax stored in PE and then mapping the abstract-syntax from PE to the transfer-syntax. Pepy reads the description of an augmented abstract-syntax module (probably produced by posy) and produces three C programs — PE parser, PE constructor and PE printer — to parse, create, and print presentation-elements (PE) of the objects described in the module. The PE constructor maps a data structure into abstract-syntax in PE and the PE parser does the inverse — mapping a presentation-element in PE into a C data structure. The syntax of the augmented CHAPTER 1. INTRODUCTION ASN. l Specification (remote operation module) librosy C Stubs and Definitions Remote Operations Abstract Syntax Module 1 r Augmented Abstract Syntax Module Data Structure C Definitions Figure 1.9: ISODE ASN.l Compiler CHAPTER 1. TNTRODUCTION 1 4 abstract-syntax module is based on ASN.l with several extensions: compiler directives, action statements, control statements and value passing statements. The ISODE ASN.l compiler does not recognize ASN.l macro-definitions. It ignores the ASN.l type-definition of COMPONENTS OF, SELECTION and DEFAULT types. 1.3 .3 E a n E n c o d e r a n d D e c o d e r The Ean messaging system developed by a research group in the Computer Science Depart-ment at the University of British Columbia contains another implementation of BER. It has a number of encoding and decoding procedures to transform data between a C structure called an EJIODE and BER transfer-syntax. An EJIODE has five fields. One field records the tag of an ASN.l type. One field records the data length. The other three fields are pointers to the prim-itive data value, to another E_N0DE if the data is of constructor type and to another E_N0DE if the data has sibling nodes (other values on the same level). The EJJODE can be viewed as a tree structure where each node corresponds to a primitive or a constructor value. The edges (repre-sented by the EJIODE pointer fields) indicate the relationship between the types defined in tree nodes. With the EJIODE structure, a data-value can be translated into the BER transfer-syntax by calling the corresponding encoding procedure. The data-value in transfer-syntax may also be decoded back into an E_N0DE by calling the corresponding decoding procedure. The E_N0DE has been implemented as an abstract data type. 1.3 .4 T h e s i s S t a t e m e n t s The three BER implementations discussed in this chapter use the same idea: An internal data structure is used to represent data in an abstract-syntax. The internal data structure is also used as the interface to the encoding and decoding routines. This is shown in Figure 1.10. CHAPTER 1. INTRODUCTION 15 User Data in Local Representation User Data in Abstract Syntax User Data in Transfer Syntax In the C Data Structure In the Internal Data Structure On Communication Link Figure 1.10: Interface of Encoder and Decoder The type t a b l e is the internal data structure in the BBN implementation, as well as the PE_Type in the ISODE implementation and the E_N0DE in the Ean implementation. With such an internal data structure as the interface, some overhead must be paid for converting data between user data and this internal data structure during encoding and decoding. This thesis presents another BER implementation — ED library — which avoids this overhead. The ED library includes a number of BER encoding and decoding routines for ASN.l defined types. They are implemented in C on UNIX 4.2 BSD. The encoding routines transform data directly from C to BER transfer-syntax. The decoding routines do the inverse, transforming data from BER transfer-syntax to C. If the transfer-syntax is from a file and is OCTET STRING or BIT STRING type in CONSTRUCTOR form (usually it contains a large data-value), the decoding routine provides a special function to decode only the data structure, and the data-value can be loaded later from the file. The ED library is implemented based on the ISO 8825 BER-definition and its addendum. The CCITT Recommendation X.208 and X.209 [1,2] are also referenced. Since data encoding and decoding are frequently used during data transformation, efficiency was the top concern in the design and implementation of the ED library . Based on the ED library, this thesis also presents a design and implementation of an ASN.l-CHAPTER 1. INTRODUCTION 16 C compiler, named CASN1. It is a package written in C on UNIX 4.2 BSD using the YACC and LEX tools. It parses an ASN.l module-definition and translates all type-definitions into C. It also generates BER encoding/decoding routines for all defined ASN.l types. CASN1 supports all ASN.l types, including COMPONENTS OF, SELECTION type and ENCRYPTED type. It ignores the ASN.l macro-definitions. However, it has the extensions for oPERATiON-definitions and ERROR-definitions in its syntax for specifying abstract operations. The operation arguments, results and error parameters are recognized as ASN.l type-definitions by CASNl. Their en-coding and decoding routines are generated and stored in files with the operation number or error number as indices. CASNl is implemented based on the ISO 8824 ASN.l-definition and its addendum. The CCITT Recommendation X.208 is also referenced. 1.4 Thesis Organization Chapter 2 briefly introduces the international standards for ASN.l and BER. Knowledge-able readers can skip this chapter. Chapter 3 discusses the translation between ASN.l and C. Chapter 4 presents the design and implementation of the ED library. Chapter 5 explains the design and implementation of CASNl. Chapter 6 shows the performance and some application examples of the ED library and CASNl. Chapter 7 summarizes the thesis and points out some future work. Appendix A and Appendix B provide the standard ASN.l syntax rules and the CASNl syntax rules in BNF. Appendix C, Appendix D and Appendix E demonstrate some examples of using CASNl and the ED library to encode/decode data-values of ASN.l types. Chapter 2 T h e O S I A S N . l a n d B E R This chapter briefly introduces the ISO standard ASN.l and BER. It also points out the differences between CCITT recommendation X.409 and ISO standards ASN.l and BER. The BNF specification of ASN.l syntax is included in Appendix A. Interested readers should refer to the ISO documents cited in the bibliography for more complete descriptions of the standards. 2.1 A b s t r a c t S y n t a x N o t a t i o n O n e ( A S N . l ) Abstract Syntax Notation One (ASN.l) is a language which enables both complex types to be defined and the values of these types to be specified without concern regarding how instances of these types are represented during data transfer. In many aspects, ASN.l is similar to the data type definitions in conventional programming languages, such as Pascal, C, and Ada. It has a formal syntax for defining and naming types, as well as mechanisms allowing users to build arbitrarily complex constructor types from simpler ones. As specified in ASN.l, a type consists of a collection of values. One specific instance of a type is called a value of the type. More generally, a value or a type often consists of several simpler values or types, together with the relationships between them. ASN.l defines seven primitive types: INTEGER, BOOLEAN, REAL, ENUMERATED, BIT STRING, OCTET STRING, NULL 1 7 CHAPTER 2. THE OSI ASN.l AND BER 18 and OBJECT IDENTIFIER. The values of these types are also defined by ASN.l. In ASN.l, there are five constructors for defining more complex types: SEQUENCE, SET, SEQUENCE OF (SET OF) , CHOICE , and S U B T Y P E . These constructors are applied according to the following rules: 1. Given an ordered list of existing types, a value can be formed as an ordered sequence of values, by choosing one from each type in the list. The collection of all possible values obtained in this way is a new type — SEQUENCE . If the tags of these types and of any immediately following types in the list are distinct, SEQUENCE can be extended to allow omissions of some values from the list. 2. Given a list of distinct existing types, a value can be formed as a (un-ordered) set of values, one from each type in the list. The collection of all possible values obtained in this way is a new type —- SET. SET can be extended to allow omissions of some values. 3. Given a single existing type, a value can be formed as a sequence or a set by choosing zero, one or more values of the given type. The collection of all possible values obtained in this way is a new type — SEQUENCE OF or SET OF. 4. Given a list of distinct types, a value can be chosen from any one of them. The set of all possible values obtained in this way is a new type — CHOICE. 5. Given a type, a new type can be formed as a subset of it by using some structure or ordering relationship among the values, resulting in a new type — S U B T Y P E . Any types denned by one of the above five rules is a structured type. Obviously, any value of these structured types are composed of the values of their component types. To correctly interpret a structured data-value, it is always necessary to know the type of the value. In a high level programming language, the type of a data-value can be found by looking CHAPTER 2. THE OSI ASN.l AND BER 19 at the variable declaration. In a BER octet-sequence transmitted on network links, the type of a data-value can be represented by certain octets and those octets are also transmitted as an integral part of the data-value. In ASN.l, every type is assigned a tag. A value is always associated with the type-tag to indicate the type of the value. The tag of a type can be defined either by ASN.l or by users. Four tag classes are specified in ASN.l and each of them represent certain kind of types: 1. The UNIVERSAL class defines tags that are only used as specified in ASN.l. Each UNI-VERSAL class tag is assigned either to a single primitive type or to a single constructor type. 2. The APPLICATION class defines tags that are assigned to types defined by other standards or recommendations. Within a particular standard, an application class tag is assigned to only one type. 3. The PRIVATE class defines tags that are never assigned by ISO standards or CCITT recommendations. 4. The CONTEXT-SPECIFIC class defines tags that are freely assigned within any use of ASN.l, and are interpreted according to the context in which they are used. A tag consists of class, form and identifier code components. A tag's class component is one of the above four defined classes. Within the same class, tags are distinguished by the identifier code of the tag which may be any positive integer. A tag's form component indicates how the data is represented during transferring, either in primitive form for most primitive types or in constructor form for structured types and some primitive types. Tags are mainly intended for machine use rather than the user. It is common to assign a tag to multiple different types. Two CHAPTER 2. THE OSI ASN.l AND BER 2 0 types can be distinguished by their content when their tags are the same. A user of A S N . l may choose to assign distinct tags to two occurrences of the same type, resulting in two distinct types. This can be useful, for example, to distinguish which choice has been made in the case of the CHOICE type. A S N . l defines a type by one of the seven primitive types or one of the five constructors and assigns a tag to each of the defined types. The types differ by their structures or by their tags. By assigning different tags to O C T E T STRING, A S N . l defines eight character string types: Nu-MERICSTRING, PRINTABLESTRING, T E L E T E X S T R I N G (T61STRING ) , VIDEOTEXSTRING, VISIBLESTRING ( I S 0 6 4 6 S T R I N G ) , IA5STRING, GRAPHICSTRING and GENERALSTRING. By applying different structure compositions, A S N . l defines four useful types: GENERALIZED T I M E , UNIVERSAL T I M E , EXTERNAL and OBJECT DESCRIPTOR . From all these existing types, more complex types may be defined. A S N . l can be applied whenever it is necessary to define the abstract-syntax of information. It is particularly applicable to specifying application protocol-standards. A S N . l is used as a semi-formal tool for defining protocols. The use of the notation does not necessarily preclude ambiguous specifications. The user is responsible for ensuring that the specification is not ambiguous. A S N . l is supported by a set of encoding rules. One of them is the Basic Encoding Rules (BER). The application of the encoding rules results in a complete specification of the data-value as well as its type during data transfer; i.e., BER transfer-syntax. Figure 2.1 shows an example of encoding an A S N . l INTEGER with the value of 8824 using BER. CHAPTER 2. THE OSI ASN.l AND BER 2 1 ASN.l Definition Type Definition: X ::= INTEGER Value Definition: x X::=8824 value identifier type of value the value Encode Decode BER Octet Sequence 02 02 22 78 T V indicate indicate the indicate the the data next two octets data-value type is contains the is equal to INTEGER data-value 8824 Figure 2.1: An Example of Data Encoding 2.2 B a s i c E n c o d i n g R u l e s ( B E R ) The Basic Encoding Rules (BER) are a set of encoding rules that may be applied to values of ASN.l types to produce a transfer-syntax for those values. BER are used at the time of data transformation by the presentation-service provider. It is implicit in the specification that the encoding rules are also used for decoding the transfer-syntax to identify the data-values being transferred. According to BER, the complete octet-sequence used to represent the data-value consists of four components which appear in the following order: 1. identifier octets, 2. length octets, 3. contents octets, and 4. end-of-contents octet (eoc). The identifier indicates the type of the data-value. It encodes the ASN.l tag of the data-value. It may contain more than one octet if the tag identifier code is greater than 32. The CHAPTER 2. THE OSI ASN.l AND BER 2 2 length determines the end of a data-value transfer-syntax representation. T w o forms of length encoding are provided: definite and indefinite. In the definite form, the length octets consist of one or more octets to represent the number of octets i n the contents octets. In the indefinite form, the length octets consist of a single octet wi th a special value indica t ing that the contents octets are terminated by an end-of-content octet. T h e contents consist of zero, one or more octets to represent a par t icular data value that dist inguish the data-value from other values of the same type. T h e data-value i n contents is encoded as specified i n B E R . T h e end-of-contents is used to determine the end of a data-value transfer-syntax representation. It is optional depending on the length octets. It w i l l be presented only i f the value of the length indicates indefinite form. Figure 2.2 shows two structures of a data-value encoded according to B E R 1 . IDENTIFIER-OCTETS LENGTH-OCTETS T CONTENTS-OCTETS Represents number of octets in contents octets IDENTIFIER-OCTETS LENGTH-OCTETS CONTENTS-OCTETS END-OF-CONTENTS OCTETS J J Indicates that the contents octets are terminated by end-of-contents octets Indicates that there are no further encodings in the contents octets Figure 2.2: Structure of B E R Transfer Syntax 1 This figure is from [9]. CHAPTER 2. THE OSI ASN.l AND BER 23 2 . 3 D i f f e r e n c e s b e t w e e n X . 4 0 9 a n d I S O A S N . l / B E R ASN.l defined in ISO 8824 and BER defined in ISO 8825 are technically aligned with the relevant parts of CCITT X.409 which predates ASN.l and BER. CCITT X.409 defines an abstract-syntax notation and encoding/decoding rules in a single document. As listed below, ASN.l has several extensions to the abstract-syntax notation which are not included in X.409: • I M P O R T and E X P O R T types among modules. • T A G D E F A U L T S are added to define the default tag of type definitions in a module. • S U B T Y P E notation is added to the type-definitions. • A N Y D E F I N E D B Y is added to the A N Y type-definition. • Five new types are introduced: O B J E C T I D E N T I F I E R , R E A L , E N U M E R A T E D , O B J E C T D E S C R I P T O R and E X T E R N A L . • Three more character string types are defined: V I S I B L E S T R I N G G R A P H I C S T R I N G and G E N E R A L S T R I N G . Along with these extensions defined by ASN.l, BER extends X.409 to include encoding rules for the newly defined types. The CCITT Recommendation X.208 and X.209 are the CCITT standards corresponding to the ISO 8824 (ASN.l) and 8825 (BER) respectively. CCITT X.208 extends ASN.l to include the E N C R Y P T E D type. Along with the X.208 extension to ASN.l, X.209 extends BER to include the encoding rules for the E N C R Y P T E D type. Chapter 3 D a t a T y p e T r a n s l a t i o n b e t w e e n A S N . l a n d C Because the C programming language has been widely used in protocol implementations, it has been chosen as the application programming language in our implementation. For most data-types, translation between A S N . l and C can be achieved simply by direct mappings. However, there are some A S N . l types which require the design of special C structures for the translations. Table 3.1 summarizes the basic translation between A S N . l types and C types. They are further explained in the following sections1. 3 . 1 P r i m i t i v e T y p e s The A S N . l types INTEGER, REAL, ENUMERATED, NULL, SEQUENCE { . . . } and SET { . . . } are directly mapped to the corresponding C types i n t , f l o a t , enum, in t and struct { . . . }. To reduce memory consumption, the A S N . l type BOOLEAN is translated into a C type bool which is defined as an unsigned char. l In this thesis, the terminologies C type, C-definition and C-structure are used interchangeably to denote the C-translation of ASN. l type definitions. Also, a word in small caps font, such as INTEGER, indicates that it is a token in ASN. l specifications and a word in type-writer font, such as int, indicates that it is a token in C-programs. 24 CHAPTER 3. DATA TYPE TRANSLATION BETWEEN ASN.l AND C ASN. l Type C Type BOOLEAN bool INTEGER int ENUMERATED enum REAL float BIT STRING BITS OCT STRING OCTS NULL int OBJECT IDENTIFIER OID SEQUENCE { . .. } struct { ...} SET { . ..} struct { ...} SEQUENCE OF LIST* SET OF LIST* CHOICE { . . . } struct { int choice; union { ... } data } CHARACTER STRING TYPE OCTS UNIVERSAL TIME TIME GENERALIZED TIME TIME EXTERNAL EXT ENCRYPTED TYPE BITS Table 3.1: Data-Type Translation between ASN. l and C CHAPTER 3. DATA TYPE TRANSLATION BETWEEN ASN.l AND C 26 typedef unsigned l o n g UNIV; typedef s t r u c t s t r u c t l o n g UNIV } BITS { BITS *next; l e n ; d ata; BITS; /* p o i n t e r t o next BITS node */ /* number of b i t s i n the b i t s t r i n g */ /* p o i n t e r o r value of the b i t s t r i n g */ typedef s t r u c t s t r u c t l o n g UNIV } OCTS { OCTS *next; l e n ; d ata; OCTS; /* p o i n t e r t o next OCTS node */ /* number of o c t e t s i n the o c t e t s t r i n g */ /* p o i n t e r to the o c t e t s t r i n g */ Figure 3.1: C Structure BITS and OCTS Definition 3 . 2 B i t S t r i n g a n d O c t e t S t r i n g T y p e s According to the ASN. l definition, the ASN. l types BIT STRING and OCTET STRING may be in CONSTRUCTOR form. Therefore, they are translated into C types BITS and OCTS respectively which are defined in Figure 3.1. The next field in BITS is a pointer to a BITS structure where another bit string may be stored. The l e n field records the length of the bit string (in number of bits). If the length is no longer than 32 bits, the d a t a field contains the value of the bit string starting from the left-most bit. Otherwise, the d a t a field stores a pointer to an octet-string where the bit string value is stored starting from the left-most bit of the first octet. The three fields in OCTS function the same as those in BITS. Notice that the l e n field contains the number of octets in the octet string and that the data field always keeps an octet-string pointer. CHAPTER 3. DATA TYPE TRANSLATION BETWEEN ASN.l AND C 27 typedef unsigned long UNIV; typedef struct OID { long len; / * number of identifier components < 20*/ int oid[20]; / * object identifier components array */ } OID; Figure 3.2: C Structure OID Definition 3.3 Object Identifier Type The ASN.l type O B J E C T I D E N T I F I E R is translated into a C type OID as defined in Figure 3.2. The two fields oid and len record the object identifier components and its length. In order to statically initialize the oid field, it is defined as an integer array with 20 components. This is based on the assumption that there are no more than 20 components in any object identifier. 3.4 Any Type Since an ASN.l type ANY may represent data of any ASN.l type, it is simply translated into a C type UNIV which is defined as unsigned long. UNIV can be considered a pointer to any C type. 3.5 Sequence and Set Types As explained in Chapter 2, the ASN.l type S E Q U E N C E / S E T contains an ordered/un-ordered list of distinct components ASN.l type. Both S E Q U E N C E { . . . } and S E T { . . . } are translated into the C type struct { . . . } where the "... " are the C definitions of the components ASN.l type in the given S E Q U E N C E or S E T type. The field names within the C-structure are the corresponding names of the components of the ASN.l type. If a component type is O P T I O N A L CHAPTER 3. DATA TYPE TRANSLATION BETWEEN ASN.l AND C 28 or is recursively defined, its corresponding field in the C-structure will be a pointer to the C-definition of that component ASN. l type. If a component is C O M P O N E N T S O F , its C translation will contain more than one field, one for each of the component types' C-translations. In order to simplify the data encode and decode procedures, a multi-level structured type is serialized before being translated. Each of the structured component types is defined as a new type. The corresponding field of the structured type will be re-defined by the new type name. Appendix C contains an example of serializing a multi-level structured ASN. l type. 3.6 Sequence of and Set of Types The A S N . l types S E Q U E N C E O F and S E T O F are translated into a C type LIST which is defined in Figure 3.3. ttdefined unsigned l o n g unit_32; #defined unsigned l o n g UNIV; typedef s t r u c t LIST.ITEM { UNIV *item; /* p o i n t e r t o the l i s t item */ s t r u c t LIST.ITEM *next; /* p o i n t e r t o next l i s t item */ } LIST.ITEM; typedef s t r u c t LLIST { uint_32 count; LIST.ITEM *top; LIST.ITEM *next; } LLIST, *LIST; /* l e n g t h of the l i s t */ /* p o i n t e r t o the f i r s t l i s t item */ /* p o i n t e r t o c u r r e n t l i s t i t em */ Figure 3.3: C Structure LIST Definition Each list item contains the data-value of one component. The item field in the LIST_ITEM is a pointer to the item data value and the next field is a pointer to another list item. In the CHAPTER 3. DATA TYPE TRANSLATION BETWEEN ASN.l AND C 29 LIST structure, the count field records the number of items in the list and the other two fields are pointers to the first and the current item. LIST has been defined as an abstract data type. A number of operations on it have been implemented. For example, ListCreateO creates a new list and ListAppendQ appends a new item to a list. 3.7 Choice Type The ASN.l type C H O I C E is also translated into a C type struct. Since it can be only one of the choices at any instant, the field data is defined as a union to store the value of the current choice. The field choice indicates the type of choice by containing the type-tag. In order to simplify the structure of a C H O I C E type encoder/decoder, sub-field choice is defined as a C type int. It represents an ASN.l type-tag as a 32 bit integer. Three tag components, class, form and identifier-code, are integrated into the 32 bits. The tag-class is represented by the left-most two significant bits. The tag-/orm is represented by the left third bit. This is similar to the tag encoding in BER. However, the remaining 29 bits, starting at the fourth bit, represent the tag-identifier-code as a 29 bit integer. This is based on the assumption that a tag identifier-code is no less than 0 and no greater than 2 2 9 — 1. The ED library utility routine PackTagO converts the three components of an ASN.l-tag into such a "tag-integer" for the choice field. Another ED library utility routine GetTagO extracts the ASN.l tag from the BER octet sequence and converts it into a "tag-integer". Appendix D shows an example of the translation from an ASN.l type C H O I C E into a C-structure. CHAPTER 3. DATA TYPE TRANSLATION BETWEEN ASN.l AND C 30 typedef s t r u c t TIME { i n t year; i n t month; i n t day; i n t hour; i n t minute; f l o a t second; f l o a t d i f f ; i n t zone; #define UTC_Z_TIME 0 #define UTC.D.TIME i #define GNL.Z.TIME 2 #define GNL_D_TIME 3 #define GNL_L_TIME 4 > TIME; /* year : 0 .. " (19** o r **) */ /* month : 1 .. 12 */ /* day : 1 .. 31 */ /* hour : 0 .. 23 */ /* minute: 0 .. 59 */ /* second: 0 .. 59 */ /* d i f f between l o c a l and st a n d a r d time*/ /* time f l a g : (0,1,2,3,4) */ /* UTC time w i t h Z */ /* UTC time w i t h d i f f e r e n t i a l */ /* G e n e r a l i z e time with Z */ /* G e n e r a l i z e time w i t h d i f f e r e n t i a l */ /* G e n e r a l i z e l o c a l time*/ Figure 3.4: C Structure TIME Defini t ion 3.8 UTC Time and Generalized Time Types T h e A S N . l types UNIVERSAL T IME and GENERALIZED T IME are bo th translated into a C type TIME which is denned i n Figure 3.4. T h e second field i n TIME is a f l o a t type which permits the TIME s tructure to represent t ime to the precision of one hundredth of a second. T h e d i f f field contains the difference between the local t ime the s tandard t ime (Greenwich t ime). It is also a f l o a t type, w i t h the integer part containing the differential i n minutes and the fractional part containing the differential in seconds. The zone field indicates the type of the t ime value as denoted by the five constants denned i n Figure 3.4. 3.9 External Type T h e A S N . l type EXTERNAL is translated into a C type EXT which is defined i n Figure 3.5. F i e l d d r e f is equal to NULL i f there is no direct reference. F ie ld i r e f may also be NULL i f the CHAPTER 3. DATA TYPE TRANSLATION BETWEEN ASN.l AND C 31 typedef s t r u c t OID { i n t l e n ; /* number of o i d components < 20 */ i n t o i d [ 2 0 ] ; /* o b j e c t i d e n t i f i e r components */ } OID; typedef s t r u c t CODING { i n t c h o i c e ; union { #define s i n g l e _ a s n l _ $ t a g 0x80000000 OCTS s i n g l e ; /* s i n g l e ASN.l type */ #define o c t e t _ a l i g n e d _ $ t a g 0x80000001 OCTS o c t e t ; /* o c t e t a l i g n e d */ #define a r b i t r a r y _ $ t a g 0x80000002 BITS a r b i t r a r y ; /* a r b i t r a r y */ } dat a } CODING; typedef s t r u c t EXT { OID * d r e f ; /* d i r e c t r e f e r e n c e ( o p t i o n a l ) */ i n t * i r e f ; /* i n d i r e c t r e f e r e n c e ( o p t i o n a l ) */ OCTS *v a l u e ; /* dat a value d e s c r i p t o r ( o p t i o n a l ) */ CODING ed; /* Encode p o l i c y c h o i c e */ } EXT; Figure 3.5: C Structure EXT Definition indirect reference is not available. Field v a l u e contains the data-value descriptor if there is any. Field ed is of C type CODING which contains the chosen encoding policy. 3 . 1 0 D e f i n e d T a g g e d T y p e s Since in ASN.l, all character string types ( N U M E R I C S T R I N G , P R I N T A B L E S T R I N G , T E L E -T E X S T R I N G , V I D E O T E X S T R I N G , V I S I B L E S T R I N G , I A 5 S T R I N G , G R A P H I C S T R I N G and G E N E R -A L S T R I N G ) are defined as tagged O C T E T S T R I N G types, they are all translated into the C type OCTS. For the same reason, the ASN.l type O B J E C T D E S C R I P T O R is translated into the C type CHAPTER 3. DATA TYPE TRANSLATION BETWEEN ASN.l AND C OID a n d the A S N . l t y p e E N C R Y P T E D is t r a n s l a t e d i n t o t h e C t y p e BITS. Chapter 4 T h e E D L i b r a r y D e s i g n a n d I m p l e m e n t a t i o n The ED library is an implementation of the Basic Encoding Rules (BER) in C on UNIX 4.2 BSD. It is based on the ISO 8825, ISO 8825 and their addendums. The CCITT Recom-mendation X.208, X.209 are also referenced. 4.1 The E D Library Design The ED library includes 38 routines for encoding and decoding ASN.l-types. The encod-ing routines translate data-values from C into BER octet-sequences. The decoding routines translate data-values from the BER octet-sequences back to C. Figure 4.1 shows the role of the encoding and decoding routines. The input to the ED library encoding routines and the output of the ED library decoding routines are data of the C-types listed in Table 3.1. The input to the ED library decoding routines and the output of the ED library encoding routines are octet-sequences in BER transfer-syntax. The input octet-sequences to the decoding routines may be stored either in main memory (as a contiguous octet-string) or on disk (as a file). A user must indicate this when the 33 CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 34 C Data-Value (Sender) (Communication Link) BER Octet-Sequence C Data-Value (Receiver) Figure 4.1: Function of Encoding and Decoding Routine octet-sequence is passed to a decoder as a parameter of type IOP. The output octet-sequence of an encoding routine is stored using an IDX structure which can be serialized into a contiguous octet-string by applying the ED library utility routine serlDXO. The definitions of the C structures IDX and IOP are in Section 4.2.1. The ED library routines are classified into four classes: primitive, constructor, utility and memory. The primitive class includes 18 routines which directly encode and decode data-values of primitive ASN.l-types. The constructor class includes 4 routines for constructing the encoders and decoders of structured ASN.l-types. The utility class includes 9 routines which are used to support the structured type encoders and decoders. The memory class includes 11 routines for the ED library sub-memory system operation. For any data-type defined by ASN.l, one can construct an encoder and a decoder using the ED library routines to translate its data-value between C and the BER transfer-syntax. The user manuals for the ED library routines is in [20]. 4.1.1 The E D L i b r a r y U t i l i t y Rout ines There are 10 utility routines in the ED library: Encode_tag(), Decode_tag(), PackTagO, GetTagO, TestTagO, Encode_eoc(), Decode_eoc(), serlDXO, LoadbitsO and LoadoctsQ. Routine Encode_tag() encodes an ASN.l tag from its three components into the BER CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 35 octet sequence. Decode_tag() decodes an ASN.l-type tag from the BER transfer-syntax and compares it with a given tag. Routine PackTagO integrates the three components of an ASN.l tag into a "tag-integer". Routine GetTagO extracts the tag from a BER octet-sequence and converts it into a "tag-integer". TestTagO compares a tag in a BER octet-sequence tag with a given tag and reports whether they match. serlDXO takes an IDX structure as input and serializes its buf fields into a contiguous octet-string. Routine Encode_eoc() creates an IDX structure and stores the end-of-content octets in it. Routine Decode_eoc() decodes the end-of-content octets from a BER octet-sequence. LoadbitsO takes a BITS index structure as input and loads the data-value from disk into main memory. LoadoctsO takes an OCTS index structure as input and loads the data-value from disk into main memory. The user manuals for these routines are in [20]. 4.1.2 Primit ive Type Encoding and Decoding As.shown in Table 4.1.2, an encoding routine and a decoding routine exist in the ED library for each of the listed ASN.l-types. These routines are used directly to convert data-values between C and BER transfer syntax. Detailed information about these routines may be found in their user manuals [20]. 4.1.3 Structured Type Encoding and Decoding To encode or decode the data-value of a structured ASN.l-type, such as S E Q U E N C E { . . . } , S E T { . . . } , S E Q U E N C E O F or S E T O F , one has to construct the encode and decode rou-tines according to the data structures of the given data-value. The ED library construc-tor class routines Encode_struct_beg(), Encode_struct_end(), Decode_struct_beg() and Decode_struct_end() are used in constructing these routines. CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 36 ASN.l Type Encode Routine Name Decode Routine Name BOOLEAN INTEGER BIT STRING OCTET STRING NULL OBJECT IDENTIFIER UNIVERSAL TIME GENERALIZED TIME EXTERNAL Encode_bool() Encode_int() Encode_bits() Encode_octs() Encode_null() Encode_oid() Encode_UTCTime0 Encode_GNLTime() Encode_ext() Decode_bool() Decode_int() Decode_bits() Decode_octs() Decode j i u l l O Decode_oid() Decode_UTCTime() Decode_GNLTime() Decode_ext() Table 4.1: The ED Library Primitive Class Routines When encoding a structured ASN.l-type, Encode_struct_beg() is called first to encode the tag and to set up the structured type encoding environment. Then, the encoder for each component type is called one after another to encode the data-values of the corresponding component types. If a component is a primitive type, its encoder is one of the ED library primitive class routines. If a component type is a constructor type, its encoder will be con-structed in the same way as constructing the encoder for a structured type. If a component type is OPTIONAL, its encoder is called only when the input data contains a value. Each BER octet-sequence of a component type is stored in one IDX structure. A stack STK records the IDX structure pointers of all component types. After the entire structured type is encoded, routine Encode_struct_end() is called to link all the component type IDX structures one after another as they were defined. Encode_struct_end() calculates the structured type content length and encodes the content length octets according to the content length form indicated by a param-eter. For the definite form, an IDX structure is created to store the encoded content length octets and the IDX structure is inserted right after the IDX structure containing the type tag. If the length form is indefinite, both the content length octets and the end-of-content octets are CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 37 stored in IDX structures and linked into the output IDX structures. Constructing the decoder for a structured type is similar to construct its encoder. Routine Decode_struct_beg() is called first. It validates the tag and sets up the decoding environment. T h e n , the decoders of the component types are called one after another to decode the data values of the corresponding element types. T h e primitive component types are decoded by the E D library primitive class routines. T h e structured component types are decoded by the corresponding decoders which are constructed i n the same way as constructing the decoder for a structured type. If the component type is OPTIONAL , the E D library utility routine T e s t T a g O is called to test the tag and determine whether to call its decoder. A stack called LENS records the start-address and the content length of the input B E R octet-sequence. After the entire data-value of a structured type is decoded, Decode_struct_end() is called to pop LENS and verify the end-address of the B E R octet-sequence. T h e decoded data-value is stored i n the corresponding C structure whose memory space is allocated by the decoder. Users are responsible for releasing the memory after using it. A n example of encoding and decoding a structured type is included in A p p e n d i x C . F o r a CHOICE type, the encoder and decoder is constructed of the encoders and decoders of its choices i n a switch statement. Since each of the choices has a distinctive tag, the tag of the input data-value can be used to determine the choice and select the corresponding encoder to encode the data-value. A p p e n d i x D shows an example of encoding and decoding a CHOICE type. T h e "tag-integer" of each choice is defined as a constant with the name of type-name followed by the choice-name followed by a "_$tag". 4.1.4 Tagged Type Encoding and Decoding T h e A S N . l Tagged type is defined as a type with an assigned tag. T h e manuals in [20] showed that the encoding and decoding routines take the tag as the input parameters. There-CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 38 fore, as long as the assigned tag is used for the tag parameters, a tagged type can be encoded by the same encoder of its original type. For the same reason, a tagged type decoder is the same as its original type decoder. The ASN.l character string types are defined as tagged OCTET STRING type. Therefore, they all use the routines Encode_octs() and Decode_octs() to encode and decode their data-values with the specific tags as parameters. For the same reason, the ASN.l type ENUMER-ATED uses Encode_int() and Decode.intO and OBJECT DESCRIPTOR uses Encode_octs() and Decode_octs() as their encoders and decoders respectively. The ENCRYPTED type, de-fined in the CCITT Recommendation only, is a tagged BIT STRING type. Its data-value can be encoded/decoded by the ED library routine Encode_bits() and Decode.bits(). 4 .1.5 Special Feature of Decoding Usually the ED library decoding routines decode the entire data-value from the input octet-sequence into the corresponding C structure in main memory. However, there is an alternative for decoding data of BIT STRING or OCTET STRING type. When the input transfer-syntax is in CONSTRUCTOR form of BIT STRING or OCTET STRING type, it usually contains a large data-value. It may not be necessary to decode the entire constructor into main memory. Therefore, when the input data is from a file and is in CONSTRUCTOR form of BIT STRING or OCTET STRING type, Decode_bits() and Decode_octs() only decode the structure of the input data-value and store indices in the C structures BITS or OCTS. The indices are based on the input file. The data field in C structure BITS or OCTS records the input file name and the len field records the data offset in the file. These BITS or OCTS indices can be converted into real data-values by applying the ED library utility routine LoadbitsO or LoadoctsO to load the whole data-value from the file into C structure BITS or OCTS in main memory. The implementation details of CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 39 BIT STRING and OCTET STRING decoding and loading may be found in Section 4.2.2. The advantage of this special feature is to provide users with a means of decoding data in an efficient way. Since decoding a large data-values takes a long time and consumes a large amount of memory in copying the data-values, it is much more efficient to leave the data-value in the file and only extract its data-structure as needed. 4.1.6 T h e A N Y T y p e Encod ing and Decoding The ASN.l ANY type is defined as a representation of any types denned by ASN.l. Both its data-type and its data-value are indefinite and non-determined. Therefore, there is no particular encoder or decoder for ASN.l ANY type. However, since any instance of ANY type is an ASN.l-type, one can always use the ED library routines to construct the encoder and decoder for a particular instance of ANY type. 4.1.7 T h e R E A L T y p e Encod ing and Decoding The ED library should have routines Encode_real() and Decode_real() to encode and decode data-val lies of ASN.l REAL type. However, in the current implementation it is not supported. 4.2 The ED Library Implementation The ED library has been implemented in the C on UNIX 4.2 BSD. The source consists of about 3,400 lines of C code. The binary is about 10K bytes. CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 40 4.2.1 T h e E D Library Data Structures Data Structure IOP The input BER octet-sequence to a decoding routine may be stored either in main memory or on disk. Users must indicate this in the parameter of type IOP when passing a BER octet-sequence as input into a decoding routine. The structure IOP is defined in Figure 4.2. The b field stores the pointer to the input octet-sequence if the octet-sequence is from main memory, otherwise it is NULL. If the input octet-sequence is from a file, the f field stores the file pointer and the fname field stores the file name. Otherwise both f and fname are NULL. All decoding routines test the f field first. If it is NULL, the input octet-sequence will be considered as a contiguous octet-string from main memory. typedef unsigned char byte; typedef s t r u c t IOP •c byte *b; /* p o i n t e r t o an o c t e t s t r i n g */ FILE * f ; /* p o i n t e r t o a f i l e */ byte fname[30]; /* f i l e name with max len=30 */ } IOP; Figure 4.2: C Structure IOP Definition Data Structure IDX The data structure IDX is defined in Figure 4.3. It is designed to store the output octet-sequence of the encoding routines. It is also used in the ED library sub-memory system. The IDX buf field stores a pointer to an octet-string. The l e n field stores the length of the octet-CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 41 typedef unsigned char byte; typedef s t r u c t IDX { by t e * buf; /* p o i n t e r t o an o c t e t s t r i n g */ l o n g l e n ; /* l e n g t h of the o c t e t s t r i n g buf */ s t r u c t IDX *next; /* p o i n t e r t o next IDX node */ } IDX, *ptrIDX; Figure 4.3: C Structure IDX Definition string in the buf field. The next field points to another IDX structure. When encoding a structured ASN.l-type, one does not know its content length until the entire structure is encoded. According to BER, the content length octets should be in front of the content octets in the encoded BER octet-sequence. Because it is possible that the content length octets consist of more than one octet, the encoded octet-sequence should be stored in a data structure whose space can be dynamically extended. The IDX structure, as a linked list, can dynamically extend its space using the next field. For each structured ASN.l-type, its encoder calls routine Encode_tag() to encode the tag and store the encoded octets in one IDX structure. All encoded component octets are stored in the IDX structures and these IDX structures are linked together as they are defined. After the entire data structure is encoded, an IDX structure is created to store the content length and inserted into the encoded octet-sequence right after the IDX structure containing the tag. The octet-sequence stored in the buf fields of an IDX structure link can be serialized into a contiguous octet-string by applying the ED library utility routine s e r l D X O . CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 42 IDXptr S[STACK.SIZE]; IDX **STK = (IDX *) S; /* st a c k f o r IDX p o i n t e r s */ l o n g S_LEN[STACK.SIZE]; /* st a c k f o r o c t e t sequence */ l o n g *LENS = ( l o n g *) S_LEN; /* address and l e n g t h */ Figure 4.4: The ED Library Stack Definition The E D Library Internal Stacks There are two internal stacks in the ED library, STK and LENS. Their definitions are in Figure 4.4. Stack STK records the IDX structure pointers during a structured data encoding. Stack LENS records the input octet-sequence address and content length during a data decoding. Both STK and LENS are implemented as abstract data types. A number of operations on the two stacks have been implemented. XINITO initiates stack STK. XPUSHO and XPOPO manipulate the STK pointer and data-values. XTOPO or XB0TT0MO reads the data-value from STK top or bottom respectively. Operation L I N I T O , LPUSHQ , LPOPQ , LTOPO and LB0TT0MO are the corresponding functions for LENS. LPLUSO increments the LENS stack pointer by the value of a given parameter. 4.2.2 T h e E D L i b r a r y R o u t i n e s The implementation of most ED library routines is straightforward. The primitive routines simply translate data of certain ASN.l-types between the C representations and the BER octet-sequences. The constructor routines are supported by some internal data structures. CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 43 Encode^struct_beg() and Encode_struct_end() Encode_struct_beg() sets up a structured type encoding environment. It turns on the structured type flag STRUCT, which is a global variable, to indicate that the following proce-dures are encoding the structured type components. It creates an IDX structure to store the tag and pushes the pointer to the structured type onto stack STK. The encoded component type octet-sequences are also stored in IDX structures and their pointers are also pushed onto stack STK. When the entire data-value of a structured type has been encoded, Encode jstruct_end() is called to complete the structured type decoding. Encode_struct_end() pops stack STK and links all the element-type IDX structures together as they are defined. It also calculates the structured type content-length by summing the octet-sequence length of all element-types. Depending on the required length form which is indicated by one of its parameters, Encode_struct_end() creates new IDX structures for storing the content length octets and inserts these IDX struc-tures into the encoded octet-sequence. The structured type flag STRUCT is turned off when Encode_struct_end() returns. Decode_struct_beg() and Decode_struct_end() Decode_struct_beg() sets up a structured type decoding environment. It checks the tag of the input BER octet-sequence, extracts its content length and pushes the input octet-sequence address and the content length onto stack LENS. After the entire data-value of a structured type is decoded, the routine Decodej3truct_end() is called to complete the decod-ing. Decode_struct_end() pops the stack LENS and validates the octet-sequences end-address by comparing it with the sum of the corresponding starting address and content length. Error messages will be printed if they do not match. CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 44 Loadocts() and Loadbi t sQ As mentioned in Section 4.1.5, routines Decode.octsO and Decode_bits() use a special way of decoding ASN.l BIT STRING or OCT STRING data-values when the input BER octet-sequence is in CONSTRUCTOR form and is from a file. They only decode the data structure and save indices in the C-type OCTS or BITS. When OCTS or BITS stores the data structure indices, each node stores the index of one piece of the string. Its data field stores the input file name and its len field stores the offset of the string value in the input file. Later, a string data-value can be load from the input file into a C-type BITS or OCTS respectively by applying the ED library utility routines LoadoctsO or LoadbitsO. Routine LoadbitsO and LoadoctsO take a BITS or OCTS index structure as a parameter, respectively. They open the data file whose name is stored in the BITS or OCTS data field, move the file pointer to the offset indicated by the len field, and load the octet-sequence from the file into main memory. The decoded, string value is stored in the data field, replacing the file name, and the string length is stored in the len field replacing the string offset. Before loading a data-value from a file into main memory, LoadbitsO and LoadoctsO verify the input BITS and OCTS respectively. If the file specified by the fname field does exist, it is considered a correct index structure. Otherwise, an error message will be printed. Detailed information can be found in the ED library user manuals in [20]. 4.2.3 The E D Library Sub-memory System Since the data encoding and decoding are integral parts of every data transfer, their effi-ciency affect the overall system performance. Therefore, a great amount of effort has been made to make the ED library implementation efficient. The ED library sub-memory system is an ex-CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 45 ample. In the C language, the system calls for memory allocation are very time-consuming. To speed up the ED library, a sub-memory system was built to support memory operations in a more efficient manner. The sub-memory system is composed of two memory pools, a free IDX pool and a free octet pool. The free IDX pool is a linked list of unused IDX nodes. Their buf fields are NULL. The free octet pool is also a linked list of IDX structure. The buf fields in these IDX nodes point to unused buffer blocks. Routine INITMEMO sets up the sub-memory system and initializes the two pools. The initial memory space of the two pools, 100 IDX nodes for the free IDX pool and 4K octets for the free octet pool, are allocated at compile time. The space in the two memory pools is dynamically extended when necessary. Routines INITIDXO, NEWIDXO, GETIDXO and FREEIDXO are the sub-memory system op-erations for IDX nodes. INITIDXO initializes the free IDX pool by resetting the memory space of the IDX linked list. GETIDXO allocates an IDX node to the user. It removes the first node in the free IDX pool and returns its pointer. If the free IDX pool is used up, it calls NEWIDXO to obtain one more block of memory space from system for the free IDX pool. FREEIDXO release IDX nodes by returning them to the free IDX pool. Routines INITBUFO, NEWBUF (), GETBUF ( ) , FREEBUF () and SQZBUFO are the sub-memory system operations for octets. INITBUFO creates the free octet pool head node and allocates a block of octets to it. GETBUF () allocates memory space to the user. It goes through the free octet pool to get the first-fit memory segment and returns its pointer. If there is no memory segment in the free octet pool large enough, routine SQZBUFO is called to compress them and try again. If there is still no room, the routine NEWBUF () is called to extend the free octet pool by obtaining a new block of octets from the system. FREEBUF () releases memory space by CHAPTER 4. THE ED LIBRARY DESIGN AND IMPLEMENTATION 46 returning space to the free octet pool. To reduce the work of system garbage collection, routine RESETMEMQ has been implemented to release all memory space allocated by routine GETIDXO and GETBUFO and to reset the sub-memory system. These memory operations are very cheap. Most operations simply modify the pointers in the corresponding memory pools. Detailed information is in the user the manual of the ED library routines [21]. 4.3 Using the ED Library Routines All the ED library routines are C procedures. They depend on two include files, defs . h and element.h, which define the ED library internal data structures and constants. A user program should include the two header files when using any of the ED library routines. The ED library should be included when loading the user program. Chapter 5 T h e C A S N l D e s i g n a n d I m p l e m e n t a t i o n Currently, many protocol standards are specified in a certain protocol specification lan-guage, such as ASN.l, Estelle, etc. To implement a protocol, a programmer has to spend a significant amount of effort in translating the protocol definition from the protocol specification language into a protocol implementation language such as C, PASCAL, etc. To achieve the goal of exchanging data in a heterogeneous computing environment, the encoders/decoders for the protocol defined data-types must be constructed as well. However, this type of translation and implementation are usually tedious, time consuming, and error prone. It would be very convenient if a software package could automatically fulfill these arduous work. Motivated by this idea, an ASN.l-C compiler, named CASNl, has been designed. CASNl compiles a protocol ASN.l-specification into the corresponding C-definitions, and automatically generates the BER encoders/decoders for all compiled data-types. The encoders/decoders generated by CASNl use the encoding and decoding routines of the ED library. CASNl has been implemented in C on UNIX 4.2 BSD using YACC and LEX as tools. It is based on ISO 8824 ASN.l-definition, ISO 8825 BER-definition and their addendums. The CCITT recommendation X.208 and X.209 47 CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 48 are also referenced. 5 . 1 The C A S N l Design CASNl has been designed and implemented as a three pass compiler. The interfaces and functions of each pass are presented bellow. 5.1.1 The Interfaces of CASNl As shown in Figure 5.1, CASNl has both internal interfaces and the external user interfaces. Users only need to use the external interfaces. C A S N l E x t e r n a l I n t e r f a c e In the current version, the input of CASNl is a file containing a single ASN.l module. For multi-module ASN.l-specifications, CASNl requires each module to be stored in one file and to be compiled separately. CASNl generates four output files: * . d e f s . c , * . e n c o d e . c , * . d e c o d e . c and * . i n i t . c , where the * in these file names denotes the input ASN.l module name1. File * . d e f s .c contains the C translation of the input ASN.l module and the type-definitions of the encode/decode procedures for every data-type. It will be included by the communication software as a header file. File * . e n c o d e . c contains the C-code of data-type encoding routines. File * . d e c o d e . c contains the C-code of data-type decoding routines. File * . i n i t . c contains the C-code of an initialization routine which will be invoked by the communication software to initialize the environment for encoding and decoding routines. 1For example, if the input ASN.l-specification module name is VTP, the output files are named in VTP.defs .c, VTP.encode.c, VTP.decode.c and VTP . init .c . Notice that it is the input ASN.l specification module name which is used, rather than the name of the input file containing the ASN.l module definition. CHAPTER 5. THE CASN1 DESIGN AND IMPLEMENTATION 49 input : ASN.l Module Definition CASN1 ( The J File outl i r Second Pass 1 r File out2 r The Third Pass File *.defs.c File passl File p a s s 3 File *.encode.c File *.decode.c File *.init.c Figure 5.1: The Interfaces of CASNl CHAPTER 5. THE CASN1 DESIGN AND IMPLEMENTATION 50 Besides the above four C files, CASNl generates two other compilation diagnosis files p a s s l and pass3. They are the execution scripts of the first and third passes of CASNl, respectively. pass3 also includes some statistic information for the input ASN.l module, such as the name of the input ASN.l module, the names of all referenced ASN.l modules and a type table. The type table contains the names, the tags and the tag integer values of all defined types. While parsing the input data, if any syntax error is detected, CASNl raises an exception and stops. The exception message reports the error and prints the error line number. C A S N l Internal Interfaces CASNl translates an ASN.l-specification into C-code by three passes. The output of the first two passes are stored in files o u t l and out2 which are used as the input to the next pass respectively. 5.1.2 The Functions of C A S N l The first two passes function as pre-processors to simplify the input ASN.l specification for the third pass. C A S N l First pass The first pass takes an ASN.l module definition in as input and parses it. If any syntax error is detected, CASNl stops and reports the error with its line number. In an ASN.l structured type definition, each component is defined by a named-type or a sub-structure. It may or may not have a reference name2. To simplify the generation of data-type encoders/decoders, the first pass serializes the nested structured type-definitions in the 2 I n t h i s thes is , t h e t ypes of s t r u c t u r e d t y p e c o m p o n e n t s a re referred as component types, sub-types, child types; t h e reference n a m e s of s t r u c t u r e d t y p e c o m p o n e n t s are re fer red as field names. CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 51 input ASN.l specification. It defines each sub-structure as a new type and assigns a name to it. An assigned type name consists of a character "T" followed by at least one digit. Then the structured type is re-defined by using the newly assigned sub-type names in the corresponding component definitions. Appendix C shows an example of serializing a nested structured type. In a structured type definition, if any component field name absents, the first pass will assign a field name to it. An assigned field name consists of a character "r" followed by at least one digit. The reason of filling in all field names is that they are going to be used as the component variable names when the structured type is translated into C. In order for CASNl to generate C-code properly, the first pass moves the ASN.l key word OPTIONAL to the front of the component-type definition. Special lines are inserted between type-definitions to mark type-definition boundaries. C A S N l Second pass In C language, type declarations obey the bottom-up order, i.e., a type has to be defined before being referenced. While in ASN.l, the type declaration order is not clearly specified although many standards adopt the common convention of top-down order, i.e., parent types are specified before their component child-types. Because of the above, CASNl assumes that the input ASN.l specification obeys the conventional top-down order in type-definitions. To simplify the type-definition translation from ASN.l into C, the second pass inverses the top-down type-definition order of the ASN.l-specification to the C-style bottom-up order, according to the special lines among type-definitions which are inseted by the first pass. Violations of top-down type-definition order in the input ASN.l module result in errors being reported in the third passes. CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 52 C A S N l Third pass The third pass does a various of error checking and generates the C code. It takes the second pass output as the input, parses it and checks the following: 1. a type must be defined before it is referenced, e.g., the component types of a structured type must be denned before the structured type definition; 2. all referenced types must be defined in current module or imported from other modules; 3. each choice of a CHOICE type must have a distinctive tag; 4. a SELECTION type must be defined by a CHOICE type and its identifier must be the name of one of the choices. 5. a COMPONENTS OF type must be defined by a structured ASN.l type, such as SE-QUENCE { . . . } or SET { ... }. If any error is detected, the third pass reports the error with its line number in file outl and aborts the compilation. CASNl does not handle cross-module references. It prints a warning message for every external type reference to let users deal with them. If the compilation succeeds, the third pass generates the C-code for data-type definitions and their encoders/decoders in four output files * .def s. c, * . encode. c, * .decode .c and * . in i t . c. All type-definitions and constants are translated into C in file *.defs.c. Type-tags are pre-sented as comments in C type-definitions. Type names and structured type field names remain unchanged. A BER encoder and a BER decoder are generated for each of the compiled types and are stored in files *.encode.c and *.decode.c, respectively. The ASN.l comments are translated into C comments and are inserted in files *. def s. c, *. encode. c and *.decode. c. CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 53 For every C H O I C E type, the third pass defines the tag integer values of all choice tags as con-stants in file * . d e f s . c. The name of such a constant is constructed with the type name followed by the choice name and followed by "$tag". The third pass translates an ASN.l value-definition into a C variable-declaration in file • . i n i t . c . The value-identifiers are used as variable names. These variables are statically initialized by the defined values. An ASN.l value-definition is processed only when its C-translation type can be staticly initialized. 5.1.3 Modification to ASN.l Syntax The ASN.l macro-definition can dynamically extend ASN.l syntax rules. There is nothing to prevent such extension from introducing infinite syntax reductions into existing syntax rules. To handle ASN.l macro-definitions, an ASN.l compiler must have the ability to dynamically extend its syntax rules while parsing the ASN.l specification. It is a very complex problem to design a dynamically extendible parser which guarantees that no infinite reduction occurs. As a result, the current version of CASNl ignores macro-definitions for simplicity. In many cases, ASN.l macro-definitions are used to define operations. After removing macro-definitions from ASN.l, we have introduced OPERATlON-definition and ERROR-definition into CASNl syntax for specifying abstract-operations. Figure 5.2 gives the syntax rules of both definitions. It is part of the BNF definition of CASNl syntax rules. The complete BNF specification of the CASNl syntax rules is given in Appendix B. According to Figure 5.2, an operation is identified by an operation name which is defined as an identif ier and is assigned a number. Operation arguments, as well as operation results, are defined by ASN.l-types. Errors of each operation are defined by a list of error identifiers. An ERROR-definition is similar to an OPERATlON-definition. An error is identified by an error CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 54 Operatic-nDef i n i t i o n OperationName OperationTypeNotation R e s u l t E r r o r s ErrorNames E r r o r D e f i n i t i o n ErrorName E r r o r T y p e N o t a t i o n NamedType I d e n t i f i e r L i s t OperationName OPERATION OperationTypeNotation "::=" number i d e n t i f i e r empty I "ARGUMENT" NamedType R e s u l t E r r o r s empty I "RESULT" NamedType empty I "ERRORS" "{" ErrorNames "}" empty I I d e n t i f i e r L i s t ErrorName "ERROR" E r r o r T y p e N o t a t i o n "::=" number i d e n t i f i e r empty I "PARAMETER" NamedType i d e n t i f i e r Type I Type i d e n t i f i e r I I d e n t i f i e r L i s t "," i d e n t i f i e r Figure 5.2: BNF of O P E R A T I O N Definition and E R R O R Definition CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 55 name which is denned as an i d e n t i f i e r and is assigned a number. The error parameters are defined by ASN.l-types. For O P E R A T I O N definitions and ERROR-definitions, CASNl translates operation arguments, results and error parameters into the corresponding C type definitions in file * . d e f s . c . Their encoders and decoders are also generated in files * .encode.c and * .decode.c. As specified in Figure 5.2, operation names and error names are defined as numbers in file * . d e f s . c . For each operation, the operation name is used as the index for locating the operation argument encoders/decoders in tables EncodeArgument and DecodeArgument, the operation result en-coders/decoders in tables EncodeResult and DecodeResult, and the operation error names in table E r r o r l d s . The error names in table E r r o r l D s can be used as indices to locate the error parameter encoders/decoders in tables EncodeError and DecodeError. Besides ignoring macro-definitions and extending O P E R A T I O N definition and E R R O R defini-tion, some equivalent changes have also been made when using ASN.l syntax definitions in CASNl in order to minimize syntax definition conflicts. These may be found by comparing the BNF of ASN.l syntax definitions and CASNl syntax definitions included in Appendix B and Appendix A. 5 .2 The C A S N l Implementation The ASN1-C compiler, CASNl, has been implemented in C on UNIX 4.2 BSD with YACC and LEX tools. The source consists of about 5,600 lines of C program and the binary is about 34k bytes. CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 56 5.2.1 T h e F i r s t pass The first pass is a parser for the ASN.l-specification. It pre-processes the input ASN.l-specification and generates the input data for the second pass in the file outl. The first pass maintains two internal objects: a data buffer srcbuf and a stack stk. All tokens from the lexical analyzer are stored in srcbuf while parsing the input data. Whenever a type-definition has been parsed, either as a top-level type-definition or as a component type definition within a structured type-definition, the data in srcbuf is transferred to stk and srcbuf is re-initialized. A top-level type definition is always pushed onto the bottom level of stk — level 0. A component type-definition is pushed onto upper levels of stk. If a component-type is also a structured type, its children type-definitions are pushed onto the one level upper above its parent type-definition. If a component-type is OPTIONAL, the key word OPTIONAL is moved to the front of the component type definition while transferring the data from srcbuf to stk. After a complete type-definition is parsed, the first pass pops off stk to generate the output data in file outl. Each of the structured component types is defined as a new type and is assigned a new type name. The corresponding component type-definitions within the parent type-definitions are replaced by the newly defined component type names. To fill the absent field names of a structured type and to assign newly defined component-type names, one field of stk has been defined as an integer to count the component-type numbers. A field name is constructed by a character "r" followed by the pointer number of stk and then followed by the component type number. A newly defined component-type name is constructed in the similar manner: a character "T" followed by the stk pointer number and then followed by the component-type number. The first pass replaces all hyphens ("-") in the input data by under-lines ("_") because C CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 57 language does not allow hyphens ("-") in type or variable names. To keep track of the input data, a variable LineCounter is denned in the lexical analyzer. Whenever a token of c h a r a c t e r r e t u r n is analyzed, the LineCounter is increased by one. The value of LineCounter is used for reporting error positions in exception messages. The last task of the first pass is to insert a special line, between every two type-definitions in the input ASN.l module. Each pair of special lines marks the boundary of a type-definition in file o u t l . The lexical analyzer and the parser of the first pass are implemented with the UNIX tools LEX and YACC. The parser has 466 states and consists of 287 grammar rules, with 86 terminals and 140 non-terminals. The source consists of about 2,000 lines of C-code and the binary is about 12K bytes. 5.2.2 The Second pass The second pass inverses the type definition order of the ASN.l specification. It is imple-mented as a simple C program. It takes file o u t l as input and reads the data line by line. The type-definition between each pair of the special lines which were inserted by the first pass is viewed as a single data block. The offsets of these data blocks are recorded in a list. Then the second pass copies these data blocks into file out2 in the inverse order using the recorded offsets. The second pass implementation consists of 154 lines C program which is about 3.3K in binary. CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 58 5.2.3 T h e T h i r d pass The third pass does the "real" translation from the ASN.l specification into C-defmitions and generates the encoders and decoders for all compiled types. It takes the pre-processed ASN.l-specification in file out2 as its input, and generates the C-code in four files: *.defs.c, *.encode.c, *.decode.c and *.init.c. The CASNl third pass defines several internal data structures for generating C-definitions and their corresponding encoders and decoders: State Stack The state stack stk is defined for recording the information of type-definitions, including type name, tag, structure flag, etc. The stack pointer starts from level 0 — the stack bottom, and is increased whenever a structured type is parsed. The stack is used when generating the C-definitions and encoders/decoders for the compiled data-types. Type Table The type table is an array of records for recording all compiled type names, tags, and offsets in the files f.defs.c, *.encode.c and *.decode.c. It is used for detecting redundant type names and for checking type reference relations. The offsets are used for generating the C code for ASN.l types SELECTION and COMPONENTS OF. Reference Type Table The reference type table is an array for recording referenced type names in the ASN.l module. It is used for detecting undefined reference types. CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 5 9 Module Table The m o d u l e t a b l e is a n a r r a y for r e c o r d i n g m o d u l e names of the i n p u t m o d u l e a n d a l l referenced modules. Operation Table The o p e r a t i o n t a b l e is a n a r r a y of records for r e c o r d i n g a b s t r a c t - o p e r a t i o n names, numbers a n d e n c o d i n g / d e c o d i n g r o u t i n e names for o p e r a t i o n a r g u m e n t s a n d results. It is used for g e n e r a t i n g the s y s t e m i n i t i a l i z a t i o n r o u t i n e i n o u t p u t file f.init.c. Error Table The e r r o r t a b l e is a n a r r a y of records for r e c o r d i n g e r r o r names, numbers, a n d the error p a r a m e t e r e n c o d i n g / d e c o d i n g r o u t i n e names. It is used for g e n e r a t i n g the s y s t e m i n i t i a l i z a t i o n r o u t i n e i n o u t p u t file f.init.c. With these i n t e r n a l d a t a s t r u c t u r e s , the t h i r d pass does the various of error c h e c k i n g a n d generates C-code for d a t a - t y p e de f i n i t i o n s a n d t h e i r e ncode/decode routines. It parses the i n p u t data, stores the i n p u t m o d u l e n ame a n d a l l i M P O R T e d m o d u l e names i n the module-table. It also stores the I MPORTed t y p e names i n the type-table. For a t y p e - d e f i n i t i o n , the type-tag, f o r m (either EXPLICIT or IMPLICIT) a n d s t r u c t u r e (either p r i m i t i v e or c o n s t r u c t o r ) are recorded i n the s t a t e s t a c k stk. Similar t o the first pass, a t o p - l e v e l t y p e d e f i n i t i o n is p u s h e d o n t o the b o t t o m - l e v e l of s t a c k stk a n d its c o m p o n e n t ty p e de f i n i t i o n s are p u s h e d o n t o the u p p e r levels. Since the first pass a l r e a d y s e r i a l i z e d the nested s t r u c t u r e d t y p e d e f i n i t i o n s , the l e v e l of the state stack stk s h o u l d never be greater t h a n 3. Whenever a c omplete type d e f i n i t i o n has been parsed, the t h i r d pass saves the t y p e name, t a g a n d offsets of the C-code i n c o r r e s p o n d i n g o u t p u t files CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 6 0 in the type-table. Redundant type names are detected by checking through the existing type names in the type-table when adding a new type to it. If a type is defined by a named-type, the named-type will be stored in the reference type-table. If a named-type is an external type3, the external module name will be stored in the module-table and a warning message will be printed to report the cross-module reference. If the named-type is not an external type and its name cannot be found in the type-table, an error message is printed to report reference error because in C a type must be defined before it is referenced. When parsing a CHOICE type-definition, the third pass checks the type-table to guarantee that all the choices have distinguish tags. For an ASN.l SELECTION type-definition, the third pass checks the type-table to guarantee that it is defined by a CHOICE type and the IDENTIFIER is one of the choices. Its C-code are generated by copying the corresponding choice's C-translation from files *. def s. c, *. encode. c and * .decode.c. The file offsets of the choice can be found in the type-table. An ASN.l COMPONENTS OF type-definition is translated in the similar way. The third pass checks the type-table to guarantee that it is defined by a structured type and then generates its C-code by copying the C-code of all components from files * . d e f s . c , *.encode.c and * .decode.c. Again, the file offsets of the component-types can be found in the type-table. A recursively structured type-definition can also be detected by checking through the type-table. A recursive component-type, as well as the OPTIONAL component-type, is translated into a pointer of the corresponding C type. For an OPERATlON-definition, the third pass stores the operation name, number, the encoder and decoder names of the operation arguments and results, and the operation error identifiers in the operation table. It generates C-definitions for operation argument and result types in file 3External type is a type denned in another ASN. l module CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 61 *. defs. c. It also generates the encoders and decoders for the argument and result types in files *.encoder.c and *.decode.c. The third pass does the similar things for an ERROR definition. It stores the error name, number and the names of error parameter encoders/decoders in the error table and generates C-definitions for error parameter types in file *. defs. c. The encoding and decoding routines for the error parameters are also generated in files *. encode. c and *.decode.c. After an complete input ASN.l module is parsed, the third pass generates a system ini-tialization routine INITSYSO in file *.init.c. It checks the operation table and error ta-ble to construct routine INITSYSO for initializing system data structures EncodeArgument, DecodeArgument, EncodeResult, DecodeResult, EncodeParameter, DecodeParameter and Errorlds. The third pass prints the type table and the module table in file pass3. It also checks un-defined reference types by comparing the types in the reference type table and the type table. The lexical analyzer and the parser of the third pass are implemented with the UNIX LEX and YACC tools. The parser has 492 states and consists of 310 grammar rules, with 86 terminals and 162 non-terminals. The source consists of about 3,600 lines of C-code and the binary is about 19.K" bytes. 5 . 3 U s i n g t h e C A S N l O u t p u t Since CASNl syntax is a sub- and super-set of ASN.l syntax, users may need to modify the ASN.l-specifications before inputing them to CASNl. All macro-definitions in the ASN.l specification should be replaced with OPERATlON-definitions and ERROR-definitions. Macro-definitions may be simply marked out as comments if they can not be properly changed to CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 6 2 OPERATION and ERROR-definitions. Command casnl at UNIX shell level invokes CASNl. The first argument is used as the input file name. The output files are generated under directory ./out. After CASNl compilation succeed, user programs should include the output file *.defs.c as a header file and invoke the routine INITSYSO, defined in file f.init.c, at the beginning to initialize the environment. Data-types defined in the file * .def s. c may be used by user programs to declare variables. The encoders and decoders defined in files *. encode. c and *. decode. c can be invoked to encode and decode the data-value of the corresponding types. User programs should be compiled together with the object-code of files * . encode. c, *. decode. c, * . init. c and the ED library. Figure 5.3 shows how to use the CASNl output in user programs. Detailed information may be found in [21]. CHAPTER 5. THE CASNl DESIGN AND IMPLEMENTATION 63 Application Program C Compiler CC-C 1 r Executable Code r File *.init.c File *.encode.c File *.decode.c File » .defs.c r r r Figure 5.3: Using CASNl Output Chapter 6 P e r f o r m a n c e a n d A p p l i c a t i o n s This chapter presents the performance profile1 of the ED library routines. Because the performance profiling data of related work is not available, the conjecture that the ED library provides better efficiency can only be justified by structural analysis and comparison as discussed in Section 1.3, rather than by comparing performance profiling data. The results of CASNl applications are also given in this chapter. 6.1 T h e E D L i b r a r y Performance As mentioned in previous chapters, efficiency has been placed as the top priority in the ED library design and implementation. To profile the performance for the ED library routines, three ASN.l-types are chosen: 1. The OCTET STRING type is a primitive type defined in ASN.l. It is chosen because it is frequently used and has a simple structure. 1 Performance profiling is a method used to determine the amount of time and storage a program consumed. Interested readers may refer to "Fundamentals of Computer Algorithms", by E. Horowitz and S. Sahni, Computer Science Press, 1978. 6 4 CHAPTER 6. PERFORMANCE AND APPLICATIONS 65 2. The BASICVTPlTEM type specified in the ISO Virtual Terminal Protocol (VTP) [11] is an ASN.l CHOICE type. It has a very complicated structure. In the VTP implementation [17], the data-structure of the BASICV T PITEM expands as the input data length increases. This type was chosen because of the special data structure results in special complexity in its data encoding and decoding. 3. The PERSONNELRECORD type is defined as an example in many standards, such as ISO ASN.l , BER and CCITT X.409, X.208 and X209. It is a structured type consisting of three constructors. The definition of PERSONNELRECORD is included in Appendix E. The experiments of performance profiling were conducted on a SUN 3/260 under UNIX 4.2 BSD. The tested routines were compiled by the UNIX command cc -pg. The pg option automatically generates a file gmon.out to record the procedure invocation performance data. A test program was written to call the encoder/decoder 5,000 times for each input. The average number of milliseconds spent per-execution of the encoder (including S e r l D X O ) and decoder are shown in the Table 6.1. In our context, the storage complexity of the encoder/decoder is interpreted as octet-complexity which is measured in the number of extra octets used for carrying the type informa-tion of the data-value being encoded. The more octets used in carrying the type information for a particular data-type as its value/size grows, the higher the encoder's octet-complexity is for encoding that data-type, and the less efficient the data-transfer will be when the data-value is transmitted. By varying the input data-value size for each of the above chosen data-types, we have the following observations: 1. The octet-complexity for encoding an OCTET STRING is approximately constant as shown in Table 6.2 and Figure 6.1. The stair cases indicate that more octets are needed to CHAPTER 6. PERFORMANCE AND APPLICATIONS 66 Input Encode Encode Encoder SerlDX Encode Decode Data type Input Output Time + Time = Time Time Octet Octet (msec) (msec) (msec) (msec) 1 5 0.14 + 0.07 = 0.21 0.25 10 14 0.18 + 0.11 = 0.29 0.26 100 104 0.52 + 0.34 = 0.86 0.64 200 205 0.94 + 0.55 = 1.49 0.80 300 306 1.36 + 0.74 = 2.10 1.05 OCTET STRING 500 506 2.22 + 1.20 = 3.42 1.21 1000 1006 3.74 + 2.38 = 6.12 2.05 3275 3281 12.74 + 7.09 = 19.83 5.54 5000 5006 19.06 + 11.27 = 30.33 9.59 10000 10006 38.30 + 22.35 = 60.65 18.85 30000 30006 115.78 + 68.73 = 184.51 57.65 1 20 3.37 + 0.43 = 3.80 3.57 10 47 4.49 + 0.77 = 5.26 6.22 50 171 10.48 + 1.84 = 12.32 16.18 100 325 17.72 + 3.93 = 21.65 27.01 B A S I CV T P I T E M 500 1525 80.10 + 18.20 = 98.30 125.27 1000 3025 163.09 + 36.47 = 199.56 259.71 2000 6025 336.37 + 73.52 = 409.89 549.62 3275 9850 608.74 + 130.03 = 738.77 941.60 4000 12025 776.38 + 159.03 = 935.41 1206.64 5000 15025 996.58 + 197.53 = 1194.11 1635.55 75 136 4.30 + 1.10 = 5.40 4.49 475 541 5.71 + 2.00 = 7.71 5.85 PERSONNELRECORD 1275 1341 9.12 + 3.70 = 12.82 9.15 3275 3341 17.30 + 8.69 = 25.99 17.03 5000 5066 23.95 + 12.35 = 36.30 23.05 10000 10066 44.79 + 23.95 = 68.74 43.22 Table 6.1: The ED Library Performance CHAPTER 6. PERFORMANCE AND APPLICATIONS 67 represent the BER octet sequence content length as the input data length increases. Input (octet) 1 127 128 255 256 500 1000 2000 30000 Output (octet) 5 131 133 260 262 506 1006 2006 30006 Overhead (octet) 4 4 5 5 6 6 6 6 6 Table 6.2: OCTET STRING Encode Octet Complexity 2. The octet-complexity for encoding a BASICV T PITEM type is approximately linear as shown in Table 6.3 and Figure 6.2. Input (octet) 1 10 50 100 500 1000 2000 3275 4000 5000 Output (octet) 20 47 171 325 1525 3025 6025 9850 12025 15025 Overhead (octet) 19 37 121 225 1025 2025 4025 6575 8025 10025 Table 6.3: BASICV T PITEM Encode Octet Complexity 3. The octet-complexity for encoding a PERSONNELRECORD is also approximately constant as shown in Table 6.4 and Figure 6.3. Notice that the minimum size of a PERSONNELRECORD data is 75. Input (octet) 75 187 197 199 314 327 500 1000 5000 10000 Output (octet) 136 249 260 263 379 393 566 1066 5066 10066 Overhead (octet) 61 62 63 64 65 66 66 66 66 66 Table 6.4: PERSONNELRECORD Encode Octet Complexity Constant octet-complexity indicates that the extra octet overhead for carrying type informa-tion remains the same as the input value/size grows. Linear octet-complexity indicates that the extra octet overhead for carrying type information grows proportionately as the input value/size CHAPTER 6. PERFORMANCE AND APPLICATIONS 68 Octet St r ing Encode Octet Complexi ty CD o o - a cd CD CD > o cu o o CD o o CO • 16 256 I 4096 30000 Input Data Length (octet) Figure 6.1: OCTET STRING Encode Octet Complexity CHAPTER 6. PERFORMANCE AND APPLICATIONS Figure 6.2: B A S I CV T P I T E M Encode Octet Complexity CHAPTER 6. PERFORMANCE AND APPLICATIONS 70 PersonnelRecord Encode Octet Complexi ty o o T 3 CO CD CD > o -I-l CD -t-J C J o CD O o a o _ 03 CO to _ CO ^ CO CO o CO 10 100 1000 1 10000 Input Data Length (octet) Figure 6.3: PERSONNEL RECORD Encode Octet Complexity CHAPTER 6. PERFORMANCE AND APPLICATIONS 7 1 grows. It is important to note that the octet-complexity reflects the storage complexity of the BER encoding algorithms. All BER implementations must pay the same octet-complexity over-head. However, different BER implementations could have different time-complexity depending on their internal structures. Time performance profile data are also summarized in Table 6.1 and plotted in Figures 6.4, 6.5 and 6.62. We have the following observations: 1. Encoding and decoding times vary in the same trend, i.e. both increase as the input data-size increases. 2. For data of type OCTET STRING or PERSONNELRECORD , the encoding time is greater than the decoding time. For data of type BASICV T PITEM the encoding time is less than the decoding time. This is because the BASICV T PITEM is a complicated CHOICE type and has many OPTIONAL sub-types. The decoder spends a considerable time in calling the ED library utility routine T e s t T a g O to test tags in the input BER octet-sequence and to decide whether the values of the OPTIONAL sub-types should be decoded. 3. For encoding/decoding data-values with constant octet-complexity, the processing time seems to increase proportionately as the input data-size increases. This is shown in Figures 6.4 and 6.5. For encoding/decoding data-values with linear octet-complexity, the processing time seems to increase parabolically as the input data-size increases. This is shown in Figure 6.6. This may be because the input data-size is used to control loops in encoding and decoding routines 2Encode time is the time spent on both Encode_*() and serlDXO. C H A P T E R 6. P E R F O R M A N C E AND A P P L I C A T I O N S 72 Octet St r ing Time Complexi ty o ° ~1 CM 6 0 0 0 1 2 0 0 0 1 8 0 0 0 2 4 0 0 0 3 0 0 0 0 Input Data Length (octet) Figure 6.4: O C T E T STRING Encode/Decode Time Complexity CHAPTER 6. PERFORMANCE AND APPLICATIONS 73 Personne lRecord Time Complexi ty Input Data Length (octet) Figure 6.5: P E R S O N N E L R E C O R D Encode/Decode T i m e Complexity CHAPTER 6. PERFORMANCE AND APPLICATIONS 74 Bas icVTPi tem Time Complexi ty Input Data Length (octet) Figure 6.6: B A S I C V T P I T E M Encode/Decode Time Complexity CHAPTER 6. PERFORMANCE AND APPLICATIONS 75 6 . 2 R e s u l t s o f C A S N l A p p l i c a t i o n s Several applications have used CASNl. It has been used in the implementation of the ISO Virtual Terminal Protocol, in compiling the OSI X.500 Directory Protocol and the CCITT X.226 Presentation Protocol to generate the data type C definitions and their encoding/decoding routines. It is also used in a project integrating PDU ASN.l definitions into Estelle specifica-tions at the University of Montreal [18]. These applications demonstrate that CASNl is a very useful tool for the automatic implementation of communication protocols. 6.2.1 T h e I S O V i r t u a l T e r m i n a l P r o t o c o l At the University of British Columbia, CASNl has been used in an implementation of the ISO Virtual Terminal Protocol (VTP) defined in ISO/DIS 9041 [11]. The implementation is in C on UNIX 4.2 BSD. The original VTP specification includeds includes 775 lines of ASN.l-definitions. Since no macro-definitions are used, it is directly fed into CASNl without any modification. After compiling the VTP ASN.l-specifications, CASNl generated 1,582 lines of C-definitions for the protocol defined data-types and 5,728 lines of C-code for the encoding/decoding routines for these data-types. The total source of the VTP implementation [17] includes 12,224 lines of C code. About 60% of it was automatically generated by CASNl. 6.2.2 T h e C C I T T X . 2 2 6 P r e s e n t a t i o n P r o t o c o l CASNl has been applied to the presentation layer protocol defined in the CCITT recom-mendation X.226 [3]. The 153 lines of the presentation layer protocol ASN.l specification also do not contain any macro-definitions. CASNl compiles the specification directly and generates 300 lines of C definitions for the data-types and 1,286 lines of C code for encoding/decoding CHAPTER 6. PERFORMANCE AND APPLICATIONS 7 6 routines for the data-types. 6.2.3 T h e O S I X . 5 0 0 D i r e c t o r y P r o t o c o l CASNl has also been applied to the OSI X.500 Directory Protocol [12]. The protocol has 12 modules in ASN.l specifications, totaling about 1,600 lines. They are stored in 12 files as input to CASNl. All macro-definitions were marked out as comments. There are several syntax errors in the original specification. After several iterations of error correction and re-compilation, CASNl generated about 1,100 lines of C-definitions for the data-types and 4,000 lines of C-code for encoding/decoding routines. This example shows that CASNl can be used to help detect errors in ASN.l protocol specifications. 6.2.4 T h e A S N . l / E s t e l l e I n t e g r a t i o n P r o j e c t D. Ouimet and G. v. Bochmann at the University of Montreal have been working on a project to integrate ASN.l-definitions into Estelle-specifications [18]. They are building a software package that translates a protocol Esteile-specification into C and generates BER encoding and decoding routines for all defined data-types. Such a system may be built by integrating an ASN.l-C compiler with an Estelle-C compiler. After comparing and evaluating many existing packages, CASNl has been chosen as their ASN.l-C compiler in the project for its high efficiency and user-friendly interface. The project is still in an early stage of development and more progress is expected. Chapter 7 C o n c l u s i o n s a n d F u t u r e R e s e a r c h This chapter summarizes the work of this thesis, points out the limitations in the current version of CASNl and presents directions for future research. 7.1 Conclusions The ED library is an efficient implementation of BER. It is flexible, easy to use and has proven helpful in many protocol implementation exercises. By structural analysis and comparison with other existing BER implementations, one can be easily convinced that the ED library provides potentially better timing performance than those referred to Section 1.3. It has been recognized that to write data-type encoders and decoders manually is quite arduous, even with the help of the ED library routines. Therefore, CASNl is designed and im-plemented as an automatic tool for translating protocol specifications from ASN.l into C and for generating the encoders and decoders for every protocol-defined data-type. CASNl is based on a subset of ASN.l syntax rules because it does not handle ASN.l macro-definitions. Users have to replace the macro-definitions with the OPERATlON-definition and ERROR-defmition be-fore feeding the ASN.l specification to CASNl. For cross-module type-references, some manual involvement may still be necessary. Therefore, a user should not fully depend on the output 77 CHAPTER 7. CONCLUSIONS AND FUTURE RESEARCH 78 g e n e r a t e d b y the c u r r e n t v e r s i o n of CASNl. Even w i t h these deficiencies, one c a n s t i l l be easily c o n v i n c e d b y m a n y a p p l i c a t i o n examples t h a t CASNl is a very p o w e r f u l t o o l f o r s p e e d i n g up p r o t o c o l i m p l e m e n t a t i o n s . 7.2 Future W o r k The c u r r e n t v e r s i o n o f CASNl c o u l d be f u r t h e r i m p r o v e d i n the f o l l o w i n g aspects. First, the s t r u c t u r e of CASNl c o u l d b e re-organized so t h a t more f u n c t i o n a l i t y c a n b e a d d e d to i m p r o v e the user interface. In the c u r r e n t version, CASNl translates a p r o t o c o l m o d u l e b y m o d u l e w i t h o u t k e e p i n g i n f o r m a t i o n a m o n g the modules. This results i n two p o t e n t i a l problems: 1. The c u r r e n t v e r s i o n of CASNl c a n not h a n d l e cross-module references. Manual involve-m e n t m a y be necessary i f m a i n t a i n i n g i n t e r - m o d u l e r e l a t i o n s h i p s is r e q u i r e d . 2. As d i s c u s s e d i n Chapter 5, CASNl assumes the top-down o r d e r of t y p e - d e f i n i t i o n s i n the i n p u t A S N.l-specifications, f o r the p u r p o s e o f s i m p l i f y i n g the c o m p i l e r i m p l e m e n t a t i o n . This c o u l d be a p o t e n t i a l p r o b l e m w h e n cross-module reference m u s t be m a i n t a i n e d , because modules are not necessarily ordered a c c o r d i n g t o t y p e reference r e l a t i o n s h i p . To i m p r o v e CASNl, a l l i n f o r m a t i o n a b o u t type-definitions, value-definitions, operation-d e f i n i t i o n s as well as er r o r - d e f i n i t i o n s c a n be saved i n a n i n t e r m e d i a t e d a t a s t r u c t u r e , c a l l e d the definition table, d u r i n g p a r s i n g . With the g l o b a l i n f o r m a t i o n r e c o r d e d i n the definition table, two u s e f u l f a c i l i t i e s c o u l d be b u i l t : 1. A m o d u l e - c o n f i g u r a t i o n m e c h a n i s m to de a l w i t h cross-module r e l a t i o n s h i p s , e.g., IM-P O R T i n g or E X P O R T i n g ty p e - d e f i n i t i o n s a n d value-definitions a m o n g ASN.l modules; usin g M O D U L E . T Y P E to reference e x t e r n a l types a n d M O D U L E . V A L U E t o reference e x t e r n a l values etc. CHAPTER 7. CONCLUSIONS AND FUTURE RESEARCH 79 2. A topological sorting mechanism to order the type-definitions according to type reference relationships. Second, it would be very useful, and not very difficult, to port the C A S N l implementation to an A S N . l - P a s c a l or an ASN.1-C-I-+ compiler. T h i r d , a complete A S N . l compiler must have a parser that dynamically extend its syntax rules because A S N . l syntax rules are very flexible and extensible. One possible solution is to bui ld a knowledge-based compiler with self-learning capability. It learns new knowledge of parsing (i.e., new syntax rules) dynamically during parsing A S N . l macro-definitions and detects infinite reduction using the knowledge it has learned. T h e testing of infinite reduction might be mapped to a problem of detecting loops in a directed graph represents the rules of syntax reduction. A l l in all, this problem remains an interesting research topic for knowledge-based compiler design and implementation. B i b l i o g r a p h y [1] CCITT, Recommendation X.208, "Specification of Abstract Syntax Notation One (ASN.l)," Geneva 1987. [2] CCITT, Recommendation X.209, "Specification of Basic Encoding Rules for Abstract Syntax Notation One(ASN.l)," Geneva 1987. [3] CCITT, Recommendation X.226 (ISO 8823 proof F) "Presentation Protocol Specifi-cation for Open Systems Interconnection for CCITT Applications," Geneva 1987. [4] CCITT, Recommendation X.409, "Message Handling System — Presentation Trans-fer Syntax and Notation," CCITT Red Book, Vol VIII, Fascicle VIII.7, Geneva 1985. [5] CCITT, Recommendation X.410, "Message Handling System — Remote Operations and Reliable Transfer Service," CCITT Red Book, Vol VIII, Fascicle VIII.7, Geneva 1985. [6] Chappell, D., "A Tutorial on Abstract Syntax Notation One (ASN.l)," Transmission #25, Open systems data transfer, Omnicom information service, Omnicom, Inc., ISSN 0741-286X, Dec. 1986. [7] International Standard for Information Processing System, "Open Systems Intercon-nection — Specification of Abstract Syntax Notation One (ASN.l)," ISO Final 8824, 1987. [8] International Standard for Information Processing System, "Open Systems Intercon-nection — Specification of Abstract Syntax Notation One (ASN.l) — Proposed Draft Addendum 1: Extensions to ASN.l," ISO DP 8824 PDAD 1, 1987. [9] International Standard for Information Processing System, "Open Systems Intercon-nection — Specification of Basic Encoding Rules for Abstract Syntax Notation One (ASN.l)" ISO Final 8825, 1987. [10] International Standard for Information Processing System, "Open Systems Inter-connection — Specification of Basic Encoding Rules for Abstract Syntax Notation One (ASN.l) — Proposed Draft Addendum 1: Extensions to ASN.l Basic Encoding Rules," ISO DP 8825 PDAD 1, 1987. 80 BIBLIOGRAPHY 81 [11] International Standard for Information Processing System, "Open Systems Intercon-nection — Virtual Terminal Protocol — Basic Class", ISO DIS 9041, 1987. [12] ISO/CCITT Directory Convergence Document #l-#8, CCITT Recommendation X.500-X.521, ISO DIS 9594.1-9594.8, "The Directory," Gloucester, November 1987. [13] ISODE, "The ISO Development Environment: User Manual," Version 4.102 Volume 1 and Volume 4, The Wollongong Group, 1129 San Antonio Rd. Palo Alto, CA, USA, Aug. 1988. [14] NBS, "User Guide for the NBS Prototype Compiler for Estelle, final report" Report No. ICST/SNA-87/3, U.S. Department of Commerce, National Bureau of Standards, Oct. 1987. [15] Neufeld, G., "EAN: a distributed message system," Proceedings of the Canadian In-formation Processing Society National Meeting, pp 144-149, Ottawa, May, 1983. [16] Neufeld, G., Demco J., Hilpert B., and Sample R., "EAN: an X.400 message system," Proceedings of IF IP Computer Message System'85, Elsevier Science Publishers, B. U. North-Holland , 1986 [17] Ng, S., "On Implementing the ISO Virtual Terminal Protocol for a UNIX Environ-ment," Master Thesis, to appear, Computer Science Department, University of British Columbia, 1988. [18] Ouimet D., and Bochmann G., "Integrating ASN.l PDU Definitions into Estelle Spec-ification, Implementation-Oriented," Unpublished document. University de Montreal, Department d'informatique et de recherche operationnelle, 1988. [19] Soloman M. , and Kramer J. , "Distributed Systems and Computer Networks," Prentice-Hall Inc., pp 303-235, 1987. [20] Yang, Y., "ED Library User Manual," Computer Science Department, the University of British Columbia, 1988. [21] Yang, Y., "CASNl User Manual," Computer Science Department, the University of British Columbia, 1988. Appendix A B N F o f A S N . l S y n t a x R u l e s M o d u l e D e f i n i t i o n ModuleBody Ass ignmentLis t Assignment E x t e r n a l t y p e r e f e r e n c e E x t e r n a l v a l u e r e f e r e n c e DefinedType DefinedValue Typeassinment Valueassignment Type ::= modulereference DEFINITIONS "::=" BEGIN ModuleBody END ::= AssignmentList I Empty ::= Assignment I AssignmentList Assignment ::= Typeassignment IValueassignment ::= moduleregerence Dot t y p e r e f e r e n c e ::= modulereference Dot valuereerence ::= E x t e r n a l t y p e r e f e r e n c e I t y p e r e f e r e n c e ::= E x t e n a l v a l u e r e f e r e n c e I v a l u e r e f e r e n c e ::= t y p e r e f e r e n c e "::=" Type ::= v a l u e r e f e r e n c e "::=" Value ::= B u i l t i n T y p e I D e f i n e d T y p e 82 APPENDIX A. BNF OF ASN.l SYNTAX RULES B u i l t i n T y p e NameType Value B u i l t i n V a l u e : := BooleanType I IntegerType I B i t S t r i n g T y p e | O c t e t S t r i n g T y p e I NullType I SequenceType I SequenceOfType I SetType I SetOfType I ChoiceType I S e l e c t i o n T y p e I TaggedType I AnyType I ExternalType I CharacterSetType I UsefulType ::= i d e n t i f i e r Type I Type I S e l e c t i o n T y p e ::= B u i l t i n V a l u e I DefinedValue ::= BooleanValue I IntegerValue I B i t S t r i n g V a l u e I O c t e t S t r i n g V a l u e I N u l l V a l u e I SequenceValue I SequenceOfValue I SetValue I SetOfValue I ChoiceValue I S e l e c t i o n V a l u e I TaggedValue I AnyValue I CharacterSetValue NamedValue := i d e n t i f i e r Value I Value APPENDIX A. BNF OF ASN.l SYNTAX RULES BooleanType BooleanValue IntegerType NamedNumberList NamedNumber SignedNumber IntegerValue B i t S t r i n g T y p e NamedBitList NamedBit B i t S t r i n g V a l u e I d e n t i f i e r L i s t O c t e t S t r i n g T y p e O c t e t S t r i n g V a l u e ::= BOOLEAN ::= TRUE|FALSE ::= INTEGER I INTEGER NamedNumberList "} ::= NamedNumber I NamedNumberList "," Named I Number :: = i d e n t i f e r " ( " SignedNumber " ) " I i d e n t i f e r " ( " DefinedValue " ) " ::= number I " - " number ::= SignedNumber I i d e n t i f e r ::= BITSTRING I BITSTRING "{" NamedBitList ">" ::= NamedBit I NamedBitList "," NamedBit ::= i d e n t i f e r " ( " number")" I i d e n t i f e r " ( " DefinedValue " ) " ::= b s t r i n g I h s t r i n g I " { " I d e n t i f i e r L i s t "}" | I I ^ M I I J . I I ::= i d e n t i f i e r I I d e n t i f i e r L i s t "," i d e n t i f i e r ::= OCTETSTRING ::= b s t r i n g APPENDIX A. BNF OF ASN.l SYNTAX RULES NullType N u l l V a l u e SequenceType ElementTypeList ElementType SequenceValue ElementValueLi s t SequenceOfType SequenceOfValue V a l u e L i s t SetType SetValue SetOfType SetOfValue ChoiceType I h s t r i n g ::= NULL ::= NULL ::= SEQUENCE "{" ElementTypeList "}" ::= ElementType I ElementTypeList "," ElementType ::= NamedType I NamedType OPTIONAL I NamedType DEFAULT Value I COMPONENTSOF Type ::= "{" E l e m e n t V a l u e L i s t "}" | 11^1111^.11 ::= NamedValue I E l e m e n t V a l u e L i s t "," NamedValue ::= SEqUENCEOF Type ::= " { " V a l u e L i s t " } " ::= Value I V a l u e L i s t "/'Value ::= SET "{" E l e m e n t L i s t "}" ::= "{"ElementValueList "}" ::= SETOF Type ::= "{" V a l u e L i s t "}" ::= CHOICE "{" A l t e r n t i v e L i s t "}" APPENDIX A. BNF OF ASN.l SYNTAX RULES A l t e r n a t i v e L i s t C hoiceValue S e l e c t i o n T y p e S e l e c t i o n V a l u e TaggedType Tag ClassNumber C l a s s TaggedValue AnyType AnyValue CharacterSetType C h a r a c t e r S e t V a l u e UsefulType EnumeratedType Enumeration RealType ::= NamedType I A l t e r n a t i v e L i s t "," NamedTyp ::= NamedValue ::= i d e n t i f i e r < Type ::= NamedValue ::= Tag Type I Tag IMPLICIT Type ::= " [ " C l a s s ClassNumber " ] " ::= number I DefinedValue ::= UNIVERSAL I APPLICATION I PRIVATE I Empty ::= Value ::= ANY ::= Type Value ::= t y p e r e f e r e n c e ::= c s t r i n g ::= t y p e r e f e r e n c e ::= ENUMERATED M { " Enumeration " ::= NamedNumber I NamedNumber "," Enumeration ::= REAL APPENDIX A. BNF OF ASN.l SYNTAX RULES 8 7 RealValue NumericRealValue Mantissa Base Exponent SpecialRealValue EncryptedType SubType ParentType SubtypeSpec SubtypeAlternativeList SubtypeAlternative SubtypeValueSet ::= NumericRealValue I SpecialRealValue ::= Mantissa "," Base Exponent ">" I number ::= SignedNumber ::= number ::= SignedNumber ::= PINFINITY I MINFINITY ::= ENCRYPTED Type ::= ParentType SubtypeSpec I SET SizeConstraint Of Type I SEQUENCE SizeConstraint Of Type ::= Type ::= " ( " SubtypeAlternative SubtypeAlternativeList " ) " ::= empty I "|" SubtypeAlternative SubtypeAlternativeList ::= SubtypeValueSet I SubtypeConstraint ::= Value I ContainedSubtype I ValueRange I PermittedAlphabet APPENDIX A. BNF OF ASN.l SYNTAX RULES 88 SubtypeConstraint ContainedSubtype ValueRange Lo werEndpo int UpperEndpoint LowerEndValue UpperEndValue SizeConstraint PermittedAlphabet InnerTypeConstraints SingleTypeConstraint MultipleTypeConstraints FullSpecification PartialSpecification TypeConstraints ::= SizeConstraint I InnerTypeConstraints ::= INCLUDES Type ::= LowerEndpoint UpperEndpoint ::= LowerEndValue I LowerEndValue Larrow ::= UpperEndValue I Larrow UpperEndValue : := Value I MIN ::= Value I MAX ::= SIZE SubtypeSpec ::= FROM SubtypeSpec ::= WITH COMPONENT SingleTypeConstraint I WITH COMPONENTS MultipleTypeConstraints ::= SubtypeSpec ::= FullSpecification I PartialSpecification ::= "{" TypeConstraints "}" ::= "{" "..." "," TypeConstraints "}" ::= NamedConstraint I NamedConstraint "," TypeConstraints APPENDIX A. BNF OF ASN.l SYNTAX RULES NamedConstraint := i d e n t i f i e r C o n s t r a i n t I C o n s t r a i n t C o n s t r a i n t := V a l u e C o n s t r a i n t P r e s e n c e C o n s t r a i n t V a l u e C o n s t r a i n t := empty I SubtypeSpec P r e s e n c e C o n s t r a i n t = empty I PRESENT I ABSENT Appendix B B N F o f C A S N l S y n t a x R u l e s H o d u l e D e f i n i t i o n M o d u l e l d e n t i f i e r T a g D e f a u l t A s s i g n e d l d e n t i f i e r ModuleBody Expor t s SymbolsExported Imports ::= M o d u l e l d e n t i f i e r DEFINITIONS TagDefault "::=" BEGIN ModuleBody END ::= t y p e r e f e r e n c e A s s i g n e d l d e n t i f i e r ::= empty I EXPLICIT TAGS I IMPLICIT TAGS ::= empty I i d e n t i f i e r I O b j e c t l d e n t i f i e r V a l u e ::= Exports Imports AssignmentList ::= empty I EXPORTS SymbolsExported ":" ::= empty I SymbolList ::= empty I IMPORTS Symbolslmported ":" 90 APPENDIX B. BNF OF CASNl SYNTAX RULES Symbolslmported SymbolsFromModuleList SymbolsFromModule SymbolList Symbol As s i g n m e n t L i s t Assignment := empty I SymbolsFromModuleList := SymbolsFromModule I SymbolsFromModule SymbolsFromModuleList := SymbolList FROM M o d u l e l d e n t i f i e r = Symbol I Symbol SymbolList := t y p e r e f e r e n c e I i d e n t i f i e r := empty I Assignment A s s i g n m e n t L i s t := Typeassignment I Valueassignment I O p e r a t i o n D e f i n i t i o n I E r r o r D e f i n i t i o n E x t e r n a l t y p e r e f e r e n c e ::= modulereference it > > t y p e r e f e r e n c e E x t e r n a l v a l u e r e f e r e n c e ::= modulereference ) > > > DefinedValue Typeassignment Valueassignment Typ eAs s i gnValue i d e n t i f i e r := E x t e r n a l v a l u e r e f e r e n c e I i d e n t i f i e r := t y p e r e f e r e n c e "::=" Type := i d e n t i f i e r TypeAssignValue := BooleanType "::=" BooleanValue I IntegerType "::=" IntegerValue I B i t S t r i n g T y p e "::=" B i t S t r i n g V a l u e I OctetStringType "::=" O c t e t S t r i n g V a l u e APPENDIX B. BNF OF CASNl SYNTAX RULES 9 2 NullType "::=" N u l l C h a r a c t e r S t r i n g T y p e "::=" C h a r a c t e r S t r i n g V a l u e O b j e c t l d e n t i f i e r T y p e "::=" O b j e c t l d e n t i f i e r V a l u e OBJDSCRPT "::=" C h a r a c t e r S t r i n g V a l u e UTCTime "::=" C h a r a c t e r S t r i n g V a l u e GNLTime "::=" C h a r a c t e r S t r i n g V a l u e RealType "::=" RealValue EXTERNAL "::=" SequenceValue EncryptedType "::=" B i t S t r i n g V a l u e DefinedType "::=" Value ChoiceType "::=" Value SequenceOfType ": :=" SequenceOfValue SetOfType "::=" SetOfValue S e l e c t i o n T y p e "::=" Value TaggedType "::=" Value AnyType "::=" AnyValue EnumeratedType "::=" i d e n t i f i e r IntegerType B i t S t r i n g T y p e O c t e t S t r i n g T y p e NullType SequenceType SequenceOfType SetType SetOfType ChoiceType S e l e c t i o n T y p e TaggedType AnyType Obj e c t l d e n t i f i e r T y p e C h a r a c t e r S t r i n g T y p e UsefulType EnumeratedType RealType EncryptedType Type B u i l t i n T y p e DefinedType B u i l t i n T y p e BooleanType APPENDIX B. BNF OF CASNl SYNTAX RULES DefinedType NamedType := E x t e r n a l t y p e r e f e r e n c e I t y p e r e f e r e n c e I SubType := i d e n t i f i e r Type I Type Value := True I F a l s e I SignedNumber I C h a r a c t e r S t r i n g V a l u e I N u l l I " { " V a l u e L i s t "}" | „{,. „ }„ I O b j e c t l d e n t i f i e r V a l u e I RealValue I AnyValue I i d e n t i f i e r Value I DefinedValue V a l u e L i s t := Value I V a l u e L i s t "," Value BooleanType BooleanValue := BOOLEAN := True I F a l s e IntegerType I n t r a i l := INTEGER I n t r a i l := empty I " { " NamedNumberList "}' NamedNumberList = NamedNumber I NamedNumberList "," NamedNumber NamedNumber := i d e n t i f i e r " ( " NumberList 1 1 ) " NumberList := SignedNumber I DefinedValue APPENDIX B. BNF OF CASNl SYNTAX RULES SignedNumber In t e g e r V a l u e B i t S t r i n g T y p e B i t r a i l N amedBitList NamedBit NumberForm B i t S t r i n g V a l u e I d e n t i f i e r L i s t O c t e t S t r i n g T y p e O c t e t S t r i n g V a l u e NullType SequenceType E l e m e n t T y p e L i s t ElementType ::= number I Minus number ::= SignedNumber I i d e n t i f i e r : := BITSTRING B i t r a i l ::= empty I " { " NamedBitList "}" := NamedBit I NamedBitList "," NamedBit := i d e n t i f i e r " ( " NumberForm " ) " ::= number I DefinedValue ::= b s t r i n g I h s t r i n g I "-[" I d e n t i f i e r L i s t "}" | ii.pi n j . l i ::= i d e n t i f i e r I I d e n t i f i e r L i s t "," i d e n t i f i e r ::= OCTET STRING : := b s t r i n g I h s t r i n g ::= NULL ::= SEQUENCE "{" ElementTypeList "} ::= empty I ElementType I ElementTypeList "," ElementType ::= NamedType APPENDIX B. BNF OF CASNl SYNTAX RULES SequenceValue SequenceOfType SequenceOfValue SetType SetValue SetOfType SetOfValue ChoiceType A l t e r n a t i v e T y p e L i s t S e l e c t i o n T y p e TaggedType Tag ClassNumber C l a s s I OPTIONAL NamedType I NamedType DEFAULT Value I COMPONENTS Of t y p e r e f e r e n c e ::= "{" V a l u e L i s t "}" ::= SEQUENCE Of Type I SEQUENCE ::= "{" V a l u e L i s t "}" I u .£11 11^.11 ::= SET "{" ElementTypeList "}" ::= "{" V a l u e L i s t "}" I I I ^ M 11^.11 ::= SET Of Type I SET ::= V a l u e L i s t "}" ::= CHOICE "{" A l t e r n a t i v e T y p e L i s t "}" ::= NamedType I A l t e r n a t i v e T y p e L i s t "," NamedType ::= i d e n t i f i e r Larrow t y p e r e f e r e n c e ::= Tag Type I Tag IMP Type I Tag EXPLICIT Type ::= " [ " C l a s s ClassNumber " ] " ::= number I DefinedValue ::= empty I UNIVERSAL APPENDIX B. BNF OF CASNl SYNTAX RULES 96 AnyType AnyValue Obj e c t l d e n t i f i e r T y p e Obj e c t l d e n t i f i e r V a l u e ObjIdComponentList ObjIdComponent NameAndNumberForm C h a r a c t e r S t r i n g T y p e UsefulType EnumeratedType Enumeration I APPLICATION I PRIVATE := ANY I ANY DEFINED BY i d e n t i f i e r := Type Value := OBJECTID := "{" ObjIdComponentList "}" I " { " DefinedValue ObjIdComponentList "}" := ObjIdComponent I ObjIdComponent ObjIdComponentList := NumberForm I NameAndNumberForm := i d e n t i f i e r " ( " NumberForm " ) " := Nums I P r i n t a b l e S t r i n g I T e l e x S t r i n g I V i d e o t e x S t r i n g I IA5String I G r a p h i c S t r i n g I V i s i b l e S t r i n g := UTCTime I GNLTime I EXTERNAL I OBJECT DISCRIPTOR := ENUMERATED "{" Enumeration ">" := NamedNumber I NamedNumber "," Enumeration APPENDIX B. BNF OF CASNl SYNTAX RULES RealType RealValue NumericRealValue Man t i s s a Base Exponent S p e c i a l R e a l V a l u e EncryptedType SubType ParentType SubtypeSpec S u b t y p e A l t e r n a t i v e L i s t S u b t y p e A l t e r n a t i v e SubtypeValueSet := REAL := NumericRealValue I S p e c i a l R e a l V a l u e := "{" Mantissa "," Base Exponent "}" I number := SignedNumber := number := SignedNumber := PINFINITY I MINFINITY := ENCRYPTED Type := ParentType SubtypeSpec I SET S i z e C o n s t r a i n t Of Type I SEQUENCE S i z e C o n s t r a i n t Of Type := Type := " ( " S u b t y p e A l t e r n a t i v e S u b t y p e A l t e r n a t i v e L i s t " ) " := empty I "|" S u b t y p e A l t e r n a t i v e S u b t y p e A l t e r n a t i v e L i s t := SubtypeValueSet I SubtypeConstraint := Value I ContainedSubtype I ValueRange I PermittedAlphabet APPENDIX B. BNF OF CASNl SYNTAX RULES 98 S u b t y p e C o n s t r a i n t ContainedSubtype ValueRange LowerEndpoint UpperEndpoint LowerEndValue TJpperEndValue S i z e C o n s t r a i n t P ermittedAlphabet I n n e r T y p e C o n s t r a i n t s := S i z e C o n s t r a i n t I I n n e r T y p e C o n s t r a i n t s := INCLUDES Type := LowerEndpoint UpperEndpoint S i n g l e T y p e C o n s t r a i n t M u l t i p l e T y p e C o n s t r a i n t s F u l l S p e c i f i c a t i o n P a r t i a l S p e c i f i c a t i o n T y p e C o n s t r a i n t s ::= LowerEndValue I LowerEndValue Larrow ::= UpperEndValue I Larrow UpperEndValue ::= Value I MIN : := Value I MAX ::= SIZE SubtypeSpec ::= FROM SubtypeSpec ::= WITH COMPONENT S i n g l e T y p e C o n s t r a i n t I WITH COMPONENTS M u l t i p l e T y p e C o n s t r a i n t s ::= SubtypeSpec := F u l l S p e c i f i c a t i o n I P a r t i a l S p e c i f i c a t i o n := "{" Ty p e C o n s t r a i n t s "}" H T M II II II II . — \ ... , T y p e C o n s t r a i n t s "}" := NamedConstraint I NamedConstraint "," APPENDIX B. BNF OF CASNl SYNTAX RULES T y p e C o n s t r a i n t s NamedConstraint := i d e n t i f i e r C o n s t r a i n t I C o n s t r a i n t C o n s t r a i n t := V a l u e C o n s t r a i n t P r e s e n c e C o n s t r a i n t V a l u e C o n s t r a i n t := empty I SubtypeSpec P r e s e n c e C o n s t r a i n t := empty I PRESENT I ABSENT O p e r a t i o n D e f i n i t i o n := i d e n t i f i e r OPERATION OperationTypeNotation "::=" number Oper a t i o n T y p e N o t a t i o n := empty I ARGUMENT t y p e r e f e r e n c e NamedType Res u l t E r r o r s R e s u l t := empty I RESULT t y p e r e f e r e n c e NamedType E r r o r s := empty I ERRORS "{" ErrorNames "}' ErrorNames := empty I i d e n t i f i e r I i d e n t i f i e r "," ErrorNames E r r o r D e f i n i t i o n := i d e n t i f i e r ERROR ErrorType Not at i on "::=" number E r r o r T y p e N o t a t i o n ::= empty I PARAMETER t y p e r e f e r e n c e NamedType Appendix C E x a m p l e o f S t r u c t u r e d T y p e E n c o d i n g a n d D e c o d i n g A S N . l Definition: — T h i s i s an example of ASN.l s t r u c t u r e d type STRUCT DEFINITIONS ::= BEGIN V a r l ::= SET { rOO INTEGER OPTIONAL r O l V a r l r02 SEQUENCE { r l O ENUMERATED { i d l ( l O ) , i d 2 ( 2 0 ) , id3(30) > r l l SET OF Var2 r l 2 NULL OPTIONAL Var2 ::= BOOLEAN END C Definition: typedef b o o l Var2; /* BOOLEAN */ typedef enum T22 { /* ENUMERATED Type */ i d l = 10 ,id2 = 20 ,id3 = 30 } T22; typedef s t r u c t T i l { /* SET/SEQ */ T22 r l O ; /* T22 */ LIST 0F(Var2) r l l ; /* Var2 */ i n t * r l 2 ; /* NULL(optional) */ } T i l ; 100 APPENDIX C. EXAMPLE OF STRUCTURED TYPE ENCODING AND DECODING 101 typedef struct Varl { int *rOO; struct Varl *r01; T i l r02; > Varl; E n c o d e r s : #include "STRUCT.defs.c" /* SET/SEQ */ / * INTEGER(optional) * / / * Varl(recursive) * / / * T i l * / IDX * Encode_Var2(class, form, code, Var2_VP) short class; short form; long code; Var2 *Var2_VP; •C IDX *p; p = (IDX *) Encode_bool(class, form, code, Var2_VP); return (p); IDX * Encode_T22(class, form, code, T22_VP) short class; short form; long code; T22 *T22_VP; •C IDX *p; p = (IDX *) Encode.int(class, form, code, T22.VP); return (p); IDX * Encode.Tll(class, form, code, T11_VP) short class; short form; long code; APPENDIX C. EXAMPLE OF STRUCTURED TYPE ENCODING AND DECODING 1 0 2 T i l *T11_VP; •C IDX *p; p = (IDX *) E n c o d e _ s t r u c t _ b e g ( c l a s s , form, code); Encode_T22(UNIVERSAL, PRIMITIVE, 10, & ( T l l _ V P - > r l O ) ) ; Encode_struct_beg(UNIVERSAL, CONSTRUCTOR, CODE.SET, & ( T l l _ V P - > r l l ) ) ; L i s t F o r ( T l l _ V P - > r l l ) Encode.Var2(UNIVERSAL, PRIMITIVE, 1, (T l l _ V P - > r l l ) - > n e x t - > i t e m ) ; Encode_struct_end(DEFINITE); i f ( T l l _ V P - > r l 2 != NULL) Encode.null(UNIVERSAL, PRIMITIVE, CODE.NULL, T l l _ V P - > r l 2 ) ; Encode_struct_end(DEFINITE); r e t u r n ( p ) ; } IDX * E n c o d e . V a r l ( c l a s s , form, code, Varl_VP) s h o r t c l a s s ; s h o r t form; l o n g code; V a r l *Varl_VP; { IDX *p; p = (IDX *) E n c o d e _ s t r u c t _ b e g ( c l a s s , form, code); i f (Varl_VP->r00 != NULL) Encode.int(UNIVERSAL, PRIMITIVE, C0DE_INTEGER, Varl_VP->r00); Encode.Varl(UNIVERSAL, CONSTRUCTOR, 17, Varl_VP->r01); Encode.Tll(UNIVERSAL, CONSTRUCTOR, 16, &(Varl_VP->r02)); APPENDIX C. EXAMPLE OF STRUCTURED TYPE ENCODING AND DECODING 103 Encode_struct_end(DEFINITE); return (p); > Decoders: #include "STRUCT.defs.c" Var2 * Decode_Var2(class, form, code, B, Var2_VP) short class; short form; long code; IOP *B; bool *Var2_VP; •C Var2_VP = (bool *) Decode.bool (class, form, code, B, Var2_VP); return (Var2_VP); > T22 * Decode_T22(class, form, code, B, T22.VP) short class; short form; long code; IOP *B; T22 *T22_VP; •C T22_VP = (T22 *) Decode.int (class, form, code, B, T22_VP); return (T22.VP); } Til * Decode.Tll(class, form, code, B, T11_VP) short class; short form; long code; IOP *B; Til *T11_VP; APPENDIX C. EXAMPLE OF STRUCTURED TYPE ENCODING AND DECODING 104 i f ( T l l . V P == NULL) T l l . V P = ( T i l *) G E T B U F ( s i z e o f ( T i l ) ) ; D e c o d e _ s t r u c t _ b e g ( c l a s s , form, code, B); Decode_T22(UNIVERSAL, PRIMITIVE, 10, B, & ( T l l _ V P - > r l O ) ) ; Decode_struct_beg(UNIVERSAL, CONSTRUCTOR, CODE.SET, B, & ( T i i _ V P - > r i l ) ) ; while ( L i s t E n d ( B ) ) L i s t A p p e n d ( & ( T l l _ V P - > r l l ) , Decode_Var2(UNIVERSAL, PRIMITIVE, 1, B, 0 ) ) ; Decode_struct_end(B); i f (TestTag(UNIVERSAL, PRIMITIVE, CODE.NULL, B) != FALSE) T l l _ V P - > r l 2 = ( i n t *) Decode.null(UNIVERSAL, PRIMITIVE, CODE.NULL, B, T l l _ V P - > r l 2 ) ; Decode_struct_end(B); r e t u r n ( T l l . V P ) ; V a r l * D e c o d e . V a r l ( c l a s s , form, code, B, Varl.VP) s h o r t c l a s s ; s h o r t form; l o n g code; IOP *B; V a r l *Varl_VP; i i f ( V a rl.VP == NULL) Varl.VP = ( V a r l *) G E T B U F ( s i z e o f ( V a r l ) ) ; D e c o d e _ s t r u c t _ b e g ( c l a s s , form, code, B); i f (TestTag(UNIVERSAL, PRIMITIVE, CODE.INTEGER, B) != FALSE) Varl_VP->rOO = ( i n t *) Decode.int (UNIVERSAL, PRIMITIVE, CODE.INTEGER, B, Varl_VP->rOO); Varl_VP->r01 = ( s t r u c t V a r l *) Decode.Varl APPENDIX C. EXAMPLE OF STRUCTURED TYPE ENCODING AND DECODING 1 0 5 ( UNIVERSAL, CONSTRUCTOR, 17, B, Varl_VP->r01); Decode.Tll(UNIVERSAL, CONSTRUCTOR, 16, B, &(Varl_VP->r02)); Decode_struct_end(B); r e t u r n ( V a r l . V P ) ; Appendix D E x a m p l e o f C H O I C E T y p e E n c o d i n g a n d D e c o d i n g A S N . l Definition D::= CH0ICE{ d [0] NULL e [1] P r i n t a b l e S t r i n g } C::= CH0ICE{ f [2] NULL g [3] P r i n t a b l e S t r i n g } A::= CHOICE* b D c C } C Definition typedef s t r u c t D { /* CHOICE */ i n t c h o i c e ; /* i n d i c a t e the ch o i c e o f data */ union { /* c h o i c e s */ i n t d; /* CONTEXT 0 NULL */ #define D_d_$tag OxaOOOOOOO OCTS e; /* CONTEXT 1 P r i n t a b l e S t r i n g */ #define D_e_$tag OxaOOOOOOl > d a t a > D; typedef s t r u c t C { /* CHOICE */ i n t c h o i c e ; /* i n d i c a t e the ch o i c e of data */ union { /* c h o i c e s */ i n t f ; /* CONTEXT 2 NULL */ #define C _ f _ $ t a g 0xa0000002 OCTS g; /* CONTEXT 3 P r i n t a b l e S t r i n g */ 106 APPENDIX D. EXAMPLE OF CHOICE TYPE ENCODING AND DECODING 107 #define C_g_$tag 0xa0000003 } data } C; typedef s t r u c t A { i n t u n i o n { D C c h o i c e ; b; c; /* /* /* /* /* CHOICE */ i n d i c a t e the c h o i c e of data */ c h o i c e s */ D */ C */ } > A; Encoders: data IDX * Encode_D(class, form, code, D_VP) s h o r t c l a s s ; s h o r t form; l o n g code; IDX *p; s w i t c h (D_VP->choice) { case D_d_$tag: p = (IDX *) Encode_struct_beg(CONTEXT, CONSTRUCTOR, 0); Encode.null(UNIVERSAL, PRIMITIVE, CODE.NULL, fc(D_VP->data.d)); Encode_struct_end(DEFINITE); break; case D_e_$tag: p = (IDX *) Encode_struct_beg(CONTEXT, CONSTRUCTOR, 1); Encode.octs(UNIVERSAL, PRIMITIVE, CODE.PRINTABLE.STRING, Encode_struct_end(DEFINITE); break; d e f a u l t : f p r i n t f ( s t d e r r , "Encode_D : No such c h o i c e \ n " ) ; e x i t Q ; &(D_VP->data.e)); } r e t u r n ( p ) ; } APPENDIX D. EXAMPLE OF CHOICE TYPE ENCODING AND DECODING 108 IDX * Encode_C(class, form, code, C_VP) short class; short form; long code; C *C_VP; i IDX *p; switch (C_VP->choice) { case C_f_$tag: p = (IDX *) Encode_struct_beg(CONTEXT, CONSTRUCTOR, 2); Encode.null(UNIVERSAL, PRIMITIVE, CODE.NULL, &(C_VP->data.f)); Encode_struct_end(DEFINITE); break; case C_g_$tag: p = (IDX *) Encode_struct_beg(CONTEXT, CONSTRUCTOR, 3); Encode.octs(UNIVERSAL, PRIMITIVE, CODE_PRINTABLE_STRING, ft(C_VP->data.g)); Encode_struct_end(DEFINITE); break; default: fprintf(stderr, "Encode.C : No such choice\n"); exitO ; } return (p); } IDX * Encode_A(class, form, code, A_VP) short class; short form; long code; A *A_VP; i IDX *p; switch (A_VP->choice) { case D_d_$tag: APPENDIX D. EXAMPLE OF CHOICE TYPE ENCODING AND DECODING case D_e_$tag: p = (IDX *) Encode_D(-l, -1, -1, &(A_VP->data.b)); break; case C _ f _ $ t a g : case C_g_$tag: p = (IDX *) Encode_C(-l, -1, -1, &(A_VP->data.c)) ; break; d e f a u l t : f p r i n t f ( s t d e r r , "Encode_A : No such c h o i c e \ n " ) ; e x i t ( ) ; } r e t u r n ( p ) ; > Decoders: D * Decode_D(class, form, code, B, D_VP) s h o r t c l a s s ; s h o r t form; l o n g code; IOP *B; D *D_VP; { i f (D_VP == NULL) D_VP = (D *) GETBUF(sizeof(D)); D_VP->choice = GetTag(B); s w i t c h (D_VP->choice) { case D_d_$tag: Decode_struct_beg(CONTEXT, CONSTRUCTOR, 0, B); Decode.null(UNIVERSAL, PRIMITIVE, CODE.NULL, B, &(D_VP->data.d)); Decode_struct_end(B); break; case D_e_$tag: Decode_struct_beg(CONTEXT, CONSTRUCTOR, 1, B); Decode.octs(UNIVERSAL, PRIMITIVE, CODE_PRINTABLE_STRING, B, &(D_VP->data.e)); Decode_struct_end(B); break; APPENDIX D. EXAMPLE OF CHOICE TYPE ENCODING AND DECODING 1 1 0 default: fprintf(stderr, "Decode_D : No such choice\n"); exitO ; } return (D_VP); } C * Decode_C(class, form, code, B, C_VP) short class; short form; long, code; IOP *B; C *C_VP; •C if (C_VP == NULL) C_VP = (C *) GETBUFCsizeof(C)); C_VP->choice = GetTag(B); switch (C_VP->choice) { case C_f_$tag: Decode_struct_beg(CONTEXT, CONSTRUCTOR, 2, B); Decode.null(UNIVERSAL, PRIMITIVE, CODE.NULL, B, &(C_VP->data.f)); Decode_struct_end(B); break; case C_g_$tag: Decode_struct_beg(CONTEXT, CONSTRUCTOR, 3, B); Decode.octs(UNIVERSAL, PRIMITIVE, CODE_PRINTABLE_STRING, B, &(C_VP->data.g)); Decode_struct_end(B); break; default: fprintf(stderr, "Decode.C : No such choice\n"); exitO ; } return (C_VP); > APPENDIX D. EXAMPLE OF CHOICE TYPE ENCODING AND DECODING A * Decode_A(class, form, code, B, A_VP) s h o r t c l a s s ; s h o r t form; l o n g code; IOP *B; A *A_VP; • C i f (A_VP == NULL) A_VP = (A *) GET B U F ( s i z e o f ( A ) ) ; A_VP->choice = GetTag(B); s w i t c h (A_VP->choice) { case D_d_$tag: case D_e_$tag: Decode_D(-l, -1, -1, B, &(A_VP->data.b)); break; case C _ f _ $ t a g : case C_g_$tag: Decode_C(-l, - i , -1, B, &(A_VP->data.c)); break; d e f a u l t : f p r i n t f ( s t d e r r , "Decode_A : No such c h o i c e \ n " ) ; e x i t ( ) ; } r e t u r n (A_VP); > Appendix E E x a m p l e of U s i n g C A S N l a n d E D L i b r a r y i . The ASN.l Definition (Input of CASNl) 1 PERS0NNELREC0RD DEFINITIONS :: = BEGIN PersorinelRecord • C title number dateOfHire nameOfSpouse child := [APPLICATION 0] IMPLICIT SET Name [0] VisibleString EmployeeNumber [1] Date [2] Name [3] IMPLICIT SEQUENCE OF Childlnformation DEFAULT {} Childlnformation ::= SET • C Name , dateOfBirth [0] Date } Name ::= [APPLICATION 1] IMPLICIT SEQUENCE 'This is the exmaple used by both CCITT X.409 and ISO ASN.l/BER. 112 APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 113 •C givenWame VisibleString, initial VisibleString, familyName VisibleString} EmployeeNumber ::= [APPLICATION 2] IMPLICIT INTEGER Date ::= [APPLICATION 3] IMPLICIT VisibleString END 2. T h e C D e f i n i t i o n ( O u t p u t o f C A S N l ) File P E R S O N N E L R E C O R D . d e f s . c : #include "/spring/yang/pub/defs.h" #include "/spring/yang/pub/element.h" typedef OCTS Date; /* APPLICATION 3 VisibleString */ IDX *Encode_Date(); Date *Decode_Date(); typedef int EmployeeNumber; /* APPLICATION 2 INTEGER */ IDX *Encode_EmployeeNumber(); EmployeeNumber *Decode_EmployeeNumber(); typedef struct Name { /* APPLICATION 1 SET/SEQ */ OCTS givenName; /* VisibleString */ OCTS initial; /* VisibleString */ OCTS familyName; /* VisibleString */ } Name; IDX *Encode_Name(); Name *Decode_Name().; typedef struct Childlnformation { /* SET/SEQ */ Name r l l ; /* Name */ Date dateOfBirth; /* CONTEXT 0 Date */ } Childlnformation; APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 1 1 4 IDX *Encode_ChildInformation(); Childlnformation *Decode_ChildInformation(); typedef struct PersonnelRecord { /* APPLICATION 0 SET/SEQ */ Name r l l ; /* Name */ OCTS title; /* CONTEXT 0 VisibleString */ EmployeeNumber number; /* EmployeeNumber */ Date dateOfHire; /* CONTEXT 1 Date */ Name nameOfSpouse;/* CONTEXT 2 Name */ LIST OF(Childlnformation) child; /* CONTEXT 3 Childlnformation */ } PersonnelRecord; IDX *Encode_PersonnelRecord(); PersonnelRecord *Decode_PersonnelRecord(); File P E R S O N N E L R E C O R D . e n c o d e . c : #include "PERSONNELRECORD.defs.c" IDX * Encode_Date(class, form, code, Date_VP) short class; short form; long code; Date *Date_VP; • C IDX *p; p = (IDX *) Encode_octs(class, form, code, Date_VP); return (p); IDX * Encode.EmployeeNumber(class, form, code, EmployeeNumber.VP) short class; short form; long code; EmployeeNumber *EmployeeNumber_VP; { APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 1 1 5 IDX *p; p = (IDX *) E n c o d e _ i n t ( c l a s s , form, code, EmployeeNumber_VP); r e t u r n ( p ) ; p = (IDX *) E n c o d e _ s t r u c t _ b e g ( c l a s s , form, code); Encode.octs(UNIVERSAL, PRIMITIVE, CODE_VSB_STRING, &(Name_VP->givenName)); Encode.octs(UNIVERSAL, PRIMITIVE, CODE.VSB.STRING, &(Name_VP->initial)); Encode.octs(UNIVERSAL, PRIMITIVE, CODE.VSB.STRING, &(Name_VP->familyName)); Encode.struct.end(DEFINITE); r e t u r n ( p ) ; } IDX * E n c o d e . C h i l d l n f o r m a t i o n ( c l a s s , form, code, C h i l d l n f o r m a t i o n . V P ) s h o r t c l a s s ; s h o r t form; l o n g code; IDX * Encode_Name(class, form, code, Name.VP) s h o r t c l a s s ; s h o r t form; l o n g code; Name *Name_VP; i IDX *p; C h i l d l n f o r m a t i o n f C h i l d l n f o r m a t i o n _ V P ; •c IDX *p; p = (IDX *) E n c o d e _ s t r u c t _ b e g ( c l a s s , form, code); APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 116 Encode_Name(APPLICATION, CONSTRUCTOR, 1, & ( C h i l d I n f o r m a t i o n _ V P - > r l l ) ) ; Encode_struct_beg(CONTEXT, CONSTRUCTOR, 0); Encode.Date(APPLICATION, PRIMITIVE, 3, &(Chil d I n f o r m a t i o n _ V P - > d a t e O f B i r t h ) ) ; Encode_struct_end(DEFINITE); Encode_struct_end(DEFINITE); r e t u r n ( p ) ; > IDX * Encode_PersonnelRecord(class, form, code, PersonnelRecord.VP) s h o r t c l a s s ; s h o r t form; l o n g code; PersonnelRecord *PersonnelRecord_VP; { IDX *p; p = (IDX *) E n c o d e _ s t r u c t _ b e g ( c l a s s , form, code); Encode_Name(APPLICATION, CONSTRUCTOR, 1, &(PersonnelRecord_VP->rll)) ; Encode_struct_beg(CONTEXT, CONSTRUCTOR, 0); Encode.octs(UNIVERSAL, PRIMITIVE, CODE_VSB_STRING, &(Pe r s o n n e l R e c o r d _ V P - > t i t l e ) ) ; Encode_struct_end(DEFINITE); Encode_EmployeeNumber(APPLICATION, PRIMITIVE, 2, &(PersonnelRecord_VP->number)); Encode_struct_beg(CONTEXT, CONSTRUCTOR, 1); Encode_Date(APPLICATION, PRIMITIVE, 3, &(PersonnelRecord_VP->dateOfHire)); Encode_struct_end(DEFINITE); Encode_struct_beg(CONTEXT, CONSTRUCTOR, 2); Encode_Name(APPLICATION, CONSTRUCTOR, 1, APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY &(PersonnelRecord_VP->nameOfSpouse)); Encode_struct_end(DEFINITE) ; Encode_struct_beg(CONTEXT, CONSTRUCTOR, 3, &(PersonnelRecord_VP->child)); L i s t F o r ( P e r s o n n e l R e c o r d _ V P - > c h i l d ) Encode_ChildInformation(UNIVERSAL, CONSTRUCTOR, 17, (PersonnelRecord_VP->child)->next->item); Encode_struct_end(DEFINITE); Encode_struct_end(DEFINITE); r e t u r n ( p ) ; } File PERSONNELRECORD.decode.c: #include "PERSONNELRECORD.defs.c" Date * Decode_Date(class, form, code, B, Date.VP) s h o r t c l a s s ; s h o r t form; l o n g code; IOP *B; OCTS *Date_VP; • C Date.VP = (OCTS *) D e c o d e _ o c t s ( c l a s s , form, code, B, Date.VP); r e t u r n (Date.VP); EmployeeNumber * Decode_EmployeeNumber(class, form, code, B, EmployeeNumber_VP) s h o r t c l a s s ; s h o r t form; l o n g code; IOP *B; i n t *EmployeeNumber_VP; i EmployeeNumber.VP = ( i n t *) D e c o d e _ i n t ( c l a s s , form, code, B, EmployeeNumber.VP) APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 118 r e t u r n (EmployeeNumber.VP); } Name * Decode_Name(class, form, code, B, Name_VP) s h o r t c l a s s ; s h o r t form; l o n g code; IOP *B; Name *Name_VP; • C i f (Name.VP == NULL) Name.VP = (Name *) GETBUF(sizeof(Name)); D e c o d e _ s t r u c t _ b e g ( c l a s s , form, code, B); Decode.octs(UNIVERSAL, PRIMITIVE, CODE.VSB.STRING, B, &(Name_VP->givenName)); Decode.octs(UNIVERSAL, PRIMITIVE, CODE.VSB.STRING, B, &(Name_VP->initial)); Decode.octs(UNIVERSAL, PRIMITIVE, CODE.VSB.STRING, B, &(Name_VP->familyName)) ; Decode.struct.end(B); r e t u r n (Name.VP); } C h i l d l n f o r m a t i o n * D e c o d e _ C h i l d I n f o r m a t i o n ( c l a s s , form, code, B, C h i l d l n f o r m a t i o n . V P ) s h o r t c l a s s ; s h o r t form; l o n g code; IOP *B; C h i l d l n f o r m a t i o n *ChildInformation_VP; • C i f ( C h i l d l n f o r m a t i o n . V P C h i l d l n f o r m a t i o n . V P = NULL) ( C h i l d l n f o r m a t i o n *) GETBUF ( s i z e o f ( C h i l d l n f o r m a t i o n ) ) ; D e c o d e _ s t r u c t _ b e g ( c l a s s form, code, B) ; APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 119 Decode_Name(APPLICATION, CONSTRUCTOR, 1, B, &(ChildInformation_VP->rll)); Decode_struct_beg(CONTEXT, CONSTRUCTOR, 0, B); Decode_Date(APPLICATION, PRIMITIVE, 3, B, ' &(ChildInformation_VP->dateOfBirth)); Decode_struct_end(B); Decode_struct_end(B); return (Childlnformation.VP); } PersonnelRecord * Decode_PersonnelRecord(class, form, code, B, PersonnelRecord_VP) short class; short form; long code; IOP *B; PersonnelRecord *PersonnelRecord_VP; { if (PersonnelRecord_VP == NULL) PersonnelRecord.VP = (PersonnelRecord *) GETBUF (sizeof(PersonnelRecord)); Decode_struct_beg(class, form, code, B); Decode_Name(APPLICATION, CONSTRUCTOR, 1, B, &(PersonnelRecord_VP->rll)); Decode_struct_beg(CONTEXT, CONSTRUCTOR, 0, B); Decode.octs(UNIVERSAL, PRIMITIVE, CODE.VSB.STRING, B, &(PersonnelRecord_VP->title)); Decode_struct_end(B); , Decode_EmployeeNumber(APPLICATION, PRIMITIVE, 2, B, &(PersonnelRecord_VP->number)); Decode_struct_beg(CONTEXT, CONSTRUCTOR, 1, B); Decode_Date(APPLICATION, PRIMITIVE, 3, B, &(PersonnelRecord.VP->date0fHire)); APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY Decode_struct_end(B); Decode_struct_beg(CONTEXT, CONSTRUCTOR, 2, B); Decode_Name(APPLICATION, CONSTRUCTOR, 1, B, &(PersonnelRecord_VP->nameOfSpouse)); Decode_struct_end(B); Decode_struct_beg(CONTEXT, CONSTRUCTOR, 3, B, &(PersonnelRecord_VP->child)); w h i l e ( L i s t E n d ( B ) ) ListAppend(&(PersonnelRecord_VP->child), Decode_ChildInformation(UNIVERSAL, CONSTRUCTOR, 17, B, 0 ) ) ; Decode_struct_end(B); Decode_struct_end(B); r e t u r n (PersonnelRecord.VP); } 3. Appl ica t ion Program #include "PERSONNELRECORD.defs.c" /* * main - example program f o r PersonnelRecord encode/decord * */ main() •c byte *octseq; IOP bp; IDX * p t r ; i n t i , l e n ; PersonnelRecord value, *v; C h i l d l n f o r m a t i o n *p; /* * * a s s i g n the data s t r u c t u r e example values * ;  */ i f (INIT != TRUE) APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 121 INITSYSO; value. r l l . g i v e n N a m e . n e x t = NULL; v a l u e . r l l . g i v e n N a m e . l e n = 4; va l u e . r l l . g i v e n N a m e . d a t a = (byte *) "John"; /* o c t e t s t r */ v a l u e . r l l . i n i t i a l . n e x t = NULL; v a l u e . r l l . i n i t i a l . l e n = 1; v a l u e . r l l . i n i t i a l . d a t a = (byte *) "P"; /* o c t e t s t r */ v a l u e . r l l . f a m i l y N a m e . n e x t = NULL; v a l u e . r l l . f a m i l y N a m e . l e n = 5; v a l u e . r l l . f a m i l y N a m e . d a t a = (byte *) "Smith";/* o c t e t s t r */ v a l u e . t i t l e . n e x t = NULL; v a l u e . t i t l e . l e n = 8 ; v a l u e . t i t l e . d a t a = (byte *) " D i r e c t o r " ; /* o c t e t s t r */ value.number = 5 1 ; /* INTEGER */ v a l u e . d a t e O f H i r e . n e x t = NULL; v a l u e . d a t e O f H i r e . l e n = 8; v a l u e . d a t e O f H i r e . d a t a = (byte *) "19710917"; /* o c t e t s t r */ value.nameOfSpouse.givenName.next = NULL; value.nameOfSpouse.givenName.len = 4; value.nameOfSpouse.givenName.data = (byte *) "Mary"; /* o c t e t s t r */ va l u e . n a m e O f S p o u s e . i n i t i a l . n e x t = NULL; v a l u e . n a m e O f S p o u s e . i n i t i a l . l e n = 1 ; v a l u e . n a m e O f S p o u s e . i n i t i a l . d a t a = (byte *) "T";/* o c t e t s t r */ value.nameOfSpouse.familyName.next = NULL; value.nameOfSpouse.familyName.len = 5; value.nameOfSpouse.familyName.data = (byte *) "Smith"; /* o c t e t s t r */ p = ( C h i l d l n f o r m a t i o n * ) G E T B U F ( s i z e o f ( C h i l d l n f o r m a t i o n ) ) ; p->rll.givenName.next = NULL; p->rll.givenName.len = 5; p->rll.givenName.data = (byte *) "Ralph"; /* o c t e t s t r i n g */ p - > r l l . i n i t i a l . n e x t = NULL; p - > r l l . i n i t i a l . l e n = 1; p - > r l l . i n i t i a l . d a t a = (byte *) "T"; /* o c t e t s t r */ APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 122 p->rll.familyName.next = NULL; p- > r l l . f a m i l y N a m e . l e n = 5; p->rll.familyName.data = (byte *) "Smith"; /* o c t e t s t r */ p->dateOfBirth.next = NULL; p - > d a t e O f B i r t h . l e n = 8; p-> d a t e O f B i r t h . d a t a = (byte *) "19571111"; /* o c t e t s t r */ L i s t A p p e n d ( & ( v a l u e . c h i l d ) , p ) ; p = ( C h i l d l n f o r m a t i o n * ) G E T B U F ( s i z e o f ( C h i l d l n f o r m a t i o n ) ) ; p->rll.givenName.next = NULL; p->rll.givenName.len = 5; p->rll.givenName.data = (byte *) "Susan"; /* o c t e t s t r i n g */ p - > r l l . i n i t i a l . n e x t = NULL; p - > r l l . i n i t i a l . l e n = 1 ; p - > r l l . i n i t i a l . d a t a = (byte *) "B"; /* o c t e t s t r */ p->rll.familyName.next = NULL; p - > r l l . f a m i l y N a m e . l e n = 5 ; p->rll.familyName.data = (byte *) "Jones"; /* o c t e t s t r */ p->dateOfBirth.next = NULL; p - > d a t e O f B i r t h . l e n = 8 ; p->d a t e O f B i r t h . d a t a = (byte *) "19590717"; /* o c t e t s t r */ L i s t A p p e n d ( & ( v a l u e . c h i l d ) , p ) ; p r i n t f ( " O r i g i n a l v a l ue of PersonnelRecord:\n\n"); p r i n t R E C ( & ( v a l u e ) ) ; /* * ; * Encode the dat a s t r u c t by ED encode r o u t i n e s * */ p t r = (IDX *) Encode_PersonnelRecord (APPLICATION, CONSTRUCTOR, 0, & ( v a l u e ) ) ; /* * * S e r i l i z e the IDX l i n k i n t o o c t e t sequence and p r i n t i t . * */ APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY o c t s e q = (byte *) s e r I D X ( p t r , ftoctseq, &len); p r i n t f ("\n\riTransf e r Syntax of PersonnelRecord: \n" ) ; p r i n t s ( o c t s e q , l e n , TRUE); /* * * Decode the o c t e t sequence and p r i n t the producted d a t a * */ bp.b = oc t s e q ; bp.f = NULL; bp.fname = NULL; v = (PersonnelRecord *) Decode_PersonnelRecord (APPLICATION, CONSTRUCTOR, 0 , &bp, 0 ) ; p r i n t f ( " \ n \ n D e c o d e d value o f PersonnelRecord:\n"); p r i n t R E C ( v ) ; /* * * r e l e a s e a l l o c a t e d memory space * */ RESETMEMO ; > /* _ * printREC - p r i n t d a t a s t r u c t u r e PersonnelRecord * */ printREC(m) /* p r i n t out the PersonnelRecord */ PersonnelRecord *m; { i n t i ; p r i n t f ( " P e r s o n n e l R e c r d { \ n " ) ; p r i n t f ( " Name {\n"); APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 124 p r i n t f ( " givenName : ") poets(&(m->rll.givenName)); p r i n t f ( " i n i t i a l : ") p o e t s ( & ( m - > r l l . i n i t i a l ) ) ; p r i n t f ( " familyName : ") poets(&(m->rll.familyName)); p r i n t f ( " >\n"); p r i n t f ( " t i t l e : " ) ; p o e t s ( & ( m - > t i t l e ) ) ; p r i n t f (" EmployeeNumber : 7,d\n" , m->number) ; p r i n t f ( " d a t e OfHire : " ) ; poets(&(m->dateOfHire)); p r i n t f ( " nameOfSpouse{\n"); p r i n t f ( " givenName : " ) ; poets(&(m->nameOfSpouse.givenName)); p r i n t f ( " i n i t i a l : " ) ; poets(&(m->nameOfSpouse.initial)); p r i n t f ( " familyName : " ) ; poets(&(m->nameOfSpouse.familyName)); p r i n t f ( " }\n"); p r i n t f ( " C h i l d I n f o r m a t i o n { \ n " ) ; L i s t F i r s t ( ( m - > c h i l d ) ) ; L i s t F o r ( m - > c h i l d ) { p r i n t f ( " {\n"); p r i n t f ( " Name -f_\n"); p r i n t f ( " givenName : " ) ; pocts(&(m->child->next->item->rll.givenName)); p r i n t f ( " i n i t i a l : ") p o c t s ( & ( m - > c h i l d - > n e x t - > i t e m - > r i l . i n i t i a l ) ) p r i n t f ( " familyName: ") poets(&(m->child->next->item->rll.familyName)); p r i n t f ( " }\n"); p r i n t f ( " d a t e O f B i r t h : " ) ; poets(&(m->child->next->item->dateOfBirth)); p r i n t f ( " }\n }\n"); APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 125 4 . Application Program Compilation Makefile OBJS = PERSONNELRECORD.encode.o PERSONNELRECORD.decode.o \ /spring/yang/the/ED/o/*o example.o example : $(0BJS) cc -g -o example $(0BJS) example.o : example.c cc -g -c example.c PERSONNELRECORD.encode.o: PERSONNELRECORD.encode.c cc -g -c PERSONNELRECORD.encode.c PERSONNELRECORD.decode.o: PERSONNELRECORD.decode.c cc -g -c PERSONNELRECORD.decode.c 5. Application Program Execution Script O r i g i n a l v a lue o f PersonnelRecord: PersonnelRecrd{ Name { givenName : John ( 4 ) i n i t i a l : P ( i ) familyName : Smith (5) } t i t l e : D i r e c t o r (8) EmployeeNumber : 51 da t e O f H i r e : 19710917 (8) nameOfSpouse{ givenName : Mary ( 4 ) i n i t i a l : T (1) familyName : Smith (5) } C h i l d l n f o r m a t i o n { { Name { givenName : Ralph (5) i n i t i a l : T (1) familyName: Smith (5) } APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 126 d a t e O f B i r t h : 19571111 (8) } • C Name { givenName : Susan (5) i n i t i a l : B (1) familyName: Jones (5) } d a t e O f B i r t h : 19590717 (8) } > T r a n s f e r Syntax of PersonnelRecord: 60 81 85 61 10 l a 4 4a 6f 68 6e l a 1 50 l a 5 53 6d 69 74 68 ' a J o h n P S m i t h aO a l a 8 44 69 72 65 63 74 6f 72 42 1 33 a l a 43 8 31 39 D i r e c t o r B 3 C 1 9 37 31 30 39 31 37 a2 12 61 10 l a 4 4d 61 72 79 l a 1 54 l a 5 7 1 0 9 1 7 a M a r y T 53 6d 69 74 68 a3 42 31 I f 61 11 l a 5 52 61 6c 70 68 l a 1 54 S m i t h B l a R a l p h T l a 5 53 6d 69 74 68 aO a 43 8 31 39 35 37 31 31 31 31 31 I f S m i t h ' C 1 9 5 7 1 1 1 1 1 61 11 l a 5 53 75 73 61 6e l a 1 42 l a 5 4a 6f 6e 65 73 aO a a S u s a n B J o n e s 43 8 31 39 35 39 30 37 31 37 C 1 9 5 9 0 7 1 7 Decoded value o f PersonnelRecord: PersonnelRecrd{ Name { givenName : John (4) i n i t i a l : P (1) familyName : Smith (5) > t i t l e : D i r e c t o r (8) APPENDIX E. EXAMPLE OF USING CASNl AND ED LIBRARY 1 2 7 EmployeeNumber : 51 da t e O f H i r e : 19710917 (8) nameOfSpouse{ givenName : Mary (4) i n i t i a l : T (1) familyName : Smith (5) } C h i l d l n f o r m a t i o n - C { Name { givenName : Ralph (5) i n i t i a l : T (1) familyName: Smith (5) } d a t e O f B i r t h : 19571111 (8) > { Name { givenName : Susan (5) i n i t i a l : B (1) familyName: Jones (5) } d a t e O f B i r t h : 19590717 (8) } } 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051939/manifest

Comment

Related Items