PACKEDOBJECTS

John P. T. Moore

Zedstar Dot Org Ltd

PO BOX 119, Pinner, HA5 2UR, United Kingdom

Keywords:

Packed Encoding Rules, ASN.1, Scheme, C.

Abstract:

packedobjects is a highly portable, cross platform, data encoding tool. The project is based on the telecom-

munications standard Packed Encoding Rules (PER). An abstract syntax language is used to deﬁne a protocol

speciﬁcation. packedobjects uses the Scheme programming language to represent the protocol speciﬁcation

within a symbolic expression (s-expression). Using an s-expression provides a more dynamic approach over

the traditional method of parsing the speciﬁcation and producing high level language code. The output of ap-

plying packedobjects’ encoding rules to a protocol speciﬁcation is a concisely encoded bit stream suitable for

application domains such as network games development and mobile application development. The project

has been released under the terms of the BSD license.

1 INTRODUCTION

Although the use of text-based protocols on the In-

ternet is widespread, binary protocols have many di-

verse application domains. Examples include: se-

curity, mobile telephony, videoconferencing, aviation

and transportation (Dubuisson, 2000). The demand

for binary network protocols has risen due to perfor-

mance requirements of domains such as online gam-

ing and mobile application development. Distinct ap-

proaches to building a binary protocol exist. These

include ”encoding by hand”, applying some trans-

fer rules to an existing text-based protocol or using

a speciﬁcation language designed to produce binary

encodings from the onset. Encoding by hand uses

speciﬁc programming language features to design a

data structure suitable for serialising for transmission

across a network (Isensee, 2004). Although it is often

possible to obtain performance gains by applying ad

hoc bit packing routines, the disadvantages are likely

to outweigh any such advantage. Disadvantages in-

clude the development and debugging time that might

be required to build robust portable solutions. A more

favourable approach might be to leverage existing

skills in markup languages and apply some transfor-

mation to the markup before it is sent across a com-

munication medium. This is the approach favoured

by the Wireless Application Protocol (WAP) (Open

Mobile Alliance, 2001). In addition, work on Fast

Web Services (Sandoz et al., 2003) marks an attempt

to improve the performance of web services by bi-

nary encoding data rather than sending textual XML

representations. In general, tests have shown that bi-

nary encoding can be signiﬁcantly faster than tex-

tual encoding (ASN.1 Consortium, 2002). The ap-

proach taken by the packedobjects project is based on

the telecommunication standard Abstract Syntax No-

tation One (ASN.1) (ITU-T, 1988b). ASN.1 has been

an international standard since 1984 and has produced

efﬁcient encoding techniques such as Packed Encod-

ing Rules (PER) (ITU-T, 1998). Support for ASN.1

has been built into languages such as Erlang, and tools

exist ranging from freeware solutions to professional

toolkits.

Development with ASN.1 usually involves trans-

forming the protocol speciﬁcation into a high level

language suitable to be compiled into an application

(Larmouth, 1999). The high level language used is

independent of ASN.1 and dependent on the tool ven-

dor support. An advantage of using a compiler is

that the speciﬁcation language can be extremely pow-

erful and expressive without fears of hindering run-

time performance. The disadvantage, however, is

that ASN.1 could be considered complex and also re-

quires special handling to provide extensibility of pro-

tocols designed to produce tightly packed bit streams.

packedobjects takes a more dynamic stance by using

an s-expression from the Scheme programming lan-

guage to represent the protocol speciﬁcation. This

approach not only eliminates the lexical obstacles

faced transforming ASN.1 into a high level language,

but also provides a simple method of extensibility

by forcing a separation between the protocol and the

compiled application. In addition:

310

P. T. Moore J. (2006).

PACKEDOBJECTS.

In Proceedings of the International Conference on Wireless Information Networks and Systems, pages 310-314

 SciTePress

• Existing tools with built in support for editing

Scheme can be used, such as Emacs.

• The Scheme language can be used to provide error

handling and reporting.

• The use of quasi-quote can provide a mecha-

nism for replicating user-deﬁned abstract types in

ASN.1.

• Other language features such as comments can eas-

ily be added to the speciﬁcation.

The disadvantage of applying such a dynamic ap-

proach is the loss of runtime performance. However,

by using a practical subset of ASN.1 the amount of

processing that is required can be constrained.

2 ENCODING RULES

ASN.1 provides notation for deﬁning abstract values

which carry information. Applying encoding rules to

an abstract syntax produces a series of bits ready for

