Flavor: A Language for Media Representation
Alexandros Eleftheriadis, Danny Hong, and Yuntai Kyong
Department of Electrical Engineering∗
Columbia University
New York, NY 10027, USA

arXiv:cs/0301003v1 [] 7 Jan 2003

January 6, 2003

Abstract
Flavor (Formal Language for Audio-Visual Object Representation) has been created as a language
for describing coded multimedia bitstreams in a formal way so that the code for reading and writing
bitstreams can be automatically generated. It is an extension of C++ and Java, in which the typing
system incorporates bitstream representation semantics. This allows describing in a single place both
the in-memory representation of data as well as their bitstream-level (compressed) representation.
Flavor also comes with a translator that automatically generates standard C++ or Java code from
the Flavor source code so that direct access to compressed multimedia information by application
developers can be achieved with essentially zero programming. Flavor has gone through many enhancements and this paper fully describes the latest version of the language and the translator. The
software has been made into an open source project as of Version 4.1, and the latest downloadable
Flavor package is available at http://flavor.sourceforge.net.

1

Introduction

Flavor originated from the need to simplify and speed up the development of software that processes
coded audio-visual or general multimedia information. This includes encoders and decoders as well
as applications that manipulate such information. Examples include editing tools, synthetic content
creation tools, multimedia indexing and search engines, etc. Such information is invariably encoded in a
highly efficient form to minimize the cost of storage and transmission. This source coding [1] operation
is almost always performed in a bitstream-oriented fashion: the data to be represented is converted to a
sequence of binary values of arbitrary (and typically variable) lengths, according to a specified syntax.
The syntax itself can have various degrees of sophistication. One of the simplest forms is the GIF87a
format [2], consisting of essentially two headers and blocks of coded image data using the Lempel-ZivWelch (LZW) compression. Much more complex formats include JPEG [3], MPEG-1 [4], MPEG-2 [5, 6]
and MPEG-4 [7, 8], among others.
General-purpose programming languages such as C++ [9] and Java [10] do not provide native
facilities for coping with such data. Software codec (encoder/decoder) or application developers need
to build their own facilities, involving two components. First, they need to develop software that deals
with the bitstream-oriented nature of the data, as general-purpose microprocessors are strictly byteoriented. Second, they need to implement parsing and generation code that complies with the syntax
of the format at hand (be it proprietary or standard). These two tasks represent a significant amount
of the overall development effort. They also have to be duplicated by everyone who requires access to a
particular compressed representation within their application. Furthermore, they can also represent a
substantial percentage of the overall execution time of the application.
Flavor addresses these problems in an integrated way. First, it allows the “formal” description of
the bitstream syntax. Formal here means that the description is based on a well-defined grammar, and
as a result is amenable to software tool manipulation. In the past, such descriptions were using ad-hoc
∗

This material is based upon work supported in part by the National Science Foundation under Grant MIPS-9703163.

1

conventions involving tabular data or pseudo-code. A second and key aspect of Flavor’s architecture
is that this description has been designed as an extension of C++ and Java, both heavily used objectoriented languages in multimedia applications development. This ensures seamless integration of Flavor
code with both C++ and Java code and the overall architecture of an application.
Flavor was designed as an object-oriented language, anticipating an audio-visual world comprised
of audio-visual objects, both synthetic and natural, and combining it with well-established paradigms
for software design and implementation. Its object-oriented facilities go beyond the mere duplication
of C++ and Java features, and introduce several new concepts that are pertinent for bitstream-based
media representation.
In order to validate the expressive power of the language, several existing bitstream formats have
already been described in Flavor, including sophisticated structures such as MPEG-2 Systems, Video
and Audio. A translator has also been developed for translating Flavor code to C++ or Java code. We
should note that Flavor is currently used in the Structured Audio as well as the Systems parts of the
MPEG-4 standard.
Emerging multimedia representation techniques can directly use Flavor to represent the bitstream
syntax in their specifications. This will allow immediate use of such specifications in new or existing
applications, since the code to access/generate conforming data can be generated directly from the
specification with zero cost. In addition, such code can be automatically optimized; this is particularly
important for operations such as Huffman decoding/encoding, a very common tool in media representation.
In the following, we first present a brief background of the language in terms of its history and
technical approach. We then describe each of its features, including declarations and constants, expressions and statements, classes, scoping rules, maps, and built-in operators. We also describe the
translator and its simple run-time API. Finally, we conclude with an overview of the benefits of using
the Flavor approach for media representation. More detailed information and publicly available software
can be found in the Flavor web site at: http://flavor.sourceforge.net. Parts of this paper have
been presented in [11, 12, 13].

2

Background

2.1

A Brief History

Flavor has its origins in a Perl script (mkvlc) [14] that was developed in early 1994 in order to automate
the (laborious) generation of C code declarations for variable-length code (VLC) tables of the MPEG-2
Video specification1 . In November 1995, the ideas behind mkvlc took a more concrete shape in the
form of a “syntactic description language,” [11, 15] i.e., a formal way to describe not just VLCs, but the
entire structure of a bitstream. Such a facility was proposed to the MPEG-4 standardization activity,
which at that time had started to consider flexible, even programmable, audio-visual decoding systems.
The language subsequently underwent a series of revisions obtaining input from several participants in
the MPEG-4 standardization activity, and its specification is now fairly stable.

2.2

Technical Approach

Flavor provides a formal way to specify how data is laid out in a serialized bitstream. It is based
on a principal of separation between bitstream parsing operations and encoding, decoding and other
operations. This separation acknowledges the fact that the same syntax can be utilized by different
tools, but also that the same tool can work unchanged with a different bitstream syntax. For example,
the number of bits used for a specific field can change without modifying any part of the application
program.
Past approaches for syntax description utilized a combination of tabular data, pseudo-code, and
textual description to describe the format at hand. Taking MPEG as an example, both MPEG-1 and
1

The mkvlc program is available at http://www.ee.columbia.edu/∼eleft/software/mkvlc.tar.gz.

2

