%
% XmStrings.tex -- Documents the XmString mechanism
%
% (c) 1996 The Hungry Programmers
% (c) 1996 Harald Albrecht (albrecht@igpm.rwth-aachen.de)
% See the file PUBLIC for details.
%
\chapter[Inside XmStrings]{Inside XmStrings\\}
\by{Chris Toshok\\Harald Albrecht}

\section{Introduction}
This chapter gives a cursory explanation of the way XmStrings are
encoded in \Motif{} 1.2 (and \LessTif{}).  This information is still
being discovered, so explanations of where it is wrong are welcome.

\index{ASN}%
\index{Abstract Syntax Notation}%
Sometime last year on the \LessTif{} mailing list, a well known SGI
persona, Doug Rand, sent an email that described the things that were
changed from 1.2 to 2.0.  One of the things he mentioned was that the
encoding rules for the external representation of XmStrings can no
longer be considered to be in ASN.1 format (ASN means ``Abstract
Syntax Notation Number One''). If you wonder why there is a full stop
in the acronym -- there's a simple reason for it. First written as ``ASN1''
many people just misread it as ASNI (note the letter ``I'' and not the
digit ``1'' at the end). And this rapidly mutated into ANSI, what was
probably not meant at all. So the OSI wrote it with a full stop and
no-one every confused it with the ANSI anymore.

\section{Get Ready for the Acronyms}

If you don't care where the rules come from, or what they are for, you
can skip this section.