network transmission. Various encoding rules have

been deﬁned, including variants within encoding rules

themselves (Mitra, 1994). A clear advantage exists

when separating the way in which information is rep-

resented on a communications link from the abstract

syntax used to describe the information. Depending

on the nature of the application, different encoding

rules may be selected without requiring any change

to the protocol speciﬁcation. It therefore may be pos-

sible to exploit advancements made in encoding tech-

niques over the years.

-- Baseball Card Abstract Syntax (BCAS)

BCAS DEFINITIONS ::= BEGIN

BBCard ::= SEQUENCE {

name IA5String (SIZE (1..60)),

team IA5String (SIZE (1..60)),

age INTEGER (1..100),

position IA5String (SIZE (1..60)),

handedness ENUMERATED {

left-handed(0),

right-handed(1),

ambidextrous(2)},

batting-average REAL

}

myCard BBCard ::= {

name "Casey",

team "Mudville Nine",

age 32,

position "left field",

handedness ambidextrous,

batting-average {

mantissa 250,

base 10,

exponent -3}

}

END

The above code is an example of how ASN.1 can be

used to describe a baseball score card. The speciﬁ-

cation is given with corresponding values. Although

some notation is unique to the standard, it is fairly in-

tuitive. Indeed, it can be useful as a means of sim-

ply communicating a protocol in a verbal or writ-

ten sense between application developers. The lan-

guage provides a set of atomic and composite types.

The example provided is comprised of the atomic

types ’IA5String’, ’INTEGER’, ’ENUMERATED’

and ’REAL’ together with the composite type ’SE-

QUENCE’. The composite types are a collection of

one or more atomic and/or composite types. To trans-

form this abstract syntax into a concise bit stream we

can apply PER. A PER speciﬁcation may use visi-

ble subtype constraints to optimise the encoding. In

the example, constraints are placed on the size of the

’IA5String’ and ’INTEGER’ type. Subtyping is a

powerful mechanism to restrict the set of values that

may be allowed for a given type (ITU-T, 1988a). Typ-

ically, subtyping is used to restrict the allowable range

of an integer type, provide a maximum and/or mini-

mum size for the length of a string, and place bounds

on the number of iterations that may occur in a ’SE-

QUENCE OF’ or ’SET OF’ type. The ability to cus-

tomise data types produces efﬁcient PER encodings.

Not only are less bits sent across the communications

link but also more optimised encoder/decoder imple-

mentations can be built to handle speciﬁc protocols.

3 PACKEDOBJECTS

packedobjects is an open source project implemented

in Chicken Scheme (Winkelmann, 2006) and the C

programming language. The software has been made

available (Moore, 2006) under the BSD license. Cur-

rently the project uses Chicken as its host language,

although it is possible to embed Chicken within C

and therefore use C as the host language

. Scheme

is used to provide all the high level data handling rou-

tines while C provides all the low level bit manipu-

lation. The project is highly portable. Chicken has

been ported to numerous platforms and the C code

conforms to the ANSI standard.

One of the motives of the project was to allow

prototyping and development on embedded hardware.

The user has the choice of working within the inter-

preter or compiling the code. Using the interpreter

provides a simple method for designing and testing

protocol speciﬁcations on embedded hardware with-

out the need to cross compile. packedobjects has been

successfully tested on a handheld device running em-

bedded Linux.

The term ”host language” is used to indicate the lan-

guage the developer would be using.

packedobjects provides a simple API. The core

functionality comprises of three routines to pack, un-

pack, and free data. Additional routines exist to

read and write data from a ﬁle descriptor which fa-

cilitates communication across a network. As pre-

viously stated, a protocol is speciﬁed using an s-

expression. For example, the following code illus-

trates how packedobjects would represent the baseball

card depicted earlier in ASN.1:

(require-extension packedobjects)

(define bbcard

’(bbcard sequence

(name string (size 1 60))

(team string (size 1 60))

(age integer (range 1 100))

(position string (size 1 60))

(handedness enumerated

(left-handed

right-handed

ambidextrous))

(batting-average sequence

(mantissa integer ())

(base enumerated (2 10))

(exponent integer ()))))

(define bbcard-values

’(bbcard

(name "Casey")

(team "Mudville Nine")

(age 32)

(position "left field")

(handedness ambidextrous)

(batting-average

(mantissa 250)

(base 10)

(exponent -3))))

3.1 Grammar

A difference exists between the way packedobjects