MPEG-2 specifications were described using a C-like pseudo-code syntax (originally introduced by Milt
Anderson, Bellcore), coupled with explanatory text and tabular data. Several of the lower and most
sophisticated layers (e.g., macroblock) could only be handled by explanatory text. The text had to be
carefully crafted and tested over time for ambiguities. Other specifications (e.g., GIF and JPEG) use
similar bitstream representation schemes, and hence share the same limitations.
Other formal facilities already exist for representing syntax. One example is ASN.1 (ISO International Standards 8824 and 8825). A key difference, however, is that ASN.1 was not designed to address
the intricacies of source coding operations, and hence cannot cope with, for example, variable-length
coding. In addition, ASN.1 tries to hide the bitsream representation from the developer by using its own
set of binary encoding rules, whereas in our case the binary encoding is the actual target of description.
There is also some remote relationship between syntax description and “marshalling,” a fundamental operation in distributed systems where consistent exchange of typed data is ensured. Examples
in this category include Sun’s ONC XDR (External Data Representation) and the rpcgen compiler
which automatically generates marshalling code, as well as CORBA IDL, among others. These ensure,
for example, that even if the native representation of an integer in two systems is different (big versus
little endian), they can still exchange typed data in a consistent way. Marshalling, however, does not
constitute bitstream syntax description because: 1) the programmer does not have control over the data
representation (the binary representation for each data type is predefined), 2) it is only concerned with
the representation of simple serial structures (lists of arguments to functions, etc.). As in ASN.1, the
binary representation is “hidden” and is not amenable to customization by the developer. One could
parallel Flavor and marshalling by considering the Flavor source as the XDR layer. A better parallelism
would be to view Flavor as a parser-generator like yacc [16], but for bitstream representations.
It is interesting to note that all prior approaches to syntactic description were concerned only with
the definition of message structures typically found in communication systems. These tend to have a
much simpler structure compared with coded representations of audio-visual information (compare the
UDP packet header with the baseline JPEG specification, for example).
A new language, Bitstream Syntax Description Language (BSDL) [17, 18], has recently been
introduced in MPEG-21 [19] for describing the structure of a bitstream using XML Schema. However,
unlike Flavor, BSDL is developed to address only the high-level structure of the bitstream, and it
becomes almost impossible to fully describe the bitstream syntax on a bit-per-bit bases. For example,
BSDL does not have a facility to cope with variable-length coding, whereas in Flavor, map (described
in Section 3.5) can be used. Also, the BSDL description would be overly verbose, requiring a significant
effect to review and modify the description with human eye.
Flavor was designed to be an intuitive and natural extension of the typing system of objectoriented languages like C++ and Java. This means that the bitstream representation information is
placed together with the data declarations in a single place. In C++ and Java, this place is where a
class is defined.
Flavor has been explicitly designed to follow a declarative approach to bitstream syntax specification. In other words, the designer is specifying how the data is laid out on the bitstream, and does
not detail a step-by-step procedure that parses it. This latter procedural approach would severely limit
both the expressive power as well as the capability for automated processing and optimization, as it
would eliminate the necessary level of abstraction. As a result of this declarative approach, Flavor does
not have functions or methods.
A related example from traditional programming is the handling of floating point numbers. The
programmer does not have to specify how such numbers are represented or how operations are performed;
these tasks are automatically taken care of by the compiler in coordination with the underlying hardware
or run-time emulation libraries.
An additional feature of combining type declaration and bitstream representation is that the
underlying object hierarchy of the base programming language (C++ or Java), becomes quite naturally
the object hierarchy for bitstream representation purposes as well. This is an important benefit for ease
of application development, and it also allows Flavor to have a very rich typing system itself.
“HelloBits” - Traditionally, programming languages are introduced via a simple “Hello World!”

3

program, which just prints out this simple message on the user’s terminal. We will use a similar example
with Flavor, but here we are concerned about bits, rather than text characters. Figure 1 shows a set
of trivial examples indicating how the integration of type and bitstream representation information is
accomplished. Consider a simple object called HelloBits with just a single value, represented using
8 bits. Using the MPEG-1/2 methodology, this would be described as shown in Figure 1(a). A C++
description of this single-value object would include two methods to read and write its value, and have
a form similar to the one shown in Figure 1(b). Here getuint() is assumed to be a function that reads
bits from the bitstream (here 8) and returns them as an unsigned integer (the most significant bit first);
the putuint() function has similar functionality but for output purposes. When HelloBits::get() is
called, the bitstream is read and the resultant quantity is placed in the data member Bits. The same
description in Flavor is shown in Figure 1(c).
As we can see, in Flavor the bitstream representation is integrated with the type declaration. The
Flavor description should be read as: Bits is an unsigned integer quantity represented using 8 bits in
the bitstream. Note that there is no implicit encoding rule as in ASN.1: the rule here is embedded in
the type declaration and indicates that, when the system has to parse a HelloBits data type, it will
just read the next 8 bits as an unsigned integer and assign them to the variable Bits.
Syntax No. of bits
HelloBits {
Bits
8
}
(a)

Mnemonic
uimsbf

class HelloBits {
unsigned int Bits;
void get() {
Bits = ::getuint(8);
}
void put() {
::putuint(8, Bits);
}
};
(b)
class HelloBits {
unsigned int(8) Bits;
};
(c)
Figure 1: HelloBits. (a) Representation using the MPEG-1/2 methodology. (b) Representation using
C++ (A similiar construct would be used for Java as well). (c) Representation using Flavor.
These examples, although trivial, demonstrate the differences between the various approaches. In
Figure 1(a), we just have a tabulation of the various bitstream entities, grouped into syntactic units.
This style is sufficient for straightforward representations, but fails when more complex structures are
used (e.g., VLCs). In Figure 1(b), the syntax is incorporated into hand-written code embedded in a
get() and put() or an equivalent set of methods. As a result, the syntax becomes an integral part of
the encoding/decoding method even though the same encoding/decoding mechanism could be applied
to a large variety of similar syntactic constructs. Also, it quickly becomes overly verbose.
Flavor provides a wide range of facilities to define sophisticated bitstreams, including if-else,
switch, for, and while constructs. In contrast with regular C++ or Java, these are all included in
the data declaration part of the class, so they are completely disassociated from code that belongs to
4

class methods. This is in line with the declarative nature of Flavor, where the focus is on defining the
structure of the data, not operations on them. As we show later on, a translator can automatically
generate C++ and/or Java methods (put() and get()) that can read or write data that complies to
the Flavor-described representation.
In the following we describe each of the language features in more detail, emphasizing the differences between C++ and Java. In order to ensure that Flavor semantics are in line with both C++ and
Java, whenever there was a conflict a common denominator approach was used.

3

Language Overview

3.1
3.1.1

Declarations and Constants
Literals

All traditional C++ and Java literals are supported by Flavor. This includes integers, floating-point
numbers and character constants (e.g., ‘a’). Strings are also supported by Flavor. They are converted
to arrays, with or without a trailing ‘\0’ (null character).
Additionally, Flavor defines a special binary number notation using the prefix 0b. Numbers represented with such notation are called binary literals (or bit strings) and, in addition to the actual value,
also convey their length. For example, one can write 0b011 to denote the number 3 represented using
3 bits. For readability, a bit string can include periods every four digits, e.g., 0b0010.01. Hexadecimal
or octal constants used in the context of a bit string also convey their length in addition to their value.
Whenever the length of a binary literal is irrelevant, it is treated as a regular integer literal.
3.1.2

Comments