I happen to work in the telecommunications industry, and I have
experience with ASN.1 and related standards as defined by the ITU
(others know these standards either through the ISO or from RFC's).
ASN.1 is used by the GDMO (roughly, ``Guidelines for the Development
of Managed Objects'' -- there are several ways I know of to decompose
that acronym) to describe MIBs (Management Information Bases). The
``Simple Network Management Protocol'' (SNMP) for example works with a
MIB describing various aspects of a networked device (like network
cards, routing tables, and IP addresses).

\index{BER}%
\index{Basic Encoding Rules}%
Basically, ASN.1 is a way to describe data types in a machine
independent way from a text description (something like XDR -- the
eXternal Data Representation used by ONC/RPC. Go and find out yourself
what the latter is).  Vaguely associated with ASN.1 are sets of
encoding rules, such as BER (or Basic Encoding Rules) which describe
how to actually create external representations of data.  There are
other encoding rules (e.g., FER), but you've had enough acronyms for
now.  ASN.1 is really a very powerful tool -- you may want to learn
more about it on your own.

\section{How It Works}

\index{TLV}%
\index{tag/length/value}%
Ok, enough of the background.  Let's see how it works in practice. The
basic idea is to describe data elements as a three piece combination:
tag/length/value, sometimes referred to as TLV.  You basically have:
\begin{itemlist}
\item a tag, which describes what type of data this is,
\item a length, which says how long the following value is,
\item and a value, which is basically an octet (or byte) sequence
that describes the value.
\end{itemlist}

The basic unit of information is the octet (or byte): 8 bits of
information.  You can see how 8 bits might be a little small to
describe large strings -- more on that later.  One thing that must be
noted is that TLVs can be nested, that is, the value part of a TLV
tuple can contain TLVs.

I'm going to skip a full description of BER and just report the basics
of how they relate to \code{XmString}s.  Let's take a trivial example:

\begin{verbatim}
    xmstr = XmStringCreateLtoR("Hello\nWorld", XmFONTLIST_DEFAULT_TAG);
\end{verbatim}

The first thing to notice is the
\code{XmFONTLIST\_DEFAULT\_TAG}. That's a clue to \Motif{} that the
string passed in is represented in the current locale (I'm not even
going to try to talk about NLS -- look elsewhere for what locale
means).  The second thing to notice is that we used
\code{XmStringCreate\-LtoR}, which means the function should be aware of
separators (normally, this means ``look for newlines'').  So \Motif{}
would parse that as ``\code{Hello}'' (locale text),
``\code{\bslash{}n}'' (separator in this locale), and ``\code{World}''
(locale text).

\codeindex{XmSTRING\_COMPONENT\_UNKNOWN}%
\codeindex{XmSTRING\_COMPONENT\_CHARSET}%
\codeindex{XmSTRING\_COMPONENT\_TEXT}%
\codeindex{XmSTRING\_COMPONENT\_DIRECTION}%
\codeindex{XmSTRING\_COMPONENT\_SEPARATOR}%
\codeindex{XmSTRING\_COMPONENT\_LOCALE\_TEXT}%
\begin{table}[h]\begin{center}\begin{tabular}[h]{|l|c|}
\hline
Identifier & Value\\
\hline
\code{XmSTRING\_COMPONENT\_UNKNOWN} & \code{0x00} \\
\code{XmSTRING\_COMPONENT\_CHARSET} & \code{0x01} \\
\code{XmSTRING\_COMPONENT\_TEXT} & \code{0x02} \\
\code{XmSTRING\_COMPONENT\_DIRECTION} & \code{0x03} \\
\code{XmSTRING\_COMPONENT\_SEPARATOR} & \code{0x04} \\
\code{XmSTRING\_COMPONENT\_LOCALE\_TEXT} & \code{0x05} \\
\hline
\end{tabular}%
{\caption{\label{xmstring_tag_ids}Component identifiers for \code{XmString}s.}}%
\vspace*{-0.4cm}
\end{center}\end{table}

Let's look at what Motif does tell us about encodings -- each
\code{XmString} component has a different identifier (see figure
\ref{xmstring_tag_ids}). Hmm, these could be the tag part of the TLVs!
Given that, the \code{XmString} that \Motif{} 1.2 generates is the
following (in hex and chars, with the \code{0x} prefix removed from
the hex):
\begin{verbatim}
   DF 80 06 10 05 05 'H' 'e' 'l' 'l' 'o' 04 00 05 05 'W' 'o' 'r' 'l' 'd'
\end{verbatim}
which makes absolutely no sense when you look at it that way. Try this:

\begin{table}[h]\begin{center}\begin{tabular}[h]{p{4.5cm}l}
\code{0xDF 0x80} & this is a \Motif{} string (essentially) \\
\ind{1}\code{0x06 0x10} & \ind{1}which contains a 16 byte \code{XmString} \\
\ind{2}\code{0x05 0x05} & \ind{2}which contains 5 bytes of locale text\\
\ind{3}``\code{Hello}'' & \ind{3}which has the value ``\code{Hello}'' \\
\ind{2}\code{0x04 0x00} & \ind{2}and a separator \\
\ind{3}-- \emph{nothing} -- & \ind{3}which has no data (never does) \\
\ind{2}\code{0x05 0x05} & \ind{2}and 5 more bytes of locale text\\
\ind{3}``\code{World}'' & \ind{3}which has the value ``\code{World}''
\end{tabular}\vspace*{-0.4cm}\end{center}\end{table}

The first number (on lines that have them) is the tag; the second
number is the length. You can see that this description shows how TLVs
can be nested.  Look at it this way; if I just describe the string
above structurally, it comes out as (using parentheses as an indicator
of nesting): TLV=(TLV=(TLV,TLV,TLV)).

The first tag value \code{0xDF} identifies every
\code{XmString}. While this value seems arbitrary at the first glance it makes
some sense. The tag value can be decomposed into three separate fields
as shown below.

\begin{figure}[h]
\hskip\leftmargin\includegraphics[scale=1.09]{TAG_val}
\end{figure}

The most significant bits 7 and 6 indicate that this is a private tag
class, thus the bits 4 to 0 are just set to an arbitrary value. The
``F'' flag (bit 5) indicates that this is a simple tag encoding and
not a composed one. Ok, after this you're scratching your head once
again.  Where does the next value \code{0x80} (the first length) fit in?
Remember how I said that 8 bits was a little small for describing
lengths?  Well, that's where BER kicks in.  There are really three
ways for describing lengths: short form, long form, and indeterminate
form.  As far as I know, Motif cheats horribly on this (more on this
below).  Here's how you describe lengths in BER:

\begin{itemlist}
\item If the length $<$ \code{0x80}, then length is contained in one octet.
\begin{figure}[h]
\hskip\leftmargin\includegraphics[scale=1.09]{BER_len1}
\end{figure}
\item If the length $>$ \code{0x80} (but not indeterminate), then the length
octet is defined as \code{0x80} plus the number of octets needed to
describe the length (up to 127 additional octets, so this can describe
lengths up to \( 2^{127\cdot8} \), or \( 2^{1016} \), which is
\emph{really} huge).  The octets describing the length immediately
follow the length octet and come before the value octets.  In practice
(as far as I know), \Motif{} limits this to two additional length
octets, which implies a maximum value length of 65535. Maybe the \CSF{}
once planned to port \Motif{} to M\textdollar{}Windooze\dots
\newpage
\begin{figure}[h]
\hskip\leftmargin\includegraphics[scale=1.09]{BER_len2}
\end{figure}
\item If the length $>$ \( 2^{1016} \), or you are really lazy (like
\Motif{} is), then the length octect contains \code{0x80}, and you're
to parse the value (which contains TLV tuples) until you come to a TLV
whose tag and length are both 0. \Motif{} uses the indeterminate form
only for encoding the first TLV, but never when encoding the subsequent
TLV's.
\begin{figure}[h]
\hskip\leftmargin\includegraphics[scale=1.09]{BER_len3}
\end{figure}
\end{itemlist}

As I said before, \Motif{} is really lazy (what else did you
expect?!). The first header (\code{0xDF 0x80}) should imply that an
\code{XmString} parser should look for a tag and length that are both
0. In practice, Motif strings contain only \emph{one} element in the
value: the \code{XmString}.  I've parsed strings in \Motif{} looking for the
(\code{0x00 0x00}) tag/length, and run off into space. Therefore,
\LessTif{} stops after finding the first \code{XmString} component.
In effect, a length of \code{0x80} in \Motif{} means ``I don't know
how long my value is, but my value is really a TLV, and there's only
one of them''.

Let's look at our example string again, in light of this information:
\begin{table}[h]\begin{center}\begin{tabular}[h]{p{4.5cm}l}
\code{0xDF 0x80} & \code{XmSTRING\_TAG}, \code{XmSTRING\_LENGTH} \\
\ind{1}\code{0x06 0x10} & \ind{1}\code{XmSTRING\_COMPONENT\_XMSTRING}, 16 bytes\\
\ind{2}\code{0x05 0x05} & \ind{2}\code{XmSTRING\_COMPONENT\_LOCALE\_TEXT}, 5 bytes\\
\ind{3}``\code{Hello}'' & \ind{3}``\code{Hello}'' \\
\ind{2}\code{0x04 0x00} & \ind{2}\code{XmSTRING\_COMPONENT\_SEPARATOR}, 0 bytes \\
\ind{3}-- \emph{nothing} -- \\
\ind{2}\code{0x05 0x05} & \ind{2}\code{XmSTRING\_COMPONENT\_LOCALE\_TEXT}, 5 bytes\\
\ind{3}``\code{World}'' & \ind{3}``\code{World}''
\end{tabular}\vspace*{-0.4cm}\end{center}\end{table}

\codeindex{XmSTRING\_COMPONENT\_XMSTRING}%
That should make more sense, now.  Note that the tags 6--125 are said
to be reserved in \Motif{}'s header files; now you should understand
why the value 6 is \code{XmSTRING\_COMPONENT\_XMSTRING} (which doesn't
appear in any Motif header). The length \code{XmSTRING\_LENGTH} is
used within \LessTif{} as a synonym for the indeterminate length value
of \code{0x80}. You'll find its definition in
\code{\textdollar(LESS\-TIF\_ROOT)/libXm/XmString.c}.

\section{Structures}

[Need to explain here why order is important in the strings -- the charsets
MUST come before the strings that use them].

\section{The Other Side of XmStrings}

As you can easily imagine, the ASN.1 representation of a
\code{XmString} isn't very suitable for fast handling, yet saves
memory. Another advantage of a \code{XmString} is that it is
independent of a \code{XmFontList}. Only when you need to know the
height and/or width of a \code{XmString} or want to render it into a
drawable a \code{XmFontList} must be specified so that the individual
string components can be ``connected'' to the fonts from the font
list.

\codeindex{\_XmStringCreate()}%
\codeindex{\_XmStringUpdate()}%
If you need to work many times with a particular \code{XmString} (like
the list widget) it is more convenient to ``compile'' the ASN.1
representation of a \code{XmString} into an internal form -- a
\code{\_XmString}. The individual TLV's from the ASN.1 \code{XmString}
are thereby transformed into string components accessible through
pointers. The compilation is carried out with
\code{\_XmStringCreate()} which takes a \code{XmString} and returns a
\code{\_XmString}. Next after the transformation the references to the
fonts should be resolved -- use \code{\_XmStringUpdate()} for this
task. Lateron, you can update the fonts the (internal)
\code{\_XmString} will use whenever you want by calling
\code{\_XmStringUpdate()}.

A \code{\_XmString} is merely a pointer to a
\code{\_\_XmStringRec}. This structure points to a table of
pointers to the string's components.  In addition the
\code{\_\_XmStringRec} also accounts for the size of that table of pointers
(see figure \ref{XmStringInt_Repr}). As the table of pointers can grow
and shrink whenever the string gets manipulated, it may also move in
memory. Thus the the \code{\_XmString} pointer can't point directly to
the components table but must point to a data structure instead which
stays at the same memory location all the time (well -- at the same
\emph{logical} or \emph{linear} memory location as modern virtual
memory management may move memory blocks at any time around the physical
memory).

In turn the string components are described by
\code{\_\_XmStringCom\-ponentRec}s, which contain the type of a
component (see table \ref{xmstring_tag_ids} on page
\pageref{xmstring_tag_ids}), the com\-ponent's data, its length, and finally
the font to be used. Every \code{\_\_XmStringComponent\-Rec} can thus be
regarded as a TLV converted to a more suitable form to the CPU. The
\code{font} member of the component record is just an index into a
\code{XmFontList}. So be sure to update these indices with
\code{\_XmStringUpdate()} whenever the font list changes which is
used for rendering the \code{\_XmString}.

\begin{figure}[h]
\hskip\leftmargin\includegraphics[scale=1.09]{XmStringInt_Repr}
\caption{\label{XmStringInt_Repr}Internal representation of a ``compiled''
\code{\_XmString}.}
\end{figure}

% End of XmStrings.tex