and ASN.1 handle ’batting-average’ in the base-

ball card speciﬁcation. packedobjects does not di-

rectly support the ’REAL’ type. This highlights how

packedobjects uses a subset of the ASN.1 data types

to represent other types. In this example the ’REAL’

type is represented by a composite type containing

three atomic types. The complete grammar for a data

type in packedobjects can be described as follows:

datatype = "(" datatype_name composite_type

| atomic_type ")" ;

composite_type = "(" "sequence"

| "sequence-of"

| "choice"

| "set" datatype { datatype } ")" ;

atomic_type = "(" string

| integer

| boolean

| enumerated ")" ;

integer = "integer" "()"

| "(" "range" range ")" ;

string = "string"

| "octet-string"

| "bit-string"

| "hex-string" "()"

| "(" "size" size ")" ;

datatype_name = symbol ;

digit = "0".."9" ;

signed_n = [ "+" | "-" ] digit { digit } ;

unsigned_n = digit { digit } ;

range = signed_n | "min" signed_n | "max" ;

size = unsigned_n | "min" unsigned_n | "max" ;

boolean = "boolean" ;

enumerated = "enumerated" "(" symbol { symbol } ")" ;

Where ’symbol’ is any valid symbol as deﬁned by the

Scheme programming language.

3.2 Extended Example

(define protocol

’(random choice

(query sequence

(num integer

(range 1 512))

(min integer

(range -1000000000 1000000000))

(max integer

(range -1000000000 1000000000)))

(response sequence-of

(n integer

(range -1000000000 1000000000)))))

The above code represents a simple protocol used to

request a sequence of random numbers from a server.

The server obtains the numbers from the site ran-

dom.org using HTTP. The client may request up to

and including 512 random numbers in the range of -

1,000,000,000 to 1,000,000,000. For example the fol-

lowing query requests 4 numbers:

