UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

How fast can ASN.1 encoding rules go? Sample, Michael 1993

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

Item Metadata

Download

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

Full Text

HOW FAST CAN ASN.1 ENCODING RULES GO?ByMichael SampleB. Sc. (Computer Science) University of British ColumbiaA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE FACULTY OF GRADUATE STUDIESCOMPUTER SCIENCEWe accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIAApril 1993© Michael Sample, 1993In presenting this thesis in partial fulfilment of the requirements for an advanced degree atthe University of British Columbia, I agree that the Library shall make it freely availablefor reference and study. I further agree that permission for extensive copying of thisthesis for scholarly purposes may be granted by the head of my department or by hisor her representatives. It is understood that copying or publication of this thesis forfinancial gain shall not be allowed without my written permission.Computer ScienceThe University of British Columbia2075 Wesbrook PlaceVancouver, CanadaV6T 1Z1Date:AbstractThe tasks of encoding and decoding complex data structures for network transmission aremore expensive in terms of processor time and memory usage than any other componentsof the protocol stack. This problem can be partially addressed by simplifying the networkdata encoding rules and streamlining their implementation.We examined the performance of four network data representation standards: ASN.1Basic Encoding Rules (BER) and Packed Encoding Rules (PER), Sun Microsystem'sExternal Data Representation (XDR) and HP/Apollo's Network Data Representation(NDR). The sizes of the encoded values produced by each set of encoding rules arecompared and several implementations are measured for code size and throughput.To help examine implementation issues, we designed the snacc ASN.1 compiler thatproduces compile-based (C and C++) and table-based encoders and decoders as wellas type tables. The performance of the snacc, UBC CASN1(BER), NIDL(NDR), rpc-gen(XDR) and ISODE(BER) tools was examined as well as a hand-coded PER imple-mentation. The implementation issues investigated include compiled versus table-basedencoding and decoding, implementation language (C/C++), buffering techniques andmemory management.We found that the areas crucial to efficient encoder and decoder implementationsare memory management, buffer management and the overall simplicity of the encodingrules. Table-based encoders and decoders typically have considerably smaller code sizebut perform less efficiently than their compiled counterparts. In contrast to popularbelief, it is possible to implement ASN.1 BER and PER encoders and decoders thatperform as well as their NDR and XDR counterparts.iiTable of ContentsAbstract^ iiList of Tables^ viiList of Figures^ viiiAcknowledgement^ ixDedication^ x1 Introduction 11.1 The Need for Network Data Representations ^ 21.2 The Performance Problem ^ 31.3 Our Research Goal 52 Data Definition Languages and Encoding Rules 72.1 Data Definition Languages ^ 92.2 General Aspects of Encoding Rules ^ 102.3 General Encoding and Decoding Procedures ^ 132.4 ASN.1: Abstract Syntax Notation One and its Encoding Rules ^ 132.4.1^ASN.1: The language ^ 142.4.2^BER: Basic Encoding Rules 152.4.3^PER: Packed Encoding Rules ^ 162.5 XDR: External Data Representation 32iii2.5.1 The XDR language ^  322.5.2 XDR Encoding Rules  322.6 NIDL/NDR ^  332.6.1 NIDL: Network Interface Definition Language ^ 332.6.2 NDR: Network Data Representation ^  342.7 C Based Encoding Rules ^  363 Related Work^383.1 Performance Issues and Ideas^ 384 Performance Considerations for the Snacc ASN.1 Compiler^414.1 Snacc Design Process and Goals ^  414.2 ASN.1 to C Data Structure Translation  434.3 Generated C Encoder Design ^  444.4 Generated C Decoder Design  464.5 Error Management ^  484.6 Compiler Directives  504.7 Buffer Management ^  534.8 Memory Management  554.9 Novel Non-performance Related Features ^  564.10 C++ Design ^  594.11 Table Driven Encoding and Decoding ^  625 Implementation of the Snacc Compiler^ 645.1 Snacc Compiler Design ^  645.2 Pass 1: Parsing the Useful Types Module ^  655.3 Pass 2: Parsing ASN.1 Modules ^  67iv5.4 Pass 3: Linking Types ^  685.5 Pass 4: Parsing Values  695.6 Pass 5: Linking Values  ^715.7 Pass 6: Processing Macros ^  725.8 Pass 7: Normalizing Types  745.9 Pass 8: Marking Recursive Types ^  755.10 Pass 9: Semantic Error Checking  765.11 Pass 10: Generating C/C++ Type Information ^ 775.12 Pass 11: Sorting Types  ^805.13 Pass 12: Generating Code ^  836 Results and Evaluation^ 856.1 The PersonnelRecord Benchmark ^  866.1.1 Tools Benchmarked  866.1.2 Benchmark Design ^  886.1.3 Benchmark Results and Analysis ^  916.2 Primitive Type Benchmarks ^  1096.2.1 Benchmark Design  1106.2.2 Benchmark Results ^  1116.3 Benchmark of Implementation Features ^  1156.3.1 Benchmark Design ^  1156.3.2 Benchmark Results  1166.4 Execution Analysis ^  1197 Conclusions^ 121Appendices^ 123vA C Example^ 124B C++ Example^ 148C The Type Table Data Structure^ 181Bibliography^ 184viList of Tables2.1 PER field types and sizes for constrained whole numbers ^ 212.2 Examples of length upper and lower bounds for BIT STRING types .^252.3 Examples of upper and lower bounds for OCTET STRING types . .^262.4 Examples of upper and lower bounds for SEQUENCE OF types ^ 286.5 Tools and encoding rules tested with the PersonnelRecord Benchmark . . 876.6 Benchmark descriptions   926.7 Code size for the stripped .o files of PersonnelRecord specific code and thestripped benchmark executable ^  926.8 Timings for encoding and decoding the PersonnelRecord 1 million times ^ 936.9 Memory usage in # pieces memory/total # bytes for the local, interme-diate and transfer (encoded) data representation ^ 936.10 Primitive type benchmark definitions ^  1126.11 Results for integer ^  1136.12 Results for real  1136.13 Results for string ^  1136.14 Benchmarks of BER implementation features ^  1176.15 Results for encoding and decoding the PersonnelRecord 1 million times^1176.16 Results for encoding and decoding an X.500 ListResult 10,000 times . .^1186.17 Overall cost of buffer and memory management for snacc's BER and PERencoders and decoders ^  119viiList of Figures2.1 A typical compilation process  ^82.2 An Internet Protocol (IP) header description  ^92.3 The encoding and decoding process ^  124.4 The snacc compiler produces C or C++ BER encode, BER decode, printand free routines or a type table.  ^424.5 The setjmp function is called before decoding ^  504.6 The longjmp function is called to signal an error  ^506.7 ASN.1 definition of the PersonnelRecord ^  896.8 PersonnelRecord Value used in the benchmarks  906.9 Time to encode and decode a PersonnelRecord 1 million times ^ 946.10 ISODE's local representation for the PersonnelRecord Value ^ 976.11 ISODE's PElement representation for the PersonnelRecord Value^986.12 CASN1 local representation for the PersonnelRecord Value ^ 1006.13 CASN1's IDX buffer structure for the PersonnelRecord Value ^ 1016.14 XDR PersonnelRecord Definition ^  1036.15 XDR's local representation for the PersonnelRecord Value ^ 1046.16 NIDL's local representation for the PersonnelRecord Value ^ 1066.17 NIDL PersonnelRecord Definition ^  1076.18 Snacc's local representation for the PersonnelRecord Value ^ 108A.19 PersonnelRecord ASN.1 data structure ^  125viiiAcknowledgementI would like to thank my loving parents for support and encouragement throughout myscholastic endeavors. In particular, tolerance of my running off to play in the mountainswhen I should have been studying.I would also like to thank Gerald Neufeld, my supervisor and friend, for his guidanceand ideas. Without his encouragement I would not have entered the M. Sc. program.Thanks also to Norm Hutchinson for plowing through this thesis.Many thanks to Barry Brachman for the suggestions, X.500 data, incredible proofreading and the jam sessions. Don Acton provided huge amounts of help with obscurefeatures of Latex, Emacs, Foiltex and other software packages. I also appreciated thehelp and support of other friends in the department: Carlin, Frank, John, George, Ian,Mike, Ming, Moyra, Murray, Peter, Stuart and Terry.Thanks to the office staff: Carol, Evelyn, Gale, Grace, Joyce, Katie, Monica and Sun-nie for cutting through the UBC bureaucracy and handling last minute courier packages.ixFor RickxChapter 1IntroductionComputer networks spawned the need for a mechanism to translate data between machinearchitectures and applications. This translation process can be a significant part of thetime it takes to process received protocol data units (PDUs) [Clark89]. In addition, theamazing speeds at which newer networks based on asynchronous transfer mode (ATM)or fiber distributed data interchange (FDDI) can deliver data to computers has increasedthe need for high performance translation mechanisms.Using faster processors will help, but the gap between processor speed and networkspeed is large. For example, if a computer receives a burst of data from a 150 MbpsATM connection, each byte of data must be processed in only 53 nanoseconds. This isless than the memory cycle time on most workstations. To make matters worse, typicalprotocol implementations make one or more copies of the PDU's data as it moves up theprotocol stack.Flow control is another possible technique to avoid overwhelming a receiving host.Flow control is a difficult issue because traffic can vary so much that a pessimistic flowcontrol mechanism may limit the network usage to much below its maximum bandwidth.Optimistic flow control that allows bursts of traffic will not solve the problem.There is no obvious single solution to the protocol performance problem. However,we can start by improving the performance of time-consuming components of computercommunication, such as data translation to minimize the chances of overwhelming anetworked computer with too much data. This thesis examines the optimization of the1Chapter 1. Introduction^ 2data translation part of computer communications.1.1 The Need for Network Data RepresentationsThe need for network data representations has been around since computers were con-nected to networks. A canonical representation enables computers with different ar-chitectures to exchange data and typically simplifies data transmission by grouping or"marshalling" the data into a single logical block. Within the OSI protocol stack, en-coding from a local machine representation to a canonical representation (as well asdecoding) is done at the Presentation Layer [OS188].The need can be illustrated with the simple example of the big versus little endianrepresentation of integers. Consider an MC68000 based machine (big endian) and anInte180486 based machine (little endian) on a network. By sending the integer 17 in itsMC68000 representation from the MC68000 to the Inte180486 without translation, thenumber will be interpreted as 16842752 on the Inte180486. This is clearly undesirable.There are many representation issues involving integers alone, such as l's versus 2'scomplement or 2 versus 4 byte or larger integers. Other types, such as real numbers andcharacter strings (e.g. ASCII or EBCDIC), add to the translation problems.Converting simple types such as integers and strings is not enough. Data groupingconcepts like linked lists, structures (struct) in the C programming language and Pascalrecords need to be supported as well.There have been many data representation standards defined in the last two decades.These include:• ISO/CCITT's Basic Encoding Rules (BER) [BER88]• ISO/CCITT's Packed Encoding Rules (PER) [PER92]Chapter 1. Introduction^ 3• Sun's eXternal Data Representation (XDR) [Sun87]• HP/Apollo's Network Data Representation (NDR) [Kong90]• Xerox's Courier [Xerox8l]• NIST's Computer Based Message System [NBS83]• Multi-Media Mail [Poste180]These encoding rules all solve the same problems. The types they support are muchthe same except that Multi-Media Mail proposed a shared reference type that is missingfrom the others. A shared reference type is potentially useful for complex data structuresthat have indexes and cycles.1.2 The Performance ProblemThe advent of high speed networks such as FDDI and ATM has moved the performancebottleneck into the higher layers of the protocol stack. Work on optimizing transportprotocols indicates that some of the most expensive parts of a protocol implementationare buffer management and memory copying [Clark89]. These problems also exist in thePresentation Layer.Perhaps the most expensive part of the OSI protocol stack is the Basic Encoding Rules(BER) encoding and decoding done in the presentation layer. A substantial amount ofthe protocol stack's processing total time can be used for encoding and decoding alone[Clark90]. There are several possible ways to reduce this overhead:• use non-standard data representations tuned for the application• use non-standard data representations tuned for the implementationChapter 1. Introduction^ 4• design and use lightweight encoding rules• optimize implementations of existing encoding rulesData representations that are tuned for a particular application or protocol can bevery efficient. TCP and IP packet definitions are examples of this technique. Unfortu-nately, this method becomes cumbersome with more complex data structures that havemany optional or variable-sized components.Assumptions based on the implementation and target environment can be used tooptimize encoding rules. For example, if the target environment is a network of Sunworkstations and the application is written in the same language on each host, complexdata structures may be exchanged simply by grouping the components and translatingpointers to offsets. This method works efficiently but is fragile with respect to the ar-chitecture of the communicating hosts; it is not a general purpose solution. Adding amachine with a different architecture to the network, such as a Inte180486 machine, wouldcause problems. This solution also assumes that the data structure used by the senderand receiver are identical.Using lightweight encoding rules is a reasonable approach [Huitema89], however, someflexibility may be sacrificed (e.g. using fixed-size integers) to simplify them. Optimizingimplementations of the existing general purpose encoding rules, if possible, is a desirablesolution as the protocol and application designers benefit from the rules' flexibility.We did not attempt to design new encoding rules or examine the less general pur-pose optimization techniques. Instead, we focussed on optimizing the implementation ofgeneral purpose encoding rules such as BER.Chapter 1. Introduction^ 51.3 Our Research GoalWe examined the performance of four network data representation standards: BER,PER, XDR and NDR. BER, XDR and NDR are popular encoding rules. PER [PER92]have recently been introduced and are likely to be widely used. We looked at the sizeof the encoded values and the performance of several implementations to determine thecritical implementation issues.The size of an encoded value generated by a given set of encoding rules can beimportant when dealing with networks that are slow or have a high cost per packet.Other considerations include storing data on machines with limited disk space. Withdisks and memory becoming cheaper and networks becoming faster, a more importantconsideration is throughput.The throughput of several implementations of BER, XDR and NDR and a handcoded PER implementation is measured. The object code size and dynamic memoryusage of these implementations is also examined. While the dollar cost of RAM memoryis small these days, code size and memory usage must be considered for their impact onthroughput.To help examine implementation issues, we implemented the snacc (Sample NeufeldASN.1 to C/C++ Compiler) ASN.1 compiler which produces C and C++ BER encodersand decoders as well as type tables. The performance of the snacc, UBC CASN1(BER),NIDL(NDR), rpcgen(XDR) and ISODE(BER) tools is examined, as well as a hand-coded PER implementation. The implementation issues investigated include compiledversus table-based encoding and decoding, implementation language (C/C++), bufferingtechniques and memory management.This thesis assumes the reader is familiar with ASN.1 [ASN188], BER [BER88], XDR[Sun87] and NDR [Kong90]. Several ASN.1 and BER tutorials are available [Steedman90]Chapter 1. Introduction^ 6[Neufeld92-1].The next chapter introduces the concept of data definition languages and data for-mats, covering the ASN.1, XDR and NIDL languages and the BER, PER, XDR andNDR encoding rules. PER are described in depth since they are a very new standard[PER92].In Chapter three we survey previous efforts to improve the performance of encodingrules. The performance-related aspects of the snacc compiler: its implementation and thecode it generates, are given in Chapters four and five. The metrics used to benchmarkthe encoding rules, the tools that implement them and an analysis of the results are givenin Chapter six. The final chapter contains the conclusions drawn from our research. Theappendix contains a C and C++ example of snacc generated code and the type table'sASN.1 data structure definition.For those familiar with ASN.1, XDR and NDR, Chapters six and seven will likely bethe most interesting. Implementors may wish to focus on Chapters three, four and sixas well as the app^ endices. Users interested in using the snacc compiler shouser manual [Sample93-1].Chapter 2Data Definition Languages and Encoding RulesData definition languages are used to specify the content and structure of data. Theencoding rules specify how a particular value of a data structure will be represented.A data definition language is referred to as an abstract syntax notation. The transfersyntax defines the way a particular instance of the application data structure is encoded.A particular data structure in the abstract syntax notation is referred to as an abstractsyntax.An example will clarify these definitions. If you wanted to specify a data structurethat contained the date (year, month, day), the abstract syntax in ASN.1 might looklike:Date ::= SEQUENCE{year INTEGER,month INTEGER (1..12),day^INTEGER (1..31)The Date value "May 1, 1993" encoded according to the BER transfer syntax is(shown in hexadecimal):300a020207c9020105020101All of the transfer syntaxes (encoding rules) that we tested grouped the representedvalues into a single logical block. The grouped or marshalled data can easily be passedto the transport layer.7Chapter 2. Data Definition Languages and Encoding Rules^ 8 DataStructureDescriptionFigure 2.1: A typical compilation processTypically the data definition languages are designed to be processed by a compilerthat generates encoders, decoders and other utility routines for the given data struc-ture in a target programming language such as C or Pascal (see Figure 2.1). Otherapproaches include extending a programming language's grammar to handle the datadefinition language internally [Bochman89].Data languages such as ASN.1 are used to define protocol data units (PDUs) inprotocol standards such as X.400 [MHS88] and X.500 [DS88]. The protocol definitiondocuments for protocols such as TCP and IP use ASCII drawings (see Figure 2.2) andtext that describe both the type content (abstract syntax) and representation (transfersyntax) of their PDUs.Using data definition languages with encoding rules separates the abstract syntaxfrom the transfer syntax. The data descriptions are more formal, with less chance forambiguity. Once a data definition language has been learned, it provides a high level wayto think about and design data structures. Another benefit of data languages is that theycan be compiled for automatic implementation of encoders, decoders and other routines.The advantages of the TCP/IP style of PDU definition is that the definitions are selfcontained (no other documents or language understanding is needed) and the PDUs canbe very compact. Also, by placing the fixed-sized components first, the decoding cost isreduced or eliminated. The disadvantage is that the use of fixed-size types limits theirChapter 2. Data Definition Languages and Encoding Rules^ 90^ 1^ 2^ 30 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+IVersionl IHL 'Type of Servicel^Total Length^I+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+I^Identification^'Flags'^Fragment Offset^I+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+I Time to Live I^Protocol^I^Header Checksum^I+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+I^ Source Address I+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+I Destination Address^ I+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+I^ Options^ I^Padding^I+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+Figure 2.2: An Internet Protocol (IP) header descriptionexpansion possibilities (e.g. the IP address space is now too small and cannot easilygrow). Also, this style of PDU definition becomes very cumbersome when the number ofcomponents is large, especially if many of the components are not fixed in size.2.1 Data Definition LanguagesThere are two main uses for data structures defined in a standardized data language.One purpose is to specify the content and structure of a PDU for a certain protocol. Forexample, the protocol definition documents for X.500, X.400, SNMP [snmp90], Kerberos[Steiner88] [Koh192] and WAIS [Z39.50] use ASN.1 to define their PDUs.The other use of the data specifications is to implement part of the protocol. Special-purpose compilers are usually used to automatically generate the encode, decode andutility routines for the PDUs.The languages in our performance test used two different approaches to define theChapter 2. Data Definition Languages and Encoding Rules^ 10language. NIDL and XDR are defined very closely to an existing programming language,C, to simplify their usage by programmers already familiar with C. This advantage isoffset by the fact that it biases the protocol implementation towards a particular language.This problem is highlighted by the fact that NIDL has a Pascal variant in addition tothe C version.The data structures defined in these languages have extra information, such aswhether a component of a struct is referenced by a pointer. This is a local datarepresentation issue that should not be dictated by a protocol standard. The imple-mentation language bias and local representation information in XDR and NIDL makethem unsuitable for heterogeneous protocol specification.ASN.1 takes a different approach. The key concepts of data structures were abstractedand separated from other implementation-specific concepts such as pointers. The factthat ASN.1 did not evolve from an implementation language such as C leaves it free tochange independently of the implementation language. The disadvantage of the ASN.1approach lies in the fact that implementors need to become familiar with a completelynew and complex language.2.2 General Aspects of Encoding RulesThere are several approaches to network data representation:• a single standardized data format• data format defined by sending host• data format defined by receiving hostUsing a single standardized format means that each host only needs a single set ofencoding and decoding routines for each primitive type. The other techniques may beChapter 2. Data Definition Languages and Encoding Rules^ 11optimal if the communicating hosts have the same architecture, but in general moreencoding and decoding routines will be needed. Specifically, if there are N machineformats and the data format is defined by the sending host, each host will need N — 1decoding routines.Encoding rules can support self-defining values. Self-defining means that type in-formation is included in the values. Other terms that have been used to describe thisinclude explicit (self-defining) and implicit type representation [DeShon86] [Partridge89].Self defining values allow the implementation of "generic" decoders, useful for implemen-tations and protocol testing.One-pass encoding and decoding is defined as conversion between the local (non-standardized) and transfer representation that can be done in one step, without usingintermediate representations. This improves performance.Some encoding rules can produce canonical encodings where each abstract value mapsto exactly one encoding. This can be useful for generating digital signatures for securitypurposes. A simple example of this is the encoding of boolean values. Some encodingrules allow "true" to be encoded as any non-zero integer. The fact that "true" can beencoded many ways implies that the encoding rules are not canonical.Encoding rules that have relay safe encodings means that encoded values can berelayed or otherwise handled by systems that do not know the values' abstract syntaxes.It is important to distinguish between forward and backward encoding and decodingtechniques. In forward encoding, the first component of the encoded value is calculatedand written first with the following components appended to it. Backward encodingis the process of writing the last component of an encoded value and prepending thepreceding components. The same terms can be applied to decoding, however, all of theencoding rules and implementations we tested used forward decoders...< decode19590621-->. James^ R>. Smithencode4 ›^.. Lisa1 —›. M5 Smith5>^ MaryL›^- Smith14 ›^.. John^ The Big Cheese99999 8 --›- 19820104›^.•> E.___,—>. SmithChapter 2. Data Definition Languages and Encoding Rules^ 12Local Representation0060818c611016044a6f686e1601451605536d697468a010160e5468652042696720436865657365420301869fa10a43083139383230313034a212611016044d61727916014c1605536d697468a341311f611116054a616d65731601521605536d697468a00a43083139353730333130311e611016044c69736116014d1605536d697468a00a43083139363130363231Network Representation(in hex)Figure 2.3: The encoding and decoding processPrimitive types are types such as integers that are not composed of other types.Constructed types are types such as lists and structures that are composed of one or moreprimitive or constructed types. We shall refer to the types that make up a constructedtype as its components.Another aspect of encoding rules that should be considered is their expected longevity.Will they need to be modified as architectures move from 32 to 64 bit words and beyond?Ideal encoding rules would be simple, canonical, relay safe and support fast encodingand decoding as well as compact encodings.Chapter 2. Data Definition Languages and Encoding Rules^ 132.3 General Encoding and Decoding ProceduresEncoding is the translation of a local representation of a data value to its network format(see Figure 2.3). Generally, encoding consists of three parts:• encoding primitive values into their network format• allocating a send buffer as necessary• writing the data in its network format into the send bufferDecoding is the process of converting a value from the transfer or external format intoa local representation of the value. There are three main parts to the decoding process:• reading from the receive buffer• decoding primitive data in its network format into its local representation• allocating space for the decoded valueThe goal is to optimize each of these steps. The choice of buffer and memory manage-ment schemes is very important as the encoding and decoding processes can make heavyuse of their services. The other consideration is the cost of translating the primitive typesbetween the local and network format.2.4 ASN.1: Abstract Syntax Notation One and its Encoding RulesASN.1 and BER were initially designed as part of the 1984 ISO/CCITT X.400 electronicmail standard [ASN184]. They are a flexible and robust means of defining protocol datastructures and representing their values.Since many other applications and protocols could benefit from the general purpose,robust nature of ASN.1/BER, they were moved out of the X.400 standard and becameChapter 2. Data Definition Languages and Encoding Rules^ 14separate standards in 1988, CCITT X.208 and X.209 (or ISO/IEC 8824 and 8825) re-spectively. ASN.1 and BER were split into two separate standards for the reason thatmore that one set of encoding rules could be used with ASN.1.Between 1984 and 1988 many features were added to the ASN.1 language, such assubtyping, a powerful type constraining mechanism. The 1992 version of ASN.1 solvessome of the parsing and semantic problems of ASN.1 '88.2.4.1 ASN.1: The languageASN.1 is a rich language that defines types. It does not contain imperative semanticsof typical programming languages nor is its syntax similar to any popular programminglanguage. It does allow very precise definition of types.ASN.1 has eight basic primitive types and five constructor types. The primitive typesare:• BOOLEAN• INTEGER• ENUMERATED• NULL• REAL• OBJECT IDENTIFIER• OCTET STRING• BIT STRINGThe constructor types are:Chapter 2. Data Definition Languages and Encoding Rules^ 15• SEQUENCE• SET• SEQUENCE OF• SET OF• CHOICEUnlike other languages, ASN.1 has more than one set of encoding rules defined forit. This allows implementors to choose encoding rules that support their needs withoutrewriting a protocol's ASN.1 definition.2.4.2 BER: Basic Encoding RulesBER produce regular tag-length-content encodings, where the content can be composedof more tag-length-content tuples or a primitive type's (e.g. INTEGER) value. Thecomponents of a BER encoding are octet (8 bit) aligned.The tag can provide information concerning the type of the content. BER produceself-defining or explicitly typed values. The fact that type information is present in BERencodings makes BER different from all of the other encoding rules we tested.It should be noted that if implicit tagging is used, the type information in a BERencoded value is not complete. For example, if UNIVERSAL tags are not used, a tagmay tell the decoder that the value is primitive (i.e. the content does not contain moretag-length-content tuples) but not whether it is an INTEGER, BOOLEAN, REAL orother primitive type.The regular nature of BER encodings allows the implementation of encoders anddecoders without knowledge of the abstract syntax. This feature is used by some imple-mentations to provide a common value form to pass to and receive from the presentationChapter 2. Data Definition Languages and Encoding Rules^ 16layer. Some consider type information in values an unnecessary expense in time and sizesince protocols typically know what type of data they will receive.The encoding techniques for the primitive values are very flexible. BER allows arbi-trarily large integer and string values. In practice these sizes are limited by the architec-ture of the encoding host. This flexibility may increase the useful lifetime of BER.There are two subsets of BER that provide canonical encodings. One is DistinguishedEncoding Rules (DER) and the other is Canonical Encoding Rules (CER).BER has a feature that makes it difficult to implement one-pass BER encoders. En-coding a definite length before a constructed value is difficult because the length itself isa variable in size but it is only known after the components of the constructed value havebeen encoded. Thus one needs a scheme to insert the length after the components havebeen encoded. Unfortunately this usually results in a two pass encoder. Fortunately,the indefinite length option does not have this problem. However, DER require definitelengths so other solutions such as backwards encoding need to be employed to avoidcostly two pass encoding.2.4.3 PER: Packed Encoding RulesIn this section most of the concepts of Packed Encoding Rules (PER) are described;for the complete definition see [PER92]. There are some problems with the currentCommittee Draft for PER that will be rectified before PER goes on to become a DraftInternational Standard.PER have evolved immensely since their initial draft [PER91]. Initially, PER werebasically an optimized BER that removed redundant tags and lengths as well as com-pressing integers and booleans under special circumstances. The current version of PERis described here.PER were designed to produce compact encodings. Compact encodings are usefulChapter 2. Data Definition Languages and Encoding Rules^ 17when storing large amounts of data on disk or transmitting PDUs over a network inwhich the cost per byte or packet is high. The amount of compression PER achieves overBER can be very dependent on the encoded values' ASN.1 type definition.Some aspects of ASN.1 type definitions that do not affect BER encodings will affectPER encodings. PER use subtyping value range and size restrictions to improve com-pression. Careful use of subtyping by ASN.1 writers can significantly reduce the size ofPER encodings.PER Differences From BERMany people are familiar with BER; here are the fundamental differences between PERand BER.In PER:• Tags are not encoded.• Subtyping information can affect the encoded value.• The value range of ENUMERATED types can affect the encoded value.• The values range of named bits in BIT STRINGs can affect the encoded value.• Lengths are only encoded before non-fixed-size primitive values.• The number of components in SET OF and SEQUENCE OF values is encodedbefore the content instead of the content's encoded length.• The components of SET and SET OF types are ordered.• Type extension must be explicitly allowed by using the "..." extensions marker inthe ASN.1 definitions of the extensible types (ASN.1 '92 feature)Chapter 2. Data Definition Languages and Encoding Rules^ 18PER uses a preamble-length-content format, each of which may be empty. The pream-ble is only present for SEQUENCEs, SETs and CHOICEs to indicate which componentsare present. Subtyping and other information that restricts the encoded length of a valuewill be used to compress or eliminate the length determinant. Subtyping and other infor-mation that restricts the value range of a type will be used to compress or eliminate theencoded values of that type. Thus, the PER preamble-length-content format is contextsensitive (to the ASN.1 definition), unlike the regular structure of the BER tag-length-content format. Hence generic (abstract syntax ignorant) decoders cannot be written forPER values.Extensions MarkerASN.1 '92 introduces the concept of the extension marker. It is briefly described herebecause it affects how values are encoded in PER.The extensions marker is expected to be used by ASN.1 designers in types that willlikely have components added or removed in future versions of their ASN.1 specification.The extensions marker can be used in the ASN.1 definition of SETs, SEQUENCEs,CHOICEs, BIT STRINGs with named bits and ENUMERATED types.BER supports type extension by the use of new tags on added SET, SEQUENCE orCHOICE components and the fact that named bits and ENUMERATED values do notaffect their encoding technique. This form of extension does not work with PER becausetags are not encoded and the named bit and ENUMERATED value information is usedto help compact the encoding (i.e. it affects the way values are encoded).Colourl ::= ENUMERATED { red(0), orange(1), yellow(2), green(3)}Colour2 ::= ENUMERATED { red(0), orange(1), yellow(2), green(3), ...IThe Colour2 type above is an extensible version of Colourl since it uses the "..."Chapter 2. Data Definition Languages and Encoding Rules^ 19extensions marker. A future version of Colour2 could be:Colour2 ::= ENUMERATED { red(0), orange(1), yellow(2), green(3), ..., blue(4)}PER decoders that were designed to handle the original version of Colour2 will beable to detect the presence of an extended Colour2 value and deal with it accordingly.This could include discarding the PDU or something else depending on the protocol.PER decoders for the above version of Colourl would not be able to decode values ofthe following extended version of Colourl because the extensions marker was not usedin the original and new definition.Colourl ::= ENUMERATED { red(0), orange(1), yellow(2), green(3), blue(4)}The addition of an extensions marker affects the way types are encoded (i.e. thebits on the line will be different); a decoder for Colour2 will not be able to handle anencoding of Colourl and vise-versa. This is why it is recommended that types that arelikely to be extended in future versions of the protocol be given an extensions marker.Flavors of PERThere are four different flavors of PER resulting from combinations of two features:BASIC or RELAY-SAFE-CANONICAL, and ALIGNED or UNALIGNED. Each flavorhas its own OBJECT IDENTIFIER for use when negotiating a presentation connectionand in other situations. The OBJECT IDENTIFIERs are:{ joint-iso-ccitt asnl(1) packed-encoding(3) basic(0) aligned(0) }{ joint-iso-ccitt asnl(1) packed-encoding(3) basic(0) unaligned(0) }{ joint-iso-ccitt asnl(1) packed-encoding(3) relay-safe-canonical(0)aligned(0) }{ joint-iso-ccitt asnl(1) packed-encoding(3) relay-safe-canonical(0)unaligned(0) }Chapter 2. Data Definition Languages and Encoding Rules^ 20BASIC PER is the most general form of PER. RELAY-SAFE-CANONICAL PER is arestriction of BASIC PER that makes an encoded value both relay safe and canonical.The UNALIGNED version of PER allows the components of the encoded value tobe written without octet alignment so that no bits are wasted between the components,yielding a very compact value.Each type is designated an "octet aligned bit field" or a "bit field". The only timealignment is performed is when appending a type that is an octet aligned bit field whileusing an ALIGNED flavor of PER. When alignment occurs, the existing encoding ispadded with zero bits until it is an integral number of octets in length, then the typethat required the alignment is appended.The concepts of constrained whole numbers, semi-constrained whole numbers andunconstrained whole numbers are used to describe encoded lengths, INTEGERs, ENU-MERATED values and other features of PER. For simplicity, they are defined here. Forpositive binary integers and two's complement binary integers the leading bit is the mostsignificant and the trailing bit is the least significant.A constrained whole number is a whole number that has both an upper and a lowerbound. The upper and lower bounds can be used to reduce the number of bits neededto represent the value.Given a constrained whole number, x, with an upper bound ub, and a lower boundlb such that lb < x < ub, its value range is ub — lb + 1. The value x will be encoded asa positive binary integer of value x — lb. The number of bits or octets that are used tohold x's encoded value are shown in Table 2.1.For example, a value of type INTEGER (4..7) needs only two bits to represent itsrange of values. From Table 2.1 we can see that this value would be encoded as a positivebinary integer in a bit field 2 bits long.Chapter 2. Data Definition Languages and Encoding Rules^ 21value range size1 0 bits2 to 255 bit field of the minimum number of bitslarge enough to hold the value range256 octet aligned bit field 1 octet long257 to 65,536 octet aligned bit field 2 octets longlarger than 65,536 octet aligned field the minimum numberof octets needed to hold the valueTable 2.1: PER field types and sizes for constrained whole numbersA semi-constrained whole number is a whole number that has a lower bound but noupper bound. A semi-constrained value, x, with a lower bound lb, is encoded as a positivebinary integer with value x — lb in an octet aligned bit field of the minimum number ofoctets needed for the value.An unconstrained whole number has no upper or lower bound. They are encoded astwo's complement binary integers in an octet aligned bit field of the minimum numberof octets in length for the value.TagsPER does not encode the tag information from ASN.1 definitions. Different mechanismsare used in the areas where BER needs tags to identify the presence of optional SET orSEQUENCE components or which CHOICE component is present. These mechanismsinvolve the preamble and will be discussed with their respective types.LengthsBER-like length determinants are only encoded before primitive values such as INTE-GERs and REALs that are not a fixed-size. If the size of the encoded value is constrainedChapter 2. Data Definition Languages and Encoding Rules^ 22by any subtyping or other information, this information will be used to shrink the length.PER lengths may be an octet count, bit count or component count depending on thetype they precede.Lengths are either constrained or semi-constrained whole numbers. They cannot beunconstrained because lengths are always positive.If a length is constrained and its upper bound is less then 65,536, it is encoded as aconstrained whole number. For example, the length of values of type OCTET STRING(SIZE (3..6)) have a lower bound of three and an upper bound of six, which means theirlength will be encoded in two bits, with '00' mapping to three and so on. For all otherlengths, the following rules apply. Note that the lower bound does not affect how thefollowing lengths are encoded.If length < 128, the length is encoded as the positive binary integer representinglength in a one octet long octet aligned bit field.Otherwise, if 128 < length < 16, 384, the length is encoded as the positive binaryinteger representing length in a two octet long octet aligned bit field and the mostsignificant bit is set to one.For lengths of 16,384 or larger, a flat fragmentation scheme is used such that themaximum length of any part of a primitive value is less than 65,536 octets.Open TypesOpen types are semantically similar to the ANY type in ASN.1 but are encoded a specialway. The type contained in the open type is encoded normally and preceded by its lengthin bits. This length allows decoders that do not know the type contained in the opentype to skip the open type's value and continue decoding the rest of the value.The length encoded before the contained type's encoding is encoded as a semi-constrained whole number with a lower bound of zero.Chapter 2. Data Definition Languages and Encoding Rules^ 23BOOLEANBOOLEAN values are encoded in one bit long bit fields. The bit is set to one to representTRUE and zero for FALSE. They are not preceded by a preamble or a length determinant.INTEGERINTEGERs are encoded as constrained, semi-constrained or unconstrained whole num-bers. They never have a preamble but require a length determinant in the semi-con-strained and unconstrained cases.INTEGERs with an upper and a lower bound such as INTEGER (10..20) are encodedas constrained whole numbers. The encoded integer is preceded by its length determi-nant only if its value range is 65,536 or greater. This is because the length of encodedconstrained whole numbers is variable when their value range is 65,536 and over.INTEGERs, such as INTEGER (0..MAX), with a lower bound but no upper boundare encoded as semi-constrained whole numbers and are preceded by their length deter-minant.INTEGERs with no constraints, such as INTEGER, are encoded as unconstrainedwhole numbers and preceded by their length determinant.ENUMERATEDENUMERATED values are typically encoded as constrained INTEGERs. To calcu-late the constraints, the defined ENUMERATED values are sorted in ascending orderand each is assigned an index starting with 0 for the first value, 1 for the second andso on. The index of the value is encoded as a constrained integer whose constraints areINTEGER(0..MAX-INDEX), where MAX-INDEX is the highest index in the ENUMER-ATED type.Chapter 2. Data Definition Languages and Encoding Rules^ 24Fool ::= ENUMERATED { spring(7), summer(12), fall(16), winter(19) }The value summer from Fool would be encoded like the value 1 of the type INTE-GER(0..3). The resulting encoding would be a bit field with the bits '01'. The bits arenot preceded by a length determinant because the values of Fool are always 2 bits long.Foo2 ::= ENUMERATED { spring(7), summer(12), fall(16), winter(19), ...IIf the extensions marker is present in an ENUMERATED type as in Foo2, the val-ues cannot be completely constrained due to the possibility of future additions to theENUMERATED values. In these cases, ENUMERATED values are encoded as semi-constrained INTEGERs with a lower bound of zero.REALREAL values are encoded the same way as BER REAL values into an octet aligned bitfield. They have no preamble and are preceded by a length determinant. When using aRELAY-SAFE-CANONICAL encoding flavor of PER, the CER[CDER92] REAL rulesare used.BIT STRINGBIT STRINGs are encoded with no preamble and in some cases will be preceded by alength determinant. The upper bound ub and lower bound lb on a BIT STRING's length,as determined from SIZE subtyping or named bits, affect the way they are encoded.BIT STRINGs with named bits are special because the named bits constrain theencoded size of the BIT STRING much like a SIZE constraint. Using n to represent thehighest named bit number, BIT STRINGs with named bits are constrained as thoughthey were a BIT STRING (SIZE(0..(n+1))). For the FooBits type, lb = 0 and ub = 20.Chapter 2. Data Definition Languages and Encoding Rules^ 25type lower bound upper boundBIT STRING 0 unsetBIT STRING (SIZE 6) 6 6BIT STRING (SIZE (3..20)) 3 20BIT STRING {night(0), day(1)} 0 2BIT STRING {night(0), day(1),...} 0 unsetTable 2.2: Examples of length upper and lower bounds for BIT STRING typesIf an extensions marker is present in the named bits, then the upper bound on size isundefined ("unser ) instead of (n + 1). Values of BIT STRING types with named bitshave their trailing zero bits removed.FooBits ::= BIT STRING {spring(7), summer(12), fall(16), winter(19)}The following rules are used to encode BIT STRING values. If ub equals zero, theencoding is empty, with no length determinant.If lb equals ub and lb is less than or equal to 16 bits, the bits are encoded in a bitfield of length lb bits without a length determinant.If lb equals ub and lb is greater than 16 bits, the bits are encoded in an octet alignedbit field of length lb bits without a length determinant.Otherwise, the bits are encoded in an octet aligned bit field preceded by the lengthdeterminant in bits as constrained by lb and ub. There is no unused bits octet as in BER.OCTET STRINGOCTET STRINGs are encoded in a way similar to BIT STRINGs. They are encodedwith no preamble and in some cases will be preceded by a length determinant. As withBIT STRINGS, the OCTET STRING encoding depends on the upper bound ub, andlower bound lb of its size.Chapter 2. Data Definition Languages and Encoding Rules^ 26type lower bound upper boundOCTET STRING 0 unsetOCTET STRING (SIZE 6) 6 6OCTET STRING (SIZE (0..20)) 0 20Table 2.3: Examples of upper and lower bounds for OCTET STRING typesIf ub equals zero, the encoding is empty, with no length determinant.If lb equals ub and lb is less than or equal to two octets, the octets are encoded in abit field of length lb octets and are not preceded by a length determinant.If lb equals ub and lb is greater than two octets, the octets are encoded in an octetaligned bit field of length lb octets and are preceded by length a determinant.Otherwise, the octets are encoding an octet aligned bit field preceded by the lengthdeterminant as constrained by lb and ub.OBJECT IDENTIFIERPER OBJECT IDENTIFIERs are encoded into an octet aligned bit field in the sameway as BER OBJECT IDENTIFIERs. They have no preamble and are always precededby their length determinant.NULLNothing is encoded for a NULL value (no preamble, length or content).SEQUENCESEQUENCE values usually have a preamble, never have a length determinant and theircontent is their encoded components in the order of their declaration.Chapter 2. Data Definition Languages and Encoding Rules^ 27The SEQUENCE preamble contains information about extensions to the SEQUENCEtype definition and the presence of OPTIONAL and DEFAULT components.If a SEQUENCE's ASN.1 definition has an extensions marker ("..."), the first bitof the preable indicates whether components that were not in the original SEQUENCEdeclaration are present in the encoding. If extension components are present in theencoding, this bit is one otherwise it is zero.The following bits in the preamble are for the optional or default elements of theSEQUENCE, if any. There is one bit for each optional/default element and they are inthe order of their declaration. A value of 1 indicates that the element is present and a0 means that the element is absent. Optional and default elements that are after theextensions marker (if any) do not have bits in the preamble. If there are more than65,536 optional or default elements, fragmentation is used for the preamble.The preamble is written as a bit field and followed by the encodings of each of theSEQUENCE's components in the order they were declared in.In the RELAY-SAFE-CANONICAL case, default values will always be included inthe encoding with their bit in the preamble set to one.There is a special procedure for encoding the components declared after the extensionsmarker. There is a "presence" bit string that has a bit for each extension component; itis encoded as if it were a BIT STRING (SIZE (1..MAX)). The extension components areencoded as open types. As before, default values will always be included in the encodingwith their bit in the preamble set to one for the RELAY-SAFE-CANONICAL cases.SETSETs are encoded the same way as SEQUENCEs after ordering the SET's componentsaccording to their tag values. This is different from BER, where SET components canbe encoded in any order. The ordering in PER removes the need for tags.Chapter 2. Data Definition Languages and Encoding Rules^ 28type lower bound upper boundSEQUENCE OF Foo 0 unsetSEQUENCE (SIZE 10) OF Foo 10 10SEQUENCE (SIZE (1..10)) OF Foo 1 10Table 2.4: Examples of upper and lower bounds for SEQUENCE OF typesFirst, a SET's component's tags are sorted by class with UNIVERSAL first, followedby APPLICATION, CONTEXT and PRIVATE. Within each of the class groupings, thetags are sorted in ascending order of tag code. This order defines the order of a SET'scomponents such that the SET can be treated as a SEQUENCE.For example, the SET Bari would be encoded in the same was as the SEQUENCEBar2.Barl ::= SET{a [1] INTEGER,b INTEGER,c [0] INTEGER}Bar2 ::= SEQUENCE{b INTEGER,c [0] INTEGER,a [1] INTEGER}SEQUENCE OFThe SEQUENCE OF type's encoding consists of the number of components followed bythe ordered encoding of each component. Upper and lower bounds on the number ofcomponents can affect how the number of components is encoded.Chapter 2. Data Definition Languages and Encoding Rules^ 29If the number of components in the SEQUENCE OF type is constant (upper boundequals the lower bound), the number of components is not encoded. Otherwise, thenumber of components is encoded as a length determinant. If the number of componentsexceeds 65,536, the SEQUENCE OF encoding will be fragmented.SET OFThe SET OF type is treated as if it were a SEQUENCE OF type. This means that theordering of SET OF types is significant, unlike BER.CHOICEIn BER, tags are used to indicate which CHOICE component is present. In PER, theindex of the component is used instead. First, the CHOICE components are sorted bytheir tags in the same manner as SET components. The first component is given theindex zero, the second component's index is one and so on. CHOICEs are encoded asthe index of the present CHOICE component followed by the encoded component.If there is no extensions marker in the CHOICE's definition, the index is encoded asa constrained whole number with a lower bound of zero and upper bound equal to theindex of the last component. The component is encoded as PER defines for its type andappended to the encoded index.If the CHOICE's definition contains an extensions marker, the index is encoded asa semi-constrained whole number with a lower bound of zero. If the component fromthe extensions root (i.e. it is declared before the "..." symbol in the CHOICE), thenit is encoded normally and appended to the encoded index. If the component is in theextension additions (i.e. declared after the "..."), it is encoded as an open type.Chapter 2. Data Definition Languages and Encoding Rules^ 30Implementation CommentsExamination of PER shows that one pass, forward encoding and decoding can be sup-ported. There appear to be no problems, such as BER's definite lengths for constructedvalues, that require more than one pass. It is possible that the fragmentation requiredfor PER open types whose contained encoding is longer than 65,536 bits may requiremore than one pass.In most cases, the tag sorting operations for SETs and CHOICEs can be done at thetime the ASN.1 is compiled. No overhead needs to be incurred during the encoding anddecoding processes. Types whose first tag depends on their value (untagged CHOICEand untagged ANY types) are the exceptions that may require some runtime sorting.The potentially unaligned nature of PER encodings requires more powerful buffermanagement routines to handle arbitrary bit alignment.The lack of tags in PER simplifies code design. For BER implementations, tags aredifficult to deal with since a class and code of a type's tag is set by its enclosing type(sometimes) but the tag's form is handled by the type itself (see Section 4.3). This canlead to clumsy implementations.ASN.1 compilers will need to do more work to generate PER encoders and decoders,since more aspects of ASN.1, such as subtyping, affect PER. BER encoders and decoderscan be generated without using the subtyping information.PER SummaryPER are an alternative to BER when more compact encodings are desired, however theyare less flexible. PER encodings cannot be decoded without knowing the original abstractsyntax. That is, PER encodings are not self-defining. There are four types of PER, basedon two factors: BASIC-PER versus RELAY-SAFE-CANONICAL PER, and ALIGNEDChapter 2. Data Definition Languages and Encoding Rules^ 31versus UNALIGNED. The RELAY-SAFE-CANONICAL PER is a restriction on someoptions in BASIC PER such that a given value has exactly one encoding. This is a usefulfeature for generating digital signatures. The UNALIGNED version of PER allows thecomponents of the encoded value to be written without octet alignment so that no bitsare wasted between the components, yielding a very compact transfer sytnax.SETs are encoded the same way as SEQUENCEs after their elements have been sortedaccording to their tag's class and code; note that this is a compile time operation (inmost cases) and therefore does not decrease performance. SET OF values are encodedas if they were SEQUENCE OF values.Tags are not encoded at all. Bitmaps before SEQUENCEs and SETs indicate thepresence of OPTIONAL and DEFAULT elements. For CHOICEs, the elements are sortedby tags like SETs and each element is then assigned an index starting from zero. Thisindex is encoded before the CHOICE to indicate which element is present.Only some primitive values will have their length encoded. Constructed values donot have their length encoded; instead they rely on their components to define theirlength. SET OF and SEQUENCE OF values have the number of components theycontain encoded before the components. For large OCTET STRING and BIT STRINGvalues, a general purpose, flat fragmentation scheme is used that allows the fragments tobe a maximum of 64K bytes long.Subtyping information is used extensively by PER to reduce the size of the encodedvalue. Specifically, value range information on INTEGERs and ENUMERATED types,and size information on other types is used. For example, if an OCTET STRING is afixed-size, its length is not encoded. For ENUMERATED types and INTEGERS withvalue ranges, the minimum number of bits that can represent the required range of valuesis usually used.Chapter 2. Data Definition Languages and Encoding Rules^ 322.5 XDR: External Data Representation2.5.1 The XDR languageXDR [Sun87] was developed around 1984 to help implement Sun's Network File System(NFS).Rpcgen is Sun Microsystems' RPC (Remote Procedure Call) stub generator. It parsesremote procedure declarations and C-like data structures written in the XDR languageand produces the C data structures, RPC stubs and the XDR encoder and decoder sourcecode for the given data structures.The rpcgen or XDR language is similar to C data structure definitions. This simplifiesimplementing a protocol in C.2.5.2 XDR Encoding RulesXDR provides a set of encoding rules that operate optimally if the encoding and de-coding hosts have 4 byte words, big endian integers and use the IEEE floating pointrepresentation.The eleven XDR primitive types are:• int - 4 byte long integer, big endian 2's complement• unsigned int - 4 byte long integer, big endian, positive binary number• hyper - 8 byte long integer, big endian, 2's complement• unsigned hyper - 8 byte long integer, big endian, positive binary number• enum - encoded as an int• bool - encoded as an int, 0 for false, 1 for trueChapter 2. Data Definition Languages and Encoding Rules^ 33• float - 4 bytes, IEEE float• double - 8 bytes, IEEE double• opaque - fixed or variable length uninterpreted data• string - fixed or variable length ASCII data• void - not encodedThe three XDR constructor types are:• array - fixed or variable length array of variable or fixed-size elements• struct• discriminated unionXDR uses a "Basic Block Size". This means each component of an XDR encodingis aligned to a 4 byte boundary to simplify decoding on machines with this architecture.The alignment requirement may introduce padding bytes. Any padding bytes that arenecessary to maintain the basic block size are set to zeros. This and the careful designof other parts of XDR, such as the bool boolean type, make XDR encodings canonical.The typing information in XDR is implicit. If a protocol needs explicit type informa-tion, one can easily modify an XDR specification to contain it.2.6 NIDL/NDR2.6.1 NIDL: Network Interface Definition LanguageApollo Computer's NIDL compiler for C is similar to rpcgen except that NDR encodersare generated. There is also a different NIDL language and compiler to support Pascal.Chapter 2. Data Definition Languages and Encoding Rules^ 34NIDL has stronger remote procedure call semantics than XDR. For example, anRPC may be defined as idempotent. NIDL and NDR are part of HP/Apollo's NetworkComputing Architecture [Kong90].NIDL/NDR have been adopted by the OSF/DCE [OSF/RPC90]. This may not be awise decision as NDR have difficulty in handling the aggregation of variable sized types.For example, a structure can only contain one array with a variable number of elements;all components of a structure except the last one must be of fixed size. Pointers cannotbe used to get around this limitation as NDR do not allow pointers. Because of the twobyte length fields for strings and arrays, NDR limits the number of characters in a stringand the number of array elements to less than 65,536. These limitations may lead tooverly restrictive data structures. Fortunately, the OSF/DCE RPC mechanism allowsnegotiation of the encoding rules that are used for a connection.2.6.2 NDR: Network Data RepresentationThe NDR [Zahn90] encoding rules are unique in that parts of the encoding rules aredefined by the host that does the encoding. For example, if running on a Sun, integers,character strings and real numbers will be encoded in Sun's standard representation,namely big endian integers, ASCII strings and IEEE real numbers. The encoded valueincludes a format label that defines which type representations were used. The receiv-ing host is responsible for converting these values to its internal representation when itdecodes the value.This technique optimizes NDR for communication between hosts with the same archi-tecture. Thus, hosts only need one encoding routine for each primitive type but they musthave different decoding routines for each type to support all of the other representations.NIDL has twenty-five abstract types that map into nineteen NDR transfer types. Inaddition to these types, there is a 4 byte long format label type to define how the integers,Chapter 2. Data Definition Languages and Encoding Rules^ 35reals and strings were encoded.The primitive NIDL types are:• small - 8 bit long, 2's complement integer• short - 16 bit long, 2's complement integer• int - 32 bit long, 2's complement integer• long - 32 bit long, 2's complement integer• hyper - 64 bit long, 2's complement integer• unsigned small - 8 bit long binary integer• unsigned short - 16 bit long binary integer• unsigned int - 32 bit long binary integer• unsigned long - 32 bit long binary integer• unsigned hyper - 64 bit long binary integer• short enum - 16 bit long 2's complement integer• enum - 32 bit long 2's complement integer• byte - 8 bits long uninterpreted data• float - 32 bits• double - 64 bits• char - always unsigned, ASCII or EBCDIC• boolean - 1 byte, 0 for false, non-zero for trueChapter 2. Data Definition Languages and Encoding Rules^ 36• bitset enum 32 bits• short bitset enum 16 bits• string() - null terminated string, ASCII or EBCDIC• void - not encodedThe constructor NIDL types are:• struct• union• arrayNDR aligns values to 2, 4 or 8 byte boundaries depending on their type. This align-ment technique can yield smaller encodings (fewer padding bytes) than by using XDR's4 byte alignment.All of the components of a struct, except the last one must be a fixed size. Thisrestriction alone makes it difficult to specify some complex data structures in NIDL.There is a "transmit-as" mechanism to translate complex data structures into simplerones that can be encoded in NDR, but it does not solve the problem very well and anotherlayer is added to encoding and decoding.2.7 C Based Encoding RulesFor comparison purposes, we defined C Based Encoding Rules. They show what per-formance can be achieved by assuming that the communicating hosts share the samearchitecture and that their protocol implementations use the same language and possiblycompiler. These encoding rules would only be viable under these restricted conditions.Chapter 2. Data Definition Languages and Encoding Rules^ 37When encoding with these encoding rules, we assume that the C data structure'scomponents have been carefully allocated contiguously from a single block of memoryand that the base address of this block and its size are known. The encoding processsimply traverses the C data structure in a depth first fashion and converts any non-nullpointers into an offset from the start of the block. Null (zero) pointers are left as is.Since a zero offset could be a valid "address" (i.e. reference to the first component of theencoding), pointer references cannot be made to the first component in the block.The encoding process could also be done by sending the base address of the blockwith the block instead of translating the pointers. The decoder would then subtract theoriginal base address from the pointers before adding the current base address. Thiswould eliminate the zero offset/null pointer ambiguity. We did not use this improvementin our tests.For decoding, we assume that the encoded value is in a contiguous representationand that the base address of the encoded value's memory block is known. The decodingprocess simply adds the current base address to the offsets while traversing the datastructure in a top down manner.The C based encoding rules do not allow for cycles in the data structure or componentsto be referenced more than once by pointer as this would complicate the algorithm andprovide a feature not found in the other encoding rules. This is not to say these featurescould be not implemented.Chapter 3Related Work3.1 Performance Issues and IdeasThere is a general notion that BER encoders and decoder are slow and produce large en-codings. This may be due to the richness of ASN.1 and BER or existing widely-availableimplementations such as ISODE. On this assumption people have devised optimizationsto BER: new "light-weight" encoding rules and compaction-oriented encoding rules.BER encodings contain explicit type information that is often unnecessary for manyprotocols since the receivers usually know the data types of the PDUs they receive. Newencoding rules such as PER have been devised to produce very compact encodings thatcontain no type information.To improve throughput, attempts have been made to minimize the cost of translationbetween the local representation and the transfer representation. These "light weight"encoding rules often resort to using fixed-size types that use the same representation ascommonly used CPUs.Huitema, Chave and Doghri [Huitema89] defined "Light Weight" Encoding Rules(LWER) as a faster replacement for BER. These rules used fixed-size integers and useoffsets for "pointers" .Their later research [Huitema92] showed that their improved BER implementationactually had throughput similar to LWER. LWER encoded values are also considerably38Chapter 3. Related Work^ 39larger than equivalent BER values due to the use of fixed size types. Their other bench-marks showed that BER can perform as well or better than XDR in some situations.These tests show how important implementation can be.In optimizing their BER implementation, they found the CPU intensive areas to bememory management for decoding (35-50%) and procedure call overhead.Fieldbus networks are designed to connect sensors, controllers and other related de-vices for process and industrial control applications [Thomesse87]. Fieldbus applications,due to real time constraints (bounded response times), need fast encoding rules. Com-pact encodings are also desirable due to the limited bandwidth in Fieldbus networks.The size of the implementation is also considered important for helping support low-costhardware.Fieldbus PDUs are expressed in ASN.1 to help compatibility with MMS [MMS87]but BER are deemed to be too slow. Several researchers have designed fast, Fieldbusoriented replacements for BER.Pimentel [Pimente188] defined a subset of BER for Fieldbus applications. Tags andlengths are often combined into a single octet and no indefinite length encodings are per-mitted. On average, the special encodings were 61% of the size of their BER equivalent.Although no implementation results were presented, the overall throughput is assumed toimprove since smaller values can be sent faster and the assumption that smaller encodingsreduce the complexity of the encoding and decoding implementations.Cardoso and Tovar [Cardoso92] also present a set of encoding rules optimized forFieldbus applications. These encoding rules are somewhat specialized in that they includeprotocol information such as PDU type (request, response, error). They support explicitand implicit type information. The authors note that handling OPTIONAL componentsis expensive in BER and provide a simpler but limited mechanism for handling them.No implementation benchmarks were presented.Chapter 3. Related Work^ 40Prasad and Gonzalo [Prasad93] found that Pimentel's encoding rules did not improvethroughput significantly. They defined another set of Fieldbus oriented encoding rulessimilar to XDR to improve throughput while maintaining small encoded values.In their rules, the only constructor types supported are SEQUENCE and CHOICE.OPTIONAL SEQUENCE elements are not permitted. Only UNIVERSAL tags are usedand then only to determine the content of a CHOICE. All other types except stringswere fixed in size.The performance of their encoding rules and implementation were measured andcompared to an ISODE based version. For larger PDUs, their values were 77% of the sizeof the BER equivalent and the encoders and decoders took 29% and 72%, respectively, ofthe time ISODE implementations used. For smaller PDUs, their encoding rules performedbetter.These papers indicate that simplifying encoding and decoding of primitive types andtheir structuring can improve performance, but also that other implementation factorsare very important. Our goal was to find out what these factors are and how to simplifytheir implementation. We also address how encoding rules can be designed to reduce theimpact of these factors on the cost of encoding and decoding.Chapter 4Performance Considerations for the Snacc ASN.1 Compiler4.1 Snacc Design Process and GoalsIn this section we present the techniques the snacc generated encoders and decoders useto improve performance. A more in-depth presentation of using the compiler and thegenerated code can be found in [Sample93-1].Snacc was designed primarily to provide high-performance encoders and decoders. Weexamined other ASN.1 compiler output and models to find problem areas. From theseobservations we designed a model for our ASN.1 compiler to use. This model was testedby implementing several encoders and decoders by hand before the compiler was written.Finally, snacc was written to produce encoders and decoders that used our design model.The following general considerations guided the design of the encoder and decodercode generated by snacc:• Do not make decisions at runtime that can be made at the time the ASN.1 iscompiled.• Avoid decoding tags more than once.• Minimize memory allocations and copying.• Streamline everything.41ASN.1DataStructureDefinition/TypeTableASN.1UsefulTypesorChapter 4. Performance Considerations for the Snacc ASN.1 Compiler^42Figure 4.4: The snacc compiler produces C or C++ BER encode, BER decode, printand free routines or a type table.Key areas to optimize are buffer and memory management. Buffers are used tohold encoded values and the memory management is used when building the internalrepresentation of values when decoding. These services are provided in the library thatsupports the code snacc generates. Their interfaces were abstracted such that differentimplementations of the buffer and memory managers could be used without modifyingthe generated code. This simplifies the testing and optimizing of buffer and memorymanagement.Another area that caused performance problems is the handling of BER definitelengths on constructed values. The typical solution involves using an intermediate datastructure between the local and transfer representations. To avoid the memory allocationand copying required by this technique, snacc implements backwards BER encoders.C macros are used where possible to eliminate function call overhead for small, com-monly used routines. Using macros with constant expressions as parameters allowsChapter 4. Performance Considerations for the Snacc ASN.1 Compiler^43smarter C compilers to do some of the calculations at compile time. In general, anyshort-cuts that could be taken without sacrificing the robustness of code or bloating thecode size too much were used. Even so, the generated code can be quite large; largereductions in the size of the binaries can be achieved by using optimizing C compilers.Snacc behaves as follows. For each ASN.1 type an equivalent C data type, a BERencoding routine, a BER decoding routine, a printing routine and a freeing routine aregenerated. C values will also be generated from simple ASN.1 values. Each aspect of theC code generation will be discussed in the next sections.Snacc can also produce type tables that allow interpreted or table based encoding anddecoding. This is different from the compiled technique in that no code is generated forthe ASN.1 data structures. Instead, a machine readable description of the ASN.1 datastructure (defined in ASN.1 and stored in BER) is used to drive a generic encoding anddecoding engine. This technique has potential code size benefits but is not designed forspeed.4.2 ASN.1 to C Data Structure TranslationEvery ASN.1 type definition maps into a C typedef. SETs and SEQUENCEs map intoC structures and other simple types map into their obvious C counterpart.Memory allocations can be expensive so snacc makes efforts to consolidate the datastructures. Small, simple types such as INTEGERs, BOOLEANs and REALs are directlyincluded in the structs of their enclosing SEQUENCE, SET or CHOICE unless they areOPTIONAL. Snacc handles OPTIONAL OCTET STRING, BIT STRING and OBJECTIDENTIFIER types in a special way to reduce memory allocations and frees.The standard technique for handling OPTIONAL SET or SEQUENCE elements isto reference the element type by pointer from the SET or SEQUENCE's C struct. If theChapter 4. Performance Considerations for the Snacc ASN.1 Compiler^44pointer is NULL, then the component is not present. OCTET STRINGs, BIT STRINGsand OBJECT IDENTIFIERs are included by value even when they are OPTIONALbecause they are small and contain an internal pointer that can be used to determinetheir presence.The SET OF and SEQUENCE OF types map into a generic list type which is doublylinked and NULL terminated. The reverse link on the lists allows for simpler backwardsencoding.4.3 Generated C Encoder DesignSnacc can generate two kinds of encoding routines for each ASN.1 type definition. One isPDU oriented and encodes the type's tag, length and content and the other only encodesthe type's content. The generated encoders only call the content encoders, except in thecase of ANY and ANY DEFINED BY types where tagging information is not known inthe calling routine.The most interesting thing about snacc generated encoders is the fact that theyencode backwards [Steedman90]. Instead of writing the first component of an encodingand appending the rest in order, snacc encoders encode the last component and prependthe others in order.This "backwards" encoding technique simplifies the use of definite lengths on con-structed values. Other encoders that encode forwards, such as those of CASN1 [Yang88][Neufeld90], use an intermediate buffer format so that a buffer containing the encodedlength of a constructed value can be inserted before its encoded content, after the con-tent has been encoded. Use of intermediate representations can hurt performance. Othercompilers' approaches have been to only encode the indefinite length alternative for con-structed values, however, this will not support some encoding rules such DistinguishedChapter 4. Performance Considerations for the Snacc ASN.1 Compiler^45Encoding Rules (DER) [CDER92] that require definite lengths.The drawback of encoding backwards is that BER values cannot be written to streamoriented connections as they are encoded. This removes the possibility of pipelining theencode and transmission tasks.Both definite and indefinite length encodings for constructed values' lengths are sup-ported. The choice is made when compiling the generated code.Handling tags for BER encoders and decoders is bothersome. The shared nature oftag information between the enclosing type and the type itself is the root of the problem'.Encoding tags is a common operation for BER encoders so it must be optimized.For example, a SET may override the UNIVERSAL tag on an OCTET STRINGcomponent by using IMPLICIT tagging. The SET controls the class and code of the tagbut the OCTET STRING itself handles the form of the tag. A typical implementationwould have the SET pass the tag's class and code as parameters to the OCTET STRINGsencoding routine.For all types except OCTET STRINGs, BIT STRINGs and those derived from them,their tag form is known when the ASN.1 is compiled. OCTET STRING and BITSTRING types are primitive types that can have "constructed" encodings so their tagform can be either primitive or constructed. BER allows encoder implementations tochoose between the constructed and primitive forms. To avoid an encode time deci-sion to determine the form, snacc supports only the non-constructed encoding of thesetypes. Snacc decoders will decode the constructed string types so BER conformance isnot sacrificed.With the above restrictions, snacc can calculate the exact encoding of every tag atASN.1 compile time. To "encode" a tag, snacc generated encoders simply copy octet(s)'The tag class and code can be defined by the enclosing type (via implicit tagging) while the typeitself defines the tag's form bit.Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^46to the buffer; the tag octet(s) are constants and require no encode time calculations.4.4 Generated C Decoder DesignSnacc uses special techniques for representing and handling tags and provides a light-weight memory manager to optimize the decoding process. As with encoding routines,snacc can generate two kinds of decoding routines for each ASN.1 type definition. Oneis PDU oriented and the other only decodes the type's content.Tag representation is very important for decoding. Tag comparison is a commondecoding operation; it is used for determining which type is next or to verify that aparticular type is present. To simplify tag comparison and passing tags as parameters,snacc uses long ints to hold tag values.To streamline the decoding of tags, the encoded tag is copied directly into a longint. The first octet of the tag is placed in the high byte of the long int with the restfollowing. If a tag is only one octet long, the remaining bytes of the long int are zeroed.This technique imposes a restriction on the maximum tag code that can be handled. Fora system with four byte long ints, the maximum tag code that can be represented is221 ; this is far higher than can realistically be expected.The shared nature of tag information can lead to tags being decoded more than oncein some implementations. For example, due to the unordered nature of SETs, SETdecoders need to decode the next tag to determine which component is to be decoded.The CASN1 decoders decode the tag once in the SET decoder routine and again in thecomponent's decoding routine. This technique hurts performances and requires that thevalue being decoded be held in a buffer that allows "backing up" so the tag can bedecoded again.Snacc avoids decoding tags twice in these situations by passing the decoded tag inChapter 4. Performance Considerations for the Snacc ASN.1 Compiler^47its long int form into every content decoding routine. All types have the tag andlength pairs on the content decoded by their enclosing type (e.g. SET), and the lastpair is passed to the content decoding routine. This allows the enclosing type and thecomponent type to use the tag information without decoding it twice 2 .To support this technique, CHOICE types are a special case. If a type such as aSET encloses an untagged CHOICE type it must decode the first tag in the CHOICE'scontent. To handle this uniformly for tagged and untagged CHOICEs, the enclosingtype always decodes all of the tag and length pairs until the first tag and length of theCHOICE content is decoded. Thus, the CHOICE decoding routine expects to be passedthe tag that determines which element is present in its value.During the decoding process, memory is allocated to hold the local representation ofthe value. Complex data structures can require many allocations and after the value hasbeen processed it is usually freed. Snacc generated decoders call the memory manager insuch a way that different memory management can easily be used. Section 4.8 describesthis in further detail.Some decoder implementations use a special stack to hold tag and length informationwhile decoding. This stack must be large enough or be able to dynamically grow tohandle some large complex values. To eliminate the need for this stack and perhapsimprove memory locality, snacc uses local variables in each generated decode routine forthe tags and lengths. This technique may also make the code easier to understand forusers.Snacc decoders ignore redundant length information. Explicit tagging in ASN.1 def-initions yields encodings that have extra tag and length pairs before a value. Snaccdecoders only verify that the innermost length is correct (definite length cases only).'Passing tag values on the stack is less costly than the CASN1 technique of decoding twice which callsan extra routine. Only OCTET STRING, BIT STRING and CHOICE decoding routines will actuallyuse the tag parameter. Optimizing compilers can eliminate it for the routines that do not use it.Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^48To save memory, decoders generated by some other tools build values that referencethe data in the encoded PDU for types like OCTET STRING. Snacc decoded values donot reference the BER data in any way for several reasons. One, the encoded value may beheld in some bizarre buffer making access to the value difficult. Two, with more encodingrules being formalized, this technique may not always work since the encoded format maybe different from the desired internal format. Three, snacc decoders concatenate anyconstructed BIT and OCTET STRINGs values when decoding, to simplify processing inthe application. The penalty for this is an extra copy for the string type components.Some protocol implementations may benefit from directly referencing data in thePDU buffer from the local representation. For example, the performance of an X.400 3email implementation that receives PDUs from the transport layer in a single memoryblock could save a copy by referencing the data directly. However, if UNALIGNED PERwere used to encode the X.400 PDU, the referenced string may not be octet aligned,which limits the benefit of this technique.4.5 Error ManagementError management is important but it must be implemented without incurring too muchcost for the common case where there are no errors. One method of streamlining errormanagement is to eliminate it by assuming that the decoded values are always correct.This is not acceptable for a reliable implementation.Snacc decoders can detect a variety of errors. All tagging errors are reported. SETsmust contain all non-OPTIONAL components and SEQUENCEs must be in order andcontain all non-OPTIONAL components. Extra components in SETs and SEQUENCEsare considered an error. Errors will also be reported if you attempt to decode values that3 X.400 PDUs are dominated by a large string body part.Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^49exceed the limitations of the internal representation (e.g. an integer that is larger thana long int allows).Snacc encoders only do minimal error checking; they assume that the value to beencoded is well formed. The buffer writing routines called by the encoders will set a flagif the buffer overflows or no memory is available to extend the buffer. After the bufferwrite error flag is set, future buffer writes are treated as no-ops. When the encodingroutine returns, the user can check the status of this flag to ensure that the value wasencoded properly.The decoding process is much more prone to errors. The value being decoded mayhave errors from network transmission or a faulty encoder. Local resource errors, suchas insufficient memory, can also cause decoding errors.To implement a complete yet light-weight error management scheme for the decoders,we used the setjmp and longjmp functions [Kernighan88]. Previously, the availabilityof these functions was very system dependent, however, they are now part of the ANSIStandard C Library.Before decoding begins, setjmp is called to record the current environment (processorregisters etc.). The environment value set by setjmp is then passed into the decodingroutine. Every decoding routine takes this parameter.When the decoding routines encounter a serious error such as running out of memoryfor the decoded value, they call longjmp with the environment value they were given asa parameter, along with a unique error code. This "returns" execution directly to wheresetjmp was called along with the error code.The setjmp and longjmp based error management is simple and does not impact theperformance of decoding correctly encoded values (other than an extra parameter toeach decoding routine). Other error management techniques such as passing back errorcodes that the calling functions must check will affect the decoding performance even forChapter 4. Performance Considerations for the Snacc ASN.1 Compiler^50jmp_buf env;if ((val = setjmp(env)) == 0)BDecPersonnelRecord( &buf, &pr, &decodedLen, env);else{decodeErr = TRUE;fprintf(stderr,"ERROR - Decode routines returned 74\n",val);}Figure 4.5: The set jmp function is called before decodingif (mandatoryElmtCount1 != 2){Asn1Error("BDecChildInformationContent: ERROR - non-optional elmt\missing from SET.\n");longjmp(env, -108);)-Figure 4.6: The longjmp function is called to signal an errorcorrectly encoded values.Figures 4.5 and 4.6 show code fragments that illustrate how snacc decoders use set jmpand longjmp for error handling.4.6 Compiler DirectivesSnacc attempts to produce a C data structure definition that is compact while not toorestrictive. However, users can often make optimizations that snacc cannot. To allow thisform of optimization, snacc provides compiler directives that allow users to influence thegenerated C data structure and the encoding and decoding routines. These can be usedto consolidate the data structure (by removing pointer references thus saving memoryallocations) or to replace the encode and decode routines with more efficient ones thatChapter 4. Performance Considerations for the Snacc ASN.1 Compiler^51are tailored to the target environment.The compiler directives have the form:--snacc <attribute>:"<value>" <attribute>:"<value>" .The attribute is the name of one of the snacc defined attributes and the valueis what the attribute's new value will be. The attribute value pairs can be listed ina single --snacc comment or spread out is a list of consecutive comments. Since thesedirectives are in ASN.1 comments, they do not make the ASN.1 unusable by other ASN.1tools.Compiler directives are only accepted in certain places in the ASN.1 code. Dependingon their location, the compiler directives affect type definitions or type references. Thedirectives for type definitions and references are different.The following example illustrates their use. Assume a data structure always dealswith PrintableStrings that are null terminated. The default snacc string type is astructure that includes a length and a pointer to the string's octets. To change thedefault type to a simple pointer (char*) the best way would be define a new string type,MyString as follows:Foo ::= SET{si [0] MyString OPTIONAL,s2 [1] MyString,i1 [2] INTEGER}Bar ::= CHOICE{s1 MyString,i1 INTEGER}Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^52Bell ::= MyStringMyString ::= --snacc isPtrForTypeDef:"FALSE"--snacc isPtrForTypeRef:"FALSE"--snacc isPtrInChoice:"FALSE"--snacc isPtrForOpt:"FALSE"--snacc optTestRoutineName:"MYSTRING_NON_NULL"--snacc genPrintRoutine:"FALSE"--snacc genEncodeRoutine:"FALSE"--snacc genDecodeRoutine:"FALSE"--snacc genFreeRoutine:"FALSE"--snacc printRoutineName:"printMyString"--snacc encodeRoutineName:"EncMyString"--snacc decodeRoutineName:"DecMyString"--snacc freeRoutineName:"FreeMyString"PrintableString --snacc cTypeName:"char*"All but the last --snacc comment bind with the MyString type definition. The lastdirective comment binds with the PrintableString type. The C data structure resultingfrom the above ASN. 1 and snacc compiler directives is the following:typedef char* MyString; /* PrintableString */typedef struct Foo /* SET */{MyString s1; /* [0] MyString OPTIONAL */MyString s2; /* [1] MyString */Asnlnt il; /* [2] INTEGER */} Foo;typedef struct Bar /* CHOICE */{enum BarChoiceld{BAR_Sl,BAR_I1choiceld;union BarChoiceUnion{MyString sl; /* MyString */Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^53Asnlnt ii; /* INTEGER */} a;} Bar;typedef MyString Bell; /* MyString */The compiler directives used on the MyString type have some interesting effects. No-tice that MyString is not referenced by pointer in the CHOICE, SET, or type definition,Bell. The snacc compiler directives are described fully in [Sample93-1].4.7 Buffer ManagementEncoding and decoding performance is greatly affected by the cost of writing to andreading from buffers. Thus, efficient buffer management is necessary. Flexibility is alsoimportant to allow integration of the generated encoders and decoders into existing envi-ronments. To provide both of these features, the calls to the buffer routines are actuallymacros that can be configured as desired. They must be configured prior to compilingthe encode/decode library and the generated code. Since virtually all buffer calls aremade from the encode/decode library routines, buffer routine macros should not bloatcode size significantly.If a single, simple buffer type can be used in the target environment, the buffer routinemacros can be defined to call the macros for the simple buffer type. This results in thebuffer type being bound at the time the generated code is compiled, with no function calloverhead from the encode or decode routines. However, this also means that the encodeand decode library will only work with that buffer type.If multiple buffer formats must be supported at runtime, the buffer macros can bedefined like the ISODE buffer calls, where a buffer type contains pointers to the bufferroutines and data of user defined buffer type. This approach will hurt performance sinceeach buffer operation will be an indirect function call.Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^54The backwards encoding technique used by snacc requires special buffer primitivesthat write from the end of the buffer towards the front. The decoder routines requireforward buffer reading routines.The encode and decode library routines deal with buffers via the BUF_TYPE type andnine buffer routines with the following names and prototypes:• unsigned char BufGetByte(BUF_TYPE b);• unsigned char BufPeekByte(BUF_TYPE b);• char* BufGetSeg(BUF_TYPE b, unsigned long int* lenPtr);• void BufCopy(char* dst, BUF_TYPE b, unsigned long int* lenPtr);• void BufSkip( BUF_TYPE b, unsigned long int len);• void BufPutByteRvs( BUF_TYPE b, unsigned char byte);• void BufPutSegRvs( BUF_TYPE b, char* data, unsigned long int len);• int BufReadError(BUF_TYPE b);• int BufWriteError(BUF_TYPE b);To map the library's calls to buffer routines to your own buffer routines, a configura-tion header file is used. For example, to configure snacc to use the buffer type MyBuffer,the following would appear in the configuration file.#include "my-buf.h"#define BUF_TYPE MyBuffer**#define BufGetByte(b)#define BufGetSeg(b, lenPtr)#define BufCopy( dst, b, lenPtr)#define BufSkip( b, len)#define BufPeekByte( b)MyBufGetByte(b)MyBufGetSeg(b, lenPtr)MyBufCopy( dst, b, lenPtr)MyBufSkip(b, len)MyBufPeekByte( b)Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^55#define BufPutByteRv( b, byte)^MyBufPutByteRv( b, byte)#define BufPutSegRv( b, data, len) MyBufPutSegRv( b, data, len)#define BufReadError(b)^MyBufReadError(b)#define BufWriteError(b) MyBufWriteError(b)4.8 Memory ManagementLike buffer management, memory management is very important for efficient decoders.Snacc decoders allocate memory to hold the decoded value. After the decoded valuehas been processed it is usually freed. The decoding and freeing routines in the libraryand the ones generated by snacc both use the memory manager. The decoders allocatememory with the AsnlAlloc routine and the freeing routines call AsniFree.The configuration header file allows the user to change the default memory managerprior to compiling the library and the generated code. Snacc provides a particularlyefficient memory manager, discussed shortly, called "nibble memory".The memory manager must provide three routines: AsnlAlloc, AsniFree andCheckAsnlAlloc. These memory routines should have the following interfaces:void* AsnlAlloc(unsigned long int size);void AsnlFree(void* ptr);int^CheckAsnlAlloc(void* ptr, ENV_TYPE env);The decoders assume that AsnlAlloc returns a zeroed block of memory. This savesexplicit initialization of OPTIONAL elements with NULL in the generated decoders.The ENV_TYPE parameter is used with the error management system for calls to longjmp.To change the memory management system the configuration file needs to be edited.For example, if performance is not an issue and you want to use calloc and free, theconfiguration file would be as follows:#include "malloc.h"#define AsnlAlloc(size) calloc(1, size)Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^56#define AsnlFree(ptr)^free(ptr)#define CheckAsnlAlloc(ptr, env)\if ((ptr) == NULL)\longjmp(env, -27);The nibble memory system does not need explicit frees of each component so thegenerated free routines are not needed. However, if you change the memory managementto use something like malloc and free you should use the generated free routines.By default, snacc uses a nibble memory scheme to provide efficient memory man-agement. Nibble memory works by getting a large block of memory from the 0/S forallocating smaller requests. When the decoded PDU is no longer required by the applica-tion the entire space allocated to the PDU can be freed by calling a routine that simplyresets a pointer. There is no need to use the snacc generated free routines to traversethe entire data structure, freeing a piece at a time.If calla c and free are used for memory management instead of nibble memory, thegenerated free routines must be used to free the values. The generated free routineshierarchically free all of a PDU's memory using a depth first algorithm4.9 Novel Non-performance Related FeaturesIn this section, the method snacc uses to handle the encoding and decoding of ANYDEFINED BY types is described.The ANY and ANY DEFINED BY type are classically the most irritating ASN.1types for compiler writers. They rely on mechanisms outside of ASN.1 to specify whattypes they contain. The 1992 ASN.1 standard has rectified this by adding much strongertyping semantics and eliminating macros.The ANY DEFINED BY type can be handled automatically by snacc if the SNMPOBJECT-TYPE [snmp90] macro is used to specify the identifier value to type mappings.Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^57The identifier can be an INTEGER or OBJECT IDENTIFIER. Handling ANY typesproperly will require modifications to the generated code since there is no identifierassociated with the type.The general approach used by snacc to handle ANY DEFINED BY types is to lookupthe identifier value in a hash table for the identified type. The hash table entry containsinformation about the type such as the routines to use for encoding and decoding.Two hash tables are used, one for INTEGER to type mappings and the other forOBJECT IDENTIFIER to type mappings. Snacc generates an InitAny routine for eachmodule that uses the OBJECT-TYPE macro. This routine adds entries to the hashtable(s). The InitAny routine(s) is called once before any encoding or decoding is done.The hash tables are constructed such that an INTEGER or OBJECT IDENTIFIERvalue will hash to an entry that contains:• the anyId• the INTEGER or OBJECT IDENTIFIER that maps to it• the size in bytes of the identified data type• a pointer to the type's PDU encode routine• a pointer to the type's PDU decode routine• a pointer to the type's print routine• a pointer to the type's free routineThe referenced encode and decode routines are PDU oriented in that they encode thetype's tag(s) and length(s) as well as the type's content.Snacc builds an enum called AnyId that enumerates each mapping defined by theOBJECT-TYPE macros. The name of the value associated with each macro is usedChapter 4. Performance Considerations for the Snacc ASN.1 Compiler^58as part of the enumerated identifier. The anyld in the hash table holds the identifiedtype's AnyId enum value. The anyld is handy for making decisions based on the receivedidentifier, without comparing OBJECT IDENTIFIERs. If the identifiers are INTEGERsthen the anyld is less useful.With ANY DEFINED BY types, it is important to have the identifier decoded beforethe ANY DEFINED BY type is decoded. Hence, an ANY DEFINED BY type should notbe declared before its identifier in a SET since SETs are un-ordered. An ANY DEFINEDBY type should not be declared after its identifier in a SEQUENCE. Snacc will print awarning if either of these situations occur.The hash tables may be useful to plain ANY types which do not have an identifier fieldlike the ANY DEFINED BY types; the OBJECT-TYPE macro can be used to define themappings and the SetAnyTypeBylnt or SetAnyTypeByDid routine can be called with theappropriate identifier value before encoding or decoding an ANY value. The compilerwill insert calls to these routines where necessary with some of the arguments left as"???" . There will usually be a "/* ANY - Fix me ! *1" comment before code thatneeds to be modified to correctly handle the ANY type. The code generated from anASN.1 module that uses the ANY type will not compile without modifications.OPTIONAL ANYs and ANY DEFINED BY types that have not been tagged are aspecial problem for snacc. Unless they are the last element of a SET or SEQUENCE,the generated code will need to be modified. Snacc will print a warning message when itencounters one of these cases.To illustrate how ANY DEFINED BY values are handled, we present typical encodingand decoding scenarios. Each ANY or ANY DEFINED BY type is represented in C bythe AsnAny type which contains only a void* named value to hold a pointer to the valueand a AnyInfo* named ai which points to a hash table entry.When encoding, before the ANY DEFINED BY value is encoded, SetAnyTypeBy0idChapter 4. Performance Considerations for the Snacc ASN.1 Compiler^59or SetAnyTypeBylnt (depending on the type of the identifier) is called with the currentidentifier value to set the AsnAny value's ai pointer to the proper hash table entry. Thento encode the ANY DEFINED BY value, the encode routine pointed to from the hashtable entry is called with the value void* from the AsnAny value. The value void* inthe AsnAny should point to a value of the correct type for the given identifier, if the userset it up correctly. Note that setting the void* value is not type safe; one must makesure that the value's type is the same as indicated by the identifier.For decoding, the identifier must be decoded prior to the ANY DEFINED BY valueotherwise the identifier will contain an uninitialized value. Before the ANY or ANYDEFINED BY value is decoded, SetAnyTypeByOid or SetAnyTypeBylnt (depending onthe type of the identifier) is called to set the AsnAny value's ai pointer to the properhash table entry. Then a block of memory of the size indicated in the hash table entryis allocated, and its pointer stored in the AsnAny value's void* entry. Then the decoderoutine pointed to from the hash table entry is called with the newly allocated block asits value pointer parameter. The decode routine fills in the value assuming it is of thecorrect type.There is a problem with snacc's method for handling ANY DEFINED BY types forspecifications that have two or more ANY DEFINED BY types that share some identifiervalues. Since only two hash tables are used and they are referenced using the identifiervalue as a key, duplicate identifiers will cause unresolvable hash collisions.4.10 C++ DesignThe C++ backend of snacc was designed after the C backend had been written. Thebasic model that the generated C++ uses is similar to that of the generated C, butbenefits from the object oriented features of C++.Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^60Some cleaner designs were rejected either due to their poor performance or the in-ability of the available C++ compiler to handle certain language features.Tags and lengths would fit nicely into their own classes but performance was consid-erably worse than the technique used in the C model. The C design was retained in theC++ model for this reason.For error management, C++'s try and catch [Stroustrup9l] are obvious replacementsfor the setjmp and longjmp used by the C decoders. Unfortunately, this is a newer C++feature and was not yet supported.C++ templates are very attractive for type safe lists (for SET OF and SEQUENCEOF) without duplicating code. Since template support was weak in the available C++compiler, templates were rejected. Instead, each SET OF and SEQUENCE OF typegenerates its own new class with all of the standard list routines.Every ASN.1 type is represented by a C++ class with the following characteristics:1. inherits from the AsnType base class2. has a parameterless constructor3. has a clone method, Clone4. has a PDU encode and decode method, BEnc and BDec5. has a content encode and decode method, BEncContent and BDecContent6. has top level interfaces to the PDU encode and decode methods (handles the setjmpetc.) for the user, BEncPdu and BDecPdu7. has print method, PrintThe following C++ fragment shows the class features listed above in greater detail:Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^61class Foo : public AsnType{// data memberspublic:Foo(); // requires parameterless constructor// PDU (tags/lengths/content) encode and decode routinesAsnLen BEnc(BUF_TYPE b);void BDec(BUF_TYPE b, AsnLen& bytesDecoded, ENV_TYPE env);// content encode and decode routinesAsnLen BEncContent(BUF_TYPE b);void BDecContent(BUF_TYPE b, AsnTag tag, AsnLen elmtLen,AsnLen& bytesDecoded, ENV_TYPE env);// methods most likely to be used by your code.// Returns non-zero for successint BEncPdu( BUF_TYPE b, AsnLen& bytesEncoded);int BDecPdu( BUF_TYPE b, AsnLen& bytesDecoded);void Print(ostream& os);AsnType* Clone();In brief, the AsnType provides a base class that has virtual BEnc, BDec and Cloneroutines. The purpose of this class is to provide a generic ASN.1 type class that canbe used to handle ANY and ANY DEFINED BY types. The Clone 4 routine is used togenerate a new instance (not a copy) of the object by calling the constructor of the objectthat it is invoked on. This allows the ANY DEFINED BY type decoder to create a new,initialized object of the correct type from one stored in a hash table when decoding.The virtual BDec method of the newly created object is called from AsnAny class's BDecmethod. When encoding, the AsnAny objects call the virtual BDec method of the typethey contain.4 Clone is a poorly chosen name. NewInstance would be better.Chapter 4. Performance Considerations for the Snacc ASN.1 Compiler^624.11 Table Driven Encoding and DecodingSnacc can generated type tables as well as source code. Type tables can be used instead ofgenerated routines for encoding and decoding. A type table can be loaded during runtimeand table routines from the library can use the ASN.1 type information in the type tableto encode, decode and for other things. The current table routines only support C.No C code specific to the ASN.1 data structure in a type table is used by the tableroutines. When decoding using a type table, the decoding routine builds a data structurefor the local representation using some simple rules.The rules for building a C data structure during decoding are as follows. For SE-QUENCEs and SETs the decoder will allocate an array of void* types. The array hasone entry for each SET component. Each entry in the array points to a value of theexpected type.The standard snacc library types are used for the primitive and list types. CHOICEtypes are similar to the ones snacc generates except the union is replaced with a void*since no type checking is done. CHOICEs are represented by a struct with a longint to define the element that is present and void* to point to the component of theCHOICE that is present.The table driven encoder expects values passed to it for encoding to be of the samestructure.Dealing with a complex data structure is difficult without a C definition for it. Typetables can be used to generate a header file that contains a friendly, properly typedversion of the data structure that the table routines will use for the given type table.The table routines do not use this header file but the user can in his code.Appendix C contains the ASN.1 definition of the type tables snacc generates. Thetype table data structure was defined in ASN.1 so that type tables are simple to encodeChapter 4. Performance Considerations for the Snacc ASN.1 Compiler^63to disk by using the snacc generated encoding routines. Conceivably, these type tablescould be sent over a network to dynamically configure a network device or to configurenetwork management and protocol testing tools.Chapter 5Implementation of the Snacc Compiler5.1 Snacc Compiler DesignThe snacc compiler is implemented with yacc, lex (actually GNU's equivalents, bisonand flex), and C. Despite the shortcomings of lex and yacc, they provide reasonableperformance without too much programming effort. Since yacc parsers are extremelydifficult to modify during runtime, any macro that the compiler is to handle must behand coded into the ASN.1 yacc grammar followed by recompilation of snacc. Macrodefinitions do not need special consideration since they are skipped by the compiler.Macro definitions and complex value notation are kept as text in the data structureresulting from a parse. This text can be parsed (via modifying the compiler) if desired.The syntax of the ASN.1 language was not initially designed with machine processingin mind. The ASN.1 grammar contains several ambiguities, and features such as macrosallow users to change the grammar. The fact that types can be referenced before theyare defined complicates parsing.To handle the anti-compiler nature of ASN.1's syntax, snacc makes several passes onthe parse tree data structure when compiling. The term "pass" is a bit misleading asnone of these traversals creates temporary files; this allows snacc to process large ASN.1specifications quite quickly. The compiler passes are explained in the next sections. Themain passes of the compiler are executed in the following order:1. Parse useful types ASN.1 module.64Chapter 5. Implementation of the Snacc Compiler^ 652. Parse all user specified ASN.1 modules.3. Link local and imported type references in all modules.4. Parse values in all modules.5. Link local and imported value references in all modules.6. Process any macro types.7. Normalize types.8. Mark recursive types and signal any recursion related errors.9. Check for semantic errors in all modules.10. Generate C/C++ type information for each ASN.1 type.11. Sort the types from least dependent to most dependent.12. Generate the C/C++ encoders and decoders.5.2 Pass 1: Parsing the Useful Types ModuleThe ASN.1 useful types are not hardwired into snacc. Instead they have been placed ina separate ASN.1 module. This allows the user to define his own useful types or re-definethe existing ones without modifying snacc . This also has the benefit that names of usefultypes are not key words in the lexical analyzer. This step is not really a compiler passon the module data, however it is described as one for simplicity.Snacc handles the useful types module differently from the other modules. Insteadof parsing the module and generating code for it, snacc parses the module and makesthe types in it accessible to all of the other modules being parsed. Note that the otherChapter 5. Implementation of the Snacc Compiler^ 66modules do not need to explicitly import from the useful types module. See Section 5.4for more information on how useful types affect linking.The encode, decode and other routines for the useful types are in the runtime library.Currently, the useful types library routines are the same as the ones the compiler wouldnormally generate given the useful types module. However, since they are in the library,they can be modified. For example, one could check character sets (string types), or uselocal time formats to represent their BER equivalent (UTCTime, GeneralizedTime).The following types are in the useful types module:ASN-USEFUL DEFINITIONS ::=BEGINObjectDescriptor ::= [UNIVERSAL 7] IMPLICIT OCTET STRINGNumericString ::= [UNIVERSAL 18] IMPLICIT OCTET STRINGPrintableString ::= [UNIVERSAL 19] IMPLICIT OCTET STRINGTeletexString^::= [UNIVERSAL 20] IMPLICIT OCTET STRINGT61String^::= [UNIVERSAL 20] IMPLICIT OCTET STRINGVideotexString^::= [UNIVERSAL 21] IMPLICIT OCTET STRINGIA5String^::= [UNIVERSAL 22] IMPLICIT OCTET STRINGGraphicString^::= [UNIVERSAL 25] IMPLICIT OCTET STRINGVisibleString^::= [UNIVERSAL 26] IMPLICIT OCTET STRINGIS0646String^::= [UNIVERSAL 26] IMPLICIT OCTET STRINGGeneralString^::= [UNIVERSAL 27] IMPLICIT OCTET STRINGUTCTime^::= [UNIVERSAL 23] IMPLICIT OCTET STRINGGeneralizedTime ::= [UNIVERSAL 24] IMPLICIT OCTET STRINGEXTERNAL^[UNIVERSAL 8] IMPLICIT SEQUENCE{direct-reference^OBJECT IDENTIFIER OPTIONAL,indirect-reference^INTEGER OPTIONAL,data-value-descriptor ObjectDescriptor OPTIONAL,encoding CHOICEsingle-ASN1-type [0] OCTET STRING, -- should be ANYoctet-aligned^[1] IMPLICIT OCTET STRING,arbitrary^[2] IMPLICIT BIT STRING}ENDChapter 5. Implementation of the Snacc Compiler^ 675.3 Pass 2: Parsing ASN.1 ModulesDuring this pass, all of the specified modules are parsed into the Module data structure.The ASN.1 source files are not consulted again. Yacc and lex are doing the work in thisstep.A lexical tie-in is where the yacc parser puts the lexical analyzer into a different mode(and is usually considered a hack). The different modes tokenize symbols differently,which is useful for skipping well delimited sections that cannot be parsed easily by ayacc parser on the first pass. Lexical tie-ins are used in two places to simplify the ASN.1grammar sufficiently for yacc and lex . There are two special modes in the lexical analyzer,one for ASN.1 macro definitions and the other for ASN.1 values enclosed in {}'s.The lexical tie-in for scanning macro definition bodies works with macro definitionsof the following form:<upper case identifier> MACRO ::= BEGIN ... ENDEverything between the BEGIN and END is stuffed into a string by lex and passedback as single token to the yacc parser.Values within {}'s are parsed in a similar way. Value parsing cannot really be done atthis stage since complete type information is needed and the types are not fully parsedor linked yet.Most syntax errors are reported during this pass. If syntax errors are encountered,snacc will report as many as it can from the offending module before the parser is hope-lessly lost. If the types and values are separated with semi-colons, the parser can recoverafter a syntax error and attempt to find more errors in that module before exiting.Chapter 5. Implementation of the Snacc Compiler^ 685.4 Pass 3: Linking TypesThe third pass links all type references 1 . Snacc attempts to resolve any currently visible(i. e. not in macro definitions or constructed values) type reference. This includes typereferences in simple value definitions and subtyping information. The useful types module(if given) is linked first.Snacc will exit after this pass if any type references could not be resolved. Errormessages with file and line number information will be printed to stderr.First, each module identifier is checked for conflicts with the others. If the moduleidentifier includes an OBJECT IDENTIFIER, snacc only checks for conflicts with theother module identifier OBJECT IDENTIFIERs. When only a module name is pro-vided, snacc checks for conflicts with the other module names, even if the other moduleidentifiers include OBJECT IDENTIFIERs. If the OBJECT IDENTIFIER of a moduleidentifier contains any value references, it will be ignored for module look-up purposes.Note that value references within the module identifier OBJECT IDENTIFIERs are notallowed in the 1992 version of ASN.1 due to the difficulty in module name resolution.Two modules with the same name but different OBJECT IDENTIFIERs are notconsidered an error within ASN.1. However, because the generated files use the modulename as part of their name, the code generation pass will fail.Next, each module's import lists are resolved by finding the named modules and thenverifying that the named module contains all of the types imported from it. Then for eachmodule, each type reference (except those of the form modulename. typename) is assumedto be a local type reference and the linker attempts to find a local type definition of thesame name. If a matching local definition is found, the type reference is resolved and thelinker continues with the next type reference.'This pass also counts and stores the number of times a type definition is referenced locally and fromother modules. This information is used during the type sorting pass.Chapter 5. Implementation of the Snacc Compiler^ 69For each type reference of the form modulename.typename, the linker looks in themodule with name modulename for the type typename. If the type is found the referenceis resolved, otherwise a linking error is reported. Note that this form of type referenceprovides a special scope that does not conflict with other local or imported types inthat module. For type references that failed to resolve locally and are not of the formmodulename.typename, the linker looks in the import lists of the current type reference'smodule for a type to resolve with. If the type is found in the import lists, the referenceis resolved.For the remaining unresolved type references (failed local and legal import resolutionand are not of the form modulename.typename), the linker looks in the useful typesmodule. If the type is found in the useful types module then the reference is resolved,otherwise a linking error is reported. Note that when a useful types module is specified,it is globally available to all modules, but it has the lowest linking priority. That is, if atype reference can be resolved legally without the useful types module, it will be.Some type checking must be done in this pass to link certain types properly. Theseinclude:• a SELECTION type must reference a field of a CHOICE type.• a COMPONENTS OF type in a SET must reference a SET.• a COMPONENTS OF type in a SEQUENCE must reference a SEQUENCE.5.5 Pass 4: Parsing ValuesThe fourth pass attempts to parse any value that is enclosed in {}'s. INTEGERS, REALsand BOOLEANS that are not enclosed in braces are parsed in the first pass. The valueparser uses each value's type information to help parse the value. Values within {}'sChapter 5. Implementation of the Snacc Compiler^ 70hidden within types such as default values and parts of subtypes are not parsed. Sincesubtypes and default values do not affect the generated code, upgrading the value parserin this respect is not very useful.The only type of value in {}'s that is parsed is the OBJECT IDENTIFIER. All ofthe OBJECT IDENTIFIER value forms are supported but snacc loosens the restrictionson using arc names defined in the OBJECT IDENTIFIER tree. ASN.1 allows OBJECTIDENTIFIER values to reference special built-in arc names from the OBJECT IDEN-TIFIER tree defined in Annexes B, C and D of CCITT X.208. For example the firstarc in an OBJECT IDENTIFIER value can be either ccitt, iso or joint-iso-ccitt. Theacceptable arc names are context dependent; for example the second arc can be one ofstandard, registration-authority, member-body or identified-organization only if the firstarc was iso or 1.Snacc uses a simplified algorithm to handle references to the arc names defined in theOBJECT IDENTIFIER tree. Any arc value that is represented by a single identifier ischecked to see if it is one of the arc names defined in the OBJECT IDENTIFIER tree;context is ignored. If the identifier matches one of the arc names then its value is setaccordingly. The lack of context sensitivity in snacc's algorithm may cause the arc nameto link with an arc name from the OBJECT IDENTIFIER tree when a local or importedINTEGER was desired. If this happens, snacc will produce an erroneous C/C++ valuedefinition for that OBJECT IDENTIFIER. The following is the list of special arc namesthat snacc understands.• ccitt = 0• iso = 1• joint-iso-ccitt = 2• standard = 0Chapter 5. Implementation of the Snacc Compiler^ 71• registration-authority = 1• member-body = 2• identified-organization = 3• recommendation = 0• question = 1• administration = 2• network-operator = 35.6 Pass 5: Linking ValuesThe fifth pass links value references. The value linker looks for value references to resolvein value definitions and type definitions, including default values and subtyping infor-mation. The value linking algorithm is virtually identical to the type linking pass (seeSection 5.4).Currently the value parsing is limited to OBJECT IDENTIFIER values. Simplevalues that are not between {}'s are parsed in the first pass. Here is an example thatillustrates the OBJECT IDENTIFIER parsing and linking The following values:foo OBJECT IDENTIFIER ::= { joint-iso-ccitt 2 88 28 }bar OBJECT IDENTIFIER ::= { foo 1 }bell INTEGER ::= 2gumby OBJECT IDENTIFIER ::= { foo bell }pokie OBJECT IDENTIFIER ::= { foo stimpy(3)}are equivalent to this:foo OBJECT IDENTIFIER ::= { 2 2 88 28 }Chapter 5. Implementation of the Snacc Compiler^ 72bar OBJECT IDENTIFIER ::= { 2 2 88 28 1 }bell INTEGER ::= 2gumby OBJECT IDENTIFIER ::= { 2 2 88 28 2}pokie OBJECT IDENTIFIER ::= { 2 2 88 28 3}5.7 Pass 6: Processing MacrosThe fifth pass processes macros. For all macros currently handled, snacc converts typedefinitions inside the macro to type references and puts the type definition in the normalscope. This way, the code generator does not have to know about macros to generatecode for the types defined within them.The only macro that receives any special processing is the SNMP OBJECT-TYPEmacro. This macro's information defines an OBJECT IDENTIFIER or INTEGER totype mapping for use with any ANY DEFINED BY type. Note that the OBJECT-TYPE macro has been extended beyond its SNMP definition to allow integer values forINTEGER to type mappings.ASN.1 allows you to define new macros within an ASN.1 module; this can changethe grammar of the ASN.1 language. Since snacc is implemented with yacc and yaccgrammars cannot be modified easily during runtime, snacc cannot change its parser inresponse to macro definitions it parses.Any macro that snacc can parse has been explicitly added to the yacc grammar beforecompiling snacc . When a macro that snacc can parse is parsed, a data structure thatholds the relevant information from the macro is added to the parse tree. The type andvalue linking passes as well as the macro processing and possibly the normalization passneed to be modified to handle any new macros that you add.The following macros are parsed:Chapter 5. Implementation of the Snacc Compiler^ 73• OPERATION (ROS)• ERROR (ROS)• BIND (ROS)• UNBIND (ROS)• APPLICATION-SERVICE-ELEMENT (ROS)• APPLICATION-CONTEXT• EXTENSION (MTSAS)• EXTENSIONS (MTSAS)• EXTENSION-ATTRIBUTE (MTSAS)• TOKEN (MTSAS)• TOKEN-DATA (MTSAS)• SECURITY-CATEGORY (MTSAS)• OBJECT (X.407)• PORT (X.407)• REFINE (X.407)• ABSTRACT-BIND (X.407)• ABSTRACT-UNBIND (X.407)• ABSTRACT-OPERATION (X.407)Chapter 5. Implementation of the Snacc Compiler^ 74• ABSTRACT-ERROR (X.407)• ALGORITHM (X.509)• ENCRYPTED (X.509)• PROTECTED (X.509)• SIGNATURE (X.509)• SIGNED (X.509)• OBJECT-TYPE (SNMP)However, no code is generated for these macros. As stated above, only the OBJECT-TYPE macro affects the encoders and decoders.5.8 Pass 7: Normalizing TypesThe sixth pass normalizes the types to make code generation simpler. The following isdone during normalization:1. COMPONENTS OF types are replaced with the contents of the SET or SE-QUENCE components that they reference.2. SELECTION types are replaced with the type they reference.3. SEQUENCE, SET, CHOICE, SET OF and SEQUENCE OF definitions embeddedin other types are made into separate type definitions.4. For modules in which "IMPLICIT TAGS" is specified, tagged type references suchas " [APPLICATION 2] Foo" are marked IMPLICIT if the referenced type ("Foo"in this case) is not an untagged CHOICE or untagged ANY type.Chapter 5. Implementation of the Snacc Compiler^ 755. INTEGERs with named numbers, BIT STRINGs with named bits and ENUMER-ATED types embedded in other types are made into separate type definitions.The COMPONENTS OF and SELECTION type simplifications are obvious but themotivation for the others may not be so obvious. The third type of simplification makestype definitions only one level deep. This simplifies the decoding routines since snaccuses local variables for expected lengths, running length totals and tags instead of stacks.The implicit references caused by "IMPLICIT TAGS" are marked directly on typereferences that need it. This saves the code generators from worrying about whetherimplicit tagging is in effect and which types can be referenced implicitly.The types with named numbers or bits are made into a separate type to allow theC++ back end to simply make a class that inherits from the INTEGER or BIT STRINGclass and defines the named numbers or bits inside an enum in the new class.5.9 Pass 8: Marking Recursive TypesThis pass marks recursive types and checks for recursion related errors. To determinewhether a type definition is recursive, each type definition is traced to its leaves, checkingfor references to itself. Both local and imported type references within a type are followedto reach the leaves of the type. A leaf type is a simple (non-aggregate) built-in type suchas an INTEGER or BOOLEAN. At the moment, recursion information is only usedduring the type dependency sorting pass.Snacc attempts to detect two types of recursion related errors. The first type of errorresults from a recursive type that is composed solely of type references. Types of thisform contain no real type information and would result in zero-sized values. For examplethe following recursive types will generate this type of warning:A : := BChapter 5. Implementation of the Snacc Compiler^ 76B : := CC : := AThe other recursion related error results from a type whose value will always be infinitein size. This is caused by recursion with no optional component that can terminate therecursion. If the recursion includes an OPTIONAL member of a SET or SEQUENCE, aCHOICE member, or a SET OF or SEQUENCE OF, the recursion can terminate.Both of the recursion errors generate warnings from snacc but will not stop codegeneration.5.10 Pass 9: Semantic Error CheckingThe ninth pass checks for semantic errors in the ASN.1 specification that have not beenchecked already. Both the type linking pass and the recursive type marking pass do someerror checking as well. Snacc attempts to detect the following errors in this pass:• Elements of CHOICE and SET types must have distinct tags.• CHOICE, ANY and ANY DEFINED BY types cannot be implicitly tagged.• Type and value names within the same scope must be unique.• Field names in a SET, SEQUENCE or CHOICE must be distinct. If a CHOICEis a member of a SET, SEQUENCE or CHOICE and has no field name, thenthe embedded CHOICE's field names must be distinct from its parents to avoidambiguity in value notation.• An APPLICATION tag code can only be used once per module.• Each value in a named bit list (BIT STRINGs) or named number list (INTEGERsand ENUMERATED) must be unique within its list.Chapter 5. Implementation of the Snacc Compiler^ 77• Each identifier in a named bit list or named number list must be unique within itslist.• The tags on a series of one or more consecutive OPTIONAL or DEFAULT SE-QUENCE elements and the following element must be distinct.• A warning is given if an ANY DEFINED BY type appears in a SEQUENCE beforeits identifier or in a SET. These would allow encodings where the ANY DEFINEDBY value was prior to its identifier in the encoded value; ANY DEFINED BYvalues are difficult to decode without knowing their identifier.Snacc does not attempt to detect the following errors due to the limitations of thevalue parser.• SET and SEQUENCE values can be empty ({}) only if the SET or SEQUENCEtype was defined as empty or all of its elements are marked as OPTIONAL orDEFAULT.• Each identifier in a BIT STRING value must be from that BIT STRING's namedbit list (this could be done in an improved value linker instead of this pass).5.11 Pass 10: Generating C/C++ Type InformationThis pass fills in the target language type information. The process is different for theC and C++ back ends since the C++ ASN.1 model is different and was developed later(more design flaws have been corrected for the C++ backend).For C and C++ there is an array that contains the type definition information foreach built-in type. For each built-in ASN.1 type, the C array holds:typename the C typedef name for this type definition.Chapter 5. Implementation of the Snacc Compiler^ 78isPdu TRUE if this type definition is a PDU. This is set for types used in ANY and ANYDEFINED BY types and those indicated by the user via compiler directives. Ad-ditional interfaces to the encode and decode routines are generated for PDU types.The SNMP OBJECT-TYPE macro is the current means of indicating whether atype is used within an ANY or ANY DEFINED BY type.isPtrForTypeDef TRUE if other types defined solely by this type definition are definedas a pointer to this type.isPtrForTypeRef TRUE if type references to this type definition from a SET or SE-QUENCE are by pointer.isPtrForOpt TRUE if OPTIONAL type references to this type definition from a SETor SEQUENCE are by pointer.isPtrInChoice TRUE if type references to this type definition from a CHOICE are bypointer.optTestRoutineName name of the routine to test whether an OPTIONAL element ofthis type in a SET or SEQUENCE is present. It is usually just the name of a Cmacro that tests for NULL.printRoutineName name of this type definition's printing routine.encodeRoutineName name of this type definition's encoding routine.decodeRoutineName name of this type definition's decoding routine.freeRoutineName name of this type definition's freeing routine.The C++ type definition array is similar to C's. It contains:Chapter 5. Implementation of the Snacc Compiler^ 79classname holds the C++ class name for this type definition.isPdu same as C isPdu except that is does not affect the code generation since the C++back end includes the extra PDU encode and decode routines by default.isPtrForTypeDef same as C isPtrForTypeDef.isPtrForOpt same as C isPtrForOpt.isPtrInChoice same as C isPtrInChoiceisPtrInSetAndSeq whether type references to this class from a SET or SEQUENCEare by pointer.isPtrInList whether type references to this class from a SET OF or SEQUENCE OFare by pointer.optTestRoutineName name of the routine to test whether an OPTIONAL element ofthis type in a SET or SEQUENCE is present. It is usually just the name of a Cmacro that tests for NULL.The first step of this pass uses the type arrays to fill in the C or C++ type definitioninformation for each module's ASN.1 type definitions. This is done for the useful typesmodule as well.The next step goes through each constructed type and fills in the type referenceinformation for each reference to a built-in, user defined or useful type. Much of the typereference information is taken from the referenced type's definition information. Thetype reference information contains the following (for both C and C++):fieldName field name for this type if it is referenced from a CHOICE, SET or SE-QUENCE.Chapter 5. Implementation of the Snacc Compiler^ 80typeName type name of the referenced type.isPtr whether this reference is by pointer.namedElmts named elements for INTEGER, ENUMERATED or BIT STRING typeswith their C names and values.choiceIdValue if this type reference is in a CHOICE, this holds the value of theCHOICE's choiceld that indicates the presence of this field.choiceIdSymbol if this type reference is in a CHOICE, this holds the C enum valuesymbol that has the choiceldValue value.optTestRoutineName name of the routine or macro to test for the presence of thiselement if it is an OPTIONAL element of a SET or SEQUENCE.5.12 Pass 11: Sorting TypesThis pass sorts the type definitions within each module in order of dependence. ASN.1does not require the types to be defined before they are referenced, but both C and C++do. Without this pass, the generated types/classes would probably not compile due totype dependency problems. There is no attempt to order the modules; command lineorder is used for the module dependence. If there are problems with mutually dependentmodules, the simplest approach is to combine the dependent modules into a single ASN.1module.Some compilers such as CASN1 [Neufeld90] require the user to order the types withinthe ASN.1 modules. This can be tedious and since snacc may generate new type defini-tions from nested aggregate type definitions in the normalization pass, the user does nothave complete control over the order of every type definition.Chapter 5. Implementation of the Snacc Compiler^ 81Snacc attempts to sort the types from least dependent to most dependent using thefollowing ad-hoc algorithm:First, separate the type definitions within a module into the following groups:1. Type definitions that are defined directly from simple built-in types such as INTE-GER.2. Types such as SET, SEQUENCE, SET OF, SEQUENCE OF and CHOICE thatcontain no references to types defined in this module. That, is they are definedfrom only simple built-in types, imported types or useful types.3. Type definitions that reference locally defined types.4. Type definitions that are not referenced by any local types.Only the 3rd group of type definitions needs more sorting. After it has been sorted,the groups are merged in the order 1, 2, 3, 4 to yield a sorted type definition list.Now we describe how the 3rd group of type definitions is sorted.1. For each type definition in the third group, a list of its local type references is builtand attached to it. This type reference list only goes one level deep; it does notfollow type references to find more type references.2. All of the linearly-dependent types are removed and sorted. This is done by re-peatedly removing type definitions that do not directly depend on any other typedefinitions that remain in the 3rd group. The process of removing the type defini-tions sorts them.3. The type definitions that were not removed in step 2 are divided into two groups:recursive and non-recursive. The non-recursive types depend on the recursive onessince they are still in the list after step 2.Chapter 5. Implementation of the Snacc Compiler^ 824. The non-recursive types from step 3 are sorted as in step 2. All of them shouldsort linearly since none are recursive.5. If the target language is C, any SET OF or SEQUENCE OF types are separatedfrom the recursive type definitions built in step 3. This is done because the Crepresentation of a list type is generic (uses a void* to reference the list element)and therefore does not really depend on the list's element type.6. The list of local type references for the recursive types from step 3 is re-generatedas in step 1 using a relaxation: types referenced as pointers are not added to atype's reference list.7. The recursive types from step two are re-sorted as in step 2 using their new localtype reference lists. Two lists are formed, those that sorted linearly and those thatdid not. The latter list should be empty.To form a sorted third group, the lists are merged in the following order:• linearly sorted types from step 2• separated list types (C only) from step 5• sorted recursive types from step 7• unsorted recursive types from step 7 (hopefully empty)• sorted non-recursive types from step 4In C, the code generator defines both typedef names and struct tags (names). Forexample,Foo ::= SET { a INTEGER, b BOOLEAN }Bar ::= SEQUENCE { a OBJECT IDENTIFIER, b Foo }Chapter 5. Implementation of the Snacc Compiler^ 83translates to the following C data types:typedef struct Foo /* SET */{Asnlnt a; /* INTEGER */AsnBool b; /* BOOLEAN */} Foo;typedef struct Bar /* SEQUENCE */{AsnOid a; /* OBJECT IDENTIFIER */struct Foo* b; /* Foo */} Bar;Note that both the struct and the typedef have the name Foo. Also note that theBar type references the Foo via struct Foo*.For types such as Bar that contain the Foo type, Foo is referenced as struct Foo*instead of just Foo* because C allows you to use the type struct Foo* (incompletetype) in defining types even prior to the actual declaration of the the struct Foo. TheFoo type can only be used after the Foo typedef declaration. The use of incompletetypes can often overcome recursion related type ordering problems (not relevant in thisexample since they are not recursive).5.13 Pass 12: Generating CodeThis pass creates and fills the source files with C or C++ code. The purpose of the nor-malization, sorting and error detection passes is to simplify this pass. The normalizationpass simplified the ASN.1 types in various ways to make C/C++ type and code gener-ation simpler. The type sorting pass hopefully eliminates type dependency problems inthe generated code. The C/C++ type generator simply proceeds through the orderedtype list writing the C/C++ type definitions to a header file.Chapter 5. Implementation of the Snacc Compiler^ 84The error detection and linking passes will make snacc exit if errors are found, so thecode generation pass can assume the ASN.1 types are virtually error free. This usuallyallows snacc to exit gracefully instead of crashing due to an undetected error.Chapter 6Results and EvaluationWe did a number of experiments to evaluate the performance of different encoding rulesand different implementations. We also ran experiments to evaluate the performancecost of various buffer and memory management features.The encoding rules we examined are HP/Apollo's NDR, Sun Microsystem's XDR,BER and PER (BASIC-ALIGNED). We also tested the simple and limited C basedencoding rules to provide information on the maximum throughput that can be achievedif many assumptions are made. These encoding rules were described in Chapter 2.We tested the implementations provided by five tools. The NIDL compiler producesC based NDR encoders and decoders. Rpcgen produces C based XDR encoding anddecoding routines. The other three tools, snacc, CASN1 and ISODE's POSY/PEPY,compile ASN.1 to produce BER routines in C. Hand-coded implementations were usedfor PER and C based encoding rulesThe encoders and decoders were compared for their throughput, the size of the en-coded values and the size of their object code. The throughput is the most importantaspect of these implementations. The size of encoded values can be important whendealing with expensive networks or for archiving purposes. The object code size of animplementation becomes a consideration when building embedded applications such asSNMP ASN.1 management for a network device.This chapter consists of four parts:• The comparison and analysis of different encoding rules and implementations with85Chapter 6. Results and Evaluation^ 86a structured value.• The comparison and analysis of different encoding rules with the integer, real andstring primitive types.• The evaluation of the performance cost of various memory and buffer managementtechniques.• The execution analysis (profiling) of snacc BER encoders and decoders.6.1 The PersonnelRecord Benchmark6.1.1 Tools BenchmarkedThe BER encoders and decoders of three ASN.1 tools, snacc, CASN1 and ISODE'sPOSY/PEPY, were benchmarked and analyzed. We also benchmarked the encoders anddecoders generated by rpcgen (XDR) and NIDL (NDR). These tests are shown in Table6.5.For each of these tools except snacc , we used the "out of the box" implementationthey produced. For configuration options that had to be set by the user, such as thebuffering mechanism, the fastest option was chosen. Section 6.2 looks into the costs ofimplementation features such as these.Three very different BER implementations from the snacc tool were used. We testedthe C, C++ and table based versions that snacc produced.NIDL and rpcgen were described in Chapter 2 and snacc was discussed in depth inChapters 4 and 5. The CASN1 and ISODE tools are briefly described here.CASN1 [Neufeld90] is an older ASN.1 compiler developed at UBC. It produces Cencoders and decoders from an ASN.1 specification. It has been used in at least oneChapter 6. Results and Evaluation^ 87tool language encoding rulesrpcgen XDR XDRNIDL NIDL NDRISODE ASN.1 BERCASN1 ASN.1 BERsnacc ASN.1 BER(by hand) ASN.1 PER(by hand) ASN.1 old PER(by hand) C ptr to offsetTable 6.5: Tools and encoding rules tested with the PersonnelRecord Benchmarkcommercial application, and in several other research projects. CASN1 supports 1984ASN.1 and some ROSE [ROS88] macros.ISODE [Rose90] is a freely available ISO protocol development environment. Becauseof the development-oriented nature of ISODE , flexibility was more of a design consider-ation than performance. ISODE includes several ASN.1 tools. The POSY tool acceptsan ASN.1 abstract syntax and produces C data structures for the ASN.1 types and aninput file for PEPY. The PEPY input file consists of the original abstract syntax aug-mented with compiler directives, action statements, control statements and value passingstatements that tell PEPY how to create correct BER encoding and decoding routinesfor the C data structure produced by POSY.PEPY supports type references to other ASN.1 modules provided that the referencedASN.1 module has already been processed by PEPY. It produces a file containing taggingand other information for each ASN.1 file it processes. Macro support requires the useof other tools such as ROSY that remove the macros from the abstract syntax andreplace them with the appropriate type definitions as necessary so the resulting file canbe processed by POSY/PEPY.Chapter 6. Results and Evaluation^ 886.1.2 Benchmark DesignThe aim of this benchmark is to compare the performance of different data represen-tations and implementations thereof in handling a structured data value. We chose a"PersonnelRecord" type shown in Figure 6.7, with the value shown in Figure 6.8 for thisbenchmark. In retrospect, a better choice of data structure may have been the Mix-Treetype from [Huitema92] that allows arbitrarily "deep" values. Perhaps an even betterchoice would be an X.400 PDU, but specifying it in anything other than ASN.1 (e.g.NIDL ) would be a difficult task.To highlight the costs of the structuring mechanisms and the overall implementation,the PersonnelRecord is mostly composed of string types. The simple string types havesimilar translation costs for all of the encoding rules tested because the characters inthe string require no real translation. Primitive types such as integers and reals arelikely to vary considerably in performance between BER, PER, XDR and NDR; theseare benchmarked in the next section.Each encoder was benchmarked on the time taken to encode the PersonnelRecordvalue in Figure 6.8 and free the resulting encoded value one million times. Each decoderwas benchmarked on the time required to decode the encoded PersonnelRecord, deletethe resulting data structure and reset the reference to the encoded data one million times.To provide more uniform results, the size of the buffer for the encoded values was setlarge enough to hold the entire encoded PDU. Thus, no "buffer faults" occurred duringencoding (writing) or decoding (reading).The timings were obtained by calling the UNIX getrusage system call [GRU90] im-mediately before and after both the encode and decode loop. The timings in the tablesrepresent the difference in user time between the first and last getrusage call.All encoders and decoders, including their support libraries, were compiled with theChapter 6. Results and Evaluation^ 89PersonnelRecord ::= [APPLICATION 0] IMPLICIT SET{Name,title^[0] IA5String,EmployeeNumber,dateOfHire^[1] Date,nameOfSpouse [2] Name,children^[3] IMPLICIT SEQUENCEOF ChildlnformationDEFAULT {}Childlnformation ::= SET{Name,dateOfBirth [0] DateName ::= [APPLICATION 1] IMPLICIT SEQUENCE{givenName IA5String,initial IA5String,familyName IA5String}EmployeeNumber ::= [APPLICATION 2] IMPLICIT INTEGERDate ::= [APPLICATION 3] IMPLICIT IA5String^YYYYMMDDFigure 6.7: ASN.1 definition of the PersonnelRecordChapter 6. Results and Evaluation^ 90givenName "John",initial^"E",familyName "Smith"},title "The Big Cheese",99999,dateOfHire "19820104",nameOfSpouse{givenName "Mary",initial^"L",familyName "Smith"I,children{givenName "James",^initial^"R",familyName "Smith"I,dateOfBirth "19570210"1 ,{givenName "Lisa",initial^"M",familyName "Smith"I,dateOfBirth "19590621"{Figure 6.8: PersonnelRecord Value used in the benchmarksChapter 6. Results and Evaluation^ 91MIPS cc compiler, using the -0 compiler switch. All benchmarks were run on a MIPSR3260 (18.2 specmarks) with 48 megabytes of RAM, running version 4.51 of the MIPSUNIX operating system. The tests were run during a time when the system usage wasminimal, however, this did not appear to affect the results.Table 6.6 holds a brief description of each benchmark we performed for this section.Each benchmark (referenced by its "benchmark id" from Table 6.6) is defined conciselyin the next sections. All BER encoders used the definite length option.We tested the optimal case for XDR and NDR. The optimal case for XDR is encodingand decoding on a machine with four byte words, big endian integers and IEEE float anddouble representation. NDR is always optimal for encoding because it uses the host'srepresentation. Our NDR decoding benchmark was optimal because the decoding hostwas the same architecture (actually the same machine). The next section looks at thenon-optimal case for NDR and XDR.The snacc C encoders and decoders for BER, PER91 and PER92 in this test wereminimal implementations. The buffers were simply a contiguous block of memory andthe nibble memory system had its expansion capability disabled. The buffer reading andwriting routines did no range checking, allowing buffer overflows. Section 6.3 examinesthe costs of using safer buffer and memory systems. The snacc C++ and table basedversions used in this benchmark were considerably more robust.6.1.3 Benchmark Results and AnalysisThe benchmark results for encoding and decoding the PersonnelRecord value shownin Figure 6.8 one million times are shown in Table 6.8. The memory usage during thebenchmark for each implementation is shown in Table 6.9. The code sizes are shown inTable 6.7. The results are briefly presented here.The C based encoding rules were by far the fastest, but the encoded size was theChapter 6. Results and Evaluation^ 92benchmark id encoding rules description1.01 BER POSY/PEPY encoder and decoder with nomodifications. String type "Presentation Stream"(buffer). ISODE version 6.1.02 BER CASN1 encoder and decoder with no modifications.1.03 XDR XDR encoder and decoder with no modifications.1.04 NDR NIDL generated NDR encoder and decoder.Version 1.51 of the NIDL compiler.1.05 C hand coded C pointer to offset encoder and decoder.1.06 BER minimal snacc encoder and decoder.1.07 PER91 minimal snacc encoder and decoder hand modified tosupport 1991 Packed Encoding Rules (obsolete).1.08 PER92 minimal snacc encoder and decoder hand modified tosupport 1992 Packed Encoding Rules.1.09 BER snacc C++ encoder and decoder.1.10 BER minimal snacc table driven encoder and decoder in C.Table 6.6: Benchmark descriptionsbenchmark id enc/dec .o executable1.01 12044 491521.02 3876 614401.03 884 409601.04 4028 1597441.05 660 327681.06 8020 450561.09 34708 2129921.10 Ot 86016tTable based tools have no abstract sytax specific code. A 660 bytetype table was loaded for the PersonnelRecord instead.Table 6.7: Code size for the stripped .o files of PersonnelRecord specific code and thestripped benchmark executableChapter 6. Results and Evaluation^ 93benchmarkidencodingtime (s)decodingtime (s)encodedsize (bytes)1.01 982.51 1291.71 1431.02 826.46 403.19 1431.03 186.54 311.67 1801.04 165.65 78.74 1451.05 7.62 8.19 2481.06 114.70 230.64 1431.07 91.17 176.93 1191.08 89.77 122.92 1011.09 80.73 330.20 1431.10 473.41 894.79 143Table 6.8: Timings for encoding and decoding the PersonnelRecord 1 million timesbenchmark id local intermediate transfer1.01 42/560 47/1552 1/1431.02 32/436 152/1260t 1/1431.03 17/208 0 1/1801.04 1/2056 0 1/1451.05 1/248 0 1/248$1.06 26/328 0 1/1431.07 26/328 0 1/1191.08 26/328 0 1/1011.09 - 1/1431.10 43/396 0 1/143f An intermediate representation was only used during encoding in CASN1.The transfer value is in the same memory as the local value.Table 6.9: Memory usage in # pieces memory/total # bytes for the local, intermediateand transfer (encoded) data representationISODE CASN1BER^BERXDR NDR C snacc^snacc^snacc^snaccBER^PER92 C++ BER table BERChapter 6. Results and Evaluation 94140012001000Se 800C0n 600ds400200El encoding time (s) - decoding time (s)Tools and Encoding RulesFigure 6.9: Time to encode and decode a PersonnelRecord 1 million timesChapter 6. Results and Evaluation^ 95largest, over twice as large as PER's, and the limitations of C make them non-viable forprotocol implementation. The C encoding rules managed over 240 Mbps for encodingand decoding.PER92, the fastest standard encoding, only managed approximately 12 Mbps (pro-jected speed if macros are used for buffer I/O and memory allocation). PER92 alsoproduced the smallest encoding. The PER92 decoder was third, after CER and NDR.The NDR decoder's speed can be attributed to two things. First, the NDR encodingwas already in the decoding host's native format so no real data conversion was required.Second, there were no allocations required for the local data value since the limitations ofNDR permit the use of a flat local data structure (i.e. the size of the local data structureis fixed so it can easily be pre-allocated).The poor performance of the PEPY/POSY encoder and decoder and the CASN1encoder can be directly attributed to their use of an intermediate data representationbetween the local and transfer representations (see Table 6.9).The table based implementation was roughly 3-4 times slower than the best of thecompiled BER, PER, NDR and XDR versions. Surprisingly, the snacc C++ encoderimplementation performed better than the stripped down snacc C version. Unlike theC version, the C++ implementation used safe buffer management and even used "ex-pensive" C++ features such as virtual functions. The gcc C++ compiler may use moreeffective optimizations than the MIPS C compiler. The C++ decoder was considerablyslower than the C version; this can most likely be attributed to the use of C++ built innew and delete operators versus the light-weight nibble memory.For the PersonnelRecord data structure PER92 is both faster and produces smallerencodings than BER. Both the PER and BER PersonnelRecord tested contained 16octet strings and 1 INTEGER and decoders allocated the same number of elements. Thedifference is in the number of tags and lengths that were encoded, resulting in the speedChapter 6. Results and Evaluation^ 96and size difference. BER encoded 30 tags, 13 constructed value lengths, and 17 primitivevalue lengths, resulting in a 143 byte encoding. PER encoded no tags, the number ofelements in the SEQUENCE OF, and 17 primitive value lengths yielding a 101 byteencoding. If the sizes of types such as the Date and the initial in the Name had beengiven in the ASN.1 via the SIZE subtype, their lengths would not need to be encoded byPER, allowing further compression.Using intermediate data representations (CASN/ and POSY/PEP)') greatly slowsencoding and decoding. This is clearly seen by comparing the three examples usingintermediate data structures to the snacc version that has similar features except for theintermediate data structure. CASN1's encoder (Benchmark 1.02 vs. 3.04) was over 7times slower, POSY/PEPY's encoder (Benchmark 1.01 vs. 3.08) was 8.5 times slower,and the POSY/PEPY decoder was over 4 times slower. Encoding rules should be designedto support one pass encoding and decoding, eliminating the need for costly intermediatedata structures. One pass, forwards encoding allows an application to encode directly toa stream oriented protocol such as TCP.Table 6.7 shows the code sizes of the stripped . o files for the PersonnelRecord specificfiles, and the sizes of the stripped benchmark programs. The most important result isthat table based encoders and decoders have no code specific to an abstract sytnax;instead they load a type table. The type tables are considerably smaller that theircorresponding code. The PersonnelRecord type table was only 660 bytes. The code sizeof the snacc generated encoders, decoders, print and free routines for the X.500 '88 ASN.1specification was 450 kilobytes. The type table for the same specification was only 27kilobytes.POSY/PEPYPOSY/PEPY encoders consist of two separate stages: the conversion of a value in anChapter 6. Results and Evaluation^ 97Figure 6.10: ISODE's local representation for the PersonnelRecord ValueThe Big CheeseSmith19570210LisaChapter 6. Results and Evaluation^ 98Figure 6.11: ISODE's PElement representation for the PersonnelRecord ValueChapter 6. Results and Evaluation^ 99abstract syntax specific data structure (see Figure 6.10) into the BER based PElementtree (see Figure 6.11) and then conversion of the PElement tree into the send bufferformat (a contiguous block for benchmarking purposes). Each PElement contains a tag,a length, a pointer to its data (primitive data or a child PElement), a pointer to itssibling (next element in the same SET or SEQUENCE) and other information. The useof the PElement tree is costly; each PElement is 48 bytes (see Table 6.9). The decodersuse the inverse of the encoding process.ISODE encoders and decoders provide flexible buffer management that supports dif-ferent buffer types at runtime by using the "Presentation Stream" data structure. ThePresentation Stream data type contains pointers to the buffer routines and data; call-ing buffer functions indirectly will hurt performance. The memory primitives used forthe decoded values and the PElements were malloc and free. Data items are freed byhierarchically traversing the data structure.CASN1CASN1's approach to encoding is to encode forwards into small, linked "IDX" buffers,maintaining a stack of buffer pointers and a corresponding stack of lengths for lengthcalculation of constructed types (see Figure 6.13). When the components of a constructedvalue have been encoded, the length on the length stack is encoded into its own IDX bufferand inserted after the buffer on the buffer stack.This encoding process results in every tag, end-of-contents and most lengths havingtheir own IDX buffer. The ratio of memory used by the IDX structures to actual BERdata is very high for some abstract syntaxes; for the 143 byte encoded length of thePersonnelRecord value used in the benchmarking, 76 IDX buffers were used. This is a6.4 to 1 ratio between the memory used for IDX buffers and actual BER data. Even forindefinite lengths, the same length insertion process is used. The IDX buffers' data areChapter 6. Results and Evaluation^ 100Figure 6.12: CASN1 local representation for the PersonnelRecord ValueChapter 6. Results and Evaluation^ 101^1^1^1^4^1^r r^rT^L^T^L^T^L John^1^1^1^14Smith^T^L^T^L The Big Chee se^1^1^1^8^1r^vT^L 99999^L^T^L 19820104 T^L^1^1^1T^L^T^L^Mary^T^L^L^T^1^1^11L^Smith^T^L^T^L^T^L^1^1^1^1^5rL^James^L^R^T^L^Smith^T^1^1^1r19570210 T^L^T^L^T1^1^5r^rLisa^T^L^M^T^L Smith^TT = encoded tagL = encoded lengthL^19590621Figure 6.13: CASN1's IDX buffer structure for the PersonnelRecord ValueChapter 6. Results and Evaluation^ 102serialized (copied) into a single buffer for transmission.CASN1 decoding is very similar to snacc decoding except tags can be decoded morethan once. When decoding the elements of a SET, the SET decoder peeks ahead inthe buffer and decodes the next tag to determine which element to decode. When theelement decoding routine is called, the tag is decoded again. Tags may also be decodedmore than once when decoding OPTIONAL elements of a SEQUENCE. When dealingwith simple type definitions, such as Foo : := Bar, CASN1 generates routines for theFoo type that simply call the Bar type's routines. This introduces unnecessary functioncalls for encoding and decoding Foo when they could easily be avoided by calling the Bartype's routines directly.Decoders produced with CASN1 have the drawback of requiring the PDU to be de-coded to be in a contiguous buffer and no range checking is done by the decoding routines.Thus, a malformed BER PDU can cause a segmentation fault (e.g. too long a length ona primitive data value).For allocating space for decoded values, a nibble memory scheme with range checkingwas used when benchmarking the CASN1 decoder.RpcgenThe rpcgen/XDR version of the PersonnelRecord is shown in Figure 6.14. Note thatthis definition contains much more information than the ASN.1 version with respect tothe local representation's format. The XDR local representation for the PersonnelRecordvalue is shown in Figure 6.15. Its simplicity reduces the allocation needs of the decoder.For each type, rpcgen produces a single XDR routine that handles encoding, decodingand freeing. The generated routines take an "XDR" type argument that is similar toISODE's Presentation Stream type, except that it includes the operation: encode, decodeor free. The XDR routine for each type checks the "XDR" type to determine whether toChapter 6. Results and Evaluation^ 103typedef string IA5String<>;typedef IA5String Date;typedef int EmployeeNumber;struct Name{IA5String givenName;IA5String initial;IA5String familyName;} ;struct Childlnformation{Name namel;Date dateOfBirth;1 ;struct PersonnelRecord{Name^namel;IA5String^title;EmployeeNumber employeeNumber3;Date^dateOfHire;Name nameOfSpouse;Childlnformation children<>; /* var-sized array */1 ;Figure 6.14: XDR PersonnelRecord DefinitionChapter 6. Results and Evaluation^ 104Figure 6.15: XDR's local representation for the PersonnelRecord ValueChapter 6. Results and Evaluation^ 105encode, decode or free.The xdrinem buffer type, a simple contiguous block, was used for the benchmarks. Webenchmarked XDR with its default memory scheme where the decoded value is allocatedusing malloc and free using a hierarchical free. By replacing the memory managementwith nibble memory, the XDR decoding time improves by a factor of two.NIDLThe NIDL version of the PersonnelRecord is shown in Figure 6.17. As with the XDRversion, it contains much more information about the local representation's format.The NIDL local representation for the PersonnelRecord is shown in Figure 6.16. Theuse of fixed-size strings makes the entire PersonnelRecord a fixed-size type. The fixed-size nature allows the NDR decoder to pre-allocate the entire PersonnelRecord; this isthe main reason that the NDR decoder performed so well.NDR encoders are a single routine that first calculates the encoded length of thegiven value and then encodes it into a buffer of appropriate size. NDR encoders encodethe data in the local host's format and include a format identifier so the receiving hostknows how to decode the data. Thus the decoding routine must choose the appropriatedecoding rules on the basis of format identifier. However, for this benchmark, the formatused in the PDU was the same as the decoder's internal format; this is the optimal casefor NDR decoders.SnaccSnacc generates "backwards" BER encoders [Steedman901. This allows snacc to trans-late directly from its local representation (see Figure 6.18) to the network format.Indefinite lengths are encoded by writing a special octet where the definite lengthnormally goes and writing an End-Of-Contents (EOC) marker after the content. TheChapter 6. Results and Evaluation^ 106Figure 6.16: NIDL's local representation for the PersonnelRecord ValueChapter 6. Results and Evaluation^ 107typedef stringO[128] IA5String; /* fixed-size locally */typedef IA5String Date;typedef int EmployeeNumber;typedef struct {IA5String givenName;IA5String initial;IA5String familyName;} Name;typedef struct {Name namel;Date dateOfBirth;} Childlnformation;typedef [handle] struct {Name namel;IA5String title;EmployeeNumber employeeNumber3;Date dateOfHire;Name nameOfSpouse;long lastIndex;Childlnformation [last_is(lastIndex)] children[];} PersonnelRecord;Figure 6.17: NIDL PersonnelRecord DefinitionChapter 6. Results and Evaluation^ 108Figure 6.18: Snacc's local representation for the PersonnelRecord ValueChapter 6. Results and Evaluation^ 109EOC is two zero octets. Indefinite lengths cannot be used on non-constructed valuesbecause the EOC may be indistinguishable from the value's data.Note that backwards encoding requires encoding the entire PDU before sending it,therefore stream-oriented communication, where parts of the PDU are sent as they areencoded, cannot be used effectively. Using the indefinite length option for constructedvalues exclusively eliminates the advantage of backwards encoders at the expense of aslightly larger encoded value (see the next section). Snacc can use both definite andindefinite lengths with similar performance.6.2 Primitive Type BenchmarksThe translation of the integer and real primitive types is very different in NDR, XDR,BER and PER. NDR and XDR used fixed-size representations, whereas BER and PERused variable-size representations. Simple string types do not typically involve muchtranslation unless different character sets are used. We tested the performance of theencoding rules for integer, real and string types to confirm these assumptions. We alsoinclude the cost of a memcpy of the same size as the encode array for each array to providea lower bound for performance.This benchmark is useful for evaluating encoding rules with respect to the typesused in an abstract syntax. For example, implementors of application protocols such asX.400 and X.500, whose PDUs are mostly structures and lists of strings, need not worryabout the integer or real type performance. However, writers of an application, such as adistributed spread-sheet, should be very concerned about the integer and real encodingand decoding performance.Chapter 6. Results and Evaluation^ 1106.2.1 Benchmark DesignTable 6.10 shows the benchmarks we performed on primitive types. In this test wewanted to avoid implementation issues, so each test used the same memory and buffermanagement. Only the actual code that performed the encoding and decoding of theprimitive type varied. This technique allows a more accurate gauge of the encoding rulesthemselves instead of just their implementation. In some cases (as indicated in Table6.10) the primitive type encoding and decoding routines were functions while in othercases they were placed "inline".No allocations or frees were done during the integer and real type benchmarks. Mallocand free were used during the string decoding benchmarks.For each set of encoding rules, the same buffer was overwritten for each encodingiteration. This buffer was then used for each decoding iteration. The same, randomly-generated integers and reals were used for all of the integer and real type benchmarks.As mentioned in the last section, there are certain conditions under which NDR andXDR operate optimally. In this section we look at both the optimal and non-optimalcases for the real and integer types. Since the non-optimal case of XDR affects both itsencoding and decoding, we used an extra XDR benchmark to represent both the XDRand NDR non-optimal case. NDR is always optimal for encoding.For the integer tests, we encoded and decoded one hundred random integers 10,000times. All of the integer tests used the same local representation for the integers, anarray of 100 long ints.All real values were internally represented by the double type. The real test wasconducted in the same manner with 100 random double precision real values.All strings were represented by a struct that contained a char* for the string and along int for the length of the string. The string benchmarks encoded and decoded anChapter 6. Results and Evaluation^ 111array containing 100 "Hello World" strings, 10,000 times. The content of the string didnot affect the encoding or decoding process in any of the cases. Each string benchmarkwas run as a separate program so the memory manager would be in the same state whenthe benchmarks started.We also tested a fixed-size string type for PER (Benchmark 2.16 in Table 6.10). Theperformance of the other encoding rules for this will be the same as for the unconstrainedOCTET STRING, however, PER can eliminate the length encoding for the string sinceit is a fixed-size. The benchmark for this type uses the same array value and number ofiterations as the other string benchmarks.For each array that was encoded, we benchmarked the cost of doing a memcpy of thesame size as the encoded array, 10,000 times. This provides a lower bound for bothencoding and decoding cost. Conceivably, encoding rules such as C based encoding rulescould be used to eliminate the need for any copying (i.e. the local representation is notcopied but modified in place).BER primitive values consist of the type's (UNIVERSAL) tag, length and content.PER primitive type encodings are just the length and content except in special fixed-sizecases where they consist solely of the content. The XDR and NDR integer and real typeswere four and eight bytes long, respectively. The XDR string encodings are precededby a four byte length determinant. NDR strings are encoded similarly except the lengthdeterminant is only two bytes. XDR requires all components to be aligned to four byteboundaries. NDR allows 2, 4 or 8 byte alignment depending on the type.The indefinite length form was used when encoding the BER SEQUENCE OF values.6.2.2 Benchmark ResultsFor the integer array, the optimal XDR and NDR cases are almost five times fasterthan the PER and BER versions. However, if XDR is used on a little endian host, theChapter 6. Results and Evaluation^ 112benchmark id encoding rules description2.01 NDR integer, optimal case, inlineint intArray [100]2.02 XDR integer, optimal case, inlineint intArray [100]2.03 XDR integer, big to little endian conversion, inlineint intArray [100]2.04 BER integer, inlineSEQUENCE (SIZE 100) OF INTEGER2.05 BER integer, fcn callSEQUENCE (SIZE 100) OF INTEGER2.06 PER92 integer, inlineSEQUENCE (SIZE 100) OF INTEGER2.07 NDR real, optimal case, inlinedouble realArray [100]2.08 XDR real, optimal case, inlinedouble realArray [100]2.09 XDR real, translating as if on a Vax, fcn calldouble realArray [100]2.10 BER real, fcn callSEQUENCE (SIZE 100) OF REAL2.11 PER92 real, fcn callSEQUENCE (SIZE 100) OF REAL2.12 NDR string, inlinestring() strArray [100]2.13 XDR string, inlinestring strArray [100]2.14 BER string, inlineSEQUENCE (SIZE 100) OF OCTET STRING2.15 PER92 string, inlineSEQUENCE (SIZE 100) OF OCTET STRING2.16 PER92 fixed size string, inlineSEQUENCE (SIZE 100) OF OCTET STRING (SIZE 11)Table 6.10: Primitive type benchmark definitionsChapter 6. Results and Evaluation^ 113benchmarkidencodingtime (s)decodingtime (s)copytime (s)encodedsize (bytes)2.01 0.62 0.61 0.14 4002.02 0.62 0.61 0.14 4002.03 1.30 1.32 0.14 4002.04 2.86 2.99 0.22 6032.05 3.09 2.71 0.22 6032.06 2.46 2.74 0.18 499Table 6.11: Results for integerbenchmarkidencodingtime (s)decodingtime (s)copytime (s)encodedsize (bytes)2.07 1.12 0.84 0.27 8002.08 1.12 0.84 0.27 8002.09 6.24 4.27 0.26 8002.10 9.36 34.30 0.41 12042.11 8.58 34.11 0.37 1100Table 6.12: Results for realbenchmarkidencodingtime (s)decodingtime (s)copytime (s)encodedsize (bytes)2.12 4.28 6.05 0.52 14002.13 3.89 7.20 0.52 16002.14 3.53 6.95 0.44 13042.15 2.92 6.59 0.40 12002.16 2.54 5.81 0.37 1100Table 6.13: Results for stringChapter 6. Results and Evaluation^ 114costs double due to the conversion between big and little endian format. This impliesthat NDR decoding time will double when the receiver's architecture has the opposite"endian-ness" from the sender.Due to the elimination of tags, the PER integer encoding is one byte smaller forevery integer encoded than the BER encoding. PER also eliminates the tag and lengthon the fixed-size SEQUENCE OF type. The BER and PER integer encodings are largerthan the XDR and NDR versions. This is mostly due to the random number generatorchoosing the more common four byte values. For applications that use integers closer tozero, the BER and PER encodings may be smaller than the NDR or XDR ones.The function call overhead difference between Benchmarks 2.04 and 2.05 did notappear to have much affect. In the encoding case, the function call overhead slowed itsomewhat but in the decoding case it was actually faster. The integer and real encodersand decoders for the optimal NDR and XDR cases were very small (2 lines of C) and usedno temporary variables; this simplified inlining them. The other encoding and decodingroutines were more complex and larger, especially in the case of the BER and PER realroutines.The BER and PER real encoders and decoders are much slower than the XDR andNDR implementations. The optimal NDR and XDR encoders and decoders simply copythe eight byte double value to encode it. Benchmark 2.09 shows that an extra cost isincurred if the local real representation is not IEEE format (Vax Gloating in this case).BER and PER real types performed poorly in all respects compared to the XDRand NDR versions. The most expensive operation is BER and PER real decoding. Theirperformance is over 40 times worse than the XDR and NDR decoders. This can be tracedto the use of floating point operations (pow from UNIX C math library). The encoderswere 9 times slower than the XDR and NDR ones. The BER and PER real encodingroutines are not as bad as their decoding routines in performance because they assumedChapter 6. Results and Evaluation^ 115that their host used the IEEE double format. Thus, they did not need to do floatingpoint operations to encode.The size of the BER and PER encodings were 1.4 to 1.5 times larger than the XDRand NDR versions. BER and PER would vastly improve their performance for realnumbers if they used the IEEE double representation for reals.The NDR strings are smaller than XDR due to their small, but more limiting, lengthdeterminant. NDR strings include a null-terminator character unlike XDR, however itdid not affect the value we tested (XDR inserted one padding byte).The PER and BER strings are smaller than the XDR and NDR ones because thelength determinant is encoded in the minimum number of bytes and no alignment isrequired. The PER encoding and decoding of the fixed-size OCTET STRING was fasterand smaller than the others due to the elimination of the string's length determinant.6.3 Benchmark of Implementation Features6.3.1 Benchmark DesignIn this section we look at the implementation issues and costs for memory and buffermanagement as well as the cost of definite versus indefinite lengths in BER. We use boththe PersonnelRecord value from Section 6.1 and an X.500 ListResult value.To observe the impact on performance, two buffer management schemes are used withsnacc encoders and decoders. The first scheme uses one fixed-size block for reading andwriting. Two variations of this were benchmarked, one that does range checking andone that does not. Range checking (checking for buffer overrun on reads and writes) isessential for preventing segmentation faults when decoding an improperly encoded value.The second buffer scheme uses linked buffers consisting of two separate parts, a bufferindex portion and a data portion. The index part has pointers to the data block and theChapter 6. Results and Evaluation^ 116next index part (if any) along with some additional information. Data blocks containonly data and are allocated from a fixed-size pool of free blocks. The index parts areallocated from another pool of index-sized blocks.Decoders can do many allocations when building the local value while decoding sothree memory allocation schemes were tested. The first method "nibbles" chunks froma fixed-size block, allowing the entire decoded value to be freed by resetting a pointer.Two variants of the nibble memory allocation scheme were tested; one that checks forallocations past the end of the block and one that does not. The second method is likethe first except that more blocks for nibbling can be allocated as needed (range checkingis required for this feature). The third scheme uses malloc with "hierarchical" freeing.Hierarchical freeing means that the data structure is freed by traversing it with freeingroutines specific to that data structure.An interesting memory management scheme that was not tested is using memoryprotection and mapping in paged memory systems. A sequence of contiguously mappedpages are used for a nibble block, with the last page being protected. A protection faultto this page would result in the allocation and mapping of more pages onto the end of thenibble block. This scheme could be used for buffers as well, where protection faults fromwrites allocate more pages or return an end-of-data indicator for reads. This method hastwo benefits: range checking overhead can be eliminated and contiguous data is easier toprocess.We also measured the performance improvement that can be achieved from usingmacros instead of functions calls for memory allocation and buffer reads (decoding) andwrites (encoding).6.3.2 Benchmark ResultsChapter 6. Results and Evaluation^ 117benchmark id encoding rules description3.01 BER minimal snacc encoder and decoder.Reference implementation.3.02 BER same as 3.01 except indefinite length formused where possible.3.03 BER same as 3.01 except range checking is done forbuffer reads and writes.3.04 BER same as 3.01 except range checking is done formemory allocations (decoding only).3.05 BER same as 3.01 except uses linked buffer scheme.3.06 BER same as 3.01 except nibble memory pool can growwith demand (decoding only).3.07 BER same as 3.01 except buffer reads/writes and memoryallocations are macros.3.08 BER same as 3.01 except memory management usesmalloc and hierarchical free.Table 6.14: Benchmarks of BER implementation featuresbenchmarkidencodingtime (s)decodingtime (s)encodedsize (bytes)3.01 114.70 230.64 1433.02 124.60 267.19 1683.03 141.48 256.96 1433.04 114.69 230.42 1433.05 163.36 272.93 1433.06 114.66 238.96 1433.07 84.50 171.29 1433.08 116.26 303.93 143Table 6.15: Results for encoding and decoding the PersonnelRecord 1 million timesChapter 6. Results and Evaluation^ 118benchmarkidencodingtime (s)decodingtime (s)encodedsize (bytes)3.01 46.41 88.26 50743.02 44.17 95.48 61523.03 46.60 100.46 50743.04 47.60 90.37 50743.05 61.30 146.30 50743.06 38.26 130.86 50743.07 31.16 69.77 5074Table 6.16: Results for encoding and decoding an X.500 ListResult 10,000 timesBenchmarks 3.01 to 3.08 measure the costs of adding various features to snacc gen-erated encoders and decoders. Using indefinite lengths (where possible) when encodingwas 9% more expensive for the PersonnelRecord yet 5% cheaper for the ListResult. De-coding was, respectively, 16% and 8% more expensive. The sizes of the indefinite lengthencodings were 17% larger for the PersonnelRecord and 21% larger for the ListResult.Benchmarks 3.01 and 3.03 show that range checking on buffer writes can increasethe encoding time by up to 23%. Range checking for buffer reads can add 11 to 14% tothe decoding time. Benchmarks 3.01 and 3.05 show that using a linked buffer scheme(requires range checking) that can expand as necessary, can add 32 to 42% to the encodingtime and 18 to 65% to the decoding time. The performance cost of the range checkingwill increase as the number of writes and reads increases. For example, range checkingwill be more of an issue when doing 100 one byte buffer writes than when doing one100 byte buffer write. If the encoding rules, abstract syntax or protocol permit, it isadvantageous to do a simple length calculation before encoding so that the actual size ofthe send buffer can be determined. This allows a much simpler buffering scheme such asa single buffer with no range checking on writes to be used.Using macros for the buffer reading and writing and memory allocation caused theChapter 6. Results and Evaluation^ 119datastructurebenchmarkid% time encoderuses forbuffer writes% time decoderuses forbuffer reads% time decoderuses formemory mgmt.PersonnelRecordPersonnelRecordX.500 ListResult3.013.083.0147473625191882811Table 6.17: Overall cost of buffer and memory management for snacc's BER and PERencoders and decodersmost significant speed up (21-33%), without a huge increase in the compiled size. How-ever, the compiled size of our implementations increased dramatically if the primitivetype encoding and decoding routines were macros.An anomaly appears in Benchmark 3.06 of the ListResult (see Table 6.16). Theencoding time should not be different from that of Benchmark 3.01 since the only differ-ence between them is the allocation scheme for decoding. The difference was traced to acompiler optimization that was possible in Benchmark 3.06 but not Benchmark 3.01.Using a malloc-like memory allocator with a hierarchical free instead of the simplernibble scheme caused a 32% increase in decoding time. An environment which permitsdecoding into a single buffer or set of buffers that can be freed in one operation willsignificantly improve the performance. Such a scheme is provided in the programmingenvironment used in implementing the EAN X.500 system [Neufeld92-2]. Snacc providessupport for this type of memory management in its runtime library.6.4 Execution AnalysisWe used "pixie" [PIX90] basic block profiling to determine the component costs ofsnacc's encoders and decoders (see Table 6.17). The results showed that snacc's BERencoder, using an extremely simple buffer format (contiguous block, no range checking),can spend almost half of their CPU cycles simply writing to the buffer. With the sameChapter 6. Results and Evaluation^ 120buffer format, decoders spent up to 28% of their time just reading from the buffer.Decoders using simple nibble allocation used from 8% to 10% of their time in memorymanagement; however, using a malloc and hierarchical free memory system insteadpushes the cost to 28%.Buffer and memory management accounted for less of the X.500 ListResult's encoder'sand decoder's processing time than those of the PersonnelRecord. This seems to indicatethat as the abstract syntax for a type becomes more complex, the cost of traversing(encoding) or assembling (decoding) the local representation value increases. The pixieprofiling also indicated that only about 20% to 40% of the encoding and decoding timewas spent in the routines generated by the compiler for the abstract syntax. The restwas spent in the library routines for the primitive types which in turn called the bufferand memory routines.Chapter 7ConclusionsOur study revealed that the majority of encoding and decoding time is spent in thefollowing areas:• writing to the send buffer during encoding• reading from a receive buffer when decoding• memory allocation for the decoded value's data structure• freeing the decoded data structureEach of these areas is examined to determine how they can be improved. However,even after optimization, these areas still consume a significant portion of the processortime during encoding and decoding.The results of the analysis indicate that the majority of time is being spent in primitivetype encoding and decoding routines (which contain most of the calls to the buffer andmemory routines) rather than the routines generated by the compilers. It is clear fromthese results that efficient encoders and decoders must be tuned to work well with thebuffer structure and memory model being used. Even highly tuned encoding rules suchas PER92 only achieved about 12 Mbps on a MIPS R3260. Either faster processors andmemory or faster encoding and decoding techniques are necessary for the presentationlayer to keep up with the potential rate at which data can arrive on today's high speed121Chapter 7. Conclusions^ 122networks. Our results suggest several design rules that can aid in the development ofefficient encoders and decoders:• Avoid intermediate representations such as IDX buffers between the local represen-tation and the fully encoded representation.• Choose the simplest buffer management system that your encoding rules and envi-ronment will allow. Using "inline" procedures or macros is a significant advantage.• Choose a memory allocation/free model that supports cheap allocations and frees.Avoid hierarchical freeing if possible.• Design local data structures that minimize the number of allocations by eliminatingunnecessary pointers.• Use a simple pre-encoding length calculation if the abstract syntax, protocol orencoding rules permit, to simplify buffer management for encoders.For the PersonnelRecord data structure, PER92 is better than BER in performanceand compression. However, the extent of the improvement greatly depends on the ab-stract syntax of the values being processed. Abstract syntaxes that use subtyping mayallow PER92 to produce smaller encodings possibly at the cost of encoding and decodingspeed.One-pass forward PER92 encoders can be implemented; this allows performance andstreaming to transport connections. Finally, both BER and PER encoders and decodersperformed well in comparison to XDR and NDR encoders and decoders. However, theBER and PER performance will decrease as the data becomes more numerically oriented.The snacc tool generates useful, efficient implementations. Obvious future develop-ment would include handling the new language features of ASN.1 '92 and supportingChapter 7. Conclusions^ 123different encoding rules such as PER, XDR, and possibly C based encoding rules (usefulwhen archiving to disk). The snacc generated type tables need to be improved such thatthey contain subtyping information; subtyping information is necessary for PER encodersand decoders.In general, the maximum throughput of encoding rules is limited by the lower boundof a simple memory copy of the PDU. In certain, limited cases, such as C based encodingrules, this can be improved upon by encoding in place.Future research on the performance of encoding rules is necessary. Perhaps parallelismcan be used to improve their throughput. C based encoding rules demonstrated that ifcertain assumptions can be made, a large performance increase can be had. For example,if hardware producers could use a common machine data representation standard thenthis type of performance improvement could be made. The translation of primitive types,which can be expensive (e.g. BER real values), would not be necessary.Support for commonly used data structure features, such as multiple references tothe same value and even cyclic references, should be examined. Perhaps ASN.1 can beextended with new language features and encoding rules to support this.Appendix AC ExampleThis appendix contains an example of the C code snacc will generate for an ASN.1data structure. Snacc generated two files for the following PersonnelRecord ASN.1 datastructure, p_rec.c and p_rec.h.124Appendix A. C Example^ 125P-REC DEFINITIONS ::=BEGINPersonnelRecord ::= --snacc isPdu:"TRUE" -- [APPLICATION 0] IMPLICIT SET{Name,title^[0] IA5String,EmployeeNumber,dateOfHire^[1] Date,nameOfSpouse [2] Name,children^[3] IMPLICIT SEQUENCE OF Childlnformation DEFAULT {}Childlnformation ::= SET{Name,dateOfBirth [0] DateName ::= [APPLICATION 1] IMPLICIT SEQUENCE{givenName IA5String,initial IA5String,familyName IA5String}EmployeeNumber ::= [APPLICATION 2] IMPLICIT INTEGERDate ::= [APPLICATION 3] IMPLICIT IA5String^YYYYMMDDENDFigure A.19: PersonnelRecord ASN.1 data structureAppendix A. C Example^ 126Snacc generated C file p_rec.hAppendix A. C Example^ 127/*• p_rec.h*• "P-REC" ASN.1 module C type definitions and prototypes*• This .h file was by snacc on Sun Apr 11 02:17:21 1993*• UBC snacc written compiler by Mike Sample*• NOTE: This is a machine generated file - editing not recommended*/#ifndef _p_rec_h_#define _p_rec_h_typedef Asnlnt EmployeeNumber; /* [APPLICATION 2] IMPLICIT INTEGER */#define BEncEmployeeNumberContent BEncAsnlntContent#define BDecEmployeeNumberContent BDecAsnlntContent#define PrintEmployeeNumber PrintAsnlnt#define FreeEmployeeNumber FreeAsnlnttypedef struct Name /* [APPLICATION 1] IMPLICIT SEQUENCE */{IA5String givenName; /* IA5String */IA5String initial; /* IA5String */IA5String familyName; /* IA5String */} Name;AsnLen BEncNameContent PROTO((BUF_TYPE b, Name* v));void BDecNameContent PROTO(( BUF_TYPE b, AsnTag tagIdO, AsnLen elmtLen0,Name* v, AsnLen* bytesDecoded, ENV_TYPE env));void PrintName PROTO((FILE* f, Name* v, unsigned short int indent));void FreeName PROTO((Name* v));typedef IA5String Date; /* [APPLICATION 3] IMPLICIT IA5String */#define BEncDateContent BEncIA5StringContent#define BDecDateContent BDecIA5StringContent#define PrintDate PrintlA5StringAppendix A. C Example^ 128#define FreeDate FreeIA5Stringtypedef struct Childlnformation /* SET */{struct Name* name; /* Name */Date dateOfBirth; /* [0] Date */Childlnformation;AsnLen BEncChildInformationContent PROTO((BUF_TYPE b, Childlnformation* v));void BDecChildlnformationContent PROTO(( BUF_TYPE b, AsnTag tagIdO,AsnLen elmtLenO, Childlnformation* v, AsnLen* bytesDecoded, ENV_TYPE env));void PrintChildlnformation PROTO((FILE* f, Childlnformation* v,unsigned short int indent));void FreeChildInformation PROTO((Childlnformation* v));typedef AsnList PersonnelRecordSeq0f; /* SEQUENCE OF Childlnformation */AsnLen BEncPersonnelRecordSeq0fContent PROTO((BUF_TYPE b,PersonnelRecordSeq0f* v));void BDecPersonnelRecordSeq0fContent PROTO(( BUF_TYPE b, AsnTag tagIdO,AsnLen elmtLenO, PersonnelRecordSeq0f* v, AsnLen* bytesDecoded, ENV_TYPE env));void PrintPersonnelRecordSeq0f PROTO((FILE* f, PersonnelRecordSeq0f* v,unsigned short int indent));void FreePersonnelRecordSeq0f PROTO((PersonnelRecordSeq0f* v));typedef struct PersonnelRecord /* [APPLICATION 0] IMPLICIT SET */{struct Name* name; /* Name */IA5String title; /* [0] IA5String */EmployeeNumber employeeNumber; /* EmployeeNumber */Date dateOfHire; /* [1] Date */struct Name* nameOfSpouse; /* [2] Name */PersonnelRecordSeq0f* children;/* [3] IMPLICIT PersonnelRecordSeq0f DEFAULTsnacc warning: can't parse this value yet --{^*/PersonnelRecord;AsnLen BEncPersonnelRecord PROTO((BUF_TYPE b, PersonnelRecord* v));void BDecPersonnelRecord PROTO(( BUF_TYPE b, PersonnelRecord* result,Appendix A. C Example^ 129AsnLen* bytesDecoded, ENV_TYPE env));AsnLen BEncPersonnelRecordContent PROTO((BUF_TYPE b, PersonnelRecord* v));void BDecPersonnelRecordContent PROTO(( BUF_TYPE b, AsnTag tagIdO,AsnLen elmtLenO, PersonnelRecord* v, AsnLen* bytesDecoded, ENV_TYPE env));void PrintPersonnelRecord PROTO((FILE* f, PersonnelRecord* v,unsigned short int indent));void FreePersonnelRecord PROTO((PersonnelRecord* v));#endif /* conditional include of p_rec.h */Appendix A. C Example^ 130Snacc generated C file p_rec.cAppendix A. C Example^ 131/** p_rec.c** "P-REC" ASN.1 module encode/decode/print/free C src.** This file was generated by snacc on Sun Apr 11 02:17:21 1993** UBC snacc written by Mike Sample** NOTE: This is a machine generated file - editing not recommended*/#include "asn_incl.h"#include "p_rec.h"AsnLenBEncNameContent PARAMS((b, v),BUF_TYPE b _AND_Name* v){AsnLen totalLen = 0;AsnLen itemLen;AsnLen listLen;void* component;itemLen = BEncIA5StringContent( b, (&v->familyName));itemLen += BEncDefLen( b, itemLen);itemLen += BEncTagl(b, UNIV, PRIM, 22);totalLen += itemLen;itemLen = BEncIA5StringContent( b, (&v->initial));itemLen += BEncDefLen( b, itemLen);itemLen += BEncTagl(b, UNIV, PRIM, 22);totalLen += itemLen;itemLen = BEncIA5StringContent( b, (&v->givenName));itemLen += BEncDefLen( b, itemLen);itemLen += BEncTagl(b, UNIV, PRIM, 22);Appendix A. C Example^ 132totalLen += itemLen;return (totalLen);} /* BEncNameContent */voidBDecNameContent PARAMS((b, tagIdO, elmtLenO, v, bytesDecoded, env),BUF_TYPE b _AND_AsnTag tagId0 _AND_AsnLen elmtLenO _AND_Name* v ANDAsnLen* bytesDecoded _AND_ENV_TYPE env){int seciDone = FALSE;AsnLen totalElmtsLen1 = 0;AsnLen elmtLenl;AsnTag tagldi;int mandatoryElmtCountl = 0;tagldi = BDecTag(b, &totalElmtsLenl, env);if ((( tagldi == MAKE_TAG_ID( UNIV, PRIM, IA5STRING_TAG_CODE)) II( tagldi == MAKE_TAG_ID( UNIV, CONS, IA5STRING_TAG_CODE)))){elmtLenl = BDecLen (b, &totalElmtsLenl, env);BDecIA5StringContent( b, tagId1, elmtLenl, (&v->givenName),&totalElmtsLenl, env);tagldi = BDecTag(b, &totalElmtsLenl, env);}elselongjmp(env, -100);if ((( tagldi == MAKE_TAG_ID( UNIV, PRIM, IA5STRING_TAG_CODE)) II( tagldi == MAKE_TAG_ID( UNIV, CONS, IA5STRING_TAG_CODE)))){elmtLenl = BDecLen (b, &totalElmtsLenl, env);BDecIA5StringContent( b, tagId1, elmtLenl, (&v->initial),Appendix A. C Example^ 133&totalElmtsLenl, env);tagIdl = BDecTag(b, &totalElmtsLenl, env);}elselongjmp(env, -101);if ((( tagId1 == MAKE_TAG_ID( UNIV, PRIM, IA5STRING_TAG_CODE)) II( tagId1 == MAKE_TAG_ID( UNIV, CONS, IA5STRING_TAG_CODE)))){elmtLenl = BDecLen (b, &totalElmtsLenl, env);BDecIA5StringContent( b, tagIdl, elmtLenl, (&v->familyName),&totalElmtsLenl, env);sepone = TRUE;if ( elmtLen0 == INDEFINITE_LEN )BDecEoc(b, &totalElmtsLenl, env);else if (totalElmtsLenl != elmtLen0)longjmp(env, -102);}elselongjmp(env, -103);if (!segDone)longjmp(env, - 104);(*bytesDecoded) += totalElmtsLenl;} /* BDecNameContent */voidPrintName PARAMS((f, v, indent),FILE* f _AND_Name* v ANDunsigned short int indent){if (v == NULL)return;fprintf(f,"{ -- SEQUENCE --\n");Indent(f, indent + stdIndentG);Appendix A. C Example^ 134fprintf(f,"givenName ");PrintlA5String(f, (&v->givenName), indent + stdIndentG);fprintf(f, ",\n");Indent(f, indent + stdlndentG);fprintf(f,"initial ");PrintlA5String(f, (&v->initial), indent + stdlndentG);fprintf(f, ",\n");Indent(f, indent + stdlndentG);fprintf(f,"familyName ");PrintlA5String(f, (&v->familyName), indent + stdlndentG);fprintf(f,"\n");Indent(f, indent);fprintf(f,"}");/* PrintName */voidFreeName PARAMS((v),Name* v){if (v == NULL)return;FreeIA5String((&v->givenName));FreeIA5String((&v->initial));FreeIA5String((&v->familyName));} /* FreeName */AsnLenBEncChildlnformationContent PARAMS((b, v),BUF_TYPE b _AND_ChildInformation* v){AsnLen totalLen = 0;AsnLen itemLen;AsnLen listLen;void* component;Appendix A. C Example^ 135BEncEoclfNec(b);itemLen = BEncDateContent( b, (&v->dateOfBirth));itemLen += BEncDefLen( b, itemLen);itemLen += BEncTagl(b, APPL, PRIM, 3);itemLen += BEncConsLen( b, itemLen);itemLen += BEncTagl(b, CNTX, CONS, 0);totalLen += itemLen;BEncEoclfNec(b);itemLen = BEncNameContent( b, (v->name));itemLen += BEncConsLen( b, itemLen);itemLen += BEncTagl(b, APPL, CONS, 1);totalLen += itemLen;return (totalLen);} /* BEncChildlnformationContent */voidBDecChildlnformationContent PARAMS((b, tagldO, elmtLenO, v, bytesDecoded, env),BUF_TYPE b _AND_AsnTag tagId0 _AND_AsnLen elmtLenO _AND_Childlnformation* v ANDAsnLen* bytesDecoded _AND_ENV_TYPE env){int sepone = FALSE;AsnLen totalElmtsLenl = 0;AsnLen elmtLenl;AsnTag tagIdl;int mandatoryElmtCountl = 0;AsnLen totalElmtsLen2 = 0;AsnLen elmtLen2;AsnTag tagld2;for ( ; (totalElmtsLenl < elmtLen0) 11 (elmtLen0 == INDEFINITE_LEN);)Appendix A. C Example^ 136{tagIdl = BDecTag(b, &totalElmtsLenl, env);if ( (tagIdl == EOC_TAG_ID) && (elmtLen0 == INDEFINITE_LEN)){BDEC_2ND_EOC_OCTET(b, &totalElmtsLenl, env)break; /* got EOC so can exit this SET's for loop*/}elmtLenl = BDecLen (b, &totalElmtsLenl, env);switch(tagIdl){case(MAKE_TAG_ID( APPL, CONS, 1)):(v->name) = (Name*) Asn1Alloc(sizeof(Name));CheckAsn1Alloc((v->name), env);BDecNameContent( b, tagIdl, elmtLenl, (v->name), &totalElmtsLenl, env);mandatoryElmtCountl++;break;case(MAKE_TAG_ID( CNTX, CONS, 0)):tagId2 = BDecTag(b, &totalElmtsLenl, env);if ((tagId2 != MAKE_TAG_ID( APPL, PRIM, 3)) &&(tagId2 != MAKE_TAG_ID( APPL, CONS, 3))){AsnlError("Unexpected Tag\n");longjmp(env, -106);elmtLen2 = BDecLen (b, &totalElmtsLenl, env);BDecDateContent( b, tagId2, elmtLen2, (&v->dateOfBirth),&totalElmtsLenl, env);if (elmtLenl == INDEFINITE_LEN)BDecEoc(b, &totalElmtsLenl, env);mandatoryElmtCount1++;break;default:AsnlError("BDecChildlnformationContent: ERROR - Unexpected tag\in SET\n");longjmp(env, -107);break;} /* end switch */Appendix A. C Example^ 137/* end for */if (mandatoryElmtCount1 != 2){AsnlError("BDecChildlnformationContent: ERROR - non-optional elmt\missing from SET\n");longjmp(env, -108);}(*bytesDecoded) += totalElmtsLenl;/* BDecChildInformationContent */voidPrintChildlnformation PARAMS((f, v, indent),FILE* f _AND_Childlnformation* v _AND_unsigned short int indent)if (v == NULL)return;fprintf(f,"{ -- SET --\n");Indent(f, indent + stdIndentG);PrintName(f, (v->name), indent + stdIndentG);fprintf(f, ",\n");Indent(f, indent + stdIndentG);fprintf(f,"dateOfBirth ");PrintDate(f, (&v->dateOfBirth), indent + stdIndentG);fprintf(f,"\n");Indent(f, indent);fprintf(f,"}");} /* PrintChildInformation */voidFreeChildInformation PARAMS((v),Childlnformation* v){if (v == NULL)return;FreeName((v->name));Asn1Free((v->name));Appendix A. C Example^ 138FreeDate((&v->dateOfBirth));} /* FreeChildInformation */AsnLenBEncPersonnelRecordSeq0fContent PARAMS((b, v),BUF_TYPE b _AND_PersonnelRecordSeq0f* v){AsnLen totalLen = 0;AsnLen itemLen;AsnLen listLen;void* component;listLen = 0;FOR_EACH_LIST_ELMT_RVS( component, v){BEncEoclfNec(b);itemLen = BEncChildlnformationContent( b, component);itemLen += BEncConsLen( b, itemLen);itemLen += BEncTagl(b, UNIV, CONS, 17);listLen += itemLen;}return (listLen);} /* BEncPersonnelRecordSeq0fContent */voidBDecPersonnelRecordSeq0fContent PARAMS((b, tagldO, elmtLen0, v,bytesDecoded, env),BUF_TYPE b _AND_AsnTag tagId0 _AND_AsnLen elmtLen0 _AND_PersonnelRecordSeq0f* v _AND_AsnLen* bytesDecoded _AND_ENV_TYPE env)Appendix A. C Example^ 139int seqDone = FALSE;AsnLen totalElmtsLenl = 0;AsnLen elmtLenl;AsnTag tagIdl;int mandatoryElmtCountl = 0;for ( totalElmtsLenl = 0; (totalElmtsLenl < elmtLen0) II(elmtLen0 == INDEFINITE_LEN);){Childlnformation** tmpVar;tagIdl = BDecTag(b, &totalElmtsLenl, env);if ( (tagIdl == EOC_TAG_ID) && (elmtLen0 == INDEFINITE_LEN)){BDEC_2ND_EOC_OCTET(b, &totalElmtsLenl, env)break; /* got EOC so can exit this SET OF/SEQ OF's for loop*/}if ( (tagIdl == MAKE_TAG_ID( UNIV, CONS, SET_TAG_CODE))){elmtLenl = BDecLen (b, &totalElmtsLenl, env);tmpVar = (ChildInformation**) AsnListAppend(v);(*tmpVar) = (ChildInformation*) AsnlAlloc(sizeof(Childlnformation));CheckAsnlAlloc((*tmpVar), env);BDecChildlnformationContent( b, tagIdl, elmtLenl, (*tmpVar),&totalElmtsLenl, env);} /* end of tag check if */else /* wrong tag */{Asn1Error("Unexpected Tag\n");longjmp(env, -109);}} /* end of for */(*bytesDecoded) += totalElmtsLenl;} /* BDecPersonnelRecordSeq0fContent */voidPrintPersonnelRecordSeq0f PARAMS((f, v, indent),FILE* f _AND_Appendix A. C Example^ 140PersonnelRecordSeq0f* v _AND_unsigned short int indent){Childlnformation* tmp;if (v == NULL)return;fprintf(f,"{ -- SEQUENCE OF -- \n");FOR_EACH_LIST_ELMT(tmp, v){Indent(f, indent+ stdIndentG);PrintChildlnformation(f, tmp, indent + stdIndentG);if (tmp != (Childlnformation*)LAST_LIST_ELMT(v))fprintf(f,",\n");}fprintf(f,"\n");Indent(f, indent);fprintf(f,"}");} /* PrintPersonnelRecordSeq0f */voidFreePersonnelRecordSeq0f PARAMS((v),PersonnelRecordSeq0f* v){AsnListNode* 1;AsnListNode* tmp;if (v == NULL)return;for (1 = FIRST_LIST_NODE(v); 1 != NULL; ){FreeChildInformation((1->data));tmp = 1->next;AsnlFree(1->data);AsnlFree(1);1 = tmp;}} /* FreePersonnelRecordSeq0f */Appendix A. C Example^ 141AsnLen BEncPersonnelRecord PARAMS((b, v),BUF_TYPE b _AND_PersonnelRecord* v){AsnLen 1;BEncEoclfNec(b);1 = BEncPersonnelRecordContent(b, v);1 += BEncConsLen(b, 1);1 += BEncTagl(b, APPL, CONS, 0);return(1);} /* BEncPersonnelRecord */void BDecPersonnelRecord PARAMS((b, result, bytesDecoded, env),BUF_TYPE b _AND_PersonnelRecord* result ANDAsnLen* bytesDecoded _AND_ENV_TYPE env){AsnTag tag;AsnLen elmtLenl;if ( ((tag = BDecTag(b, bytesDecoded, env)) !=MAKE_TAG_ID(APPL, CONS, 0))){Asn1Error("BDecPersonnelRecord: ERROR - wrong tag\n");longjmp(env, -110);}elmtLenl = BDecLen(b, bytesDecoded, env);BDecPersonnelRecordContent(b, tag, elmtLenl, result, bytesDecoded, env);} /* BDecPersonnelRecord */AsnLenBEncPersonnelRecordContent PARAMS((b, v),BUF_TYPE b _AND_PersonnelRecord* v){AsnLen totalLen = 0;AsnLen itemLen;AsnLen listLen;void* component;Appendix A. C Example^ 142if (NOT_NULL((v->children))){BEncEoclfNec(b);itemLen = BEncPersonnelRecordSeq0fContent( b, (v->children));itemLen += BEncConsLen( b, itemLen);itemLen += BEncTagl(b, CNTX, CONS, 3);totalLen += itemLen;}BEncEoclfNec(b);BEncEoclfNec(b);itemLen = BEncNameContent( b, (v->nameOfSpouse));itemLen += BEncConsLen( b, itemLen);itemLen += BEncTagl(b, APPL, CONS, 1);itemLen += BEncConsLen( b, itemLen);itemLen += BEncTagl(b, CNTX, CONS, 2);totalLen += itemLen;BEncEoclfNec(b);itemLen = BEncDateContent( b, (&v->dateOfHire));itemLen += BEncDefLen( b, itemLen);itemLen += BEncTagl(b, APPL, PRIM, 3);itemLen += BEncConsLen( b, itemLen);itemLen += BEncTagl(b, CNTX, CONS, 1);totalLen += itemLen;itemLen = BEncEmployeeNumberContent( b, (&v->employeeNumber));BEncDefLenTo127( b, itemLen);itemLen++;itemLen += BEncTagl(b, APPL, PRIM, 2);totalLen += itemLen;BEncEoclfNec(b);itemLen = BEncIA5StringContent( b, (&v->title));itemLen += BEncDefLen( b, itemLen);itemLen += BEncTagl(b, UNIV, PRIM, 22);itemLen += BEncConsLen( b, itemLen);Appendix A. C Example^ 143itemLen += BEncTagl(b, CNTX, CONS, 0);totalLen += itemLen;BEncEoclfNec(b);itemLen = BEncNameContent( b, (v->name));itemLen += BEncConsLen( b, itemLen);itemLen += BEncTagl(b, APPL, CONS, 1);totalLen += itemLen;return (totalLen);/* BEncPersonnelRecordContent */voidBDecPersonnelRecordContent PARAMS((b, tagldO, elmtLenO, v, bytesDecoded, env),BUF_TYPE b _AND_AsnTag tagId0 _AND_AsnLen elmtLenO _AND_PersonnelRecord* v ANDAsnLen* bytesDecoded _AND_ENV_TYPE env){int sepone = FALSE;AsnLen totalElmtsLenl = 0;AsnLen elmtLenl;AsnTag tagId1;int mandatoryElmtCountl = 0;AsnLen totalElmtsLen2 = 0;AsnLen elmtLen2;AsnTag tagld2;for ( ; (totalElmtsLenl < elmtLen0) II (elmtLen0 == INDEFINITE_LEN);){tagId1 = BDecTag(b, &totalElmtsLenl, env);if ( (tagIdl == EOC_TAG_ID) && (elmtLen0 == INDEFINITE_LEN)){BDEC_2ND_EOC_OCTET(b, &totalElmtsLenl, env)Appendix A. C Example^ 144break; /* got EOC so can exit this SET's for loop*/}elmtLenl = BDecLen (b, &totalElmtsLenl, env);switch(tagldl){case(MAKE_TAG_ID( APPL, CONS, 1)):(v->name) = (Name*) Asn1Alloc(sizeof(Name));CheckAsnlAlloc((v->name), env);BDecNameContent( b, tagId1, elmtLenl, (v->name), &totalElmtsLenl, env);mandatoryElmtCountl++;break;case(MAKE_TAG_ID( CNTX, CONS, 0)):tagId2 = BDecTag(b, &totalElmtsLenl, env);if ((tagId2 != MAKE_TAG_ID( UNIV, PRIM, IA5STRING_TAG_CODE)) &&(tagId2 != MAKE_TAG_ID( UNIV, CONS, IA5STRING_TAG_CODE))){AsnlError("Unexpected Tag\n");longjmp(env, -111);elmtLen2 = BDecLen (b, &totalElmtsLenl, env);BDecIA5StringContent( b, tagId2, elmtLen2, (&v->title),&totalElmtsLenl, env);if (elmtLenl == INDEFINITE_LEN)BDecEoc(b, &totalElmtsLenl, env);mandatoryElmtCountl++;break;case(MAKE_TAG_ID( APPL, PRIM, 2)):BDecEmployeeNumberContent( b, tagId1, elmtLenl, (&v->employeeNumber),&totalElmtsLenl, env);mandatoryElmtCount1++;break;case(MAKE_TAG_ID( CNTX, CONS, 1)):tagId2 = BDecTag(b, &totalElmtsLenl, env);if ((tagId2 != MAKE_TAG_ID( APPL, PRIM, 3)) &&(tagId2 != MAKE_TAG_ID( APPL, CONS, 3))){AsnlError("Unexpected Tag\n");Appendix A. C Example^ 145longjmp(env, -112);elmtLen2 = BDecLen (b, &totalElmtsLenl, env);BDecDateContent( b, tagId2, elmtLen2, (&v->dateOfHire),&totalElmtsLenl, env);if (elmtLenl == INDEFINITE_LEN)BDecEoc(b, &totalElmtsLenl, env);mandatoryElmtCount1++;break;case(MAKE_TAG_ID( CNTX, CONS, 2)):if (BDecTag(b, &totalElmtsLenl, env) != MAKE_TAG_ID( APPL, CONS, 1)){AsnlError("Unexpected Tag\n");longjmp(env, -113);elmtLen2 = BDecLen (b, &totalElmtsLenl, env);(v->nameOfSpouse) = (Name*) AsnlAlloc(sizeof(Name));CheckAsnlAlloc((v->nameOfSpouse), env);BDecNameContent( b, tagId2, elmtLen2, (v->nameOfSpouse),&totalElmtsLenl, env);if (elmtLenl == INDEFINITE_LEN)BDecEoc(b, &totalElmtsLenl, env);mandatoryElmtCount1++;break;case(MAKE_TAG_ID( CNTX, CONS, 3)):(v->children) = AsnListNew(sizeof(char*));CheckAsn1Alloc((v->children), env);BDecPersonnelRecordSeq0fContent( b, tagIdl, elmtLenl, (v->children),&totalElmtsLenl, env);break;default:Asn1Error("BDecPersonnelRecordContent: ERROR - Unexpected tagin SET\n");longjmp(env, -114);break;/* end switch */Appendix A. C Example^ 146} /* end for */if (mandatoryElmtCountl != 5){AsnlError("BDecPersonnelRecordContent: ERROR - non-optional elmt\missing from SET\n");longjmp(env, -115);}(*bytesDecoded) += totalElmtsLenl;} /* BDecPersonnelRecordContent */voidPrintPersonnelRecord PARAMS((f, v, indent),FILE* f _AND_PersonnelRecord* v ANDunsigned short int indent){if (v == NULL)return;fprintf(f,"{ -- SET --\n");Indent(f, indent + stdIndentG);PrintName(f, (v->name), indent + stdIndentG);fprintf(f, ",\n");Indent(f, indent + stdIndentG);fprintf(f,"title ");PrintlA5String(f, (&v->title), indent + stdIndentG);fprintf(f, ",\n");Indent(f, indent + stdlndentG);PrintEmployeeNumber(f, (&v->employeeNumber), indent + stdlndentG);fprintf(f, ",\n");Indent(f, indent + stdlndentG);fprintf(f,"date0fHire ");PrintDate(f, (&v->date0fHire), indent + stdIndentG);fprintf(f, ",\n");Indent(f, indent + stdlndentG);fprintf(f,"nameOfSpouse ");PrintName(f, (v->nameOfSpouse), indent + stdlndentG);if ( NOT_NULL((v->children))){fprintf(f,",\h");Appendix A. C Example^ 147Indent(f, indent + stdIndentG);fprintf(f,"children ");PrintPersonnelRecordSeq0f(f, (v->children), indent + stdIndentG);}fprintf(f,"\n");Indent(f, indent);fprintf(f,"1");} /* PrintPersonnelRecord */voidFreePersonnelRecord PARAMS((v),PersonnelRecord* v){if (v == NULL)return;FreeName((v->name));AsnlFree((v->name));FreeIA5String((&v->title));FreeEmployeeNumber((&v->employeeNumber));FreeDate((&v->date0fHire));FreeName((v->nameOfSpouse));AsnlFree((v->nameOfSpouse));if ( NOT_NULL((v->children))){FreePersonnelRecordSeq0f((v->children));AsnlFree((v->children));}/* FreePersonnelRecord */Appendix BC++ ExampleThis appendix contains an example of the C++ code snacc will generate for an ASN.1data structure. Snacc generated two files for the PersonnelRecord ASN.1 data structure,prec.0 and prec.h.148Appendix B. C++ Example^ 149Snacc generated C++ file prec.hAppendix B. C++ Example^ 150//// p_rec.h - class definitions for ASN.1 module P-REC//// This file was generated by snacc on Sun Apr 11 03:17:42 1993// UBC snacc by Mike Sample// NOTE: this is a machine generated file - editing not recommended//#ifndef _p_rec_h_#define _p_rec_h_// forward declarationsclass EmployeeNumber;class Name;class Date;class Childlnformation;class PersonnelRecordSeq0f;class PersonnelRecord;/* [APPLICATION 2] IMPLICIT INTEGER */class EmployeeNumber : public Asnlnt{public:EmployeeNumber(): AsnInt() {}EmployeeNumber(int i): Asnlnt(i) {}AsnType* Clone() { return new EmployeeNumber; }AsnLen BEnc(BUF_TYPE b){AsnLen 1;1 = BEncContent(b);1 += BEncConsLen( b, 1);1 += BEncTagl(b, APPL, PRIM, 2);return(1);void BDec(BUF_TYPE b, AsnLen& bytesDecoded, ENV_TYPE env){AsnTag tag;AsnLen elmtLenl;Appendix B. C++ Example^ 151if ( ((tag = BDecTag(b, bytesDecoded, env)) !=MAKE_TAG_ID(APPL, PRIM, 2))){Asn1Error("EmployeeNumber::BDec: ERROR - wrong tag\n");longjmp(env, -100);}elmtLenl = BDecLen(b, bytesDecoded, env);BDecContent(b, tag, elmtLenl, bytesDecoded, env);int BEncPdu( BUF_TYPE b, AsnLen& bytesEncoded){bytesEncoded = BEnc(b);return(!b.WriteError());int BDecPdu( BUF_TYPE b, AsnLen& bytesDecoded){ENV_TYPE env;int val;bytesDecoded = 0;if ((val = setjmp(env)) == 0 ){BDec(b, bytesDecoded, env);return(!b.ReadError());}elsereturn(FALSE);};class Name : public AsnType{public:IA5String givenName;IA5String initial;IA5String familyName;Appendix B. C++ Example^ 152Name() {}void Print(ostream& os);AsnType* Clone() { return new Name; }AsnLen BEnc(BUF_TYPE b){AsnLen 1;1 = BEncContent(b);1 += BEncConsLen(b, 1);1 += BEncTagl(b, APPL, CONS, 1);return(1);void BDec(BUF_TYPE b, AsnLen& bytesDecoded, ENV_TYPE env){AsnTag tag;AsnLen elmtLen1;if ( (tag = BDecTag(b, bytesDecoded, env)) !=MAKE_TAG_ID(APPL, CONS, 1))AsnlError("Name::BDec: ERROR - wrong tag\n");longjmp(env, -101);}elmtLen1 = BDecLen(b, bytesDecoded, env);BDecContent(b, tag, elmtLen1, bytesDecoded, env);AsnLen BEncContent(BUF_TYPE b);void BDecContent(BUF_TYPE b, AsnTag tag, AsnLen elmtLen,AsnLen& bytesDecoded, ENV_TYPE env);int BEncPdu( BUF_TYPE b, AsnLen& bytesEncoded){bytesEncoded = BEnc(b);return(!b.WriteError());int BDecPdu( BUF_TYPE b, AsnLen& bytesDecoded){ENV_TYPE env;Appendix B. C++ Example^ 153int val;bytesDecoded = 0;if ((val = setjmp(env)) == 0 ){BDec(b, bytesDecoded, env);return(!b.ReadError());}elsereturn(FALSE);1 ;/* [APPLICATION 3] IMPLICIT IA5String */class Date : public IA5String{public:Date(): IA5String() {}Date(const char* str): IA5String(str) {}Date(const char* str, const unsigned long int len): IA5String(str,len) {}Date(const IA5String& o): IA5String(o) {}Date& operator=(const Date& o) {ReSet(o); return *this;}Date& operator=(const char* str) {ReSet(str); return *this;}AsnType* Clone() { return new Date; }AsnLen BEnc(BUF_TYPE b){AsnLen 1;1 = BEncContent(b);1 += BEncDefLen( b, 1);1 += BEncTagl(b, APPL, PRIM, 3);return(1);void BDec(BUF_TYPE b, AsnLen& bytesDecoded, ENV_TYPE env){AsnTag tag;AsnLen elmtLenl;if ( ((tag = BDecTag(b, bytesDecoded, env)) !=Appendix B. C++ Example^ 154MAKE_TAG_ID(APPL, PRIM, 3))&&(tag != MAKE_TAG_ID(APPL, CONS, 3))){AsnlError("Date::BDec: ERROR - wrong tag\n");longjmp(env, -106);}elmtLenl = BDecLen(b, bytesDecoded, env);BDecContent(b, tag, elmtLenl, bytesDecoded, env);int BEncPdu( BUF_TYPE b, AsnLen& bytesEncoded){bytesEncoded = BEnc(b);return(!b.WriteError());int BDecPdu( BUF_TYPE b, AsnLen& bytesDecoded){ENV_TYPE env;int val;bytesDecoded = 0;if ((val = setjmp(env)) == 0 ){BDec(b, bytesDecoded, env);return(!b.ReadError());}elsereturn(FALSE);} ;class Childlnformation : public AsnType{public:Name* name;Date dateOfBirth;Childlnformation() {}Appendix B. C++ Example^ 155void Print(ostream& os);AsnType* Clone() { return new Childlnformation; }AsnLen BEnc(BUF_TYPE b){AsnLen 1;1 = BEncContent(b);1 += BEncConsLen(b, 1);1 += BEncTagl(b, UNIV, CONS, SET_TAG_CODE);return(1);void BDec(BUF_TYPE b, AsnLen& bytesDecoded, ENV_TYPE env){AsnTag tag;AsnLen elmtLenl;if ( (tag = BDecTag(b, bytesDecoded, env)) !=MAKE_TAG_ID(UNIV, CONS, SET_TAG_CODE)){AsnlError("ChildInformation::BDec: ERROR - wrong tag\n");longjmp(env, -107);}elmtLenl = BDecLen(b, bytesDecoded, env);BDecContent(b, tag, elmtLenl, bytesDecoded, env);AsnLen BEncContent(BUF_TYPE b);void BDecContent(BUF_TYPE b, AsnTag tag, AsnLen elmtLen,AsnLen& bytesDecoded, ENV_TYPE env);int BEncPdu( BUF_TYPE b, AsnLen& bytesEncoded){bytesEncoded = BEnc(b);return(!b.WriteError());int BDecPdu( BUF_TYPE b, AsnLen& bytesDecoded){ENV_TYPE env;int val;Appendix B. C++ Example^ 156bytesDecoded = 0;if ((val = setjmp(env)) == 0 ){BDec(b, bytesDecoded, env);return(!b.ReadError());}elsereturn(FALSE);1 ;class PersonnelRecordSeq0f : public AsnType{protected:unsigned long int count;struct AsnListElmt{struct AsnListElmt* next;struct AsnListElmt* prey;Childlnformation* elmt;} *first, *curr, *last;public:void Print(ostream& os);AsnType* Clone() { return new PersonnelRecordSeq0f; }PersonnelRecordSeq0f 0 { count = 0; first = curr = last = NULL; }void SetCurrElmt(unsigned long int index);unsigned long int GetCurrElmtIndex();void SetCurrToFirst() { curr = first; }void SetCurrToLast() { curr = last; }// reading member fcnsint Count() { return count; }Childlnformation* First() { if (count > 0) return(first->elmt) ;else return(NULL); }Childlnformation* Last() { if (count > 0) return(last->elmt) ;else return(NULL); }Childlnformation* Curr() { if (curr != NULL) return(curr->elmt) ;else return(NULL); }Childlnformation* Next() { if ((curr != NULL)&& (curr->next != NULL))Appendix B. C++ Example^ 157return(curr->next->elmt) ; else return(NULL); }Childlnformation* Prev() { if ((curr != NULL)&& (curr->prev != NULL))return(curr->prev->elmt) ; else return(NULL); }// routines that move the curr elmtChildlnformation* GoNext() { if (curr != NULL) curr = curr->next;return(Curr()); }Childlnformation* GoPrev() { if (curr != NULL) curr = curr->prev;return(Curr()); }// write & alloc fcns - returns new elmtChildlnformation* Append(); // add elmt to end of listChildlnformation* Prepend(); // add elmt to beginning of listChildlnformation* InsertBefore(); //insert elmt before current elmtChildlnformation* InsertAfter(); //insert elmt after current elmt// write & alloc & copy - returns list after copying elmtPersonnelRecordSeq0f& AppendCopy( Childlnformation& elmt);PersonnelRecordSeq0f& PrependCopy( Childlnformation& elmt);PersonnelRecordSeq0f& InsertBeforeAndCopy( Childlnformation& elmt);PersonnelRecordSeq0f& InsertAfterAndCopy( Childlnformation& elmt);// encode and decode routinesAsnLen BEnc(BUF_TYPE b){AsnLen 1;1 = BEncContent(b);1 += BEncConsLen(b, 1);1 += BEncTagl(b, UNIV, CONS, SEQ_TAG_CODE);return(1);void BDec(BUF_TYPE b, AsnLen& bytesDecoded, ENV_TYPE env){AsnTag tag;AsnLen elmtLenl;if ( (tag = BDecTag(b, bytesDecoded, env)) !=MAKE_TAG_ID(UNIV, CONS, SEQ_TAG_CODE))AsnlError("PersonnelRecordSeq0f::BDec: ERROR - wrong tag\n");Appendix B. C++ Example^ 158longjmp(env, -111);}elmtLenl = BDecLen(b, bytesDecoded, env);BDecContent(b, tag, elmtLenl, bytesDecoded, env);AsnLen BEncContent(BUF_TYPE b);void BDecContent(BUF_TYPE b, AsnTag tag, AsnLen elmtLen,AsnLen& bytesDecoded, ENV_TYPE env);PDU_MEMBER_MACROS} ;class PersonnelRecord : public AsnType{public:Name* name;IA5String title;EmployeeNumber employeeNumber;Date dateOfHire;Name* nameOfSpouse;PersonnelRecordSeq0f* children;PersonnelRecord()f/* init optional/default elements to NULL */children = NULL;void Print(ostream& os);AsnType* Clone() { return new PersonnelRecord; }AsnLen BEnc(BUF_TYPE b)fAsnLen 1;1 = BEncContent(b);1 += BEncConsLen(b, 1);1 += BEncTagl(b, APPL, CONS, 0);return(1);Appendix B. C++ Example^ 159void BDec(BUF_TYPE b, AsnLen& bytesDecoded, ENV_TYPE env){AsnTag tag;AsnLen elmtLenl;if ( (tag = BDecTag(b, bytesDecoded, env)) !=MAKE_TAG_ID(APPL, CONS, 0)){AsnlError("PersonnelRecord::BDec: ERROR - wrong tag\n");longjmp(env, - 113);}elmtLenl = BDecLen(b, bytesDecoded, env);BDecContent(b, tag, elmtLenl, bytesDecoded, env);AsnLen BEncContent(BUF_TYPE b);void BDecContent(BUF_TYPE b, AsnTag tag, AsnLen elmtLen,AsnLen& bytesDecoded, ENV_TYPE env);int BEncPdu( BUF_TYPE b, AsnLen& bytesEncoded){bytesEncoded = BEnc(b);return(!b.WriteError());int BDecPdu( BUF_TYPE b, AsnLen& bytesDecoded){ENV_TYPE env;int val;bytesDecoded = 0;if ((val = setjmp(env)) == 0 ){BDec(b, bytesDecoded, env);return(!b.ReadError());}elsereturn(FALSE);} ;Appendix B. C++ Example^ 160// externs for value defs#endif /* conditional include of p_rec.h */Appendix B. C++ Example^ 161Snacc generated C++ file p_rec.0Appendix B. C++ Example^ 162//// p_rec.0 - class member functions for ASN.1 module P-REC//// This file was generated by snacc on Sun Apr 11 03:17:42 1993// UBC snacc written by Mike Sample// NOTE: this is a machine generated file - editing not recommended//#include "asn_incl.h"#include "p_rec.h"// value defsAsnLenName::BEncContent(BUF_TYPE b){AsnLen totalLen = 0;AsnLen 1;1 = familyName.BEncContent(b);1 += BEncDefLen( b, 1);1 += BEncTagl(b, UNIV, PRIM, IA5STRING_TAG_CODE);totalLen += 1;1 = initial.BEncContent(b);1 += BEncDefLen( b, 1);1 += BEncTagl(b, UNIV, PRIM, IA5STRING_TAG_CODE);totalLen += 1;1 = givenName.BEncContent(b);1 += BEncDefLen( b, 1);1 += BEncTagl(b, UNIV, PRIM, IA5STRING_TAG_CODE);totalLen += 1;return(totalLen);} /* Name::BEncContent */Appendix B. C++ Example^ 163voidName::BDecContent(BUF_TYPE b, AsnTag tag°, AsnLen elmtLen0,AsnLen& bytesDecoded, ENV_TYPE env){AsnTag tagl;AsnLen seqBytesDecoded = 0;AsnLen elmtLenl;tagl = BDecTag(b, seqBytesDecoded, env);if (( tagl == MAKE_TAG_ID( UNIV, PRIM, IA5STRING_TAG_CODE)) II( tagl == MAKE_TAG_ID( UNIV, CONS, IA5STRING_TAG_CODE))){elmtLenl = BDecLen(b, seqBytesDecoded, env);givenName.BDecContent(b, tag1, elmtLenl, seqBytesDecoded, env);tagl = BDecTag(b, seqBytesDecoded, env);}else{Asn1Error("ERROR - SEQUENCE is missing non-optional elmt.\n");longjmp(env, -102);if (( tagl == MAKE_TAG_ID( UNIV, PRIM, IA5STRING_TAG_CODE)) II( tagi == MAKE_TAG_ID( UNIV, CONS, IA5STRING_TAG_CODE))){elmtLenl = BDecLen(b, seqBytesDecoded, env);initial.BDecContent(b, tagl, elmtLenl, seqBytesDecoded, env);tagl = BDecTag(b, seqBytesDecoded, env);}else{AsnlError("ERROR - SEQUENCE is missing non-optional elmt.\n");longjmp(env, -103);if (( tagi == MAKE_TAG_ID( UNIV, PRIM, IA5STRING_TAG_CODE)) II( tagl == MAKE_TAG_ID( UNIV, CONS, IA5STRING_TAG_CODE))){elmtLenl = BDecLen(b, seqBytesDecoded, env);familyName.BDecContent(b, tagl, elmtLenl, seqBytesDecoded, env);Appendix B. C++ Example^ 164}else{AsnlError("ERROR - SEQUENCE is missing non-optional elmt.\n");longjmp(env, -104);bytesDecoded += seqBytesDecoded;if ( elmtLen0 == INDEFINITE_LEN ){BDecEoc(b, bytesDecoded, env);return;}else if (seqBytesDecoded != elmtLen0){AsnlError("ERROR - Length discrepancy on sequence.\n");longjmp(env, -105);}elsereturn;/* Name::BDecContent */voidName::Print(ostream& os){os << "{ -- SEQUENCE --" << endl;indentG += stdIndentG;Indent(os, indentG);os << "givenName ";os << givenName;os << "," << endl;Indent(os, indentG);os << "initial ";os << initial;os << "," << endl;Indent(os, indentG);os << "familyName ";os << familyName;os << endl;indentG -= stdIndentG;Indent(os, indentG);Appendix B. C++ Example^ 165os << "1";} 1* Name::Print */AsnLenChildInformation::BEncContent(BUF_TYPE b){AsnLen totalLen = 0;AsnLen 1;BEncEoclfNec(b);1 = dateOfBirth.BEncContent(b);1 += BEncDefLen( b, 1);1 += BEncTagl(b, APPL, PRIM, 3);1 += BEncConsLen( b, 1);1 += BEncTagl(b, CNTX, CONS, 0);totalLen += 1;BEncEoclfNec(b);1 = name->BEncContent(b);1 += BEncConsLen( b, 1);1 += BEncTagl(b, APPL, CONS, 1);totalLen += 1;return(totalLen);} /* ChildInformation::BEncContent */voidChildInformation::BDecContent(BUF_TYPE b, AsnTag tag°, AsnLen elmtLen0,AsnLen& bytesDecoded, ENV_TYPE env){AsnTag tag1;AsnLen setBytesDecoded = 0;unsigned int mandatoryElmtsDecoded = 0;AsnLen elmtLenl;AsnLen elmtLen2;for( ; (setBytesDecoded < elmtLen0) II (elmtLen0 == INDEFINITE_LEN);){tagl = BDecTag(b, setBytesDecoded, env);Appendix B. C++ Example^ 166if ((elmtLen0 == INDEFINITE_LEN) && (tag1 == EOC_TAG_ID)){BDEC_2ND_EOC_OCTET(b, setBytesDecoded, env)break; /* exit for loop */}elmtLenl = BDecLen (b, setBytesDecoded, env);switch(tagl){case(MAKE_TAG_ID( APPL, CONS, 1)):name = new Name;name->BDecContent(b, tag1, elmtLenl, setBytesDecoded, env);mandatoryElmtsDecoded++;break;case(MAKE_TAG_ID( CNTX, CONS, 0)):tag1 = BDecTag(b, setBytesDecoded, env);if ((tags != MAKE_TAG_ID( APPL, PRIM, 3)) &&(tagl != MAKE_TAG_ID( APPL, CONS, 3)))AsnlError("Unexpected Tag\n");longjmp(env, -108);elmtLen2 = BDecLen (b, setBytesDecoded, env);dateOfBirth.BDecContent(b, tag1, elmtLen2, setBytesDecoded, env);if (elmtLenl == INDEFINITE_LEN)BDecEoc(b, setBytesDecoded, env);mandatoryElmtsDecoded++;break;default:AsnlError("Unexpected Tag on SET elmt.\n");longjmp(env, -109);/* end switch *//* end for loop */bytesDecoded += setBytesDecoded;if (mandatoryElmtsDecoded != 2)AsnlError("ERROR - non-optional SET element missing.\n");Appendix B. C++ Example^ 167longjmp(env, -110);}} /* ChildInformation::BDecContent */voidChildInformation::Print(ostream& os){os << "{ -- SET --" << endl;indentG += stdIndentG;Indent(os, indentG);os << *name;os << "," << endl;Indent(os, indentG);os << "dateOfBirth ";os << dateOfBirth;os << endl;indentG -= stdIndentG;Indent(os, indentG);os << "1";} /* Childlnformation - operator<< */void PersonnelRecordSeq0f::Print(ostream& os){os << "-I -- SEQUENCE/SET OF -- " << endl;indentG += stdIndentG;SetCurrToFirst();for (; Curr() != NULL; GoNext()){Indent(os, indentG);os << *Curr();if ( Curr() != Last())os << ",";os << endl;}indentG -= stdIndentG;Indent(os, indentG);os << "1";} /* Print */Appendix B. C++ Example^ 168void PersonnelRecordSeq0f::SetCurrElmt(unsigned long int index){unsigned long int i;curr = first;for( i = 0; (i < (count-1)) && (i < index); i++)curr = curr->next;}} /* PersonnelRecordSeq0f::SetCurrElmt */unsigned long int PersonnelRecordSeq0f::GetCurrElmtIndex(){unsigned long int i;struct AsnListElmt* tmp;if (curr != NULL){for( i = 0, tmp = first; tmp != NULL; i++){if (tmp == curr)return(i);elsetmp = tmp->next;}return(count);} /* PersonnelRecordSeq0f::GetCurrElmtIndex */// alloc new list elmt, put at end of list// and return the component typeChildlnformation* PersonnelRecordSeq0f::Append(){struct AsnListElmt* newElmt;newElmt = new struct AsnListElmt;newElmt->elmt = new Childlnformation;newElmt->next = NULL;if( last == NULL ){newElmt->prev = NULL;first = last = newElmt;Appendix B. C++ Example^ 169}else{newElmt->prev = last;last->next^= newElmt;last^= newElmt;}count++;return( newElmt->elmt );} /* PersonnelRecordSeq0f::Append */// alloc new list elmt, put at begining of list// and return the component typeChildlnformation* PersonnelRecordSeq0f::Prepend(){struct AsnListElmt* newElmt;newElmt = new struct AsnListElmt;newElmt->elmt = new Childlnformation;newElmt->prev = NULL;if( first == NULL ){newElmt->next = NULL;first = last = newElmt;}elsenewElmt->next = first;first->prev = newElmt;first^= newElmt;}count++;return( newElmt->elmt );} /* PersonnelRecordSeq0f::Prepend */// alloc new list elmt, insert it before the// current element and return the component type// if the current element is null, the new element// is placed at the beginning of the list.Childlnformation* PersonnelRecordSeq0f::InsertBefore()Appendix B. C++ Example^ 170{struct AsnListElmt* newElmt;newElmt = new struct AsnListElmt;newElmt->elmt = new Childlnformation;if (curr == NULL){newElmt->next = first;newElmt->prev = NULL;first = newElmt;if (last == NULL)last = newElmt;}else{newElmt->next = curr;newElmt->prev = curr->prev;curr->prev = newElmt;if (curr == first)first = newElmt;elsenewElmt->prev->next = curr;}count++;return( newElmt->elmt );} /* PersonnelRecordSeq0f::InsertBefore */// alloc new list elmt, insert it after the// current element and return the component type// if the current element is null, the new element// is placed at the end of the list.Childlnformation* PersonnelRecordSeq0f::InsertAfter(){struct AsnListElmt* newElmt;newElmt = new struct AsnListElmt;newElmt->elmt = new Childlnformation;if (curr == NULL){newElmt->prev = last;newElmt->next = NULL;last = newElmt;Appendix B. C++ Example^ 171if (first == NULL)first = newElmt;}else{newElmt->prev = curr;newElmt->next = curr->next;curr->next = newElmt;if (curr == last)last = newElmt;elsecurr->next->prev = newElmt;}count++;return( newElmt->elmt );} /* PersonnelRecordSeq0f::InsertAfter */PersonnelRecordSeq0f& PersonnelRecordSeq0f::AppendCopy(Childlnformation& elmt){struct AsnListElmt* newElmt;newElmt = new struct AsnListElmt;newElmt->elmt = new Childlnformation;*newElmt->elmt = elmt;newElmt->next = NULL;if( last == NULL ){newElmt->prev = NULL;first = last = newElmt;}else{newElmt->prev = last;last->next^= newElmt;last^= newElmt;}count++;return(*this);} /* AppendCopy */PersonnelRecordSeq0f& PersonnelRecordSeq0f::PrependCopy(Appendix B. C++ Example^ 172ChildInformation& elmt){struct AsnListElmt* newElmt;newElmt = new struct AsnListElmt;newElmt->elmt = new Childlnformation;*newElmt->elmt = elmt;newElmt->prev = NULL;if( first == NULL ){newElmt->next = NULL;first = last = newElmt;}else{newElmt->next = first;first->prev = newElmt;first^= newElmt;}count++;return(*this);} /* PersonnelRecordSeq0f::PrependCopy */// alloc new list elmt, insert it before the// current element, copy the given elmt into the new elmt// and return the component type.// if the current element is null, the new element// is placed at the beginning of the list.PersonnelRecordSeq0f& PersonnelRecordSeq0f::InsertBeforeAndCopy(Childlnformation& elmt){struct AsnListElmt* newElmt;newElmt = new struct AsnListElmt;newElmt->elmt = new ChildInformation;*newElmt->elmt = elmt;if (curr == NULL){newElmt->next = first;newElmt->prev = NULL;Appendix B. C++ Example^ 173first = newElmt;if (last == NULL)last = newElmt;}else{newElmt->next = curr;newElmt->prev = curr->prev;curr->prev = newElmt;if (curr == first)first = newElmt;elsenewElmt->prev->next = curr;}count++;return( *this );} /* PersonnelRecordSeq0f::InsertBeforeAndCopy */// alloc new list elmt, insert it after the// current element, copy given elmt in to new elmt// and return the component type// if the current element is null, the new element// is placed at the end of the list.PersonnelRecordSeq0f& PersonnelRecordSeq0f::InsertAfterAndCopy(Childlnformation& elmt){struct AsnListElmt* newElmt;newElmt = new struct AsnListElmt;newElmt->elmt = new Childlnformation;*newElmt->elmt = elmt;if (curr == NULL){newElmt->prev = last;newElmt->next = NULL;last = newElmt;if (first == NULL)first = newElmt;}else{newElmt->prev = curr;Appendix B. C++ Example^ 174newElmt->next = curr->next;curr->next = newElmt;if (curr == last)last = newElmt;elsecurr->next->prev = newElmt;}count++;return( *this );} /* PersonnelRecordSeq0f::InsertAfterAndCopy */AsnLen PersonnelRecordSeq0f::BEncContent(BUF_TYPE b){struct AsnListElmt* currElmt;AsnLen elmtLen;AsnLen totalLen = 0;for (currElmt = last; currElmt != NULL; currElmt = currElmt->prev){BEncEoclfNec(b);elmtLen = currElmt->elmt->BEncContent(b);elmtLen += BEncConsLen( b, elmtLen);elmtLen += BEncTagl(b, UNIV, CONS, SET_TAG_CODE);totalLen += elmtLen;}return(totalLen);} /* PersonnelRecordSeq0f::BEncContent */void PersonnelRecordSeq0f::BDecContent( BUF_TYPE b, AsnTag tag°,AsnLen elmtLen0, AsnLen& bytesDecoded, ENV_TYPE env){Childlnformation* listElmt;AsnTag tagl;AsnLen listBytesDecoded = 0;AsnLen elmtLenl;while ((listBytesDecoded < elmtLen0) II (elmtLen0 == INDEFINITE_LEN)){tagl = BDecTag(b, listBytesDecoded, env);if ((tagl == EOC_TAG_ID) && (elmtLen0 == INDEFINITE_LEN)){BDEC_2ND_EOC_OCTET(b, listBytesDecoded, env);Appendix B. C++ Example^ 175break;}if ((tagl != MAKE_TAG_ID( UNIV, CONS, SET_TAG_CODE))){AsnlError("Unexpected Tag\n");longjmp(env, -112);elmtLenl = BDecLen (b, listBytesDecoded, env);listElmt = Append();listElmt->BDecContent(b, tagl, elmtLenl, listBytesDecoded, env);bytesDecoded += listBytesDecoded;} /* PersonnelRecordSeq0f::BDecContent */AsnLenPersonnelRecord::BEncContent(BUF_TYPE b){AsnLen totalLen = 0;AsnLen 1;if (NOT_NULL(children)){BEncEoclfNec(b);1 = children->BEncContent(b);1 += BEncConsLen( b, 1);1 += BEncTagl(b, CNTX, CONS, 3);totalLen += 1;}BEncEoclfNec(b);BEncEoclfNec(b);1 = nameOfSpouse->BEncContent(b);1 += BEncConsLen( b, 1);1 += BEncTagl(b, APPL, CONS, 1);1 += BEncConsLen( b, 1);1 += BEncTagl(b, CNTX, CONS, 2);totalLen += 1;Appendix B. C++ Example^ 176BEncEoclfNec(b);1 = dateOfHire.BEncContent(b);1 += BEncDefLen( b, 1);1 += BEncTagl(b, APPL, PRIM, 3);1 += BEncConsLen( b, 1);1 += BEncTagl(b, CNTX, CONS, 1);totalLen += 1;1 = employeeNumber.BEncContent(b);BEncDefLenTo127( b, 1);1++;1 += BEncTagl(b, APPL, PRIM, 2);totalLen += 1;BEncEoclfNec(b);1 = title.BEncContent(b);1 += BEncDefLen( b, 1);1 += BEncTagl(b, UNIV, PRIM, IA5STRING_TAG_CODE);1 += BEncConsLen( b, 1);1 += BEncTagl(b, CNTX, CONS, 0);totalLen += 1;BEncEoclfNec(b);1 = name->BEncContent(b);1 += BEncConsLen( b, 1);1 += BEncTagl(b, APPL, CONS, 1);totalLen += 1;return(totalLen);} /* PersonnelRecord::BEncContent */voidPersonnelRecord::BDecContent(BUF_TYPE b, AsnTag tagO, AsnLen elmtLenO,AsnLen& bytesDecoded, ENV_TYPE env){AsnTag tagl;AsnLen setBytesDecoded = 0;unsigned int mandatoryElmtsDecoded = 0;AsnLen elmtLenl;AsnLen elmtLen2;Appendix B. C++ Example^ 177for( ; (setBytesDecoded < elmtLenO) II (elmtLenO == INDEFINITE_LEN);){tag1 = BDecTag(b, setBytesDecoded, env);if ((elmtLenO == INDEFINITE_LEN) && (tagl == EOC_TAG_ID)){BDEC_2ND_EOC_OCTET(b, setBytesDecoded, env)break; /* exit for loop */}elmtLenl = BDecLen (b, setBytesDecoded, env);switch(tagl){case(MAKE_TAG_ID( APPL, CONS, 1)):name = new Name;name->BDecContent(b, tagl, elmtLenl, setBytesDecoded, env);mandatoryElmtsDecoded++;break;case(MAKE_TAG_ID( CNTX, CONS, 0)):tagl = BDecTag(b, setBytesDecoded, env);if ((tagl != MAKE_TAG_ID( UNIV, PRIM, IA5STRING_TAG_CODE)) &&(tagl != MAKE_TAG_ID( UNIV, CONS, IA5STRING_TAG_CODE))){AsnlError("Unexpected Tag\n");longjmp(env, -114);elmtLen2 = BDecLen (b, setBytesDecoded, env);title.BDecContent(b, tagl, elmtLen2, setBytesDecoded, env);if (elmtLenl == INDEFINITE_LEN)BDecEoc(b, setBytesDecoded, env);mandatoryElmtsDecoded++;break;case(MAKE_TAG_ID( APPL, PRIM, 2)):employeeNumber.BDecContent(b, tagl, elmtLenl, setBytesDecoded, env);mandatoryElmtsDecoded++;break;Appendix B. C++ Example^ 178case(MAKE_TAG_ID( CNTX, CONS, 1)):tagl = BDecTag(b, setBytesDecoded, env);if ((tagl != MAKE_TAG_ID( APPL, PRIM, 3)) &&(tagl != MAKE_TAG_ID( APPL, CONS, 3)))AsnlError("Unexpected Tag\n");longjmp(env, -115);elmtLen2 = BDecLen (b, setBytesDecoded, env);dateOfHire.BDecContent(b, tag1, elmtLen2, setBytesDecoded, env);if (elmtLenl == INDEFINITE_LEN)BDecEoc(b, setBytesDecoded, env);mandatoryElmtsDecoded++;break;case(MAKE_TAG_ID( CNTX, CONS, 2)):tagl = BDecTag(b, setBytesDecoded, env);if (tagl != MAKE_TAG_ID( APPL, CONS, 1)){AsnlError("Unexpected Tag\n");longjmp(env, -116);}elmtLen2 = BDecLen (b, setBytesDecoded, env);nameOfSpouse = new Name;nameOfSpouse->BDecContent(b, tag1, elmtLen2, setBytesDecoded, env);if (elmtLenl == INDEFINITE_LEN)BDecEoc(b, setBytesDecoded, env);mandatoryElmtsDecoded++;break;case(MAKE_TAG_ID( CNTX, CONS, 3)):children = new PersonnelRecordSeq0f;children->BDecContent(b, tag1, elmtLenl, setBytesDecoded, env);break;default:AsnlError("Unexpected Tag on SET elmt.\n");Appendix B. C++ Example^ 179longjmp(env, -117);} /* end switch */} /* end for loop */bytesDecoded += setBytesDecoded;if (mandatoryElmtsDecoded != 5){AsnlError("ERROR - non-optional SET element missing.\n");longjmp(env, -118);}} /* PersonnelRecord::BDecContent */voidPersonnelRecord::Print(ostream& os){os << "{ -- SET --" << endl;indentG += stdIndentG;Indent(os, indentG);os << *name;os << "," << endl;Indent(os, indentG);os << "title ";os << title;os << "," << endl;Indent(os, indentG);os << employeeNumber;os << "," << endl;Indent(os, indentG);os << "dateOfHire ";os << dateOfHire;os << "," << endl;Indent(os, indentG);os << "nameOfSpouse ";os << *nameOfSpouse;if (NOT_NULL(children)){os << ","<< endl;Indent(os, indentG);os << "children ";os << *children;}os << endl;Appendix B. C++ Example^ 180indentG -= stdIndentG;Indent(os, indentG);os « "1";} /* PersonnelRecord - operator« */Appendix CThe Type Table Data StructureThis appendix contains the definitions of the type table data structure.-- TBL types describe ASN.1 data structures.-- These can be used in generic, interpretive encoders/decoders.-- The type table is defined in ASN.1 to provide a simple (BER)-- file format for tables. It also allows tables be sent over a-- network for dynamic re-configuration of encoders/decoders.-- MS 93TBL DEFINITIONS ::=BEGIN-- imports nothing-- exports nothingTBL ::= --snacc isPdu:"TRUE" -- SEQUENCE{totalNumModules INTEGER, -- these totals can help allocationtotalNumTypeDefs INTEGER, -- when decoding (ie use arrays)totalNumTypes^INTEGER,totalNumTags^INTEGER,totalNumStrings INTEGER,totalLenStrings INTEGER,modules SEQUENCE OF TBLModuleTBLModule ::= SEQUENCE{name^[0] IMPLICIT PrintableString,181Appendix C. The Type Table Data Structure^ 182id^[1] IMPLICIT OBJECT IDENTIFIER OPTIONAL,typeDefs [2] IMPLICIT SEQUENCE OF TBLTypeDef}TBLTypeDef ::= SEQUENCE{typeDefId TBLTypeDefId,typeName PrintableString OPTIONAL,type^TBLType}TBLType ::= SEQUENCE{typeld^[0] IMPLICIT TBLTypeId,optional [1] IMPLICIT BOOLEAN,tagList^[2] IMPLICIT SEQUENCE OF TBLTag OPTIONAL,content^[3] TBLTypeContent,fieldName [4] IMPLICIT PrintableString OPTIONALTBLTypeContent ::= CHOICE{primType [0] IMPLICIT NULL,elmts^[1] IMPLICIT SEQUENCE OF TBLType,typeRef [2] IMPLICIT TBLTypeRefTBLTypeRef ::= SEQUENCE{typeDef TBLTypeDefId,implicit BOOLEANTBLTypeId ::= ENUMERATED{tbl-boolean(0),tbl-integer(1),tbl-bitstring(2),tbl-octetstring(3),tbl-null(4),tbl-oid(5),Appendix C. The Type Table Data Structure^ 183tbl-real(6),tbl-enumerated(7),tbl-sequence(8),tbl-set(9),tbl-sequenceof(10),tbl-setof(11),tbl-choice(12),tbl-typeref(13)}TBLTypeDefId ::= INTEGERTBLTag ::= SEQUENCEtclass TBLTagClass,code INTEGER (0..MAX)TBLTagClass ::= ENUMERATED { universal(0), application(1),context(2), private(3)}ENDBibliography[ASN184] CCITT, "Recommendation X.409, Presentation Transfer Syntax and No-tation", Data Communications Networks Message Handling Systems, RedBook, Volume VIII, Fascicle VIII.7, pages 62-93, Omnicom, 115 Park St.,S.E., Vienna, VA 22180 USA, Oct. 1985.[ASN188] CCITT, "Recommendation X.208, Specification of Abstract Syntax No-tation One (ASN. 1)", Data Communications Networks Open systems In-terconnection (OSI) Model and Notation, Service Defintion, Blue Book,volume VIII, Fascicle VIII.4, pages 57-130, Omnicom, 115 Park St., S.E.,Vienna, VA 22180 USA, Nov. 1989.[BER88] CCITT, "Recommendation X.209, Specification of Basic Encoding Rulesfor Abstract Syntax Notation One (ASN.1)", Data Communications Net-works Open systems Interconnection (OSI) Model and Notation, ServiceDefintion, Blue Book, Volume VIII, Fascicle VIII.4, pages 130-151, Om-nicom, 115 Park St., S.E., Vienna, VA 22180 USA, Nov. 1989.[Bochman89] G. von Bochman and M. Deslouriers, "Combining ASN1 Support withthe LOTOS Language", Proceedings of the International Symposium onProtocol Specification, Testing, and Verification IX, North Holland Pub-lishers, 1989.[Caneschi87][Cardoso92][CDER92][Clark89]F. Caneschi and E. Merelli,^"An Architecture for an ASN.1 En-coder/Decoder", Computer Networks and ISDN Systems, 14:297-303,1987.Artur Cardoso and Eduardo Tovar, "Defining More Efficient TransferSyntax for Application Layer PDUs in Field Bus Applications", SigcommComputer Communication Review, 22(3):98-105, Jul. 1992.ISO/IEC, "DIS 8825-3: Specification of ASN.1 Encoding Rules - Part 3:Distinguished and Canonical Encoding Rules" , Jun. 1992.David D. Clark, Van Jacobson, John Romkey and Howard Salwen, "AnAnalysis of TCP Processing Overhead" , IEEE Communications Maga-zine, pages 23-29, Jun. 1989.184Bibliography[Clark90][DeShon86][DS88][Gaudette89][GRU90][PIX90][Herlihy82][Huitema89][Huitema92][Kernighan88][Koh192][Kong90][MHS88]185David D. Clark and David L. Tennenhouse, "Architectural Considera-tions for a New Generation of Protocols", Sigcomm '90, 20(4):200-208,Sep. 1990.Annette L. DeSchon, "A Survey of Data Representation Standards (RFC971)", Network Information Center, SRI International, Jan. 1986.CCITT, "Recommendation X.500, OSI:Specification of the DistributedDirectory System", Data Communication Networks, Blue Book, VolumeVIII, Fascicle VIII.8, pages 131-151, Omnicom, 115 Park St., S.E., Vi-enna, VA 22180 USA, Nov. 1989.Phillip Gaudette, Steve Trus and Sarah Collins, "The Free Value Toolfor ASN.1", National Institute of Standards and Technology, Feb. 1989.MIPS Computer Inc., "GETRUSAGE(2-BSD)", RISC/os ReferenceManual, Aug. 1990.MIPS Computer Inc., "PIXIE(1-SysV)", RISC/os Reference Manual,Aug. 1990.M. Herlihy and B. Liskov, "A Value Transmission Method For AbstractData Types", ACM Transactions on Programming Languages and Sys-tems, 4(4):527-551, Oct. 1982.Christian Huitema and Assem Doghri, "Defining Faster Transfer Syn-taxes for the OSI Presentation Layer", Sigcomm Computer Communica-tion Review, 19(5):44-55, Oct. 1989.Christian Huitema and Ghislain Chave, "Measuring the Performances ofan ASN.1 Compiler", Upper Layer Protocols, Architectures and Appli-cations, pages 99-112, May 1992.Brian W. Kernighan and Dennis M. Ritchie, "The C Programming Lan-guage, 2nd Edition", Prentice-Hall, 1988.John Kohl and B. Clifford Neuman, "Internet-draft: The Kerberos Net-work Authentication Service (v5)", Sep. 1992Mike Kong, "Network Computing System Reference Manual", Prentice-Hall, Inc., 1990.CCITT, Recommendations X.400-X.420, Data Communication NetworksMessage Handling Systems, Blue Book, Volume VIII, Fascicle VIII.7,Omnicom, 115 Park St., S.E., Vienna, VA 22180 USA, Nov. 1989.Bibliography[MMS87][NBS83][Neufeld90][Neufeld92-1][Neufeld92-2][OSF/RPC90][OS188][Partridge89][PER91][PER92][Pimente188]186ISO/IEC, "9506: Manufacturing Message Specification (MMS)", Jun.1987.National Bureau of Standards, "Specification for Message Format forComputer Based Message Systems", (also published as RFC 841), FederalInformation Processing Standards Publication 98, Jan. 1983.Gerald Neufeld and Yeuli Yang, "An ASN.1 to C Compiler", IEEETransactions on Software Engineering, 16(10):1209-1220, Oct. 1990.Gerald Neufeld and Son Vuong, "An Overview of ASN.1", IEEE Net-works and ISDN Systems, 23(5):393-415, Feb. 1992.Gerald Neufeld, Barry Brachman, Murray Goldberg and Duncan Stick-ings, "The EAN X.500 Directory Service", Internetworking: Researchand Experience, 3:55-81, 1992.Open Software Foundation Inc. (OSF), "OSF/DCE Remote ProcedureCall in a Distributed Computing Environment" , 1990.CCITT, "Recommendation X.200, Reference Model of Open Systems In-terconnection for CCITT Applications" , Data Communications NetworksOpen Systems Interconnection (OSI) Model and Notation, Service Defin-tion, Blue Book, Volume VIII, Fascile VIII.4, pages 3-56, Omnicom, 115Park St., S.E., Vienna, VA 22180 USA, Nov. 1989.Craig Partridge and Marshall T. Rose, "A Comparison of External DataFormats" , IFIP '89: Message Handling Systems and Distributed Applica-tions, pages 233-245, Elsevier Science Publishers B.V. (North Holland),1989.ISO/IEC, "8825-2, 1st CD: Specification of ASN.1 Encoding Rules - Part2: Packed Encoding Rules", Oct. 1991.ISO/IEC, "8825-2, 2nd CD: Specification of ASN.1 Encoding Rules -Part 2: Packed Encoding Rules", Jun. 1992.J.R. Pimentel, "Efficient Encoding of Application Layer PDUs for Field-bus Networks", Sigcomm Computer Communication Review, 18(3):14-44, May 1988.[Pope84]^Arthur Pope, "Encoding CCITT X.409 Presentation Transfer Syntax",Sigcomm Computer Communication Review, 14(4):4-10, Oct. 1984.Bibliography^ 187[Poste180]^J. Postel, "Internet Message Protocol (RFC 759)" , Network InformationCenter, SRI International, Aug. 1980.[Prasad93]^Raja Prasad and Ulloa Gonzalo, "A Simple Encoder for Fieldbus Appli-cations", Sigcomm Computer Communication Review, 23(1):34-44, Jan.1993.[ROS88]^CCITT, "Remote Operations: Model, Notation and Service Definition",Data Communications Networks Open Systems Interconnection (OSI)Model and Notation, Service Defintion, Blue Book, Volume VIII, Fas-cicle VIII.4, pages 465-502, Omnicom, 115 Park St., S.E., Vienna, VA22180 USA, Nov. 1989.[Rose90]^Marshall T. Rose, "ISODE, The ISO Development Environment: UserManual", Wollongong Group, 1129 San Antonio Rd., Palo Alto, Califor-nia, USA, Feb. 1990.[Sample93-1] Michael Sample, "Snacc 1.0: A High Performance ASN.1 to C/C++Compiler (User Manual)". University of British Columbia, Feb. 1993.[Sample93-2] Michael Sample and Gerald Neufeld, "Implementing Efficient Encodersand Decoders for Network Data Representations", IEEE INFOCOM '93Proceedings, Volume 3, pages 1144-1153, Mar. 1993.[snmp90]^M. Rose and K. McCloghrie, "Structure and Identification of Manage-ment Information for TCP/IP-based Internets (RFC 1155)", NetworkInformation Center, SRI International, May 1990.[Steedman90] Douglass Steedman, "ASN.1, The Tutorial and Reference", TechnologyAppraisals Ltd., 1990.[Steiner88]^J. Steiner, C. Neuman, and J. Schiller, "Kerberos: An AuthenticationService for Open Network Systems", Proceedings of the USENIX WinterConference, Feb. 1988.[Stroustrup9l] Bjarne Stroustrup, "The C++ Programming Language", 2nd Edition,Addison-Wesley Publishing Co., 1991.[Sun87]^Sun Microsystems Inc., "XDR: External Data Representation Standard(RFC 1014)", Network Information Center, SRI International, Jun. 1987.[Thomesse87] J.P. Thomesse and J.L. Delcuvellerie, "FIP: A Field Bus Proposal", NBSWorkshop on Factory Communications, Gaithersburg, Md., March 1987.Bibliography^ 188[White89]^James E. White, "ASN.1 and ROS: The Impact of X.400 on OSI" , IEEEJournal on Selected Areas in Communications, 7(7):1060-1072, Sep. 1989.[Xerox81]^XEROX Corporation, "Courier: The Remote Procedure Call Protocol",xsis-038112, Dec. 1981.[Yang88]^Yueli Yang, "ASN.1-C Compiler for Automatic Protocol Implementa-tion" , Master's thesis, University of British Columbia, Oct. 1988.[Z39.50]^ANSI, "Z39.50/V2D3", May 1991.[Zahn90]^Lisa Zahn, "Network Computing Architecture", Prentice-Hall, Inc.,1990.

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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051367/manifest

Comment

Related Items