Both multi-line (/**/) and single-line (//) comments are allowed. The multi-line comment delimiters
cannot be nested.
3.1.3

Names

Variable names follow the C++ and Java conventions (e.g., variable names cannot start with a number).
The keywords that are used in C++ and Java are considered reserved in Flavor.
3.1.4

Types

Flavor supports the common subset of C++ and Java built-in or fundamental types. This includes char,
int, float, and double along with all appropriate modifiers (short, long, signed and unsigned).
Additionally, Flavor defines a new type called bit and a set of new modifiers, big and little. The
type bit is used to accommodate bit string variables and the new modifiers are used to indicate the
endianess of bytes. The big modifier is used to represent the numbers using big-endian byte ordering
(the most significant byte first) and the little modifier is used for the numbers represented using the
little-endian method. By default, big-endian byte ordering is assumed. Note that endianess here refers
to the bitstream representation, not the processor on which Flavor software may be running. The latter
is irrelevant for the bitstream description.
Flavor also allows declaration of new types in the form of classes (refer to Section 3.3 for more
information regarding classes). However, Flavor does not support pointers, references, casts, or C++
operators related to pointers. Structures or enumerations are not supported either, since they are not
supported by Java.
3.1.5

Declarations

Regular variable declarations can be used in Flavor in the same way as in C++ and Java. As Flavor
follows a declarative approach, constant variable declarations with specified values are allowed everywhere (there is no constructor to set the initial values). This means that the declaration ‘const int
5

a = 1;’ is valid anywhere (not just in global scope). The two major differences are the declaration of
parsable variables and arrays.
Parsable Variables
Parsable variables are the core of Flavor’s design; it is the proper definition of these variables that
defines the bitstream syntax. Parsable variables include a parse length specification immediately after
their type declaration, as shown in Figure 2. In Figure 2(a), the blength argument can be an integer
constant, a non-constant variable of type compatible to int, or a map (discussed later on) with the
same type as the variable. This means that the parse length of a variable can be controlled by another
variable. For example, the parsable variable declaration in Figure 2(b) indicates that the variable a has
the parse length of 3 bits. In addition to the parse length specification, parsable variables can also have
the aligned modifier. This signifies that the variable begins at the next integer multiple boundary of
the length argument - alength - specified within the alignment expression. If this length is omitted, an
alignment size of 8 is assumed (byte boundary). Thus, the variable a is byte-aligned and for parsing,
any intermediate bits are ignored, while for output bitstream generation the bitstream is padded with
zeroes.
As we will see later on, parsable variables cannot be assigned to. This ensures that the syntax is
preserved regardless if we are performing an input or output operation. However, parsable variables can
be redeclared, as long as their type remains the same, only the parse size is changed, and the original
declaration was not as a const. This allows one to select the parse size depending on the context (see
Expressions and Statements, Section 3.2). On top of this, they obey special scoping rules as described
in Section 3.4.
[aligned(alength)] type(blength) variable [=value];
(a)
aligned int(3) a;
(b)

aligned int(3)* a;
(c)

aligned int(3) a = 2;
(d)

Figure 2: Parsable variable. (a) Parsable variable declaration syntax. (b) Parsable variable declaration.
(c) Look-ahead parsing. (d) Declaration of a parsable variable with an expected value.

In general, the parse size expression must be a non-negative value. The special value 0 can be
used when, depending on the bitstream context, a variable is not present in the bitstream but obtains a
default value. In this case, no bits will be parsed or generated, however, the semantics of the declaration
will be preserved. The variables of type float, double, and long double are only allowed to have a
parse size equal to the fixed size that their standard representation requires (32 and 64 bits).
Look-Ahead Parsing
In several instances, it is desirable to examine the immediately following bits in the bitstream
without actually removing the bits from the input stream. To support this behavior, a ‘*’ character can
be placed after the parse size parentheses. Note that for bitstream output purposes, this has no effect.
An example of a declaration of a variable for look-ahead parsing is given in Figure 2(c).
Parsable Variables with Expected Values
Very often, certain parsable variables in the syntax have to have specific values (markers, start
codes, reserved bits, etc.). These are specified as initialization values for parsable variables. Figure 2(d)
shows an example. The example is interpreted as: a is an integer represented with 3 bits, and must have
the value 2. The keyword const may be prepended in the declaration, to indicate that the parsable
variable will have this constant value and, as a result, cannot be redeclared.
As both parse size and initial value can be arbitrary expressions, we should note that the order
of evaluation is parse expression first, followed by the initializing expression.
Arrays
Arrays have special behavior in Flavor, due to its declarative nature but also due to the desire
for very dynamic type declarations. For example, we want to be able to declare a parsable array with
different array sizes depending on the context. In addition, we may need to load the elements of an
6

array one at a time (this is needed when the retrieved value indicates indirectly if further elements of
the array should be parsed). These concerns are only relevant for parsable variables. The array size,
then, does not have to be a constant expression (as in C++ and Java), but it can be a variable as well.
The example in Figure 3(a) is allowed in Flavor.
int(5) a;
int(2) A[a];
(a)

int A[2] = {1, 2};
int A[3] = 5;
(b)

int a = 1;
int((a++)) A[(a++)] = (a++);
(c)

int(2) A[[3]] = 1;
int(4) B[[2]][3];
(d)

Figure 3: Array. (a) Declaration with dynamic size specification. (b) Declaration with initialization.
(c) Declaration with dynamic array and parse size. (d) Declaration of partial arrays.
An interesting question is how to handle initialization of arrays, or parsable arrays with expected
values. In addition to the usual brace-expression initialization, Flavor also provides a mechanism that
involves the specification of a single expression as the initializer as shown in Figure 3(b). This means
that all elements of B will be initialized with the value 5. In order to provide more powerful semantics
to array initialization, Flavor considers the parse size and initializer expressions as executed per each
element of the array. The array size expression, however, is only executed once, before the parse size
expression or the initializer expression.
Let’s look at a more complicated example in Figure 3(c). Here A is declared as an array of 2
integers. The first one is parsed with 3 bits and is expected to have the value 4, while the second is
parsed with 5 bits and is expected to have the value 6. After the declaration, a is left with the value 6.
This probably represents the largest deviation of Flavor’s design from C++ and Java declarations. On
the other hand it does provide significant flexibility in constructing sophisticated declarations in a very
compact form, and it is also in line with the dynamic nature of variable declarations that Flavor provides.
Partial Arrays
An additional refinement of array declaration is partial arrays. These are declarations of parsable
arrays in which only a subset of the array needs to be declared (or, equivalently, parsed from or written to
a bitstream). Flavor introduces a double bracket notation for this purpose. The example in Figure 3(d)
demonstrates its use. In the first line, we are declaring the 4-th element of A (array indices start from 0).
The array size is unknown at this point, but of course it will be considered at least 4. In the second line,
we are declaring a two-dimensional array, and in particular only its third row (assuming the first index
corresponds to a row). The array indices can, of course, be expressions themselves. Partial arrays can
only appear on the left-hand side of declaration and are not allowed in expressions.

3.2

Expressions and Statements

Flavor supports all of the C++ and Java arithmetic, logical and assignment operators. However, parsable
variables cannot be used as lvalues. This ensures that they always represent the bitstream’s content,
and allow consistent operations for the translator-generated get() and put() methods that read and
write, respectively, data according to the specified form. Refer to Section 4.1 for detailed information
about these methods.
Flavor also supports all the familiar flow control statements: if-else, do-while, while, and
switch. In contrast to C++ and Java, variable declarations are not allowed within the arguments of
these statements (i.e., ‘for(int i=0; ; );’ is not allowed). This is because in C++ the scope of this
variable will be the enclosing one (even though this is fixed in the new ANSI C++ standard, some
compilers still use the older concept), while in Java it will be the enclosed one. To avoid confusion, we
opted for the exclusion of both alternatives at the expense of a slightly more verbose notation. Scoping
rules are discussed in detail in Section 3.4. Similarly, Java only allows Boolean expressions as part of
the flow control statements, and statements like ‘if (1) { ... }’ is not allowed in Java. Thus, only the
flow control statements with boolean expressions are valid in Flavor.
Figure 4 shows an example of the use of these flow control statements. The variable b is declared
with a parse size of 16 if a is equal to 1, and with a parse size of 24 otherwise. Observe that this
7

construct would not be meaningful in C++ or Java as the two declarations would be considered as
being in separate scopes. This is the reason why parsable variables need to obey slightly different
scoping rules than regular variables. The way to approach this to avoid confusion is to consider that
Flavor is designed so that these parsable variables have to be properly defined at the right time and
position. All the rest of the code is there to ensure that this is the case. We can consider the parsable
variable declarations as “actions” that our system will perform at the specified times. This difference,
then, in the scoping rules becomes a very natural one.
if (a == 1) {
little int(16) b; // b is a 16 bit integer in little-endian byte ordering
} else {
little int(24) b; // b is a 24 bit integer in little-endian byte ordering
}
Figure 4: Example of a conditional expression.

3.3

Classes

Flavor uses the notion of classes in exactly the same way as C++ and Java do. It is the fundamental
structure in which object data are organized. Keeping in line with the support of both C++ and Javastyle programming, classes in Flavor cannot be nested, and only single inheritance is supported. In
addition, due to the declarative nature of Flavor, methods are not allowed (this includes constructors
and destructors as well).
Figure 5 shows an example of a simple class declaration with just two parsable member variables.
The trailing ‘;’ character is optional accommodating both C++ and Java-style class declarations. This
class defines objects which contain two parsable variables. They will be present in the bitstream in the
same order they are declared. After this class is defined, we can declare objects of this type as follows:
‘SimpleClass a;’.
class SimpleClass {
int(3) a;
unsigned int(4) b;
}; // The trailling ‘;’ is optional
Figure 5: A simple class declaration.
A class is considered parsable if it contains at least one variable that is parsable. Declaration of
parsable class variables can be prepended by the aligned modifier in the same way as parsable variables.
Class member variables in Flavor do not require access modifiers (public, protected, or private).
In essence, all such variables are considered public.
3.3.1

Parameter Types

As Flavor classes cannot have constructors, it is necessary to have a mechanism to pass external information to a class. This is accomplished using parameter types. These act the same way as formal
arguments in function or method declarations do. They are placed in parentheses after the name of the
class. Figure 6 gives an example of a simple class declaration with parameter types. When declaring
variables of parameter type classes, it is required that the actual arguments are provided in place of the
formal ones as displayed in the figure.
Of course the types of the formal and actual parameters must match. For arrays, only their
dimensions are relevant; their actual sizes are not significant as they can be dynamically varying. Note
that class types are allowed in parameter declarations as well.
8

class SimpleClass(int i[2]) {
int(3) a = i[0];
unsigned int(4) b = i[1];
};
int(2) v[2];
SimpleClass a(v);
Figure 6: A simple class declaration with parameter types.

3.3.2

Inheritance

As we mentioned earlier, Flavor supports single inheritance so that compatibility with Java is maintained. Although Java can “simulate” multiple inheritance through the use of interfaces, Flavor has no
such facility (it would be meaningless since methods do not exist in Flavor). However, for media representation purposes, we have not found any instance where multiple inheritance would be required, or
even be desirable. It is interesting to note that all existing representation standards today are not truly
object-based. The only exception, to our knowledge, is the MPEG-4 specification that explicitly addresses the representation of audio-visual objects. It is, of course, possible to describe existing structures
in an object-oriented way but it does not truly map one-to-one with the notion of objects. For example,
the MPEG-2 Video slices can be considered as separate objects of the same type, but of course their
semantic interpretation (horizontal stripes of macroblocks) is not very useful. Note that containment
formats like MP4 (MPEG-4 Systems file format) and Apple’s Quick Time are more object-oriented, as
they are composed of object-oriented structures called “atoms”.
Derivation in C++ and Java is accomplished using a different syntax (extends versus ‘:’). Here
we opted for the Java notation (also ‘:’ is used for object identifier declarations as explained below).
Unfortunately, it was not possible to satisfy both.
In Figure 7(a) we show a simple example of a derived class declaration. Derivation from a bitstream
representation point of view means that B is an A with some additional information. In other words, the
behavior would be almost identical if we just copied the statements between the braces in the declaration
of A in the beginning of B. We say ‘almost’ here because scoping rules of variable declarations also come
into play, as discussed in Section 3.4.
Note that if a class is derived from a parsable class, it is also considered parsable.
class A {
int(2) a;
}

class A:int(1) id = 0 {
int(2) a;
}

class B extends A {
int(3) b;
}
(a)

class B extends A:int(1) id = 1 {
int(3) b;
}
(b)

class slice :
...
}