(define query

’(random

(query

(num 4)

(min -1000000000)

(max 1000000000)))

Supplying values to be encoded is straightforward,

however, care is needed when using the ’sequence-

of’ type. Each iteration of a ’sequence-of’ type must

be delimited as it may contain multiple items. Square

brackets are used to highlight the iteration of numbers

in the random number protocol response as follows:

(define response

’(random

(response

[(n -841852048)]

[(n 350371729)]

[(n -99891633)]

[(n -76431948)])))

This response indicates that the ’sequence-of’ con-

tains just one item (an integer) and this sequence re-

peats four times.

Figure 1 shows a comparison of the number of

bytes transfered at the application layer using HTTP

Figure 1: Total bytes transfered with HTTP and

packedobjects.

and obtaining the numbers via the packedobjects pro-

tocol.

The results show the packedobjects ver-

sion offers signiﬁcant improvements in performance

in terms of bytes transfered.

This example together with the previous baseball

card example has illustrated the usage of all the data

types available in packedobjects apart from the ’set’

and ’boolean’ type. Supplying values to the ’set’ type

is exactly the same as the ’sequence’ type. Finally,

using a ’boolean’ type simply requires supplying the

value 1 or 0 to indicate true or false respectively.

3.3 Extensibility

packedobjects allows the following types to be ex-

tended:

• constraints on integers and strings

• enumerations

• choices

• set items

To maintain compatibility between applications of

different versions requires obtaining the latest pro-

tocol. This protocol could reside on a server from

which the application bootstraps. Another beneﬁt of

this approach exists in domains such as gaming where

it is important to stay one step ahead of users who are

trying to reverse engineer the network protocol. Al-

though using bit packed protocols provides some pro-

tection from casual observers, the dynamic approach

of using s-expressions facilitates easy change to a pro-

tocol without requiring any patches to be applied to

existing binaries. If the protocol is kept secure, then

Due to the nature of random numbers the data between

tests will vary, however, this will have little impact on the

results displayed.

reverse engineering the bit stream is not straight for-

ward.

3.4 Encoding Deviations

Although the ’set’ type is not often seen in PER

speciﬁcations, it can provide a ﬂexible addition to

packedobjects protocols. The use of ’set’ not only

allows unordered items but also allows each item to

be optional. This can provide support for the non

extensible ’sequence’ and ’sequence-of’ types. In

packedobjects the items of a ’set’ are encoded in the

order in which they appear in the speciﬁcation. In

PER order is deﬁned by ”the tag value” of the data

type. The use of optional items requires a bitmap

to be encoded to indicate which items are present.

packedobjects encodes this bitmap as a ’bit-string’.

This differs from PER which uses a constrained whole

number approach. Using a ’bit-string’ provides a sim-

ple way to support unlimited length sets and avoids

the limitations described in the the following section.

The disadvantage of using this approach and using

sets in general is that they are less efﬁcient in terms

of the processing overhead required.

3.5 Limitations

The number of choices or enumerations is restricted

to 2

values. In practice this should be adequate,

however, additional support could be provided by tai-

loring the speciﬁcation accordingly and/or using the

’set’ type. This limit also matches the limit imposed

by the Chicken Scheme language for ﬁxnums. There-

fore, all integers are limited to ﬁxnum ranges.

4 FUTURE WORK

A study of different protocol speciﬁcations could

highlight which features of ASN.1 are most widely

used. Often, however, protocol speciﬁcations devel-

oped in ASN.1 are not available in the public do-

main. The packedobjects project could beneﬁt from

such a study to help determine the most optimum sub-

set of the language to support. A trade-off will ex-

ist between supporting a wide range of the language

and runtime performance. When CPU performance

is critical the sfsexp project could be examined (Sot-

tile, 2005). The sfsexp project provides a library for

working with s-expressions from C/C++. In addition,

the speciﬁcation language used by packedobjects is

minimal and therefore it is possible to build optimised

custom interpreters for other high level languages.

Whether or not CPU performance is an issue de-

pends on the application domain. The cost of packing

network messages may be negligible when the size

of the network packets are small. In some networks,

such as mobile networks, users are charged for the

quantity of data they transfer. CPU performance again

may not be deemed the main design factor, especially

as the power of embedded hardware increases. Ul-

timately, it is the concept of throughput which de-

termines overall performance of a network protocol.

Throughput takes into account the cost in terms of

CPU performance as well as the cost in terms of ”bits

on the wire”.

5 CONCLUSION

The packedobjects project demonstrates the suitabil-

ity of mixing the Scheme programming language and

the C programming language to build a dynamic data

encoding tool capable of producing concise binary

network protocols. The increasing demand for bi-

nary protocols is being fueled by web developers,

games developers and mobile application develop-

ment. Along with this increasing demand is an in-

crease in the number of hardware platforms to sup-

port. The range of high level languages available

to do the same or similar job is also increasing.

packedobjects uses an s-expression to describe a net-

work protocol in a way that is independent of the pro-

gramming language used or the target hardware plat-

form.

The project has been designed to meet the de-

mands of ubiquitous embedded computing and is ide-

ally suited to bridge a gap between ad hoc bit packing

and more formal approaches such as those offered by

ASN.1 based solutions.

REFERENCES

ASN.1 Consortium (2002). Benchmark review : Com-

parison between binary encoder vs. textual encoder.

http://www.asn1.org/benchmark/benchmark1.htm.

Dubuisson, O. (2000). ASN.1 Communication between Het-

erogeneous Systems. Morgan Kaufmann.

Isensee, P. (2004). Bit Packing: A Network Compression

Technique, chapter 6, pages 571–578. Games Pro-

gramming Gems 4. Charles River Media.

ITU-T (1988a). Abstract syntax notation one (ASN.1):

Constraint speciﬁcation. Rec. X.682.

ITU-T (1988b). Information technology – abstract syntax

notation one (ASN.1): Speciﬁcation of basic notation.

Rec. X.680.

ITU-T (1998). ASN.1 encoding rules: Speciﬁcation of

packed encoding rules (PER). Rec. X.691.

Larmouth, J. (1999). ASN.1 Complete. AP Professional.

Mitra, N. (1994). Efﬁcient encoding rules for ASN.1 based

protocols. Technical report, AT&T Technical Journal.

Moore, J. (2006). packedobjects. http://www.call-with-

current-continuation.org/eggs/packedobjects.html.

Open Mobile Alliance (2001). Wireless Appli-

cation Protocol Architecture Speciﬁcation.

http://www.openmobilealliance.org/tech/afﬁliates/

wap/wap-210-waparch-20010712-a.pdf.

Sandoz, P., Pericas-Geertsen, S., Kawaguchi,

K., Hadley, M., and Pelegri-Llopart,

E. (2003). Fast Web Services.

http://java.sun.com/developer/technicalArticles/

WebServices/fastWS/.

Sottile, M. (2005). the small, fast s-expression library.

http://sexpr.sourceforge.net/.

Winkelmann, F. (2006). Chicken. http://www.call-with-

current-continuation.org/.