aligned bit(32) slice start code = 0x00000101 ..

0x000001AF {

(c)
Figure 7: Inheritance. (a) Derived class declaration. (b) Derived class declaration with object identifiers.
(c) Class with ID range.

9

3.3.3

Polymorphic Parsable Classes

The concept of inheritance in object-oriented programming derives its power from its capability to
implement polymorphism. In other words, the capability to use a derived object in a place where an
object of the base class is expected. Although the mere structural organization is useful as well, it could
be accomplished equally well with containment (a variable of type A is the first member of B).
Polymorphism in traditional programming languages is made possible via vtable structures, which
allow the resolution of operations during run-time. Such behavior is not pertinent for Flavor, as methods
are not allowed.
A more fundamental issue, however, is that Flavor describes the bitstream syntax: the information
with which the system can detect which object to select must be present in the bitstream. As a result,
traditional inheritance as defined in the previous section does not allow the representation of polymorphic
objects. Considering Figure 7(a), there is no way to figure out, by reading a bitstream, if we should
read an object of type A or type B.
Flavor solves this problem by introducing the concept of object identifiers or IDs. The concept
is rather simple: in order to detect which object we should parse/generate, there must be a parsable
variable that will identify it. This variable must have a different expected value for any class derived
from the originating base class, so that object resolution can be uniquely performed in a well-defined
way (this can be checked by the translator). As a result, object ID values must be constant expressions
and they are always considered constant, i.e., they cannot be redeclared within the class.
In order to signify the importance of the ID variables, they are declared immediately after the
class name (including any derivation declaration) and before the class body. They are separated from
the class name declaration using a colon (‘:’). We could rewrite the example of Figure 7(a) with IDs as
shown in Figure 7(b). Upon reading the bitstream, if the next 1 bit has the value 0, an object of type
A will be parsed; if the value is 1, then an object of type B will be parsed. For output purposes, and
as will be discussed in Section 4, it is up to the user to set up the right object type in preparation for
output.
The name and the type of the ID variable is irrelevant, and can be anything that the user chooses.
It cannot, however, be an array or a class variable (only built-in types are allowed). Also, the name, type
and parse size must be identical between the base and derived classes. However, object identifiers are
not required for all derived classes of a base class that has a declared ID. In this case, only the derived
classes with defined IDs can be used wherever the base class can appear. This type of polymorphism
is already used in the MPEG-4 Systems specification, and in particular the Binary Format for Scenes
(BIFS) [20]. This is a VRML-derived set of nodes that represent objects and operations on them, thus
forming a hierarchical description of a scene.
The ID of a class is also possible to have a range of possible values which is specified as start id
. . . end id, inclusive of both bounds. See Figure 7(c) for example.

3.4

Scoping Rules

The scoping rules that Flavor uses are identical with C++ and Java with the exception of parsable
variables. As in C++ and Java, a new scope is introduced with curly braces ({}). Since Flavor does not
have functions or methods, a scope can either be the global one or a scope within a class declaration.
Note that the global scope cannot contain any parsable variable, since it does not belong to any object.
As a result, global variables can only be constants.
Within a class, all parsable variables are considered as class member variables, regardless of the
scope they are encountered in. This is essential in order to allow conditional declarations of variables
which will almost always require that the actual declarations occur within compound statements (see
Figure 4). Non-parsable variables that occur in the top-most class scope are also considered class member
variables. The rest live within their individual scopes.
This distinction is important in order to understand which variables are accessible to a class
variable that is contained in another class. The issues are illustrated in Figure 8. Looking at the class
A, the initial declaration of i occurs in the top-most class scope; as a result i is a class member. The
10

variable a is declared as a parsable variable, and hence it is automatically a class member variable. The
declaration of j occurs in the scope enclosed by the if statement; as this is not the top-level scope, j
is not a class member. The following declaration of i is acceptable; the original one is hidden within
that scope. Finally, the declaration of the variable a as a non-parsable would hide the parsable version.
As parsable variables do not obey scoping rules, this is not allowed (hiding parsable variables of a base
class, however, is allowed). Looking now at the declaration of the class B which contains a variable of
type A, it becomes clear which variables are available as class members.
class A {
int i = 1;
int(2) a;
if (a == 2) {
int j = i;
int i = 2; // Hides i, ok
int a; // Hides a, error
}
}

class B {
A a;
a.j = 1; // Error, j not a class member
int j = a.a + 1; // Ok
j = a.i + 2 // Ok
int(3) b;
}

Figure 8: Scoping rules example.
In summary, the scoping rules have the following two special considerations. Parsable variables
do not obey scoping rules and are always considered class members. Non-parsable variables obey the
standard scoping rules and are considered class members only if they are at the top-level scope of the
class.
Note that parameter type variables are considered as having the top-level scope of the class. Also,
they are not allowed to hide the object identifier, if any.

3.5

Maps

Up to now, we have only considered fixed-length representations, either constant or parametric. A wide
variety of representation schemes, however, rely heavily on entropy coding, and in particular Huffman
codes [1]. These are variable-length codes (VLCs) which are uniquely decodable (no codeword is the
prefix of another). Flavor provides extensive support for variable-length coding through the use of maps.
These are declarations of tables in which the correspondence between codewords and values is described.
Figure 9(a) gives a simple example of a map declaration. The map keyword indicates the declaration of a map named A. The declaration also indicates that the map converts from bitstring values
to values of type int. The type indication can be a fundamental type, a class type, or an array. Map
declarations can only occur in global scope. As a result, an array declaration will have to have a constant size (no non-constant variables are visible at this level). After the map is properly declared, we
can define parsable variables that use it by indicating the name of the map where we would put the
parse size expression as follows: int(A) i. As we can see the use of variable-length codes is essentially
identical to fixed-length variables. All the details are hidden away in the map declaration.
The map contains a series of entries. Each entry starts with a bit string that declares the
codeword of the entry followed by the value to be assigned to this codeword. If a complex type
is used for the mapped value, then the values have to be enclosed in curly braces. Figure 9(b)
shows the definition of a VLC table with a user-defined class as output type. The type of the variable has to be identical to the type returned from the map. For example, using the declaration YUVblocks(blocks per component) chroma format; - we can access a particular value of the map
using the construct: chroma format.Ublocks.
As Huffman codeword lengths tend to get very large when their number increases, it is typical
to specify “escape codes,” signifying that the actual value will be subsequently represented using a
fixed-length code. To accommodate these as well as more sophisticated constructs, Flavor allows the
use of parsable type indications in map values. This means that, using the example in Figure 9(a), we
11

map A(int) {
0b0, 1,
0b01, 2
}
(a)
map A(int) {
0b0, 1,
0b01, 2,
0b001, int(5)
}
(c)

// The output type of a map is defined in a class
class YUVblocks {
unsigned int Yblocks;
unsigned int Ublocks;
unsigned int Vblocks;
}
// A table that relates the chroma format with
// the number of blocks per signal component
map blocks per component (YUVblocks) {
0b00, {4, 1, 1}, // 4:2:0
0b01, {4, 2, 2}, // 4:2:2
0b10, {4, 4, 4} // 4:4:4
}
(b)

Figure 9: Map. (a) A simple map declaration. (b) A map with defined output type. (c) A map
declaration with extension.

can write the example in Figure 9(c). This indicates that, when the bit string 0b001 is encountered
in the bitstream, the actual return value for the map will be obtained by parsing 5 more bits. The
parse size for the extension can itself be a map, thus allowing the cascading of maps in sophisticated
ways. Although this facility is efficient when parsing, the bitstream generation operation can be costly
when complex map structures are designed this way. None of today’s specifications that we are aware
of require anything beyond a single escape code.
The translator can check that the VLC table is uniquely decodable, and also generate optimized
tables for extremely fast encoding/decoding using our hybrid approach as described in Section 4.6.

3.6

Built-In Operators

Operators are built-in functions that are made available to the Flavor programmer in order to facilitate certain frequently appearing data manipulations. These operators are the only functions that are
available in the current version of Flavor.
3.6.1

lengthof()

The lengthof() operator is used to obtain the parsed length of a parsable variable. The general syntax
is as follows: ‘lengthof(var);’ where var must be a parsable variable of any type that has been
previously declared. The result of the operator is treated as an integer.
Since parsable variables can be declared more than once, the operator considers only the last
instance of the variable that has been declared (parsed from the bitstream). The following (Figure 10)
is an example of the use of the operator.
int(5) i = 3;
...
int(3) j = lengthof(i);
(a)

int i = 1;
int(i++) a[5];
int j = lengthof(a[4]);
(b)

Figure 10: lengthof(). (a) A simple example. (b) A more complex example where a multi-dimensional
array is used.
In Figure 10(b), we declare an one-dimensional array a with five elements. The variable j is set
12

with the length of the last (4-th) element. It is easy to see that the length of this element is going to be
5.
In a declaration such as ‘aligned class A{}’, the bits skipped for alignment are not accounted
for by the lengthof() operator. This is true for simple variables as well. These bits, however, are
counted for the enclosing class.
3.6.2

isidof()

The isidof() operator is used to check if the value of a varible is among the IDs of a polymorphic
class. The general syntax is as follows: ‘isidof(class name, var);’ where class name is the name
of a polymorphic class that has been previously declared, and var is the name of a simple variable.
The result of the operator is treated as an integer, and it is 1 if the value of var is among the IDs of
class name or 0, otherwise.
This operator was introduced to accommodate a coding structure in which the syntax was expressed as: pase as many objects of a particular type as you can from the bitstream. This corresponds
to examining the following bits on the bitstream and, if they correspond to an object of the given type,
parsing it; otherwise the syntax would continue to the next constrcut. Without this operator, the programmer would have to explicitly construct a switch statement or a series of if-then-else statements,
checking against all IDs of the class. This not only would be tiresome, but would also be a source of
errors if one of the IDs were not included.
The following is an example of the use of this operator for parsing the above-mentioned constructs.
abstract class A : int(8) id = 0 {
...
}
...
int(8)* id;
int i;
while (isidof(A, id)==1) {
A a[[i++]];
int(8)* id;
}
Figure 11: An example of using the isidof() operator.
In Figure 11, we declare an (abstract) class A, with presumably a number of derived classes (not
show here). The while loop following the declaration of A examines the next 8 bits of the bitstream. If
they correspond to an ID of one of the classes derived from A then the object is parsed; if not, the code
continues.

4

The Flavor Translator

Designing a language like Flavor would be an interesting but academic exercise, unless it was accompanied by software that can put its power into full use. We have developed a translator that evolved
concurrently with the design of the language. When the language specification became stable, the
translator was completely rewritten. The most recent release is publicly available for downloading at
http://www.sourceforge.net/projects/flavor.

4.1

Run-Time API

The translator reads a Flavor source file (.fl) and, depending on the language selection flag, it generates
a pair of .h and .cpp files (for C++) or a set of .java files (for Java). In the case of C++, the .h
file contains the declarations of all Flavor classes as regular C++ classes and the .cpp file contains
13

the implementations of the corresponding class methods (put() and get()). In the case of Java, each
.java file contains the declaration and implementation of a single Flavor class. In both cases, the get()
method is responsible for reading a bitstream and loading the class variables with their appropriate
values, while the put() method does the reverse. All the members of the classes are declared public,
and this allows direct access to desired fields in the bitstream.
The translator makes minimal assumptions about the operating environment for the generated
code. For example, it is impossible to anticipate all possible I/O structures that might be needed by
applications (network-based, multi-threaded, multiple buffers, etc.). Attempting to provide a universal
solution would be futile. Thus, instead of having the translator directly output the required code for
bitstream I/O, error reporting, tracing, etc., a run-time library is provided. With this separation,
programmers have the flexibility of replacing parts of, or the entire library with their own code. The
only requirement is that the customized code provides an identical interface to the one needed by the
translator. This interface is defined in a pure virtual class called IBitstream. Deriving from the
provided IBitstream class will ensure compatibility with the translator. Additionally, as the source
code for the library is included in its entirety, customization can be performed quite easily. The Flavor
package also provides information on how to rebuild the library, if needed.
The run-time library includes the Bitstream class that is derived from the IBitstream interface,
and provides basic bitstream I/O facilities in terms of reading or writing bits from a binary file. A
Bitstream reference is passed as an argument to the get() and put() methods.
If parameter types are used in a class, then they are also required arguments in the get() and
put() methods as well. The translator also requires that a function is available to receive calls when
expected values are not available or VLC lookups fail. The function name can be selected by the user;
a default implementation (flerror) is included in the run-time library.
For efficiency reasons, Flavor arrays are converted to fixed size arrays in the translated code. This
is necessary in order to allow developers to access Flavor arrays without needing special techniques.
Whenever possible, the translator automatically detects and sets the maximum array size; it can also
be set by the user using a command-line option. Finally, the run-time library (and the translator) only
allows parse sizes of up to the native integer size of the host processor (except for double values). This
enables fast implementation of bitstream I/O operations.
For parsing operations, the only task required by the programmer is to declare an object of the
class type at hand, and then call its get() method with an appropriate bitstream. While the same is
also true for put() operation, the application developer must also load all class member variables with
their appropriate values before the call is made.

4.2

Include and Import Directives

In order to simplify the source code organization, Flavor supports %include and %import directives.
These are the mechanisms to combine several different source code files into one entity, or to share a
given data structure definition across different projects.
4.2.1

Include Directive

The statement - %include "file.fl" - will include the specified .fl file in the current position and
will flag all of its content so that no code is generated. Figure 12(a) displays a .fl file (other.fl) that
is included by another .fl file (main.fl). The other.fl file contains the definition of the constant
a. The inclusion makes the declaration of the a variable available to the main.fl file. In terms of the
generated output, Figure 12(b) outlines the placement of information in different files. In the figure,
we see that the main and included files each keep their corresponding implementations. The generated
C++ code maintains this partitioning, and makes sure that the main file includes the C++ header file
of the included Flavor file.
The %include directive is useful when data structures need to be shared across modules or
projects. It is similar in spirit to the use of the C/C++ preprocessor #include statement in the
sense that it is used to make general information available at several different places in a program. Its
14

operation, however, is different as Flavor’s %include statement does not involve code generation for the
included code. In C/C++, #include is equivalent to copying the included file in the position of the
#include statement. This behavior is offered in Flavor by the %import directive.
Similarly, when generating the Java code, only the .java files corresponding to the currently
processed Flavor file are generated. The data in the included files are allowed to be used, but they are
not generated.
// In the file, other.fl
const int a = 4;
// In the file, main.fl
%include "other.fl"
class Test {
int(a) t; // The variable ’a’ is included from the other.fl file
}
(a)
// In the file, other.h
extern const int a;

// In the file, other.cpp
#include "other.h"
const int a = 4;
(b)

// In the file, main.h
#include "other.h"
...

Figure 12: The %include directive. (a) The other.fl file is included by the main.fl file. (b) The
other.h and other.cpp files are generated from the other.fl file whereas the main.h file is generated
from the main.fl file.

4.2.2

Import Directive

The %import directive behaves similarly to the %include directive, except that full code is generated for
the imported file by the translator, and no C++ #include statement is used. This behavior is identical
to how a C++ preprocesor #include statement would behave in Flavor.
%import "other.fl"
class Test {
int(a) t; // The variable ’a’ is included from the other.fl file
}
(a)
// In the file, main.h
extern const int a;
...

// In the file, main.cpp
const int a = 4;
...
(b)

Figure 13: The %import directive. (a) The main.fl file using the %import directive. (b) The main.h
and main.cpp files generated from the main.fl file defined in (a).
Let’s consider the example of the previous section, this time with an %import directive rather
than an %include one as shown in Figure 13(a). As can be seen from Figure 13(b), the generated code
includes the C++ code corresponding to the imported .fl file. Therefore, using the %import directive
is exactly the same as just copying the code in the imported .fl file and pasting it in the same location
15

as the %import statement is specified. The translator generates the Java code in the same way.
Note that the Java import statement behaves more like Flavor’s %include statement, in that no
code generation takes place for the imported (included) code.

4.3

Pragma Statements

Pragma statements are used as a mechanism for setting translator options from inside a Flavor source
file. This allows modification of translation parameters (set by the command-line options) without
modifying the makefile that builds the user’s program, but more importantly, it allows very fine control
on which translation options are applied to each class, or even variable. Almost all command-line options
have pragma equivalents. The ones excluded were not considered useful for specification within a source
file.
Pragma statements are introduced with the %pragma directive. It can appear wherever a statement
or declaration can. It can contain one or more settings, separated by commas, and it cannot span more
than one line. After a setting is provided, it will be used for the remainder of the Flavor file, unless
overridden by a different pragma setting. In other words, pragma statements do not follow the scope
of Flavor code. A pragma that is included in a class will affect not only the class where it is contained,
but all classes declared after it. An example is provided in Figure 14.
// Activate both put and get, generate tracing code, and set array size to 128
%pragma put, get, trace, array=128
class Example {
%pragma noput // No put() method needed
unsigned int(10) length;
%pragma array=1024 // Switch array size to 1024
char(3) data[length];
%pragma array=128 // Switch array size back to 128
%pragma trace="Tracer.trace" // Use custom tracer
}
// The above settings are still active here!
Figure 14: Some examples of using pragma statements to set the translator options at specific locations.
In this example, we start off setting the generation of both get() and put() methods, enabling
tracing and setting the maximum array size to 128 elements. Inside the Example class, we disable the
put() method output. This class reads a chunk of data, which is preceded by its size (length, a 10-bit
quantity). This means that the largest possible buffer size is 1024 elements. Hence for the data array
that immediately follows, we set the array size to 1024, and then switch it back to the default of 128.
Finally, at the end of the class we select a different tracing function name; this function is really a
method of a class, but this is irrelevant for the translator. Since this directive is used when the get()
method code is produced, it will affect the entire class despite the fact that it is declared at its end.
Note that these pragma settings remain in effect even after the end of the Example class.

4.4

Verbatim Code

In order to further facilitate integration of Flavor code with C++/Java user code, the translator supports
the notion of verbatim code. Using special delimiters, code segments can be inserted in the Flavor source
code, and copied verbatim at the correct places in the generated C++/Java file. This allows, for example,
the declaration of constructors/destructors, user-specified methods, pointer member variables for C++,
16

etc. Such verbatim code can appear wherever a Flavor statement or declaration is allowed.
class GIF87a {
char(8) GIFsignature[6] = "GIF87a"; // GIF signature
%g{ print(); %g}
ScreenDescriptor sd; // A screen descriptor
// One or more image descriptors
do {
unsigned int(8) end;
if (end == ’,’) { // We found an image descriptor
ImageDescriptor id;
}
if (end == ’!’) { // We found an extension block
ExtensionBolck eb;
}
// Everything else is ignored
} while (end != ’;’); // ’;’ is the end-of-data marker
%.c{
void print() { ... }
%.c}
%.j{
void print() { ... }
%.j}
}
Figure 15: A simple Flavor example: the GIF87a header. The usage of verbatim code is illustrated.
The delimiters %{ and %} can be used to introduce code that should go to the class declaration
itself (or the global scope). The delimiters %p{ and %p}, and %g{ and %g} can be used to place code
at exactly the same position they appear in the put() and get() methods, respectively. Finally, the
delimiters %*{ and %*} can be used to place code in both put() and get() methods. To place code
specific to C++ or Java, .c or .j can be placed before the braces in the delimiters, respectively. For
example, a verbatim code to be placed in the get() method of the Java code will be delimited with
%g.j{ and %g.j}.
The Flavor package includes several samples on how to integrate user code with Flavor-generated
code, including a simple GIF parser. Figure 15 shows a simple example that reads the header of a
GIF87a file and prints its values. The print statement which prints the values of the various elements
is inserted as verbatim code in the syntax (within %g{ and %g} markers, since the code should go in the
get() method). The implementation of the print method for C++ code is declared within %.c{ and
%.c}, and for Java, the corresponding implemenation is defined within %.j{ and %.j}. The complete
sample code can be found in the Flavor package.

4.5

Tracing Code Generation

We also included the option to generate bitstream tracing code within the get() method. This allows
one to very quickly examine the contents of a bitstream for development and/or debugging purposes
by creating a dump of the bitstream’s content. With this option, and given the syntax of a bitstream
described in Flavor, the translator will automatically generate a complete C++/Java program that can
17

verify if a given bitstream complies with that syntax or not. This can be extremely useful for codec
development as well as compliance testing.

4.6

Map Processing

Map processing is one of the most useful features of Flavor, as hand-coding VLC tables is tedious and
error prone. Especially during the development phase of a representation format, when such tables are
still under design, full optimization within each design iteration is usually not performed. By using the
translator, such optimization is performed at zero cost. Also, note that maps can be used for fixed-length
code mappings just by making all codewords have the same length. As a result, one can very easily
switch between fixed and variable-length mappings when designing a new representation format.
When processing a map, the translator first checks that it is uniquely decodable, i.e., no codeword
is the prefix of another. It then constructs a class declaration for that map, which exposes two methods:
getvlc() and putvlc(). These take as arguments a bitstream reference as well as a pointer to the
return type of the map. The getvlc() method is reponsible for decoding a map entry and returning
the decoded value, while the putvlc() method is responsible for the output of the correct codeword.
Note that the defined class does not perform any direct bitstream I/O itself, but uses the services of
the Bitstream class instead. This ensures that a user-supplied bitstream I/O library will be seamlessly
used for map processing.
According to Fogg’s survey on software and hardware VLC architectures [21], fast software decoding methods usually exploit a variable-size look-ahead window (multi-bit lookup) with lookup tables.
For optimization, the look-ahead size and corresponding tables can be customized for position dependency in the bitstream. For example, for MPEG video, the look-ahead can be selected based on the
picture type (I, P, or B).
One of the fastest decoding methods is comprised of one huge lookup table where every codeword
represents an index of the table pointing to the corresponding value. However, this costs too much
memory. On the other end of the spectrum, one of the most memory efficient algorithms would be of
the form of a binary tree. The tree is traversed one bit at a time, and at each stage one examines if a
leaf node is reached; if not, the left or right branch is taken for the input bit value of 0 or 1, respectively.
Though efficient in memory, this algorithm is extremely slow, requiring N (the bit length of the longest
codeword) stages of bitstream input and lookup.
In [13], we adopted a hybrid approach that maintains the space efficiency of binary tree decoding,
and most of the speed associated with lookup tables. In particular, instead of using lookup tables, we use
hierarchical, nested switch statements. Each time the read-ahead size is determined by the maximum of
a fixed step size and the size of the next shortest code. The fixed step size is used to avoid degeneration
of the algorithm into binary tree decoding. The benefit of this approach is that only complete matches
require case statements, while all partial matches can be grouped into a single default statement (that,
in turn, introduces another switch statement).
With the above-mentioned approach, the space requirement consists of storage of the case values
and the comparison code generated by the translator (this code consists of just 2 instructions on typical
CISC systems, e.g., a Pentium). While slightly larger than a simple binary tree decoder, this overhead
still grows linearly with the number of code entries (rather than exponentially with their length). This
is further facilitated by the selection of the step size. When the incremental code size is small, multiple
case statements may be assigned to the same codeword, thus increasing the space requirements.
In [13], we compared the performance of various techniques, including binary tree parsing, fixed
step full lookups with different step sizes and our hybrid switch statement approach. In terms of time,
our technique is faster than a hierarchical full-lookup approach with identical step sizes. This is because
switching consumes little time compared to fixed-step’s function lookups. Furthermore, it is optimized
by ordering the case statements in terms of the length of their codeword. As shorter lengths correspond
to higher probabilities, this minimizes the average number of comparisons per codeword.
With Flavor, developers can be assured of extremely fast decoding with minimal memory requirement due to the optimized code generation. In addition, the development effort and time in creating
software to process VLCs is nearly eliminated.
18

5

Concluding Remarks

Flavor’s design was motivated by our belief that content creation, access, manipulation and distribution
will become increasingly important for end-users and developers alike. New media representation forms
will continue to be developed, providing richer features and more functionalities for end-users. In order
to facilitate this process, it is essential to bring syntactic description on par with modern software development practices and tools. Flavor can provide significant benefits in the area of media representation
and multimedia application development at several levels.
First, it can be used as a media representation documenting tool, substituting ad-hoc ways of
describing a bitstream’s syntax with a well-defined and concise language. This by itself is a substantial
advantage for defining specifications, as a considerable amount of time is spent to ensure that such
specifications are unambiguous and bug-free.
Second, a formal media representation language immediately leads to the capability of automatically generating software tools, ranging from bitstream generators and verifiers, as well as a substantial
portion of an encoder or decoder.
Third, it allows immediate access to the content by any application developer, for such diverse
use as editing, searching, indexing, filtering, etc.
With appropriate translation software, and a bitstream representation written in Flavor, obtaining
access to such content is as simple as cutting and pasting the Flavor code from the specification into an
ASCII file, and running the translator.
Flavor, however, does not provide facilities to specify how full decoding of data will be performed
as it only addresses bitstream syntax description. For example, while the data contained in a GIF
file can be fully described by Flavor, obtaining the value of a particular pixel requires the addition of
LZW decoding code that must be provided by the programmer. In several instances, such access is not
necessary. For example, a number of tools have been developed to do automatic indexing, searching and
retrieval of visual content directly in the compressed domain for JPEG and MPEG content (see [22, 23]).
Such tools only require parsing of the coded data so that DCT coefficients are available, but do not
require full decoding. Also, new techniques, such as MPEG-7, will provide a wealth of information about
the content without the need to decode it. In all these cases, parsing of the compressed information
may be the only need for the application at hand.
Finally, Flavor can also be used to redefine the syntax of content in both forward and backward
compatible ways. The separation of parsing from the remaining code/decoding operations allows its
complete substitution as long as the interface (the semantics of the previously defined parsable variables)
remains the same. Old decoding code will simply ignore the new variables, while newly written encoders
and decoders will be able to use them. Use of Java in this repect is very useful; its capability to download
new class definitions opens the door for such downloadable content descriptions that can accompany the
content itself (similar to self-extracting archives). This can eliminate the rigidity of current standards,
where even a slight modification of the syntax to accommodate new techniques or functionalities render
the content useless in non-flexible but nevertheless compliant decoders.
The authors gratefully acknowledge Olivier Avaro (France Telecom), Carsten Herpel (Thomson
Multimedia), and Jean-Claude Dufourd (ENST) for their contributions in the Flavor specification during the development of the MPEG-4 standard. We would also like to acknowledge Yihan Fang, who
implemented early versions of the Flavor translator.

References
[1] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, 1991.
[2] CompuServe Inc. Graphics Interchange Format, 1987 and 1989.
[3] ISO/IEC 10918 International Standard (JPEG). Information technology – Digital compression and
coding of continuous-tone still images, 1994.

19

[4] ISO/IEC 11172 International Standard (MPEG-1). Information technology – Coding of moving
pictures and associated audio for digital storage media at up to about 1,5 Mbits/s, 1993.
[5] ISO/IEC 13818 International Standard (MPEG-2). Information technology – Generic coding of
moving pictures and associated audio information, 1996.
[6] B. G. Haskell, A. Puri, and A. N. Netravali. Digital Video: An Introduction to MPEG-2. Chapman
and Hall, 1997.
[7] ISO/IEC 14496 International Standard (MPEG-4). Information technology – Coding of audio-visual
objects, 1999.
[8] Signal Processing: Image Communication, volume 15 no. 4–5 of Tutorial Issue on the MPEG-4
Standard, January 2000.
[9] B. Stroustrup. The C++ Programming Language. Addison-Wesley, 2nd edition, 1993.
[10] K. Arnold, J. Gosling, and D. Holmes. The Java Programming Language. Addison-Wesley, 3rd
edition, 1996.
[11] Y. Fang and A. Eleftheriadis. “A Syntactic Framework for Bitstream-level Representation of AudioVisual Objects”. In 3rd IEEE International Conference on Image Processing, Proceedings, pages
II.426–II.432, Lausanne, Switzerland, September 1996.
[12] A. Eleftheriadis. “Flavor: A Language for Media Representation”. In ACM International Conference on Multimedia, Proceedings, Seattle, WA, USA, November 1997.
[13] Y. Fang and A. Eleftheriadis. “Automatic Generation of Entropy Coding Programs Using Flavor”.
In IEEE 2nd Workshop on Multimedia Signal Processing, Proceedings, pages 341–346, Redondo
Beach, CA, USA, December 1998.
[14] A. Eleftheriadis. mkvlc: A Variable Length Code Table Compiler. Columbia University, May 1994.
[15] A. Eleftheriadis. A Syntactic Description Language for MPEG-4. ISO/IEC JTC1/SC29/WG11
M546, Dallas, November 1995.
[16] J. Levine, T. Mason, and D. Brown. lex & yacc. O’Reilly, 2nd edition, 1992.
[17] S. Devillers and M. Caprioglio. Bitstream Syntax Description Language (BSDL).
JTC1/SC29/WG11 M7433, Sydney, July 2001.

ISO/IEC

[18] S. Devillers, M. Amielh, and T. Planterose. Bitstream Syntax Description Language (BSDL).
ISO/IEC JTC1/SC29/WG11 M8273, Fairfax, May 2002.
[19] ISO/IEC JTC1/SC29/WG11 N4801, Fairfax. MPEG-21 Overview v.4, May 2002.
[20] ISO/IEC 14496-1 International Standard. Information technology – Coding of audio-visual objects
– Part 1: Systems, 2001.
[21] C. Fogg. “Survey of Software and Hardware VLC Architectures”. In SPIE Vol. 2186 Image and
Video Compression, 1994.
[22] J. R. Smith and S. F. Chang. “VisualSEEk: A Fully Automated Content-Based Image Query System”. In ACM International Conference on Multimedia, Proceedings, Boston, MA, USA, November
1996.
[23] S. W. Smoliar and H. Zhang. “Content-Based Video Indexing and Retrieval”. IEEE Multimedia
Magazine, Summer 1994.

20

